How to configure Argon2d for commodity hardware?

The first thing to note is that KeePass uses Argon2d which is the Argon2-variant with data-dependent memory access.

Now it's best to (roughly) follow the guidelines lined out in the Argon2 specification (RFC draft):

Figure out the maximum number h of threads that can be initiated by each call to Argon2._ This means you should set the parallelism value to match your physical core count, ie 2 if you have a dual-core, 4 if you have a quad-core, ... You should double this value if you have (true) hyper-threading enabled on your CPU.
Optional: If you want to use the key-derivation on a lower power device (such as your phone), you need to figure out first how much RAM it has available during average use. This will be your upper limit for memory usage.
Optional: If you have less than 8GB of RAM on your machine, figure out how much is available during average use. The minimal value of this and the previous point will be the upper bound for memory.
Pick an iteration count between 1 and maybe 5. The higher you pick the harder it is for an attacker to reduce the memory required. Analysis suggests that low, single digit values are good, but going slightly higher should increase the penalty when trying to reduce memory usage. But do not higher this value indefinitely because while it would increase the penalties for reducing memory for an attacker, it could very well make the difference between you using 25MB and 500MB of memory and 500MB with "medium" penalties for reduction is likely going to be much worse for an attacker than 25MB with "high" penalties for reduction.
Figure out the actual memory usage parameter. To do this you pick a rather low value like 100MB or a tenth of your maximal budget and test how long it takes. If it takes not long enough increase the memory usage. The used time will roughly scale linear with the memory usage, that is, if you double the memory usage, you will get a doubled time. You want to tweak this time value to your liking, but about 1 second is recommended for disk-encryption or password databases.
If you hit the maximal memory budget, don't go over it (thinks will end badly), but rather increase the iteration count now. Also note here that the used time will scale linear with the iteration count, that is, double the iteration count and it will take about twice as long.

Overall your parameters should take maybe one second for the computation on your intended usage machine where you have to unlock the database often.

So…

TL;DR:

Set the parallelism to your thread count (double the core count if you have hyperthreading), set the iteration count in the range 1-5 and set the memory usage as high as you can while staying within your time and memory budget.

thanks to axapaxa for pointing out that the thread count should be used.
thanks to Luis Casillas for pointing me to the RFC draft and making me improve this answer.


Add a pepper to a hash: as a string or a buffer, and should I calculate a hash of a peppered plain text?

To calculate a pepperedPassword I can either just concatenate two values:

Bcrypt limits the password. This means that if the password is too long (longer than 56 bytes), it will simply be truncated. If you just attach the pepper to the password, there is a high risk that this will happen. Then the pepper's security gain could even be lost without being noticed.

Use HMAC or even a hash function to combine a password and a pepper.

  Should I represent a PEPPER as a string or as a buffer?

That's up to you, but if you use HMAC or a hash function, it's obvious not to use a string.


Understanding the definition of polynomially CPA (IND-CPA) security

As explained on Wikipedia:

  The reciprocal-of-polynomial formulation is used for the same reason that computational boundedness is defined as polynomial running time: it has mathematical closure properties that make it tractable in the asymptotic setting. For example, if an attack succeeds in violating a security condition only with negligible probability, and the attack is repeated a polynomial number of times, the success probability of the overall attack still remains negligible.

Which is why you want it to work for all polynomial $p$ in your definition.

It is also important to notice that in this definition, it is implied that the adversary has a polynomially bounded computational power.

Which means basically that in the IND-CPA game, the adversary has the right to perform a polynomially bounded number of encryptions or other operations, before sending the two plaintexts to the challenger, which will choose one and return its encryption to the adversary, who must now guess to which plaintexts it corresponds.

Let me develop this with an example:
in the RSA-OAEP case, this forbids for instance the adversary to factor the public key using the GNFS since it has a complexity of :
$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right]$$
for factoring the number $n$, but we're usually interested by the security parameter, which, in RSA-OAEP case, is the $\lambda=\log_2(n)$ , but this is not a problem, since its running time is super-polynomial but sub-exponential in the size $\lambda$ of the input $n$:
$$O\left(\exp\sqrt[3]{\frac{64}{9} \lambda (\log \lambda)^2}\right)$$ so it is still not a polynomial algorithm and thus cannot be considered when studying the IND-CPA security of RSA-OAEP.

However, if factorization were to be proven polynomial, then the adversary would win the IND-CPA game in the RSA-OAEP case thanks to it.

PS: As mentioned below, plain RSA is not IND-CPA since it is deterministic.


About numberical comparison in Attribute based encryption

Is it true that the access policy only use "0" bit string? If yes, it is safe enough to encrypt the message with 2 attributes *0** and **0* (i.e., 1*** and ***1 are not needed)?

First off, a numerical attribute such as *0** is nothing more than the ASCII string "*0**" which is then hashed.

The following is a user's secret key:

$$\text{SK}=\left(D=g^{\left(\alpha +r\right)/\beta}, \forall j\in S:D_j=g^r\cdot H\left(j\right)^{r_j}, D^{'}_j=g^{r_j}\right)$$

All $r$ and $r_j$ are chosen randomly and independently which means that the attributes ($D_j$ and $D^{'}_j$) of a secret key are not linked together in any way.

A user can or the attribute authority can safely remove multiple attributes without invalidating the whole key. The remaining attributes can still be used to decrypt ciphertexts provided that the remaining attributes satisfy the access policy. This is true for (almost?) all schemes that utilize monotonic access structures as is the case with BSW-ABE.

However, this cannot be true for schemes that utilize non-monotonic access structures. Such access structures can be used to model negation of attributes. In such schemes, all attributes are linked together. If they weren't, then it would be possible for a use to remove a negated attribute and be able to decrypt more ciphertexts.

1*** and ***1 are not needed to satisfy the policy: a<11. However, if the attribute authority removes all attributes containing a 1, then it would limit the expressiveness of the access policy. Furthermore, access policies containing attributes with a 1 can be reduced to improve the policy evaluation performance.

  Do you know a reference that describes how the choice of gates are made?

This is off-topic. I don't know a natural language description of this, but you can certainly try to deduce the algorithm by looking at the code. cpabe has the original implementation of that in C and JCPABE has an extended implementation of that in Java.


Can frequency attack be successful on Vigenère cipher?

Yes, Vigenère cipher is vulnerable to frequency analysis.

BUT! It requires some pre-processing first.

I propose to walk us through a small example of how frequency analysis can help decrypting Vigenère cipher in order to get a better idea of the process.

Firstly, it is important to notice that if you were to choose a key length of 1, then Vigenère cipher becomes Caesar cipher, which is one of the best examples of ciphers sensitive to frequency analysis!

Let us consider the following ciphertext encrypted using Vigenère:

  Vyc qxgv gpdzfcdq pks yigimsp jm iaov tmbiivzlv foeygcxg erl exfhfpb mvgd ojbqmcw pgr uf rwth jlkpg pgzlvl qce scwstjrpgr vycb vzgrpar. O rimvkoodcg bg kucpeza rl tlgcpghm kjf udkyu ngia htrbxmwqeya tsukftmwe rls ewvvppkm hfpbl ou ncae ou dyiasorrxvon tmcvsrkq, ih qqdkjgwerrt mvg nyn mvck yc tzifpxmvo nmgdg ceb ih qqetxgqg r pttrgi rwth vyc gxgwcrh pwnc zt vcticrm.

If we were to perform a simple frequency analysis on it, we do not get really insightful information:

letter  occurrences  %
G           25      8.2%
R           21      6.89%
C           20      6.56%
V           19      6.23%
P           17      5.57%
T           16      5.25%
M           16      5.25%
I           13      4.26%
E           12      3.93%
O           11      3.61%
K           11      3.61%
Q           11      3.61%
W           10      3.28%
Y           10      3.28%
L           9       2.95%
F           9       2.95%
H           9       2.95%
D           8       2.62%
B           8       2.62%
X           8       2.62%
S           8       2.62%
Z           7       2.3%
A           7       2.3%
U           7       2.3%
N           7       2.3%
J           6       1.97%

On a total of 305 characters (not counting punctuation marks), we can see the raw frequency analysis is not helping on first sight, as it's far from matching English's frequency.

But, if we study the n-grams appearing in that ciphertext, we can notably see the following occurrences:

n-gram    occur.  positions
RWTH        2       74,278
HFPB        2       54,186
IHQQ        2       219,261
VYC         3       0,102,282
MV          5       58,116,232,238,250

Now, the positions of these repetitions is important, let us take a look at the distance between any two of them:

n-gram    positions     distances
RWTH        74,278      278-74= 204
HFPB        54,186          132
IHQQ        219,261         42
VYC         0,102,282       102, 180
MV    58,116,232,238,250    58, 16, 6, 12

Now, if we are to look at each of these distances, we can see that among all the common divisors there are between any two distances, the most common one is 6:
$\gcd(12, 42, 102, 132, 180, 204) = 6$

This allows us to infer the size of the key could probably be 6.

From there, we just need to split it into 6 columns (I mean in Python it would be [trimmed[i::6] for i in range(6)]) and consider each column as a single string encrypted using Caesar cipher! We thus get:

Vvcypvveehgmujgctvgrokacjutquevhuuonrqegciocqggvwnt
ygdijtzyrfdcflzejyridurpfnrekrvfndrtkdrnkfneeriycci
cpqgmmlglpowrklsrcpmcclgugbyflppcyrmqkryypmbtprcrzc
qdpiibvcebjpwpvcpbavgpthdixatspbaixcijtncxgixtwghtr
xzkmaifxxmbgtglwgvrkbelmkamtmekleavvhgmmtmdhgttxpvm
gfssoiogfvqrhpqsrzOogzgkyhwswwmoososqwvvzvgqqrhgwc

And now we can again perform a frequency analysis like we would for any Caesar cipher, but this time on each string independently:
Vvcypvveehgmujgctvgrokacjutquevhuuonrqegciocqggvwnt gives:

let.   occ.  %
V       7   13.73%
G       6   11.76%
U       5   9.8%

And we know that in English the frequency table goes as follows:

let.  %
E   12.02
T   9.10
A   8.12
O   7.68

Which means that since the most common letters in the English alphabet are E, T A and O, we can assume they are very likely represented by the most common letters in the cipher too. (Sadly, this won't work here for all 6 Caesar ciphertexts we got, and some require a better frequency analysis using more advanced tools such as cross-entropy or chi-squared tests...)

So, let us find in Vigenère matrix which column is using V for E or for T, G for T (or for E),  and U,C or E for A!
We find that if V is used for E, we would be in the case where key would be R and then G would match P, and U would be the matches for D, which doesn't really fit our frequency table for English...
But if V is used for T, then we would be in the case where the key is C, and then the cleartext for G would effectively be E! Now this latter case seems way more plausible, so we have probably found the first letter of the key: C.
Notice that in practice, instead of performing such deduction, we would typically use the graphs of the frequency of each letter under every 26 possible keys to find which one is the closest to the English distribution. (Well, in fact we would probably be computing the cross entropy between the English frequency and the frequency we obtain from our ciphertext when it is decrypted as a Caesar cipher for each letter of the alphabet and we would retain the letter that has the smallest entropy as our best candidate.)

If we do the same for ygdijtzyrfdcflzejyridurpfnrekrvfndrtkdrnkfneeriycci, we can find that the most probable shift would be for index 17, that is the letter R. But here it is not trivially done by hand anymore and I've relied on the
cpqgmmlglpowrklsrcpmcclgugbyflppcyrmqkryypmbtprcrzc gives Y when analysed in turn by frequency like Caesar cipher.
qdpiibvcebjpwpvcpbavgpthdixatspbaixcijtncxgixtwghtr gives in turn P.
xzkmaifxxmbgtglwgvrkbelmkamtmekleavvhgmmtmdhgttxpvm gives T (with I also a possibility).
Finally gfssoiogfvqrhpqsrzOogzgkyhwswwmoososqwvvzvgqqrhgwc will be a bit more of a problem: frequency analysis tells us it could probably be S, E, N, D, C or O ... What a pain! (However, notice cross-entropy is the lowest for O)

However, since we've greatly reduced the number of candidates, we can simply try all of them until our ciphertext decrypts using Vigenere decryption to an English text.

And this finally works here with the CRYPTO keyword and gives the following plaintext:

  The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.

(A quote by D.Knuth)


SHA-3 is not vulnerable to cache timing attack.

Only implementations could be vulnerable to timing attacks.

Also it is to be noted that cache timing attacks relate secret data and cache lines refreshed. This is again implementation dependent and could not be observed through Python script.


Short answer,
 - yes
 - yes
To be honest I don't really know how to give a longer answer.
He are some pointers
http://www.secg.org/download/aid-780/sec1-v2.pdf
http://digital.csic.es/bitstream/10261/32674/1/Gayoso_A%20Comparison%20of%20the%20Standardized%20Versions%20of%20ECIES.pdf


Several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier cryptosystem.

A worked example of the latter scheme:

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have:
$$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$
$$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$
$$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows:
$$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$
$$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$
$$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation:
$$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$
$$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$
$$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

EDIT: Thanks tylo for specific examples


Hash collision using the leading 40-bits of SHA-1

Ok, here's how it is supposed to work: we take the function (which maps a string of $n$ bits to a string of $n$ bits), and iterate it repeatedly.  After some amount of time, we'll run into a loop (that is, we'll evaluate to a value that we visited before, and there after, we'll repeatedly run through the loop).  And, we'll run the function iteration twice, with one of iterations running twice as fast as the other; what will happen eventually is that they'll both fall into the loop, and that the fast one will catch up with the slow one, and give us the collision (using somewhat more computation than other methods would, but using hardly any memory at all).

This is all well and good; the question is: how much computation do we expect.  Well, if the function acts like a random function (and SHA1 is believed to), we'll expect to hit a collision somewhere around $c2^{n/2}$ (for a value of $c$ not drastically larger than 1).

Ok, and so what's the value of $n$?  Well, you're feeding 160 bits into SHA, and using all 160 bits of SHA output in the next iteration, and so $n=160$ (and so this logic is unlikely to fall into a loop drastically earlier than $2^{80}$ iterations).

Now, during your comparison, you're comparing only 40 bits; however because it is unlikely you've fallen into a loop, you are effectively comparing random values; you might run into a collision, but with only probability $2^{-40}$ per comparison.  Hence, it's not at all surprising that you haven't found anything yet.

And, given all this, what is the correct fix?  Well, the obvious thing to do is to actually use $n=40$; that is, when you do your SHA1 computation, feed in only 40 bits (and not all 160).  That should fix your problem.


Does hashing require non-linear components as well?

Yes

  How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search?

You could find a preimage by solving for the preimage with linear equations; that is, for a linear function, each output bit is a linear function of the input bits.  We would express the entire output as a set of linear equations (with the preimage bits being the unknown), set the right side to be image we're looking for, and solve that set of linear equations, giving us the preimage.


Cryptography studies properties of information. Information, at least in discrete form (a sequence of bits) can inherently be duplicated. Inasmuch as a document conveys meaning, it can be expressed as a sequence of bits. If someone obtains a copy of the document, they can duplicate the sequence of bits and make other copies. It is impossible to prevent the copying of a document by cryptographic means alone.

It's also impossible to prevent making modified copies of a document. It is however possible to detect whether a copy of a document is pristine: this property is called authenticity, and it's one of the basic security properties that cryptography studies. Authenticity can be guaranteed by including a signature (which can be produced only by entities who know a particular private key and can be verified by anyone knowing corresponding the public key) or a MAC (which can be verified by entities who know the secret key that was used to produce the MAC).

While copies cannot be prevented, they can be made detectable through watermarking. Unlike authenticity, for which robust, generic solutions exist, watermark techniques are inherently tied to a particular medium (e.g. sound or video) and tend to be broken.

Protection against copying can be achieved by physical means (optionally in combination with cryptography). This is not always easy to achieve. In order to prevent copying, the information has to stay within systems that are under the control of the information holder. Properties such as “this information may not be copied outside a certain system” are known as digital rights management (DRM).

As soon as the information needs to be communicated to a human, it has to leave the controlled system. This is an analog hole, and cannot be prevented by physical means alone. There are two ways to mitigate the analog hole:

By physical means: the analog hole implies a quality degradation for some types of documents (e.g. filming a video in a cinema produces a lower-quality video — but technology is improving rapidly). Fundamentally, the analog hole represents a limit on the rate at which the information leak out of the controlled system.
By legal means: show the document only to people who have signed a contract whereby they guarantee that they will not make copies. In effect, legal means can make the human part of the controlled system.

In practice, DRM works (inasmuch as it works at all) by arranging to make the computer that a user bought remain under the control of the content provider: your computer is not your computer, you only paid for it, and you can only use software that is approved by the content provider. If DRM-protected content escapes computers that are under the control of a content provider (for example, if it's visible on a PC), it is no longer protected.

As long as the document is on systems under your control, you can configure your systems to require a password to view it. If the document leaks, then you can enforce confidentiality by encryption, making the document only readable only to holders of a key. Someone who doesn't have the key can tell that the document is there and (at least approximately) how large it is but not what it contains. It is possible to derive a key from a password, so that only entities who know the password can read the document.


Why is the signature field in X.509 a BIT STRING, despite there being ASN.1 (DER) data inside?

The contents of the signature field is dependent on the signatureAlgorithm being used. So it can hold anything (including DER serialisation) for as long as it's eventually encoded as a BIT STRING.

Therefore the length of the signature can be different. Using BIT STRING allows you to know the exact number of bits being used in the signature. With OCTET STRING you may get some extra bits at either ends of the octet-stream which would probably need some special handling to exclude them from further processing at the receiving end.

The SEQUENCE type is like a record, I am not sure why it could be useful here.


A cryptosystem can be represented by multivariate equations and the analyzer tries to solve these equations efficiently in order to mount the algebraic attack. It is known that this is an NP-hard problem.

Linearization is a method for solving these where the degree of monomials is at most two. It first appears in Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization by Kipnis and Shamir. It is simply renaming the variables and solving the new system and then determining the real solutions to the original problem.

Linearization is well written in Bard's book

Given a quadratic system of $m$ equations in $n$ variables;

\begin{align*}
x_1 + x_2 x_3  &= 1\\
x_1 x_2 + x_1 x_3 + x_1
 & = 0\\
x_2 x_3 + x_2
 & = 0\\
x_1 x_2 + x_1 + x_3 + x_2
 & = 0\\
x_1 + x_1 x_2 + x_3
 & = 0\\
x_2 x_3 + x_1 + x_2 &=1
\end{align*}

we are renaming the total ${n \choose 2}$ quadratic monomials and $n$ linear monomials. With renaming (linearization);

\begin{align*}
x_1 &= y_1\\
x_2 &= y_2\\
 x_3 &= y_3\\
x_1 x_2 &= y_4\\
x_1 x_3 &= y_5\\
x_2 x_3 &=y_6
\end{align*}

we get a linear system;

\begin{align*}
y_1 + y_6 &= 1 \\
y_4 + y_5 + y_1 &= 0\\
y_6 + y_2 &= 0\\
y_4 + y_1 + y_3 + y_2 &= 0\\
y_1 + y_4 + y_3 &= 0\\
y_6 + y_1 + y_2 &= 1
\end{align*}

Now one can perfrom the Gaussian Elimination  to get;
\begin{align*}
y_1 & = 1\\
y_2 & = 0\\
y_3 & = y_5\\
y_4 & = y_5 + 1\\
y_5 & = \text{free}\\
y_6 & = 0\\
\end{align*}

This gives out two solutions  $(1, 0, 0, 1, 0, 0)$ and $(1, 0, 1, 0, 1, 0)$. One is valid and one is not (left to reader). This is due to the fact that linearization destroy information. Therefore;

The solution of the original system of equation is also the solution of its linearization but the reverse will be not correct.

What is the benefit of the linearization?

If one can given $m = (n^2+n)/2$ equations the linearization will yield a few candiate solutions.
if $m \approx n' \approx n^2/2$ then the system will have too much information that will yield numerous spurious solutions.


Are Feistel ciphers subject to the birthday bound?

No. You need to focus on the stated assumptions in the paper.

It is saying that you need 6 or more rounds to get high security against attacks with no more than $2^{n}$ plaintext ciphertext pairs for a classical (balanced) feistel cipher with truly randomly chosen round functions. This is of course an idealized model for a feistel cipher.

To test your understanding the sentence "In this paper we will show that 5-round random Feistel schemes resist all CPA-2 attacks when m ≪ 2n and that 6-round random Feistel schemes resist all CPCA-2 attacks when m ≪ 2n." is the crucial statement.


Is there a digital equivalent to the Great Seal of the United States?

Is there a way, then, of doing something like the above, but without the need for a central authority?

Why, yes, we do have a way to solve that problem - we refer to it as a 'digital signature'

Here's how it works:

Select a signature algorithm, and come up with a public/private key pair for a signature algorithm
With the private key, generate a signature of the document (possibly with the time stamp and anything else you find relevant).  Affix the above hash, together with the timestamp, to the document.
When someone wants to authenticate a document, simply get the public key, and check that the signature validation algorithm, together with the document and the timestamp, states that the signature verifies.

The fundamental property of a signature algorithm is that, while it is easy to sign any document you want with the private key, you cannot sign any document (where "sign" means generate a signature that verifies with the signature validation algorithm and the public key).

Common signature algorithms in use today are RSA, ECDSA and EdDSA

Of course, one step I didn't go into is "how, in step 3, does someone get the public key" and "how do they know that the public key they get is actually the signer's, and not some attackers"?  These are valid questions, with good answers; but I think I'll leave the exploration of that for another question...


How can I estimate the amount of entropy (with JavaScript) that I'm seeding a CSPRNG with?

If someone chooses to run your program with a seed that you can't predict but an adversary can, you won't be able to tell.  There is no way around this: nothing about the software can tell you what an adversary does or doesn't know; you can only use cryptography to ensure that if an adversary doesn't know a key and the message, then they can't decrypt the message.

In general, to estimate the entropy of a system, you need to have a model for how the system behaves.  This is how all entropy estimation tools work: they posit some parametric model for how the input data might have been generated; then use the data to fit parameters for that model; and finally spit out the entropy of the model with the fitted parameters.


The key schedule uses constants that differ between the key sizes. For arbitrary sized keys you would have to define an algorithm for deriving them. Each key size also uses a different number of rounds, for which you would have to do the same.

Also, what's the point? 256-bit keys are enough for all eternity. Using a longer keylength variant would likely just introduce a false sense of security.

If AES gets broken, it is IMO unlikely that such an attack would break a 256-bit key variant without also breaking an e.g. 512-bit variant with an equal number of rounds. The main exception would be if there was something wrong with the key schedule for one, like the weaknesses in the 256-bit variant, but in that case a less studied longer key variant would be even more of a risk.


Here is the simpler method I can think of: let's assume some PKI has been setup, so that there is a known public key $\mathsf{pk}_i$ for each receiver $R_i$. Then, the share sender can simply broadcast a list $c_i = \mathsf{Enc}_{\mathsf{pk}_i}(s_i)$ to everyone, where $\mathsf{Enc}$ is some encryption scheme and the $s_i$ form the secret shares of the secret $s$. This allows each receiver $R_i$ to retrieve his share (and only his share), but also adds a public value that binds the share sender to each share - this is necessary if you want to prove anything.

Then, the share sender can use any standard NIZK proof system to prove the following NP statement:
$\{\exists (r_1, s_1, \cdots, r_n, s_n): \forall i\leq n, c_i = \mathsf{Enc}_{\mathsf{pk}_i}(s_i;r_i)  \wedge F(\mathsf{Reconstruct}(s_1, \cdots, s_n)) = 1\}$,

where $\mathsf{Reconstruct}$ is the reconstruction algorithm of the sharing scheme you are using, and $F$ is the function that checks whatever you want to check about the secret $s$ (e.g. $F$ could return 1 if and only if its input is a bit, if you want to check that $s\in \{0,1\}$).

Depending on the encryption scheme used, the secret sharing scheme used, and the function $F$, the NIZK will be more or less complex - but it is always theoretically feasible to build such a proof (under a variety of standard cryptographic assumptions) since it is an NP statement, and we have NIZK proofs for any NP statement.

If you want the NIZK to be efficient, you'll need to use algebraic and compatible schemes - typically, something like the additive variant of ElGamal for the encryption scheme, with a group of prime order $p$, and a secret sharing over $\mathbb{F}_p$. For example, proving that $n$ ElGamal ciphertexts encrypt additive shares (modulo $p$) of a bit can be done relatively efficiently with existing techniques for NIZKs (it's a relatively simple extension of a Schnorr Sigma protocol, plus the usual Fiat-Shamir heuristic - or a Groth-Sahai proof in case you don't want to rely on heuristics).


How does NaCl Poly1305 implementation do modular multiplication?

Numbers get represent as in base 256, i.e. $h = \sum_{i=0}^{17} h_i \cdot 256^i$. Since ints are used which are significantly larger than bytes you don't need to propagate carries immediately.

If you forget about modular reduction, then the $i$th digit of the result is computed as $\sum_{j=0}^i h_j\cdot r_{i-j}$. Apart from the lack of carry this is pretty much the same as schoolbook multiplication.

Now to take modular reduction into account you take the high bits of the result starting with bit 130. Now you can shift these 130 bits to the right, multiply them by 5 and add it to the unreduced result. Now shifting to the right by 130 bits can be done by shifting to the right by 17 bytes and then shifting 6 bits to the left. Shifting 17 bytes to the right is done using index arithmetic in r[i + 17 - j]. Shifting 6 bits to the left is equivalent to multiplying with 64. Combining that with the multiplication with 5, gives you a multiplication by 320.

for (i = 0;i < 17;++i)
{// compute the i-th byte of the output
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];// schoolbook multiplication
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];// 5 * overflow >> 130
    hr[i] = u;
}

So the first inner loop is the contribution of those digits that didn't overflow, and the second inner loop the contribution of the overflow.

freeze seems to simply be:

if(h > p)
    return h - p;
else
    return h;

Except it uses bitwise operations to avoid the branch. minusp is $2^{8 \cdot 17}-(2^{130}-5)$, i.e. it simply represents $-p$. It can be used to reduce modulo $p$ if the input is less than $2p$.

Since the individual elements of h can be larger than 256 but are in base 256 you need to propagate carries at the end of each multiplication. This is done using squeeze. Now after propagating the carries you get a number between 0 and $2p-1$. Having a slightly too large value as the result of an intermediate step isn't a problem, so no further reduction happens by default.

But at the of the MAC you need a number between 0 and $p-1$, so freeze is used as final reduction.


Yes, the seed to the KSA in RC4 is essentially the secret key for the stream cipher. With the secret key (the only input to the KSA) an adversary can recreate the keystream, and thereby recover any information encrypted under that key.


Is there an advantage to "weak" hashing and stretching over strong hashing?

The purpose of key stretching is to increase the strength of the resulting output keying material, compared with the input keying material. The input of the keying material is of course generally a password. If the strength of the keying material is already high enough then there is not need to stretch the keys.

Note that the word "length" is in this case a bit of a misnomer. "This is a very secure password" is obviously not a very strong passphrase, even though it probably exceeds the length requirements of many (badly programmed) systems.

PBKDF2 also has a salt component to it which makes it possible to derive keys that also depend on a unique salt, which makes sure that if it is used multiple times with a different salt that it produces different keys. This is an advantage of PBKDF2 against a secure hash.

It seems that you want to use SHA-256 for deriving keys however. For this purpose there are other algorithms that are closely related to PBKDF's: KBKDF's.

A PBKDF is an algorithm where a key is derived from a password, while KBKDF's derive directly from a key that already has enough strength. The strength of the input key is directly transferred to the output keying material (to a certain high maximum, depending on the KBKDF algorithm that is chosen).

As with PBKDF2 it is not required that the randomness in the input keying material is well distributed, so it could for instance be the output of an asymmetric calculation that doesn't provide this distribution.

KBKDF's have some advantages over secure hashes, as they have been especially designed for this functionality:

they can use additional diversification data, e.g. the ASCII encoding of "ENC" and "MAC" to derive multiple keys;
they often have an input parameter for a salt;
they often have a configurable output key length;
they can be implemented in cryptographic hardware where the input / output key are kept inside the hardware, without being exposed to the outside world.

The most modern, standardized KBKDF is HKDF, which itself is based on HMAC, and HMAC in turn is based on - you'd guess it - a (reasonably) secure hash.

You could use PBKDF2 as a poorly designed KBKDF, and similarly you could use a hash yourself to create a poorly designed KBKDF. But I'd just use HKDF. It would seem from the question that you'd need the full HKDF by the way, HKDF-extract and -expand.

If you're faced with a direct choice of using a PBKDF2 with SHA-256 over SHA-512, I would say that it doesn't make too much of a difference, especially if you can set the iteration count to 1. I'd choose PBKDF2 as it was at least designed for this purpose and you can tweak it with a salt and generate as many output bits as required, using a standardized algorithm.

That would however be after indicating that a KBKDF should be used instead.


What is the difference between subtracting the modulus from a scalar field element and reducing it?

We have many mathematical operations for the Cryptography as $$\neg, \ll, \gg , \oplus, + , \times, /, \operatorname{mod}, \operatorname{div}, \operatorname{exponential},\ldots$$ and the list goes on. As we all knew that the time is money and all of the operations have some cost. Our aim is the minimize the cost as much as possible.

For example, we prefer left shifts to multiplication by powers of two

$$ n \cdot 2^k = n \ll k$$

or right shifts to division by the powers of two

$$ n / 2^k = n \gg k$$

or combination of bitwise and operator ($\wedge$) and subtraction by 1 to remainder by the powers of two

$$ n \mod 2^k = n \wedge (2^k-1).$$

The cost of multiplication and division is reduced into the cost of the shift operation and the cost of the remainder into $\wedge$ (modulus $2^k$ is equivalent to taking the $k$ least significant bits).

In your question, you wrote

if a > q{
  a = q-a
}

This should be

if a >= q{
  a = a-q
}

for modular reduction by subtraction as noted by @fgrieu's in the comments.

In your case, we have a prime number $q$ and we are trying to take the modulus. One way during the calculations is to reduce modulo at the end. However, this may increase the size of the operands and this will result in larger operation costs.

What I can see from your piece of code that they reduce the number by subtraction with $q$. Assuming that the result $r = a-q$ is always in $$0 \leq r < q$$ then we can say that $$q\leq a<2q,$$ to see this subtract $q$ from the above equation;

$$q-q \leq a-q <2q-q$$ and get

$$0 \leq a-q=r <q.$$


How can I prove that a function F isn't a pseudo random function?

your title asks "How to prove that a function F isn't a pseudo random function", in your question case (b) is not PRF which is easy to prove. function $F'$ is PRF if for all PPT distingushers $D$, success probability of $D$ distinguishing $F'$ from random function be negligible. So for proving that function $F'$ is not PRF it suffices to construct one distinguisher (which queries to its oracle and look for non-random patterns) with non-negligible success probability.

In contrast case (a) here is PRF, which is harder to proof. for proving function $F'$ is PRF as @fkraiem mentioned suppose $F'$ is not PRF and $D'$ is distinguisher for $F'$ then construct an algorithm $A$ which breaks some assumption (Distingush $F$ from random function here breaks assumption of $F$ being PRF).


number of blocks, and size of padding at 64bit

As written, this exercise is ambiguous, since we don't know how many bits make one character, or even if this number is constant or not.  (For e.g. Unicode text using the UTF-8 encoding, it's not — one character can take up between 1 to 4 bytes, or 8 to 32 bits.)

However, if we assume that one character = one byte = 8 bits, then the message has 2003 × 8 = 16024 bits.  This amounts to 250 (= 16000 / 64) full 64-bit cipher blocks, and 24 bits (= 3 bytes) left over, for a total of 251 blocks (= 251 × 64 = 16064 bits) after padding.

(A perhaps simpler way to calculate this is to note that 64 bits = 8 bytes, and that 2000 is a multiple of 8.  Thus, the message has 2000 / 8 = 250 full blocks and 3 extra bytes, giving a total of 2008 bytes after 5 padding bytes have been appended to round the length up to the next multiple of 8 bytes.)


What you are looking to do can be done, but if you expect it to just work, you are mistaken.

Performing the calculation of the inverse here is the easy part, the hard part is the choice of affine transform polynomial and vector, as incorrect choice will lead to an insecure s-box.

Multiplicative Inverse

The most simple method of calculating the inverse is to build tables. You need to start by building antilog and log tables for the given field size and reduction polynomial.

The antilog table is built like this:

$Antilog(0) = 1$
   $Log(0) = 0$

$Antilog(i) = g \times Antilog(i-1)$
   $Log(Antilog(i)) = i$

for $i = 1$ to $2^{n-1}$, where $g$ is the generator of the table for a given $m$ (reduction polynomial), and addition and multiplication are done in $GF(2^n)$

The multiplicative inverse is then done using a lookup in these tables:

$b^{-1}(x)=Antilog(2^{n-1} - Log(b(x)))$

where $b(x)$ is the byte representation of the polynomial you want inverted, and subtraction is not in the field. $0^{-1}$ is mapped to $0$.

For Rijndael, $n$ is 8, $m$ is 0x11B, the smallest $g$ is 3.

Once the log and antilog tables are generated, you can either build a separate table for the inverse, or perform the double lookup to get it.

Affine Transformation

For the affine transform matrix multiplication, see my answer here for an implementation example. The bit indexes of the new affine transformation polynomial need to be placed into the correct locations of the rotational matrix.

The bit indexes of 0x1F do not match those of the polynomial representation, which is actually the right most row top to bottom. The 0x1F representation makes a software algorithm a little easier to write and debug, since the column index now matches a successive division by 2 of the input and taking the LSB. This could be done in the correct order using multiplication, but requires steps to prevent an overflow with specific data types (byte) in numerous programming languages. Creating a table for transformations by $r$ will be the quickest for testing.

The 0x1F representation is also used in many papers describing the Rijndael s-box or when presenting alternatives, so I tend to use it by default, while keeping in mind the polynomial is different.

The $r$ and $s$ values used in Rijndael do not seem to be optimal for avalanche properties, and seem to have been chosen without detailed analysis. $r^{-1}$ is the inverse of $r$, details here. $s^{-1} = r^{-1} \times s$.

Testing

When changing the width of the s-box, there are several important things at this point that need to be kept in mind. The choice of affine polynomial determines the avalanche properties of the s-box, and the vector determines if there are any fixed points. Avalanche properties are also determined by initial choice of $m$. See this paper for the effects of changing these:

S-boxes generated using Affine Transformation giving Maximum Avalanche Effect

Upon generation of a candidate s-box it needs to be tested to make sure it meets all relevant cryptographic properties. Test for avalanche first (with the first functional vector), and once you have found the best affine transform, run through all vectors. Additional testing should then be performed on the remaining s-boxes. Note the lack of vector testing in the first s-box generated in the above paper (table 4) which has a fixed point at 0x10. The Rijndael design criteria requires that fixed points do not exist; this restriction was imposed despite the fact no attacks which exploit fixed points were known.

For every 1 bit increase in $n$, the workload goes up substantially. Each s-box takes 2 to 3 times longer to generate, and you have have 4 times as many affine/vector combinations to test, and up to 8 times the workload for avalanche testing per combination. Additionally, if you test all choices of $m$ for best avalanche effect, that's another doubling on average. Memory required to store the tables also more than doubles.


$p$ is a prime number and $g^a\bmod p$ will fall between $[1, p-1]$, so $p$ will never be a multiple of $g^a \bmod p$ unless $g^a= 1\bmod p$.
In Diffie Hellman, the secret exponents $a,b$ are chosen uniformly and randomly from $[1,q-1]$, where $q$ is a very large number. The probability that $Pr[g^{ab} = 4]$ or more generally $Pr[g^{ab} = x]$ for any $x$ in the group is negligible. This implies that for any integer $y=poly(n)$ where $n$ is the security parameter and $poly(\cdot)$ is any polynomial, $Pr[g^{ab} \le y]$ is negligible as well. So you don't need to worry about the key being a small value.


Must the order of the groups in a bilinear map be the same?

If both $G_1$ and $G_2$ have prime order $r$, then this means that there are generators $g_1$ and $g_2$; thus, for every $u_1 \in G_1$, there is an integer $x_1$ modulo $r$ such that $u_1 = g_1^{x_1}$. Therefore, every pairing value $e(u_1, u_2)$ is equal to $e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2}$ by bilinearity. It follows that $e(g_1,g_2)$ is a generator of all the possible pairing values, and the bilinearity implies that $e(g_1,g_2)^r = e(g_1^r, g_2) = 1$. Hence, the group of possible pairing values also has prime order $r$.

Now you can imagine $G_n$ as being larger, with possible pairing values being only a strict subset of $G_n$, but that's just cheating.

Note that bilinearity and non-degeneracy imply that if a prime $p$ divides the order of $G_1$, then $1 = e(u_1^p,u_2) = e(u_1,u_2^p)$, from which we can conclude that $p$ also divides the order of $G_2$, and the order of $G_n$ as well. So we cannot have pairings over just any groups.

It is possible, however, that $G_1$ and/or $G_2$ are larger than $G_n$. In practice, the currently known efficient pairings are all derived from Weil or Tate pairings, which work over elliptic curves. From now on, I will denote operations in $G_1$ and $G_2$ additively, because Tradition requires that we talk about point additions. The basic setup of Weil and Tate pairings goes thus:

Let $\mathbb{F}_q$ be a finite field of order $q$. Let $E$ be an elliptic curve over $\mathbb{F}_q$. Let $r$ be a prime divisor of the order of $E$, such that $r^2$ does not divide the order of $E$, and $r$ is not equal to the field characteristic (this is to avoid a lot of degenerate cases). We denote $E[r](\mathbb{F}_q)$ the subgroup of points of $r$-torsion: these are the points which yield $0$ (the "point at infinity") when multiplied by $r$, and there are $r$ of them.

Then there is an embedding degree which is the lowest integer $k \geq 2$ such that $r$ divides $q^k-1$. It so happens (theorem of Balasubramanian-Koblitz) that $E[r](\mathbb{F}_{q^k})$ (the group of $r$-torsion points over the curve $E$, this time considering point coordinates over the field $\mathbb{F}_{q^k}$) contains $r^2$ points.

In that situation, both Weil and Tate pairings become non-trivial; they take as input $r$-torsion points in $E[r](\mathbb{F}_{q^k})$, and yield as output values in $\mathbb{F}_{q^k}^*$, and more specifically $r$-th roots of $1$ in that extended field. This is a subgroup of size exactly $r$ of the invertible elements in the field. This is our group $G_n$.

So we have the following situation:

$G_1$ and $G_2$ are both subgroups of $E[r](\mathbb{F}_{q^k})$, and thus may have order $r$ or $r^2$.
$G_n$ has always order $r$, no more, no less.

At that point, we must choose our groups so that we get some desirable properties:

$G_1$ and $G_2$ both have order $r$.
It is easy to hash arbitrary data messages into elements of $G_2$ (i.e. we can "randomly" generate elements of $G_2$ without knowing the discrete logarithm of the resulting point with regards to a given generator of $G_2$).
There exists a one-way non-trivial morphism from $G_2$ to $G_1$: this is a linear function which outputs values in $G_1$, such that values other than 0 are achievable, the function is easy to compute, but its inverse is computationally infeasible.

Unfortunately, we cannot have all three properties simultaneously. We end up with the following usual choices:

We use a supersingular curve of embedding degree $2$. $G_1$ is $E[r](\mathbb{F}_q)$ (the $r$-torsion points on the curve in the base field, not the extended field). $G_2$ is the very same group; to compute the pairing, we first map $G_2$ into another subgroup of $E[r](\mathbb{F}_{q^k})$ through a distortion map (if both operands of Weil or Tate pairing are from the curver over the unextended field, the pairing output is always 1, hence trivial). Easily computable distortion maps are a rarity, but with a supersingular curve, we have some. For that scenario, $G_1$, $G_2$ and $G_n$ all have the same order $r$; it is easy to hash data into elements of $G_2$; an isomorphism between $G_1$ and $G_2$ is easily computed in both directions since they are the same group.
We use a non-supersingular curve. $G_1$ is $E[r](\mathbb{F}_q)$ and $G_2$ is a subgroup of $E[r](\mathbb{F}_{q^k})$ generated by a conventional $r$-torsion point (not one which is in $G_1$); thus, $G_1$ and $G_2$ both have order $r$. We do not know how to hash points into $G_2$. The Trace of Frobenius of a point $P = (X, Y)$ is defined as:

$$ \phi(X,Y) = \sum_{i=0}^{k-1} (X^{q^i}, Y^{q^i}) $$

(it is a sum of elliptic curve points, and each of these points is obtained by taking the coordinates of the input point, raised to power $i$). $\phi$ happens to be an isomorphism from $G_2$ onto $G_1$, and it appears to be difficult to invert.
We use a non-supersingular curve. $G_1$ is $E[r](\mathbb{F}_q)$. $G_2$ is the subset of $E[r](\mathbb{F}_{q^k})$ consisting in points $P$ such that $\phi(P) = 0$ (the set of "points of trace zero"). $G_2$ is a group of order $r$ and we know how to hash points into $G_2$. However, we do not know any easily computable non-trivial morphism from $G_2$ to $G_1$, or from $G_1$ to $G_2$.
We use a non-supersingular curve. $G_2$ is the complete $E[r](\mathbb{F}_{q^k})$; thus, it has order $r^2$. $G_1$ is any subgroup of $G_2$ (of order $r$), possibly $G_2$ itself (of order $r^2$). It is easy to hash into $G_2$.

One way to think of pairings is that a pairing is a product. If we had a group $G$ with an "addition" and we could find a pairing of pairs of elements of $G$ into elements of $G$ itself, then that pairing would behave just as multiplication behaves with regards to addition (it would, by the way, totally break Diffie-Hellman on the group $G$). So the "natural" situation is really that $G_1$, $G_2$ and $G_n$ all have the same order.


Cryptography Headers in Cryptographic Libraries

What associated data (or encrypted header in the plaintext message) to use is dependent on the protocol, not on the cryptographic algorithm.

Generally, for messages in a transport protocol, you'd use the to avoid replay attacks.

The header data may also contain other meta-data that you want to authenticate for the message.

Beyond that, there is nothing to tell you, because you've only listed a (partial) algorithm, and not the protocol.


Are the SHA family hash outputs practically random?

Say I hashed the output from a random number generator (with nonce), would the resulting SHA256 hash be as random as the inputted number?

Let's suppose you flipped a perfectly fair coin. You flip it 1024 times to create a bit string of 1024-bits.

Because the coin is perfectly fair, this means that each strings of 0s and 1s will appear with precisely the same probability.

What happens if we apply SHA-512 to these strings? Well, in order for SHA-512 to give a completely uniform 512-bit output, it would have to be the case that if we hashed every 1024-bit string then each 512-bit hash value would have to appear precisely $2^{512}$ times.

There is no proof that SHA-512 behaves in this way. I would be very surprised if this turned out to be the case!

As such, the output of hashing a truly random stream is a stream which is bias. This bias will be very small indeed, but it will be there. So the answer to that specific question is no.

In practice, the bias is so unbelievably small that it doesn't matter. In fact, many hardware RNGs hash the entropy pool to produce output bytes.

However, it's worth noting that using such an RNG as the basis for generating a  one-time-pad actually ruins the security proof! It would be technically insecure but good luck exploiting it.


How do RSA and ElGamal key sizes compare?

RSA and ElGammal are about equally secure at the same modulus size (assuming, of course, intelligent parameter selection in both cases).

For RSA (assuming you use good padding), the best known-attack is to factor the modulus with NFS.

For ElGammal (assuming you use a subgroup with a large enough prime factor), the best known-attack is to compute the discrete log of the public key with NFS.

Now, the version of NFS to compute discrete logs is somewhat more complicated than if it were used to factor; however I don't believe that extra complication adds a significant time to the time taken.


The presentation probably went along with a more verbose lecture.

I would assume there was some discussion about message lengths there, since that statement is obviously incorrect. In most applications, the "message" length is longer than the digest, and the average message length is also most likely longer. Think file verification, or processing of an actually message, instead of of a password.

In that statement, substitute "much shorter" to "usually much shorter"


Is it safe to publicly expose PBE-protected PGP secret keys?

What I understand from the question, as if you have a Certificate Authority key around.

Using an air-gapped pc, raspberry pi zero, etc. is a good choice. The important points;

Sign the document in the offline solution, do not carry the key.
You can have more than one air-gapped solution. Extra hardware against failures.
You can keep your old paper around.
Have an extra security against the easy copying from the device

Extream care

Off-line encryption: In the military, when a message is top secret, the message, firstly, encrypted with an off-line system that has no connection to the network. After the off-line encryption, the message is sent by on-line crypto. The problem is not finished here.

Tempest Attack: The signal from a pc can be carried by air or the power lines. This requires an expert in this area to filter the machine. So the off-line system and the power lines are filtered.

Covert channel: If an adversary can install a software to your air gapped solution that he can use the heat to transfer the data. Have a mechanism to prevent access to the solution.


Is there something wrong with my decryption using key=9, mod 26?

Your punctuation is slightly off:

  What's in a name? A rose by any other name would smell as sweet.

It's a reference to Romeo and Juliet


Leaving authentication data blank less secure for AES GCM?

AEAD modes like GCM are authenticated encryption with associated data; this setting only affects the associated data half of that. The ciphertext itself is still authenticated. The associated data portion is there to provide contextual information for the authentication of the ciphertext. Usually this data is something that's outside of direct control of the party providing the ciphertext to be decrypted.

As a contrived example, it could be the database ID of the user whose data is encrypted. This way, even if another user found a way to copy a victim's secret key and ciphertext into his own account, he wouldn't be able to successfully decrypt the ciphertext since the user IDs would not be the same. Alternatively, in something like an over-the-wire communication protocol, a sequence number could be used as the associated data. This would prevent some types of replay attacks at the cryptographic layer — any attempt to replay a ciphertext would fail, since the other side can reject packets with duplicated sequence numbers, and any other sequence number would fail to decrypt the cryptogram.

To get around to answering your question, "less secure" than what? Not using authenticated data doesn't render the underlying ciphertext inherently weaker than had you used another, non-AEAD mode. But if there's additional context that could be included and you're not using it, it could be more secure if you did use it.

As always, it's important to understand what your threat model is before you involve cryptography. What are you trying to protect? From whom are you protecting it? What are the possible threats, and the vectors an attacker might use to compromise the protected data?


How does the key agreement process take place in Virgil E3Kit SDK for end to end encryption?

E3kit uses ECIES under the hood. It's a hybrid encryption scheme where symmetric key is encrypted using the key derived from the DH shared secret. KDF is needed because it's not secure to use the raw DH result as a symmetric key.


When you multiply an $n$-bit integer by an $m$-bit integer, the product is an $(m+n-\epsilon)$-bit integer, with $\epsilon \leq 1$.

For RSA the security recommendations specify that secret factors of the public modulus must be of approximately the same size. If the difference in the number of bits is modest (less than a machine granularity) it could be approved.

There is also another suggestion from Shamir about generation of RSA keys for paranoid, which recommends for example a prime $p$ of say $1000$ bits and the other prime $q$ of $5000$ bits.


This would be better than simply CTR if your nonces do collide, but it is still not very good.

Suppose you use the same IV for two messages $m_0||m_1||...m_n$ and $m_0'||m_1'||...m_n'$ where all the $m_i$ are 128-bit blocks. Each block is XORed with the same keystream value as the corresponding block in the other message. They then pass through AES, the same as in ECB mode. If any $m_i=m_i'$, they have the same ciphertext, so the cipher leaks information about the message.

SIV mode would be closer to what you are looking for. It should be approximately as fast, though it does require two separate passes over the data. In the case of nonce reuse it leaks the equality of the (complete) messages, but no further information.


TL;DR     The answer is classical cryptography.
Besides a quantum link, secure data communication with Quantum Cryptography (more precisely, Quantum Key Distribution) uses classical links, mathematically provable classical cryptography, and a setup procedure using initially trusted material just as in classical cryptography.
To perform the same, classical cryptography uses the one-time pad; or assumes a bound of the adversary's computing power and some unproven mathematical hypothesis. But assumptions may turn out wrong, and the risk exists that future progress allows decryption of archived intercepts. Pure quantum key distribution avoids that particular risk by instead relying only on physics when it comes to unproven assumptions.

Quantum Key Distribution (QKD) is now a subfield of Quantum Cryptography (QC), which also includes:

Post-Quantum Cryptography, exploring cryptographic methods usable on classical computers that will resist attack by Quantum Computers, should they become applicable to attack today's cryptography.
Quantum Random Number Generation, which aims at producing a demonstrably secure source of near-perfect random secret non-shared bits demonstrably rooted in some identified quantum physics phenomena; these are often used as RNGs in Quantum Key Distribution, and that's consistent.
Quantum Cryptanalysis, studying attacks of any kind of cryptography with a Quantum Computer, and attacks with any kind of device against Quantum Key Distribution or Quantum Random Number Generation.

The thought experiment in the seminal BB84 article quoted in the question can lead to practical QKD. I explain how and give links, but no math. That's out of ignorance on the quantum side, laziness on the information-theoretic side, and the 30000 characters limit as an excuse.

A. Issues prevent direct use of sifted bits
The question summarized only a subset of the article, and stops at obtaining sifted bits. These are squarely unsuitable for direct use, and do not achieve Quantum Key Distribution (QKD), for three main reasons:

Errors creep in the sifted bits

The many imperfections of the model (heavily simplified compared to the actual hardware and the known laws of quantum physics, even at the time the article was written) are such that, without Eve messing, sizably many sifted bits differ at Alice's and Bob's end. Sifted bits are thus unusable as key to a cipher, for decryption would likely fail.

The sifted bits are not nearly secret enough

An eavesdropper can gain sizable knowledge about the sifted bits. That makes them unacceptable for direct use as a keystream, for Eve's partial knowledge puts confidentiality in jeopardy. Quoting the article, the best assurance given by the quantum model of the adversary is only:

it can be shown that no measurement on a photon in transit, by an eavesdropper who is informed of the photon's original basis only after he has performed his measurement, can yield more than 1/2 expected bits of information about the key bit encoded by that photon

Who are these sifted bits shared with?

The first part of the article, and the question, assume the classical channels are

susceptible to eavesdropping but not to the injection or alteration of messages

Without such insurance, Alice and Bob would be unsure about who their sifted bits are really shared with! It could be that Eve rather than Bob is who receives Alice's photons and "communicates over the public channel to Alice", thus that Alice shares sifted bits with Eve. Bob faces a similar issue if Eve really is who sent him photons and "tells him which filters are correct". This allows a Man-in-the-Middle attack when data transmission time comes.

B. Classical cryptography rooted in information theory fixes them all

Secret-Key Reconciliation protocol remove errors, and more

Coding theory and error detection and correction are used to build a secure Secret-Key Reconciliation protocol additional to sifting, also running over the classical channels. Its objectives are to

remove or fix errors in the sifted bits, with bounded low odds of the contrary;
obtain an upper bound on the actual error rate, which is attributed to Eve spying the quantum channel;
obtain and minimize an upper bound on the information leaked by running the protocol over the classical channels, that Eve is assumed to scrutinize;
deduce a lower bound of what entropy (if any) remains in the rest; if there is less than some headroom, QKD failed.

Such reconciliation protocol can lose little-enough entropy as to be usable in practice, and be information-theoretically provable, but no simple such one is known. A most scrutinized milestone is the cascade protocol in Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

Privacy Amplification distillates a shared key

The entropy demonstrably remaining after reconciliation (if any) is distilled into bits with close to perfect entropy. A classical cryptographer would use a hash, but provable information theory has nothing to offer in that category. ID Quantique's 2020 whitepaper gives a rudimentary Privacy Amplification Protocol, but that's only for illustration.
Further, for use as an ever-flowing source of near-perfect random secret shared bits, it must be removed from the outcome enough bits to renew the setup key (see 3 below). Articles scrutinizing this circularity go under variations of the name Universally Composable Quantum Privacy Amplification.

Classical setup key and cryptography make the classical channels secure

The method proposed by the article is the most common:

Alice and Bob have agreed beforehand on a small secret key, which they use to create Wegman–Carter authentication tags

That's similar to the low-tech key ceremony of classical cryptography: Bob physically meets Alice, each throws a hex dice 20 times, and writes the outcomes as 20 characters, forming two lines on paper. Chemical carbon copy ensures Alice and Bob keep identical notes. They are sealed in two opaque tamper-evident envelopes to ensure secrecy until use. Bob protects his envelope while he gets back. Alternatively, Alice does the whole job, and a trusted courier hands Bob the envelope against signature.
For each of the two classic communication channels, the half of the setup key generated by the sender on that channel is used as the key to an information-theoretic Message Authentication Code (like Universal hashing of Mark N. Wegman, J. Lawrence Carter; New hash functions and their use in authentication and set equality, in Journal of Computer and System Sciences, 1981), computed over all the data sent on the channel for sieving and reconciliation. That MAC (one of the two "tags" in the article) is sent on the conventional channel it protects. The receiver can recompute and check it, and this gives demonstrably bounded odds of forgery. Our example's 80-bit half key demonstrably gives 40-bit security: better odds than one in a trillion against undetected forgery, which satisfies any rational person.
Setup key transfer must ensure integrity, but  it can be differed to a moment when secrecy is no longer required, like in classical asymmetric cryptography. However, setup key halves must then be conveyed separately in each direction, after reconciliation, but before the key established by QKD can be trusted. That's inconvenient, and common practice is to keep the setup key secret: ID Quantique's 2020 whitepaper states that it is made

use of a pre-established secret key in the emitter and the receiver, which is used to authenticate the communications on the classical channel. This initial secret key serves only to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.

Note: This did not cover a number of things needed for a working QKD, and possible pitfalls:

How does Bob conclude that a photon did not pass thru a polarizing beam splitter, which is an absence of event? If that's by timing, how do Alice and Bob get a common timing reference precise enough? At a coarser level, how do Bob and Alice agree on common indexing of expected photon events?
How much exploitable information leaks thru classical side-channels not accounted for in the reconciliation's estimate of remaining entropy, e.g., due to timing variations in the sifting or reconciliation protocol, varying light intensity, electromagnetic leakage, etc.?
How much other headroom is necessary for the test at end of reconciliation to robustly cover the imperfections of the quantum model, including those sneakily introduced by a creative adversary? How can it be safely arranged a retry should that test fail?
How is the setup key stored secretly in the QKD devices? How is it kept in synchronization under down-to-earth constraints like power failure?
Uncaught design errors or runtime faults (accidental or deliberate) in the implementation, which relies on conventional electronics, processors, and software, are possible pitfalls.

C. Quantum Cryptography from Quantum Key Distribution
Like conventional cryptography, quantum cryptography aims to transmit arbitrary data with confidentiality and integrity (underestood to include assurance of origin and destination). Each of these two goals can be reached in two ways, both using classical cryptography over classical channels, using the outcome of Quantum Key Distribution as key:

Provably secure conventional cryptography rooted in information theory

The One Time Pad (or an essentially equivalent variant) for confidentiality, using the random bits of QKD as keystream.

Security relies heavily on the quality of the Privacy Amplification of B.2, and on the soundness of the insurance given by the Secret-Key Reconciliation protocol of B.1. Throughput is bounded by the sift rate diminished by what's eaten by the tasks in B.
An information-theoretic message authentication code for integrity and origin, keyed from the QKD flow, as in B.3 above. That tolerates small imperfections in Privacy Amplification.

Conventional symmetric cryptography without mathematical proof

Some symmetric cipher for confidentiality, regularly re-keyed using the keystream of QKD. That's the only method to boost an otherwise insufficient rate of QKD. Also, it adequately mitigates small imperfections after Privacy Amplification.

A typical choice is the block cipher AES-256, perhaps with an operating mode like CTR. That's pragmatic and makes a lot of sense: AES-256 is rubber-stamped by civilians and military, is largely conjectured adequately secure from brute force attack for decades including using quantum computers, and against side-channel attack assuming regular key change with classical key derivation, which QKD can supplement or replace.

Some standard Message Authentication Code for integrity, e.g., HMAC-SHA-512, probably regularly keyed from the QKD; giving up on using an information-theoretic MAC could make sense when reusing a commercial classical cryptography device without modification.

Authenticated encryption (perhaps AES-GCM), which is a modern way to integrate a symmetric cipher and a standard MAC.

The above techniques are believed secure, or even mathematically provable for those of C.1. The technically difficult points are the prior QKD, and correct implementation as for conventionally applied cryptography: Random Number Generator, side channels and fault attacks, integration in a protocol...

D. Operational constraints of Quantum Cryptography
There are severe limitations to QKD, at least as widely available:

Incompatibility with network gear along the fiber (standard optical amplifiers or other standard repeaters as used in long fiber cables, switches, and routers directing data to the right user). Solutions exist only at the laboratory level. Commercial offers are restricted to point-to-point communication, or/and use conventional cryptography beyond that.
Small range, and (when not assisted by conventional cryptography not mathematically proven) low bandwidth, with a compromise between the two. For example, the Cerberis3 QKD System is specified for 1.4 kbit/s over 50 km, and less at the maximum range of 75 km. For direct line-of-sight ground-satellite by night, a 2017 paper reports ~12 kbit/s at 645 km to ~1 kbit/s at 1200 km. In lab conditions with supercooled photon detector it is reported

If we want pure QKD, it is lost the convenience of Public-Key Infrastructure based on digital certificates issued by certification authoritie(s).
No interoperability between vendors (closest I could find is Toshiba's call for arms towards that, in a Feb. 2017 newsletter).
No extensive data on operational availability of QKD links are available, especially under varying temperatures; it is reasonable to fear low Mean Time Between Failure for some parts, e.g., photon detectors after temperature cycling.
To my knowledge, no device employing QKD has obtained so far (Aug 2017) a public security certification covering QKD. Fact-checking this datasheet for a "Certified Common Criteria & FIPS 140-2 Level 3" product with "Support for QKD" available as an upgrade, I conclude the only quantum-related feature covered by certificates is an RNG, and the FIPS 140-2 security policy's only mention of QKD is:

The Quantum Key Channel serial port connects to a separately available ID Quantiqe (sic) Cerberus quantum key distribution server (not a supported FIPS140-2 Level 3 mode of operation under this certification).

E. Security of Quantum and conventional cryptography

How Quantum Key Distribution implementations fail

The security of QKD is rooted in parts of cryptography that are mathematically proven secure; and a physical model of how photons (possibly other quantum physics objects) behave per modern physical theory, which exquisitely matches experimental results and allows theoretical proofs.
However, a large fraction of particle physics and electromagnetism, and all of gravity/relativity, is typically brushed aside from the analysis; and the hypothesis of proofs do not fully model the equipment used, which has allowed some credible attacks, like phase-remapping.
Worst, adversaries think outside of the box and actively modify the quantum experiment so that the model is no longer a close fit. Like Eve blinds the photon detector! Quoting Lars Lydersen, Carlos Wiechers, Christoffer Wittmann, Dominique Elser, Johannes Skaar, and Vadim Makarov: Hacking commercial quantum cryptography systems by tailored bright illumination, in Nature Photonics Letter 2010:

we demonstrate how two commercial QKD systems id3110 Clavis2 and QPN 5505, from the commercial vendor's ID Quantique and MagiQ Technologies, can be fully
cracked. We show experimentally that Eve can blind the gated detectors in the QKD systems using bright illumination, thereby converting them into classical, linear detectors. The detectors are then fully controlled by classical laser pulses superimposed over the bright continuous-wave (c.w.) illumination. Remarkably, the detectors exactly measure what is dictated by Eve.

A joint 2010 press release with the company whose QKD device was hacked mentions that it was

developed and tested a countermeasure. [..] “Testing is a necessary step to validate a new security technology and the fact that this process is applied today to quantum cryptography is a sign of maturity for this technology,” explains [..] CEO of [..company..]

That's an arms race, similar to what has been ongoing for 40 years in Smart Cards, often used nowadays for convenient cryptographic key distribution. Eve has blueprints for other attacks:

inducing Alice to make errors by blinding her side rather than Bob's;
probe the (assumed random and secret) orientation of Alice and/or Bob polarizers by remotely sending photons (perhaps entangled, and with whatever characteristic best fits the job) in-between the individual photons sent (typically regularly) by Alice;
predicting Alice's or Bob's RNG from the earlier output (to reach the record rates reported in D.2, several gigabit/second of assumed perfect randomness are consumed by Alice; that's hundreds of times more than common quantum sources);
classical TEMPEST information leaks or induced-faults targeting the state of the quantum gear, the current setup key, or the QKD outcome.

Quantum and Classical assumptions compared

Conventional cryptography achieves the equivalent of QDK only by relying on some mathematically unproven hypothesis. For symmetric (secret-key) cryptography, that can be broadly described as the hardness of solving some combinatorial problem. Further, asymmetric (public-key) cryptography is required for turning a channel with integrity into one with confidentiality (something QKD can do), and that relies on the hardness of solving some other problem; examples include integer factorization, discrete logarithm, or RLWE.
There is wide consensus, but no mathematical proof, that (ignoring implementation issues) current conventional cryptography is currently secure; and that symmetric cryptography needs at most a doubling of the key size to become secure against future quantum computers hypothetically usable for problems of cryptographic interest. Which key size is required for which of the various problems used in asymmetric cryptography is an active research topic.
The security of QKD relies on physical hypothesis, where the security of conventional cryptography relies on mathematical hypothesis. Both kinds of hypotheses are not mathematically proven. But both are firmly established (at least when we restrict conventional cryptography to its symmetric branch). Any insecurity (beyond, inevitably, the humans involved) is likely to lie elsewhere: oversimplified theoretical model, undetected mistakes, or backdoors in the implementation. The complexity of QKD makes these mishaps more likely.

Quantum Key Distribution's strongest point

QKD gives insurance that classical cryptography does not. Arguably, if a data transfer protected by QKD is secure when it takes place, and uses only mathematically proven cryptography, then no future progress will decipher that data. The argument is that even if the photons sent on the quantum channel could be stored (a trick that has been pulled) at the time of the communication in hope of decryption in the future, the photons would not reach the quantum receptor, QKD would fail (with high insurance), actual data encryption would not occur, and the data would be safe.
By contrast, the channels of classical cryptography can be passively eavesdropped on and stored for hypothetical future decryption using superior technology. That's reasonable: even perfect forward secrecy won't resit a break of the symmetric cipher. Intercepts kept from the past that used a well-documented cipher with less than about 100-bit key are decipherable today with enough resources, 3DES (64-bit block, 111-bit key) will likely succumb, AES-128 can assuming mere stability of technical progress, AES-192 too if further assuming quantum computers usable for cryptanalysis, AES-256 also if we stop wondering about how and when.

F. Use cases for commercial Quantum Cryptography
The justified scientific recognition and the press coverage of QKD/QC helps sales, and is enough for targeting some markets:

Experimental study of QKD/QC, which is of high scientific and educational value from both experimental quantum physics and applied cryptography/cryptanalysis/auditing/hacking perspectives.
A segment of the computer security market: purchase-decision-makers in quest of prestige, reassurance, or theatrical effect. Quantum can be to crypto what gold is to audio, and silver to bullet.
The funneling out of money for a plausible cause. Expensive security equipment is good at that, usefulness is secondary, unconventionality no obstacle: see ADE 651.
Cover for a backdoor. QKD equipment is sold to supply keys for the encryption of sensitive data. Knowing an easily exploitable vulnerability in the QKD implementation (e.g., leak of the shared key on classical channels, perhaps subtly by timing variation in sifting or reconciliation, accidentally or deliberately) can break an otherwise secure encrypted link.
Cover for a trojan. QKD equipment has reasons to be in a secure perimeter. Its cabinet is thus ideal to physically sneak-in a microphone, camera, spy gadget, or side-channel attack device (being physically connected to the targeted security equipment helps immensely).

It is harder to find a security problem that today's QKD can solve (and penetrate the bulk of the market); many conditions must be met:

The confidentiality of some data to be transferred from point to point is of vital importance (at time of transfer, or later).
And the One Time Pad (which has successfully been used in that situation) is not an option; perhaps the means that must transport the shared key of QKD with at least integrity won't transfer a 1TB memory stick full of randomness with integrity and confidentiality, or the data of vital importance is larger than 1TB; see Johny Mnemonic.
And QKD is left usable despite D.1, D.2 (excluding the bandwidth issue which is adequately taken care of by C.2), D.4, D.5, and D.6.

Assuming the above, then it is rational to think about using commercial QKD as a supplement to classical cryptography; fortunately, we are not bound to choose between the two and can get the best of both worlds on security, when it is acceptable to get the worst on availability.
Classical cryptography featuring perfect forward secrecy and robust cipher with large block and the key is widely available. On the communication link it uses, it can be inserted an independently sourced commercial QKD equipment, of course with independently managed setup keys for each of the two encryption means as in any sound use of multiple encryption. An auditor can ensure confidentiality is at least as good as without QKD by merely ruling out a trojan (see F.5), for a fee. Perhaps the reduction in simplicity and assurance of working on D-day is worth the price and added confidence in long term confidentiality; however, tarnished it is by the use of classical cryptography without mathematical proof to reach acceptable throughput.
But it would be entirely irrational to rely solely on QKD, given its immaturity, unconvincing security argument against adversaries not bound by the narrow physical hypothesis made, deep complexity when we account for the arsenal of classical cryptography necessary to make it work at all, the tainted security track record for these reasons, poor auditability and recognition by practitioners, and the requirement for the same inconvenient setup key management as classical cryptography.

Operational summary
Quantum Key Distribution (a subfield of Quantum Cryptography) in principle performs the same tasks, and uses the same operational procedures as conventional cryptography, with no operational simplification whatsoever. In particular, the need for initially trusted material established by inconvenient human means remains.
QKD relies on physics rather than mathematics when it comes to an unproven hypothesis. That's a remarkable achievement and paradigm shift. But if that's a benefit, it is intangible and did not help QKD get a clean security track record, much less be widely recognized as useful by practitioners.
Integration of QKD in current networks is utterly impractical: QKD currently requires a dedicated fiber with a practical range limit ≪500 km, or direct line of sight with no sunlight, rain, or fog. That can only be extended with trusted facilities at each intermediary endpoint. Practical throughput is low, except when supplemented by conventional cryptography (then losing some of the aforementioned intangible benefits).
Commercial QKD equipment is complex, in part because it relies heavily on many classical mathematically provable cryptographic techniques. It is expensive, big, power-hungry, in low demand and stock, of unproven field reliability, seldom used in practice, and not recognized by security certification authorities.
QKD removes the risk that future technological progress allows compromise of intercepts made earlier. It is worth consideration in complement (not replacement) of carefully vetted classical cryptography with independent secure setup procedure, for data which confidentiality is of utmost importance (especially if that's for decades), if we trust couriers for setup keys but not for the one-time pads traditionally used for perfect secrecy in that situation.


"I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice."

Yes, modular exponentiation is much faster.

How much do you think a number expands if you perform non-modular exponentiation?

And what's keeping an adversary from just trying all possible inputs, and encrypt them to see which one matches?

You can of course random pad $M$ with e.g. 128 random bits, but then your input will grow even larger, the exponentiation slower and the result even larger.

But most importantly, what's hard about calculating $\sqrt[e]C=\sqrt[e]{M^e}=M$ if $e$ is known? I don't think that that's a hard problem even if $e$ is very large. For a large $e$  the calculation really becomes problematic because the result size would be humongous anyway.

Of course, your encryption function needs to be irreversible without the private key value - in this case $d$ - and it isn't.


If you are concerned with preventing retroactive decryption—e.g., making sure that when the bad people in uniforms take your phone away from you to a forensics lab to find evidence by which to convict you of exercising human rights, they can't use what's on it to decrypt all the past conversations you had over the internet while they were eavesdropping—then you need to rotate the IKM and erase the old one and all keys derived from it.

If you are merely trying to encrypt large volumes of data with cryptosystems that can handle only small volumes per key—e.g., you are trying to use AES-GCM with a single key to encrypt petabytes of messages—then you can just use a different HKDF-Expand info parameter with the same salt/IKM/OKM.

The main purpose of varying the salt is to mitigate multi-target attacks: if everyone used the same salt, or no salt, with IKM having only 128 bits of min-entropy, and if there are $u$ different users of the system, the adversary can get a factor of $u$ cost reduction and factor of $u^3$ speedup by attacking them simultaneously parallelized $u^2$ ways at an expected cost of ${\sim}2^{128}/u$ in the expected time for ${\sim}2^{128}/u^3$ sequential trial evaluations of the cryptosystem.  But if all users have distinct salts, the batch advantage vanishes.  Another way to thwart the batch advantage is to use 256 bits of min-entropy instead, and 256-bit keys everywhere.

(The salt is also documented to prevent accidentally using the same key material for two different purposes, if somehow an adversary can cause the same secret IKM to appear in two different places, though it seems to me that if that happened you would probably have bigger problems.)


Encrypt-then-MAC Confidentiality, Integrity and Authenticity

Encrypt-then-MAC has been standardized in ISO/IEC 19772:2009 hence it is safe to assume all the properties that you mentioned.

To the best of my knowledge, the best way to perform EtM is:

E = ENCRYPT(PLAINTEXT)

  I am assuming that you are using a block cipher such as AES and
  appending the encryption IV or nonce to the start of E unless of course you are using ECB.

M = HMAC(E)

  HMAC also takes a key which must be different from your encryption
  key. There are of course other MACs, but I recommend HMAC since it removes the complexity of MAC IVs.

OUTPUT E, M


Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

Not quite.  A randomness extractor is not simply a function $F\colon A \to S$ such that $F(X)$ has small distance from uniform if $X$ has high min-entropy.  Rather, a randomness extractor is a keyed family of functions $F_k\colon A \to S$ such that if $K$ is uniformly distributed and $X$ has high min-entropy, then $F_K(X)$ has small distance from uniform.  In other words, the premise is that you already have a uniform random key.

So, there is essentially no reason to use a randomness extractor in a practical application.  Generally, either:

You have a secret with high enough min-entropy to do cryptography.

Great!  Use HKDF-SHA256 or your favorite KDF to derive keys from it for each cryptosystem you want to use.

You don't have a secret with high enough min-entropy to do cryptography.

No amount of cryptidigitation with randomness extractors will raise its min-entropy.  Just flip the coin a few more times.

Randomness extractors are essentially of theoretical interest only, so it is not surprising if you have trouble finding practical implementations of them labeled as such (although any universal hash serves as a randomness extractor with the leftover hash lemma).  If you actually want to do cryptography, just feed your initial secret with high min-entropy through a hash function like HKDF-SHA256 or SHAKE128.


Authenticate encrypted seed for KEM + AEAD hybrid cryptosystem

It probably doesn't hurt to include the encapsulation as additional data for the AEAD, but there is no need.  The generic KEM/DEM composition,

\begin{align}
  &(C_0, k) \leftarrow \operatorname{KEM}_{\mathit{pk}}() \\
  &C_1 \leftarrow \operatorname{DEM}_k(M) \\
  &\operatorname{return} C_0\mathbin\|C_1,
\end{align}

provides adequate security by the standard theorems, e.g. Cramer–Shoup 2001, Theorem 5 on p. 41.

You can safely separate the concerns of

generating the encapsulation $C_0$ and the key $k$ with RSA, and
one-time authenticated encryption under $k$,

as separate subroutines that communicate only $k$.

See Shoup's ISO proposal for more practical details of composition and instantiation with less math.

Incidentally, it is also unnecessary to generate an IV, since the key is used only once: you can safely use an IV/nonce of zero for the AEAD as a DEM.


Create a ciphertext that decrypt to different plaintexts with different keys in RSA

For the problem as stated in the question, yes what's asked is possible, exactly per the method stated in the question. For textbook RSA (except with unusually tolerant decryption code), no, that's not possible. For RSA as practiced, there exists solutions or not, and it can be found on not, depending on methods and parameters.

The critical differences are due to different definitions of a valid ciphertext $C$ for a message $m$ and public key $(n,e)$:

In the question's RSA, that's $C\equiv m^e\pmod n$, which allows arbitrary many integers $C$, since that notation only means that $n$ divides $C-m^e$, and implies that if $C$ is valid, then $z\,n+C$ also is for any $z\in\Bbb Z$. Notice that this version of RSA makes $C=m^e$ a valid ciphertext, and this choice of ciphertext allows decryption without the private key, as $m=\sqrt[e]C$.
In textbook RSA, that's $C=m^e\bmod n$, which further implies $0\le C<n$. This should be tested before decryption (and actual implementation often do this, or at least depend on $C$ not having much more bits than $n$). That leaves a single (or relatively few) valid ciphertext for any message $m$. A ciphertext is uniquely defined for $m_1$ with $(n_1,e)$, and there's no way to make it coincide with the uniquely defined ciphertext for $m_2$ with $(n_2,e)$. A spontaneous match won't occur by chance for even half-realistic modulus size.
in RSA as practiced, well there's not a single practice, but at least there again are many ciphertexts for any given plaintext, because the message is always combined with randomness for encryption¹. Block RSA encryption usually has $C=g(r,m)^e\bmod n$ where $r$ is a large random bitstring and $g$ is injective with output domain a subset of $[0,n)$. The size of $m$ is severely restricted compared to textbook RSA. If $r$ has sizably more than half as many bits has $n$, by the birthday bound, it is likely that one of the valid ciphertexts for $m_1$ with $(n_1,e)$ coincides with one of the valid ciphertexts for $m_2$ with $(n_2,e)$, implying there's a solution².

Doing what the question wants is easy: one computes $C_1=m_1^e\bmod n_1$ and $C_2=m_2^e\bmod n_2$ per textbook RSA, then by the Chinese Remainder Theorem one computes a $C$ such that $C\equiv C_1\pmod{n_1}$ and $C\equiv C_2\pmod{n_2}$. There is exactly one such integer $C$ in $[0,n_1\,n_2)$ under the hypothesis that $n_1$ and $n_2$ are coprime, which should hold for proper RSA keys. It can be computed as
$$C=\bigl(({n_2}^{-1}\bmod n_1)(C_1-C_2)\bmod n_1\bigr)\,n_2+C_2$$
This $C$ will decipher to $m_1$ for private key $(n,d_1)$ and to $m_2$ for private key $(n,d_2)$ under implementations of textbook RSA decryption that do not check that their ciphertext input is less than the modulus, and still compute exactly despite the anomalous input.

¹ Deterministic RSA allows anyone to check a guess of the plaintext, e.g. find who's name on a public class roll was encrypted. The addition of randomness fixes that often devastating weakness.

² For PKCS#1 v1.5 encryption padding (but not the better OAEP) it is conceivable to actually exhibit a solution if the message is very short and the corresponding private key is known and of the same size. With $m_1$ short, we compute various ciphertexts for $m_2$ and different random padding, and decipher each under $(n,d_1)$ until that does not cause an error, and the deciphered plaintext has the desired size, and it happens to match $m_1$. For 2048-bit $n_1$ and $n_2$, and $m_1$ of $k$ bytes, this is expected to require on average less than $2^{8k+26}$ attempts.


I'm assuming here that you are talking about this Signal defined protocol.

It depends. It basically hangs on one of the very first security consideration:

Security considerations
4.1. Authentication

Before or after an X3DH key agreement, the parties may compare their identity public keys IKA and IKB through some authenticated channel. For example, they may compare public key fingerprints manually, or by scanning a QR code. Methods for doing this are outside the scope of this document.
If authentication is not performed, the parties receive no cryptographic guarantee as to who they are communicating with.

Now if authentication is not performed for one of the parties then the protocol would allow the impersonation of that party by controlling (or acting as, if this is not protected otherwise) the server. That's not entirely the same as a MiTM attack - only the untrusted party can be impersonated after all.
Only if the public keys of both parties are not trusted can a full MitM attack be performed. An MitM means that both parties are impersonated, after all.

Note by the way that in the rather dumbed-down description of the protocol it seems that Alice is not authenticated. That's not true.
See the following line in the protocol:

$$\mathrm{DH1 = DH(IK_A, SPK_B)}$$

Here $\mathrm{IK_A}$ must clearly be the private key of Alice and $\mathrm{SPK_B}$ must be the public signed prekey of Bob. That's a horrible notation that they use because $\mathrm{IK_A}$ is introduced earlier as a public key and $\mathrm{SP}$ is commonly used to refer to a secret (or private) key. This is all done under the because:

All public keys have a corresponding private key, but to simplify description we will focus on the public keys.

and that led unfortunately to the invalid description of the DH protocol.
Still, that does mean that Alice is authenticated as well, not by using a signature, but by using her authentication key pair as part of the calculation of the shared secret key.
Bob of course needs to use the corresponding public key in his calculations, but that is hidden by the following line:

Using these keys, Bob repeats the DH and KDF calculations from the previous section to derive SK, and then deletes the DH values.

This means that Alice identity is confirmed implicitly by verifying the authenticated, encrypted part of the initial message. It's kind of scary that this part about Alice's authentication is missing entirely from the protocol description; hopefully implementations will handle bad authentication tags within the ciphertext of the initial message as authentication failures.


How will Cryptography be changed by Quantum Computing?

Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical algorithms, but the best known quantum attack against AES is effectively "try all the keys." In a quantum computer, the time taken to solve a general search problem (such as "find the AES key that gives a reasonable message") scales slower than for a classical computer; this would effectively turn an n-bit key into an n/2-bit key. Fortunately, that would leave AES-256 with an effectively 128-bit key against a quantum attacker, which is still believed unfeasible to crack. Similar considerations apply to hashes. You'd want to increase key lengths and the like, but you could fairly reasonably do that.

The main issue is actually asymmetric cryptography. Unlike symmetric crypto and hashes, asymmetric algorithms have extreme levels of mathematical structure -- they're based on the difficulty of a single hard problem. The two main problems used for this can be solved extremely quickly on a quantum computer; if you tried to increase key lengths to make it take a long time there, it'd take an infeasibly long amount of time for the legitimate user on a classical computer to use the long keys. However, this is something of a historical accident: there's no reason asymmetric crypto has to be easily breakable by a quantum computer, it's just that the most commonly used ones happen to be easily breakable by one. Others may not be; post-quantum cryptography is an active research area, and people are working on algorithms that rely on problems not believed to be efficiently solvable by quantum computers.


What MAC did SSLv3.0 use? How did it compare to HMAC in TLS 1.0 and above?

The key was concatenated in SSL 3.0:
    hash(MAC_write_secret + pad_2 +
         hash(MAC_write_secret + pad_1 + seq_num +
              SSLCompressed.type + SSLCompressed.length +
              SSLCompressed.fragment));

but XOR'ed in HMAC:
    H(K XOR opad, H(K XOR ipad, text))


Last Sbox of a block cipher for Linear Cryptanalysis

If you include a key addition layer ($K_1$) at the output as well the key addition layer ($K_0$) at the input of the Sbox then you can perform linear cryptanalysis on this simple cipher. You shall have access to $P,C$ pairs but no keys, of course, and the $P/C$ relationship is
$$C=K_1\oplus(S(P\oplus K_0))$$
and so your linear bias equations become something like
$$
\textrm{bias}(A,B)=\sum_{P} (-1)^{B \cdot (C\oplus \hat{K_1}) + A \cdot P}
$$
where  $A$ is the input mask, $B$ is the output mask, $P$ plaintext, $C$ resulting ciphertext and you choose the most likely key guess $\hat{K_1}$ which maximizes the observed bias. Before this, you choose the best mask pairs $(A,B)$ with $A\neq 0$ which give the best bias for the Sbox linear characteristics defined below
$$
\sum_{X} (-1)^{B \cdot S(X) + A \cdot X}
$$
where the sum ranges over the input set of the Sbox, and perform the attack for that $(A,B).$


I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered.

That is not known to be true; as long as the modulus is large enough to make factorization infeasible, there is no known way to compute e-th roots in general.

Now, if the plaintext $p$ is small enough that $p^e < N$, then it is easy to recover $p$ (just take the e-th root over the integers, which is an easy problem).  That's as close as we know to the result you're trying to get.

  Would this be inversion: Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.

If $N$ is small enough to make work in a practical amount of time, then $N$ is small enough to factor.


Fastest multiplication algorithm for efficient exponentiation in C++?

It depends on the length of the inputs and characteristics of the target platform:

If inputs are short (at most around a thousand bits), try a Comba multiplication.
If inputs are short and your platform has a lot of registers, try a hybrid Comba multiplication.
If you have a multiply-accumulate instruction, give a shot at Schoolbook multiplication.
If inputs are larger, divide-and-conquer approaches (Karatsuba, Toom-Cook) start to become faster.


AES-128 or AES-256 with 18 bytes of key storage?

I'd argue for (3) for these reasons:

the algorithms are used within their operating assumptions;
related: AES may be insecure if the keys have a specific format;
no entropy is lost when performing the conversion to 32 bytes as compared to (1).

AES-128 is also considered secure at the moment, but it may not be if quantum computers are created that enable Grover's algorithm. So there is some reason to prefer AES-256 over AES-128. Of course, Grover will still work for 18 byte keys as well, but with the KDF you'd have at least a trickier target.
Of course you'd want a KDF that provides 256 bits of security, accept 18 byte input key material and provide key expansion. HKDF would probably be a good choice.

Note that you could argue that reason #1 & #2 is rather speculative. Actually, the NIST FIPS 197 standard (AES) reads:

No weak or semi-weak keys have been identified for the AES algorithm,  and there is no restriction on key selection.

However, AES doesn't have the strongest key expansion routine, and I'd also be somewhat worried about side channel attacks. Better error on the safe side...