Prove that shares can reveal a seceret key. in a secret sharing scheme

The obvious way to do this is to do a secret derivation on committed values, and have the dealer show that derived committed value is the same as the value he originally committed to.

For this, I'll assume that the secret sharing scheme is over the prime field $GF(q)$.

The dealer publishes the commitment $P$, and remembers the commitment value $v$.

And, when the dealer generates the share $i$ (for participant $i$), it generates the share id (which we'll assume is $i$), actual share value $a_i$ (which is the value of the secret polynomial evaluated at the share id $i$) and a commitment value $v_i$.  It then gives the values $a_i, v_i$ to share holder $i$ secretly, and publishes the commitment $P_i = a_iG + v_iH$, as well as the share id $i$.  The dealer also remembers all the $v_i$ values.  When a shareholder gets his share, he can verify that his public commitment is consistent with the secret values he got.

Then, we select $k$ participants (you've already proved that the shareholders hold a consistent secret, and so it doesn't matter which set we pick).

Then, the actual secret value is $a = f_1a_1 + f_2a_2 + ... + f_ka_k \bmod q$, for some publicly computable values $f_1, f_2, ..., f_k$ (which depends on the actual set of shares).  Hence someone, possibly the dealer, computes the value:

$$Q = f_1P_1 + f_2P_2 + ... + f_kP_k - P$$

which everyone can verify, as all the parameters are public.

The dealer can express this as:

$$Q = \sum f_i(a_iG + v_iH) \ - (aG + vH) = (\sum f_ia_i - a)G + (\sum f_iv_i - v)H$$

Where the dealer knows the values $f_i, v_i, v$.  Hence, if $a = f_1a_1 + f_2a_2 + ... + f_ka_k$, then the dealer can generate a ZKP that he knows the discrete log of $Q$ to the base $H$; if not, then he cannot generate such a proof (because, if it knew that discrete log, it could (assuming it also remembered $a, a_i$) compute the discrete log of $G$ to the base $H$, which we assume was a hard problem.


Forgery against signature using RSAES-PKCS1-v1_5 padding

Less than satisfactory partial answer, which no longer fits a comment.

With $N$ of $k$ bytes and message of $l$ bytes, a (signature, message) pair with random signature is accepted by the most stringent verification oracle with probability $$2^{-8l-24}\;(2^{8k}/N)\;\left(1-2^{-8}\right)^{k-l-3}$$

For 2048-bit $N$ and small $l$, that's about $2^{-8l-25}$. Probability is higher for an oracle comparing messages as C strings, stopping with the first zero encountered.

That's enough for universal forgery of short messages with about $2^{8l+25}$ queries to the verification oracle or modular exponentiations to the $e$, and existential forgery with about $2^{24}$ modular exponentiations to the $e$. No signing oracle is used.

Malleability allows a small speedup: we pick some $a$ (e.g. $a=2$), compute $b=a^e\bmod N$, then $b^i\bmod N$ for incremental $i$, which we check for acceptable padding (and match with the message for universal forgery). If $b^i$ is accepted, $a^i\bmod N$ is a signature of the message embedded in $b^i$. Each new candidate $b^i$ is obtained with a single modular multiplication by $b$, rather than 16 sqrmod and 1 mulmod for modular exponentiation with $e=2^{16}+1$. Further, modular multiplication by a constant can be appreciably optimized by precomputations.

Independently, malleability allows to obtain $f$ existential forgeries from $f+2$ queries to a textbook-RSA signature oracle. We can efficiently prepare $2f+2$ values $c_i$ with acceptable padding such that $c_0 c_{2j}=c_1 c_{2j+1}$, submit $c_0$, $c_1$, and the $c_{2j}$ for $1\le j\le f$ to the oracle, then compute what it would return for the $c_{2j+1}$. There is a lot of freedom for the messages which forged signature is obtained. The attack still works if the signature oracle checks that what it is asked to sign has correct padding format, but fails if the oracle supplies the R part of the padding.

It remains unclear what The Bear had in mind with the following in his answer:

  If you use (this) padding for signatures, then you obtain a very weak signature scheme (because of the malleability inherent to modular exponentiations)


How can a fully encrypted homomorphic program resist copying?

That sounds impossible: your homomorphically encrypted program is just a program itself, and the fact that it runs some FHE does not matter with respect to the question of whether it can be copied.

A user with direct access to the program can always copy it, whatever you do (e.g. he could always take photos of the source code with his smartphone if he wanted).

If you want to make it truly impossible to copy, you need to run it in a secure environment (and as such a program will be likely very lengthy, that would most likely correspond to running it on a trusted machine to which the user is only given some input-output access).


How are random numbers for RSA generated?

Very important:

Determining whether an integer is prime is significantly easier than factoring it (at least in the current state of our knowledge). We can easily determine whether integers having thousands of decimal digits are prime, but such integers are far beyond the reach of current factoring algorithms.

Now to answer your question: "plain" RSA does not specify how the prime numbers are to be generated. For any particular implementation, you would need to look at its source code or documentation to see how it does it. A popular method is the "generate-and-test" paradigm:

Generate a random number of appropriate length.
See if it is prime, using either a probabilistic or a deterministic test depending on your level of paranoia. If it is prime, you have your prime. Otherwise, go back to step 1.

A simple application of the prime number theorem can give you an estimate of the probability that the number you picked is prime (depending on its length). This is generally not the same thing as the probability that your primality test will consider it prime, however, if you are using a probabilistic test.

I'll leave it to you as an exercise to implement this in your favourite CAS (e.g., PARI/GP or Sage) and see how it works in practice.

EDIT:

The two "tricks" given in the other answer will not make any difference in most cases.

Ensuring that we only give odd numbers to the primality test is useless: any decent primality test will immediately discard even numbers, precisely so as to not waste time on them.
Adding $2$ to the previous number instead of generating a new one from scratch also does not make any difference (at least on my machine). I can't see any reason to believe it should, either.


Tools for modelling and analysis of cryptographic protocols

There are a couple of options for protocol analysis tools.
(I don't know any established tool for their design - as said by someone else, designing your own protocols is not really recommended.)

If you are looking for formal methods based, symbolic tools, some well-known tools that have been applied to many protocols are ProVerif and Scyther. Given that you were looking for the NRL protocol analyzer, I guess this is the class you are interested in. The NRL protocol analyzer has been superseded by the Maude-NPA tool. If you are looking for something recent with interesting new features, the Tamarin prover may be worth considering. All these tools work in the "symbolic" model often referred to as the Dolev-Yao model: they assume that the underlying cryptographic primitives (encryption schemes, signature schemes) are perfect and analyze all possible interactions between an active network attacker and the protocol. The mentioned tools can verify correctness of a protocol (with respect to an unbounded number of sessions) as well as find attacks.

The other tool mentioned here, CryptoVerif, works very differently. It aims to establish "computational" security: it (partially) automates the game-based reductions typically used for proving the security of cryptographic primitives or Key Exchange protocols. Here one tries to construct a proof that if the attacker can break the protocol, he can break the underlying hardness assumption. (An example of such a hardness assumption is computing the discrete logarithm in a Diffie-Hellman style setting.) The tool cannot find attacks. In this category I would also recommend looking at EasyCrypt and CertiCrypt.

These two types of tools work at different abstraction levels, and usually a higher abstraction level makes it feasible to analyze more complex protocols.
For example, Scyther and ProVerif have been successfully used for relatively complex/large protocols. The tools in the second category give more precise security guarantees, but have so far only been used for primitives or very small protocols.

Caveat 1: if a tool finds an attack for you, you can effectively verify that it is a real attack on your protocol, which is useful. If the tool says "no attack" or "proof", it can still be the case that there is a flaw in your protocol model or security property, or that there is an attack outside of the scope of the used tool. All these tools differ in very subtle (technical) ways, which can make it very hard to compare their results.

Caveat 2: there are many more tools in the first category and I'm sure other people can explain cases in which you might want to consider on of the alternatives I didn't mention. However, without seeing your protocols and their intended security properties it is hard to give generic advice.


Is there parameter recommendation of DSA or RSA?

Are there recommendations of DSA[...]?

Yes, but you really want to verify these parameters yourself. DSA uses - as parameters - $(p,q,g)$ such that $q\mid p-1$ and $\operatorname{ord}(g)=q$. Among other things you want to verify that $q$ is prime, that $p$ is prime, that $q\mid p-1$ indeed holds, that $g^q\bmod p=1$ (ie that $g$ has the alleged order), that $p>2^{2047}$ and that $q>2^{255}$.

  Are there recommendations of [...] RSA [..]?

No, but you can re-use the public RSA exponent safely. To understand what can  be shared and what not, we first need to understand the relevant RSA parameters which are $(N,e,d)$ such that $ed\equiv 1\pmod{\lambda(N)}$ where $\lambda(\cdot)$ is the carmichael function. Now note that $(N,e)$ forms the public key and given just $N$ recovering $e$ or $d$ from each other is equally hard (ie as hard as brute-forcing the value). Note however that given a valid $(N,e,d)$ one can recover the factorization of $N$ (by applying the classical part of Shor's algorithm) using which one can break all other key-pairs $(N,e')$ (by the same way you'd normally find $d$ when generating the key), so sharing $N$ is out, but sharing $e$ is fine and commonly done with the value $e=65537=2^{16}+1=F_4$, where $F_4$ is the fourth fermat number.


Can spatial filters be used to factor composite numbers?

There are some good reasons why this hasn't been tried.

Firstly, it's not "discrete boundaries" but all points with integer coordinates $(x,y)$ on the hyperbola $xy=N$ which are candidates for factorization. The only information that matters is in those points, it doesn't matter if one uses your
$$
(N-xy)^2
$$
and look for zeroes, or if one uses
$$
(N/x)-\lfloor N/x\rfloor
$$
and looks for zeroes.

Secondly the function will be horribly noisy, and given our statistical knowledge about primes on the coarse scale, it is unlikely that it can be compressed much. The spatial filters can only use global, coarse information, otherwise they have to behave like functions that depend on brute force searching, in which case one might as well throw out the function, and the filter and the complications it represents, and work directly with discrete objects, i.e., integers, number fields, etc.

Finally, the state of the art factoring algorithms use a lot information from statistical as well as algebraic domains to optimize their execution complexity, but still have huge complexity, simply because $N$ is too large, and for the case we're interested in, $N=xy$ has ONLY one solution: This is when $x,y$ are two primes of roughly equal size.


It is the IV as a whole that needs to be unpredictable... but knowing some bits would make guessing the IV easier.

The requirement of an unpredictable IV has to do with chosen plaintext attacks. If the attacker can predict the IV, they can choose the first block of plaintext such that they can verify any guesses they have for the content of previous messages. For this to work, they must be able to end up with exactly the right input to the cipher – even a one-bit difference will generate a completely different ciphertext block and not verify the guess. (It would verify a slightly different "guess", which might sometimes be important, so getting very close to predicting could still be a problem.)

By using some bits of the IV on the predictable IP address, you make it that much easier to guess the rest. If the other 96 bits were completely random, the attacker would have a $2^{-96}$ chance of correctly guessing it, which is uselessly small. If it was less random then the attacker could have a chance.

By reducing the random part of the IV you also make IV collisions more likely (between IVs of the same device). The situations where this would be helpful are few. For example if you have a good CSPRNG but equal/close seeds on the different devices. If that was the case you would be better off seeding the CSPRNG with the IP/MAC in addition. Or using deterministic derivation of IVs as CodesInChaos suggested.


Appropriate public exponent choice for RSA encryption

we can arbitrarily choose an exponent $e$ as long as $\gcd(e,\phi(n))=1$.

No. If we want any security, we further :

Must NOT choose $e=1$, because that makes $x\mapsto x^e\bmod n$ the identity function over $[0,n)$.
Must NOT choose $e$ in a way revealing information about of $\phi(n)$ or the factors of $n$ beyond that $\gcd(e,\phi(n))=1$. For example, we can not choose  $e$ as $e=p$, nor $e=\phi(n)-3$, nor as the first integer larger than $\phi(n)/42$ with $\gcd(e,\phi(n))=1$, nor in such a way that $d$ is small.
Should choose $e$ not too small if there is a regulatory minimum or we have little assurance about how the key will be used. This mitigates to some degree some poor message padding and some poor decryption implementations. Using $e\ge2\log_2(n)$ should be technically OK for all except the worst (or absent) paddings.

What is the most appropriate choice for $e$?

The simple, safe, standard option is: choose $e=F_4=2^{(2^4)}+1=65537$, then choose prime factors $p$ of $n$ with $p\bmod e\ne1$. This test (and factors being distinct of $e$, which holds for suitably large factors) is enough to ensure $\gcd(e,\phi(n))=1$, since we picked $e$ prime. And picking factors as a function of $e$, rather than the other way around, ensures minimal information is revealed about $\phi(n)$ and factors of $n$. $65537$ is large enough that $e\ge2\log_2(n)$ is met for practical sizes of $n$, and conforms to recommendations by all major security authorities.
If for some reason we must choose $e$ after factors of $n$, a common practice is to choose the lowest $e$ above some minimum with $\gcd(e,\phi(n))=1$. A very slightly safer practice would be to choose $e$ randomly in some interval $[m,2m)$ until $\gcd(e,\phi(n))=1$, but that's overkill (and there's seldom a good reason to choose $e$ after the factors of $n$ anyway).

Should $e$ be small compared to $\phi(n)$ or approach it?

The former: $e$ should be small, and $\phi(n)$ large. There is often a conventional upper limit to $e$, like $e<2^{256}$ in FIPS 186-4, or $e<2^{32}$ in some Windows APIs, when $\phi(n)$ must be in the thousands of bits. And for reasons already spelled, $e$ must not be chosen close to $\phi(n)$. Also, it is best to keep $e$ not too large for performance reason: public-key use requires time roughly proportional to the bit size of $e$. The standard $e=F_4=2^{(2^4)}+1$ is attractive because encryption with it is faster than with larger values of $e$ (and as well as most lower values). Still, that $e$ makes public-key use about 8 times slower than with $e=3$; the latter can be a good choice when the performance of public-key use is paramount, appropriate padding and implementations are used, and regulatory requirements allow.


Security of a security protocol for key exchange, using symmetric-key cryptography

If we assume that $E$ is just semantically secure, without providing authenticity and integrity of the encrypted message then this scheme is has a huge drawback. It would be possible for an attacker to pose himself as either A or B, or to alter any message send from A to B.

So without authenticated encryption, this scheme may protect against eavesdropping, but not against alteration of messages. Although the attacker won't be able to decrypt messages from the other party, it is possible for an attacker to create an active attack and inject garbage into the messages received by either A or B.

As indicated, many smart cards provide similar key establishment routines, but those schemes use two master keys and two session keys - one for encryption providing confidentiality (symmetric encryption) and one for entity authentication and message authentication (MAC), although a single key and authenticated encryption (CCM or GCM) may also be used for $E$.

Note that above does not constitute a full crypto-analysis of the protocol, it simply points out that $E$ should be an authenticated cipher.


How effective noise based voice encryption against attack?

In WWII the primary way of encrypting radio broadcasts was to have the broadcaster transmit a signal with noise added from record, while the receiver would have an identical copy of the record subtracting the noise.

This is referred to as "scrambling", which is "encryption" in the analogue domain.

  Assuming that the noise is totally random, and the record is never replayed. How would one attack it?

Randomness of noise is quite a vague concept. You seem to be hinting at some kind of "one time pad" here. I'll first hint you why this isn't a thing for a scrambler, then give you some hints at possible attacks.

One time pads are carried out using a xor operation. A key property of the XOR operator is that when the distribution of $s$ is equiprobable (50% 1's, 50% 0's, which hold for the pad of a one time pad), the resulting ciphertext $e=m\oplus s$ will also have this probability, independently of the distribution of $m$. This is what makes the one time pad unbreakable.

Compare this to a scrambler. A scrambler adds the message to the pad: $e=m + s$. The plus operator does not have this equiprobability; it even, when $m$ and $s$ are independent, mixes the frequency spectrum! (To see this: the Fourier transform is a linear operator)

Let's break some analogue scramblers, using digital technology! Let's assume our message is speech, which feels like a pretty broad assumption. Speech has some cool properties; one of which is that it has a lot of repetition it vowels, and that most information is below 3000 Hz.

You can, for example, try a windowed cross-correlation in windows of around 30 milliseconds. The peaks of the cross-correlation give you an idea of the repetition frequency of certain vowels (out of which you even might extract the vowels). You may now attempt averaging out over different shifts, which should give you your vowels back.

A bunch of other statistical attacks can be carried out here. You can try yourself easily in MATLAB: sample a sine wave, add white noise, and try the above trick. Speech is a bit more difficult, but should be doable.

As always, give me a ping if you want me to go more in depth. I have no real references here, as I have this in my head from my signal processing and statistics courses.

  do modern encrypted radios that work in frequencies that are too low to transmit digital data like this still use this principle?

I cannot really answer that question, sadly. e-sushi made a comment that points to this question though, which seems to answer your question partly.


Commitment based on authencticated encryption

is there a property that guarantees that $D_{k'}(c)$ fails to verify/decrypt?

No, there is not; all the security guarantees that authenticated encryption provides is of the form "if you don't know the keys, then it is difficult to..."; it says nothing about the difficulty of anything if you do know the keys.

And, it turns out that, with GCM, you can generate a ciphertext that authenticates with two different keys, and it's not that difficult.

Here's how it works; you pick two random keys $k_0, k_1$, a random authentication tag $t$, and an appropriate nonce and AAD.  Then, GCM has the property that, if you have a 32 byte ciphertext consisting of the 16 byte blocks $X_a, X_b$, this ciphertext would authenticate (in the context you picked) if:

$$h^3 X_a + h^2 X_b = C$$

where $h$ is the authentication key generated by the key, and $C$ is a constant that depends on the key, authentication tag, nonce and AAD, and all math is in $GF(2^{128})$

The two different keys generate different $h$ and $C$ values, and hence we can generate two simultaneous equations:

$$h_0^3 X_a + h_0^2 X_b = C_0$$

$$h_1^3 X_a + h_1^2 X_b = C_1$$

Everything here is known except for $X_a, X_b$; you have two simultaneous linear equations, and so you can solve for $X_a, X_b$, thus giving you a ciphertext that will decrypt to something with two different keys.

Now, this method doesn't give you any control over what they decrypt to, but still, that is enough to show that GCM isn't binding.

Instead, it would make a lot more sense to use a hash function, that is, $\text{Hash}(r, M)$ for a random fixed length nonce $r$.  The collision resistance property means that it is binding.  And, if the random nonce $r$ you include is longer than the hash, then it is plausible that even a computationally unbounded attacker cannot get more than weak probabilistic information of what you committed to.


Using a PRP $\pi: \{0,1\}^{16} \to \{0,1\}^{16}$ to construct an ideal cipher

There are $2^{16}!$ distinct permutations of the 16-bit strings $\{0,1\}^{16}$.  For any fixed Feistel structure built out of one of these as you suggest, there are still only $2^{16}!$ possible outcomes.

There are $2^{128}!$ distinct permutations of the 128-bit strings $\{0,1\}^{128}$.  In an ideal cipher, for any fixed key $k$, $E_k$ is an independent uniform random permutation: each possible permutation has probability $1/2^{128}!$ of being $E_k$.

But in your construction, there are at least $2^{128}! - 2^{16}!$ permutations that $E_k$ cannot be.  (There may be more because conceivably some pairs of permutations may collide under the Feistel structure, pending further analysis to rule that out.)  So no matter what Feistel structure you choose, or non-Feistel composition of the permutation, you cannot get an ideal 128-bit block cipher out of a random 16-bit permutation.

What about a pseudorandom permutation family?  Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter.

Table lookups are, indeed, a common design element in cryptographic primitives, including the venerable DES.  You can view AES as a composition of table lookups and xor, but as the rest of the paper demonstrates this implementation strategy will lead you into trouble, which is why alternative designs like Serpent and newer designs like Salsa20 don't even tempt implementors into using secret-dependent table lookups.

Further, to make a thing that can be computed with, rather than a probability distribution that can be studied, you need to choose particular tables—and as Don Coppersmith and his team at IBM learned in 1974, the choice of tables can be tricky.


Why does SRP-6a use k = H(N, g) instead of the k = 3 in SRP-6?

If k is a constant, such as 3, it becomes possible to select a pair (N,g) such that the discrete log of k to the base g is known, which would enable the two-for-one guessing attack again.


In common cryptographic protocols there is only a need to generate RSA asymmetric keys now and then, say once a year. The key pair generation does not have to take place in the same environment either; e.g. you could use openssl command line if that is available. Note that RSA key pair generation time depends on finding large primes; the runtime is not static - it changes on each run.

If your protocol does have to rely on asymmetric key generation then you would do well to switch to Elliptic Curves. Elliptic curve key pair generation is very fast and private key operations are faster as well. Verification is slower than RSA though, at similar security levels.

Try e.g. the BrainpoolP256r1 named curve. Warning; EC crypto is not for the weak of heart.


How can I simulate and measure brute force hacking using RSA?

Firstly, I assume we are talking about classical computers

Implementing a brute force attack on a RSA may not be the most sensible thing, unless of course the security parameter of your target system is small.. (160 bit numbers! )

Even then you may not want to implement a brute force here.. try using Fermat's Factoring or  Pollards $\rho$ method.

If you just want to measure time try to do a more theoretical research, i.e. use the time take per multiplication op. and the no. of operations your computer can perform in a sec to determine exactly how long will it take you to brute force a $n-$bit security.

To sum it up, YOU CANNOT BRUTE FORCE THE (properly implemented) MODERN DAY RSA (~4096 bit numbers) even if you use all computers in your state.


Ok, here we are speaking of non-interactive zero-knowledge proof systems for some language $L\in NP$. We there have a pair $\sf (P,V)$ of
probabilistic polynomial time algorithms (called the prover and the verifier) where both have input $x\in L$ and $\sf P$ additionally
holds a secret witness $w$ for membership of $x$ in $L$ and wants to convince a verifier $\sf V$ of this fact without revealing $w$.

One requires (a bit informal):

correctness: for $x\in L$ all proofs generated by $\sf P$ will always be accepted by $\sf V$
soundness: for $x\notin L$ proofs generated by by $\sf P$ will only be accepted with negligible probability by $\sf V$
zero-knowledge: for $x\in L$ the view of a verifier can be efficiently simulated without
the knowledge of $w$. Actually, the definitions you provide are in the common reference string (CRS) model, i.e., there is a $crs$ to which all entities
have access to. For zero-knowledge one requires that $(crs,x,\pi)$ with $\pi \leftarrow {\sf P}(crs,x,w) $ and $(crs,x,\pi)$ with $(crs,\pi) \leftarrow {\cal S}(x)$,
where $\cal S$ is the so called simulator, are computationally indistinguishable.

Now, adaptive zero-knowledge means, that soundness and zero-knowledge are with respect to adaptive adversaries. For soundness this
means that an adversary $\cal A$ is allowed to choose $x\notin L$ after seeing the $crs$. For zero-knowledge one requires from
the simulator $\cal S$, that $\cal S$ has to output $crs$ first and afterwards produce the simulated proof $\pi$. These two steps of the
simulator are denoted as ${\cal S}^{crs}$ and ${\cal S}^{proof}$ respectively. Note that these two definitons
are stronger definitions than in the static setting (described in the beginning).

Since the authors are talking about zero-knowledge proofs of knowledge for some $NP$ relation $\cal R$, they additionally require a property known as knowledge extraction.
Basically this means that the witness $w$ can be extracted from the proof transcript (this extractor is the algorithm $E$).

They also use a common reference string $crs$ with a trapdoor $trap$ which is required in order for ${\cal S}^{proof}$ to simulate a
proof without knowing the secret witness (you may look for instance at Groth-Sahai NIZK proof system for examples).

The notation ${\cal A}^{S'(crs,trap,\cdot,\cdot)}$ means that the adversary $\cal A$ has oracle access to the algorithm $S'$ where the inputs
 $crs$ and $trap$ are fixed and the latter two input arguments (indicated by $\cdot$) can be arbitrarily chosen by $\cal A$. Hope that helps a bit.


Using the output of a stream cipher, how to guarantee the integrity of 4 bytes of data?

So you have a small integer, and you want to transmit it in such a way that (a) you don't particularly care if the attacker finds out what that integer is, but (b) no matter what the attacker changes or substitutes, you don't want the receiver to be tricked into thinking you sent some other number (in particular, some other much larger number).

securing the integer

As you've already figured out, that is exactly the purpose of a MAC such as a UMAC
and the purpose of a digital signature.

There are many protocols (including gzip and MP3) that add a CRC immediately after the header, in order to allow the receiver to immediately reject a packet with accidental noise in the "length" field (a), (b), for exactly the reason you mention.

I've seen a few ad-hoc constructions where the transmitter sends the number N
followed by some simple function of N, such as (N+1), (~N), (-N), N itself again, CRC(N), fletcher_checksum(N), etc.

Alas, as you already know, a standard CRC is vulnerable to malicious modification (even when encrypted by a stream cipher):
an attacker who knows the exact position of the length field and the CRC that covers it
can flip the high bit of the length field, and then flip the effected bits of the CRC,
resulting in a valid-looking header -- even if the entire message -- length, CRC, and all -- is protected by a "perfectly-secure" one-time pad.
(Most other "simple function of N" are just as vulnerable).

(Does switching from a stream cipher to a block cipher help?)

Your idea of using a MAC such as UMAC to protect the header (including the "length" field and perhaps also including a few bytes of random nonce) helps a lot, but it doesn't completely fix the DoS issue you mention:

message = header || MAC(header) || clear text || MAC( header || clear text )

then transmit

( message ) ⊕ unique stream cipher

The " Should we MAC-then-encrypt or encrypt-then-MAC? " question implies that it may be better to do that in the opposite order:

header = (length || other stuff) ⊕ unique stream cipher
body = (clear text of message) ⊕ unique stream cipher

then transmit

header || MAC( header ) || body || MAC( header || body )

Either way, the attacker won't be able to "blindly" DoS your system by sending a short message that looks like a valid header for a gigabytes-long message, unless he comes up with a valid-looking MAC(header) -- which is difficult.

securing the integer isn't enough

However, if you ever really do start sending a valid message with a valid header indicating "gigabytes of data will follow", and then if the attacker manages to insert or delete or change any bits or bytes in the following message, then the receiver will still get hung up doing useless work processing those gigabytes of data, only to throw them all away in the end.
(And what happens next week when the attacker sends a short message that replays that valid "gigabytes of data follows" message header again?)

alternatives that don't require securing the integer

For this reason, many protocols and file formats (ZMODEM, IPv4, IPv6, gzip, MP3, etc.) put a hard limit on the maximum length of a packet (with a "length" field of 16 or fewer bits), forcing larger amounts of data to be chopped up into a series of packets.
Rather than "a 4 byte message size",
they have, for example, "a 12 bit message size field",
and then files of data longer than 4 KBytes are sent as a series of packets,
each packet with its own independent CRC or MAC or digital signature.

In addition to avoiding the "DoS" problem you describe, breaking up long messages into packets
also has other advantages.
When a few packets are damaged by "innocent" noise,
the system can figure out which packets were damaged,
and then resend just those packets,
rather than re-sending the multi-gigabyte file all over again from the beginning.

Possibly related questions:

Can you make a hash out of a stream cipher?
Converting a stream cipher into a block cipher


Defining RSA Problem as finding $m$, having $N,e,c$ where $c=m^e \mod N$ and $N=pq$, two unknown same-size prime numbers.

So far the best generic method we know to solve this is to factor $N$.

But there might be other methods, so far unknown, to compute the $e$-th root of $c$ and recovering $m$.

This is different from the discrete logarithm problem, where the exponent is secret. This is just computing an $e$-th root. We know how to compute roots modulo a prime, we don't know how to compute roots modulo a composite number of unknown factorization.

Note: for bad choices of m (i.e. without the use of padding) or $e$ or $d$ (the private exponent) there are practical attacks that recovers $m$ without factoring. For example the Weiner's or Coppersmith's attack. In particular the method of Coppersmith does compute $e$-th roots if $e$ and $m$ are small enough therefore it is not a generic method.

The RSA Problem is at least as easy as factoring. But there might be other, so far unknown, easier way to compute $e$-th roots without factoring.


Algorithm accepting every passphrase to fool unlegit user

I'm not sure of the exact status of the program, since there was some controversy surrounding it a few weeks ago, see: Is TrueCrypt not secure now and should I stop using it?. But the very popular program TrueCrypt, a program is typically used to encrypt stored files and drives, I believe has the property that you are asking about. Its called: Plausible Deniablility. So combine the concept of plausible deniablility with strong crypto and you have Deniable Encryption

A passage from the page on deniable encryption states:

  Normally ciphertexts decrypt to a single plaintext and hence once
  decrypted, the encryption user cannot claim that he encrypted a
  different message. Deniable encryption allows its users to decrypt the
  ciphertext to produce a different (innocuous but plausible) plaintext
  and insist that it is what they encrypted. The holder of the
  ciphertext will not have the means to differentiate between the true
  plaintext, and the bogus-claim plaintext.

How TrueCrypt implements this, is basically by allowing you to make hidden partitions on a hard drive, and have "fake" partitions to fool attackers.


If we are to summarize things in one sentence, let's say that pairings allow for three-party mathematical protocols.

Consider for instance identity-based encryption. In a classical public-key cryptography system for encrypting messages (e.g. emails), the sender must know the recipient's public key in order to encrypt the message. Distribution of public keys is a known troublesome problem (less hard than distribution of secret keys, but hard nonetheless). IBE strives to make the recipient's public key actually equal to the recipient's name (or email address), because the sender already knows it. If you want to do IBE with, say, RSA, you usually end up with a centralized system in which there is a central system C through which all messages go. Every user knows one public key, the one of C, and encrypts the message with that public key. C decrypts the message, and reencrypts it with the intended recipient's public key (C knows all user's public keys).

This classical model for IBE does not scale well, because the central system must receive, decrypt, encrypt and send every email. Pairings resolve that by moving the central systems to mere mathematics. With pairings, the central system C still exists, but it needs not be invoked for every email. Things go more or less like this:

The central system C has a private key, and the corresponding public key K is known to every user.
Each user U obtains his private key KU from C.
When sender S wants to send an email to recipient R, he can "somehow" compute R's public key using only R's name (email address) and the central system public key K.
Recipient R uses KR to decrypt the message.

The pairing is what resides in this "somehow". It is a computation involving K, R's name, and some input from U. It moves C out of the physical picture. C is still there mathematically (and, in particular, C knows the private keys of every user, since C computes these private keys), but C needs not do anything in particular at the time the email is sent. This prevents C from becoming a network bottleneck when traffic increases.

In a similar way, pairings are convenient for electronic cash protocols (three-party protocols between buyer, merchant and bank, and we would prefer not to have to actually talk to the bank for each transaction).

Historically, pairings were a mathematical curiosity from the 1950s, shown practical for cryptography in 1986 by Miller, and first used to break elliptic curves. Indeed, a pairing from $G_1\times G_2$ to $G_3$ turns a discrete logarithm problem on $G_1$ into a discrete logarithm on $G_3$. For known pairings on elliptic curves, $G_1$ is an $n$-bit curve, and $G_3$ is a multiplicative subgroup in a finite field of size $kn$, where $k$ is the embedding degree of the curve. Sub-exponential algorithms for breaking DL on finite fields are known, so if $k$ is small, applying the pairing makes the DL problem easier.

Fortunately, for most curves as used in practice, $k$ is astronomically high, so the pairing does not break DL on these curves. Some specific curves (especially most supersingular curves) turned out to have very low embedding degrees, and, for them, pairings are a useful breaking tool.

Constructive uses of pairings (as for IBE) rely on using "slightly weakened" curves, i.e. curves for which the embedding degree is sufficiently small to allow the pairing to be efficiently computed, but not small enough to make DL on $G_3$ too easy. For instance, IBE would use an 800-bit supersingular curve of embedding degree 2; DL on a 1600-bit finite field is still way beyond what is technologically feasible. This still is a rather delicate dance which explains that a lot of cryptographers feel uneasy in the presence of a pairing.


Looking for title of encryption machines book

This is the book, I believe.

W Barker: Cryptanalysis of shift register generated stream cipher systems

I have (had? I need to check, maybe gave it away) a copy.


How can I hash an input into an arbitrary domain point?

Hash functions we use, e.g. Sha-1, Sha-256, Sha-512, usually don’t have a sufficiently large range. But we can construct full domain hash via repeated application of a hash function $h$: $FDH(m) = h(m||0)||h(m||1)||\cdots  $, then take the leading n-bit. This way the hash value is deterministic and the size is arbitrary.

This is something like MGF1 defined in PKCS #1 v2.2, B.2.1.


Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

/!\ the counter-example I build below is not a formal refutation of the statement, a more rigorous analysis is needed, but it gives an intuition of why I think that $f'x\mapsto f(x)\mathbin\|f(f(x))$ is not necessarily an OWF (thanks to Christian Matt for pointing out the necessity of a more rigorous analysis).

It seems to me that $f': x \mapsto f(x)\mathbin\|f(f(x))$ is not necessarily a OWF when $f$ is not length-preserving. Consider the following function $f$:

$h$ is an arbitrary length-preserving OWF. $g$ is an arbitrary OWF that compresses its input by a factor two.
$f$ is defined as follows: on input $x$, if $|x|$ is odd, then $f(x) = 0^{|x|} \mathbin\| h(x)$. Else, if $|x|$ is even, then if $|x|/2$ is also even and $x$ is of the form $x' \mathbin\| 0^{3|x|/4}$, return $x' \mathbin\| 0^{|x|/4}$. Otherwise, if $x$ is of the form $x'' \mathbin\| 0^{|x|/2}$, return $h(x'')$. In all other cases, return $g(x)$.

So, as you can see, $f$ maps $n$-bit inputs to $n/2$-bit outputs when $n$ is even, and to $2n$-bit outputs when $n$ is odd. I think that one can prove that $f$ is indeed an OWF by picking an appropriate function $g$ whose image does not intersect with $\{0\}^n \times \{0,1\}^n$ so that on a random input $x$, the probability that $g(x)$ is of the form $x' \mathbin\| 0^{3|x|/4}$ is very small (as this is the "easy to invert" case).

Now, let $n \equiv 2 \bmod 4$ ($n$ is even, and $n/2$ is odd). Then when you receive $y = f(x)$ for a random $n$-bit input $x$, it is easy to invert $y \mathbin\| f(y)$: with very good probability, $x$ is not of the form $x'\mathbin\|0^{3|x|/4}$, hence $f(x) = g(x)$ (which is of odd length $n/2$). In this case it holds that $f(y) = 0^{n/2}\mathbin\|h(y)$. But this makes inverting $y \mathbin\| f(y)$ trivial:

$$y\mathbin\|f(y) = y\mathbin\|(0^{n/2}\mathbin\|h(y)) = (y\mathbin\|0^{n/2})\mathbin\|h(y) = f(y\mathbin\|0^{3n/2})\mathbin\|f(f(y||0^{3n/2}))$$

Hence one can simply return $y\mathbin\|0^{3n/2}$ to successfully invert $f':x \mapsto f(x)\mathbin\|f(f(x))$. So unless I'm missing something / making a mistake, $f': x \mapsto f(x)\mathbin\|f(f(x))$ is not necessarily a OWF when $f$ is not length-preserving.

EDIT: corrected mistakes in the previous version of my counter example.


Why in RSA do we use mod n rather than mod phi(p⋅q)?

There are two reasons for not using $\varphi(n)$ during encryption.
The first one is that it doesn't work - you can verify this by looking at the RSA correctness proof. It requires, that the modulus is $n$.
The second one is - if you know $\varphi(n)$ you can efficiently compute $d$ given $e$, and therefore know the private key.


Is there a zero knowledge proof for divisibility by 7?

Everyone has access to a number divisible by 7, like 0, 7, 21, 434, etc, so I will assume you mean there is a secret that a party has and is using and THAT number has to be divisible by 7.

  Is this a reasonable thing to prove with a zero knowledge system?

It does seem rather odd, but if the other party needs to be sure your secret is divisible by 7, then you need this proof.  I can't imagine such a protocol off the top of my head, but if you have one that requires it, then I guess you need it.

You can do this in Zero Knowledge if you are willing to concede pieces of information that are usually considered minor.  You can prove anything problem in NP in zero knowledge.  It would imply knowledge of the divisor, but if you know the secret number, you can already the number divided by 7.  By the nature of the cryptographic tools, you will be forced to place an upper bound on the size of $n$ and $n \over 7$.  There is also the issue of overflow.  In many cryptographic settings, $n \over 7$ could be large enough so that if you were to multiply by 7, it would wrap around and reach some normally unrelated $n$.

If $n$ is divisible by 7, then there is an integer $k = {n \over 7}$

You can encrypt $n$ and the $k$ in exponential (additive) elgamal or use Pedersen Commitment, all of which are homomorphic.  I will use Pedersen Commitments.  With a group $G$, take generators $g, h \in G$ such that the DLOG between $g$ and $h$ is unknown.   and $r_x$ be random numbers.  $q = |G|$.

This proof consists of two distinct parts:  First, we prove that $7k \equiv n
 \text{ mod } q$, then we prove that $7k < q$.

The Prover creates two commitments $C_k = g^k h^{r_k}$ and $C_n = g^n h^{r_n}$ and sends them to the Verifier.
The Verifier and Prover raise ${C_k}^7 = g^{7 k} h^{7 r_k} = {C_{7k}}$.
The Verifier and Prover computes $C_{7k} \cdot {C_n}^{-1} = g^{7k - n} h^{7r_k - r_n} = h^{7r_k - r_n}$.
The Prover privately calculates $r_1 - 7r_0$
The Prover and Verifier run Schnorr's protocol on $C_{7k} \cdot {C_n}^{-1}$, with the Prover proving knowledge of the DLOG of $h^{r_n - 7r_k}$ base $h$.

NOTE:  At this point, it is proven that $k \equiv {n \over 7}$ mod $q$, but it is not proven that $k$ didn't overflow, meaning at this point $7k$ could be greater than $q$, meaning in $n = 7k \text{ mod } q$, $n$ may be divisible by $k + q$ instead of $k$.  The following steps prove $7k$ didn't overflow by representing it in a bitwise manner, essentially setting bounds on $k$ based.  This implicitly puts an upper bound on the value of $0 \leq k \lt 2^t$, where $t$ is the number of bits.  You can have as many leading zeroes as you need if $k$ is small.

If the Verifier accepts the Schnorr proof, the Prover creates a bitwise representation of $k$.  The Prover constructs a list of $t$ bit commitments representing $k$, of the form $C_{b_i} = g^{b_i} h^{r_i}$, where $b_i$ is the bit in the $2^i$ place in $k$.  $t$ has to be 4 bits less than the number of bits (or fewer) in the order $q$ to avoid overflow and to leak as little information as possible, as multiplying will add 3 total bits to the number.
Prove each commitment hides a bit.  There is a proof for this in the appendix of this paper: http://crypto.stanford.edu/~dabo/pubs/abstracts/provisions.html.
If these proofs are accepted, both parties homomorphically combine the bits to get a commitment of $k$:  $C_k' = \prod_{i=0}^{t} {C_{b_i}}^{2^i} = g^k h^{r'_k}$. The Prover knows $r'_k = \sum_{i=0}^t r_i \cdot 2^i$.
The Verifier and Prover computes $C_{k} \cdot {C_k'}^{-1} = g^{k - k} h^{r_k - r'_k} = h^{r_k - r'_k}$.  The Prover calculates $r_k - r'_k$.
The Prover and Verifier run Schnorr's Protocol to prove knowledge of the DLOG of $C_{k} \cdot {C_k'}^{-1}$ base $h$, which happens to be $r_k - r'_k$.

This protocol does release some information about the secrets, namely $n < 7\cdot 2^t < q$, ${n \over 7} < 2^t$, but usually with this kind of proof, the Prover is willing to concede these points.  You can get more precise by using a range proof to prove that $k < \left \lfloor{q\over 7} \right \rfloor$ on steps 6 and 7, but you can find that on your own.  Other than these pieces of information, this protocol should be Zero Knowledge.

This protocol perfectly hides $k$ within the bounds above.  Any $k$ within those bounds can produce an identical transcript.  Even with infinite computational power (assuming true random numbers), an adversary can not figure out your $k$ afterwards.  Same mostly goes for $n$, except they know $n$ is divisible by 7.

It should be noted that nothing here makes the Prover use the appropriate $n$.  This will need to be either verified beforehand.  If you don't care which $n$ he chose, he is still bound to using the $n$ from this proof if you use the appropriate Zero Knowledge Proofs to require he use the $n$.

This protocol can be made non interactive by taking the component Zero Knowledge Proofs and applying the Fiat-Shamir Heuristic, which replaced the Verifier's challenge with a hash of the inputs and the initial communication.

There is also the logic circuit option, which is more flexible but less efficient.  You essentially prove your bits from the $k$ can go through a multiplication logic circuit and end up with $n$.

If you haven't read it yet, I would recommend reading Hazay and Lindell's section on Zero Knowledge Proofs from the book Efficient Secure Two-Party Protocols: Techniques and Constructions (Information Security and Cryptography)


What is the relation between RSA & Fermat's little theorem?

To walk you through RSA from start to end, here's how it works.

Choose two large distinct primes $p$, $q$. Calculate $n=pq$.
Calculate $\phi(pq)$. This happens to be $(p-1)(q-1)$.
Choose $e$ such that $gcd(e, \phi(pq)) = 1$ and $1 < e < \phi(pq)$.
Compute $d$ such that $de = 1 \mod \phi(pq)$.
Do some crypto; $c = t^e \mod n$ and $t = c^d \mod n$.

What you really want to know is why these statements hold. Fermat's little theorem states that $a^p = a \mod(p)$ An alternative, equivalent definition is that $a^{p-1} = 1 \mod(p)$.

Actually, for the purposes of RSA, that's insufficient. What you want is a generalisation called the Euler-Fermat generalisation, which states:

$$a^{\phi(n)} = 1 \mod{n}$$
Next up - what the hell is this $\phi(x)$ function? In plain English, it's the number of numbers less than or equal to $x$ which are also coprime to it. For any given prime $p$, every number less than itself is coprime to it, which means $\phi(p) = p-1$. If you're wondering about why $\phi(1) = 1$, well, $gcd(x, 1) = 1$ is the definition of coprimality, including for 1 itself.

Now, it's also possible to prove that $\phi(xy) = \phi(x)\phi(y)$. Unless someone really wants me to, I'll skip the details (see a textbook on number theory) but, this essentially means $n = pq \Rightarrow \phi(n)=\phi(p)\phi(q) \Rightarrow \phi(n)=(p-1)(q-1)$.

Now, a little group theory too. Multiplication for certain sets of positive integers forms a group under modulo provided all the elements you pick for it are coprime to the modulo you're using. It so happens we've picked $e$ to be co-prime to our modulo $\phi(pq)$. Group theory guarantees us the existence of an integer in the group that acts as an inverse uniquely for that integer and transforms, under multiplication, that integer to the identity. The identity element under multiplication is $1$ and the inverse here is $d$.

So, let's recap: we've got $e$ and we've got $d$. One is the inverse of the other under the group $\phi(n)$. What we need is a link back to the Euler Fermat generalisation showing this:

$$ t = ((t^e)^d) = t^{ed} \mod (n) $$

So, before we do that let's just review what we understand by congruences. If I have the number $4 \mod (9)$, are you happy that $13 = 4 \mod(9)$? And that $22 = 4 \mod 9$? And that $31 = 4 \mod (9)$? You should see a patter emerging here; in fact, your general representation in this case is $4 + 9k$ generates you the set of numbers that are equivalent to $4$ modulo $9$.

So, $de = 1 \mod \phi(pq)$ could be expressed as $de = 1 + k\phi(pq)$, yes? I.e. to 1, I can add multiples of $\phi(pq)$ then apply modulo $phi(pq)$ and it'll be equivalent to 1.
This might take some getting your head around.

Once you've got there, $t^{ed} = t^{1+k\phi(pq)} \mod (pq)$. All I've done is substitute one expression for the other; no magic. Now a little re-arranging: $t^{1+k\phi(pq)} = t^1 t^{k\phi(pq)} \mod (pq)$ then $t^{1}t^{k\phi(pq)} = t^1 (t^{\phi(pq)})^k \mod (pq)$.

Now, we use the Euler-Fermat generalisation. Notice we have $t^{\phi(pq)} \mod (pq)$. Being "under modulo", we can still evaluate this, since the power to the $k$ simply means multiplying $k$ lots of that expression together. So now, apply the theorem:

$$t^{\phi(pq)} = 1 \mod (pq)$$

and we're left with $t^1 (t^{\phi(pq)})^k = t^1 \times (1)^k \mod (pq)$, which as you probably know is just $t$.

So, that is how they relate. This isn't the only way to prove RSA either. The Chinese Remainder Theorem proof I think is nicer, but I also think it is harder to understand.


How long does it take to crack DES and AES?

Assume that 1 evaluation of {DES, AES} takes 10 operations, and we can perform $10^{15}$ operations per second. Trivially, that means we can evaluate $10^{14}$, or about $2^{46.5}$ {DES, AES} encryptions per second. This is a simplistic view: we are ignoring here the cost of testing whether we found the correct key, and the key schedule cost.

So on our hypothetical machine, a 56-bit DES key would take, on average, $2^{55}/2^{46.5} = 2^{8.5} \approx 362$  seconds to find. Similarly, a 128-bit AES key would take $2^{127}/2^{46.5} = 2^{80.5}$ seconds $\approx 2^{55}$ (or approximately $36$ quadrillion) years to find.


The MixColumns $MC$ and InvMixColumns $IMC$ implement matrix multiplications. These two matrices defined over Galois Field $GF(2^8)$ and they are inverse of each other.

$$MC \times IMC = I_4$$

To find the inverse, one can use the Gaussian Elimination method. But finding the inverse a bit tricky, since you will need the inverse of the pivot elements. The inverse in $GF(2^8)$ can be found by using the Extended Euclidean Algorithm.

In general, instead of calculating the inverse, the invMixColumn matrix copied from FIPS 197 or  AES submission of  Rijndael.


Stopping timing attacks on AES: Why is it important to prevent the OS from interrupting the AES computation?

The paper explains why.  Preventing the OS from interrupting the AES computation is part of Bernstein's proposed method of defense against cache-based timing attacks.  Let me sketch the argument for you:

The early part of the paper explains that if the time is variable, then it introduces a risk of timing attacks.  Sections 3-6 demonstrate that such an attack is practically feasible.

This raises the question of how to provide high assurance that we have stopped these attacks -- and not just the ones we know about, but the entire class of timing attacks.  Bernstein argues that the best defense against this class of attacks is to ensure that the running time for the AES computation is constant, and independent of the inputs.  See Section 8.

So, this raises the question of what we need to do to ensure that the AES computation is timing-independent.  The remaining sections identify some challenges, and outline solutions.

In particular, Sections 10-11 point out that cache effects can cause timing variability.  And, it is easy to see how this could affect security: cache effects mean that the time taken depends upon the address you look up, and the design of AES means that (if you use table lookups in the obvious way) the address you look up depends upon the key.  Indeed, this is almost certainly exactly the effect that enabled the attack in Sections 3-6.

So the next question is, how do we ensure that cache effects don't introduce timing variability?  The natural solution is: load the entire table into L1 cache, lock it into L1 cache, and make sure it doesn't get kicked out at any point during the AES computation.  However, this natural solution has a problem, on time-sharing operating systems: the OS might preempt us at any point and run some other task.  If that happens, it screws up our defense, by evicting our pre-loaded values from the L1 cache.
In particular, if our pre-loaded values get evicted from the L1 cache, we're back to the vulnerable situation where we started.  Now the total time taken depends upon the sequence of addresses looked up.  For instance, if you look up the same index in the table twice, it'll be faster than looking up two separate indices -- so we might leak information about whether table lookups use the same indices or different indices.  However, in (a natural implementation of) AES, those indices are key-dependent.  Thus, this timing leak might leak information about key-dependent values: it'll leak whether two intermediate values are equal, where both intermediate values depend upon some key material.  This leaked information can plausibly be used to learn some partial information about the key material, thus creating exactly the sort of side-channel attack we're trying to stop.

To prevent this, we need to have some way to be sure that this sort of bad outcome won't happen.  The obvious way to be sure is to somehow introduce some mechanism to ensure the AES computation cannot be interrupted.  If the AES computation cannot be interrupted, then we eliminate the risk of attacks based upon such interruptions.  So, that's what Bernstein proposes.

Bernstein goes on to argue that this is the only solution he is aware of, that meets the requirements.  In particular, the key requirement here is "we need a way to be confident (with high assurance) that there are no attacks".
Does this mean I can tell you with certainty that there is no other defense?  Of course not.  It just means that someone smart studied this and came to the conclusion that, at the moment, the highest-assurance solution appears to be preventing interruptions by the OS.  If someone else wants to argue that this is unnecessary, the burden is on them to show that their alternative is guaranteed to be free of attacks.

Please understand that an important principle of cryptography is: just because you can't think of any attacks, doesn't mean no attacks are possible.  In cryptography, there's a big difference "no evidence that an attack is possible" vs "evidence that no attack is possible".  It's not uncommon for cryptographic schemes that are justified on the basis that the designer couldn't think of an attack (in other words, couldn't find any evidence that an attack is possible) to get broken.  For that reason, cautious cryptographers often aim for the goal of demonstrable evidence that the system is secure (finding positive evidence that no attack is possible).  This is harder, but a more solid foundation for security.

That said, it's important to understand that this paper represents Bernstein's recommendations, which are somewhat at odds with the conventional wisdom of the rest of the community.  Most of the cryptographic community doesn't bother with preventing the OS from interrupting the AES computation, on the theory that they don't know of any attack that's practical enough to pose a significant risk to their system as deployed in the wild.  Basically, they judge that the risk of such an attack is low enough that they are willing to accept the risk.  They may be right.  Or they may not.  Either way, my answer above is predicated on the assumption that you want to understand Bernstein's argument, so you can form your opinion about whether you are convinced or not.  I'm not trying to take a position on whether Bernstein is right or whether the conventional wisdom is right, just trying to respond for your request for help understanding the paper.


Is it possible to encrypt data in such a way that it cannot be decrypted with the key used to encrypt it but can be decrypted with another key

Yes.  Use public-key encryption: encrypt the data using the server's public key.  You should be able to fill in the details from there.


This is the Matyas–Meyer–Oseas construction.  It was introduced by engineers at IBM in 1985, and analyzed in the ideal cipher model by Black, Rogaway, and Shrimpton in 2002 among all possible iterated compression functions $h_i = f(h_{i-1}, m_i) = E_a(b) \oplus c$ where $a$, $b$, and $c$ are message blocks $m_i$ or chaining values $h_{i-1}$.  For this case ($i=1, j=6$, or $a = h_{i-1}$, $b = m_i$, $c = m_i$), in the ideal cipher model, the adversary's probability of finding a preimage after $q$ queries lies in $[0.4 q/2^n, 2q/2^n]$.

Now, AES is not an ideal cipher—at best, it is a pseudorandom permutation family.  But it is likely that the related-key attacks of Biryukov and Khovratovich do not substantively affect the security of this scheme when the salt is not under attacker control.

(All the references you need are actually in the paper you cited already, right where it recommends using AES.  If you can't follow them because of morally reprehensible academic paywalls, Sci-Hub and LibGen are your friends.)


Can you exchange a shared key without any hardness assumptions?

In cases where Alice and Bob are guaranteed to arrive at the same key, this is impossible: the function that takes Alice and Bob's private info as input, and produces the public transcript as output, must be a one-way function if the scheme is to be secure and if it always negotiates a shared key. If it sometimes fails, then you don't necessarily get a OWF; you get a function which can be turned into a OWF, but it's more complicated. Assuming that either Alice or Bob knows if it succeeded, you can make this construction work.

It should be pretty clear why the nonexistence of OWFs implies that you can, given a transcript, compute a possible set of private info for Alice and for Bob that gives that transcript. In comments, you suggested many inputs giving the same transcript but different keys. This is impossible if, after the protocol, either Alice or Bob knows if they successfully negotiated a key or not (and the other one doesn't think they know but actually have it wrong). In that case, any two inputs that lead to successful key exchange and produce the same transcript must negotiate the same key.

Each party has private information for any particular run; it's just whatever secret they had, plus the result of every single coin flip that happened during that run of the protocol. We can specify this in advance; if you need more coin flips than are in the private information, the algorithm just fails. Then at any step, whatever message is sent is a deterministic function of the transcript so far and the private information the sender has (all randomness got embedded in the private info). Also, include whatever check you're doing to verify key exchange worked in the protocol.

Suppose the set of private info $A_0,B_0$ and the set $A_1,B_1$ produced the same transcript. WLOG, Alice sent the first message each time. Consider what happens with $A_0,B_1$; we want it to be the same transcript as well. Alice sends the first message again; this is based only on $A_0$, so it's the same as the first message there. Now, suppose the first $k$ messages are the same in this new transcript as in $A_0,B_0$. Alice has exactly the same information as after the first $k$ messages in $A_0,B_0$, so she does the same thing (either doesn't send or sends the same message as there). Bob has exactly the same info as after $k$ messages in $A_1,B_1$, so does the same thing he did there. As the transcripts of $A_0,B_0$ and $A_1,B_1$ are the same, Bob did the same thing in the latter as in the former, so after message $k$, Alice and Bob behave the same as they did in $A_0,B_0$. So the first $k+1$ messages are the same if the first $k$ are. So, $A_0,B_1$ produces the same transcript as $A_0,B_0$.

Alice now computes a key from $A_0$ and the transcript. She can't know whether Bob had $B_0$ or $B_1$, so the key is the same. Likewise, Bob can't know if Alice had $A_0$ or $A_1$, so he produces the same key as $A_1,B_1$. If Alice and Bob know whether or not key exchange was successful, and Alice knew $A_0,B_0$ led to successful exchange, then she also knows $A_0,B_1$ did. That means the key from $A_0,B_0$ is that from $A_0,B_1$ is that from $A_1,B_1$. The only other option is that $A_0,B_1$ failed; in that case, Alice did not know it failed, so she doesn't ever know if her key exchange succeeded or failed.

The reason one party has to know if it succeeded or failed in this proof is that that's how we get that $A_0,B_1$ necessarily succeeded. It may be possible to prove that without someone having to know, but even without that, just extend the private info to contain the actual message being sent (e.g. if it's a one-way message, then Alice has it in her private info and the negotiated key is really the message itself). If the proof doesn't work because neither one knows, then that means neither Alice nor Bob knows whether or not Bob got Alice's message correctly, which is a bit of a problem.


Whats wrong with my El Gamal signature example

In general case, $k^{-1}$ is equal to $x$ such that $x \cdot k=1$. In your question, to computing $11^{-1}$, you must find $x$ such that $x\cdot11=1 \pmod {8368}$. You can compute $x$ by using the extended Euclidean algorithm.


RSA: Is possible get p and q from this d and n?

I'll assume that $p$ and $q$ are prime.

Here's one approach to recover them

Step 1: recover $l = d^{-1} \bmod n$
Step 2: select a random $x$ and compute $y = x^l \bmod n$

Here's why such a $y$ is interesting.

We have $y \equiv 1 \pmod q$ (because $l$ is a multiple of $q-1$); similarly, we have $y \equiv 1 \pmod p$.  However, if we consider $y \bmod p^2$, the group order of $\mathbb{Z}^*_{p^2}$ is $p(p-1)$; $l$ is unlikely to be a multiple of that (and will never be if $p$ and $q$ are the same size), and so we have (with great likelihood) $y \not\equiv 1 \pmod{p^2}$

Step 3: compute $z = \gcd(y-1, n)$

$y-1$ is a multiple of $pq$, but not a multiple of $p^2q$, hence $z$ will be $pq$.

Then, it's trivial, $p = n/z$ and $q = z/p$

Now, the above might not work if the prime values $p$ and $q$ were deliberately selected to have $y \equiv 1 \pmod n$ consistently.  However, we have another method:

Step 2': set $l_0, k$ such that $l_0 = l / 2^k$ is odd
Step 3': select a random $x$ and compute $y_0 = x^{l_0} \bmod n$
Step 4': for $i := 0 .. k-1$

Check if $x_i = 1$; if so, fail (and go back to step 3' and select a different x)

Check if $\gcd(x_i - 1, n) \neq 1$; if so, that gives you a nontrivial factor of $n$ (and return success; completing the factorization should be straight-forward)

Otherwise, compute $x_{i+1} = x_i^2 \bmod n$

Here's how the above works; we know that we'll have $x_k = x^l \bmod n = 1$, and so $x_i \bmod p$ and $x_i \bmod q$ will both become 1 at some point in the computation; however it is likely that they'll become 1 at different points in the process; that is, one of them will become 1 first (and if so, the gcd will catch it)


Would the encryption of bigrams and trigrams weaken the code?

What you essentially do is compressing the plaintext before encrypting it. If the rotor machine offers a secure encryption, it should be secure for any type of input, including the compressed one. There is, however, a caveat: The ciphertext leaks the length of the plaintext and if you compress the plaintext, you change its length and therefore change what is leaked. Depending on how the encryption is used, this can actually cause problems. See this question.


How to mutually share values without influencing senders

What you want is a commitment scheme.
Typically these are a pair of functions $c(m), v(c,m')$ where the first creates a commitment (while not leaking information on $m$) and the latter verifies a commitment against a message.

Let $c(\cdot)$ be such a committing algorithm, then you can use the following protocol:

\begin{align}
A\to B:\quad &c(a)\\
B\to A:\quad &b\\
A\to B:\quad &a
\end{align}

In this case, A doesn't know $b$ when sending $a$, and B doesn't know $a$ when sending $b$. When A then sends $a$, B can verify that this $a$ is indeed the $a$, A commited to earlier and thus that it wasn't chosen in dependence of $b$.


Using ChaCha20 as a PRNG with a variable-length seed

Davies–Meyer?  That would be a very unusual way of seeding a PRNG.  The standard way of entropy extraction is to use a vetted hash algorithm such as SHAx.  I'm not quite sure how you want to use your RNG, and I'm having trouble deciphering how many bits of what you want.  I'm going to assume that you simply want 256 bits of entropy to inject into the state.

Having an entropy source available changes things somewhat compared to a plain PRNG. You don't need a key or a nonce in this case.  You'd collect 128 bytes from your entropy source.  It's twice 64 as NIST recommend that you double the input entropy for each bit of output entropy when using a hash based extractor.  Then run it through SHA256 and inject into ChaCha in place of the nonce and key.

Further I'm also assuming that this is to be only a PRNG.  With seeding from a true entropy source, you won't be able to repeat the output sequence.  Intuitively it feels wrong to use a PRNG to self seed, but I can't demonstrate this mathematically.  Follow the hash route as it's the obvious way, well proven and likely to be simpler than rolling your own recursive version of Davies-Mayer.


Can we have Rijndael s-boxes constructed using reducible polynomials?

As noted by poncho in the comments to your previous question, the Rijndael S-box is defined based on the multiplicative inverse of the input byte in a particular representation of the finite field $GF(2^8)$, where the representation is defined by the choice of the reduction polynomial.

However, in order to represent a finite field using addition and multiplication of polynomials modulo some reduction polynomial, the reduction polynomial must be irreducible.  If it isn't, the resulting algebraic structure will not be a field, and in particular, not all non-zero elements will have multiplicative inverses.

Of course, you could simply dispense with the finite field inverses entirely, and just construct your S-box in some other way.  As the Rijndael authors note in section 7.2 of the Rijndael AES proposal:

  Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an S-box that is “average” in this respect is likely to provide enough resistance against differential and linear cryptanalysis.


A standard approach in cryptography is to separate out the ideal specification (of what a scheme is supposed to achieve) from the particular instantiation (the implementation of the scheme).

To specify the security and functionality goals, sometimes cryptographers specify an "ideal functionality", which is an idealization of what we are hoping to achieve.  Then, one designs a specific instantiation -- a particular scheme -- and proves that the scheme meets the goals set out in the "ideal functionality".  We describe this by saying that the scheme securely realizes the ideal functionality.  How to prove that is another can of worms entirely... but that's what is meant by the terminology.

This kind of approach and terminology is common in, for instance, theoretical work that adopts an "ideal world/real world" formalization (including, e.g., simulation-based security; indifferentiability; universal composability; and other lines of work in cryptography).  See Wikipedia on universal composability for a high-level introduction.


As Maeher & Codesinchaos noted you're going to want to look into Zero Knowledge protocols.
Matt Green at Hopkins wrote an easy to understand blog article that gives you one such example w.r.t. mental poker Poker is hard.
Claude Crepau wrote a fair amount in the 80s and 90s about zk/mental poker; here is a link to one paper A zero-knowledge Poker protocol that achieves confidentiality of the...

Simari has a good primer on zk here:A Primer on Zero Knowledge Protocols


The security of adding random noise many time pad

Too tricky for a comment...

Conceptually, your scheme is 110% information theoretic secure, as it's a one time pad($ \downarrow $). But since we tend to use octet based computer architecture these days, $  \mathbb{Z}  $ is more appropriate.

Note 1. Ensure $ |r| \ge |v| $.

Note 2. Don't want to patronise, but the one time pad is thee most contentious and misunderstood aspect of cryptography ever invented. Especially on this forum. Is $r$ truly random or just pseudo-random? It's worrisome that I read 'generate' in a kinda algebraic context...


Difference between lightweight, online and low memory Authenticated Encryption schemes

Thought I'd begin with some references for you that might be of interest. These terms are used as key 'selling points' for a number of schemes, including many of the CAESAR submissions. Some examples using the terms specifically are given below - most of which are from CAESER because I have the zoo in-front of me:

"Online": OCB, Ascon, CBA, APE, NORX
"memory-constrained devices": Ketje / Keyak / Spongewrap,
"lightweight": PRESENT, JAMBO, APE, BLINKER (presented CT-RSA14)

Also, there was an eCrypt report on Lightweight crypto.

I can't provide a decent distinction between the 1 & 3, since low memory footprint is a more specific sub-aim of lightweight. Both of these are types of schemes designed to be run in highly restricted environments, such as on embedded devices. These often have constraints that actually affect what operations you can/cannot run on them, such that more efficient algorithms than an AES-based mode may be preferred.

Online AE deals with something completely different. Let A be some associated data, $M=(M_1,\dots,M_n)$ a message, encrypting to $C=(C_0,\dots,C_n)$ and tag $T$. The scheme is online if $C_i$ can be calculated without knowledge of $M_j$ for any $j>i$.

Often lightweight or small footprint ciphers are 'online'. This is because it allows them to process plaintext blocks as they come through. In contrast, an offline cipher would have to collect the complete plaintext before calculating the ciphertext, which means it must have enough memory to store $n$ blocks of data, which not all devices will do - especially for example a small industrial sensor reporting on large amounts of data.

Recently there has been some controversy about the validity of an online decryption function, since they release unverified plaintext (for example, see the CAESER mailing list or this paper). For categorization of some schemes under development, see here.


Hash functions with or without secret key

The parameter $k$ appeared in the definitions of hash functions, since many properties are difficult to formulate for a single concrete hash function. For instance, what would it mean that SHA-256 is collision resistant? Clearly, there are values that collide, and there exists a very short algorithm that outputs a collision in a small constant time. To meaningfully define collision resistance, theoreticians started talking about infinite families of hash functions
$$
H = \{H_k\,|\,k\in \mathbb{N}\},
$$
so that the family $H$ is collision resistant if an adversary needs to spend asymptotically $O(2^{n/2})$ time to find collisions for $n$-bit hash function from the family. Though the definition becomes sound, it does not help in practice since it is hard to expand the single SHA-256 to an infinite family of functions.

This parameter $k$, introduced solely to simplify the theory of hash functions, is often confused with a secret key. A hash function might take a key $K$ as an input, usually to form a message authentication code (MAC). A MAC should be difficult to forge, i.e. it is hard to find $M$ and tag $T$ such that
$$
H(K,M) = T
$$
without knowing $K$ (but knowing tags for other messages).

To answer your questions now

Whenever you need a collision-resistant hash function you choose a concrete function according to your security requirements and environment restrictions. You do not bother about families, they are for theoreticians.
It is usually MAC, but can also be a key derivation function. Usually MACs are not called hash functions (with key). When we talk about hash functions with key, it is quite often a usual hash function with part of its input made secret.


Is ciphertext stealing important in relation to Blowfish?

Ciphertext stealing doesn't bring you any security benefits, although – if you're hell-bound on using CBC mode – it could avoid padding oracle attacks. Otherwise it is just a way to avoid padding the plaintext and therefore increasing the ciphertext size in CBC mode.

Ciphertext stealing is independent of the block cipher used. So you could use it with 3DES, Blowfish or indeed AES in CBC mode. It's also available in ECB mode but ECB mode itself is not considered secure.

Blowfish is not an interesting alternative to AES. Even Bruce Schneider, the principal engineer of the cipher, recommends against using Blowfish. Although it hasn't been broken its 64 bit block size makes it an uncomfortable fit to most modern modes of operation, especially those that use CTR underneath.

When using messaging you should probably have a look at AES/GCM or another mode of authenticated encryption. Ciphertext stealing is not that interesting, just use something based on counter mode such as GCM. CTR and most other modes of operation do not require padding nor ciphertext stealing.

Choice of the block cipher isn't that important; creating a secure protocol is much harder. Then you can drop in any modern, secure block cipher you want. To play it safe, just use AES.


Why restrict nonce/IV and counter to specific sizes?

The answer is that you can do exactly what you say. Initialize the counter to a random 16 byte number and start counting. Wikipedia (not sure if that is where you got the idea that it must be 8 bytes and 8 bytes) has the following note:

  The IV/nonce and the counter can be combined together using any lossless operation (concatenation, addition, or XOR) to produce the actual unique counter block for encryption.

There is some benefit to separating things though. For example, splitting it into 8 bytes and 8 bytes, as long as you never generate the same 8 byte nonce/IV while using the same key, your encryption stream will never repeat. Further, you know exactly how many nonces/IVs you can generate before expecting to see a repeat ($2^{32}$ from the birthday paradox) with about a 0.5 probability. In a submission to NIST by some very reputable cryptographers, this method of doing CTR mode was called "the recommended usage scenario".

Lets instead assume you generate a 16 byte nonce/IV and just start incrementing it. What happens if two nonces/IVs have a difference of 1000 (i.e., $|n_1 - n_2| = 1000$). Well, after encrypting 1000 blocks (with the same key) you will now be using the same encryption stream. Analyzing this is a bit more tricky as you need to know the probability of generating two nonces that are within some range of each other (the range being determined by how many blocks you will encrypt). Depending on the application this could be a major problem. My guess though is that in the majority of applications it isn't a problem.


Why does the Secure Remote Protocol have resistance of dictionary attack?

The property of SRP is that:

If the attacker is a passive listener to an exchange between a client and a server, he learns nothing about the shared password
If the attacker is a participant in the exchange with either a client or a server with the password (or modifies the exchange between the client and the server), the attacker learns nothing except for the validity of one password.

What you point out is that, if the attacker mimics the server, he can check on a single guess to the password.  There is a similar attack if the attacker mimics the client; he takes this guess at the password, and runs through the protocol with his guess; if he succeeds, his guess was correct.

Why do we accept such a vulnerability?  It's because it is inevitable given the assumptions.  For any protocol whose sole authentication is based on a shared password, the attacker could always take his guess at the password, and run the protocol with someone with the valid password.  If it succeeds, his guess was right.

Now, why is this vulnerability considered acceptable?  Well, if the attacker's dictionary contained one million entries, then this would require one million exchanges with someone.  This is considerably more costly then being able to do one (or several) exchanges, take the results, and then use a GPU farm (or botnet) to attack it offline.


Collision resistance of hash function built on modular exponentiation

sReduction to RSA
Let $\mathcal C\colon \mathbb Z \times \mathbb Z \to \mathbb Z \times \mathbb Z$ be a collision-finding oracle giving $(x, x') = \mathcal C(n, y)$ such that $x \ne x'$ and $y^x \equiv y^{x'} \pmod n$, with some probability $p$ given some distribution on RSA moduli $n$ and integers $y$.  For any positive odd $e$, define $\mathcal R_e\colon \mathbb Z \times \mathbb Z \to \mathbb Z$, a root-finding algorithm giving $m = \mathcal R_e(n, c)$ whenever  $\gcd(e, \lambda(n)) = 1$, which succeeds if $\mathcal R_e(n, m^e \bmod n) = m$, as follows:

If $c \in \{0,1\}$, return $c$.
If $\gcd(c, n)$ is a nontrivial factor of $n$, exploit it for ordinary RSA private-key computations and stop here.
Compute $(x, x') = \mathcal C(n, c)$ with $x \ne x'$, $c^x \equiv c^{x'} \pmod n$.  (If not, fail.)
Compute $\delta = (x - x')/e^i$ so that $\gcd(\delta, e) = 1$.  (I.e., divide off all factors of $e$.)
Compute $d \equiv e^{-1} \pmod \delta$ with the extended Euclidean algorithm.
Compute and yield $c^d \bmod n$.

Why does this work?
Let $c = m^e \bmod n$.  If $c$ is neither zero nor a nontrivial factor of $n$, then $c \in (\mathbb Z/n\mathbb Z)^\times$.  Since $c^x \equiv c^{x'} \pmod n$, we know $\operatorname{ord}_n c \mid x - x'$.  Further, since $\operatorname{ord}_n c \mid \lambda(n)$ and $\gcd(e, \lambda(n)) = 1$, we must have $\gcd(e, \operatorname{ord}_n c) = 1$, and thus $\operatorname{ord}_n c \mid \delta = (x - x')/e^i$.  Now $\gcd(e, \delta) = 1$, so that $e$ is invertible modulo $\delta$, with inverse $d$.  Since $ed \equiv 1 \pmod \delta$, we can conclude $\operatorname{ord}_n c \mid \delta \mid ed - 1$, i.e. $ed \equiv 1 \pmod{\operatorname{ord}_n c}$.  Thus $c \equiv c^{ed} \equiv (c^d)^e \pmod n$, and since $u \mapsto u^e \bmod n$ is a permutation of $\mathbb Z/n\mathbb Z$, $c^d \equiv m \pmod n$.  (Note that $d$ is not the inverse of $e$ modulo $\lambda(n)$, or even modulo the order of $m$: we may need to use a different $d$ for each ciphertext $c$.)
This root-finding algorithm $\mathcal R_e$ succeeds with the same probability as the collision-finding oracle $\mathcal C$, and handful of arithmetic: a GCD with $n$, a few divisions by $e$, an extended Euclidean algorithm, and a modular exponentiation.  If the collision-finding oracle works uniformly on all elements of $\mathbb Z/n\mathbb Z$, then the root-finding algorithm works uniformly to decrypt all RSA ciphertexts in $\mathbb Z/n\mathbb Z$.  But if it is restricted to quadratic residues, which appear with probability $(p + 1)(q + 1)/4pq$ in a uniform distribution on $\mathbb Z/n\mathbb Z$ for $n = pq$, then so is the root-finding algorithm.
So it's not clear to me why this is restricted to quadratic residues: the reduction works better if not restricted!
Reduction to factoring
Let's take a simpler case first.
Suppose for $n = pq$ that $p = 2p' + 1$ and $q = 2q' + 1$ are safe primes, i.e. $p'$ and $q'$ are prime too.  Then $\lambda(n) = 2p'q'$ for primes $p'$ and $q'$ nearly the size of $p$ and $q$, so the only possible orders modulo $n = pq$ are $$\{1,2,p',q',2p',2q',p'q',2p'q'\},$$ and for a quadratic residue $y$, the only possible orders of $y$ are $$\{1,p',q',p'q'\}.$$  Thus, except for $1$, the order of every quadratic residue is either $p' = (p - 1)/2$, $q' = (q - 1)/2$, or $p'q' = \lambda(n)/2 = \phi(n)/4$.  A collision $x \ne x'$ implies $\operatorname{ord}_n y \mid x - x'$.  As long as $(x - x')/\operatorname{ord}_n y$ is not too large, it is merely a small combinatorial search to factor $n$ from there.
But it's still not clear to me why you need the base $y$ to be a quadratic residue.  The combinatorial search is a little larger, but not much larger, if $y$ is an arbitrary element.  Indeed, for any modulus, as long as $y$ has large enough order, a collision is practically guaranteed to reveal factorization of $n$ either directly or via $\lambda(n)$.  Pick $y$ to attain the maximal order $\lambda(n)$, and factorization of $n$ from a collision $x \ne x'$ is even easier because $\lambda(n) \mid x - x'$, for any $p'$ and $q'$ whether prime or not.
Maybe picking maximal-order elements uniformly at random is not trivial in general—but quadratic residues never have maximal order, and when $p$ and $q$ are safe primes, any uniform random element works except with negligible probability ($\pm1$).
Related constructions
A nearly more general theorem was proven by Pointcheval (Thm. 4, p. 117) for any modulus $n$ where the prime factors of $p'$ and $q'$, and the order of $y$, all exceed $\alpha$—with the caveat that $y$ must be asymmetric, meaning that its order has opposite parity modulo $p$ and $q$, so it is not quite a generalization.  This leaves open the question of what the distribution of the order of $y$ or $y^2$ is under uniform random $y \in (\mathbb Z/n\mathbb Z)^\times$, and whether it is below $\alpha$ with negligible probability.
Shamir and Tauman proposed a similar collision-resistant hash function for a base $y$ of maximal order modulo a product of safe primes, although it is defined on $\mathbb Z/n\mathbb Z \times \mathbb Z/\lambda(n)\mathbb Z$ rather than on $\mathbb Z/\lambda(n)\mathbb Z$: specifically, it sends $$(m, r) \mapsto y^{2^{\lceil\lg\lambda(n)\rceil}m + r} \bmod n.$$
But none of these involves quadratic residues, and in two minutes of skimming I couldn't find any relevant literature that does involve quadratic residues, other than the seminal GMR signature scheme (paywall-free link) that works rather differently.
In an answer to an earlier related question on the difficulty of finding high-order elements, poncho concludes that an oracle to compute the order of an arbitrary element $y$ modulo $n$ is enough to factor $n$, by finding a nontrivial square root of unity using the odd part of the order of $y$.  But there is a gap in applying it here: if the order of $y$ is odd, as it must be if (e.g.) $p$ and $q$ are safe primes and $y$ is a quadratic residue, the attack doesn't work, because we cannot necessarily construct such an order-finding oracle from a collision oracle in case the collision oracle always returns $x$ and $x'$ differing by an odd integer.
(On the other hand: maybe it works to test, for $i = 0, 1, 2, \dots$ until you pass $2^i > n$, whether $z^{2^i (x - x')} \not\equiv \pm 1 \pmod n$ and $z^{2^{i+1} (x - x')} \equiv 1 \pmod n$, in which case you have a nontrivial square root of unity so that $n \mid (z^{2^i (x - x')} + 1)(z^{2^i (x - x')} - 1)$ from which $\gcd(n, z^{2^i (x - x')})$ recovers a nontrivial factor of $n$.)


Diffie-Hellman server/client generated secret size

The issue is plain and simply: JavaScript sucks.

In this particular case the issue is that JS has no integer type, so everything is stored as a double. In particular the last calculation $13^{16}$ would yield a 60-bit integer which JS computes as ordered. However double only has 52 bits for the mantissa and so can't possibly contain the full value. So JS rounds. Then it takes the rounded number and applies the $\bmod 23$ reduction yielding some unrelated value to the one you intended to compute.


How exactly is the output of the XOR step in PBKDF2 used?

So, I've been interested in building a diagram myself, and I find your diagram slightly misleading. I don't know if it's a mistake, or intentionally hiding specific pieces of the algorithm, but I think it could benefit from more granularity.

According to RFC 2898, the algorithm is as follows:

Take the ceiling of the division the desired key length (dkLen) by the digest size. This will give you the number of intermediate keys to concatenate at the end.

So, for a 512-bit key, using HMAC-SHA-256 as the hashing function, we will only need 2 intermediate keys to concatenate, each 256-bits in size:

CIEL(512/256) = 2

For each intermediate key T_i, apply F(P, S, c, i), where F() is a generic function defined below, P is your password, S is a salt, c is the number of rounds, and i is the intermediate key index.

Thus, T_1 = F(P, S, c, 1), and T_2 = F(P, S, c, 2). The final key will be those concatenated:

T = (T_1 || T_2) = (F(P, S, c, 1) || F(P, S, c, 2))

F() is defined as the exclusive-or sum of the first c iterates of the underlying pseudorandom function applied to the password and the concatenation of the salt and the block index i.

Thus, F(P, S, c, 1) = U_1 XOR U_2 XOR ... U_c and F(P, S, c, 2) = U_1 XOR U_2 XOR ... U_c. In other words, each intermediate key is processed with c rounds. Thus, for 2 intermediate keys, we are doing 2c rounds to build the final key. Generically, for n-intermediate keys, we are doing n*c rounds to build the final key.

U_i is defined as the most granular function, giving us the interface to the pseudorandom hashing function. U_i is processed c times using its previous output as the "salt" for the next input

Note that at the first round, we concatenate the intermediate index counter to the salt, thus ensuring that U_1 is always unique for each intermediate key.

U_1 = PRF(P, S || i)
U_2 = PRF(P, U_1)
...
U_c = PRF(P, U_c-1)

So, if we specificed c=100, then:

T_1:
  U_1 = PRF(P, S || 1)
  U_2 = PRF(P, U_1)
  ...
  U_100 = PRF(P, U_99)
T_2:
  U_1 = PRF(P, S || 2)
  U_2 = PRF(P, U_1)
  ...
  U_100 = PRF(P, U_99)

Finally, concatenate the intermediate keys, producing the desired key length:

T = T_1 || T_2

Thus, in your diagram, I think you should specify that "PRF" is doing c-rounds of XOR with to produce the intermediary key.

I think this flowchart might be a bit more thorough:


Why 3 round Feistel cipher are not common

The main issue is that this only holds if you start with a PRF. Constructing a secure PRF is just as hard as constructing a secure strong PRP, so haven't gained much. In practice we typically start with constructing a PRP and then turn it in into a PRF, not the other way round.

Feistel based blockciphers use many rounds, because their round functions are individually weak but also faster than a PRF.

In addition we typically want a strong PRP, so you need at least four rounds, not three. Another limitation is that the block size must be big enough for the target security level (IIRC you need 2n-bit blocks for n-bit security while we often target a security level equal or higher than the block size (e.g. AES has 128-bit blocks and 128/192/256-bit keys with the security level matching the key size).

There is one area where Feistel constructions using a small number (two to four) strong round functions are popular: Large and variable width permutations. OAEP is based on a two round feistel structure. There is the EME mode for wide block encryption.


Is rainbow table attack applicable to any hash?

Rainbow tables are a size optimization of lookup tables at the cost of time. This is the typical time/memory tradeoff found everywhere in computer science.

However, hash functions themselves are not really susceptible to rainbow table attacks. Rather, it's a specific use of a hash function that may (or may not) be susceptible to rainbow tables. And, even then, rainbow tables are used essentially for finding pre-images of hash functions; e.g., given $H(x)$, find $x$.

For example, suppose you are using a hash function to store the fingerprints of files---just files in general. If you allow sufficiently large files to be stored, say, then this scheme is not going to be very susceptible to rainbow tables: the 'space' of possible inputs to the hash function is just going to be too big to generate a useful rainbow table. You might be able to do it for some subspace, which may or may not be useful, but probably not. The point is that: (1) there are many possible inputs, so many that the table would be huge to be exhaustive, and (2) "all files" is rather general, and while some files are undoubtedly more common than others, this statistical bias is not really well-known.

On the other hand, if you are doing password hashing with the naive "just hash the password", then the space of possible passwords is rather small (for most services), and, most importantly, the distribution of passwords is very non-uniform. A password like 123456 is vastly more common than AvdJv89}{. Hence, you can generate a rainbow table with the top X most common passwords and get significant "coverage" with the table. Given that the goal of password hashing is to keep plaintext passwords out of the hands of attackers for as long as possible, this is quite bad, especially given that the users who are using passwords like 'password123' are probably going to be doing similar things for other services. Thus, with rainbow tables against password hashes, the real idea is to hit the weakest X% of users. That one user with a 48-char password is probably security-conscious enough that it's not worth the effort to break his password, so attackers are mostly interested in users whose passwords are insecure. And, at any rate, that assumes the service allows long passwords; my university allows only up to 24 characters for whatever reason.

This attack is possible really because the preimages we are interested in are (1) few in number and (2) highly biased towards certain preimages. Also, crucially, we already "know" the most common inputs to the hash function. This is why "salting" passwords breaks the rainbow table attack: the random "salt" prevents us from knowing the common inputs, since now there's a salt being sent into the hash function too. If it is a "global" salt and is known to the attacker, then the attacker can generate a rainbow table that uses the 'salt' (a 'pepper' more accurately). But for the case of a real per-user random salt, rainbow tables aren't a possible line of attack.

To answer your question more directly, all of the generic cryptographic hash functions are vulnerable when used in a vulnerable way: MD5, SHA1/2/3, etc. On the other hand, the popular key derivation functions of today (PBKDF2, bcrypt, scrypt) are not vulnerable because they use a salt internally. (Also, for properly-tuned KDFs, the generation of a useful rainbow table would take a very, very, very long time even if a salt weren't used.) The faster the hash function, the faster the rainbow table can be generated, so MD5 is "less secure" against rainbow table attacks in that sense than SHA2.

Keep in mind that the whole point of a rainbow table is to pre-compute values to make finding preimages fast. If you can't predict the preimages you're interested in, then the whole attack is foiled.


Sieving the sequence $x^2-n$ to recognize b-smooth numbers

The statement "To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2−n$ giving a perfect square" is incorrect is only a subset of a possible more general definition: looking for a product of numbers $x^2-k\cdot n$ giving a perfect square (by restricting the numbers to be suitably smooth, factoring them, and using some equivalent of Gaussian elimination to form the product so that the multiplicity of every prime in its factorization is even). Introducing $k$ allows more freedom in the search (but is seldom used in practice).

The definition of QS used in reference [1] is identical to that in Wikipedia. It is looking for smooths of the form $x^2\bmod n$. That falls under the more general definition of QS that I give, since $x^2\bmod n$ is $x^2-k\cdot n$ with $k=\Big\lfloor{x^2\over n}\Big\rfloor$.

The issue encountered in the question is that the sieving algorithm used finds $x$ such that $x^2-n$ is smooth; but when $x$ exceeds $\sqrt{2n}$, that sieving algorithm no longer is sieving $x^2\bmod n$.

Options to fix this

Sieve only $x^2-n$, including when that exceeds $n$; and use $x^2-n$ rather than $x^2\bmod n$ everywhere else. Problem is, the density of suitable $x$ decreases as $x$ grows. Also, that's not an option for large $n$, since sieving even a fraction of $(\sqrt2-1)\sqrt n$ values is way too long.
Sieve only $x^2-n$, but use a larger factor base. That increases the number of relations to be found, but increases the number of smooths retained even more, so that the required number of relations will be reached sooner.
Sieve $x^2-k\cdot n$ for several values of $k$. For example: until there is enough smooth collected, and for $k$ from $1$ onward, sieve $x^2-k\cdot n$ for smooths, varying $x$ from $\Big\lceil\sqrt{k\cdot n}\Big\rceil$ to $\Big\lfloor\sqrt{k\cdot n+m}\Big\rfloor$ for some bound $m$. That matches reference [1] when the bound $m$ is set to $n$. That could be viewed as an overly naive Multiple Polynomial Quadratic Sieve.
Sieve integers of the form $(a\cdot x+b)^2-n$, with $(a,b)$ chosen appropriately, in particular such that $(a\cdot x+b)^2-n$ is divisible by $a$ (allowing $a$ as a factor, if it does not belong to the factor base). This is what actually used variants of the Multiple Polynomial Quadratic Sieve do. The multiple polynomials allows to remain in the region where the un-factored part of what's sieved is small, so that the rate of finding smooth does not become vanishingly small. One advantage compared to the previous solution is that the factor base used for sieving is the same for all the polynomials used, see this question.

There are several other, independent optimizations of QS; including:

Allow what's sieved to be negative, and include $p_0=-1$ in the factor base.
Actually factor $m\cdot N$ for some small $m$ chosen to optimize the yield of the factor base.


Is modular Barrett reduction usable for Ed25519?

Note that $q = 2^{252} + n$ for $n < 2^{125}$.  Consequently, $2^{252} \equiv -n \pmod q$, so $$2^{504} \equiv (2^{252})^2 \equiv (-n)^2 \equiv n^2 \pmod q.$$  Since $n^2 < 2^{250}$, you can reduce $$2^{504} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod q.$$  Since the original input was only 512 bits long, $x_{\mathrm{hi}} < 2^8$, so we can set the bound $$n^2 x_{\mathrm{hi}} < 2^{250} 2^8 = 2^{253} < 2^{253} n + n^2 = q^2 - 2^{504},$$ which puts the reduced sum $n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} < q^2$ in the range of Barrett reduction.


Default mode of operation in TLS cipher suites

If you look at the official list, you'll see that the official cipher suite name always has the mode explicitly stated; each AES-based transform is explicitly called out to be CBC, GCM or CCM.

Going through the OpenSSL source code, we find that the ciphersuite you cited has the value 0x00, 0x37, that is, TLS_DH_RSA_WITH_AES_256_CBC_SHA.  Hence, CBC is the mode being implicit.  I suspect this is implicit because OpenSSL predates TLS 1.2; in TLS 1.1 and prior, CBC was the only block cipher mode allowed (and hence there was no need to call it out); once the started supporting TLS 1.2, they didn't feel like they should go back and modify the name strings they used for existing ciphersuites.


The length of the shortest vector in Lattice

Remember that we are considering $q$-ary lattices, as defined by

$$ \Lambda^{\perp}_q(\mathbf{A}) = \{ \mathbf{y} \in \mathbb{Z}^m : \mathbf{A} \mathbf{y} = \mathbf{0} \mod q \}. $$

Clearly the vector $(q,\mathbf{0})$ is in this lattice, and has length $q$. This is a trivial, uninteresting solution, as it doesn't give a better understanding of the lattice.

$\min \{ q, 2^{2 \cdot \sqrt{(n\cdot \log{q} \cdot log{\delta})}} \}$ refers to the shortest vector one can find using (then) state of the art lattice reduction algorithms. If you're choosing parameters in order to make a cryptographic scheme secure, you are trying to ensure that the shortest non-trivial vectors that can be found are not very short. If trivial vectors break your scheme, it is broken anyway, and no amount of parameter tweaking will fix it.