Doubt about published test vectors for gimli hash

I'm one of the authors of Gimli.

TL;DR: Test vectors provided by the paper are indeed wrong.

We had a error when we generated the paper and the test vectors have not been updated with respect to the last iteration of Gimli (in development stages).

Also one of the test vectors had a double space at some place. This has been corrected and will be updated in the revision of the paper.

Please find the correct ones below:

Test vectors

input 1:

  There's plenty for the both of us, may the best Dwarf win.

54686572 65277320 706c656e 74792066 6f722074 68652062 6f746820
6f662075 732c206d 61792074 68652062 65737420 44776172 66207769
6e2e

output 1:

4afb3ff784c7ad6943d49cf5da79facfa7c4434e1ce44f5dd4b28f91a84d22c8

input 2:

  If anyone was to ask for my opinion, which I note they're not, I'd say we were taking the long way around.

49662061 6e796f6e 65207761 7320746f 2061736b 20666f72 206d7920
6f70696e 696f6e2c 20776869 63682049 206e6f74 65207468 65792772
65206e6f 742c2049 27642073 61792077 65207765 72652074 616b696e
67207468 65206c6f 6e672077 61792061 726f756e 642e

output 2:

ba82a16a7b224c15bed8e8bdc88903a4006bc7beda78297d96029203ef08e07c

input 3:

  Speak words we can all understand!

53706561 6b20776f 72647320 77652063 616e2061 6c6c2075 6e646572
7374616e 6421

output 3:

8dd4d132059b72f8e8493f9afb86c6d86263e7439fc64cbb361fcbccf8b01267

input 4:

  It's true you don't see many Dwarf-women. And in fact, they are so alike in voice and appearance, that they are often mistaken for Dwarf-men. And this in turn has given rise to the belief that there are no Dwarf-women, and that Dwarves just spring out of holes in the ground! Which is, of course, ridiculous.

49742773 20747275 6520796f 7520646f 6e277420 73656520 6d616e79
20447761 72662d77 6f6d656e 2e20416e 6420696e 20666163 742c2074
68657920 61726520 736f2061 6c696b65 20696e20 766f6963 6520616e
64206170 70656172 616e6365 2c207468 61742074 68657920 61726520
6f667465 6e206d69 7374616b 656e2066 6f722044 77617266 2d6d656e
2e20416e 64207468 69732069 6e207475 726e2068 61732067 6976656e
20726973 6520746f 20746865 2062656c 69656620 74686174 20746865
72652061 7265206e 6f204477 6172662d 776f6d65 6e2c2061 6e642074
68617420 44776172 76657320 6a757374 20737072 696e6720 6f757420
6f662068 6f6c6573 20696e20 74686520 67726f75 6e642120 57686963
68206973 2c206f66 20636f75 7273652c 20726964 6963756c 6f75732e

output 4:

8887a5367d961d6734ee1a0d4aee09caca7fd6b606096ff69d8ce7b9a496cd2f

input 5:

 no bytes

ouput 5:

b0634b2c0b082aedc5c0a2fe4ee3adcfc989ec05de6f00addb04b3aaac271f67


Is this modified Schnorr signature scheme secure?

This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message.

To do this, the forger would take the message $M$, the public key $y$, pick an arbitrary $z$, and compute $r = y^{-H(M)} g^{z} \bmod p$ and output $(r,z)$


Given A, B, G, H prove the I know x s.t. $A=xG$ and $B=xH$

There is a standard $\Sigma$-protocol for proving knowledge of a witness showing that $(G,H,A,B)$ is a DDH-tuple, assuming a group of prime order $p$:

The prover picks a random exponent $r \in \mathbb{Z}_p$ and sends $(R,S) = (rG, rH)$.
The verifier sends a random challenge $e$ from $\mathbb{Z}_p$.
The prover computes and send $d = e\cdot x + r$.
The verifier accepts the proof if and only if $eA+R = dG$ and $eB+S=dH$.

Since you seem to ask these questions for the purpose of learning, I'd suggest that you try to prove yourself the security of this protocol (that is, soundness, and honest-verifier zero-knowledge). You can take inspiration from the security analysis I gave for a similar protocol in this answer, that deals with the Schnorr protocol (about which you asked in another question).


How is it possible for a VPN connection to be created through the ISP?

So how is it possible for you and VPN provider to communicate a key
  without ISP knowing [that you are communicating]?

You can't. The ISP will always see that there is some traffic going on. Whether the ISP will be able to see with whom you are (actually) talking depends on whether you use things like TOR and on the details of the target network, but in general the packet metadata will tell the ISP where to send the packet and thus with whom you are talking.

  So how is it possible for you and VPN provider to communicate a key
  without ISP knowing [the key used to encrypt the data]?

This is due to the "magic" of asymmetric cryptography. In short, this allows you to reduce the requirement from a trusted, secret channel (to transport a symmetric key) down to an authentic channel, ie a channel where nobody gets to alter, drop or insert malicious messages***. And as you may have guessed, in current TLS versions (1.2 and earlier**), if you use a so-called "ciphersuite" without DH, DHE, ECDHE or ECDH in the name, you are essentially encrypting a secret with the server's public key, sending it and then you both go from there and derive a key* for the session.

*: To get some neat extra security properties.
**: TLS 1.3 has explicitely removed this type of ciphersuite because of something called forward secrecy.
***: So-called certificates are then used to reduce this requirement even further from "always need authentic channel" to "sometimes need authentic channel + need to trust a third party"


When looking at it it looked quite similar to mondern cryptographíc algorithms relying on a secret key and do some "magic" on the plain text to get the ciphertext.
So, on first thought I'd say that these codes follow the rule that it solely relies on the secrecy of a key (in the example on the page you linked it's SCHULPFORTA DEGEN) and not the secrecy of the algorithm (which is the contrary of "security by obscurity").
I can't give analysises about the strongness of an algorithm by myself but because David Kahn's "Codebreakers" is mentioned and I have this book sitting in my shelf next to my computer, I can cite from there:

Such an encipherment virtually obliterates ciphertext repetitions. Even if an exact 18-letter plaintext group recurs, it must begin at exactly the same point in the encipherment equation to produce a ciphertext repetition - and there is only one chance in 18 of this happening. More importantly, a polygraphic encipherment of this magnitude is possible only with a Hill transformation. The more than 40 quintillion 18-letter groups, printed 100 to each side of a page with their ciphertext equivalents, would fill a codebook thicker than the distance from the sun to Pluto.
[...]
The cryptology of today is saturated with mathematical operations, mathematical methods, mathematical thinking. In practice, it has become virtually a branch of applied mathematics. Its sophistication, its range, and its power have grown far beyond the imaginings of the most imaginative cryptologist in Yardley's Black Chamber. And in this evolution, Lester Hill was a prime mover.

BTW: By "today" Kahn is speaking about the 60s/70s, the book was publshed 1967.
Edit: As promised I had a look at C1 and C2.
At first glance at C1 I thoght the same but there is a bit more to it than "security by obscurity". C1 uses a key and one of five filling methods. The key not only sets up the substitution table but is also used to specify the order in which to write down the blocks of cipher elements after filling the key-table.
So an attacker who wants to do statistical analysis to break the key needs to guess the used filling method, the length of the key and the order of letters in which they appear in the key. A brute force attack today might not take that long with todays computing power but for the 50s that's another story.
C2 on the other hand doesn't look robust even after second glance. There are only four substution tables (all of which leaves a cipher that is vulnerable to statistic attacks) and a fixed filling method, so by knowing about this algorithm, breaking a cipher shouldn't be hard.
But even C2 might have it's use because in the Cold War (and any other time that is ;-) you sometime want your enemy to "break" a code in order to feed false information. The information in a deciphered message looks more authentic than a plain message you find on a postcard.
Also, it might also be suitable for messages where the value of the information decreases very fast. E.g. if I use C2 as cipher to send a buying order to my broker and it keeps other trading parties from reading that information until the order is fulfilled (and the information can then be found in the order book anyway) this cipher (which can be calculated manually quite fast) might still be suitable.


Verifying the integrity of ciphertext using the cleartext hash?

There really isn't such a function $f$; encryption algorithms attempt to generate what looks like random bitstrings (at least, it looks that way to anyone who doesn't know the key), and because the plaintexts and the ciphertexts look unrelated, their hashes are also going to look unrelated.

On the other hand, what is the problem you're trying to solve?  When you say 'verify the integrity of a ciphertext', who is doing the verification?

Are you trying to allow the decryptor to verify that the message he got was the message that the encryptor sent without someone modifying it in the middle?  If that's the case, the standard way of addressing it is with a Message Authentication Code
Are you attempting to allow the encryptor to verify that the encryption process proceeded properly?  About the only ways to do that are to either run the encryption process again (with the same IV) and compare, or attempt to decrypt the ciphertext and compare.
Are you trying to allow someone in the middle (without the keys) to verify that a specific ciphertext happens to be a specific plaintext?  Well, that would be an unusual requirement; I don't have any bright ideas on that one.


Is the role of public key/private key determined arbitrarily or mathematically?

The web article states

  ..a key generation program (produces) two keys. It is arbitrary which of these is made public and which is kept private.

This second sentence is wrong, especially since it appears in a general discussion about "Asymmetrical-key algorithms" (sic: the closer usual adjective in the cryptographic literature is asymmetric, and the concept is better known as public-key).

In most common forms of public-key cryptography, the public and private keys are very different beasts, and we can't exchange them. Examples:

Public-key cryptography based on the Discrete Logarithm Problem (DSA, ECDSA, EdDSA, Schnorr signature, ElGamal encryption, ECIES..), where there is a direct method to find the public key from the private key: $\text{Pub}=g^\text{Priv}$ (or $\text{Pub}=\text{Priv}\times G$ depending on notation), when that's not possible in the other direction (security relies on that).
Hash-based public key cryptography, for a similar reason.
RSA encryption and signature as practiced, where the public key is $(N,e)$ and the private key is $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ (see RSAPrivateKey in PKCS#1 v2.2). And even if we reduce the later to $(N,d)$ so that the two keys become substitutable, doing such substitution would ordinarily ruin security, because ordinarily $e$ is small, thus guessable. Better methods allow to recover $e$ from $(N,d)$ for size of $e$ up to $29.2\%$ the size of $N$ (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999), which covers all values of $e<2^{256}$, often considered as a practical upper limit.

In fact, I can only see that the quoted statement applies to a particular cryptosystem: a form of RSA where $e$ in the public key $(N,e)$ is random and large, and the private key is stored as $(N,d)$. That is barely used because it makes the use of either key several times more costly than in regular RSA with small $e$ (in the hundreds for the public key, like 3 to 4 times for the private key), and almost double the storage requirement of the public key.

  Are private keys called 'private' only because you keep them private, or (do) they have some mathematical merits that fundamentally differentiate them from their public counterpart?

The later!

  Is public key always for encryption, and private (for) decryption?

No, because there are other uses of public/private keys than encryption and decryption.

When doing encryption and decryption, the public key is always the one used for for encryption, and the private key is always the one used for encryption.

When signing (or demonstrating one's identity), the private key is always the one used. When verifying a signature (or someone's identity), the public key is always the one used.

In the context of an RSA cryptosystem, the expression "encrypt with private key" is sometime used where there should be "sign" or "apply the private-key transformation $x\to x^d\bmod N$". Same for "decipher with public key" where there should be "verify" or "apply the public-key transformation $x\to x^e\bmod N$". The web article does that without emphasis on the impropriety, and worse for an unspecified asymmetric cryptosystem. That's a sign of lack of rigor in the material, and sadly is very common. It seems some authors believe that all signatures are based on a trapdoor permutation, like RSA signatures are. I've recently seen that in a standard for train tickets under review, where a drawing explains that the prescribed DSA signature verification compares the hash of the message to be authenticated against the result of decryption with the public key (which is plain wrong). That same misconception is there (which mentions DSA two paragraphs after the drawing).


How can I calculate the entropy of an image?

You don't need the probability distribution of images to calculate the information entropy of an image.  That isn't how the entropy calculation works.  For example, we can certainly calculate the entropy value of a symbol - say [@] - it would have an entropy value of 0, if we add multiple symbols...[@#], then the entropy value of two distinct bits of information would be 1.0, if we add even more [@#$] then the entropy value of the three distinct bits would be 1.58 - interestingly, if you add in redundant characters to your string, then you will reduce its entropy value, because you are not adding anything new to the string that we did not already know.

Consequently we can apply the same principle to image analyses, we do it all the time.  You would just vectorize the pixel data, read the flattened vector data into a dataframe, then do the entropy calc on the dataframe.  In my case, I just use scipy library from Python (scipy.stats.entropy).  We have analyzed many images using the technique, on average an image has an entropy somewhere between 3 and 4.  You can test this concept, by calculating the entropy of a pure white image (it should approximate zero, or be equal to zero), versus a more complicated image with graphs, people, chairs, cars, etc...(should be upwards of 4)

A fun way to cross check the validity of this, is to compare the entropy value of an "image of a string" to the entropy value "of the string bits" themselves - they won't be exactly the same (the image of a string is slightly higher (especially in languages that have multiple separated symbols within a single character bit [i.e., farsi, kanji, etc...]) - but in English they are pretty close.


GPG and PAR2 error correction data from the plain archive, will it compromise security?

You could GPG-encrypt both the .7z archive and the PAR2 error-correction data.  That will take care of the security issues.

Alternatively, you could compute the PAR2 error-correction data on the results of the GPG encryption, for the reasons Ricky Demer explains.  That would be secure too.

Either one works.


In typical ECC-based cryposystems, the one-way function is based on the Discrete Logarithm problem as in classical Diffie-Hellman key exchange; only working in a different finite group, built with the help of some Elliptic Curve over a finite field, rather than in the group obtained directly by multiplication modulo a prime.

In classical Diffie-Hellman key exchange with parameters a large prime $p$ and generator some integer $g$, the private key is some integer $x$, and the public key is $y=g^x\bmod p$. This is equivalent to multiplying $g$ by itself $x$ times in the multiplicative group $\mathbb Z_p^*$; though actually, this is done with $\mathcal O(\log(x))$ such modular multiplications, using e.g. exponentiation according to the binary representation of $x$.

In ECC, we just use a different group, and typically note the group law $+$ and the generator $G$ (uppercase is used for members of the group, while lowercase denotes integers). The private key is some integer $x$, and the public key is $Y=x\times G$. This is equivalent to adding the generator $G$ to itself $x$ times per the group law; though actually, this is done using $\mathcal O(\log(x))$ such additions in the group, using techniques as above.

In both cases, obtaining $y$ or $Y$ from $x$ is easy, but obtaining $x$ from $y$ or $Y$ is believed intractable (for proper choice of group and generator, and $x$ random in $[0,n)$ where $n$ is the order of the generator).

Elliptic Curve Diffie-Hellman works essentially identically as its classical counterpart in $\mathbb Z_p^*$, except that the Elliptic Curve group allows shorter public key and more efficient calculation for the same security level. The same transposition from $\mathbb Z_p^*$ to Elliptic Curve group works for ElGamal encryption (which becomes the basis of ECIES) and various signature algorithms including Schnorr and DSA (becoming EC-Schnorr and ECDSA).


Recovering private key from Secp256k1 signatures

In ECDSA, each signature has its own ephemeral key $k$. If $k$ is generated properly, then no amount of signatures will help you recover the private key. "Proper" generation here means either random uniform selection in the proper range, or an appropriate derandomization process such as the one described in RFC 6979.

If the very same $k$ value is used in two signatures, on two distinct messages, but with the same private key $x$, then the private key is revealed. This is the deadly mistake of Sony back in early 2011 (and the initial motivation for RFC 6979, btw). Indeed, if the two messages are $m_1$ and $m_2$, and both values use the same $k$ values, then the two signatures are $(r,s_1)$ and $(r,s_2)$:
\begin{eqnarray}
  s_1 &=& (h(m_1) + xr) / k \\
  s_2 &=& (h(m_2) + xr) / k \\
\end{eqnarray}
The ephemeral key $k$, and the private key $x$, can then be computed as:
\begin{eqnarray}
  k &=& \frac{h(m_1) - h(m_2)}{s_1 - s_2} \\
  x &=& \frac{ks_1 - h(m_1)}{r} \\
\end{eqnarray}

If the values of $k$ are not reused, but are generated with some bias (i.e. not all values in the $[1,q-1]$ range are selected with the same probability), then the private key $x$ can still be recovered from a set of signatures. If for instance $q$ has size 256 bits, but values of $k$ are always lower than $2^{253}$ (i.e. the top three bits are always zero), then a few hundreds of signatures suffice.

If the values of $k$ are generated with a strong, cryptographically secure source, and with no bias, then there is no known attack against ECDSA that would recover the private key $x$, even if many signatures are known. The first reuse of $k$ out of pure back luck is expected to happen after an average of $2^{n/2}$ signatures for an $n$-bit curve, i.e. never in practice if you use a decent curve.

Also, in Bitcoin, people tend not to sign a lot with any given key. For privacy reason, address reuse is discouraged.


You have two algorithms, $A$ and $B$, that claim to compute two (essentially) injective, hard-to-invert and costly-to-compute functions $F$ and $G$. Your fear is that either of the algorithms instead compute functions $F'$ and $G'$, that may be neither injective, hard-to-invert, nor costly-to-compute. This may happen because of programming mistakes or (these days) deliberate sabotage.

What you want is some way to combine $A$ and $B$ such that the corresponding combination of $F$ and $G$, $F'$ and $G$, and $F$ and $G'$ is (essentially) injective, hard-to-invert and costly-to-compute. (If both are defective, then it will obviously not be possible to do anything.)

Observe that $F(G(\cdot))$ and $G(F(\cdot))$ are bad constructions (they fail injective).

The construction $(F(\cdot),G(\cdot))$ does not fail injective and costly-to-compute, but may fail hard-to-invert.

If we assume that $F$ and $G$, $F'$ and $G$, and $F$ and $G'$ are in some sense independent (that is, say, $F'$ is not $G$), then $$F(\cdot) \oplus G(\cdot)$$ should be ok.

Why don't we do this? To a certain extent, you can verify the implementations by comparing with test vectors and other known-to-be-good implementations.


Is the KDF pbkdf2 included in the openssl suite?

LibreSSL enc docs: https://man.openbsd.org/openssl.1#ENC

OpenSSL enc docs for version 1.1.1 : https://www.openssl.org/docs/man1.1.1/man1/enc.html

Both support pbkdf2. I am kinda surprised LibreSSL still supports DES, I would not support it. Can you paste the exact error you're getting?

Edit:

The changelog of libressl says pbkdf2 support was added in version 2.9.1 (latest current version).

Comparing the openssl 1.1.1 man page above with the openssl 1.1.0 enc man page, I see pbkdf2 support was added in version 1.1.1 (latest current stable version).

You're trying to use a very new feature.


Inversion in $GF(2^{10})$ Using Composite Fields

Do you know how to invert complex numbers? If yes, then you also know the answer to your question:

$$z^{-1} = \frac{\bar{z}}{z\cdot\bar{z}},$$

where $\bar{z}$ is the complex conjugate of $z$ (if $z=x+y\cdot i$ with $x, y\in\mathbb{R}$, then $\bar{z}=x-y\cdot i$) and $z\cdot\bar{z}=x^2+y^2\in\mathbb{R}$.

Complex conjugation is a field automorphism of order $2$, i.e., composed with itself it is the identity ($\bar{\bar{z}}=z$). For the field $\mathbb{F}_{2^{10}}$ squaring is a field automorphism (called Frobenius automorphism) of order $10$, as $z^{2^{10}} = z$ for $z\in\mathbb{F}_{2^{10}}$. So if you take the field automorphism $\sigma$ of $\mathbb{F}_{2^{10}}$ defined by $\sigma(z) = z^{32}$ (the 5th power of the Frobenius automorphism) you get an automorphism of order $2$ like for the complex numbers. The role of the real numbers (which are fixed under complex conjugation) is played by the field $\mathbb{F}_{32}$ (whose elements are fixed under $\sigma$).

If you know an irreducible polynomial $f$ of degree $5$ over $\mathbb{F}_2$, you can use it to define the field $\mathbb{F}_{32}$ as $\mathbb{F}_2[X]/(f(X))$. To get $\mathbb{F}_{2^{10}}$ as extension field of degree $2$ over $\mathbb{F}_{32}$ you can take the irreducible polynomial $g(T) = T^2+T+1$ over $\mathbb{F}_2$, which stays irreducible over $\mathbb{F}_{32}$ as $2$ does not divide $5$ ($\mathbb{F}_{32}$ doesn't have subfield of order $4$, as its order $32$ prevents it to be a vector space over $\mathbb{F}_4$): $\mathbb{F}_{2^{10}} = \mathbb{F}_{32}[T]/(g[T])$.

Any element $z\in\mathbb{F}_{2^{10}}$ you can write as $z = x+y\cdot T$, where for $T^2 = 1+T$ holds for $T\in\mathbb{F}_{2^{10}}$ (as $T$ is root of $g$). Now

$$z^{-1} = \frac{\sigma(z)}{z\cdot\sigma(z)} = \frac{\sigma(x+y\cdot T)}{(x+y\cdot T)\cdot\sigma(x+y\cdot T)} = \frac{x+y\cdot \sigma(T)}{(x+y\cdot T)\cdot(x+y\cdot\sigma(T)},$$
using that $x,y\in\mathbb{F}$ are fixed by $\sigma$. As $T^4 = (T^2)^2 = (T+1)^2 = T^2 + 1 = T + 1 + 1 = T$ ($T$ is in the subfield of order $4$ of $\mathbb{F}_{2^{10}}$) we get $\sigma(T) = ((T^4)^4)^2 = T^2 = T+1$ and therefore

$$z^{-1} = \frac{x+y\cdot(T+1)}{(x+y\cdot T)\cdot(x+y\cdot(T+1))} = \frac{x+y\cdot(T+1)}{x^2 + x\cdot y\cdot (T+1) + y\cdot T\cdot x + y\cdot T\cdot y\cdot(T+1)} =
\frac{x+y\cdot(T+1)}{x^2 + x\cdot y + y^2},$$
using $T^2 + T = 1$.

The denominator is an element of $\mathbb{F}_{32}$, it's non-zero (do you know why?), so you can invert elements of $\mathbb{F}_{2^{10}}$ if you know how to invert elements of $\mathbb{F}_{32}$.


RSA is good for short messages, so think about applications involving short messages. e.g.

Key encryption. i.e. use RSA to encrypt an AES key for transport
Credit card data. i.e. encrypting a credit card number for transmission


How to calculate the redundancy of a language

Not really, for example if your language has $m$ letters, and the letters are independent identically distributed then $H(X)=H(X_1,\ldots,X_N)=N H(X_1)$ where $H(X_1)$ is is the entropy of the single letter distribution $(p(1),\ldots,p(m)),$ where $P[X_k=u]=P[X_1=u]=p(u)$ for any $k\geq 1.$

This is because for independent random variables
$$
H(X_1,\ldots,X_n)=
$$
$$
=H(X_1)+H(X_2|X_1)+H(X_3|X_1 X_2)+\cdots+H(X_N|X_1X_2\cdots X_{N-1})=
$$
$$
=H(X_1)+H(X_2)+\cdots+H(X_N).
$$

So $X$ in that statement refers to the sequence of $N$ characters.

If your language is first order markov then
$$
H(X_1,\ldots,X_n)=
$$
$$
=H(X_1)+H(X_2|X_1)+H(X_3|X_1 X_2)+\cdots+H(X_N|X_1X_2\cdots X_{N-1})=
$$
$$
=H(X_1)+H(X_2|X_1)+H(X_3|X_2)+\cdots+H(X_N|X_{N-1})\geq (N-1)H(M).
$$
where $H(M)$ is the entropy of the Markov chain, i.e.,
$$
H(M)=\sum_{s\in S} \mu_s H(X_{n+1}|X_n=s)
$$
where $\mu_s$ is the steady state probability of being in the state $s$. Of course we need to assume a stationary Markov chain here.

See Shannon's classical paper Prediction and Entropy of Printed English (here )for a number of ways of calculating the entropy.


Why hash function are used in digital signatures?

Bruce Schneier writes in Applied Cryptography (2nd ed., p. 38f):

  In practical implementations, public-key algorithms are often too inefficient to sign long documents. To save time, digital signature protocols are often implemented with one-way hash functions (...). Instead of signing a document, Alice signs the hash of the document.

The references Schneier cites are:

D. W. Davies and W. L. Price, "The Application of Digital Signatures Based on Public-Key Cryptosystems," Proc. of the Fifth International Computer Communications Conference, Oct 1980, pp. 525--530.
D. W. Davies and W. L. Price, "The Application of Digital Signatures Based on Public-Key Cryptosystems," National Physical Laboratory Report DNACS 39/80, Dec 1980.


Is a digital signature of use if you don't also encrypt the message containing it?

So lets say Bob sends Alice an unencrypted message, and Charlie overhears it. What's to stop Charlie from signing his own messages with that private key and henceforth having the ability to impersonate Bob?

Alice already possesses Bob's public key $\text{pub}_{B}$, and Bob is the only one that has access to the corresponding private key, $\text{priv}_{B}$.

The private key is not shared with anyone, while the public key can be published.

Bob can use $\text{priv}_{B}$ to perform the sign procedure which creates a signature $s$ from a message $m$.

Then Alice acquires $s, m$ and can use them with $\text{pub}_{B}$ to perform the verify procedure, which only outputs $1$ if $s$ was created using $m, \text{priv}_{B}$.

Charlie does not have $\text{priv}_{Bob}$, and so he cannot create a value $s$ for any $m$ that will pass the verify procedure that Alice will perform. (At least, he cannot do so with non-negligible probability, assuming that the signature scheme is secure).

  So is there a point to digitally signing some message that isn't also encrypted?

Yes

  Or are all communications using digital signatures also encrypted?

No

  Wikipedia made it seem like there were two independent ideas

They are two independent ideas.

Digital signatures provide authenticity and integrity of the signed message - if the signature verifies correctly, then you know that the message came from Bob and was not tampered with.

Encryption provides confidentiality, which means that unauthorized parties cannot learn the contents of the message.

  but I can't see a use case for signing-without-encrypting, where I can for encrypting-without-signing and encrypting-and-signing.

There are plenty of use cases for signatures without encryption.

Exchanging public keys for public-key encryption or key agreement is one of the most important examples (e.g. Public key Infrastructure).


Does there exist equivalent hash function?

If a hash function can be described using boolean algebra, you can transform it into an equivalent function using distributivity, commutativity, associativity, De Morgan laws, absorption, etc... Two functions will be equivalent if you can find a serie of transformations that will lead to one another while preserving the equivalence.

See:
https://en.wikipedia.org/wiki/Logical_equivalence

If you need a more complex function with flow control, whether two Turing machines are equivalent is undecidable in the general case. You might construct two functions with the same input/output mapping without being able to prove it except by testing all possible inputs, which hashing functions are designed to prevent. However, yes, you can always construct an equivalent function by yourself, by replacing subparts which are provably equivalent ($y+y+y$ becomes $y*3$) or reorder instructions when the order is commutative.


How do I find the key of the Vigenere cipher is if I already know the key length?

If you know the key length of a Vigenere cipher, you should group the letters in the given huge message by each of the key letters, then compute the frequencies for each group separately. If I understand right, you are doing a total frequency analysis, which is of no use.


Why are RSA ciphertexts different for the same plaintext?

Am I correct in assuming the above?

No you are not. You are showing textbook/raw RSA, which is little more than modular exponentiation. To be secure RSA has to use padding methods. Without padding, RSA would indeed generate the same ciphertext each time. This alone would break the security requirements of a cipher. There are many other attacks on textbook RSA. Fortunately the code you linked to specifies OAEP encryption, which is assumed to be secure.

  If yes, where is $n$ and what is the format for storing the message?

$n$ is not part of the ciphertext. It is however part of both the public key and the private key. The output format of RSA/OAEP is simply a byte array of the same size - in bytes - as the modulus, almost indistinguishable from random.
In your case it is base 64 encoded, which is needed if you want to store or send the ciphertext as printable text. See also the answer on your last question below.

  If No, what is the correct method?

The method used in the code, OAEP, is specified in PKCS#1 v2.1 and 2.2 of RSA labs. As these standards keep changing location I usually use the RFC 3447 instead.

  The output is 172 characters each time? How does that work out?

The output of the RSA encryption is of course always less than the modulus. As part of the PKCS#1 algorithm it is put through the I2OSP transformation (see the RFC). This encodes the resulting number from the calculation to an octet string (or byte array) with the same size as the modulus, in bytes. To be precise, it is transformed into a byte aligned, statically sized, unsigned, big endian encoding.

Now you see the output as Base 64. That means that it consists of $(172 / 4) * 3 = 129$ bytes. However, there is one padding character =, so that means a ciphertext of 128 bytes or a ciphertext of 1024 bits. This means that your modulus and therefore your key size is also 1024 bits. You should upgrade to a higher key size.

  If padding is different each time, shouldn't it be mentioned or the length of the actual message be mentioned with the cipher text so that deciphering code can differentiate the padding from the actual message?

The trick is that first the ciphertext is converted in the number, then after modular exponentiation the padded plaintext message appears. The padding is self descriptive; it isn't just random characters.

  I also found out that I can't encrypt more than 86 characters. Why? Is there a limit on the number of characters by RSA?

There is a relatively high amount of padding, including said overhead. So the type and minimum amount of padding determines the limit that can be encrypted using a single "block" encrypt of RSA. Usually a random symmetric data key is encrypted, which in turn encrypts the plaintext. This is because RSA is highly inefficient. This type of protocol is called a hybrid cryptosystem. Instead of PKCS#1 compatible RSA, RSA KEM could also be used for encryption.


Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):

  If $f$ is a $n$-bit one-way function, then $g(x)=0^{n}\mathbin\|f(x)$ is a $2n$-bit one-way function.

We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.

Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $\mathtt{false}$ if all the left $\left\lfloor m/2\right\rfloor$ bits of the result are zero; otherwise output $\mathtt{true}$.

That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $\mathtt{false}$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $\mathtt{false}$ with probability $2^{-n}$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^{-n}$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.

We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.

The question errs when it states

  because it is easy to find a number that could be an output from $g$, that isn't pseudorandom.

Problem with that line of thought: it holds including for a pseudo-random function $f$ that "it is easy to find a number that could be an output from $f$"; in particular, the all-zero bitstring $0^{2n}$ is such "number".

We can try and make that quantitative: the all-zero bitstring $0^{2n}$ is much more likely to occur for $g$ (probability $2^{-n}$ with some extra hypothesis) than it is for a random function $f$ with the same output set (probability $2^{-2n}$).

But it's not enough to remark that it is easy to find a number more likely to be an output from $g$ than it is to be an output for random function $f$. Problem with that alternate line of thought: as $n$ grows, it becomes exponentially unlikely that a certain number will be the output of $g$ or $f$, thus we can't build a polynomial-time distinguisher from the existence of a single such number.

Note, per comment: this answer assimilates a pseudorandom generator to a pseudorandom function (as does the question), by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.


Prevent hash collisions with HMAC secret as IV

Probably not, unless the paths you are trying to protect include a secret large enough to make it impossible to brute force the hash.

The problem is that this will protect against people finding paths by matching against all the possible values. But assuming the paths can be easily guessed, it is probably not enough to prevent brute-forcing a single path at a time. Furthermore, if you have a hierarchic tree and you also hash the roots of a particular branch, then you can first brute force the root, then the first subdirectory ... until you reach the desired end node.

Most of the time people will protect URL's by keeping a map, where a random value of about 64 to 128 bits is mapped to a specific URL (or path). Obviously the map itself must then be kept secure.

You can slightly approve your algorithm by actually using PBKDF2 with a high iteration count. But even with that brute-forcing the path could be doable.


Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$

The complexity of the number field sieve can be obtained from the expected size of the coefficients of the polynomial $f(x) = x^d + c_{d-1} x^{d-1} + \ldots + c_0$: if $c_i \le N^{\epsilon/d}$, then the expected runtime is

$$ \exp\left(\left(\left(\frac{32(1 + \epsilon)}{9}\right)^{1/3} + o(1)\right) (\log N )^{1/3} (\log \log N)^{2/3}\right),$$

or simply $L[1/3, (32(1 + \epsilon)/9)^{1/3}]$. When $\epsilon = 1$, we get $L[1/3, (64/9)^{1/3}]$ aka the GNFS, and when $\epsilon = 0$ (more accurately $o(1)$) we get the SNFS. Where does that put your example?

This requires analyzing the probability of smoothness of the numbers tested in the sieving phase, which, among other factors, depend on the size of the evaluated polynomial. The sieving process tests integers of the form

$$ F(a,b) = (a - bm) b^d f(a/b) = (a - bm)(a^d + a^{d-1}b c_{d-1} + \ldots + b^d c_0). $$

If we bound $a$ and $b$ to $M$, and $m, c_i$ to $N^{1/d}$, the size of $F(a,b)$ is bounded by $2(d + 1) M^{d+1} N^{2/d}$. In the SNFS, since both $m$ and $c_i$ are $o(1)$, the bound is much smaller, since it does not carry a $N^{1/d}$ factor anymore.

In your case, we have a mixed bag: the upper coefficients of the polynomial will be very small or 0, while the lower ones will be larger. For example, with degree $8$ and base $2^{256}$, your example results in the polynomial

$$ x^8 + c_1 x + c_0. $$

This polynomial is sparse, yes, but its expected $F(a, b)$ value size bound is not very far out from the general case: $2h M^{d+1} N^{2/d}$, where $h$ is the amount of nonzero coefficients in the polynomial. This is a constant improvement, but does not asymptotically alter the smoothness probability. So I expect your suggestion to be somewhat easier that a random prime, but not significantly so.

Since finding good polynomials seems to be an art in itself, it is hard to say when exactly the $c$ in $2^n + c$ becomes large enough to thwart the SNFS. A good rule of thumb would perhaps be to ensure that at least $c_0$ is $N^{1/d}$, by setting $c>2^{n/d}$. Since $d$ is an exponent in the size expression stated above, it will tend to be small: 1024-bit numbers are expected to have a $d$ of $6$ or $7$; 2048-bit will probably use degree $8$; and the optimal asymptotic expression for $d$ is $((3\log N)/(\log \log N))^{1/3}$, so it is very slow growing.

On a related note, the Schirokauer method for low-weight primes would not work here: it bounds the $c$ in $L[1/3, c]$ complexity of the NFS for an integer of (signed) weight $w$ as

$$ (32/9)^{1/3}((\sqrt{2}w - 2\sqrt{2} + 1)/(w - 1))^{2/3} < c < ((32/9)(2w-3)/(w-1))^{1/3}. $$

Replacing $w$ with $256$ results in the bound $1.9215 < c < 1.9217$, barely distinguishable from the GNFS.


RSA algorithm: Must $e$ be less than $\varphi(N)$?

First, the Euler's theorem

if $n$ and $a$ are coprime positive integers then
$$a^{\varphi(n)} \equiv 1 \pmod n$$ where $\varphi(n)$ is Euler's totient function.

Take $e> \varphi(n)$. Then, there exists $e' < \varphi(n)$ such that: $$e \equiv e' \pmod {\varphi(n)}$$
Then, we can write $$e = e' + k \cdot \varphi(n).$$
This $e'$ is the smaller representation of $e$ that does the same job.
$$a^{e} \equiv  a^{e' + k \cdot \varphi(n)} \equiv a^{e'} a^{k \cdot \varphi(n)}  \equiv   a^{e'} (a^{\varphi(n)})^k  \equiv a^{e'} (1)^k  \equiv a^{e'} \pmod n$$ Therefore, there is no need for $e > \varphi(n)$.
We choose $e$ small so that the encryption can take a small amount. This is what we can control. We don't want the private exponent $d$ small, since it is insecure. If we take a random $e$, then we will not have the benefit.
Commonly used $e$'s are $\{3, 5, 17, 257\text{ or }65537\}$ and there is no danger even with $e=3$, as long as correct padding is used.
For encryption: Use Optimal Asymmetric Encryption Padding (OAEP) (RSA-OAEP) or RSA PKCS#1 v1.5 padding, the former is easier to implement, the later had many attacks due to improper implementations.
For signatures: Use Probabilistic Signature Scheme (PSS) and known as RSA-PSS.

Note 1: We first choose the $e$, then we choose the primes, not the reverse, since we may not get $\gcd(e,\varphi(n)) =1$  for all $n = p \cdot q$ is product of two distinct primes $p$ and $q$.
Note 2: We use Carmichael lambda $\lambda$ instead of $\varphi$, since it can produce smaller $d$s, since $\lambda(n)∣\varphi(n)$


Can one-way permutations be constructed from one-way functions?

It was shown by Rudich in his PhD thesis [R] that it is not possible to construct one-way permutations (OWPs) from one-way functions (OWFs) in the framework of black-box reductions.$^1$ This was later strengthened by Matsuda and Matsura [MM], who ruled out black-box construction of OWPs from injective OWFs (which are much more structured than OWFs) that expand by even a single bit. So, yes assuming OWPs is strictly stronger than assuming OWFs (or iOWFs).

The technique employed in both the results is called oracle separations. The idea is to construct an oracle relative to which OWFs (or iOWFs) exist, but any black-box construction of one-way permutations is broken. An overview of Rudich's argument can be found on this thread.

But as Maeher points there could still exists non-black-box constructions of OWPs from OWFs. For example, we know that given indistinguishability obfuscation (IO), it is possible to construct (even trapdoor) OWPs from OWFs [BPW].$^2$ I believe a construction without IO is still open.

You can read more about the different notion of reductions here and on black-box separations here and the references therein.

$^1$ This was under a conjecture which was later proved by Kahn et al. [KSS].

$^2$ There have been attempts at at ruling out even non-black construction of cryptographic objects from one-way functions (e.g, [DS]), but I am not sure if any of them extend to OWPs.

[BPW] Bitanksy, Paneth and Wichs, Perfect Structure on the Edge of Chaos, TCC 2016

[DS] Dachmann-Soled, Towards Non-Black-Box Separations ofPublic Key Encryption and One Way Function

[KSS] Kahn, Saks and Smyth, A dual version of Reimer's inequality and a [enter link description here]5proof of Rudich's conjecture, CoCo 2000

[MM] Matsuda and Matsuura, On Black-Box Separations among Injective One-Way Functions, TCC 2011

[R] Rudich, Limits on the Provable Consequences of One-way Functions, PhD Thesis


Finding out the greater number under zero-knowledge conditions?

Yes, it is possible. Actually, any statement in NP can be proven in zero knowledge. This means that if something can be proven by releasing some information, it is possible to prove the same without releasing any information, i.e. in zero knowledge.


On the practical side of things, if your hypothetical function is hard to invert, and assuming collisions are hard to find, why does it matter that it be bijective? For sufficiently large $n$ you can't construct a counterexample anyway, so a hash function may as well be bijective as far as anyone cares.

Otherwise, not exactly what you're asking for but you could try for a white-box block cipher implementation, basically just pick a block cipher, pick a random key, and embed the key in your implementation in such a way as to not be easily retrievable from the code. There are some papers describing techniques to do so, it might be worth taking a look.


Yes it is possible, check out the CGS voting protocol: A Secure and Optimally Efficient Multi-Authority Election Scheme. In this voting scheme, each voter encrypts their vote $v \in \{0,1\}$ with Elgamal encryption: ${\it ctxt} = (g^vg^{xy}, g^y)$ under public key $(g, g^x)$. At this point anyone can compute the aggregate of all votes as the componentwise product of all ballots: $(g^{\sum v_i}, g^{x\sum y_i}, g^{\sum y_i})$ and the authorities (who jointly hold the secret key $x$ matching the public key) decrypt this ciphertext.

In order to make this protocol secure against malicious voters, the voters are required to provide a zero-knowledge proof the their encryption is an encryption of 1 or 0 but of nothing else. This is accomplished using the CDS '94 technique, which allows you to compose simple zero-knowledge proofs using (among other access structures) "and" and "or" type predicates. Specifically, the zero-knowledge proof says "this ciphertext is an encryption of 1 OR this ciphertext is an encryption of 0".

In your case, a voter's ballot should consist of two ciphertexts so that they can be tallied independently across voters leading to a tally for each candidate. Accordingly, there should be two "this ciphertext encrypts 0 or 1" proofs.

You do need a way to collect all these encrypted ballots. Voting schemes usually assume the existence of a public append-only bulletin board available to everybody. If access to the bulletin board logs your identity, then you can use those logs to identify double voters and count only their most recent ballot. An alternative is to assume that each voter has a public / private key pair associated to a digital signature scheme. They then sign their votes, and the talliers make sure not to count votes twice that are signed by the same public key.


Regarding your first question, it is my understanding that DKG techniques are in practice mainly used for offline signing, such as when a certificate authority issues new intermediate CA certificates. Using DKG for online signing, such as server side SSL/TLS, is not a problem that is solved by the papers you refer to, since the threat scenario is significantly different from that of offline signing. More precisely, to guard yourself against unauthentic signing requests in the online case, the front end server has to authenticate itself to the back end key share servers, but if it is able to do that, it is able to store a private (or secret) key securely and doesn't really need DKG in the first place.


What is the main difference between finite fields and rings?

Since you specified finite fields and other answers didn't talk about it, I am adding the following:

Fields are rings which are commutative and in which all nonzero elements have multiplicative inverse.

But finite fields have another important property that distinguish them from rings: every finite field is completely specified by its order, because they always have exactly $p^n$ elements for some prime $p$ and natural $n$ and any two finite fields of same order are isomorphic.

Notice, saying that two fields are isomorphic means that they are the same, but represented in two different ways.

That is not the case for rings. For instance, this answer provides examples of rings that have $4$ elements but are not isomorphic:

$\mathbb{Z}_4,~ \mathbb{F}_2[x]/(x^2+x),~ \mathbb{F}_2[x]/(x^2+x+1),~ \text{and} ~ \mathbb{F}_2[x]/(x^2)$


Is reusing keys for CBC and CBC-MAC secure when using encrypt-then-MAC?

No, it is not necessarily secure. Here is a simplified example of why not.

Assume one block zero messages are encrypted without padding. The ciphertext is $I||E(I \oplus 0)$. The MAC value is thus $E(E(I) \oplus E(I)) = E(0)$. So regardless of the IV, the MAC is the same for all such messages. So if you encrypt several zero messages you can leak that fact through the MAC.

When you take padding into account this exact issue is no longer possible, but you should see how it is possible for the MAC and encryption functions to end up using the same values.


Why does TLS 1.3 use random-looking nonces for AEAD?

As @CodesInChaos mentions in the comment, the purpose of the nonce randomization in TLS 1.3 is to combat multi-user attacks. That is, attacks where the adversary attacks multiple users simultaneously, and is happy as long as it breaks at least one user's connection without any regard to which user this is specifically. This motivation is explicitly called out in the RFC (Appendix E.2):

  In order to prevent mass cryptanalysis when the same plaintext is repeatedly encrypted by different users under the same key (as is commonly the case for HTTP), the nonce is formed by mixing the sequence number with a secret per-connection initialization vector derived along with the traffic keys. See [BT16] for analysis of this construction.

The idea of randomizing the nonce has received analysis in two academic papers:

Mihir Bellare and Björn Tackmann. The Multi-user Security of Authenticated Encryption: AES-GCM in TLS 1.3. CRYPTO'16. ePrint link
Viet Tung Hoang, Stefano Tessaro and Aishwarya Thiruvengadam. The Multi-user Security of GCM, Revisited: Tight Bounds for Nonce Randomization. CCS'18. ePrint link


Automated security protocol verification tool for eCK model

Just wrapping my comment into an answer as it seems to be what you're looking for…

CryptoVerif can be used for verification of security against polynomial time adversaries in the computational model. It's available via http://prosecco.gforge.inria.fr/personal/bblanche/cryptoverif/cryptoverifbin.html

Related to your "it doesn't work on my computer", here's an example how to test if it works (which it will on Win7 - which you previously wrote you're using):

create c:\cv\ and decompress the contents of the downloaded package in there.
Open a command-line prompt and go to c:\cv\ where the cryptoverif.exe resides.
Run cryptoverif.exe c:\cv\examples\fdh.cv

As for your question about TEX output, it would go like this:

cryptoverif.exe -tex somefilename.tex c:\cv\examples\fdh.cv

The manual, which is included in the download package, will provide you with the rest of the commandline parameters and a detailed description on how to use it.

Here's a screenshot of the --help parameter:

EDIT

A bit late, but The Scyther Tool may come handy too.


ECDSA over $\mathbb{F}_{p^n}$ for $n>1$. How to calculate $r$ and $s$

However, $x_1$ is an element of $\mathbb{F}_{p^m}$, which for $m>1$ it doesn't make sense to compute it's remainder over an integer.

True; when they defined ECDSA, they did not consider curves over extension fields.  This means that ECDSA just isn't defined in that case.

Now, it wouldn't be unreasonable to extend ECDSA to cover that case; the requirement for the $kG$ to $r$ mapping is that it $r$ be computationally uncorrelated to $k$; you might (once you've defined the field representation) treat $x_1$ as an $m$ digit number in the base $p$, and then take that value modulo $n$ (which might be what you suggested...).   Of course, any such extension would need to be analyzed before usage...

Also, as for your objection "$r d_A$ is a curve point", no, it is not.  $d_A$ is the private key, which is an integer between 0 and $n-1$


Is building your own inefficient but secure cipher hard?

If you are building something based on existing research, then yes, the construction of such a system would not be challenging. As a very basic example, it wouldn't be extremely challenging to implement a system based on the One-Time Pad given that you have a good programming background and assuming you follow the algorithm's stipulations correctly (e.g. avoiding repeated keys for new messages, good RNG, etc.), your system will be provably secure.

However, if you seek to design and develop new encryption schemes, you might have a harder time. You will likely encounter issues in multiple layers starting from the theoretical development and proof of security and all the way to the practical implementation of the scheme. That is, you will have to, firstly, design an encryption algorithm that can be proved to be secure in a mathematical way. Secondly, depending on the complexity of the algorithm that you designed, you will have to be extra careful in avoiding bugs in your code that could allow a motivated attacker to break your crypto system.

Because of these reasons, it is highly encouraged that such algorithms are open: it allows for more eyes to look for both flaws in the theory as well as in practice.

Some resources to expand your research:

https://crypto.stanford.edu/~ananthr/docs/crypto-proofs.pdf
http://eprint.iacr.org/2000/067
(taken from: Proofs of security methodologies)


Forgery attack on Poly1305 when the key and nonce reused

In Poly1305

16-byte AES key k
16-byte additional key r
16-byte $n$ nonce

is required. The obligations of the users

Any protocol that uses Poly1305-AES must ensure unpredictability of the secret key $(k, r)$.
The sender must never use the same nonce for two different messages

The obvious attack is the crib-dragging that destroys confidentiality and this doesn't mean that the encryption key is revealed. And this is not the case.
The nonce for Poly1305 is calcualted as $nonce = \operatorname{AES}_k(n)$
$$\operatorname{Poly1305}( r, m, \operatorname{AES}_k(n))$$
The $r$ actually $\in \{ 2^{106} \}$ not a full 128-bit.
The Poly1305 authentication can be simplified as
$$(((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + \operatorname{AES}_k(n)) \bmod 2^{128}$$ where $c_i$'s are encoded message $m$, $r_i$ is the $r$ in bytes.
OPs case
if we omit the $\operatorname{AES}_k(n)$ for pure Poly1305 then the equation becomes
$$(((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) \bmod 2^{128}$$
Now, for simplicity only consider a small message that has 16-bytes and the same key and nonce is used. Then the for loop inside the while loop will work only once.
void poly1305_gmpxx(unsigned char *out,
    const unsigned char *r,
    const unsigned char *s,
    const unsigned char *m,unsigned int l)
  {
    unsigned int j;
    mpz_class rbar = 0;

    for (j = 0;j < 16;++j)
        rbar += ((mpz_class) r[j]) << (8 * j);

    mpz_class h = 0;
    mpz_class p = (((mpz_class) 1) << 130) - 5

    while (l > 0) {
        mpz_class c = 0;
        for (j = 0;(j < 16) && (j < l);++j)
            c += ((mpz_class) m[j]) << (8 * j);
        c += ((mpz_class) 1) << (8 * j);
        m += j; l -= j;
        h = ((h + c) * rbar) % p;
    }
    //Omitted since Pure Poly!
    //for (j = 0;j < 16;++j)
    //    h += ((mpz_class) s[j]) << (8 * j);

    for (j = 0;j < 16;++j) {
        mpz_class c = h % 256;
        h >>= 8;
        out[j] = c.get_ui();
    }
}

then we have
mpz_class h = 0;
mpz_class c = 0;
for (j = 0; j < 16 ;++j)
    c += ((mpz_class) m[j]) << (8 * j);

h = (c * rbar) % p;

for (j = 0;j < 16;++j) {
    mpz_class c = h % 256;
    h >>= 8;
    out[j] = c.get_ui();
}

The last loop actually outputs the 16 bytes of the $h$, since $p = 2^{130}-5$ is slightly less than the modulus.
Hint: play with the message, especially the upper part.
Note: rfc8439 replaced  RFC 7539

RFC 7539, the predecessor of this document, was meant to serve as a
stable reference and an implementation guide.  It was a product of
the Crypto Forum Research Group (CFRG).  This document merges the
errata filed against RFC 7539 and adds a little text to the Security
Considerations section.


Is there any non-interactive zero knowledge proof for Diffie-Hellman tuples

Usually, non-interactive ZK proofs are achieved by using a technique to transform an interactive proof into a non-interactive. For example you can use a common reference string or the Fiat-Shamir heuristic. If you assume pairings, then you can also use the techniques used in Groth-Sahai proofs, but I guess that doesn't apply to Diffie-Hellman tuples.


Determining susceptibility to frequency analysis

Whatever parameters you pass in will affect the resulting hashes.  If you compute only H(Firstname), then two users with the same first name will lead to the same hash even if they have different surnames.

P.S.  Consider letting users simply have a name so that you respect the vast populations of people out there whose names do not conform to the anglophone forename/surname model of names, or other problematic oversimplifications.


Encryption algorithms and the "One-Time pad"

There is an entire class of ciphers that do exactly this. They're called stream ciphers. At their most basic, they pretend to be a one-time pad. You give them a small key and they generate a stream of seemingly random bits. You then XOR these bits with your plain-text to make ciphertext.

You can add bells and whistles to this basic behaviour but what I've described is the essence of the stream-cipher.

The most famous of these stream ciphers is probably RC4. If you ever used SSL at all then you will have used this steam cipher.

Equally, if you've ever used a mobile phone you've probably had your voice traffic "protected" with A5/1.

There are people who are experts in just this area of cipher design.

There's nothing more to say really other than that this is a well established branch of cryptography with a very well developed body of research and many fielded designs.


the key space should be 5

Something is $5$, but that's not the key space.

The key space is the set $\{\mathtt{K1},\mathtt{K2},\mathtt{K3},\mathtt{K4},\mathtt{K5}\}$. We'll note it $\mathcal K$.

The size of the key space (or key space size for short) $\|\mathcal K\|$ is $5$.

The size of the key (or key size for short) in bits, that we'll note $k$, is the base-2 logarithm of the size of the key space, that is $k=\log_2(\|\mathcal K\|)$.
Here $k=\log_2(5)=\log(5)/\log(2)=2.3219\ldots$ bit.

  But some articles I've read say you do do $k^2$.

Read again: probably the article says that the size $\|\mathcal K\|$ of the key space $\mathcal K$ is $2^k$, where $k$ is the size of the key in bits. That is, $\|\mathcal K\|=2^k$. Or equivalently, $k=\log_2(\|\mathcal K\|)$.


What do we gain from hashing the length in Merkle–Damgård?

I am making the assumption you are asking why not just append the length to the output of the hash, the question is not quite clear on that. Take a very simple example of SHA-1 modified to do what I think you are asking. The results here are fake, but the example stands.

If we hash a byte stream of 0xFE25B6A1C8, we may receive the digest a9993e364706816aba3e25717850c26c9cd0d89d0000000000000028.

If we hash a byte stream of 0xFE25B6A1C800, we may receive the digest a9993e364706816aba3e25717850c26c9cd0d89d0000000000000030.

It should be clear that this is not a desirable property.

The same property applies to other inputs where there are trailing 0 bits within the same compression function call and the same total number of compression calls, the bits have no effect on the hash function without the length because of how they are used to generate the message word array.


I'll use ChaCha20 as an example. It's a stream cipher, but is used as the core of the system random number generator on Linux.
I'll also refer you to this excellent article about how ChaCha20 works as a stream cipher.
ChaCha20 can be used as a fast key erasure CSPRNG. When a caller requests $N$ bits of random data (a single number in the sequence), it's used to generate $N+256$ bits, and the last 256 bits are used as a new key for future requests. (Some systems like Linux additionally XOR in some bits from various system noise sources when they make this new key.)
ChaCha20 works by scrambling a 512-bit block repeatedly, using 20 rounds (broken into 80 quarter rounds) for each $N-256$ bits of output.
The inner state is the 512-bit block that gets scrambled. It consists of a constant value, a counter, a nonce (a second counter in this case), and a key (which is where the initial seed goes).
ChaCha20 is a strong cipher. It's computationally infeasible (read: effectively impossible) to discover anything about the key given only the output.
So if an attacker gets a copy of the inner state used in the generation of a requested number, they know the key used for that particular request, which is the last 256 bits of the previous request's output. But it's impossible to generate the key used for the previous request from any amount of its output, let alone the last 256 bits only, so they can't discover the number returned by the previous request from this alone. Therefore, they can't discover the previous number returned, and from there can't determine any other previous numbers in the sequence.
CSPRNGs other than ChaCha20 may have different sized inner states, but there's generally some fixed-size block that gets scrambled repeatedly in some manner. Part of it will be the seed, part will be other data needed in the computation of the output.


RSA figuring out the recipient of a ciphertext

First, we'll assume that $n_B > n_C$, and we'll assume that he has no knowledge of the plaintext messages (which, if $A$ uses randomized padding, which he ought, is an appropriate assumption, even if the adversary knows the text of the message).

Then, if any of the 12 messages $\mathit{ciphertext}_i \ge n_C$, then he knows that message cannot be to $n_C$ (because the result of the RSA encryption process is always an integer less then the modulus.  Hence, if all messages were to the same endpoint, then they all must be to $B$.

In contrast, if all 12 messages $\mathit{ciphertext}_i < C$, then it is possible that the messages were to either, however it is somewhat more plausible that there were to $C$, because of the possibility that, if there were to $B$, that fact would be leaked above.

Now, we can actually estimate the probability that the messages were actually towards $B$, but that fact wasn't leaked; RSA encrypted messages can be modeled as random values between $0$ and the modulus size.  Hence, the probability that all 12 encrypted messages happen to be $< n_C$ is approximately $(1 - n_C/n_B)^{12}$; how large that is depends on the relative magnitude of the two modulii.


The immediately obvious idea is to use Pedersen commitments.  The idea here is that, in some group where the DLog problem is hard, we have two generators of unknown relation $g, h$, and a commitment to $x$ is the value $g^x h^r$ (for some random $r$).

To reveal the commitment is easy; you just give the values $x, r$ (and the verifier can check).

To prove that a value $x'$ is not the committed value to a commitment $g^x h^r$, the prover selects random values $s, t$, and publishes the value $h^t$, along with a zero knowledge proof that he knows the dlog of $h^t$ to the base $h$ (a standard cut-and-choose proof works).  Then, both sides compute $g^{-x'} h^t (g^x h^r) = g^{x - x'} h^{r+t}$, which we will call $j$.  Now, the prover computes $j^s = g^{s(x-x')} h^{s(r+t)}$, and outputs that, along with the values $s(x-x')$, $s(r+t)$.  He also outputs a zero knowledge proof that he knows the discrete log of $j^s$ to the base $j$.

The verifier can check that $s(x-x') \ne 0$, that the values $s(x-x')$, $s(r+t)$ make up the outputted value $j^s$, and that the proofs of knowledge of $s, t$ are valid.

Then, the verifier knows that the prover knows the value $s(x - x')$ and that it's not zero, hence $x - x' \ne 0$ and so whatever $x$ is, it ain't $x'$

There are also standard range techniques that would also work; I believe that this is more straight-forward...


Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?

I believe it is also used in other lattice based schemes that use standard LWE. For example, the Frodo paper. They used a $seed_A$ and a Gen($\cdot$) function to compute $A$. Then Alice sends $seed_A$ instead of $A$ for the actually exchange. Gen($\cdot$) is a prior-agreed pseudorandom function that extracts and extends the seed.


Is this scheme to derive multiple keys secure?

I see no obvious security flaws, but it seems inefficient and is nonstandard.

You would be better off always using the root key as the HMAC key and basing the HMAC message/data on only the key index (or other identity) rather than previous keys. That way you can create any of the keys independently. That is essentially what HKDF does in HKDF-Expand.

If you wanted to use HKDF-Expand you would have something like:

val privateKey0 = HMAC-SHA256(key: rootPrivateKey, data: "key0" || 0x1)
val privateKey1 = HMAC-SHA256(key: rootPrivateKey, data: "key1" || 0x1)
...

The 0x1 is the byte with value 1. You could skip it since you use a hash with the same length as the derived keys, but including it allows you to easily define how to move to a larger elliptic curve (i.e. just use HKDF to generate a longer key).


What is the difference between: ecdsap, ecdsak, and ecdsab in the output of "openssl speed"? What do the letters P/K/B refer to?

First: If you're looking for a signature scheme, forget all of those; I recommend Ed25519.  It too uses elliptic curves, it's standardized in RFC 8032, and there are implementations widely available.  It's safer and faster and simpler than any of the signature schemes you listed: ECDSA is an archaic design, and most or all of the curves mentioned there fail to satisfy modern security criteria for curves.

With that caveat in mind, to answer the question you asked:

The nomenclature $\mathrm{ecdsa}tn$, for a type $t \in \{\mathrm p, \mathrm k, \mathrm b\}$ and number $n$, mostly corresponds to ECDSA over the NIST Curve $t{\operatorname-}n$ defined in FIPS 186-4, over a field of about $2^n$ elements.  For example, ecdsap256 uses NIST Curve P-256, or just NIST P-256 for short.  Prior to FIPS 186-4, the curves also appeared in SECG standards.  One of the curves, secp160r1 as used by ecdsap160, does not appear in FIPS 186-4, presumably because it provides too little security.

(The methods allegedly used to choose the curves are prescribed in ANSI X9.62, and some of the curves also appear in it, and possibly also in IEEE P1363, but what self-respecting anarchist cypherpunk has the cash to shell out for a copy of a bureaucratic standard like that?)
The field size $2^n$ means that the highest expected cost for Pollard's $\rho$ to compute discrete logarithms that you, the defender, can hope for is approximately $\sqrt{2^n\pi/4} \approx 2^{n/2}$; for more on prime, field size, curve shape, and curve order, see an answer to an earlier question, and for more on other security criteria, see SafeCurves.
The letters p, k, and b represent different types of curves with different properties.  I include the full gory details for the sake of curiosity, not because you should be discriminating on these criteria—as before, ideally, you would just use Ed25519, which uses a curve, edwards25519, not in this list at all.

The p curves are curves over prime fields $\mathbb Z/p\mathbb Z$ with allegedly* randomly generated parameters.  They all have the short Weierstrass form $y^2 = x^3 - 3x + b$ for a coefficient $b$ chosen from an unexplained seed.

Using a prime field rather than an extension field, particularly a binary extension field, is the most conservative choice for an elliptic curve.  The most widely used one is probably NIST P-256, also known as secp256r1.

In addition to being defined on a prime field, all of these curves have prime order, meaning the number of elements on the curve (with coordinates in the field and not an extension) is prime.  Thus all of these curves fail SafeCurves because they cannot admit the Montgomery ladder for fast constant-time scalar multiplication, or complete Edwards formulas for fast constant-time arithmetic, which require a cofactor of at least 4; and they are not rigid.  Some of them additionally fail SafeCurves for other reasons.

ecdsap160: secp160r1, defined in [1], §2.4.2, p. 10, over the prime field of characteristic $p = 2^{160} - 2^{31} - 1$ by $y^2 = x^3 - 3 x + b$, where $b$ is 1C97BEFC 54BD7A8B 65ACF89F 81D4D4AD C565FA45, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 1053CDE4 2C14D696 E6768756 1517533B F3F83345.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{80}$ curve additions, which is a plausible cost today,† so it is not endorsed by NIST and it falls far short of the SafeCurves requirement of $2^{100}$ cost for Pollard's $\rho$.
ecdsap192: secp192r1, a.k.a. NIST P-192, defined in [2], §2.2.2, p. 6 and [3], §D.1.2.1, p. 90, over the prime field of characteristic $p = 2^{192} - 2^{64} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 3045AE6F C8422F64 ED579528 D38120EA E12196D5.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{96}$ curve additions, and while it is endorsed by NIST, it falls short of the slightly higher standard imposed by SafeCurves.
ecdsap224: secp224r1, a.k.a. NIST P-224, defined in [2], §2.3.2, p. 8 and [3], §D.1.2.1, p. 90, over the prime field of characteristic $p = 2^{224} - 2^{96} + 1$ by $y^2 = x^2 - 3x + b$ where $b$ is B4050A85 0C04B3AB F5413256 5044B0B7 D7BFD8BA 270B3943 2355FFB4, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{112}$ curve additions.  It fails SafeCurves additionally because its twist has composite order with no particularly large prime factors, enabling a variant of Lim–Lee small-subgroup attacks, and therefore requiring the additional complexity of point validation in protocols using it.
ecdsap256: secp256r1, a.k.a. NIST P-256, defined in [2], §2.4.2, p. 9 and [3], §D.1.2.3, p. 91, over the prime field of characteristic $p = 2^{224} (2^{32} - 1) + 2^{192} + 2^{96} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed C49D3608 86E70493 6A6678E1 139D26B7 819F7E90.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{128}$ curve additions.
ecdsap384: secp384r1, a.k.a. NIST P-384, defined in [2], §2.5.1, p. 10 and [3], §D.1.2.4, p. 91, over the prime field of characteristic $p = 2^{384} - 2^{128} - 2^{96} - 2^{32} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is B3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112 0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed A335926A A319A27A 1D00896A 6773A482 7ACDAC73.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{192}$ curve additions.
ecdsap521: secp521r1, a.k.a. NIST P-521, defined in [2], §2.6.1, p. 11 and [3], §D.1.2.5, p. 92, over the prime field of characteristic $p = 2^{521} - 1$ by $y^2 = x^3 - 3x + b$ where $b$ is 0051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3
B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88 3D2C34F1 EF451FD4 6B503F00, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed D09E8800 291CB853 96CC6717 393284AA A0DA64BA.

The expected cost of Pollard's $\rho$ to compute discrete logarithms in this curve is about $2^{259}$ curve additions.  It is not assessed by SafeCurves, presumably because there is a much better curve E-521 over the Mersenne prime $2^{521} - 1$, but it turns out to pass all the same criteria as NIST P-256 and NIST P-384 at a somewhat higher security level: embedding degree $(\ell - 1)/4$; CM discriminant ${>}2^{100}$; not rigid (manipulable but not trivially so); no Montgomery ladder; twist embedding degree $(\ell' - 1)/6$, twist cofactor $5\cdot7\cdot69697531\cdot635884237 = 1551184646225159645$, prime twist subgroup order $\ell' \approx 2^{460.57}$; no Edwards addition law.

The k curves are curves over binary extension fields $\operatorname{GF}(2^m)$ with a special property, called Koblitz curves.  Specifically, each exponent $m$ of the field size is prime, and each curve has the Weierstrass form $y^2 + xy = x^3 + ax^2 + b$ where $a, b \in \{0,1\}$, chosen so that the Frobenius map $\varphi\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$ (which can be efficiently computed by bit-shifting) has trace 1, which has the consequence that $[2^m]P = \varphi(P) - \varphi^2(P)$, making the evaluation of scalar multiplication particularly cheap, as noted by Koblitz in 1992 after whom the class of curves is named.

The security of binary elliptic curves against discrete logarithms is not as well-understood (see in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18), so all of these curves fail SafeCurves.

The class of curves named Koblitz curves is sometimes considered to include any curve with an efficient endomorphism to speed up computations as proposed by Gallant, Lambert, and Vanstone in 2001, not just binary curves.  secp256k1, used by Bitcoin, is an example of a prime Koblitz curve.  These endomorphisms make some people nervous but are not known to destroy security.

ecdsak163: sect163k1, a.k.a. NIST K-163, defined in [2], §3.2.1, p. 17 and [3], §D.1.3.1.1, p. 94, over the binary field $\operatorname{GF}(2^{163})$ by $y^2 + xy = x^3 + x^2 + x + 1$.
ecdsak233: sect233k1, a.k.a. NIST K-233, defined in [2], §3.3.1, p. 19 and [3], §D.1.3.2.1, p. 95, over the binary field $\operatorname{GF}(2^{233})$ by $y^2 + xy = x^3 + x^2 + 1$.
ecdsak283: sect283k1, a.k.a. NIST K-283, defined in [2], §3.5.1, p. 21 and [3], §D.1.3.3.1, p. 96, over the binary field $\operatorname{GF}(2^{283})$ by $y^2 + xy = x^3 + x^2 + 1$.
ecdsak409: sect409k1, a.k.a. NIST K-409, defined in [2], §3.6.1, p. 23 and [3], §D.1.3.4.1, p. 97, over the binary field $\operatorname{GF}(2^{409})$ by $y^2 + xy = x^3 + x^2 + 1$.
ecdsak571: sect571k1, a.k.a. NIST K-571, defined in [2], §3.7.1, p. 25 and [3], §D.1.3.5.1, p. 99, over the binary field $\operatorname{GF}(2^{571})$ by $y^2 + xy = x^3 + x^2 + 1$.

The b curves are curves over binary extension fields $\operatorname{GF}(2^m)$ with allegedly* randomly generated parameters.  They all have Weierstrass form $y^2 + xy = x^3 + x^2 + b$ for a coefficient $b$ chosen from an unexplained seed.

Unlike the binary Koblitz curves, the allegedly-random binary curves have neither a rigid form, nor special structure admitting efficient implementation.  Like the binary Koblitz curves, they are binary, and so their security is poorly understood.

ecdsab163: sect163r2, a.k.a. NIST B-163, defined in [2], §3.2.3, p. 18 and [3], §D.1.3.1.2, p. 94, over the binary field $\operatorname{GF}(2^{163})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 02 0A601907 B8C953CA 1481EB10 512F7874 4A3205FD, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 85E25BFE 5C86226C DB12016F 7553F9D0 E693A268.

There is also a similar curve sect163r1, generated by a variant of the ANSI X9.62 Annex A.3.3 procedure.
ecdsab233: sect233r1, a.k.a. NIST B-233, defined in [2], §3.3.2, p. 19 and [3], §D.1.3.2.2, p. 95, over the binary field $\operatorname{GF}(2^{233})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 0066 647EDE6C 332C7F8C 0923BB58 213B333B 20E9CE42 81FE115F 7D8F90AD, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 74D59FF0 7F6B413D 0EA14B34 4B20A2DB 049B50C3.
ecdsab283: sect283r1, a.k.a. NIST B-283, defined in [2], §3.5.2, p. 22 and [3], §D.1.3.3.2, p. 97, over the binary field $\operatorname{GF}(2^{283})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 027B680A C8B8596D A5A4AF8A 19A0303F CA97FD76 45309FA2 A581485A F6263E31 3B79A2F5, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 77E2B073 70EB0F83 2A6DD5B6 2DFC88CD 06BB84BE.
ecdsab409: sect409r1, a.k.a. NIST B-409, defined in [2], §3.6.2, p. 24 and [3], §D.1.3.4.2, p. 98, over the binary field $\operatorname{GF}(2^{409})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 0021A5C2 C8EE9FEB 5C4B9A75 3B7B476B 7FD6422E F1F3DD67 4761FA99 D6AC27C8 A9A197B2 72822F6C D57A55AA 4F50AE31 7B13545F, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 4099B5A4 57F9D69F 79213D09 4C4BCD4D 4262210B.
ecdsab571: sect571r1, a.k.a. NIST B-571, defined in [2], §3.7.2, p. 26 and [3], §D.1.3.5.2, p. 100, over the binary field $\operatorname{GF}(2^{571})$ by $y^2 + xy = x^3 + x^2 + b$, where $b$ is 02F40E7E 2221F295 DE297117 B7F3D62F 5C6A97FF CB8CEFF1 CD6BA8CE 4A9A18AD 84FFABBD 8EFA5933 2BE7AD67 56A66E29 4AFD185A 78FF12AA
520E4DE7 39BACA0C 7FFEFF7F 2955727A, allegedly generated by the ANSI X9.62 Annex A.3.3 procedure from the unexplained seed 2AA058F7 3A0E33AB 486B0F61 0410C53A 7F132310.

References:

Recommended Elliptic Curve Domain Parameters, Standards for Efficient Cryptography: SEC 2, Certicom Research, version 1.0, 2001-09-20.
Recommended Elliptic Curve Domain Parameters, Standards for Efficient Cryptography: SEC 2, Certicom Research, version 2.0, 2010-01-27.
Digital Signature Standard (DSS).  Federal Information Processing Standards: FIPS PUB 186-4, United States National Institute of Standards and Technology, July 2013.
Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287.
C.H. Lim and P.J. Lee, ‘A key recovery attack on discrete log-based schemes using a prime order subgroup’, in Burton S. Kaliski, Jr., ed., Proceedings of Advances in Cryptology—CRYPTO 1997, Springer LNCS 1294, 1997, pp. 249–263.
Stephen D. Galbraith and Pierrick Gaudry, ‘Recent progress on the elliptic curve discrete logarithm problem’, IACR Cryptology ePrint Archive: Report 2015/1022, 2015-10-22.
Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200.

* NIST claims to have no documents about the origin of the seeds under which the parameters of curves over prime fields were pseudorandomly chosen.  I have not verified that they followed the ANSI X9.62 Annex A.3.3 procedure.  See also the bada55 curves and the SafeCurves commentary on rigidity. N.B.: This is not evidence of a back door.  (In contrast, Dual_EC_DRBG was clearly designed to have a back door that cryptographers rapidly recognized—the back door was even patented under the not-very-subtle euphemism of ‘key escrow’.)  This is only evidence that the authors didn't think hard about inspiring confidence that there is no back door.

† For comparison, the Bitcoin network today computes over $2^{80}$ SHA-256 evaluations in a day.


What's the differences among Blind Computation, Secure Multi-Party Computation, Secure Circuit Evaluation and Homomorphic Encryption

In short,

A cryptography scheme is a homomorphic encryption scheme if it is somehow equivalent to manipulate its plaintexts and its ciphertexts.

Secure multi-party computation and secure circuit evaluation are protocols to calculate functions in a distributed way without disclosing the data owned by each party and blind computation is any technique for transforming the data in a manner such that a third-party can calculate a specific function $f$ over these transformed data without knowing the value of $f$ when applied over the real data.

-- Verbose answer --

It is not right to say that

  all can process the encrypted data

In fact, the only one that must process encrypted data by definition is homomorphic encryption, because a scheme $\gamma$ is homomorphic for one operation $*$ if, considering $c_1 = E(m_1)$ and $c_2 = E(m_2)$, then $m_1 * m_2$ is equivalent to $c_1 * c_2$ (where equivalent means that $m_1 * m_2 = D(c_1 * c_2)$.

Secure Multi-Party is any protocol for doing distributed computations without revealing the data owned by each party.

For example, if I have $n$ numbers, you have $m$ numbers and we find out how to calculate the average of these $n + m$ numbers in such a way that we will get the result, but I will not know your numbers and you will not know mine, then we are doing Secure Multi-Party Computation. It doesn't require homomorphic encryption. But, homomorphic encryption is typically used because it makes things easier.

Blind computation (in this context) is a technique that aims to hide the input and the output values of a function, in such a way that this function can be calculated for one person and this person will not know the real values used as input and the real value of output. Note that in Secure Multi-Party Computation, unlike the blind computation, all the parties involved know the output value, and the function is typically calculated by all of them in some iterative process.

For example, if I have $n$ numbers $x_1, x_2, ..., x_n$ and I require you to calculate their average. Then, I generate random numbers $r_1, r_2, .., r_n$ and, instead of sending the real data to you, I send $x_1+r_1, x_2 + r_2, .., x_n + r_n$. Then, you will calculate an average $\mu'$ that is not the real answer and send it me. Finally, I just have to subtract the random numbers divided by $n$ to get the real $\mu$.

This example is too simple. Usually, the function to be computed is more complex and it's hard to figure out how to preprocess the data to hide them and come back to the result after the computation. So, again, homomorphic encryption is a good tool...


Term for non-ARX symmetric-key cryptographic primitive design strategy

Primitives based purely on bitwise and shift/rotate operations can be described as being based on:

Binary Polynomials

Bitwise and, or, not, xor are element-wise $\mathbb{F}_2$ additions and subtractions; $n$-bit shift are based on multiplication by $x^n$ reducing $x^w$ where $w$ is the width of the word; rotation are based on multiplication reducing $x^w+1$.


Is there a maximum amount of data which can be encrypted using a symmetric (AES256) key?

You should generally never use a single AES key for more than a few petabytes of data because of the so-called birthday bound: Cryptosystems based on AES like AES-GCM tend to have distinguishing advantages bounded only by $$\frac{q(q - 1)/2}{2^b}$$ after processing $q$ blocks of data, where $b = 128$ is the block size, arising from the birthday paradox.

When $q \approx \sqrt{2^b} = 2^{64}$, the standard theorems provide essentially no security guarantees.  See sweet32 for what can go wrong when you reach the birthday bound of a block cipher—of course the birthday bound is much smaller for a 64-bit block cipher like Blowfish, where it is $2^{32}$, but the idea is still relevant to AES.

(Had we standardized a 256-bit block cipher like Rijndael-256 or Threefish, the birthday bound of $2^{128}$ would be completely irrelevant.  But we didn't, and while there are 256-bit block ciphers out there, hardly anyone ever uses them.)

Particular cryptosystems using AES may have smaller limits—for example, AES-GCM with a random nonce is unsafe for more than a few billion messages under the same key, because the nonce is only 96 bits long and the security degrades catastrophically in case of collision, which is expected to happen after only about $\sqrt{2^{96}} = 2^{48}$ messages.


PBKDF2 is defined for an arbitrary PRF, but in practice HMAC is usually used. Either with SHA-1 (original definition), SHA-256 (e.g. in scrypt) or even SHA-512-256 (NaCL). So first you can look at how swapping key and message affects HMAC.

HMAC has two cases depending on the length of the key: if it's no longer than the block size of the hash, it is used as is; if it's longer it is first hashed. After that, two keys are derived by XORing it with pads and the final function is:

$$H(k_1||H(k_2||m))$$

This leads to two reasons to prefer the defined order to the swapped one:

For every key shorter than the blocksize, there's an equivalent key $k' = k||0$, where a zero byte is appended. For every key longer than the block size, there's another key $k' = H(k)$ which is equivalent.

For randomly generated keys, or even passwords, these do not matter in practice. If you used a message in that position, however, it would be malleable – you could swap a long message with a gibberish one and use the same MAC value.
The key derivation through hash and/or XOR, as well as the initial block of each of the two hashes can be calculated once for a given key and used for many messages. In the swapped order everything would have to be calculated again.

Neither of these is a problem in PBKDF2, if you use a constant width salt, like a 256-bit random number. The first can only happen if two distinct salts can collide, which – barring an actual hash collision – requires them to be different length. The second doesn't matter, since many iterations are done with the same $k$ whether it's the password or the salt. (Swapping makes it an inconsequential amount faster to try multiple passwords against one salt.)

Additionally, swapping the order will not make finding a preimage any easier, unless the hash is broken. Since preimage resistance is what a password hash in concerned with, HMAC with arguments swapped should be OK.

(The above is not true for all MACs. For example, it is trivial to find some preimages for CBC-MAC with a known key.)

Regarding PBKDF2 itself, there's the additional fact that the password (i.e. HMAC key) is a part of every hash iteration, while the salt is only used once. This affects the cycles the hash can enter. With a constant salt as the HMAC key, every possible password would enter the same set of cycles. Since it only happens after around $2^{80}$ iterations for SHA-1, it too doesn't matter, even if it was somehow exploitable.

In conclusion, then, swapping the password and salt with PBKDF2-HMAC seems secure. With another PRF it could be insecure. Swapping them in HMAC for many other uses is also insecure. However, there is no good reason to swap them, so you should still use the normal defined order.


How can we formally define a Pseudo-Random Shuffle function?

A PRP (pseudorandom permutation) can be mapped onto the index of each element in vector $\mathbf{v}$ to generate a new index for that element in the shuffled array.

As long as the PRP is secure, the shuffle should be indistinguishable from random. Theoretically, this works if the PRP's input/output is the same size as the number of elements in the array. But in the real world, a PRP construction that can vary it's input/output size for various lengths doesn't exist.

AES-256 could be used as the PRP if there were $2^{256}$ elements in the array. Any stream cipher could be used as long as the size of the vector was a power of $2$. In the real world, there are also memory issues as you have to store values somewhere as you shuffle them. Fisher-Yates solves both these issues by using a PRNG to choose elements to exchange.

That's just my idea of a way to define a pseudorandom shuffle. Using a PRP should make the proof easy. Here's a paper that defines a pseudorandom shuffle in a different way: "The Strength of Weak Randomization: EasilyDeployable, Efficiently Searchable Encryptionwith Minimal Leakage"


Can you help me understand some details about the attack using SSL3 POODLE bytes?

to try again, I guess the attacker need try to modify the last byte

No. Some other (symmetric) padding oracle attacks do that, but here the attacker can't tweak the prior block and try another decryption because the MAC error already caused the session to be terminated. Instead the attacker causes the client (browser) to make a new request with the same data, and thus the same target plaintext (the cookie byte), but a random new key and state (IV). Statistically 1/256 of the time the last bytes in the $C_{i-1}$ (edited) and $C_{n-1}$ ciphertext blocks will be a 'lucky' pair that combines with the target (last) byte in $P_i$ so that the tampered plaintext block $P'_n$ ends with the desired value, 15 or 7 depending on the cipher blocksize. I.e. depending on your point of view either 1 of 256 values in $C_{n-1}$ reverses $C_{i-1}$ or 1 of 256 values in $C_{i-1}$ reverses $C_{n-1}$; the math treats them identically. For a slightly longer explanation, see my answer here or Steve Peltz's here.

  How does Adam get the chance ($2^{−64}$ or $2^{−128}$) in TLS?

Since TLS unlike SSLv3 checks all the padding octets, there is only one valid all-padding block out of all possible blocks the size of the blocksize of the cipher, which is either 128 bits for AES Camellia SEED or ARIA, or 64 bits for triple-DES or IDEA -- or original DES or the deliberately weakened 'export' DES-40 or RC2-40 if still used, although even implementations that still used SSLv3 protocol prior to POODLE should have disabled the single-DES and export ciphersuites.


Define $\mathbb{G} = \langle G \rangle$ the cyclic group generated by $G$.  The order of $\mathbb{G}$ is $n$.

In your scheme, an 8-bit message is encoded as a point $m = kG$.  An attacker gets access to the value of $sG + m$ for a random $s \in [0,n-1]$.  The question is: can the attacker recover the value of $m$ (and then the value of the corresponding message)?

The answer is no.  To see it, observe that the point $S = sG$ is a uniformly random element in $\mathbb{G}$.  As a result, the point $S + m$ is in turn a uniformly random element in $\mathbb{G}$.


Why are there $2^{56}$ possible DES keys when there are 64 key bits?

Each 56-bit key has a unique 8-bit parity value. For this reason there are only $2^{56}$ keys.


Do a 160-bit SHA-1 hash and a 160-bit slice of a SHA-256 hash have the same strength in terms of collision-free?

SHA-1 is broken in practice in terms of finding collisions. This shattered attack (identical-prefix collision attack) requires roughly $2^{63.1}$ SHA-1 evaluations and this is approximately 100,000 faster than finding collisions with generic birthday attack on 160-bit output that has $2^{80}$- time complexity. That is, for a hash function with $\ell$-bit output we expect at least one collision with a 50% probability within $2^{\ell/2}$ outputs.

There are no attacks on SHA-256 trimmed to 160 bit better than the generic collision attack due to the birthday attack. Therefore they are not the same in finding collisions, in this case, SHA-256 trimmed to 160-bit has better security than SHA-1.

The attacks on SHA-256 or similarly other iterated hash functions are performed on reduced rounds. We don't expect weakness on the trimmed version of well designed cryptographic hash functions. Except for the resistances which happens naturally. If such a weakness exists, it can represent a weakness in the designs of the hash function and this could be used to attack the full version.

Note that NIST deprecated the use of SHA-1 in 2011 way before the actual attack. 160-bit hash output is no longer considered secure. If you consider that Bitcoin miners reached $\approx 2^{92}$ double SHA-256 hashes per year in 06 Agust 2019, 160-bit is no longer secure, or even 180-bit. The hash rate $2^{92}$ for a year is for the double SHA-256 hashes. Therefore they can calculate $2^{93}$ SHA-256 in a year.

note: I've re-check the current hash rate of Bitcoin miners, it is was 80.294 Exa Hashes/s (1 exa is one quintillion (1,000,000,000,000,000,000) ) in 06 Agust 2019. It reached 110.6056 Exa on 23 October 2019, unfortunately, or hopefully, this is still $\approx 2^{92}$. In a second, this makes $2^{67}$ double SHA256 calculations which means, they can break the DES key less than a second or any 64-bit block-cipher.


Can you please explain weak keys of the following 2-round DES?

The definition of weak key in the question is a mixup with that of semi-weak key pair, or/and semi-weak key. Let's put these definitions straight.

We'll consider a block cipher $E$ over set $M$, with a key set $\mathcal K$.

The defining property of a weak key $K\in\mathcal K$ is: $\forall x\in M,\,E_K(E_K(x))=x$. In other words, encryption and decryption with $K$ are the same.

The defining property of a semi-weak key pair $(K_1,K_2)\in\mathcal K^2$ is: $\forall x\in M,\,E_{K_1}(E_{K_2}(x))=x$. In other words, encryption with one key in the pair is the same as decryption with the other.

The defining property of a semi-weak key $K\in\mathcal K$ is that there exists $K_2\in\mathcal K$ such that $(K,K_2)$ is a pair of semi-weak keys. In other words, the key occurs in a semi-weak key pair.

The M-DES block cipher in the question is a symmetric Feistel cipher with 4-bit message space $M$ and 4-bit key space $\mathcal K$; and a structure similar to that of DES, but simplified to caricature. In particular

The S-boxes have 1-bit input and 1-bit output (one is bit inversion, the other has constant output 1). Complete linearity follows: within polarity, any ciphertext bit is the XOR of whatever few plaintext and key bits influence it.
Expansion E is removed; and, beyond a mysterious and probably unrelated $|P|=2^4$, we are not told about a permutation P. Complete lack of diffusion between odd and even bits of the message space would follow that both are gone.

Reducing M-DES to equations, then applying the definition to find weak keys, is left as an exercise to the OP. A computer is not useful.


security of using digital signature as key derivation material

I'm sorry, but chances are this doesn't work.

The reason is of course that ECDSA signatures are usually fully randomized, meaning that there's randomness introduced in between the private key and the final signature. If you're looking at an ECDSA specification, the relevant value usually is called $k$.

What you'd rather need would be an RSA encryption / decryption keypair or an ECDH keypair. In this case you'd just store an encrypted key as a file or something and let the secure enclave decrypt it at each startup and keep the key in RAM. The downside being of course if an attacker can extract it from memory this application's security is screwed. If you have a static ECDH key pair you'd just store a public ECDH share and statically derive the key each time and use it as suggested.

If you have to use signatures though, you need to find a deterministic one that is offered by the enclave and use it as proposed in your question.
This can include ECDSA if it follows any standard for deterministic ECDSA (like RFC 6979) and this can also include deterministic RSA signatures (e.g. usually the older signature standards).

Bottom line: As long as you use some (intermediate) value in the key derivation which directly relies on a hardware-backed key (in a deterministic way), chances are this will be secure.
An example of how not to do such a derivation is given in Android's FDE setup (with the counter-example for a good derivation would be iOS actually)


Determine if a public key point y is negative or positive, odd or even?

Elements of finite fields don't really have a sign. But depending on context you can define a property that's different for $x$ and $-x$ (when $x$ is not $0$) and call that property sign.

Some possible choices:

A number is called a square (or Quadratic residue) if there is another number which produces it when squared. Since positive real numbers are squares, identifying square field elements with a positive sign is a natural choice.

The Legendre symbol is 0 for 0, +1 for squares and -1 for non-squares. The Legendre symbol of the product of two numbers is the product of the two Legendre symbols, which mirrors how signs behave under multiplication.

You can even define $i = \sqrt{-1}$ to get some kind of complex numbers. Imaginary values of the $y$ coordinate of an elliptic curve correspond to its twist.
You can use the least significant bit. Computing this is very cheap, you only need to look at that one bit. This approach is often used to store the "sign" of a compressed elliptic curve coordinate.
Values smaller than $p/2$ have one sign, values greater than $p/2$ the other. I believe Bitcoin uses this convention to define canonical signatures.

You can extend any of these definitions from the underlying field to the elliptic curve defined over that field by defining the sign of the point as the sign of its $y$ coordinate.


How does knowing the factorization of N help to obtain the secret?

Your question is related to the well known RABIN Cryptosystem which is similar to RSA, except the public exponent is 2.

As fgrieu mentioned, decipherment can be easily processed by the CRT algorithm, but some precautions must beforehand be observed during the key generation. In fact the solution of the equation gives 4 roots, which means that the solution of the initial problem when they exist (... $x \in QR(p\cdot q)$) is not unique. And asking which of one of four solution to return is a security problem, and without knowing these constraints, the probability of divulging the factorization of modulus is $0.5$. The determination of the right and secure solution must be carefully studied regarding the form of the factor p & q, and the properties of special integer called "Blum integers".

When restricting to correct message space, there is a unified inversion formula which runs on $\mathbb{Z}/n \mathbb{Z}$. I know it because it was specified in an early draft of SC27-ISO9796 at the end of the $80^{th}$. Unfortunately I don't remember it. Probably Fgrieu can confirm and search for it.