Would adding daily changing nulls in front of their messages have made the Engima harder to crack?

No, padding would make the message much easier to crack.  This is a great example of why cryptography is left to the professionals (I am not a professional cryptographer, I'm not even a very good amateur one).  Amateurs tend to just make things worse.

First problem is the Enigma had no way to produce a "null".  It was only capable of producing letters.

The nearest equivalent of your scheme would be to pick a letter to use as padding (for example, A) and then add that at the start of the message.  Yes, it makes it a bit harder to find the KEYKEY repetition, but not much. You just need to slide your window of six characters over a bit and cryptographers were already doing such sliding window analysis to find other cribs.

But because it's always the same letter at the start of the message it gives the cryptographer a very reliable crib.

(For this answer I'm ignoring the plugboard and rings, there were other techniques to work those out).

Let's say the Germans always put at least two padding letters before the key.  And let's be generous and say they choose a different padding letter every day.  Now the cryptographer knows at least the first 2 letters are going to be the same letter, and there's a very good chance the next letters are also the same.  This provides the cryptographer with a very small set of possible texts to work through.  Since they're right at the start of the message, they can reveal the rotor settings.

Now any setting can quickly be eliminated if decryption does not result in a message which starts with at least two identical letters.

It doesn't even do a very good job at masking the key, since it's still known that the repeated key will start somewhere in the first N characters (where N is the maximum amount of padding the Germans use).  It adds, at most, N - 1 more possibilities.

A A K E Y K E Y

A A A K E Y K E Y

A A A A K E Y K E Y

...and so on...

This is not worth the cryptography gold that is the padding.

  The British decrypted the German enigma because they knew that they would repeat the message key twice at the start of every message.

While this was the first and most important crib, and it was found by the Poles, different branches of the German government and armed forces had different procedures for using the Enigma which changed over the war. This flaw did not last long. For example, by 1937 the German Naval Enigma had already rectified this flaw but was cracked anyway.

Key repetition was just one of many the Poles and British had available to them.  "Pinches" (stealing code books) were one, but the most reliable was the methodical Germans themselves.

The cryptographers knew, for example, that certain operators would always end a message with H E I L H I T L E R, or begin a weather report with the same phrasing, or that somewhere in the message would appear the name of their unit, or location, or any number of other likely texts.

The operators also provided their own cribs.  The person encrypting the message had to come up with a key.  Humans are very bad at producing randomness.  A radio operator, possibly in the field, possibly tired, hungry, cold, has to come up with dozens of unique keys every day.  They're going to get sloppy.  The cryptographers could use this to guess what the key is likely to be, or eliminate unlikely keys (for example, it's not going to be AAA).

Furthermore, they could identify individual radio operators by how they transmitted their Morse Code, known as a "fist".  Certain operators would have certain ways of picking their keys, or certain ways of writing their messages to provide cribs, and the cryptographers could use this to their advantage.

The Enigma machine had other mathematical flaws which were exploited.  Rather than going into them here, I recommend Numberphile's excellent videos on the subject.

158,962,555,217,826,360,000 (part one)
The Flaw In The Enigma Machine (part two)
Extra Enigma Footage

In addition Simon Singh's book on code breaking, "The Code Book".


In the Diffie Hellman Key exchange, why is a value of $a=\frac{p-1}{2}$ a bad choice?

In Diffie-Hellman besides $p$ being prime, if the factorization of $p-1$ comprises at least one big prime $k$ such that $p=2k+1$ (can be also $jk+1$, this is a safe prime). In the worst case if the factorization is composed of computable factors then we can compute $x$ using the direct product of cyclic groups (Pohlig-Hellman).

Normally, if $p$ is prime and $g$ a generator with order $p-1$ then $g^{\frac{(p-1)}{2}} \equiv p-1 \equiv -1 \pmod p$

If $g$ is a generator of the subgroup of prime order $k$, where $k$ is large enough then $g^{\frac{(p-1)}{2}} \equiv g^k \equiv 1 \pmod p$

Both congruences are deterministic as you can see.

Generally, two congruences are related by symmetry, since both have the same square root mod p:

$$g^a \equiv -(g^b) \pmod p \quad \iff b = x-d, \ d = \frac{p-1}{2}$$


Perfect zero knowledge for the Schnorr protocol?

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$).

Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it to the prover. The prover computes $z = r + ue$ and sends it to the verifier. The verifier checks that $g^z = a y^e$.

Remember, (informally) a protocol is zero knowledge if for any verifier $V^*$ there exists a simulator that can create conversations with the same distribution as conversations between the honest prover and $V^*$.

Proof sketch: Our simulator chooses $z$ uniformly at random and guesses what challenge $V^*$ will issue. Based on the guess $e$, it computes its initial message $a$ as $g^z y^{-e}$. If $V^*$ chooses $e$ as its challenge, the simulator has the correct response and has created a challenge with the correct distribution. It is a fairly easy exercise to prove that it succeeds with probability $1/2$, when $V^*$ is restricted to respond with $0$ or $1$.

So Schnorr is zero knowledge when the challenge space is small (so that we can guess the challenge with significant probability), but Schnorr is also not very useful when the challenge space is small, since you need to run the protocol many times to be sure that the prover really knows the secret.

When the challenge space is large, the above simulator fails. I can't remember a proof that there cannot be a different simulator that succeeds, but no such simulator is known. Which means that while we cannot say that Schnorr is zero knowledge. On the other hand, as far as I know, we cannot say that it is not zero knowledge.

There are alternative notions of zero knowledge, e.g. honest verifier zero knowledge. We can prove that Schnorr satisfies these notions even when the challenge set is large, and for many applications this is sufficient. E.g. in the random oracle model, we can get non-interactive zero knowledge via the Fiat-Shamir heuristic. There are also constructions for converting honest verifier zero knowledge to zero knowledge.


RSA: Why must e be relative prime to phi(n)

Because RSA takes advantage of the fact that:

$a^{\phi(n)} \equiv 1 \mod n$

Which means:

$a^{\phi(n)+1} \equiv a \mod n$

So, in order to encrypt and decrypt using $e$ and $d$, we need:

$ed \equiv 1 \mod \phi(n)$

Which can only be true if $gcd(e,\phi(n)) = gcd(d,\phi(n)) = 1$


How can I generate large prime numbers for RSA?

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime number.

The preselection is done either by test divisions by small prime numbers (up to few hundreds) or by sieving out primes up to 10,000 - 1,000,000 considering many prime candidates of the form $b+2i$ ($b$ big, $i$ up to few thousands).

The deterministic prime number test by AKS is to my knowledge not yet used as it is slower and as the likeliness that an calculation error caused by the hardware is higher than $2^{-100}$.

Most smart cards offer a coprocessor for modular arithmetic with moduli from 1024 up to few thousand bits. The manufacturers often provide also libraries for RSA and RSA key generation using the coprocessor.


Partially-known-plaintext attack of a stream cipher based on modular arithmetic

Whenever you're trying to attack a scheme that is [algebraically] relatively simple like this one, a sensible first step is to write out everything you know. Now, considering the information you've been given, try and substitute things into oneanother, and see where this leads you.

Let $(m,c)$ be the first 1024 bits of the plaintext-ciphertext pair.

Now, some pointers

Given this is a stream cipher, how is $c$ created? In particular, $c=g(m,K)$ for some function $g$. What is this function? Substituting in the data you know, what do you learn?
Write out $F(x)$ and $F(a \cdot x)$. If I tell you $F(x)=y$, calculate $F(a\cdot x)$
Now, consider everything you know. Put it together and finish the problem yourself.


How practical are side-channel attacks and how much of a concern are they?

Yes, side-channel attacks are practical and a real concern, if the past is indicative of the future.
I've been professionally involved with Smart Cards since the mid eighties, and have repeatedly witnessed deployed systems vulnerable to many forms of side-channel attacks; examples (I personally did 1 and 3):

RAM buffer not cleared at reset, readable (with standard command Get Response), leaking state of previous PIN comparison, even if incrementing the PIN presentation counter had been inhibited (by hardware reset or/and removing EPROM programming voltage); that allowed recovering the 4-digit pins with expected 5000 attempts.
Timing dependency where the duration of PIN presentation with permanent-memory writes inhibited leaks if the PIN is correct or not, to the same effect.
Timing dependency where the duration of a comparison between values leaks the index of the first incorrect byte, allowing finding an $n$-byte value with expected $n\cdot2^7$ attempts instead of $2^{8\cdot n-1}$.
Return to manufacturer test mode (by a software exploit, hardware modification or upset), allowing extraction of permanent memory content, including secrets (variant: normal software can be coerced to read the wrong location).
Micro-probing to spy on bus lanes, leaking all kind of secret information.
Simple Power Analysis directly leaking bits of exponent in RSA.
Simple Power Analysis leaking activity (e.g. start programming of permanent memory), which combined with timing measurement leaks sensitive information (e.g. good or bad PIN, before that is recorded).
Differential Power Analysis, allowing key recovery.
Fault Injections (often considered side-channel attacks).

I have seen this causing great embarrassment to the suppliers of the vulnerable Smart Cards, and believe multiple reports that in the (distant) past, such vulnerabilities occasionally have been exploited on a large scale, especially in the field of Pay-TV with Smart Card.
More generally, when a device using cryptography is broken, this is often by means better described as a side channel attack than a cryptographic attack.
Addition: check this introductory article's part1 (alt.), part2 (alt.), part3; and this 2012 paper showing remote SPA and DPA attacks on Smart Phones and PDA.

If a cryptographic device/system can get in the hands of the adversary or otherwise become accessible enough (timing/Tempest/DEMA/SPA/DPA attacks can be remote to some degree), and it contains any information which confidentiality or even integrity matters (such as secret/private keys, authenticators, counters..), then one needs to pay close attention to side-channel attacks.


The reference for this is NIST SP800-38A, especially its appendix B.

Basically we consider the IV a binary value of the width of the block cipher (64-bit for DES, 128-bit for AES), and add 1 to that, except for one detail: there is no carry at some application-specified rank, defining the maximum number of blocks that can be enciphered with a single IV; if that limit is exceeded, we are in trouble (as if we reused a One Time Pad).

A possible setup for AES would be to draw the line at half the 128-bit words size, which "limits" to $2^{64}$ 128-bit blocks. That is $2^{68}$ bytes, or 256 Exbibyte, or 295 Exabyte, or a little over 49 million 6-TB hard disks (the biggest commercially available at time of writing); moving these would require about 1400 double-size (40') containers of 28 tons each.

The other 64 most significant bits can be used as session number. If we draw such session numbers randomly, one each second, for a decade, odds are 1/370 that two session numbers are equal (and we have a small problem there).

It is also perfectly fine to increment over the full 128 bits, and start from a random 128-bit value.

In any practical case: the IVs after $\texttt{69dda8455c7dd4254bf353b773304eec}$ would be $\texttt{69dda8455c7dd4254bf353b773304eed}$ - IF everything is expressed using big-endian convention!

Update: It is also possible to define non-standard ways to increment an IV. One with a low hardware overhead would be cycling a maximal-length LFSR from an initial non-stationary state, which can be implemented with 1 or 3 XOR gates (depending on if the degree allows a trinomial or not) within a single clock delay, rather than some wide adder perhaps with some carry lookahead for high clock rate.


How can I prove that a Feistel round is its own inverse for DES?

There's a simple way by which "each round of DES algorithm is its own inverse". Consider round $n$ of DES as involving (almost  only) a function $g_n$ with
$$g_n(L\mathbin\|R)=\bigl(L\oplus f(R,K_n)\bigr)\mathbin\|R$$
where $K_n$ is the 48-bit subkey for round $n$, function $f$ is the "cipher function" (given in the definition of DES), and $L$ and $R$ are 32-bit bitsrings forming a 64-bit block.

That function $g_n(L\mathbin\|R)$ verifies $g_n(g_n(L\mathbin\|R))=L\mathbin\|R$, as thought in the question; or in other words $g_n$ is an involution; or in yet other words $g_n\circ g_n$ is the identity function. Proof:
$$\begin{align}
g_n(g_n(L\mathbin\|R))&=g_n\Bigl(\bigl(L\oplus f(R,K_n)\bigr)\mathbin\|R\Bigr)\\
&=\Bigl(\bigl(L\oplus f(R,K_n)\bigr)\oplus f(R,K_n)\Bigr)\mathbin\|R\\
&=\Bigl(L\oplus\bigl(f(R,K_n)\oplus f(R,K_n)\bigr)\Bigr)\mathbin\|R\\
&=\left(L\oplus0^{32}\right)\mathbin\|R\\
&=L\mathbin\|R
\end{align}$$
That proof invokes the definition of $g_n$ (twice), associativity of $\oplus$, that $f$ is a function, that for all 32-bit $X$ it holds $X\oplus X=0^{32}$ (the bitstring of 32 zero bits), which is the neutral for $\oplus$.

DES encryption chains these 33 operations on 64-bit quantities:
$$\mathsf{IP}\,,\,g_1\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,g_{16}\,,\,\mathsf{IP}^{-1}$$
where $\mathsf S$ is the "swap" involution defined by $\mathsf S(L\mathbin\|R)=R\mathbin\|L$, function $\mathsf{IP}$ is some permutation of bits, and $\mathsf{IP}^{-1}$ is the inverse permutation.

DES decryption chains these 33 operations on 64-bit quantities:
$$\mathsf{IP}\,,\,g_{16}\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,g_1\,,\,\mathsf{IP}^{-1}$$

We see that DES encryption then decryption is the identity function: the $(34-j)^\text{th}$ operation of decryption cancels the $j^\text{th}$ operation of encryption:

For $j=33$, because $\mathsf{IP}$ cancels $\mathsf{IP}^{-1}$.
For $j=1$, because $\mathsf{IP}^{-1}$ cancels $\mathsf{IP}$.
For other even $j$, because $g_{j/2}$ is an involution.
For other (odd) $j$, because $\mathsf S$ is an involution.

Importantly, encryption and decryption use the very same structure, only the indexes (that, is, the order of the subkeys $K_n$) differ. That allow to use identical hardware or code for both encryption and decryption.

The usual definition of a round of a Feistel cipher includes the swap $\mathsf S$:
$$\begin{align}
g'_n(L\mathbin\|R)&=\mathsf S\bigl(g_n(L\mathbin\|R)\bigr)\\
&=R\mathbin\|\bigl(L\oplus f(R,K_n)\bigr)
\end{align}$$
and this function is not its own inverse per the sense in the question.

With that notation, DES encryption and decryption are the 18 operations
$$\mathsf{IP}\,,\,g'_1\,,\,g'_2\,,\,\ldots\,,\,g'_{15}\,,\,g_{16}\,,\,\mathsf{IP}^{-1}\\
\mathsf{IP}\,,\,g'_{16}\,,\,g'_{15}\,,\,\ldots\,,\,g'_2\,,\,g_1\,,\,\mathsf{IP}^{-1}$$
In that presentation, it is less apparent that decryption undoes encryption. But that still holds, and becomes obvious again if we expand the $g'_n$ into $g_n$ followed by $\mathsf S$.

When it is said that DES has 16 rounds, it is ignored $\mathsf{IP}$ and $\mathsf{IP}^{-1}$. And, for a strict Vulcan, only the 16th round (the one without swap) is its own inverse.

The DES specification, and many textbooks on Feistel ciphers, give indexes to $L$ and $R$ before and after round $n$ of encryption, with $L_0\mathbin\|R_0$ the plaintext after $\mathsf{IP}$. The above equation for $g'_n$ can then be written as:
$$\begin{align}
L_n&\gets R_{n-1}\\
R_n&\gets L_{n-1}\oplus f(R_{n-1},K_n)
\end{align}$$

DES (which as $m=16$ rounds) and some textbooks consider the ciphertext (before $\mathsf{IP}^{-1}$) to be $L_m\mathbin\|R_m$, and specialize the last encryption round's equations:
$$\begin{align}
L_m&\gets L_{m-1}\oplus f(R_{m-1},K_m)\\
R_m&\gets R_{m-1}
\end{align}$$

There are other conventions around: some texts use the same equations for all rounds. Then some add a final swap, or consider the ciphertext to be $R_m\mathbin\|L_m$; others consider $L_m\mathbin\|R_m$ as the ciphertext (that later kind does not obtain the same ciphertext as DES).

As to decryption, DES uses the same round equations for encryption and decryption except for the numbering of subkeys, that is for $1\le n<m$:
$$\begin{align}
L_n&\gets R_{n-1}&&&L_m&\gets L_{m-1}\oplus f(R_{m-1},K_1)\\
R_n&\gets L_{n-1}\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1}
\end{align}$$
with the decryption's $L_0\mathbin\|R_0$ defined as the encryption's $L_n\mathbin\|R_n$, from which it follows that for $1\le n<m$, the decryption's $L_n\mathbin\|R_n$ is the encryption's $R_{m-n}\mathbin\|L_{m-n}$ (notice the inversion), and the decryption's $L_m\mathbin\|R_m$ is the encryption's $L_0\mathbin\|R_0$.

Other texts use the same naming for equal variables in decryption and encryption, and define different round equations for decryption. For regular round structure that gives:
$$\begin{align}
R_{n-1}&\gets L_n\\
L_{n-1}&\gets R_n\oplus f(L_n,K_n)
\end{align}$$

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes in the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we exclude the swap as part of its definition.


Weak Boneh-Boyen Signature in Composite order group

1) To perform verification in the order $p$ subgroup (if the order is $n=pq$ for $p,q$ prime, $a^q$ maps an element $a$ into the order $p$ subgroup - and this clearly also holds in the target group).

2) The argumentation in the unforgeability proof is that switching from $h$
of order $n$ in the common reference string of the GS proof to $h$ of order $q$, then under the subgroup decision
assumption the probability of a forgery to happen only changes negligibly. So their idea is that
playing the original unforgeability game with the adversary (where $h$ is of order $n$) and a forgery happens,
then playing the modified game with $h$ of order $q$ does not change the probability of a forgery
to happen. But now as in the modified game the commitments are perfectly binding and the
proofs are perfectly sound (the adversary cannot forge a proof), a forgery output by the adversary implies a forgery of a BB signature (which we know can
only happen with negligible probability).

Now, as the simulator who interacts with the adversary knows the the factorization of $n$ (trapdoor of the GS common reference string), it would not yield a valid reduction
if the security of the BB signatures would be considered in the entire group and would require that the factorization of $n$ is unknown (as the simulator knows the factorization, it could then compute a forgery on it's own and thus the reduction would be meaningless). However, if one assumes that forging BB signatures in the order $p$ subgroup is hard even if knowing the factorization of $n$, then the reduction can use the forgery output by the adversary in the unforgeability game to break the unforgeability of the BB signature scheme.

As the proof in the paper is very sketchy, this does not show up anywhere else in the paper.


Practical lattice based signatures and key exchange with strong security reduction

Your best bet at the moment are probably the lattice-based key exchange described in the "Post-quantum key exchange – a new hope" paper. You can also find different implementations. C code can be found on Peter Schwabe's homepage.

For signatures, if you want to use lattices, you will end-up with BLISS or BLISS-B both of which are implemented by various people.

However, a word of warning. While there exist parameter proposals and especially the "new hope" paper is even very conservative regarding the parameter choice, both schemes use ideal lattices. The parameter estimates assume that there exists no significantly better attack for ideal lattices than for random lattices. While this is true at the moment, it is unclear if this will be the case in the long run. As always, there are several researchers that believe it will stay that way and several that believe faster algorithms will be found.

A second issue is that implementation security of these schemes was not really studied so far and is hence not understood.

Anyway, combining these with ECC for example will definitely improve your security.


NIST DRBG algorithms' optional parameter

A partial answer is that the 2012 version of SP 800-90A included a fourth DRBG construction, Dual_EC_DRBG (§10.3.1.2), for which the security_strength parameter was required. Since one DRBG flavor required this parameter, to have a common interface, all DRBG flavors had to take this parameter. In Dual_EC_DRBG, security_strength is used only for one thing: to select the curve.

  Using the security_strength and Table 4 in Section 10.3.1, select the smallest
  available curve that has a security strength security_strength. The values for
  seedlen, p, a, b, n, P, Q are determined by the curve.

Dual_EC_DRBG was retired after it became public that is was probably backdoored by NSA, but its legacy survives in this minor way.

What escapes me is why Dual_EC_DRBG chooses the curve based on the security strength, whereas Hash_DRBG and HMAC_DRBG are parametrized by a choice of hash algorithm and CTR_DRBG is parametrized by a choice of block cipher.


Why are some x-coordinates unsuitable for an ECDSA generator point?

Here is a plot of secp256k1 over the reals. That I'll use for illustration purposes.

What happens at $x=-3$, well, we get $y^2 = (-3)^3+7$ which reduces to $y^2=-20$. Solving for $y$ we get $y=\sqrt{-20}$, which is not in the reals, so, we cannot have a point on that curve for $x=-3$.

This is what is happening. In the case of the real secp256k1 used in bitcoin, we are using a finite field instead of the reals. In the reals, the equation $y^2=x^3+7$ is not defined for the entire domain. Similarly, over the finite field, the equation is not defined over the entire field.

In other words, in order for there to be a point (actually 2 points) on the curve at $x$, we must be able to take the square root of $x^3+7$ in the field. As to the number of valid $x$ values, see this question on Math.SE.


Why does this RSA example break when: 1) setting p or q as non-prime, or 2) setting p and q as the same number?

A first step is to use the correct value for
the totient function
$\phi(n),$ which is $432$ and $110$ in your examples.

Even better use the
Carmichael function $\lambda(n)$ as described in RSA key generation, which is
$36$ and $110.$

With either of these numbers, your encrypted messages are decrypted correctly.


The obvious issue is the probability of guessing the key, and the probability of guessing the MAC.

But there's also a qualitative difference.  Suppose you have learned a message/authenticator pair $(m, a)$ where $a = H_k(m)$.

You can test a guess $k_0$ for the key offline by testing whether $a \stackrel?= H_{k_0}(m)$.

The feasibility of finding the key $k$ depends on how much money the adversary has to commit to an offline key search.
You can test a guess $a'_0$ for the authenticator $a' = H_k(m')$ of a forged message $m'$ only by submitting $(m', a'_0)$ online to the legitimate system and seeing how the legitimate system reacts.

The feasibility of forging an authenticator $a'$ this way depends on how much bandwidth the legitimate system has to accept online forgery attempts.


For high security applications using 3DES, NIST recommends using keying option 1 (all keys are different). This is simply because it's the safest. For any application, keying option 1 should be used. If you set K1==K3, then you are reducing your key size to 112 bits, which is less than the smallest key size for AES. Worse still, due to cryptanalysis done on DES, setting K1==K3 (known as keying option 2), NIST has said this has an effective security of 80 bits. This is barely an improvement on plain DES.

So in short, yes, NIST claims for federal applications you should use 3 different keys. But this is true for any application.

Your second proposal has an effective security of 56 bits, which is just plain DES. A globally fixed K2 means that it has no security, and once one client is broken and decompiled (and trust me, this will happen), then they have K2 for all clients. This effectively makes it have 0 bits of security. K3, being the same as K1, also has 0 bits of security. The only security comes from K1, which is 56 bits. The EFF showed us that a 56 bit key is insecure and is susceptible to a brute force attack.

You really shouldn't be using 3DES though. It's only used in legacy applications where there are absolutely no other options. AES is currently the standard. If you must, and only if you must use 3DES, use 3 distinct keys that are randomly generated per session.


Can you derive a 128 bit AES encryption key using PBKDF2 with SHA-256

Truncate the output to 128 bits.

(Or, consider using AES-256 instead.)


Why does FIPS 186-4 seem to have an excessively complex q generation?

This is meant to allow domain_parameter_seed to be longer than 160 bits and to allow for the "verifiable canonical generation" of domain parameters described in Appendix A of the document you linked. See A.1.1.2 and A.2.3 in particular.

A truly random seed would be acceptable to use without hashing, but using a chosen number directly would be suspicious at least. Possibility of poor RNG may also be a consideration.


In RSA. Why is $\phi(n)$ kept secret and $n$ is public?

No, it is not easy! RSA is based on the difficulty of factoring the product $n=pq$ of two large prime numbers. But if you know $\varphi(n)$ for plain RSA you can compute the secret exponent $d=e^{-1}\bmod \varphi(n);\;$ and you can factor $n$ from the two equations $n=pq,\;\varphi(n)=(p-1)(q-1)$.


How to prove that a encryption scheme is not IND-CPA secure

In IND-CPA experiment, can the adversary generate a key (that may not be real secret key) and compute Enc(key, message)?

Yes, for message available to the adversary per the rules of the game. The adversary is always assumed to be able to use as a subprogram the algorithm under attack, or any part of it (e.g. encryption, or decryption, or key generation as is the case here; or any deterministic internal block, such as a hash including when modeled as a random oracle). That's per Kerckhoffs's principle. The computation is still counted as work performed by the adversary.

The random inputs and the outputs of any internal TRNG of the scheme under attack are assumed to be supplied to the adversary only inasmuch as prescribed by the scheme (e.g. IV for encryption; that's uncommon for key generation). The adversary has unlimited randomness available (e.g. to generate new keys, collisions), except if it is explicitly specified to be deterministic.


Some questions on building permutations from boolean functions

The general algebraic question is multifaceted and can be quite complicated. Some depend on vector space, some on extension field properties.
As mentioned in the comments checking the property can be simpler.
I answered a related question Examples of multi output bit balanced Boolean functions
Nyberg’s articles mentioned there are
K. Nyberg, Differentially uniform mappings for cryptography, 1993 and
K Nyberg, Perfect nonlinear S-boxes, 1992
both easily locatable on google scholar.
Edit: The keccak $\chi$ maps $\{0,1\}^5$ to itself.
I will use $a_i$ as input and $A_i$ as output variables as in the edited question.
Counting indices modulo 5, if there is no $i$ such that $(a_i,a_{i+2})=(0,1)$ then $\chi$ has a fixed point for that input. Let $W=\{i: (a_i,a_{i+2})=(0,1)\},$ then the general mapping just inverts the bits belonging to $i.$
Note that the sets $J_i,J_j$ where $J_i=\{i,i+2\}$ are disjoint except when $j=i+2$ or $i=j+2.$ So there is no ambiguity for determining the inverse unless we are in this special case, thus the inverse exists except in this special case. But even in this case the patterns
$(a_i,a_{i+2},a_{i+4})$ which result in bitflips are unambiguous.
If $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ then $a_{i+1}$ will be flipped but not $a_{i+3}$. So $A_{i+1}=1\oplus a_{i+1},$ and $A_{i+3}=a_{i+3}.$
If $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ then $a_{i+1}$ will be flipped but not necessarily $a_{i+3}$, that will depend on the value of $a_{i+6}=a_{i+1}$. But that bit is not impacted by the previous argument since $J_i$ and $J_j$ are disjoint if $i=j+1\pmod 2.$
So a unique inverse mapping exists.
Remark: In general going between "basis independent" extension field formulations of permutations vs "basis dependent" bit vector permutations is hardly straightforward. I don't see an immediate basis independent extension field formulation for this permutation, and as pointed out in the comments to the question such formulations obtained (say) by Lagrange interpolation, can be quite complicated and high degree.


What is a branch number in the PAEQ algorithm?

In AES, the MixColumns transform as a branch number of 5, this is because a change to a single byte input causes 4 of the output bytes to change. Like branches of a tree, 1+4=5. This is because MixColumns uses an MDS matrix for multiplications against the input.

AESQ operates on entire 128-bit blocks, which are further broken down into AES round operations. 2 AES round operations create full diffusion of the 128-bit block, so a single AESQ round consists of 2 AES rounds, in 4 parallel paths, followed by a shuffle operation so that 4 bytes from every AES round group go to a different group for the next round. What I am callling an AESQ round here is the output of a shuffle to the next shuffled output, I believe they call this 2 rounds in the paper.

Because the 2 AES rounds offer full diffusion, the branching of AESQ is a change 1 AES input block resulting in a change to 4 bytes of each AES output block. I color coded the blocks to show the distribution of modified bytes due to a change in any input byte over a single AESQ round (built from 8 AES rounds).

Therefore, just like in AES, we need 2 AESQ rounds for full diffusion of a single bit change to the the 512-input. This involves 16 AES rounds and 2 shuffle operations. This is considered MegaMixColumns plus MegaSubBytes, with a branch number of 5. This is called 4 rounds in the paper.


Algorithm for proving Carmichael numbers

Well, yes, there is a probabilistic polynomial time algorithm the determines whether a number is a Carmichael number of not (probabilistic in the sense that it  always returns the correct value, it terminates quickly with high probability).  However, it isn't as helpful as you are thinking for your application.

The algorithm is based on two observations:

Carmichael numbers are easy to factor
Given the complete factorization, it is easy to verify whether a number is a Carmichael number or not (Korselt's criterion, as Thomas mentioned).

Here's the details on the first observation: if we have a composite number $N$, and an even value $e$ for which $x^e \equiv 1 \bmod N$ for a nontrivial fraction of the values $x$, then we can factor $N$.  We do this by computing $\lambda$ a power of 2 such that $e/\lambda$ is odd, and for random values of $x$, compute $x^{e/\lambda}, x^{2e/\lambda}, x^{4e/\lambda}, ..., x^e$.  If the series ends in 1 (which it will with good probability; that's the condition we placed on $e$), we look at the value immediately previous to the first 1; if that value $x^{ke/\lambda}$ is not -1, then we have the nontrivial factors $gcd(N, x^{ke/\lambda}-1)$ and $gcd(N, x^{ke/\lambda}+1)$ (because $x^{ke/\lambda}$ is a nontrivial square root of 1).  In addition, if $N$ has more than 2 factors, this yields a random factorization of $N$.

Now, if $N$ is a Carmichael number, then $e = N-1$ is such a value; in fact, for any $x$, we have either $gcd(x,N)>1$ (and hence we have a factorization of $N$), or $x^{e} \equiv 1$ (and hence we have a factorization with good probability).  In addition, if we pick a value $x$ and we find that $gcd(x,N)=1$ and $x^{e} \neq 1$, then we've just shown that $N$ is not a Carmichael number.

Hence, the probabilistic algorithm would look like:

Check if $N$ is prime; if it is, then return FALSE.
While we have don't have a complete factorization of $N$

Select a random $x$
If $gcd(x, N)=1$ and $x^{N-1} \ne 1 \bmod N$, then return FALSE.
Otherwise examine $gcd(x, N)$, $x^{(N-1)/\lambda}$ for a nontrivial factorization of $N$
If we have found a nontrivial factor, use that nontrivial factor to attempt to find more prime factors of $N$

Once we have a complete factorization of $N$, apply Korselt's criteria to determine whether $N$ is a Carmichael number.

This answers your question, however it's not very useful for determining whether a number is prime.

On the other hand, if you need an algorithm that produces large prime numbers, and you aren't happy with probabilistic methods, have you considered the Shawe-Taylor algorithm appendix A.1.2.1?  The numbers this algorithm generates are guaranteed prime, and my experience is that it is about as fast as searching for primes using a Miller-Rabin test.


Is there an accepted way to cryptographically enforce tracked changes on a document?

A checksum of the original file would be included and encrypted by the password provided. This would prevent other users from editing the block and producing a new checksum.

This is a failed attempt to achieve integrity, with a secret password. A Message Authentication Code does that, with a secret key (see e.g. HMAC). One issue with the question's encrypted checksum is that for most document formats, it's easy to make two apparently identical documents with the same checksum. And even if we fix that by using a hash instead of a checksum, an encrypted hash is still not necessarily a proper MAC. That's because encryption is intended to provide confidentiality, not integrity. And for some common encryption systems (including the widely used and recognized AES-CTR), it's possible to alter the cryptogram obtained by encrypting a checksum/hash to match a different checksum/hash.

I believe that this would constitute a vulnerability because it would expose the password to a brute-force attack.

Yes, but there is a standard mitigation to this: using a purposely slow and salted Password-Based Key Derivation Function, such as Argon2 or scrypt, in order to generate the key of the MAC from the password (note: while PBKDF2 and it's ancestors are Password-Based Key Derivation Functions, they are obsolete, and do not seriously deter brute-force password search by powerful adversaries).
With the combination of a Password-Based Key Derivation Function and a MAC, there remains a devastating issue: the password or the key is needed to check the MAC, and that allows to forge a new MAC for a different text.
This issue is solved by using (public-key) digital signature instead of a MAC. Each user generates a public and a matching private key. The private key is necessary to make a signature, the public key allows to check it, and with that the integrity of the document, and which private key produced the signature. That could be extended to revisions (e.g. what's signed is the document as it stood when the user made the last revision. Multiple signatures of multiple states of the document can coexist, be stored in the document, and checked quickly enough).
A remaining problem is to distribute the public keys in a way ensuring their integrity and unique association to a user. One method is thru public key certificates.
Another remaining problem is storing the private keys in a manner ensuring confidentiality. That's usually done with encryption, and generating the encryption key with a Password-Based Key Derivation Function. That's standard with PGP/GPG private keyrings, and private keys matching public key certificates.

I would like to add a feature to lock tracked changes.
Is there any commonly accepted way to approach this problem?

Not much if you ask a cryptographer, beside

The aforementioned use of digital signature with a trusted public repository of public keys, or public key certificates.
Keeping the document on a trusted server keeping track of changes thru cryptographic authentication of users and user-originated changes, and defining the document as what's on this server; or a copy of that signed by the server.

And then the first option does not really prevents untracked changes, only bogus attribution of a change to a user that didn't originate it (assuming it's required that any change is signed). And in both options there remains the very real possibility that a user's computer is compromised, and changes to the document attributed to a user have been made contrary to the will of the user.
From a cryptographic standpoint, if one can read data using an untrusted computer, one can copy and alter it. The best crypto allows is detect that. This would be different if one assumed people can't modify what a program does. But that's not something crypto knows how to achieve on a standard, open computer.
Another option might be a blockchain. I don't really understand what that is or does (I recently asked), but can tell it does not qualify as widely accepted.


How to convert random bytes into blocks of numbers without weakening entropy?

Yes, it is called the simple discard method or rejection sampling. Basically you generate a byte of randomness, then check if the value is equal to or higher than 250 (the highest multiple of 10). If so, you discard the value and regenerate the byte. If you have a value in the range [0, 250) then you simply use modulo 10 (the remainder after the division). And there you are, a well distributed and secure value.
Of course, this method is not very efficient when it comes to a one-time-pad. Generally the one-time-pad is used over bits. But if you have it over digits then it is easier to use 10 to the power of digits you need, then use the simple discard method to generate the larger value, and then perform the (optional) modular reduction. If you take just enough bits, the modular reduction is not needed. After generating the binary value you can perform base conversion to convert the binary value into digits.
If you think the second method is still not efficient enough, then you can use the optimized simple discard method of which I'm the author.

Note that many libraries have both a method to create a large random number in a range as well as methods to get a decimal string, so in that case you can retrieve all required random digits in just two calls (although you may have to convert the character string into values within an integer representing each digit).


Why avoid custom HMAC implementations like the following?

You need to be clear about the interface and security goals of what you're trying to achieve, vs. those of HMAC.  This passage of your question seems to state your security goals:

  What if an attacker knows the o_pad, i_pad, the static_salt, and the final HASH but not the message... it's potentially possible obtain the message (other than just brute-forcing it) using this custom implementation?

But that's neither the interface nor the security goal of HMAC:

Interface: MACs are secret keyed functions; they take a key and a message as argument, where the message may or may not be secret.  You're describing something that takes a message and no key; it's not the same interface!
Security goals: MACs expect the key to be a secret random value, and allow (but not require) the message to be non-secret; the goal is to resist forgery of message/tag pairs.  In your construction, on the other hand, you're assuming that messages are secret, and that an attacker who knows every other value (o_pad, i_pad, the static_salt, and the hash result) must not recover the message.

So you're asking us to do an apples-to-oranges comparison.  And in addition, the goal that you have in mind—inability to recover the message for an attacker who sees all the other values—is already a goal of SHA512-crypt.

I hope this isn't too harsh, but what you're doing basically is adding some extra complexity on top of SHA512-crypt that doesn't do anything to further the goal that you've set for it, and superficially resembles HMAC.


Choosing encryption algorithms and encryption protocols in military systems

Militaries have some options on choosing Encryption algorithms, schemes, and protocols;

They can use open community encryption algorithms, schemes, and protocols that are designed and analyzed by many brilliant cryptographers.
They can ask to 3rd parties to built for them if they have no Cryptographic expert in their army.
They can create their own Cryptographic Algorithms and Schemes and keep the designs and analyzes to themselves.

They fear from the first option since they don't want to use the open algorithms.
 They think that there can be always a back door.

They use the second option if they don't have the talent and even they buy from a another country's companies. Many examples are exist in history.

For the last two option, we can see it like security by obscurity but not exactly. Oscar (the eavesdropper of the signal) has to deal many problems:

The communication can be online encryption that is the network traffic is always encrypted and there is always a dummy message to encrypt to keep the traffic always on even to prevent signal intelligence.
The even the Error Correcting Codes (ECC) can give huge disadvantage to Oscar. Which ECC is used is a problem especially if the ECC applied data is an encrypted data.
Below this online encryption, the officials of the army can encrypt the messages with the usual symmetric and asymmetric encryption schemes. This turn the data into double encryption.

The above list may no be complete, anyway, jump to history;

The history shows us that, obscurity is not the correct way. Remember how the Enigma was stolen and finally broken. Even when the 4th rotor was introduced, only the knowledge of the 4th hole was enough to break again. Ironically, the M-209 much easier to break which was mechanical marvel.

Today, information espionage much easier than the older times. So, in reality, the militaries also plays with the Kerckhoffs's principles. They assumes that even the designs falls into the hands of the enemy rule, too. They only use the secrecy of the design and analyze as a frontal counter measure with the deep question;

What if our algorithms, schemes, and protocols are not really secure as we think.


For RSA, is there a specified size range for $p$ and $q$ when calculating $N$?

There is no specific length for $p$ and $q$; however, one must mind the following:

Since $N = pq$, the size of $N$ will be more or less the sum of the sizes of $p$ and $q$ (± 1 bit).
Security of the key relies on the difficulty of integer factorization. The best known algorithms for that have a cost that depends on the size of $N$, but some other algorithms (in particular ECM) have a running cost that depends on the size of the smallest factor. If one of the factors $p$ and $q$ is too small, then it may make ECM practical, leading to a security weakening.
Private key operations with RSA can be expensive (especially on small, embedded hardware). A common optimisation is to do private key operations not modulo $N$, but modulo $p$ and $q$ (the Chinese remainder theorem tells us that it works). Since $p$ and $q$ are smaller than $N$, this is a net gain. The speed-up factor is highest when $p$ and $q$ are both about half the size of $N$.
Some widespread implementations of RSA require the two factors to be exactly half the size of the modulus. This is the case, for instance, for Microsoft's CryptoAPI: when importing a private key, the import format uses fixed-size slots for the factors, that are exactly half the size of the modulus.

Therefore, while the RSA standard does not mandate any specific sizes for the individual factors, the general practice is to make both factors $p$ and $q$ to be exactly half the size of the modulus $N$. So, for a 1024-bit modulus, the factors will be 512-bit integers.

(To be even more precise, it is customary to generate each factor with its two top bits set to 1. If you just take two 512-bit integers, their product may be a 1023-bit integer; by setting the two top bits of each factor to 1, this ensures that the product will be a 1024-bit integer.)


While doing the affine mapping after calculating the inverse of my polynomial using the EEA, I am not getting the value of the inverse as it should be


The property you are probably looking for is whether the MACs are PRF.

With HMAC it depends on the pseudo-randomness of the hash function used. If the hash is a PRF then the HMAC is as well. However, that is not required for MAC security of HMAC, so it's not necessarily true even with a secure HMAC. See New Proofs for NMAC and HMAC: Security without Collision-Resistance.

In both of EAX and CMAC, the MAC is a particular (unique) output of the block cipher and is indistinguishable from random as long as the block cipher is a PRP and the outputs are not seen too many times to distinguish a PRP from a PRF.

Similarly, GCM outputs the XOR of a unique block cipher output with the GHASH and so is PRF as long as the block cipher is. (You also have to assume that the GHASH output is independent of the block cipher output.)

CWC has a Carter-Wegman MAC that is again indistinguishable as long the block cipher is, because it outputs a XOR of two independent block cipher outputs.


Counter Mode: static IV but different keys

If you assume AES is a pseudo-random permutation(which is pretty much necessary for it to be secure), then yes. However, it's way easier to just use a random IV/noce and keep the keys. Your new  key must be distributed to both parties secretly, the IV/nonce can be public, so you can just send it (HMACed of course) in the clear. You obviously can't do this with a key and you may introduce problems depending on how you try to send it.

Typically the IV in CTR mode is called a nonce (shot for number used once). The reason for this is that it, unlike most uses of an IV, need not be random, just only used once. Since we assume the block cipher is a pseudo-random function, we just need to ensure it doesn't get the same value feed into it twice and it will giving us random looking output. Strictly speaking, we just care that the same (Nonce,counter) pair is not used twice, but since we have no control over the  counter value, we make sure the nonce is unique..

Assuming that the block cipher is a pseudo random permutation also tells us we only care if the same (key,nonce, counter) is used. Effectively, the key is just selecting at random the permutation we use from the set of all permutations of a given length( the cipher's block size). For each permutation, the output on (nonce,counter) is unique, so we don't care about repeats under different keys.


Direct use of textbook RSA for encryption is very insecure. For example, a guess of the plaintext can be checked: if what's encrypted is a name on the class roll, enciphering all names on the class roll until getting the ciphertext breaks confidentiality. There are several other attacks.

That motivates RSA-OAEP. It turns textbook RSA, a hash, and a source of random bits, into a demonstrably secure encryption scheme. Encryption of message $M$ first transforms $M$ into padded message $X$ by mixing it with random bits and applying reversible transformations with the hash; then enciphers $X$ into $X^e\bmod N$, that is per textbook RSA encryption. Decryption starts by textbook RSA decryption, yielding $X$; then the padding is undone, yielding $M$ or an error indication.

I essence, the distribution of $X$ is random enough that textbook RSA becomes secure. A proof of that can be made for the strongest definition of security of a cipher, IND-CCA2, and under some hypothesis:

the RSA problem of finding a random $X$ given $X^e\bmod N$ is hard;
the hash is undistinguishable from a public function selected at random;
the source of random bits is indistinguishable from one producing uniformly random and independent bits;
a decryption device given a cryptogram only outputs the correct plaintext or an error indication (it does not leak any other information).

A (highly technical) reference proof is in Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern's RSA-OAEP Is Secure under the RSA Assumption, in Journal of Cryptology, 2004. A more gentle text is David Pointcheval's How to Encrypt Properly with RSA?, originally in Cryptobytes 5n1, 2002.

The practical form of RSA-OAEP is named RSAES-OAEP and defined in PKCS#1 v2.2.


Is it possible to utilize an AES-128 encryption hardware unit for AES-256?

There are two important differences between AES-128 and AES-256:

AES-128 has 10 rounds, AES-256 has 14
The key expansion process (that is, how they generate subkeys) is different

If your AES-128 encryption hardware just takes a plaintext block and a 128 bit key, and produces a ciphertext block, well, no, there's not much you can do.  In this case, the hardware knows the AES-128 subkey expansion process, and there's nothing you can do to ask it to do the AES-256 expansion process instead.

However, if the hardware takes the plaintext block and the $11 \times 128$ bit expanded key, yes, there are things you can do.

The obvious approach would be (in the encrypt direction) to perform the first four rounds in software (stopping just before the addround transform at the end of the fourth round); then hand the intermediate block to hardware to compute the last 10 rounds.

In your key expansion process, you'd run the AES-256 key expansion process in software; you'd keep the first 4 generated subkeys for your software routine; you'd hand the last 11 subkeys to hardware as your expanded "AES-128" key.

This idea won't be as fast as doing AES-256 in hardware; however it should be faster then performing everything in software.

Also, you want hardware to handle the last round (in the encrypt direction); that last round is handled slightly differently - while you can adjust for it, there's no reason to.


How can we prove that the scrambled G matrix in McEliece cryptosystem preserves the minimum distance properties of G matrix?

$P$ is required to be a permutation matrix. Thus, the effect $P$ has on $G$ is simply to reorder its columns. Crucially, this does not change the weight of any of the codewords. Note that this holds irregardless of the code; be it Goppa or something else.

More concretely, suppose $G$ is any $(n,k,d)$ code. This means that $G$ can correct up to $\frac{\lfloor d \rfloor}{2}$ errors. So let $d' \leq \frac{\lfloor d \rfloor}{2} $ be the weight of $e$. Now suppose
$$c = mSGP + e.$$
On decrypting $c$ we first apply $P^{-1}$ to $c$ to get
$$ c' = cP^{-1} = (mSGP + e)P^{-1} = mSGPP^{-1} + eP^{-1} = mSG + e'. \tag{1}$$
You see that the r.h.v. in (1) is simply a codeword in the code generated by $G$ with an added error of $e'$.
But the inverse of a permutation matrix is also a permutation matrix, so the vector $e'$ also has weight $d' \leq \frac{\lfloor d \rfloor}{2} $.  Consequently, we can apply the decoding procedure of the code to get rid of $e'$ and obtain $mS$. Since $S$ is invertible, we can obtain $m$ by multiplying with $S^{-1}$ on the right.


Disclaimer: I'm answering without any knowledge on the content of the paper in question.

  Why there are numbers in this Figure 1, that are placed in vertical form?

Because otherwise the figure would not fit into the page width (or the authors would have to use unreadably small font).

  How to interpret this axis X?
  I imagine that are interval times but I do not understand why they are in vertical form. Moreover, on the same axis there are twice the number 180.

What you imagine is most probably correct. The vertical form I explained above. This is not 180 but 1800 (the second time). After 990 goes 1030, not 103. The last zero is either lost or simply omitted to save space because it is assumed to be obvious for a reader that "After 990 goes 1030, not 103".


Getting the encryption/has algorithm used for modem configuration file

You cannot; most (symmetric) encryption routines create output that is indistinguishable from random. This is however more likely to be the output of a password hash. The only thing you can say is that the result is 24 bytes. That 24 bytes hopefully contains a fully random salt (mostly 8 bytes) and a hash or password hash. In that case it's probably MD5 as there are only 16 bytes left. It could also be the output of SHA-224 directly over the password, or a HMAC using SHA-224 or similar with a device specific key.

If it is salt | MD5 or just SHA-224 is of course something you could test yourself. You could do this using your own password or - possibly - a dictionary attack. Note however that the password should now be changed ASAP as anybody can perform a dictionary attack.


Here is an attack that I think will, with excellent odds, allow certain determination of which value is on the ticket of colluding players; and consequently give an advantage on guessing the tickets of these colluding players, and a (typically lesser) advantage on guessing the tickets of honest players. I'm assuming:

The adversary knows the value on every ticket (as confirmed by a comment), with no ambiguity about that under orientation of the ticket.
It is not known the initial state of the LFSR (as now explicit).
All players press their button haphazardly, which when the exact instant is unknown sorts of partially reseed the LFSR.
The adversary knows exactly when $m$ consecutive players pressed the button (because these $m$ players collude with the adversary), thus exactly how many steps of the LFSR there has been between theses presses; this allows the adversary to express the state of the LFSR at the key-presses of the colluding players as a linear function of the (assumed unknown) state when the first colluding player pressed the button.
$n$ is low enough that the adversary can perform some processing for each of the (at most) $n!/(n-m)!$ distinct orders of values for colluding players ($n=15$, $m=10$ means that about $11\cdot10^9$ orders are to be considered, and would be very feasible).
$t$ is large enough that it is likely that only a single of these ticket order matches the linear functions; there are $b$ unknown bits, $(n-1)\cdot t$ known bits, thus by an entropy argument (based on the vague and unproven hypothesis that the haphazard behavior of players makes the system of linear equations unremarkable), there should typically be a single possible order of values when
$$m\cdot t\gg b+\log_2(n!/(n-m)!)$$

It is then easy to check a candidate order, and deduce the $b$ bits of initial state. Just plug $m={2\over3}n$ for $2\over3$ of the players colluding.

Also, if the uncertainty on when the honest players pressed (assumed to have uniform distribution in an interval with $u$ steps, with that the product of time per frequency) is such that $u\ll2^t/(n-m)$, we can often guess the (value on the) tickets of other players immediately before and after the $m$ colluding players; even all of them if $u\ll2^t/(n-m)!$ or something on that tune.

Further (as the saying attributed to the NSA goes, and illustrated by a sizable improvement in version 5 of this answer): attacks only get better; they never get worse. In particular, I have not fully exploited the information that can be gained from the known value on the tickets of the honest players, which is significant if $u\ll2^t$; or speedups possible for many parameters to dramatically cut down on $n!/(n-m)!$ explorations; or what improvements could be achieved when colluding players press at a chosen instant, rather than at a random but known instant.

The above does not give a condition that would insure an adversary can't succeed. Here are some thoughts towards that. I'll consider that the LFSR is maximum-length (has period $2^b-1$, or equivalently uses a primitive polynomial and is never all-zero); and that a key-press occurring when the LFSR is all-one prints an all-one ticket, but leaves the LFSR as if no key-press had occurred.

Assume a player stays exactly $u=2^b-1$ clock periods in the room, and consider the 4 variables

LFSR state $I$ on entrance
LFSR state $P$ as sampled by key-press (of which $t$ out of $b$ bits are printed)
LFSR state $O$ on exit
number of clock periods $w$ between entrance and key-press, with $0\le w<2^w$

It holds that $P=M^w\cdot I$ and $\hat P=M^w\cdot O$, where $\hat P$ is the bitwise complement $\bar P$ of $P$ except that all-ones is unchanged; and $M$ is the $b\times b$ sparse matrix corresponding to advancing the LFSR by one step.
When any of $I$ $P$ $O$ $w$ is fixed, these relations defines a one-one mapping from any of the other three variables to either of the two last variables. Note: when $w$ is unknown, finding it (or $P$ if also unknown) seems to be a discrete logarithm problem; I consider an adversary able to solve that.

It follows that when an honest player stays in the room for much longer than $2^b-1$ clock periods, to an adversary knowing only one of the LFSR states on entry or exit,

the other of these states is indistinguishable from a uniformly random non-zero variable,
the value printed on the ticket has the same distribution as for a random sampling (all-zero with odds $2^{b-t}-1\over2^b-1$, any of the other $2^t-1$ values with higher odds $2^{b-t}\over2^b-1$).

The above two unknowns are however strongly related.

If we see the LFSR as an entropy pool,

an honest player staying in the room for much longer than $2^b-1$ clock periods refills that entropy pool to its full capacity $c=\log_2(2^b-1)$ bit
however knowledge of the value of a ticket reveals at most $r=\log_2(2^b-1)-\log_2(2^{b-t}-1)$ bit of information when $t<b$ (this occurs when the value printed is all-zero), or $r=\log_2(2^b-1)$ bit when $t=b$ (the value printed can't be all-zero).

From this I tentatively conjecture that with all but very small $b$, the adversary has negligible advantage if at least $h$ honest players, who each stay in the room for much longer than $2^b-1$ periods, stand between any two players colluding with the adversary, and
$$h\cdot c\ge (h+1)\cdot r \text{ , that is } t<b \text{ and } (h+1)\cdot\log_2(2^{b-t}-1)\ge\log_2(2^b-1)$$

The condition is constructed as: in a sequence of $h+1$ players, at least as much entropy is injected as revealing all the ticket values consumes. My intuition is that this condition is enough that the adversary can't learn more about the state of the LFSR when a player presses a key than knowledge of the corresponding ticket value would reveal, and/thus is unable to tell if an hypothesis on which ticket belongs to who is more or less likely.


Testing hash functions for collision resistance

I think calculation of probability is not a good idea. Because your pool is gonna greater when you want to work with complex hash algorithms (for ex: sha256/512...)It may work just for md5 or sha1.
I suggest you to check out also Linear Cryptanalysis Attack to understand Differential Cryptanalysis deeply.

Good luck


Public Key encryption /Assymetric encryption

The part you're missing here is that Public Key encryption is asymmetric - that is, data can only be encrypted with the public key, and can only be decrypted with the private key. Public key encryption systems are created in such a way that the encryption is (mostly) irreversible, but there is a mathematical 'trapdoor' that allows the private key to be used decrypt the data.

Compare this with a symmetric encryption scheme, where there is only one secret key (so both Alice and Bob would have to share the key to use such a scheme).

i.e. once the data is encrypted by Bob using Alice's public key, noone holding Alice's public key can decrypt it. Only Alice, using the private key and the different decryption algorithm can decrypt it.

The answers to How does asymmetric encryption work? give more detail as to how this works.


No.  That's not going to help you.  The cycle structure of a random function is well-studied, and it doesn't help you break hash-chaining, "proof-of-work", Bitcoin, etc.  Crypto schemes already take into account the structure of (the graph of) a random function.  It's not going to help you "pre-mine" and get some speedup on breaking Bitcoin (for instance).

For instance, the graph of a random function $\{0,1\}^n\to \{0,1\}^n$ typically has the following form: there is a single large cycle of length $\Theta(2^{n/2})$, such that most inputs eventually lead to the cycle.  Starting from a random input, the length of the path that leads to that large cycle is typically $\Theta(2^{n/2})$.  This does not break standard schemes for hash-chaining, proof-of-work, Bitcoin, etc., as the parameters for their hash function is chosen to take this structure into account.

Whether you want to count this as "chaos" depends upon your precise definition of "chaos", which you haven't provided in the question.  Anyway, from a technical/scientific/engineering perspective, what label we assign it (chaos or not) is less important than the technical properties it provides and the security goals it can help to protect.


Intuition behind the asymmetry between invertibility of key and ciphertext in block ciphers

If you had a block cipher with this property, it would necessarily be insecure!

The most basic requirement for a block cipher is to be a pseudorandom function (PRF). In the game that defines security of PRFs, the attacker gets to choose input blocks $x_1, x_2, \ldots$ and gets back responses $y_1, y_2, \ldots$. It should be hard to distinguish whether the $y_i$'s are uniformly random or have the form $y_i = F(k,x_i)$ for a random (secret) key $k$.

Suppose your block cipher was ``key-invertible'' in the way you describe. Here's an attack against the PRF security of the block cipher. Ask for some $x_1$ and get back $y_1$. Now you do this key inversion process and you can learn (a candidate) key $k'$. Then you can make one more query on $x_2$ and get back $y_2$. If $y_2 = F(k',x_2)$ then you guess that you are getting outputs of the PRF; otherwise you guess that you are getting random responses.

This attack completely breaks PRF security. It assumes that the key-inversion process is perfectly correct --- that is, given $x$ and $y = F(k,x)$ for unknown $k$, you can always compute that exact $k$. Even if you assume the key-inversion procedure is not always correct (e.g., maybe there are two keys that satisfy $F(k,x) = F(k',x)$ so sometimes you get it wrong), It seems likely to me that this attack can be extended.


On the privacy of perfect hash functions

The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash function on the set of n bit strings. Obviously this function does not hide the input at all.

So the answer to your questions is that it depends on the hash function. It being a perfect hash function alone (minimal or otherwise) does not guarantee any privacy at all. Neither does it say anything about what happens outside of the set for which the function is perfect. That means if the users hashes a value outside of this set it may well result in a collision with value in the set. Such a collision is easy to construct for the hash function I mention above.

On the other hand, if the reason you want to use a perfect hash function is that there are no collisions, you might as well use a cryptographic, collision resistant hash function instead. In this case there is basically no way for user to find a value outside of the set that collides with one in the set.

If using a collision resistant hash function in your protocol is enough for secure private set-intersection is a more complicated question. It essentially depends on your security assumptions and the flavor of PSI you want: Is the server malicious? Is the client? Should both parties learn if there is an intersection or not?


The cost of computing $x^e \bmod n$, which is the bottleneck in any RSA-based cryptosystem, is $\lfloor\log_2 e\rfloor$ squarings and $H(e) - 1$ multiplications modulo $n$, where $H$ is Hamming weight.*  Since $e$ is required to be coprime with $\operatorname{lcm}(p - 1, q - 1)$, the most efficient possible choice is $e = 3$.†

Originally, the 1977 RSA proposal (which was broken by modern standards in several ways, even ignoring parameter sizes) was to choose $d$ at random and derive $e$ from it.  But there's no security advantage to that, and it's much cheaper to choose $e$ to be small.

Historical RSA-based cryptosystems were badly designed and failed to provide meaningful security: if you naively try to encrypt a message $m$ like a 256-bit secret key by computing $m^e \bmod n$, and $e = 3$, and $\log_2 n > 768$, then it turns out $m^e \bmod n$ is just the integer cube of $m$ and an attacker can recover $m$ from $m^3$ just by computing integer (i.e., real number) cube roots.

So, in an attempt to stem the bleeding of such painfully naive use of RSA like this, people started using bigger exponents like $F_4 = 2^{16} + 1 = 65537$, despite the additional cost it imposes.

The sensible thing to do would be to choose $x$ at random, use a hash of $x$ as a secret key for an authenticated cipher, and transmit $x^3 \bmod n$ alongside the ciphertext—we call this RSA-KEM today.  But because of the decades of RSA abuse, people developed PTSD about small exponents with RSA, and some still break out in a cold sweat when you mention any exponent smaller than 65537.

* For certain exponents the cost may be a little lower with an appropriate choice of Lucas chain, but when $H(e) = 2$ as in $e = 3$ or $e = 2^{16} + 1$ there's not much improvement to be had over the naive square-and-multiply algorithm.

† Rabin-type cryptosystems use modular squaring, or ‘$e = 2$’, but they are qualitatively different from RSA-type cryptosystems.


How to deterministically generate a 256 bit ECC key from 128 bits of entropy without a CSPRNG

If you need a CSPRNG, there is no safe alternative.

Your assertions that “it's difficult to find a cross language, cross platform CSPRNG” and “SHA3-256, for which implementations are widely available” are contradictory. SHA3 implementations are not very common, whereas every cryptography library provides a CSPRNG. Furthermore, given a hash implementation, it is fairly easy to construct a CSPRNG: use either Hash_DRBG or HMAC_DRBG, both defined by NIST SP 800-09A. Hash_DRBG is slightly faster and HMAC_DRBG is slightly more resistant in case a weakness in the hash algorithm is found.


The easiest way to find a collision in 50 bits is to hash distinct values (random, incrementing, however's convienent), and put the results in a hash table, based on the 50 bits you're interested in.  When you insert a value into the hash table, and there's already an entry there, you've found a collision.

With 50 bits, you expect to have to hash around $2^{25}$ values, or about 30 million or so; if you're unlucky, you might run into 50 or 100 million before hitting a collision. That many entries easily fits into memory, and so this works out fairly well.


What telltale signs would indicate that quantum computers are about to become dangerous to classical cryptography?

There are three main standard quantum threats to traditional cryptography:

Shor's algorithm.  Spend $O(\log \ell \cdot \log \log \ell)$ quantum gates and $O(\log \ell)$ additional qubits in a quantum circuit to compute the period of a function $f$ bounded by $\ell$.  The number of quantum gates to compute $f$ is about the same as the number of classical gates, and the number of qubits is about double the number of classical bits to be reversible.

Standard examples:

Fix a group $G$ of order $q$, say $(\mathbb Z/p\mathbb Z)^\times$ for prime $p$, or the $k$-rational points $E(k)$ on some elliptic curve $E/k$ over a field $k$.  For $g, h \in G$, define $f(x, y) := h^y g^{-x}$.  If $h = g^n$ for some integer $n$, then $f(x, y) = g^{n y - x}$ and any period $(\delta, \eta)$ of $f$ satisfies $g^{n y - x} = g^{n (y + \delta) - (x + \eta)}$ for all $x$ and $y$ including zero, so that $0 \equiv n \delta - \eta \pmod q$, from which we can recover $n \equiv \eta \delta^{-1} \pmod q$.  Hence by finding a period $(\delta, \eta)$ of $f$, Shor's algorithm computes discrete logs.
Let $n = pq$ be a product of two secret large primes $p$ and $q$.  If for random $a \in \mathbb Z/n\mathbb Z$ the period of $f(x) = a^x \bmod n$ is $2r$ and $a^r \not\equiv -1 \pmod n$, then $\gcd(a^r \pm 1, n) \in \{p,q\}$, yielding a nontrivial factor of $n$.  If not—if the period of $f$ is odd, or if $a^r \equiv -1 \pmod n$—then try again with another $a$.  Hence by finding a period $2r$ of $f$, Shor's algorithm factors integers.

The current record for Shor's algorithm in 2012 computed the period of $x \mapsto 4^x \bmod{21}$, which is (spoiler alert!) 3, by reducing the machine to a single qubit and a single qutrit and computing bits of the period one serially, rather than two control qubits and five work qubits as the algorithm would generally require for integers of that size to give the answer all at once.

This record is not much of an improvement over the first report of Shor's algorithm in 2001, which computed a period of 2 or 4 for $x \mapsto a^x \bmod{15}$ using seven qubits without the qubit recycling that enabled the 2012 record to use fewer qubits.

To scale this up to numbers of thousands of bits, we would need a much larger quantum computer than that.  There are various estimates of how many qubits and quantum gates we need[cetacean needed].  Allegedly IBM has made a 50-qubit quantum computer, and Google has made a 72-qubit quantum computer, but nobody has reported successfully running Shor's algorithm on them.  Evidence that quantum circuits can be scaled up to run Shor's algorithm beyond a handful of qubits to find periods larger than 4 will be a necessary first step before it threatens cryptography based on abelian hidden subgroups.  The adiabatic quantum computer of D-Wave is unfit to run Shor's algorithm.  But:
Quantum annealing to factor by optimization.  Given $n = pq$, write $n = \sum_i n_i 2^i$, $p = \sum_i p_i 2^i$, and $q = \sum_i q_i 2^i$.  Knowledge of the bits $n_i$ of $n$ yields a system of quadratic constraints for the unknown bits $p_i$ and $q_i$ of $p$ and $q$.  This is a system of $O(\log n)$ equations in $O(\log n)$ unknowns.  Use classical computation to optimize away some of the unknown variables to reduce the system of constraints.  For example, we can posit that $p_0 = q_0 = p_{\lambda-1} = q_{\lambda-1} = 1$ since the factors are odd and of known size, where $\lambda$ is the size of the factors, typically 1024 for a 2048-bit modulus.  Then use quantum annealing on an adiabatic quantum computer to find the values of $p_i$ and $q_i$ minimizing $(n - pq)^2$ with $O(\log^2 n)$ qubits.

The current records for factoring by annealing in 2018 use 94 qubits to encode this optimization problem for 376289, along with >1000 additional qubits to implement the optimization on the D-Wave 2000Q.  The paper's estimate for the number of qubits to factor the current classical RSA-768 record with this method is 147456, in contrast to this ‘RSA-19’ problem taking 94 qubits—and that doesn't count the additional >1000 qubits needed to implement the program on the D-Wave machine.  (It is unclear to me whether those are counted in the $O(\log^2 n)$ growth curve advertised for this method, but I assume they are.)

One paper pointed out that other integers have been accidentally factored by the same method ‘without awareness of the authors’ of the prior method, but all this means is that the other integers turn out to have essentially the same set of constraints; it implies nothing about the cost of a high probability for success at factoring random semiprimes as chosen in RSA key generation.

D-Wave's computers seem to be getting bigger, but to my knowledge it remains unclear whether they actually provide quantum speedup at all vs. any specialized hardware to solve optimization problems.  Even if they do, it is unclear what the scaling of the time-to-solution will be as a function of the number of variables or constraints, which nobody seems to have attempted to address short of fitting a curve to small samples of experiments.  Answering these questions—is quantum annealing faster than classical annealing on specialized hardware, and how does time-to-solution scale for optimization-based factoring?—is a necessary first step before this technique will even begin to threaten cryptography based on factoring.
Grover's algorithm.  Spend $O(2^{n/2})$ time evaluating a boolean circuit in quantum superpositions of inputs to find a preimage among $O(2^n)$ possibilities.

There's some literature on experimental realizations[cetacean needed], including combining it with optimization-based factoring in a quantum circuit rather than on an adiabatic quantum computer[cetacean needed], but I'm out of time to bloviate about this for now.

Mitigations for Grover's algorithm are widely known, if excessively conservative[cetacean needed], by increasing symmetric key and hash sizes.  Grover's algorithm could in principle threaten factoring-based cryptography using Grover-ECM[cetacean needed], again requiring doubling of the prime sizes, but to my knowledge it doesn't improve attacks on modern elliptic-curve cryptography[cetacean needed].


Discrete logarithm with exponentiation oracle

No, there is no known way to recover $d$ using an Oracle that, given $m$, returns $m^d \bmod n$; there is also no proof that such a method does not exist.

Such a method would imply that the RSA problem (which is, given $m^e \bmod n$, recover $m$) is equivalent to the factorization problem (which knowledge of $d, e$ would allow you to solve); it is unknown if these two problems are equivalent.


The bottom of page 3 of your second link (the specification for LED) seems pretty clear:

"Note that for a 64-bit key $K$, all subkeys are equal to $K$, while for a 128-bit key $K$, the subkeys are alternatively equal to the left part $K^1$ and to the right part $K^2$ of $K$."

Basically, the input master key is split into a sorted list of nibbles, and whenever the algorithm needs subkey material it just uses nibbles directly from this sorted list -- moving each used nibble to the 'back of the line', so that all nibbles are used in succession.  Since the algorithm calls for 64 bits of subkey material at a time (16 nibbles), for a 64-bit master key every subkey will simply be the master key, and for 128-bit keys the algorithm will use the first 16 nibbles of the master key, and then the second 16 nibbles, and then the first 16 again, and so on.  The top of page 4 shows a diagram of how this works out for an 80-bit master key.

I would also point out that the subkeys are not used in each 'round' as stated in your question, but rather in between each step, where every step is composed of 4 rounds.  Each round consists of four operations, very similar to those used in AES -- first you xor a round constant into the state, then you replace each of the nibbles using a nonlinear substitution operation (the s-box from the cipher PRESENT), you transpose the nibbles, and then you 'mix' the nibbles by passing them through a highly diffusive linear permutation with a high branch factor (similar to MixColumns in AES, except optimized for nibbles).


Homomorphism and Zero Knowledge in FIPS 140-2 compliant systems

I'm no FIPS expert but I strongly suspect the answer is no. FIPS is incredibly restrictive and laughably behind the times.

To evaluate those algorithms that don't appear in FIPS, first make sure their component parts are secure (maybe even built with FIPS algorithms as subroutines). Then, if there are known answer tests anywhere, maybe from the authors of the algorithm, you can test the implementation against those. Do a thorough code audit, making especially sure that the malleability of a partially-homomorphic scheme does not lead to a side channel somehow.

If you get to this point, the schemes will be better-audited than 99% of crypto code, and you can probably sleep soundly knowing that you did the best you could with a non-standard algorithm.

As an aside, exactly what "homomorphic" and "zero-knowledge" techniques does it use? The term "zero-knowledge" especially is thrown around a lot in industry, so there's really no telling what they're doing without more info.


Can you help with that definition for a CCA?

In step 2, the adversary outputs two messages. One of these will be selected at random for encryption. You can think of the adversary sending these messages to a "challenger" that also has oracle access (or is the oracle itself). It doesn't really matter who is running the challenge since the challenger doesn't have any "intelligence." All the challenger does is flip a coin to choose a message and remember which message she chose, so she can determine if the adversary guesses correctly or not.

If you think of the adversary as an interactive Turing machine, then the values are put on its output tape (likely why it was phrased that way in the text).

The random bit is just a formalization of flipping an unbias coin. The challenger uses it to pick one of the two messages. If the ciphertext of a given plaintext is indistinguishable from any other ciphertext, then the adversary cannot know which one was chosen any better than predicating the value of the coin flip: which is one half. Therefore, if the adversary can demonstrate the ability to predict better than one half which message was encrypted, it must be the case that the encryption function causes the ciphertexts to leak information about the plaintexts (either by looking at the ciphertext or by submitting related ciphertexts for decryption). In this case, the system is not CCA-secure.


How to design a secure challange-response authentication protocol?

Is this protocol design secure?

See below.

  What would be the advantage to use HMAC (or any other MAC) instead of AES encryption?

HMAC was originally proposed as a construct that turns a Merkle-Damgaard hash function based on compression functions built from block ciphers, into a message authentication code. Although there's no decryption in HMAC, you can actually easily replace your AES decryption-based authentication with comparing HMAC-signed tags.

  Did I miss something?

What you're doing is essentially an authenticated security transport without confidentiality.

What you're missing is that you didn't authenticate the exchange following the initial authentication - this allows for connection hijacking, arbitrary injection of data packets, and more.

Therefore, you should use HMAC+[hash] or CMAC+[block cipher] to authenticate all of your messages exchanged, and also keep a counter as a state to detect duplicate packets and message replay attackes.


What security do digital signatures provide (like used when signing PDFs)?

You've stumbled on the requirement for authentication.

Recall that signature schemes have a private key and a public key. The private key is used to sign the document in question, and the public key is given to the verifying party so that they can verify that the signature is correct.

You're correct that it is possible to strip a digital signature and replace it with a fake one from, say, a different key. To defeat this, the verifying party needs to check that it has the correct public key to verify the signature. For example, the signer might coordinate with the verifying party a week ahead of time, in real life, and exchange keys physically (here, you could use some form of ID as authentication, since IDs include pictures). Or they might take the SSL route and use third-party certificate authorities. At any rate, they need some way to obtain the correct public key.

Then, if a man-in-the-middle attacker has replaced the signature with a fake one from the wrong key, when the verifying party attempts to verify the signature against their known-good public key, the verification will fail. The point here is that only the (proper) signing party knows the private key associated with the known-good public key, so only the signing party can generate an authenticate signature that will match that public key.

Thus, simply checking that a digital signature is present is not enough; one needs to computationally verify that the signature is correct using an authenticated public key, i.e. one that the verifying party knows for sure is "owned" by the alleged signer.


What is the definition of "security beyond the birthday paradox"?

For a MAC algorithm considered to be good, the best way to attack a MAC should be by collision (a birthday attack)

This means, that for MACs with $n$ bit tags an adversary will suceed with a forgery after having issued $q=O(2^{n/2})$ tag queries.

In the literature this bound is called the birthday barrier.

Now, if you are able to come up with a MAC construction for which you can prove that an adversary will require more queries, say $q=O(2^{2n/3})$ or $q=O(2^{5n/6})$ as for instance shown here, as given by the birthday bound, your MAC provides security beyond the birthday paradox.


How do I calculate e, d and N based on raw and encrypted message in RSA?

In general, you can't do that.  You have one equation and two unknowns (not three, since $d$ is uniquely determined by $n$ and $e$, even if actually computing it without knowing the factors of $n$ is difficult), so the solution will in general not be unique.

Of course, you could guess that $e$ might be one of the common values (e.g. 3 or 65537) and try to solve for $n$.  But that only works if you guess the right $e$.  And even if you do manage to determine $n$ this way, you'll still have to factor $n$ to be able to calculate $d$.

As for your code, it has many mistakes.  I have no idea why you're setting n = enc+1 or e = k * n, for example — neither of those make any sense whatsoever.  It looks as if you may be missing some fairly basic knowledge of either Python programming or the mathematics behind RSA.

As I can't really tell from just your code what it is that you might be missing, all I can suggest is finding some good tutorials and revising the basics.  And maybe ask for help from your instructor / TA / tutor / etc., if you have one available.


Why has the sponge construction's generic collision finding attack a complexity of O(min(2^(-n/2) , 2^(-c/2)))?

Denote the internal sponge state by
$$
S = R\mathbin\|C,
$$
where $C$ has size $c$ — capacity.

Every iteration a message block of length $|R|$ is xored into $R$ and then the permutation $P$ is applied. Therefore, if we obtain a collision in $C$ (which can be obtained in $2^{c/2}$ steps with the basic birthday attack), we could cancel any difference in $R$ by injecting an appropriate pair of messages.

So, if $(M_1,M_2)$ yields a zero difference in $C$ and difference $\Delta R$ in $R$,
the pair
$$
(M_1\mathbin\|X,M_2\mathbin\|(X\oplus \Delta R))
$$
is a collision pair for the full function $F$ for any $X$.


Why does decryption in RSA not fail with 2 different moduli?

The question assumes, wrongly, that $a^b\bmod n$ is the same as $a^{b\bmod n}$ or $a^{b\bmod n}\bmod n$. In general these are three different quantities, as demonstrated with $a=5$, $b=5$, $n=3$:
$$\begin{array}{}
a^b\bmod n&=&\left(5^5\right)\bmod 3&=&3125\bmod 3&=&2\\
a^{b\bmod n}&=&5^{(5\bmod 3)}&=&5^2&=&25\\
a^{b\bmod n}\bmod n&=&\left(5^{(5\bmod 3)}\right)\bmod 3&=&25\bmod3&=&1
\end{array}
$$
Note: going from the second to third expression of the last line uses the result obtained above.


Is 80 bits of key size considered safe against brute force attacks?

TL;DR: no longer unconditionally.
As of 16 Feb 2021, the Bitcoin miners hashed at an aggregate rate of $\approx154 \cdot10^{18}H/s$ according to this source, where one hash is two nested SHA-256; that is $\approx2^{93.0}$ SHA-256 per year.
Here is this data redrawn in SHA-256 per year with a $\log_2$ vertical scale, to facilitate comparison with key size in bits. I believe the notable growth in 2010-2011 was the rise of GPUs, while the 2013-2014 period corresponds to an increased use of ASICs. Nowadays, bitcoin mining is mostly performed using highly specialized ASICs. Recent hardware advertises 220 T SHA-256/s at 15 pJ/SHA-256 (3250 W power on wall) for \$3769. It's sold out, and the planet struggles with carbon emissions.

Thus 80 bit of security can not blindly be said good enough today. 80-bit may be very safe, or clearly not enough, depending on a variety of factors;

Value of the target
Time frame during which a break makes sense
How easier (or harder) it is to check a key compared to SHA-256, due to

use of entropy stretching,
the amount of memory necessary per search engine

Possibility of multi-target attacks, where the attacker's goal is to find any one in several target keys, and they manage to make the cost of testing a candidate key against all target keys mostly independent of their number. That's sometime straightforward (e.g. when a ciphertext block for the same known plaintext block is available block-enciphered under all the target keys).

Addition: I second everything in Thomas Pornin's answer (Feb. 2014), except perhaps "Right now, 80 bits still seem quite sturdy" which is only valid in some contexts, including the context of the question, at least at the time.
In the context intended for KATAN (really low-end devices such as RFID tags), an expectable consequence of key recovery is to be able to clone one single RFID tag. Recovering the key is likely feasible at far lower cost than brute force, by side channel attack or micro-probing, regardless of key size (even though testing a KATAN key requires significantly less work than performing one SHA-256). So right now (Nov. 2015), 80 bits of key is not a major weakness for an individual RFID tag key on rational economic grounds (if we discount the irrationally devastating effect of the announce of any break, and the more rational desire to not have to argue on key size if such break occurs). 80 bits would not be enough for the master key from which the RFID tag keys are derived, or some other uses of KATAN.


Quadratic sieve for DLOG performance - theory vs actual?

To my knowledge, there are two reports that deal with the crossover point between the Gaussian integer sieve—which is the rough analogous of the quadratic sieve for discrete logarithms—and the number field sieve over prime fields:

Weber (1998) computed discrete logarithms over a 85-digit (~283 bits) prime, and concluded that at that size point the Gaussian integer sieve was faster.
Joux and Lercier (2003) not only compared the two algorithms, but made some improvements of their own to the number field sieve for discrete logarithms. They concluded that the number field sieve was faster already at the 100-digit (~332 bits) range.


Dieharder input data format. Do I need new line at the end?

Looking at the source, file_input_get in dieharder-3.31.1/libdieharder/rng_file_input.c: you are safe with a single newline after the last decimal number, as supplied by Java's writer.println. You do not need an extra newline. If there was a problem, DieHarder would stop with "# file_input(): Error: EOF on (filename)" or "Error: converting (stuff) failed. Exiting."

But this is kinda off-topic.


Detecting the amount of entropy used for random number generation

Suppose we have some seed-extensible PRG, meaning, it can operate on seed of any length $l$, and extracts a pseudorandom string in time polynomial in $l$ and the output length. What you are asking is: given a pseudorandom string produced by this PRG, can I find the input length $l$ that was chosen?

The number of bits of entropy fed as seed to a cryptographic pseudorandom generator can be seen as the security parameter $\lambda$ for the system. The security of your PRG (assuming it is a cryptographically strong PRG) states that any adversary that runs in time polynomial in $\lambda$ cannot distinguish the pseudorandom output from a random string. In particular, if it cannot distinguish it from a random string, it cannot tell anything at all about the input length that generated it. Therefore, either you have chosen $\lambda$ so that breaking the security of the PRG takes too much time for the adversary, and he will in this case not be able to tell the seed length either, or you have set up $\lambda$ to be a too small value, in which case the adversary will indeed find out the seed length, but also break the security of your PRG.


CryptoJS.AES result always has same first few bytes?

If you decode the resulting cipher text with a base64 decoder it says:

Salted__XXXXXXXXXXX

Where XXXX changes, but "Salted__" doesn't. So I guess it is a prefix added to the ciphertext to define its format.


How to cipher with N public keys and decipher with ANY of the N private keys?

Pick your favorite KEM, say RSA-KEM.  Let $P_1, P_2, \ldots, P_n$ be the public keys, and $(k, c) = \operatorname{Encap}(P)$ be a random key $k$ and encapsulation $c$ of the key that can be opened by $k = \operatorname{Decap}(S, c)$ if $S$ is the secret key corresponding to $P$.

Let $(k_i, c_i) = \operatorname{Encap}(P_i)$.  Pick $k$ uniformly at random and yield $$c = ((c_1, k'_1), (c_2, k'_2), \ldots, (c_n, k'_n)), \quad\text{where}\quad k'_i = k \oplus k_i,$$ as the encapsulation of $k$.  Then use $k$ as a key for a DEM, or authenticated encryption, say NaCl crypto_secretbox_xsalsa20poly1305, to transmit your message.  The $i^{\mathit{th}}$ recipient can recover $k$ by decapsulating $k_i$ from $c_i$ and computing $k = k'_i \oplus k_i$ and thereby decrypt the message.


Is there a feasible way to generate an RSA key manually the same way as it is for an ECC one?

You can pick a 1024-bit prime more or less uniformly at random by flipping only 256 coins.  But there's additional computational cost to it.  Here's a naive algorithm that is deterministic after the initial coin flips:

Flip 256 coins, yielding a bit string $s$.
Compute $p_0 = \operatorname{SHAKE128-1024}(s) \mathbin| 1$ and interpret it as an integer in little-endian bit order.  (The $\cdots \mathbin| 1$ forces it to be odd, saving you the wasted effort of testing a large even number for primality.)
Compute a primality certificate for $p_0$, such as a Pratt certificate (which requires computing the prime factorization of $p_0 - 1$) or a Pocklington–Lehmer certificate (which requires computing half the prime factorization of $p_0 - 1$, up to a composite factor below $\sqrt{p_0 - 1}$) or an Atkin–Goldwasser–Kilian–Morain elliptic curve primality proof certificate (which requires a ~512-bit prime, and doing some arithmetic on an elliptic curve).
If it turns out that $p_0$ is composite, then try again with $p_1 = p_0 \pm 2$, and so on.  If you hit $2^{1024}$ or $2^{1023}$, you probably made a mistake.

Generating an RSA key.
You can use the same 256-bit seed $s$ to pick both prime factors $p$ and $q$ of an RSA modulus $n$, e.g. by splitting the output of $\operatorname{SHAKE128-2048}(s)$ into two 1024-bit integers $p_0$ and $q_0$ instead of step (2).  You will also want to try again with the next candidate if you get $\gcd(e, \operatorname{lcm}(p - 1, q - 1)) \ne 1$, where $e$ is your favorite exponent, which ought to be 3 or 65537 unless you have eclectic taste in exponents.

Efficiency.
There are variations on the theme: you can use trial division to save some work, for instance, or use a fancier faster sequence of trials at small cost to uniformity of the distribution (but be careful or else you might have a billion-euro mistake on your hands).

Obviously, step (3) costs a lot more computation than generating an elliptic-curve scalar uniformly at random, even if you do the rejection sampling necessary to avoid the (negligible) modulo bias.  What's the exchange rate between computation and coin flips?

You can save a lot of computation by doing a fast probabilistic primality test first, like 128 independent Rabin tests, which gives reasonably high confidence that you found a prime, but this costs a lot more coin flips.

If you believe in the extended Riemann hypothesis, you could even avoid the additional coin flips and use a deterministic variant, the Miller test (paywall-free), which is named after the person who first republished the novel result of Russian mathematician М.М. Артюхов in English.  It might even perform better than finding an ECPP certificate.

Choice of prime vs. primality testing.
All this will take quite a lot of effort with the computational power of pen and paper.  But you could write a computer program to do everything past the coin flips in step (1), and feed that computer program the outcomes of your coin flips.  Even if it uses a probabilistic primality test, the choice of the prime will be (unless the primality test goes haywire) a deterministic function of the coin flip outcomes.

With a primality certificate, as a bonus you get a verifiable proof that it is prime, which you can independently verify in case a god with a cosmic ray gun angry at your computational arrogance decided to disrupt your faster-than-pen-and-paper computer.

(You might want to keep the certificate secret too.)


How to solve this decryption algorithm given the encryption algorithm?

Here's a hint about the second part of the question:

b. Is the given system perfectly secure? Prove your answer.

Hint: what is the encryption of the plaintext $(0, 0, 0, 0)$?  If the ciphertext is something other than $(0, 0, 0, 0)$, what can we infer about the plaintext about that?


MIT says: mathematical theory behind encryption is wrong. What are the consequences?

So the article is fluff, the details can be found in the linked paper.  The just of it is a refutation of the following assertion: if you have a set of symbols chosen with identical independent distributions and subject to some kind of coding, the result can be approximated as a uniform distribution.

The paper asserts, with a few citations to some examples, that this is a common cryptographic assumption. It is, as far as I can tell from reading the literature and talking to other practitioners, not a common assumption at all. In fact, in standard encryption systems, we assume that the plaintext is chosen with a known distribution that can be arbitrary(indeed, attacker chosen), and keys are chosen randomly.

In practice, keys are not chosen randomly, they are chosen using cryptographically secure random number generators. Those can fail, but not in the way the paper is talking about.

Certain papers, such as maybe the cited ones about biometrics and  passwords, might make this erroneous assumption, but it's not common and certainly  doesn't relate to what most non-practitioners would consider "encryption."

Moreover, it appears that you still can't make guesses about messages in polynomial time with this technique, you can just make them in faster exponential time. It depends highly on how the assumption was used if this maters in practice. Not having read the papers which do make this assumption, I can't say for sure, but if doing this breaks those systems in a practical sense, the schemes likely had other issues.

A better title for the article is: a few cryptographers made some dumb mistakes. Mistakes neither pervasive or of massive consequence.


Why is AES resistant to known-plaintext attacks?

A known-plaintext attack (i.e. knowing a pair of corresponding plaintext and ciphertext) always allows a brute-force attack on a cipher:

Simply try all keys, decrypt the ciphertext and see if it matches the plaintext.

This always works for every cipher, and will give you the matching key. (For very short plaintext-ciphertext pairs, you might get multiple matching keys. Then you need to try more pairs to eliminate the wrong ones).

If you have no known plaintext, only the ciphertext, you can do it similarly, but you also need a function which says whether what you decrypted is a plausible plaintext.

The problem with try all keys is that for every modern cipher (i.e. key sizes of 128 bit or more) the key space is that large that you need much more time than the remaining lifetime of the universe to check a significant portion of all keys.

So, the question is, are there any attacks which are faster than brute-force?

For now, there seem to be some attacks which are slightly faster (like needing only $2^{125}$ steps instead of $2^{127}$ for brute-force, a bit better for the 256-bit-key version) and needing either a really large amount of chosen plain- or ciphertexts (and knowing the result), or even larger amounts of known plaintexts. These are still not practically doable in our world.

There are no proofs that AES (or any block cipher) is really secure, only the heuristic "many smart people tried to break it and until now, nobody was successful" (or at least, nobody who succeeded told the public).