How to attack polyalphabetic affine cipher with only ciphertext?

This is a simple variant of the Vigenère cipher, and can be broken in basically the same way:

First, you need to determine the key length.  The standard methods for doing this for any Vigenère-like cipher, like Kasiski examination or calculating the index of coincidence, work just fine here.

Once you've determined that the key most likely consists of $k$ separate affine maps, you then split the plaintext into $k$ columns, each encrypted with a different affine map, and break each of them like you'd break a normal monoalphabetic affine cipher, using letter frequency analysis.

Note that crib dragging or $n$-gram frequency analysis generally won't work for solving the columns, since the letters in each column aren't consecutive in the plaintext.  On the other hand, since you have multiple columns taken from the same plaintext, you can mostly solve the cipher without knowing the actual letter frequency distribution of the plaintext (as long as it's sufficiently non-uniform).

To do that, simply take the letter frequencies from one of the ciphertext columns (say, the first one) and use them instead of the expected plaintext letter frequencies to solve all the other columns.  Assuming that you have enough ciphertext for the statistical analysis to yield robust results, and that the plaintext doesn't just happen to contain any repetitive elements with period equal to the key length, this should give you a "pseudo-key" that, when used to decrypt all the other columns, will convert them to the same cipher alphabet as the first one.  Thus you can effectively reduce the polyalphabetic cipher into a monoalphabetic one, which you can then solve e.g. by brute force.

(For increased robusteness, you can do the same thing with each of the ciphertext columns as the reference column, and check that the resulting affine maps between the columns are consistent with each other.  If you find any mismatches between the maps suggested as most likely by frequency analysis, that can be a sign that some columns don't have sufficiently similar plaintext letter frequency distributions.  In that case, you may want to examine the other reasonably likely maps found by frequency analysis to see if they'll solve the mismatch.)

This works because affine maps form a group.  In particular, the inverse of any affine map is an affine map, and so is the composition of any two affine maps.  Thus, decrypting a ciphertext column with one affine key and re-encrypting it with another is always equivalent to encrypting (or decrypting) it with some third key.  The same trick works for ordinary Vigenère ciphers too, and for any other repeating-key substitution cipher (like the XOR cipher) whose underlying monoalphabetic substitutions form a group.


How is the root certificate transmitted to pc?

You are correct that getting the root certificate to the end user is a problem. There are two usual ways to solve this:

Out of Band: The root cert is carried by USB stick, or is placed on the system during install, or is pushed by an IT management tool, or by some other non-internet method.
Certificate Pinning: As an example, Firefox includes in its source code the root certs of all the publicly trusted SSL CAs. When you connect to an HTTPS site, Firefox checks that the root issuing cert matches one of the ~50 that are hard-coded into its source code. If Firefox wants to add / remove / modify one of the pinned root certs, it has to push a security patch to everyone. Since the binaries for Firefox are signed, it is difficult (though I'm sure not impossible) to plant a fake root cert in the list.


Can CBC encryption have separate keys for separate blocks of plain text?

SHORT: The key remains the same. CBC mode is one of the ways which allow block cipher to securely process multi block input.

Block cipher with single key produces same output for same input, as it is relatively common for input to contain duplicate blocks, instead of using block cipher as is, a more complex construct is needed.

The idea of CBC mode is that the ciphertext of the previous block affects encryption of the next block. Specifically, plaintext input is XORed with the previous block cipher text (or with "Initialization Vector" also known as IV) for the first block. This operation is much less time consuming than key change.

So shortly, the benefit of CBC mode is that it allows securely using the block cipher, something that raw block cipher (ECB mode) generally does not allow for multi block messages.

In addition to CBC mode, also numerous other block cipher modes of operation exist. There are circumstances where one of the other block cipher modes of operation is more appropriate than CBC.

The most basic block cipher modes of operation (ECB, CBC, CFB, OFB, CTR) are described e.g. in Wikipedia and NIST Special Publication 800-38A. The Wikipedia article contains great picture, which illustrates the need for modes of operation beyond ECB.


Why Static RSA and Diffie-Hellman cipher suites have been removed in TLS 1.3?

TLS 1.3 has a huge clean up as having 5 cipher suites. As stated in the RFC document RFC 8446 section 1.2 :

  Static RSA and Diffie-Hellman cipher suites have been removed; all public-key based key exchange mechanisms now provide forward secrecy.

With forward secrecy (also called PFS for Perfect Forward Secrecy), even if one of the site's key is compromised, the previously generated keys are safe since there is no method that can regenerate them. The keys are called ephemeral keys.

You can still use ECDH in TLS 1.3 for key establishment but not statically. This version also named ECDHE where the last E is Ephemeral.

There is one drawback, that is; even if you use FPS, the other side can not only store the keys but can also store all the decrypted messages. You don't/can't know that. Storing is not recommended but you cannot prevent that.

When one side stores the keys, it is the opposite of the forward secrecy. Once the attackers breached into the site that will access all the stored keys, but the system was perfect secrecy! Actually, the keys must be erased after the decryption.

See also, misuse of forward-secrecy on Squeamish Ossifrage's answer.


Why encrypt symmetric keys first with RSA and then the private-key with a PW?

There are a few likely, closely related reasons for this:

you need both a password and the encrypted private key to decrypt (i.e. you need two factors);
it is possible to attack the password for the encrypted symmetric key using an offline attack, even if it is using a key derivation function such as PBKDF2.
private keys can also be stored on smart cards that perform the private key operation, that way the decryption key can be stored even more securely, and protected against offline attacks.

Reason 2 is of course also possible for the encrypted private key, but generally we can assume that the encrypted private key is less accessible to an attacker.

Another possible advantage is that you may not need a password or private key to encrypt the symmetric key. If this is an actual advantage is of course dependent on the use case. For file systems it seems like a useful feature, but I don't think it will be the one that tips the balance.

The major drawback is of course that you cannot just remember a private key; you need some kind of connected computing or at least storage device for the encrypted private key. If you store the private key and leak it (e.g. copy it over and not securely delete it) then a lot of the advantages can be lost.


Save the last cycle in GCM GHASH calculation

Well, the GCM tag can be rearranged as $Tag = (Len(C, A) \times H) \oplus \textit{Other Stuff}$; if the length of your ciphertext (and additional authentication data) is consistent, you could precompute $Len(C, A) \times H$, and xor that in along with everything else in the final step.

One note: the (add/multiply) that you do in cycle 6 has the side effect of multiplying the result of the GHASH from the ciphertext by $H$; if you eliminate that multiply, you'd need to somehow get the same effect.


Can I construct a feasible stream cipher out of HMAC and a secure hash algorithm?

Here is your algorithm in formula form, which might be easier to understand for non-objective-C-experts:

Encryption:

$P_1 \mathbin\Vert P_2 \mathbin\Vert \dots \mathbin\Vert P_n := P$ (split plaintext in blocks, same size as hash output, except the last one)
$K := \operatorname{SHA256}(\mathit{key})$
$O_0 := \mathit{IV} (= K)$
$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, O_{i-1})$ for all $i \in \{ 1, \dots, n\}$ (key stream)
$C_i := P_i \oplus O_i$  for all $i \in \{ 1, \dots, n\}$ (the usual stream cipher XOR)
$C := C_1 \mathbin\Vert \dots \mathbin\Vert C_n$

(where the last block $O_n$ is truncated to match the length of $P_n$)

Decryption: same, but with $C_i$ and $P_i$ swapped.

$P_i := C_i \oplus O_i$  for all $i \in \{ 1, \dots, n\}$

As you remarked right, this is output feedback mode (OFB) with HMAC-SHA-512, with the key reused as the IV. (The value you named IV – $K$ here – is actually the effective key, derived by SHA-256 from the original key, the IV is your first segkey, initialized to the same value).

If you use the commented variant with

$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K \mathbin\Vert C_{i-1}, O_{i-1})$,

you have some new mode which is like a mixture of cipher feedback mode and output feedback mode, which uses the cipher feedback as part of the key (?). It is not a synchronous stream cipher anymore, as the keystream depends on the previous ciphertext. You can still decrypt it, you just have to use the previous version of segment instead of the previous version of last as input in the decryption function (i.e. you need one more variable in your program).

If you want to stay with established modes of operation, here is cipher feedback mode (CFB):

$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, C_{i-1})$

This is Counter mode (CTR):

$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, i)$

The analogons to ECB, CBC, PCBC don't work with a MAC (or other PRF like a keyed hash), as there is no inverse which would be needed for decryption.

Also, as Ivella remarked, your stream cipher is a lot slower than dedicated stream ciphers, or the same modes applied to a block cipher.


Interpreting Figure 1 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography"

The points of $\mathbb Z/q\mathbb Z$ are mapped to $\mathbb R/\mathbb Z$ and plotted in a circle.  The plot shows
\begin{align*}
  x &= \sin (2\pi i/q), \\
  y &= \cos (2\pi i/q), \\
  p &= \Psi_\alpha(i/q).
\end{align*}
for each $i$ in the least nonnegative residues modulo $q$.

The following gnuplot script gives a similar graph, for $q = 31$:

set parametric
set samples 31
psi(alpha, r) = exp(-pi*(r/alpha)**2) + exp(-pi*((r - 1)/alpha)**2)
splot [i=0:30] sin(2*pi*i/31), cos(2*pi*i/31), psi(0.1, i/31) with points


In such terms, I suppose you should to find GCD of two numbers Key1 and Key2. It seems that with big probability it will give to you one of the prime number which was generated by compromised generator.
Pollard`s method is very hard, and I doubt, that you can successfully apply it in the case.


Is it possible to reverse Diffie-Hellman key exchange?

It is certainly possible given enough compute resources.

However, if you mean to ask whether it is computationally feasible for an eavesdropper to derive the private keys, then- no, it is not.

Refer to the secrecy chart on Wikipedia:

The private keys a and b are meant to be known only to Alice and Bob respectively.

In the real world, the Logjam attack is one example of how adversaries with nation state-level compute resources (such as the NSA) could theoretically break Diffie Hellman implementations, relying on the fact that a small set of primes were used across most common implementations.


It is proportional to $poly(k)$. Here $k$ is the security parameter (or more strictly speaking it should be $(1^k)$) and intuitively the adversary's can only be allowed to query polynomial times (since it is a PPT algorithm) bounded in terms of $k$. Then $e$ and $e'$ only differs by a polynomial factor, and thus allows you to reduce what you want to prove to the RSA problem.

The subtle technicality is that when modeling the adversary as a Turing machine and reasoning complexity (which is based on the size of input), the integer $k$'s length is only $log_2 k$, which will cause some formality problem. The more rigorous way is to supply $1^k$, a bit string of length $k$ that contains all 1s.


Java recover the public key by only having the privatekey possible?

OK, I will take a stab in the dark and ask the cryptographic question at hand.

  Given a private key, can we recover the public key?

The answer is it depends, but usually you can.

If we are talking about RSA, then the private key sometimes is depicted as "only" being $d$, which isn't enough to recover $e$ and $n$ (even though $e$ is usually fixed). However practically, all decent forms of encoding and libraries should store auxiliary information as their private key, which usually includes $d,n$ and some other values and from $d$ and $n$ we can easily derive, guess or brute force $e$ (see this Q/A on the site for more information).

If we are talking about elliptic curves, then the private key is some integer $a$. Again this integer alone is not enough to recover the public key, but as soon as we also learn which curve is used (which is usually stored in the private key format as well), we can recover the public key the same way as we do during key generation, using scalar multiplication on the curve, i.e. $P=[a]G$.

Now on your StackOverflow post, people have commented "nope" or similarly unhelpful statements. These are false (as you can see above).  However, they apply for the converse statement. That is, given a public key, you can't (easily) recover the private key.


Is it possible to prove the time a message was produced?

If the the message is generate by a one-way function then incorporating in the message a sample from a randomness beacon (such as https://www.nist.gov/programs-projects/nist-randomness-beacon) will prove that the message was generated at a time later than when the sample was taken.


Can a salt for a password hash be public?

The usual answer is that a salt can be make public; if that was a problem, then the salt would not be called a "salt" but a "key".

In some protocols, unauthenticated obtention of the salt is the norm, and is not considered to be a problem. E.g. with SRP, a password-authenticated key exchange, where any salting and hashing must necessarily occur client-side.

Some people have argued that if the attacker can know the salt in advance, then he can do precomputations. This is a gain for the attacker only in a specific scenario, where the context is such that the attacker must be able to crack a password within a very short time frame (say, one second) but has a few weeks to prepare for his one-second attempt, for a specific target user. This is a fringe scenario which very rarely applies.


There is a reasonably clear description in section 2 of Pascal Junod's thesis.

A linear approximation, which allows guessing 1 key bit

Linear cryptanalysis begins by finding a linear equation which holds with probability distinct from $1/2$. We are talking about linearity in $\mathbb{Z}_2$, i.e. we XOR bits together. The question is a XOR of some specific bits of the plaintext, the ciphertext and the key (I am talking about linear cryptanalysis of a block cipher, as it was originally designed, about DES by Matsui in 1993). The XOR of several bits is either 0 or 1, and, assuming that the block cipher is "perfect", it should give 0 with probability $1/2$ and 1 with probability $1/2$.

Now let's assume that a given equation will yield 1 with probability slightly higher than $1/2$: for a given key, if you do the XOR with many plaintexts and corresponding ciphertexts, you will get 1 a little more often that you will get 0. This is the bias which linear cryptanalysis will exploit.

The first basic step is that by gathering many plaintext/ciphertext pairs, where the encryption used the key we want to attack (this is a "known plaintext attack"). For each of them, the equation is a XOR between a few bits of the plaintext, a few bits of the ciphertext, and a few bits of the key. For each pair, we know the plaintext and ciphertext, so the equation tells us what is the value of the XOR of the few key bits. The equation is "right" a bit more often than "wrong", so, with enough pairs, a majority emerges and gives us a definite answer. This yields 1 indirect key bit.

Guessing many more key bits

1 key bit is not much (although it divides by two the cost of exhaustive search), so Matsui enhanced the attack in the following way. Let's consider the linear cryptanalysis over the first 15 rounds of DES (DES has 16 rounds). That cryptanalysis has a corresponding linear equation. A quirk of DES (at that point it becomes useful to have a look at some schematics about DES) is that we can "mostly" see the output of the 15th round. For linear cryptanalysis, we are interested in some specific bits of the plaintext and of the "ciphertext", the ciphertext being here the output of the 15th round. We have the output of the 16th round; from it, we can compute the value of the bits we are interested in, from the output of the 15th round, provided that we correctly guessed a dozen specific key bits. That's because the 16th round modifies the output of the 15th round using the key, but not all key bits are involved in the computation of each bit for this round. Only 12 key bits in total have any influence on our "back-computation" where we try to compute the bits-for-the-equation in the 15th round.

Now comes the really smart part. Matsui runs 4096 linear cryptanalyses in parallel. That is, given the plaintext/ciphertext pairs (for the full 16 rounds of DES), Matsui tries each of the $2^{12} = 4096$ possible values for the 12 key bits, each of them allowing him to recompute the output of the 15th round, and apply the 1-bit linear cryptanalysis. Now, for the one instance where he guessed correctly, the 1-bit linear cryptanalysis "works" and a clear majority emerges; but for the others, the incorrect guess on the key bits means that we work with wrong values (for the 15th-round bits), so the equation does not work and no clear majority emerges. So the attack not only yields one indirect key bit (from the equation) but also twelve additional key bits: the twelve bits which make the 15-round linear approximation work. 13 key bits, now that's good: it divides cost of exhaustive key search by 8192.

Matsui got even further by doing the "guess some key bits" for two rounds, the first and the last, using a linear approximation of 14 rounds (rounds 2 to 15). This yields 22 direct key bits (and one indirect). DES has 56 key bits, so the remaining $2^{33}$ are easily obtained by exhaustive key search (only 8 billions of possibilities).

Limitations

The real problem with linear cryptanalysis is that it needs many known plaintext/ciphertext pairs, enough for a clear majority to emerge when applying the linear approximation (the equation is only slightly more often right than wrong). Matsui computed the number of needed pairs to be $2^{43}$, although Junod found out that with a few tweaks, $2^{39}$ are enough. Each plaintext is 8 bytes, so we are talking about 4 terabytes. There are not many attack situations where the attacker can correctly guess 4 terabytes of plaintext, and still needs to obtain the key...

(Linear cryptanalysis of DES is how I first entered the realm of cryptography; my task was to reimplement Matsui's method on DES reduced to 8 rounds. The approximation on 6 rounds is much better than on 14 rounds, so it requires only a million or so plaintext/ciphertext pairs. It took less than a minute on the machines of that era, 50 MHz Sparc systems. The part about guessing some key bits and doing many 1-bit cryptanalyses simultaneously is what took me the most time to understand. It was very educational.)


A modification of the Blum-Micalli construction

Discuss the advantages/disadvantages of outputting also $f^l(x)$.

Knowledge of the trapdoor secret would allow the receiver of a message encrypted with the  pseudo random one time pad to recover the seed $x$ if one block of the generator output would be xored with a fixed value known to both the sender and receiver.

This would allow to encrypt more than one message by using a random seed for each message. If the seed could not be recovered from the ciphertext then sender and receiver had to securely exchange random seed values for each message in order to avoid using the same pseudo random one time pad twice.


Yes, P-256 generates 256 bit private keys (give or take a single bit).

The confusion here is that this key is 256 bit effective (giving ~128 bit security) even if it starts with zero bits. So the private key is 256 bit even if the representation as a large integer can be smaller than the requested size. This simply means that the full key space is being used. So there is a relatively big chance (about 1/256) that the big endian encoding of the integer is one byte smaller. Most libraries however require an integer to octet string primitive to be used (I2OS or I2OSP). This represents the private key in a static number of bits, e.g. 256 for the above.

The same is true for RSA by the way. Always expect numbers to start with a random number of zero bits, unless this is explicitly not possible. And be warned against signed/unsigned representations, of course.


It sounds like you're thinking of AES-GCM-SIV as "AES-GCM with an SIV layer on top."  It's not.  Rather, AES-GCM-SIV is a separate encryption mode build out of similar (but not identical) components as AES-GCM, and where the components are combined in a different way.  While AES-GCM-SIV is in some ways similar to AES-GCM, you can't actually implement AES-GCM-SIV as a wrapper on top of an existing library that implements AES-GCM.
What makes things a bit confusing is that there is also something called the generic
"SIV construction" that allows a nonce-misuse-resistant authenticated encryption mode to be constructed out of any conventional (non-authenticated) encryption mode meeting certain technical criteria plus any pseurodandom function (PRF) on the plaintext space.  For example, AES-SIV (RFC 5297) is an instance of the SIV construction with AES-CTR as the encryption mode and CMAC* (a multi-input variant of CMAC) as the pseudorandom function, while AES-GCM-SIV is essentially an instance of the SIV construction with (again) AES-CTR as the encryption mode and POLYVAL (a variant of the AES-GCM pseudorandom function GHASH) as the PRF.
But that doesn't mean that you can just take an AES-GCM implementation and use it to implement AES-GCM-SIV, at least not without first pulling it apart into its component parts.  And even then, the components of the two schemes (as standardized in their respective RFCs) differ in some details (like byte order; see RFC 8452 appendix A), so you can't just reuse the parts without modification, either.
Technically, I believe you could implement AES-GCM-SIV on top of GHASH and AES-CTR, if your crypto library exposes both of those directly.  However, that would require implementing POLYVAL on top of GHASH, which, while technically possible, is somewhat awkward and inefficient due different byte orders used by the two hashes.


How to solve rubix-cube like symmetric encryption

Is this the correct way to solve a rubix cube (reversing the moves)?

This isn't really a question about cryptography, and might be better suited for a math or even puzzling stackexchange site.

That being said, while reversing the moves is a way, and is probably the way that you would use to undo the transpositions of your cipher considering you use the ordering of moves as your key, that does not necessarily mean that given an actual Rubik's cube the solution is to invert the moves that shuffled it from the initial position.

  If not, what would the correct way be?

There apparently exist optimal algorithms for solving a traditional 3x3x3 cube in 20 steps. These don't appear to assume that you are inverting the steps that shuffled the cube. Your setup may be larger, but that still doesn't bode well for using the shuffling as some kind of cryptographic hardness assumption.


Once you've XORed two messages with the same secret value, the net result is the same as if you had XORed them with each other without using the secret at all.

Given $plaintext_1$ ⊕ $key$ = $cyphertext_1$ and $plaintext_2$ ⊕ $key$ =  $cyphertext_2$, then $cyphertext_1$ ⊕ $cyphertext_2$ == $plaintext_1$ ⊕ $plaintext_2$.  Because it's XORed twice with the same key, the double XOR becomes the identity function and the key is simply factored out.

If the attacker learns any bits of the plaintext of either message, they can recover those corresponding bits of plaintext from the other cyphertext message, plus they can recover those bits of the key as well.

So it falls to you to determine if $cyphertext_1$ or $cyphertext_2$ have any knowable information in them.  It's completely irrelevant if the plaintext data is ASCII, binary, or EBCDIC.  If an attacker can discover or guess what any piece of the data is, it's vulnerable.

This is the classic weakness with the Vernam cypher, and is what enabled the Venona decryption of Soviet secrets.  And it's why it's no longer a one-time pad cypher if you use either the plaintext or the key more than one time.


Can a user of a password-protected Wi-Fi sniff on other user's communication?

Well, it depends on the which protocol is being used.

For WEP and WPA, the keys used are derived directly from the pre-shared keys; that means that as long as you know the pre-shared keys, you can immediately decrypt packets as well.

On the other hand, WPA2 is somewhat stronger; the two sides exchange nonces to derive the keys.  Hence, unless you listen into the initial exchange, you're out of luck.  On the other hand, depending on when you start listening, this might not be that great of an improvement.


How to Formalize Noise Protocol Messages

ee and es aren't values, they're function invocations.

ee denotes the use of a Diffie-Hellman key exchange using two ephemeral keys, es denotes the use of a Diffie-Hellman key exchange using an ephemeral key and a static key. The first letter is the initiator, the second is the responder.

So it's just $ee = DH(e, re)$, $es=DH(e,rs)$, $se = DH(s, re)$, $ss = DH(s, rs)$, where $DH(i,r)$ is the Diffie-Hellman exchange function applied to the $i$nitiator's key and the $r$espoder's key.


Combining several symmetric ciphers using XOR

The usual method to do this is to turn the block cipher into a stream cipher. In that way the ciphertext is generated by XOR'ing the plaintext with a generated key stream. This key stream in turn is generated by the mode of operation that turns the block cipher into a key stream. There are several of these modes, but CTR mode of operation is most often used (in new protocols anyway). You don't need to do this for stream ciphers of course.

Now you can just use $C = P \oplus K^1 \oplus K^2$ where $C$ is the ciphertext, $P$ is the plaintext and $K^1$ is the key stream of one cipher and $K^2$ is the key stream of the other cipher. As XOR is associative and commutative you can see this as first applying key stream 1 or key stream 2, and then the other. The key streams will have the same size as the plaintext.

This is similar to applying two one-time-pads to the plaintext. Given a secure block cipher, a key stream generated using CTR is secure but not perfectly secure. So it's not identical to using two one-time-pads. One difference with a one time pad is that CTR mode requires a nonce; the same nonce can be used for both stream ciphers though.

In contrast to one time pads it is possible to cryptoanalyze a stream cipher. This means that the key streams should be sufficiently independent of one another. So the stream ciphers should be created using separate keys and ciphers. If you would use the same key, IV and cipher then key streams would cancel each other out, leaving you with the plaintext after encryption.

Small stream cipher introduction

With a stream cipher a key and a nonce are used with the cipher to generate a key stream of any size. Usually the plaintext is not needed as input at this stage. The key stream is then XOR'ed with the plaintext. As the key stream should be indistinguishable from random to an attacker, it should be impossible to invert this operation without the key and nonce. Decryption is identical to encryption and if a block cipher is used then you may only need to use the block cipher in one direction (encryption or decryption). You can encrypt and decrypt by applying the key streams in any order as the XOR operation is associative and commutative.


The APK signing is well documented by Android, actually:

You have here a high level overview of the process.
A new APK signature scheme (v3) has been introduced with Android 9, that is detailed  here. However notice the v2 can still be used.

The documentation about v2 has a good overview of what is contained in a signature block in an APK:

  For each signer, the following information is stored:

  (signature algorithm, digest, signature) tuples. The digest is stored to decouple signature verification from integrity checking of the APK’s contents.
  X.509 certificate chain representing the signer’s identity.
  Additional attributes as key-value pairs.

Now, what does that mean?

Well, the signer has to own the secret key corresponding to a certificate, that has to be verified by some Certificate Authority. The signer can then sign an APK and has to bundle their certificate chain inside of the APK, so that anyone can verify the certificate chain, and if it checks out, then check that the signature verifies under that certificate.
And the certificate is required in order to be able to link the public key we are using to verify that APK with a given identity. (Because otherwise, without certification, you have no link between a given secret/public key and an identity.)

Here "digitally signed with a certificate" is a misuse of language to mean that one is signing the APK using the private key corresponding to a public key stored in a certificate.

This is effectively done in practice by computing the signature of a digest (a hash) of the  of APK contents that is computed as indicated here.


How much time will it take to brute force a password

There is a basic problem with your idea, which makes the entire calculation and the result pretty much meaningless. Your actual question is:

Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker.

Let's keep that in mind for now. You want security.

We'll assume that the password is at least eight characters long with a mix of numbers and upper, lower, and special characters. So that makes 72 possibilities per character
Thus total passwords to brute force = 72^8 = 722 trillion

It is approximately $722$ trillion, that is not equal to $72^8$ but an approximation. Other than that, this is fine (although I find $10^{12}$ more intuitive than trillion).

If I want it to take 100 years to try all possibilities using 10 computers, then per second my settings should be able to produce 22,900 passwords
Now what I am unable to figure out is, how many iterations would it take to limit a GPU such as 8x Nvidia GTX 1080 to be able to generate 22,900 passwords?

We can assume HmacSHA1 or HmacSHA256

Okay, these all belong together and can't be answered alone. Your math in 3. is fine, the question in 4. can be answered with basic arithmetic and a benchmark of the system, and the statement about the used algorithm is needed to answer number 4 at all.
I think it would be much clearer to go this way:

Find a benchmark or generate one yourself. For your specific setup I found this source. It only lists SHA1 and SHA256, but for a rough approximation it's fine to consider two hashes euqal to one HMAC ($0.5$ times the number of hashes per second). For SHA-256 it's around $23\cdot 10^9$ hashes per second and SHA-1 almost exactly three times this number.
Calculate how long it takes for your setup ($10$ systems) to test all combinations ($72^8$ - but actually this is a lower bound, not the exact number).  For example for HMAC-SHA256 this would be: $\frac{72^8}{0.5 \cdot 23 \cdot 10^9} \approx 62800$ seconds for one system, and thus $\approx 6280$ seconds for 10 systems.
If you want to achieve "security for a 100 years", calculate the number of requires iterations as $6280 x = 3153600000$, where the righthand side is the number of seconds in 100 years. The result is approximately $5 \cdot 10^8$.

To put this number into context: You can't run these $500$ million hashes in parallel. According to this list SHA256 can process around $223 \cdot 1024^2$ Byte per second, with blocksize $512$ bit that's around $3.65$ million SHA256 operations per second. So as a very rough estimate we get $\approx 137$ seconds for $500$ million iterations.

Now let's go back to the original question:

Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker.

Unfortunately, you completely disregarded that passwords are not uniformly distributed - and you are asking about a hacker: a person who can adapt  and choose which values to test first - it is not just a brute force algorithm.
Passwords are usually not drawn from all possible passwords with equal probability, but they are usually chosen by a person instead. The hacker knows this - and he can use it to his advantage. This can be used e.g. in a so-called dictionary attack - and if we talk about passwords we have to keep this in mind.
An alternative point of view is: Passwords actually have much less entropy than a truly random (uniformly and independently drawn) string of the same length with the same set of symbols.
So while your idea is not entirely wrong, it does not have any meaning regarding the security of the password - unless you can make sure that the passwords actually are not chosen by a person but generated with the full entropy.

Instead of trying to make up your own password hashing scheme and calculations like this one, I would suggest checking out existing solutions. There are key-derivation functions for passwords, e.g. Argon2 won the Password Hashing Competition (from 2013 to 2015). Another popular function is scrypt, and previously PBKDF2 (I wouldn't recommend using this today, but it was very popular at some point). All of them offer various parameters you can adjust to your needs, including more than just number of iterations. The modern ones allow you to adjust the memory requirement to evaluate the function, which is an entirely different countermeasure to the full search than just increasing the number of iterations.


Observe that for any $n$, $l$, as long as $l | n$, any equivalence $a \equiv b \pmod n$ also holds mod $l$: $a \equiv b \pmod l$ .
To fully see this, we can write
$$
\begin{align*}
    a &\equiv b \pmod n \\
    \Leftrightarrow \\
    a &= b + kn
    \\&=b + ktl \quad(\text{since } l|n\text{, so } n = tl)\\
    \Rightarrow\\
    a &\equiv b \pmod l
\end{align*}
$$
So you could solve $m^e \pmod p \equiv a$ and $m^e \pmod q \equiv b$, then use CRT to get $m \pmod n$.


Cryptography: Oblivious Transfer with at most one transfer?

The obvious approach is to help Bob learn $s_0 \oplus (s_0 \oplus s_1) \times c$, presumably using $F$ to help him learn this information.  So, here is the natural protocol:

Alice and Bob invoke $F$.  Alice provides the input $s_0 \oplus s_1$, Bob provides the input $c$.  Alice learns $p$ and Bob learns $q$, where we are guaranteed that $p \oplus q = (s_0 \oplus s_1) \times c$.
Alice sends $p \oplus s_0$ to Bob.

Notice that, with this information Bob can compute $s_c$.  I leave it as an exercise to you how to do that.

Also, notice that Bob learns only one of $s_0,s_1$.  I leave it to you as an exercise to prove that.

Finally, notice that if $F$ does not disclose anything about its inputs to either part, then Alice does not learn anything about Bob's bit $c$.


Are there any existing open source implementations of "id-tied" public/private key encryption?

What you're looking for is probably Identity-Based Encryption (IBE).
I'm not sure if I've got the terminology correct, but here's a few concept with IBE.
IBE has a key generation center that has a function equivalent to a CA. The key generation center manages a master private key for deriving private keys for decryption users, and a master public key for which encryption users to derive the public keys corresponding to the decryption users.
The rest is pretty much the same with other public-key encryption: encryption users encrypt their messages with the public key of the decryption users and send the ciphertext to them; the decryption users decrypt the message with the private key they've obtained from the key generation center.
It is to be noted that there is the obvious problem of key escrow and difficulty with revoking exposed private keys.
China has developed the SM9 identity-based cryptography standard. An English version is available at IACR. The official version is in Chinese, and is behind paywall, some provincial administration publish free links to Baidu Netdisk file sharing service.
The OpenSSL fork GmSSL mentioned in the comment, has appears to be the most comprehensive implementations of Chinese commercial cryptography standards.


Is it safe to use unauthenticated AES CBC when encrypting random bytes?

Is this a safe implementation?

No. An adversary can change just the first encrypted block that contains part of the AES data key. Then HMAC authentication will succeed, but decryption with the AES key will result in the wrong plaintext message. If an IV is used then the IV can also be changed, resulting in only the first 128 bits of the AES data key to be changed.

After all, CBC has limited error propagation, and the block size of AES requires a minimum of 4 blocks to encrypt two 256 bit keys.

If padding is used then padding errors may also result in a padding oracle attack on the key material. But those would only work in a limited amount of scenarios.

  Does the fact that the key material is random byte data change its need to have HMAC authentication to protect it from attacks?

No, not necessarily. It depends on how the random data is used. If alteration of the random data can help with creating an active attack then integrity / authenticity is required. To state that it doesn't need protection just because it is random data is certainly wrong.

  Is the key material decryption from step 4 subject to the same attack vectors as standard string decryption, as in step 5?

No. The bits of the encrypted random data are unrelated to each other and they do not need to be padded, which thwarts many attacks on CBC mode. But it still has limited error propagation and no integrity / authenticity.

PBKDF2 should indeed be limited to generate only as many bits as the internal hash function provides. Generally you'd use an additional Key Based Key Derivation Function or KBKDF such as HKDF to derive the keys from a master secret, generated by PBKDF2:

$$K_{master} = \text{PBKDF2}(p, ...)$$
$$K_{enc} = \text{HKDF}(K_{master}, \text{"enc"})$$
$$K_{mac} = \text{HKDF}(K_{master}, \text{"mac"})$$

This doesn't require any additional storage as the labels "enc" and "mac" are simply constant values.

An ugly hack would be to also include the IV (if present) and ciphertext of the encrypted keys in the HMAC verification. I'm just mentioning this because the protocol may have used this already - it could be just a change of an offset - and it may have been overlooked.


How does the possible attack on passwords and salts mentioned in PKCS#5 v2.1 work?

This appears to be describing an attack that allows an active attacker to defeat a seemingly-secure protocol.

In the normal setting where no one is attacking them, Alice and Bob share a password $W$; Alice derives a symmetric key $K$ from the password $W$ and encrypts her message with $K$, then sends it to Bob; now Bob can derive the same key (since he knows the password $W$), decrypt, and learn the message.  At least, that's how things work when there is no attacker.  If Alice derives a 80-bit key $K$, and if the password is sufficiently strong, then this scheme might be secure against eavesdroppers.

The part you quote is talking about an active attack that could defeat the security of that arrangement.  Recall that Alice (the sender) encrypted with a 80-bit key $K$ (derived from a password $W$).  In the attack, an active attacker modifies the ciphertext somehow so that the recipient Bob will decrypt it with a 40-bit key $K'$ (derived from the same password $W$).  Suppose the derivation procedure has the property that $K'$ is the first 40 bits of $K$.

When Bob decrypts the ciphertext under $K'$, he will get gibberish (since he is decrypting with a different key than Alice encrypted with).  Suppose that Bob replies to Bob with a complaint that decryption failed, quoting the gibberish he got back.  Now the attacker can learn $K'$. Notice that a 40-bit key $K'$ does not provide adequate security, and in this scenario, the attacker knows both the ciphertext and its decryption under key $K'$; thus, the attacker can use trial decryption to find the key $K'$.

At this point the attacker knows the first 40 bits of the key $K$ that Alice encrypted with.  Thus, by doing exhaustive keysearch (trial decryption) on the remaining unknown 40 bits of $K$, the attacker can recover the full key $K$ and decrypt the message.  In this way the attacker learns the resulting message.

This is a related-parameter/related-key attack, where the attacker desynchronizes the endpoints and causes them to use different, conflicting parameters (e.g., different keys, different key lengths).  In general, a well-designed key exchange scheme should be designed to prevent such attacks.  Without additional context, I'd guess that the part you are quoting is explaining the need to guard against such attacks.


I don't have David Bressoud's book, and so I can't say whether you made a mistake or he did.  However, the algorithm you're using might come from the preliminary steps of Lenstra's method; however, it's missing the part that is designed to actually find the factors.  In addition, as written, it can be shown (as written) to be lousy; not much better than trying random factors.

Here's the demonstration that it is a poor method:

Your method is to pick random values for $a$, $X$ and $Y$, and compute $GCD( n, P(a, X, Y))$ (where $P$ is a polynomial in the three variables $a$, $X$ and $Y$); you succeed if the $GCD$ is neither 1 nor $n$.

Another way of looking at it is that one of the necessary conditions for you to succeed is for $P(a, X, Y) = 0 \mod p$, where $p$ is one of the prime factors of $n$.  However, if we consider $X$ and $Y$ fixed, then $P(a, X, Y)$ is a cubic polyinomial in $a$ (and is not the zero polynomial); such a polynomial has at most 3 zeros modulo a prime.  That is, if we pick $X$ and $Y$ first, we have at most 3 value of $a \bmod p$ that will give us a solution; hence the probability of us picking such an $a$ is at most $3/p$.  By symmetric, this also applies to the other prime factor $q$ of $n$ (assuming that there are only two), and hence the success probability per iteration is at most $3/p + 3/q$.  This success probability is maybe a factor of 6 larger than picking a random value $r$ between 1 and $\sqrt{n}$, and checking if that's a factor (factor of 6 assuming $p \approx q$)


CRC32 catches errors, but then what's the point of SHA?

CRCs are OK to detect naturally-occurring errors. But in cryptography, we face intelligent adversaries, which can use the mathematical properties of CRCs in order to make an arbitrary alteration in a file without altering its CRC. This is easy, even for large CRCs.

Hashes are designed to prevent that (called a second-preimage attack), and other attacks such as making two different files with the same hash (called a collision attack).

If CRCs or cryptographic hashes are different, then their input is different. In a cryptographic context, if CRCs are equal, we can't tell if their input are equal or not; whereas if cryptographic hashes are equal, then their input must be equal (or the hash used is not a secure cryptographic hash).


Is there an adaptive version of LWE assumption with respect to some potentially non-uniform secret distribution?

For Q1, $m = O(n\log q)$ is the size required for the leftover hash lemma to kick in and $Ax$ to be statistically close to uniform (I believe). See questions like this one.

For Q2, the answer is yes. The hardness of LWE is essentially independent of the dimension $m$, as you can generate new LWE samples from a fixed collection of samples with only a mild loss in the error term. See proposition 2.1 of Regev's survey (and the "other implications" discussion after the proof).


Is there a security risk associated with using a PBKDF for an AES encryption key and Sha256 for a hash using the same password text?

Yes, using a PBKDF and a SHA-256 hashing algorithm on the same password negates the usefulness of the PBKDF, by allowing to test a candidate password using a single hash; and (assuming unsalted password hash, which is not the case in the question) amortizing across multiple users/instances the computation of a rainbow table allowing to find the password quickly if its hash has been precomputed.

To make an analogy, imagine two safes, each with a 3-digit combination lock, and known to use the same 3-digit code. One safe contains valuables and uses a timed lock, preventing trying codes faster than one per hour; the other safe contains nothing and uses a non-timed lock. That second lock negates the benefit of the first one being timed, by allowing to quickly find the code for the first safe and extract the valuables.

With the unsalted SHA-256 of a mild password, a kid with a brain and web browser cracks it. Add some computing power, and the salted hash can be broken. Ask 10 random humans to pick a password they can remember a week later, and I bet at least one password succumbs to that attack.

While Rfc2898DeriveBytes is last century's password hashing / key stretching, it is still much less bad than plain hashing is. The order of magnitude of how less bad is the IterationCount parameter (and if there's no salt to the plain hash: times the number of users that an adversary is content cracking the password of).

For more efficient key stretching often available in practice, consider bcrypt or scrypt.


Is the context of "constant time" algorithms inclusive when you have a clock control?

When I read a paper that specifically says that it robust to side channel attacks because the algorithm is constant time, is the assumption that one does not have clock/voltage control?

Generally, when we mention side channel without context, we actually mean a side channel in software. I.e. an adversary has (only) the ability to run code on the same CPU. Moreover, the adversary does not have physical access to the executing CPU.

In your case—underclocking the CPU and screwing around with the power supply—you are manipulating the CPU itself. In my book this would be considered a fault attack, which is a technique in hardware side channel analysis. Hardware side channel analysis is super-powerful, and because so much is possible it has a less obvious defined attacker model.

So it kinda depends on the context. Most of the time the literature will be about software side channels (time, cache, etc.). But when you are reading a CHES paper, it's probably about hardware.


Currently, there are very few practical barriers to deploying zero-knowledge proofs. They've been deployed in everything from anonymous credentials to cryptocurrencies to privacy-preserving survey systems. Very fast academic systems have been developed which use zero-knowledge proofs for privacy-preserving distributed machine learning. This last example hasn't been deployed yet, but clearly is fast and scalable enough to be used in practice.


How to get an output of SHA-1 with first 2-bit are zeros?

Hash random values until you get a hash with two leading zeroes. We would expect  about 1 in 4 values to have a hash-value of that form.
So let's try this:
echo hello | sha1sum
f572d396fae9206628714fb2ce00f72e94f2258f  -

Nope.
echo hello1 | sha1sum
0ef562ff2d0c21358f9d289f1c908436714fc923  -

There we are, 4 leading zeroes.


Is just a bit of random, "fully random"?

Let's look at this from the bottom ("what is random?") to the top (is that secure?).

When we talk about "random" in cryptography we almost always prefer to talk about "entropy". The intuitive and concise definition of cryptographic entropy is that it is a measure of how much information the attacker does not know about the target message. When you hear about, for example, "128 bits of entropy" in cryptography, it essentially means that the message has 128 bits of information that the attacker is expected to not know about, and thus a total $2^{128}$ possible values that, from the attacker's perspective, could be the one they're looking for. For example, a 100-bit string might be generated by always prefixing a 1 and then having the remaining 99 bits filled in from a perfect random number source. This string would have 99 bits of entropy, since the first bit is known by the attacker to always be 1 and thus all strings starting with 0 are invalid. (This is all fairly simplified, by OP's request.)

So then, what's the entropy of "pseudo-random"? A pseudo-random string is just something that looks random (ie, passes all good tests for randomness) but is deterministically derived from an input. So the amount of cryptographic entropy in a pseudo-random string is actually the amount of entropy in the seed input that was used to create the pseudo-random string. This is because if the attacker can determine the seed, then they too can generate the resulting pseudo-random string. So from the attacker's perspective, the number of possible pseudo-random strings is simply the number of possible inputs that could have been supplied. (This fits with the above notion of cryptographic entropy.)

Why the distinction between "entropy" and "random"? Because we have have strings that look very random but actually have low entropy. (Such as a pseudo-random generator that always looks random regardless of the input.) In cryptography we don't usually care how random a secret looks but rather how hard it would be to re-create, and as far as vocabulary goes, "entropy" is more explicitly a measure of the source of the string, not the content. (However, for what it's worth, the terms "random" and "very high entropy" often seem to be used interchangeably amongst those familiar with the concepts.)

So what does your proposed scheme do with entropy? Your time-stamp will have some entropy, but it's unclear how much. The attacker will likely know something about the time-stamp (such as the year it was generated) but not everything (such as the exact millisecond). So the entropy won't be maximal or minimal for that source. For your secret string, it will have entropy because it has some information unknown to the attacker. If it's a string you hand-designed then it is highly unlikely it has full entropy, but it does likely have some entropy if you put any effort into designing it. (Without knowing more we can't estimate how much entropy your string has.)

The fact that you hash the concatenation of your strings does not change the amount entropy. The attacker still needs only to guess the input to the hash function. The hash will act similar to the pseudo-random generator above in that it will provide random-looking output that conceals the content of the input. But the attacker's job is simply to guess the input to that hash and so the measurement of cryptographically secure entropy is the same despite the use of the hash. The same number of original message possibilities remain, from the attacker's perspective.

To address your italicized question: A message that is "fully random" is going to have entropy the same size as the message. For example, a truly random 128-bit key will have 128 bits of entropy, but 128-bit key with 127 bits of entropy is probably not going to be considered "fully" random.

But practically speaking, we actually don't really care about having full entropy, we care about having enough entropy. A 128-bit string with 128 bits of entropy is, in theory, just as secure as a 500-bit string with 128 bits of entropy, especially if you're going to put it through some sort of function like a hash or a PRG. If security is your goal, be primarily concerned with how much entropy you collect and less so with how many bytes it took to do so.

The summary here is that a string has at least as much entropy as its highest entropy source. If you concatenate a weak string with a strong string, your result is a strong string. If you have a weak string and add a strong string and hash the two, the hash output should be a strong string.


How to encrypt a message such when a certain condition is met it can be decrypted?

You can use a standard asymmetric encryption like RSA. Certificates merely serve the purpose of linking things to other things, approved by some (hopefully trusted and trustworthy) entity.

What you're probably thinking about is an ID certificate which links an identity to a public key. This key is in no way encrypted. It simply occurs in a field of the certificate. Signing the certificate does not change its fields. It just adds a signature of everything else.

This means that anyone with access to the certificate has access to the public key, be the certificate signed or not. Signing the certificate mere means: "I approve of this."

Regarding your edit: When you want to decrypt something, you have that something and it's not enough to attain the plain text, given the encryption is secure. You need some other information. Note that I don't say what that other information is but we know for certain that additional information is needed because if it wasn't anyone who obtained the ciphertext could compute the plain text which would mean that the encryption is not secure.

We now need to determine a possible piece of additional information α. That information has to come from somewhere. It doesn't just emerge for no reason because some outside event happened.

You dictated in your edit that that α has to be found on the death certificate. To have any chance of encrypting something using any such information, we need to require at least that these conditions are met:

As the encrypter, need to know some mathematical property of α. Note that we don't necessarily need to know α itself.
α needs to be of a nature such that there are plenty of possible variations for different α with the same structure. Otherwise an attacker could brute-force α.
The attacker must not know α or be able to reduce the solution space to a small number of known elements.

If it's not possible for the encrypter to collaborate with the authority issuing the death certificate, there is no α we can find because we can only use the information found on any normal death certificate: Name of the issuer, name of the person who died and other personal information like date of birth or address, date of death, location of death, file number, and signature of the issuer.

The name of the person and their other personal information is not a secret. As the encrypter, we don't have control over the signature of the issuer nor ever the file number as we cannot collaborate with the authority. The attacker will already know what authority issues the death certificate, so the issuer is known. So we're left with date and location.

As the date is only stated with the precision of days and we can be sure to know the date of death as an attacker, except for an uncertainty of approximately 100 years which is 36524 days and therefore 36524 possibilities (if we're generous). As the location of death is only stated to the precision of the municipality where the person died, there aren't many options for this either. Even for large countries like the US, there only are 19492 options. So we have a total solution space of 36524*19492 = 711925808 < 10^9 elements.

This is far too small to exclude brute-force attacks and this assumes we have total control over where in the country the person dies and how old they become which is both impractical.

So there are no possible α we can choose one from and therefore there cannot be any such encryption.


regular expression matching on encrypted data using secure multiparty computation

there are some special constructions that could be used. for example see this paper of florain kerschbaum (freely available version).
also, you can use some secure DFA evaluation protocols, as any regex can be represented as a DFA.

what you have proposed is not secure and the servers can learn lots of information.


What is the Common Reference String (CRS) model

The CRS has nothing to do with modeling hash functions. Rather, it is a model where there is a public string that was generated in a trusted manner, and all parties have access to the string. It has two flavors: a common random string (where it is just a uniformly distributed string) and a general common reference string (which may have an arbitrary distribution).
The main difference between the ROM and CRS model is that proofs in the ROM are heuristic, since the actual protocol instantiation uses a hash function that is blatantly NOT a random oracle. In contrast, proofs in the CRS model have a standard reduction-based proof of security, and so are not heuristic.
The main advantage of the CRS model over the random oracle model is that security is standard, and doesn't rely on a heuristic belief system that the real protocol that uses a standard hash function is secure. The main disadvantage is that you need to somehow generate this CRS, and this isn't trivial if there's no trust. Zcash uses a CRS and ran a large MPC protocol between many parties to generate the CRS. As long as you believe that not all the participants colluded, then you can trust the system from that point on. This is a good example of where a CRS can be deployed in reality.


What was NIST’s reason to switch naming from MD… (Message Digest) to SHA… (Secure Hashing Algorithm)?

When NIST introduced SHA-0 in 1993, they – for the first time – switched their naming convention from MD-n to SHA-n

Actually, MD-n was not NIST's naming conventions; it was RSA Security's (a private company) naming convention.  Before SHA (which was the original name; SHA-0 is retroactive terminology given to distinguish the original proposal from what was finally adopted: SHA-1), NIST didn't define any hash functions.


Can two different pairs of RSA key have the same modulus?

The users will be able to read each other's messages (even though they can have different private keys, say $d_1$ and $d_2$). This is because knowledge of $d_i$ is sufficient to factor $N$, thus allowing that party to compute the other party's private key. This was detailed by Boneh in his analysis of RSA attacks.


Why does second pre-image resistance imply pre-image resistance

Let me try to elaborate on their proof. Suppose you had a hash function $H$ that was second-preimage resistant but not first-preimage resistant. By showing that this leads to a contradiction, we will be showing that with second-preimage resistance, you must have first-preimage resistance. Namely, we will show that the lack of first-preimage resistance is enough to break second-preimage resistance.

When breaking second-preimage resistance, we are given a random $x$ and the goal is to find another $x' \ne x$ such that $H(x') = H(x)$. Suppose we are given a random $x$. Then we can compute $H(x)$ and then use our preimage-finding algorithm (since this hash function isn't first-preimage resistant, remember?) to find an input $x'$ such that $H(x') = H(x)$.

The question becomes whether or not $x' = x$. For a hash function with an infinite domain, there are infinitely many inputs that $H$ maps to the same output. That is, there exist infinitely many second-preimages for any particular $x$; the question is whether or not we can find one.

Intuitively, the preimage-finding algorithm "should" give back an $x' \ne x$. After all, there are infinitely many inputs that map to the same output as $x$, so the probability that we find the exact $x$ we were given "should be" low, right?

So we should have an $x' \ne x$ such that $H(x') = H(x)$. But this is a second preimage! Thus, assuming that $x'$ indeed does not equal $x$, we cannot have a hash function that has second-preimage resistance but not first-preimage resistance. Thus, second-preimage resistance must imply first-preimage resistance. This is not a formal proof: just an intuitive argument.

The crucial assumption in this "proof" is that the domain is infinite. If it were not infinite, then all bets are off. In that case, the output size of the hash function needs to be sufficiently small relative to the input size for this argument to hold. I've written about that idea in great detail on my answer on the question "Pre-image resistant but not 2nd pre-image resistant?", so I refer you to that for more technical details.


Include sender and receiver in the plaintext message (you need some kind of message format for that) and also sign the message (including sender / receiver) before encryption. That way an attacker cannot alter or swap the plaintext message. You may also need to assign the message a number of include some kind of timestamp to avoid replay attacks.

You could encrypt the message first using a message key and encrypt that key using the various public keys of the receivers. Note that the encryption scheme should not fall to plaintext / padding oracle attacks, as the signature should be over the plaintext, not the ciphertext.


In these systems, is adversary able to generate semi-functional ciphertexts?

Quoting the paper figlesquidge mentioned in a comment:

  Crypto 2009
  Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions
  Brent Waters

  Abstract: We present a new methodology for proving security of encryption systems using what we call Dual System Encryption. Our techniques result in fully secure Identity-Based Encryption (IBE) and Hierarchical Identity-Based Encryption (HIBE) systems under the simple and established decisional Bilinear Diffie-Hellman and decisional Linear assumptions. Our IBE system has ciphertexts, private keys, and public parameters each consisting of a constant number of group elements. These results are the first HIBE system and the first IBE system with short parameters under simple assumptions.

  In a Dual System Encryption system both ciphertexts and private keys can take on one of two indistinguishable forms. A private key or ciphertext will be normal if they are generated respectively from the system's key generation or encryption algorithm. These keys and ciphertexts will behave as one expects in an IBE system. In addition, we define semi-functional keys and ciphertexts. A semi-functional private key will be able to decrypt all normally generated ciphertexts; however, decryption will fail if one attempts to decrypt a semi-functional ciphertext with a semi-functional private key. Analogously, semi-functional ciphertexts will be decryptable only by normal private keys.

  Dual System Encryption opens up a new way to prove security of IBE and related encryption systems. We define a sequence of games where we change first the challenge ciphertext and then the private keys one by one to be semi-functional. We finally end up in a game where the challenge ciphertext and all private keys are semi-functional at which point proving security is straightforward.

(bold emphasis mine)

I would have loved to add more, but your question can simply be answered with a humble “yes”.


How exactly does key whitening manage to increase security?

While it may be confusing, that Wikipedia article is actually correct! Let me try to explain it a bit better…

Definition of key whitening

Key whitening is an extremely simple technique to make block ciphers like DES much more resistant against brute-force attacks. Like you’ve already discovered yourself, this is the basic scheme:

Or, defining it a bit more mathematically…

Encryption: $y = e_k,k_1 ,k_2 (x) = e_k (x \oplus k_1 ) \oplus k_2$
Decryption: $x = e_k^{-1},k_1 ,k_2 (x) = e_k^{-1} (y \oplus k_2 ) \oplus k_1$

In addition to the regular cipher key $k$, two whitening keys $k_1$ and $k_2$ are used to $\oplus$ (XOR-mask) the plaintext and ciphertext.

Security added by key whitening

Now, it is important to stress that key whitening does not strengthen block ciphers against most analytical attacks such as linear and differential cryptanalysis.

So, your observation/interpretation is somewhat correct.

Key whitening indeed isn’t a “cure” for inherently weak ciphers or something like that. Its use only makes sense when ciphers are relatively strong against analytical attacks, but possess a too short key space.

Trying to use your wording: key whitening can only increase security by strengthening a cipher where its key space is too short. That’s it. When it comes to increasing security, you won’t gain anything else from a key whitening step.

Ciphers using key whitening

A prime example of such a cipher would be DES. A variant of DES which uses key whitening is DES-X. In the case of DES-X, the $k_2$ is derived from $k$ and $k_1$.

If you take a look around, you will notice that most modern block ciphers already apply key whitening internally by adding a sub-key prior to the first round and after the last round… prime example: AES.

An aside: In case you want to dig in deeper, it might be interesting for you to check out books like “Understanding Cryptography”  by Bart Preneel, Christof Paar, and Jan Pelzl; or “The Block Cipher Companion” by Lars R. Knudsen, and Matthew Robshaw.


How could consumer level OTP + QKD over the internet ever be practical?

There are many questions here; I am not answering the question in the title, but rather addressing the final questions in the body.

  One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists and the limitations of mathematics to make strong encryption, there will no longer be any crypto algorithm that survives the evolution of cryptology, unless it meets the standards of information-theoretical perfect security. Just as classical pencil-and-paper ciphers were rendered useless with the advent of the computer, so will current computer based crypto algorithms become victim to the evolution of technology, and that moment might creep on us much faster than we expect. Only one-time pad encryption, the only information theoretically secure encryption, will survive that evolution.

The linked article describes OTPs at great length. It goes on to quickly make casual claims about how doomed all other cryptographic algorithms are, without providing any kind of citation or real argument for why this will be the case. There is no reference to even a weak argument such as "but maybe P=NP". They make vague references to increasing computational power and improved cryptanalytic techniques, so I guess that is what we will have to cover.

Computational Power

This demonstrates a lack of understanding of how the cost of cracking a key actually scales. Claiming that advances in computational power alone will ever threaten the security of, for example, AES-256, is evidence in support of this. No amount of computing power will ever brute force an AES-256 key. It is not a possibility even from a theoretical point of view, let alone a practical one.

Additional misunderstandings are present in the paragraph immediately preceding that one:

  Another disadvantage is that one-time encryption doesn't provide message authentication and integrity.

Ok good, this is true and at least the author recognizes this much.

  Of course, you know that the sender is authentic, because he has the appropriate key and only he can produce a decipherable ciphertext ...

This is silly. Anyone can simply craft any set of bits they want and submit it as a "ciphertext", and the receiving party has no way of verifying that the message actually came from anyone in particular (indeed, they could not accurately tell the difference between a ciphertext intended for them and a pile of random bits)

Continuing further into that same paragraph, we see the author advocate MAC-then-encrypt (edit: Actually, it's arguably not even MAC-then-encrypt as the hash is not even keyed), which runs contrary to standard best practices

  A solution is to use a hash algorithm on the plaintext and send the hash output value, encrypted along with the message, to the recipient (a hash value is a unique fixed-length value, derived from a message). Only the person who has the proper one-time pad is able to correctly encrypt the message and corresponding hash. An adversary cannot predict the effect of his manipulations on the plaintext, nor on the hash value. Upon reception, the message is deciphered and its content checked by comparing the received hash value with a hash that is created from the received message. Unfortunately, a computer is required to calculate the hash value, making this method of authentication impossible for a purely manual encryption.

Interestingly enough, regular old hash functions appear to be good enough for our information-theoretic security lover, despite the fact that information-theoretically secure MACs exist.

But what about cryptanalysis?

Cryptanalytic attacks may exist that can recover a key in less time then brute force. This does not imply that:

The space requirements of such attacks is practical
The time requirements of such attacks is practical (> 2 ** 100 == impractical)
The conditions required for the attack to function may not be realistic

For example/before anyone comments with "But related key attacks on AES-256!", consider the context and costs of that attack:

  There is a key owner; the key is KA
  and the attackers tries to guess it.
  The key owner can somehow be persuaded to compute three other keys KB
  , KC and KD, from KA, using a specific derivation algorithm (KB is equal to KA XORed with a constant that the attacker chooses; KC and KD
  use a more complex but equally deterministic derivation algorithm).
  Then, the attacker can make the key owner encrypt and decrypt arbitrary blocks -- that the attacker chooses -- with the keys KA
  , KB, KC and KD.
  The key owner will accept to process up to $2^{99.5}$ blocks (that's 16-byte blocks, hence a grand total of about 14 thousands of billions of billions of gigabytes).
  Finally, the attacker has access to some storage space of about one million of billions of gigabytes.

Did you see the part where the adversary can encrypt and decrypt 14 thousands of billions of billions of gigabytes under four different keys of their choosing? What exactly is your cipher protecting, in this scenario? Why does the adversary even need your key if they have access to a decryption oracle? Is this really a reasonable and practical scenario to be in? Would you really base your decision on which algorithm to use based off of an attack with these kind of requirements?

The point is that just using "the bottom line" where the author(s) consolidate all of their attack into a single measurement of time as the only gauge for security is too narrow of a perspective. Is an algorithm that is broken in time 2 ** 115 really less secure then an algorithm that requires time 2 ** 128 to break? Obviously in theory the correct answer to the question is "yes", but in practice both such attacks would take too long to execute and hence both would offer equivalent security as neither attack would ever be performed (we will ignore the argument that the hypothetical attacks could be improved).

  Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?

There are reasons to believe that the conclusion of the article is questionable. The author of the article basically claims that widespread QKD+OTP is needed, but does not appear to offer any constructive advice as to how to build such a future, nor any supporting evidence for why all of the rest of cryptography is apparently doomed.

Amidst all of the praise of the OTP, they completely neglect to mention how the algorithms that are used in practice (i.e. AES/ChaCha) succeed at providing security to the entire world on a regular basis, while the OTP in all of it's theoretically perfect glory has been broken in practice on multiple occasions.

The OTP and quantum cryptography are basically the opposite of practical cryptography. The more complicated the communication system is, the more vulnerable it will be to attack.

Adversaries will not target the strongest parts of the equation; Supposing you really did utilize QKD and OTP to secure your messages, they will simply wait for you to receive the messages then extract the information from you personally.

Either that or they will target/exploit some aspect of the implementation, because there is a difference between a theoretically secure algorithm and a secure implementation of that algorithm.


How to compute the inner product on encrypted vector by using a third party?

One possible way to calculate the inner product is by using fully homomorphic encryption schemes.
First, you encrypt each vector $$x = (x_1,x_2,\ldots,x_n), \quad y = (y_1,y_2,\ldots,y_n)$$
with your public key $$X = Enc_{pub}(x) \text{ and } Y = Enc_{pub}(y)$$ where $$X = (X_1,X_2,\ldots,X_n), \quad Y = (Y_1,Y_2,\ldots,Y_n)$$ and $$X_i = Enc_{pub}(x_i) \text{ and } Y_i = Enc_{pub}(y_i)$$
Now, you can send $X$ and $y$ to the server to calculate the inner product, IP, under FHE.
$$IP = \langle X,Y \rangle = X_1 \odot  Y_1 \oplus X_1 \odot Y_1 \oplus \cdots \oplus X_n \odot Y_n$$ when the server send you back the result, use your public key to decrypt the result. Where $\odot$ represent homomorphic multiplication and $\oplus$ represent homomoprhic addition.
$$res = \langle x,y \rangle = Dec_{priv}(IP)$$
Note 1 : You have to assume the server semi-honest. Here, there is no integrity against a malicious server.
Note 2 : For the implementation, you can use TFHE: Fast Fully Homomorphic Encryption over the Torus or Helib
Note 3 :  You can also use 2DNF by Boneh et.al, which support one multiplication but many additions. This work is enough for the calculation of the inner product under 2DNF encryption. The decryption, however, is not straightforward. As noted on page 4 of the paper;

To recover $m$, it suffices to compute the discrete log of $C^{q_1}$ of base $\hat{q}$
Note that decryption in this system takes polynomial time in the size of the message space T.
Therefore, the system as described above can only be used to encrypt short messages

Note 4: there is an article titled as Design and Implementation of Low Depth Pairing-based
Homomorphic Encryption Scheme by Herbert at. al that that

can handle the homomorphic evaluation of polynomials of degree at most 4.
and uses Elliptic Curves. And, they have an implementation posted on github.


Yes, you are correct.

The simplest way without stepping outside NaCl would be to have both create an ephemeral, random crypto_box_keypair, then exchange public keys using their long term keys. Further communication would use that new keypair for crypto_box during that session. After they are done with the session, delete those ephemeral keys from memory.

The private keys would only exist for the session, so an attacker who later compromised one of their computers would be unable to decrypt any of the messages encrypted with those keys and could only find out their public keys from stored communications.


using random encrypted RSA challenge as key material

If you want to be really sure, you could generate both the reply and the encryption keys from the challenge using a suitable key derivation function, such as HKDF (RFC 5869), e.g. as in:

salt = sender-ID | recipient-ID
PRK = HKDF-Extract(salt, challenge)

reply = HKDF-Expand(PRK, "reply", reply_len)
encrypt_key = HKDF-Expand(PRK, "encrypt", keylen)

Provided that HKDF is instantiated appropriately and that the underlying hash function is secure, it should not be possible for an attacker observing the reply to learn anything useful about the challenge or the encryption key, at least provided that the same challenge is never sent twice between the same parties.  (If you want to eliminate even that minor loophole, include something unique, such as a timestamp, in the salt.)

Edit: Your originally proposed scheme could also be safe, but there are some potential pitfalls.  For example, if you're using the same hash function to generate the reply as for HMAC, and if your challenge is longer than one hash input block, and you're not using any kind of salting to differentiate the two uses, then you could have a problem.

That's because, if the keystring is too long, HMAC will first hash it down to less than one input block using the underlying hash function, and then use the hash output as the actual key.  Thus, anyone knowing the hash of the key would be able to compute the HMAC output just as easily as if they had the key itself.

That's one reason why I'd recommend using a KDF to generate both the reply and the encryption / HMAC keys, with different role strings as I suggest above.  That's exactly what a KDF is designed for.


How much bigger does a precomputed lookup table get when salt is added?

Looks right to me, assuming you know what the 10 salts are.

If you don't know a priori what the salts are (which is typically the case when building a rainbow table), you'd have to compute for the entire salt space. This is where the big gain comes into play as for each additional salt bit, the storage requirement doubles. Thus you get exponential growth of the storage requirement.


Is there any security issue if an attacker recovers the key stream generated by a stream cipher?

First, there's no issue with modern stream cipher constructions - either using an AEAD block cipher mode of operation such as GCM, or the combination of ChaCha20-Poly1305 as Google had experimented and subsequently formalized in the form of Internet RFC documents.

Stream ciphers are basically reduced-capability one-time-pads as one may infer: stream cipher cipher streams only has as many possible values as there are keys, where as one-time-pads are truely random. This is fine since physically buildable computers (including those hypothetical quantum computers) are bounded in capabilities - in both time and space dimensions.

Second, the new trend in the field is to build AEADs from permutations using Duplex construction (I admit these aren't the popular knowledges you might learn from school or might encounter in your TV programs or newspapers).

Indeed, ChaCha20 and Poly1305 are separate primitives that were introduced as "backup"s to AES, etc. Even the original paper proposing Poly1305 introduced it as AES-Poly1305.

Roughly describing the concept:

Recall the SHA3 hash functions are based on 1600-bit Keccak permutation running in Sponge mode - the permutation is partitioned into 2 parts, 1 part is used to absorb data and squeeze out the hash digest, the other part is kept secret as the security capacity.

Duplex is similar, except the data is read as they goes in. Adding in some careful design, you get a AEAD from a single primitive - the permutation.

Examples of these types of cipher include Gimli, Xoodyak, etc. You'd find some more at NIST lightweight cryptography project page.


Is authenticated encryption basically a lockable box?

No.

Yes, by choosing an authenticated encryption scheme with a known $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ and $k_{\hspace{.02 in}0}$ and $k_1$ such that decrypting $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ with $k_{\hspace{.02 in}0}$ and $k_1$ yields different outputs, neither of which are $\perp$.

These three links describe a black-box construction of authenticated encryption from one-way functions. $\:$ On the other hand, there is no known construction of non-interactive commitments from one-way functions, and this paper declares, "We rule out the possibility of black-box constructions of non-interactive commitments from general (possibly not one-to-one) one-way functions." However, Naor's scheme comes close.

The only candidate constructions of non-interactive commitments that I'm aware of either use a

$\:$ (1) key agreement scheme with sufficient completeness (this is the standard way to do it), or
$\;\;\;\;$
$\:$ (2) family of injections given by tuples of multi-variate polynomials over finite fields, or a
$\;\;\;\;$
$\:$ (3) keyless CRHF (these cannot be secure against non-uniform committers), or a
$\;\;\;\;$
$\:$ (4) hitting one-way function (in addition to presumably being only computationally hiding,

$\:$ these are also not known to be binding against (uniform) efficient committers)

.


Montgomery Exponentiation - selecting input value R for a given BigInteger

Montgomery multiplication makes sense only with word sizes. If your word size is $w$ (e.g. $w = 32$ if you have 32-bit words), then $R = 2^{kw}$ for some integer $k$; you choose $k$ as small as possible, given that you must have $R \geq N$.

In plain words, if your modulus $N$ has size $n$ bits, then you look for the next multiple of $w$. For a 1024-bit modulus, which is already a multiple of 32, you use $R = 2^{1024}$. For a 1025-bit modulus, you would use $R = 2^{1056}$.

You really want to read chapter 14 of the Handbook of Applied Cryptography.


Estimating the probability of sucess of Pollard's p-1

estimate the probability that Pollard's p-1 factorization in its two-stages variant finds a factor of an RSA modulus product of $k$ random $b$-bit primes, as a function of the bounds $B_1$ and $B_2$ used

TLDR: GMP-ECM is fine. Modify it for $b$ bits rather than n decimal digits, and use $k\;P$ where $P$ is the low probability shown.

The way GMP-ECM ecm -v -pm1 coumputes $P$ is described by Alexander Kruppa in section 5.3.3 of his Doctor's thesis, as
$$P=\hat\rho\biggl(\frac{\log(N_\text{eff})}{\log(B_1)},N_\text{eff}\biggr)+\sum_{B_1<q\le B_2\\\quad q\in\Bbb P}\hat\rho\biggl(\frac{\log(N_\text{eff}/q)}{\log(B_1)},N_\text{eff}/q\biggr)/q$$
where
$$\begin{align}\hat\rho(u,x)&=\rho(u)-\gamma\frac{\rho(u-1)}{\log(x)}\\
\gamma&=\lim_{n\to\infty}\biggl(-\log(n)+\sum_{i=1}^n\frac 1 n\biggr)
\approx0.5772156649\\
N_\text{eff}&=N\;e^{-\delta}\\
\delta&=\sum_{q\in\Bbb P}\frac{\log(q)}{(q-1)^2}\approx1.2269688057\\
N&=2^{b-0.5}\text{ is an approximation of the factor}
\end{align}$$

In this, $\displaystyle\hat\rho\biggl(\frac{\log(N)}{\log(B_1)},N\biggr)$ estimates the probability that a random integer near $N$ has all its primes factors at most $B_1$; $\displaystyle\sum_{B_1<q\le B_2\\\quad q\in\Bbb P}\hat\rho\biggl(\frac{\log(N/q)}{\log(B_1)},N/q\biggr)/q$ estimates the probability that a random integer near $N$ has all its primes factors except the largest at most $B_1$ and has that largest factor in $(B_1,B_2]$; and $\delta$ is a correction to account for the fact that a random prime $p$ near $N$ has $p-1$ divisible by small prime $q$ with probability $1/(q-1)$, rather than $1/q$ for a random integer near $N$.

Note: that answer is still missing how to compute the sum for large $B_2$. GMP-ECM uses some indirect method when $q>20000$, which is always for parameters of practical interest in factoring an RSA modulus. For this reason, I make the question a Community Wiki.

As an illustration: ecm -pm1 35e9 uses $B_1=35000000000$, $B_2=81866328103009612$, and a 256-bits random prime is found with $P\approx0.0000119$. A factor is found in a 3-factors RSA 768-bit modulus product of random 256-bit prime factors for about one in 28000 moduli. Testing a moduli costs about 3.5 hour using one core and 48GiB RAM. Most of the RAM is used <25% of that time, so that one 4-core CPU 64GiB machine can test at a rate over one modulus per hour. If an adversary is content with factoring any one in like a thirty thousand such RSA moduli, Polard's p-1 is a plausible strategy to pull a factor (with expected cost 1170 CPU×days), followed by GNFS to factor a 512-bit composite. This beats GNFS alone, and I believe ECM. This is a setup where it makes sense to generate primes in a way that defeats Polard's p-1 and probably Williams's p+1 too.

Thanks to Paul Zimmermann and Alexander Kruppa for their guidance.

  What's the cause of that discrepancy?

Main problem: the question's term $\displaystyle\frac{\log_2(B_2)}{\log_2(B_1)}$ is grossly too high. It was supposed to be a lower bound of the probability that the second-highest factor of a large random integer is less than $B_1$, knowing that the highest factor is less than $B_2$. That was baseless and wrong.


Asymmetric Encryption vs Shared secret via ECDH

Your alternate method has an expensive public key operation for each push message.
While the first protocol does a key exchange just once per subscription and then continues with a symmetric key.
If in the key exchange both sides authenticated themselves (Or at least the Application) the user can rely on this, if authenticated encryption is used it still a fast symmetric key operation to decrypt and authenticate the message.


Is it possible to sample HE ciphertexts using pseudo-random generator?

Since BFV scheme is IND-CPA secure, its valid fresh ciphertexts should be indistinguishable from malformed ones (i.e., drawn from uniform distribution).

IND-CPA says that someone who doesn't know the secret key cannot distinguish those two distributions.

  However, the experiment result shows that a uniformly-distributed ciphertext does not form a valid ciphertext of BFV scheme

You can only check whether a ciphertext is "valid" if you have the secret key. So there is no contradiction.

An analogy is a length-doubling PRG $G: \{0,1\}^n \to \{0,1\}^{2n}$. The output of the PRG is indistinguishable from the uniform distribution over $\{0,1\}^{2n}$. That doesn't mean that most strings in $\{0,1\}^{2n}$ are "valid outputs" of the PRG. In fact, only a negligible fraction ($2^n$ out of $2^{2n}$) of them are.


What algorithm would give the shortest ciphertext for very short plaintexts?

There is a technique called "format preserving encryption", which could be called an "arbitrary-size block cipher". This would allow to map your set of 5-character strings onto itself. Of course, this can't really get too secure, as it has still the limitations of ECB mode: encrypting the same string with the same key always gives the same ciphertext.

Your idea of using a mode with initialization vector helps, but bloats the message size, of course.

Since your effective message is sufficiently smaller than the block size, you could use a kind of "random padding" (similar to how it is used for asymmetric ciphers like RSA). For example, if your actual message is 5 bytes (and always this size, so we don't need to encode the size), you could add 8 random bytes and three zero bytes (as an integrity check), and pass the whole 16-byte-string to AES (as a block cipher, i.e. one-block-ECB).

On the decrypting side, you check that the last three decrypted bytes are zero, and then ignore the random bytes.

Now the ciphertext is different each time a different random value is used, independently of the actual plaintext, making it secure if the cipher is secure. (Of course, you should not use the same key for more than about $2^{32}$ messages.)

The protection against existential forgery is not that high, though, as three check bytes mean only 24 bit protection (in average 4 million tries necessary before a message is accepted). You can make this higher by using a smaller random part and bigger check part (meaning you should use the same key even less often).

If your protocol is serial, you can include a message number instead of a random value and check value, which also helps against replay attacks.


What is the purpose of having a one-way function also be a permutation on it's on domain?

A one-way permutation (OWP) is more structured than a one-way function, and hence a stronger object. This makes the task of constructing higher cryptographic objects from OWPs easier and also, at times, leads to more efficient constructions. For example, consider pseudo-random generators (PRGs): it is quite straightforward to construct a PRG from a OWP; but constructing a PRG from a OWF took a lot more effort -- you can read more here.


What would be the most efficient way to find two large (2048bit) integers $k$ and $q$ such that $p = kq + 1$ is prime and so is $q$?

What you ask is basically DSA parameter generation (albeit with a larger $q$). This is described in FIPS 186-4, section A.1.

Conceptually, prime generation is merely: make a random integer, see if it is prime, loop if it is not. In this case, you will want to do things the following way:

Generate a random integer $q$ of the intended size (2048 bits). You'll want to make sure that the top bit it set (because you want a 2048-bit integer, not a 2047-bit or less integer). You also set the bottom bit so that $q$ is odd (if it is even then it is not prime).
Test if $q$ is prime. If not, go back to step 1. The normal primality test is Miller-Rabin. If you use an existing big-integer library, then chances are that it already offers that test.
Compute the proper range for $k$. Basically, if you want the final $p$ to be exactly 4096 bits in length, then set $k_l = \lceil (2^{4095} - 1) / q \rceil$ (division of $2^{4095}-1$ by $q$, rounded up) and $k_h = \lfloor (2^{4096}-1) / q \rfloor$ (division of $2^{4096}-1$ by $q$, rounded low). You need $k$ to be such that $k_l \leq k \lt k_h$.
Set $s = k_h - k_l$.
Generate a random $r$ integer between $0$ (inclusive) and $s$ exclusive. A good way is to generate a random sequence of bits of the size of $s$ (i.e. if $s$ has length 2049 bits, generate 2049 bits); of the generate value does not fit in the range, then try again. This should ensure uniform selection in the range.
Compute $k = r + k_l$, then $p = kq + 1$. Thanks to how $r$ was generated, it is quaranteed that $p$ has the proper size.
Test whether $p$ is prime. If not, loop to step 5.

The only semi-smart thing here is that once $q$ is generated, you don't have to do it again. So it is just two successive but not nested loops, one for $q$, then another one for $k$.

In practice, finding a random prime has complexity between $O(n^3)$ and $O(n^4)$ (where $n$ is the length of the prime, in bits)(exact value depends on how well the primality test is written, in particular when it comes to avoiding the Miller-Rabin test for composites with small prime factors) so the loop on $p$ will be eight to sixteen times more expensive, on average, than the loop on $q$.


Diffie-Hellman key agreement with both Server Authentication and Perfect Forward Secrecy

$Adversary\:$ receives $C^1_{publ}$

$Adversary\:$ adaptively queries an oracle that implements:

take $C^2$ as input, generate $S^1_{publ}$, set $\: k_{adv} = KDF\left(\left(C_2\right)^{S^0_{priv}},label_0\right) \:$, $\:$ output $\: AE_{k_{adv}}\left(S^1_{publ}\right)$

Note that $\:Adversary\:$ can (with, heuristically, overwhelming accuracy) test whether or not a given

value was used as $k_{adv}$ on a given query to that oracle (since the encryption is authenticated).

$Adversary\:$ guesses $k_{tmp}$ and then runs the rest of the protocol with $\:Client\:$.

If the guess was correct, then $\:Client\:$ will accept with $k_S$ and $k_C$ known to $\:Adversary\:$.

(There is slightly more that the adversary can do, which I'll

explain if you don't think the above justifies my next sentence)

It seems that it would be very difficult to prove security against the above sort of attack

without proving that even if the oracle instead outputs [if $\: C^2 = C^1_{publ} \:$ then $\perp$ else $k_{adv}$],

it would still be infeasible to distinguish $k_{tmp}$ from a randomly chosen key.

That is the analogue of CCA2 security for Diffie-Hellman+your-KDF.

You could reduce the main security assumption to KDF-Diffie-Hellman by having

$Server$'s$\:$ long
term key pair be for signatures, replacing the step 6 message with

$S^1_{publ}\;||\;\text{sign}_{S^0_{priv}}\left(C^1_{publ}\:||\:S^1_{publ}\right)\;$, $\;\;$ and then removing step 4 and the "decrypt" part of step 7.

Both of these methods use two messages, and I will assume they are done using Elliptic Curves

and that the $AE$ in step 6 of yours does not include an IV (since the plaintext has high min-entropy,

and that particular plaintext doesn't actually need to be confidential). $\;\;$ In both of these protocols,

the length of the first message is $\:2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k\:$,$\:$ where $k$ is the (confidentiality) security parameter.

In your protocol, the length of the second message if $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)+\sigma\:$,$\:$ where $\:Adversary$

has a trivial attack that will violate explicit authentication with probability $1/(2^{\sigma})$

and cause $\:Client\:$ to reject otherwise. $\;\;$ In my protocol, the length of the second

message is $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)+(4\hspace{-0.035 in}\cdot\hspace{-0.03 in}k_{\hspace{.01 in}0})\:$,$\;$ where $\hspace{.02 in}k_{\hspace{.01 in}0}\hspace{.01 in}$ is the authentication security parameter.


I'm curious on methods of encrypting files using C++

3DES is an old and slow cipher.
In 2019, it is probably a bad idea to build new applications based on this algorithm.

Choosing a cipher, is not the only thing that matter in cryptography.
You need a mode of operation like CBC or GCM to specify how to combine encryption function on long messages.
If you don't use AEAD modes, you probably need a MAC construction to protect ciphertexts from malleability.

Choosing all theses things in a secure way is difficult.
That's why, your best option is to use a library that provide a secure API for encryption.
Libsodium is a mature example of such library and the crypto_secretbox_* functions are probably what you need.
They are based on XSalsa20+Poly1305 construction.


My code above is a fascinating huge damping pile of... you know.

generator.init(password, salt, iterations);
Arrays.fill(password, (byte) 0);

BC fails to copy the content of the password array, so my security "improvement" of clearing the password after use, clears it before use and leads to a password of all zeros.

Btw., the mailing list was no better than this site. No answer.


Why does Rijndael with a 256-bit block require the bottom two rows to be shifted one more space than usual?

That variation directly implements Rinjdael's ShiftRow as specified (section 4.2.2) in the proposal to NIST, defining Shitftrows for 128, 192 and 256-bit block size (Nb=4, 6 and 8).

Loosely speaking, the offsets improve the mixing (diffusion) properties of consecutive rounds of the cipher. More precisely the authors state their motivation (section 7.4) as:

  The ShiftRow offsets

  The choice from all possible combinations has been made based on the following criteria:

  The four offsets are different and C0 = 0;
  Resistance against attacks using truncated differentials [Kn95];
  Resistance against the Square attack [DaKnRi97];
  Simplicity

  For certain combinations, attacks using truncated differentials can
  tackle more rounds (typically only one) than for other combinations.
  For certain combinations the Square attack can tackle more rounds than
  others. From the combinations that are best with respect to criteria 2
  and 3, the simplest ones have been chosen.


If $P \neq NP$ why doesn't this prove the existence of OWF?

an answer from  Goldwasser and Bellare's lecture notes.
P ≠ NP is not a sufficient one. P ≠ NP only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct “encryption schemes” for which the breaking problem is NP-complete and yet there exist an efficient breaking algorithm that succeeds on 99% of the cases. Hence, worst-case hardness is a poor measure of security. Security requires hardness on most cases or at least average-case hardness. Hence, a necessary condition for the existence of secure encryption schemes is the existence of languages in NP which are hard on the average. Furthermore, P≠ NP is not known to imply the existence of languages in NP which are hard on the average.


Calculate the RSA private exponent from the CRT parameters

Calculate $\phi(n) = (p-1) (q-1) = n - p - q + 1$. Then $d = e^{-1} \mod \phi(n)$.

With OpenSSL, the code should look something like this (error checking omitted):

BN_CTX *ctx = BN_ctx_new();
BIGNUM *d = BN_dup(n);
BN_sub(d, d, p);
BN_sub(d, d, q);
BN_add_word(d, 1);
BN_mod_inverse(d, e, d);
BN_ctx_free(ctx);
return d;

If the public exponent is not known, it's usually possible to guess it, since it's usually chosen from a very small pool. But failing that it's possible to find working values of both the public and private exponents from $d_p$, $d_q$, $p$ and $q$. See user94293's answer.

The inverse calculation is less straightforward. There's a good description in Twenty Years of
Attacks on the RSA Cryptosystem by Dan Boneh (Fact 1) or in How to calculate RSA CRT parameters from public key and private exponent


How can you determine how long the MAC for GCM must be?

In Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC Appendix C, Table 1 & 2 NIST gives the recommended maximum number of invocations of the decrypt function of GCM for different message lengths using a MAC of 4 and 8 Byte.

My message length of 7 Byte cipher text + 0 Byte additional authenticated data (AAD)  enables me to decrypt $2^{22}$ and $2^{32}$ messages respectively, before having to change the symmetric key.

Since in my application I want to send $2^{32}$ messages before I'll have to change the key, I'll have to use 8 Bytes.