No, $e=N$ is no less secure than any other value of $e>1$.

In fact, we can make a stronger statement; if setting $e=N$ allows us to compute the corresponding $d = N^{-1} \mod \phi(N)$, then we can factor $N$ (and hence we can find the $d$ corresponding to any $e$).  This is due to the fact that knowledge of any nontrivial pair $(d,e)$ with $d \cdot e = 1 \mod \phi(N)$ allows us to efficiently find the factorization of $N$.

We don't use $e=N$, not because of security reasons, but because of efficiency. Setting $e=N$ makes the public key operation (encryption, signature verification) far more expensive than it would be if we set $e$ to a small value; given that a large $e$ typically would have no advantage to make up for that, we generally don't use large $e$.

Historical note: when Clifford Cox initially devised his varient of RSA (which wasn't declassified until well after RSA was published), he actually had $e = N$.


SPHINCS and HORST: can we sign the same message twice?

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme.

Actually, Sphincs as originally proposed is deterministic; however there is nothing preventing a signer from selecting a path randomly (rather than making it a secret function of the message).

But yes, if we assume that a signer doesn't decide to do this, you are correct; signing the same message twice will produce the same signature.

  Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?

I'm not sure what a 'replay attack' would mean for a signature algorithm.  For any signature algorithm, the adversary can take a message and valid signature pair, and present it multiple times; the verification algorithm would accept it every time; this is not unique to Sphincs.  Now, there may be other things in the protocol to reject this situation; that's not the job of the signature verification algorithm.

In addition, seeing the same signature multiple times would inform the adversary that the same message was being signed multiple times; on the other hand, we don't assume that signature algorithms provide privacy, and so that is also not considered an issue.

BTW: if you look at Sphincs+, things change; they made the signature algorithm nondeterministic (not because they are afraid of determinism, but instead to try to avoid relying on collision resistance of the hash function; everything else within Sphincs+ relies on preimage or second preimage resistance).


"Fine grain Cross-VM Attacks on Xen and VMware are possible" and OpenSSL 0.9.7

Actually the authors used both OpenSSL 0.9.7 and 1.0.1; they detail the differences between the versions, what changed in the implementations, and what they can do from other VM.

They refer to 0.9.7 because that was the version used by Bernstein in 2003 when he worked on cache-timing attacks on AES. This allows to highlight how much (or how little) the cross-VM boundary complicates things for the attacker. They also did tests on 1.0.1, since that's the current, modern version.


Cracking short ciphertexts made by Vigenère cipher

You used the same key for both words so we can start with the obvious: both words start with the same letter and end with the same four letters.  We can process your initial word list, picking out sets of words that match this pattern.  Then just brute force each possible pair within each set until we find one or more pairs.  Work back from the first possible word of a pair to the key, and then forward to the encryption of the second possible word.  Check whether or not it matches "XDBEWUMHNL".

If there is more than one matching pair, then we would need more information.


If hash functions append the length, why does length extension attack work?

Let hash be the raw hash function, as you're referring to. You mentioned that the attacker knows hash(message || length), but to be more precise, they know hash(message || padding || length). Let full_hash be the proper hash with padding and length, i.e. full_hash(message) = hash(message || padding || length).

You're correct that if the attacker knows hash(message || padding || length), then they can't compute hash(message || appended_data).

But they can compute hash(message || padding || length || appended_data || actual_padding || actual_length) which is equal to full_hash(message || padding || length || appended_data), which may be enough for an attack. The inner padding and length become "garbage" which can be ignored depending on the attack scenario.

In order to carry out the attack, start from hash(message || padding || length) (i.e. the original hash), use it as the initial state for the hash, and then feed the remaining data (appended_data || actual_padding || actual_length).


$w$ is a parameter that can be freely chosen, to maximize performance.   Each element of the signature encodes $w$ bits of the message to be signed, so the larger $w$ is, the fewer elements you need to include in the signature.

If you make $w$ large, then signatures can be shorter; however, the tradeoff is that key generation, signing, and verification run slower.  If you make $w$ small, then signatures are longer; however, key generation, signing, and verification run faster.  So this is a tradeoff between the size of the signatures vs the running time of the scheme.  You can choose $w$ to provide the best tradeoff for your application.  The scheme will be secure no matter what value of $w$ you choose.


Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?

The question asks to prove the (true) fact that, in order to perform point addition $R\gets P+Q$ graphically on an Elliptic Curve over the field $\mathbb F_p$ of equation
$y^2\equiv x^3+a\,x+b\pmod p\tag{1}\label{fgr1}$
with $p$ suitably small (here $p=29$, $a=4$, $b=20$) and
$4\,a^3+27\,b^2\not\equiv0\pmod p\tag{2}\label{fgr2}$
we can (except in the special case¹ of $P$ and $Q$ equal or on the same vertical line) perform the geometric construction of $R$ per the figure

Draw on a (black) square grid of side $p$ the points of the curve (blue dots) other than the neutral².
Draw a red line that starts from $P$ parallel to and in the direction of $\overrightarrow{PQ}$.
As soon as the line hits a point of the curve other than $Q$, call it $R'$; then on the vertical (purple) line going thru $R'$, find another point of the curve and call it the result $R$ of $P+Q$.
If the red line hits a side, draw an horizontal or vertical (green) line from there to the opposite side; then from that intersection keep drawing the red line parallel to and in the direction of $\overrightarrow{PQ}$, and iterate to the above bullet.

After drawing the red line for a displacement of $d$ along the $x$ axis starting from $P$, and accounting for the wraparound on the sides, the pen drawing the red line has coordinates
$\begin{align}x&=(x_P+d)&\bmod p\tag{3}\label{fgr3}\\ y&=\left(y_P+d\,\frac{y_Q-y_P}{x_Q-x_P}\right)&\bmod p\tag{4}\label{fgr4}
\end{align}$
with the computations in $\mathbb R$. Justification: What's on the left of the $\bmod$ operator³ in $\eqref{fgr3}$ and $\eqref{fgr4}$ is the position of the pen having moven by $d$ along the $x$ axis if we did not wraparound on black edges. The $\bmod$ operators capture the effects of the wraparound.
The points on the red line with both coordinates an integer (including but not limited to any point of the curve) thus have a corresponding $d$ an integer, and verify
$(y-y_P)(x_Q-x_P)\equiv(x-x_P)(y_Q-y_P)\pmod p\tag{5}\label{fgr5}$
And any $(x,y)$ matching this equation would be on the red line if we kept drawing it indefinitely; $P$ would be reached when $d=p\,(x_Q-x_P)$ (or earlier).
It follows that our graphical search procedure for $R'$ hits a point of the curve (and thus terminates), and yields a point $R'$ which coordinates $(x,y)$ involves integers that verify $\eqref{fgr1}$ and $\eqref{fgr5}$. But we have not shown yet that $R$ obtained from $R'$ is the expected point (we have not ruled out that $R'=P$ or some other unwanted point of the curve).
An intuitive argument is that when we remove the $\bmod p$ from equations, and work in the field $\mathbb R$ instead of $\mathbb F_p$, $\eqref{fgr5}$ becomes the equation of the line going thru $P$ and $Q$ in the Euclidean plane (with coordinates in $\mathbb R$). Our graphical procedure that draws the red line and finds a third point on the curve that the line intersects is thus a mere translation⁴ in field $\mathbb F_p$ of the graphical construction of point addition on the curve with the same equation in the field $\mathbb R$, and must thus "work", in the sense of yielding a commutative group law on the set of curve points and neutral.

Alternatively, we can make an analytical proof that this graphical procedure terminates and yields the same $R$ as the usual formulas for point addition on the curve of equation $\eqref{fgr1}$ with $\eqref{fgr2}$, that is when $x_P\ne x_Q$
$$\begin{align}
\lambda&\gets(x_Q-x_P)^{-1}(y_Q-y_P)&\bmod p\tag{6}\label{fgr6}\\
x_R&\gets\lambda^2-x_P-x_Q&\bmod p\tag{7}\label{fgr7}\\
y_R&\gets\lambda(x_P-x_R)-y_R&\bmod p\tag{8}\label{fgr8}
\end{align}$$
Note: In this, all quantities are elements of $\mathbb F_p$, or equivalently integers in range $[0,p)$. In particular, $(x_Q-x_P)^{-1}$ is a modular inverse.
Proof sketch, which mostly⁴ parallels a possible demonstration of the point addition formulas for the same equation in the field $\mathbb R$:

We analytically show that $\eqref{fgr1}$ and $\eqref{fgr5}$ are verified by $(x,y)\gets(x_R,(-y_R)\bmod p)$ computed per $\eqref{fgr6}$, $\eqref{fgr7}$, $\eqref{fgr8}$.
The condition $\eqref{fgr2}$ allows to prove $x\ne X_P$ and $x\ne X_Q$.
Thus the point with these coordinates $(x,y)$ is on the red line drawn indefinitely, and neither $P$ nor $Q$.
When we eliminate $y$ from equations $\eqref{fgr1}$ and $\eqref{fgr5}$, we get a cubic equation in $x$ in the field $\mathbb F_p$. It thus has at most 3 distinct solutions. Two of these are $x_P$ and $x_Q$, and the third is the above $x$, neither $x_P$ nor $x_Q$.
Since our graphic procedure start from $P$ and skips $Q$, it must reach a point with that $x$ before reaching $P$ again.
Hence the $R'$ of our search procedure has the $x=x_R$ of $\eqref{fgr7}$
Points of the curve on the same vertical line share the same $x$, thus the same $y^2\bmod p$ per the curve's equation. It follows that the $R$ graphically constructed has the coordinates $(x_R,y_R)$ of $\eqref{fgr7}$, $\eqref{fgr8}$, Q.E.D.

¹ This special case subdivides into

$P\ne Q$, in which case $P+Q$ is the neutral².
$P=Q$. One graphical construction chooses two distinct points $S$ and $S'$ on the same vertical line, both distinct from $P$, and computes $(P+S)+(P+S')$. When $S$ can be chosen on the same horizontal line as $P$, that simplifies drawing the red line for $P+S$. I know no more direct graphical analog to the "tangent" technique used for a curve in the field $\mathbb R$.

² The neutral is an extra point of the curve, not on the figure, often noted $\infty$ or $0$, such that for any point $S$, $S+\infty=S=\infty+S$.
³ The $\bmod$ operator has a canonical extension from $\mathbb Z$ to $\mathbb R$: we can define $u\bmod m$ with $u\in\mathbb R$ and $m\in\mathbb R_+^*$ as $v\in \mathbb R_+$ with $v<m$ and $(u-v)/m\in\mathbb Z$.
⁴ The only operational difference is that for the Elliptic Curve in the field $\mathbb R$ we must draw the red line in both directions, when that's optional here because we're in a finite set and the line ultimately wraparounds back to $P$.


If the message is small enough to be stored in full with the signature in the embedded device, and the software on the embedded device is trusted to not be altered (including the embedded public key) or worked around (a JTAG port or a clever upset can change PC across a test), this is fine, and an intended usage of ECDSA. Most implementation traps are on the signing side.

I doubt that "pretty much anything else is beyond the resources of the device", though. RSA (or Rabbin) signature verification in software is much simpler (thus uses less code) and much faster (like a factor of 10 for usal key size) than ECDSA signature verification. Reasons to prefer ECDSA in this particular application can only be:

RAM is horribly limited; but 1k byte (used only during signature verification) is ample for RSA-2048.
The signature size matters much (it's 256-byte with RSA-2048 versus 56-byte for ECDSA P-224 or ECDSA P-256/secp256r1 or secp256k1) and we can't use RSA signature with message recovery (ISO 9796-2) because

the signature must be separate from the message (RSA signature with message recovery embeds part of the message in the signature, e.g. 222 bytes in a 256-byte signature; that part becomes available only as a byproduct of signature verification)
or the message is too small (below 200 bytes) for message recovery being a space saver.

Performance on the signer side is a limiting factor. ECDSA (or better, EdDSA as in Ed25519) has a clear edge there.
Some regulation/constraint prescribes ECDSA (like there's already an implementation, and there's not one for RSA, and time to market is the essence).
(Update per comment): code size; but that can only realistically be when there's already some code (ECDH) that already does a large fraction of ECDSA, and uses arithmetic code that for some reason can't be re-purposed for RSA  (e.g. it handles fixed-size arguments only; or its modular reduction is specialized for moduli of a certain form); and space is badly missing, as RSA itself can fit under 3kByte including public key (add <1.5kByte for SHA-256).


Shor's algorithm for discrete log and periodic function

Knowing the period of the second function cannot help you, because you already know it (at least for common Diffie-Hellman setups)!

First note that the period $\omega$ of $f(x_1)=b^{x_1}\bmod p$ is the order of $b$ because $f(0+\omega)=f(0)=1$ is implied by the general definition of a period $\forall x\in\mathbb Z:f(x)=f(x+\omega)$.

Now assume that $p$ is a safe prime (as is common for Diffie-Hellman). By Lagrange's theorem, we know that all multiplicative subgroups must have order $1,2,p-1$ or $\frac{p-1}{2}$ (the only divisors of $p-1$ by construction of $p$). Note that all these 4 values are trivially publicly computable.

Now notice that $f(x)$ generates a multiplicative subgroup of $\mathbb Z^*_p$ (similarly to how the generator works in DH). So this subgroup must have one of the 4 possible orders from above, which we already know. So we have learned nothing new by finding the order of the public key.


Streaming API to authenticated encryption

As pointed in the question, a conservative API to authenticated encryption should only ever release authenticated plaintext on the deciphering side. Anything else is too open to attacks (padding, timing, denial of service, unamit).

In a streaming API, this forces aggregation of data into blocks, each authenticated. The simplest method is fixed size ciphertext blocks (blocking related to characteristics of plaintext, e.g. at end-of-line for text, is too susceptible to information leak; on-demand blocking by the receiver requires feedback on the communication link, that could leak information, and is overly complex).

One obvious drawback of blocking is that it increases the overhead; however, even with 128-bit overhead per block (which is enough for an IV and authenticator), 8kiB blocking leads to less than 0.1% overhead, and this is acceptable in many use cases. That's basically what the OP is proposing.

One other very real problem with this blocking strategy is that we must resist suppression, duplication, and reordering of authenticated blocks by an adversary, with the intend of altering the plaintext correspondingly. The scheme proposed in the question does not, and is vulnerable to these attacks.

To correct that, one method is to include a block sequence number in the authenticated data, starting at 0 at start of data, and incremented by one at each block. That does not even necessarily increase the size overhead, as this block number needs neither to be encrypted, nor explicitly transmitted. Using GCM, we can have this block number implicitly included in the authenticated data, but not transmitted. With an Encrypt-then-MAC authenticated encryption, we can insert the block number after encryption and before MAC-ing. With a MAC-then-encrypt authenticated encryption, we can enter this block number in the MAC-ed data, and remove it before encryption.

Another method to correct that is to use a different key for each block, generating them with a fast KDF.

With such tweak, I do not see any systematic flaw in the use of authenticated encryption with blocking, packaged in a streaming API to authenticated encryption, beyond the obvious inherent (but practically acceptable) dangers, in particular

the adversary can interrupt the flow of authenticated data and deduce something from how the receiver reacts to that, especially if there is a retry mechanism other than "redo from start".
the receiver is likely to perform actions detectable by the adversary on the basis of what is in a block; that's enough to leak information that would not leak in non-blocked authenticated encryption (for example, assume the plaintext is known to contain either 98 or 99 ! characters, with spacing much higher than the block size, each ! causing a power consumption burst on the receiver side, and the adversary gets a power meter reading every second allowing to reliably discern if that burst occurred or not. Then when blocking is used, she can use that to determine whether there are 98 or 99 ! characters, by restricting the flow of information to one block between two meter readings; something that likely would not be possible without blocking assuming there is 5% uncertainty in the difference between two consecutive power readings).


Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?

Yes, the problem of finding unknown random $x\in\mathbb Z_N$ given $N\in\mathbb N$, $u\in\mathbb N$ with $1<u\le\lceil\log_2N\rceil$, and $x^u$ computed in $\mathbb Z_N$, is believed hard unless the factorization of $N$ can be determined, which itself is believed hard for appropriately constructed RSA moduli $N$. Moreover, depending on $u$ and $N$, there might be several solutions with no way to tell the right one (if $u$ is odd and $N$ squarefree with no divisor up to $\lceil\log_2N\rceil$ then there is a single solution). Notice that I have excluded $u=1$ (which the question allows), for it makes finding $x$ trivial.

When $u$ is odd this is the RSA problem with small exponent, which is believed hard when the factorization of $N$ can't be determined (with the caveat that a usual definition of that problem asks that $N$ is squarefree and without small divisors).

When $u$ is $2$, this is the square root modulo unknown composite problem, which is demonstrably hard when the factorization of $N$ can't be determined.

Ability to consistently solve both that square root problem and the RSA problem implies ability to find a solution to the question's problem, by writing $u$ as $e\cdot2^s$ with odd $e$, solving the RSA problem for exponent $e$, and solving the square root problem $s$ times.

Addition: this answer is for version 5 of the question. As correctly noted in another answer for an earlier version of the question, knowing that $N$ is a square does not make the problem easier if the factorization of $N$ remains unknown.

Further addition following comments:

It is easy to find the inverse of any given element of $\mathbb Z_N$ when its exists, using the Extended Euclidian algorithm.
It is hard to exhibit $a\in\mathbb Z_N$ that has no inverse modulo $N$, other than $0$ or a multiple of an easily found factor of $N$ (argument: if such an $a$ was found, then $\gcd(a,N)$ would be a non-trivial divisor of $N$  contributing towards finding the full factorization of $N$).
If $\gcd(u,N)=1$ (which we'll assume hereafter), it is thus easy to find non-negative integers $v$ and $k$ with $u\cdot v=k\cdot N+1$, otherwise said with $v\equiv u^{-1}\pmod N$.
It does follow that $\forall x\in\mathbb Z_N$, $(x^u)^v=x^{k\cdot N+1}=(x^N)^k\cdot x$.
That does not seem to help finding $x$, because we have nothing telling us that $x^N=1$; on the contrary, $x^N=1$ seldom holds when $x\ne 1$; in particular $x^N=1$ holds only for $x=1$ when $N$ is prime, since in this case: $\forall x\in\mathbb Z_N$, $x^N=x$ by Fermat's little theorem.


If someone had a list of all primes, would it be possible for them to factor any integer in polynomial time?

Mathematically, yes, it will work. Practically, you will require an extremely very long time and an incredible amount of energy, considering the sizes of the primes  involved in RSA (usually around 1024-bit prime numbers). It is about billion and billions of years and billions and billions times the energy of the whole universe (RSA: How effective is this keypair-trash attack)


What are the benefits of the two permutation tables in DES?

The initial and final permutation have no influence on security (they are unkeyed and can be undone by anybody). The usual explanation is that they make implementation easier in some contexts, namely a hardware circuit which receives data over a 8-bit bus: it can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit area) than a single 64-bit register. This process "naturally" performs the initial permutation of DES.

In more details: Suppose that you are designing a hardware circuit which should do some encryption with DES, and receives data by blocks of 8 bits. This means that there are 8 "lines", each yielding one bit at each clock. A common device for accumulating data is a shift register: the input line plugs into a one-bit register, which itself plugs into another, which plugs into a third register, and so on. At each clock, each register receives the contents from the previous, and the first register accepts the new bit. Hence, the contents are "shifted".

With an 8-bit bus, you would need 8 shift registers, each receiving 8 bits for an input block. The first register will receive bits 1, 9, 17, 25, 33, 41, 49 and 57. The second register receives bits 2, 10, 18,... and so on. After eight clocks, you have received the complete 64-bit block and it is time to proceed with the DES algorithm itself.

If there was no initial permutation, then the first step of the first round would extract the "left half" (32 bits) which, at that point, would consist of the leftest 4 bits of each of the 8 shift registers. The "right half" would also get bits from the 8 shift registers. If you think of it as wires from the shift registers to the units which use the bits, then you end up with a bunch of wires which heavily cross each other. Crossing is doable but requires some circuit area, which is the expensive resource in hardware designs.

However, if you consider that the wires must extract the input bits and permute them as per the DES specification, you will find out that there is no crossing anymore. In other words, the accumulation of bits into the shift registers inherently performs a permutation of the bits, which is exactly the initial permutation of DES. By defining that initial permutation, the DES standard says: "well, now that you have accumulated the bits in eight shift registers, just use them in that order, that's fine".

The same thing is done again at the end of the algorithm.

Remember that DES was designed at a time when 8-bit bus where the top of the technology, and one thousand transistors were an awfully expensive amount of logic.


Is there any block-cipher, format-preserving or similar encryption method with known cycle size? (without short-cut, with known source/runtime vars)

CAUTION: The following matches the requirement "no short-cut in computing $m_i$ is allowed. It always either require the knowledge of  $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$" only with respect to an adversary not knowing the key. That goes straight against the added requirement that an adversary has "access to runtime variables".

Well make an explicit construction from an $n$‑bit block cipher $E$ with the desired keyspace. Note $D$ the matching decryption.
Make a public partition of the blockspace $\{0,1\}^n$, assimilated to $[0,2^n)$ by e.g. big-endian convention, into intervals of size $c$ or slightly more according to the allowance for $k$. When $c$ is a power of two (e.g. $c=2^n/8$), that can be $2^n/c$ intervals of size $c$. When $\left\lfloor2^n/c\right\rfloor\ge(2^n\bmod c)$ [thus including any case with $c\le2^{n/2}$ ], that can be $\left\lfloor2^n/c\right\rfloor-(2^n\bmod c)$ intervals of size $c$, and $2^n\bmod c$ intervals of size $c+1$.
Define $h$ the bijection on $\{0,1\}^n$ that, to $x$ in a certain interval of said partition, associates the next integer in said interval if that's still in said interval, or the first integer in said interval otherwise. When $c$ is a power of two, that can be $h(x)\underset{\text{def}}=c\left\lfloor x/c\right\rfloor+(x+1\bmod c)$.
Define $f\underset{\text{def}}=D\circ h\circ E$. That is $f$ the bijection on $\{0,1\}^n$ with $f(x)=D(h(E(x)))$. That $f$ has the property "After applying the function $c$ times (within allowance) it will result in $m_0$ again" thought in the question, and has matching decryption $f^{-1}=D\circ h^{-1}\circ E$.

I conjecture that under the ideal cipher model for $E$, the resulting block cipher $f$ is secure when the number of (adaptive) queries an adversary can make remains negligible compared to $c$.
One slight implementation difficulty is avoiding side-channels in the implementation of $h$ and $h^{-1}$.


Bitwise operation question with shifting involved

Actually, you want to solve it from the LSB side.

First, solve for the 3 LSBs of X; we can see that the 3 LSBits of the left hand side of ((X XOR a)+b)<<3 = (X+c) XOR d doesn't actually depend on X (and there's no propogation anywhere from the higher order bits of X, so they can be ignored for now), so it's effectively a simple equation, easily solved.

Then, solve for the next 3 LSBs of X; again the 6 LSBits left hand side doesn't depend on those bits (it does depend on the 3 LSBits of X, but we already know those); again, that portion of X is easily solved.

So, just keep on iteration until we have all the bits of X.

One thing we can see from this process is that there is always exactly one solution for X for any (a, b, c, d) values.


Are cryptographic hash functions perfect hash functions?

If a hash function is a random oracle, which is about as perfect as can be expected for a hash function, then we actually expect a lot of collisions. If the hash function output is in a space of size $N$ (e.g. $N = 2^n$ for a "$n$-bit output") then collisions are expected, on average, when about $\sqrt{N}$ distinct inputs are hashed (see the birthday problem for more details).

If you want to feed the $2^n$ possible sequences of $n$ bits to a hash function $h$, which produces $n$-bit outputs, and such that no collision occurs at all, then $h$ must severely depart from the normal hash function model -- in a way, it must be quite imperfect. This calls for a pseudo-random permutation. Think of it as a block cipher which you can compute in the "encrypt" direction but not the "decrypt" direction.

I am not aware of good constructions for that. Some attempts include RSA: let $N$ be a RSA modulus of unknown factorization, and $e$ the public exponent; then $m \mapsto m^e \pmod N$ is a one-way permutation of the set of integers modulo $N$. But it is not completely "random looking" (it is one-way on average) and requires a big $N$. Other constructions can use elliptic curves, but still with some drawbacks and caveats.


Schnorr protocol: how does malicious verifier win?

This all seems to be explained in the book (warning: large) you mention, all I mention here is taken from there.

This is the last sentence before $\S18.3.2$:

  Enlarging challenge size not only improves performance (a positive result), in $\S18.3.2$ we will further see that this also has a negative consequence. Be careful, size matters!

This last sentence is of critical importance, but we will focus on the first one for now. Moving to $\S18.3.2$, we find the last sentence before $\S18.3.2.1$:

  However, there is a subtlety for the problem. Let us examine it now.

This is followed by about 2 pages of explanation to your question, which indeed they agree to have subtleties. Although you have read all the internet twice (kudos), your answer suggests you may have missed this.

It seems that setting

  $${\tt Challenge}={\tt prf}(M||{\tt Commit})={\tt prf}(M||g^{\tt Response}y^{\tt
> Challenge}\bmod{p})$$

leads to two options:

  The equation was constructed by Alice using her private input, and hence Alice discloses the fact that she has been in interaction with,
  and fooled by, $\tilde{Bob}$, or
  $\tilde{Bob}$ has successfully broken the pseudo-random function ${\tt prf}$ of the large output space $\mathbb{Z}_q$, because he has
  constructed equation $${\tt Challenge}={\tt prf}(\cdots y^{\tt Challenge}).$$ This is a well-known hard problem because ${\tt prf}$
  is assumed to be one-way.

  Given that $\tilde{Bob}$ is assumed to be polynomially bounded, the
  third party will of course believe that (i) is the case.

The information revealed is thus the fact that the prover has been interacting with the malicious verifier. Luckily, the authors mention that

  A small consolidation for Alice is that the information disclosure caused by $\tilde{Bob}$ is not a too disastrous one (though this assertion has to be based on applications really). [...] the proof transcript still does not disclose to $\tilde{Bob}$ or a third party any information about Alice's private input $a$.


Determining the degree of freedom for a chi-squared test on a strict avalanche criterion matrix

you have $n=64\times 32$ random variables so your degrees of freedom should be $n-1=2047.$


How good is using AES CTR mode with initial counter as 0?

As long as you never re-use a specific counter value with the same key, counter mode protects the privacy of the message.

All counter values are equally secure. You just have to be sure never to re-use any counter value in two different messages. Zero is no different to any other counter value in this respect.

However, if you ever re-use any counter values then the secrecy of both messages is completely lost.

If you plan to encrypt many messages under the same key, then it would be wise to choose a different counter strategy to avoid the possibility of re-using counter values.

One such strategy is to allocate the first 64-bits of the block to the milliseconds since 1970. This is safe if the key is only used in a single thread and you don't encrypt more than one message per millisecond. This won't take the full 64-bits, so you can just fill the remaining bits at random. You then reserve the remaining 64-bits for the counter. This will make it difficult for two messages to use the same counter values.


How much pre-hashing a password increase security against brute force attack?

Would this help preventing brute force attacks?

It would slow down an attacker and prevent them from trying as many password guesses. E.g. if you used 1000 rounds like in RFC 2898, you would reduce the number of guesses by a factor of 1000.

Assuming you count dictionary attacks under brute force attacks, such attacks would definitely not be completely prevented. Simplest passwords like your example of 'apple' could be cracked regardless of which (practical) number you choose for iterations. You can't make the work factor large enough that the attacker can't still make hundreds or thousands of guesses in a feasible time, or you can't yourself use it.

But yes, your use of PBKDF2 makes sense and is essentially the purpose of having it in a key generation context. It's just that there is no way to make as simple passwords as 'apple' secure under any circumstances. (At least unless there's another authentication factor.)


Can Grover's Algorithm be combined with a meet-in-the-middle attack?

You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption:

Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$.
For each partition generate the inner encryption table.
Run Grover's on the outer keyspace in $O(2^{n/2})$ time.
If you find the preimage in the table, you found both keys, otherwise return to 2.

You would get $O(2^{n})$ time and $O(2^{3n/4})$ storage, which is better than classical meet-in-the-middle and requires less quantum computations, $O(2^{3n/4})$, than just using Grover's on the whole combined keyspace in $O(2^{n})$ time.

The problem of the size of the quantum computer would probably apply (maybe $O(2^{3n/4})$ qubits here?).


I will give the 1 round answer which will help complete the question.

Let $X_{1,i},i=0,\ldots,3$ be the 32-bit outputs of the first round, before the swap, numbered left to right. Then,

$$P_2=X_{1,2}, \quad P_0=X_{1,0}$$
and
$$P_1=WK_0\oplus F_0(RK_0,X_{1,0})\quad
P_3=WK_0\oplus F_0(RK_1,X_{1,2}),
$$
The equations for the $P_{i}$ are as above.


Proof that pseudo-random generated key is semantically secure

In order to answer that, let's remember the definition of a secure PRG:

Let $G: k \to \{0, 1\}^n$ be a PRG. $G$ is said to be a secure PRG if and only if $G(k)$ is indistinguishable from $r$, where $r$ is a truly random string from $\{0, 1\}^n$

By indistinguishable we mean that no statistical test can differentiate $G(k)$, where $k$ is chosen at random from the set $K$, from a truly random string $r$, $r \in \{0, 1\}^n$.

That said is easy to see that, if $G$ is a secure PRG no adversary can distinguish, with non-negligible advantage, the ciphertexts generated from $E$ and $E'$. So your idea of proof is correct.

Most of the times this should be enough to prove it... But bellow I present a proof using an Attack Game and an Statistical Test

To help with the actual proof one can define the problem as:

  If G is a secure PRG, then $\xi'$ is semantically secure.

Then, we can use the contrapositive to prove it:

  If $\xi'$ is not semantically secure, then G is not a secure PRG.

To prove that, given an adversary $A$ that can break the semantic security from $\xi'$, we need to be able to build an adversary $B$ using $A$ that can distinguish $G(k)$ from $r$, again, where $r$ is a truly random string from $\{0, 1\}^n$.

So, the way we would do this is by using $B$ at the same time as the challenger of $A$ and as the statistical test to distinguish $G(k)$ from $r$.

$A$ would provide $B$ two messages $m_0$ and $m_1$;
Then $B$ would get from his challenger an string $s$ that can either be $G(k)$ or $r$;
Then $B$ encrypts $m_0$ using $E$ and the string $s$ as key (essentially, he is using $E'$ when $s = G(k)$ and $E$ when $s = r$).
Finally, $B$ sends the encryption $c$ to $A$ that answers $1$ if he thinks $c$ comes from the encryption of $m_1$, and $0$ otherwise.
$B$ outputs to his challenger whatever is the answer of $A$

Note that if $B$ answer his challenger with $0$, then $s = G(k)$; If he answers $1$, then $s = r$.

Given that $A$ can break the semantic security of $\xi'$ he would output $0$ (guess correctly) whenever $s = G(k)$, and as we can see, $B$ would also be right by answering that $s$ is in fact $G(k)$.

This would break the definition of a secure PRG, thus proving that $G$ is not secure. $\square$

Just for a matter of completude:

What you are asking for is also the idea of turning the OTP practical, where the idea is to use a pseudo-random key instead of a truly random key, so we can use small seeds to generate much larger keys.

I should also note that a cipher who uses a PRG to generate its key can't be called a perfectly secure cipher. That's why the definition of security is stretched so the security property depends on the specific generator. That's where the semantic security definition comes on.


Using different hashing function with ECDSA

I will first address the issues of the diagram;
Encryption part
Although the encryption is mentioned as optional

there is no mention of how the AES key is generated. The common method is the Diffie-Hellman Key Exchange and the Elliptic Curve version of it is preferred ECDH.

there is no mention of the mode of operation. CBC, CTR, GCM,... etc.

There is no mention of the nonce/IV generation. The nonce generation is crucial;

In the CBC it must be unpredictable
In the CTR and GCM the (IV,key) pair should be never use more than once.

ECDSA part;

The naming is completely wrong. We use signature and verification and those processes are completely different than encryption and decryption, even in the RSA. In short RSA decryption is not signature.

The verification part is wrong. Only the signature part is sent, the signature and message must both exist during the ECDSA verification.  They tend to make it symmetric but it is wrong.

Questions

I'm wondering must the ECDSA pair with the SHA Hashing function?

They didn't show which curve is used there. If a curve like P521 or Goldilocks is used the one may need XOFs like SHAKE128-512 series, or use SHA256 as CTR mode to generate more than one block to support all of the curve needs.

Alternatively, what if using the AES-GCM to generate both CIPHER & TAG? The GF generated TAG later go through the ECDSA to be encrypted with the private key.

The AES-GCM doesn't produce a digital signature, they can provide confidentiality, integrity, and authentication only if correctly used. AES-GCM can not provide non-repudiation. For digital signatures, you need a digital signature algorithm.

Or will anything go wrong with the scheme I describe above?

If there is no need for a digital signature, then it can be fine. The AES-GCM has a better alternative; AES-GCM-SIV is a nonce misuse resistant scheme. This can only leak the same message is sent again if the same message is sent again with the same (key,IV) pair is.


why must the encryption exponent e be relatively prime to $\phi(N)$

If it's not, then the decryption will not be unique.  That is, there will be multiple messages $M_1 \ne M_2$ such that $M_1^e \bmod N = M_2^e \bmod N$; hence if the decryptor receives that common value, he will not be able to determine if the original message was $M_1$ or $M_2$

  Why must any public key encryption algorithm resist CPA

When we're analyzing the security of a public key algorithm, we assume that an attacker has the public key (after all, we assume that we can give it out freely, so it is not unreasonable that the attacker can get a copy).  With that public key, the attacker can pick list of message he wants, and encrypt those messages.  Hence, a public key encryption algorithm must resist CPA because, practically speaking, an attacker can actually perform that attack.


What is so difficult about this if $z=y^n\ mod\ n^2$

We don't know of an efficient way of solving it.  That's essentially what we can say about just about any hard problem in cryptography.

We also don't know a reduction to a better studied problem (for example, the factorization problem); hence it gets called out as a separate hard problem.

  The more important thing what is so dangerous in knowing that a number in the residues set. How It can help me break the encryption?

That's easy; an Oracle that can solve the n-th residuosity problem (without knowing the factorization) allow us to determine whether a Pallier encrypted message is an encoding of 0 (because a ciphertext is an encoding of 0 if and only if it is an n-th residue).

Not only would that, in itself, be considered a break in security, we could (for example) test an encrypted message for equality with any other value (by encrypting that value, homomorphically subtracting the test ciphertext from the ciphertext of the encrypted value, and checking if that is an encoding of 0).


Determining nonce between unsynced systems

The standard approach is to have the sender pick his nonce (either randomly, or as a counter), and send it with the packet.  The decryptor then knows what nonce to use to decrypt, because it's right there.  Because nonces aren't assumed to be secret, this works.


Why do the signature and ciphertext size increase in post-quantum schemes?

What you say isn't entirely correct. In some post-quantum schemes, the signature or ciphertext is actually smaller than the equivalent-but-classical security level analogue in ECC. See for example the MQ encryption scheme ZHFE (link) or the code-based signature scheme CFS (link). However, in these cases the public key is invariably huge. In other cases we have the opposite: e.g. in the hash-based signature scheme SPHINCS (link), the public key is nice and small, but the signatures are huge. Lattice-based schemes tend to produce public keys of roughly the same size as the ciphertext or signature, but both are noticeably larger than their ECC counterparts. So there is a question there, but it should be rephrased to something like "why is $|\mathsf{pk}| + |\mathsf{s}|$ or $|\mathsf{pk}| + |\mathsf{c}|$ always so large in post-quantum crypto, but not in classical crypto?"

The way all public key schemes work is by relying on hard computational problems with a very definite algebraic structure.* This structure is necessary to guarantee a link between the public and private keys, i.e., only the holder of the private key that matches the public key should be able to decrypt or sign messages. This stands in stark contrast to symmetric crypto, where security relies on breaking -not retaining- algebraic structure and no such link is necessary because there is no distinction between public and private keys. Public key schemes are the subject to more functional constraints than symmetric schemes and as a result there are fewer strategies for their construction. Of those strategies we know to work, only schemes based on number theory and elliptic curves are known to be broken by Shor's quantum algorithm. The others are consequently considered part of post-quantum cryptography. So maybe the best phrasing of your question is something like "why are schemes that are broken by Shor's algorithm, also the schemes with the smallest $|\mathsf{pk}| + |\mathsf{c}|$ and $|\mathsf{pk}| + |\mathsf{s}|$?"

This question has a straightforward answer: both number theory and elliptic curves, or commutative group theory in general, enable a very succinct encoding of computational hardness while retaining a lot of algebraic structure. Unfortunately, this copious algebraic structure comes back to bite you in the ass because it is precisely what allows Shor's algorithm to work.

The good news is that, like Yehuda says, there is no proof that hard algebraic problems that resist attacks on quantum computers cannot have a succinct encoding. So conceivably, it may be possible to design short public key and short signature/ciphertext post-quantum schemes. We just don't know of any that accomplish this.

In terms of a comparison of existing schemes, take a look at eBATS (link), a website that compares operational cost as well as key and message size of various pre- and post-quantum schemes.

*: The exception to this rule is the branch of hash-based signatures. But their notable lack of algebraic structure is also what causes the inherent statefulness (i.e. you have to keep track of all previous signatures to be secure) and what kills the possibility for public key encryption based on hash functions.


Is the Representation Problem hard on elliptic curves?

If RP is easy, then so is discrete logarithm.

Assume that you have a way to easily solve the RP for a given $n$. Now I give you $G$ and $P$ on the curve (of size $q$), and I want you to find $x$ such that $P = xG$. What you do is the following: you generate random integers $r_1, r_2, \cdots, r_n \mod q$, and compute $Q_i = r_iG$ for all $i$ from $1$ to $n$. Then you solve RP for P relatively to those $Q_i$, yielding the $a_i$. You then get $x = a_1r_1 + a_2r_2 + \cdots + a_nr_n \mod q$.

Since discrete logarithm is hard in elliptic curves, so must be RP.


Since the generator should be a primitive root of p

Well, here's your misunderstanding; the generator $g$ needn't generate the entire group $\mathbb{Z}^*_p$; instead, it can generate a proper subgroup (and in most cases, we select such a subgroup).

Here's the issue, if $h$ is a factor of the size of the group generated by $g$, then given $g^x \bmod p$, we can compute $h \bmod n$ in $O(\sqrt h)$ time.  If $g$ generates the entire group, well, its size will be $p-1$, which always has a factor of 2 (assuming $p>2$), and so we'd be giving away $x \bmod 2$ for free.

In contrast, if the size of the subgroup is a large prime (which implies that it is not the entire group), then the above observation doesn't give the attacker any advantage; the only factors of the subgroup size are 1 (which doesn't tell the attacker anything) and the large subgroup size itself (which is too large to make $O(\sqrt{h})$ time feasible.


There is no need for those image encryption algorithms.

You can encrypt an image file, like any other sequence of bytes using standard encryption.
If you really want to encrypt the pixels themselves (not recommended), you can use standard length preserving encryption, such as a four round feistel network.

I've seen some image encryption papers, but they were badly written by people with little understanding of cryptography and not published in cryptography journals/conferences.


One-time pad encryption of ASCII characters

So you were really close. You are right that the 3rd ciphertext's 10th byte(0xED) in the 3rd message is a space. So we know 0x20 in hex is a space in ASCII. So now to find the 10th byte of the key you need to xor 0xED and 0x20 to get 0xCD(which is the 10th byte of the key). Well now that you know the key, you can xor the 10th byte of the 3rd ciphertext 0xBD with 0xCD. So you get 0x70 in hex and 'p' in ASCII.


Generating 64 bit random values using AES-CTR

AES-CTR can be used as a random number generator if you don't mind that it never repeats the same 128 bit value - but the chances of that happening are minimal with a true RNG anyway.

In that case there is no need to have any plaintext though: you'd simply create the key stream (the encrypted counter values). If you only have a higher level cipher at your disposal you can simply do this by encrypting zero bytes.

If your key (the seed) is random then you can leave the IV/nonce set to zero as well and just start the counter (encoded as 16 bytes) at all-zeros.

If you'd use only 64 bitsof the 128 bit key stream generated by encrypting the counter then you would not have a repeated block within $2^{64}$ blocks. Although AES-CTR does have a period of $2^{128}$ blocks there is no guarantee that a value of 64 bit isn't repeated earlier.

Of course the cipher still has a period (as in, a long repeated sequence) of $2^{128}$ blocks as the counter will restart at zero when that happens, inconsequential of how many bits are actually used of each block.


Memory hard password based key derivation functions?

Memory hard functions are designed so that the internal calculations rely on a relatively large state. The functions should not have shortcuts that allow an adversary to calculate the result without using of the state at once (at least not without incurring a very high overhead). That way it is impossible for fast hardware to be developed that does not require large amounts of memory.

There isn't one specific design for memory hard functions within PBKDF's. You can have a look at various existing designs (scrypt, Argon2) of memory hard PBKDF's for examples of memory hard functions.

Lets define 3 different methods, going from low level to high level:

Catena was mentioned specifically in the comments as it simply requires a generic hash method to function. If any secure hash function can be used then Skein should be a secure option.
KMAC by now has been defined as a secure HMAC replacement by NIST. So you could use scrypt with PBKDF2 where the HMAC is replaced by KMAC.
scrypt uses PBKDF2 as underlying CPU hard function. Simply replace the PBKDF2 function within scrypt with another CPU hard function such as Skein's PBKDF.

These are hints, providing the security proof is left to the reader.


Is there any valuable Cryptography certification for working in the field?

Cryptography is a quite academic field. Outside of universities, practice of cryptography tends to be "applied crypto", which feeds on academic papers while contributing its own perspective on things, in particular with regards to implementation issues. In any case, this means that whatever you do in cryptography will involve reading a lot of research papers, and, correspondingly, the formal degrees about it are academic. If you want to go that road and be recognized as a "cryptographer" through certifications and degrees, then go get a PhD or at the very least a Master's degree in cryptography.

There are alternate roads to building your crypto street cred:

You might demonstrate your deep knowledge of the field by flooding some well-known public forums or Q&A sites (e.g. this very site, crypto.stackexchange.com) with hundreds of well-researched and explained answers that make people instinctively think of you as "that guy knows his stuff".
While paper publication in peer-reviewed conferences or journals is a difficult art, "publishing" software implementations is simple; you just have to create a free GitHub account, and roll with it. If you manage to write some kick-ass piece of crypto software, that people find useful and appears to be of high coding quality, then you could also gain some reasonable level of recognition.
There occasionally are some "cryptographic competitions" (some are referenced here; an ongoing one is the NIST call for Post-Quantum algorithms) in which anybody can submit a "candidate". This is substantial work, and little glory is achieved if it gets broken right away. But if a candidate survives one or two rounds, then it can lend some credibility to the authors.

The common theme in all of these is that you should show, at all times, that you understand the academic side of things, and you know not to make unsubstantiated outrageous claims of security.


Standard DHKE
Standard DHKE is defined on the multiplicative groups.  Alice and Bob agree on the cyclic group $G$ of order $n$ and a generator $g$ then the key agreement is performed as follows;
\begin{array}{lcl}
\text{Alice} & \text{Transmit} & \text{Bob}\\ \hline
a \stackrel{R}{\leftarrow} [1,n-1]& & b \stackrel{R}{\leftarrow} [1,n-1]\\
\text{calculates } A = g^a & \xrightarrow{A} & \text{calculates } B = g^b\\
 & \xleftarrow{B} & \text{calculates } s = B^a = (g^a)^b = g^{ab} \\
\text{calculates } s = A^b = (g^b)^a = g^{ab} & &
\end{array}
Therefore both sides have agreed on the $s = g^{ab}$ and
Group Selection
We can use the below 3 prime classes to choose the $p$;

Choose a prime in the form $p = kq+1$ and those are called DSA prime by poncho. They are cheap to generate.

Choose a prime of the form $p = 2qr+1$ and those are called Lim-Lee primes where both $q$ and  $r$  primes around the half size of $p$.

Choose a prime of the form $2q+1$ and those are called sage primes and $q$ is called Sophie Germain prime.

Generation easiness and order of security of these groups are $1<2<3$
If you choose $\mathbb{Z}_p$ then the multiplicative order is $p-1$ which is not a prime and the group may vulnerable to Pohlig-Hellman. With the above methods, we guarantee that we have an element with large order $q$.
Modular Exponentiation
def modular_pow(base, exponent, modulus):
    if modulus == 1:
        return 0
    result = 1
    base = base % modulus

    while exponent > 0:
        if (exponent % 2 == 1):
            result = (result * base) % modulus
        exponent = exponent //2
        base = (base * base) % modulus
    return result

Calculation
Let's take ffdhe2048 from RFC 7919

$p = p = 2^{2048} - 2^{1984} + (\lfloor(2^{1918} \cdot e \rfloor + 560316 ) \cdot 2^{64} - 1$
$g = 2$
$q = 2*p+1$, so we have a safe prime.
$n = q = (p-1)/2$, and
a = 160

Exponent =  0
   Squaring   , base   =  4
Exponent =  0
   Squaring   , base   =  16
Exponent =  0
   Squaring   , base   =  256
Exponent =  0
   Squaring   , base   =  65536
Exponent =  0
   Squaring   , base   =  4294967296
Exponent =  1
   Multiplying, result =  4294967296
   Squaring   , base   =  18446744073709551616
Exponent =  0
   Squaring   , base   =  340282366920938463463374607431768211456
Exponent =  1
   Multiplying, result =  1461501637330902918203684832716283019655932542976
   Squaring   , base   =  115792089237316195423570985008687907853269984665640564039457584007913129639936

Result =  1461501637330902918203684832716283019655932542976

Note on 160
The exponent is too small to be square. When the attackers see the result and compared to the
p=16158503035655503650076756738912581681244028566744537587294217069634903417068105001396028181320082342729278178967665408464414511540286736312636777371230622870513101263958286486431353150162631714106572883465707111827110470555674314995828739134017115276543174525317778856109593945166364784848064871928120870618118612598673201345927898883988411507312698966529007613429365380598766218233737927730357521948422470183065248848906427147979329798783525641926066392234261462752284136439556860049465936979571687087918913000139017486599276030303766617061301627342044060015552953742140501997483478059848478124314516169036419563519
They simply will consider that you used a small number and will search it by brute force. The $a$ must be chosen uniformly random as $a \stackrel{R}{\leftarrow} [1,n-1]$.
Actually, we don't need $a \stackrel{R}{\leftarrow} [1,n-1]$ for the security $a \stackrel{R}{\leftarrow} [1,2^{224}]$ is enough between 2019 and 2030 according to NIST ( see as keylenght.com). As stated poncho on the commends, this is more efficient.
Performance
Now the number of operations is quite countable. We have to square for every bit of the exponent ( $160_{10} = [10100000]_2$) and a multiplication whenever a bit is 1 ( 2 times for 160 sine $160= 128+32$).
The above function is not optimal to calculate modular exponentiation and vulnerable to side-channel since there is a conditional that depends on the exponent bits.
MITM
Standard DHKE is vulnerable to MITM attack and Telegram had a different one too. To mitigate the MITM attack digital signatures are required.


What is the purpose of decomposing ciphertext into digits during relinearization in Brakerski Vaikuntanathan homomorphic encryption?

The decomposition helps with the noise growth of your scheme.

You see, the decryption only works if you "error" (here the terms you denote by $e$) is small enough. If $t*e$ grows beyong the modulus (all the computations are done modulo some number, let's say $q$), the mod $t$ operation won't yield the message $m$, but $m$ + $t*e$ mod $q$.

Now when you're multiplying 2 ciphertexts, the errors get multiplied, and they also get multiplied by the plaintext.
Hence, you need your plaintext to be small enough, so $s^2$ cannot be used directly for this reason. When you decompose it in binary, you will have a sum of $log(q)$, but each of those will have a much smaller noise, because they only get multiplied by at most $t$.


How can semi-weak DES keys be leveraged to attack DES?

The answer is that they cannot. DES weak keys will be chosen with such a small probability that they don't matter at all. The only reason that weak keys are of interest is when you want to use a block cipher as an "ideal cipher" like in order to construct a collision resistant hash function. These sort of constructions break completely when a cipher has weak keys. But, this is not a criticism of DES or other block ciphers; they are made to be pseudorandom permutations and are not made to be hash functions. Rather, in my personal opinion, this is a criticism of people who try to use primitives designed for one purpose for something completely different.


Trying to follow as reference Burt Kaliski's The Mathematics of the RSA Public-Key Cryptosystem, the question has the following issues:

The question selects $n=19$ as a prime, rather than as the factor of two distinct primes $p$ and $q$ ($p=5$, $q=11$, $n=55$ in the reference); this is however not disastrous, and we'll adapt the reference by taking $n=p$ and ignoring $q$.
The question uses $d$ such that $e\,d\equiv1\pmod n$, when nothing suggests that in the reference; the reference uses $e\,d\equiv1\pmod L$ with $L=\operatorname{lcm(p-1,q-1)}$, and with our adaptation that becomes $L=n-1$, thus the relation between $e$ and $d$ should be
$$e\,d\equiv1\pmod{(n-1)}$$
The question ignores the stated requirement that $e$ is relatively prime to $p-1$ and $q-1$ (meaning: $e$ shares no prime factor with either $p-1$ or $q-1$); with our adaptation this becomes that $e$ is relatively prime to $n-1$. It follows that $e=3$ is an invalid choice for $n=19$, since $3$ divides both $e=3$ and $n-1=18$.

If we keep $n=19$, we can use $e=5$, find $d$ such that $e\,d\equiv1\pmod{18}$, e.g. $d=11$. Then $c=m^e\bmod p=14^5\bmod19=10$, and $m'=c^d\bmod n=10^{11}\bmod19=14=m$, as expected.
Note: I use $c$ for the ciphertext as in the reference, and $m'$ for the the result of the decryption.

This is an application of Fermat's little theorem, which states that if $p$ is prime, then for all $m$ not divisible by $p$, it holds that $m^{p-1}\equiv1\bmod p$.

Notice that since we chosed $d$ with $e\,d\equiv1\pmod{(n-1)}$, it holds that $e\,d=k(n-1)+1$ for some integer $k$.

Now, the way we computed $m'$, it holds that
$$\begin{align}m'&\equiv c^d&\pmod n&&\text{ using }m'=c^d\bmod n\\
&\equiv{(m^e)}^d&\pmod n&&\text{ using }c=m^e\bmod n\\
&\equiv m^{e\,d}&\pmod n\\
&\equiv m^{k(n-1)+1}&\pmod n&&\text{ using }e\,d=k(n-1)+1\\
&\equiv {(m^{n-1})}^k\,m&\pmod n\\
&\equiv 1^k\,m&\pmod n&&\text{ using FLT}\\
&\equiv m&\pmod n\\
\end{align}$$
Note: when using the FLT, we rely on $n$ prime, and $m$ not divisible by $n$, which holds.

Since $m'=c^d\bmod n$ it holds that $0\le m'<n$. We have $0<m<n$ and $m'\equiv m\pmod n$, hence $m'=m$ Q.E.D.

An incorrect assumption made in the question's reasoning is that it would hold that $m^i\bmod n=m^{(i\bmod n)}\bmod n$; that's false in general, and a proof is given by the computations in the question.

What really holds is that $m^i\bmod n=m^{(i\bmod\lambda(n))}\bmod n$ where $\lambda$ is the Carmichael function, and $m$ is coprime with $n$ or $n$ is square-free. The later holds in RSA. In the reference $n=p\,q$ with $p$ and $q$ distinct primes, and $\lambda(n)=L=\operatorname{lcm}(p-1,q-1)$.

Standard notation, used in this answer (but not the reference, which omits parenthesis in the first notation): for $w>0$

$u\equiv v\pmod w$ means that $w$ divides $u-v$
$u=v\bmod w$ means that $w$ divides $u-v$ and $0\le u<w$.


Let's say $b$ is our block size. We can easily see that if the message has the size $b$, the following holds $MAC(k, d) = E(k, d)$. So, let's first try to solve this for a single block message (let's call it $p$).

One block message

The goal is to compute $E(k, p)$, because that is $MAC(k, p)$.

The message must go through $E$ at some point. The only function that can take the message is $mac3$ (in contrast, $mac0$ takes a number). The problem is that $mac3$ takes exactly 3 blocks of input. So, our one block message $p$ has to be expanded to a three block message in some way. If we put our message block at the beginning of the 3 blocks, the first invocation of $E$ would produce $o_1$ which will be mangled in the second and third invocation of $E$. We can't do that.

What happens if we put our message block $p$ at the end of the 3 block input to $mac3$? The $o_3$ which contains the encryption of our message block $p$ will only be XORed, but not encrypted again. There we have a winner, because it is easy to reverse XOR, since we don't need a key.

Let's recap the way XOR works: if $x \oplus y = z$ then $x \oplus z = y$. Also, $x \oplus x = 0$ and $x \oplus x \oplus y = y$. We're going to need it.

Back to our problem. We can control $o_3 = E(k, o_2 \oplus d_3)$ to be our MAC of our one block message if we can control $o_2$. This is where $mac0$ comes in.

What happens if we set the 3 block message to $0^b | 0^b | p$ where $|$ means concatenation and $x^b$ means to repeat $x$ $b$-times?

$o_1 = E(k, 0^b)$
$o_2 = E(k, o_1 \oplus 0^b) = E(k, o_1)$
$o_3 = E(k, o_2 \oplus p)$
$m = o_1 \oplus o_2 \oplus o_3$

We know that $o_1 = mac0(1)$, but that isn't enough to control $o_2$, because we don't know key $k$. What exactly is $mac0(2)$ then? ...

$o_{1,m2} = E(k, 0^b) = o_1$
$o_{2,m2} = E(k, o_{1,m2} \oplus 0^b) = E(k, o_{1,m2}) = o_2$
$m_{m2} = o_{1,m2} \oplus o_{2,m2} = o_1 \oplus o_2$

From that, we can calculate $o_2$:

$$o_2 = o_1 \oplus m_{m2} = mac0(1) \oplus mac0(2)$$

OK, now we control $o_2$. We still want to calculate $E(k, p)$. So let's set $d_3 = o_2 \oplus p$. This leads to

$$o_3 = E(k, o_2 \oplus d_3) = E(k, o_2 \oplus o_2 \oplus p) = E(k, p)$$

OK, now we're nearly there. The final MAC is $m = o_1 \oplus o_2 \oplus o_3$. Since we already know $o_1$ and $o_2$ from before, we have

$$m = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus p\right) \oplus mac0(2) = E(k, p)$$

Multi-block message

The last formula contains the way how $E(k, p)$ can be calculated for any single-block message $p$. This can be used to calculate the intermediate values $o_x$ if the composite message.

Let's say, our message is

$$d = d_1 | d_2 | ... | d_N$$

Then the final MAC can be calculated as

$o_1 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus d_1\right) \oplus mac0(2)$
$o_2 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_1 \oplus d_2\right) \oplus mac0(2)$
$...$
$o_N = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_{N-1} \oplus d_N\right) \oplus mac0(2)$
$m = o_1 \oplus o_2 \oplus ... \oplus o_N$

Here is the (untested) Java code for this.


The state of a stateful algorithm is its “memory”. One round of the algorithm can be modeled as a function from $S \times I$ to $S \times O$ where $I$ is the input to one round and $O$ is the output from one round. For a PRNG, $I$ would either be a singleton (i.e. no input, just a request to generate more output), or a small amount of information such as the requested output size, or some additional entropy to inject. $O$ is the chunk of pseudorandom output.

The size of the state before and after the round is the same. So for a given input, the state update function is onto (surjective) if and only if it is one-to-one (injective).

If you have a state update function that is onto but not one-to-one, it means you're working in a different model where the size of the state decreases at each round. Your PRNG would have a limited lifetime since the size would eventually shrink to near-zero (near-zero being any size where the adversary can realistically enumerate the possible states). That would limit its usefulness.

In such a case, just because the knowledge of the current state alone doesn't allow the attacker to be certain what the previous state was doesn't particularly confer any security. Security is not plausible deniability. To make a system secure, it isn't enough to make it so that the adversary cannot prove beyond a doubt that they've broken it! You actually need to make it effectively impossible to break. It is very common that the adversary has some partial information and not just the one piece of knowledge that you're focusing on. For example, suppose that in the previous round, the PRNG was used to generate 32 bytes of data, out of which 16 bytes were used as a key and 16 bytes were used as an IV, and the adversary has been able to see the encrypted message and now wants to decrypt it. The adversary knows the IV, i.e. they know half of the output of the PRNG, and they're looking for the other half which is the key. In order for the PRNG to have backtracking resistance, you need to ensure that the knowledge of the current PRNG state plus the knowledge of the IV is not enough to reconstruct the previous PRNG state. Maybe the knowledge of the current PRNG state alone is not enough, but that is not at all helpful in the actual scenario where the adversary also knows half of the output.

There are real-world PRNG where it's trivial to inverse the state update function, i.e. to find the previous state if you know the current state (and possibly the corresponding output). But by definition, they are not backtracking resistant.


Compression function is not collision resistant but Merkle-Damgard is collision resistant

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its  compression function has a known collision.

Consider SHA-256. Note its round function $F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^{256},0^{512})$ is defined to be $F(0^{256},1^{512})$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.


If you happen to know also $e$ then you can use the formula

$$d = d_p + d_q - e\cdot d_p\cdot d_q \quad\bmod (p-1)\cdot(q-1).$$

Instead of modulo $\varphi(p\cdot q) = (p-1)\cdot(q-1)$ you can also calculate the result modulo the least common multiple of $p-1$ and $q-1$.

PS: I do not understand the downvote(s) for the question. When generating an RSA key one usually first finds $p, q, d_p, d_q$ (and maybe $p^{-1}\bmod q)$ given $e$. If one uses the private key on an embedded device that is susceptible to fault attacks like the Bellcore attack, one might prefer to refrain from using the CRT despite the performance advantages.


"The DH key space for 128 bit is limited by how many primes existed in the finite field of Zp, where p is the largest prime that can be represented by a 128-bit value", so I got a bit confused about what it really means.

I believe that the appropriate meaning to the quote is "I have no clue about cryptography, here are some plausible sounding buzzwords that I've heard".

No one uses (or, should use) a 128 bit prime for Diffie Hellman; the current conventional wisdom to use (at least) a 2048 bit prime with a large prime subgroup; this is often done by using a "safe prime".

Now, sometimes we perform Diffie-Hellman based on an elliptic curve, which might also be based on a prime curve.  However, even in this case, a 128 bit prime is still too small; the conventional wisdom is to use at least a circa 256 bit prime (Curve25519 comes close enough).

If the author of the fractal method isn't aware of this, well, that doesn't indicate that he knows all that much about cryptography.  That would certainly call into question anything he has to say about his fractal key exchange.

BTW: "key space" isn't a very useful way to think about DH security.  If the size of the large prime subgroup is $q$, then the "key space" size is $q$; however there are generic attacks that recover the shared secret in time $O(\sqrt{q})$, hence you aren't as secure as the size of the key space would indicate (and, for some groups, there may be even faster attacks).


Best password hashing strategy with Argon2 in a web app

Only peripherally related, but consider doing somewhat expensive hashing on the client side as well as on the server, and arguably instead of on the server. This increases the costs of an attacker brute-forcing passwords, but scales better, and depending on your clients this could be viable - for example, browsers expose built-in PBKDF2 via webcrypto APIs.


There are two forms of entropy here at work. First there is "uncertainty" entropy from the user password which is typically very low (on the order of 20 to 40 bits for most passwords out there). And then, there's "computational" entropy, which is artificially obtained by forcing an attacker to do work to calculate keys.

Essentially, if you run your KDF for $k$ iterations, you'll add about $\log_2(k)$ bits of computational entropy.

This doesn't take into account the fact that not all KDF's are equal, it is just an asymptotic observation.

So, yes, theoretically, you can transform a weak password of, say, 20 bits of entropy, into a very strong 256-bit key with roughly 256 bits of entropy, but you'd need $2^{256 - 20} = 2^{236}$ KDF iterations... at this point it may be more beneficial for the attacker to try a different approach. I mean, putting aside the fact that nobody is going to wait around to compute your KDF - the iteration count has to be low enough so that normal users can't feel it but attackers can (say, half a second per KDF invocation).

Also, what do you mean by a "KDFed ASCII password"? In general, the output of a KDF is used directly into a cipher or message authentication code, not as a new password. But, given that there's 96 ASCII printable characters (I think) then each character has a maximum entropy of $\log_2(96) \approx 6.58$ bits.

So to obtain 256 bits of entropy you'll need at least $256 / 6.58 \approx 39$ characters in your password.


Could public-key crypto be performed long ago if the idea had been discovered?

What an interesting question! Yes, it certainly could. The math required to carry out RSA encryption, for example, have been known for millennia. The most complex algorithms are:

Primality testing for key generation. I think that the first efficient algorithm was Fermat's, from ~1600
Euclid's, which is from 300 BC
Binary exponentiation, which I couldn't find when it was
discovered, but I'd guess it's pretty old too
Even the Chinese Remainder Theorem, which can speed up the RSA computation, is from 300 AD.

So, if someone discovered RSA and also Fermat's primality testing, then it would be possible to use RSA millenia ago.

People wouldn't need to use keys as large as in use today since any attacker would also need to do calculations by hand. The first efficient (sub-exponential) factorization algorithm, the continued fraction algorithm appeared in 1931. So an attacker would need to brute force the key with trial division, in $O(\sqrt{n})$ steps. In 1903, a 67-bit Mersenne number was factored. Leaving 2 bits of breathing room (the calculation took half a year, 3 additional bits would make it take four years), then $(67+3) = 70$-bit (21-digit) keys would be more or less safe against brute-forcing by hand. This seems to be an overestimation, though, since calculators existed at that time, see this discussion.

20-digit calculations seem a lot, but considering it may be overestimated, it seems using RSA millenia ago would be possible.

These are all approximations though, someone with deeper knowledge of math history should be able to shed more light in this question. (Maybe this question would even fit the Math.SE better)


Why is a 2048-bit public RSA key represented by 540 hexadecimal characters in X.509 Certificates?

That's because the public key in DER format (which is a way of expressing X.509 objects as a sequence of bytes) includes more than just the modulus.  Specifically, it consists of:

This is a collection of the following objects; that takes up 4 bytes
The first object is an integer (which happens to be the public modulus); the integer itself is 257 bytes (not 256; that's because ASN.1 integers are signed, and so there has to be a leading 00 to make the top bit zero to signify positive), as well as 4 overhead bytes, for a total of 261 bytes
The second object is an integer (which happens to be the public exponent); if you use 65537 as the exponent, this takes up a total of 5 bytes long (including overhead)

4+261+5 gives you a total of 270 bytes, or 540 hexadecimal characters.

This assumes that the encoder uses an RSA public exponent of 65537 (or some other value between 32769 and 8388607, all of which would encode in the same length); 65537 is by far the most common value nowadays, but is not mandated.

Note that this does not count the encoding that says "this is an RSA public key"; that takes up an additional 24 bytes (including overhead).  That's generally included in public keys, but apparently you're not counting that part; that would bring the length past the 540 hex characters you see.


Which test suit is better to say if PRNG is CSPRNG:TestU01 or NIST?

Please don't.

TestU01 or NIST?

Neither.  Trust what they say on the xoshiro256+ website. A CSPRNG is not defined by it's speed. It's defined by security against predictability, i.e. the next bit test. And that's determined by it's construction.
All that TestU01, NIST's STS and all the others do is check for uniform randomness of output (within a certain degree of confidence). A good PRNG will pass, as will a good CSPRNG. I don't think that a mathematical expression can be formed to enumerate the difference between an invertable PRNG and a non-invertable CSPRNG, other than something derived from $\text{xoshiro256+} \ne \text{CSPRNG}$. See note.
It's as mathematically defining the difference between apples and bananas.

My other question is that NIST statistical tes...

They say that because they are talking specifically from a computer security perspective. That's their raison d'etre. As in the last word of your linked title :-) NIST is not interested in PRNGs.

Note. With hindsight, something may be possible along those lines. Formulae can be written to invert PRNGs. How Brittle Are LCG-Cracking Techniques? discusses this with extensive formulae/code for a simple PRNG.  No complete formulae are (yet) possible for inversion of a CSPRNG. This is a form of mathematical distinction if you will.


using different IV and SALT with AES-CBC but same KEY

Question: is it safe to use the DERIVED key, where the ORIGINAL key is the same, but the salt is different every time?

No, but the reason is a little tricky.

First, forget AES-CBC—you should use an authenticated cipher like AES-GCM (if you must use AES) or NaCl crypto_secretbox_xsalsa20poly1305, and focus on the security contract.  AES-CBC is hard to use correctly and doesn't provide good security even if you do.  If you really just need to send multiple messages in sequence with a single key you've negotiated, you can just use the number of messages you've sent so far as a nonce for an authenticated cipher—no need to derive keys.

Second, if users are choosing their own passwords, you should use a modern password hash like Argon2 (specifically, Argon2id), not PBKDF2, so that you can take advantage of more of the user's resources to drive up the adversary's costs—specifically, so you can take advantage of the user's memory and parallelism too.  (If users aren't choosing their own passwords—if the computer is choosing passwords with (say) 256 bits of entropy—then there's no need for password hashing and you can skip that step.)

But let's say you have to use PBKDF2 for some reason, so that's the only way you can drive up the adversary's costs.  Should you repeatedly use PBKDF2 with multiple salts to derive multiple keys?

The purpose of the iteration count is to drive up the adversary's costs, at the expense of also driving up the legitimate users costs.  But the costs mean something slightly different to the legitimate user and the adversary:

The legitimate user cares about latency of key derivation: How long do I have to wait after I type in my password and hint ENTER before I get logged in?

If I'm willing to wait (say) one second, that's one second of resources that the application can spend on PBKDF2 to drive up the adversary's costs.  From the user's perspective, there's no difference between computing one key in one second vs. two keys consecutively in half a second each.  But from the adversary's perspective the story is a little different.
The adversary cares about throughput of password guesses: How many passwords can they guess every hour on my 100-CPU cluster?

The adversary doesn't care about deriving every key needed by the application during the password search process.  The adversary is happy if they use one key in the application to confirm a password guess.  If the application has to compute PBKDF2 twice for two different keys in one second, the adversary only has to spend half a second to test a password guess.

Even worse, if you ask PBKDF2 for a key that is longer than the hash output size, it is as if you invoked PBKDF2 multiple times in a row with the same iteration count.  There are some applications in which this may not hurt, but it was largely a stupid design.

So how should you derive multiple keys from a single passphrase?

Let's suppose you can't just reuse the key with different nonces.

Answer: Use a key derivation function, such as HKDF with SHA-256.  (Not a password-based key derivation function, also called a password hash—just a vanilla key derivation function; more on the distinction.)  A key derivation function takes a master key, such as what you got from PBKDF2, and a string uniquely identifying a purpose sometimes called the ‘info’, and returns a derived subkey.  Every time you feed in the same master key and info, you get back the same subkey, but without knowledge of the master key, the subkeys appear to be independent uniform random bit strings.

For example, you might do this:

Master key: $k = \operatorname{PBKDF2-HMAC-SHA256}(\mathit{salt}, 16384, \mathit{pw})$
File encryption key: $k_f = \operatorname{HKDF-Expand}_k(\text{‘file encryption’})$.
Backup encryption key: $k_b = \operatorname{HKDF-Expand}_k(\text{‘backup encryption key’})$.
etc.

(Note: HKDF has two steps—HKDF-Extract and HKDF-Expand.  HKDF-Extract is not necessary here: its purpose is to map a high-entropy but nonuniform bit string, like a diceware passphrase, into a short uniform bit string, but PBKDF2 already does that for us.  HKDF-Expand takes a short uniform bit string and an info parameter, and derives a subkey.  If you only have a combined HKDF-Extract/Expand module available to you, it doesn't hurt to do HKDF-Extract on the output of PBKDF2, but it doesn't do anything useful either.)

Addendum: What about the salt?

The purpose of the salt is to mitigate multi-target attacks: if everyone used the same salt, then breaking the first of $t$ targets would be cheaper than breaking one target by a factor of $t$, because there are ways an adversary can save effort by attacking many targets at once in a batch.  Adversaries like batch advantages like this because once you have a foot in the door of a network you can often exploit it to compromise more of the network.  But if everyone uses a distinct salt, that factor of $t$ batch advantage evaporates.


An elliptic curve as used in cryptography is a finite group, constructed on top a finite field. A pair of elements of the field that obey the curve equation form the Cartesian coordinates of a point of the elliptic curve group (and vice versa for all points of the elliptic curve group, except the neutral / point at infinity, often noted $\infty$).
In the field we can add; subtract; multiply; and divide, except by 0. The result is an element of the field.
In the elliptic curve group we can add and subtract. The result is an element of the elliptic curve group. One such addition involves several operations in the field (with the exception of addition of the neutral).
There is no multiplication in the elliptic curve group: we can't meaningfully multiply two points of an elliptic curve group. We can however define multiplication of an integer $k$ and a point $U$ of an elliptic curve group, by using repeated addition:
$$k\times U\,\underset{\text{def}}=\;\begin{cases}\infty&\text{if }k=0\\((k-1)\times U)+U&\text{if }k>0\\(-k)\times(-U)&\text{if }k<0\end{cases}$$
It follows $1\times U=U$, and $2\times U=U+U$.

On the elliptic curves, there is no divide function.

That's an oversimplification. We can meaningfully define division of two points of an elliptic curve. $U/V$ can be the lowest non-negative integer $k$ such that $U=k\times V$, when there exists such an integer. For many elliptic curves of cryptographic interest, that operation is defined except when $V=\infty$; but is not efficiently computable for random $U$ or $V$ (that's the very basis of the security of cryptography on that elliptic curve).

How to divide 2 coordinates on elliptic curve?

That's just a division in the field, independent of an elliptic curve. How to perform the operation depends on the field.
A common field is $\Bbb F_p$, that is arithmetic modulo a prime $p$. In this field, we can compute $x/y$ (for $y\ne0$):

as $x\cdot\left(y^{p-2}\right)$, computed modulo $p$. In Python, that's x*pow(y,p-2,p)%p.
or, more efficiently, as $x\cdot a$, computed modulo $p$, where $a$ is the modular inverse of $y$ computed using the extended Euclidean algorithm. The integer $a$ (and the integer $b$, that we do not need) is found by solving for unknowns $a$, $b$ and givens $y$, $p$ the Bézout identity $a\cdot y+b\cdot p=1$. In Python starting with version 3.8, that's x*pow(y,-1,p)%p.


OpenSSL - creating random elliptic curve and measuring performance

Yes. The hard part is of course to find the order of the elliptic group and its factorisation. Ideally, if the order of the group is a prime number (use a primality test), you know that $k = 1$, and any point on the curve is a good generator.

That said, it is not because you have found an elliptic group with prime order, that it is a cryptographically safe group. For instance, if the order of the group equals p when you are working over $F_p$, you have a cryptographically weak curve.

There are other conditions that give rise to cryptographically weak curves.  Generating a cryptographically good curve is somewhat tricky.

If this is for a toy example, with relatively small curves for illustrative purposes only, then as others said, use Sage.


Why a "Next Header" field is part of ESP trailer?

Well, in IPsec transport mode, the 'Next Header' gives the protocol type of the encrypted packet (e.g. TCP, UDP, etc), and hence is considered confidential, as we don't want the adversary to know the type of traffic.  The ESP Header is not encrypted, and hence we cannot put the 'Next Header' field there.

In AH, privacy is not a concern (everything is visible), and hence they do put the 'Next Header' field in the AH header.


Authentication and encryption of messages

First and foremost, you don't mention why you feel the need to invent your own crypto protocol. "Don't roll your own crypto" is a common saying around here for a reason: there are so many small things to be aware of when implementing a crypto protocol, and if you do any one of them wrong, your entire protocol will be insecure. Designing crypto protocols really needs to be done by committees of experts - preferably in an RFC to give the public a chance to point out things that you missed.

For the use-cases you describe, why are you not using an off-the-shelf SSL/TLS or PGP library?

If this is just for your own learning, then cool, but if you plan to use this for real then please tell me the name of the project or product it will be in so I can, umm, take a closer look -_-

The following assumes that this is just a learning project.

You keep saying

  encipher with the private key

What does that mean? That doesn't really make sense as a concept. I know that with RSA the public key and private key have the same format and can both be used for either encipherment or decryption, but in general with other algorithms (DSA, ECC, many of the post-quantum proposals) the two keys look very different and only the public key can be used for encipherment.

Are you trying to do a digital signature? If so, you need to calculate the signature for the massage, and attach the signature string to the packet in some way.

At it's core, your question seems to boil down to Should we sign-then-encrypt, or encrypt-then-sign? I'm not really clear what additional information you're asking for, but let's look at how some standard protocols solve this problem:

TLS / SSL

TLS takes a different approach by using authenticaled key exchange prior to sending any messaged: during the initial handshake when the connection is opened, both parties use public-key crypto to authenticate themselves, and to establish a shared AES key that only those two people know. Once that has been done, you don't need to use public-key to authenticate each message because if the message decrypts properly with the shared AES key, then it must have been sent by the other person.

PGP

This is a little closer to your use-case. You can read about all the packet types that PGP supports in section 5 of the PGP RFC-4880. My understanding is that the programmer or end-user has the choice of whether they do

sign-then-encrypt (like your option 1)

Symmetric-Key Encrypted Session Key Packet (Tag 3)
    Signature Packet (Tag 2)
        data

or encrypt-then-sign (like your option 2)

Signature Packet (Tag 2)
    Symmetric-Key Encrypted Session Key Packet (Tag 3)
        data

So this doesn't really help with your core question of sign-then-encrypt vs encrypt-then-sign.

Bottom line:

You've asked a lot of questions here, and I have only answered some of them. I suggest you go back and study the fundamentals of cryptography. I think some of your questions would answer themselves.
For any practical use, please for the love of God, use a standard library of either TLS or PGP.


Stream Ciphers -- Need clarification on their benefits in practice

Stream ciphers not necessarily encrypt one byte at a time; they encrypt/decrypt by generating keystream and xorring it with plaintext/ciphertext. Old stream ciphers like RC4 generate keystream byte by byte, modern stream ciphers like Salsa20 generate keystream by blocks (Salsa20 by 64-byte blocks). Block ciphers can be converted into stream ciphers using CTR mode of operation, and then they generate keystream by blocks too.

The ability to generate keystream one byte at a time is sure useful for some applications, but generally one need to implement it yourself. Modern ciphers (at least most of them) do not provide it "out of the box".


Deterministically combine more than one source of entropy

Set $r = r_1 + r_2 - \mathsf{floor}(r_1 + r_2)$. One (possible) advantage of this approach is that the result will be uniformly random in [0, 1] even if only one of $r_1$, $r_2$ is uniformly random. (Assuming the two values are independent.)

In Python you can also express this as

r = (r1 + r2) % 1.0


From the key creators point of view, notice that:$g_1\bmod p=1$ and $g_2\bmod q=1$.

Which means that $(g_1-1)\cdot(g_2-1)\bmod N=0$.

Which implies that $g_1-1$ and $g_2-1$ share a common divisor with $p$ and $q$.

To obtain $p$ we simply take $\gcd(g_1-1,N)$.

To obtain $q$ we simply take $\gcd(g_2-1,N)$, or $N/p$.

Because we have been able to factor the modulus using only the public keys and with no protocol error on the part of the implementer, this cryptosystem is insecure.


Can i modify data "protected" by a CRC16?

Yes, it is possible. And quite efficient, too.

$\DeclareMathOperator{\crc}{crc}$CRC is linear, meaning $\crc(x \oplus y) = \crc(x) \oplus \crc(y)$, where $\oplus$ is bitwise exclusive-or.

Suppose there's a message $m$ and we're given $\crc(m)$.

Linearity means we can effectively compute the difference in the CRC digest by computing the CRC of the difference. For example, $m \oplus 1$ is the message with the right-most bit flipped — that's how XOR works. Because of linearity

$$\crc(m \oplus 1) = \crc(m) \oplus \crc(1)$$

So by computing $\crc(1)$ and doing a little bitwise arithmetic, we can find the CRC digest for the message if we were to flip the rightmost bit... without knowing the original message at all.

The same principle applies to your question. If you know the first byte of the message is (for example) 15 and you want to change it to 8, then compute $15 \oplus 8 = 7$ and pad that value with zero bytes on the right so it lines up with the first byte of the message. Let the padded value be called $d$. Then compute $$\crc(m) \oplus \crc(d) = \crc(m \oplus d)$$ which will be the forged CRC value. The reason you right-pad with zero bytes is $x \oplus 0 = x$ for any $x$: XORing a value with zero doesn't change it.

Here's what $m \oplus d$ looks like, if it helps clarify:

$$
\begin{array}{ccc}
                 & 15 & \text{unknown bytes} & (\leftarrow m) \\
          \oplus & 7 & \text{00 00 00 ...}  & (\leftarrow d) \\ \hline
                 & 8 & \text{(same) unknown bytes} \\
\end{array}
$$

(I realize using decimal instead of hex here may look a little weird, but oh well.)

The original message's first byte was 15. We wanted it to be 8 instead. We found $15 \oplus 8$ to be 7, so that's the value we right-pad with zeros, because the zeros won't affect the rest of the message. Linearity lets us pull off the trick. Of course, this technique works for any number of bytes, not just the first one.

(By the way: the need to right pad the difference with zero bytes is why we needed to know the length of the original message.)

Note: fgrieu's comment below about some CRCs having a weaker property is relevant, but doesn't materially affect the attack (set $z = 0$ in his comment to use the same attack essentially).


Known risks for publishing ECDSA public keys and signatures

ECDSA is advertised to prevent existential forgery even in the face of an adaptive chosen-message attack.  That is: even if the adversary can control the messages you sign, not just see a few signatures, they still can't find a single message/signature pair for a message they didn't ask you to sign.

As part of your obligations of the ECDSA security contract, of course, you must choose the per-signature secret $k$ independently and uniformly at random; if you fail to do this—if you repeat the per-signature secret, or if your choice of it is even substantially biased—then you might leak the private key.  RFC 6979 defines a way to derive the per-signature secret by a pseudorandom function of the message under the secret key, which obviates the need for an entropy source at signing time—or at least mitigates a broken one.

But you could also just use Ed25519, which has this design built-in so you never need to worry about an entropy source at signing time, and has a clearer security story, and is an all-around better design.


Customizable Crypto Algorithms in Hardware

Your doubts are absolutely valid. Disguising the algorithm is not a valid argument for security. It also contradicts to Kerckhoffs Law.

  It (the algorithm) should not require secrecy, and it should not be a problem if it falls into enemy hands;

Designing cryptographic algorithms (ciphers, hashfunctions, ...) is a long and complicated process. In academia such algorithms are proposed and are analyzed afterwards by other researchers for a long time trying to break them. For AES, it took about two years from publishing to standardization.

If you take a look at linear or differential cryptanalysis, you will notice that innocent looking S-boxes for example can be highly biased reducing the cipher's security drastically. Same applies to other parts of the cipher.

This contradicts highly to the promised security. I would not trust these algorithms at all, nor a machine designing them.

For the hardware part. They could use some sort of FPGA-based HW. This would allow the company to implement the different algorithms on the same boards easily. Speed is a valid point. However, I doubt that their generated algorithms are side-channel proof, which means one could get information about the algorithm itself or the payload that gets en-/decrypted by measuring power, timing or EM for example. If so, the point of "unkown algorithm" would be broken.

TL;DR

Hiding the algorithm is not a good idea.
Refrain from inventing your own crypto.
Do not trust companies that break both :P

Hope this helps


Group Signature Scheme without Opening but with Revocation

(If members "expiring" is the only reason for revocation, then you could just skip the whole "standard signature scheme" part of the following, encode the expiration dates into the IDs, and have the signers' arguments include that issue too.)

Well, there's always the generic approach:

the GM generates a common reference string for an otherwise-noninterative computationally witness-indistinguishable system that is co-sound as a stand-alone argument of knowledge; i.e., it's infeasible to give a valid argument for any statement that it would be infeasible to know a witness for
the GM chooses a function from a collision-resistant hash family
the GM generates a two inner key-pairs, one for a standard signature scheme
and one for an identity-based signature scheme
the GSS's public key is the ordered quadruple whose entries are
the common reference string and the collision-resistant hash function and the inner public keys
the GM's private key is the ordered pair whose entries are the inner private keys
the GM uses the standard signature scheme for signing [the root hash of a Merkle tree of the result of sorting the revoked identities] along with [other information, such as a date], and regularly gives out that signature along with that sorted list, similarly to how CRLs are issued in standard implementations of PKI
for users issuing and verifying signatures, let "the sro" denote the most recent version known to the signer of the previous bullet point's signature together with [the root hash ... revoked identities] and the specified other information
the GM issues for the GSS by issuing for the identity-based signature scheme
users sign by generating a key-pair for a strongly unforgeable one-time signature (OTS) scheme, choosing enough information to specify what Identity Revocation List to use, arguing knowledge of a signature on the OTS verification key by an identity and two branches through the tree witnessing that the identity is not on the list, using the OTS signing key to sign the ordered triple whose entries are the sro and the argument and the message, and letting the signature be the ordered quadruple whose entries are the sro and the OTS verification key and the argument and the OTS signature
receivers verify by verifying the signature on the sro, verifying that its "other information" is appropriate (specifically, it's date is recent enough), verifying the argument for the sro and the OTS verification key and the message, and then verifying the OTS signature

The main problem with this approach is the size of the witness-indistinguishable arguments.

If you use the modification of figure 3 in this link obtained by replacing $K_{\text{binding}}$ with $K_{\text{hiding}}$,

then the existence of a witness that the commitment key is hiding suffices for perfect anonymity.

Thus, you could have the GM keep such a witness and give
concurrent zero-knowledge proofs that such a witness exists.

There are apparently lots of identity-based signature schemes that can work in bilinear groups.

It is possible that the type of system described in this paper can be adapted to such a scheme. $\:$ Although I'm not sure, it seems likely that NIZK co-sound arguments constructed from the previous two sentences could provide the same anonymity as I mentioned in the previous paragraph.

This paper gives a NIZK protocol with whose use in this approach comes with a trade-off:

soundness is based on the generic bilinear group model (analogous to the Random Oracle Model),

but by having users verify the common reference string's structure as described on page 3,

perfect anonymity is guaranteed without needing to trust or interact with the GM.

I have not managed to come up with any scheme for what you

are asking about that does not use a non-interactive argument.


I think the flash implementation is wrong: (using Linux, OS X terminal etc.)
not true, see below

echo 328831e0435a3137f6309807a88da234 | xxd -r -p > plain.dat
openssl enc -e -aes-128-ecb -iv 00 -K 2b28ab097eaef7cf15d2154f16a6883c -in plain.dat -out plain.dat.out -nopad

yields

hd plain.dat.out

00000000  57 16 aa fa 2c c6 8b 9b  8b 9b e5 0d 30 e3 f2 06  |W...,.......0...|

And I do trust openssl to give the right results.

Are you sure you use raw bytes (not ASCII representations of hex or something like that?). This is one block, using a 16 byte key. I tried the first of the AES-128 test vectors using openssl in the same way, and that gave the right result.

Post your code if you are in doubt.

Added:

I remembered that the order in the blockstate and keystate are different than one would think! Specifically, the block used in the flash implementation is really

32 43 f6 a8 88 5a 30 8d  31 31 98 a2 e0 37 07 34

Because a block is put into the state by column, not by row!
The same holds for the key, which is really

2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c

(which is, probably not by accident, the same as the one used in the test vectors you linked to)

So the flash implementation is right, but you need to realise that you have to put the blocks from the test vectors in by column, not by row. I made the same mistake in my initial answer as well. So if the state is a matrix a[i][j] and the block is b[i], we see that a[i][j] = b[4*j+i], and similarly for the key. See page 9 of the AES document, e.g.