Good entropy source for generating openssl keys

First off, using '-rand' is only seeding the OpenSSL RNG. It can be 1 byte or 1 TB. It's only used as a seed to get things started internally. Then, OpenSSL will use the systems entropy to actually generate the primes needed by RSA.

Further, entropy is just a measure of unpredictability in a sequence, not an actual pool of stored bits. The larger the estimation on entropy, the more likely certain things will have unpredictable behaviors, such as a sequence of random numbers.

Again though, the Linux kernel file /proc/sys/kernel/random/entropy_avail is just an estimation. When you have an entropy pool of "4096 bits", this just means that the random numbers being generated have the highest quality of unpredictability you can produce. As the entropy pool estimation drops, the confidence in the sequence of random numbers also drops. When the entropy pool is 0, the kernel will block at generating random data until the pool can be filled again. As you generate random data, it reduces the estimation on entropy. This is the behavior of /dev/random.

In other words, think of the entropy pool as a "crypto thermometer". When the meter is at "full up", the generated numbers will be very difficult, if not near impossible to reproduce, and highly unpredictable. When the meter is completely empty, generating random bits could be reproduced by a 3rd party with little knowledge of the system accurately.

So, getting to your OpenSSL key question. OpenSSL will want the kernel to keep entropy as full as possible. However, OpenSSL will seed from /dev/urandom by default. This device will still exhaust entropy, but rather than block when there is no entropy estimate, it will use a PRNG to generate the rest of the data. Keep the entropy pool filled, and the PRNG will never been utilized.

The /dev/random device on FreeBSD is a strict PRNG, and not a TRNG. As you mentioned, it uses the Yarow algorithm to generate random numbers. However, after generating 2^256 numbers, the cycle repeats, generating the exact same numbers in the exact same order as before, as is the case with all PRNGs. By comparison, /dev/urandom in the Linux kernel uses SHA1, which will generate a total of 2^160 numbers before recycling when the entropy pool is exhausted.

Now, to address your question. You mentioned that you are using haveged(8) with Linux to keep the entropy reserve full. On most systems, haveged(8) is generating about 1 MBps of true random data to the kernel, and using the ioctl() system call to increase the entropy counter. As such, generating your 4096-bit RSA OpenSSL key will have the highest quality of cryptographic strength you could ask for, and adding additional random data from other systems won't increase its strength.

The whole point of the certificate generation is to create random numbers from either your file, or from a random number generator, as noise input into an algorithm to generate very large primes. The trick is getting to those prime numbers. With an entropy pool of 4096 bits, at full up, all the time, as haveged(8) will be providing, the ability of someone to regenerate the same primes, even if they have full knowledge of your system, is highly improbable.

So, in my opinion, run haveged(8) keeping the kernel topped at 4096-bits of entropy, and just generate your certificate there using "-rand /dev/random", rather than generating a file from every system.


Are relatively prime numbers used in RSA

are only prime numbers used in RSA ?

That depends on what is meant by "numbers used in RSA". I'll restrict to a reading of the question where these are $p$ and $q$, with $N=p\,q$ the public modulus in the RSA public key.

That also depends of the defintion of RSA. In the original definition, or when we see $N=p\,q$ in an applied RSA cryptography context, we think of $p$ and $q$ primes, large and randomly seeded, and perhaps deliberately distinct. In this case, $p$ and $q$ are primes. They are distinct either deliberately or with overwhelming probability, and distinct primes are coprime.

In some modern definitions including PKCS#1v2.2, RSA is extended to $N$ the product of $u\ge2$ distinct (odd) primes. In this case, when $u>2$ and if we nevertheless still write $N=p\,q$ (which is highly unusual), then at least one of $p$ or $q$ is not prime, but still $p$ and $q$ are coprime.

On the other hand, from a mathematical standpoint, we can define RSA for any positive $N$: if $\gcd(e,\varphi(N))=1$ then the function $x\mapsto x^e\bmod N$ is a bijection of $\Bbb Z_N^*$, that is of the subset of $x$ in $\Bbb Z_N$ with $\gcd(x,N)=1$. That function is also a bijection in $\Bbb Z_N$ if and only if $N$ is square-free (equivalently, if and only if $p$ and $q$ are coprime in any factorization of $N$ as $N=p\,q$). Whenever pulling a factor out of $N$ is hard, overwhelmingly most elements of $\Bbb Z_N$ belong to $\Bbb Z_N^*$, thus the distinction $N$ square-free or not is immaterial for random $x$ (as used in good practice). In that mathematical definition of RSA, we might have $N=p\,q$ with $p$ and $q$ prime or not, coprime or not. For example for $N=11\cdot16$ we can write $N=p\,q$ with $p=8$ and $q=22$, neither is prime, and they are not coprime. Yet $(N,e=3)$ and $(N,d=7)$ are a valid RSA key pair when we restrict to odd integers in $[0,n)$ for message and ciphertext (we can, but need not, exclude multiples of $11$).

  I understand why RSA is multiplicative when $p$ and $q$ are prime but not when they are relatively prime.

RSA is multiplicative no matter what, in the sense that for all $x_0$ and $x_1$ it holds that $E(x_0\cdot x_1\bmod N)=E(x_0)\cdot E(x_1)\bmod N$  for $E$ the function $x\mapsto x^e\bmod N$. That's because $(x_0\cdot x_1)^e\equiv x_0^e\cdot x_1^e\pmod N$, and that holds for all positive $e$ and $N$, without consideration of $N$ being the product of coprime integers, and from what set $x_0$ and $x_1$ are taken.


Most of the time - the key is not included in the cipher-text. The key needs to be "pre-shared" between the sender and recipient. This is true for symmetric encryption.

Or - the key can be encrypted using the asymmetric encryption. That the sender could encrypt with the recipient's public key (not secret) and only the recipient could decrypt with its private (secret) key.

This is base of the asymmetric encryption. It is very expensive (in performance), so a one-time symetric key is generated and encrypted using the asymmetric encryption. The key is used for symmetric encryption of the payload (of any size). The recipient receives the encrypted symmetric key (what could be retrieved using the private asymmetric key) and then the rest of the payload can be decrypted.


Is 3DES still feasible (in terms of security and performance) to use?

3DES is very slow except if you have specialised hardware, so it at most wins in speed on legacy hardware that has dedicated DES circuitry but no AES circuitry. If no specialised hardware is available, AES or most other modern lightweight ciphers will be significantly faster.

3DES also has a very small block size, meaning it can start leaking data after just a few GB of encrypted data, see also Sweet32. Additionally the 112-bit key is considered to be quite short these days even though technically still sufficient, but it could be too short for e.g. reasonable security against multi-target attacks.

  Is 3DES safe to use in ECB mode?

No block cipher is safe to be used in ECB mode, as you will always see which plaintext blocks appear multiple times. Additionally deterministic encryption (such as when ECB is used) cannot achieve security against chosen-plaintext attacks (a rather weak security notion).

  Every time on giving the same input (plain text) to encrypt via 3DES
  results same output (cipher text). What would the reason be for that?
  For example: Every time I gave input plain text 'wealth' the output
  generated was 'VxDfWEQA'. Or is that even possible?

(3)DES is a deterministic function, so if you give it the same input (that is the same message-key pair) twice you will get the same output twice. Randomness usually is only brought into the picture when using the block cipher. Also note that the probability of getting an ASCII-text ciphertext is $(52/256)^8\approx 0.000002898$.

  If one would want to discourage a company to not to use 3DES with
  cipher mode ECB and padding PKCS7 what would that reason would be and
  why?

See (1) and (3).

  If a company/entity still insists to use 3DES. What configuration
  would be the most suitable to be set for it e.g. cipher mode and
  padding.

EAX or CCM mode or if neither are an option CTR mode with a counting (context-dependent) IV and then a secure message authentication code (MAC) applied on the ciphertext (which is what CCM and EAX do). These modes require no padding.


Propagating CBC insecure Authenticated Encryption

PCBC doesn't offer authentication at all; there is no cryptographic checksum calculated over the ciphertext, and there is no verification part within the algorithm.

The only thing that PCBC offers is error propagation over all subsequent blocks after a changed block in the ciphertext. However, as there is no verification at the end of the decryption, that will just mean that the (padded) plaintext will contain random data. This may result in a padding error, but it is also possible that it does not by pure chance.

Even if you would add a known plaintext at the end then PCBC will allow you to swap blocks of ciphertext in the middle. And if you add a cryptographic checksum before encryption (i.e. verified after decryption) then you may still be vulnerable against certain ECB-style plaintext attacks.

I'm not really sure what the differently sized messages are supposed to do, to be honest. Maybe somebody else knows the precise attack.

Just like any other secure mode of operation you can still use PCBC for authenticated encryption. For instance, you could use it for a PCBC-HMAC encrypt-then-MAC security scheme where the ciphertext is authenticated before decryption is performed.


OpenSSL RSA same plaintext but different ciphertext

The "normal", unmodified RSA (called textbook RSA) is susceptible to some attacks. We need to change it slightly to avoid this problems. The question Definition of Textbook RSA and the Wikipedia lists some possible attacks. In practice a special padding algorithm is used, like the Optimal asymmetric encryption padding (OAEP). The documentation of the RSA_public_encrypt function in OpenSSL shows the possible padding algorithm which can be used.

So yes, OpenSSL adds some random information to the plaintext. Without this, RSA would be deterministic: The same ciphertext would reveal that the plaintext was also identical. If you want to decrypt the ciphertext, then you have to either use OpenSSL again, or remove the padding manually.


Inside the probability brackets, everything on one side of the colon describes the distributions of the variables used to define an event on the other side. In the case you described, the success probability of $A$ is the probability that $y=f_k(x')$ (which is the event) happens for $k,x',y$ sampled/generated from the left-side operations, i.e., sampling a random key $k$ and a random $x$, then computing the output $y=f_k(x)$, and finally giving $k,y$ to the adversary $A$ and getting its output. In English, that means the adversary $A$ wins if and only if it can find a preimage of $f_k(x)$ for random $k,x$, where $k$ is known to $A$.


Secure use-cases of block cipher with 64-bit block size

We can still safely use 64-bit-block ciphers when used in an otherwise sound protocol, and all of the following three conditions are met:

The effective key size is made big enough; that disqualifies DES (55-bit), but not Blowfish (up to 448 bits), TEA (128 bits), 3DES (167 bits), and to some degree 2-keys-3DES (111 bits). Note: I computed the effective key size of DES and variants accounting for unused low-order bits of keys, and the complementation property. Theoretical attacks allowing better-than-brute-force key search for 2-key-3DES are not a practical concern for the time being (except from demonstration of security and certification standpoints).
The number $n$ of blocks that could be used with the same key (legitimately or by an attacker abusing a legitimate device) is low enough to guard against a birthday attack. If we want the maximum odds of the adversary to succeed in this way to be bounded by $2^{-k}$ for some $k>0$, we are safe if we limit $n$ to about $2^{(65-k)/2}$. E.g. if we accept only a one in a million chance than an adversary succeeds by birthday attack, $k\approx 20$, thus we should limit to $2^{22.5}$ blocks; that's only about 45MiB in an encryption application.
The implementations are suitably protected from various side-channel attacks. When the adversary has physical access to the device implementing the block cipher, this often requires further lowering the number of uses of a given key. 3DES is well analyzed in this regard, Blowfish much less so.

A common example of safe use of 3DES is as session keys (for integrity or confidentiality protection) in Smart Card applications, with the amount of data in the session limited, as in this European Regulation (search CSM_021 thru CSM_031 for a description, CSP_301 and CSM_013 for the limitation of the number of blocks).

Update: A small block size worsen some insecure encryption protocols/modes, such as ECB, especially when used with low entropy in the plaintext. Solution is: use secure encryption protocols/modes; there's then no worry about entropy in the plaintext.


Verion of crypto_box() which doesn't allow the sender to decrypt previously sent messages

In order to verify the identity of the sender, the messages needs a signature, that the receiver can verify using the sender's public key.

After encrypting the message with crypto_box_seal(), sign it with crypto_sign().

The receiver can verify the signature and remove it with crypto_sign_open() and then decrypt the rest.

What you suggested also works, but you'll have to implement all the bits yourself.


Can Eve break this public key cryptosystem if she can solve DLP or DHP?

Can Eve break it if she can solve Diffie-Hellman problem?

Yes, at least, the computational Diffie-Hellman problem.  This problem is "given the triplet $h, h^x, h^y$, recover $h^{xy}$"

Let us assume that Eve has an Oracle that solves this problem.  Then, she sets $h=m^{ab}$, $h^x = m^b = (m^{ab})^{a^{-1}}$ and $h^y = m^a = (m^{ab})^{b^{-1}}$, and passes $h, h^x, h^y$ to her Oracle.  The Oracle returns with $h^{xy} = (m^{ab})^{a^{-1}b^{-1}} = m$, problem solved.

And, if she can break the Discrete Log problem, she can solve the CDH problem, so this answers that question as well.

N.B. The protocol you listed is known as the "Shamir Three Pass Protocol", and is currently viewed more as a curiosity rather than something that solves some problem better than other solutions.


Practical necessity of semantic security under chosen plain text attack (CPA) in CBC mode

Repeatedly encrypting the same message to the same ciphertext is full of practical attacks. Encryption is supposed to leak no information about the content of the message other than its length, and there are very real ways to exploit the information leakage you mention. Some of them have to do with the fact that plaintext domains are not always very large. Others have to do with the fact that an attacker who can perform a chosen plaintext attack (CPA) gets to learn a lot about the ciphertext.

Here are some attacks, assuming that we use a CBC-like encryption scheme that is deterministic (and thus not semantically secure):

If the attacker sees the encryption of message A, then later learns message A, he can then know the contents of message A whenever it was sent in the past or the future. That's a very real threat if the total messages that could be sent are reasonably small.

Example: Consider an army that coordinates movement by sending instructions to each other on who is to move where. The attacker might be able to catalog intercepted encrypted communication and then determine what the message meant based on what happened after it was sent. When a duplicate message is intercepted, they will know that what happened the last time the message was sent and thus what is likely to happen this time the message is sent.

Plaintexts that begin the same way will have ciphertexts that begin the same way. Even if two ciphertexts don't match, some prefix of them may match. If they do, knowing the contents of one ciphertext can lead to knowing the beginning of another ciphertext. While this isn't much different than the previous case, it means that the problem is much worse than simply having ciphertexts that are the same, it extends to ciphertexts that begin the same way.

Example: Consider a style of document with a person's (Alice) identifying information at the beginning. Even if two document contents differ, the attacker will still know the documents belong to the same person. If Alice ever sends the attacker one document, he learns how to identify a document encrypted by her. If one of those documents is recovered from another person's (Bob) computer, the attacker learns that Alice likely communicated with Bob. Information about the content of the the document is expected to remain confidential under encryption, failing to do so is a failure for the encryption.

It's also possible that the small domain of the plaintext will pair with the context of the ciphertext and reveal information.

Example: Consider a program like SSH that transmits what a user types, sending small sets of encrypted key strokes at a time. We would have limited number of possible ciphertexts because every key maps to the same ciphertext each time. If every set of messages is stand alone (no ciphertext chaining across gaps in key strokes), then an attacker could use frequency analysis to determine which ciphertext mapped to which keys. They could then do a decent job of learning what the user had typed. It would be even worse if every message were stand-alone, in which case it would be ECB. (In case it wasn't obvious, note that deterministic CBC has a similar taste to ECB.)

The attacker may be able to inject chosen plaintext into a live system and see the resulting ciphertext. (This is a very real attack that we must be able to withstand and motivation for why we consider chosen plaintext attacks.) He can then brute-force decrypt other ciphertext by simply finding plaintext that encrypts to the known ciphertext. The smaller the plaintext domain, the easier this is.

Example: A bank may encrypt the amount of money involved in a transaction in one block of the ciphertext. The attacker may be able to conduct his own transactions and determine what numbers encrypt to what ciphertexts, then be able to learn about other ciphertexts.

(Obviously, the specific players in those examples are arbitrary, you could swap them out for any number of other situations.)

The main problem is that we don't know how messages are going to be formatted and what kind of content it will contain, and it's very possible to pick formatting and content that will leak information through the encrypted ciphertext. Encryption is supposed to do it's job of protecting all information you give it, and leaving some edge cases vulnerable and telling the user that they're only secure if they take extra precautions to avoid those edge cases isn't acceptable. Nobody wants to use something that is insecure for edge case (especially not when there's the option of eliminating those edge case vulnerabilities). It would be like your house being stable for everything, except if you slam the bathroom door the kitchen ceiling falls in. Who'd want that?


How often is Ratchet key pair changed in signal protocol?

First, how often is a new DH ratchet key is decided by the implementation.
Alice will trigger a DH ratchet step when she receives a new public key in the header of the message sent by bob (section 4.1 of double ratchet specification[0] goes into the detail of it). In this case, B2's header did not have a new public key, while B3 and B4 do.
Coming to your question, It doesn't matter if A2 had a new key or not. Why? Because this protocol allows for messages to arrive with old keys. Think of the case where Alice's message is not delivered but bob keeps sending message(s).
[0] https://signal.org/docs/specifications/doubleratchet/


Is this a UC-secure commitment scheme in the ROM?

No, your construction is insecure, specifically it fails to be hiding. A receiver who has a guess of $M$ can simply check whether $H(M)=c$ since $H$ is public. You can see that your suggested simulation strategy fails when the adversary has already queried $H$ on $M$ before the simulator learns that the commitment should hold $M$. The argument to $H$ should have high entropy even conditioned on a correct guess of $M$. Change the construction to $H(M\|r)$ for long random $r$ and you have the standard folklore commitment in the random oracle model.
Naively using a random oracle in the UC model is kind of like cheating. You get a totally independent random oracle for each protocol instance. It's not a great model for a supposedly public object. Those papers you reference try to use a random oracle in a less "cheaty" way, so their protocols have to work harder. Also at least the first paper avoids having the simulator program the oracle's outputs (non-programmable random oracle model) which is often seen as more palatable.


What's the definition of the width of a circuit

The width of a circuit is in some sense related to concept of circuit depth which you appear to already be familiar with. To understand these concepts it is very helpful to think about the graphic representation of circuits in the form of circuit diagrams. I drew an example of such a diagram here:

The depth of a circuit is loosely speaking the number of layers we can partition the circuit into so all gates in layer $i$ can be evaluated if we have the output of all gates in layers $0,\ldots,i-1$. The diagram above is a circuit with three layers, i.e., the circuit has depth three.

On the other hand, the width of the circuit is then the number of gates in the layer with the most gates. So in the example diagram the width is also three because the top layer has three gates.

In the field of secure computation (including Yao circuits) the width of the circuit is typically interesting because it says something about how parallelizable the evaluation of a circuit is. I.e., circuits with wide layers parallelize better.


What's wrong with XOR encryption with hash and an iterated salt

Assuming that:

the functions $F_k(s) = {\rm hash}(k + s)$ form a pseudorandom function family (PRF) indexed by the key $k$, and
each key is only used to encrypt one message,

then this construction is provably1 secure against chosen-plaintext attacks.

Being a PRF is not a standard property of a cryptographic hash function, so one cannot just assume that any given secure hash function will satisfy it.  A "perfect hash" (i.e. a random oracle) would indeed yield a PRF when used in this manner, but some real-world hash functions might have weaknesses that using them in this way could expose.

Fortunately, however, there's a standard way of converting a hash function into a PRF, called HMAC.2  Thus, you could fix this part of your scheme by using ${\rm HMAC}_{\rm hash}(k; s)$ instead of ${\rm hash}(k + s)$.  Or just use a hash function that does claim to be a PRF when used this way.3

As for encrypting multiple messages, the problem is that, as cygnusv notes, XORing two ciphertexts encrypted with the same key would cancel out the hash outputs, yielding the XOR of the corresponding plaintexts.  If one of the plaintexts is known to the attacker, they can then trivially recover the other.

This limitation would be easily fixed by picking a unique nonce string $n$ for each message and including it in the hash input, e.g. as ${\rm hash}(k + n + s)$ or ${\rm HMAC}_{\rm hash}(k; n + s)$.  Of course, the nonce would have to be stored / transmitted alongside the ciphertext, so that it can be decrypted.

(Also, to avoid attacks due to the ambiguity of concatenation, at least two of $k$, $n$ and $s$ should have a a fixed length; otherwise, it would be possible for e.g. $k = \text{"xyz"}$, $n = \text{"123"}$, $s = \text{"4"}$ to yield the same hash input as $k = \text{"xyz"}$, $n = \text{"12"}$, $s = \text{"34"}$ or $k = \text{"xyz1"}$, $n = \text{"23"}$, $s = \text{"4"}$.  Or you could simply replace the concatenation with some less ambiguous encoding.)

1) The proof is essentially the same as that used to prove the IND-CPA security of CTR mode encryption, except that we don't need the PRP/PRF switching lemma since we already have a PRF, and the requirement that only a single message can be encrypted obviously requires some modification to the IND-CPA game to keep it non-trivial.  A natural choice would be to allow the adversary online access to the encryption oracle, i.e. the ability to submit individual blocks of plaintext, which the oracle will encrypt as successive parts of a single message stream and immediately return to the adversary.

2) Strictly speaking, the standard security proof of HMAC only applies to certain types of hash functions, known as Merkle-Damgård hashes, and only with certain specific assumptions on their internal operation.  That said, most traditional hashes (including SHA-1 and SHA-2) are of the Merkle-Damgård type, and most newer hashes like SHA-3 are explicitly claimed to be secure when used in HMAC, even if they don't use the Merkle-Damgård construction.

3) Off the top of my head, I believe SHA-3 / Keccak effectively makes this claim, via its "flat sponge claim"; of course, if you're using Keccak anyway, it would be even easier to just use its variable-length output, standardized as SHAKE128/256, to generate enough bits to encrypt the whole message from a single hash input.


When to use /dev/random over /dev/urandom in Linux

In which practical situations would one want to use /dev/random in preference to /dev/urandom, and why?

Basically none on a typical desktop or server system. Assuming the PRNG produces cryptographically secure random numbers, there is no reason to use /dev/random instead.

There are a couple of corner cases, however:

You use the random numbers for a one-time pad. In that case if you wanted information theoretic security you should not use pseudorandom numbers. (No real reason to do that in my opinion.)
Early boot on a very low entropy device. The /dev/urandom device cannot guarantee that it has received enough initial entropy, while when using /dev/random that is guaranteed (even if it may block). However, in this case you could use the newer getrandom interface (man page) instead.

Running cryptsetup on first boot of an embedded device is the kind of thing where you would need to consider your options. (Modern desktop and server CPUs tend to include hardware random number generators which are used to seed /dev/urandom.)

There is some work underway to make /dev/urandom block when initial entropy is insufficient, but it may not be possible due to programs which assume it will never block. (See e.g. this LKML thread.)


How does order-preserving encryption work?

In the last couple weeks I've become pretty well-acquainted with the recent work in this area. I also built a prototype order-preserving encryption scheme following the algorithms presented in 'Order-preserving Symmetric Encryption' by Boldyreva et al. I'll take a stab at explaining the method I just implemented, which requires some understanding of discrete probability and the hypergeometric distribution.

Let $M$ and $N$ be two positive integers such that $M < N$. Start by considering a random order-preserving injective function from $[M]$ to $[N]$, where $[M] = \{1, 2, ... , M\}$ and $[N] = \{1, 2, ... , N\}$. Now, choose $M$ elements of $[N]$ randomly and put them in order. Our injective function $f:[M] \to [N]$ is simply this ordered set. To encrypt $i \in [M]$, just output the $i$-th element of this list. Obviously we can't use this as a real encryption scheme, we might need to randomly generate billions of numbers! So how do we proceed?

We proceed by noticing that we don't need the whole function in advance. If we could figure out a way to only generate an element of the ordered set when we need it as a ciphertext, we'd be hunky dory. This is called lazily sampling the function. To lazily sample our proposed function, we first need to look at the range space a bit differently.

Let's stick with our random order-preserving injective function $f$, which we're thinking of as an ordered list of elements of the range. Think of an element of the range as 'marked' if it's in the list and 'unmarked' if it's not. Now think of all the elements of the range, marked and unmarked, as being balls in a giant bin. If we draw balls without replacement, the number $x$ of 'marked' balls we've drawn after $y$ samples can be characterized by the hypergeometric distribution. The HGD has PMF $$\frac{\binom{y}{x} \binom{N-y}{M-x}}{\binom{N}{M}}$$
If you don't know what a PMF is, don't sweat it. All we really need to understand is the connection between OPFs and the HGD, which is that we can figure out how many points of our OPF lie below a given point of the range by treating the range point as the number of 'samples' in a hypergeometric experiment where the number of marked balls is $M$ and unmarked balls is $N-M$.

Also important to know is that we can efficiently and deterministically sample the HGD, i.e. given $y$, $M$, $N$, and some random coins $cc$ we can always generate an $x$ that describes the number of marked balls in our sample of size $y$.

We're close, I promise. We have the groundwork laid, we just need to figure out how to get an encryption scheme out of this.

Our encryption scheme follows fairly naturally from the above. Given a plaintext $m \in [M]$ and a key $k$ we can lazily sample our OPF and produce a ciphertext $n \in [N]$ by recursively searching the domain and range like so:

Start with the entire domain $[M]$ and range $[N]$. Call $y \leftarrow \frac{N}{2}$ our range gap. Now using our key $k$ we generate some pseudorandom coins and give them to our HGD sampling routine along with $y$, $M$, and $N$. This gives us an $x \le y$ that describes the number of points of our order-preserving function less than $y$. Call this $x$ our domain gap. Now because the $m$-th point of our OPF is the ciphertext of $m$, we know that if $m \lt x$ we need to recur on the points of the domain less than or equal to $x$ and less than or equal to $y$. If $x \lt m$, we recur on the points of the domain greater than $x$ and $y$. When our domain only has one point remaining, we'll have as our range a set of points in which our ciphertext can reside. Pick a point of this set and output it.

So after all that, it's just a fancy binary search??? Kinda, yeah. If you want to know all the messy details and how to actually make it secure, read the original OPE paper or look at the CryptDB implementation. My java implementation will also be open-sourced sometime soon, so you might check that out as well.

Order-preserving encryption has several caveats. To know all the details, read the follow-up of Alexandra Boldyreva, Nathan Chenette and Adam O'Neill's Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions (in proceedings of CRYPTO 2011, or full paper here). It analyzes the security of a random OPF and characterizes its leakages. Their most glaringly problematic result has to do with an adversary's ability to guess approximately where the underlying plaintext of a ciphertext lives in the plaintext space. Intuitively, it says that certain attackers can learn half the bits of a plaintext given its ciphertext. For certain applications this trade of security for functionality is acceptable, but in any case it's important to know what you're getting when you use these schemes.

Post a comment if you want something clarified in the above, I'll try to make a cogent edit.


Order Preserving Encryption for Numeric Data Values

To answer your second question, Paillier and other CPA-secure homomorphic encryption schemes cannot provide order-preserving encryption. The security of these schemes rely on using a random factor during encryption to ensure their ciphertexts are distributed randomly in the ciphertext space. OPE must use a weaker notion of security than CPA.

In terms of your first question, I don't know enough about the data structure behind OPE to follow what you are asking. I know OPE is an available option in CryptDB so maybe they have automated the process of defining the limits you are asking about?


The small key-search circuit for brute-force of Bernstein

The crucial part is not just the definition of $Z$, which is a random walk in possible keys.  It's also how you use it, on the next page:

Search for $Z(\beta, 2^{23}, r_j)$ among $Z(\beta, 0, H(k_i)),$ $Z(\beta, 1, H(k_i)),$ $Z(\beta, 2, H(k_i)),$ $\dots,$ $Z(\beta, 2^{23} - 1, H(k_i))$.
If you find that $Z(\beta, 2^{23}, r_j) = Z(\beta, \ell, H(k_i))$, then you have a candidate trail to follow!
In this case, start over computing $Z(\beta, 2^{23}, r_j)$, but only go $2^{23} - \ell - 1$ steps until the state $(\beta, \ell + 1, s)$ rather than all the way down to $(\beta, 0, s')$.
If $H(s \oplus (\beta, \ell)) = H(k_i)$, you've found a candidate for $k_i$, namely $s \oplus (\beta, \ell)$.

One way to look at it is as follows: The function $H$ (e.g., $k \mapsto \operatorname{AES}_k(18238)$) represents a directed graph where each node $k$ has exactly one successor $H(k)$.  Imagine the graph as a network of rivers on a terrain.  They're not all connected, but they flow in only one direction.

You're teleported onto a node in the middle of a river, and you're trying to find the node just behind you, but you can't look there.
You shoot out a scattershot of cheap drones.  They will record the node where they landed, and then flow down the river exactly $2^{23}$ steps before stopping and embedding themselves in the river bed.
You go to sleep for the night.  In the morning, you trawl down the river looking for a drone.  If you find one after $\ell$ steps, you go to the point where it started and move forward by $2^{23} - \ell - 1$ steps, and see if the next one is the node you were sitting on at the beginning.

Of course, the drone you find could have come down a different tributary of the river, so you might have to retry with another drone.

This is the rough idea: the model breaks down because rivers are never cyclic, and the advantage comes either from (a) precomputing where the drones landed (as in precomputed rainbow tables) so that you can save effort by reusing them for many trawlings, or (b) simultaneously trawling and shooting out drones in parallel, and then searching for a collision by sorting the nodes where the drones landed together with the nodes you trawled through.


RC4 , Is it possible to find the key if we know the plaintext and ciphertext?

No, to the best of our knowledge, it is not possible, apart from a brute force search over all possible keys.  RC4 has known cryptographical weaknesses; however, none of them are of much help in recovering the key, given a plaintext/ciphertext pair.

There are backtracking approaches that might take circa $2^{700}$ effort independent of the key size; however that is impractically huge (and unless the key is huge, a brute force search is still simpler)

On the other hand, if you have two ciphertexts encrypted with the same RC4 key, and you know the plaintext for one of the ciphertexts, it's easy to recover the other plaintext.  All you need to do is compute the exclusive-or of the two ciphertexts, and the known plaintext -- the result will be the unknown plaintext.

This works because RC4 takes the key, and using that, generates a long string of bytes (the keystream).  RC4 then takes the keystream, and exclusive-or's that with the plaintext, generating the ciphertext.  That is, if $P_i$ is byte $i$ of the plaintext, and $C_i$ is byte $i$ of the ciphertext, and $RC4_i(key)$ is byte $i$ of the keystream generated by the key, then:

$$C_i = P_i \oplus RC4_i(key)$$

If we have a second plaintext $P'$ and ciphertext $C'$ that is encrypted with the same key, we then have:

$$C'_i = P'_i \oplus RC4_i(key)$$

Combining them, we have:

$$P_i = P'_i \oplus C_i \oplus C'_i$$

Now, we can recover the values of $RC4_i(key)$, however there's no known way to recover $key$ from that.  However, if all you want to know is the plaintext $P$, you don't need the key.

Of course, if $P$ (the unknown plaintext) is longer than $P'$ (the known plaintext), this trick will reveal only the first part of $P$.

In addition, even if you don't know the value of $P'$, a similar trick will allow you to compute be value of $P \oplus P'$ - depending on what the plaintext is, that is often sufficient to allow an attacker to deduce the original values of $P, P'$.  Hence, it is always a mistake to RC4 encrypt two different things with the exact same key.


What are sources for the performance difference in asymmetric and symmetric encryption?

There are three different possible things you are asking for:

Concrete stats and numbers from a benchmark
Analysis of the algorithms in terms of bit operations required
Proof that asymmetric encryption must be more expensive than symmetric encryption

Benchmarks

If you're just looking for actual stats and numbers, there are the SUPERCOP/eBATS benchmarks.

You can also investigate the command openssl speed.

Bit operations

If you're looking for a theoretical analysis of the number bit operations used by asymmetric encryption compared to the number of bit operations used by symmetric encryption, that may be harder to come by in the form of a single paper. You'd need to do an analysis of the number of bit operations of all the relevant $\operatorname{encrypt}$ function (which may be different than the $\operatorname{decrypt}$ function).

For symmetric algorithms, the introductory paper(s) will typically provide a measure in cycles per byte. But cycles per byte are a feature of architecture and implementation, not intrinsic to the abstract algorithm, and so are not useful here.

You would need to know which algorithm is being used to implement the required function. For example, with modular exponentiation the naive algorithms of multiplying $g$ times itself $x$ times will have a drastically different number of bit operations compared to using the square and multiply algorithm.

And on that note, you would also need to know the most optimal algorithm for implementing each functionality to conclusively say that algorithm $A$ requires more bit operations than algorithm $B$. That could prove to be a challenge at the very least, and maybe even prohibitive in the worst case.

Proof it must be this way

If you're looking for a proof that says asymmetric encryption must be slower than symmetric encryption, then I doubt such a result exists.

There is a paper that shows that (secure) key exchange in the random oracle model is impossible.

One supporting argument might Diffie-Hellman and the discrete logarithm problem. There are generic attacks against the discrete logarithm problem which place a minimum on the size of the used group, which consequently raise the cost of using the algorithm.

However, DH is not public-key encryption, it is key agreement, and it is only a single algorithm, so it certainly does not qualify as proof that all asymmetric encryption must be slower than symmetric encryption.

On a related note, in general, asymmetric algorithms (discounting hash-based signatures) have structure, whereas symmetric algorithms (typically) do not. This structure appears to contribute to an increase in the amount of space required to use such algorithms, which again contributes to an increase in the amount of time required to use such algorithms. However, this is again not proof that it must be this way.


Triple DES (Wikipedia) is simply DES used three times, usually ciphertext = E(k3,D(k2,E(k1,plaintext))), although I have seen other arrangements such as E(k1,E(k2,E(K3,plaintext).  So just split the 3-DES key into three (sometimes two) parts k1, k2, and k3, and run 1-DES three times, using the appropriate key each time.

So, for example, if my 3-DES key is aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbcccccccccccccccc (hex), then the 1-DES keys would typically be aaaaaaaaaaaaaaaa, bbbbbbbbbbbbbbbb, and cccccccccccccccc, with the system documentation letting us know which one is k1, k2, and k3.  So assuming we encrypted using ciphertext = E(k3,D(k2,E(k1,plaintext))), then we can decrypt using 1-DES as follows:

temp1 = D(k3,ciphertext)
temp2 = E(k2,temp1)
plaintext = D(k1,temp2)

And of course if we are using something like Cipher Block Chaining, the whole sequence above would be considered one block cipher decryption.

Edit:
1. If only two keys are used (the ABA mentioned in the comments), the general approach is the same, except instead of having a separate k3, we just set k3=k1 and do the same as before.

Just to be clear, E(k,p) is enciphering the plaintext p using the key k, and D(k,c) is decrypting the ciphertext c using the key k.  For this example, we are using plain DES for both E() and D().


IMO implementing RSA yourself is a bad idea. While textbook signing is pretty easy, if you have access to a BigInteger class, you also need to get the padding right. In some use-cases timing attacks are also a problem.

But if you want to go that route, PKCS #1 is the standard you need to implement. It details how the padding should look like.

The text-book RSA signing operation is pretty easy, in principle. Just calculate $m^d \mod n$. Unfortunately without correct use of hashing and padding it's very insecure i.e. you can't use the actual message as $m$, but the padded hash of the message.

I'd look into mono's crypto code. They have purely managed implementations of most .net crypto classes. These should work even if you don't have access to the built in classes.

A few interesting looking classes:

All classes related to RSA in System.Security.Cryptography
RSAManaged

They use the MIT X11 license, which is a permissive open source license.


Differential Privacy: is the bound for group privacy tight?

Yes, this bound is tight.
The optimal partition selection mechanism introduced in this paper achieves the bound: every step "uses up" all the $(\varepsilon,\delta)$ budget available, and for the particular case of $k=2$, the probability of releasing the partition is exactly $(1+e^\varepsilon)\delta$, while this probability is $0$ for $k=0$. The recurrence relationship gives you a tight bound for any $k$.
(Disclaimer: I'm one of the authors of this paper.)


How to protect against ephemeral key reuse in some signature schemes?

Would you say: the probability of mass life extinction on earth caused by asteroid impact is like $2^{-28}$/year; but the risk is so big that I think it's worth taking some countermeasure?

The applied cryptographer's position is that below a certain probability, like $2^{-40}$ lower than mass life extinction on earth, there's no need to mitigate the risk. It is best to spend effort on countermeasures against a stuck TRNG, by accident or attack.


For me it is not obvous, why encryption of (A+P) --> (C+T) followed by decyption gives again P and the same Tag T...

Actually, the reason both sides get the same T is quite simple; GCM defines the tag as a function of the key, the nonce, the AAD (additional associated data) and the ciphertext.  This function happens to be something along the lines of "form a polynomial in $GF(2^{128})$ from the AAD and the ciphertext, evaluate that polynomial on a value $H$ which is a function of the key, and then add in an encryption of the nonce", however the details really aren't important for this question; what's important is that it is a determanistic function of those four things and nothing else.

When the encryptor produces the ciphertext, he computes this function (using his copy of the key, nonce and AAD), generating the tag.

When the decryptor receives the ciphertext, he also computes the function.  If the ciphertext was the same (that is, not modified in transit), and the nonce, AAD and the keys are also the same, then he'll compute the same tag (as he does the same function with the same inputs).


Use of crypto on QR codes for access control

The question is about using digital signature for signing access-control 2D-barcodes.

In the simplest form, some authority will generate and hold a private key, with the corresponding public key stored in the access control systems. A message with access rights (e.g. time interval and location for authorized access) will get signed by the authority using the private key, and encoded with (or in) the signature as a 2D-barcode. The access control system reads the 2D-barcode, thus obtaining the message and signature. It then verifies the signature against the message and the public key (that's the signature verification step of digital signature), and (only if the verification succeeds) allows access or not according to the access rights in the message.

It is cryptographically impossible to make an acceptable 2D-barcode without knowing the private key, other than by duplicating verbatim the content (message and matching signature) of a known one. In particular, any attempt at the alteration of a message will cause the signature verification to fail, and access won't be granted. This is obtained with a purely local verification process, as could be carried by almost any CPU.

The use of digital signature starts to make sense when the access control system is distributed: even reverse-engineering a device can't let one make a forged 2D-barcode that gets accepted. That's because the reverse-engineering can not get at the private key, for it's not there.

Among the most common signature standards usable (and routinely used) for this application are DSA, ECDSA, and EdDSA. The signature will add like 64 bytes for 128-bit security. A Raspberry Pi is powerful enough to perform an ECDSA or EdDSA signature verification step in a small fraction of a second.

If we want to make the size overhead incurred by signing as small as possible¹ (because the less information in a 2D-barcode, the easiest it is to read), there is also the short/original Schnorr signature scheme (48-byte for 128-bit security), but AFAIK it is not standardized². There also are BLS signature schemes, but good luck figuring out safe parameters, and I'm not even sure there's any gain.

Digital signature with message recovery could help a little: it embeds some of the messages in the signature. For short messages (below about 192 bytes) the best standard such schemes are the DLP based ones³, which achieve about the same size overhead as the aforementioned Schnorr scheme, with a better security justification and a standard to boast. For larger messages, an RSA/Rabin based scheme⁴ lowers the overhead to 34 bytes, and also greatly reduce the computational overhead of verifying a signature.

An obvious issue with the system is that signed 2D-barcode can still be duplicated, including captured as screenshots and sent electronically.

Notes:

¹ Of course the message size should be as low as possible. The best is using a compact encoding, or when that's not possible after-the-fact data compression to compensate for a lousy encoding. That's independent of crypto.

² Perhaps because simple security arguments for short Schnorr signature are not rigorous, and the latest developments are complex to the point of being hard to interpret.

³ Some standards are ISO/IEC 9796-3 and X9.92-1, see this for bibliography; beware of the patent minefield.

⁴ ISO/IEC 9796-2 scheme 3. It is not patent-encumbered AFAIK, but the standard itself is not legally available online for free.


Envelope Encryption with asymmetric keys vs KMS

It's all about where you store the secret and who has access to it.

First a clarification: You are confused. KMS does not use asymmetric encryption (also called Public-Key encryption).  It uses private key encryption to enable envelope encryption.  They are two different things.

In asymmetric encryption the producer of the encryption never has to access the secret, they just need the public key.  The producer uses the public key to encrypt, the consumer uses the corresponding private key to decrypt.  In order to facilitate key rotation the producer sometimes appends the public key that was used to encrypt so that the consumer knows what private key to use to decrypt.
No matter how much data is encrypted there are no hints at the private key.  The algorithm for decryption is usually more compute intensive than private key encryption.

In envelope encryption the producer and the consumer must be the same (or both have access to the master key). You use a master key to generate a secondary key called a data key.  You then encrypt the data key using the master key and the data itself using the data key, then you append the encrypted data key to the encrypted data.  When you decrypt you use the master key to decrypt the appended data key, then use the decrypted data key to decrypt the data.

The advantage of this is that you can cost effectively store your master key in purpose build Hardware Security Module and never expose it to anything else without having to pass all the data you encrypt into the HSM.  You can even generate the key inside the HSM and not take it out so that there's no chance that it has ever been exposed to anything externally.  KMS provides you with a cloud based HSM and it's backed by physical HSMs at Amazon.

If you don't care about keeping your master key in an HSM, then you can do the same kind of encryption using your own key that you try to keep safe by putting in on a jump server or something like that.  Also as long as you aren't encrypting more than 250 million TB you can skip the envelope.

If you're looking for some example code you can snatch up to implement either simple AES encryption or envelope encryption you might want to check our open-source project.  It's got an implementation for each you can leverage...

https://github.com/kunai-consulting/KeyStor


Composing two one-way functions such that the result is not a one-way function

The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$).  For convenience, let me quote that answer here:

Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$
From this function, we now construct a new function
$$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows:
$$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$
where $|x_1|=|x_2|=n/2$.

As shown in Maeher's answer, $f$ is one-way if $h$ is.  However, $f(f(x)) = 0^{n/2}\Vert h(0^{n/2})$ is constant, independently of $x$ (except for its length $n$), and thus finding pre-images is trivial.


For the symmetric-key encryption algorithm, is it possible to use the exponent and modulo to be the keys

I don't think 'mod' can be reversed, so it is not possible.
Consider k1 = 2, k2 = 6.
Now,
M = 1 => C (ciphertext) = 1.
M = 5 => C = 1

You have no way of knowing whether the cleartext was 1 or 5, as you get the same ciphertext for both.


To encode the signature you first have to parse the ASN.1 structure also shown in the linked answers provided by dave_thomson_085. Once you have got two integer in the programming language / runtime of your choice then you need to encode them as two statically sized integer encodings. These integers (usually) need to be big endian / network order, unsigned integers.

To do this you need to implement a function called I2OSP from the RSA specifications. You feed this the two numbers and the key size (the size of the order of the curve) rounded upwards to bytes (that's $192 / 8 = 24$ bytes).

There are two ways to do this:

directly implement the mathematical functions and concatenate the resulting bytes or
encode the integer back to bytes - most platforms have a function for this - and then adjust the encoding by padding and possibly reversing the encoding

The latter is probably faster as it just requires byte operations. I usually opt for the latter, but I've seen many cryptographers (naively, in my opinion) do the first.

Finally you simply concatenate the numbers and presto - you're done (there is also OS2IP in RSA, in case you need to do the reverse).


HMAC-SHA256 vs HMAC-SHA512 for JWT API authentication

Both algorithms provide plenty of security, near the output size of the hash. So even though HMAC-512 will be stronger, the difference is inconsequential. If this ever breaks it is because the algorithm itself is broken and as both hash algorithms are related, it is likely that both would be in trouble. However, no such attack is known and the HMAC construct itself appears to be very strong indeed.

SHA-512 is indeed faster than SHA-256 on 64 bit machines. It may be that the overhead provided by the block size of SHA-512 is detrimental to HMAC-ing short length message sizes. But you can speedup larger messages sizes using HMAC-SHA-512 for sure. Then again, SHA-256 is plenty fast itself, and is faster on 32 bit and lower machines, so I'd go for HMAC-SHA-256 if lower end machines could be involved.

Note that newer x86 processors also contain SHA-1 and SHA-256 accelerator hardware, so that may shift the speed advantage back into SHA-256's favor compared to SHA-512.


"Safe" or Safest Method for Non-Hardened Key Derivation Functionality

There needs to be a way to prove that any one of those keys is derived from the master key. In this scenario, the private and the public keys of all of the derived keys can be considered common knowledge and can be used in that verification process.

The following seems to mach that requirement (as I understand it), and the additional one that private keys embed an identifier (that could be the Common Name or/and Certificate Serial Number of a certificate of the derived private key).

The master key is for a deterministic signature scheme with total message recovery with no place for a side-channel (that is: verification of a signature does not require the message, which is recovered as part of the signature verification; and it is impossible for anyone, including holding the master private key, to exhibit two different valid signatures for the same message).
Derived keys are for an (e.g. signature) scheme with the properties that:

a private key can be any signature per the master key scheme;
the public key is a public function of the private key;
it's impossible to turn a private key into a different private key yielding signatures that verify against the unmodified derived public key.

The master key signature scheme can be RSA-4096 per ISO/IEC 9796-2 mode 3, SHA-512 hash for signature and MGF1, trailer field option 1, non-alternative signature, which embeds any message up to 446-byte in a 512-byte signature.
We enforce that at least one bit is zero in the high-order 66 bits of the 4096-bit master key public modulus (though not the highest order bit), so that the signature codes an integer in range $[2,2^{4095}-2^{4029})$, making it suitable as private key for the scheme below.

The derived key signature scheme can be Schnorr signature (per Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991) with SHA-512 hash (and missing details), in the 4096-bit MODP group of RFC 2526.

The 4096-bit MODP group has internal law the integer multiplication modulo prime $p=2^{4096}-2^{4032}+2^{64}\left(\lfloor2^{3966}\pi\rfloor+240904\right)-1$. It is generated by $\alpha=2$, hence is precisely the set of all $2^k\bmod p$ for integer $k$. It has order the (Sophie Germain) prime $q=(p-1)/2$. Private key $s$ is any integer in $[0,q)$, expressed as 512 bytes. Public key is $v=2^{q-s}\bmod p$, expressed as 512 bytes.

To generate a derived key pair, we sign an identifier with the master private key, yielding the derived private key; and from that compute the derived public key. The two are paired by a public relation ($v=2^{q-s}\bmod p$ in Schnoor signature) hence the derived public key can't be changed without changing the private key. Security properties of the master signature scheme protect against forged private keys. There can't be two derived keys with the same identifier, even if the master private key was misused.

  any way to prove that derived keys could only have come from one master key pair, without exposing that master key pair's private key?

To check a derived key pair, we verify its public key against its private key (which is easy with Schnorr signature), check that the alleged private key verifies as a signature against the master public key, and get the identifier in the process (which perhaps can be checked against an alleged public key certificate).


As many of the other answers have said the proposed method above is only as strong as the weakest cipher used (this is especially dangerous if the same key is used for all the ciphers).

Furthermore, basing the cipher transitions on the plaintext opens up the door to a range of timing side-channel attacks if any of the ciphers are faster or slower that each other.

One way you could guard against cryptanalytic breakthroughs is to use secret sharing to split a message $m$ into $n$ plaintexts ($p_i$) that must be combined to recover the original message.
$$ m = p_0 \oplus p1 ... \oplus p_n $$
These $n$ plaintexts could then be enciphered by $n$ ciphers.

$$ciphertext = cipher_0(key_0, p_0)|cipher_1(key_1, p_1) ... |cipher_n(key_n, p_n)$$

The size of the ciphertext increases with the number of ciphers (size of message $\times n$), but you could ensure that even if $n-1$ of the ciphers were broken the message would remain secret. This also requires $n$ keys.

One could try some sort of key expander to expand a $key$ to a different key for each cipher:

$$key_0 = cipher_0(cipher_1( ... cipher_n(key, key)), cipher_1( ... cipher_n(key, key)))$$
$$key_1 = cipher_n(cipher_0( ... cipher_{n-1}(key, key)), cipher_0( ... cipher_{n-1}(key, key)))$$

but I don't have much faith its security (theoretically it is probably as weak as it's weakest cipher) and when one is so concerned with cryptanalytic breakthrough it would be foolish to introduce a "trusted" key expander (why not then introduce a trusted cipher and use that). I have asked the key expander issue as a separate question ( Designing a key expander out of ciphers ).


Trapdoor committement using ring lattices involving three parties

I think that this is just a digital signature scheme. $A$ should generate a private signing key and a public verification key for your signature scheme of choice. The then create a signature for the message $m$ and which you are calling the commitment $c(m)$. $B$ can then pass on the $c(m)$ to $C$ who can confirm that is is signed by $A$, but $B$ cannot produce signatures for other messages that verify using $A$'s verification key.
There are several lattice-based signature schemes though they are all quite tricky to parameterise and implement securely. The NIST competition has advanced the lattice-based signatures FALCON and Crystals DILITHIUM to the final round.


How to convert projective to jacobian co-ordinate in ECC?

If the question is how to take a point in projective coordinates (a triplet $(A,B,C)$, where the corresponding affine coordinate is $(AC^{-1}, BC^{-1})$), and you want to convert it into the same point in Jacobian coordinates $(D, E, F)$ (where the affine coordinate is $(DF^{-2}, EF^{-3})$), I believe this works:

$$D = AC$$

$$E = BC^2$$

$$F = C$$

We can easily see that $DF^{-2} = AC^{-1}$ and $EF^{-3} = BC^{-1}$, hence $(D,E,F)$ refers to the same point as the original, and this conversion takes only three multiplies.


Computing the powers of hash (ripemd-160) function

The only way to do so with cryptographically secure hashes is to perform the actual computations... (i.e. this is not a feature any hash propose to the extent of my knowledge, nor will likely propose in the future.)

But this is not practically possible since if you were to perform such a feat, then you'd be able to perform a brute force collision search attack on a 200-bit hash... Since Ripemd-160 is only 160 bits, the complexity of such a brute force attack is only $2^{80}$ (without any optimization). This means that you would exceed the computing power needed for it.

For reference, SHA-1 was broken after a whooping $2^{63}$ operations, and it took the equivalent of 6,500 years of single-CPU computations or 110 years of single-GPU computations.


Format of NONCE in Initialization Vector (IV)

No. In the context of the Initialization Vector of a cipher operated in some mode, the most significant property of a cryptographic nonce is that it is not reused. It often matters that it is random and unpredictable (e.g. with CBC). It is immaterial that it represents a number or anything else under some particular encoding.

If an IV is chosen at random, it would be bad to restrict it to represent a number (say, restricting each byte to be a digit according to ASCII), in particular because it would dramatically increases the odds of reusing the same IV.


A PRNG has an internal finite state. The value of that state determines all subsequent outputs; that's the point of the PRNG being a deterministic engine. Whenever the PRNG produces a new output element, its internal state evolves into a new value. Since the internal state is finite in size, it is a mathematical certainty that the PRNG, at some points, enters a cycle and never leaves it.

The details are worth analysing:

The PRNG will enter a cycle, not necessarily start on the cycle. For instance, if the PRNG state $S$ has size $n$ bits, and, when the PRNG outputs an element, the state $S$ is replaced with $h(S)$ for some hash function $h$ with an output of $n$ bits, then, on average, the cycle will be reached after about $2^{n/2}$ steps, and the cycle length will also be about $2^{n/2}$. You won't get back to the initial state.
This is about the internal state, not the output. If you get at some point output element $x$, then later on obtain $x$ again, then you did not necessarily completed or even entered a cycle, because two distinct internal state values may yield the same output element.
In practice, for a cryptographically secure PRNG, the cycle cannot be completed or even reached, it is way too large for that. The cycle length used to be a sort of traditional measure of "security" but it does not play this role nowadays. Any cycle length beyond $2^{128}$ is as good as "infinite".

A stream cipher is an encryption system specialized in the encryption of bulk data. Many stream ciphers operate like PRNG: from they key, they produce a long sequence of pseudorandom bits, which is combined by XOR with the data to encrypt or decrypt. In such a case, the internal PRNG state is not impacted in any way with the data that is encrypted. However, some other stream ciphers modify their internal state by injecting the encrypted data as well. When the data is injected, this changes the situation with regards to cycles: if the data to encrypt is not cyclic, then you won't get a cycle.

Block ciphers can be turned into stream ciphers by using some modes of operation, in particular CFB, OFB and CTR. The CFB mode injects the encrypted data into the internal state; OFB and CTR do not. With a block size of $n$ bits (e.g. $n = 128$ for AES), then CTR offers a cycle length of exactly $2^n$ blocks, i.e. $n2^n$ bits; OFB cycle length is more random (if you are terribly unlucky you could hit a short cycle).

A condition for a stream cipher to be deemed "secure" is that its output is computationally indistinguishable from randomness even when encrypted a long sequence of zeros. A consequence is that in a secure stream cipher, the cycle cannot be fully walked or even simply reached in practical terms. Beyond that point, cycle length has no meaning for security.


Requirement for the exponent generation during DH protocol

Since $g$, $A=g^a$ and $B=g^b$ are made public, everyone could repeat the same operation and brute force DH with small exponents.

There are already many responses:
link to security.stackexchange.com
link to crypto.stackexchange.com

Summary: considering a security level of $n$, it is advised to use exponents of at least $2n$ bits.


It's not clear what they actually mean by half of their things, or if there is any benefit of using them together. That site doesn't want to create any meaningful security, it's just to play around with numbers and letters.

They state to use Vigenere, that's okay, usual classic cipher, which can be broken if the text is long enough.
"Caesar box code": I have no idea what that means, unless they mean basically the same as a Vigenere cipher with length 5. This is kind-of pointless with a fixed block size, because that's one part of what makes Vigenere decent for a classical cipher.
"Skip letter code": No idea again, what they actually do. If you leave out letters, that's just not reversible. Going backwards comes down to guessing.
Railfence is a fixed transposition of letters, which is again pretty pointless.
Reverse: Same as railfence.
Encoding with morse or similar: Fixed codes like morse are just replacing one set of symbols by another, just takes time if you do it by hand.

What do we do if we don't know what was used? Well, first security by obscurity is bad in reality, because the scenario is unrealistic against serious adversaries. But for toying around: It's not that difficult just to try the various combinations of "algorithms". A computer will probably solve any such system within seconds. Building things from classical (broken) ciphers are not maknig things complicated for today's advanced machines.


Constructing scheme for indistinguishability test with variable length messages

That homework assignment is not entirely precise: If you allow $|m| = p(n)$, the padding doesn't make sense: $0^{-1}1$. Therefore, you would have to limit $|m| \leq p(n)-1$ to avoid that case.

For your example and question: You're right, if you consider that a prefix $0^{-1}1$ actually is the empty string (no padding). Then your strings are equal. However, that case is actually undefined and should be fixed with reducing the message length by $1$.

From an information theoretic point of view:
There are $2^{n}$ messages of length (exactly) $n$. And there are $\sum_{k=0}^{n}2^k = 2^{n+1} - 1$ messages of length $n$ or less. So if you consider the set of all messages of length $n$ or less, and consider those shorter messages as different messages, then you actually have $n+1$ bits of entropy (rounded to the next integer) and need at least a message of $n+1$ bits length to encode that information.


Deep Learning application in decryption?

There is no evidence of deep learning breaking modern cryptography. Deep learning is simply glorified gradient descent.
With a reasonable cipher you get no indication of almost finding the key, so I see no hope of deep learning breaking a black box cipher.

In order to use deep learning for cryptography we would need to find a notion of gradually or partially solving the problem, not an easy task.

We have seen some work to use deep learning to build new ciphers, using adversarial training. But there is not much evidence these ciphers are secure against human cryptanalysis.


ECDSA Compressed public key point back to uncompressed public key point

All points on an elliptic curve verify, by definition, the curve equation, usually written as $Y^2 = X^3 + aX + b$, with two given $a$ and $b$ parameters (these two parameters actually define the curve). So, if you know $X$, you can use the curve equation to recompute $Y^2$. A square root extraction will yield $Y$ or $-Y$. The compressed point format includes the least significant bit of $Y$ in the first byte (the first byte is 0x02 or 0x03, depending on that bit): this bit is enough to know whether you got $Y$ or $-Y$ with the square root, and adjust in consequence.

All computations above are done in the base field, i.e. (usually) the integers modulo a prime integer. See this for square root extraction modulo a prime.

Edit: for binary curves, things are somewhat similar. We work in a field $GF(2^m)$, so addition is a XOR; the curve equation is $Y^2+XY = X^3+aX^2+b$ (generic equation for non-supersingular curves). When point $P = (X,Y)$, the opposite point is $-P = (X,Y+X)$. We assume that the point we are encoding and decoding has coordinate $X \neq 0$, because a point with such a coordinate $X = 0$ is equal to its opposite, i.e. has order $2$. In practice, when we work on such a curve, we really use a sub-group of order $r$ prime (generally, we arrange for the complete curve order to be equal to $2r$ or $4r$).

Since $X\neq 0$, we can define $Z=Y/X$, and divide the curve equation by $X^2$. This yields:
$$ Z^2+Z = X+a+\frac{b}{X^2} $$
Thus, given $X$, we can compute $Z^2+Z$. From that value, we can compute the two solutions, which are $Z$ and $Z+1$ (see below). Since $Y = XZ$, this yields $Y$ and $Y+X$, thus the points $P$ and $-P$.

This gives us the compression method for curves in binary fields: from $(X,Y)$, compute $Z=Y/X$; the compressed point then consists in $(X,z_0)$, where $z_0$ is the least significant bit of $Z$. When decompressing, you use the equation above to recompute $Z^2+Z$, then $Z$ (the knowledge of $z_0$ tells you which of the two solutions is the right $Z$), then $Y = XZ$.

To know how to solve for $Z$, we need to define the trace and the half-trace. We are in $GF(2^m)$; the trace of a value $x$ is:
$$ \mathrm{Tr}(x) = \sum_{i=0}^{m-1} x^{2^i} $$
We are in a field of characteristic $2$, which implies that squaring is an automorphism: $(uv)^2 = u^2v^2$ and $(u+v)^2 = u^2+v^2$ for all $u$ and $v$ (this is called the Frobenius automorphism). Moreover, for all $u$, $u^{2^m} = u$ (this is analogous to Fermat's little theorem, because the non-zero elements of $GF(2^m)$ are a multiplicative group of order $2^m-1$). This implies two important characteristics of the trace:

The trace is linear: for all $u$ and $v$, $\mathrm{Tr}(u+v) = \mathrm{Tr}(u) + \mathrm{Tr}(v)$.
The trace of any $u$ is either $0$ or $1$. Indeed, for all $u$, $\mathrm{Tr}(u^2) = \mathrm{Tr}(u)^2$ (by the Frobenius automorphism), and also $\mathrm{Tr}(u^2) = \mathrm{Tr}(u)$ (try it in the equation that defines the trace). Thus, for all $u$, $\mathrm{Tr}(u)^2 = \mathrm{Tr}(u)$. The equation $x^2=x$ is a polynomial equation of degree $2$, so it can have only (at most) $2$ solutions in a field, and $0$ and $1$ are solutions. Therefore, $\mathrm{Tr}(u)$ can only be $0$ or $1$.

Let's now define the half-trace. For now, I suppose that $m$ is odd (this is the normal case for binary elliptic curves, e.g. NIST curve B-233 is defined in $GF(2^{233})$). For any value $x$, the half-trace of $x$ is:
$$ H(x) = \sum_{i=0}^{(m-1)/2} x^{2^{2i}} $$
That is, we take the equation for the trace, but we keep only half of the operands in the sum.

Like the trace, the half-trace is linear. Also, for any $x$, we can see that:
$$ H(x)^2 + H(x) = \mathrm{Tr}(x) + x^{2^m} = \mathrm{Tr}(x) + x $$

Let's get back to our equation $Z^2+Z = \beta$ where $\beta = X+a+(b/X^2)$. Since the trace is linear, and since for $Z$ and $Z^2$ have the same trace, it follows that $\mathrm{Tr}(\beta) = \mathrm{Tr}(Z^2+Z) = \mathrm{Tr}(Z^2)+\mathrm{Tr}(Z) = 0$ (remember that addition is XOR in $GF(2^m)$). Thus, the equation can have solutions only if $\mathrm{Tr}(\beta) = 0$. Then, we have $H(\beta)^2+H(\beta) = \beta$, so the solutions for $Z$ are $H(\beta)$ and $H(\beta)+1$.

If $m$ is even (this will often be the case if using pairings over binary curves, although this is probably not a good idea since discrete logarithm in binary fields is a lot easier than previously expected), then most of the above hold, although we need another definition for the half-trace. Basically, we need a constant element $w$ such that $\mathrm{Tr}(w) = 1$, and we can define the half-trace as:
$$ H(x) = \sum_{i=0}^{m-1}\left(\sum_{j=0}^{i} x^{2^j}\right)w^{2^i} $$

In both cases ($m$ odd and $m$ even), the half-trace is linear, so it can be computed as a XOR of some precomputed values for the bits equal to $1$ of the source. This is rather inexpensive. The trace is even easier: it is simply a XOR of some of the input bits, and, in practice, often a XOR of very few of these bits.


Can one generalize the Diffie-Hellman key exchange to three or more parties?

The standard Diffie-Hellman key exchange algorithm (or family of algorithms) works in an cyclic group with generator $g$, and relies on

$$ {y_A}^{x_B} = (g^{x_A})^{x_B} = (g^{x_B})^{x_A} = {y_B}^{x_A}, $$

where $y_A$ and $y_B$ are publicly transmitted, while $x_A$ and $x_B$ remain private.

With three parties, we still have

$$((g^{x_A})^{x_B})^{x_C} = ((g^{x_A})^{x_C})^{x_B} = ((g^{x_B})^{x_A})^{x_C} = ((g^{x_B})^{x_C})^{x_A} = ((g^{x_C})^{x_B})^{x_A} = ((g^{x_C})^{x_A})^{x_B}. $$

As each party wants to let its own key private, each exponentiation needs to be done at different locations, which means some parties have to send their second-step results to the other parties.

One possible protocol could be the following:

A, B, C each generate their private keys $x_A$, $x_B$, $x_C$.
A, B, C each calculate $y_A = g^{x_A}$, $y_B = g^{x_B}$, $y_C = g^{x_C}$.
A sends $y_A$ to B, B sends $y_B$ to C, C sends $y_C$ to A.
A calculates $z_{CA} = {y_C}^{x_A}$, B calculates $z_{AB} = {y_A}^{x_B}$, C calculates $z_{BC} = {y_B}^{x_C}$.
A sends $z_{CA}$ to B, B sends $z_{AB}$ to C, C sends $z_{BC}$ to A.
A calculates $k_{BCA} = {z_{BC}}^{x_A}$, B calculates $k_{CAB} = {z_{CA}}^{x_B}$, C calculates $k_{ABC} = {z_{AB}}^{x_C}$.

The above equality means that the three parties now know a common secret $k_{ABC} = k_{CAB} = k_{BCA}$.

This obviously generalizes to more than three parties, but it needs one additional group exponentiation per participant more for each additional participant (i.e. in total $n^2$ exponentiations).

All of this works in all groups, so also in the elliptic curve groups (where this is usually written as point multiplication instead of exponentiation).

In practice it might be easier to exchange secret keys with some "hub" node, which then creates a common secret and sends it to each participant, like Dennis proposed in his answer.


I've written extensively about how to solve this problem, over on the IT Security Stack Exchange site.  Let me point you to my answers over there:

What is the best way to securely keep clear passwords?
How can I create a service that automatically logs onto a third-party service without storing credentials in plain text?
How should you store a password that needs to be retrieved as plaintext?

Basically, I'm suggesting you set up a separate machine that stores people's credentials for the third-party website as well as a hash of their local password, authenticates the user, and then connects directly to the third-party website.  That separate machine should be secured and locked down as carefully as possible, to reduce the likelihood that it is compromised.  But read those links for all sorts of extensive details and suggestions.


Are there other digital certificate formats than X.509?

Although x.509 is the standard for PKIs with CAs, different certificate formats have been defined for the other 2 major PKI approaches:

SPKI has defined its own certificate
format , still (forever?) in
draft status.
Web-of-Trust models usually use the OpenPGP certificate format defined in RFC2440

RFC4212 "Alternative Certificate Formats for the Public-Key Infrastructure Using X.509 (PKIX) Certificate Management Protocols" may also be of interest.


How to derive the curve Ed25519 from Curve25519?

First off, your equation is correct and there seems to be no calculation mistake.

To understand on how to get from
$$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$
 to
$$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}$$
one first needs to observe that $e=(d-2)/(d+2)=121665/121666$ holds.

The next step is to consider:
"What operations are actually allowed with birational equivalence?". According to this presentation on a similar topic, linear transformations in the coordinates don't break the birational equivalence as do simple equivalence transformations (the ones having takens us here).

So the substitution $x^2:=x^2\cdot d/(d+2)$ is allowed. If you now perform the substitution, you'll observe
$$dx^{2}+dy^{2}=d+d(d-2)/(d+2)x^{2}y^{2}$$
and dividing by $d$ yields the desired equation.


Encrypting many small messages (log-lines)

Ok, answering myself then, trying to summarize all the good input from above.

First of all, this design will provide confidenciality to each log message, but it will not:

ensure the integrity of the log as a whole, it will be possible to insert or remove log-entries unnoticed
authenticate the sender of log-messages, a rouge client or a man-in-the-middle could insert fake log-messages

However, if this is OK (or you have other ways of solving these issues), this scenario is probably secure.

As for performance, on my machine I get the following numbers:

Just RSA: just below 4000 messages pr second
RSA and AES with a new key each time: just above 4K msg/sec
RSA and AES with a new key each 10 messages: 17 K msg/sec
RSA and AES with a new key each 100 messages: 25K msg/sec

Just RSA seems to have no advantage over RSA+AES, and there is an upper limit to message size.

Now, this just encrypts the same string over and over. For a more real-life test I will make new strings (serialized xml) and write these to disk, to se if the difference is still significant.

As for the use of gzip, I have tried a 218-byte xml-message which gzipped into 164 bytes (25% reduction in size). This is a relevant testcase in my scenario, but of course your milage may vary.

Edit: I have re-tested with different values for key-size and exponent. All of these are using RSA to encrypt an 128-bit AES session key, with a new key for each message (I guess in effect I am measuring the throughput of RSA-encryption of 128-bit random numbers).

keysize=1024 bits, $e = 2^1+1$: 7 tx/millisecond
keysize=1024 bits, $e = 2^{16}+1$: 10 tx/millisecond
keysize=2048 bits, $e = 2^1+1$: 11 tx/millisecond
keysize=2048 bits, $e = 2^{16}+1$: 4 tx/millisecond

This is using the default crypto-provider in java 7. I let each configuration run 20 iterations before starting the measurement to "warm up" the jit-compiler.

My environment:

java.vm.version: 23.7-b01
java.vm.vendor: Oracle Corporation
java.vm.name: Java HotSpot(TM) 64-Bit Server VM
file.encoding.pkg: sun.io
java.runtime.version: 1.7.0_15-b03
os.arch: amd64
os.name: Windows 7
sun.management.compiler: HotSpot 64-Bit Tiered Compilers
os.version: 6.1
sun.arch.data.model: 64


Who can create a MAC? Who can verify a MAC?

Anyone who holds the key can create a MAC. For any secure MAC it should be computationally infeasible to create a MAC without knowledge of the key.

By the correctness of a MAC, anyone who holds the key can verify it. In pretty much any practical MAC, the key is also needed to verify, but this is not something that's actually implied by the functionality or security definitions.


Does hashing a compromised rng and a secure rng give cryptographically secure random output?

If you have a cryptographically secure hash function and you use as much input from each of the sources as there is output i.e.

for $H: \{0,1\}^* \rightarrow \{0,1\}^n$ you use $n$-bits of input from each RNG it will work.

However, in your specific example if you only use 3 letters to generate 512 bits of output, when the DEF repeats the entire 512 bits of output will repeat and this will happen with pretty high probability and after detecting it the rest of the 512 bit are known to an attacker.


Addition of a point with itself is "just" the limit case of normal addition. Geometrically, point addition starts with a line that goes through the two points to add; point doubling uses the tangent to the curve on that point, which is what you expect to have when the two points are made very close to each other.

In that geometric interpretation, the tangent to the curve on a point $P = (x,0)$ is vertical, and thus won't intersect the curve anywhere else; or, more accurately (using projective geometry terminology), that vertical line meets the curve again only at infinity. The sum of $(x,0)$ with itself is thus the point at infinity. This also means that $(x,0)$ is its own opposite.

Now, in cryptography, we use curves in finite fields, which are discrete and don't look like curves. One interesting point to make is that a point $P = (x,0)$ is such that $2P = \mathcal{0}$, i.e. it is a point of order 2. Since an elliptic curve is a group, if there is a point of order 2, then the total curve order must be a multiple of 2. Many standard curves (e.g. the very widespread NIST curve P-256) have been chosen to have a prime order, hence odd; it follows that, for such curves, there is no point $(x,0)$, and the question of doubling such a point does not arise at all.


In a Feistel cipher structure, what exactly does the "round function $F$" do?

What exactly does the "round function F" do

Pretty much anything it wants, with the proviso that it must be a deterministic function of the right hand data and the keying data; it cannot depend on the left hand data.

With that constraint, you get an easily invertible cipher structure, with the inverse function being essentially the same (except that you perform the various rounds in the opposite order; if you feed different subkeys into the various rounds, you invert that, and if you use different F functions for different rounds, you reverse the order of that as well).

Now, to get a secure and efficient cipher, well, that takes a bit more work...


Is forward search attack is the same as dictionary attack?

In the context of passwords, a dictionary attack is a forward search attack improved by using a dictionary of likely passwords (best ordered from most to least frequent), rather than enumerating all possible passwords in a mechanical manner (like in lexicographic order).

In other words, the dictionary attack necessarily uses a dictionary, when a forward search attack can do without.


Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic

Yes, there exist other deterministic PHE schemes. Actually, you can turn any probabilistic PHE into a deterministic one. This is achieved by deriving the random coins for the encryption deterministically from the message to be encrypted, e.g., by computing the random coins as a hash of the message (using a suitable hash function compatible with the randomness space of the encryption scheme).

Moreover, the determinism of the PHE is not related to whether the operation on plain- and ciphertexts are identical (a simple counterexample is ElGamal encryption, which is a probabilistic PHE, and uses the same operations on plaintexts and ciphertext components).


It doesn't really prove it, and isn't meant to. If he really does know the hash, it's most likely that he has access to the source tree, which almost certainly means he knows more about Microsoft's corporate culture than the average person, which is the most important bit (if he's a Microsoft dev, he also has little incentive to claim to be a kernel dev if he's, say, a UI dev; either one gives him some authority on the subject). The issue is that only another person with source access can verify the hash, but it means that if he made up the hash, someone with source access could go "No, the hash is this instead" -- that's not something subjective, so it wouldn't just be a difference of opinion.

The hash specifically gives some piece of information that strongly implies he has access to the full file (and the full source tree), without actually giving out the file (which is a trade secret). It's not much different than saying "revision 102 had this timestamp," or "the combo to the supply closet last year was 1-2-3-4-5," or (leaving aside privacy) "here's my business card." It doesn't, and isn't intended to, provide a real proof; it just makes it a bit more likely he has some idea what he's talking about, which is the real goal.


Correctness of Propagating Cipher Block Chaining mode of operation (PCBC)

How the PPCBC mode works
Propagating Cipher Block Chaining mode of operation (PCBC) works as with message indexes starts from 1;

For PCBC encryption we have;

$$C_i = E_K(P_i \oplus P_{i-1}\oplus C_{i-1})\text{ and } \color{red}{C_0 = P_0 \oplus IV}$$

For PCBC decryption ve have;

$$P_i = D_K(C_i) \oplus P_{i-1}\oplus C_{i-1}\text{ and } \color{red}{C_0 = P_0 \oplus IV}$$
given $C_1$ to decrypt $P_1$
$$P_1 = D_K(C_1) \oplus P_{0}\oplus C_{0} = P_1$$
given $C_2$ to decrypt $P_2$
$$P_2 = D_K(C_2) \oplus P_{1} \oplus C_{1}$$ Now we can solce since we know, $P_1$ and we have all $C_i$s.
and so on...
The red part was missing in your question.

The Correctness of the PCBC mode
An encryption scheme must satisfy the correctness requirement; for every key $k$ output by the key generation algorithm and for every message $m \in \mathcal{M}$ ($\mathcal{M}$ is the message space), the following must hold;
$$ D_k(E_k(m)) = m$$

To see that PCBC has the correctness; take
$$C_i = E_K(P_i \oplus P_{i-1}\oplus C_{i-1})$$ take decryption on the both sides
$$D_K(C_i)= \color{red}{D_K}(\color{red}{E_K}(P_i \oplus P_{i-1}\oplus C_{i-1}))$$ cancel Enc with Dec.
$$D_K(C_i)= P_i \oplus P_{i-1}\oplus C_{i-1}$$
Therefore:
$$P_i = D_K(C_i)  \oplus P_{i-1}\oplus C_{i-1}$$
Since we know, all $C_{i}$s, and previously decrypted $P_{i-1}$.
If it is the first case $(i=1)$, then we already know $\color{red}{C_0 = P_0 \oplus IV}$


This protocol doesn't authenticate the mote at all.  Consider this attack:

Mote B sends a 'hello' message to Base. This message contains the ID# of Mote A and a random nonce [R] (HW generated) encrypted by the base's public key.
Base decrypts the 'hello' and verifies the ID# against a whitelist.
Base sends an 'ack' message. This message contains some gibberish that Mote B cannot understand.
Mote B sends ID#, data and [R+2] to base encrypted by Base public key.
Base decrypts and sends more gibberish that Mote B cannot understand
Mote B ignores the ack.

Here, the base has accepted data as coming from Mote A, even though it actually came from Mote B.

In addition, it does nothing to prevent a replay attack (as someone just replaying the two messages that the mote sends to the server would cause the server to accept the replay).

For this general idea to work, then either:

The base needs to send some data to the mote encrypted by the mote's public key, and the mote must use that data as a necessary part to continue the exchange; or
The mote needs to sign something with its private key (which the base validates)

In addition, then if the server cannot store state about the messages it has already received, then it is the one that needs to pick the random number (nonce), and inject that into the protocol.


How to find q in a corrupted ECDSA signauture

First note that this is essentially the same problem as if you just generated the curve parameters and now wanted to find out the order, so we can use the same strategies as for that case here:

Ask a tool like sagemath: EllipticCurve(GF(17),[2,2]).cardinality() which constructs an elliptic curve over $\mathbb F_{17}$ with $a=2,b=2$ and finds out its cardinality which is $q=19$. This is the easisest way.
Calculate it yourself using Schoof's algorithm. Of course this is an $\mathcal O(\log^5 p)$ algorithm, so it will be quite tiresome to execute by hand, especially for small values. But for large curves it is the way to go.
Guess it using the Hasse-Bound. Essentially you want to solve the discrete logarithm $q\cdot P=\mathcal O$ (with $\mathcal O$ being the additive neutral element). Now you can use standard discrete-logarithm finding techniques, such as plain brute-force or BSGS to find it and also use the constrain that the Hasse-Bound gives you: $|p+1-q|\leq 2\sqrt p$, so $q\in[p+1-2\sqrt p, p+1+2\sqrt p]$ or in your concrete case: $q\in [17+1-2\cdot 5,17+1+2\cdot 5]=[8,28]$. So you would e.g. start with $8P$ and check if that's $\mathcal O$ and if not proceed to $8P+P=9P$ until you find the index that yields you $\mathcal O$ which is the order of $P$ (and in this case also the order of the curve because the curve order is prime).


Is it true that for RSA with no padding, the length of data must be equal to the length of key?

The short answer is NO. Generally, it is not true that for RSA with no padding, the length of data must be equal to the key length. When and if that applies, that's a restriction of a particular cryptographic library, and either that's not the only restriction about the data, or the library does not allow reliable decryption of what's encrypted.

RSA (encryption) with no padding is a well defined algorithm when enciphering integers. It uses a public key $(N,e)$. The key length is given as the bit size $n$ of $N$; that is $n$ is the integer such that $2^{n-1}\le N<2^n$. This form of RSA encryption with no padding takes as input some integer $m$ with $0\le m<N$ called the plaintext (or message), and outputs the integer $c$ with $0\le c<N$ called the ciphertext, such that $c\equiv m^e\pmod N$ (or in other words such that $m^e-c$ is a multiple of $N$). That transformation is reversible for decryption. Notice that if we remove the restriction that $m$ is less than $N$, we create the problem that $m$ and $m+N$ yield the same $c$, therefore decryption of the ciphertext can not reliably recover the plaintext; for example, $m=2^n-N-1$ and $m=2^n-1$ both encipher to the same $c$.

RSA with no padding is not universally defined when we move to data rather than integers, for many reasons including:

There's no agreement on the stuff data is made of. Is that bits? Octets of 8 bits? Characters for various definitions of that?
Endianness in the conversion to integer and back.
Dealing with the aforementioned $m<N$ requirement; a fine option would be defining a fixed data size insuring that. For example, message data of exactly $\lfloor (n-1)/8\rfloor$ octets (and some usual conversion to integer) would insure $0\le m<2^{n-1}\le N$; but then that fixed data size is less than the key length (in octets).

The library in the question does not do the later. Its requirement seems to be that the input data length in bytes (octets) must be a multiple of $n/8$, where $n$ is the key size in bits (an a multiple of 8 in all the examples). We can guess that the input is split into data blocks of exactly $n/8$ octets, each individually converted to a number $m$ (probably using straight big-endian convention, which is the most common), then RSA-enciphered as above, with each result converted back to exactly to $n/8$ bytes using the same convention, and the results concatenated in the same order as the original to form the ciphertext. We have no way to guess what happens when one of the $m$ does not meet the $m<N$ requirement.

It seems the library in the question unify symmetric and asymmetric cryptography into a one-size-fits-all API, even if that's at the price of drawbacks:

Making it easy to unwillingly implement an unsafe cryptosystem; in particular, if some data belonging to a small set (like a dice throw, or candidates to an election) is enciphered in this way, it is trivial to break the encryption (just encipher each possible plaintext and see which match the ciphertext).
Allowing large data and subdividing that into blocks before enciphering each with RSA, which makes decryption grossly inefficient; and is insecure when used with no padding: in particular repeated plaintext blocks are visible in the ciphertext.
Either ignoring the $m<N$ requirement (with the consequence that for some data, encryption followed by decryption does not give back the original data); or rejecting some data at encryption time (which might escape testing). Most likely, one of this occurs when enciphering a block of data consisting of $n/8$ octets all 0xFF.

Except in very specific cases (such as enciphering a random bit string of $n-1$ bits):

Do not use RSA with no padding (also called textbook RSA or naked RSA), but rather use some secure RSA scheme built on top of that; see e.g. RSAES-OAEP of PKCS#1. Among the reasons not to use RSA encryption with no padding

Like any deterministic public encryption, it is unsafe when the plaintext has low entropy.
Short plaintext is vulnerable. In particular, even uniformly random plaintext of $\lfloor n/e\rfloor$ bits can be found by $e^{\text{th}}$ root extraction, and there are extensions to that.
Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem has more excellent reasons; and there are even more.

Do not use RSA to directly encipher application data that could be larger than what makes the RSA scheme used safe (for example, RSAES-OAEP with 2048-bit key and SHA-256 hash allows to safely encipher data of 0 to 190 octets and still have enough randomness added by the scheme); rather, use hybrid encryption.


Is there an encryption/decryption algorithm that can give two different outputs?

It looks like you might be interested in applying
 Deniable Encryption.

The general idea of this kind of encryption is that you can decrypt the data to produce a different (but still plausible) plaintext. In this way, the airport staff or whoever is asking you to decrypt the data, would by no means differentiate between the real plaintext and the alternative one.
I suggest to have a look a this paper.


Finding the probability of a message encrypting to a given ciphertext

Part of your confusion is coming from ignoring the distinction between random variables (e.g., $K$) and their values (e.g., $k$).

Let $p$ be probability distribution of the keys $k\in {\cal K}$ and let $q$ be the probability distribution of the messages $m \in {\cal M},$ assuming both sets $\cal K$ and $\cal M$ are finite. The encryption mapping $E_K(M):=E(K,M)$ is a mapping  $$E:{\cal K} \times {\cal M} \rightarrow {\cal M}$$
where we assume the ciphertext space is also $\cal M$ for simplicity. Clearly a well defined cipher would select keys independently of the messages.

Then, using the definitions of conditional probability all quantities can be evaluated. In particular, the ciphertext distribution is directly obtained from the other two distributions since it is completely determined by them.

In general one could have $m$ mapping to $c$ under different key values $k$ and these will need to be summed, each admissible choice weighted by $p(k)q(m).$

Clearly, $P(m=m_1)=q(m_1),$ while $P(m=m_1|E_k(m)=c)$ is $$P(m=m_1|E_k(m)=c)=\frac{\sum_{k\in {\cal K}:E_k(m_1)=c}p(k)q(m_1)}{\sum_{k\in {\cal K},m\in {\cal M}:E_k(m)=c}p(k)q(m)}  $$
where the numerator is taken to be zero in case of an empty sum, and $c$ is fixed.


For example, assume an RNG spits 128-bit values $X$ that are all-zero with odds $p=1/120$, and otherwise independent and evenly distributed among the other values. The 128-bit values spit by this RNG contain $H(X)=-p\log_2(p)-(1-p)\log_2\big((1-p)/(2^{128}-1)\big)>127$ bits of entropy.

Yet, if repeatedly the same secret is XOR-ed with this RNG forming 128-bit ciphertext blocks, the secret can be recovered, with overwhelming odds, as the first value that repeats; and there are better than even odds that this occurs with a mere 250 ciphertexts.

Another example would be a 128-bit RNG where each bit is independent with odds $p=9/20$ to be one, for $H(X)=-128\big(p\log_2(p)+(1-p)\log_2(1-p)\big)>127$ bits of entropy.

With the same hypothesis as in the first example, the secret can be recovered by keeping the most frequent bit value for each rank. Few hundred ciphertexts are enough to recover the secret with fair odds.

Note: the generator of the second example is still safe to generate AES-128 keys; while the first is disastrous; which illustrates that entropy is not the only thing that matters for a RNG.


Can universal hashing functions be (ab)used as stream ciphers?

No. Consider the simple universal hash function $H(k, x) = k \cdot x \in \mathbb{F}_{2^n}$. It is universal as $\text{Pr}[H(k, x) = H(k, y)] \le 1/(2^n - 1)$ for a randomly-selected $k$; polynomial evaluation degenerates to this function when run on a single block. If you run this in counter mode you get as ciphertext $k \cdot 0$, $k \cdot 1$, $\ldots$, which is clearly insecure and leads to immediate key recovery.

Universal hash functions (or the weaker almost-xor-universal variants) work with authentication because their sole job is to uniformly map a potentially long message to a shorter one; the secrecy job is handled by some PRF or PRP.


Does GCM improve the strenght of weak passwords?

No, it doesn't make weak passwords magically stronger.  If they know part of the file (e.g. the header), or even is just able to recognize it, what they can do is, for each plausible password, just decrypt that small area of the file (and ignore everything else), and see if the decryption of that area is plausible.  Once the password guess passes that check, they can then do a full decryption and see if everything checks out.

To make brute forcing a weak password more difficult, I would suggest a strong (expensive) password hashing method, such as Argon2.

BTW: the estimated time of 1 msec to decrypt a 1kbyte GCM-encrypted file is far too large; I would expect that an adversary might be able to do it in perhaps within a few microseconds...


How can we create the AES S-box using a different irreducible polynomial?

I would like to change the irreducible polynomial for another suitable one

Suitable in what way? Are you trying to make a cipher with improved hardware performance or resource usage? Trying to increase the security of the cipher? Any change would result in a similar cipher but would no longer be AES.

1: I believe Sage can perform the calculation if you can write the correct script, and I believe they have an online version

2: not easily, you need to generate multiple tables, then do all the math. I can do it quickly in VB6, and Excel uses a VB type script language, but it may not be comprehensive enough to get it done, and since it would not be compiled, it would be slower, and you would still need to write a substantial amount of code

3: you have to choose it. The affine transform in AES was chosen based on the polynomial so that the s-box would meet certain criteria, you could simply brute force all of them (there are about 65000) and choose the best result. That is the last step, and the most computationally expensive, doing it in excel would take an absurd amount of time, probably years.