Understanding hybrid cryptography's concepts: signing and CA

You're confusing a lot of things:

  Alice and Bob agrees on a shared private key that is to be used to encrypt

You cannot have a "shared private" key; sharing and keeping things private are opposite terms. That would be called a secret key, as it is kept secret between Alice and Bob (some books confuse these terms as well, but yeah).

  To reach private key agreement, Alice and Bob will use DH

OK, the first statement should come after this second one. And yeah, secret key agreement or establishment.

  To ensure that Bob can verify the message $p$ comes from Alice, Alice will sign the message $p$.

With what key? You've used key agreement using DH and you've specified that you'd use a secret key for encryption.

  Because signing requires a lot more resources and can only typically only sign a message with a limited amount of length, Alice will first hash (say using SHA-1) then message $p$ to a message digest called $\mathit{md1}$.

Hashing is typically part of the signature generation and verification operation.

  encrypting them using an encryption algorithm (say AES)

AES is a block cipher, it is not a generic cipher that handles messages of any size, and it isn't CPA secure by itself. This matters because if e.g. you'd use AES CBC, it may fail to padding oracle attacks before you decide to check the signature. This was one of the mistakes of e.g. the early TLS protocols (well, up to 1.2, so this is not the distant past or anything).

  With RSA, Bob can convert the signed message digest $s$ back to message digest $\mathit{md2}$.

There is no rule that retrieval and comparing hashes is part of the verification procedure for signature schemes. Recalculation of the hash is of course necessary, but the verification procedure may have a different way of making sure that the hashes are identical.

  Bob magically knows that the algorithms used are SHA-1, RSA and AES. How do Alice and Bob agree on the algorithms used in the whole process?

They agree on it beforehand. The algorithms may be static, depend on a single version number, or be established during a handshake (a la TLS).

  2a. When I'm hashing and signing, I'm providing integrity and authentication at the same time. Are these two processes inseparable if I want to provide both aspects?

The processes are not inseparable but they are commonly linked to each other. Unless you explicitly think of a way to untangle them you're probably OK for both.

  2b. I'm assuming that you always sign the message digest because of efficiency problems (as mentioned above), is this correct?

That depends, as you'd normally use an authenticated cipher or MAC to provide message integrity / authenticity. Those may not use a hash at all.

  The very first step of DH is to exchange a public key generated by Alice and Bob. To do that, they will need to agree on an initial large prime number $\mathit{pn}$ and its prime generator $g$. Then, I will send the public key generated by both sides. However, as I will be exchanging messages, how do I know that the agreed $\mathit{pn}$ and $g$ are not tampered by others and that the public key sent from both sides are indeed from themselves and not an attacker? Do I need to sign these message exchanges?

That's not strictly necessary as using different values will lead to an invalid secret. It does make sense to:

Validate that DH was successful before validating messages. Although not strictly required, it will better allow you distinguish between broken key establishment and broken messages.
Include the parameters or parameter names in the above validation.
For particular protocols (ECDH with a P-xxx or Brainpool prime curve) to check the validity of the public key.

But note that if you'd use pre-established parameters that the attacker may not have an attack vector in the first place. It depends on your protocol.

  4a. As you can see in my example, I have failed to involve a CA in my imaginary hybrid cryptosystem.

You've also failed to define a key pair for signing / verification, so that should come at no surprise.

  4b. In my understanding, a CA will verify that messages are indeed from a company/person. To verify the messages are from one side, CA will see the digital certificate that is sent alongside the message.

Incorrect. A CA is used to establish trust in the certificates used, which contain the public key used for signature verification (or, in other protocols, encryption). A CA is not involved in the transport protocol at all, except maybe to validate that the certificates are still valid (CRL / OCSP) at the time that the connection is being established.

  4c. However, why do I need to involve a CA when I can sign a message myself and ask the receiver to verify the signed message? Why involve a third-party?

The CA is only involved to let the receiver trust the public key of your certificate. If you can use an out-of-band procedure to trust the public key / certificate then you don't need a CA (you could e.g. use self-signed certificates in that case).

You're still a terrible long way off of defining your own secure transport protocol. Either you should follow a crypto course and practice a lot, or you should use an existing protocol such as TLS.


Why would the use of Curve25519 in Dragonfly leak information?

In the Dragonfly protocol on an elliptic curve, the password is mapped to a point $P$, and then both sides exchange (among other things) the values $-mP, -m'P$.

If the elliptic curve has a composite order, and in particular, has a small cofactor $h$, then it is easy, given a value $P = xG$ (where $G$ is a generator), to find the value $m \pmod h$, that is, the order (mod $h$) of $P$.

So, if an attacker observes an exchange between two legitimate parties, what he can do to test a potential password is to map it into a point $P'$, and compute the order (mod $h$) of $P'$, and the two observed values $-mP, -m'P$.  If his guess of the password was correct, then the order of $-mP, -m'P$ will always be a multiple of $P'$; if it is not, his guess of the password is impossible, and so he can remove that from his list.

Using this logic, it is likely that the attacker ma be able to eliminate approximately half of his dictionary entries by listening into one (or possibly several in a slightly more sophisticated version of this attack); this is contrary to the security goals of Dragonfly.

Also, it would be fairly easy to modify the HuntAndPeck procedure to avoid this weakness (just multiply the derived point by $h$); however the RFC doesn't specify that...


I guess it makes more sense if you write the two equations like this (referring to the nice diagram in Wikipedia):
$$L_{i+1}=R_i,\; R_{i+1}=L_i\oplus F_{K_i}(R_i).$$
In each round, the round function $F$ takes as input the corresponding round key $K_i$ and the previous round's right output, then computes the output value, which is then XORed with the previous round's left output.
$F$ is usually modeled as a pseudorandom function and has many instantiations (see here for a list of Feistel ciphers, of which each specifies its own $F$ instantiation and key schedule).
This post discusses the requirements/goals for good $F$ instantiations.


How to understand why an algorithm uses additive or multiplicative homomorphic

The Why question has a deep answer since it is deep research! The How question is a lot easier. To check that how an encryption scheme is homomorphic look at the general homomorphism;
Let $f:A\to B$ be a map that preserve the structures.
$$f(x \cdot y) = F(x)\cdot f(y)$$ then we say $f$ is homomorphism ( in a very simple terms).
This is a bit different in FHE settings since schemes are semantically secure ( most of them) so the comparison cannot be made on the range ( encrypted message space) so you need to decrypt to see that.
To check the addition ( or any operation that FHE ( or partial FHE) uses) take two different inputs $x_1 \neq x_2$ and apply the rule where $\mathcal{E}$ stands for FHE encryption and $\mathcal{D}$ stands for FHE decryption.
$$\mathcal{E}(x_1 + x_2) = \mathcal{E}x_2) \boxplus \mathcal{E}(x_1),$$ we cannot check this, so we need decryption.
$$x_1 + x_2 = \mathcal{D}\left(\mathcal{E}(x_2) \boxplus \mathcal{E}(x_2)\right)$$
As done for addition this can be done for any operation. Why $\boxplus$ instead of $+$, the operation on the encrypted messages doesn't need to be an addition for addition.
So the general rule, let $\oplus$ be the operation that you want to test its homomorphism. Then
$$x \oplus y = \mathcal{D}\left(\mathcal{E}(x) \boxplus \mathcal{E}(y)\right)$$ where $\boxplus$ can be equal to $\oplus$  or not.
For example in Goldwasser–Micali cryptosystem
\begin{align}
\mathcal{E}(b_1)\cdot \mathcal{E}(b_2) &= x^{b_1} r_1^2 x^{b_2} r_2^2 \;\bmod\; n \\[6pt]
&= x^{b_1+b_2} (r_1r_2)^2 \;\bmod\; n \\[6pt]
&= \mathcal{E}(b_1 \oplus b_2).
\end{align}
the multiplication of the ciphertext is equal to the X-OR of the plaintext this is mostly used in fingerprint validation on encrypted data.
In the Paillier cryptosystem
\begin{align}
\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= (g^{m_1} r_1^n)(g^{m_2} r_2^n) \;\bmod\; n^2 \\[6pt]
&= g^{m_1 + m_2} (r_1r_2)^n \;\bmod\; n^2 \\[6pt]
&= \mathcal{E}(m_1 + m_2).
\end{align}
As we can see the multiplication of the ciphertext is equal to addition of the plaintext. This is used for the aggregation of the data, especially in databases.
The ( textbook) RSA cryptosystem  on the other hand
\begin{align}
\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= m_1^e m_2^e \;\bmod\; n \\[6pt]
&= (m_1 m_2)^e \;\bmod\; n \\[6pt]
&= \mathcal{E}(m_1 \cdot m_2)
\end{align}
uses the same operation on both plaintexts and ciphertexts.


How do malware rely safely on ECDH algorithm to maintain secrecy of keys?

Quick summary.
Ransomware works by a public-key key encapsulation mechanism: pick a secret key $h$ and an encapsulation $\sigma$ of it for the malware operator's public key, so that only the malware operator can recover $h$ from $\sigma$ using their private key; then encrypt all the files using a symmetric cipher under the key $h$, erase $h$, and pay the malware operator ransom to get $h$ back from $\sigma$.

It's easy to build a public-key key encapsulation mechanism out of a public-key key agreement scheme such as ECDH with a long-term public key for the recipient: Generate a single-use anonymous key pair for the sender, combine the sender's private key with the recipient's public key to derive $h$, erase the sender's private key, and transmit the sender's public key as the encapsulation of $h$.  Using that as a subroutine, the malware then works just like it would with any public-key key encapsulation mechanism.

Details.
First, for reference, here's a way malware on the host can use a public RSA modulus $n$, say between $2^{2047}$ and $2^{2048}$, with secret factorization $n = pq$ known only to the malware operator.

Pick a nonnegative integer $x$ below $n$ uniformly at random using the host's random number generator, e.g. /dev/urandom on Unix or CryptGenRandom on Windows.
Compute and store $y = x^3 \bmod n$.
Compute $h = H(x)$, where $H\colon \mathbb Z/n\mathbb Z \to \{0,1\}^{256}$ is a random oracle.  E.g., you might instantiate $H$ with SHA-256 on the little-endian $\lceil\log_{256} n\rceil$-byte encoding of the least nonnegative residue of $x$.
Compute and store $c = \operatorname{AES-GCM}_h(\mathit{data})$, where $\mathit{data}$ is whatever important data are on the host's persistent storage that you're ransoming.
Erase $x$, $h$, and $\mathit{data}$.
When the hapless user pays the ransom, transmit $y$ and a proof of payment to the malware operator.

On receipt of $y$ and proof of payment, the malware operator can use secret knowledge of $p$ and $q$ to compute $x = y^d \bmod n$ where $d$ solves $3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}$, and from there derive $h = H(x)$ for the luser to use to decrypt $c$ with AES-GCM.

The security of this scheme relies on the difficulty of computing cube roots of uniform random integers modulo $n$ without knowledge of the factorization of $n$.  There are some integers whose cube roots modulo $n$ are very easy to compute: the ones that are perfect cubes as integers in the first place, so that ordinary real number cube root algorithms can compute them.  But the vast majority of integers are not perfect cubes, so the probability that $y$ happens to be a perfect cube is negligible, and the cheapest algorithms we know to compute $x$ or $h$ given $y$ with nonnegligible probability work by factoring $n$, namely ECM and GNFS.

How does it work with ECDH?
Fix a standard public field $k$, say $\operatorname{GF}(2^{255} - 19)$.  Fix a standard public curve $E/k$, say $y^2 = x^3 + 486662 x^2 + x$.  Fix a standard public $k$-rational point $G \in E(k)$ of large prime order, say $G = \pm x^{-1}(9)$.  Fix a public $k$-rational point $P \in E(k)$ for which the malware operator knows a secret integer $s$ such that $$P = [s]G = \underbrace{G + G + \dots + G}_{\text{$s$ times}}.$$  Using these parameters, the malware on the host will:

Pick a nonnegative integer $t$ between $2^{254}$ and $2^{255}$ that is a multiple of 8, uniformly at random using the host's random number generator, e.g. /dev/urandom on Unix or CryptGenRandom on Windows.
Compute and store $Q = [t]G$.
Compute $h = H([t]P)$.
Compute and store $c = \operatorname{AES-GCM}_h(\mathit{data})$.
Erase $t$, $h$, and $\mathit{data}$.
When the hapless user pays the ransom, transmit $Q$ and a proof of payment to the malware operator.

On receipt of $Q$ and proof of payment, the malware operator can use secret knowledge of $s$ to compute $$[s]Q = [s\cdot t]G = [t\cdot s]G = [t]([s]G) = [t]P,$$ and from there derive $h = H([s]Q) = H([t]P)$ for the user to use to decrypt $c$ with AES-GCM.

This scheme is sometimes called ECIES.  The pair $(s, P)$ serves as the recipient's long-term key pair, while the pair $(t, Q)$ serves as the sender's single-use key pair, for public-key key agreement with an elliptic-curve Diffie–Hellman function.*  Choosing a single-use anonymous key pair like this turns a public-key key agreement scheme into a public-key key encapsulation mechanism.

The security of this scheme relies on the difficulty of computing discrete logarithms in the group $E(k)$.  The parameters are all public; all that the adversary—in this case, the hapless user who has been afflicted by ransomware, or the IT specialists they hire to recover their data without just paying the ransom—doesn't know are the secret integers $s$ and $t$, the AES-GCM key $h$, and the poor user’s data.

* The curve chosen, Curve25519, admits a fast algorithm to compute $x([s]G)$ given only $s$ and $x(G)$, which is why the Diffie–Hellman function is called X25519; we actually don't ever compute the $y$ coordinates or full points, just the $x$ coordinates above, but the notation got cumbersome when everything was written as $x(Q)$, $H(x([t]P))$, etc.


Difference between Verification and Public Key for Signature Schemes

Should I always call the key used for verification "public key" even on those settings?

Usually it is a public key, or at least it is called that in the key pair generation procedure of the cryptosystem that is used. Public key is in that case a more generic term - it may not be decided for what the key will be used after all.  Similarly, cryptographic API's will often have a specific class that performs the key pair generation, so in that case the more generic term "public key" is likely to be used.

  Is it ok to call it verification key on those settings instead?

Sure, and I've seen many cases where the shorthand SK and VK are used for "Signature generation Key" (or just "Signing Key") and "Verification Key". I'd probably prefer it because it is more precise; I guess there is no judge out there that decides these things for us.

Beware that SK is also often used for "Secret Key" which is kinda-OK, because private / signing keys are of course secret by definition.

  I have seen more work say on multivariate, lattice based and post quantum in general stuff call it more and more verification key they assume is public, is it something that is coming to fore or there is a difference of meaning between the 2 terms?

Yes, it is about usage. Many things are still based on RSA where you can also use a public key for encryption. In that case calling it a verification key doesn't make sense. I think that for signature generation / verification specific keys the term "verification key" makes perfect sense, especially if in that scheme the key is not public.

As an aside: beware that in many schemes it is possible to derive the public key from data such as signatures. There is nothing in the definition of signature generation that prevents that. Moreover, for many schemes you can directly calculate the public key from the private key, so you cannot swap the terms whenever you like to do so.

In short, don't assume that you can keep the verification key a (shared) secret; you'll need proof for that.


Characteristics of an isogeny between super-singular elliptic curves

Given two elliptic curves $E_1$ and $E_2$, an isogeny from $E_1$ to $E_2$ is an algebraic map $\phi$ (it is basically defined from rational functions) that sends the neutral element from $E_1$ to the neutral element of $E_2$.
As stated in Theorem 4.8 in page 71 of The Arithmetic of Elliptic Curves by J.H. Silverman:

Let $$ \phi : E_1 \longrightarrow E_2 $$ be an isogeny. Then $$ \phi(P+Q) = \phi(P) + \phi(Q)\quad \text{for all } P, Q \in E_1.$$

In other words, the isogeny is a group homomorphism (the group law of the curve $E_1$ is preserved after the transfer to the curve $E_2$).
The proof involves the divisor class groups of the curves, using the fact that the isogeny induces a group homomorphism between them.


Just no.
If you use some files and a CSPRNG as data source for a deterministic algorithm, it's not a true random number generator.

According to your own Schneier quote:

  If you run the sequence generator twice with the exact same input (at
  least as exact as humanly possible), you will get two completely
  unrelated random sequences.

It sounds like your generator will generate the same numbers, so... don't mistake the CSPRNG for your generator. The CSPRNG is input for your generator. (And even if not, same input for CSPRNG is same output).

There are other problems (like thinking two images of the same place are independent), but they don't really matter anymore.

...

  Obviously I tried to create a TRNG

That's a pretty good giveaway that you don't really know what your doing. A TRNG can't be created with some software piece on a turing-machine-alike. Nobody can, never.


Is there a signature scheme in which private keys can't be linked to their signatures?

The use case I have in mind is that Alice would have 100 private keys, with one key be the distinguished "true" key, and then send these 100 public/verifier keys to Bob (and then Alice would delete the 100 private keys from her computer). She would always sign messages with "true" key.

If she deleted all private keys, how can she then always sign with the true key? She has to keep all private keys, because in a rubberhose attack, the adversary would demand access to check what kind of private keys Alice has stored. Obviously she could only sign messages with a key she didn't delete again.
But for your scenario, you actually don't need an unusual signature scheme, here are two ways to achieve what you want:

Alice uses common signature schemes (they don't have to be the same, as long as the signatures have equal length), with all verification keys being public. And when she sends a message to Bob, she always uses the same signing key. And now she always encrypts the signature with Bob's public key. As long as Bob isn't compromised, no one knows which key was used.
as fgrieu pointed out, the randomized signatures can be used to get covert channels. Basically you agree with Bob on at the setup on a function over a bit array. Examples would be lowest (few) bit, parity of bits, 1st bit xor 5th bit, etc.
In RSA-PSS you can put that information directly in the padding. In DSA (or ElGamal signatures) you would have to put it in the signature itself or an intermediate result of the verification, because the verifier can't extract $k$ from the signature. Instead, you would have to try multiple values of $k$.

But coming back to a previous part of your question:

Namely, I'm looking for a signature scheme in which given a signed message and a private key, you can't tell whether the private key was used to sign the message; only the public key (or rather verifier key) can.
A corollary is that public/verifier key is not derivable from the private key. In addition, the signing process must be stochastic, as otherwise you could sign the message and see if it produces the same signature.

ElGamal and DSA signatures don't fit this: From $x,r,s$ you can calculate $k$, and then check if $r=g^k$ holds. If you consider the RSA setting, there is a really interesting property, which Ilmari Karonen pointed out in his comment: Assume that there are two keys, with each one consisting of the modulus $n$ and one exponent, s.t. we get the usual RSA relation. If you have random values for the exponents, e.g. both have to be in a certain range, then both exponents are actually drawn from the same distribution, and knowing one does not reveal the other - under the RSA assumption.
However, there is one problem: Verification keys are public. As soon as the attacker gets hold of a signing key, they can calculate the product of the exponents. And with this the modulus can be factorized efficiently, so basically everything is out in the open.
At this point I am not sure what the adversary actually knows exactly. In general, (basic) signature schemes are built from oneway-trapdoor functions and there has to be a efficiently computable equation for the verification. In order to achieve this, the public key is always derived from the private key with the trapdoor in mind, so that you can't calculate "backwards" to the private key. But if you want that this computation is infeasable, then this might imply that the key generation can't be done efficiently.
However, group signatures or ring signatures might be of interest to you, because they have following properties:

There are different signing keys (derived from a master key) and just one verification key
In ring signatures it is not possible to determine which signing key created a signature
In group signatures, the master key is required to determine which key signed a message.

In your case you could give Alice multiple keys, but there is a problem: If you require Bob to be able to tell which key signed a message, then you need group signatures and Bob has to have the master key. Because otherwise he won't be able to tell the difference either.


Problem related to the discrete logarithm problem

This problem is equivalent to the Computational Diffie Hellman problem; this remains true even if we know $u$.
See this paper for details; in summary:

Suppose we have an oracle that, given $G$, $X = xG$ and either (depending on the oracle type) $U = uG$ or $u$, gives us the value $J = x^{-1}uG$.  Then, we can use this Oracle to construct a second Oracle that, given $H, aH$, computes $a^2H$ (by passing $G = aH$, $X = H = a^{-1}G$, $U=G$ (or $u=1$), and recovering $J = (a^{-1})^{-1} \cdot 1 \cdot aH = a^2H$.  We can then use this second Oracle to solve the CDH problem (given $G, aG, bG$, we compute $(2ab)G = (a+b)^2G - a^2G - b^G$, and then do a point halving.

Suppose we have an oracle that solves the CDH problem, that is, given $H, aH, bH$, gives us the value $abH$.  Then, given $G$, $xG$, we can compute $x^{-1}G$ by setting $H = xG$, $aH = bH = G = x^{-1}H$ and $bH = H$.  We give this to the Oracle which gives us the value $(x^{-1} \cdot x^{-1}) H = x^{-1}G$.  Then, we can convert that value into $J$ by either multiplying it by $u$ (if we know it), or invoking our CDH Oracle one more time with the inputs $G, x^{-1}G, uG$.


Relation between factors and their sum on RSA

Let $n = p \cdot q $ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup.
The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both are known.
Let $b = p +q$. If $b$ is also known, then we can form a quadratic equation as
$$ f(x) = x^2 - b x + n \label{1}\tag{1}$$ by using the following identity:
$$(x-p)(x-q) = x^2 - (p+q) x + (p\cdot q).$$
The solution of the quadratic equation (\ref{1}) is that $p$ and $q$ and can be found by the second-degree formulas using this equation:
$$p,q =  \frac{ b \pm \Delta}{2}$$ where the discriminant $\Delta = \sqrt{b^2 - 4n}.$
It is also possible to directly find the private exponent too! Observe that:
$$\varphi(n) = (p-1)(q-1) = pq - p -q +1 = pq - (p +q) +1 = n - b + 1.$$
Since $e \cdot d \equiv 1 \bmod \varphi(n)$, you can solve for $d$ without computing $p$ and $q$, though those are also cheap to compute if you would still like to use them.

Example:
Let $m = 35$ and $b = 12$. We thus need to solve $x^2 - 12x + 35$, which gives us:
$$\Delta = \sqrt{12^2 - 4 \cdot 35} = \sqrt{144 - 140} = \sqrt{4} =2. $$
As a result:
$$p = \frac{12 + 2}{2} = 7 \text { and }  q = \frac{12 - 2}{2} = 5.$$


Parallel file encryption and authentication for large files

To answer your ideas of:

"I use hash-then-encrypt" with CBC + SHA-1
"I use MAC-then-encrypt" with CBC + HMAC
"I won't use GCM because of unclear usage guidance"

First, hash-then-encrypt is a really bad idea. You really should avoid it if possible. Details are explained in this related question on Crypto.SE.

Second, MAC-then-encrypt is a concept you also should avoid. Not only do generic compositional security proofs don't generally hold, but it also allows for padding oracle attacks in some circumstances, so encrypt-then-MAC is better and there's no significant advantage to use authenticate-then-encrypt over the more generically secue encrypt-then-authenticate. Also see our canonical question on this subject.

Third : GCM. You indeed only should encrypt than less than 60GiB of data under a given key-nonce pair. However, you could assign (ascending) nonces to your data chunks (of a few kBs each) and authenticated encrypt them each using a different nonce. This way you stay way below the 60GB limit and you generate your nonces deterministically (using counter incrementation) which will also quite reliably protect you against nonce re-use based on nonce collisions. Upon retrieval of the data you could just check then whether all chunks are valid and whether a chunk is missing (because there's a gap in the nonces) and maybe you'd want to encode the number of chunks into each chunk to allow proper verification.


How to calculate if probability is negligible or not

First of all, keep in mind that all meaningful probabilities must be between $0$ and $1$.  In particular, this means that, if $X$ and $Y$ are probabilities, $0 \le XY \le \min(X, Y)$.

In cryptography, a probability is considered "negligible" if it is very small.  What actually counts as "negligible" depends on context, but typically, we're talking about probabilities on the order of $1/2^{128}$ or less.

Conversely, a "non-negligible" probability may be high, perhaps even close to $1$.  In fact, since we typically want probabilities (of an attack succeeding) to be small, we may safely assume that, in the worst case, all non-negligible probabilities are $\approx 1$.  This leads to the following "rules":

The product of two negligible probabilities is (always) negligible.
The product of a negligible and a non-negligible probability is also (always) negligible.
The product of two non-negligible probabilities is (usually) not negligible.

Corollary: For the product of several probabilities to be negligible, at least one of them must (usually) be negligible.

Multiplying a probability by a constant $\approx 1$ (say, between $1/2^{16}$ and $2^{16}$) does not (usually) change its negligibility.
The sum of two negligible probabilities is (usually) negligible.
The sum of a negligible and a non-negligible probability (or of two non-negligible probabilities) is never negligible (and might not always, strictly speaking, be a probability).

Thus, without knowing anything about $A$ and $B$, except that they are probabilities, the most we can say about $Q = 2C(AB)$ is that it is somewhere between $0$ and $2C$.  Furthermore if $C$ is not negligible, then $2C$ is definitely not negligible; thus, for $Q$ to be negligible, $AB$ must (generally) be negligible.

For $AB$ to be negligible, it's sufficient for either $A$ or $B$ to be negligible.  If neither $A$ nor $B$ is negligible, their product cannot be assumed to be negligible either — although it's possible for $AB$ to be negligible (e.g. $AB \approx 1/2^{128}$) even if both $A$ and $B$ are only "nearly negligible" (e.g. $A \approx B \approx 1/2^{64}$).

Conversely, for $Q = 2C(AB)$ not to be negligible, neither $A$ nor $B$ may be negligible.  (Strictly speaking, for any specific threshold of negligibility, the factor of $2 > 1$ could bump a probability just below the line to just above it; but the whole point of using terms like "negligible" is to note that we're speaking loosely and usually ignoring such factors of $\approx 1$.)  It's still possible for all of $A$, $B$ and $C$ to be above our negligibility threshold, but for their product to be below it (if two or more of them are "almost negligible"), but we cannot assume this without knowing their values more precisely.


Can one claim that AES is a perfect cipher?

Short version: I don't think AES restricted to key-size messages is a perfect cipher, and I'm quite sure it can't be proven without breaking AES.

Long version:

A perfect cipher means that an attacker has the same chance to guess the plaintext if he has the ciphertext or he has no ciphertext at all, i.e. the ciphertext gives no information to someone who doesn't have the key (even with infinite computation resources).

AES itself is a 128-bit block cipher. To use it for longer messages, you need a mode of operation, and the probabilities in this statement will likely depend on the chosen mode. To avoid the complications, let's assume we have a 128 bit message encrypted with ECB mode (i.e. directly application of the block cipher), and the key is not reused for any other message.

$\newcommand\Enc{\operatorname{Enc}}\newcommand\P{\mathbb P}$Then we have a probability distribution $\P$ of the plaintext $P$ (this distribution is assumed to be known to the attacker), and on the (secret) key $K$ (which is assumed to be a uniform distribution). This induces a probability distribution of the ciphertext $C = \Enc_K(P)$ by
$$\P(c=C) = \sum_{k} \P( K = k \text{ and } \Enc_k(P) = c) = \frac{1}{2^\text{key size}} \sum_k \P(\Enc_k(P) = c)$$
The conditional probability $\P(P=p|C=c)$ is defined as $$ \P(P=p|C=c) = \dfrac{\P(P = p \text{ and } C = c)}{\P(C = c) },$$
and for a perfect cipher we want that this is equal to $\P(P=p)$ for all $c$ and $p$.

In effect, this means at least that for each pair of 128-bit-blocks $(c, p)$ there must be an equal number of keys $k$ with $\Enc_k(p) = c$. With 128-bit keys, this would mean that each key maps a given plaintext on a different ciphertext, and all ciphertext blocks can be hit this way.

While this sounds like a reasonable property for a block cipher, most block ciphers (including AES) instead are trying to approximate a random permutation, where each key's actions are independent from each other – which includes the possibility that there are plaintexts $c$ and pairs of keys $k_1, k_2$ with $\Enc_{k_1}(c) = \Enc_{k_2}(c)$.

A proof that this is not possible could possibly (depending on the proof) provide a way to retrieve the key in a known-plaintext attack, which would mean that AES is broken for all practical uses (with more than one use of each key).

(This is similar for the one-time pad: correctly used, it is a prefect cipher, but using the same key twice, it is totally broken.)

AES doesn't look like easily broken, so we can assume that this is not possible.


I am going to have to say splitting it into blocks. Although your definition of large may differ from mine, GCM is unsuitable for large files, and hashing the entire file can be problematic, especially if the file is spread across storage devices, and parts of it are not currently available for reading in the sequence you want.

Splitting it into blocks, say 4-16MB at a time, will incur very little overhead for storage of a hash, allow you to encrypt several blocks at a time in whatever order is currently available, and allow you to verify integrity of selected data out of sequence.

Each large file would be given an index file, which contains the IVs and integrity hashes for each block, which can then be encrypted and authenticated independently of the blocks. If you have verified the index data, you can perform random reads of the blocks by validating their hash and decrypting them.

As long as you are using secure methods for hashing, authenticating, and encrypting, (say SHA-512, HMAC-SHA-512, AES-CTR) the full system should be secure, and be very simple to implement, in addition to being extremely fast and being able to handle extremely large files. At least 36 index bytes would be required per block depending on implementation, so a 1TB file with 16MB blocks would require a 2.25MB index file, 100TB 225MB, and so on, and the ability to scale up to 64PB per large file, using a 144GB index, which could also be broken into blocks using the same method if necessary.

You would be looking at around a 60ms latency or less to access any 16MB block of the large file due to encryption/hashing overhead, if the index file is already authenticated. Smaller blocks would give lower latency but larger index files. Spinning storage latencies are larger and there is overlap between read and decrypt, so the performance hit on a modern cpu would be much smaller, probably well under 10ms per block, as decryption can be performed at the same time as hashing with the same read, in 1KB increments, and the decryption speed is not the limiting factor. When using faster storage such as NVME drives, a hash tree mode will improve performance if you have CPU cores to spare.


If you need a 32 bit PRP, might I suggest the Speck cipher?  It isn't greatly secure (with a 32 bit block size, the only option is a 64 bit key, which isn't great), however it's extremely fast.


FHE: What is the difference between multiplicative depth and multiplicative level?

In Fully Homomorphic Encryption (in short FHE), we have a noise that increased with every operation, and it is almost doubled with the multiplication. When preparing the circuit $\mathcal{C}$ to $\texttt{EVAL}$ on the cloud we have to consider various parameters to deal with the noise of which the FHE scheme provides. Minimizing boothstrapping calls, which is very costly, number of modulus switching and linearization, etc. According to parameters, the FHE scheme may provide more than 1 multiplication without bootstrapping.

Multiplicative depth (From your reference) :

  The multiplicative depth is the maximal number of sequential homomorphic multiplications which can be performed on
  fresh ciphertexts such that once decrypted we retrieve the result of these multiplications.

What is multiplicative level?

This cannot be easily understood if you don't implement some problems. Here is a simple explanation from Efficient Fully Homomorphic Encryption from (Standard) LWE

  During the homomorphic evaluation, we will generate ciphertexts of the form $c = ((v, w), \ell)$, where the tag $\ell$ indicates the multiplicative level at which the ciphertext has been generated (hence fresh ciphertexts are tagged with 0). The requirement that $f$ is layered will make sure that throughout the homomorphic evaluation all inputs to a gate have the same tag.

Here is the trick, if you need to add a fresh ciphertext $c_i$ into a level $l$ (that can be quite common as encryption of 1 or 0 1), you need to increase the level of $c_i$ to $l$. Otherwise, the operations will fail.

Example: Let we want to multiply $p_1,p_2, p_3$ with FHE. Let $c_i = Enc_{k_{pub}}(p_i)$, and clearly they have 0 multiplication level. You need to send $$\texttt{EVAL}(\mathcal{C},k_{pub},c_1,c_2,c_3)$$ The server first calculates3 $$c_4 = c_1 \cdot c_2.$$ Now, the $c_4$ has multiplication level 1. To multiply $c_4 \cdot c_3$ we need to increase the multiplication level of $c_3$ to 1. Once they are equal, we can multiply.

In short: multiplicative depth is how much multiplication can be performed and multiplicative level is how many multiplication is performed on a ciphertext2.

For the comment: While implementation we want to keep track of the current level of the ciphertexts so that if the scheme doesn't allow multiplications of different ciphertext we can adjust or we make sure that the level on any ciphertext doesn't exceed the depth. So, it is a quite useful definition for a variable.

1 The Private Information Retrieval article Bandwidth Efficient PIR from NTRU is implemented as Mux and the selector bits needs to have the same multiplicative level.

2Multiplcative level cannot exceed the multiplicative depth, otherwise you cannot decrypt.

3The calculation performed according to your circuit $\mathcal{C}$.


How many iterations for Pollard's $p-1$ with $p = r^k + 1$ for prime $r$?

What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + 1 < q < r^{k+1}$?

Assuming that $p$ is prime, and that $N$ is smaller than 8 billion bits in length, then step 3 of the referenced algorithm will take at most 17 iterations before exiting via condition (a) or condition (b).


A multi-target attack is an attack on many users of a cryptosystem at once.

The attacker might be satisfied with breaking one user—for example, if there are a thousand human rights activists in a network under attack by an authoritarian state, breaking into the Signal chats of one activist may be enough to compromise the whole network.

Moreover, the state's intelligence agency may have many more targets than the one activist network—there may be an environmental activist network, an anticorruption activist network, foreign intelligence networks, different branches of government, etc.—and it is in the state's interest to break into any of these.

Of course, there may actually be only one human user who has many keys—for example, a thousand (say) HTML documents encrypted with different AES keys derived from a master key with HKDF-SHA256, so the adversary has the ciphertext for the same plaintext <!DOCTYPE html>\n under many different keys.  More generally, a multi-target attack is an attack on many instances of a cryptosystem: many keys with known plaintext/ciphertext pairs under the same cipher, many group elements with the same discrete log base, many public keys for the same signature scheme, etc.

There are many different batch advantages that multi-target attackers might take advantage of—you asked about block ciphers, but it's worth noting several different settings because their qualitative differences can lead to substantial quantitative security differences:

For a hash function $H$, the adversary may have hashes $H(k_1),$ $H(k_2),$ $\dotsc,$ $H(k_t)$ for $t$ different unknown target keys $k_1, k_2, \dotsc, k_t$.  The goal is to recover any one of the $k_i$.  Examples of $H$:

AES in CTR mode on a known file header:
$k \mapsto \operatorname{AES}_k(0).$
A message authentication code under HMAC-SHA256 on a TLS record:
$k \mapsto \operatorname{HMAC-SHA256}_k(\text{‘250 OK’}).$
A seed phrase from which a cryptocurrency address is derived:
$\mathit{seedphrase} \mapsto \operatorname{X25519}(\operatorname{HKDF-SHA256}(\mathit{seedphrase}), \underline 9).$

The best generic multi-target preimage search algorithms—parallel versions of Oechslin's rainbow tables and Rivest's distinguished points—have area*time cost proportional to $2^\lambda\!/t$ evaluations of $H$ where $\lambda$ is more or less the size of the $k_i$.

That is: The cost of a generic preimage search to break the first of $t$ targets is $1/t$ the cost of a generic preimage search to break one specific target.  Have a thousand activists to target?  It'll cost a thousand times less to compromise one of them if you attack them in a batch than if you try to attack them one by one independently.  It will still cost $2^\lambda$ to find all of the target keys, but you usually don't need to wait that long.

How do these algorithms work?

You might think of a multi-target ‘speedup’ as populating a hash table ht and then replacing the single-target test for a candidate key H(k) == h by H(k) in ht which also runs in ‘O(1)’ time but tests $t$ keys at once.  However, this simplified algorithm doesn't actually reduce the adversary's area*time cost—which is generally a good proxy for cost in, e.g., yen to power a machine for long enough to find the key—because for very large numbers of keys it spends lots of time sequentially waiting for communication due to memory latency twiddling thumbs that could have been spent running random walks in parallel.  Instead:

Rainbow tables.  We do a pseudorandom walk on the space of inputs and compute a chain of $$\sigma_0 \xrightarrow{H} h_0 \xrightarrow{R_1} \sigma_1 \xrightarrow{H} h_1 \xrightarrow{R_2} \cdots \xrightarrow{H} h_\ell,$$ alternating between inputs and hashes with a family of reduction functions $R_i$ mapping a hash back to some other input, e.g. yielding a 128-bit candidate key or a candidate BIP39 passphrase.  We store the starting point $\sigma_0$ and the ending point $h_\ell$.

Actually, we don't do this just once; we do this in parallel on a large number $p$ of randomly chosen starting points.  We also compute the ending point in chains starting at $H(k_i)$ as if it were $1, 2, \dotsc, \ell$ iterations from the end:

\begin{align*}
    \sigma_{1,0} \xrightarrow{H} h_{1,0}
                 \xrightarrow{R_1} \sigma_{1,1}
                 \xrightarrow{H} h_{1,1}
                 \xrightarrow{R_2} \cdots
                 &\xrightarrow{H} h_{1,\ell}, \\
    \sigma_{2,0} \xrightarrow{H} h_{2,0}
                 \xrightarrow{R_1} \sigma_{2,1}
                 \xrightarrow{H} h_{2,1}
                 \xrightarrow{R_2} \cdots
                 &\xrightarrow{H} h_{2,\ell}, \\
    \vdots \\
    \sigma_{p,0} \xrightarrow{H} h_{p,0}
                 \xrightarrow{R_1} \sigma_{p,1}
                 \xrightarrow{H} h_{p,1}
                 \xrightarrow{R_2} \cdots
                 &\xrightarrow{H} h_{p,\ell}; \\
    H(k_1) \xrightarrow{R_1} R_1(H(k_1))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{1,1}, \\
    H(k_1) \xrightarrow{R_2} R_2(H(k_1))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{1,2}, \\
    \vdots \\
    H(k_1) \xrightarrow{R_\ell} R_\ell(H(k_t))
           &\xrightarrow{H} h'_{1,\ell}; \\
    \vdots \\
    H(k_t) \xrightarrow{R_1} R_1(H(k_t))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{t,1}, \\
    H(k_t) \xrightarrow{R_2} R_2(H(k_t))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{t,2}, \\
    \vdots \\
    H(k_t) \xrightarrow{R_\ell} R_\ell(H(k_t))
           &\xrightarrow{H} h'_{t,\ell}.
  \end{align*}

Then we sort all the ending points—the $h_{j,\ell}$ and the $h'_{i,r}$—and look for a collision among them.  If we find a collision $h_{j,\ell} = h'_{i,r}$, then we can start up again at $h_{j,0}$ and compute forward by $\ell - r$ steps to find a candidate input $\sigma_{j,\nu}$ if $H(\sigma_{j,\nu}) = H(k_i)$.  (Of course, $H(\sigma_{j,\nu})$ may turn out not to be $H(k_i)$ if two random walks happened to collide temporarily, but false positives should be fairly rare.)

The batch advantage arises in part because in the sorting step, we are effectively simultaneously testing all hashes from the $p$ parallel chains against the $t$ target hashes (with some false positive rate), at cost about $(p + \ell t)^{1.5}$ of sorting a $(p + \ell t)$-element array rather than at cost $\ell\cdot p\cdot t$ of testing all $\ell\cdot p$ guesses directly against all $t$ hashes (with zero false positive rate).  When $p \geq t^2$, the net reduction in cost is a factor of about $t$.
Distinguished points.  We pick small subspace of points in the key space that are easy to discern, say those whose first 23 bits are 10100011110110001010, and call them distinguished points.  Again we will do many independent pseudorandom walks in parallel, but instead of stopping after exactly $\ell$ iterations, we will stop when we find a distinguished point.

On $p$ parallel machines, we pick starting points $h_j$ uniformly at random from the key space and iteratively compute $H(h_j),$ $H(H(h_j)),$ $\dotsc,$ $H^\nu(h_j)$, until either $H^\nu(h_j)$ is a distinguished point, in which case we store $h_j$ and $H^\nu(h_j)$, or $\nu$ exceeds a limit $\ell$, in which case we throw it out and start over with a different $h_j$:

$$h_j \xrightarrow{H} H(h_j) \xrightarrow{H} H^2(h_j) \xrightarrow{H} \cdots \xrightarrow{H} H^\nu(h_j).$$

We also iteratively compute $H(H(k_i))$, $H(H(H(k_i)))$, etc., for each $i$, until we find a distinguished point $H^\mu(k_i)$.  Then we sort the $H^\mu(k_i)$ and the $h_{j,\nu}$, and if there is a collision $H^\mu(k_i) = H^\nu(h_j)$, we start over at $h_j$ and iterate $H$ until we find a candidate $k_i$: $$h_j \xrightarrow{H} \cdots \xrightarrow{H} H^{\nu-\mu}(h_j) \stackrel?= k_i \xrightarrow{H} H(k_i) \xrightarrow{H} \dotsc \xrightarrow{H} H^\nu(h_j) = H^\mu(k_i).$$  Of course, this might also happen because of a collision in $H$ elsewhere causing the two chains starting at $h_j$ and $H(k_i)$ to spuriously merge, so there's some false positive rate.

Again, the batch advantage arises in part because in the sorting step, we are effectively simultaneously testing all hashes anywhere in the $p$ parallel chains against the $t$ target hashes at cost $(p + t)^{1.5}$ rather than $\ell\cdot p\cdot t$, with some false positive rate arising from collisions in $H$.

(Extending distinguished points with reduction functions to make the technique work on, e.g., password spaces is left as an exercise for the reader.)

For detailed analyses of the expected costs and success probabilities, see Oechslin's paper and Wiener's paper (paywall-free).  (To my knowledge, the distinguished points technique first appeared in an abstract by Quisquater and Descailles at CRYPTO 1987 and in the followup paper at EUROCRYPT 1989, but it is usually credited to Rivest.)

What countermeasures can you use as the user or cryptosystem designer?  The standard two options are:

Make $\lambda$ so large that a factor of $t$ doesn't matter.  Don't use AES-128 for a 128-bit security level—use AES-256.  (Even better, use ChaCha so you can largely forget about side channel attacks.)  In general, always make sure that the narrowest pipe of secret key material is 256 bits wide.
Separate the input spaces.  For example, salt your password hashes, so that instead of having hashes $H(p_1),$ $H(p_2),$ $\dotsc,$ $H(p_t)$ for secret passwords $p_1, p_2, \dotsc, p_t$, the adversary will have salted hashes $H_{\sigma_1}(p_1),$ $H_{\sigma_2}(p_2),$ $\dotsc,$ $H_{\sigma_t}(p_t)$, which thwarts the batch advantage of the rainbow table and distinguished points algorithms.

This can be applied to block ciphers too, e.g. with randomly chosen initialization vectors, but there are costs: extra data transmission, limited block sizes for randomization, the implied secret key inside the randomly chosen IV, missed opportunity to detect replay attacks or nonce misuse, etc.

Input space separation also doesn't make it any harder for the adversary to find your key in particular, so you personally have little motivation to choose a cryptosystem with input space separation; it only makes it harder for the adversary to find anyone's key.  In contrast, using a 256-bit key provides you and the herd immunity against brute force.

But generic key search is not the only setting where multi-target attacks might be relevant.  Here are some others:

For a DLOG group with generator $g$—e.g., RFC 3526 Group #14, or Curve25519, or secp256k1—the adversary may have the powers $g^{x_1},$ $g^{x_2},$ $\dotsc,$ $g^{x_t}$ for $t$ different unknown target exponents $x_1, x_2, \dotsc, x_t$.  The goal is to recover any one of the $x_i$.

Of course, this can be solved by any generic preimage search under the hash function $H\colon x \mapsto g^x$, but there are much cheaper algorithms that cost $O(\sqrt q)$ where $q$ is the largest prime factor of the order of $g$—a combination of Pollard's $\rho$ and Pohlig–Hellman, and Pollard's kangaroo if more information is known about the ranges of the $x_i$, as well as other alternatives like baby-step/giant-step.  For specific groups there may be speedups too over generic algorithms, like the elliptic curve negation map in Pollard's $\rho$.

The cost to find the first of $t$ target discrete logs cannot be much cheaper than finding one target discrete log!  Why?  Fix a single target $h = g^x$, and pick $g^{r_1},$ $g^{r_2}$, $\dotsc,$ $g^{r_t}$ for uniform random exponents $r_i$; then apply a multi-target attack to $$(h g^{r_1}, h g^{r_2}, \dotsc, h g^{r_t})$$ to find $\log_g (h g^{r_i})$ for some $i$, figure out what $i$ was by a linear list search at worst, and finally return $$\log_g (h g^{r_i}) - r_i = \log_g (h g^{r_i}\!/g^{r_i}) = \log_g h.$$  So a single-target DLOG can't be substantially more expensive than a multi-target DLOG attack, because this shows how to use a multi-target DLOG attack to perform a single-target DLOG attack at essentially negligible additional cost.  In other words, having multiple possible targets can't make a DLOG attack cheaper the way it can make a generic key search cheaper.

This is why, for example, Curve25519 should be considered to have a ‘128-bit security level’ while AES-128 should not: in the multi-target setting of the real world, the cost of breaking the first of $t$ target Curve25519 keys is still about $2^{128}$—the same as the cost of breaking one target Curve25519 key—while the cost of breaking the first of $t$ target AES keys is only $2^{128}\!/t$.

On the other hand, there is still a cost reduction to finding all of the $t$ targets with parallel $\rho$: while it's $O(\sqrt q)$ for the first of any number of targets, it's $O(\sqrt{tq})$ for all of $t$ targets rather than $O(t\sqrt q)$ for a single-target attack repeated $t$ times—that is, a multi-target attack to find all of $t$ keys is a factor of $\sqrt t$ cheaper than $t$ independent single-target attacks.  There may also be an advantage to precomputation: for finite fields, the best DLOG algorithms factor into an expensive target-independent precomputation that can then be done once and then reused over and over again to quickly attack many targets in the same group, leading to attacks like logjam.  An intelligence agency could use that to intercept TLS conversations in real time.
For a Diffie–Hellman function $f(n, P)$ with standard base point $B$—e.g., FFDH under RFC 3526 Group #14, or X25519—the adversary may have the public keys $f(n_1, B),$ $f(n_2, B),$ $\dotsc,$ $f(n_t, B)$, for $t$ different unknown DH secrets $n_1, n_2, \dotsc, n_t$, along with oracles for $P \mapsto H(f(n_i, P))$ by claiming to have public key $P$ and trying to have an encrypted conversation with the $i^{\mathit{th}}$ user.  The goal is to recover any one of the $H(f(n_i, f(n_j, B)))$ shared secret keys used by user $i$ and user $j$ to have a private conversation.

Of course, when $f(n, P) = [n]P$ in a group written additively, this can be solved by any generic DLOG algorithm.  But the oracles provide additional information that could be exploited—Lim–Lee active small subgroup attacks if the points $P$ live in a group of composite order, Cheon's strong DH attack if the key derivation function $H$ is the identity.  These themselves don't provide batch advantages, but they are evidence that the DH problem is qualitatively different from the DLOG problem, so in principle it may admit batch advantages that DLOG does not.
For a signature scheme the goal is to forge a message/signature pair $(m, \sigma)$ under any of $t$ public keys $A_1, A_2, \dotsc, A_t$.  The story depends on the details of the cryptosystem; see an analysis of Schnorr signatures in the multi-target setting for example.  The countermeasure chosen by EdDSA, for example, is to hash the public key in with the message to limit the avenues for multi-target signature forgery.


Forcing participants to be honest in Secure Multiparty Communication

Try reading this paper https://www.math.ucla.edu/~tdokos/notes_files/garbledCircuits.pdf. It will answer your question.


Modification of RSA using two inverses, one for P mod (Q-1) and one for Q mode (P-1), instead of inverse d mod [(p-1)(q-1)], more or less secure?

This system was invented in 1973 by Clifford Christopher Cocks of the GCHQ and described in his document (then secret) A note on Non-Secret Encryption, before RSA was published. See this question for more context.

  Is this scheme more secure or less secure than the normal RSA? Better or worse?

On security, we know no difference with RSA. The restriction that $p$ and $q$ are relatively prime to $p-1$ and $q-1$ does not sizably reduce the keyspace, in fact this restriction is always met when $p/2<q<2p$, which is customary in RSA as practiced. And, by using $N$ as the public exponent, nothing more than their product is revealed about the factors. From this standpoint, RSA with small exponent reveals more: with $e=3$, about half the primes are ruled out, and this is not known to make factoring sizably easier. But, like in RSA, factorization is only one of the security threats: we know no reduction to factorization for either scheme.

On practicality, RSA is superior because it can use a small $e$, which greatly speeds-up encryption (and signature verification), with no known drawback if proper padding and leakage protection is used, or $e$ is comfortably above the bit size of $N$. Small $e$ was not in Ronald L. Rivest, Adi Shamir, and Leonard Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978. But that quickly was added by Rivest's MIT group: it's in the challenge they made for Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977).

Cock's paper clearly suggests using the Chinese Remainder Theorem for decryption, which from the standpoint of speed is superior to RSA as initially described. As far as I know, that improvement was not published before Jean-Jacques Quisquater and Chantal Couvreur's Fast decipherement algorithm for RSA public-key cyptosystem, in Electronics Letters, Oct. 1982. It is now standard practice in RSA, because it speeds up things by a factor up to about 4 compared to computing $x^d\bmod N$ by performing all the arithmetic modulo $N$.


Ciphers don't use signature schemes. They do use MACs, which are different (and employ HMAC variants of hash functions, e.g. HMAC-SHA1). There is no danger in using SHA1 in this manner (or MD5 either, but I wouldn't advise doing that if you can avoid it). TLS 1.0 and TLS 1.1 also use SHA1 and MD5 internally, but this is still considered secure because they use them differently than certificates do. The main reason SHA1 is becoming deprecated is because  the community believes attackers may someday soon gain the ability to forge SHA1 certificate signatures.


Can there be more than one valid private exponent for a given p, q, and e in RSA encryption?

Both values satisfy the checking equation (de)%phi=1, so are both correct, and if so, is one better than the other?

Actually, $(3 * 4243) % phi = 8484$; however $d=4243$ is a valid private exponent, because both $(3 * 4243) \bmod (p-1) = 1$ and $(3 * 4243) \bmod (q-1) = 1$

In any case, as I stated in a comment, if there is a valid private exponent, there there are an infinite number of valid private exponents.  If $d$ is value, then so is $d + k (p-1)(q-1)/\gcd( p-1, q-1 )$, for any integer $k$.

  Since there are an infinite number of valid private exponents, are any of them theoretically better than others?

Cryptographically speaking, they are all equivalent, and so in that sense, no one is any better than any other.

Practically speaking, well, in some rare cases, there may be, but in a surprising number of cases, it doesn't make a difference.

We generally use a CRT optimization when performing RSA private operations; with this, we precompute the values $d_p = d \bmod p-1$ and $d_q = d \bmod q-1$, and those those values exclusively (not referring to $d$ otherwise).  And, any valid value of $d$ will give you the exact same value for $d_p, d_q$, and so it doesn't matter which value of $d$ you started with.

In some rare cases, we may use the value of $d$ directly (perhaps we value simplicity over performance, perhaps we don't want the holder of the private key to know the factorization [1].

In that case, computing $C^d \bmod N$ would likely be a bit faster if $d$ where smaller; in that case, the value $d = e^{-1} \bmod \text{lambda}(p-1, q-1)$ might be somewhat preferable...

[1] On the other hand, if someone gets the values of both $d$ and $e$, they can factor, and so there may be little interest in this.


How can I find the original message of two encrypted (Vernam Cipher) text without the key

You know that the two ciphertext you are given are formed as
$$C_1 = S_1 \oplus R\\C_2 = S_2 \oplus R$$ with the same $R$ in both cases.
So you can get rid of $R$ by calculating $$C^\ast = C_1 \oplus C_2 = S_1 \oplus S_2$$
Then you know that there are only two words, $111$ and $0000$. Thus, in $C^\ast$ $1$ can only occur if one sentence contains $A$ while the other contains $B$.
From there, since the two words have different lengths, you should be able to determine candidate sentences.


As defined in FIPS 202, whereas SHA3-256 is a function mapping an arbitrary-length bit string to a string of 256 bits, the extendable output function SHAKE256 is a function mapping an arbitrary-length bit string to a string of infinitely many bits.

In both cases, the conjectured cost of computing a preimage or second preimage for a given $\ell$-bit output ($\ell = 256$ for SHA3-256, arbitrary for SHAKE256) is about $2^{\min\{256,\ell\}}$ bit operations, and the conjectured cost of computing a collision is about $2^{\min\{256,\ell/2\}}$ bit operations.  For SHAKE128, it's rather $2^{\min\{128,\ell\}}$ for (second) preimages or $2^{\min\{128,\ell/2\}}$ for collisions.

For an adversary with a quantum computer, the exponents for preimage and second preimage attacks are halved for qubit operations due to Grover's algorithm: for SHAKE256, $2^{\min\{256,\ell\}/2}$, etc.  (The costs of quantum collision search are sometimes reported to divide the exponent by three, but this is not really an accurate measure of the cost; I'd rattle off some citations but I have other work to do right now.  Patches welcome!)

Note that while SHA3-256 is usually treated as an independent random oracle from SHA3-512, and while the derivative of another SHA-3 candidate BLAKE2b-256 is also usually treated as an independent random oracle from BLAKE2b-512, in contrast the functions SHAKE256-$\ell$ for all $\ell$ are dependent because they are all just $n$-bit truncations of the same SHAKE256 function.  This also means that the length of the output need not be known ahead of time before computing SHAKE256.


Curve25519 function, scalar multiplikation

I got the answer now! Curve25519 does not have key validation. Usually you have a point $P =(x,y)$ on a elliptic curve $E$ over $F_p$. But there is not a point $P$ on the elliptic curve for every value in $F_p$. If you make a key exchange with such a system, you will get a point, or a x-Value (using Montgomery x-only computation). Now you have to test, wether the given point is on the elliptic curve or not, because you can't calculate with a point, thats not on the curve.
Now as i said Curve25519 does not have key validation, because it takes time. But the theorem (in which $X_0$ is defined, too) in the paper about Curve25519 that says, that there is a Point for every x-Value over $F_p$. So you don't need key validation!
The bottom line of is, that you only need the extension field $F_{p^2}$, because you don't want key validation.


Plaintext XOR'd with keylength-shifted plaintext

Well, if we have plaintext^shiftedPlaintext, what we have is the values $P_i \oplus P_{i+k}$, where $k$ is the length of the shift.

What does this imply?  Well, if we consider the values $P_i \oplus P_{i+k}$, $P_{i+k} \oplus P_{i+2k}$, $P_{i+2k} \oplus P_{i+3k}$, ... we get a chain where, if we guess one of the values $P_{i+nk}$ for some $n$, we can immediately reconstruct all other plaintext bytes in the chain; thus giving us the correct value for every $k$th plaintext byte.

That can be exploited in several ways.  One approach is crib dragging; we guess that a common word (the canonical crib for English is "the") occurs at a specific location, and see what that implies for other places in the plaintext; if it makes sense, then it is likely correct (and we have a large amount of plaintext; that gives useful context for other cribs); if it doesn't make sense, we try our crib elsewhere.

In addition, if the plaintext includes spaces, then a useful fact of ASCII can be useful; alphabetical letters have bit 6 set, spaces have bit 6 clear (and while numbers and punctuation also have bit 6 clear, those are comparatively rare).  So, if we see that the value of $P_i \oplus P_{i+k}$ has bit 6 set, then a good guess is that either $P_i$ or $P_{i+k}$ is a space; that acts as a 1 character crib.


More general - what is the hard problem of recovering r from r*p mod q?

When given a single triple consisting of $(p,q,x)$ with $x = r \cdot p \mod q$, then there is no hard problem. It takes one inversion and one multiplication (both in modular arithmetic) to calculate $r$.

If just $x$ is given, then you can choose $p$ and $q$ arbitrarily and calculate a matching $r$ to fullfill $x = rp \mod q$.

If the actual question is about recovering the original values: That's not possible. This is exactly the same situation like only giving some bounds for random values (e.g. $q>x$) and nothing else.


In SSL and TLS, why is there a separate Change Cipher Spec Protocol rather than including a change_cipher_spec message in the Handshake Protocol?

TL;DR
It could be in the handshake, but separating the two makes it easier to enforce the desired behavior in the protocol.
Long Answer
The same question has already been asked at Security.SE.
For your convenience, this community wiki answer provides the related, accepted answer which was provided by Thomas Pornin
:

SSL uses messages which are encoded over records. Encryption is done on a per record basis. However, several messages of the same type (e.g. handshake messages) can be crammed together in the same record. Since the Change Cipher Spec message modifies encryption settings, a new record should begin immediately afterwards, so that the new settings are immediately applied (in particular, it is crucial for security that the Finished message uses the new encryption and MAC).
Using a specific record type for Change Cipher Spec is a way to enforce this property. An SSL/TLS implementation cannot help but begin a new record for the Finished message, since it uses a record type distinct from that of the Change Cipher Spec message. Such a specific record type could be avoided if all SSL/TLS implementations were disciplined enough to begin a new record where they need, and also to verify that the peer also began a new record. It is safer and more robust to make it unavoidable through the record type.


Your computations are correct.

For each valid $x$ coordinate there are 2 valid $y$ coordinate, $+y$ and $-y$, as you correctly said.

But note that numbers in a field $\mathbb{F}_p$ are usually written $\mod p$, which means they lie in the interval $[0,p-1]$, so without the "-" sign.

So, when you write the $y$ coordinate of your $-10G$, which you call $10*G (Inverse)$ but obviously $10*(-G)=-10*G$ so it's equivalent, you write it as:
-62070622898698443831883535403436258712770888294397026493185421712108624767191
but this can be written as a field element as p - 62070622898698443831883535403436258712770888294397026493185421712108624767191 with $p$ being the prime defining the field.
This results into 53721466338617751591687449605251649140499096371243537546272162295800209904472 .

Plugging the coordinates into the curve's equation is the correct way to verify that points are on the curve, and yours are on the curve.

For example: your $2G-10G$ and $8G$ share the same $x$ coordinate, in fact, $2G-10G=-8G$ so they are opposite points. You can get the value of the $y$ if you subtract one's value from $p$. E.g.

p - 41749993296225487051377864631615517161996906063147759678534462689479575333124
= 74042095941090708372193120377072390691273078602492804360923121318429259338539


Clarification of the terms "brute force" and "guess"

The difference in that answer is that brute force refers to an exhaustive guessing attack (having guaranteed success but requiring exponential time) whereas guessing (a polynomial number of) random values refers to exactly what it says (requiring polynomial time but having only a certain chance of success).


AES-CBC Padding: Why always attach 16x 0x10 pad?

You are talking about the PKCS#7 padding. There is a simple reason;  assume that when the last block is full and you don't apply the padding before encryption and then send the message.

When decrypting, the receiver needs to see a padding pattern to remove the padding. What if the last byte is 01 of the message? is it padding or the message itself? Similarly with low probability same if the last bytes are 0202, and so on.

Instead of this, padding with 10 for an additional extra plaintext block solves the problem.

There are no reasons to perform this particular kind of padding if the plaintext size is known in advance. It may also not be required if the size of the plaintext can be determined by other means. For instance, ASCII encoded text will generally not contain a byte set to zero, so zero-byte padding may be used if the text is not a multiple of the block size. PKCS#7 padding can however always be removed deterministically, independently of the contents of the message.

Many modes, especially streaming modes such as the popular CTR (counter) mode and derivatives - such as the authenticated GCM mode - do not require padding at all;  they operate on plaintext bytes rather than plaintext blocks.


Idiomatic description for an adversary in possesion of a quantum computer?

I think what you are looking for is an adversary that

has access to a quantum computer, and
is efficient (i.e., runs in polynomial time -> independent of the property it tries to attack).

In this case, the common way to model the adversary is just as a polynomial time quantum algorithm. Note, it depends on the security model for the property that the adversary tries to attack (e.g., collision resistance, or EU-CMA) if it gets quantum access to a primitive or not, not on the adversary model. Schemes which achieve security in terms of traditional security definitions (i.e., with no quantum access to secretly keyed resources) against any polynomial time quantum algorithm are what we call post-quantum cryptography.

As in the traditional / classical setting, the question if a certain problem like the MQ-problem still is hard when considering such polynomial time quantum algorithms boils down to an assumption again: We do not have a proof that there exists no polynomial time quantum algorithm that solves MQ / SVP / [choose your favourite PQ problem] with noticeable success probability. However, we got reason to believe that no such algorithm exists.


What is SHA-512's input space, taking into account variable message size?

There is one zero-length message, two 1 bit long messages, four 2 bit long messages, eight 3 bit long messages, and so on. Since these messages are distinct, you can simply use the formula:

$$1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n-1$$

Note that the maximum message length is the same as the maximum value of a 128-bit integer, ie. $2^{128} - 1$, not $2^{128}$. That makes $n-1 = 2^{128} - 1$, so $n = 2^{128}$. That makes the total number of distinct inputs

$$2^{(2^{128}-1)} - 1 $$


Why do the majority of SSL cipher suite used CBC?

Historically, CBC was for long the dominant block cipher mode, but in recent years there's been a slow but firm move away from it, based on two trends:

The move toward authenticated encryption as the "go-to" ciphers for practical applications;
A reevaluation of the merits of CTR-based modes over CBC, driven by a variety of factors like:

The proliferation of attacks against CBC-based ciphersuites;
The simplicity and performance of CTR.

So you see a lot of CBC because it was the king for a long time, and it's only going away slowly.  This blog entry by Cloudfare has graphs of the SSL cipher suites they're seeing and shows AES-GCM gradually gaining over AES-CBC.

Two references I've found useful:

Phillip Rogaway, "Evaluation of Some Blockcipher
Modes of Operation"
Chris J. Mitchell, "Error Oracle Attacks on CBC Mode:
Is There a Future for CBC Mode Encryption?"


Can FFT be useful in encryption of dicom images?

I had a quick look and the images are already encoded with standard image enncoding algorithms, which means DCT and other appropriate transforms have already been used, e.g., as part of jpeg, tiff, mpeg,whatever.

I see no utility to applying an FFT on top of all this effort, neither from a security point of view.


You can do this: essentially, if the initial key is uniform random and you use it for no other purpose, you can safely treat keys derived from it by distinct labels as independent uniform random from one another.  The only danger is if you might accidentally use the same sequence of labels for two different purposes, which would be catastrophic.  So make sure that each sequence of labels uniquely identifies the role that a key might be used for.  (Formally, a KDF is a PRF, so if the key is uniform random, the output is hard to distinguish from uniform random.)

But what are you going to use mc for?  Most authenticated ciphers, like AES-GCM, like AES-OCB, like NaCl crypto_secretbox_xsalsa20poly1305, etc., are designed to handle more than one message under a single key.  Except for ‘SIV’ schemes which specifically don't conceal repeated messages, these all require some additional input to distinguish them—a random initialization vector, or a unique nonce.  And if you aren't repeating message counters, a message counter makes an excellent nonce.

So while there's no problem with this as long as the labels uniquely identify key roles, you shouldn't need to do it—just use a standard authenticated cipher with the message counter as a nonce!


In CBC mode the decryption equation is $P_i = D_k(C_i) \oplus C_{i-1}$. If you received a corrupted $C_i$, $P_i$ and $P_{i+1}$ will be decrypted wrong, but $P_{i+2}$ no longer depends on $C_i$ and will be correct.


When you have a RSA key pair, it means that you know the private key (otherwise this is not "your" key pair). The private key format, normally, contains the two factors $p$ and $q$ (at least so it goes with PKCS#1). Even if all you have are the modulus $n$, the public exponent $e$ and the private exponent $d$, the factorization of $n$ can still be worked out from $e$ and $d$ (see this answer for a detailed description). The bottom-line is that if two people "share the same modulus" then they also both know the private keys of each other. In effect, there is only one actual key pair and they both know it.

The "shared modulus" situation is thus mostly irrelevant.

A second, most important point is that what you described ($c = m^e \pmod n$) is not RSA. It is often, confusingly, called "textbook RSA"; in the same way, a car engine, resting on the floor, could be called a "textbook Ferrari". RSA, as an asymmetric encryption algorithm, is a combination of several operations; the modular exponentiation is the most CPU-intensive of them, but not the only one, and the other operations are very important for security. In the case of PKCS#1, what enters the exponentiation is the padded message; the padding includes random bytes.

Even if you imagine a setup where the same message $m$ will be encrypted twice, once with $(n,e)$ and once with $(n,e')$ (same modulus, but distinct exponents), what will be really exponentiated will be, in the first case, a padded value $x$ that includes $m$ and some randomness, and, in the second case, another padded value $x'$ that includes $m$ and some other, distinct randomness. This would avoid the reconstruction of $m$ by an attacker observing both encrypted messages.


Questions about indexing a hash output to compose a final key

The speaker says that to use a byte from the user key as a subscript of an array allows side channel attacks.

Using secret data (be it the user key, the actual secret key or internal key or secret-dependent data of the crypto routine) can, depending on what you're doing and what sort of access the attacker has to your machine while you're working with the key.

  My question is what if to use this during a key crunching stage

  FinalKey += HashOut[currentKeyByte mod KeySize]

It depends on what currentKeyByte is (your pseudocode doesn't specify it).

If it's an index that iterates between 0 and WantedSize in a predictable fashion, then that's not an issue.  The attacker could potentially deduce information of what currentKeyByte is; on the other hand, if he knows that this is iteration 5, he already knows that currentKeyByte is 4, and so any further information he gets from the side channel doesn't tell him anything he doesn't already know.  Now, if that's the case, then this code would wrap around if KeySize < WantedSize; that's might not be what you want to do, but that's an unrelated issue.

On the other hand, if currentKeyByte is, in fact, a byte from the user's password, well, yes, that can be an issue (if the attacker can plausibly run a program on the same computer while the above code is running); if I were you, I'd rethink this, and rework this code.


what kind of custom header add to encrypted file to identify my encryption,consider safe and reliable.like pseudo format extension or file size

As indicated, the header format of your proprietary encryption is entirely up to you. Still, as I see this forgotten or done imperfectly a lot of times, I'll give some general hints in the right direction.

First of all, complexity is the enemy of security. If you make your header overly complex you may get into trouble. It could be possible to generate invalid packets, buffer overruns because of incorrect length fields or simply combination that do not make sense.

Furthermore you must be aware that attackers may be able to mess with your header format. This is mainly a problem for encryption formats that are or can be used for transport security. For transport security you should take care of man-in-the-middle attacks. So if an attacker can downgrade your security level through the header format then that's obviously a bad thing. You don't want to end up with all the configuration options for, e.g. IPSec. It makes no sense to allow (and code, and test!) AES-256 with MD5 configured together.

If you have lots of configuration options then those are likely to have a big influence on security if they haven't been established beforehand. So you must make sure you check your header format in advance. It's highly recommended to let your header format be included in any authentication tag calculation (MAC), and to make sure that that MAC verification itself isn't an issue. The simplest attack is simply to remove the MAC authentication tag entirely if your protocol supports it. This sort of attack actually happened on protocols like WS-Security (web services) due to broken implementations of both Glasfish and Apache/Tomcat where the signature was simply stripped off and the server accepted those messages without issue.

Probably the simplest header is a single identifier defining the version of the protocol. That version then defines a well defined suite of algorithms with parameters that make sense. So for instance byte version 01 would indicate that AES-GCM is used with a security level of 128 bits. The security level of 128 bits is then maintained for all other algorithms as well (e.g. key derivation with 256 bit hashes and RSA with 4K bit keys.

It may be useful to define an additional 8 byte constant value so you can identify the file type by looking at the content instead of the file extension (if applicable, e.g. for in place file encryption).

So there you are:

apply the KISS principle, don't allow overly flexible configuration;
make sure you are protected against attacks on the header and that buffer overruns are not possible (or at least warned against);
verify the validity of the header upon receival, checking as much as possible, and at least an authentication tag;
include a constant value for file identification when applicable.


What are KDF parameters in OpenSSL command-line utility for `enc`?

OpenSSL uses EVP_BytesToKey, an algorithm proprietary to OpenSSL, with a salt and an iteration count set to 1. The algorithm is secure; the iteration count of 1 of course is not secure (for passwords with an average strength). Implementations for other languages/runtimes can be found by searching for it by name.

This page (on nabble.com) explains a bit about accessing PBKDF2 from the command line. It also shows that OpenSSL CLI isn't always taken that seriously; OpenSSL is mainly a cryptographic library that can also be used from the command line.

It is possible to find code to include the iteration count in the CLI in the answers to this question on the security site (not reviewed by me). That code is however specific to private keys encrypted using the PKCS#8 standard.

It could well be that PGP is more suited for end-to-end password encryption (I haven't reviewed it for a while). It was certainly more specifically created for it.


What are the details of the DES weakness of reusing the same IV in CBC mode with the same key?

The initialization vector is a property of the mode of operation (aka "chaining mode"), not of the block cipher itself. A block cipher does only one thing, which is mapping blocks (block size depends on the cipher, 64-bit for DES, 128-bit for AES) unto other blocks. The chaining mode is what says how input data should be transformed into block values, and how the corresponding encrypted blocks should be combined.

The simplest chaining mode is ECB, in which data is split into blocks in the natural way. The main problem is that for a given key, the block cipher will always transform the same input block value into the same output block value (the algorithm is deterministic), which means that with ECB, the encrypted message will show identical block values where the input blocks were identical. The Wikipedia page linked to above has a nice picture which illustrates what's wrong when applying ECB to a picture. In a general way, this is because "real-life" data has redundancy.

CBC corrects the problem by "randomizing" the input blocks by XORing each input block with the previous encrypted block: encrypted blocks have a "random look" (if the block cipher is any good) so this makes the occurrence of two identical blocks improbable. The IV is just the "previous encrypted block" for the first data block.

CBC is secure as long as the P xor C values, where P is a plaintext block and C the previous encrypted block (or the IV), do not collide more often (or less often) than randomly chosen value would. Since real-life input data has structure, this implies that this "random distribution" must come from the encrypted blocks. A good block cipher will ensure that, except for the IV which is not an encrypted block; so the IV must be randomly chosen. At the extreme case, if the IV is always the same for a given key, then two plaintext messages which begin with the same bytes will yield encrypted messages beginning with the same sequence of block values, and the attacker will see it. More generally speaking, if the IVs have some structure in their choice (e.g. a counter), then that structure could interact with that of the plaintext messages, and again yield collisions which reveal information on the encrypted messages. Conversely, if for a given key you encrypt only a single message, then you can use a conventional IV (e.g. an all-zero IV), because trouble begins when considering two messages encrypted with the same key.

All of the above equally applies to DES and AES. However, the 128-bit blocks of AES make it a bit less vulnerable to sloppy IV selection, because real-life data tends to show less redundancy at the 128-bit level than it does at the 64-bit level. This is still a weakness, and you shall use properly generated random IV for AES too.

Some recent mode of operation (e.g. EAX) have less stringent requirements on IV selection: EAX only needs unique IV values, but does not require random selection (a counter, incremented for each message, is fine with EAX).


Bandwidth and block size for Paillier cryptosystem

Let $c$ denote a ciphertext and let $m$ denote a plaintext.
To my best knowledge, researchers in cryptography employ "bandwidth" as different meanings, say, ciphertext expansion ($|c|/|m|$) or a number of bits of plaintexts contained in a ciphertext ($|m|$). @owlstead refers "overhead," which is $|c| - |m|$.
For example,

Joye and Libert (EUROCRYPT 2013, ePrint 2013/435) wrote that "the scheme is computationally efficient but somewhat wasteful in bandwidth as $k \cdot \log_2{N}$ bits are needed to encrypt a $k$-bit message." Here, the scheme is the Goldwasser-Micali scheme and it encrypts a bit into a ciphertext of length $\log_2{N}$ and "bandwidth" seems to be $|c|/|m|$.
Chevallier-Mames, Naccache, and Stern (SCN 2008, ePrint 2008/119) defined "bandwidth" as the number of bits contained in a ciphertext, that is, $|m|$.

I think you mean the latter, i.e., $|m|$ and "block size" seems to be $|c|$.

Let us calculate $|m|/|c|$.

Paillier: The plaintext space is $\mathbb{Z}_n$ and the ciphertext space is $\mathbb{Z}_{n^2}$. Hence, the ratio of bandwidth/blocksize is $1/2$.
DJ with $s\geq 1$: The plaintext space is $\mathbb{Z}_{n^{s}}$ and the ciphertext space is $\mathbb{Z}_{n^{s+1}}$. Hence, the ratio is $s/(s+1)$.
ElGamal: The plaintext space is $\mathbb{G}$ and the ciphertext space is $\mathbb{G}^2$. Hence the ratio is $1/2$.


Does applying a "PushEntropy"-function increase security of a private key?

Why is a cryptographically secure random-number-generator (to generate the private key aka data-bytearray) not enough?

A Cryptographically Secure True Random Number Generator would be enough. This code uses a belt-and-suspenders approach. This is common in RNGs, in recognition of the fact that RNGs are traditionally one of the most brittle components in crypto implementations (see e.g.SmartFacts).
The intention appears to be: if UseAdditionalEntropy is at it's default of true, and additionalEntropy has been set with something unguessable or/and truly random by calling one of two forms of AddEntropy

Try to save the day if initially data contains something guessable, by mixing the two (in the first loop)
Make it hard to "walk back" from the result, by applying a non-reversible transformation. When data is 32-byte and entropyIndex starts at zero, this transformation is $\mathtt{data}\mapsto\operatorname{SHA-256}(\mathtt{data})\oplus\mathtt{data}$. Given the output, the only hope to find the input is by enumeration of likely input values¹.

Step 1 can conceivably backfire, e.g. if data passed is the SHA-256 hash of what was previously passed to AddEntropy.
Step 2 slightly reduces the entropy (by less than 1 bit if data was full-entropy, see this; and negligibly so if data was less than full-entropy), but in the context that's fine.

Does this function increase security in any kind?

It does, if Random.GetBytes of the calling context has a flaw, and AddEntropy was used and passed something secret (including something random and independent of what Random.GetBytes outputs; or just a secret constant generated at random at time of installation). As long as PushEntropy,  additionalEntropy and entropyIndex remain private (thus not accidentally callable), this precaution is unlikely to accidentally backfire.

¹ If we changed += to ^= in the final mixing step of the round function of SHA-256, this transformation would be reversible. And it would be dangerously close to reversible if we changed ^= to -= in the code shown.


Enforcing Randomness in Malicious Setting

The way that this is used is that each party proves in zero-knowledge during the protocol that it sent the correct message based on its committed input, the randomness defined by the committed $s_i$ value and the clear $s'_i$ value, and the series of incoming messages. This proof forces the party to not use any other randomness.

However, in order for this to work formally, you can't use plain commitments. Rather, the commitment must be something that we call ``extractable'' by a simulator.

In any case, you should read more about this as the GMW compiler. You can read about it in the 2nd volume of Goldreich's textbook.


Has there been any cryptanalysis of AES under a non-uniformly distributed key?

As far as I know, NO, there has not been any cryptanalysis of AES under a non-uniformly distributed key. That holds even if we let the adversary decide what the non-uniform distribution is. Of course we should adjust the expected difficulty of attack according to the entropy remaining per the distribution; but typically, hashing a low-entropy password looses negligibly few entropy.

Further, the scenario that motivates the question has a low-entropy key hashed then the result (known as a derived key) used as the AES key. Indeed that leads to a non-uniform distribution of the AES keys, but that distribution is unrelated to the structure of AES, thus it is highly implausible that an attack on AES can take advantage of that non-uniform distribution.

The closest thing to what's asked is related-key attacks, but (as stated in the question) such attacks do not apply in the scenario that motivates the question. See in particular Alex Biryukov and Dmitry Khovratovich's Related-Key Cryptanalysis of the Full AES-192 and AES-256 (in proceedings of AsiaCrypt 2009). Quoting their adversarial model:

  The related-key attack model is a class of cryptanalytic attacks in which the
  attacker knows or chooses a relation between several keys and is given access to
  encryption/decryption functions with all these keys. The goal of the attacker is
  to find the actual secret keys. The relation between the keys can be an arbitrary
  bijective function R (or even a family of such functions) chosen in advance by
  the attacker.

In the scenario that motivates the question, the best general attack is typically enumerating the low-entropy key (approximately from most likely to least likely), applying the key derivation algorithm (or hash) for each, then testing if this is the right AES key based on known or low-entropy plaintext. That is slowed, to a large (but often insufficient) degree, by using a purposely slow key derivation algorithm, such as scrypt, or the lesser bcrypt or PBKDF2.


Is there such a thing as a hash function with a fixed size input?

Such a category of functions is not generally used as is, but compression functions, which are close to what you describe, are (as you describe) used to build (variable length) hash functions. For example, Merkle–Damgård hashes like SHA-2 have a compression function that takes an IV (or previous block output) and a fixed size data block to generate a smaller fixed-size output.

If you want to use a compression function as a cipher you can. If you use the key as the data block input, you get a block cipher that in the case of SHA-1 and SHA-256 is called SHACAL-1 and SHACAL-2. You can then construct a stream cipher from these using CTR mode.

However, Merkle Damgård does not require a block cipher, and Damgård suggested several number theoretical problems for the compression function in A Design Principle for Hash Functions.

  Relatedly, why is it that block ciphers seem to be the low-level building block of choice for hashes and stream ciphers?

Many hashes and stream ciphers are built from something else, like Salsa20 or SHA-3.

However, it is true that block ciphers have been used a lot. Partially because everyone was looking for ways to use DES (and later AES) which was standardized by NIST. Partially because the design of block ciphers is well understood.


Recommended Shake256 digest size for KMAC based HKDF

HKDF already has expansion on top of the MAC that it is based on. What would be the point of using a XOF for that? Why not use the XOF directly or define a different KDF? Because having two different methods for expanding the output seems troublesome to me.

If you're going to use HKDF then use one of the normal SHA-3 / HMAC functions with it. Sure, that's less than optimal, but commonly that's not a huge issue for deriving a limited amount of key material anyway.

Any form of HKDF that redefines the PRF used to derive the key material will not be compatible with anything out there. That's true regardless of the XOF and KMAC standardization.


Collision resistant hash functions with prime domain

Suppose you have a PPT algorithm $M(1^n;r)$ that given the length of your target prime and the randomness $r\in\{0,1\}^{\rho(n)}$ finds a prime of length $n$. Suppose further $M$ is secure in the sense that if you feed it a properly random input $r$ it will output an unpredictable, random prime suitable for use in say RSA. Most cryptographic libraries have an implementation of this.

Suppose further you have a PRG $G:\{0,1\}^l\to\{0,1\}^{p(l)}$ that given a properly random string as input outputs a (much) longer random-looking string as output. This is e.g. realized by using something like AES-CTR with the input being the key and using a fixed nonce.

Then take any hash function that can reasonably be modelled as a random oracle $O:\{0,1\}^*\to\{0,1\}^l$, e.g. SHA3. The defining feature of a random oracle is that you get fresh randomly drawn values as output for every fresh input value.

Now construct your hash as follows: $P_n(x)=M(1^n;G(O(x)))$. Assuming you can securely generate RSA keys this will also be secure (as long as $x$ is unnpredictable).


Determine the Key given ciphertexts and plaintexts?

There is a straightforward brute force method. For example, take the lowest $8$ bits of everything and check for valid values of $K_1$ and $K_2$, mod $2^8$. You will need about $2^{16}$ checks to get the lower $8$ bits of $K_1$ and $K_2$. Proceed then to values mod $2^{16}$, as you know the lower $8$ bits of $K_1$ and $K_2$, only bits $8\dots15$ of these must be checked, the effort is $2^{16}$ again. Proceed until you get $K_1$ and $K_2$ in full.

Better, do the same but instead of $8$ bit increments do $1$ bit increments. So, brute force for values mod 2, mod $4$ ... mod $2^n$. You will need to check $4$ different values each step (one bit from $K_1$ and another from $K_2$), and do this $n$ times. Therefore, the cost of finding $K_1$ and $K_2$ is $4n$, meaning this isn't just polynomial in respect of the number of bits: it's linear.

However, must be noted that if $P_1 \equiv P_2 \pmod{2^i}$, then the first $i$ bits of $K_1$ and $K_2$ are indeterminable, so more plaintext/ciphertext pairs will be needed until finding some pair where $P_1 \not\equiv P_2 \pmod{2}$, to retrieve then the whole keys.

Update: Probably there are (for a given $n$) $2$ pairs $(K_1,K_2)$ compatible with an adequate $(P_1,P_2)$ pair, so this method should check incrementally $2$ pairs of keys.


How can I use eulers totient and the chinese remainder theorem for modular exponentiation?

To step through it simply:

Step 1: we first compute compute $M^e \bmod p$ (where $p$ is one of the factors of the modulus.  By Fermat's Little Theorem, this is the same as $M^{e \mod p-1} \bmod p$ (and that's where the real savings are), and so in your example ($p=5$), we get:

$M^e \bmod p = 27^{37 \bmod 4} \bmod 5 = 2^1 \bmod 5 = 2$

Step 2: we do the same for the other prime $q$:

$M^e \bmod q = 27^{37 \bmod 10} \bmod 11 = 5^7 \bmod 11 = 3$

Step 3: using the Chinese Remainder theorem, we reconstruct $M^e \bmod pq$ from $M^e \bmod p$ and $M^e \bmod q$:

$C_p = M^e \bmod p = 2$
$C_q = M^e \bmod q = 3$
$M^e \bmod pq = C_q + q \cdot (q^{-1} (C_p - C_q) \bmod p) = 3 + 11 \cdot (1 \cdot (2-3) \bmod 5) = 3 + 11 \cdot 4 = 47$


Comparing Ciphertext when there is a change in source plaintext p1

i don't think that there is a way to check the changes on block cipher if you are using random IV here, since the IV will go to Enc first, then the output would be totally different than before,

if you are using the same IV, then try to figure out the the block length for the block you are using, if it is 16 bytes, then change the first 16 bytes will result first 16 bytes of ciphertext to be different. Since before output the ciphertext, it is just a one-time pad.

hope it helps.


Algorithm for n-of-m keys with partial results

The way I see it, you have a few options. The right one will depend on the details of the application, which are sparse in the question.

Use a stream cipher (or stream-like mode). Each party has a separate key and encrypts/decrypts with their individual key. With this you only get n-out-of-n, not m-out-of-n where $m<n$.
Use MPC. You can evaluate the AES encryption/decryption circuit via MPC. It is fairly fast based on the numbers I've seen recently. Unfortunately, I don't think there is any good publicly released software out there to do this. Under this paradigm, each party would hold a share of the secret key and they would cooperatively work to do the encryption/decryption. The work I cited requires all n parties, but if the secret were originally shared with an m-out-of-n sharing scheme (like Shamir), you could convert that to an additive sharing (see this paper for a method of doing the conversion).

Some things to think about:

Who generates the key initially?
Who is suppose to receive the output of the operations?


How were semagrams encrypted in the pre-digital era?

There was a telegraphic code that mapped the comparatively frequently used 10000 words (that's very much more than for common daily use, e.g. newspapers) of Chinese to [0,9999]. There was once also a patented mechanical device that effected a poly-alphabetical substitution of [0,9] with a set of disks containing certain scrambled alphabet of [0,9], which the user selected 4 of them (aggreed upon with the partner) to encrypt the 4 digits from the telegraphic code. Since frequency analysis of the digits barely helps, the result from that device isn't bad IMHO even today (anyway assuming one has a somewhat larger set of disks than at that time.)


is H1 (H2(x)) hash function collision-resistant

Hint: what do you know about H2? What happens if H2 is not collision-resistant, i.e. you know two different messages that result in the same hash with H2?


can we know the sign of a ciphertext (homomorphic)

Pallier encryption works over the finite ring modulo $n^2$.  The distinction between positive and negative numbers don't exist there (or in any finite ring or field), so there isn't really a sign that works like the sign of integers.
Of course you can use signs in the notation, e.g. $-1$. But that is just the same element as $n^2-1$. Both represent the same residue class modulo $n^2$.


Recovery public key from secp256k1 signature and message

You can usually derive two public keys. However, sometimes (very rarely), you can get four public keys.

With some details:

There is an elliptic curve. In Bitcoin, this is secp256k1. Each curve point has two coordinates $(X,Y)$; the coordinates are integers modulo a given prime integer $p$ (precisely, $p = 2^{256} - 4294968273$).
The curve order (number of points on the curve) is an integer $n$, which happens to be prime, and to be very slightly lower than $p$.
Private key is $x$, a non-zero integer modulo $n$. Public key is $Q = xG$, i.e. multiplication of a conventional generator point $G$ by the private key $x$.
To sign a message $m$, things go the following way:

A random (non-zero) integer $k$ modulo $n$ is generated.
The point $kG$ is computed, and its $X$ coordinate (an integer modulo $p$, hence in the $0$ to $p-1$ range) is reduced modulo $n$, thus yielding a value between $0$ and $n-1$. The result is called $r$.
The value $s = (h(m)+xr)/k \bmod n$ is computed. $h(m)$ is the hash of the message to sign, with some hash function that yields a sequence of bytes which is interpreted as an integer.
The signature is $(r,s)$.

Now suppose that you have a message $m$ and a signature $(r,s)$, and you want to recompute the corresponding public key $Q$. If you somehow obtain the point $P = kG$, then you can compute:
$$ Q = r^{-1} (sP - h(m)G) $$

Thus, if you can get the point $P$, then you can have the public key $Q$. However, you do not have the point $P$. Instead, you have $r$, the $X$ coordinate of the point $P$, reduced modulo $n$.

Since $n$ is very slightly lower than $p$, there can be two values $X$ that match $r$. In general there will be only one, but if $r < p-n$, then there will be two.

For each possible coordinate $X$, there can be two corresponding points. Indeed, points on the curve follow the curve equation:
$$ Y^2 = X^3+7 $$
Thus, if $(X,Y)$ is a point on the curve, then $(X,-Y)$ is also a point on the curve, and has the same coordinate $X$.

Putting all together: from the value $r$ (in the signature), you can have up to two candidates for the $X$ coordinate of $P$, and from each such candidate, you can have up to two matching points. In total, there can be up to four curve points $P$ that match the $r$ value from the signature. For each of them, you can compute the corresponding public key $Q$. But note that the case of two possible $X$ coordinates for a single $r$ is very rare; indeed, this will happen randomly with probably about $2^{-128}$, i.e. never in practice (although you might be able to force it with specially crafted data). Thus, you can normally expect to recover two public keys, but (at least theoretically) you might get four.