In the Lecture Notes on Cryptography of Goldwasser and Bellare, one can find (page 35) the following text:

Recall that f(x) does not necessarily hide everything about x even if f is a one-way function. E.g. if f is the RSA function then it preserves the Jacobi symbol of x, and if f is the discrete logarithm function EXP then it is easy to compute the least significant bit of x from f(x) by a simple Legendre symbol calculation. Yet, it seems likely that there is at least one bit about x which is hard to “guess” from f(x), given that x in its entirety is hard to compute. The question is: can we point to specific bits of x which are hard to compute, and how hard to compute are they. The answer is encouraging. A number of results are known which give a particular bit of x which is hard to guess given f(x) for some particular f’s such as RSA and the discrete logarithm function. We will survey these results in subsequent sections.
More generally, we call a predicate about x which is impossible to compute from f(x) better than guessing it at random a hard-core predicate for f.

So a predicate over $x$ is "a bit of $x$". Not necessarily a bit in the sense of "$x$ can be represented as a sequence of bits"; rather, a function which, from $x$, returns 0 or 1. The predicate is thus a function which "says something" about $x$ where the something is a binary choice.
For instance, over plain integers, "is multiple of 7" is a predicate (any integer is multiple of 7, or not).
A hard-core predicate of a function $f$ is a predicate of $x$ (an input to $f$) which can easily be computed from $x$ but not from $f(x)$. There are very trivial hard-core predicates when the information is simply lost (e.g. if $f(x)$ is defined as "SHA-256 of $y$ where $y$ is the bit sequence of $x$ with the first bit removed" then the predicate "first bit of $x$" cannot, by definition, be recomputed from $f(x)$); these are not interesting for cryptography. More interesting are predicates which do have a well-defined value for a given $f(x)$ (i.e. for a given value $z$, the predicate $b(x)$ has always the same value for all $x$ such that $f(x) = z$).
One example of hard-core predicate is in the BBS pseudo-random generator. Let $n = pq$ a big integer (like a RSA modulus), where both $p$ and $q$ are equal to $3$ modulo $4$. Consider the subset of integers modulo $n$ which are coprime to $n$ and are quadratic residues (a quadratic residue is a value $x$ such that there exists an integer $y$ such that $y^2 \equiv x \mod n$; in plain words, it is "a value which has at least one square root"). It can be shown that a quadratic residue (coprime to $n$) has 4 distinct square roots, and exactly one of them is itself a quadratic residue.
Thus, we can define the function $f(x) = x^2 \mod n$. It is a permutation of the quadratic residues modulo $n$. For a given quadratic residue $y$, there is a single quadratic residue $x$ such that $f(x) = y$.
Now, the predicate: I define $b(x)$ to be the XOR of all the bits of the binary representation of $x$. It returns 0 or 1 (it is a predicate). Given $x$, computing it is trivial. However, given $f(x)$ (i.e. $x^2 \mod n$), computing $b(x)$ appears to be as hard as factoring $n$. If you can factor $n$, you can compute $x$ from $x^2$ and thus computing $b(x)$ becomes easy; the strange part is that there is no known better way to compute $b(x)$ given $x^2$. The predicate $b$ is then said to capture the essence of the one-wayness of $f$: given the output of $f$, not only is it hard to find the matching input, but "only" finding the XOR of the bits of the input is already as hard as that.
Thus, we call the predicate "hard-core".
It is like saying that to invade the USA you have to defeat the whole of fighting-able US citizens, one of them being Chuck Norris. It is reasonable to assume that if you can beat Chuck Norris, then the rest of them should be a piece of cake. Chuck Norris is the hard-core predicate of US military supremacy.


Why doesn't any cryptographic library apply the Lehman's method?

I think the question really is: why don't cryptographic libraries generating RSA keys check if $p$ and $q$ are such that $N$ would be easily to factorize by Lehman's method?
That's because the probability that this stands are negligible. One way to prove this is to establish that Lehman's method overall has cost $O(N^{1/3})$ for random distribution of $p$ and $q$ with whatever limit the generation method has, like $\max(p,q)<2\min(p,q)$. GNFS and Lentra's ECM factorization are more credible ways to factor such $N$, and the later has to an even higher degree than Lehman's method the characteristic of having probability of success grow progressively with effort. So why bother with a test against Lehman's method when a rational adversary would skip Lehman's method in favor of GNFS or ECM?
Then one can ask: so why do some cryptographic libraries generating RSA keys check if $\lvert p–q\rvert$ is above some bound, apparently to protect against Fermat's factorization method? That's because it's a way to check some failure modes of the prime generator, including returning a constant value. And because $\lvert p–q\rvert>2^{(n_\text{len}/2)–100}$ is mandated by FIPS 186-4, section B.3.1, item 2(d).
But why is there this check in FIPS 186-4? I guess that's essentially because it's been in the earlier ANSI X9.31:1988, combined with it's indirect way of checking some horrible RNG failure, and the unlikeliness that it would harm (even in a side-channel attack).
But why is there this check in ANSI X9.31:1988? My understanding is that's bowing to request of some member(s) of the committee, sponsored by bankers, who wanted to show that every reasonable precaution was taken. Based on my memory of what Bob Silverman (who stood at this committee and was instrumental in writing the standard) has reported, the rationale was to make it harder for a lawyer to repudiate an RSA signature in court, by a wrong but superficially credible argument on the tune of: these "RSA signatures" are not admissible evidence! It was not taken reasonable precautions to make the factorization of the modulus $N$ difficult. Look, even some algorithm known to XVIIth century mathematician Pierre de Fermat could have been used to forge that "signature" thing opposed to my client!


I think you're confused about the module boundaries (so to speak) between the symmetric algorithms and the random number generator.

Symmetric algorithms generally expect some of their inputs to be randomly selected.  For example, symmetric algorithms generally expect secret keys to be randomly selected.  Some algorithms also want you to supply non-secret, randomly selected nonces or initial values (IVs).

But those are preconditions that the algorithms expect you to meet before you call them.  The mechanism for generating random values is external to them.

Here's a silly car analogy.  If symmetric algorithms are like cars, then random numbers are like fuel and random number generators are like refineries:

Cars use fuel, and fuel is made in refineries, but neither the fuel nor the refinery are parts of the car.
The car's function depends on the composition of the fuel, but not really on the design of the refinery—as long as it produces appropriate fuel, any refinery is fine.

Symmetric algorithms can be fed randomness directly from a random number generator, but very often they're "fueled" indirectly from intermediate sources that use an RNG.  The most significant of these is the Diffie-Hellman key exchange.

You may enjoy reading chapter 9 of Ferguson, Schneier and Kohno's Cryptography Engineering, which happens to be the one available as a free sample, which motivates and details the design of one cryptographic random number generator design, at an informal, introductory level.


A public key ultimately needs to be securely exchanged out of band to fulfill the commitment part of the signature process.

Typically the public key is pre-distributed where it needs to be used. As an example, your web browser comes pre-installed with the public keys it needs to validate certificates signed by certificate authorities. This can be used to obtain new public keys that are not pre-installed.

You are probably looking for Public Key Infrastructure (PKI).


If M0, and M1 are any 2 m-bit messages, how is it possible that their encryption be equal b?

The definition does not say that their encryption is equal b. It says that the function f outputs b. This function is often called distinguisher (or attacker) and he should not be able to distinguish which message M0 or M1 was encrypted. In other words there exists no distinguisher who can distinguish which message was encrypted better than with probability of guessing (0.5).


Can an encryption method be used as a hash function?

Provably secure cryptographic hash functions are often built using the same sort of operations as what are used in asymmetric crypto. The major problem with these constructions are that they are very inefficient. Also, a lot of these sorts of constructions have finite input domains. Thus, you have to figure out how to extend it to arbitrary length inputs.

Now, on to your specific construction. I wouldn't use it, inefficiencies aside. How do I know that you destroyed your private key? If you didn't, likely you would have a great advantage in breaking some of the properties listed above.


Is there any way to have a coded string such that it can be decoded in multiple ways?

Maybe this example is only remotely related to the question, but anyway:

VeraCrypt application for encrypting computer's disks has an ability to offer part of the disk capacity to reach the plausible deniability with the help of 2 different passwords:

the first one unlocks so called outer volume with a non-important content,
the second one unlocks inner, hidden volume with the important content.

So both passwords are used in the same manner (in a command or a dialog box) and only by choosing between them decides which content will be accessible.


LFSR get output from characteristic polynomial?

The variable of a polynomial is traditionally noted $x$, not $X$; and, when dealing with LFSRs, the polynomial is seldom considered a function. Thus I'll rewrite the polynomial as $P(x)=x^4+x^3+1$, a polynomial of degree $n=4$.

This is a polynomial with coefficients in the field $\operatorname{GF}(2)$, also noted $\mathbb Z_2$ or $(\{0,1\},+,\cdot)$ [note: in $\operatorname{GF}(2)$, $1+1=0$, and $-$ is the same as $+$]. The polynomial's coefficients are all either $0$ or $1$, and not shown: a term $x^j$ is present when its coefficient is $1$, and absent when its coefficient is $0$. When performing polynomial arithmetic, we are manipulating polynomials irrespective of the value and domain of their variable and result, unless otherwise stated.

The state of the LFSR is a polynomial $S(x)$ with coefficients in $\operatorname{GF}(2)$ of degree at most $n-1$, but can also be thought as:

A vector of $n$ bits $(s_0,s_1,\dots,s_{n-1})$ that are the coefficients of $S$ starting from the constant term going up to higher order terms, that is with $S(x)=\sum_{j=0}^{n-1}s_j\cdot x^j$ with the convention that $x^0=1$;
The integer $\hat S=\sum_{j=0}^{n-1}s_j\cdot 2^j$; addition of polynomials becomes bitwise eXclusive-OR, and multiplication of polynomials becomes carry-less multiplication [performed as binary multiplication, but replacing additions with bitwise eXclusive-OR]; the same integer can be defined as $\hat S=S(2)$ [note: here we are considering $S$ as a polynomial function over $\mathbb Z$].

The next state of the LFSR is, by definition, the remainder of the polynomial division of the polynomial $x\cdot S(x)$ by the polynomial $P(x)$, noted $\big(x\cdot S(x)\big)\bmod P(x)$.
By definition of polynomial division, the remainder of the division of polynomial $T(x)$ by non-zero polynomial $P(x)$ is the polynomial $R(x)$ of degree less than $P(x)$ such that there exists a polynomial $Q(x)$ with $T(x)=P(x)\cdot Q(x)+R(x)$.
In the context of moving to the next step of a LFSR, $Q(x)$ is either $Q(x)=1$ [when $S$ is of degree $n-1$] or $Q(x)=0$ [otherwise]; thus the next state $\big(x\cdot S(x)\big)\bmod P(x)$ is either $x\cdot S(x)+P(x)$ [when $S$ is of degree $n-1$] or $x\cdot S(x)$ [otherwise].

For example, if the initial state of the LFSR is $S_0(x)=x^2$,

the first non-initial state is $S_1(x)=\big(x\cdot S_0(x)\big)\bmod P(x)=\big(x\cdot x^2\big)\bmod P(x)=x^3\bmod P(x)=x^3$.
the second non-initial state is $S_2(x)=\big(x\cdot S_1(x)\big)\bmod P(x)$ that is $\big(x\cdot x^3\big)\bmod P(x)=x^4\bmod P(x)=x^3+1$, with the last step because $x^4=P(x)\cdot Q(x)+x^3+1$ with $Q(x)=1$, and we can obtain $x^3+1$ as $x^4+P(x)=x^4+x^4+x^3+1=x^3+1$.
$S_3(x)=\big(x\cdot S_2(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x\big)\bmod P(x)=x^4+x+P(x)=x^3+x+1$.
$S_4(x)=\big(x\cdot S_3(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x^2+x\big)\bmod P(x)=x^4+x^2+x+P(x)=x^3+x^2+x+1$.
$S_5(x)=\big(x\cdot S_4(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x^2+x+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x^3+x^2+x\big)\bmod P(x)=x^4+x^3+x^2+x+P(x)=x^2+x+1$.
$S_6(x)=\big(x\cdot S_5(x)\big)\bmod P(x)=\Big(x\cdot\big(x^2+x+1\big)\Big)\bmod P(x)$ that is $\big(x^3+x^2+x\big)\bmod P(x)=x^3+x^2+x$.

It is easy to perform the same calculation using either bit vectors, or integers, and that's practice in most computer programs. With integers, we define $\hat P=P(2)$ [that is $\hat P=\text{0x19}$ with our $P(x)$], and the state following $\hat S$ with $0\le \hat S<2^n$ is whichever of $(2\cdot\hat S)\oplus \hat P$ or $2\cdot\hat S$ is less [or, equivalently, less than $2^n$], where $\oplus$ is bitwise eXclusive-OR [operator ^ in C].

One common definition of the output of the LFSR is the coefficient of the term of degree $n-1$ in the states of the LFSR. The constant term is also popular when the reduction polynomial $P(x)$ has a constant term, which is the case in practice. Sometime [especially with the later convention], the initial state is not taken in consideration.

In the above example, the output of the LFSR [including the initial state $S_0(x)=x^2$] is thus
$0$, $1$, $1$, $1$, $1$, $0$, $1$...

Sometime it is used a reflected representation, where state $S(x)$ is represented by the integer $\check S=\sum_{j=0}^{n-1}s_j\cdot 2^{n-1-j}=2^{n-1}\cdot S(1/2)$ [note: here we are considering $S$ as a polynomial function over $\mathbb Q$].
This allows obtaining the output as the low-order bit of the integer representing the state [rather than its bit of rank $n-1$, which might be less easy to isolate]; and makes it possible to compute the next state without any test, using only common operators on unsigned words of size at least $n$ bits, using the C expression
S = (S>>1) ^ (P & -(S&1))
where P is $\check P=\lfloor2^{n-1}\cdot\big(P(1/2)\big)\rfloor$ [that is P of $9$ with our $P(x)$] and fits an unsigned word; >> is unsigned right shift [that's >>> in Java]; & is bitwise AND; and by definition of unary operator - over unsigned words, -U is the unsigned word such that the sum of U and -U is divisible by the smallest power of two that is not representable as an unsigned word [that's the definition of unary operator - using Two's-complement].

For example, starting from the same $S_0(x)=x^2$ and P of $9$, we have S taking the values $2$, $1$, $9$, $13$, $15$, $14$, $7$.. when applying S = (S>>1) ^ (P & -(S&1)) repeatedly, and the same output $0$, $1$, $1$, $1$, $1$, $0$, $1$.. obtained as S&1.

If we are able to do with bit vectors or integers rather than with polynomials, why are we using polynomials, even in theory?

One important reason is that $S_{i+1}=\big(x\cdot S_i(x)\big)\bmod P(x)$ gives $S_i=\big(x^i\cdot S_i(x)\big)\bmod P(x)=\Big(\big(x^i\bmod P(x)\big)\cdot S_i(x)\Big)\bmod P(x)$, and that's key to computing the $i^\text{th}$ state in time $\mathcal O(\log i)$ rather than $\mathcal O(i)$, and linking the period of the generator to properties of $P(x)$.

The schematic in the question (where the first + in reading order is a XOR gate with output on the left, and any other + is just a wire) at first does not seem to be matching what's above in this answer, which applies to the so-called Galois construction of a LFSR. That drawing uses the Fibonacci construction of a LFSR.

The two constructions give the same output, but starting from a different state. The state of a Fibonacci LFSR of degree $n$ [with polynomial $P(x)$ having a constant term] is the first $n$ bits output by the Galois LFSR with the the same polynomial [or that polynomial reflected, depending on definition of a Fibonacci LFSR].

For nice schematics of gate realizations of the two kinds of LFSR, see here.


AES-256 is a function from a 256-bit key and a 128-bit plaintext block to a 128-bit ciphertext block.  Same key and plaintext, same ciphertext.

But it is unlikely that your application uses AES-256 directly—most applications don't, because most applications are concerned with encrypting messages, not with permuting the set of strings of 128 bits.  From the information you've given, there's no way for us to know how you use AES-256, or even if you do use it directly, whether there's an application bug that just causes some wrong IP address to be stored or retrieved or causes some IP addresses to be dropped on the floor.


Hash algorithm with the least chance for collision

As Richie Frame noted in the comments, you basically listed them in order of ascending collision resistance.

The latter hashes have greater collision resistance due to their increased output size. With the exception of SHA-1 and MD5, this is denoted by the number in the name of the algorithm. For example, SHA-512 produces 512 bits of output.

The size of the output influences the collision resistance due to the birthday paradox.

To quote Wikipedia:

  The "birthday paradox" places an upper bound on collision resistance: if a hash function produces N bits of output, an attacker who computes only $2^{N/2}$ (or $ \sqrt{2^N}$) hash operations on random input is likely to find two matching outputs.

So SHA-512 should have the greatest theoretical collision resistance.

Note that MD5 and SHA1 should probably not be selected as a candidate when developing anything new and should only be used for compatibility purposes when required.

The SHA-2 algorithms calculate their digests in an almost identical manner, so generally we assume they are equally secure, digest sizes aside.


Is it possible for a simulator to always abort?

This is very strange, and somewhat suspect. The abort here is one that prevents the client from getting output. However, the real-world adversary may behave in a way that the client does get output. I suggest writing to the authors to ask and/or going through this very carefully. Without having gone through the details at all, my initial guess is that this doesn't seem right. Having said that, I didn't check it at all (and this section does say "Initial...", so maybe this is just part of the simulation).


How do the constants in this implementation of AES match up with the algorithm?

The tables represent the composition of some of the routines from the round function. These tables are used because they facilitate an efficient implementation. These slides and the "Advanced Implementation" section this blog post do a good job of explaining. The table based implementation was also mentioned in the Rijndael AES proposal as well, if I recall correctly.


El Gamal Cryptosystem Proof, Step-by-Step Explanation Needed. I feel like I don't understand what I have on this proof

First, we should make clear what we're proving here. The derivation you're showing is part of a proof of correctness of ElGamal encryption, not security.

Perfect correctness (also referred to as completeness) of a public key encryption scheme is defined as follows.

Let $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be a public key encryption scheme. The scheme is said to be perfectly correct if it holds that for any security parameter $n\in\mathbb{N}$, any key pair $(\mathsf{ek},\mathsf{dk})\gets\mathsf{Gen}(1^n)$, any message $m$ from the message space, and any ciphertext $c \gets \mathsf{Enc}(\mathsf{ek},m)$ it holds that $\mathsf{Dec}(\mathsf{dk},c)=m$.

To see whether ElGamal encryption is correct, we first recall the definition of ElGamal encryption. I will try to follow the notation in your notes as close as possible. From the notes it's not clear what kind of group is being used. But $e_1$ is a generator of some subgroup of $\mathbb{Z}_p^*$. Let $q$ be the order of that subgroup. (If $e_1$ is a generator of $\mathbb{Z}_p^*$, then $q=p-1$, if we are in a safe prime setting, then $q=(p-1)/2$ and prime.

\begin{align}
&\mathsf{Gen}(1^n) && \mathsf{Enc}(e_2,P) && \mathsf{Dec}(d,(c_1,c_2))\\
&d\gets\mathbb{Z}_q&&r \gets \mathbb{Z}_q&&P' := c_2\cdot (c_1^d)^{-1} \bmod p\\
&e_2 := e_1^d \bmod p&&c_1:= e_1^r\bmod p&&\text{return }P'\\
&\text{return } (e_2,d)&&c_2 := P\cdot e_2^r\bmod p&\\
&&&\text{return } (c_1,c_2)&&\\
\end{align}

To verify that the scheme is correct, we need to verify that for any choice of key pair, and message it always holds that $\mathsf{Dec}(d,\mathsf{Enc}(e_2,P)) = P$. This is where the derivation you're looking at comes in.

\begin{align}
 P' =& c_2\cdot (c_1^d)^{-1} \bmod p \tag{1}\\
=& c_2\cdot (e_1^{rd})^{-1} \bmod p\tag{2}\\
=& P\cdot e_2^r\cdot (e_1^{rd})^{-1} \bmod p\tag{3}\\
=& P\cdot e_1^{rd}\cdot (e_1^{rd})^{-1} \bmod p\tag{4}\\
=& P\cdot e_1^{rd}\cdot e_1^{-rd} \bmod p\tag{5}\\
=& P\cdot e_1^{rd-rd} \bmod p\tag{6}\\
=& P \bmod p\tag{7}\\
\end{align}

Now let's go through this line by line.

In line (1) we simply have the definition of the decryption algorithm.
In line (2) we use the definition of $c_1 = e_1^r\bmod p$ from the encryption algorithm and replace $c_1$ by its definition.
In line (3) we do exactly the same with $c_2$ and replace it with its definition $c_2 := P\cdot e_2^r\bmod p$ from the encryption algorithm.
In line (4) we now look at the key generation algorithm and replace $e_2$ by its definition from there $e_2 := e_1^d \bmod p$. Note that we have not changed anything. We have simply replaced the variables $c_1,c_2,e_2$ by their respective definitions.
In line (5) we use a basic rule of exponentiation, namely that $(x^a)^b = x^{a\cdot b}$, therefore $(e_1^{rd})^{-1} = e_1^{-rd}$.
In line (6) we again use a basic rule of exponentiation, namely that $x^a\cdot x^b = x^{a+ b}$, therefore $e_1^{rd}\cdot e_1^{-rd} = e_1^{rd-rd}$.
Since $rd-rd=0$ and anything raised to the $0$th power equals the identity, we are left with $P\cdot 1 \bmod p$ and thereby, since $1$ is the identity of the group with $P$ in line (7).

Since this derivation makes no assumptions whatsoever about $P,d,e_2,c_1$ and $c_2$, besides that they were generated according to the above definition of ElGamal encryption, it holds for any choice of key-pair and any plaintext $P$.

The derivation thus shows that decryption always works and results in the same plaintext that was encrypted, thus showing that the encryption scheme is in fact correct.

What it does not show is anything about the security of the scheme.


How to calculate leaked information from a check digit

Assuming the mod 11 check digit is among 0123456789X, disclosing it reduces the number of possible plaintexts among 8-digit numbers by a factor of about 11 (from 100000000 to about 9090909; exactly how much depends very slightly on the value of the check digit), thus reveals about $\log_2(11)$ bits of information about the plaintext, that is just a little less than 3.46 bits.

The consequences vary depending on context. If the goal of an adversary is to rule out that a plaintext is a certain value, there are about 10 chances out of 11 that knowing the check digit allows the adversary to succeed.

In the hypothesis of "a single 3DES encrypted CBC block for which the check digit of the plaintext is known" because it is used to derive an IV using a deterministic method allowing to recover that check digit (as in the example where the IV is the MD5 hash of the check digit, truncated to 8 bytes), the worse problem might not be that the check digit is revealed by the IV. Another serious issue is that the same plaintext is always enciphered to the same ciphertext, which is foremost among what an IV is designed to prevent. If that's tolerable, we could just as well use 3DES in ECB mode on a single block, and live happier with a simpler system using no IV, and leaking less about the plaintext.

Knowing the check digit of the plaintext does not much help recovering the key. In the example, the key can best be found by enumerating the candidate keys (assumed to be the MD5 hash of a small string of decimal digits), and deciphering the ciphertext until the plaintext makes sense. The check digit still helps, in that it reduces the (already remote) odds of guessing the wrong key, by a factor of 11; however another ciphertext helps even more in this regard.


What is the recommended number of iterations for Argon2?

I'm wondering what the recommended number of iterations would be?

Unlike bcrypt or traditional crypt, argon2 does not have a single iteration count, but three parameters affecting the computational cost:

Number of iterations $t$, affecting the time cost.
Size of memory used $m$, affecting the memory cost.
Number of threads $h$, affecting the degree of parallelism.

In addition there are two versions of argon2: argon2d uses data-dependent accesses for presumably stronger tradeoff resistance, while argon2i eschews them to avoid side channel attacks. The latter is recommended for password-hashing.

The argon2 paper gives the following procedure (paraphrased) for determining the parameters you should use:

Figure out how many threads you can use, choose $h$ accordingly.
Figure out how much memory you can use, choose $m$ accordingly.
Decide on the maximum time $x$ you can spend on it, choose the largest $t$ such that it takes less than $x$ with your system and other parameter choices.

I.e. they recommend you run it on your system and decide the largest parameters that match your limits on memory and processor time use.


Why does Carter-Wegman MAC have 2n-bit output?

The MAC consists of the pair of the n-bit random value $r$ and the n-bit value $t = F(k_1,r) \oplus S(k_2,m)$. The length of $(r,t)$ is at least $2n$ bits, partly depending on how it is encoded. If the two values are simply concatenated, the total length is $2n$, as stipulated.


diffie hellman digital signatures vs MACs

The homework task is making an implicit assumption:

They don't have a common shared secret.

That's implicated by the fact that they do a DH key exchange and nothing else to exchange the key. A common shared secret would offer muc more possibilities, e.g. combine a DH key exchange with the shared secret as input to a KDF.

You realized yourself that a shared secret is required for MAC. So what protects the DH  key exchange from man-in-the-middle attacks? Because (not-authenticated) DH key exchange is vulnerable to that.


What is the signifcance of inside threat in "How to Construct Multicast Cryptosystems ... Secure Against CCA2"

The "significance of inside attacker or threat" is making the problem non-trivial.

We "should we care about it in this case" because the

protocol apparently claims to provide some sort of revocation.


The only published faster-than-brute-force preimage attack I can find is this one from 2009 by Yu Sasaki and Kazumaro Aoki.

From their abstract:

  This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage
  of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5.
  The memory complexity of the attack is $2^{45}\times 11$ words.

In short, this is not practical at all.


There are very few non-trivial proven lower bounds in computational complexity, and none whatsoever in cryptography, as far as I know.

Almost all results are of the form "If X is infeasible, then so is Y." For example, "If AES is a secure pseudo-random function, then so is CBC-AES given parameters such-and-such."

RSA and traditional Diffie-Hellman use integers and finite fields (integers modulo a prime). Those mathematical objects have, in some ways, "too much structure"; there are short cuts to factoring and to discrete log, so you have to use much larger keys than you would expect if you did not know about those short cuts.

As far as anyone knows, elliptic curves have "just enough" structure to do cryptography, but no additional structure that can be exploited to extract discrete logarithms via some short cut. That is why the number of bits for EC algorithms is generally chosen to be something like twice the symmetric key length, instead of something like 2048+ bits for RSA.

If you want some mathematical details, this thesis has a good overview:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.6034&rep=rep1&type=pdf

But again, none of these problems have been proven to be intractable. Maybe there is some linear-time factoring algorithm out there. Maybe elliptic curves -- or the particular curves approved by NIST -- have some unknown structure that could allow discrete log approaches with comparable complexity to those for finite fields. Maybe the NSA's mathematicians have found that structure ahead of everybody else...


There seem to be no standardized ElGamal test vectors available in the public domain.  However, there are some ElGamal test vectors generated with libgcrypt 1.5.0 available in this fork of the pycrypto project.


Decrypting DES with decrypted and encrypted data

Do you know anything at all about the key?  If not, then what you have is a "Known plaintext attack" - you know the cyphertext is 16 05 78 B0 0A C2 78 7F and the plaintext is FF FF FF FF FF FF FF FF.

DES has some weaknesses, but it isn't that weak.  A cypher that can be cracked with a mere 8 bytes of plaintext/cyphertext would be very weak indeed.

Can you generate more cyphertext/plaintext pairs if you want to?  That might allow you to use linear attacks and differential attacks.

Apart from that, you will have to try to brute force all possible keys and see which one works.


Does such an entity exist?

No, not really.  There isn't any organizations who's in the business of doing public cryptanalysis, and there certainly aren't any organizations that are sufficiently trusted for the cryptographical community to say "we know algorithm X is secure - organization Y said so".

Let's go through the likely suspects:

NSA (and other TLAs) - they have the internal resources to do a decent cryptanalysis, and while it's not guaranteed to catch everything, they'll catch most weaknesses.  However, they are certainly not in the business of soliciting contributions, they are most certainly not interested in publishing their results, and even if they did, no one would trust that they're revealing all that they know.
NIST (and other standards bodies) - you might think otherwise, but they typically don't have the resources to do an exhaustive analysis themselves (NIST, at least, does have the resources to analyze results found by other people, but they don't pretend to have the wherewithal to do it entirely in house).
IACR - actually, the IACR is not in the business of doing cryptography; instead, they're there to promote cryptographical research in others (and they do a very fine job at that IMHO).  If you want to organize a cryptographical conference, the IACR might be of some help; if you want some cryptanalysis done, well, the best the IACR can do is point you at some relevant researchers.
Private organizations - I believe that there a few companies that will accept submissions, and publish analysis on them (for pay); however at present, most of them consist of a single researcher who will do analysis for hire.  Not horrid; however they don't have the "clear credentials" that everyone will accept as weighty (assuming, of course, that they don't find anything).

You appear to be wondering "there's CAVP and CMVP, which people accept; why isn't there the analogue for cryptanalysis?".  Well, CAVP and CMVP is mostly a list of checkboxes; the reviewer has a list of requirements (things like: encrypt this AES block with this key; did you get that result); meet all those requirements, and you'll get the certification.

Cryptanalysis can't be put into such a checklist - instead, the analyst needs to figure out if there are any clever ways to break the system - it's hard to put cleverness as a checkbox item.

And, ultimately that's why there aren't any 'trusted organization'; even if someone where to say 'looks secure to me', there's always the possibility that someone else would find something.  The best we have is have a lot of independent people look at it; it's possible that everyone missed something, but it's less likely.


None.

When enciphering any small set of values (including a fair coin flip, a byte, even a small password..), unpadded RSA (or RSA with any padding that does not include randomness) is a terminally weak encryption method: the adversary can enumerate the possible plaintext values, encrypt them using the public key, and check against the ciphertext to determine if the candidate plaintext value being enumerated is the right one.


Meaning of Dilithium-1024x768 or Dilithium2

1024 and 768 refer to the dimension of the base "generator" matrix $A$, these numbers are multiples of 256, which is the size of the module ring.
If the terminology is a bit confusing so far, then let me explain a little:

$A$ is a component of the public key, it's computed from a random seed chosen during key generation. It's also used in signing and verification.

Dilithium (along with Kyber, Saber, and some others) uses a "modular" lattice. That is, instead of a polynomial ring, or a matrix of integers, they use a matrix of high-dimension polynomial ring (degree-256 in the case of Dilithium and Kyber, etc.). This greatly improves performance and the scalability of the security level.

Some may question: "didn't document say $(k,l) = (4,4)$ (or $(4,3)$ in earlier versions)?". That's true, and those numbers are referring to when you consider module ring as matrix element. If you expand the ring modules into 256-by-256 matrices, the full matrix will be 1024-by-768. And for those familiar with lattice-reduction attacks, 4 is obviously too small a dimension that can be easily attacked.
As for "2", I'm not certain. Maybe it just refers to the version of Dilithium submitted to NIST in the 2nd round.


Alright, let's first agree on a few things:

The rsa_private operation is the operation requiring knowledge of the secret RSA key. This operation is required by one of the following processes:

RSA signature, to ensure authenticity and integrity of a given message in a way publicly verifiable
RSA decryption, to decrypt a message which was sent to you, encrypted with your public key,
more rarely, it might also be used to encrypt a message so that it can be decrypted by anybody knowing your public key. This latest usage is disputable since it provided nothing more than a signature.

In RSA, randomness is required at different stages:

When signing, with RSA-PSS (the provably secure RSA signature scheme), you'll need randomness in the PSS-encoding operation.
When encrypting, with RSA-OAEP (the provably secure RSA encryption scheme), you'll need randomness in the OAEP encoding operation.
When performing blinding on RSA operation, the blind is randomly generated.

Now, you're asking about how you could be generating your randomness without entropy, and you mentioned a PRNG, the key, and $m^d$, so I'll assume you only need randomness for RSA decryption, and to blind it.

Remark that it is not the same kind of properties that one would expect from
a PRNG used in a masking scheme and a PRNG used for keys generation. When you are masking something, the PRNG mainly requires uniform distribution and other such good statistical properties. But it does not necessarily require to be a cryptographically secure PRNG. This is due to the fact that all generated values are supposed to be a secret, so you mostly require a good initial entropy source... Which could contradict your current requirements.

In my opinion, generating your randomness out of (part of) your secret key, plus the message (typically by hashing the concatenation of (part of) your secret key together with the message), is providing you with a seed that an attacker could not possibly guess without knowing your private key, so there is no security risk there.

Furthermore by definition, the private key can be considered as a good entropy source, since its generation requires good entropy and the security of the RSA scheme crucially relies on the randomness used when generating the key pair.

The method of using (part of) the private key is actually already used by EdDSA for example to deterministically generate a secret nonce, whose disclosure would allow for private key material recovery.

Now, you asked:

  And if so should it be seeded by message+key or key alone? Or does the blinding need to be unpredictable?

And as I tried to explain, the private key can be considered as a good entropy source, but this is only a one-time entropy source, so if you simply seed your PRNG using the private key, and there is a way to reset the device so that it would get seeded again with that same private key, then there would be a way to get every new RSA operations to be conducted using the same random values, which actually means that you could not rely on your random values as being nonces, and the same mask would always get generated after $x$ calls to the just seeded PRNG...

One solution against this would have to be sure you can rely on a counter and seed your PRNG with the hash of your private key concatenated with that counter.
Finally, taking even more "pseudo-entropy" by also adding in the message value cannot hurt.

Fixed randomness certainly hurts, but the question is to which extent?

You didn't mentioned why and how you wanted to perform blinding, but let's say you are trying to protect against timings or power analysis (or such side-channel) attacks, and you are using blinding.

Now, it all depends on how you actually do the blinding, if you perform simple blinding by tacking a random $r$ value, computing $r^e\bmod n$ and then decrypting the message $m^e=c$ by doing $(r^ec)^d \bmod n$ and multiplying your result by $r^{-1} \bmod n$, then you really want to take a different $r$ for each computation, even of the same message, since otherwise, you would leak the secret value $d$, since the attacks target recovery of the exponent used.

Now, if you have another way to blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing:
$(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem...
So in the end, you really want to have a different blind for each computation.

Notice that relying on a counter means that if an attacker is able to reset that counter, then the attacker can cause the PRNG to repeat itself, which brought us back to the problem of using fixed blinds... But this might not be a problem for you, depending on the fact whether the attacker is supposed to have access, or not, to the device.

By the way, since you mentioned those, attacks against both common $m^d$ and CRT implementations exist, see most notably:

  P. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA,
  DSS and Other Systems. In: N. Koblitz (ed.): Crypto 1996, Springer,
  Lecture Notes in Computer Science 1109, Heidelberg 1996, 104–113.

  W. Schindler: A Timing Attack against RSA with the Chinese Remainder
  Theorem. In: Ç.K. Koç, C. Paar (eds.): Cryptographic Hardware and
  Embedded Systems — CHES 2000, Springer, Lecture Notes in Computer
  Science 1965, Berlin 2000, 110–125.

Finally, let me add a word regarding side-channels such as SPA and DPA: if you are using a vulnerable exponentiation algorithm (e.g. plain square and multiply, see maybe this paper for more info), SPA cannot be prevented using just masking, it depends more on your exponentiation algorithm. Timing attacks and DPA are both working if the attacker is able to gather enough traces which are correlated, so they should be defeated by using masking, as long as you avoid fixed masks.


Homomorphic Encryption vs. Garbled circuits

There has been work on using garbled circuits while also hiding the function. This can be done via implementing a universal circuit inside the garbled circuit. However, the standard garbled circuit does reveal the topology of the circuit. Also, when considering malicious security, the most efficient method is cut-and-choose, and this reveals the actual circuit. When you need to hide the function, then you need to take care of this explicitly (e.g., via a universal circuit, as mentioned). Here is one paper by Mohassel and Sadeghian that considers this question.

Beyond this, there are many differences between FHE and secure computation. In general, FHE is one way of getting secure computation, but it can also be used in other settings where secure computation is not applicable (e.g., when you cannot have interaction). However, FHE is not yet efficient enough for most tasks, and garbled circuits is much much faster. Having said this, in some cases, it suffices to use somewhat FHE (which works for low-depth circuits), and this can be very fast.


i think “ Introduction to Modern Cryptography “ by Jonathan Katz and
Yehuda Lindell is a very good book for your requirements.
you could also try "Foundations of Cryptography” by Oded Goldreich.


Does anyone know why NISTs SHA3 256 output Hash for the 1600 bit file is different to other SHA3 256 output hashes?

NIST gave the 1600-bit input as a bit-string, with each byte in LSb first bit order. So 1 1 0 0 0 1 0 1 is A3, not C5 as one would expect.


Raw signature of public key vs full certificate

X509 certificates contain a lot of additional (management) data that is required to manage the PKI. If you do not require interoperability, you do not need this extensive structure. However, you might want to go through the basic fields of an X509 certificate and think over if you really do not need each of these fields. E.g., you might want the ID of the device signed together with the public key. You also might want a validity period assigned to a key pair and so on. You could also have a look at WAP or CVC certificates. These are more compact than X509 certs.


Is encryption time greater than decryption time?

It depends.  Specifically, it depends on the type of cipher, and on the way it's used.

For stream ciphers like RC4, and for block ciphers like AES in CTR and OFB modes, decryption is effectively identical to encryption, and thus takes the exact same time.  (Minor exception: encryption may require generating a unique nonce / IV, which might take a small amount of extra time.)

For block ciphers in CFB mode, encryption must be done sequentially (since each cipher block depends on the previous one), but decryption can be parallelized.  Thus, on a multi-core implementation, CFB decryption is typically faster than encryption.

The same is also true for CBC mode, but there's an additional quirk: CBC mode decryption requires using the block cipher in inverse ("decryption") mode (CTR, OFB and CFB all use the block cipher only in forward direction, even for decryption).  For some block ciphers (notably including many implementations of AES), using the cipher in the inverse direction may be somewhat slower than the forward direction e.g. due to asymmetries in the key schedule.  Thus, on systems that support parallel decryption, CBC decryption is typically faster than encryption, but on systems that don't, it may be slightly slower.

Finally, for block ciphers in ECB mode (which is insecure for most purposes, and so should not be used), the only difference between encryption and decryption is the direction the block cipher is used in.  Thus, as noted above, decryption may be slightly slower than encryption (although, of course, you could always decide to swap the directions if you want).

Of course, in modern cryptography, you really should be using an authenticated encryption mode.  Many of these (like GCM, EAX, CCM, etc.) are essentially based on a combination of CTR mode and a MAC; since CTR decryption is identical to CTR encryption, and since the MAC is computed the same way in either case, the total time for encryption and decryption should be approximately the same.

That said, there are, again, some exceptions.  For example, for SIV mode encryption, the MAC must be computed (to generate the synthetic IV) before encryption can begin, whereas for SIV decryption, the MAC can be computed (mostly) in parallel.  Thus, for SIV mode, encryption may be up to twice as slow as decryption.  (Of course, this is by wall clock time; the CPU time consumed should still be approximately the same for both directions.)

Finally, for asymmetric encryption (RSA, (EC)IES, etc.), the difference could really go either way.

For RSA specifically, decryption is typically slower than encryption; that's because both RSA encryption and decryption involve modular exponentiation, but whereas the public encryption exponent is normally small and fixed (usually either 3 or 216+1 = 65,537), the secret decryption exponent is usually almost as long as the modulus.  Thus, doubling the modulus size makes encryption take twice as long, but makes decryption take four times as long.  Using the Chinese Remainder Theorem does speed up RSA decryption, but only by a factor of about four (as it effectively halves the size of the numbers one needs to work with) at most.

Conversely, for ECIES, encryption requires generating a random number and computing two scalar multiplications, and is thus generally slower than decryption, which only requires a single scalar multiplication.

In any case, asymmetric encryption of large messages is typically done using hybrid encryption, where the message is first encrypted using a symmetric cipher, using a random key, and the random key is then encrypted asymmetrically.  Thus, for large enough messages, most of the time will be spent on symmetric encryption anyway.


Security implication of deriving key with fixed salt for files authentication

For that purpose, are there some security implications having that
  salt as a fixed byte string?

The key re-use is fine here, because the standard model for MACs allows the attacker to request an arbitrary (polynomially bounded) amount of authenticated messages while still not being able to forge new MACs.

As a bonus, you may want to consider using the built-in MAC mode for Blake2, because it reduces code complexity and improves speed while providing a comparable security level (thanks to Richie here)


In ECDSA, why are u and v dividing by s?

In the actual ECDSA, $(r,s)$ is called the signature of the message $m$ whose hash is $z$ i.e. $z=H(m)$.
By removing $z$ from the equation, you have completely eliminated any correlation of this "new incorrect signature" (which isn't even a signature) with the message, which is completely against the notion of a digital signature being a representative of the message which has been signed. If digital signatures did not depend on the messages, then anyone could just strip off a signature by someone, say $A$, from one message and use this signature to sign any document of their choice without $A$ even knowing.
In ECDSA, it is the $s$ value which is coupled with the message hash $z$, so if the $s$ value is completely independent of $z$ (and therefore $m$), then (r,s) is not at all a signature. It is then just a random linear equation between 2 points on an elliptic curve.


(You should take a look at page 18 of FIPS 197 where it describes the MixColumns transform).

You're close. Swap the order of your matrices so that you have:

|02 03 01 01| |d4 e0 b8 1e|
|01 02 03 01| |bf b4 41 27|
|01 01 02 03| |5d 52 11 98|
|03 01 01 02| |30 ae f1 e5|

And then you compute the new columns. i.e. the new first column is:

|02 03 01 01| |d4|
|01 02 03 01| |bf|
|01 01 02 03| |5d|
|03 01 01 02| |30|

Which equals:

|02*d4 + 03*bf + 01*5d + 01*30|
|01*d4 + 02*bf + 03*5d + 01*30|
|01*d4 + 01*bf + 02*5d + 03*30|
|03*d4 + 01*bf + 01*5d + 02*30|

And so on.

Do you See the pattern in the sum? Each column in the matrix is multiplied by an element in the column and then they are summed. We can precompute these columns, and compute the above sum using 4 table lookups and 32-bit XOR operations.

The tables will be arrays of 32-bit values which look like this ("|" denotes byte concatenation):

T0[00] = 02*00 | 01*00 | 01*00 | 03*00
T0[01] = 02*01 | 01*01 | 01*01 | 03*00
...
T0[FF] = 02*FF | 01*FF | 01*FF | 03*FF

T1[00] = 03*00 | 02*00 | 01*00 | 01*00
T1[01] = 03*01 | 02*01 | 01*01 | 01*01
...
T1[FF] = 03*FF | 02*FF | 01*FF | 01*FF

T2[00] = 01*00 | 03*00 | 02*00 | 01*00
T2[01] = 01*01 | 03*00 | 02*00 | 01*00
...
T2[FF] = 01*FF | 03*FF | 02*FF | 01*FF

T3[00] = 01*00 | 01*00 | 03*00 | 02*00
T3[01] = 01*01 | 01*01 | 03*01 | 02*01
...
T3[FF] = 01*FF | 01*FF | 03*FF | 02*FF

Using four tables, you can compute the new state matrix with 16 table look-ups and 12 32-bit XOR operations.


Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. –  xagawa

  @xagawa Yes, I want that :-) –  Dingo13

I list the PRFs based on the number-theoretical assumptions.
They are ``arithmetic or mathematical function.''
You can use the Feistel network to obtain (S)PRPs from PRFs in theory.

From the DDH assumption

The Naor-Reingold Pseudorandom Function is a PRF based on the DDH assumption.
Let $\mathbb{G}$ be a finite group of order prime $q$ with a generator $g$,
on which the DDH problem is hard.
Let $\{0,1\}^\ell$ be a domain.
The function is defined as
$$\mathrm{PRF_{NR}}(k, x) = g^{a_0 \prod_{i=1}^{\ell} a_i^{x_i}},$$
where $k = (a_0,a_1\dots,a_{\ell}) \in \mathbb{Z}_q^{\ell}$.
For the proof, see the original article in J. ACM.

Lewko and Waters generalized the NR PRFs in CCS 2009 (and ePrint 2009/486).
Their PRFs are based on the decisional linear assumption (and its weaker variants).

Most efficient one

Under stronger assumptions such as the DHI assumption,
 we have a cute PRF, say,
the Dodis-Yampolskiy PRF proposed as
Verifiable Random Function (VRF).

Let $\{0,1\}^{\ell}$ be the domain of PRF.
Suppose that $2^{\ell}$ is a polynoimal of the security parameter.
The DY PRF is defined on a symmetric bilinear group as follows:
$$\mathrm{PRF}_{DY}(k,x) = e(g,g)^{1/(x+k)},$$
where $k \in \mathbb{Z}_q$.

From the factoring assumption

This is a classical result obtained by a combining the Blum-Blum-Shub PRG and the Goldreich-Goldwasser-Micali PRF from any PRG.
Naor, Reingold, and Rosen improved efficiency of factoring-based PRFs.
See the original article available at ECCC TR 2001-064,

From the hardness of lattice problems

Nowadays, the lattice problems are often employed to construct cryptogrphic primitives.
You can find the PRFs from lattices in
Banerjee, Peikert, and Rosen (EUROCRYPT 2012),
Alwen, Krenn, Pietrzak, and Wichs (CRYPTO 2013),
and Banerjee and Peikert (ePrint 2014/074).


How was AES Encryption cracked on my app?

If the characters are from $[A..Z]$ and $[0..9]$ then that makes 39 possibilities per character (byte). Then the keyspace will be $39^{16}$ and that is approximately 83-bit. This is space is achievable with supercomputers but not for ordinary people. Therefore, there must be something else around that cracks your system.

Used key & IV which was only plain text length of 16

That is not a good way.

The IV must random, though, your mode of operation is not clear therefore we cannot recommend the exact usage. In short, we can say that a (key,IV) pair must be used only once. You can use Android's secure random to generate the random IV.

For the key, one should go for the diceware or Bip39 to have good strength on the password. The user can still have a longer character than 16 so that at least 128-bit strength is achieved. With the password, the memory-hard password hashing algorithms like Argon2 to reduce the attack capability of the attackers.

Key not hashed with SHA-256

SHA-256 is not a password hashing algorithm we have Scrypt, PBKDF2, and Argon2 for those kinds of problems.

It was an Android app ( Xamarin Forms) and I did not obfuscate the app

This sentence indicates that probably you hardcoded the key into your application. And the attacker resolved the key by getting the package and analyzed the reversed byte code. This is not the correct way to store a cryptographic key.
If you want to communicate with your server use DHKE with your server to create the session key and possibly the IV by using the full exchanged key with HKDF. Then apply AES-GCM or ChaCha20-Poly1305 to achieve the authenticated encryption. In this way, you don't need to store secret keys. You only need the public key of your server. With this, you can achieve, forward secrecy, confidentiality, integrity, and authentication.
If you want to use app-in encryption, then get the password with a good strength from the user and derive the encryption key by using Argon2id.
You may also have the benefit of using the Android-KeyStore if that fits your needs.

updates

[Update] This app is reading information from QR Code encrypted content. An attacker able to create a QR Code with fake information that becomes a valid QR code

As Fgrieu mentioned that you can use a signed QR. To check the signature one only needs a public key.

If the content doesn't need to be encrypted, then there is no need for an encryption key.

If encryption is required, one can either install the key later and store it in the key-store or use a server-client approach so that the device doesn't use the key at all. The client either gets the key temporality from the server, or it can use the server as a decryption oracle while using a secure channel as told above.

[Update] The app needs to operate in offline mode. That's why I hardcode keys in the application

Installing the key later is the solution. You can install the key either manually in Android activity or use a specially designed QR code to read in then store it in the Android Key-Store.


IND-CCA insecurity of modified CBC encrypt + MAC scheme

One security issue that comes to mind is that the tag of a message in this scheme relies only on the last block of ciphertext, not the rest of the message.

So, what would happen if the adversary took a valid $⟨c, \tau⟩$ pair and modified $c$ by repeating the last block, that is, converting it into the pair $⟨c || c^*, \tau⟩$ and forwarding that to the decryptor?
Would the modified ciphertext pass the integrity check?
Bonus question (to make the attack even worse): if it did, what would the resulting plaintext look like?


Quoting from RFC 4492

  All ECDH calculations (including parameter and key generation as well
   as the shared secret calculation) are performed according to [IEEE 1363, 2000]
   using the ECKAS-DH1 scheme with the identity map as key derivation    function (KDF), so that the premaster secret is the x-coordinate of    the ECDH shared secret elliptic curve point represented as an octet    string.  Note that this octet string (Z in IEEE 1363 terminology) as  output by FE2OSP, the Field Element to Octet String Conversion    Primitive, has constant length for any given field; leading zeros found in this octet string MUST NOT be truncated.

More specifically, it is the byte count of the prime of the Elliptic Curve Field that you are using to exchange your keys.


How "hard" it is to take an e'th root mod p?

It is  very easy.
$gcd(e,p-1)=1$ so there exist $k,t$ where $ek+t(p-1)=1$. Let $x$ be the $e$-th root of $y$, so $x^e=y \bmod p$.

$y^k=x^{ek}=x\cdot {(x^{p-1})}^{-t}=x \bmod p$.

Also in decryption of RSA we use this method.


Removing Padded Value in Decrypted Message

How you remove padding after decryption depends on how padding was added before encryption.

Typically, we design padding methods so that it is easy to figure out exactly how much padding was added; see This article for an overview.

From your question, it sounds like the encryptor is doing zero padding (that is, adding zero bytes until the next block boundary); if you can assume that the message will never end in a zero byte, then it is easy to remove.  If you can't make that assumption, it sounds like you may need to switch to another padding method; the one in RFC5652 is one common method.


How to realize a hash function H:{0,1}* × G × {0,1}* -> Zq ？

If elements $R$ of $G$ can uniquely be expressed as a bitstring $\overline R$ (e.g. by taking the two components in a finite field of the affine coordinates of $R$, each uniquely representable as a fixed-size bitstring, and these are concatenated to form $\overline R$), then it is easy to construct a generic hash $H:\{0,1\}^* \times G \times \{0,1\}^* \to \mathbb Z_q$ from a standard $b$-bit hash $F:\{0,1\}^* \to \{0,1\}^b$, say SHA-512 with $b=512$, as follows:

$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$, which is a hash of $(\text{ID},R,\text{RN})$ in the set $\{0,1\}^b$
if $\log_2q>b/2\,$, expand $h$ as follows:

$g\gets h$
for $i$ from $1$ to $\big\lceil(\log_2q-b/2)/b\big\rceil\,$

$h\gets h\mathbin\|F(g\mathbin\|\overline i)\,$, where $\overline i$ is a bitstring uniquely representing the integer $i\,$ (e.g. encoding $i$ in big-endian base 256 as a minimal number of bytes, then converted to binary)

$r\gets \underline h\bmod q\,$, where $\underline h$ is the integer coded by the bitstring $h$ per big-endian binary

The result $r$ is the desired hash of $(\text{ID},R,\text{RN})$ in the set $\mathbb Z_q$.
This hash has nearly the same security as $F$ or an ideal hash in $\mathbb Z_q$, whichever is lower. Argument (or lack of a reference), under a model of the hash $F$ as a random oracle (and any security reduction is is with respect to that):

The step "$h\gets F\big(F(\text{ID})\mathbin\|F(\overline R)\mathbin\|F(\text{RN})\big)$" is a generic composition of hashes, in order to hash multiple inputs of variable size (while maintaining collision resistance contrary to mere concatenation), and allowing a security reduction.
The step "if $\log_2q>b/2\,$, expand $h$" does that essentially as in MGF1, again allowing a security reduction.
The step "$r\gets \underline h\bmod q\,$" insures the output is in the desired range. It create a bias towards low values, but since at least $b/2$ bits are discarded this bias is low, and it's possible to upper-bound the advantage a distinguisher can obtain.


Is packing an executable just like encrypting it?

No, packing an executable is not just like encrypting it. The difference is that to use an encrypted executable, a secret key/passphrase is necessary, beyond the method/program to do the decryption (typically public, sometime embedded). By contrast, no key is required to run a packed executable, and how to use it often reduces to: just run it as usual; a clever piece of built-in code (a self-decompressing header) will do the rest.

Yes, you can (and it is common to) encrypt a file that is already packed/compressed, including an executable, including a self-decompressing executable, perhaps even producing a self-decrypting-then-decompressing executable; however the latter is not recommendable: it works in a world of fairy where executable file format is clearly defined, is respected by the self-decompressing header, and does not trigger a bug in the self-decrypting header.

There's nothing to prevent you from trying to pack/compress a file that is already encrypted (except if you want the result directly executable and the fairy did not bless, see above). However, that will often increase the size. There are exceptions: for example, if the encryption used ASCII armor, and the packing does not, there will likely be a moderate size gain.

Some programs pack/compress, some encrypt, some do both in one use (these are typically encryption programs happening to use compression; e.g. PGP/GPG). That's true both for general files, and when it comes to executables that remain directly executable (typically, after entering a passphrase/key if encryption was performed).

From the standpoint of cryptography, packing/compression is not encryption. A virus checker, security auditor, or perhaps customs officer, might nevertheless treat a packed file or executable as if it was encrypted, on the grounds that it is not as easily amenable to scrutiny as if it was not packed, or just as the result of some poor choice.


Checking a file for integrity and authentication

This relate to the difference between authenticity and integrity.

Authenticity:
you are sure of the identities involved:
Where does the data come from?

Integrity:
you are sure that the content has not been modified:
Was there an error during the transmission?

The second is usually provide through a Checksum (such as any hash function) e.g. $$SHA-3(\ M\ )$$
while Authenticity requires a MAC (Message Authentication Code), often in a form of a HMAC or KMAC e.g.  $$SHA-3(\ K\ ||\  M\ )$$
or a signature e.g. $$ Sign_{K_{priv}}(\ SHA-3(\ M\ )\ ) $$
Remark:$$\textbf{Authenticity} \implies \textbf{Integrity}$$

As for your second question:
You have to hash the whole file, hashing sub contents will increase the workload but will provide you integrity over small part and allow you to detect which part has been corrupted.
Note:
To hash big files you might want to have a look this article: Is SHA-3 slow ?
Further readings:

What are the differences between a digital signature, a MAC and a hash?
What is the advantage of digital signatures over message authentication codes?
How is digital signature different from a message authentication code (MAC)?


Calculating ECDSA m or k (k or d) when s1 = s2

However, I'm confused by what I should do with two different messages ($e_1 \ne e_2$) with the same $s_1$ and $s_2$

Well, if we consider how $s$ is computed:
$$s_i = m^{-1} ( \text{hash}(e_i) + r \cdot k )$$
If $s_1 = s_2$, then (because the private key $k$ is the same in both cases, and $m$ (the secret nonce) and $r$ are assumed to be the same, we have $\text{hash}(e_1) = \text{hash}(e_2)$
If $e_1 \ne e_2$, that means that we have a hash collision on our hands; because the signature depends on the hash of the message (and nothing else about the message), that means that (as far as ECDSA is concerned) we're signing the same message twice, and so the attack isn't possible.


Confusion about definition of homomorphic encryption

The operation does not have to be the same. For example, with Paillier, we multiply ciphertexts to get the addition of the plaintexts.

That said, I think what the 2nd quotation is saying is that the operation that is passed to the oracle is the desired operation in the plaintext domain. The oracle knows how to translate that operation into something that, when performed on the ciphertexts, results in the desired operation in the plaintext domain.


How should the length field be handled in a cipher?

It should not be possible to simply remove or add data to a value and come to a valid MAC for a specific key, without knowing the key value. So in that sense you can get away with moving the length out of the encryption.

It would be wise to MAC the length and ciphertext for your authentication tag (MAC value). If you'd be using an authenticated (AEAD) cipher you could put the length in the Additionally Authenticated Data (AAD) input for the cipher.

Generally the length of the plaintext can be easily retrieved or guessed from the ciphertext length; it is for instance identical in CTR mode (and therefore most authenticated modes as well). So in that sense specifying the length is not a security risk. If you want to keep the size secret you must pad the plaintext before using the encryption mode of operation.

Note that you should be aware that without an overall MAC it is possible for an attacker to swap chunks around in your scheme (!). You are also missing an IV value in your scheme, although you could simply count the chunks and use the counter. This would also solve the issue with the re-ordering (but not with truncation!).


Quality test for an hardware source of randomness

NIST has a statistical test suite for testing (pseudo) random number generators.  There are a number of other suites as well, such as Diehard, Dieharder, and TestU01.

But all these tests can do is disprove the claim that your generator is random; they cannot prove it.  So you really need, in addition, an independent argument for why your generator's output really is random.  A true random number generators generally comprises of:

A entropy source that outputs digitized samples of a random process (but whose output may be neither uniform nor independent).
A nondeterministic random bit generator (NRBG) that uses the entropy source's output to produce uniform and independent random bits.

So correspondingly, you need:

An argument that your entropy source is random and that justifies a lower bound on its entropy rate (how random it is, per unit of time);
An argument that your NRBG, given the noise source's output, produces full entropy outputs (uniform and independent random bits).

And there's no "bright line" test to be had here.  You don't prove that your outputs "really are random"—you prove that the processes you're using to produce your outputs are sound, that your implementation of them reliable, that your hardware resists monitoring and interference, etc.  You also provide health check mechanisms and fallbacks to detect and guard against failures.

You may be interested in the NIST SP 800-90 series, which details standards for random number generators:

SP 800-90Ar1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators (1st revision)
SP 800-90B: Recommendation for the Entropy Sources Used for Random Bit Generation (2nd draft)
SP 800-90C: Recommendation for Random Bit Generator (RBG) Constructions (2n draft)

In particular 90B deals with the entropy sources, and parts of 90C deal with nondeterministic random bit generators (NRBGs)—algorithms designed to take the output of a noise source and produce truly random outputs.


The Salsa20 specification paper contains examples for testing for each function. quarterround 7 example, rowround 2 example, etc..
Indeed this paper is written as a tool for programmers, or the analyzers so that they can use these test vectors.

Salsa20 exists in the Crypto++ which is a C++ library originally written by Wei Dai. You can use this code to test, too.

Also, the snuffle page of the Bernstein contains code for various platforms.


Curve25519 - Alice can decrypt her own message to Bob?

However, Eve has a copy of Alice's key pair and intercepted the outgoing message.  She uses crypto_box_open and passes in pKb and sKa, the same keys that were used to encrypt the message. This yields the plain text message.  She changes the message, re-encrypts it, and sends it on to Bob.

As you correctly observed, Eve having Alice's private key is insecure. It allows Eve to decrypt and replace messages with arbitrary contents. In any public key encryption system it would allow Eve to at least replace messages, though some would not allow decryption.

An equally serious issue would be for messages going the other way. If Bob sends Alice a message, Eve who has Alices keys would be able to read and modify the message.

In short, private keys must be kept private. You cannot share a key-pair between multiple users unless they all trust each other completely. In your situation, the normal thing to do would be for each client to have their own key pair.


Also, there is CBC-MAC for providing integrity and confidentiality. Which one is better CBC-MAC or CBC with HMAC?

Generally, asking which one is better results in opinionated answers.

However, since CBC-MAC cannot be used for dynamically sized messages and may lead to compromise when the same key is used, HMAC definitely is less prone to abuse. Differently worded: CBC-MAC is more brittle than HMAC: it may break when abused.

That CBC-MAC it can still be used correctly is shown by the CCM authenticated mode of operation, which uses AES-CTR for confidentiality and AES-CBC-MAC for message integrity & authenticity. It is unwise to replace CTR mode with CBC in CCM mode because CBC with CBC-MAC is likely to introduce security vulnerabilities.

[EDIT]: I completely read over the fact that this says "integrity and confidentiality". CBC-MAC is a MAC algorithm that has been derived from the CBC mode of operation, hence the name. It does not provide confidentiality itself, it provides just message integrity and message authentication. See Luis' answer for more details. This is also why it is unwise to pair CBC and CBC-MAC (see previous section).

  And when do I need to use CBC and HMAC?

You could use it when message integrity and/or message authenticity is required on top of the confidentiality that CBC mode offers. That is: if you are afraid that the ciphertext can be altered by an adversary. Generally transport protocols require message integrity / authenticity.

However, generally we use a modern authenticated mode of operation for that. AEAD ciphers such as AES-GCM and EAX are more robust than putting CBC and HMAC together. For instance, it would be easy to forget to include the IV into the calculation of the authentication tag. If that's forgotten than the adversary can still alter the first block of ciphertext. Likewise, CBC requires an IV that is indistinguishable from random to the adversary, while most AEAD ciphers require a nonce (which could be random, but it could also be a counter).

EAX uses CMAC (or OMAC) as MAC internally. CMAC has been build on top of CBC-MAC to make it secure for dynamically sized messages. The earlier mentioned CCM mode that does use CBC-MAC is also secure, but as a packet mode cipher it can be hard to use (let alone implement, as I found out).

There is an RFC draft called Authenticated Encryption with AES-CBC and HMAC-SHA which tried to standardize CBC and HMAC as an AEAD cipher. That didn't succeed (most other modes are more efficient) but if you want to use CBC with HMAC then it shows a few best practices.


What you are envisioning has basically been standardized as the integrated encryption scheme being a hybrid encryption scheme providing message authenticity (IND-CCA security).


If you only ever use a particular OTP block to encrypt one plaintext block, there is no way to decrypt it.

However, with your approach anyone looking at multiple versions of the file will be able to tell which parts have changed. For example, if the file contained secret messages stored by users, it would leak the length of each message added. Maybe that's a problem, maybe not. Depends on your application.


Private Information Retrieval with a pre-prepared database

Efficiency of PIR largely depends whether you have a single-server or a multi-server PIR (replicate the database $n>1$ times).

Multi-server PIR seems more attractive (Ian Goldberg does a lot of research into this direction, e.g., this paper is the basis for most multi-server PIR approaches). Considering the database to be organized in a $r\times s$ matrix the client communication function of $r$ and the number of servers and the servers communication a function of $s$.

This is a recent paper on boosting the  efficiency when receiving multiple blocks in one query PIR in multi-server PIR.

What you mention (as far as I understand it) is a single-server solution and typically called hardware-assisted PIR (you may look here) and seems to be a practical alternative to multi-server PIR. Here, loosely speaking, you have a trusted component to which you send encrypted queries, this trusted party scans the entire database (typically co-located at the server for performance in form of some hardware secrutiy module) and then sends you back the encrypted query-result.


Inverting the encryption equation of a symmetric cipher

Addition modulo $N$ in the above example is another way of key mixing that adds more non-linearity to the cipher as it operates across a group of $N$ bits, vs XOR which is addition modulo 2 on individual bits. For example, where $N=2^6$ or 64:

$44 ⊞ 44 = 24$

$44 ⊕ 44 = 0$

Addition within larger groups is also used in mixing operations such as Pseudo Hadamard Transformations. Key addition instead of XOR also plays a prominent role in the block ciphers Twofish and IDEA.

Edit:
Here are posts with more detail on the choice of addition:

What exactly is addition modulo $2^{32}$ in cryptography?

Why Addition Mod 32?


How to use GCM mode and associated-data properly

GCM mode already incorporates any params that could affect the outcome of the decryption. The associated authenticated data is there to allow you to rely on context for your decryption.

For example, say you are encrypting some records associated with a user. You may want to include the user's database ID as the authenticated data. If a user found a way to copy another user's data and key into his own record, it would still fail to decrypt since his database ID is not the same.

In general, you would like it to be something that's inherently managed separately from the nonce and ciphertext.


Proof of the basic differential privacy composition theorem

You are right, we need to assume the coin toss of mechanisms are independent to each other, as stated in the proof.

You are right, again. The proof in the paper seems to be problematic. Here's the modified proof:
\begin{align}
Pr[(x_1, x_2) \in S] &= Pr[x_1 \in S_1] Pr[x_2 \in S_2 | x_1 \in S_1] \\
&\le (\min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1]) + \delta )Pr[x_1 \in S_1] \\
&\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])Pr[x_1 \in S_1] + \delta \\
&\le \min(1, e^\epsilon Pr[x_2' \in S_2 | x_1 \in S_1])(e^\epsilon Pr[x_1' \in S_1] + \delta) + \delta \\
&\le e^{2\epsilon} Pr[(x_1', x_2') \in S] + 2\delta
\end{align}

The key to avoid the problem you stated is instead of using
$$
Pr[x \in S] \le e^\epsilon Pr[x' \in S] + \delta
$$
we use
$$
Pr[x \in S] \le \min(1, e^\epsilon Pr[x' \in S]) + \delta
$$
for the inequalities.


What you describe will work once, and it will be fine to use one salt, which need not even be secret as long as it's different from everyone else's salt.  Just derive each service password from the same master key with a different HKDF info parameter.

But what happens when a site's password database is breached, and turns out not to have been hashed, and you need to generate a new password for the site?  What happens if a site imposes restrictions on the character set, length, or structure of the password?

See Tony Arcieri, ‘4 fatal flaws in deterministic password managers’, blog post, 2016-11-22 for further discussion.  (The title should perhaps have been about stateless password managers rather than deterministic ones.)


Why is the output of a True Random Number Generator (TRNG) insecure after it has been compressed?

I think you're misinterpreting the source. The source says the TRNGs "rely" on compression (a cryptographic hash would be the compression function, or possibly some simpler function to increase throughput).
The random data isn't insecure after compression, it's insecure before compression.
Why?
When you roll dice there's an equal probability of it being any one of the possible values, but let's say the dice aren't quite perfect - in nature you'll find things are almost always more like weighted dice than perfect RNGs.
If the output is biased it means it's less likely to produce certain outputs, breaking the security of an RNG - for a CSPRNG to be secure it must produce every output with equal probability, and a TRNG isn't exempt from that rule.
The solution is to take more random bytes than you plan to use, then use a compression function to merge them. It could be as simple as XORing every pair of bytes, or as thought-out as a cryptographic hash, but you need something to even out the probabilities.
That said, using a compression function like what's used to shrink your ZIP files would be an easy way to mess with the probabilities in a way you don't want, so that should be avoided, but that's not what they were referring to.


Is there a hash function with 2048bit output?

I was already wondering why you would need 2048 bits, because brute forcing a 512 bit output hash takes already a $2^{256}$ operations on average (w.r.t to collision resistance, due to the Birthday Paradox – preimage and second-preimage attacks take on average $2^{511}$ hashes), which is secure enough, for all kinds of hardware available today.

I assumed that you would probably want to transform the hash output into some form of key with a length of 2048 bits, your comment confirmed this. In that case, what you need is not necessarily a hash output of that length, but you need a secure Key Derivation Function (KDF) that allows "stretching" the random hash output to the desired size.

Have a look for example at the KDF described in NIST Special Publication 800-56A: “Recommendation for Pair-Wise
Key Establishment Schemes
Using Discrete Logarithm
Cryptography ” that describes how to stretch hash outputs to arbitrary sizes securely.

When equipped with such a KDF, it basically doesn't matter what hash function you are using (as long as it itself is secure) so you can safely use one of the sha-2 family hashes (SHA-256, 512 etc.).


Will using large keys with Classic cryptographic algorithms beat quantum computers?

For symmetric cryptography, it is highly plausible that doubling the key size compared to current practice (say from 128 to 256-bit) provides more than adequate protection against hypothetical quantum computers capable of running Grover's algorithm (or similar) on large inputs. It requires $O(2^{n/2})$ effort for $n$-bit key, compared to $O(2^n)$ for brute force key search on classical computers.

Many asymmetric cryptographic algorithms, including all those commonly used (RSA encryption and signature, Diffie–Hellman key exchange, ElGamal encryption, Schnorr signature, DSA, ECDH, ECDSA, ECIES, EdDSA..) are in principle vulnerable to an hypothetical quantum computer capable of running Shor's algorithm on large inputs, which uses resources and work only polynomial in the number of key bits $n$. That does not work on symmetric cryptography because Shor's algorithm derives the private key from the public key under assumption of arithmetic relations between them, which do not exist between symmetric key and the rest of what an adversary is expected to know in symmetric cryptography. Due to the polynomial growth, demonstrably high security would require impractically large RSA or even ECC keys; this is made quantitative in the two RSA entries of the NIST Post-Quantum Cryptography round 1.

Still, increasing the key size of common asymmetric cryptosystems does increase their resistance to hypothetical quantum computers usable for cryptanalysis. At least, that makes it necessary to use proportionally more coherent qubits, which is a hurdle. We are so far from having quantum computers useful for anything crypto-related that predictions are hard.


No, because even SHA-512 was considered overkill from a security perspective. It has 256-bit collision resistance, which is unbreakable. (The link is about keys but a similar argument applies.)

If you think large quantum computers will be efficient, a 512-bit hash makes some sense, but even then a 1024-bit one wouldn't. A quantum computer requires $O(2^{n/3})$ operations to find break the collision resistance of a secure $n$-bit hash.

Finally, SHA-256 uses 32-bit words and SHA-512 64-bit. If you wanted to use the same way to extend SHA to 1024-bit state, you would need to use 128-bit operations which are slow on practically all platforms.


Public-key encryption with associated data

There are no schemes that I'm aware of that are specifically designed for this task, i.e. where this was advertised as feature in a description I've come across.

The most standard solution I can provide is McBits (PDF). McBits is based on XSalsa20-Poly1305 and thereby can natively supports the associated data interface if enabled by the implementation. However (good) implementations of McBits are rare, although they shouldn't be too hard given a (standard) McEliece implementation.

What you can also do, is take your generic (IND-CCA2 secure) public key encryption scheme (e.g. RSA-OAEP), encrypt a symmetric key with it and use that key for the AEAD scheme of your choice (e.g. AES-GCM) to encrypt and authenticate bulk data and to authenticate header data.

The more distinguished solution is to just take the KEM of your choice (like the one used by ECIES, DHIES or RSA-KEM), use that to derive the key and then continue normally with your AEAD scheme of choice (e.g. AES-GCM). McBits basically is this with the KEM being standard McEliece encryption of a random vector.


How can I create a fixed length output in my hash function?

Basically, typical hash functions produce a fixed-length output by the following method:

They expand the input to some multiple of their block size by adding padding.
They compress the first two blocks into a single block using a mixing function and repeat until only one block is left.
The use a fixed finalizing function to turn that last block into their output.

As a simple example, consider a rather trivial and insecure hash function for decimal numbers that produces a one decimal digit output. It could work like this:

Add a 9 onto the end of the input. Then add zeroes until the number of digits is even.
If there are more than two digits, replace the first four digits with the two-digit sum of those four digits. Repeat until only two digits remain.
Sum the final two digits to get the output.

This will produce a single decimal digit of output for any decimal input.

For example, take 123.

Add a 9 on the end - 1239. The number of digits are even, so no zeroes appended.
We replace the first four digits with their sum, 15. There are two digits, we're done.
We sum the 1 and 5 to get 6. Our output is 6.

While this function is simple and insecure (because its mixing function is so bad and its block size so small) it illustrates how hash functions produce a fixed-sized output from a variable-sized input.


The wikipedia article @SEJPM links to is about as high level of an overview as you can really get. We can elaborate on some of the points.

DES is weak against Brute force in this day and age.

Actually, it was weak against brute force pretty much as soon as it was standardized. According to the wikipedia article, the cipher was standardized in 1977. Reading further, in the section about brute force attacks:

  In 1977, Diffie and Hellman proposed a machine costing an estimated US$20 million which could find a DES key in a single day.

So it is arguable that DES was never strong against brute force attacks (the standardized post-NSA consultation version anyways - originally the designers did propose a "real" key size).

Why was DES so strong originally

Let's look at the section of the article for attacks faster then brute force:

Differential cryptanalysis is one area where DES was relatively strong. It's understood that IBM and the NSA both knew about differential cryptanalysis when DES was designed, and chose to keep this information secret. There exists differential attack(s) against DES, but they are not as devastating as they are against some other ciphers (i.e. FEAL)

Resistance to differential attack is determined by differential characteristics of the S-box. The DES s-box was designed with this in mind.
A "differential" is a pair of differences: The difference between two inputs to the function, and the difference between the two corresponding outputs. The probability that this output difference occurs for a pair of inputs with the given difference is the basis for the attack.

Are there any DES specific weaknesses that can be practically exploited?

Continuing further in the same section of the article as before, they discuss linear cryptanalysis.

DES was not known to be written with defense against linear cryptanalysis in mind. It is arguable whether or not the mentioned attacks constitute a "practical" break; These attacks only require known plaintext-ciphertext pairs, which are actually not uncommon in practice (i.e. HTTP GET) and can be practical to obtain, but it does require a large number of such pairs.

It is possible to defend against linear cryptanalysis by choosing s-box values appropriately, similarly to differential cryptanalysis. "Linearity" can be a somewhat nebulous concept and difficult to understand.. Put possibly over simplified, the s-box should be as different as possible from any linear equation. Basically, it should be difficult to come up with a simple equation that accurately approximates the equation of the s-box.

DES has weak keys

A stronger key schedule should prevent weak keys
Weak keys are technically uncommon, but it's arguable that all 56 bit keys are weak

The 64 bit block size could be larger

This is technically more relevant to the security of the mode of operation used with the cipher then the cipher itself


Is concatenated data hashed with scrypt vulunarable to a length extension attack?

No, scrypt in not vulnerable to password extension attacks.

Internally, scrypt passes the password to PBKDF2, which uses it as a key for the HMAC function -- hence they've effectively already done the workaround you thought of.


Tls 1.3 ClientHello legacy_session_id as zero length vector alignment

Yes exactly. Nothing in the TLS spec is ever required to align on a boundery of a power of 2 in fact.


What is the key derivation function used in GnuPG, and how long may its input be?

What is the maximum input size of a symmetric key for GnuPG?

The key size of the symmetric key is defined by the cipher and is derived from a passphrase using OpenPGP's string to key function. The standard does not define a maximum input length, and I'm not aware of a limitation in GnuPG (but did not look up in the source code). Be aware that providing a passphrase as input to the string to key function longer than the symmetric key (ie., having more entropy than the symmetric key) does not increase security any more.

  What key derivation function does GnuPG use?

OpenPGP calls the key derivation function "string to key function", which is defined in RFC 4880, OpenPGP, String-to-Key (S2K) Specifiers. It boils down to applying a hash function on the passphrase and optionally a salt, usually those get concatenated for a number of iterations to increase the workload for brute force attacks.


Curve 25519 (X25519, Ed25519) Convert coordinates between Montgomery curve and twisted Edwards curve

The formulas actually work.
You just have to keep in mind to make computation in the field of intergers modulo $2^{255}-19$ and that there are actually two square roots, you need to use the right one if you want to have the expected result.

You can test the following SAGE code

gf=GF(2^255-19)
X_P = gf(15112221349535400772501151409588531511454012693041857206046113283949847762202)
Y_P = gf(46316835694926478169428394003475163141307993866256225615783033603165251855960)
u = (1+Y_P)/(1-Y_P)
v = gf(-486664).sqrt()*u/X_P,-(gf(-486664).sqrt())*u/X_P
print u
print v

on the Sage Cell server.


For something to be a PRF, it must be impossible for a probabilistic polynomial time algorithm to distinguish it from a random function. The distinguisher you note in your attempt is correct, as a random function would not have that property (xor two calls with the same key but different x values and you get the xor of the two x values).

As a side note, these notes are very good when it comes to PRFs. Especially 3.3 and 3.4.


Is it secure to ECDSA-sign a public key without hashing it first?

From FIPS 186-4, section 6.4

  An approved hash function, as specified in FIPS 180, shall be used during the generation of digital signatures.

Thus if the hashing step was removed, then this is no longer ECDSA. Let's call the resulting Modified signature scheme MECDSA.

MECDSA has a potential weakness: it is easily exhibited a valid MECDSA signature for message(s) $m\equiv0\pmod n$: signature $(r,s)$ with $r=s=x_A\bmod n$, where $x_A$ is the $x$ coordinate of the signer's public key $Q_A$; at verification we get $z=0$, $u_1=0$, $u_2=1$, $u_1\times G+u_2\times Q_A\,=\,Q_A$, hence $r\equiv x_1\bmod n$ and the signature verifies. With true ECDSA, it is computationally infeasible to exhibit a message hashing to $0\pmod n$, making this a non-issue.

Update: things get much worse: we can efficiently exhibit an arbitrary number of (message, signature) pairs passing verification (but there's no control on the message); see this answer.

It is not quite clear if MECDSA signs an integer $m$ or a bitstring; and the maximum $m$, or the maximum size of the bitstring:

If $m$ was an unbounded integer, the signature for $m$ would also be valid for $m+n$, where $n$ is the order of the group ($n\approx 2^{256}-2^{224}$ for curve P-256). To solve this, we'd need to restrict to $0<m<n$.
If $m$ was a bitstring of exactly as many bits as $n$, then we would also have a number of bitstrings with interchangeable signatures (about $2^{224}$ such 256-bit bitstring pairs for curve P-256).

In either case, we are slightly in trouble if the public key to sign is using the same curve as used for the ECDSA signature: the usual ("uncompressed") form of a public key is twice as wide as $n$ is; and even with point compression (which is not all that usual, and is not considered by FIPS 186-4), a public key is one bit more than $n$ is. In order to solve this, we'd need to restrict the allowable public keys (e.g. with sign bit clear, and the $x$ coordinate less than $n$, thus removing very slightly more than half of the valid public keys).

An important other issue is that signatures of public keys, also known as public key certificates, typically need attributes, like who they belong to. We could spare a few more bits for a serial number at the cost of further restrictions in the public key, but each bit spared doubles the difficulty of generating a public/private key pair. Thus in the end we might need to sign two messages instead of one, with something to link the two signed messages. That's feasible, but hairy!

With such restriction to signing messages $m$ with $0<m<n$, and non-standard form of public key or/and certificate content, carefully enforced/compensated at verification, MECDSA could be used to sign a public key. But it is clumsy, and is it safe? I'm not entirely sure. That's not a well-studied problem. I would never prescribe it, and would feel very uncomfortable endorsing or doing it, for lack of positive security argument, and because of the usability issues. Hashing is cheap (it can be done in less than 1 kByte of code), and signing hashed message is the way to go.

Addition: here is a tiny (1.2 kiB) implementation of SHA-256

// tinysha256 - a public domain, compact implementation of sha256
// input is limited to 0 to 0xffffffff octets(s) in memory
// gcc 5.3.0 for x386 with -Os compiles this to 1280 bytes
#include <stdint.h>

// hash len bytes in memory pointed by ibuf
void tinysha256(
    uint8_t         hash[32],           // result
    const uint8_t * data,               // input
    uint32_t        size                // input size
    )
    {
    uint32_t s[8] = {                   // init state
        0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19};
    uint32_t w[16];                     // data buffer
    uint32_t x;                         // warning about unitialized x can be safely ignored
    const uint8_t *e = data+size;       // end of data
    int n = 0;
    for(;;) {
        while (data!=e) {               // while there is data..
            x = (x<<8)+ *data++;        // accumulate it in x, big-endian
            if ((3&~n)==0) {            // a full 32-bit chunk
                w[n>>2] = x;
                if (n==63) {
                    n = 0;
                    goto c;             // compression
                    }
                }
            ++n;
            }
        switch(n) {                     // handle padding
        case 64:
            n = x = 0;
            break;
        case 65:
            n = 31;
            do
                hash[n] = s[n>>2]>>((3&~n)<<3);
            while(--n>=0);
            return;
        default:
            x = ((x<<8)|0x80)<<((3&~n)<<3);
            }
        w[n >>= 2] = x;
        while (++n!=14) {
            if (n==16) {                // extra compression needed
                n = 64;
                goto c;
                }
            w[n] = 0;
            }
        w[14] = (uint32_t)(size>>29);   // length padding
        w[15] = (uint32_t)(size<< 3);
        n = 65;
c:          {                           // compression
            static const uint32_t k[64] = {
                0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
                0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
                0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
                0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
                0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
                0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
                0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
                0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
                };
            uint32_t r[8];
            int j = 7;
            do
                r[j] = s[j];
            while (--j>=0);
            j = 0;
            do
                {
#define RL(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
#define S0(x)   (RL((x),30)^RL((x),19)^RL((x),10))
#define S1(x)   (RL((x),26)^RL((x),21)^RL((x),7))
#define S2(x)   (RL((x),25)^RL((x),14)^((x)>>3))
#define S3(x)   (RL((x),15)^RL((x),13)^((x)>>10))
#define S4(x,y,z) ((z)^((x)&((y)^(z))))
#define S5(x,y,z) (((x)&(y))^((z)&((x)^(y))))
                uint32_t t = r[7] + S1(r[4]) + S4(r[4], r[5], r[6]) + k[j] + w[j&15];
                r[7] = r[6]; r[6] = r[5]; r[5] = r[4]; r[4] = r[3] + t;
                r[3] = r[2]; r[2] = r[1]; r[1] = r[0]; r[0] = t + S0(r[1]) + S5(r[1], r[2], r[3]);
                w[j&15] += S3(w[(j+14)&15]) + w[(j+9)&15] + S2(w[(j+1)&15]);
                }
            while(++j!=64);
            j = 7;
            do
                s[j] += r[j];
            while (--j>=0);
            }
        }
    }


I assume that the paper you have read is the paper by Kobara and Imai in PKC 2001 (or its journal version), which proposed a padding scheme for the McEliece PKE scheme. In Lemma2, the authors showed CPA security of the padded scheme.

The first answer is NO. They are not.
Let $C(n,t) = \{z \mid z \in \{0,1\}^n, Hw(z) = t\}$, where $Hw(z)$ denotes $z$'s Hamming weight.
As the authors defined in Section 4.1, $Hash_z: \{0,1\}^* \to C(n,t)$ is a cryptographic hash function and $Gen: C(n,t) \to \{0,1\}^*$ is a PRG.
The second answer is YES. They are same.

In Lemma 2, the authors assume that there exists an adversary A "for any $Hash_z$ and $Gen$" breaking the padded scheme. Here, the authors assume that the adversary works even if we separate $Hash_z$ and $Gen$ as oracles (instead of giving their codes to the adversary). Indeed, the authors modeled $Hash_z$ and $Gen$ as the random oracles in the proof.