In search of a pedagogically simple example of asymmetric encryption routine?

Asymmetric encryption: What?

Alice wants to be able to receive messages sent by anyone, posted on a public website or whatsapp group, that only her will be able to decipher. Traditional cryptography would require that the sender and her share some secret (key or password), used for encryption and decryption.

In asymmetric encryption, Alice generates and keep a secret private key, and openly shares a corresponding public key. Anyone with Alice's public key can encipher a message to her. Alice's private key is necessary to decipher it.

Asymmetric cryptography also includes digital signature: Alice signs data with her private key, then anyone with Alice's trusted public key can verify that she signed that exact data. All this was thought impossible until the 1970's. It is now commonplace, e.g. in web browsers.

Asymmetric encryption: How?

It's done with mathematics. Only a computer can realistically perform the computations. One of the commonly used method is ElGamal encryption. We can illustrate that with a little Python.

We'll use Python's pow(a, x, n). It computes "a to the power x modulo n". In this, "a to the power x" means x copies of the number a multiplied together; and "modulo n" means that we keep what remains when dividing by n.

Take pow(2, 4, 10) for example. "2 to the power 4" is 2×2×2×2, that is 16. When we split 16 things among 10 persons, each gets 1 and it remains 6.
Therefore, pow(2, 4, 10) yields 6.

Alice will chose a private key at random, and compute her public key as
PublicKey  = pow(2, PrivateKey, n). This is easy and fast in Python, but computing PrivateKey from PublicKey is believed infeasible by even the most powerful computer, when n is a large-enough safe prime, and PrivateKey is random and large. n is typically made public, like this. We'll use something just as safe but easier to key-in:

# Setup
import secrets                      # needed for randbits
n = 2**4096 - 3**2542 + 3547696     # some public 4096-bit safe prime

# Alice generates her keys
PrivateKey = secrets.randbits(400)  # generate secret Private Key
PublicKey = pow(2, PrivateKey, n)   # compute Public Key

# Barnabé got PublicKey and wants to send a message to Alice
M = "Surprise for you in my locker, code 47918. Barnabé"
# turn M into an integer m, at most 500 bytes
m = int.from_bytes(bytes(M, 'utf-8'), byteorder='big')
assert m.bit_length()<=4000         # bark if message is too large

# encryption of m into Ciphertext
x = secrets.randbits(400)           # number used once
r = pow(2, x, n)                    # Alice need this to decipher
s = pow(PublicKey, x, n)            # shared one-time secret
c = (s%(2**4000)) ^ m               # produce ciphertext using XOR

# remove Barnabé's secrets
del M, m, x, s

# Alice receives ciphertext c and r, and deciphers that using PrivateKey
s = pow(r, PrivateKey, n)           # shared one-time secret
m = (s%(2**4000)) ^ c               # decipher using XOR
# turn integer m into a string M
M = str(m.to_bytes((m.bit_length()+7)//8, byteorder='big'), 'utf-8')
print(M)                            # show the deciphered message

# remove Alice's secrets, except her PrivateKey which can be reused
del s, m, M

The values of s computed by the sender during encryption is pow(pow(2, PrivateKey, n), x, n), that used by Alice during decryption is pow(pow(2, x, n), PrivateKey, n), and thanks to  mathematical properties of pow these are the same.

Summary: with asymmetric encryption, nothing secret is needed to send a confidential message. We can do with some clever math, a trusted computer able to generate random numbers, and the trusted public key of the intended receiver.

Pedagogical notes

While I believe that a sizable fraction of a 17yo audience would be able to grasp/appropriate/extend the above, only a small fraction of 11-13yo would. Thus I think the best with such young audience is to explain what asymmetric encryption does (and if possible digital signature, which is at least as useful). Illustrate that using key generation/encryption/decryption boxes with the corresponding Python code inside as small characters or truncated, and the values exchanged shortened with ellipsis, but do not dive into exactly what the code does. But give access to material (source code) showing how this is done and allowing to reproduce it. Those ready for that might use it.

ElGamal encryption is a direct transposition for encryption of Diffie-Hellman key exchange, one of the first asymmetric cryptosystem published. It is using that for all positive integers $a,n,\text{PrivateKey},x$,
$${\left(a^\text{PrivateKey}\right)}^x\equiv a^{\text{PrivateKey}\,x}\equiv a^{x\,\text{PrivateKey}}\equiv{\left(a^x\right)}^\text{PrivateKey}\pmod n$$
and, for $n$ a large safe prime and most $a$ including 2,  if $x$ and $\text{PrivateKey}$ are chosen at random, with $a$, $n$, $a^\text{PrivateKey}\bmod n$ and $a^x\bmod n$ public but $\text{PrivateKey}$ and $x$ are large random unknowns, then $a^{x\,\text{PrivateKey}}\bmod n$ is believed computationally indistinguishable from random in $\Bbb Z_n^*$ except for 1 bit of information. If we spare some high-order bits, the low-order ones are a shared secret, which we use for symmetric encryption using XOR.

This is not toy cryptography. That's IND-CPA secure asymmetric encryption in the academic sense. Parameters give a very high security level. The later has no penalty in a pedagogical context since the computations can't be done by hand anyway, and the code remains fast enough on anything running Python 3.

However, it must be noted that ElGamal encryption, and the code, have serious shortcomings:

There's nothing to prevent alteration of Alice's public key on its way to Barnabé, and that allows an attack. Barnabé could be tricked to use some adversary's public key instead of Alice's, and then the adversary could decipher the message and access Barnabé's locker.
There's no authentication: Alice is not sure that the message is from Barnabé. Anyone can encipher any message towards her.
There's worse: an adversary can subtly alter the message and get some information. For example: guessing that the message ends in Barnabé (because he always do that), an adversary could alter the ciphertext so that what Alice deciphers ends with a different name. Alice might try and fail to open that other person's locker; and if the adversary rigged that locker to beam Alice's attempted code, the attacker now can access Barnabé's locker before Alice can. More generally, the scheme lacks IND-CCA2 security.
Secure storage of keys and key distribution are not illustrated.
Ciphertext transmission/reception is eluded.
The code is not protected against implementation attacks (e.g. padding oracle, timing and side-channels).

Small parameters would limit the message size, or make the code more complex. That would also be teaching kids to make unnecessary compromise (in the same spirit, I have not limited the message to ASCII, and it's size is range-checked, because we should promote sound coding habits when possible). However, there can be imperatives to use smaller values, like adapting the demo code to an environment without built-in support for large integers, or actually transferring the values between individuals on paper. In that case, perhaps limit message to 24 bits (3 bytes, good for 3 or 4 characters), change n to 2147481143, 2**4000 to 16777216, and use random integers in range [1, 1073740570] for PrivateKey and x. Of course, all security is lost: a programmable calculator can find the private key.

I have refrained from introducing RSA, because it uses heavier math (we need modular inversion and the little Fermat theorem to explain why it works), and RSA is harder to implement. Worse, most pedagogical implementations have a fundamental shortcoming: a guess of the plaintext (e.g. a name on the class roll) can be verified from the ciphertext. Independently, the parameters are typically so small that this check can be made letter by letter; and re-encrypting the ciphertext a small and fixed number of time is enough to decipher without any guesswork. Also the modulus can be factored, typically by hand (perhaps with Fermat's method).

My point of view is that it is best not to mislead an audience, especially a young one, into believing they understand how asymmetric encryption works, or that it can be done with 10-digit numbers. It took centuries of effort to devise it, and that's because it's hard.


Is encrypting multiple message with same key and iv secure for this case?

If the initial "random padding" is (at least) 16 bytes, this is effectively CBC mode with a random IV.

That's because the initial block of the ciphertext is, with your scheme:

$$E_k( \text{IV} \oplus \text{Random Padding} )$$

which is equidistributed among all $2^{128}$ possible values (assuming Random Padding is equidistributed among all $2^{128}$ possible values independent of the IV).

The rest of the ciphertext is effectively the CBC mode encryption of the rest of the plaintext, with the above equidistributed value as the IV


Extract one unique SBox from Canonical Representative

This illustrates the idea with no efficiencies considered. Take the canonical Sbox, and let $$X:=[X[1],\ldots,X[16]]$$
be the vectors in $\{0,1\}^4$ in the order given by the canonical Sbox map.

Looping through all invertible $4\times4$ matrices $M_0,M_i$ and all constant vectors $c_0,c_i$ compute the list of column matrices
$$
F(M_0,M_i,c_0,c_i):=M_0 \cdot [M_i\cdot(X[1]\oplus c_i),M_i\cdot(X[2]\oplus c_i), \ldots M_i\cdot(X[16]\oplus c_i)]\oplus [c_0,\ldots,c_0],
$$
and you will find the target Sboxes for some $F$ computed during this process.

See extract from the paper quoted in the question below:


Schnorr's protocol is an interactive proof of knowledge. The 'attack' that you provide does not contradict this: if the powerful prover that you describes can indeed try all $r$ such that $h^r = t\cdot z^c$, then she can as well try all $x$ and check for $z=h^x$. Put otherwise, this prover does indeed know the discrete logarithm of $z$: in fact, any 'unbounded' prover knows the discrete log of $z$.

The proof that a prover that provides an accepting proof must know the discrete logarithm is done by using rewinding, and showing that a simulator could extract this discrete log from its interaction is quite straightforward (repeat the last two flows twice, write out the equations, cancel the randomness introduced in the first flow, and you get the witness); furthermore, if you write it, you'll observe that it does not rely on any computational assumption - if the verification succeeds with non negligible probability, extraction will succeed as well, with comparable probability. This holds independently of the computational power of the prover.

EDIT: to answer your follow up question, yes, you got the intuition right: if the prover can produce two accepting transcripts, she must know $x$, as $x$ can be extracted from these transcripts. Your issue seems to be that a computationally unbounded prover can always compute $x$, hence he always 'knows' $x$ - so, how is that interesting to consider also unbounded provers in the security analysis?

The answer lies in the formal guarantee given by a proof of knowledge. While the intuition is that it guarantees that the prover 'knows' the witness, the actual guarantee is the following: if the prover produces an accepting transcript, then a simulator can (using rewinding) extract the witness. This is of crucial importance in many cryptographic protocols where the proof of knowledge is part of a larger system: the simulator will often need to extract the witness from the proof, to use it when simulating other parts of the protocol. Now, in an argument, which is only secure against computationally bounded provers, an unbounded prover could well produce an accepting transcript from which the simulator cannot extract a witness - by breaking the computational assumption on which the knowledge soundness relies. Hence, even though this unbounded prover does indeed know a witness (she is unbounded, so she can obtain all witnesses via brute force), she does not necessarily allow the simulator to extract it from successful transcript, hence the analysis of ant larger system in which the simulator would need this witness would break down.

In Schnorr's protocol, however, as the soundness is unconditional, the simulator is guaranteed to always succeed in extracting the witness from the prover, even if she is unbounded.


Homomorphic crypto allowing anonymous yes/no votes?

A homomorphic cryptosystem has some operation $*$ on ciphertexts that correspond to some other operation $\circ$ on plaintexts, that is
$$\mathcal{D}(c_1 * c_2) = \mathcal{D}(c_1) \circ \mathcal{D}(c_2).$$
Typically, the ciphertexts you get by applying $*$ look like ciphertexts that are produced by the encryption algorithm. For Damgård-Jurik, $*$ is multiplication modulo $n^{s+1}$ and $\circ$ is addition modulo $n^s$.

A cryptosystem is secure if the ciphertext does not help you to say anything about the message encrypted.

Suppose you encode "yes" as $1$ and "no" as $0$. The voter will encrypt his encoded vote and send it to the server. Suppose the server receives ciphertexts $c_1, c_2, \dots, c_L$ that are all encryptions of $0$ or $1$. The server can now multiply the ciphertexts to get a single ciphertext, which by the above requirement will satisfy
$$\mathcal{D}\left(\prod_i c_i\right) \equiv \sum_i \mathcal{D}(c_i) = \text{number of "yes" votes.}$$
The server can therefore find the correct election result by decrypting the product ciphertext.

It does not really matter how many ciphertexts are submitted.

If the server is passive (honest-but-curious, will try to break confidentiality without deviating from instructions), the voters are honest and the cryptosystem is secure, the server cannot deduce anything about the votes from the ciphertexts (except the result, of course, since he decrypted a ciphertext containing the result). Damgård-Jurik is generally believed to be secure.

The interesting question is of course what happens when the voters aren't honest or the server tries to cheat. There's a lot of nice cryptography in the answers to those questions.


What is encrypted with the key to give the keystream in CTR mode exactly?

The counter is increased for each block in a message. However, it is restarted at zero for the next message. That way only the nonce is required to be different. If you can synchronize the counter over multiple messages then yes, just increasing the counter is secure. However, you would loose the ability to encrypt messages in parallel, and you would somehow need to keep track of the counter when finishing encrypting a message.
Note that the 8 byte nonce and 8 byte counter is just one way to create a unique input for the block cipher. Other schemes / sizes are certainly possible. For instance, you could use the ID of an entity in there to separate those for the same key (a bit for a client & one for the server). Generally however, we keep to a nonce and counter in that order. Domain separation is often performed by using different keys for different purposes.
Beware that it is often up to the user to make sure that the counter doesn't overflow into the nonce. Furthermore, if the nonce is randomized then you should take note of the birthday paradox; it might be a good idea to increase the nonce size compared to the message size. E.g. a 32 bit counter would still leave you with $16 \cdot 2^{32} = 64\ \text{GiB}$  message size. That should even be enough for most high bitrate movies, and it would leave you with a full 96 bits for the nonce. The authenticated cipher mode GCM - which uses CTR mode internally - does exactly specify 64 GiB - 32 bytes as maximum message size, so you can guess the nonce and counter size by that alone.


DES-CBC with random IV - how big is the keyspace? Can COTS tools crack it?

Is the keyspace really 120 bits?

No. It's still 56 bits, at least when multiple blocks are encrypted. For CBC mode then you can try and decrypt a block with the key, XOR it with the previous ciphertext block you should get a plaintext block. If you did this for the last plaintext block you'll have the PKCS#5 padding to find. If that's correct then you can start looking if you can produce valid plaintext.

If only one block is encrypted then the IV acts as a one-time-pad. In that case you will have to guess the password (presuming you have the salt of course).

  Am I missing something or is hashcat not capable of cracking this?

Could be. But it would probably not be that hard for an accomplished programmer to program it in. Hashcat seems to focus on the password hash itself. Assuming the password is not too complex, guessing it may still be the best way to try and decrypt the ciphertext.

  Can other tools crack it?

Well, cracking single DES can be done by specialized hardware for sure (a list is here). Asking for resources like that is off-topic though.

  Is it even possible to deduce correct outputs without making assumptions on expected output (eg all output must be ASCII data, or match a file header)

Well, other than the padding, yes, you must be able to test if the plaintext is comprehensible in some kind of way. However, if you decrypt many blocks the plaintext is likely not all that random, so you could test for that. If it compresses well, for instance, it may be worth another look (but compression is generally pretty expensive).


Multiplying integers modulo $2^{255}-19$ using the Curve25519 polynomial reduction algorithm

The paper states

  $R$ contains $2^{255}x^{10}-19$, which represents $0$ in $\mathbb Z/(2^{255}-19)$.

In other (slightly simplified) words:
  $$x^{10} \;\;\text{is}\;\; 2^{-255}\cdot19 \text!$$
(Note that this contradicts your comment to the question: $x^{10}$ does not represent $2^{255}$.)

To understand this, recall that a value in $\mathbb Z/(2^{255}-19)$ is represented by a polynomial which has that value at the point $1$. Indeed, evaluating $2^{255}x^{10}-19$ at $1$ yields precisely the modulus $2^{255}-19$, hence identifying it with zero does not change the represented value.
Now observe that reducing modulo $2^{255}x^{10}-19$ means identifying that polynomial with zero.
The resulting relation can also be stated as
$$\begin{align*}
&2^{255}x^{10}-19 \;=\; 0
\\\iff\quad& 2^{255}x^{10} \;=\; 19
\\\iff\quad& x^{10} \;=\; 2^{-255}\cdot 19
\text, \end{align*}$$
as claimed. Thus you can always (for instance: when reducing degrees) replace $x^{10}$ by $2^{-255}\cdot19$ without changing the represented value.


Diffie-Hellman "handshake" vs RSA "handshake"

Using a client's RSA public key to encipher a session key generated by the server is possible, but has a several disadvantages:

If the client's RSA private key leaks in the future, past communication sessions can be deciphered; there is no forward secrecy, like there can be in some Diffie-Hellman variants. The only option to get that desirable property would be to use a new RSA key pair for each exchange, but then

the server has no way to verify the public RSA key generated by the client, thus the protocol might become vulnerable to a man-in-the-middle, unless the client also has a long-term key to sign it's one-session RSA public key.
as pointed in that other answer, it requires generation of an RSA key on the client side for each session, and that is typically quite slow.

The client does not participate in the generation of the session key, thus might be vulnerable to replay, and rightly less confident in the session key (one generator more easily becomes stuck or low-entropy than the combination of two generators implemented by two parties).
RSA decryption on the client side is significantly more compute-intensive than the whole Diffie-Hellman exchange needs to be (same for the signature of the RSA public key needed for forward secrecy, if that signature is RSA-based). That's true if DH is performed on a group $\mathbb Z_p$ (notice that the modulus is of the same order of magnitude in RSA and DH for comparable security, but the decryption exponent in RSA has about as many bits as the modulus, when it can be much shorter in DH; we are talking e.g. 2048 versus 256 bits, and commensurate performance gap; use of RSA CRT does not fully offset that); the difference in performance can be even larger if we use an elliptic-curve group for DH.


This will not be secure in general, and is not recommended.  The reason is that a PRG is guaranteed to produce a pseudorandom output only if its input is uniformly random (or pseudorandom).  Moreover, several PRG outputs are jointly pseudorandom only if the PRG is run on independent seeds.  But here you are invoking the PRG on "structured" inputs, i.e., the counter part is known and predictable (hence not (pseudo)random), and the key part is reused multiple times.

Concretely, here is a secure PRG $G$ for which your construction is completely insecure: let $G'$ be a secure PRG, and define $G(s \| \text{ctr}) = G'(s) \| \text{ctr}$, where $\text{ctr}$ has the same length as the counter you use in your construction.  This is still a secure PRG because in proper usage, $s$ and $\text{ctr}$ are uniform and independent.  However, your construction is insecure when instantiated with $G$ because the (public, non-random) $\text{ctr}$ part is simply "passed through" to the output, and the successive calls to $G$ always produce the same $G'(s)$ part.

CTR mode with a PRF is OK because a PRF has the property that even for adversarially chosen inputs (e.g., the counter values), the outputs of the PRF (on the same random secret key) are jointly pseudorandom.


Does it make sense to have a 4000 bit long key?

A 4000-bit RSA key is reasonable (more precisely, that would be the bit size of the public modulus; and 4096-bit would be more common). But it is not reasonable to memorize it (or, more precisely, that the owner try to memorize the corresponding private key); and that's practically never done.

One does not ask normal users to memorize or remember a key, or other information, with more than perhaps 50 bits worth of entropy (say as 8 characters among 77, or 2 phones numbers); even that is hard, and XKCD's method is probably more reasonable.

Long asymmetric private keys are usually

Stored encrypted by way of a symmetric algorithm using a stretched password/phrase as key, and stored on disk as a file; that's what PGP, GPG, and many other programs do.
Not stored, but rather re-generated at each use, from a passphrase combined with stretching seeding a CSPRNG used by the key generator; advantage is that the passphrase entirely replaces the private key in normal usage; but that makes safe passphrase change impossible; and requires a lot of stretching and a long passphrase to be secure.
Stored (and while we are at it used) inside a Smart Card protected by PIN with error counter (locking the card after 3 consecutive errors).


Can Hash Functions take fixed-size input?

The C#/.NET GetHashCode() is not a cryptographic hash function.  As a non-cryptographic hash function I think what you've written is reasonable assuming that X and Y are the only "public" properties that make up the object.
Having said that, cryptographic hash functions are very different both in implementation and purpose than C#/.NET/Java hash codes and probably other languages as well, so you might want to take this question to a more appropriate venue.


Has anyone implemented a public-key encryption scheme using a universal one-way function?

We don't know of any construction of PKE based on a universal OWF. Actually, we do not even have any plausible candidate PKE that would be based on an arbitrary OWF. Obtaining such constructions is a major open problem. We know that there is no black-box construction of PKE from any OWF by a seminal result of Impagliazzo and Rudich. Of course, we cannot rule out all possible constructions: since we believe that both PKE and OWF exist, a valid construction of PKE from any OWF is: ignore the OWF and take a PKE which exists.
In any case, universal OWFs are too inefficient to be really useful in practice. Levin's initial construction is really, really super-duper inefficient. Levin also gave a more combinatorial construction based on tiling in this paper, but that would still be way to inefficient for any practical purpose (though perhaps "implementable in theory", unlike his first candidate).
There are constructions of universal PKE (that are secure if any PKE exists), see for example the pointers in this paper, paragraph "Brief history of combiners and universal cryptographic primitives" in the introduction.

EDIT: answering the question in the comment
Universal cryptographic primitives are closely related to cryptographic combiners. A $(1,n)$-cryptographic combiner takes $n$ candidate cryptographic primitives, where one of them is guaranteed to be correct and secure (but we do not know which one), and produces a single combined correct and secure primitive.
Combiners and universal constructions have been formally studied in this work. The authors formally prove that the existence of a $(1,n)$-combiner for a primitive implies a universal construction of the primitive.
Then, their paper also provides a $(1,n)$-combiner for key agreement protocols; by their previous result, this implies a construction of universal key agreement. Furthermore, their construction is round-preserving: the final key agreement has the same round complexity as the candidate which had the highest round complexity in the combination.
This is actually more general than the result you are looking for, because a PKE is just a 2-round key agreement. Indeed, take a 2-round key agreement protocol between Alice and Bob, where Alice speaks first. Define the first flow of Alice to be the public key, and the secret state that she keeps to be the secret key. Given this first flow, Bob can compute his output, i.e., the shared key (since he will not receive any further message). An encryption of a message $m$ can then simply be defined as (second flow of the protocol, $K \oplus m$) (where $\oplus$ denotes the bitwise XOR): given the second flow and her secret state, Alice can recover $K$ (by the correctness of the key agreement), from which she can unmask $K \oplus m$ and retrieve $m$. Security of the encryption scheme follows from the unpredictability of the key in the KA protocol.
Furthermore, this is actually a 2-way equivalence: given a PKE, it is straightforward to build a 2-round KA protocol (I'll let you check it).
Summing up: there is a $(1,n)$-combiner for two-round key agreements (hence in particular for PKE) by the result of the work I pointed to above, where the result of the combination is still a 2 round KA. By their other result, this implies a universal construction of two-round key agreement. By the simple reduction I gave above (which is a standard exercise), this implies a universal PKE.


How to decrypt using CRT, and then verify by encrypting without CRT?

The square and multiply algorithm allows you to compute $g^k$ in an arbitrary group using $O(\log k)$ multiplications, instead of the $O(k)$ you would expect.
This is done by letting:
$$k = \sum_{i = 0}^{\lceil \log_2 k\rceil} 2^i k_i,\quad k_i\in\{0,1\}$$
To be the base-2 decomposition of $k$.
Then, we have that:
$$g^k = g^{\sum_{i = 0}^{\lceil\log_2 k\rceil}2^ik_i} = \prod_{\substack{0\leq i \leq \lceil\log_2 k\rceil\\k_i = 1}} g^{2^i} $$
I'll demonstrate the computation for your particular case, where we want to compute $721^{17}\bmod 1147$.
Note that for modular arithmetic, we additionally have Euler's Theorem to work with, which states that:
$$x^{\varphi(N)}\equiv 1\bmod N$$
Where $\varphi(N)$ is Euler's totient function.
Using basic properties of $\varphi$, one can compute that $\varphi(31\times 37) = 30\times 36 = 1080$.
So throughout our computations, we have the identity $x^{1080}\equiv 1\bmod 1147$ (which unfortunately ends up not being useful).

One can compute by hand that $721^2 = 519841$, which we can then reduce mod $1147$ to get $721^2\bmod 1147 = 250$.
We can repeat this to find that $250^2 = 62500$, which we reduce mod $1147$ to get 562.
We square this again to get 315844, which we reduce mod 1147 to get 419.
Finally, we square this again to get 175561, which we reduce mod 1147 to get 70.

Collecting together these computations, we get:
\begin{align}
721^{2^0} &= 721 \mod 1147\\
721^{2^1} &= 250 \mod 1147\\
721^{2^2} &= 562 \mod 1147\\
721^{2^3} &= 419 \mod 1147\\
721^{2^4} &= 70 \mod 1147.
\end{align}
Note that $17$ decomposes base 2 as $1 + 16 = 2^0 + 2^4$.
We can then find the result via:
$$721^{2^0}\times 721^{2^4} = 721\times 70\mod 1147 = 50470 \mod 1147 = 2\mod 1147$$

You may look at this and think it still involved a ton of multiplications of three digit numbers.
This is true --- this is the group operation in $(\mathbb{Z}/1147\mathbb{Z})^*$, so one expects to have to do it a number of times.
You can count to see that we only used 5 multiplications, instead of the 16 one would naively expect. It's still not great to do by hand though, but the only way I know of making the computations better by hand is by using the Chinese remainder theorem, which you specifically don't want to be used.


Simply using password as a third "private key" for PAKE

Here's the problem with this scheme: suppose $A$ is the honest client, and $B$ is a dishonest server (who doesn't know $s$).  Then, $A$ tries to log in, he selects $a$ and transmits

$$A = g^{as} \bmod p$$

Then, $B$ just picks a random value $b$, and transmits

$$B = g^b \bmod p$$

Then, $A$ will compute a 'shared secret' $$S = B^a \bmod p$$ (which would be $g^{abs} \bmod p$ had $B$ executed the protocol honestly, instead, we have $S = g^{ab} \bmod p$).  Then, $A$ sends a message $M_S$ keyed by that shared secret (whether it be a key confirmation message or an initial encrypted data exchange, it doesn't really matter).

$B$ has no further interactions with $A$.

Then, here is what $B$ can do; he can pick an entry in his dictionary $password'$ and compute $s' = hash(password')$.  He can then compute $S' = A^{s'^{-1}b} \bmod p$; if he happened to pick the correct password, then $s = s'$, and so $S' = A^{s^{-1}b} = g^{as \cdot s^{-1}b} = g^{ab} = S$, and so he can use that shared secret to verify the message.

If he didn't happen to pick the correct password, he can go back and select another entry in his dictionary, and repeat the off-line computation until he finds the right entry.

Bottom-line: with your protocol, an active attacker can do a full dictionary search as the result of a single exchange.


How to find a generator g for a large prime p?

Here's one easy approach: Pick a large safe prime $p = 2q + 1$ for prime $q$.  If you pick $p$ congruent to 1 or 7 modulo 8, then 2 is a quadratic residue modulo $p$, and thus generates a subgroup of large prime order $q$.  If you pick $p$ congruent to 3 or 5 modulo 8, then 2 is not a quadratic residue modulo $p$, and thus generates the entire group $(\mathbb Z/p\mathbb Z)^\times$.  There are, of course, other choices of generator, which you can use the law of quadratic reciprocity to figure out.

For more general primes $p$, if you know the factorization of $p - 1$, then you can compute generators of all the subgroups independently and combine them with the Chinese remainder theorem.  If you look up Schnorr groups, e.g. in DSA parameter generation, you'll find a special case of this for primes $p = kq + 1$ where $q$ is the prime subgroup order of interest: simply pick $h \in (\mathbb Z/p\mathbb Z)^\times$ uniformly at random until you find one with $h^k \not\equiv 1 \pmod p$, and you've found a generator of an order-$q$ subgroup.  You can get this by picking a prime $q$ first and varying $k$ until you find a prime $p$ in the desired range.

If you don't know the prime factorization of $p - 1$, then Sage is probably computing it for you!  That might take a while if $p - 1$ is 1024 bits long.

(Caveat: I don't know whether you mean Elgamal encryption or Elgamal signature, nor whether either one has any requirements other than the decisional DH assumption, because approximately nobody ever uses Elgamal encryption or signature these days.)


What you're actually looking for is called the cycle length most of the time in cryptography.

For a random mapping $f:\{1,2,\ldots,k\} \rightarrow \{1,2,\ldots,k\}$ the cycle length is expected to be $\sqrt{\pi k/8}$ and the tail length is expected to be the same.
If you want more details and some fancy illustrations, the Handbook of Applied Cryptography (PDF) has them.

If you model a cryptographic hash function as a random mapping (which you do most of the time), then you'd expect a cycle length of $\sqrt{\pi 2^n / 8}=\sqrt{\pi}\cdot 2^{\frac{n-3}{2}}$ which is $\approx 2^{127.325748064736}$ for $n=256$, which is the case for SHA-256.

So the TL;DR is:
No it has not been proven that no such $n,k$ exist, but chances are that they exist and range in the area of the values I showed above, which are of no practical relevance as of today.


Size of bitwise OR between vectors represented as polynomials

It holds that $$\begin{align}|A \vee B|&=d-1-|\overline{A \vee B}|\\
&=d-1-|\overline A \wedge \overline B|
\end{align}$$

Define $K(x)$ as the polynomial of degree $d-1$ with all 1 coefficients. $\overline A$ can be represented as the polynomial $K(x)-A(x)$.

Thus the desired $|A \vee B|$ is obtained by subtracting from $d-1$ the coefficient for $x^{d-1}$ of the polynomial $(K(x)-A(x))\cdot(K(x)-\tilde B(x))$, where $\tilde B(x)$ is $B(x)$ with "inversion" of coefficients, that is the coefficient of degree $i$ becomes coefficient of degree $d-1-i$.

We can use polynomial addition rather than subtraction: $d-1$ minus the coefficient for $x^{d-1}$ of the polynomial $(A(x)+L(x))\cdot(\tilde B(x)+L(x))$ also works (where $L(x)$ is the polynomial of degree $d-1$ with all $-1$ coefficients).


Is there any concrete reason to call BLAKE more secure than BLAKE2?

I guess that reducing the rounds is indeed the main reason to call it less secure. Generally attacks are over a specific number of rounds. If better attacks are found then the reduction of rounds could mean that Blake2 gets broken while Blake is not.

How secure something is is up for discussion for the simple reason that we cannot predict the future. I guess that the authors were confident enough in the overall structure of Blake to make the changes.

Neither algorithm has been broken so up to now they are right and Blake2 is as secure as Blake. The full rounds version of neither is affected by the attacks.

However as an attack is more likely to affect Blake2 you can still argue that Blake2 is less secure if an uncertain future is taken into account. With so few rounds broken you can argue that the difference is minimal (AES has many more broken rounds) but it's there.


Extracting Randomness from a Poisson Distribution

The question's method is not secure absent a model of the source. In particular, applied to a source evolving in time as this sawtoothassumed of period several times the sampling time between Brightness(0) and Brightness(1), the output will be terribly biased towards 0, because the function is decreasing most of the time (this effect will decrease with added Gaussian noise, spacing the samplings).

Another issue is that multiple pixels can output correlated bits.

Both effects might well occur in practice, for a variety of reasons: switching regulator of the power supply of the gizmo, or of the LED source of the ambient lighting. In a cryptographic context, adversaries often have some level of access to a RNG, and might induce that effect on purpose (e.g. varying the power supply, or a light source). And by a corollary of Murphy's law often verified in this very context, such things will happen without explicit adversaries (e.g. as the effect of aging of power supply capacitors) and at the worst time.

  The data generated using this method passed 15/15 NIST tests

If a source fails any statistical test¹, this conclusively proves that the source is bad from a cryptographic perspective. But if the source passes all tests, it can still be horribly bad from a cryptographic perspective; the best that can be reasonably be said is that the source, as tested, was free from the particular defects that the tests are designed to detect.

My though experiment with the sawtooth shows that the source could fail under different, realistic conditions. And it is trivial to design a bit source that passes all tests, yet is terribly weak cryptographically.

¹ significantly more often that predicted by the test's $p$-value, with the test correctly designed, implemented and applied.


Difference between decryption and deciphering?

There's no actual technical difference, but it's sometimes used in different contexts.

Decryption: Used when talking about reversing an encryption of any type and when you know for sure that a message has been encrypted.

Deciphering: Used when (mostly) turning a ciphertext back to the plaintext, i.e. when a sentence has been encrypted with some sort of cipher like for example Caesar or Vigenère. It's also appropriate to use this term if people assume that a message has been encrypted or obfuscated.


Birthday attack on hash functions derived from a collision-resistant hash function

Hint:  Can you break down the problem of finding a collision in $H_2$ into two independent subproblems that you can compute separately, or do you have to find a collision for all of it together?  What about $H_3$?


Is this a valid scheme to authenticate through a 'human-readable' certificate?

No, it is not. There are several misconceptions with your scheme.

First, your question/answer pairing does simply not contain enough entropy. This is much less entropy than your common "please choose a password" input, because you can't just use all words/numbers/common symbols. You have to stick to answers that make sense. This is what Ricky Demer hinted at in his comments. Even using scrypt or another password based KDF will be able to negate this fundamental issue.

Secondly, your 'salt' is entirely pointless. Salts are used to prevent attacks (multi user setting, rainbow tables), which are not considered in your scenario. You assume Eve to have only access to the communication network.

Thirdly (and most important): Your scheme mixes key exchange and authentication, but has vulnerabilities with both regards: Neither Bob nor Alice have a way to determine, if a question is from the other partner or was actually modified by Eve. She can just swap out the questions to those she is knows the answers to (possibly from a previous exchange, where she researched the correct answers). The question/answer format is not a suitable challenge-response mechanism, because there is no intractable computational problem (e.g. Diffi-Hellman) involved.

From a computational point of view, this has no security at all, because the questions are sent in the clear, knowledge of a question almost immediately implies knowledge of the possible answers, and then you just throw a hash function on top. And Eve can do that all by herself as well. And even worse, she can just take her time, find out the correct answers to the easy questions and decrypt everything afterwards.

The only way to use this would probably be to use the "unique serial number" from the pen you mentioned, and limit its usage to a single time. That means, basically you got something like a one-time-password and use it to seed a CSPRNG. But if you limit yourself to that, you can just leave out the clunky non-secure question/answer game.


Yes, HMAC with a sufficiently long key will survive Grover's algorithm.  Grover's algorithm breaks a cryptosystem with a $n$-bit key using $2^{n/2}$ (quantum) steps of computation.  Therefore, in practice, a 128-bit key is likely to survive Grover's algorithm, and a 160-bit key almost surely will.

So, HMAC with a 160-bit key is safe against Grover's algorithm, and HMAC with a 128-bit key is almost certainly safe enough against Grover's algorithm for most purposes -- even assuming someone figures out how to build a working quantum computer.


What is the efficiency of the new Crown Sterling semiprime factoring method?

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works.  For a semiprime $n$ chosen by modern RSA key generation methods, there are approximately $\sqrt n$ candidate solutions to check, which is also the expected cost of this method.  For instance, with RSA-2048, it will cost approximately $2^{1024}$ trial boogers.

The technical term for everything about these clowns is ‘uncastrated male bovine stool’.*  There is no more merit to the technical claims of Crown Sterling than there is to Treadwell Stanton DuPont.  The company's method is quite simple: the CEO Robert Grant is a scam artist who presumably uses technobabble like this to defraud unwary investors, and who sank some of the money into buying the prestige of a BlackHat talk slot (which is something that BlackHat really shouldn't offer) in order to drum up more hype around their scam.

And then they act the victim in a bogus narrative of persecution by the dominant establishment when subjected to universal derision by any competent cryptographers who bother to look at the nonsense.

So, what did these scam artists claim?

In their arXiv draft (which they proudly claim Cornell University published even though anyone can upload a draft to the arXiv with no peer review), Robert Grant and Talal Ghannam:

(§II) made the remarkable observation that every prime above 3 is congruent to $\pm1$ modulo 6 (proof: $2 \mid 6k \pm 2$ and $3 \mid 6k \pm 3$; this is the newest result they recycled, several centuries old—first published no later than 1509 and first proven no later than 1603, according to Dickson pp. 7–9, but quite possibly known earlier because it's so obvious);
(§III) reinvented the sieve of Eratosthenes several thousand years late;
(§IV) discovered that $x \mapsto x \bmod 9$ is a ring homomorphism (a technique known since antiquity and more commonly called ‘casting out nines’), and figured out that if $x \equiv 3 \pmod 9$, $x \equiv 6 \pmod 9$, or $x \equiv 9 \pmod 9$, then $x$ can't be prime (proof: duh);
(§VI) deluded themselves into thinking if $pq \equiv 1 \pmod{10}$ then either $\{p \bmod 10, q \bmod 10\} = \{3,7\}$ or $p \equiv q \equiv 1 \pmod{10}$ (counterexample: $19\cdot 29 = 551$; perhaps they used ‘proof by trying numbers until I got bored’); and
(Appendix) proved that $p \equiv \pm 1 \pmod 6$ implies $p^2 \equiv 1 \pmod{24}$, a trivial consequence of the Chinese remainder theorem first stated no later than nearly two millennia ago (proof: $p \equiv \pm1 \pmod 2$ so $p \bmod 8 \in \{1,3,5,7\}$ so $p^2 \equiv 1 \pmod 8$, and $p \equiv \pm1 \pmod 3$ so $p^2 \equiv 1 \pmod 3$; hence by CRT, $p^2 \equiv 1 \pmod{3\cdot 8}$).

Earthshattering stuff, I'm sure you'll agree.
In March, they published a press release as Strathspey Crown LLC announcing their findings with no additional technical claims.
In August, at BlackHat, they spent 115 000 USD for an unreviewed talk slot to debut Time AI, which

  uses five dimensions of encryption, leveraging biometrics, music’s infinite variability and dynamic change to secure your data

and is sometimes quantum and which was predictably laughed off the stage at considerable cost to BlackHat's reputation as a purveyor of fine corporate stoogery.

(Crown Sterling have since sued BlackHat because people were mean to them and BlackHat did nothing to stop people from pointing out their idiocy when they presented it at the BlackHat podium they bought.)
In September, they held a live stunt where they alleged to factor a 256-bit semiprime on a laptop on stage.

For perspective, this record was surpassed no less than a quarter century ago by Dixon & Lenstra, who reported solving a 110-digit/364-bit factoring challenge.  The 129-digit/426-bit factoring challenge announced in Scientific American by Martin Gardner in 1977 with the advent of RSA was solved in 1994 by Atkins, Graff, Lenstra, & Leyland revealing the magic words Squeamish Ossifrage.  Today you can factor a 512-bit integer for 100 USD using CADO-NFS and msieve on Amazon EC2.

Well, actually, Grant walked back the claim that it was a laptop (apologies for Twitter link to screenshot of Instagram; I don't deal in Instagram so I can't link to the page directly).  But randos on Twitter showed how you, too, can break this record in the privacy of your own living room on your own laptop in comparable time.

The fraudsters gave no details about the alleged novel factoring algorithm actually used in the demonstration.  A poor soul—pour one out for him!—who actually bothered to watch the video (which I'm not linking because I don't want to give these fraudsters any clicks) noted that some of the output of the alleged program appears to be output from CADO-NFS.
What about the Instagram post?  (Always a highly reputable venue for mathematical and cryptologic publication!)  The claim seems to be that you can find the factors of $pq$ in the decimal expansion of $1/pq$.

First, it doesn't always work.  For example, $1/(11\cdot13) = 0.\overline{006993}$ in which neither factor 11 nor 13 appears.  But one might wonder whether it probably happens.

The period of the decimal expansion of $1/pq$ for prime $p$ and $q$ is $\operatorname{lcm}(\operatorname{ord}_p 10, \operatorname{ord}_q 10)$, which is usually not much smaller than $pq$.  If we model the expansion as a uniform random digit string $pq$ (not $\log_{10} pq$, but $pq$) digits long, what's the probability of finding particular a $\log_b p$-digit string, namely $p$, in it?  The expected number of times that any particular $m$-character needle appears as a substring of a uniform random $h$-character haystack in a $b$-symbol alphabet is $(h - m + 1) b^{-m}$ (proof: exercise for reader).  Here $m \approx \log_b p$ and $h \approx pq$, so this is about $$(pq - \log_b p + 1) b^{-\log_b p} \approx q.$$  Cursory random experiments suggest that this is a reasonable model for the substring search, and I know of no theory that would suggest otherwise; it is up to the fraudsters to put up or shut up if they can prove anything better than this.

In other words, in this model, there's a reasonable probability that the the method works if you're willing to search through about (say) $2^{1024}$ possible candidate factors of the 2048-bit semiprime in question.  Which, as it happens, is essentially random trial division.  The fraudsters make it look easy by showing a screenshot with the answer already highlighted in a selectively cropped fragment that skipped over thousands of digits—about as many digits as the value of the numbers we're searching for.

In brief, these clowns—who are trumpeting thousand-year-old mathematical results on a preprint host open to the world as publications by Cornell University—appear to have at best caught up to the state of the art in factoring records from a quarter century ago by copying an alleged algorithm into software that looks just like off-the-shelf factoring software…or they're just using the off-the-shelf factoring software to wow an audience of chumps.

* Stack Exchange may have a profanity filter that has the unfortunate effect of interfering with using certain precise technical terminology.


generate hash of all handshake messages for verify data (DTLS)

First, I am assuming, per https://security.stackexchange.com/questions/29172/what-changed-between-tls-and-dtls, that the client handshake protocol in DTLS is not different from that in TLS over TCP.  This seems a safe bet since the client/server encrypted handshake protocol in OpenVPN's UDP implementation is the same as in standard TLS over TCP.

I am not sure what you mean by "using sha1", since the client encrypted handshake message hash $V$ use a concatenation of MD5 and SHA1 hashes of the concatenated handshake (TLS opcode 0x22) messages.  Details are in Davies' "Implementing SSL/TLS," pp. 345-350:

$$V= \text{PRF}(\text{master secret},\text{"client finished"},\text{MD5}(H)\|\text{SHA-1}(H),12)$$

$H$ is the concatenation of the handshake messages; "PRF" is TLS-PRF, a Python implementation of which follows:

def TLS_PRF(secret,label,seed,length):
    def P_HASH(secret,seed,length,h):
            i = 1
            A = [seed]
            out = ''
            while len(out) < length:
                    A.append(HMAC(A[i-1],secret,hasher=h))
                    out += HMAC(A[i]+seed,secret,hasher=h)
                    i += 1
            return out[:length]
    f=''
    md5 = P_HASH(secret[:len(secret)/2],label+seed,length,hashlib.md5)
    sha1= P_HASH(secret[len(secret)/2:],label+seed,length,hashlib.sha1)
    for m,s in zip(md5,sha1):
            f += "%c"%(ord(m)^ord(s))
    return f

If you run the concatenated 0x22 messages through the complicated process noted above, you should get agreement with at least the hash in the client's plaintext EHM.

Calculation of the server EHM hash is slightly trickier.  To $H$, the extant concatenated 0x22 messages, you will need to concatenate the decrypted 12 byte value $V$ contained in the client EHM.  Do not forget, per the RFC, to prepend this 12 byte value with the message type (probably 0x14) and three byte length value (0xc) - so add 14 00 00 0c <12 bytes of V> to the $H$ used for the client EHM, run that through the PRF (using "server finished" for your label), and you should have your final hash value.

Calculation of DTLS Application Data MACs

This is in response to an additional question posed by OP in comments to this answer, concerning calculation of the Application Data (DTLS packet type 0x17) MAC values.  According to RFC 4347:

  The DTLS MAC is the same as that of TLS 1.1. However, rather than
     using TLS's implicit sequence number, the sequence number used to
     compute the MAC is the 64-bit value formed by concatenating the epoch
     and the sequence number in the order they appear on the wire.  Note
     that the DTLS epoch + sequence number is the same length as the TLS
     sequence number.

Here is some Python code that implements this for a packet at the beginning of the DTLS session, with the starting SeqNum and EpochNum values.  $D$ is the decrypted application data including the "decrypted" IV at the start of the message, and the MAC and padding at end of message (basing all of on this on how Wireshark dissects DTLS traffic).

    SeqNum="000000000001".decode("hex")    #passed over wire
    EpochNum="0001".decode("hex")          #passed over wire
    PacketType="17".decode("hex")          #Application Data
    ProtocolVersion="feff".decode("hex")   #DTLS 1.0
    PacketLength="0400".decode("hex")      #Tricky - the length of AppData (as passed in clear over the wire) minus 0x20 bytes of SHA-1 MAC and padding
    D="0xf00ba..."                         #The decrypted blob

Then the HMAC will be:

HMAC(EpochNum+SeqNum+PacketType+ProtocolVersion+PacketLength+D[0x10:-0x20],hmacKey)

Don't forget the exclude the first 0x10 bytes (which will be the meaningless, "decrypted" IV) and the last 0x20 bytes (MAC+padding).  Apart from not including/ordering EpochNum and SeqNum correctly, the only other big pitfall, as previously noted, is forgetting to adjust the PacketLength to reflect the fact that the MAC obviously doesn't include itself as part of the message (see Davies, p. 376 for a discussion of this point in traditional TLS context).


The output of the block cipher is used as the new key, and also passed to the "output block" function, which is referenced in the NIST document as $B^m_R$.

The purpose of the IV $R$ and the function $B^m_R$ is to reduce the output to a smaller size in a manner that hides the true output of $f$. Too large an output allows key recovery.

The output of this function is an $m$-bit value, which is then used to build the keystream. The inputs are $R$ and the $n$-bit output of the block cipher. $R$ is a binary $m \times n$ matrix, and is multiplied against the block cipher output modulo 2 arranged as an $n \times 1$ matrix, resulting in a matrix of $m \times 1$ bits, which is used for the output.

An example of this uses the following:

$f = $ AES-128
$n = 128$
$m = 8$

$R$ would be an $8 \times 128$ matrix and require 128 bytes to build, and when multiplied against the 128-bit output of AES, would result in 8 bits of data (1 byte) for the keystream. $R$ must be unique to each message, and must be random and non-zero, but does not need to be secret. It can be built using a smaller amount of bits using appropriate methods (such as HKDF), as long as at least $n$ bits are used to generate it.

The constant input $p$ does not have any special requirement and is generally some constant, possibly even all 0 bits.

It is obvious that with a small output and the need to perform the key schedule for every iteration, the efficiency of KFB is very low, and thus it is generally not used for practical applications, despite the provable security bounds.

I assume a partial key feedback mode could be made using AES-256 with 128 of the key bits fixed, and the rest fed back from the output, or using some kind of shift mechanism.


$m^b = z^b \pmod{n}$ - single solution $m = z$?

Is it the only solution?

It will be iff $b$ and $\phi(n)$ are relatively prime.

If $b$ is relatively prime to $\phi(n)$, then the operation $x \rightarrow x^b \bmod n$ is a permutation of the set $\mathbb{Z}_n^*$, hence there will be exactly one solution to the equation $m^b \equiv z^b \pmod n$ (and since we know that $m \equiv z$ must be a solution, it must be the only one.

If $b$ is not relatively prime to $\phi(n)$, then there must be a nontrivial solution to $c^b \equiv 1 \pmod n$ (where nontrivial means "other than 1"); in fact, there will be at least $\gcd(b, \phi(n))-1$ such nontrivial solutions.  Values $m = z \cdot c^k \bmod n$ will be the other solutions to the equation.

As for finding these other solutions (which, as above, is equivalent to the problem of finding the nontrivial roots of 1), it's straight-forward if you know the factorization of $n$ (which is equivalent to knowing the value of $\phi(n)$; this includes the case of $n$ being prime.

First, we set $d = \gcd(b, \phi(n))$ and $e = b / d$ (and so $b = d \cdot e$, with $d$ being a factor of $\phi(n)$, and $e$ being relatively prime to $\phi(n)$.

Then, select a random value $r \in \mathbb{Z}_n^*$ and compute $s = r^{\phi(n)/d} \bmod n $; if $s$ happens to be 1, then go back and try another random number.

If $s \neq 1$, then set $c = s^{e^{-1} \bmod {\phi(n)}}$; that's one value of $c$

Now, if $d$ happens to be composite, then you might need to go through this procedure multiple times to find all the possible values of $c$; if $d$ is prime, then one value is sufficient (and the other roots of 1 are $c^k$ for $k \in \{2, …, d-1\}$

On the other hand, if you don't know the factorization of $n$, this is sometimes a hard problem, and sometimes not.  A case where this is not a hard problem; $b = 2$, which has $c = n-1$ as an easy-to-find solution.


HSMs: Encrypt/Decrypt - But Not Read or Export Key

Can HSMs be configured to store a key, and allow encryption or
  decryption with said key, but prevent any export or backup of the key
  itself?

Yes, because that's precisely what HSMs are designed to do*. Assuming of course you don't mind your public (encryption) key being exportable, but if you don't want that, just get an HSM that supports symmetric encryption.

*: Actually more often than not you don't want your high-value or encryption keys to be completely without backup as to allow recovery of plaintexts or continuation of operation in case the HSM dies, which is why HSMs tend to have mechanisms that allow to securely backup keys, unlike smart cards which instead require you to backup keys before putting them onto the card.


Given $ g^s, g^y , g^r, g^t, g^{st-rs}, g^{(yr+d)/t}$ , is it hard to distinguish $e(g,g)^{syr}$ from a random value?

No, it's no easier than the standard DBDH problem.

Here's the reduction that shows that: suppose that we have an Oracle that solves your problem (given $g^s, g^y, g^r, g^t, g^{st-rs}, g^{(yr+d)/t}, e(g,g)^x$ is $e(g,g)^x = e(g,g)^{syr}$?)

Now, suppose we're given $g^s, g^y, g^r, e(g,g)^x$, and are asked whether $e(g,g)^x = e(g,g)^{syr}$.

What we do is select a random values $t'$ and $z$, and compute $g^{t'} / g^r = g^t$ and $(g^s)^{t'} = g^{st-rs}$; we don't know the value of $t = t' - r$, but we know that it exists).  We further compute $g^z = g^{(yr+d)/t}$ (again, we don't know the value $d = zt - yr$; but we don't have to know).

Then, with these values, along with the values we got with the original query, we ask the Oracle (and get the answer).


Regarding the [B] and [C] parts of the question per the comments:
I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most SEA algorithm implementations work with any curve in the generalized Weierstrass form. (If it's not 1 then you can easily map into a curve with $B = 1$, the same way that short Weierstrass curves can be mapped into $a = -3$)
So basically:

Search for a Montgomery curve matching the criteria;
Then convert it into Edwards form.

One optimization is to instruct SEA to quickly discard curves whose order it knows beforehand that have a small factor (other than 4 or 8), see the tors parameter of the ellsea PARI/GP function, for example.
The paper "A note on high-security general-purpose elliptic curves" has a Magma implementation of the process (though IIRC it uses a slightly different approach). RFC 7748 has a Sage script that also searches for a Montgomery curve (though it will probably be much slower, since it doesn't seem to support that optimization).


Can I secure my key by XORing it with a hashed password?

You are using a Vernam-encryption (simple XOR), as for the one-time pad.

The general principle for Vernam is that it is perfectly secure as long as you never reuse the same key for more than one message, and gets utterly broken as soon as it is reused even once (this is the "two-time pad"). The key here is the hashed password, the message the key.

If one of your encrypted keys is leaked, all others encrypted with the same password are immediately broken, too (since you can get the password hash, which is the actual key). You normally don't want this property in an encryption system, even if it is only used for data which is of random nature and of only temporary use.

Instead, do one of the following things:

Use a real encryption (like a block cipher) with the hashed password as key and the stored key as input.
Use some (random) salt in the hash function, so that each use of the password gives another hash. Store the salt with the XOR-ed key.
Use a key derivation function to derive the actual key from salt and password. Do only store the salt, not the key in any form.

The OpenPGP message format uses some of these, I think.


The questions

Does the security of a hash function from the preimage attack also depend on the secrecy of the length of X.?

The preimage attack: given a hash function $h$ and a hash value $y$ the computationally bounded adversary tries to find a pre-image $x$ such that $y = h(x)$.
This is like an adversary trying to find a password given the hash of it with the known hash function. Note that one doesn't need to find the actual input value for the success of the pre-image attack. Any password with the same hash value will be work for the adversary.
There is no known practically successful pre-image attack on any cryptographic hash functions, even those that are practically broken with collision attacks like MD5 and SHA-1. There is a pre-image attack on MD5 that requires $2^{123.4}$ complexity by Sasaki and Aoki Finding Preimages in Full MD5 Faster than Exhaustive Search in 2009. This is still far from practical usage though it is faster than direct searching.
To hash a value one needs to apply the standard encoding of the message that includes the padding mechanism so that the hash fits into the block size of the hash function. NIST defines them for their standards. The block size can be like 512 bits in SHA256 or 1024 bits in SHA512.
If ever we find a successful pre-image attack, it will also reveal the size of the found pre-image and that was not necessarily the input used to generate the hash value. The padding mechanism, however, can prevent some attacks. Usually, the adversary has lots of freeness for the attack since hash functions can hash any size. This is used in SHA-1 collision attack (identical-prefix collision attack). If the size is limited, that can be a big problem too.

If the adversary knows the length of X, then it can easily brute force X for smaller lengths of X. I understand that smaller lengths of X will get appended and pre-processed into larger blocks but that does not stop the adversary from brute-forcing since there are no secrets in the pre-processing.

If the message space is small, then the adversary simply brute-forces all possible inputs. The current computational capabilities of the adversaries can be evaluated from public information. For example, the bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year on 06 August 2019.
During the candidate input generation and testing the hash value, the adversary will also apply the padding mechanism.
for each candidate in [0..2^t]
    paddedCandiate = pad(candidate)
    if hash(paddedCandiate) == y
       return candidate

where $t$ is the predetermined bound. This search space can be easily parallelized by dividing space into segments.
The padding mechanism is not a secret and nothing to do with the secrecy of the mechanism. In unkeyed hash functions, there is no secret.
If you fear that your small input space is vulnerable, you might look at keyed hash functions like HMAC, KMAC.


Can all asymmetric key pairs be reversed?

This depends on the public-key system (algorithm).

For RSA, technically the private and public key (i.e. the exponents, the keys share the same modulus) are symmetric, you can swap them, and it still works.

But you usually don't want to do this: The public exponent is usually a small number (like $3$ or $2^{16} + 1$) in order to speed up encryption/signature verification, and can thus be easily guessed. You don't want this property for a private key.

Also, in practice the private key is often not just the exponent $d$ and modulus $n$, but also the factors of the modulus (i.e. $p$ and $q$), in order to speed up decryption or signature. That kind of key certainly doesn't work as a public key.

For other public-key systems (like ElGamal/DSA, Diffie-Hellman, or EC), the relation between public and private key is not symmetric at all. In the examples mentioned you have a private key $x$ and a public key $y = g^x$ (with some kind of exponentiation operation which is difficult to reverse).

In these cases, you certainly can't swap out public and private key.


What kind of decryption is used in this example?

Well, it seems it is a basic substitution cipher, with a twist: some letters map to the same cipher text letter (not just e,r,t map to l, also e.g. n,u map to o . So decryption is not unique. But a pattern matching algorithm with a German dictionary could probably filter those. The mapping seems to group letters in such a way, that only one combination makes sense.

Anyway, from the example text you can probably find most character mappings, and then you just need to guess words based on valid combinations in a dictionary.

In general, I would not actually call this encryption at all. A scheme like this won't work for just any non-injective mapping, so it's unclear if there is some key involved or not. Also, an encryption scheme requires, that (with overwhelming probability) the decryption is unique and correct, s.t. $D(E(m))=m$.


I assume the question is related to academic work: why do we implement a protocol if we already know how efficient it is by a complexity analysis? The answer depends very much on the type of protocol. However, the answer typically is that a theoretical complexity analysis usually does not suffice to understand the concrete efficiency. If the "previously best known protocols" required a certain number of operations and your improvement is exactly the same but with less operations, then this could suffice. However, this is rarely the case. Rather, your protocol may have less exponentiations but more communication; it may have less symmetric operations but be less memory efficient. It is almost impossible to really know that it's more efficient without implementing it.

Another issue, which is certainly the case in secure multiparty computation (where I work), is that implementation helps us understand what the bottlenecks are. In fact, we are very often surprised at what the "expensive" part is. In just one example, in this paper (sorry for the self citation, but it's just a good illustrative example), we were very surprised to find out that a large percentage of the time went on a matrix inversion which had nothing to do with the cost of the cryptographic operations. Without implementing, we never would have found out about this.

One thing that as a field we have to improve upon is the quality of our work in this sense. We don't have good benchmarks and implementations and comparisons are all very ad hoc.

I will finish with one final comment. Despite the above, not all new protocols need to be implemented in order to be published. When the protocol contains an important new idea, or when it clearly beats the previous work, then it can be published without an implementation. However, follow up work with implementation is always important. (Of course, protocols whose claim is that of asymptotic and theoretical efficiency never need to be implemented.)


What is the difference between PPE and SPPE?

An efficiently computable Permutation Ensemble is (Weakly) Pseudo-Random

if and only if it is infeasible for an adversary with oracle access to

[a function that was chosen either from then Ensemble or uniformly from

the set of all permutations on bit-strings of the corresponding length]

to distinguish between those two cases.

An efficiently computable Permutation Ensemble is "Super" (= Strongly) Pseudo-Random

if and only if it is infeasible for an adversary with oracle access to

[$\hspace{.02 in}$[a function that was chosen either from then Ensemble or uniformly from

the set of all permutations on bit-strings of the corresponding length] and that function's inverse]

to distinguish between those two cases.


It seems that this is just a misunderstanding between bits and bytes.  32 bytes is 256 bits, so 32 bytes is more than enough.

The security of HMAC is very strong; the security is directly related to the minimum of the key size and HMAC output size. So using 32 bytes / 256 bits as output size is fine. You could use fewer bytes for the authentication tag (using the leftmost bytes is the default), but it is recommended to keep to the default. Using SHA-512/256 might be a good idea for larger messages on 64 bit machines. SHA-224 could also be an option if you require a smaller authentication tag. For a newer protocol you could go with KMAC / SHA-3.

AEAD ciphers almost exclusively use the block cipher for the final calculation to produce the authentication tag. If AES or an AES finalist is used then the block size will be 128 bits - which means that 128 bit is the maximum authentication tag supported. You could go for a smaller authentication tag than 128 for real time protocols or protocols for embedded devices. In that case GCM is not recommended as there are security concerns if smaller tag sizes are used for that mode. CCM or EAX mode would make more sense for smaller authentication tags. These modes use CBC-MAC and CMAC respectively.

Note that the verification of an authentication tag should be performed using a constant time compare.


Explain the fast Walsh–Hadamard transform in simple steps or pseudocode

The fast Walsh-Hadamard transform algorithm generally applies to Hadamard matrices $H_n$ which are of dimension $2^n\times 2^n, n\geq 1$. Using row and column transpositions, $H_n$ can be arranged so that it is of the form
$$H_n = \left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right].$$ As a special case, note that
$$H_1 = \left[\begin{matrix}+1& +1\\+1& -1\end{matrix}\right].$$

Now, the Hadamard transform of the (row) vector $\mathbf x$ of length $2^n$
is the row vector $\mathbf xH$ where, if we partition $\mathbf x$ as the
concatenation of $2^{n-1}$-vectors $\mathbf x_L$ and $\mathbf x_R$
$\bigr($that is, $\mathbf x = \big[\mathbf x_L, \mathbf x_R\big]\bigr)$, then we can write
$$\mathbf xH = \big[\mathbf x_L, \mathbf x_R\big]\left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right]
= \big[\mathbf x_LH_{n-1}+\mathbf x_RH_{n-1}, \mathbf x_LH_{n-1} - \mathbf x_RH_{n-1}\big].$$
This suggests that if we have already computed $\mathbf x_LH_{n-1}$ and $\mathbf x_RH_{n-1}$, we can compute $\mathbf xH$ in $2^n$ more additions/subtractions. So, we can proceed recursively, partitioning $\mathbf x_L$ into $\big[\mathbf x_{LL}, \mathbf x_{LR}\big]$ and
$\mathbf x_R$ into $\big[\mathbf x_{RL}, \mathbf x_{RR}\big]$, and
repeat the above calculations with shorter vectors,....

Pseudocode
would be something like

recursive function FHT$(\mathbf x)$
begin
partition $\mathbf x$ into two equal-length parts $\mathbf x_L$ and $\mathbf x_R$
$\mathbf y_L$ = FHT$(\mathbf x_L)$; $\mathbf y_R$ = FHT$(\mathbf x_R)$
return $\big[\mathbf y_L+\mathbf y_R,\mathbf y_L-\mathbf y_R\big]$.
end

The total number of additions/subtractions is $n2^n$; there are no multiplications needed


For perfect secrecy, does the keyspace need to be uniform?

The answer to your question in the title is No.
For example, let's modify a little the one-bit OTP considered in your question description (with a one-bit message space $M=\{0,1\}$). Instead of using a one-bit key $K=\{0,1\}$, we can use a two-bit key $K=\{00,01,10,11\}$ and discard its last bit when doing the xor. It's easy to see that perfect secrecy holds as long as the first bit satisfies uniform distribution, while the 2-bit key distribution is rather arbitrary.
Therefore, for perfect secrecy, the key distribution does not have to be uniform. Actually, this statement should be true for any kind of security. Security-wise, what really matters is the key entropy rather than the exact key distribution. We see uniform key distribution assumed almost everywhere because it is convenient to use (a weird key distribution could cause problems, e.g., for usability) and it gives us maximum key entropy.
Note that though seemingly contradictory, kelalaka's answer is also true; but it considers only the classical use of OTP where the keyspace matches the message space. In this case, the key distribution has to be uniform because a non-uniform key distribution xoring the message distribution will not generate a ciphertext distribution that has the same distribution as the messages.


Given only the information in the original question, it would be easy for an attacker to calculate generate an arbitrary message E, then calculate the Hash("This is message E + ab3ed") = 31415, and if the system can be tricked into trusting that 31415 is the hash of a valid message, there's no way to prove that E isn't really a valid sibling of B.

This may be why every hash tree implementation I've ever seen doesn't include the hash of the parent in the hash of the child.
Instead, it includes the hash of the children in the hash of the parent.

Say I have a graph of messages like this:

   A
   |
   B
  / \
 C   D

By including every child hash in the message to be hashed I can show that B is the only child of A, and C and D are the only children of B.

For example

Hash("This is message A; its child has hash e4c90") = ab3ed
Hash("This is message B; its children have hashes 83e39 and 456aa") = e4c90
Hash("This is message C") = 83e39
Hash("This is message D") = 456aa

Assuming a cryptographically secure hash, and assuming I somehow get the root hash ab3ed from a trusted source,
This way I can prove that C and D are the only children of B, and B is the only child of A -- i.e., B has no siblings.


Selecting secret value in certificateless identity-based encryption

I think there will be some kind of collision in selecting secret value.

What sort of collision could there be (that has a nontrivial probability of actually happening)?

If $p$ is the order of $g$, then $Pub_i = Pub_j$ only if $x_i = x_j$.  And, if $p$ is large (e.g. at least 256 bits), and we assume that $x_i, x_j$ are selected randomly and independently (that is, no one participant is allowed to peak at any of the other's secret, and they all have good entropy), then the probability of $x_i = x_j$ happening is $< 2^{-256}$, that is, mindboggling unlikely.

In fact, if we have, say 7 billion participants, and each one selects an $x_n$ randomly, the probability of there exists two different participants selecting the same value is $< 2^{-191}$, still mindboggling unlikely.

This does assume that the entropy of each participant is good; something that tends to be ignored in security proofs, but cannot be ignored when implementing the system.

  In security proof, they make assumption that secret value cannot be allowed to attackers. Is it enough?

They also assume (and they ought to make it explicit) that the discrete log problem is hard; that is, given the value $g^{x_i}$, it's hard to recover $x_i$.  If the group was small enough that someone would have a nontrivial probability of obtaining $x_i$, by guessing it (and computing $g^{x}$ to verify), well, that'd mean that the discrete log problem would be tractable.


Induction is problematic in computational cryptography - Why?

The problem with induction is what it typically hides. I'll give an example. Assume that I want to prove that $n$ samples of $X$ is indistinguishable to $n$ samples of $Y$, assuming that a single sample is indistinguishable. Instead of doing a hybrid argument, I prove by induction. The base case is immediate, since a single sample is indistinguishable by assumption. Next, I assume for $i$ and prove for $i+1$. In this claim, I prove that for every PPT adversary $\cal A_{i+1}$ who can distinguish $i+1$ samples with non-negligible probability, there exists a PPT adversary $\cal A_i$ who can distinguish $i$ samples with non-negligible probability (or a distinguisher who can distinguish a single sample, but let's leave that for now). It seems that this suffices for the proof to go through.

However, what happens if $\cal A_i$ runs in twice the time than $\cal A_{i+1}$ (this is of course fine since they are both polynomial time)? Then, when I "unwind" the induction, I will get the following. Assume that there exists a probabilistic polynomial-time adversary $\cal A_n$ who distinguishes $n$ samples with non-negligible probability; let $p(n)$ be its running time. Then, by applying the inductive argument repeatedly, I obtain that there exists an adversary $\cal A_1$ who distinguishes a single sample, but runs in time $2^n\cdot p(n)$, thereby contradicting nothing.

Another problem that can happen is as follows. Assume that our proof of the inductive step is such that $\cal A_{i+1}$ distinguishes with non-negligible probability $\epsilon(n)$ and as a result $\cal A_i$ distinguishes with non-negligible probability $\epsilon(n)/2$. This is of course fine since both probabilities are still non-negligible. However, when we unwind the induction, if $\cal A_n$ distinguishes with non-negligible probability $\epsilon$, we will have that $\cal A_1$ distinguishes with probability $\epsilon/2^n$ which is negligible. Thus, no contradiction is achieved.

In order to overcome this, one can prove explicitly in the inductive step that the running time difference between $\cal A_{i+1}$ and $\cal A_i$ is additive, meaning that there is an additional polynomial factor only. Then, over $n$ (or any polynomial) steps of the induction, the additional running time overall is still polynomial. Likewise, if there is a reduction in the distinguishing probability, then the result at the end is still non-negligible.

I have used induction once in a paper; see pages 22-23 of http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps, so it can be done. But one must be careful.

(A note: all of the above I learned from Oded Goldreich.)


Is ssl_sign safe as it is using OPENSSL_PKCS1_PADDING

You're fine.

There are several different padding methods listed in PKCS v1.5.  The method that has active attacks is actually a padding used during public key encryption - that is, it's used to encode the plaintext message before handing it off to the RSA public function. We don't use that method to sign messages.

For that matter, the attack model used against that PKCS v1.5 encryption padding doesn't apply to a signature method.  In that attack model, the attacker  generates bogus ciphertexts, and send them to the holder of the private key and see what it does with them, and uses that to be able to figure out the decryption of a specific ciphertext.  This doesn't apply to signature methods, as the holder of the private key just signs messages, and performs any necessary padding itself.


No, there isn't. There are too many different systems out there to make a generic tool.


Problems when using PBKDF2 to create an ECDSA private key from a password?

How are you going to trust the resulting public key that is required to verify anything signed by the private key?

How are you going to maintain security after you've authenticated?

ECDSA may be vulnerable against analysis using quantum computing.

You've only partly described one part of a cryptographic system. This means you've got plenty to worry about.


Practical OWP of the set of $k$-bit bitstrings for low $k$

Here is an outline of a system that would yield $k \approx 256$.

Let us select an elliptic curve (based on a prime field of size $N \approx 2^{256}$ with:

Is secure, and has twist security (that is, the discrete log problem on the curve and on its twist is infeasible)
Has a single point of order two (the $x=y=0$ point)
Both the curve, and its twist form a cyclic group (which is mostly a consequence of the previous two assumptions)

We'll select a generator of the curve $G$ and a generator of the twist $G^*$ (note: if you are basing this on Curve25519, then the conventional $g=9$ does not work, as that generates a prime-order subgroup, not the entire curve)

Then, if the order of the curve is $q$ and the order of the twist is $q^*$, then every value between 1 and $N-1$ can be represented as either (but not both):

The $x$ coordinate of a point $kG$, for some $1 \le k < q/2$
The $x$ coordinate of a twisted point $kG^*$, for some $1 \le k < q^*/2$

So, if we map the integers $k \in [1, q/2)$ to the $x$ coordinate of $kG$, and the integers $k \in [q/2, q/2 + q^*/2)$ to the $x$ coordinate of $(k - q/2 + 1)G^*$, I believe that gives a hard-to-invert permutation of the integers in the range $[1, N-1]$.  And, you can use the tricks you have listed to make that down into a slightly smaller range $[0, 2^k)$.

Do you see any obvious problems with this?


What is the difference between RSASSA-PSS signing and RSA-PSS signing?

Some authors draw a distinction between:

RSA-PSS, analyzed by Bellare and Rogaway in 1996[1] and proposed for IEEE P1363 in 1998[2], which is roughly defined in terms of $H(r \mathbin\| m)$, and
RSASSA-PSS, standardized in IEEE P1363-2000 and RSA PKCS #1 v2.1, which is roughly defined in terms of $H(r \mathbin\| H(m))$.

This distinction is significant: RSA-PSS relies only on target collision resistance[3] (or universal one-way hash function…ness[4]) of $H$, while RSASSA-PSS relies on full collision resistance of $H$.

Another way to view it is that RSASSA-PSS—like RSASSA-PKCS1-v1_5 and any other signature scheme where the message figures in only via $H(m)$—is vulnerable to collisions in $H$.  This spells bad news when $H$ is MD5, as many people used in practice for many years.  Academic cryptographers publicly demonstrated certificate forgery using an MD5 collision attack on RSASSA-PKCS1-v1_5[5][6]; the United States and Israel forged a Microsoft software update signing certificate using an independently developed MD5 collision attack[7] to sabotage Iran's nuclear program.  But as far as anyone can tell, MD5's target collision resistance still holds up to this day, so RSA-PSS would have thwarted this entire avenue for certificate forgery even with MD5.

Why IEEE P1363-2000 and RSA PKCS #1 v2.1 standardized $H(r \mathbin\| H(m))$ instead of $H(r \mathbin\| m)$ is a mystery to me.  Coincidentally, this standardization happened around the same time that RSA, Inc., accepted a 10e6 USD bribe from the NSA to deploy Dual_EC_DRBG to all their RSA-BSAFE customers[8].

Modern signature schemes like Ed25519 use the design principle $H(r \mathbin\| m)$ in order to rely only on the weaker property target collision resistance like PSS or at least enhanced target collision resistance[9], and as such are advertised to have collision resilience.  (More on the history of these and related concepts in a previous answer.)


Proving/verifying keys for zero knowledge proof (zkSNARK) in a simple case (possession of a string whose hash is x)

This section from the paper Succinct Non-Interactive Zero Knowledge
for a von Neumann Architecture is what you want. See the following image.

I will describe the very high-level idea below.
ZKSNARK that libsnark and ZCash use is based on the Knowledge of Exponent assumption. Basically, the exponent used in the elliptic curve cryptography is just the "toxic waste" that you mentioned. Denote $G$ as the group generator of the curve used, $G*t, G*t^2, \ldots$ ($t$ is part of the so-called private coin and this series will continue until the evaluation of some polynomial like $H(t))$ is covered. You may wonder what $H(t)$ is. A brief answer is that we have transformed the NP statement (the preimage of SHA256 is a witness to the NP statement due to the property of the one-way function) to the arithmetic circuit consisting of additive and multiplicative gates (just assume no boolean comparison here), then to the polynomial $A(t)*B(t)-C(t)=H(t)*Z(t)$. This polynomial equation holds ($H(t)$ exists particularly) $iff$ the proving procedures are correctly executed. Put it more simply, if the circuit contains $N$ gates (constraints), then we need a polynomial representation of order $N$. Again why this weird equation? Assume the underlying computation takes $T$ steps, this gives us lower bound $T\log(T)$ on proving time thanks to the deep connection between polynomials and the $\text{Fast Fourier Transformation (FFT)}$. Before this method, the proving time is at least $T^2$ (inner product and outer product are used, thus the square). On the other hand, we can further reduce the polynomial equation to the $\text{ECC}$ bilinear pairing problem. We need this one last transformation because it allows the verification steps to be very efficient. The proof is constantly 128 bytes (3 pairings) and the verification is always around 3-5 ms. So now we can also answer where this "trusted setup" concept comes from. It is import no one has a trapdoor to the setup procedures, i.e., no one has access to the "toxic waste". Typically, multi-party computation is applied so that if at least one party is honest, the setup is a trusted one. Another thing you mentioned is $pk$ and $vk$. As you can see, $pk$ is a proving template that uses homomorphic encryption for the verifier to check the knowledge commitments of polynomials $A(x)$, $B(x)$ and $C(x)$ and whether they use the same coefficients. And $vk$ is just used in the pairing.

If you want to know more details, a great start would be the explanation by Vitalik Buterin. It is not hard to understand this one. Here is another somehow more formal explanation by Christian Reitwießner. Also, for more academic teaching resources, this lecture series covers the general topic of verifiable computation, interactive arguments system, ZKSNARK with pre-preprocessing, ZK system front-end transformation and much more.


Yes, that's a correct assumption: sometime statistical properties of the plaintext (like, compressibility using standard algorithms, which can be quickly approximated, then refined) are used to check that a correct key was found during brute-force search, when there is no better way, like known plaintext.

By the second Kerckhoffs's principle, if a decoy method is used, that fact is part of the algorithm, and public (the value of the decoy can be an input, considered part of the key, and either secret or public). However modern cryptographic algorithms are designed to resit any amount of known plaintext (and even chosen plaintext), and therefore do not need such decoy method in order to achieve confidentiality; which is why I doubt you'll find (recent) peer-reviewed articles about decoy in order to improve confidentiality, only as a mean to implement plausible deniability, as in TrueCrypt. In this application, decoy is used, but not for improved resistance to exhaustive key search.

Update: Sometime the key is really a passphrase stretched to a key using some password-based key derivation function. When you count brute-force search of such passphrase as key search, which is quite legitimate, a decoy (deciphering to plausible decoy plaintext with a weak decoy passphrase) is an interesting idea. One issue is that, as stated above, the adversary is assumed to know there is potentially a decoy; anyway it seems hard to hide the fact that an encryption system allows the use of decoy passphrases(s) and plaintext(s), when that system is analysed by the adversary to the point necessary to mount an efficient passphrase search. Therefore, the adversary performing passphrase search has the option to continue searching after finding decoy(s), and I do not see that the overall resistance to a given effort of passphrase search is much improved. Towards that goal, it is probably better to use a good key derivation function, using the principles pioneered by scrypt; also, that avoids the ciphertext expansion unavoidably caused by the use of decoy.


Implementing Inferno's ECIES: Creating a symmetric key from sender's public key

You are not leaking anything, because ephemeralBundle will contain a new, unique public-private ephemeral key pair, and the encryption will occur with brand-new [ephemeral_public  sender_private == ephemeral_private  sender_public] secret key.

Using sender's pk as a receiver (ie. sending to yourself) is safe in your scenario above.


$\mathbb Z_n^*$ is a mathematical notation for the multiplicative group of integers modulo $n$.  In other words, it is the set of integers that are relatively prime to $n$, all taken modulo $n$ (excluding zero). The $*$ symbol is commonly used for denoting "the set of elements in the multiplicative group", which in this case means "the set of elements that are relatively prime to $n$".

Normally $\mathbb Z_n^*$ is treated as a multiplicative group, so it comes coupled with the multiplication operation modulo $n$.  (In contrast $\mathbb Z_n$ would denote the group of integers modulo $n$ under addition, or the field over the same set with both addition and multiplication.)

When such algebraic structures are raised to the power of two, it is an abbreviation for the Cartesian product of the underlying set with itself, in this case $\mathbb Z_n^* \times\mathbb Z_n^*$, i.e. the set of value pairs $(x,y)$ where both $x,y$ are integers in the range $1$ to $n-1$ and relatively prime to $n$.

Cartesian products of sets are also sets and might be coupled with one or more binary operations to form algebraic structures, such as fields and groups. In this case, the operations would be determined by context.

Edit: It should be noted that in mathematics, the $*$ symbol is more generally used for denoting a set excluding element zero. For instance, $\mathbb Z^*$ means the set of integers except $0$. However, it doesn't make sense to extrapolate this notation to finite sets such as $\mathbb Z_n^*$, except when $n$ is prime. If $n$ is composite, the set of integers $1$ to $n-1$ is not closed under multiplication, but the set of integers relatively prime to $n$ is. Hence, it is usually safe to presume $\mathbb Z_n^*$ denotes the (underlying set of the) multiplicative subgroup, unless explicitly stated otherwise.


Are libhydrogen's Gimli permutations production ready?

If you consider a feature being enabled by default as meaning the feature is production ready, then yes Gimli is production ready. However, it's still fairly new and hydrogen allows you to switch a compile time flag to use NORX/Keccak-p at the cost of being slightly slow.


How do we know one-way functions can be iterated?

We cannot - we might need another function to adjust the value to be acceptable. Assuming however that $h$ is a hash - this is the crypto site - then it should accept any size of input in bits; up to a seriously high limit anyway.


Is a transposition cipher categorized as asymmetric algorithm?

No, it is not an asymmetrical algorithm, becayse the decryption key can be derived from the encrytion key.

Even in a symmetrical algorithm the encryption and decryption algorithms may be different, and the decryption algorithm might include firct calculating a decryption key from the encryption key. However, the same key can be used for both encryption and decryption in the sense that if you know that key you are able to both encrypt and decrypt messages.

In an asymmetrical algorithm, someone who only knows the public key can not decrypt messages. That is not the case for a transposition cipher.


Significance of y-coordinates in ECDH public key exchange

The paper you reference mentions that although both coordinates are sent, the protocol only requires the x-coordinate to be authenticated and validated. This means that the y-coordinate is free to be manipulated in implementations that do the bare minimum. As mentioned in a comment, "poor programmers and bad quality testers will not consider [this vulnerability]".
Sending only one coordinate makes it less likely for an implementer to make a mistake. With only one coordinate, it's impossible for the second coordinate to be manipulated, and it's significantly harder to force someone to use a point not on the curve. It's easier to test that given a value, a function always generates a valid point or throws an error than it is to test that a protocol works correctly end-to-end for all possible inputs.


Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols

As a concert example lets consider the protocol for knowledge of discrete-logarithm.
The aim of the protocol: P wants to prove that it knows $x$ for $pk=g^x$.

commitment: P chooses a random $r$ and commit to it by sending $R=g^r$ to the verifier.

challenge: the verifier chooses a random value $c$ and sends it to P.

P sends $z=r+cx$ to the verifer.

verification: the verifier checks if $g^z=R.pk^c$ if yes it accepts it.

Now what will happen if the prover does not commit to $R$ before sending $z$ ?
After receiving $c$ from the verifier, P chooses a random $z$ and finds $R'$ from the equation $g^z=R'pk^c$, i.e., it sets $R'=g^zpk ^{-c}$.  Then it sends $R',z$ to the verifier.
By this $R'$ it can pass the verification check, and the point is that it even does not use $x$ in $z$. This means a malicious prover who does not have $x$ can prove the knowledge of $x$!
Putting together, commitment is necessary to protect the proof system against prover such that just the honest provers can convince the verifier.


Retrieving ElGamal message with negative exponent value

In order to retrieve the message $M$ from the Discrete Log provided by the final step of ElGamal, knowing that $-l \le M \le l \text{ where } |\ l\ | \lt \lfloor p/2\rfloor$ works the same way as if $1 \le M \le p - 1$ that is, testing for all exponents.
For negative values of $l$ we use modular division, e.g. $$5^{-3} \equiv 125^{-1} \equiv 6^{-1} \equiv 6\bmod7$$ and we find the inverse with Ext-GCD algorithm

It is important to note that $|\ l\ | \lt p/2$ where $p/2$ is rounded down e.g. for $l=5$ then $p \ge 13$. The reason for this is that the number of encoded values for $-l \le M \le l$ is $2\ l + 1$ due to the existence of the value $0$ and the defined cyclic group must have order greater than that.


Is there any benefit of changing the AES-CCM encryption key periodically even if the Nonce space is not exhausted yet?

CCM mode uses CTR mode the encryption and CBC-MAC for the authentication. For a security proof you can refer to On the Security of CTR + CBC-MAC.

With CTR the fact that AES is a PRP rather than PRF starts to show after $2^{64}$ blocks have been encrypted. In practice this does not lead to a very effective attack even then.

After a similar number of blocks encrypted, collisions could allow MAC forgeries for new messages. This is a much more serious attack, though it of course requires an active adversary to take advantage of it. To keep the probability of collisions low it is sometimes recommended to use similar authentication modes (e.g. CMAC) for only $2^{48}$ blocks.

Note that the above limit is not dependent on the nonce size, which for CCM is usually e.g. 12 bytes, but the block size of the cipher which for AES is 128 bits (16 bytes). (With random nonces a nonce collision would be likely earlier than the above.)

In practice, you can rest easy while using the same key for gigabytes or even terabytes of data. Only if your get into petabyte range does key lifetime become a concern. However, the above attacks are probabilistic and if you can frequently agree on a new key, you get lower probabilities.


Securing communication between limited embedded systems

A rule in cryptographic protocols is to never implement them on your own. Unfortunately I did not find anything that matches this use case.

Have you considered DTLS?  That tries to address the same problem (except for time stamps; that could be added by inserting the time stamp in the datagram), and already has things thought through.  Another possibility would be IPsec; however DTLS looks closer to addressing the problem you have (unless the data traffic you're protecting is IP traffic).
That said, here are some thoughts on the protocol you outlined:

What happens if two sequential messages are dropped (e.g. received incorrectly)?  Will the two sides realize what happened, or will they proceed to drop all subsequent messages (because of the 'nonce has to increment no more than 2' rule)?

Presuming they attempt a rekey, how is this coordinated?  If one side thinks they haven't rekeyed yet, and the other side thinks they are, what will happen to messages encrypted with the old key?  We find it generally useful to include a 'which key this is encrypted under' tag with the ciphertext (in DTLS, this is the 'epoch').

Can your communication channel reorder messages?  I suspect it can't in your case, but if it can, you should think about how that should be handled.

What happens if someone injects a previous (valid) handshake message?  How will that confuse things?

In the data encryption path, you use CBC encryption and CMAC integrity.  While this is a workable solution, this is prone to various padding attacks if they aren't integrated correctly.  Current fashion is to use an AEAD mode (such as GCM or Chacha20/Poly1305) which does both.

Is the encrypted traffic unidirectional or bidirectional?  If traffic goes both ways, do you use the same set of keys to protect both sets of traffic?

"If anything is not as expected, Handshake is sent again, then message is sent again with newly exchanged parameters." - how does that work?  If the receiver decided it didn't like the message, how does the sender know to resend it?