Without proof or even a precise definition: when a random variable has independent outputs with $p$ the probability to output $c$, then an optimal encoding of the source's outputs (one that minimizes the expected number of bits consumed to encode all successive values of a large number of outputs, including order) will use on average $-\log_2(p)$ bit to encode the output $c$. For example, $-\log_2(\frac14)=2$ bit for $p=\frac14$, as told to the OP.

As noted in the question, it is possible to make a different encoding that only uses $1$ bit to encode $c$, and that's less than $-\log_2(p)$ when $p<\frac12$. But that different encoding will use more bits on average than an optimal encoding does, thus that observation does not contradict the statement in the previous paragraph.

For example, if the source outputs $c$ with probability $p=\frac14$ and $b$ with $p'=1-p=\frac34$, the encoding that outputs 0 for $c$ and 1 for $b$ requires $1$ bit per output, always, thus also on average. But it is possible to make a different encoding that consume less bits on average, down to the Shannon entropy of the source, which for two outputs is $-p\log_2(p)-(1-p)\log_2(1-p)\approx 0.81$ (see binary entropy function). An example of such encoding is to group outputs two by two, and encode as follows:
$$
\begin{array}{cc|l|cc}
\text{first} & \text{second} & \text{encoding} & \text{size} & \text{probability}\\
\text{output} & \text{output}& & s & q\\
\hline
b & b & \mathtt{0}   & 1 & \frac9{16}\\
b & c & \mathtt{10}  & 2 & \frac3{16}\\
c & b & \mathtt{110} & 3 & \frac3{16}\\
c & c & \mathtt{111} & 3 & \frac1{16}
\end{array}
$$

The probabilities $q$ sum to $1$, and it is possible to unambiguously decode a stream of bits output by this encoder.

The average number of bits for encoding two outputs is the sum of the products $s\,q$, that is $\frac{27}{16}$. The average number of bit per output is half that, that is $\frac{27}{32}\approx0.85$, which is less than $1$.

It's possible to prove that we can make encoders that arbitrarily approach the output bit per input symbol ratio of the Shannon entropy, but not encoders below that limit. It's also possible to rigorously define the average number of bits needed to represent an output value for a given encoder, then to show that this quantity must converge to $-\log_2(p_i)$ for encoders that approach optimality. That's involved, but we can at least justify that value.

Whatever sensible definition we give to the average number of bits $r_i$ needed to represent an output value $i$ for a given encoder, it must be such that we can compute the average number of bits produced by the encoder to represent an output of the source as $\sum p_i r_i$. We see that with $r_i=-\log_2(p_i)$, we get the standard formula for Shannon entropy:

$$S=-\sum p_i\log_2(p_i)$$

which justifies that in this formula, $-\log_2(p_i)$ is the average number of bits needed to represent an output value $i$. Which matches what the OP was explained.


What schemes support atomic decryption+reencryption

The blockchain network Nucypher offers something like that, through their cryptographic scheme, with a help of semi-trusted proxies. The scheme is secure as long as proxies don't cooperate, enough proxies don't reveal the secret and enough proxies stay online. They have papers on their website.


What is the standard way to generate a unique non-reproducible ID?

It is desired a Unique Non-Reproducible ID (UNRID) which genuineness is publicly verifiable.

I know no standard for that. But we can take as UNRID the signature of a public fixed message (e.g. empty), if the signature scheme is randomized and EUF-CMA secure. Verification simply checks the signature. If probability of collision among signatures is satisfactorily low, security follows from EUF-CMA.

The signature scheme could be RSASSA-PSS of PKCS#1v2.2, with the advantage of fast signature verification. But for modern security that requires 256 bytes (342 Base64 characters), which is a lot.

A more compact option is a slight variant of ECDSA, where a signature $(r,s)$ becomes the UNRID $(r,\min(s,n-s))$, which is presented as EUF-CMA secure there, without proof but plausibly: EUF-CMA security of the signature scheme matters in Bitcoin, and was repaired with apparent success, in a manner equivalent to what's proposed. That would make the UNRID 64-byte (86 Base64 characters).

Using a signature scheme with message recovery, we can embed a serial number or other small ancillary information in the UNRID, without making it bigger. For RSA, ISO/IEC 9796-2 Scheme 2 would do (it's essentially RSASSA-PSS with message recovery). There are ECC-based randomized signature schemes with message recovery as compact as ECDSA, see bibliography.


Historic Authentication Schemes Before Computers

As explained by Cort Ammon, they mostly relied on physical, rather than mathematical processes.

Here is a video on Youtube titled "How to launch a nuclear missile", taken in the Titan Missile Museum mentioned by Cort Ammon.

The message contains a seven character string.
The personnel in the shelter have a set of envelopes with the first two letters on the outside.
If the inside of the envelope matches the message, they launch.

Here is another one from a British sub, starting at 23:00. Decryption is done behind a curtain.

It is all very manual, no computer is visible.
Note the wooden club used to protect the codes (24:17).


SHA's finite character set and collision

My question is, while we have infinite permutations for the input text, if the output hash is finite, then aren't all SHA algorithms meant to collide at some point?

Due to the pigeonhole principle, all hash functions will collide at some point. Since there are more inputs than outputs, the existence of collisions is unavoidable.

The job of a cryptographic hash function is to make finding collisions cost so much that it will never happen, and to make finding preimages prohibitively expensive as well.


There is no way to reduce the output of a single AES encryption operation to 64 bits with the possibility of decryption without error.

There are however ways to use AES to build a 64-bit cryptogram that can be decrypted without error. The simplest is: encipher the constant zero with AES, keep the first 64 bits, XOR with the plaintext to get the cryptogram. Problem is, that's insecure if the AES key is used more than once.

There are ways to allow several uses with the same key:

If an initial IV setup is tolerable (e.g. the IV overhead negligible compared to many later 64-bit cryptograms delivered in order), CTR mode is fine, as noted by Thomas M. DuBuisson.
Construct a 64-bit symmetric Feistel cipher using AES encryption for the round function (AES-encipher the concatenation of the round number and 32-bit input); with 10 rounds for good measure, and perhaps using addition modulo $2^{32}$ rather than XOR for combination of the output of the round function (so that the cipher is not always an even permutation, which would be noticeable after $2^{64}-2$ plaintext/ciphertext pairs), that's a secure 64-bit block cipher. Beware however that with this method (or any 64-bit block cipher) alone, identical 64-bit plaintexts will be recognizable as identical 64-bit ciphertexts.
FFX mode is another possibility, as noted by CodesInChaos.


Which algorithm do you recommend for practical use to generate unique passwords for each website?

The problem is almost exactly the same as in password based key derivation, so you could use a similar solution.

Derive a master secret from your password and a unique salt using e.g. PBKDF2 or scrypt: $S_m = PBKDF(p, s)$.
Derive a site-specific secret from the master using e.g. HKDF and the site URL: $S_u = HKDF(S_m, u)$.
Turn the site secret into a usable password, e.g. by encoding in base 64.

If you go this route you are putting all your eggs in one basket. If you forget the master password, you lose all the derived ones. If someone guesses it, they can derive all the others.

You would probably be better off just using a password manager that prevents guessing attacks. Otherwise the master must be very strong. A password manager generates random site passwords that leak no information about the master.


What is insecure about this simple AES implementation?

I think it is "dangerously hard" because there are things that might go wrong that you might be unaware of.

Below the list of things (not necessarily valid in your example) that might be the weak spot in the crypto:

is your random function random enough? If not it might be possible to predict the output
re-usage of things that should not be reused - keys, nounce etc.
timing attacks - does your code uses the same amount of time independently on where during the algorithm it fails or succeeds?
is there not side channel attack? - that can be used to determine the plaintext or part of the crypto

and the list is not complete.

I think in general the "bad at crypto" means that people are bad at implementing the algorithms and should not do it.

Use something that's there implemented by smarter people.
If you do it can still be misused (cases with re-using things that should not be reused or using not-random enough random numbers) but at least the implementation should be better and resistant to some attacks.


What cipher algorithm is this routine using?

Normally, questions like this are considered off-topic; however, in this case, I can give a quick answer -- it's RC4


Why does knowing the number of points on a curve help solve ECCDLP?

Actually, we don't count points to attempt to break Elliptic Curves, a major reason we count points is to ensure that we can't.

If the number of points on the curve is $n$, then we know how to solve the ECCDLP problem in $\sqrt{n}$ time.  However, if we know a factorization $n = pq$, then we can use that factorization to solve the ECCDLP problem in $\sqrt{p} + \sqrt{q}$ time.  Note that this is distinctly smaller; if $n$ is 256 bits, then $\sqrt{n}$ is 128 bits; we believe that no one has the computational resources to do $2^{128}$ work.  On the other hand, if $p$ and $q$ is 128 bits, then $\sqrt{p} + \sqrt{q}$ is about 65 bits; we know that performing $2^{65}$ work is achievable in practice.

To avoid this potential problem, we generate curves until we find one with a prime number of points on it (or, a prime times a small cofactor); once we have that, the above observation is of no use to an attacker.

Now, that's not the only reason knowing the number of points on a curve is useful, however it is a major one.


Is there any way to check hash of homomorphic encrypted data?

Note: I'm not a cryptographer, please take what I write below with a grain of salt. Most probably this protocol, without further fixes (or even fundamentally), is flawed.

I'm reformulating your question as follows, dropping the hash requirement, and replacing it with an interactive proof.

Alice has a message $m$ and wants send this message $m$ to Bob.
Charlie is monitoring the public communication between Alice and Bob; and wants Alice to publicly release a blinded version of $m$; so that he can verify Alice indeed is sending the encrypted version of $m$ to Bob.

The protocol has 2 parts in it; but first let's define the parameters.

$m$ is the message from Alice to Bob
$(e,N)$ is Bob's RSA public key, $(d,N)$ is Bob's private key.

Encryption and Blinding

Charlie creates a random number $1 < r < N$ and announces it publicly.
Alice computes the following values:

$x = m^e \bmod N$ (RSA encrytion)
$x_{blinded} = (m * r)^{e} \bmod N$ (Note that $(m * r)^{e} = m^e * r^e$)

Charlie then, verifies $x_{blinded} = x * r^e$ (this way Charlie ensures that, $x$ indeed contains the encrypted message)

Decryption

Bob decrypts $x$, calculating $m = x^d \bmod N$ (RSA decryption)


$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$

but $s_{i-1} \cdot N = 0 \pmod N$, so

$s_i = s_{i-1} + 1 \pmod N$

which means you can discover the next number to be generated just looking to the current one...


Has the distributed project "Number Fields @ Home" project benefited cryptography in any meaningful way?

TL;DR: The NumberFields@home Project has not benefited cryptography.

Background
Number fields play an important role in cryptography, especially when talking about the RSA cryptosystem.
The security of RSA is based on the presumtion that factoring a large semi-prime (the product of two prime numbers) is very hard to achieve, this problem is known as the integer factorization problem.
Quadratic sieve
The Quadratic sieve is an algorithm for factorization. It's the fastest known algorithm for factoring a number $n$, where $n < 10^{100}$.
Number fields
General number field sieve
The General number field sieve is the fastest known algorithm for factoring a number $n$, where $n > 10^{100}$.
It currently holds the record for factoring the RSA-number RSA-768, meaning it has factored a 768-bit semi-prime. A detailed describtion about how this was achieved can be found in this published paper.
Are 1024-bit numbers considered safe if 768-bit numbers can be factored?
Well... Less so. Factoring a 1024-bit RSA modulus would be about a thousand times harder than a 768-bit. They have achieved factoring this number by a collection of parallel computers and the total time amounted approximately to the equivalent of almost 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.
Quoting the previously mentioned paper from February 18, 2010:

Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within
the next decade by an academic effort such as ours or the one in. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.

But you can rest assured that the current standard (2048-bit RSA modulus) is safe.
NumberFields@home Project
Number Fields @ home has yet to reveal some "breakthrough" for cryptography. You can see a list of there achievements here, so strictly speaking the answer is No.
But it might reveal something someday, even though the purpose of this project is "backwards", since the goal of this project is not to prove anything directly, but rather to gather information that might answer a question we maybe haven't asked yet.
To quote the project:

The project as a whole is basic research, in effect, charting unknown territory. In the future, this may have a bearing on a number of questions.

And quoting directly the impact on cryptography:

Number fields are used in some modern factoring algorithms which are relevant to attacks on RSA. Other researchers have investigated using properties of number fields as the basis of new cryptosystems. It is not clear what number fields will be useful in this research, but the more we know about the general landscape of number fields, the better.


Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)?

The definition of DAE security, as given in Rogaway and Shrimpton's original paper (which both defines the security notion and proves that SIV mode satisfies it), does effectively require that a DAE scheme must protect ciphertext integrity.

Specifically, the definition of DAE security (definition 1 in the paper) says that an encryption scheme is DAE secure if an adversary cannot, with non-negligible advantage, tell whether it is talking to the real encryption and decryption oracle, or to a fake encryption oracle that returns for each distinct query a random bit string of the same length as the real encryption oracle would've returned, and a fake decryption oracle that treats all ciphertexts as invalid, with the limitation that the adversary may not submit strings previously returned by the encryption oracle to the decryption oracle or vice versa.

Crucially, while the definition forbids the adversary from submitting ciphertexts previously returned by the encryption oracle to the decryption oracle (and thereby winning trivially), it does not forbid the adversary from submitting a modified version of a previously obtained valid ciphertext to the decryption oracle.  Thus, if an adversary could modify a valid ciphertext in a way that does not almost certainly render it invalid, they could win the "DAE game" simply by requesting a ciphertext from the encryption oracle, modifying it somehow to obtain another, distinct valid ciphertext, and submitting it to the decryption oracle (which, if the adversary is indeed talking to the real oracles instead of the fake ones, would then successfully decrypt it).

In particular, since the SIV construction only directly verifies plaintext integrity, this implies that, for an SIV-style encryption scheme to be DAE secure according to Rogaway and Shrimpton's definition, the encryption layer must not allow the ciphertext to be modified in a way that leaves the plaintext unchanged.

Fortunately, CTR mode does satisfy this property (as indeed do all length-preserving classical encryption modes, such as OFB, CFB and even CBC with ciphertext stealing).  In particular, a simple counting argument shows that, for any encryption mode where the length of the ciphertext (excluding the IV!) equals the length of the plaintext, no two ciphertexts with the same IV can correspond to the same plaintext.  Thus, for these modes, verifying plaintext integrity is equivalent to verifying ciphertext integrity, assuming that the IV is unchanged.

What remains to be shown is that the adversary also cannot change the synthetic IV (possibly together with the ciphertext) in SIV mode in a way that would not be detected.

Indeed, for plain CTR mode, this would be trivial: given two CTR mode encrypted messages $m_1 = (iv_1, c_1)$ and $m_2 = (iv_2, c_2)$ of the same length, and the corresponding plaintexts $p_1$ and $p_2$, one can construct a new message $m' = (iv_1, c_1 \oplus p_1 \oplus p_2) \notin \{m_1, m_2\}$ that also decrypts to $p_2$.

However, in SIV mode, the IV also serves as the authentication tag for the plaintext.  Thus, in effect, it is not feasible for an adversary to find two plaintexts that would be valid for the same IV, and thus any modification attempts like the one described above will be detected.

Furthermore, the SIV construction requires that the (keyed) function used to derive the synthetic IV must be a PRF.  This is a significantly stronger requirement than merely requiring it to be a forgery-resistant MAC (or even a privacy-preserving one), and essentially requires that an adversary must not be able to find any valid IV / plaintext pairs other than those returned by the encryption oracle.  Thus, for any IVs other than those returned by the oracle, the adversary cannot produce any valid message; and for the IVs that the oracle does return, the adversary only has the single valid plaintext, and thus, due to the length-preserving encryption, only one valid ciphertext.

In short, the key properties that make the Encrypt-and-MAC construction in SIV mode provably DAE secure are that:

the encryption layer is length-preserving (and thus, for each IV, bijective),
the encryption layer IV also serves as the plaintext authentication tag, and
the function used to derive the IV from the plaintext is a PRF.

Ps. For further reading, you may also be interested in the following paper:

Namprempre, Rogaway and Shrimpton. "Reconsidering Generic Composition". Cryptology ePrint Archive, Report 2014/206, 2014.


Toy public/private key example open to frequency analysis?

The site also misrepresents RSA encryption. If you are using textbook RSA (i.e. this scheme, with no padding), you don't independently encrypt each letter. Rather, you take the entire message, treat it as a number, and encrypt that.

This doesn't work if your primes are 3 and 11, but if they're each, say, 8 bytes long, then you could encrypt a 16-byte message using textbook RSA by treating the whole message as a single number. The only time you run the encryption operation multiple times on different parts of the message is if the message is longer than the RSA modulus, in which case you need a chaining mode.

RSA has no real chaining modes (no one's bothered coming up with one), but a real block is fairly big anyway. The site broke the message into letters and encrypted each separately (which is the horrible no-good ECB mode) to make the math easier, but that's not even how textbook RSA is used.

There are all sorts of attacks on textbook RSA; frequency analysis isn't really one of them.


Choice of padding scheme to prevent CBC padding oracle attacks?

Padding oracle attacks are not the padding scheme's fault! They are not fixed by changing the padding! They are fixed by not leaking partial information about the result of decryption, or (preferably) by just using CCA encryption.

Any time you provide this to an adversary:

* Accept arbitrary c
* Decrypt m = Dec(c)
* Reveal formatcheck(m)

... if it's only a CPA-secure encryption scheme, you undermine all security of encryption. The specifics of the format check don't much matter. Some padding schemes (more generally, "format checks") can make a plaintext recovery attack more or less direct, but all will undermine overall security to some extent.


What does encryption with RSA public key provide?

Properly done encryption with the RSA public key of the server provides confidentiality of the request, but not integrity or proof of origin (anyone can forge a request with any desired content).

There must be some secret on the sender's side to prove integrity. That can be an RSA private key used for RSA signature (with sender public keys known to the server either by transmission over a channel with integrity, or by way of a digital certificate). Other signature schemes also work (DSA, ECDSA..).

Symmetric crypto also works for integrity, if it is acceptable that the server holds the client's secrets (or a master key allowing the server to re-compute the  secrets of all clients).

Symmetric crypto can provide both integrity and confidentiality (e.g. Salsa20-Poly1305 per RFC 7539), but asymmetric encryption has a superiority: the confidentiality that it offers does not depend on the client's ability to keep a key secret on the long run; only integrity does.


How long would it take all of the supercomputers or cloud computing on Earth to bruteforce a significantly long password?

A salt is supposed to be publicly available, for instance it needs to be stored in a DB next to the password hash. In that case the time it takes to recover the password is just a brute force or dictionary for the password. If the salt is static then rainbow tables may be used as well for any attack. Now if the password has an entropy of 256 bits then this is obviously not a problem. Actual passwords however only have about 42 bits of entropy on average, and this is why bcrypt is often needed to provide some additional security.
It is of course also possible to use a 256 bit pepper, which is a salt value that is kept secret. In that case "cracking" the hash will require both the password and the pepper. We cannot do that even with quantum computers because the energy requirements would be too high (cracking > 128 bit security against classical computers or > 256 bit against quantum computers is completely infeasible and forever will be).


Would a "Triple AES" (in the sense of how Triple Des works) serve for a dramatic increase in safety?

It really depends on what sort of break AES would suffer. The primary issue with DES was that it's key length was too small (56-bits). Multiple encryption can help here because it increases the effective key length of the whole operation. The meet-in-the-middle attack on DES takes about 2^112 operations, which is infeasible to brute force anytime soon.

AES doesn't have an issue with keysize, so multiple encryption won't really help you that much in that sense. It really depends on what sort of attacks emerge on AES so it's hard to tell if multiple encryption will be better. It might be more secure, but it won't be a "huge" improvement and it's hard to judge.


Alice answering Bob without knowing the question

You can use Oblivious transfer protocol for the answers: https://en.wikipedia.org/wiki/Oblivious_transfer

Here is an example with only 2 answers ($m0$ and $m1$) and uses RSA ($e,d,N$) :

In your case Alice would have to send $x_0 \ldots x_9$ and Bob would have to pick $b \in \{0,\ldots,9\}$ where $b$ is the number of his question. The operation $m + k$ can be considered as a symmetric encryption of $m$ with the key $k$.


Do I need to use null bytes and \x80 in hash length extension attack?

But is it necessary to use these bytes?

Yes, it is, at least for most messages that you'll see in practice.  MD5 works by taking the message, and applying a fixed padding to it. This fixed padding involves, for messages which are a number of bytes (as opposed to, say, a message of 119 bits) an 0x80 byte, and for not huge messages, 0x00 bytes (in the length field if nowhere else).  Then, it runs an iterated compression function over the padded message, and the end result is the MD5 hash.

What the length extension attack does is artificially appends that exact padding pattern to the message; so when the MD5 processes that message, it performs the exact same operation, and so comes up with an intermediate state that is exactly what the MD5 hash output is (which we know).  After that, we can append anything else we want (and we can predict how MD5 will handle that, because we now know the MD5 state).

For this to work, we have to do precisely the same padding to the message that MD5 does; because it uses an 0x80 and some 0x00 bytes (for any reasonable message), you do too.


Difference left-or-right CPA security, IND-CPA security

As you are giving your adversary an access to an encryption oracle, I suppose that you implicitly consider the security of a symmetric encryption scheme. In the asymmetric setting, the definitions are slightly different. Here is my understanding of it (disclaimer: I'm by no mean a specialist on security for symmetric encryption scheme).

IND-CPA is the standard name for asymmetric semantic security. The adversary chooses two messages, the challenger encrypts one of them at random and the adversary tries to guess which one was encrypted. An important difference with the symmetric setting is that one does not have to define precisely the kind of oracle access given to the adversary, as he can just encrypt whatever he wants by himself (he is given the public key of the scheme).

Hence, when it comes to symmetric security, one has to be more precise as the oracle access to an encryption oracle is necessary (the adversary cannot encrypt by himself), and can come in different flavors.

So, to me, if one refers to IND-CPA security for a symmetric scheme, it's essentially a shorthand for "one of the security definitions in the CPA model" which are "essentially equivalent". More precisely, here are the four security definitions considered in this seminal paper:

-Left-or-Right CPA security. The oracle always encrypts the left ciphertext or he always encrypts the right ciphertext; you try to guess whether you see a left oracle or a right oracle.

-Real-or-Random CPA security. The oracle always encrypts the message you sent, or always encrypt a uniformly random message (independently of your message). You try to guess whether it's a real oracle or a random oracle.

-Find-Then-Guess CPA security. That one is the closest to the IND-CPA security notion in the asymmetric case: you give two plaintexts to the oracle, who encrypts one of them chosen at random, you have to guess which one.

-Semantic security. Given an encryption of some x drawn according to a distribution D you've chosen, find "some information" about x, id est, some f(x) for a function f of your choice.

Now, to answer your question, here are the security comparisons:

-Left-or-Right CPA security and Real-or-Random CPA security are equivalent (there is a security preserving reduction in both direction)

-Semantic security and Find-Then-Guess CPA security are equivalent

-There is a security preserving reduction from Left-or-Right CPA security to Find-Then-Guess CPA security. This does not hold in the other direction. This means that if an adversary breaks one of the two last security properties, he must also break the two first, but the convert is not true.

EDIT: if by IND-CPA, you mean the security notion I defined with the name Find-then-Guess CPA, then as stated above, if one can break IND-CPA, one can break LOR-CPA, but the converse is not true. Hence, LoR-CPA security is a stronger security notion than IND-CPA (and the proof for this statement is in this paper) Doesn't that answer your question?

For your last question: if IND-CPA is indeed find-then-guess CPA, then the difference is the following. In LOR, the oracle picks a bit once and always answer with an encryption of the plaintext indexed by this bit, for all the encryption requests. In IND-CPA, each time you submit a pair of plaintext to the oracle, the oracle picks a random bit and encrypts the corresponding plaintext.


How are "string-messages" converted to "number-messages"?

Cryptographic schemes handle byte strings. To convert a string to a byte string, you need some encoding like ASCII (which can't handle every character) or UTF-8 (which can handle the entire Unicode).

Some specific schemes, like RSA, do need to interpret the byte string as a number. This process is defined in the scheme specification (e.g. for RSA, the PKCS#1 standard - see the OS2IP conversion function). In RSA, the byte string is read as a big endian number in base 256. For example, the byte string 0x01 0x02 is interpreted as the number 258 (256 * 1 + 2).


What is the probability of attacking SHA1 used in RSA signature with small exponent?

This is not an answer; rather, I attempt to improve the method outlined in the question.

Problem statement (slightly simplified): it is given an RSA public key $(N,e)$ with $2^{n-1}<N<2^n$, $n=2048$, $e=41$, a hash function $H=\operatorname{SHA-1}$ with output of $w=160$ bits. It is asked an $(m,s)$ with $0\le s<N$ and $H(m)=(s^e\bmod N)\bmod2^w$.

Note: for simplicity, I ignore the six given (message, signature) pairs and that the $(m,s)$ to exhibit must not be among them. These $(m_i,s_i)$ are such that $0\le s_i<N$ and $(s_i^e\bmod N)=H(m_i)+c$ with known $c=2^{n-15}-2^{8+v+w}+2^w b$, $v=120$, $2^{v-8}\le b<2^v$, $b=\mathtt{0x3021300906052b0e03021a05000414}$ (that's by definition of EMSA-PKCS1-v1_5).

As noted in the question, for any given $m$ with $H(m)$ odd, if there exists an odd $s$ such that $(m,s)$ is a solution to our problem and $0\le s<\Big\lceil\sqrt[e]N\Big\rceil$, then we can efficiently find that $s$ by computing $h=H(m)$ and solving for $w$-bit $s$ the equation $s^e\equiv h\bmod 2^w$; we keep $s$ as solution if $s<\Big\lceil\sqrt[e]N\Big\rceil$.

If we try this for a random $m$, each attempt costs an average of two hashes to find $H(m)$ odd, finding one solution to the equation $s^e\equiv h\bmod 2^w$, and succeeds with probability about $\epsilon=\sqrt[e]N/2^{w+1}\approx2^{(n-1/2)/e-1-w}$; that's slightly under $2^{-111}$ and as is, this strategy is doomed.

Notice that for any given $m$, if there exists $r\ge0$ with $r+H(m)$ odd and odd $s$ such that $(m,s)$ is a solution to our problem and $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s<\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$, then we can find that $s$ by computing $h=H(m)$, and solving for $r$ of appropriate parity and $w$-bit $s$ the equation $s^e\equiv(h+r N)\bmod 2^w$; we keep $s$ as solution if $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s<\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$.

If we just enumerate small incremental $r$ of the appropriate parity, compute $h'=h+r N\bmod 2^w$, and solve for $w$-bit $s$ the equation $s^e\equiv h'\bmod 2^w$, then for each $r$ we have probability about $\epsilon_r=\left(\sqrt[e]{(r+1)N}-\sqrt[e]{r N}\right)/2^{w+1}$ that $s$  turns out to be in the correct range; that is, $\epsilon_r=\begin{cases}
\epsilon=\sqrt[e]N/2^{w+1}&\text{ if }r=0\\\left(\sqrt[e]{1+1/r}-1\right)\;\epsilon&\text{ if }r>0\end{cases}$
This is an improvement if the cost of solving $s^e\equiv h'\bmod 2^w$ is much lower that the cost of a hash (or if our messages $m$ are heavily constrained). In particular, if $h=H(m)$ turns out to be even, we formerly abandoned that $m$, and now have probability about $\epsilon_1\approx\epsilon/59$ that the solution $s$ to $s^e\equiv(h+N)\bmod 2^w$ is acceptable.

Also, when solving $s^e\equiv(h+r N)\bmod 2^w$, if we compute $s$ bit by bit starting from the low-order bits, we can abandon as soon as we have enough bits that it is certain that $s$ is not in the appropriate range.

Perhaps a simultaneous search of $(r,s)$ is feasible; I'll be thinking about it. As the saying (attributed to the NSA) goes: attacks only get better; they never get worse.


Why can't different messages result in the same ciphertext when encrypted with RSA?

The property that you are talking about is the injectivity. I think this link will maybe help you.


Is it possible to combine digital signature to provide message addition?

No, in textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$, there is no method to deduce $\operatorname{Sig}(15)$ from $\operatorname{Sig}(5)$ and $\operatorname{Sig}(10)$.

It is possible to deduce $\operatorname{Sig}(50)$, by using the general fact that in textbook RSA signature, if $x$ and $y$ are positive integers (with $xy$ below the limit for messages that can be signed, if any), then $\operatorname{Sig}(xy)\;=\;\operatorname{Sig}(x)\operatorname{Sig}(y)\bmod N$. But notice that being able to obtain an admissible signature for a message from the signature of other messages is considered a break of a signature scheme. That's why textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$ is not a secure signature scheme (rather, it is a building block towards one).

Further, if we have a signature scheme such that $\operatorname{Sig}(x+y)$ can be deduced from $\operatorname{Sig}(x)$ and $\operatorname{Sig}(y)$, then the signature of any message $x>0$ can be deduced from $\operatorname{Sig}(1)$ with $O(\log(x))$ deductions. That's why the literature tends to consider such additively homomorphic signature schemes only to repel them.

If we really want an additively homomorphic signature scheme, we can define one related to RSA, as $\operatorname{Sig'}(x)=\operatorname{Sig}(g^x\bmod N)=(g^x\bmod N)^d\bmod N=(g^d\bmod N)^x\bmod N$ for some fixed public $g$ generator of the groups $\mathbb Z_p^*$ and $\mathbb Z_q^*$ (it is easier and best that $(p-1)/2$ and $(q-1)/2$ are primes). In order to verify the alleged signature $s$ of $x$ per this system, it is checked that $s$ is the textbook RSA signature for $g^x\bmod N$, that is $0\le s<N$ and $s^e\bmod N\,=\,g^x\bmod N$. For all non-zero $a$ and $b$ and messages $x$ and $y$ it holds that $\operatorname{Sig'}(ax+by)\;=\;\operatorname{Sig'}(x)^a\operatorname{Sig'}(y)^b\bmod N$. This is comes at the price of extreme insecurity: revealing the signature of $x$ and $y$ allows the efficient computation of the signature of any multiple of $\gcd(x,y)$.


Difference on montgomery curve equation between EFD and RFC7748

This is not a bug: it arises from different choice of sign in the definition of a24 := (a ± 2)/4; the RFC uses - while the EFD uses +.

RFC, following the Curve25519 paper:

  The constant a24 is (486662 - 2) / 4 = 121665 for curve25519/X25519 and (156326 - 2) / 4 = 39081 for curve448/X448.

EFD, following Montgomery's paper (paywall-free):

  Assumptions: 4*a24=a+2.

This apparent discrepancy was raised by Paul Lambert on the CFRG mailing list during discussion on the draft.  It doesn't really matter which one you choose, as long as you're consistent about it!


I'm not sure if I get your question correctly. Do you like to use a 256 bit curve to generate a (secret) key of this size and later drop 192 bits? If this is the case your 64 bits will be useless because you secret key will not have any relation with the public. Furthermore, in a magic case that this works, your field operations will continue living in a 256 finite field.

If you like to use a 64 bits EC cryptosystem, first thing you need is to stablish the "setup": a tuple that 'configures' this set up. You may like to check the IEEE P1363 for details, but to have a cryptographically good curve (ignoring the fact that 64 bit is very few). As an example for a finite field:

Generate $p$: random big prime of your 64 bits.
Generate $a$ and $b$: in $\mathbb{F}_{p}$
Check non zero discriminant: $\Delta\neq 0$
Calculate the cardinal $|E(\mathbb{F}_p)|$
Check this cardinal is in the hasse interval
Check this cardinal factorises in $n$ and $h$ where $h<<<n$ and $h\in[1,2,4]$

If steps 3, 5 and 6 fails, go back to step 2 or even 1.

At this point you have a cryptographically good curve, then you need the cyclic subgroup where the ECDLP will protect your secrets.

Generate a random $x\in_R \mathbb{F}_p$ until you find a valid point in your curve. (for a valid $x$ there will be two $y$, select at random).
Check $[n]G=\mathcal{O}_E$

Same than before, if you random point doesn't pass check 2, repeat. But the probability to find a good one is bigger as your cofactor $h$ is smaller.

As you can see, this process is not light and it becomes heavier and heavier (exponentially) when you increase your 64 bits.


Simple application of verifiable random function?

Sharon Goldberg's research group at Boston University has a web site on VRFs with research references and applications, including key transparency in CONIKS, authenticated enumeration-resistant denial of existence in DNSSEC with NSEC5, and the Byzantine agreement protocol Algorand.

Here's a quick history of how negative answers work in DNS and DNSSEC.  The things to watch out for are:

Forgery of A records, so a MITM can direct legitimate users to evil hosts.
Forgery of negative answers, so a MITM can cheaply deny service to legitimate users without getting out the wirecutters and digging a trench by their house.
Consequences of breaking into a live nameserver but not an operator's airgapped laptop.
Zone enumeration: what is the computational and network cost of enumerating all names in a zone?

The DNS can be used for many purposes, and you might want to prevent someone from enumerating all hosts on your network, or all users' if each user gets a unique hostname for their mailbox, or what-have-you.  (Debating the merits of zone enumeration or its prevention is left as an exercise for a pyromaniac on an IETF mailing list.)

Unauthenticated version (NXDOMAIN):

  CLIENT: Can you give me the A record for stackexchange.com?

  MITM: stackexchange.com does not exist.

  CLIENT: Thanks!

  SERVER: stackexchange.com is at 1.2.3.4.

  CLIENT: What?  I already had an answer which I acted on.  Go away!

There's no way for the client to distinguish an answer by the legitimate nameserver from an answer by a malicious MITM—positive or negative.

This fails to thwart forgery of positive (1) and negative (2) answers, and if an attacker breaks into a live nameserver (3) then the legitimate operator can't recover until the longest TTL period after they regain control of the live nameserver or delegation.  But zone enumeration (4) costs one network query per guess.

Hypothetical online signed version:

  CLIENT: Can you give me the A record for example.com?

  MITM: example.com is CNAME for malicious.badguys which is at 4.3.2.1.

  CLIENT: What?  That doesn't have a valid signature.  Go away!

  SERVER: example.com does not exist.  Signed, --Server.

  CLIENT: Thanks.  Can you give me the A record for example1.com?

  SERVER: example1.com does not exist.  Signed, --Server

  ...

  CLIENT: Thanks.  Can you give me the A record for example11237.com?

  SERVER: I'm tired and I'm out of CPU to answer legitimate queries because signing takes too much effort.

  ATTACKER: I broke into the live server because it was running an unpatched version of BIND 8 and now I can forge records with wild abandon!  Haha!

  OPERATOR: Damnit!  I knew we should have chosen a protocol with an offline signing key.

The computational cost of signing every negative query seemed prohibitive at the time DNSSEC design began.  The world has since changed, so that doesn't matter as much now.

This thwarts forgery of positive (1) and negative (2) answers, though if an attacker breaks into a live nameserver (3), which necessarily has a signing key, then it's much the same as the unauthenticated story. Zone enumeration (4) still costs one network query per guess.

Can we do signing offline instead?

Offline signed version (NSEC):

  CLIENT: Can you give me the A record for example.com?

  SERVER: There are no domains between exampla.com and examplo.com.  Signed, --Server

  CLIENT: Can you give me the A record for examplo1.com?

  SERVER: There are no domains between examplo.com and exemption.com.  Signed, --Server

  CLIENT: Can you give me the A record for exemption1.com?

  SERVER: There are no domains between exemption.com and exuberate.com.  Signed, --Server

  ...

  CLIENT: Aha!  I have enumerated all the domains in the com zone!

This still thwarts forgery of positive (1) and negative (2) answers (as will all subsequent methods), and the signing key can be offline so the worst an attacker can do by breaking into the live nameserver (3) is deny service.  But now zone enumeration (4) is amazingly cheap: it costs one network query per name in the zone, and negligible computation.

With the original NXDOMAIN system, the client must test each guess with a query to the server.  With NSEC, the client can quickly skip large ranges of the space of names because the server says which ranges to skip.

Offline hashed signed version (NSEC3):

Here $H$ is a public hash function, such as SHA-256 iterated 1000 times.

  CLIENT: Can you give me the A record for example.com?

  SERVER: There are no domains with hashes between H(foo.com) and H(bar.com).  Signed, --Server

  CLIENT (after some work to find bar.com from H(bar.com)): Can you give me the A record for ejemplo.com?

  SERVER: There are no domains with hashes between H(fnord.com) and H(fjord.com).  Signed, --Server

  ...

  CLIENT: Aha!  I have enumerated all the domains in the com zone!

Live nameservers still need not have signing keys.  Zone enumeration costs more computation per guess now, but it still costs only one network query per name in the zone.  Since the space of domain name labels is relatively sparse, it is not hard to guess them; there's even a prepackaged tool to automate the process called nsec3walker.

This is the point at which standard DNSSEC as of today stopped.  CloudFlare took a middle ground between online signing and NSEC3 called ‘NSEC3 white lies’, eating the server's computational cost of signing each negative answer afresh and the cost of live nameserver compromise by storing the signing key online and answering ‘there are no domains with hashes between SHA256(query.com) and SHA256(query.com) + 1’.  (NSEC3 white lies is what motivated CloudFlare to push for the deployment of elliptic-curve cryptography in DNSSEC, since its signing performance beats the pants off RSA's at the same security level.)

But there's another option with VRFs:

Offline VRF'd signed version (NSEC5):

Here H is a secret hash function, namely a VRF, with a corresponding public key that can verify proofs of the output of H.

  CLIENT: Can you give me the A record for example.com?

  SERVER: There are no domains with hashes between H(bar.com) and H(foo.com).  Signed, --Server (NSEC5)

  SERVER: P.S.  ‘H(example.com)’ is H(example.com), and here's a proof of the fact.  (NSEC5PROOF)

  CLIENT: Blast!  I'm thwarted.

Forgery is prevented as usual.  The cost of zone enumeration is back to one network query per guess, because the client cannot evaluate H(guess.com) to try a guess.  And if an attacker compromises a live nameserver, although there is secret key material for evaluating H(query.com) when a client asks for a nonexistent query.com, that's useful only for evaluating the NSEC5PROOF postscript.  The signing key for the NSEC5 record denying the existence of any domains between H(bar.com) and H(foo.com) can remain offline.


Can I compute “SHA256(secret||data)” when having “SHA256(secret)” and “data”?

As @yyyyyy already commented: if you are able to successfully apply a length extension attack, you would be able to compute

$$\operatorname{SHA256}(\mathit{secret}\Vert\mathit{padding}\Vert\mathit{data})$$

But computing $\operatorname{SHA256}(\mathit{secret}\Vert\mathit{data})$ for freely chosen $\mathit{data}$ without the $\mathit{padding}$ in between is assumed to be “hard”; meaning that you’ll end up having to brute-force your way towards a result.

Also see “understanding a length extension attack” for a more indeep understanding of things.


Also is it known how to generate $g^{x^{2^i}} \bmod p$ at every $i \in \mathbb{N}$ in $O((\log ip)^c)$ time at a fixed $c>0$?

No, it is not known; that would immediately imply a polynomial-time method to solve the computational Diffie-Hellman problem, and that's better than what's currently known.

This problem is: given $p, g, g^x \bmod p, g^y \bmod p$, compute $g^{xy} \bmod p$.

Given such an Oracle, here is how we would solve it (and from here on in, everything is done $\bmod p$): first, we can compute $g^x \cdot g^y = g^{x + y}$

Then, we ask our Oracle to compute $g^{x^2}$, $g^{y^2}$, $g^{(x+y)^2}$ in $O((\log p)^c)$ time.

We then compute $g^{(x+y)^2} \cdot ( g^{x^2} \cdot g^{y^2} )^{-1} = g^{2xy}$

Then, we take the modular squareroot of $g^{2xy}$, that gives us $g^{xy}$

Every step above takes polynomial time.


Why is appending the key to a mesage and then hashing that insecure if the hash isn't weakly collision resistant?

It's a question about how actual hash functions work. So in the scheme where MAC=H(m||k) in practical terms that's equivalent to doing M=H(m) and then, with the resulting state of the hash function do H(k) starting with the state resulting of doing H(M), so you can see that's possible to find a collision, a m' such that H(m')=H(m), then H(m'|k)=H(m|k) with a cost n/2 bits. HMAC construction reduces substantially (according to wikipedia) the chances of finding such a collision, in fact a collision H(m')=H(m) is useless, so the weakness in this sense of the used hash function has no use.

Note: If $M_i$ are hash function's input blocks and $S_i$ are successive states most hash functions do just $S_i=F(S_{i-1},M_i)$, and the hash result is the last state, making length extension and collision attacks possible.

PD: Let me apologize if the answer is not clear enough. The answer is yes, HMAC can improve a collision weakly hash where H(m|k) does not.


The system proposed has no practical interest.

If $r$ is public, then it is easy to check a guess $\overline m$ of $m$ (compute $\overline m'=\overline m+r$, feed it to the RSA function, and compare the result to the actual ciphertext; it matches when $m=\overline m$). That possibility is a disaster in practice; e.g. if $m$ is a name on the class roll, or a credit card number, poof goes confidentiality.
If $r$ is secret and chosen randomly in $[0,n)$ for each message, then the system is safe and we can use $m'$ as the ciphertext, without needing RSA on top of that. That's in effect a One Time Pad.


formulas for adding points on curve25519

Classically, if you want to add two points $P = (x_2,y_2)$ and $Q = (x_3, y_3)$, you need all coordinates to compute $R = P+Q = (x_5, y_5)$.

The geometric relation between those points are that $P$, $Q$ and $-R = (x_5, -y_5)$ are aligned. Now, suppose you know only the $x$-coordinates of $P$ and $Q$, meaning you cannot differentiate between $P$ and $-P$ on one hand, and $Q$ and $-Q$ on the other hand. So there are four possible outputs: $P + Q$, $P - Q$, $-P + Q$ and $-P - Q$. We can remark here that $P + Q$ and $-P -Q$ share the same $x$-coordinate $x_5$ according to the previous notation, and $P - Q$ and $- P + Q$ the same $x$-coordinate. Let's call it $x_5'$.

This means by knowning only $x_2$ and $x_3$ we can get the two possible resulting $x$-coordinates of $P+Q$ or $P-Q$. So if you know the $x$-coordinate of $P - Q$, you can compute $P + Q$. That's what happens in the formula you quoted: the coordinates $X_1$ and $Z_1$ correspond to the point $P - Q$.

This is useful for the Montgomery scalar multiplication. It takes on input a point $P$ and compute $nP$ where $n$ is a scalar. At each step of the algorithm, the addition always involve two points $R_0$ and $R_1$ such that $R_1 - R_0 = P$ is a constant. So, since this is known, the addition can always be performed using only the $x$-coordinate (well, $XZ$ projective coordinates).

This can work for other model of curves, but in the case of Montgomery curves, it gives pretty fast formulas for addition and doubling!


Ed25519 choice of private key implementation

To perform an Ed25519 signature operation, you need to know three values, denoted by $\sf RH$, $a$ and $A$ in the diagram.  Now, as it happens, these values are not independent:

$A$ can be derived from $a$, and
both $\sf RH$ and $a$ can be derived from the seed $k$.

Thus, all you really need to store is the seed $k$; everything else can be derived from it.  Alternatively, it's possible to store $\sf RH$ and $a$ like NaCl does, which saves you the (minor) effort of one SHA-512 hash computation whenever you need to sign something.

There's no particular need to store the public key $A$ as part of the private key, since it can be derived from $a$ and you need to know $a$ anyway to be able to sign.  However, deriving $A$ from $a$ requires an elliptic curve multiplication, which is a reasonably expensive operation compared to the other key generation steps.  Thus, also storing $A$ as part of the private key provides a modest performance gain compared to storing just $k$ or just $\sf RH$ and $a$.


What you need to show is that the output bits are i.i.d. and uniform.

Given there is an output bit, clearly the probability that you output a zero is the same as the probability that you output a one, namely $p(1-p)$ as you indicated. So uniformity is settled.

These bits are also independent since they depend on disjoint subsequences of the input stream, which is itself assumed to be i.i.d, though non uniform.

So all you still need to prove is that bits are output at some nonzero  rate. This rate is $2p(1-p)$ per two input bits and is positive provided $p \in (0,1)$ which is the case of a non degenerate source.


Second challenge in Fiat-Shamir for 5-round schemes

These are equivalent. Given that the first challenge is a deterministic function of the statement and $\alpha_1$, it makes no difference. What is crucial is just to include the statement, and the entire transcript to that point. (Note that anything that is deterministically dependent on other things doesn't have to be included in the transcript.)


I'm not sure if I understand the question correctly, but let's try anyway.

By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete logarithm problem in $\mathbb{Z}_m^*$, say we have $g,h\in\mathbb{Z}_m^*$ such that $h=g^\ell$ for some integer $\ell$.

We note that $\mathbb{Z}_m^*$ is a finite abelian group of order $\varphi(m)$, so by the fundamental theorem of finite abelian groups we have that $\mathbb{Z}_m^*\cong\mathbb{Z}_2\times\mathbb{Z}_p\times G(q^5)\times G(r^2)$, where $G(q^5)$ and $G(r^2)$ are groups of order $q^5$ and $r^2$ respectively (they are Sylow subgroups). Pohlig-Hellman implicitly makes use of this fact. That is, instead of finding $\ell\pmod{\varphi(m)}$ directly, we map $g$ and $h$ to elements of $\mathbb{Z}_2$, $\mathbb{Z}_p$, $G(q^5)$ and $G(r^2)$ respectively. We then solve the DL's in those groups, finding $\ell\pmod{2}$, $\ell\pmod{p}$, $\ell\pmod{q^5}$ and $\ell\pmod{r^2}$. Finally we recombine them using the Chinese Remainder Theorem.

For example, since $g$ and $h$ have order dividing $\varphi(m)$, we have $g^{2pq^5r^2}\equiv h^{2pq^5r^2}\equiv 1\pmod{m}$. That means that $(g^{pq^5r^2})^2\equiv (h^{pq^5r^2})^2\equiv 1\pmod{m}$, i.e. they are both elements of order 2. In other words, we can think of them as lying in $\mathbb{Z}_2$. Thus, we have that $h^{pq^5r^2}=(g^{pq^5r^2})^{\ell\pmod{2}}$. This is an easy DL and we solve it to find $\ell\pmod{2}$.

So we have reduced to solving DL's in $\mathbb{Z}_2$, $\mathbb{Z}_p$, $G(q^5)$ and $G(r^2)$. Carefully looking at the Pohlig-Hellman shows that we can actually reduce the DL in $G(q^5)$ to 5 DL's in $\mathbb{Z}_q$. Similarly we reduce the DL in $G(r^2)$ to 2 DL's in $\mathbb{Z}_r$. Hence the remaining problem is solving some DL's in the group $\mathbb{Z}_s$, for $s\in\left\{2,p,q,r\right\}$. That is, a prime order cyclic group.

You may start wondering why I'm going through all of this. The point is that the usefulness of Pohlig-Hellman is precisely this reduction step. Assuming that $p,q,r$ are all small, we can easily solve all DL's in our groups $\mathbb{Z}_s$. However, what if $p,q,r$ are not small? Then we have to solve the DL's in $\mathbb{Z}_s$ some different way, but Pohlig-Hellman does not come with any restrictions. The most straightforward way would perhaps be Baby-Step Giant-Step, but we are free to choose any other method.

Therefore in relation to your actual question, any sieving technique that applies to solving a DL in a prime order group, will also apply here. Although I guess it is most commonly known for factoring, there are definitely applications of the NFS to these groups, see e.g. https://cr.yp.to/bib/2003/joux.pdf.


Traditionally, one would just use an implementation of DTLS and some form of challenge-response player authentication.


Have crypto side-channel attacks happened in the wild?

None that recover the key?

Osvik, Shamir, Tromer, 2006: Recover AES-256 secret key of
Linux’s dmcrypt in just 65 ms
AlFardan, Paterson, 2013: “Lucky13” recovers plaintext of
CBC-mode encryption in pretty much all TLS implementations
Yarom, Falkner, 2014: Attack against RSA-2048 in GnuPG 1.4.13:
“On average, the attack is able to recover 96.7% of the bits of the
secret key by observing a single signature or decryption round.”
Benger, van de Pol, Smart, Yarom, 2014: “reasonable level of
success in recovering the secret key” for OpenSSL ECDSA using
secp256k1 “with as little as 200 signatures”

Those are all examples of timing attacks that were usable in the wild. Also, they're all timing attacks. Nevermind Spectre, Meltdown, and the plethora of other predictive branching vulnerabilities that followed suit.
There's also the RSA "exponent 3" attack (which I may or may not have exploited myself one or 2 times against web servers' TLS certificates)
(edit: The exponent 3 attack isn't really a side-channel attack but it's so hilarious I couldn't resist.)
In short, most timing attacks can be performed in the wild. There was even an issue with Amazon AWS instances that allowed someone to steal encryption keys from other instances simply by creating an AWS free tier account.
The good news is, usually researchers find them before bad actors and there's time to develop a fix before it gets too crazy. But these attacks are very real and usually crippling; both on paper and in practice.
I might suggest reading this document [PDF] which outlines the nature of such attacks in slightly more detail.


Relationship between exponent and modulus in RSA (as RSA properties as listed in X.509)

The requirement was introduced in IUT Recommendation X.509 (November 1993), informative appendix D.5.2:

  It must be ensured that e > log2(n). If not, then the simple operation of taking the integer eth root of a ciphertext block will disclose the plaintext.

This advice was removed in the 2000 edition of the standard. It was arguably misguided, and at the very least the justification given was very incorrect (even when using RSA for encryption without padding, what's stated in the justification works only for a very small portion of plaintexts, including for $e=3$; it thus does not work at all for random plaintext, or when using RSA with proper padding).

The assignment itself is questionable: we are asked to choose among two incorrect justifications for advice so questionable that it was removed; and it turns out that the few plaintexts allowing the attack in 1 to work also allow to perform precisely what's claimed in 2. The only superiority of argument 1 is that it more clearly describes an attack which is NOT a good reason to use a public exponent larger than some bound.


From the HMAC-RFC 2104, section 3
(B = blocksize, L = hash output length):

  The key for HMAC can be of any length (keys longer than B bytes are
  first hashed using H).  However, less than L bytes is strongly
  discouraged as it would decrease the security strength of the
  function.  Keys longer than L bytes are acceptable but the extra
  length would not significantly increase the function strength. (A
  longer key may be advisable if the randomness of the key is considered
  weak.)

Tldr, unlike you, they don't consider a longer key to be more secure.


Why gcd(r,(p-1)/r) needs to be 1 in benaloh cryptosystem

$gcd(r,(p-1)/r)$ needs to be $1$ in Benaloh cryptosystem that mean that $(r)$ and $(p-1)$ are preliminary among them.


What is the need for Diffie-Hellman key exchange when we have asymmetric encryption?

when the client send something to the server it will be encrypted with the server's public key (so only the server can decrypt it) and vice versa (when server has to send something to the client it will be encrypted with the client's public key)

As I understand it, you are suggesting not to bother using symmetric encryption; instead, have both sides exchange messages using public key encryption.
That would be horribly expensive (that is, slow); symmetric schemes are literally thousands of times faster than asymmetric schemes.
For example, on my test machine (using OpenSSL), it would 0.4 microseconds to encrypt a 64 byte message (size selected because that would fit within a single RSA encryption); in contrast, it took 614 microseconds (that is, 1500 times as long) to RSA decrypt the same amount using 2048 bit RSA.
Performance varies a lot depending on the processor, however this sort of huge performance is typical.

What is the need for Diffie-Hellman key exchange when we have assymmetric key exchange?

Well, one could use assymmetric key exchanges to share symmetric keys, and use those symmetric keys to encrypt the actual messages - that certainly can be done (for example, in some ciphersuites in older TLS versions).  It wasn't great when dealing with server compromise (which is why newer TLS versions abandoned it), but it did work.


Can a book cipher be cracked without key?

First things first, finding the key (book) is not impossible, but just tough. If someone, like Google for example, has scanned millions of books into digital formats then it won't take long for them to figure out which book (simply try decrypting the first sentence only until the key is found, should be feasible for a mainframe).

Also, there is a lack of randomness. As the book you choose might not have random sequences the substitution will not decorrelate anything, which is another drawback. The best way to improve this is by choosing random references for each character by using a random number generator, which is tedious.


RSA engine with inaccessible private keys - susceptible to any attacks?

Would this setup be susceptible to any oracle-kind attack which would allow extraction of the on-chip key $x$?

Not as far as we know.

Any such Oracle attack that could recover the private key would demonstrate that the "RSA problem" and the "factorization problem" are equivalent.  Currently, that is an open question; such an attack would be a noteworthy advance...


In what aspects is the function based on four iterations of SHA-256 compression function weaker than the SHA-512 compression function?

The original question did not have $C$, introduced to address otus's comment. The next section of the present answer was written with that in mind, or equivalently $C_1=C_2$ and the second input of functions removed; we'll get $C$ back in the final section.

Yes, $G_{1024}$ is weaker than $F_{1024}$ from a cryptographic point of view. For example, about $2^{257}$ evaluations of $F_{512}$ have a sizable chance to be enough to find a 512-bit value $B$ such that $G_{1024}(B)$ is the all-zero 512-bit bitstring, when doing so should require an expected $2^{512}$ evaluations of $G_{1024}$, that is about $2^{257}$ times more work.

To form such $B=B_1\mathbin\|B_2$, we use incremental 256-bit $B_1$, compute $x_1=F_{512}(B_1)$, compute $B_2=x_1\oplus B_1$, know without computation that $x_2=x_1$, compute $x_3=F_{512}(x_2\oplus B_1)=F_{512}(B_2)$, until it happens that $x_1=x_3$ or we have exhausted all 256-bit $B_1$. This gives non-negligible odds to find $B_1$ with $x_1=x_3$, in which case $x_2=x_4$, and thus $G_{1024}(B)$ is the all-zero 512-bit bitstring.

Back to the question as it stood in its second major revision, with $C_1$ and $C_2$, presumably distinct in the first round of the 512-bit hash.

In that first round, for random $B_1$ and $B_2$, $x_1\oplus x_3=x_2\oplus x_4$ has odds about $2^{-256}$, and the expected work to find such $B_1$ and $B_2$ is about ${3\over4}2^{258}$ evaluations of $F_{512}$. With such $B_1$ and $B_2$ as first block, in the next round of the 512-bit hash, the round function will have its 512-bit chaining input $C$ such that $C_1=C_2$, and we can carry the previous attack on the second round. If that attack fails, we now can retry by redoing the attack on the first round, with one full try costing on average about ${5\over4}2^{258}$ evaluations of $F_{512}$ . $2^{260}$ evaluations of $F_{512}$ can with good probability exhibit a 2048-bit input such that the 512-bit intermediary hash after two rounds of $G_{1024}$ is all-zero; that's $2^{254}$ times easier than it should.

We can attack the full 512-bit hash obtained from $G_{1024}$ with length-strengthening, and find a 239-octet input hashing to all-zero with an additional $2^{136}$ work factor (because the length-strengthening forces 17 octets in $B_2$ of the second round). This is a break of first-preimage resistance by a factor of $2^{118}$, albeit specialized to the all-zero result.

Sure, that's not devastating, and in particular does not break a 256-bit security claim. But attacks only get better; they never get worse.

The last system can be attacked as follows: chose an arbitrary first block, yielding fresh $C_1$ and $C_2$ for the second block. For each, try to find find $B_2$ yielding $x_2=0$ and ending with the 17-octet length-strengthening prescribed for a 239-octet hash input; if none of the $2^{120}$ such values of $B_2$ is fit, try another first block. If one is found, try to find $B_1$ yielding $x_1=0$; otherwise start over with another first block. That yields a 239-octet string hashing to all-zero per the full 512-bit hash with length-strengthening. The length-strengthening was less taxing than in the previous system, and the attack is a break of first-preimage resistance by a factor of like $2^{252}$ (albeit still specialized to the all-zero result).

Comment: modern crypto does not design its cryptosystems by trial and error until no error is found. We want at least a security argument, if possible a proof under some security model and plausible assumptions.


How to perform Multiplicative Inverse Modulo in IDEA

Well, the multiplicative inverse of $a$ is defined to be that value $b$ for which $a \times b = 1$, where $\times$ is the multiplication operation in the field/ring/group in question.

Because we're talking about the group of multiplication modulo 65537, that means that the problem is, given $a$, find $b$ such that $ab \bmod 65537 = 1$.

Now, the % operator is C doesn't do it.  The classical way is to use the Extended Euclidean algorithm, where the two inputs to the algorithm is $a$ and $65537$; and have it find a solution to the equation $ax + 65537y = GCD(a, 65537) = 1$; the value $x$ is the multiplicative inverse you're looking for.

Of course, since there are only 65536 possible inverses, another possibility is simply have a table of the 65536 possible inverses, and just do a lookup.  In that case, you can use the Extended Euclidean algorithm to build the table.

Oh, and as a reminder; idea interprets the 0000 bit pattern as the value 65536 as far as multiplication is concerned (as the value 0 doesn't have an inverse).


Are the RFC3526 MODP groups Schnorr groups?

Yes, it meets the formal definition of a Schnorr group; however it was constructed somewhat differently.  Normally, when we generate a Schnorr group, we pick a prime $q$, and then search for an $r$ so that $qr+1$ is also prime; with the RFC3526 group, they picked $p$ and $q$ simultaneously.  In addition, when it came to selecting the generator, they did not select the value $h$ and compute $g$ from that.  Instead, they selected $p$ such that $g=2$ generated a prime subgroup.

As for the values you asked about:

$$p = 2^{1536} - 2^{1472} - 1 + 2^{64} * \lfloor 2^{1406} \pi + 741804 \rfloor$$

(and yes, $pi = \pi$ is everyone's favorite transcendental number)

$$q = (p-1)/2$$

$$r = 2$$

$$h = 2^{(p+1)/4} \bmod p$$

We have this rather odd looking $h$ because that makes $h^r \equiv 2$.  Since Schnorr groups had no restriction on what $h$ is (other than $h^r \not\equiv 1$), this satisfies the definition.


Challenges of Fiat-Shamir Transformation of ZK Proof / Sigma Protocol

If the challenge is calculated as $H(\Sigma_1)$ the transform is called the weak Fiat-Shamir (wFS) transform. On the other hand, when the challenge is computed as $H(x\mathbin\Vert \Sigma_1)$ the transform is called the strong Fiath-Shamir (sFS) transform.

In scenarios where the attacker can choose adaptively the statement she would like to prove, the proof system is not secure anymore, ie. it is not a proof-of-knowledge anymore. For instance, this leads to many practical attacks against the Helios voting system. Let's consider the Schnorr identification as an example where the wFS transform is not secure.

In a group $\mathbb{G}$ of order $q$ generated by $G$, it proves knowledge of an exponent $x$ satisfying the equation $X = G^{x}$ for a known $X$. Viewing $(x, X)$ as a signing/verification key pair and including a message in the hash input yields a signature of knowledge. To create a proof, the prover picks a random $a\leftarrow \mathbb{Z}_q$ and computes $A = G^a$. She then hashes $A$ to create a challenge $c=H(A)$. Finally she computes $f=a+cx$;
the proof is the pair $(c, f)$ and the verification procedure consists in checking
the equation $c
= H\Big(\frac{G^f}
{X^c}\Big)$.

However, if the goal of the adversary is to build a valid triple $(X, c, f)$ for any $X$ of her choice, then this protocol is not a proof of knowledge anymore unless the discrete logarithm problem is easy in $\mathbb{G}$. Suppose indeed that there is an extractor $K$ that, by interacting with any prover $P$ that provides a valid triple $(X, c, f)$, extracts $x = \log_G(X)$. This extractor can be used to solve an instance $Y$ of the discrete logarithm problem with respect to $(\mathbb{G}, G)$ as follows: use $Y$ as the proof commitment, compute $c = H(Y )$, choose $f\leftarrow \mathbb{Z}_q$ and set $X = \Big(\frac{G^f}{Y}\Big)^{1/c}
$. Since the proof $(Y, c, f)$ passes the verification procedure for statement $X$, the extractor $K$ should be able to compute $x = \log_G(X)$ by interacting with our prover. We now observe that, by taking the discrete logarithm in base $G$ on both sides of the definition of $X$, we obtain the solution $\log_G(Y ) = f − cx$ to the discrete logarithm challenge.

A nice paper describing the pitfalls of the wFS transform can be found here.

Since this is an instance of the sFS transform, your proposed change yields a secure ZKP, for proof see Section 4. in the above linked paper.

However, I'm not aware of any practical deployment of ZKPs which would use such reduction techniques. Generic ZKPs for NP-complete languages are overkill and inefficient in most application scenarios. In my opinion, those results are mostly considered as theoretical results to show that there exists ZKPs for all NP languages.


How long does it take a quantum computer to brute force AES?

I'm not going to exactly answer your question, because I have no idea. I simply do not know how fast the quantum computer is that NSA is building in secret.

However I could explain why people recommend 256-bit security in the face of quantum computing using some numbers. If you feel that $2^{128}$ is a comfortable security against bruteforcing, remember that a $2^{64}$ security level is $18446744073709551616$ times faster to bruteforce.

That means a ~0.000000000162630 GHz quantum processor bruteforces a 128 bit key faster than a 3GHz regular processor, assuming one lookup per cycle.


XORing a nonce with a ciphertext vs XORing a nonce with plain text and then encrypt

option 2 is insecure. Recall the nonce is public and must be sent with the ciphertext, which means it can be removed from the ciphertext trivially and therefor has no effect at all.
You are effectively doing ECB with some useless extra step and extra communication.


Why does bootstrapping (R)LWE homomorphic encryption produce small noise?

The output of bootstrapping has relatively small noise because it starts from an encryption (of the secret key) that has very small noise, and performs some homomorphic operations on it. These operations increase the noise somewhat, but it starts out so small that the result still doesn’t have much noise.
It doesn’t really matter that the ciphertext being bootstrapped has large noise, because that ciphertext only defines the function we (homomorphically) evaluate, namely, decryption of that fixed ciphertext by the (encrypted) secret key. In other words, the secret key is the input to the function we homomorphically evaluate, and it is encrypted with very small noise, so the result has only moderate noise.


For large prime P, how often is (P-1) evenly divisible by 65537?

If you generate a prime randomly, and then check, it happens with probability $1/65536$.

On the other hand, it is common practice to include the criteria $p \not\equiv 1 \pmod {65537}$ as part of the prime search; if you do that, the probability is 0.


Keyless Signature Infrastructures as a secure Post-Quantum Scheme

I would just like to know on what basis they can say it is PQC without any NP problem reduction.

I believe that the point you're making is assuming that a Quantum Computer could solve any problem in NP that's not actually NP-complete quickly (or, at least, in polynomial time).  That's not known to be true; Quantum Computers would be able to solve some problems (such as factorization) in polynomial time, if $P \ne NP$, there's a whole range of problems in NP that's neither P nor NP-complete.


How does OpenSSL know if a decryption failed?

This code is very near the lines the error mentions for evp_enc.c (there may be some differences between different versions of OpenSSL):

 527                 n=ctx->final[b-1];
 528                 if (n == 0 || n > (int)b)
 529                         {
 530                         EVPerr(EVP_F_EVP_DECRYPTFINAL_EX,EVP_R_BAD_DECRYPT);
 531                         return(0);
 532                         }
 533                 for (i=0; i<n; i++)
 534                         {
 535                         if (ctx->final[--b] != n)
 536                                 {
 537                                 EVPerr(EVP_F_EVP_DECRYPTFINAL_EX,EVP_R_BAD_DECRYPT);
 538                                 return(0);
 539                                 }
 540                         }

This is an implementation of PKCS#7 unpadding (b is the block size, retrieved from the "context").

There is no mention of MAC verification or authentication tag inside this code, so we can safely assume this is only called for ECB/CBC decryption (if you don't provide a mode of operation, OpenSSL defaults to CBC with PKCS#7 padding).

This also means that there is no certainty at all that the decryption was correct if you do not receive an error. For instance, you may get "lucky" and create a valid padding even though the wrong ciphertext was decrypted (or, with the wrong IV or key). And if the ciphertext two blocks before was changed then the error won't be caught either because CBC has limited error propagation.

In other words, if you need integrity / authenticity then you need an authentication tag, for instance using an authenticated mode such as AES-GCM.


Example of a universal one-way hash function that is not collision resistant hash function

One can construct such an example artificially. Denote the key to the hash function by $s$ (and recall that this key is public). Now, let $H$ be any universal one-way hash function, and define $H'_s(s) = H'_s(s+1)$. This requires changing just one point in $H$, and so is easy.
Notice that $H'$ is clearly not collision resistant: given $s$, just output the pair $(s,s+1)$. However, I argue that $H'$ is still a universal one-way hash function (often called target collision-resistant). The reason for this is that the only way that this change to $H$ can help is if the adversary chooses $x=s$ or $x=s+1$ before the key is chosen. However, this can only happen with negligible probability, unless the key space is polynomial in size. However, if the key space is so small, then the hash function cannot be secure anyway (basically, in such a case, you can just get rid of the key).


Why is public-key encryption so much less efficient than secret-key encryption?

There are three efficiency issues to discuss here: CPU, network bandwidth, and functionalities.

The "moral" reason of public key encryption being slower than private key encryption is that it must realize a qualitatively harder feature: to be able to publish the encryption key without revealing the decryption key. This requires heavier mathematics, compared to symmetric encryption which is "just" making a big tangle of bits. Most known asymmetric encryption systems seem to achieve the needed security, but at some relatively heavy computational cost. Note that the McEliece cryptosystem and NTRUEncrypt achieve asymmetric encryption and decryption at high speed (much higher than, say, RSA or El Gamal over elliptic curves). There is no proof that asymmetric encryption must really be harder, computationally-wise, than symmetric encryption, but the contrary would still be mildly surprising.

Another efficiency issue with asymmetric encryption is network bandwidth. This one is an absolute limitation. Public key encryption is public: anybody, including the attacker, can use the public key to encrypt arbitrary messages. This means that if the encryption is deterministic, then the attacker can run an exhaustive search on the encrypted data (i.e. encrypting potential messages until one matches). The data which is encrypted is still "useful data": it has structure, it is subject to such a search. Therefore, an asymmetric encryption scheme must include extra randomness. This, in turn, necessarily implies a data size increase. For instance, with RSA as described by PKCS#1, with a 1024-bit key, you can encrypt a data element only up to 117 bytes, yielding a 128-byte value. Therefore, if you were to encrypt a big file with "only RSA", you would end up with an encrypted message about 9% bigger than the plaintext: that's 900 extra megabytes for a 10 GB message. On the other hand, symmetric encryption only incurs a constant size overhead (say, at most +32 bytes for AES-CBC, including room for the initial value). There are many contexts where network bandwidth is a scarcer resource than CPU.

Finally, there are key exchange algorithms, which are like asymmetric encryption except that you do not get to choose the "message" you send: the sender and receiver do end up with a shared secret, but that value is mostly "randomly selected". Diffie-Hellman is the most well-known key exchange algorithm. To do "asymmetric encryption" with a key exchange algorithm involves using the "shared secret" as key in a symmetric encryption algorithm.


Q: How long shall the RSA key be in order to be secure against practical attacks?

A: Impractically large. This does not imply that RSA is unsafe against practical attacks; only that some of these attacks must be prevented by ways other than increasing the key size.

That's because key size is not a parameter with a major impact on the efficiency of many attacks against RSA, with the exception of factorization of the public modulus. For example, in (Simple) Power Analysis of RSA (without CRT), the secret exponent $d$ is directly recovered from observation of the power trace of one execution of the private-key function, thus any increase in public modulus length making attack impractical also makes usage impractical.

For less severe signal leakage (like in the sound pattern attack linked to in the question), the attack may require a number of executions of the private-key function growing with the key size (all things being equal), perhaps linearly or per some other slow-growing function; but again increasing the key size will make the system impractical before it gets safe.

Q: Is there any new advancement in factorization?

A: Publicly, no experimental progress. The state of the academic art remains close to that when factorizing RSA-768 in late 2009. However there has been claims of breakthrough by the NSA which could be explained by factoring 1024-bit RSA moduli; quoting that Wired article quoting an unnamed former senior intelligence official

  “They made a big breakthrough” (..) “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

One of the few notable theoretical progress that I'm aware of is: Daniel J. Bernstein and Tanja Lange, Batch NFS, in proceedings of SAC 2014, free on ePrint in revised version.

Independently of NSA breakthrough claims, because both technical and theoretical progress has not stopped, it would be prudent to assume that 1024-bit RSA is vulnerable to factorization these days, if even a small fraction of the funding of the NSA is poured into trying that; see this answer.

Q: What is your recommendation?

A: With respect to public modulus size: French authorities recently vetted 2048-bit RSA good enough for civilian use up to year 2030 at least (rather than year 2020 formerly), and ask for 3072-bit RSA afterwards. When there is incentive (like: efficiency, compatibility, availability, or cost) not to use something wider, or/and good reason to fear side-channel or fault attacks attacks (e.g. in a Smart Card), I find 2048-bit a reasonable choice for many systems.

A: With respect to choice of implementation: know precisely what you trust and why, or delegate that to competent parties that you have reasons to trust. That's what Common Criteria security certification aims at. Microsoft RSA Implementation is not something well defined enough that advice can be given about it.


Encrypting h(k) for defeating partition oracle attacks

The partition oracle attack works if the oracle returns information like the tag is correct or not. Without a response, there is no Oracle at all. The information can also be obtained from side-channels, too.
The partition oracle simply speeds up the password attack by grouping the passwords. The passwords are selected from a possible set of password list $\mathcal{D}$ and the corresponding key is generated by a PBKDF. The corresponding keys are grouped under a ciphertext that can be correctly decrypted.  Here one must note that the correctly decrypted ciphertext doesn't need to have some meaningful plaintext at all. The attacker only requires that under the grouped keys, the ciphertext has valid or invalid tag information returned back to them. This attack works since GCM and Poly1305 are non-committing, i.e. it is computationally feasible to find a pair of keys and a ciphertext (with its tag) that decrypts under both keys.
For the update 1

basically $E_k(h(k)\mathbin\|m)$ or $E_k(k\mathbin\|m)$ where $E$ is an AEAD mode like $(x)chacha20poly1305$. The $k$ is derived from a password from a pkdf like argon2/scrypt/etc. At the start it is computed on both ends but then the party decrypting the ciphertext also checks if $h(k)$ (or just $k$) is correctly appended before the message.

If one uses $E_k(h(k)\mathbin\|m)$ or $E_k(k\mathbin\|m)$, then two cases can occur;

The tag is not valid. This means that the oracle must return the $\texttt{tag invalid}$ response. Now, this is the core of the partition oracle attack. They sent the server a ciphertext that has a valid tag for the $k$ passwords. Returning invalid simply eliminates the $k$ passwords from the passible known password list $\mathcal{D}$.
If the communication is one-way, then there is no need to return any tag. But this really depends on the protocol. A usual protocol must respond.

The tag is valid. In this case, we return to your modifications. Now you will respond as the message format not valid. Viola, the partition oracle still get the information that the current tested $k$ password contains the valid password since the tag passed.

Of course, for both cases, there are false negatives for the attacker to eliminate. Those have a low probability to occur.
The main mitigation is using a committing AEAD that is not standardized yet or use HMAC with one key in as Encrypt-Then-HMAC. And remember using a strong password is always recommended.
For the update 2

The first block that also contains $k$ or $h(k)$ would be decrypted before checking the MAC tag (as an exception, unlike the following blocks). This is in order to verify whether the $k$ or $h(k)$ that is encrypted in the message matches the k that we are decrypting with before verifying the MAC tag (in order to not leak information about whether the MAC tag is invalid). If the encrypted k or $h(k)$ does not match the decryption k then the decryption aborts (before any MAC tag is checked at all)

I this case, I don't see any way that partition oracle attack will work. The attacker can still group but the probability of a random text to have the hash of the key is $1/2^{256}$ if SHA-256 is used. Therefore no feasible attack.
The standard online password attack will still work. Therefore the usual advice of having passwords with good strength is still applied.
I did not like the idea of encrypting the key under the same key, though we don't expect a problem with AES or ChaCha20. Someone can correct me if I'm wrong about this.


Homomorphic (encrypted) comparison to an integer

I may have found an answer (welcoming any comment on whether I missed something) which works, given certain size restrictions on the input $x$ and $y$:

Say, party A has Enc(x) and Enc(y):

A flips a coin: b in {-1, 1}
A computes: $Enc(c) = (Enc(y) Enc(-x))^{b*r} Enc(-r') = Enc(b*r*(y-x)-r')$ where (r, r') are a pair of random obfuscating values such that:

$r' < r$
the distribution of the random variable $r(y-x)-r'$ does not reveal anything about $(y-x)$ (see Edit 2 below).
$log_2(n) > log_2(max(x,y)) + log_2(r) + 2$

A sends Enc(c) to the other party B
B sends back Enc(d) = Enc([c > 0])

If b = 1, Enc([y > x]) = Enc(d)
If b = -1, Enc([y > x]) = Enc(-d)Enc(1)

Am I missing an obvious flaw?

Edit: To avoid modulo problems, $c$ should obviously be smaller than n. Which should be guaranteed by enforcing the conditions on $r$, $r'$ listed above.

Also: negative values refer to the upper range of [0, n-1], as detailed in section 2 of this paper.

Edit 2: The main attack vector would be in the possibility to identify a specific distribution of $c' = r(y-x) - r'$, revealing information on $(y-x)$ (and particularly whether $x = y$). I initially blindly assumed (based on this paper) that $c'$ had to follow a uniform distribution, but this actually does not seem to be a direct requirement.

Section 3.3 of this paper notes that, for $x$ and $y$ in domain $\mathcal{D}_a = [l_a,h_a]$, if $r$ is picked in domain $\mathcal{D}_r = [1, (h_a-l_a)^2]$ and $r'$ from $[0, r]$ (both uniform), then the probability of accidentally revealing $a = b$ is $p \approx \frac{\ln h_r}{h_r}$. This is negligible for e.g. $h_r = 64$ ($p < 2^{-58}$), which still can fit the modulo limit, given a typically secure $n$ (e.g. 512 bits).

This can be made even more difficult by choosing a distribution at random to pick $r$ and $r'$ from.

Same paper discusses a (seemingly tighter) bound on $r, r'$ to prevent wraparound (haven't checked it yet, but it would not really affect the above).


According to Wikipedia (with two articles sourced):

Computing the discrete logarithm is the only known method for solving the CDH problem. But there is no proof that it is, in fact, the only method. It is an open problem to determine whether the discrete log assumption is equivalent to the CDH assumption, though in certain special cases this can be shown to be the case.


byte length and offset for k3d3/ed25519 byte[] variables?

Almost every Java .valueOf(byte[] s, int offset, int length) has the same meaning:

s is the array to read from.
offset is the location in the array to start reading from (inclusive).
length is the number of bytes to try and read - "try" because the array may not be long enough to have that many bytes from offset.

Remembering that Java arrays are zero-indexed, .valueOf(z, offset, length) will read from every byte from s[offset] to s[offset+length-1]. However, if offset+length > s.length, then every byte from s[offset] to s[s.length] will be read.

As an example, if we have byte[] s = new byte[] {10, 20, 30, 15, 4}, then:

LargeInteger.valueOf(s, 0, 5) will use all five bytes.
LargeInteger.valueOf(s, 1, 3) will use bytes {20, 30, 15}.
LargeInteger.valueOf(s, 3, 7) will use bytes {15, 4}.

In Ed25519, the length and offset you use will depend on what part of the byte[] you need to access. For example, initially you take a seed k and hash it to get h = H(k), which you then split into a LHS and RHS. You could convert the LHS and RHS independently into LargeIntegers with LargeInteger.valueOf(h, 0, b/8) for the LHS, and LargeInteger.valueOf(h, b/8, b/4-b/8) for the RHS.

So the end answer is, in most cases yes, you will use offset = 0 and length = s.length. And it looks like you can directly replace BigInteger.valueOf() with LargeInteger.valueOf().


Why did TLS 1.3 prohibit PGP authentication?

It seems that PGP certificates have the problem that they can be changed by the user. Furthermore, there were extensions for 1.2 that are incompatible for 1.3 (if they were secure in the first place):

I found this on the TLS mailing list from Ilari Liusvaara:

  Ugh, the situation is way worse than what I thought.

  Basically, all three assume they have full control of certificate
  message, worst of all being OpenPGP, which modifies it in more complex
  ways (it isn't a pure element or list anymore).

  And even with RPK, which appiles least severe modifications, still
  modifies the structure in ways that are not obvious in implications
  w.r.t. TLS 1.3.

  Oh, and turns out I had implemented RPK in TLS 1.2 wrong by assuming
  that it doesn't actually modify the certificate message format. Which
  turned out to be wrong assumption (I fixed this after discovering the
  format changes).

  And then certificate types don't currently work sanely for client
  certs, even if you knew how those map to Certificate message.

  Client_certificate_type and server_certificate type aren't the only
  problematic extensions w.r.t. TLS 1.3. The table of extensions has the
  following too (all marked as allowed, I added short reason I think
  those are problematic):

  client_certificate_url: Replaces certificate message. Hardcodes   SHA-1 (which is now provably broken).
  user_mapping: Has extra handshake message.
  cert_type: All the problems of CCertT and SCertT, combined with   fixing both to be the same.

  With user_mapping, applying similar trick as in status_request is not
  completely trivial because extensions that are answered in client
  Certificate are offered in CertificateRequest. Okay, except that
  extension is not an answer to ClientHello extensions, and the
  extension assumes offer-answer relationship between client and server
  extensions. Might need some special-casing.

  ...

Source: https://www.ietf.org/mail-archive/web/tls/current/msg22576.html

In other messages in the thread they talk about disabling OpenPGP until somebody comes up with an extension in a separate RFC. So it doesn't seem to be malice, just a whole bunch of compatibility reasons. In other words: as it is now it looks very broken - until somebody manages to fix it.


As you specified in the question, the key, nonce, and initial counter value are what is required in addition to the ciphertext and algorithm used.

However, it is best practice to have the initial counter always be 0. Common standards place no specific restrictions on the size of the nonce unless it is used in an authenticated encryption mode, but it is generally 96-bits, leaving 32-bits for the counter. A 32-bit counter allows 64 GiB of data to be encrypted per nonce using a 128-bit block cipher. A 32-bit 0-start counter is also more simple for software implementations. If you expect to send more than 64 GiB in a single message, you will need to reevaluate the counter size.

If you plan on having both the clients encrypt data with the same key, care must be taken so that there is no nonce overlap. 2 ways of doing this are prenegotiating a client to only use even or odd nonces, or having one of the clients use only nonces with the high bit set to 1.


Your math is off.

The key space of "four squares of random letters" is not four times as big as the one provided by one square, but the fourth power of that size.

To see this easier, consider the case of one $2×2$-square (or four ones), where you can still calculate everything by hand.

There are $4! = 24$ possible ways to fill a $2×2$-square. If you have four such squares, independently of each other, each has 24 ways to fill, so you get $24·24·24·24 = (4!)^4 = 331776$ ways to fill the four squares. This is a lot more than $4·(4!) = 96$. As an exercise, try to find more right groups of 4 such squares than 96 to see that this is actually true.

(An easier exercise would be to try this with 4 1×1 squares, though that is a bit less obvious to understand. There is only one $= 1! · 1! · 1! · 1! = 1!^4$ way of filling the four squares, instead of four $= 4 · 1!$ ways.)

A playfair cipher based on a 2×2 square would be trivial to break even by brute force, as the effective key space has a size of 6 (there are 4 equivalent squares each obtained by swapping rows and columns) ... and for each plain text pair, 4 of the six key pairs just act by swapping the plain text "letters" with each other. Also, you would have a plain text alphabet of size 4 (or better 3, so you have one letter left for inserting when you have double letters). You can try to break one by hand.

For our 25 square, this means that when one square gives 25! ways of filling it, four squares give $25!^4 \approx 5.7887 · 10^{100}$ different ways of filling them. That is your key space for the four-square cipher.

For the 8×8-square, you have $64!$ ways of filling them. But this is not $1.551⋅10^{64}$ (you can't simply convert factorials to powers this way), it is around $1.269·10^{89}$.

Four squares of that caliber give more than the google calculator can handle, i.e. $64!^4 = 2.592 · 10^{356}$.

To use this cipher, you don't need a computer at all (other maybe for generating your random squares), much less a super computer.

The strength of such a cipher is nevertheless much lower than a modern cipher with a similar (or even much lower) key space size would offer. Don't use such a cipher in real live.


what are the uses of tweaks in block ciphers?

There are a couple of related concepts here: Tweakable blockciphers and format-preserving encryption (FPE). It turns out that tweakable blockciphers provide a very natural way of obtaining FPE, but they have other uses as well.

As the blog discusses, sometimes we want, say, encrypted credit card numbers to themselves look like credit card numbers. That is, we want encryption to be an invertible function that takes a 16-digit number and spits out a 16-digit number, and this function should essentially look random to anyone who doesn't know the secret key. In mathematical terms, we want encryption to be a pseudorandom permutation on the set of 16-digit numbers.

But sometimes this isn't enough. For various reasons, it's often the case that only part of your credit card number gets encrypted, while the rest (e.g., the BIN and the last four digits) gets stored in plaintext. This creates a problem: what if two cards share the same 8 encrypted digits? Then if one card is known, the other can be recovered by an attacer. Or worse, what if an attacker has an opportunity to build a dictionary mapping 8-digit plaintexts to 8-digit ciphertexts?

This is where tweaking comes in. Tweaking effectively gives us access to a lot of completely independent pseudorandom permutations --- one for each possible tweak value. So if we encrypt the 8 secret digits using the BIN as the tweak, then the attacks above are no longer a concern. From an attacker's perspective, the ciphertext Encrypt(BIN-1, 01234567) will appear independent of Encrypt(BIN-2, 01234567). This remains true even if BIN-1 is very similar to BIN-2, and even if the attacker knows both BIN-1 and BIN-2. And we don't need to restrict ourselves to BINs -- any cleartext data that can be encoded into a tweak may be used in this fashion.

As I mentioned earlier, FPE is just one use of tweakable blockciphers. Because tweakable blockciphers are so much more powerful than (regular) blockciphers, they are a very nice building block to use when designing other cryptographic algorithms (such as OCB).


How can I decrypt 8 times repeated 128-bit AES key encrypted by 1024-bit RSA?

There is no proper padding and the message $m$ can be recovered easily if $e$ is small.

First, we can rewrite $(m\mathbin\| m\mathbin\|\ldots\mathbin\|m)$ as
$$
(m + m2^{128} + \cdots + m2^{128\times 7}) = m(1 + 2^{128} + \cdots + 2^{128\times 7}),
$$
and when we put it back in the equation, we have
$$
c = m^e(1 + 2^{128} + \cdots + 2^{128\times 7})^e \mod n.
$$
We can compute
$$
c' = c\times (1 + 2^{128} + \cdots + 2^{128\times 7})^{-e} \mod n,
$$
so we have the relation $c' \equiv m^e \bmod n$. In the case that $m^e < n$ (which happens for $e=3$, $5$ or $7$), then this is in fact an equality:
$$
c' = m^e.
$$
The value $m$ can be recovered by taking the $e$-nth root of $c'$.


Relationship between Fibonacci LFSR and Galois LFSR

Consider a Galois LFSR with feedback polynomial $x^3 + x + 1$ and initialization $1 + 0x + 0x^2$, that is, the shift register shifts its initial content $(1,0,0)$ rightwards, and the output bit (the rightmost bit) is fed back into the shift register into the $1$ and the $x$ position.  The initial loading of the LFSR is the Galois field element $1$, and successive contents are as follows:

$$\begin{array}[ccl]{3}
(1,0,0) &= 1 + 0x + 0x^2 &= 1\\
(0,1,0) &= 0 + 1x + 0x^2 &= x\\
(0,0,1) &= 0 + 0x + 1x^2 &= x^2\\
(1,1,0) &= 1 + 1x + 0x^2 &= x^3 ~~~ \text{remember that} ~x^3 = x + 1\\
(0,1,1) &= 0 + 1x + 1x^2 &= x^4\\
(1,1,1) &= 1 + 1x + 1x^2 &= x^5\\
(1,0,1) &= 1 + 0x + 1x^2 &= x^6\\
(1,0,0) &= 1 + 0x + 0x^2 &= x^7~~~ \text{remember that} ~x^7 = 1\\
\end{array}
$$
The LFSR output is the (periodic) sequence leaving the right end of the LFSR and is thus $(0,0,1,0,1,1,1)$ at which point the sequence repeats (the period is $7$). Notice that if we look at the successive contents of the leftmost bit in the LFSR,
they are $(1,0,0,1,0,1,1)$ which is just the output sequence shifted right cyclically by 1 bit while the middle bit is $(0,1,0,1,1,1,0)$ which is just the output sequence shifted left cyclically by one bit.

With the Fibonacci LFSR, there are two conventions as to what the feedback polynomial means. We can take $x^3+x+1$ to mean that the LFSR shifts right while the (XOR) sum of the current values of the output cell and the leftmost cell are fed back into the leftmost cell, or that the XOR sum of the two rightmost cells is fed back into the leftmost cell.  The corresponding LFSR contents are
$$\begin{array}[ccc]{3}
\text{output plus leftmost} & \quad & \text{two rightmost}\\
(1,0,0) & &(1,0,0)\\
(1,1,0) & &(0,1,0)\\
(1,1,1) & &(1,0,1)\\
(0,1,1) & &(1,1,0)\\
(1,0,1) & &(1,1,1)\\
(0,1,0) & &(0,1,1)\\
(0,0,1) & &(0,0,1)\\
(1,0,0) & &(1,0,0)
\end{array}
$$

Note that in the righthand column, the output sequence is $(0,0,1,0,1,1,1)$ which is identical to the output sequence of the Galois LFSR while in the lefthand column, the output sequence is $(0,1,1,1,0,1,0)$ which is just a reversed and shifted version of the output sequence of the Galois LFSR. Now, all this can be explained in great generality with reference to dual polynomial bases etc (as I did in my answer to the math.SE question cited by the OP), but the point is that the Fibonacci LFSR produces the same sequences as those produced by the Galois field LFSR, and that the reciprocal polynomial can be useful in explaining why this is so depending on the convention used to map the polynomial onto the circuit connections.

As a final note, Fibonacci LFSRs are vastly preferable to Galois LFSRs because the latter require Exclusive-OR gates between the "cells" of the LFSR while the former don't. Some modern hardware implementations of Fibonacci LFSRs don't actually store the data in the cells in a shift-register where the data goes ka-chunking from cell to cell as the register shifts (each transition costs energy!) even though that's what is always shown in illustrations and diagrams in textbooks and papers.  Instead, each cell content is stored in sRAM and accessed as and when needed (e.g. to participate in a XOR to be fed back to the "left-most" cell). What changes from clock cycle to clock cycle is the mental image (or memory map) of where the LFSR contents are stored in sRAM. The data itself does not move at all though one sRAM storage cell (the current "left-most" cell as per the memory map) gets its contents modified in each clock cycle. In a Galois LFSR implementation, many cells would need to be modified in each clock cycle leading to vastly increased complexity if everything is done in parallel or slowing down of the implementation so that the updates can be done sequentially in the time available for one "clock cycle" of the LFSR.