Quantum key distribution and the one-time pad

Well, to understand why QKD is often associated with OTP, we need to review what Quantum crypto is, and why it claims to be secure.

Overall, we know of three implementable paradigms for cryptographical security:

Informational: the attacker does not have enough information to determine the plaintext from the ciphertext
Computational complexity: the process of deriving the plaintext from the ciphertext involves solving a mathematical problem that is just too difficult for the attacker.
Quantuum: the laws of physics forbids the attacker from learning the data needed to rederive the plaintext without disturbing the system detectably.

For example, OTP uses the "Informational" paradigm, while AES uses the "Computational complexity" paradigm.

Most of the cryptographical systems in use today rely on the "Computational complexity" paradigm.  It appears to work well in practice; however, there is one troubling detail; there's an assumption that the underlying problem is too difficult for any attacker, and the only evidence we have of that is "lots of fairly bright people tried to solve the problem, and were unable to".  Quantuum crypto attempts to get around this assumption by instead relying on the laws of physics; those laws have been fairly heavily tested, and it would appear to be a solider foundation than the assumption that a specific mathematical problem is difficult.

However, if you pair QKD with a symmetric cipher, well, you're no longer relying on something that is stronger than a computational complexity assumption; if the attacker can solve the mathematical problem associated with the symmetric cipher, he has broken the security.  Indeed, in some sense, pairing QKD with a symmetric cipher gives a solution that is the worst of both worlds; you get the implementation difficulties (not to mention the potential side channel attacks) that we see with Quantuum Crypto, while giving a system that's guaranteed to be no stronger than conventional crypto.

In contrast, if you don't use a symmetric cipher at all, and instead you exclusive-or the distributed bits with the plaintext bits (analogous to what an OTP does), you do get a system that is potentially stronger than conventional crypto.  Now, whether it is stronger in practice (because of the side channel attacks that have been found on QC implementations), and whether that increased strength is actually worth the considerably larger implementation cost, well, that's a different question.


encryption of digest of unkeyed hash function is susceptible to forgery?

An attacker can trivial forge the MAC of any message, given one valid MAC of a known message, in either CBC mode or CTR mode.

Let us assume that the attacker knows a message $m$ and its MAC $E(k, H(m)) = IV, E(k, IV, H(m))$; he has a message $m'$ he wants to form the message to.  He computes $\delta = H(m) \oplus H(m')$, then:

For CTR mode, he computes $IV, E(k, IV, H(m)) \oplus \delta$, when this is decrypted, this results in $H(m) \oplus \delta = H(m')$
For CBC mode, we computes $IV \oplus \delta, E(k, IV, H(m))$; because of how CBC mode works, the first block (128 bits for AES) are the first 128 bits of $H(m) \oplus \delta = H(m')$; because $H$ generates only 128 bits, that's the entire message (nit: depending on CBC mode is padded, that may also be an issue; I'm assuming no padding).

Also, there is no such thing as a "collision resistant hash function with 128 bits output"; assuming that the hash function takes an arbitrary bitstring, we can find a collision in $O(2^{64})$ time, and that's generally considered feasible.


Why do you need padding block at the end of Merkle damgard if the input is multiple of block length?

Let's say we have a message $m$ whose length is not a multiple of the block length, and that our hashing scheme pads it to a multiple of the block length by appending the padding $p_m$ to it.  That is to say, $$\textsf{Pad}(m) = m \,\|\, p_m,$$ where the length of $m \,\|\, p_m$ is a multiple of the block size.

Now, if messages whose length was a multiple of the block size were not padded at all, consider what would happen if one deliberately tried to hash the modified message $m' = m \,\|\, p_m$.  Since the length of $m'$, by construction, is a multiple of the block size, we'd have $$\textsf{Pad}(m') = m \,\|\, p_m = \textsf{Pad}(m).$$

And since the final hash value is calculated from the padded message, this would mean that $m$ and $m'$ would have the same hash value.


Can RSA signing be implemented on top of RSA encryption/decryption?

Yes, you can, but you would need access to raw or textbook RSA encryption and you would have to implement the PKCS#1 v1.5 or PSS padding primitives yourself. Beware that PKCS#1 v1.5 compatible padding is different for encryption signature generation.

If you only have PKCS#1 v1.5 encryption or OAEP encryption available then the encryption routine will already pad your data, and in that case you cannot use the encryption API to sign.

The padding methods in common use are found in RFC 3447 which basically is a copy of RSA/EMC's PKCS#1 v2.1 specification.


Proving that RSA encryption function with non-square free modulus is not a permutation

While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.

It's rather straightforward to demonstrate (assuming $e>1$; with $e=1$, it is a permutation, but not a very interesting one).
A value $N$ is nonsquarefree if there is a value $p>1, q$ such that $N = p^2q$ (note that $q$ may have $p$ as a factor).  If so, then consider the encryption of the two values $0$ and $pq$.  In the two cases, we have:
$$0^e \equiv 0 \pmod N$$
$$(pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N$$
for $x = e-2$ and $y = e-1$.  Now, both $x, y \ge 0$, and so $p^{2+x}q^{1+y}$ is a multiple of $p^2q$, and so this latter is equivalent to $0 \bmod N$
Since these two distinct plaintexts map to the same ciphertext 0, the mapping cannot be bijective.


Why does the verifier have to send a challenge in Shnorr protocol?

my question is why the verifier sends a challenge, would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w \cdot y$  ?

That is, why doesn't the prover just send $t$ and $y$?  Well, anyone can pick a random $t$ and compute $y = g^t \cdot (g^w)^{-1}$.  Because $g^w$ is public, this can be computed by anyone, and so wouldn't serve as a proof of knowledge.

And, it is easy to find a solution to $g^t=(g^w)^x \cdot y$ (without knowing $w$), if you know the $x$ value before selecting the $y$ (and you suggested a constant $x=1$, hence the prover knows it up-front).  However, if you can find a solution for $g^t=(g^w)^x \cdot y$ for two different $x$'s, that's different; it's easy to show that with solutions to two different $x$'s (and the same $y$), we can recover $w$ (and hence someone who can do that must know $w$).  On the other hand, we can't just give out two solutions (as that means the verifier would then be able to deduce $x$).

So, what we do is get the prover to give a solution for an $x$ he cannot predict in advance; either he got extremely lucky (and he guessed the correct $x$ value when he generated $y$), or he does in fact know multiple solutions (and hence knows $w$).


Basic questions on how asymmetric keys "interact"

To use a key and lock analogy. With an asymmetric pair of keys (when used to encode) can either key be used to encode the message (close the lock) and only the "pair" be used to decode (open the lock)?

No, not in practice. Although some systems work kind-off like that, for instance raw (unpadded) RSA, others do not. Besides that, one key is supposed to be public so anybody could use that key to open the lock. Locks are used to emulate encryption, and encryption is used for confidentiality. If you use the private key to lock then anybody could open the lock. That's not a good way to achieve confidentiality.

The confusion mainly seems to arise from RSA where signature schemes were seen as encrypting a (padded) hash value. Nowadays the specification of secure RSA goes out of the way to make sure this confusion doesn't arise. More information here.

  Taking the key analogy further, is it a useful comparison to say that the first key of the pair changes the lock after it is used so that only the asymmetric key of the pair can open the lock?

Both keys in the key pair are asymmetric to each other. So there is not one asymmetric key, but two (or more). The analogy is already broken, it doesn't make sense to take it further.

  The description of keys as "public" and "private" is only a convention that relates to their use and not the order in which they are used i.e. can use 3.1 public then private (encoding for one intended recipient) or 3.2 private then public (digital signatures)?

Yes, that is right.


Why is this authenticated Diffie–Hellman key exchange insecure?

My guess is that when it is written approximately

Can we really have a non-replayable 2-msg protocol?
□ Remember (the question's protocol) insecurity

the author is thinking about an attacker capturing the first message of the exchange $(A, g^x, \operatorname{SIG}_a((g^x, B)))$ and using a replay of that to impersonate Alice.
There are two variants:

Declaring victory just because Bob thinks (and the logs of its machine show) that Alice connected again, when she did not.
Further, if Alice leaked the $x$ she used in the past, that allows the attacker to get the new shared secret by doing just as Alice normally does, and fully impersonate Alice.


relationship between equivalent ways of computing RSA private key

$D={k \phi(N)+1 \over E}$ is equivalent to $ED = k \phi(N) + 1$

$ED \equiv 1 \pmod {\phi(N)}$ means "there's some integer $k$ s.t. $ED = 1 + k \phi(N)$"

Hence, they're equivalent.

BTW: the actual necessary and sufficient condition on E, D actually is $ED \equiv 1 \pmod {\text{lcm}(P-1, Q-1)}$ (for RSA modulii that consists of two primes); the relation you're using is sufficient, but not necessary.


How can I evaluate the congruency of an AKS primality test?

This is never "evaluated" as such. The above equation must hold for the number to be prime for certain $a$, or else it's composite.

See the algorithm on Wikipedia to exactly see for which $a$ the equation is tested.


Number of preimages of hash function from bounded domain

I assume you mean behaves like a uniformly chosen function from the set of functions mapping $\{0,1\}^{n+k}$ to $\{0,1\}^n.$

Let $p_z$ be the probability that the random variable $Z=|H^{-1}(b)|=z,$ for $0\leq z\leq 2^{n+k}.$
Then $$p_0=(1-2^{-n})^{2^{n+k}}\approx \exp[-2^k]$$
which is the probability that a fixed $b$ is missed $2^{n+k}$ times. Of course $\mathbb{P}(|H^{-1}(b)|=z)$ is independent of $z$ and distributed binomially, i.e., $$\mathbb{P}(|H^{-1}(b)|=z)=\binom{2^{n+k}}{z}(1-2^{-n})^{2^{n+k}-z} (2^{-n})^{z}$$

With high probability, the distribution $p_z$ is concentrated around its expectation $Z=2^{k},$ for example via the Chernoff bound.


SVP=SIVP in ring lattice (ideal lattice)

Consider the ring $R = \mathbb{Z}[x]/(f(x))$ for $f(x)$ an irreducible monic polynomial of degree $n$.
Fix a basis $\{1,x,\dots,x^{n-1}\}$, and define the following transformation:
$$L(x^i) = x^{i+1}$$
Extend this transformation to all of $R$ via linearity.
Cayley-Hamilton theorem [1] states that the characteristic polynomial $p(t) = \det(L - tI)$ is such that:
$$p(L) = 0$$
One can explicitly compute the square matrix corresponding to $L$ (it is the companion matrix of $f(x)$), and it is known that:

The characteristic polynomial of $L$
The minimal polynomial of $L$
$f(x)$

Are all identical.
It follows that $f(L) = 0$, and this is the smallest polynomial $f(x)$ for which this holds, so among other things $\{1,x,\dots,x^{n-1}\}$ are linearly independent over $R$.

Now let $v(x)\in R$ be any vector (including a candidate "shortest vector").
We have that $\{v(x), xv(x), \dots, x^{n-1}v(x)\}$ are linearly independent over $R$.
This is because if there were some linear relation between them:
$$\sum_i a_iv(x)x^i = 0\implies v(x)\sum_i a_ix^i = 0\implies \sum_i a_i x^i = 0$$
Contradicting the linear independence.
As $\| x^i v(x)\|$ are all the same, we've exhibited a basis of vectors of the same norm.
So finding one short vector is enough to find all $n$ short vectors.

[1] Technically we need to make sure that Cayley-Hamiltonian holds over modules over general rings. Fortunately it is known to hold for commutative rings, so we're fine.


Since Bob already knows $K_{AB}$ he can run $D_{K_{AB}}(E_{K_{AB}}(E_{K_{AC}}(K)))$. Which will leave him with $E_{K_{AC}}(K)$. And to decrypt that any further (in order to get $K$) he would need either Alice or Charlie's help.


What's the difference between threshold signatures and multisignatures?

Threshold signatures do not enforce accountability meaning a t-out-of-n threshold signature does not tell the verifier which $t$ of the $n$ signers created the signature. Multisignatures enforce accountability as the verifier learns which t signers created the signature. There does not need to be a threshold for multi-signatures.

But n-out-of-n threshold signature should give same properties as an n-multisignature.

As an example, consider BLS signatures. You can have a 3-of-5 threshold signature without learning which 3 signers created it but if you had a multisignature from 3 signers, you need to know which 3 signers created the signature (so you add their public keys). In fact a threshold signature by any 3 signers will have the same value but a multi-signature will have different values depending on which 3 signers were involved. You could create a multi-sig from 2 signers as well.


How were the AES key and block length subsets of Rijndael selected?

Prompted by Paŭlo's comment, I took a look at the original requirements set out for the AES candidates.  A useful page for that turns out to be AES - The Early Years (1997-98) on the NIST web site (and surprisingly hard to find there; the internal links are broken and Google doesn't find it either).

The AES key lengths were specified in the original Request for Candidate Algorithm Nominations for the AES published in the Federal Register on September 12, 1997, in section 3, Minimum Acceptability Requirements (emphasis original):

  "The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits.  A submitted algorithm may support other key-block sizes and combinations, and such features will be taken into consideration during analysis and evaluation."

So where did those key/block size combinations come from?  In the earlier notice Announcing Development of a Federal Information Processing Standard For Advanced Encryption Standard, posted in the Federal Register on January 2, 1997, the "proposed draft minimum acceptability requirements and evaluation criteria" include:

  "A.3  AES shall be designed so that the key length may be increased as needed."

This proposed requirement received many comments, and was discussed in the AES workshop on April 15, 1997.  Bruce Schneier, in his notes on the workshop, writes:

  "Discussion followed. All the pre-lunch arguments were about block and key size. Block sizes of 64 bits and 80 bits were quickly eliminated, as was a 64-bit keysize. People wanted variable keysizes of some subset of 128, 192, 256, or even 512 bits, and block sizes of either 128 bits or 128 and 256 bits. There was no discussion of stream ciphers, or using block ciphers as hash functions."

Apparently, the three key sizes and one block size specified in the NIST minimum requirements, and later in the AES standard, were selected at least in part based on those discussions.

Ps. I've seen it claimed, e.g. by Thomas Pornin in this answer, that the three key lengths "exist mostly to satisfy some US military regulations which call for the existence of several distinct 'security levels'".  The notes and comments cited above strongly suggest to me that this probably wasn't the only reason for the decision to require multiple key lengths, although it could certainly have been one reason.  In any case, if anyone can actually point to the specific regulations that require these distinct security levels (assuming they're publicly available), I'd be interested in seeing them.


Permutation of keys that guarantees different hashes

I assume you're asking whether there exists a hash function $H: \{0,1\}^* \to \{0,1\}^\ell$, and a permutation $m: \{0,1\}^* \to \{0,1\}^*$, such that $$H(x) = H(y) \implies H(m(x)) \ne H(m(y))$$ for all $x \ne y$.

The answer, alas, is no — there is no such $H$ and $m$.

If there was, we could construct a collision-free hash function $H': \{0,1\}^* \to \{0,1\}^{2\ell}$ as $$H'(x) = H(x) \| H(m(x)).$$  But since the set $\{0,1\}^*$ is infinite, while $\{0,1\}^{2\ell}$ is finite, this is clearly impossible.

More generally, the same argument shows that no such $H$ and $m$ can exist if the input domain of $H$ has more than $n^2$ elements, where $n = 2^\ell$ is the number of possible outputs of $H$.


Use any DRBG (deterministic random bit generator) in the NIST FIPS (the NIST 800-90 publication series).  Except... don't use Dual EC DRBG, which has serious problems and is likely to be withdrawn.  Use any DRBG in that standard other than Dual EC DRBG.

Or, hash the seed with SHA256, then use AES256 in counter mode to generate output.

Either of those will work fine.

Don't use BBS.  It has major problems (search on this site for other examples).  There is no reason to use any of the number-theoretic PRGs in practice.


This follows essentially from the security of the one-time pad: if you have some arbitrary distribution $D$ over a group $G$, and the uniform distribution $U$ over the same group $G$.  If $D$ and $U$ are independent, then sampling $x\gets D$, $y\gets U$ and computing $z=x\cdot y$, the resulting $z$ is distributed uniformly over $G$.

So, in fact, $G'$ doesn't even have to be $G(x_1)\oplus G(x_2)$; something like $B(x_1)\oplus G(x_2)$ for some arbitrary stretching function $B$ which doesn't necessarily have to be a PRG would be also fine.


ECDSA, EdDSA and ed25519 relationship / compatibility

Ed25519 is a specific instance of the EdDSA family of signature schemes.  Ed25519 is specified in RFC 8032 and widely used.  The only other instance of EdDSA that anyone cares about is Ed448, which is slower, not widely used, and also specified in RFC 8032.  Keys and signatures in one instance of EdDSA are not meaningful in another instance of EdDSA: Ed25519 and Ed448 are different signature schemes.

The ECDSA family of signature schemes is not related to EdDSA, except in that the mathematics behind it also involves elliptic curves.  Any particular instance of ECDSA, such as ECDSA over the curve secp256k1 with SHA-256 (as Bitcoin uses), is incompatible with any other instance of it, such as ECDSA over the curve nistp521 with SHA-512.

On a practical level, what a user might need to know is that Ed25519 keys are not compatible in any meaningful sense with keys in any instance of ECDSA.  So, e.g., in the ssh protocol, an ssh-ed25519 key is not compatible with an ecdsa-sha2-nistp521 key, which is why they are marked with different types.  Similarly, an ssh-ed448 key, for Ed448, is incompatible, which is why it is also marked with a different type.

On a technical level, what a protocol designer should know is that the ECDSA family of signature schemes is an archaic slow design that encourages security-destroying implementation errors, while the EdDSA family of signature schemes is a modern design that avoids those errors.


how is the rsa $publickey(n ,e)$ transformed into a textfile allowing its public distribtution?

There are two concepts that are relevant for your question: Base64 encoding and ASN.1 DER encoding.

So, to deal with the most immediate concern, take n and e as the representation of the RSA values stored in a byte array.

Base 64

Given that cryptographic algorithms usually deal with purely binary data (keys, ciphertexts, random values), their representation can lead to communication issues. The most evident: you can't send the key as a string (e.g. via email) because it can be misinterpreted and even reformatted. What is just a random byte of a key could be an EOL character, and parsing can be jeopardized.

Base64 aims to solve all that family of issues by encoding the data using only 64 printable characters. I will not detail here the encoding rules, but, at a cost of roughly 30% of communication overhead, you get rid of encoding issues dependent on the platform. A base 64 string will have only letters, numbers and the symbols "+", "/" and "=".

ASN.1 DER

The Distinguished Encoded Rules define the encoding of certain data types with the format TLV: Type Length Value. Some of the types can be classical (BOOLEAN, INTEGER), some can be understandable (BIT STRING, OCTET STRING, UTF8String, UTCTIme), some are rather specific (OBJECT IDENTIFIER, SEQUENCE, SET) and some are constructions that build over existing data types to build upon.

Unless you're very interested in the details of how it works, I would suggest to avoid the details about the encoding of each data type and use a parser instead. The encoding rules are a bit dark and contribute little to nothing to the understanding of what's built on top. You can, however, Base64-decode the public key you posted and pass the result to a tool like dumpasn1 to see how nested the structure can get.

What you're seeing

Given all the background, I can finally reply to your question. The first key you got is a PEM encoding: a ASN.1 DER structure subsequently Base-64. I have seen the structure below as an equivalent and functional text representation of the same data, but I can't seem to find the right name for that encoding.

UPDATE: It seems I published an incomplete version of my answer. Particularly, I did not include the link to the RFC 3280, which contains the definition of the DER encoding of a RSA public key (page 15). Thanks to @dave_thompson_085 for bringing it up and the useful additional links:

RFC 3280 (page 15)
PEM
RFC 3447 (Appendix A)
Wikipedia ASN.1 entry
Wikipedia BER encoding entry


Reasons for Chinese SM2 Digital Signature Algorithm

The SM2 digital signature algorithm.  Fix a curve $E/k$ over a field $\mathbb F_p$.  Fix a standard base point $G$ of prime order $n$ on $E/\mathbb F_p$.  Fix a hash function $H\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$.

A public key is the encoding of a point $P \in E/\mathbb F_p$ together with an string $Z$ identifying a principal.
A signature on a message $m$ under the public key $P$ with identifier $Z$ is is a pair of integers $(r, s)$ in $[1, n - 1]$ such that $r + s \ne 0$ and $$r \equiv (H(Z \mathbin\| m) + x([s]G + [r + s]P)) \pmod n.$$
The signer knows the secret scalar $d$, the private key, such that $P = [d]G$.  To make a signature, the signer picks a scalar $k$ uniformly at random, and computes

\begin{align}
    r &\equiv (H(Z \mathbin\| m) + x([k]G)) \pmod n, \\
    s &\equiv (k - r d)/(1 + d) \pmod n,
  \end{align}

rejecting and starting over if $r \equiv 0$, $r + k \equiv 0$, or $s \equiv 0 \pmod n$.

This is a valid signature because

\begin{align}
    [s]G + [r + s]P
    &= [s]G + [(r + s) d]G \\
    &= [s + s d + r d] G \\
    &= [(1 + d) s + r d] G \\
    &= [(1 + d)(k - r d)/(1 + d) + r d]G \\
    &= [k - r d + r d]G \\
    &= [k]G.
  \end{align}

Why?  There has been relatively little analysis of the SM2 signature scheme that I can find in the anglophone cryptography literature beyond some side channel attacks.  The most salient aspect of it to my eyes is that it is just different from various other national pride digital signature schemes.

The SM2 signature scheme has a small advantage over ECDSA (US) and ECGDSA (Germany) for verifiers: the verifier need not compute any inverses modulo $n$.  Otherwise the signer's costs are similar to the others.  Security analysis of ECDSA is extraordinarily complicated and unsatisfying, in contrast to Schnorr; I expect the same is true of the others.

My guess about why SM2 was chosen is precisely to be different from all the others, for the sake of nationalism—they are all worse in performance and confidence than the much simpler inversion-free Schnorr-based EdDSA.


Public Key Cryptography: Diffie-Hellman Key Exchange

Alice didn't know that $16\equiv 3^{24}\mod 17$. The video just made it clearer that they were intrisically computing the same value.

I'm guessing that the point the video was trying to make was that
$$3^{54\times24}\equiv3^{24\times54}\equiv 16^{54}\equiv15^{24}\equiv1\mod 17.$$


RSA Encryption and Signature - Weak Padding

Yes, there is an attack that has a fair chance of success, like $2^{-8}$ per $Sign$ (and perhaps $Sm$) submitted; or even more depending on exactly how the encryption padding is removed/verified. The attack does not require submitting a message for signature to a party knowing the signature private key. I consider the attacker successful whenever she manages to submit something that the receiver accepts, deciphering and recovering the message $m$, even when the attacker gets no clues about $m$.

More hints: The attacker needs no other input than the signature verification public key, and perhaps the size of the encryption modulus. The attacker's expected cost for a success may be $2^{15}$ modexp (more or less depending on exactly how the signature padding is removed/verified, and for some interpretations of that how much the bit size of the signature modulus exceeds the bit size of the encryption modulus, rounded-up to the next multiple of 8).

The big picture: the attacker repeatedly chooses $Sign$ arbitrarily, and weeds out some appropriate subset of them for submission, by making just what the receiver would do, as far as the attacker can; because there is (explicitly at least) little more than one byte (the $01$) of verifiable signature padding, a sizable fraction of $Sign$ are an acceptable signature for some $Sm$, and (critically) the adversary can find that $Sm$. The adversary submits those $Sign$ (and the associated $Sm$ if that's part of the protocol) that pass that (very weak) signature verification test; and because there is (explicitly at least) little more than one byte (the $00$) of verifiable message padding, a sizable fraction will also decipher to some $m$.

Like most simple attacks exploiting a lack of enough padding (here: in a signature scheme allowing message recovery), the cost of the attack (expressed in number of modular operations) is mostly independent of the size of the signature modulus.

To better grab how the system and attack works, we need to further define what the parameters are. Let the signature modulus be $N$ of $n$ bits, and the encryption modulus be $N'$ of $n'$ bits. The result of the encryption step is a number up to $N'-1$, thus $Sm$ is a bytestring of $\lceil n'/8\rceil$ bytes when it is used in the signature padding $01||Sm$, which has one more byte. Thus $01||Sm$ is a bytestring representing an integer of exactly $\lceil n'/8\rceil\cdot8+1$ bits, and the cryptosystem can sign the result of any encryption when $N\ge(2^{\lceil n'/8\rceil\cdot8}+N')$, including but not limited to if $n\ge(\lceil n'/8\rceil\cdot8+2)$ bits. Perhaps the system is intended for $n=(\lceil n'/8\rceil\cdot8+8)$. If $n$ was much more, the signature padding would be shown as $00..01||Sm$.

We must also reconstruct or assume what exactly the receiver does:

receive $Sign$;
perhaps (that's untold) reject the submission if $Sign\ge N$;
compute $Sign^e\bmod N$, making that a bytestring of $\lceil n/8\rceil$ bytes;
reject the submission if the leftmost byte of that is not $01$;
consider the remaining bytes of the bytestring of (3.) to be $Sm$ (or if $Sm$ is explicit in the receiver's input, fail if the remaining bytes do not match $Sm$);
perhaps (that's untold) reject the submission if $Sm\ge N'$;
compute $Sm^{d'}\bmod N'$ and convert that to a bytestring of $\lceil n'/8\rceil$ bytes;
perhaps (that's untold) reject the submission if the leftmost byte of that bytestring is not $00$ (that corresponds to checking the few zero bits that customarily are on the left of $randompad||00||m$ in order to make the corresponding integer less than $N'$);
assuming that $m$ has fixed width $w$ bytes, reject the submission if the $(w+1)$th byte from the right of the bytestring of (7.) is not $00$ (or, assuming that $m$ is a bytestring of variable width not containing $00$ such as a C or UTF-8 string, recover $w$ and $m$ by scanning that bytestring from the right until a $00$ is found, rejecting the submission if the bytestring contains no such byte);
Having found no rejection reason, accept the message $m$ extracted from the bytestring of (7.).

The attack should be obvious by now: the attacker repeatedly selects $Sign$ e.g. randomly in $\{0\dots N-1\}$, and performs (3.), until the bytestring obtained has a $01$ on the left so that it pass (4.), and the remaining $Sn$ pass (6.) if applicable [note: I have not included (6.) in my estimate of the attack's cost, but the increase would be by a factor of $2^{\lceil n'/8\rceil\cdot8}/N'$, which is less than $2^8$]. The attacker submits those surviving $Sign$ (and perhaps the matching $Sn$ if that's required). In the first option of (9.), the odds of success of the attacker are $2^{-8}$ per attempts (and more in the other option), assuming no step (8.).

A speedup (and a practical attack even when $n\gg n'$) is possible when $e$ is very small, like $3$, $5$, $17$; that is left as an exercise to the reader. The conclusion should be: use strong padding (not: do not use very small public exponents).


Probably all you need to know about RC4 (at your level) is on the Wikipedia page. There's even code. And then there are all the links to follow for more detail. And two books in Further Reading:-

Paul, Goutam; Subhamoy Maitra (2011). RC4 Stream Cipher and Its Variants. CRC Press. ISBN 9781439831359.
Schneier, Bruce (1995). "Chapter 17 – Other Stream Ciphers and Real Random-Sequence Generators". Applied Cryptography: Protocols, Algorithms, and Source Code in C (2nd ed.). Wiley. ISBN 978-0471117094.

Make sure you acknowledge the Security section on that page.


Are there some problems to use pseudo-random number generator in Smart Card?

All modern microprocessor Smart Card ICs contain a physical True RNG, generally followed by conditioning using a hardware de-biaser (such as Van Neumann's) or/and deterministic Pseudo-RNG of some kind that make the TRNG output more indistinguishable from random. Independently, a Smart Card could contain a (Cryptographically Secure) Pseudo-RNG. The later is what the question as worded is about, but I'll cover both.

Yes there are possible problems with these RNGs - and techniques to deal with them.

Defective RNGs happen. In a well-documented recent example, the TRNG used inside a Smart Card to generate its RSA public/private key pair was bad on a fraction of the production, making the RSA modulus factorisable with specialized techniques. This class of failure is a bad design or build of the physical randomness source. Here it was most likely accidental, but an adversary could try to induce similar fault (e.g. by varying the temperature of the IC, its power supply..) e.g. so that a random number generated as challenge by a Smart Card actually repeats with much higher probability than normal.

In order to guard against such failure in TRNGs, the reasonable thing to do is to include tests of the TRNG source at least before conditioning, and use well-thought post conditioning, perhaps including Cryptographically Secure for some usages. This is codified in the AIS31 scheme for common-criteria security evaluation of TRNG (index in German, linking to documents in English; see also how French authorities have been using AIS31 method, including some reservation in section 5).

Sometime, the state of a PRNG is held in non-volatile memory (if it was not, when we power-off the Smart Card, the state would be lost and, absent special precaution, the PRNG's output would be the same each time we power-up the Smart Card, which is a devastating issue). The adversary would like to recover that state, or alter it to a known state (e.g. by removing power while this state is being changed). Well-designed Smart Card hardware and software have layered protections against such attacks on their non-volatile memory, making memory examination extremely difficult, preventing data loss using temporary duplicates and flags, and using techniques for detection (perhaps correction) of errors.

Another issue for implementation of a PRNG in a Smart Card is side channel and fault injection attacks (slides), which try to guess the PRNG state while it normally changes, or alter how it changes (the aforementioned power removal is a fault injection). Again, Smart Cards have an arsenal of countermeasures against these.

Comments suggest comparing use cases of PRNG vs TRNG in a Smart Card.

Smart Cards need randomness, and a lot of it, as part of protection against side-channel attacks. That's starting right at power-up, which can be performed an unlimited number of times (I have seen contactless Smart Card readers doing a hundred power cycles per second). A pure PRNG just can't work: it is deterministic, and will either produce the same output on two card power-up, or require update of a non-volatile memory, which is slow, easily detectable by SPA, and doable only a limited number of times in the operational life of the device. Also, this state must be initialized at some point of the life of the Smart Card, with a random secret, an operational annoyance.

That's why all Smart Cards ICs provide at least one hardware TRNG, at least for their internal use. The only hardware PRNG that I ever met on these ICs was used as post-conditioning of a TRNG. This (conditioned) TRNG provides excellent randomness, of near-crytographic quality, in usably ample quantity, easily and quickly accessible to the low-level system programmer (after a check that the TRNG is actually working, which is a source of serious complications). It is common (and the recommendation of many competent persons beyond French authorities in the aforementioned section 5) to use this as seed to a CSPRNG implemented in software (often using hardware accelerators for a block cipher) for something requiring cryptographic characteristics.


RSA 3072 is 65,536 more difficult to factor than 2048?

If RSA 3072 is equal to 128 bit symmetric and 2048 is equal to 112 bit symmetric...

To be precise, a 2048 bit composite is estimated to take approximately $2^{112}$ operations using the Number Field Sieve algorithm; 3072 bit composites are estimated to take approximately $2^{128}$ operations using that same operation.

Since the Number Field Sieve (NFS) algorithm is the fastest factoring algorithm known on a classical computer for large general composites, this is taken as the work estimate

  In that case wouldn't this make 3072 more future proof against quantum computers or does Shor's algorithm mean they will both be equally useless?

Once we bring Quantum Computers and Shor's algorithm into the mix, that opens up another algorithm that is potentially more efficient than NFS.  And, for Shor's, 3072 bit integers isn't that much more difficult that 2048 bit ones.


Currently we do not think that 512 bit DH is secure. You can look for more secure parameters (i.e. above 1280 bits at the very least) is secure. Secure key sizes can be found at keylength.com. For DH you can e.g. look at the NIST recommendations for "Discrete Logarithm" (the underlying mathematical problem that is the base of DH-based cryptography).

Using Diffie-Hellman as base for AES-256 is a bit misleading, as it is not likely that your DH provides the same level of security as AES-256. As you can see in the tables DH requires a 15K key size (!!!) to reach the same security level. Claiming a security level of 256 bits would be unfair (but read the next section)

What DH generates is a shared secret. This shared secret has a lot of pseudo-randomness. As such it can be used directly by using the leftmost (or rightmost, but leftmost is more common) bits of the shared secret as a key. More information here (note the author of the question!). This is however not considered good practice, as you preferably do not want to have any bias of bits in the secret (AES) key.

So commonly we use a key based key derivation function (key based KDF or KBKDF) to condense (or extract) the pseudo-randomness of the master secret into one or more keys. That way each bit of the key depends on each and every bit of master secret material and removes any possible bias in the bits of the resulting secret key.

Quite often cryptographic API's offer combined key agreement / key derivation functions where a KDF is already used upon the result. Sometimes that means indicating a hash function, which is then used as (only) primitive within the KDF. The compression functionality within a hash is, as you might imagine, perfect for condensing the pseudo-randomness.

If you do not use a KDF then you might want to use a 256 bit AES key as it will have at least 247 bits of pseudo-randomness, as specified in the answer on my question. A 128 bit key will have less than 128 bits after all.


Pub alg - Reserved for Elliptic Curve(pub 18)
    unknown(pub 18)

The output explains pgpdump knows this is an elliptic curve algorithm (which has ID 18), but does not understand the exact details (which curve was used, ...). Try gpg --list-packets instead which has full support for ECC (requires GnuPG 2.1, binary might also be called gpg2 on Debian and derivatives).

    -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02

These are details of the session key used for the symmetrically encrypted packet that will follow: the symmetric algorithm, a checksum and finally the PKCS-1 encoded session key. From RFC 4880, OpenPGP, 5.1.  Public-Key Encrypted Session Key Packets (Tag 1):

  The value "m" in the above formulas is derived from the session key
     as follows.  First, the session key is prefixed with a one-octet
     algorithm identifier that specifies the symmetric encryption
     algorithm used to encrypt the following Symmetrically Encrypted Data
     Packet.  Then a two-octet checksum is appended, which is equal to the
     sum of the preceding session key octets, not including the algorithm
     identifier, modulo 65536.  This value is then encoded as described in
     PKCS#1 block encoding EME-PKCS1-v1_5 in Section 7.2.1 of [RFC3447] to
     form the "m" value used in the formulas above.  See Section 13.1 of
     this document for notes on OpenPGP's use of PKCS#1.


Would a symmetric cipher with a keylength a big as the data length be information theoretically secure?

No, using any keyed permutation with key length equal to the block size reduces the number of possible plain texts by ~1/3

Assume first that AES reasonably approximates a pseudorandom permutation, for each block of the message, the attacker (assuming unbounded computing power) can calculate the plain text for all keys. This is equivalent to throwing 2^128 balls into 2^128 baskets randomly. There will be collisions. The chance that any plain text is not a valid solution is approximately 1/e

filled fraction = 1-((n-1)/n)^n , n=2^128

this converges to 1-1/e

this reduces the effective number of plaintexts by  about 1/3 (=0.63 ~= -0.66 bits). The reduction also tells the adversary about the probablity of any ciphertext being correct since about half the remaining plain texts got two hits instead of one with 2x the probability of being correct.

A problem with this scheme is that fooling the observer into accepting a plausible fake message requires solving for the key K which would connect the plaintexts and ciphertexts, fortunately, thanks to the recent SHA3 competition the cryptanalysis to do so has been mostly done.


Good challenges for a crypto competition for teenagers

Perhaps you could do something with Visual Cryptography.
Maybe something like:

Gather a few low-resolution images (symbols or short text phrases), perhaps a few more images than you have kids
Use visual cryptography to split each image into 2 random-looking images, and print each random-looking image on its own piece of transparency paper
Shuffle the pile of transparency papers
somehow let the kids find matching pairs of transparencies that show the original symbol or phrase.

Is there some way to let kids produce Visual Cryptography image-pairs "by hand", without a computer?

Links and further reading:

"What is Visual Cryptography"
online visual cryptography generator
"Visual Cryptography Kit"
visual cryptography example
"Visual Cryptography and Bit-Plane Complexity Segmentation"
XOR with polarized film


I assume you mean H to be a one-way function. The way you 'prove' that you know half of the input of a one-way function (i.e. y or H(y) for the outer H()) will be to produce the other half of the input (i.e. x or H(x)) and show that H() of the two parts together gives you z.

In general, if your H is a Pseudo-random-function (which any good crypto-hash function is), then ANY possible combination of y and z has an infinite number of xs that will combine in the way you ask.


Digital signature providing a proof of file authenticity

First of all, authenticity and integrity are related especially when it comes to cryptography. The reason is simple: if an attacker can alter the file - void the data integrity - then the file is obviously not authentic / original anymore. Note that data integrity does not disallow replacing the signed file by another file signed with the same private key.

It is required to verify that the signature and file match to provide authenticity. The verification procedure most show that the signature was created by the entity that that was supposed to have signed the file. Usually asymmetric cryptography is used for this, where a key pair is generated by the signing party. The private key is kept by the signing party and the public key can be distributed to parties that need to perform verification.

The private key an be used to perform signature generation over the file. The public key can be used to verify that the file was signed by that particular private key because the public key and private key are mathematically related to each other. Generally the signature generation and verification both have to use a cryptographic hash over the file to calculate a statically sized, computationally unique value to represent the file; this unique hash is used in signature generation and verification rather than the file itself.

The verification shows that the file must have been signed using the private key that is part of the key pair. It is however of vital importance that the public key is trusted to belong to the private key of a particular party. Otherwise an adversary could simply substitute their own key pair and substitute both the public key and signature values. In other words, the signature value can only be trusted once the public key is trusted.

Note that cryptographers generally talk about message authentication. A file is just a persistently and sequentially stored message with a particular name. In cryptography a message can consist of any ordered amount of bits. We don't care how the bits are presented during signature generation / verification, as long as they are present when required.


What is Indistinguishability Obfuscation?

Program Obfuscation is a method to scramble the program code such that it becomes unintelligible but preserves the program's functionality. The notion of indistinguishability obfuscation was proposed in [BGI+01]. Actually they first consider another notion which is called virtual black box obfuscation (VBB Obfuscation). However, they showed that VBB Obfuscation is impossible, so they proposed the concept of indistinguishability obfuscation (IO).

In 2013, [GGH+13] proposed the first candidate IO from assumptions over multilinear maps. After that, a number of its applications were proposed. For example, deniable encryption [SW14], witness encryption [GGSW13] and round optimal (2-round) MPC [GGSR13] (Actually, just review the list of IACR preprint after the appearance of the first candidate IO, you could find a great number of paper discussing applications of IO).

Currently the central problem is how to build IO from standard mathematical assumptions (e.g., LWE and Bilinear Maps). The most most recent breakthrough was made by Rachel Lin et.al. from last year through this year [Lin16][LV16][Lin16][AS16][LT17].


Other than password hashes, are there other uses for non-reversible crypto

Data integrity is another usage. For example, when you want to send/download data, you want to make sure that the data is not modified or transmitted/downloaded correctly. To achieve this the data hashed and the hash value sent/downloaded on another channel. One may see examples of this file verification on Linux ISO download pages. Of course, hashing is not enough to protect you against some attacks. Therefore you need digital signatures.

Another one, when digitally signing the document, we first hash the document then sign the hash value. This is more efficient than signing the whole document.

Keyed-Hash Message Authentication Code (HMAC) is a message authentication code (MAC) that involves a Cryptographic hash function and a Cryptographic key.

Key Derivation Functions are also using hash functions to derive a key from your password plus various random sources.

Key Stretching: making a possibly weak password more robust against brute-force attacks. PNKDF2, bcrypt, Argon2 use key stretching.

Ratcheting: forward key chaining with no backward availability.

A special case of hash usage is the Merkle-Tree to verify the integrity of data with low bandwidth.

In Blockchains: hashes are a fundamental part of the blockchains.

Proof-of-work systems:

A Proof-of-Work (PoW) system (or protocol, or function) is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer.

Bitcoin mining and Hashcash use Proof-of-work systems.

Constructing Stream Ciphers as in ChaCha2 in TLS 1.3. This construction uses CTR mode of operation.

Public Key Cryptography: Trapdoor one-way functions are easy to compute hard to invert without special information. Most of the public key cryptosystems are based on Trapdoor one-way functions.

Commitment schemes allow committing a value while keeping others hidden and give the ability to reveal at a later time.

Lamport signature or Lamport one-time signature scheme can use one-way functions in which usually cryptographic hash functions are preferred.

Secure Random Number Generators such as Hash_DRBG use hash functions to improve and stretch the output from a true random number generator


Consequences of AES-GCM always encrypting the same plaintext

The main obligation for the AES-GCM is never to reuse a (Key, IV) pair.

Can the encryption key be compromised if you have enough transcripts of protocol runs?

How many protocol runs would you need (AES-128-GCM is used)?

The standard IV size is 96-bits. If sequentially used (as NIST says counter/LFSR ) then one cannot finish this IV space in a lifetime. Once reuse occurs, however, with a system failure etc., then the confidentiality is revealed and the same string that always sent is compromised.
Also, using the same key with a new random IV can cause replay attacks. The attacker can just re-transmit and old data. It is valid since the same key is used. Mitigation is putting time-tamps on the encrypted message. A new key establishment per record is better as used in TLS 1.3.
AES-GCM for single (Key, IV) pair the total encryption is most $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits. No problem here.
Once the keystream revealed with the key reuse, the attacker needs to execute a known-plaintext attack against AES-CTR. AES-CTR is secure against KPA attacks it has Ind-CPA.

The plaintext that is being encrypted is always the same. It may be assumed that the plaintext is known by the adversary.

The IV used in the encryption provides probabilistic encryption so that the same message will have different ciphertexts. This is crucial in modern Cryptography. And, again AES-CTR is secure against this KPA attack even Ind-CPA.
Suggestions:

Change the key with a predefined protocol.
Don't send the same message again, use new challenges in each message.
If the message is known to the adversary, what is the point of the encryption? You just give the attacker lost of known-plaintext that is normally hard to collect.
Use timestamps to protect againstt replay attacks,


In general a function $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ is a PRF, if you can not distinguish it from a real random function. For that you can play a game with an adversary. The adversary get eather a real random function or your random function. If the adversary can distinguish these functions better than with negigible probability, the function is not pseudorandom. If he can't distinguish them that good, the function is pseudorandom. In Katz & Lindell's textbook (2nd edition) on page 448ff you can find more about this. But for a PRF you need to arguments and I don't see, that your functions are defined over two.
Therefore I think you mean pseudorandom generator PRG instead of PRF. For the game with the PRG an adversary only gets two strings and he has to distinguish a real random string from a string that was constructed by the PRG. If he can distinguish them better than with negigible probability, the PRG is not pseudorandom. If he can't, it is pseudorandom.
For both games you don't look at one case, but for all cases. So if the adversary can find a strategy to only distinguish 1% correctly, he "won" the game and the PRF or PRG is not pseudorandom.
In your case: For your first function I can't tell weather it is a PRG or not, because I don't know more about $a$ and $b$. For the rest you can build an adversary, if N is known, that can distinguish them pretty easily. If you want to learn how to write a correct proof for that, you should definitely look into Katz & Lindell's textbook (2nd edition) or Katz & Lindell's textbook (3nd edition).
In general: Easy mathematical function like linear or quadratic functions are no good PRG in general. Even logistic functions aren't. For beginners in cryptographie and learning abouot PRG you mainly assume you got a PRF and then build another based on it and then proof is using reduction. In practise you can use a hash-function as a PRG.


The obvious solution would be to use secret sharing: the file $F$ is encrypted using a secret key $K$, and $K$ is secretly shared between the $n$ parties, so that if at least $t$ parties reveal their share, the key $K$ can be reconstructed, while if less than $t$ parties reveal their share, the key $K$ remains perfectly hidden: Secret sharing can be constructed from simple interpolation methods, see Shamir's secret sharing scheme.

An issue of the above method is that, once the key $K$ is reconstructed, everyone knows it, so a fresh new key should be generated and shared between the parties for each file that we want to encode. A better solution, where many files can be encrypted using the same key, and so that a sufficiently large group of parties can decrypt a given file without leaking anything about the remaining encrypted files, is to use threshold encryption. A public-key threshold encryption scheme allows everyone to encrypt a file, but the decryption is performed as an interactive protocol between parties holding shares of the secret key. We know construction of such schemes from most standard cryptographic assumption, such as DDH.


The attack is even more simple with RSA than with symmetric keys, because the asymmetric encryption key is assumed to be public.

Let me tell you a story involving Alice, Bob and Mallory :). Alice wants to send a message to Bob using RSA.

Alice encrypts the message using Bob's public key and sends it
Mallory performs a Man-In-The-Middle attack, and encrypts another message using Bob's public key (as it's public)
Bob received the new message thinking it comes from Alice, as there's no origin authentication.


Each column of 4x4 byte array S is regarded as column vector over the Rijndael field F.
It is then updated by multiplying the column vector by a specified 4x4 matrix over F.
Thus muxColumns modifies the state array by hte matrix multiplication (0<=j<=3),
Hence, in your example you are encoding ${S_{(3,3)}}$ which is last row of Matrix and represented as polynomial ${3x^3+x^2+x+2}$


The problem

Frequency attack is a big problem for databases. For example, these two 1 2 articles represent the attack in CryptDB. This can have serious results, especially if you consider that the encryption is enough. You can find more about frequency attack if you search. There is no clean solution if you have to query over the encrypted data and if you don't know about the distribution of the columns.

The pioneer work

Hacıgumüş et. al was a pioneer in this subject; Executing SQL over Encrypted Data in the Database-Service-Provider Model. Their work used partitioning of the data into buckets. The first column etuple contains the encryption of the columns in concatenate form and the columns are bucketed. You query over the bucket columns and decrypt the etuple on the returned query result. On section 2.1 you can find partition example functions.

Using hash

Using a trimmed hash function at first may seem like a solution but not necessary. We are not under control of the output of the hash functions. The two most frequent data in a column may have the same trimmed hash result. Therefore one needs to check the buckets.

Another not enough solution

There was an article about, that I couldn't find it1, was proposing dividing the data into equal size buckets. This works requires preknowledge of the frequency.

The technique was in the simple term normalizing the data into buckets that is differs from your solution. For example; assume that we have 5 different data in a column with the following name and amounts; $\{(a,5),(b,10),(c,20),(d,40),(e,25)\}$ then they proposed to partition into buckets that can contain at most 10 elements;

$$\{(a,5,10), (b,10,10),(c_1,10,10),(c_2,10,10), (d_1,10,10),(d_2,10,10),(d_3,10,10),(d_4,10,10), (e_1,10,10),(e_2,10,10),(e_3,5,10) \}$$ where the sub indexes are different encryption of same value, that can be satisfied by a fixed IV for CBC mode per bucket.

For the query, you have to store the bucket information in your appliaction server. Wait; if attackers see the row count of returned result from the DB, they can identify some buckets. For example, if you query $a$ they can know that it is either $a$ and $b$.

Note 1: If you are not carefully bucketing, the row count will have a similar result for bucketing. For this one may assume that the attacker has limited time on the attack and can say only a few queries may be leaked. This totally depends on your risk analyzes.

Note 2: if the frequency of the data changes over time, you may need to re-bucketing

1 I'll link if I can find someday.


Communication Complexity of Equality comparison (Catrina and de Hoogh)

What does an invocation mean?

The communication cost of opening 1 secret-shared field element.

Since the protocols of Catrina and de Hoogh are mostly independent of the underlying MPC protocol, this cost can vary. In SPDZ, for example, the trivial opening algorithm requires $O(n^2)$ field elements to be sent across the network in all, but it can also be done in $O(n)$ (see p25).

  Can Costs #1 and #3 also be moved to a pre-processing phase?

Step 1 just generates random bits, so can be done as preprocessing. Step 3 consists of two parts: the first (line 4 of Protocol 4.2 in the paper) can be preprocessed, while the second (line 9) depends on the inputs, $[a_i]$, so must be done online.

  Is Catrina and de Hoogh the most computationally efficient constant-round protocol currently out there that does a secure equals-zero test of a secret value to generate a secret result?

There's a paper by Lipmaa and Toft with a constant-round equality test with less communication than Catrina and de Hoogh's. However, it has higher local computation costs. I don't know of a computationally more efficient protocol.


How can PUF hardware be proportional to the number of challenge/response bits?

To implement challenge-response in ROM only (no computations), you basically need a lookup table, a mapping from challenges to responses. So for a $k$ bit challenge, you would need $2^k$ entries in your lookup table.

How would this work on a PUF?

Consider the following PUF example (taken from Improved Ring Oscillator PUF: An FPGA-friendly Secure
Primitive, Journal of Cryptology, 2011):

The portion on the right shows the ring oscillator (RO), whose value is going to be entirely dependent on the fabrication process and therefore is "unclonable". You put a bunch of these ROs together, feeding into two MUXs, with the challenge determining which RO value to select. Finally, the outputs of the two MUXs are used to increment two counters, which are (after some short period of time) used to determine a single bit by doing a comparison. Your $k$ bit challenge may be divided up into smaller challenges to get a larger response from the PUF than a single bit. This would be a deterministic process so that given the same $k$ bit challenge, you would get the same response (in practice there is some probability of bits being flipped in the response, so typically some error correcting is done).

To get a secure $k$ bit response, you will need some number of ROs, but you won't need an exponential number of ROs. If you have $N$ ROs, there are $N(N-1)/2$ distinct pairs of ROs. Each pairing can be used to generate a single bit using the setup shown above. However, as noted in Physical Unclonable Functions for Device Authentication
and Secret Key Generation, the entropy of the circuit will not be as high as that. In that paper, the authors derive the maximum entropy of the circuit as $\log_2(N!)$. So for a desired $k$, you could compute $N$. As an alternative method, the authors note that for simplicity, you could design the system such that each oscillator is used only once for any challenge value. If you did this, you would need $2k$ oscillators to generate a $k$ bit response. I would note that due to error correcting, you may need additional bits, but this should only increase the number of oscillators by a constant factor.

Now, how would this be used in a challenge/response protocol. Well, first there must be a trusted setup. The challenger, in a clean environment, sends a bunch of challenges to the PUF and records the responses. So, the challenger may have to store a lot of challenge/response pairs depending on the application. The point is, the hardware does not have to store all that information.

Then, when the system is fielded, the challenger sends a challenge to the device. The device runs it through the PUF and returns the response. Someone without access to the PUF could not compute the correct response. Further, someone trying to clone the PUF would not succeed because of the manufacturing variations in the ROs. Those manufacturing variations, even when very subtle, would be enough that the responses would not be the same.


Find out which keying option is being used in Triple DES?

Actually, there's no known way (assuming practical amounts of computing power) to distinguish keying methods 1 and 2.  You mention a "brute-force attack of complexity $O(2^{56})$ followed by a chosen plaintext attack of complexity $O(2^{57})$", there's no obvious way to frame an attack against either of the first two options in this matter; you can't do a brute force attack on one of the keys, because there's no obvious way to confirm a guess on a potential key (other than immediately doing a brute force attack on another of the keys, in which case you're really talking about an effort of $O(2^{112})$.

On the other hand, it is feasible (if moderately difficult) to distinguish the third option from the other two.  This third option is essentially DES; a brute force search of all possible $2^{56}$ DES keys will distinguish it given a single plaintext/ciphertext pair.  In addition, with sufficient known plaintext/ciphertext, linear cryptanalysis can make the distinguishing effort moderately easier.

The best work I known on linear cryptanalysis is this paper; using approximately $2^{43}$ plaintext/ciphertext pairs (that is, a few trillion), they are able to distinguish DES from a random permutation with about $O(2^{39})$ DES computations, which is moderately cheaper than simple brute force.


A simple solotion could be that all phones need to have the same pre-shared key.
The pre-shared key could be downloaded once at first run, maybe from a password protected httpS site, or maybe from a url that delivers an encrypted and signed file with private/public key.

Then the pre-shared key is used on all phones, and it is used to encrypt by the sender, and decrypt by everyone else.

This simple solution provides only encryption, because  this is what the only requirement of the original question.

This doesn't address all security issues, for example replay attack and impersonation.
If you needed more than just encryption, then the solution will have to be a bit more complex.


Countermeasures to prevent integral cryptanalysis against 4-rounds AES

This question may be theoretically interesting.

However, it looks to me strongly likely that the nice diffusion properties of AES using operations of order $4$ ShiftRows) and matrix ($4\times 4$) multiplication on vectors of dimension $4$ (MixColumns) are the reason for the existence of these attacks and changing these properties may well require more rounds for security.

The requirement that these operations be one-to-one, in the absence of a feistel structure, means that the SPN structure may also need to be dumped in order to avoid 4 round integral cryptanalysis.


In ElGamal Signature Scheme we have:

$$\beta=\alpha^a \bmod p$$

The values $p,\alpha$ and $\beta$ are public key, and $a$ is private key.

$$\operatorname{sig_k}(x,k)=(\gamma , \delta)$$

  where $\gamma = \alpha^k \bmod p $ and $\delta = (x-a\gamma)k^{-1} \bmod {p-1}$.


Applications of machine learning in classical ciphers?

A cryptanalyst finds the right key for decryption, while a machine learning model finds a suitable solution in a large space of possible solutions. With enough data, the machine learning model could find a good solution. How much data is needed to reliably use machine learning for breaking complex ciphers such that it's less work than brute-force search could be a challenge.


If I understood you correctly, the protocol you are analysing doesn't reinitialize the encryption before encrypting, so it seems like it is encrypting everything it send yet and sends only the part that "is new".

To answer your question, let's take a little excourse into stream ciphers (as RC4). These ciphers basicly generate a stream of random numbers which are then xored with the plaintext. To decrypt, you have to generate the key stream again and then xor it with the ciphertext.

$C = P \oplus K$

$P = C \oplus K$

($C$ is the ciphertext, $P$ is the plaintext, $K$ is the keystream and $\oplus$ is XOR)

One property of such ciphers is that to en- or decrypt one section is that you just need the related section of the keystream. So, in your protocol, following will likely happen:

Client-Side:

Calculates $K_{0}$
Sends $C_0 = P_0 \oplus K_0$
Calculates $K_1$
Sends $C_1 = P_1 \oplus K_1$

Note that the client doesn't need $K_0$ nor $P_0$ to encrypt $P_1$.

Server-Side:

Calculates $K_0$
Recieves $C_0$ and decrypts it using $P_0 = C_0 \oplus K_0$
Calculates $K_1$
Recieves $C_1$ and decrypts it using $P_1 = C_1 \oplus K_1$, the server doesn't need $K_0$ nor $P_0$ to decrypt $C_1$, so it doesn't have to do the operations you did while reverse engineering.


Diffie-Hellman over several non-secured HTTP requests - will it work?

First, I'd like to say: Don't roll your own crypto.

Your first protocol is basically "your own crypto". The easiest / standard solution to this problem is to use TLS. You can use TLS (with server-authentication only) as a replacement for your first part. I'd recommend though, using DNSSEC / DANE as well (if possible) so you don't have to have a (complex) root-certificate store.

What you do next is up to you. I'll first analyze your proposal and then provide another.

If an attacker (within your threat model) can get hands on the
serial number he can pretend being that device and thereby may break
security guarantees, because the server doesn't know who he's
talking to.
In your third step you say that "Client to Server" sends the key. I think you meant it the other way around? Note that if you send the private key over the wire, the key is only as secure as the connection (so if you use a "bad" DH private key the key could still be compromised even though it's high entropy).

Otherwise this looks fine and pretty standard.

You generate your own private key on the device along with a CSR.
You send the CSR to your server along with some "secret" that identifies the device in question and that can not easily be retrieved for attackers in your threat model.
The server will create the certificate from the CSR and send it back to the client.
The client can now use said certificate for client-authentication.

As for the "how" of the generation of the private key:

You stated that you have a somewhat reliable entropy source on the device.
If you can guess any private key generated on the device there's no chance that you can get a private key securely to the device as the transport key could be broken (because it's weak).
Assuming you can scratch enough entropy together (i.e. 128 bits of entropy distributed over an unspecified amount of bytes) you can run your "random" bytes through a key based key derivation function (e.g. HKDF), to get a key and an IV for the stream cipher of your choice (e.g. AES-CTR or ChaCha20 or Salsa20).
You can now use this stream cipher to generate a pseudo random stream of bytes that you can use as a replacement for your system RNG to get a good private RSA key. Note that 128-bit entropy is good enough for a 3072-bit RSA key as it anyways only provides a 128-bit security margin.


Knowing the key, how do I decrypt the affine cipher?

This is a special case of the affine cipher where $m=26$.

Let's encrypt a single letter using your $E$. Let it be m, say, which is at index 12. So, $$E(12) = (7 \cdot 12 + 10) \mod{26} = 16$$

Now if we try to use the $D$ in your question, we decrypt this as:

$$D(16) = (7 \cdot 16 - 10) \mod{26} = 24$$

which is obviously not right. The issue is that your $E$ and $D$ aren't really inverses. The general technique in math classes for finding simple function inverses is to swap the dependent/independent variables and solve, so let's do that to find the inverse for $E$.

Let $y = E(p)$ for convenience's sake. Now let's swap $y$ and $p$ in the encryption function (and swap over to modular arithmetic notation):

$$p \equiv ay+b \mod{26}$$

and try to solve for $y$ (aka $E(p)$). Well, we move $b$ over first, which is just your typical "Algebra" material from school.

$$p - b \equiv ay \mod{26}$$

Now here comes the kicker: you need to "divide by" $a$. Now, I don't know your abstract algebra background, but arithmetic modulo $n$ takes place in the ring $\mathbb{Z}/n\mathbb{Z}$, also sometimes written as $\mathbb{Z}_n$. The issue is that multiplicative inverses are not guaranteed to exist in rings. In the case of $\mathbb{Z}/n\mathbb{Z}$, an element $x$ only has a multiplicative inverse if $\gcd(x, n)=1$. Fortunately for us, $a = 7$ and $m = 26$ are coprime, so $a^{-1}$ does exist.

Hence, we can write:

$$a^{-1}(p - b) \equiv y \mod{26}$$

which gives us:

$$D(c) = a^{-1}(c - b) \mod{26}.$$

This agrees with Wikipedia's article on the affine cipher, so it's good to know that we're not totally off-track here. How do you find $a^{-1}$? The article Modular Multiplicative Inverse on Wikipedia gives you a few ways. In this case, I'd probably just try trial-and-error, but you can also use the Extended Euclidean Algorithm to do so if you dislike trial and error. Fortunately for us, someone at Princeton is hosting this modular inverse calculator, which tells us that $a^{-1} = 15$.

So, taking the above $E(12) = 16$, let's see if our new $D$ works:

$$D(16) = 15 \cdot (16 - 10) \mod{26} = 12$$

which succeeds! From there, I trust you can complete the computation for your ciphertext.


What is shared-input for Multi Party Computation?

With additive shared input, can any computations be evaluated??
If so, what is the method used for the evaluation??
Is garbled circuit applicable to this scenario??

Yes, any computation can be evaluated. This is achieved by representing the functionality to be computed as an arithmetic circuit (not a garbled circuit) that consists of addition and multiplication gates. The addition gate can be evaluated by the parties locally because the shares are additively homomorphic. The multiplication gates can be evaluated by the parties interactively.
If you want to know more about it, there is a book: Secure Multiparty Computation and Secret Sharing, by Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen.
There are also some relevant papers if you are interested:
Ronald Cramer, Ivan Damgård, Ueli M. Maurer:
General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. EUROCRYPT 2000: 316-334
Dan Bogdanov, Sven Laur, Jan Willemson:
Sharemind: A Framework for Fast Privacy-Preserving Computations. ESORICS 2008: 192-206
Ivan Damgård, Valerio Pastro, Nigel P. Smart, Sarah Zakarias:
Multiparty Computation from Somewhat Homomorphic Encryption. CRYPTO 2012: 643-662


The certificate makes sure that whoever you're talking to is who they claim they are. With TLS/SSL without certs you wouldn't notice if you're communicating with an impostor over an encrypted channel instead of whoever you're expecting to communicate with. This leads to so called man-in-the-middle attacks. You really should read this, if you're going to use TLS:

http://en.wikipedia.org/wiki/Certificate_authority


Why only non-prime order fields have small subgroup attacks?

In Group theory, it is known that if $G$ is a finite group and $q$ is a prime number dividing the order of $G$ (the number of elements in $G$), then $G$ contains an element of order $q$ (Cauchy's theorem). And the order-$q$ element generates an order $q$ subgroup.

Thus if a group $G$'s order $N$ is not a prime number, then $N$ can be factored and $q_1,\cdots,q_n$ are the prime factors of $N$. For each $q_i$, there must exist a subgroup of order $q_i$. When $q_i$ is small, the subgroup is small. Hence small subgroup attack may be possible.

If a group $G$'s order is a prime number $p$, then by the Lagrange's theorem, the order of every subgroup $H$ of $G$ divides the order of $G$. Now $p$ has only two factors $1$ and $p$, thus $G$ can have two only subgroups: the trivial subgroup containing the identity $\{1\}$, and $G$ itself. There is no other small order sub-groups.

You also need to distinguish the finite field $F_p$ and the curve over the finite field $F_p$. They are two different things. The order of $F_p$ is the $p$ (elements are integers from 0 to $p-1$, inclusive), and the order of the curve over the finite field $F_p$ is the number of points on the curve and is bounded by the Hasse theorem $|order(E(F_p)) - p-1|\le 2\sqrt{p}$. A curve can be prime-ordered (or we can use a prime-ordered subgroup of all the points on the curve if the curve order is composite), but it is not simply because it is over a prime field.


how to use salt to sign a message and how is it effective?

There are a couple of reasons why a salted signature would be helpful. It really depends on the particular implementation of a system.

For example if your message is encrypted, then signing with a salt could give you a different signature for the same message each time. This can be very important depending on the situation.

If the salt was actually provided by the client, then it could be used to prevent man-in-the-middle replay attacks. But there may be better ways to achieve this.


Am I on the right track with reversing DJB2 (can it be reversed?)? Is there some way of finding the remainder of a large number that has been modded by 232?

You were on a right track to explain why it can't be easily inverted.

Given an arbitrary $h_i$, every letter of the alphabet will give you another potential $h_{i-1}$ that the value was before that letter was concatenated. Subtract the letter's value, then invert the multiply. That's a possible hash of some string.

Just six or seven letters will allow you to construct most numbers modulo $2^{32}$ as hash values. For strings longer than that it is impossible to tell what the last letter could have been just from looking at the possible hash values before that letter.

Unless you know the strings are very short, trying to invert the function is unlikely to give you much better performance than an exhaustive search such as you'd need to run for a cryptographically strong hash function. I.e. guess strings that match your expected pattern and see if they give the same hash value.


In what way does using a 256-bit key rather than a 512-bit key with HMAC-SHA-512 decrease its security strength?

It doesn't, in any real sense.  With a 256 bit key, it can be broken by searching through a key space of size $2^{256}$; a simple computation on the energy required to do such a search shows that it is ludicrous (and is the source of the 'Dyson Sphere' comment made by CodesInChaos).

If we assume that the attacker had a working reliable Quantum Computer, he could, in theory, attack the system by performing $O(2^{128})$ HMAC-SHA512 evaluations, which is still not very practical, but not nearly as ludicrous.  However, to achieve such a 'low' number of computations, he would have to perform those computations serially (which would extend the total time taken to do the search to something longer than the current age of the universe).  Yes, he could speed things up by using multiple parallel Quantum Computers, but it turns out that drastically increases the already huge number of evaluations required.

There is no known way to attack the system with any less effort; hence the system is quite secure against any even remotely plausible attacker.


Proving the right encrypted message was sent

A simple way to achieve this is with asymmetric cryptography, by letting both Alice and then Bob broadcast a message to the network with the shared private key. This message should be a digital signature, proving that both Alice and Bob have knowledge of that private key.


Symmetric : Generate new key from old ones

Yes, this idea is good, even though it's usually considered with only one key from which you derive all your following keys.

The "some sort of hash" you describe here, actually is commonly referred to by the name of "key-based key derivation function" (KBKDF) with the most famous instantiation being HKDF, which will also replace the TLS specific counter-part in TLS 1.3.

As for why one doesn't actually use the "cycling idea" your propose here, this has two reasons: a) You have to keep a lot of secret keys secret if you want to have a large $N$ and have $N$ independent keys and b) this solution is worse than simply hashing all $N$ keys in one go (combined with some identifier to ensure uniqueness) and use the derived value, because if only a portion of the keys (i.e. one) is leaked, the corresponding follow-up key is in danger whereas with a full hash nothing bad happens because there's still enough entropy left.

As for why this sort of key-derivation is useful:

Backward secrecy. If your current encryption keys get leaked, an attacker can only predict the ones you'll use in the future but can't recover the old ones.
Key rotation. Rotating the keys limits the number of plaintext-ciphertext pairs an attacker can obtain under the same key which is crucial for most cryptanaltic attacks on block ciphers.


What exactly is the purpose of the multi-tree variant in hash-based schemes?

What exactly is the purpose of the multi-tree variant in hash-based signature schemes?

The biggest reason for using a multitree variant is to keep the public key generation time reasonable, even if the upper limit on the number of signatures is huge.
With a single Merkle tree, the value of the root is a function of all the Winternitz public keys.  That is, if we wanted to create single Merkle tree that could sign (say) a trillion (circa $2^{40}$) messages, we would need to compute all $2^{40}$ WOTS public keys.  And, if a single WOTS public key requires a thousand hash computations (say, with LMS and W=16; XMSS would take about three times as many hash computations), we're looking at $2^{50}$ hash computations - that takes too long for most purposes.
In contrast, if we have multiple levels of trees, we only need to compute the top level Merkle tree; if that's a $h=20$ tree, then the same public key computation would take $2^{30}$ hash computations - still quite a lot, but far more feasible.
Of course, as we sign all trillion messages, we'll need to generate all trillion WOTS public keys as a part of that process.  However, the vast part of that computation can be done as a part of the trillion signature operations we'll (adding a small fixed cost to each one), and hence is never a large burden to an one operation.


You need to know something about the plaintexts and their structure for an attack, otherwise (more precisely: if you have to assume the $p_i$ are uniform distributed and truly random) knowing $s_1,...s_{11}$ is the very same as having $11$ one-time-pads for the same message (consider $k$ the message and $p_1$ to $p_11$ the keys) - which is still perfectly secure.

If you know for example that the plaintext is English words encoded in ASCII, then you can identify probabilities for the Xor of two plaintexts and start there. However, in that exercise you might be challenged just to try out different things, if they don't tell you anything else. Your best bet is so calculate all $s_i \oplus s_j$ with $i \neq j$ and compare this distribution to the XOR of symbols of natural language.


Attack on textbook RSA with small messages

The attacker sees $E(2^{100}\cdot m) = (2^{100} \cdot m)^e \,(N) = 2^{100e} \cdot m^e \,(N)$. The attacker can compute $A = 2^{100e} \,(N)$ from public parameters, so he can also compute $A^{-1} \,(N)$ (if not he would already have a factor of $N$). So he then knows $m^e \,(N) = E(2^{100}\cdot m) \cdot A^{-1} \,(N)$ and you can apply the previous attack. This abuses the homeomorphic property of RSA.


How do I encrypt a bunch of messages by different authors, shared with that group of people?

There are many ways to solve that problem. I would like to tell you my first ideas:

Create a protocol, so that everyone shares the same key. With this key everyone can decrypt the file, write stuff, and the encrypt it again. It is a symmetric approach, but you public key infrastructure may be good to share the key (e.g. Diffie Hellman key exchange. This can also be used for groups). This idea is similar to group chats of messengers. Therefore you could inform yourself, how known messenger apps solve it.

If we assume that they communicate circular ( A -> B -> C -> D -> A -> etc. ) you could only use public key crypto: Just give everyone a public key to decrypt and a private key to encrypt. A writes the file, decrypts it with the public key of B and sends it B. B can encrypt it, write stuff, etc.

What can be a problem is the point that Edgar also wants to know the previous messages. In idea 2. it's simple: Just add him to the circle. For idea 1 it's a bit more complex. When you add Edgar you want to create a new symmetric key. Therefore someone in the remaining network can decrypt the file first, then produce the new key and afterwards share the encrypted file (with new key) again.
Anyway: There are a lot of methods to solve your problem and for most applications performance is very important. Therefore in practice you want to choose the solution which is fastest, cheapest and still provides security.
I hope I way able to help you!


TLS/SSL's usage of Non-Ephemeral DH vs DHE

A Diffie-Hellman key agreement has the following general form, presuming it is done in a group $G$ of order $q$ with generator $g$:

$A$: Generate $x \in \mathbb{Z}_q$ at random. Calculate $X = g^x$
$B$: Generate $y \in \mathbb{Z}_q$ at random. Calculate $Y = g^y$
$A \to B$: $X$
$B \to A$: $Y$
$A$: Calculate $S = Y^x$
$B$: Calculate $S = X^y$

First question: The certificate of $A$ contains the public key $X$ and a reference to the group $G$. The group might either be explicitly specified (as is common in the case of DH) or referenced by an identifier (as is common in the case of ECDH). The corresponding private key is the secret exponent $x$. Note that such certificates are rare; most commercial certificates contain RSA public key and might not be used for DH or ECDH (obviously).

Second question: No. If static-DH/ECDH or ephemeral-static-DH/ECDH is used, at least one party will always use the same private key. If that private key is apprehended by an adversary, all prior shared secrets that involve the key pair that private key belongs to, might be calculated from the protocol messages.

Third question: The security of RSA key transport trivially requires that the client (who generates and sends the RSA encrypted pre master secret) has access to a good (pseudo) random number generator. This is true for all attack scenarios; if the client random generator is compromised, RSA key transport will provide no secrecy. For DH/ECDH on the other hand, there are attack scenarios where the client doesn't even need a random generator.

Fourth question: AFAIK DH/ECDH are rare for SSL/TLS, because they require that the server has a DH/EC certificate, and those are rare.


In Paillier homomorphism, how do you deal with bit length?

What you're missing is the fact that your $c$ value can get waaay beyond what the library is expecting there and thus issues an error which can be read as "your value is too large".

The solution is simple: Reduce the multiplication result $\bmod N^2$, where $N=pq$ is the actual value of your modulus.

The code-line which you would need to add there would then be

 c=c.remained(p.getNsquare())

after the multiplication.


Can you use the same key to provide a signature and a MAC?

The usual meaning of signature (in cryptography) is this:

Bob has a pair of keys, a public and a private one. The public one is known to Alice, too. (And to any possible attackers, too.)
Bob wants to send a message to Alice.
Bob does some operation with the message and his private key (he signs the message), and obtains a signature.
Bob sends message and signature to Alice.
Alice does some operation with message, signature and the public key and can verify these fit together, i.e. that the message really was signed by Bob.

The usual meaning of a MAC (message authentication code) is this:

Bob and Alice have a shared secret key.
Bob wants to send a message to Alice.
Bob does some operation with the message and the secret key, and obtains a MAC.
Bob sends message and MAC to Alice.
Alice does some operation with message, MAC and the secret key and can verify these fit together, i.e. that the message really was sent by Bob. (Actually, as she knows the key, too, she can only verify that "the message was sent by Bob or Alice", and has to know by some other means that this was not her own message.)

How could they use the same key to produce a MAC and a signature? We could use one of the signature keys for the MAC:

If this would be Bob's private key, Alice would need to know it too for verification, and then it wouldn't be private anymore. (And Bob would be able to forge Alice's signatures, too.)
If they used the public key, then anyone knowing it would be able to forge the MAC.

Both are not good ideas, normally.

There might be a way to do something similar, though. For example, if both Alice and Bob have a key pair, they might be able to calculate a shared secret from both (e.g. using the Diffie-Hellman key exchange if these are discrete-log-type key pairs), and use this shared result for a MAC. At the same time, Bob might use his private key to sign the message.


Where is Challenge/Response and Certifcate Verification in TLS-DHE

Aside: that diagram is only correct (or nearly) for TLS 1.0 through 1.2, not 1.3. It mentions, without explanation, the number 3.2, which is the internal version for TLS 1.1, suggesting it is intended to match that version, for the two DHE key exhanges (DHE_RSA and DHE_DSS). But it references CDH, which usually means Cofactor Diffie-Hellman, which TLS does not use -- and in that step it doesn't show $p,g$ as parameters which for these protocols they definitely are. (In 1.3 they still are, but via predefined curves which could be considered the 'source'.) 1.0 and 1.2 are identical for most of the handshake, but vary slightly in the second part of the (shared) key derivation.

Diffie Hellman Key Exchange
I am fairly certain that this Part can be found in the Exchange of SKE and CKE, since they contain the public Key with Signatures and can be used by the other party to derive a shared key

Basically, yes. SKE contains the parameters (p,g) and publickey which this calls Y but the RFCs call Y_s; CKE contains publickey here X but in RFCs Y_c. The server also provides a signature in SKE, and the client may provide a signature in CV (adjacent to but not in CKE); while these contribute to the overall handshake they don't contribute to DH itself.

Challenge/Response
I am having trouble identifying this part. Since this part is usually something you would do before exchange a key, i reccon it can only occur in the Part with the CH. However, i fail to see how CH (CHallenge?) is a challenge for the Server S, because usually challenges are solved by using private information

First, the all-caps and mostly-caps items (other than SID = Session Identifier, PRF, and CDH) are clearly abbreviations of the TLS message types:
CH = Client Hello
SH = Server Hello
SKE = Server Key Exchange
CRT = Certificate
CReq = Certificate Request
SHD = Server Hello Done
CKE = Client Key Exchange
CV = Certificate Verify
CCS = Change Cipher Spec
FIN = Finished
See e.g. the summary diagram in RFC 4346 7.3 at page 33.  Note Creq in server's first flight, and CRT and CV in client's second flight, are shown in brackets, indicating they are optional; this corresponds to asterisks in the RFC summary diagram.
There are two challenges in the TLS handshake: the client and server randoms, shown here as $r_C$ and $r_S$. These are included in the data signed (server always, client sometimes, as above), and the (shared) key derivation, and the Finished message values (which MAC the handshake).

Certificate Verify
I know the Certificate consists of Public Key and digital Signature, but how can a Certificate be authenticated here without having established a shared secret yet? I do not see any Certification Authority here as well, so i am clueless

Certificate verification and validation (terms which are often interchanged, although a distinction can be made) as applied to TLS includes several steps, and I'm not sure which your teacher intends you to cover. First off, a certificate (of the type relevant here) contains a publickey and signature, but also much other information. And the cert itself is not authenticated, rather it is used to authenticate something else -- in TLS the server is almost always authenticated by a certificate, and the client sometimes (but rarely) is. And although TLS connections almost always use cert-based authentication, strictly speaking it isn't part of the TLS protocol: TLS only conveys the cert data, leaving its processing up to the relying endpoint(s). TLS can also convey certificate 'status' (i.e. revocation) information, in the form of pre-generated OCSP responses; this is called 'stapling' and has become very common since about 2012, but is not in your diagram. And while each certificate is issued by a Certificate Authority, and the related CRL and/or OCSP information either by or on behalf of the CA, the CA is not involved in the TLS protocol.
For a basic explanation of cert chain usage and validation for HTTPS see my old answer to this Q. A bit more formally:

every certificate is issued and signed by a CA; in practice your server's cert is not signed directly by a root CA, instead there is at least one intermediate CA in between, and the list of certs from your server's cert (or client's when used) through the intermediate(s) to the root is called a chain

each certificate below the root in a chain is verified by verifying its signature using the publickey from the next cert in the chain or the root; and checking a number of items in the certificate data, see RFC5280 section 6; and checking for revocation, for which there are several options, and expiration

the set of root CAs that are trusted can be defined separately for each relier, although typically a system-provided or browser-provided default is used; the root CA information is usually stored as a series of self-signed certficates (although this isn't strictly necessary, see e.g. the Java CertPathValidator API) and called a 'truststore'

for some TLS applications like HTTPS, the name in the 'leaf' (end-entity) certificate for the server is checked to make sure it identifies the correct server (the one the client wanted to connect to)


Diffie-Hellman key size to symmetric formula?

Your intuition is correct: for the same security parameter, the size of asymetric keys of symmetric keys is (at least) proportional to twice the size of a symetric key, or equivalently, 2^{sym. key} is proportional to the square root of 2^{asym. key}.

The reason for that is that symetric cryptography does not need any particular structure for the operations involved - in fact, it tries to avoid any kind of structure. As a consequence, a symetric scheme with a key of size k will be bruteforced in time O(2^k), by searching for all the possible keys.

Asymetric schemes, however, do heavily rely on algebraic structure. And this structure gives more power to an adversary: a computational problem in a group of order p with no more structure (a generic group) can be solve in time O(sqrt(p)). This is related to the birthday paradox. A classical example is Shank's baby-step giant-step algorithm (or its space-efficient variant, the Rho-Pollard algorithm), which allows to solve the discrete logarithm problem in a group of size p in time O(sqrt(p)).

Hence, if your public key scheme works over a group, you cannot avoid using keys at least twice bigger than in the symetric case. This size of the keys will be sufficient if there is no better attack than the generic attack (the baby-step giant-step approach) in the group you use. This is the case, for exemple, for well-chosen elliptic curves; hence the ElGamal cryptosystem over suitable ellipic curves might use keys "only" twice bigger than standard symetric keys. But in some other groups, like finite fields, or the RSA group, the group has more structure than a "generic" group, and there exist way better attacks on problems, such as factorization and discrete logarithm, than the baby-step giant-step attack. Hence, for cryptosystems based on such groups, the keys will in general be way bigger - and that time, the recommanded size of the key does simply depends on the best know attack.


Does seemingly random output imply irreversibility in hash function?

Now my question is if a hash function has this property: for small changes in inputs it outputs such numbers that will seem random so that from output it will be hard to determine changes in input, does it imply any of the above property specially property 1, i.e. irreversibility of cryptographic hash function?

No. Randomness is hard to test and it's easy to use any of the non-secure random number generators to generate random looking output. So anything that is "non-random" is certainly not irreversible because of just that.

  Putting slight differently is it possible to train a hash function from input and output if outputs are not seemingly random so that for given output I will know input?

That's kind of the opposite. But if you just take $H'(x) = H(x) | 1$ then it should be clear that $H'(x)$ is as irreversible as $H(x)$, while the output is clearly not random.


Substitution ciphers amended with cipher block chaining: susceptible to frequency analysis?

CBC in this context means that each letter of the ciphertext is used to help encrypt the next letter.
Let's say, making up some numbers, that a certain ciphertext letter is C. The next plaintext letter is T. So to encrypt it, we will add C (or 2) to T, giving V. Then we do the substitution step, which could be anything and happens to be J.
The key observation here is that every time there is a C in the ciphertext, the next letter goes through the same thing. Plus two, substitute. And every time you find a C in the ciphertext, the next letter all Ts go to Js.
The break, then, is to go through the ciphertext looking for Cs. Then you write down all the letters that immediately follow. You get 200 Rs, 160 Js, whatever it is. So you can conclude that after a C, E is probably mapping to R and T is probably mapping to J.
Do the same thing with other letters: everything following Ds, everything following Es, and so on. You'll have 26 different sets of letters to do frequency analysis on. And once you have done them, you'll know the substitution several times over.


The process in the picture shows nothing about authentication

You are correct in that explicit signatures are never sent, however the exchange involves so-called implicit signatures. You will note that the derivation of the shared secret relies not only on the ephemeral session keys $(x,X)$ and $(y,Y)$, but also the long-term authentication keys $(a,A)$ and $(b,B)$. The concept then is to create a system where knowledge of both $x$ and $a$ is required for Alice to construct the correct shared secret. If either party does not know both the private keys, then they will disagree on the established secret, and thus the exchange will fail.
The importance of this in AKE is that we construct a scheme which retains many of the desirable traits of ephemeral key exchange whilst still having a long-term key which can be used as the basis for a certificate. If the protocol succeeds (assuming there are no good attacks on MQV), the parties can be assured that they know the correstponding private keys to their long-term public keys $A,B$.

Besides, a man-in-middle can impersonate B to negotiate with A, because A does not verify the identity of B.

You're correct; the scheme in its raw form, without a trusted third party, is vulnerable to someone simply publishing their own long-term keys whilst purporting to be a legitimate party. However, this is not the purpose of authenticated key exchange in the form presented here. The purpose of authenticated key exchange as presented here is to verify private key ownership, which is different to identity. Much like how a digital signature does not actually prove that Alice signed something, only that someone who knows the private key corresponding to the public key you believe to be Alice's signed it.
We can construct a system which verifies identity from a system that verifies private key ownership with the aid of certificates and a T3P in the form of a CA.
This is not to say there are not attacks on MQV which can undermine some aspects of its intended goals
B. Kaliski showed that MQV is vulnerable to a Unknown Key Share attack whereby Eve can trick two participants into performing a key exchange where:

Alice knows she is performing a key exchange with Bob
Bob thinks he is performing a key exchange with Eve

Note that Eve does not actually discover the shared secret, and this can be mitigated with a key confirmation step, where participants prove to each other that they know the shared secret, but the MQV protocol does not force this. HMQV is a version of the protocol which aims to stop the attack whilst not requiring explicit key confirmation.