ECDSA is specified in SEC1. It's instantiation with curve P-256 is specified  in FIPS 186-4 (or equivalently in SEC2 under the name secp256r1), and tells that it must use the SHA-256 hash defined by FIPS 180-4.

I'll leave aside ASN.1 decoration (since the question uses none), conversions between integer to bytestring of fixed width (which all are per big-endian convention), and to hexadecimal¹.

Signing using ECDSA on P-256 takes as input

a private key $d$ (the question's D), which is a 32-byte bytestring
a message, which is bytestring $M$ of $0$ to $2^{61}-1$ bytes
a random number generator

and outputs

a signature $S=(r,s)$ consisting of

an $r$ component (the question's R), which is a 32-byte bytestring
an $s$ component (the question's S), which is a 32-byte bytestring

Verifying a signature using ECDSA on P-256 takes as input

a trusted public key $Q$, which should be a point of curve P-256 other than the point at infinity. It was originally computed as $d\,G$ during key generation. It is defined by its Cartesian coordinates

$x_Q$ (the question's Qx), which is a 32-byte bytestring
$y_Q$ (the question's Qy), which in the question is³ a 32-byte bytestring

a message $M$
the signature $S=(r,s)$ in the form output by the signature process.

and outputs valid (if the message matches the one signed and there was no errors) or invalid (in all other cases except a successful forgery).

The question's message is the 27-character Example of ECDSA with P-256 converted to bytestring per some unspecified convention, likely ASCII or UTF-8. Both yield the same 27-byte bytestring $M$4578616D706C65206F66204543445341207769746820502D323536

Both signing and verification manipulate $M$ only to compute it's SHA-256 hash $H$ (the question's H), which is a 32-byte bytestring. It is converted to an integer $e$ (the question's E), which when using P-256 thus SHA-256 is² $H$.

Signing is per SEC1 section 4.1.3. In a nutshell:

Draw a secret random number $k$ (the question's K) in range $[1,n)$, where $n$ is the order of the curve P-256. It is critically important that $k$ is uniformly distributed on this interval and independent⁴ of other $k$.
Compute the Elliptic Curve point $R=k\,G$ of the curve P-256, where $G$ is the generator point. $R$ has Cartesian coordinates $(x_R,y_R)$ (the question's R_x and R_y), but only $x_R$ is needed.
Compute  $r=x_R\bmod n$ (the question's R). If $r=0$ something went wrong⁵, ⁶.
Compute $k^{-1}$ modulo $n$ (the question's Kinv), that is the integer in range $[1,n)$ with $k\,k^{-1}-1$ a multiple of $n$.
Compute $s=k^{-1}(e+r\,d)\bmod n$. If $s=0$, something went wrong⁵.
Output $(r,s)$.

CAUTION: Signing can be the target of various attacks, e.g. timing or other side channel, and fault injection. Mitigation of these attacks is difficult.

Verification is per SEC1 section 4.1.4. In a nutshell:

Check that the point $Q$ of coordinates $(x_Q,y_Q)$ is an ordinary point of P-256; otherwise, output invalid.
Check  that $r$ and $s$ both are in range $[1,n)$; otherwise, output invalid
Compute $s^{-1}$ modulo $n$ (the question's Sinv), that is the integer in range $[1,n)$ with $s\,s^{-1}-1$ a multiple of $n$.
Compute $u_1=e\,s^{-1}\bmod n$ (the question's U)
Compute $u_2=r\,s^{-1}\bmod n$ (the question's V)
Compute the Elliptic Curve point $R=u_1\,G+u_2\,Q$ of the curve P-256, where $G$ is the generator point, and $Q$ is as determined by the public key. $R$ has Cartesian coordinates $(x_R,y_R)$ (the question's Rprime.X and Rprime.Y), but only $x_R$ is needed.
If $R$ is the point at infinity, output invalid.
If $e\bmod n\ne x_R\bmod n$, output invalid (see note⁶).
Output valid.

DISCLAIMER: This contains simplifications and likely errors⁷. It is only meant as an aid to understand the standards.

¹ Hexadecimal is only for display purposes in the question and this answer. It's use in application is uncommon, and would waste space.

² Some implementations avoid the rare case $e\ge n$ (where $n$ is the order of the curve P-256) by reducing $H$ modulo $n$ to produce $e$. That changes the outcome of neither signature nor verification, thus does not hamper interoperability.

³ If point compression is used, $y_Q$ is reduced to its low-order bit, which combined with $x_Q$ and the curve's equation is enough to fully define point $Q$.

⁴ In particular, independence precludes reuse. If we want to be standards-conformant, that's including when signing the same message with the same key. However, from a security perspective it is safe, exclusively in this case, to reuse an earlier $k$. In some ECDSA variants, that's used to generate $k$ as the output of a Pseudo Random Function keyed by $d$ with input $H$.

⁵ It is then advisable to consider this an attack and erase/zeroize/burninate the private key, although the official thing to do is to try another $k$.

⁶ In overwhelmingly most cases occurring absent attack or deliberate test, $x_R<n$. The official thing is to handle the contrary unmoved, but it is a corner case worth consideration, if only to handle it as above⁵ during signature. The case $e\ge n$ is rare² (like one in four billion), but comparatively very common.

⁷ Thanks to dave_thompson_085 for pointing some of the many errors I made, as usual; and pardon the endless stream of edits.


Derive a key from public data using a secret master key

I'd still go with HKDF. Since you already have a good uniform master key, you can skip the extraction step.

So HKDF simply becomes HMAC-SHA-2(masterKey, info+\x01) I'd start info with a string identifying your use, and add the user specific information after that.

Your system should be secure as well as long as you only produce a single block of output. Essentially the user specific info serves as an IV for a mode similar to AES-CTR.

NIST Special Publication 800-56C - Recommendation for Key Derivation through Extraction-then-Expansion defines a scheme similar to AES, but it's probably unnecessarily complicated for your scenario.


The problem suggests that the encryption does not use padding, and $C_0=\mathit{IV}$, $C_0'=\mathit{IV}'$. Then
$$E_k(C_0\oplus P_1) = C_1$$
$$E_k(C_1\oplus P_2) = C_2$$
$$E_k(C_0'\oplus P_1') = C_1'$$
You also have
$$C_1'=C_2$$
That is enough to find $P_1'$.


Normalization of points on an Elliptic Curve

This is just about the representation of the point on the curve.

In the affine form of elliptic curve points, $(x,y)$ is the representation of points. But in the projective coordination, points are in the form $(X:Y:Z)$. Let $K$ be a field, and let $c$ and $d$ be positive integers and $\lambda\in K^*$. In this representation $(X:Y:Z)\sim (\lambda ^cX:\lambda ^dY:\lambda Z) $. That is, any element of an equivalence class can serve as its representative. In particular, if $Z\ne 0$ then  $(\frac{X}{\lambda ^c}:\frac{Y}{\lambda ^d}:1) $ is a
representative of the projective point $(X:Y:Z)$, and in fact is the only representative
with $Z$-coordinate equal to $1$. In this state, affine form of points is $(x,y)=(\frac{X}{Z ^c},\frac{Y}{Z ^d})=(X,Y)$.

For more details you can see page $86$ of "Guide to elliptic curve cryptography", Hankerson, ....


Is there a cryptographic way (a la mental poker) two people can determine if they both Like each other, without revealing their personal preferences?

The answer to your specific scenario is no, it cannot be done. As mentioned in a comment, if Bob knows his preference (B->A) and learns that the result of the calculation is $0$, then Bob now knows Alice's preference, i.e., A->B is 0.


How to use a secret to allow the generation of public keys, where the private keys can be calculated later

To expand on Ricky's comment, assuming Alice and Bob are the only participants, they can use an identity-based encryption scheme where Alice also acts as the trusted third-party ("Private Key Generator" in the Wikipedia article). Namely:

Alice puts on her PKG hat, and generates the public parameters of the system and a secret which will be used later.
Alice removes her PKG hat, she broadcats the public parameters and says: anybody who wishes to send me messages, just use any string you want as your public key and send it to me along with your ciphertexts.
All the Bobs of the world encrypt messages using their chosen public keys and send the ciphertexts and the public keys to Alice.
When Alice wants to decrypt a message, she puts on her PKG hat and obtains the private key associated with the public key which was used to encrypt the message.
Alice removes her PKG hat and uses the private key to decrypt the message. Optionally, she may store the private key so that she does not have to do step 4 again if she receives another message encrypted with the same public key.

The only requirement is that when Alice wants to decrypt a message, she must know which public key it was encrypted with. There is no requirement on the public keys themselves, including how or by whom they are generated. In any case, Alice is the only one who can decrypt since she is the only one who knows the secret. Matching a specific Bob to a specific public key seems to make it more or less equivalent to a regular cryptosystem.


How to reverse x XOR (x >>> 1) XOR (x >>> 2)

In order to invert $f(x) = x \oplus (x \lll 1) \oplus (x \lll 5)$ (where all quantities are 32-bit), we do not need the low-order bits of $x$; given $f(x)$ we can find $x$.

Let's first solve $f(x)=1$ for $x$. We must have (where $x_i$ is bit $i$ of $x$, with $i=0$ for the low-order bit)
$$\begin{align}x_{0}\oplus x_{31}\oplus x_{27}&=1\\x_{i}\oplus x_{(i+31\bmod32)}\oplus x_{(i+27\bmod32)}&=0\;\text{ for }1\le i<32\end{align}$$

This is a system of 32 linear equations with 32 unknowns, and the tried and tested method of Gaussian elimination yields
$x_0=1$, $x_1=1$, $x_2=1$, $x_3=0$, $x_4=1$, $x_5=0$, $\dots$, $x_{27}=1$, $x_{28}=0$, $x_{29}=0$, $x_{30}=1$, $x_{31}=1$, which we can combine into $x=\mathtt{0xCAF84657}$ which indeed is such that $f(x)=1$ (see second part for alternative methods, based on polynomial arithmetic or brute force).

Given the rotation-invariant structure of $f$, it follows that for $0\le i<32$, the solution of $f(x)=(1\lll i)$ is $x=(\mathtt{0xCAF84657}\lll i)=k_i$.

And because $f$ is linear, we can solve $f(x)=y$ by combining with $\oplus$ those $k_i$ such that bit $i$ of $y$ is set; the combination being the desired $x$.

Or, for a more direct expression, we can write $x=y\oplus(y\lll1)\oplus(y\lll2)\oplus\dots\oplus(y\lll27)\oplus(y\lll30)\oplus(y\lll31)$ where the rotations $i$ in the terms are those such that bit $i$ is set in $k_0=\mathtt{0xCAF84657}$ (argument: this is such that $y=1$ yield $x=k_0$, and the rest follows by linearity and rotation invariance).

The Boolean matrix defining the system of equations is circulant; that allows finding $k_0$ by finding the inverse of the Boolean polynomial $1+z+z^5$ modulo $1+z^{32}$ using the Extended Euclidean algorithm for polynomials; see related answer.

More directly, with the indexes of the bits set in $x$ [resp. $y$ ] the coefficients of the Boolean polynomial $X(z)$ [resp. $Y(z)$ ], we have
$$y=f(x)\iff Y(z)=F(z)\,X(z)\bmod(1+z^{32})\;\text{ with }F(z)=1+z+z^5$$
thus inverting $F$ modulo $1+z^{32}$ (if possible) gives us $G$ which is to $f^{-1}$ what $F$ is to $f$.

In Mathematica, the Extended Euclidean algorithm for Boolean polynomials $1+z+z^5$ and $1+z^{32}$ is invoked as
{g,{u,v}} = PolynomialExtendedGCD[1+z+z^5, 1+z^32, z, Modulus->2]
giving the following result, where g of 1 at the beginning confirms that $f$ is invertible, and the bits sets in $k_0$ [and the rotation counts in the expression for $f^{-1}(y)$ ] are given by the coefficients of u, which I isolated on the second line:
{1,{
1+z+z^2+z^4+z^6+z^9+z^10+z^14+z^19+z^20+z^21+z^22+z^23+z^25+z^27+z^30+z^31
,z^3+z^4}}

For my initial answer, I actually neither did this, nor solve the linear system. If the problem was for more than 32-bit variables, I'd do that; but here I used brute force and wrote this C code which output 0xCAF84657 in about 5 seconds:

#include <stdio.h>
#include <stdint.h>
int main(void) {
    uint32_t x=0;
    do
        if ((x^((x<<1)^(x>>31))^((x<<5)^(x>>27)))==1)
            printf("0x%08lX\n",(unsigned long)x);
    while(++x);
    return 0;
    }


Why use Needham-Schroeder if we have Diffie-Hellman?

Both Needham-Schroeder (N-S) and Diffie-Hellman (D-H) are one of the earliest proposed key exchange protocols and thus they are usually used as classical textbook examples.
However, the originally proposed protocols have some flaws. The N-S Symmetric Key Protocol is vulnerable to a replay attack, the N-S Public-Key Protocol is vulnerable to a man-in-the-middle attack and the D-H is also vulnerable to a man-in-the-middle attack.

Therefore, improved schemes such as Kerberos (for N-S) and the Station-to-Station (STS) protocol (for D-H) were proposed.
The N-S makes use of a trusted server for authentication while the improved D-H or STS protocol uses public key certificates for authentication.
With STS, we are still making use of a trusted party which is the Certificate Authority for authentication.
Even though the web of trust concept (in PGP) may be used, it may not be scalable.

So the main differences between the two protocols would be:

To trust a single trusted party which you can maintain yourself or to trust the public Certificate Authorities.
To depend on the security of the underlying encryption schemes (such as AES for Kerberos) or to depend on the assumption of the discrete logarithm problem (for D-H).


Modern ciphers are explicitly designed to be resistant to key recovery under known and chosen plaintext attacks. Assuming a successful cipher design, encrypting an incrementing counter does not offer an adversary any advantage in regards to obtaining the key, or predicting future ciphertext blocks.

This could be less true with a weak cipher and/or extremely large numbers of encrypted plaintexts.


Difference between single-pass and two-pass MACs

I suspect the questioner is asking not about MAC's per say, but rather Authenticated Encryption (AE, and if there is additional data, AEAD).  I've been wondering this myself, so I asked Phillip Rogaway of UC Davis, who is one of the creators of EAX - a "two pass" "online" operation mode for block ciphers that - since it provides AE (confidentiality and integrity in the same process) does not need a MAC.
His response is really quite helpful - so (with his permission) I'm quoting it here:

There's no standard and rigorous definition of "one pass" vs. "two pass" for AE / AEAD schemes.  Focusing only on encryption and the processing of plaintext, people mean either of two things by the terms “one pass” and “two pass”:

“One pass” (or “online”) could mean that the algorithm is constructed so that you can process an arbitrary length plaintext, left-to-right, spitting out the corresponding bits of ciphertext, again left to right, as you  go, while you use only constant memory.   In this sense, EAX is one-pass. This notion is easy to make rigorous. “Two pass” would then be interpreted to mean that you can make due with two constant-memory left-to-right passes through the plaintext, but not one.  And so on.

Alternatively, “two pass” might mean that, when a human being looks at the description of the mode, there is one logical part of the design, this comprising a significant portion of the computational cost, that is clearly designed for privacy; and there is another logical part of the design, again a significant portion of the computational cost, intended for authenticity.  One pass would mean that you can’t partition things up like this: that the privacy and authenticity are more tightly interwoven (often with an “authentication tag” being computed cheaply as a byproduct of whatever else is going on for privacy).  I don’t know any way to make this concept rigorous, but I think it’s the more traditional use. Under this (informal) notion, EAX is two-pass, despite it being online. To help separate these uses, and stop calling something “two pass” when it could easily be implemented so as to be online, my paper with Krovetz on OCB3 introduced, for sense (2),  “integrated” and “composed” instead of “one pass” and “two pass”. I don’t think these terms caught on ;-)

And for the curious, the papers he refers to is (I think) The Software Performance of Authenticated-Encryption Modes
I found (after getting his answer) his FAQ quite helpful - especially this answer.


Calculating IHVs from known message and hash output

By 'IHV', I assume you mean the Initial Hash Vector; that is, the state of the hash function before you start hashing.

Well, if they aren't using the standard initial values (specified by the hash function definition), well, there isn't much you can do.  The problem is that the compression function used by Merkle-Damgaard hash functions (such as MD5 or SHA-1) is specifically designed to be noninvertable; that is, the problem of "finding the previous state, given the final state and the value being hashed" is a hard problem.  They design things that way because if that wasn't true, the "second preimage problem" is easier than expected.

This hard problem of "running the hash function backwards" is precisely the problem you would need to solve to reconstruct the hash function's starting value.


The data must be encrypted and decrypted very fast in case of
  emergency.

  Which encryption algorithm should I use? I think I should use AES.

Indeed, symmetric cryptography (such as AES) is a good choice for performances. But a significant factor that you did not mentioned is the platform on which the algorithms will run. Does it contains cryptographic hardware accelerators? If yes, for which kind of algorithms (ECC, AES, RSA, ...)?

That will determine which algorithm will be the most relevant.

For example, if you have hardware accelerators for ECC or RSA, involving asymmetric cryptography to exchange the secret keys used for encryption should not slow down the system that much. In the other case, it can be very challenging to implement it in software with good performances on an embedded device.

This is also the same compromise for the choice of the symmetric algorithm. If you have a hardware accelerator for AES, then you should probably use it. In the other case, AES will not be the fastest algorithm. For efficient software implementations on embedded devices, you can take a look at lightweight ciphers.


Generate $4\times 4$ Sboxes with a given branch number

The differential branch number is the sum of hamming weight between input and output difference distribution table (DDT). it is similar to linear branch number.

One way to construct S-box with branch number 3 is to use concept of differential-equivalence, DDT-equivalence and the $\gamma$-equivalence as shown in paper "Two Notions of Differential Equivalence on Sboxes".

The new paper accepted "Reconstructing an S-box from its Difference Distribution Table " provides algorithm to reconstruct S-box . therefore, you could apply the concept on  $\gamma$-equivalence DDT to find S-Box with branch number as you want.


Can a TLS client perform any DH regeneration?

A client can indeed "regenerate" DH-keys.
But this simply means he re-connects to the server. The Logjam attack works by recording the connection establishment and then compute the derived private key. For this attack to work the domain parameters of the DH-exchange need to remain unchanged as precomputation is neccessary. If you just reconnect the server will present you with the exact same group and the attack will only take seconds to decrypt the session key. For Logjam to be defeated one needs new domain parameters, which take a while to be generated, hence this isn't done on every connection, usually this isn't even done in years.

Logjam isn't solely a server issue. If the vulnerability is fixed on either the browser (how-to: next paragraph) or server-side it's closed. Both sides need to support it and all major browser companies (Mozilla, Google,...) already announced patches to close this vulnerability.

The client can circumvent the issue by requiring 2048-bit+ primes for the domain parameters of DH, if the client decides to use DH-exchange.
The best way to avoid Logjam is to avoid DH, by choosing ECDH, which isn't vulnerable.This is also the way recommend by the authors of the accomplying paper.


Is there difference between Algebraic Homomorphic Encryption and Fully Homomorphic Encryption Schemes?

It seems that the answer depends on who you ask. Some would say that they are the same. Personally I feel there is a difference. To me, an algebraically homomorphic cryptosystem is one that supports unlimited multiplications and additions of ciphertexts due only to the mathematical structure. A fully homomorphic cryptosystem is one that supports unlimited multiplications and additions of ciphertexts. Thus all algebraically homomorphic cryptosystems are fully homomorphic, but not the other way around.

Given this distinction, none of the existing fully homomorphic cryptosystems are algebraically homomorphic. All existing systems take a somewhat homomorphic cryptosystem and use some tricks to make them fully homomorphic (most commonly Gentry's bootstrapping idea).

PS. I read a paper recently which made this distinction, but cannot seem to find it. I'll keep looking so you'll have a reference other than me.


What Cipher Suite in this list is the worst to use

Assuming you are actually asking whether any cipher suite is objectively worse than the others, the answer is clear:

TLS_RSA_WITH_3DES_EDE_CBC_SHA. Why? Well, this cipher suite suffers from 3 "major" problems, at least one of which is remedied by any of the other cipher suites:

Lack of forward secrecy. This cipher suite doesn't use any form of (EC)DHE key exchange, thus if the private RSA key is leaked (eg through a server compromise), all passively captured past data exchanges can be decrypted.
Use of CBC. TLS has a history of having (somewhat practically exploitable) issues with its padding used for CBC, e.g. POODLE or with IV selection, e.g. BEAST. Also notable here is Lucky13, which apparently is somewhat hard to mitigate if you want to use CBC. The CBC padding issues are  available to attackers because AES-CBC is used in a mac-then-encrypt situation where the padding is removed before the message is authenticated.
Use of a cipher with a small block size. If you use a block cipher with a $n$-bit block cipher, you expect to see a collision in the CBC ciphertext after about $2^{n/2}$ blocks. With AES, this is $2^{64}$, but with 3DES this is $2^{32}$ blocks (due to its 64-bit blocksize) which gave reason for the Sweet32 attack.

You may also want to note that technically the security margin of three key 3DES is 112-bit, as opposed to AES' 128-bit, so it's worse off even there, but it's a matter of "meh, can't brute-force" vs "meh, can't brute-force".


Is there any simple interactive zero-knowledge proof?

What is the simplest known scheme that allows one to, given an input x : {0,1}* for which F(x) == y where F : {0,1}* -> {0,1}, elaborate a proof p : {0,1} such that V(p, y, F) iff F(x) == y?

First, in your definition the verifier needs to know $F,y$ and $p$, as he uses those in the verification process.

As @RickyDemer pointed out, if $F$ is some invertible function, the zero knowledge property trivially holds - but that might not be what you wanted:

If $F$ is invertible, the verifier can calculate $F^{-1}(y) = x$
Knowing $x$ and the distribution of the random coins used in the proof, the verifier can just act like the prover.

However, this is probably not what you had in mind with zero knowledge in the title. It does not mean, the verifier can't learn $x$. In order to achieve that, we need that $F$ is some kind of a one-way function. If we model the prover as computationally unbound, we could also assume that the evaluation of $F$ is super-polynomial, and in that case the polynomially bound verifier could not act like the unbounded prover - but then any  verification would most likely also be super-polynomial.

If we require $F$ to be a one-way function of some kind, a proof of knowing a preimage can take different forms, depending on the function $F$. The most common and simple ones utilize algebraic structures and known hard problems like the discrete logarithm. More generally, for any NP-complete problem you can create a zero knowledge proof (assuming one-way functions exist), and graph coloring is a classic example. For non-algebraic statements, there is also some research, but it's much more complicated. Here are two related questions, which have some relevant references:

Proving knowledge of a preimage of a hash without disclosing it?
How we can create a protocol using Schnorr as identification scheme and a hash function as a puzzle?


No, neither of the two blocks of 6 equalities in the current version of the question are correctly describing either a trapdoor one-way function (first citation); or its use for public-key encryption; or signature of a message using a one-way hash and RSA (second citation).

The two citations are only distantly related. In particular, the "one-way hash" in the second citation is not a "trapdoor one-way function" as defined in the first citation.

We'll be illustrating the vocabulary in the first, then the second citation, in the context of RSA only; in each case, giving formulas as attempted in the question.

Assume a public/private RSA key pair has been established. The public key is $(N,e)$, and as its name implies is assumed known to everyone.

In the first citation:

The "trapdoor one-way function" is the function $f$ that transforms $x$ into $f(x)=(x^e\bmod N)$; we'll note $c=f(x)$.
"the secret" (also "some secret information"), is the private key $(N,d)$, which is noted $y$ (or equivalently: anything which knowledge allows factorization of $N$).
Knowledge of the private key $y=(N,d)$ allows computing an $x$ from $c$, such that $c=f(x)$; that can be done as $x=g(c)=(c^d\bmod N)$; it turns out that if $c$ was established by choosing $x$ with $0\le x<N$ and computing $c=f(x)$, then computing $g(c)$ always give $x$.
Doing the same without "the secret" is believed intractable, for random choice of $c$, or for $c$ chosen as $c=f(x)$ for random choice of $x$ assumed secret.
"the secret trapdoor" (function) is the function $g$; notice that $g(f(x))=x$ if $0\le x<N$; and $f(g(c))=c$ if $0\le c<N$.

In textbook RSA public key encryption, $f$ is the encryption function, and $g$ is the decryption function. Encryption is public, while decryption requires knowledge of the secret trapdoor $y$.

The notation used in the question's equations uses a function with two arguments and derives both $f$ and $g$ from that. That is done by defining the RSA function as accepting as second argument the key (a pair of integers), as follows:

$i=(N,e)\;\;$ (the public key)
$y=(N,d)\;\;$ (the private key, unlocking the trapdoor)
$r(z,(N,k))=(z^k\bmod N)\;\;$ ($r$ is the RSA function, $z$ and $k$ are variables)
$x=\text{message}\;\;$ (the plaintext)
$c=r(x,i)=f(x)\;\;$ (the ciphertext per textbook RSA public-key encryption)
$x=r(c,y)=g(c)\;\;$ (the deciphered plaintext)

Note: this only illustrates textbook RSA public-key encryption, which is extremely insecure in many practical situation (e.g. $x$ is unknown, but known to belong to a known set, such as $\{\text{head},\text{tail}\}$, or a class roll). This is avoided in actual uses of RSA for encryption.

In the second citation, which describes signing a (possibly large) message using textbook RSA and a one-way hash function:

"the one-way hash function" is a one-way function, noted $H$, which has no relation to RSA, and is assumed to not be a trapdoor one-way function in the sense of the first citation; rather, $H$ could be something like SHA-512.
"document" is a message $m$, expressed as a bitstring (including, a file).
"the hash of the document" (also "a one-way hash of a document" of step 1) is the result of applying $H$ to $m$, noted $h=H(m)$; that $h$ is assimilated to an integer, and $0\le h<N$ holds.
In step 2, "Alice encrypts the hash with her private key" is poor terminology for: Alice applies the secret trapdoor function $g$ (as in our analysis of the first citation) to $h$; that yields $s=g(h)$.
In step 3, "the signed hash" is that same $s=g(h)$.
In step 4:

Bob computes "a one-way hash of the document that Alice sent"; that will be $h$ as originally computed by Alice if and only if the document that Bob received is exactly $m$ as Alice has processed it; the only if part is because $H$ is one-way (or, depending on threat model, collision-resistant).
(Bob) "decrypts the signed hash with Alice’s public key" is poor terminology for: Bob applies the trapdoor one-way function $f$ (as in our analysis of the first citation) to $s$ that it received from Alice, giving $f(s)$; in the absence of alteration of $s$, that will be $f(g(h))$, that is $h$ as originally computed by Alice.
Bob will consider that the document he received is as signed by Alice when these two computations of $h$ give the same result.

Again sticking to the notation in the question

$i=(N,e)\;\;$ (Alice's public key)
$y=(N,d)\;\;$ (Alice's private key, unlocking the trapdoor, known only to Alice)
$r(z,(N,k))=(z^k\bmod N)\;\;$ ($r$ is the RSA function, $z$ and $k$ are variables)
$m=\text{message}\;\;$ (the message to sign, approved by Alice)
$h=H(m)\;\;$ (the hash of the message as computed by Alice)
$s=r(h,y)=g(h)\;\;$ (the signature as computed by Alice)
$(m,s)\;\;$ (the signed message that Alice sends)
$(\tilde m,\tilde s)\;\;$ (the alleged signed message that Bob receives)
$\tilde h=H(\tilde m)\;\;$ (the hash of the alleged message as computed by Bob)
$\widehat h=r(\tilde s,i)=f(\tilde s)\;\;$ (the hash computed by Bob from the alleged signature)
Bob accepts $\tilde m$ as genuine and signed by Alice if and only if $\tilde h=\widehat h$.

Signing is by applying the secret trapdoor function, and can be performed by Alice only; anyone knowing Alice's public key can perform the verification that Bob does.

Note: this only illustrates textbook RSA signature with hash, which has known security limitations; notably, if the width of $h$ was small enough (e.g. 256 bit as if SHA-256 is used for $H$), and Alice signs many messages specially crafted by Carol, then Carol can forge another message and its signature, even though Alice never signed that other message. This is avoided in actual uses of RSA for signature.


Is PKCS#5 deterministic if both sides use an agreed salt and iteration count

Yes. PBKDF2, defined in PKCS#5, is deterministic; you can check its description.


Interpolation in the Exponent (Shamir Shared PRF)

The answer to this is that you need to select "gen"  not randomly, but specifically as a generator of order P (your modulus prime used for shamir).

For secp256k1 field of size P this works:

Select R = P*4-1.
Select a gen=H(w) such that pow(gen, P, R) == 1
During reconstruction choose R as the modulus

Now you've basically chosen a field R of order P, and everything will reconstruct correctly.

With ECC, you'd need to use curve.n as your modulus during sharing, but then you'll run into trouble with "hashing into the curve".  See: https://eprint.iacr.org/2009/226.pdf to use ECC.


Each participant can create his own random k,n secret sharing and send one share to each other participant.
Each participant can then add up his sub-shares to get his final share.

Due to linearity the resulting is also a valid shamir secret sharing.

This produces a random shared secret. If there is something you want to protect with it, we need to ask who knows it initially?


Curve25519 over Ed25519 for key exchange? Why?

There's a few different related parts here, and the nomenclature of the library you've cited is a little confusing.

Curve25519 is an elliptic curve over the finite field $\mathbb F_p$, where $p = 2^{255} - 19$, whence came the 25519 part of the name.  Specifically, it is the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, but you don't need to know the details other than that it was designed to admit fast computation of $x([n]P)$ given $n$ and $x(P)$ which is useful for Diffie–Hellman key agreement.

(Side note: Sometimes the Montgomery form is written with the letters $u$ and $v$ as in $v^2 = u^3 + 486662 u^2 + u$, especially when drawing a contrast to another form like Weierstrass or Edwards.)
X25519 is a Diffie–Hellman function built out of Curve25519.  An X25519 public key is the encoding of the $x$ coordinate of a point on Curve25519, hence the name X25519.

(Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic curve and X25519 means the cryptosystem.)
Edwards25519 is an elliptic curve over the same field, with a different shape, the twisted Edwards shape $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$, which admits fast computation of $P + Q$ given the $x$ and $y$ coordinates of $P$ and $Q$.  It is related to Curve25519 by a birational map, so most points on Curve25519 can be mapped to edwards25519 and vice versa.
Ed25519 is a public-key signature scheme built out of edwards25519, using the EdDSA construction.  An Ed25519 public key is the encoding of the $x$ and $y$ coordinates of a point on edwards25519.

Curve25519 and X25519 were developed first; then Harold Edwards came along and blew the minds of Dan Bernstein and Tanja Lange by inventing Edwards curves which let you compute $P + Q$ in constant time faster than any other curve shapes and competitively with variable-time (i.e., leaky) formulas for other curve shapes.  Fortuitously, it turned out that Curve25519 was birationally equivalent to a (twisted) Edwards curve, leading to Ed25519.  Under the birational equivalence of Curve25519 and edwards25519, each X25519 public key corresponds to two possible Ed25519 public keys.  As Ruggero explained, Curve25519 admits faster variable-base scalar multiplication, while edwards25519 admits faster fixed-base scalar multiplication and double-base scalar multiplication.

So what do you do if you want to use the same key material for key agreement and signature?  There are a few options:

The library you cited uses edwards25519 points as public keys, and converts them on the fly to Curve25519 $x$ coordinates for key agreement.  This is simple and works if you have full control over the public key format and can choose to use edwards25519 points.  It's confusing to call the function ed25519_key_exchange, but such is life.
XEd25519 as used by Signal uses Curve25519 $x$ coordinates as public keys, and for signatures, always chooses the ‘positive’ point on edwards25519 as a corresponding Ed25519 public key.  This is useful if you already have a lot of public keys deployed and you really don't want to redeploy them just to determine which ones are positive and which ones are negative.
The signature scheme qDSA, following an idea used in Mike Hamburg's Strobe, uses Curve25519 $x$ coordinates as public keys, and uses a variant of the EdDSA signature equation to take advantage of the Montgomery ladder and avoid the Edwards shape and point addition altogether.  This is useful if you want very small code like on a microcontroller, where there is a high cost to having several different scalar multiplication routines, e.g. for fixed-base vs. double-base.


Affine cipher : Why it is required to have GCD(a, m) equals to 1

OK, to understand this issue, let's first recap how the affine cipher is defined:

$$c=a\cdot x+b\bmod m$$

Note that the following holds: $a\cdot x+b=c\iff a\cdot x=c-b$, where you would calculate $-b$ as $m-b$ which is $>0$ because $m>b$ because otherwise you could reduce $b\bmod m$ further.

Ok, so on our way to decryption we now only need to get $x$ out of $a\cdot x=c'\bmod m$ (with $c'=c-b\bmod m$).

Now if $d=\gcd(a,m)>1$ then this equation has either $0$ or $d$ solutions, neither being what you want from a decyption function (no plaintext recovery or uncertain plaintext recovery).

So this is why we make the restriction $\gcd(a,m)=1$, which will ensure that there is exactly one integer solution to $a\cdot x=c'\bmod m$ with $0\leq x<m$.

If you want illustration of the lack of solutions, have a look at the modular multiplication table of for example 15. You will note for example that there is no $x$ such that $6\cdot x=5\bmod 15$ however, there are three $x$ such that $6\cdot x=3\bmod 15$ and note that $\gcd(15,6)=3>1$.


Chosen Cipher Text Security for Double Encryption

To understand the case of double encryption's CCA security, I read the paper Chosen-Ciphertext Security of Multiple
Encryption by Yevgeniy Dodis and Jonathan Katz in 2005.
With the help of this paper, now I'm able to understand why for the mentioned encryption scheme it will be no longer CCA secure when the key $k_2$ is known! Do give it a read for those having issues understanding CCA multiple encryption schemes.


GCM as a general purpose cryptographic hash?

GCM does not provide secure hashing. In general, a MAC has all the properties of a hash only against an adversary who does not know the key. If you want to use the function as a MAC then the key has to be public and then A MAC is not a secure hash. With most common MAC constructions other than HMAC, if you know the key, you can easily construct, at least, a second preimage.

For example, look at how the authentication tag GHASH of GCM is calculated. I use the notations from the Wikipedia article; the plaintext is $A_1A_2A_3\ldots$ (split into blocks), $H$ is calculated from the key (so it would be some public constant to use GHASH as a hash) and the $X_i$ are calculated incrementally to produce the hash (so if $X_i = X'_i$ for some $i$ and two different messages then the hash will be the same).
$$ \begin{align}
X_0 &= 0 \\
X_1 &= A_1 \cdot H \\
X_2 &= (X_1 \oplus A_2) \cdot H = ((A_1 \cdot H) \oplus A_2) \cdot H \\
\end{align} $$
Let $A'_1 = A_2 \cdot H$ and $A'_2 = A_1 \cdot H$. Then $A_1A_2A_3\ldots$ and $A'_1A'_2A_3\ldots$ are (assuming that $A_2$ didn't happen to be equal to $A1 \cdot H$) two distinct messages with the same hash (and the same length, incidentally). And that's just from a trivial computation — with a bit more work first preimage can be broken too.


Security analysis of a "one-time pad" type hill cipher

Expand the equation system corresponding to the matrix multiplication:

$c_j = \sum_{i=0}^{n-1}k_{i,j}p_i$

In other words, each element of the cipher text corresponds to the sum of the cipher text elements of an OTP encryption of the input plain text. If the matrix is never reused, it should be fairly easy to go from here. You are basically using $n$ one time pads to encrypt the message instead of a single one. - Almost, since the $k_{i,j}$ values of the matrix have to be selected in such way that the determinant is not zero (presuming a prime field is used for the arithmetic operations). The next step is therefore to observe what this constraint means: If the diagonal is selected at random, the other matrix elements might be selected in such way that the determinant is non-zero.


How to detect if n long messages have encrypted with the same one-time pad?

Specifically, the $K(K-1)/2$ symbolwise difference of the, say $K$, messages should obey the plaintext distribution. If the plaintext is in a natural language, patterns can be detected using various techniques.

If the messages are binary $n=5$ won't be nearly enough. If the messages are in ASCII, $5$ symbols yield 40 bits, so that might be enough, and you'd even rule out key guesses that don't yield printable ASCII characters when XORed with ciphertext.


Is a second preimage attack on MD5 feasible?

As far as I am aware, there are no practical known second pre-image attacks on MD5, under the conditions you listed.

However: if the attacker can control any part of the original, I would worry about using MD5 in this setting.  Its security in this setting may be fragile and there may well be cleverer attacks than anything currently in the literature.  I wouldn't be shocked to discover that second pre-image attacks are possible if the attacker has control over part of the original, even if we assume that the original starts with some unpredictable stuff before the part that the adversary can control.

So using MD5 in this way in new systems would not be prudent.  (I don't think I'm telling you anything you don't already know...)


Signing a binary hash vs character representation of the same hash

Which of the hash versions (hash_bin – 4 bytes / hash_text – 8 bytes) is better to use for signing the hash by RSA, security-wise?

Doesn't matter; as long as there is a 1:1 relationship between versions, it doesn't matter which representation you sign.

The only situation where you might run into a problem is if two different hashes (with version A) mapped to the same hash (with version B) - that doesn't happen here.

Now, with RSA, we (almost) always hash the message being performing the actual low-level RSA operation - are you doing the traditional RSA signature method here (which would involve computing a hash of your hash)?  Or, are you expecting to take the hash you have, do RSA padding (you are doing RSA padding, aren't you), and then doing the RSA private operation)?


What is so special about elliptic curves?

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others.

For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line that goes through the identity element. Here's a handy picture for one of the best known conics, the unit circle $x^2 + y^2 = 1$:

If you take the identity element to be $(1, 0)$, then you get the very simple addition formula (modulo your favorite prime)

$$ (x_3, y_3) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)$$

This is much faster than regular elliptic curve formulas, so why not use this? Well, the problem with conics is that the discrete logarithm in this group is no stronger than the discrete logarithm over the underlying field! So we would need very large keys, like prime-field discrete logarithms, without any advantage. That's not good.

So we move on to elliptic curves, which do not have reductions to the logarithm on the underlying field.

But wait, we can generalize elliptic curves to higher degrees. In fact,

$$ y^2 = x^{2g+1} + \ldots $$

when $g > 1$ and some restrictions are respected, is called a hyperelliptic curve, and we can work on it too. But for these curves there does not exist a nice geometric rule to add points, like in conics and elliptic curves. So we are forced to work in the Jacobian group of these curves, which is not the group of points anymore, but of divisors (which are kind of like polynomials of points, if that makes any sense). This group has size $\approx p^g$, when working modulo a prime $p$.

Hyperelliptic curves do have some advantages: since the group size is much larger than the prime, we can work modulo smaller primes for the same cryptographic strength. But ultimately, hyperelliptic curves fall prey to index calculus as well when $g$ starts to grow. In practice, only $g \in \{2,3\}$, i.e., polynomials of degree $5$ or $7$ offer similar security as elliptic curves. To add insult to injury, as Watson said, the addition formulas also get much more complicated as $g$ grows.

There are also further generalizations of hyperelliptic curves, like superelliptic curves, $C_{a,b}$ curves, and so on. But similar comments apply: they simply do not bring advantages in either speed or security over elliptic curves.


How does re-hashing affects security strength?

By using more iterations you increase the work factor that an attacker needs to deal with needed to conduct a brute force attack.  This is a good thing.  More is generally better as long as it doesn't affect user satisfaction with UI responsiveness.  I think 10,000 iterations would be considered a low number at this point.  50,000 or 100,000 would be preferred.

Indeed one needs to consider the usual advice for password hashing,

Salt stored on the DB to disable Rainbow Table attack
Pepper stored on the Application server so that DB only attack will fail.
Work factor to increase the attack time by brute-forcing the users's passwords
Huge memory requirements against massive parallel run like in ASIC.

The good candidates for password hashing algorithms are PBKDF2, Scrypt, and Argon2id, the last one was the winner of the password hashing competition and should be preferable whenever available.


Determining the Shamir's secret sharing scheme for the following problem

Each person might be allotted more than one share of the secret.

Let $G$, $C$ and $D$ denote the number of shares allotted to a General, a Colonel, and a Desk Clerk respectively, and let $T$ denote the Threshold of the secret sharing scheme.  Then, we have that
\begin{align}
T &\leq 5G,\\
T &\leq 4C + 3D,\\
T &\leq 3G + 3D.
\end{align}
Can you find suitable values for $G,C,D$,and $T$? The total number of shares is
$N = 6G + 5C + 4D$ and we have a $(T,N)$ secret sharing scheme.

     $D=2, C=3, G=4, T=18$, and $N = 47$ seems to work. There are, of course, other combinations that would result in $18$ or more shares, e.g., $5C+2D$ or $4G+D$ but nothing in the problem statement says that this is not to be allowed. Note that the $5$ colonels (or the $4$ Desk Clerks for that matter) cannot stage a coup by themselves; the colonels have to have at least two Desk Clerks (or a General) as co-conspirators.

Addendum: in the spirit of @IlmariKaronen's answer,

Divide the secret $S$ into 6 shares in a $(5,6)$ secret-sharing scheme and give each of the six generals a share. Any 5 of them can reconstruct $S$.
Create a random binary vector $X$ as long as the secret $S$, and then make five shares of $S\oplus X$ in a $(4,5)$ secret-sharing scheme, giving one share to each colonel. Any four of them can reconstruct $S\oplus X$. Create $4$ shares of $X$ in a $(3,4)$ secret-sharing scheme and hand one share to each desk clerk. Any $3$ desk clerks can reconstruct $X$, and together with $S\oplus X$ from the $4$ colonels, $S$ can be reconstructed.
Create $6$ shares of $S\oplus X$ in a $(3,6)$ secret-sharing scheme and hand a share to each general. Any three generals can reconstruct $S\oplus X$, and together with $X$ from three desk clerks, can recreate $S$.

Note that this has have fewer secret-sharing schemes to implement than Ilmari's method, and the desk clerks and colonels have only one share to have and hold. Only the generals have two different shares and must remember to use the correct one in the two different cases when they are acting by themselves and when in conjunction with three desk clerks. Also, the desk clerks, by themselves, can only reconstruct $X$.


How to calculate M when the attacker know e and w

You have $\{(n,e=2), M, w, C, \text{ and }, C'\}$ where;
\begin{align}
C &= M^2 \pmod n \\
C'&= (M+w)^2 \pmod n = M^2+2Mw+w^2 \pmod n
\end{align}

Now calculate $C'-C = M^2+2Mw+w^2 - M^2 \pmod n = 2Mw+w^2 \pmod n$
Substruct $w^2 \pmod n$ get $2Mw \pmod n$
Divide by 2 and get $Mw \pmod n$.
Find the inverse of $w$ to mod $n$ and multiply it to get the $M$.

in total $$M = (C' - C - w^2) (2w)^{-1} \pmod n$$
Note : when $e=2$ it is not RSA. The below quote form this answer;

  In fact, the Rabin Cryptosystem does exactly that.


Is creating a own protocol safe or should TLS always be used?

Designing your own crypto protocol (using existing primitives) is dangerous if you're not sufficiently familiar with cryptographic protocol design and the ways such protocols might be attacked.

If you wish to gain such familiarity, I'd recommend taking a few introductory crypto courses that focus on protocol design and analysis.*  This won't turn you overnight into an experienced protocol designer, but it should at least give you some idea of how much you actually (don't) know about the subject.

Also, regardless of you own skill level, a critical part of designing a secure communications protocol is to get other experienced cryptographers to review it and look for ways to attack it.  Even the most skilled cryptographers can make mistakes and overlook potential attacks, so it's essential to have as many eyeballs on the system as possible.
To paraphrase Bruce Schneier, anyone can design a cryptosystem which they cannot break — what's hard is designing something that others cannot break, either.

This is also one of the main reasons to go for existing standard solutions whenever possible: they've already been subject to more scrutiny by skilled cryptographers than your home-brewed protocol is likely to receive in any reasonable time.  Thus, by leveraging existing standard protocols and implementations, you get to enjoy the benefits of this pre-existing third-party scrutiny.

(Of course, there are standards and then there are standards.  Something published in an IETF RFC or an NIST SP is probably fairly safe (except when it isn't), whereas something found in a random article in The International Journal of Computer Engineering and Agricultural Machinery may actually be complete bollocks.  When in doubt, look for credible reviews by well known competent cryptographers.)

As for TLS specifically, I'd say that it's a good choice in general, but hardly perfect; its major weakness is its complexity, which makes it hard to analyze thoroughly, and easy to make mistakes in implementing it.  Using an existing, thoroughly reviewed implementation helps, but even widely used TLS implementations have been known to carry unfixed bugs for a long time.  Especially on constrained platforms, where the complexity and overhead of TLS may be problematic in themselves, a well written and reviewed custom protocol may sometimes be a better choice than TLS — but it all depends on how carefully the protocol has been designed and implemented.

*) I'm probably not the best person to recommend any specific courses, but in general terms, I've heard good things about Dan Boneh's Crypto I and II on Coursera, for example.  There are also several decent books on the subject, but again, I hesitate to give any specific recommendations for lack of personal familiarity.


Proof of the Diffie-Hellman Key Exchange

Let $g^a = x \bmod p$ then  $k \in \mathbb{Z}$; $$g^a = x + k \cdot p$$ Now take $b$-th power of both sides and $\bmod p$.
\begin{align}
(g^a)^b &= (x + k \cdot p)^b \pmod p\\
g^{ab} &= x^b + x^{b-1}(k \cdot p) + \cdots + (k \cdot p)^b \pmod p\\
g^{ab} &= x^b \pmod p
\end{align}
Similarly;
Let $g^b = y \bmod p$ then $g^b = y + \ell \cdot p$ now take $a$-th power and $\bmod p$ and arrive
$$g^{ab} = y^a \pmod p$$
Therefore $$x^b = y^a = g^{ab} \pmod p$$


What is the practical relevance of the wordsize when using a Hash?

Yes, the internal word size of a hash algorithm has some significance, pretty much for the reasons given in the question.

Algorithms with 64-bit word size have a (typically sizable) performance edge on 64-bit machines (more precisely: for large messages, and comparable implementations, the ratio of the number of bytes hashed in a given time over that for a comparable algorithm with 32-bit word size will likely be significantly higher using a 64-bit machine and making good use of the architecture, than this ratio is on a 32-bit machine). For this reason we have SHA-512/256, a 256-bit hash obtained by truncating to 256-bit a natively 512-bit hash with internal 64-bit word size: on a 64-bit machine, SHA-512/256 can be faster than SHA-256, a natively 256-bit hash with internal 32-bit word size. See this for more details.

And, on most machines, there is some (typically small) performance penalty if the message to hash is not aligned to the native word size.


Do all ciphers have equivalent decryption keys?

Do all ciphers suffer from the problem of multiple equivalent decryption keys?

No. The number of non-equivalent keys is bounded by the number of permutations. Since the number of permutations is very high there is a very big chance that ciphers do not have equivalent keys. This is especially true for ciphers with a high block size (AES with 128 bits). Even if an equivalent key would exist, it would probably be rather tricky to find a set of two equivalent keys. How tricky depends on the cipher of course.

  Is the existence of equivalent keys an essential property for the security of a cipher?

Therefore no.

  If you could prove that a cipher had no equivalent keys, would that lead to a procedure for recovering the key under the known-plaintext attack model?

No. Finding that a cipher does not have equivalent keys would enhance the security of the cipher, not decrease it.

More information about equivalent keys here.


How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$

Actually, it is not necessary for the prover to show that "exactly half" of elements with Jacobi symbols being +1 are, in fact, QR.  Instead, here are some hints:

Assuming that n is not of that form (and also n is not of the form $n = p^a$, which is easy test for), the probability that a random element with Jacobi symbol +1 is a QR is at most $q$ (homework assignment for you: what is the value of $q$)
If we get a value $x$ from the verifier which is a QR, how can we show in a zero knowledge way that $x$ is a QR (with probability $> 1 - \delta$)?
If the provider gives us a series of random $x$'s, and we either respond to each $x$ with 'not a QR', or 'it's a QR; here's the zero knowledge proof with probability $> 1 - \delta$', how many trials with random elements would be needed before the verify can conclude (with probability $> 1 - \epsilon$) that the fraction of Jacobi symbol +1 elements which are QR are $> q$?


Decrypting a message encrypted twice with RSA but with same n

The approaches in the question are leading nowhere.

In both the present question, and the other question that it links to, it is used textbook RSA encryption (no padding), and two public keys sharing the same public modulus. But the similarity stops here. In the present question the plaintext is enciphered with the first public key, that first ciphertext (that we do not get) is enciphered again with the other public key, and we only get the final ciphertext. In the other question, it was given two separately obtained ciphertexts, and that's central to the cryptanalysis method that was used.

There's no easy way to find a $d_1$ corresponding to $e_1=11$; whatever was made to get $d_1=2$, that's wrong. To find a $d_1$ directly, we would need a factorization of $n$ (or equivalent information), and it is 1022-bit, which is out of our reach for proper generation.

A first observation is that the first of the two chained encryptions perform $m\mapsto c_1=m^{e_1}\bmod n$; and the second $c_1\mapsto c={c_1}^{e_2}\bmod n$. Thus $$\begin{align}
c&=(m^{e_1}\bmod n)^{e_2}\bmod n\\
&={(m^{e_1})}^{e_2}\bmod n\\
&=m^{(e_1\cdot e_2)}\bmod n
\end{align}$$
and we see that the two encryptions are equivalent to one encryption using $e=e_1\cdot e_2$, which we can compute. But that alone is not enough to conclude.

The crucial observation is that $e_2$ is unusually large (1018-bit): there's seldom a good reason to use $e$ larger than the common $2^{16}+1$, which is 17-bit, and it is exceptional to use $e$ more than 128-bit.

This hints that $e_2$ (and/or $e=e_1\cdot e_2$) may have been chosen such that a corresponding private exponent $d_2$ (or $d$) is short. Like, a $d_2$ sizably shorter than $n$ was chosen, then it was computed an $e_2\equiv {d_2}^{-1}\bmod\lambda(n)$, where $\lambda$ is the Carmichael function (or same for $e$ computed from a short $d$). In practice that would be almost as silly as reusing the same $n$ is, and comparable to the sin of leaving aside random padding; but this obviously is a puzzle. For short-enough choice of $d_2$ (and/or $d$), such a poor key generation method would allow to carry Wiener's attack. If that succeeds, we can factor $n$ and conclude. As a shortcut, if we find $d$, we can directly use it to decipher $c$.

It turns out attacking either $e_2$ or $e$ works, I guess because the actual generation method chose $d$, computed $e$, then chose $e_1$ as a small factor of $e$.

Note: a question with the same numeric values was recently asked, and got rightly deleted as off-topic after failing migration (this one is better because there is some general question, and some level of effort shown). It was discussed in the side channel.


Known plaintext attack on 3 round SIMON block cipher

The paper also discusses linear characteristics for multiple rounds:

We present several approaches to produce linear characteristics for
SIMON32/64 and present the best known linear characteristic for
11-round SIMON 32/64 with the bias of $2^{-16}$. We then extend this
characteristic to 13 rounds of the cipher.
We present several
approaches to produce an LC for SIMON32/64, as a case study, and
present the best known 11-round LC for this cipher with the bias of
$2^{-16}$ (expendable to 13 rounds of the cipher).

The linear approximations you list seem to be from equation 3. SIMON is a Feistel cipher. By combining the equation that describes one round of Feistel, the authors of the paper get the following linear expression for an entire round:
$$ (P_R)_2 \oplus (K^1)_2 \oplus (X^1_L)_2 = (P_L)_0, $$
which holds with probablity $3/4$. Here $X^1 = X^1_L || X^1_R$ is the output of the first round, and $P = P_L || P_R$ is the plaintext. The notation $(X)_i$ is used for the $i$th bit of $X$.
Note that the expression is written here for the first round, but it equally applicable to any round $i$, when written in the following form:
$$ (X^{i-1}_R)_2 \oplus (K^i)_2 \oplus (X^i_L)_2 =  (X^{i - 1}_L)_0, $$
where we replaced $P$ by $X^{i - 1}$ and $X^1$ by $X^i$.
This can of course also be written as
$$ (X^{i-1}_R)_2 \oplus (K^i)_2 \oplus (X^{i - 1}_L)_0 = (X^i_L)_2. $$
This is still true with probability $3/4$.
If we "substitute" (pile up) this last equation into a 3 round Feistel network (shown by Figure 3 in the paper), we get:
$$(X^{i - 1}_R)_2  \oplus (K^i)_2 \oplus (X_L^{i -1})_0 = (X^{i + 2}_R)_0  \oplus (K^{i + 2})_2 \oplus (X_L^{i + 1})_2,$$
or:
$$\Sigma_K \oplus (X^{i - 1}_R)_2  \oplus  (X_L^{i -1})_0 \oplus (X^{i + 2}_R)_0 \oplus (X_L^{i + 1})_2 = 0,$$
with $\Sigma_K = (K^i)_2 \oplus (K^{i + 2})_2$.
The paper goes on to use this expression for more rounds, but we can stop here. The above expression is a linear characteristic for 3 rounds of the cipher. Since we know with which probability the above expression holds (depending on the parity of $\Sigma_K$), we can start obtaining key bits.
This document explains that part well:

The process followed involves partially decrypting the last round of
the cipher. Specifically, for all possible values of the target
partial subkey, the corresponding ciphertext bits are exclusive-ORed
with the bits of the target partial subkey and the result is run
backwards through the corresponding S-boxes. This is done for all
known plaintext/ciphertext samples and a count is kept for each value
of the target partial subkey. The count for a particular target
partial subkey value is incremented when the linear expression holds
true for the bits into the last round’s S-boxes (determined by the
partial decryption) and the known plaintext bits. The target partial
subkey value which has the count which differs the greatest from half
the number of plaintext/ciphertext samples is assumed to represent the
correct values of the target partial subkey bits. This works because
it is assumed that the correct partial subkey value will result in the
linear approximation holding with a probability significantly
different from 1/2. (Whether it is above or below 1/2 depends on
whether a linear or affine expression is the best approximation and
this depends on the unknown values of the subkey bits implicitly
involved in the linear expression.) An incorrect subkey is assumed to
result in a relatively random guess at the bits entering the S-boxes
of the last round and as a result, the linear expression will hold
with a probability close to 1/2.

The above applies to SPNs, but for a Feistel network the prinicple is the same.


Storing a Secure Boot image with AES-GCM instead of AES + RSA signature

Yes, if you already have a shared symmetric key then this would be something to consider.

Note the following:

you do not need to store a private key in the embedded systems in your previous scheme;
the security of the key generating the signature is probably more important than the key providing confidentiality of the update (updates are often not encrypted - at least for many software packages out there);
related with the previous topic, keeping a private key secure at a central location is more secure than distributing the symmetric key (even if it is placed in a HSM);
the access to the HSM is paramount in this scheme, if the software contains all the data to use the key in a HSM, then one hacked embedded device is still enough to compromise the security - you probably need to encrypt / "sign" for each device with separate keys if you use just AES-GCM.

That's just out of the top of my head - there are very likely more points to consider.


Is padding of the digest needed in SHA256 with RSA-2048 scheme?

For a signing scheme involving generating a 256-bit digest using SHA-256 followed by RSA with 2048-bit modulus, the signature would always be 256-bit without padding..

That assertion is wrong. For every RSA signature scheme, the signature is always at least as wide as the modulus (or next to that; there are tricks to reduce it by a few bits). Much shorter signatures are not verifiable.

  Is there a need to pad the 256-bit digest to improve security?

If the question asks whether a more elaborate padding scheme than signing message $M$ as $(\operatorname{SHA-256}(M))^d\bmod N$ is needed: Yes. Otherwise, an existential forgery might be possible per a variant of the Desmedt and Odlyzko attack; it is feasible at least for a 200-bit hash.

Common RSA signature schemes:

RSASSA-PSS of PKCS#1v2.2. It is a randomized RSA signature scheme with appendix (that is, with the signature appended to the unmodified message). It has a strong security reduction to the RSA problem (finding $M$ from $M^e\bmod N$ for random $M$). It remains secure  (assuming slightly stronger hypothesis) if it's randomness source is stuck.
ISO/IEC 9796-2 scheme 2. It is a randomized RSA signature scheme with message recovery (that is, with some or all of the message conveyed in the signature itself, saving bandwidth). It has a strong security reduction to the RSA problem. It remains secure (assuming slightly stronger hypothesis) if it's randomness source is stuck.
ISO/IEC 9796-2 scheme 3. It is a deterministic RSA signature scheme with message recovery, equivalent to scheme 2 above with no randomness, and maximum ability to embed data in the signature (size of the modulus, minus hash width and 2 bytes). It inherits scheme 2's security reduction.
RSASSA-PKCS1-v1_5 of PKCS#1v2.2. It is a deterministic signature scheme with appendix. There is no known attack against this scheme, but no security reduction.
ISO/IEC 9796-2 scheme 1, a deterministic RSA signature scheme with message recovery. There is an existential forgery against this scheme when the adversary can obtain signature of chosen messages, thus the (fully compatible) scheme 3 should be used in all new systems.


Verifying randomness and uniqueness of TRNG output

There is no such thing as a random number and as such it is a category error to attempt to verify whether a particular set of numbers is ‘random’.  There are random generators of numbers; the relevant question is whether you—or, more importantly, a well-funded adversary—can predict the output when you don't know it a priori.  To answer that, you must:

Study the physics of mechanism inside the device.  Hire the world's best theoretical physicists to find the best model with humanity's current understanding of physics for how the mechanism behaves.

What verification can you do here?  You, or the experimental physicists you hired, can devise experiments to rule out alternative hypotheses for how physics might work.  But there's nothing at this stage that you can meaningfully do to the output of your RNG device.

Study the engineering of the device.  Hire competent engineers to determine whether there are ways for the device to fail, and if so, model how it will behave when it does fail.

What verification can you do here?  You, or the statisticians you hired too, can devise a hypothesis test to distinguish a failed component from a working component based on the output of your RNG device.
Make sure that computing the hypothesis test doesn't leak secrets through side channels.

If there is a CSPRNG involved, study the cryptography of the CSPRNG.  Hire the smartest cryptanalysts in the world to find distinguishers for the CSPRNG.

What verification can you do here?  You, or the cryptography engineers you hired too, can write automatic tests using known-answer test vectors to confirm that the CSPRNG implements the same design that has been subjected to decades of scrutiny and vetted by cryptanalysts publishing in serious peer-reviewed academic conferences around the world.
Note that the CSPRNG is essentially guaranteed to prevent hardware health tests, which is why you should apply those first to the hardware RNG output before conditioning it with a CSPRNG.

Alternatively, if you don't like these answers, I hear you can buy a book of certified random numbers from RAND Corporation, so named presumably because they're experts on the matter.

As for detecting duplicates, it depends on what units the data are in.  Duplicate bits?  Well, there's only two possible bits, so you probably have duplicates unless you've found new kinds of bits hitherto unknown to humankind!  Duplicate terabit-length bit strings?  You probably have only one of those even if you have several terabytes of data.  But maybe you meant something like 32-bit or 256-bit strings.  One way to detect duplicates in a large list is to sort it—costing $O(n \log n)$ time in the naive view of things, or $O(n \sqrt n)$ in the more realistic area-time metric which may become relevant in large volumes of data—and then scan through it for duplicates.  But this seems to be a general non-cryptographic algorithm question.


If you encrypt the words with the ECB mode then it will reveal information which we call frequency attack. The attacker can see which words are repeating among the rows and try to extract information especially if the attackers have some knowledge of the data contained in the database.

We can see this in a small SEARCH column if encrypted with ECB mode;

| ID  |...| SEARCH                                         |
| x01 |...| 0xF41, 0x650, 0x086, 0x331 ....                |
| x02 |...| 0xF41, 0x165, 0x086, 0x63f, 0x754 ....         |
| x03 |...| 0x650, 0x331, 0x1E6, 0x12f, 0x004 ....         |

As you can see, if you use the ECB mode directly, you can extract information from the SEARCH rows. Using ECB column in CryptDB is your choice. If you think that the data is vulnerable to attack, don't use the ECB mode.

Instead of using ECB, they choose to Song's work and modified as;

They split the words with standard delimiters, removed the repetitions, randomly permuted the repeated words, padded each word into the same size then encrypted.

They claim that their SEARCH nearly as secure as their RND mode, CBC mode with randomized IV for each encryption. They also claim that DBMS server cannot distinguish whether a word repeats in multiple rows and it only leaks the number of distinct words by comparing the size of RND column and SEARCH column.

It is not clear from their article that how this effect the performance. Actually, it is clear that the encryptions with different keys for each row are not performed on the Database. The whole burden of the system is based on the Proxy-Server, and the overhead to the proxy server is not measured for the article.


CTR mode encryption, instantiated with a secure block cipher, is IND-CPA secure under the usual definition (Bellare et al., 1997; Rogaway, 2011).

The term "mult-CPA" does not appear to be in widespread use, but it's found e.g. in these German lecture slides (Kiltz, 2011).  In the slides, it is defined (on slide 66) in a similar way as ordinary IND-CPA security, except that, instead of just single messages $m_0$ and $m_1$, the attacker is allowed to submit two vectors of messages $M_0 = (m_0^1, m_0^2, \dots, m_0^t)$ and $M_1 = (m_1^1, m_1^2, \dots, m_1^t)$ of length $t$ to the challenger, where the individual messages $m_0^i$ and $m_1^i$ have the same length for all $i$, and receives a vector of encrypted messages $(E(m_b^1), E(m_b^2), \dots, E(m_b^t))$ in return.

The same slides also contain a proof that mult-CPA security, as defined above, is equivalent to ordinary IND-CPA security.  The proof takes the form of a hybrid argument, and essentially shows that, if an attacker can distinguish encrypted vectors of length $t$ in the mult-CPA game with advantage $\epsilon$ over random guessing, then they can also distinguish individual encrypted messages in the ordinary IND-CPA game with advantage $\frac\epsilon t$.


Does some method exists to decrypt using some encryption keys (not all)

Extending from my comment:

  Yes it exists and is known as "threshold decryption". See Shamir's Secret Sharing. You may encrypt each share with with the respective preshared symmetric key for each party, or otherwise distribute the shares. Alternatively you may use asymmetric solutions instead which tend to have less ciphertext expansion than SSS at the cost of asymmetric operations.

For an example I'll use an online implementation of SSSS

The following example splits a secret message "my secret root password" into 5 components where any 3 may be used to recover the message.

% ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: my secret root password
Using a 184 bit security level.
1-1c41ef496eccfbeba439714085df8437236298da8dd824
2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
4-468de7d6eb36674c9cf008c8e8fc8c566537ad6301eb9e
5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0

As demonstrated

% ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
Share [2/3]: 5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0
Share [3/3]: 2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
Resulting secret: my secret root password

Instead of splitting the message, it is cleaner to split the key used to encrypt (and authenticate) the message. These key shares may then be encrypted using per-participant preshared keys or with public keys.

There are more threshold decryption options but they are more complicated. For more information these slides should be helpful. I must add that they reference trusted dealers, you may use verified dealers instead so they cannot cheat the protocol.


Two-way secret sharing for authentication?

This scheme is no different from standard password-based authentiation / standard cookie-based authentication:

You have a token (call it "password", "cookie" or "share") and an ID (call it "username"), you send it to the server, the server does some processing using additional values only it knows and gives you a yes / no answer for whether or not you are authenticated.

For classic passwords, this would be password-hashing with a DB-stored salt and comparison to the stored salt.
For cookies, this would be either a static comparison or an integrity check on the cookie server-side with a server-side static key.
For the given scheme, this is the secret-recovery and verifying whether the recovered content matches a specific format.

  Is this authentication scheme secure?

It is as secure as the standard approach of sending a username and a password. So it usually works, especially if your channel is authenticated, eg using server-authenticated TLS, anyways.

  If an adversary were to intercept a secret share for a user, would
  anything other than the user be compromised?

Well, if the server-side shares are user-dependent and the shares are unrelated / independent, then obviously nothing can happen to the others if one is compromised. The exception being of course if the user in question can log-in as an admin or something and just read-out or modify the shares or the received shares.


Is semantic security important in a hybrid cryptosystem?

Not a complete answer, but since you mentioned "unmodified RSA" I feel it's relevant.

Something stronger than vanilla RSA is necessary, even if it isn't semantic security.

Example: What if you have a public key exponent of 3 and the symmetric key being encrypted is 16 bytes long? Using raw RSA, $m^e$ would be about $128 \times 3 = 384$ bits long and thus smaller than any modern public key modulus would be. Being smaller than the modulus would prevent the calculation from taking advantage of the RSA Assumption, which is the premise of RSA's security. Since $m^e$ is easy to factor simply over the integers all security would be lost. (And this mistake would be somewhat obvious to the attacker because the vast majority of the high bits would all be 0.)


Paillier estimate attack costs on short keys

As far as we know, the most efficient attack against well-implemented Paillier encryption is to factor the public modulus $n$ part of the public key. That's also the best known attack against RSA, thus is well-studied.
For history of factorization open records, see this. In 2020, CADO-NFS has factored a 828-bit $n$ with "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)".
A smaller data point: CADO-NFS factors a 337 bit $n$ in 5 mn on a single 32-core system.

How much does it cost to break a 64bit keypair? And a 128bit? And so on till 256 or so?

Nothing worth consideration if there is a single such problem to solve.


Getting a key size of DSA/Elgamal certificate

It's extremely likely that 1024 is the master key size as authentication and signing are usually the main purposes of PGP. The key used for encryption is generally valid for a shorter time and is therefore a subkey of the master key. So both 1024 and 2048 bit public keys are included in the PGP certificate.

Note that the key size for encoding the key will be larger and the key strength (compared to e.g. an AES key) will be much less.

Both 1024 and 2048 bit keys are rather small for common purposes. It is highly advisable to upgrade to larger, RSA based keys. For more information about key sizes and their strengths, please take a look at https://keylength.com.


Query sensitivity of time series under differential privacy

I think you should explain what is $x_i$ in this time series. I would recommend linking the paper. I think without a strong context we could answer wrongly because maybe you could have understood something wrong as it has happened to me sometimes. Some points:

Query output could be $\mathbb{R}$ or $\mathbb{R}^n$, depends what kind of query you are defining and using.

You are right, I suspect they are defining a global sensitivity because maybe is easier to compute. But this depends on the kind of query they are defining on the paper, is a linear query, an only-one query  or a non-linear query


What is a “witness” in zero knowledge proof?

A witness for an NP statement is a piece of information that allows you to efficiently verify that the statement is true. For example, if the statement is that there exists a Hamiltonian cycle in some graph, a witness would be such cycle. Given a cycle, one can efficiently check whether it is a valid Hamiltonian cycle, but finding such cycle is difficult.

Knowledge extractors are used in the definition of proofs of knowledge. There, you don't just prove that some statement is true, but that you know a witness for this statement. A machine knowing something is defined via the existence of a knowledge extractor that, roughly speaking, interacts with the machine and then output the (extracted) witness.


Understanding multiplication in the AES specification

011b is a hexadecimal representation of the polynomial $m(X) = X^8 + X^4 + X^3 + X + 1$ (so you should never regard it as an integer). This polynomial has coefficients in the finite field $\mathrm{GF}(2)$, which is just the math-y way to say that its coefficients are in $\{0,1\}$:

hex | 0    1    1    b
bin | 0000 0001 0001 1011
x^n |         8 7654 3210

The 1-bits indicate which power has a coefficient of $1$. When you take any polynomial and divide it by $m(x)$, which has degree $8$, the remainder will have degree smaller than $8$, so using the same representation scheme as above, it can be represented on one byte.
57 and 83 are likewise representations of polynomials using that same method, I will leave it to you to check that when you multiply those two polynomials, you do indeed find the asserted result.
Your understanding is correct, those two operations are the same. But again, remember that you are working on polynomials, not integers.

EDIT: It's important to understand the difference between the objects AES manipulates and those you are used to. When you think of a data type which takes only one byte, you think of integers in $\{0,\dots,255\}$ with the usual addition and multiplication modulo $256$. The problem with those numbers is that while they have all the nice properties we are used to for addition, they fail catastrophically for multiplication: you can take two non-zero numbers (which ones?), multiply them, and obtain $0$!

This is not acceptable for AES: it requires a "nice" multiplication operation, meaning that when you multiply two non-zero elements, you want to obtain a non-zero element. This weird system of polynomials modulo $m(X)$ does exactly this.


Even with two rounds and known plaintext you don't know the intermediate round inputs to the sbox since you don't know the round keys. This necessitates the brute forcing of the key bits, or other structural analysis. There's your confusion.


Efficient function/algorithm/method to do modular exponentiation

Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python;

def fast_power(base, power):
    result = 1
    while power > 0:
        # If power is odd
        if power % 2 == 1:
            result = (result * base) % MOD

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

The if condition is an attack point for side-channel attacks. One can measure power usage and determine exponent bits. The below image or similar research images can show the idea of the attack.

If you are signing with RSA your private exponent can be revealed. Squaring can be implemented faster than multiplication, in that case, it can also be exploited. Therefore, you need constant timing to prevent this. The python library contains power modulus pow(a,e,n) which is based on repeated squaring and it is not secure. The below version of the repeated squaring method always calculates the (result * base) % MOD and discards it when it is not necessary. This may help mitigate the attack, however, this can be still traced if there is an instrument with enough resolution. Also, during compilation, make sure that this mitigation is not removed by compilers. Compilers, like Cray's CC can discard unused calculations as an optimization by default.

def constant_time_power(base, power):
    result = 1
    while power > 0:
        # else to prevent leak
        if power % 2 == 1:
            result = (result * base) % MOD
        else:
            result_temp = (result * base) % MOD

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

As mentioned above code, taddedhe above can be optimized by compilers with dead code elimination technique since the code contains unused code. Some compilers have pragma directives to disable local optimization. Instead of relying on compiler directives and their bugs, changes, etc., it is possible to use a constant-time conditional copy. The below show this;

def constant_time_power_with_conditional_copy(base, power):
    result = 1
    while power > 0:
        # constant-time conditional copy
        sBit = power%2==1
        result = ((result * base) % MOD)*sBit+(1-sBit)*result

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

The famous GMP library has a secure version mpn_sec_powm of their standard mpn_powm.

  This function is designed to take the same time and have the same cache access patterns for any two same-size arguments, assuming that function arguments are placed at the same position and that the machine state is identical upon function entry. This function is intended for cryptographic purposes, where resilience to side-channel attacks is desired.

There are other modular multiplications like Barret or Montgomery. They have also constant-time implementations. For example for Montgomery based

2009 Fast and Constant-Time Implementation of Modular Exponentiation by Gopal et al.


When encrypting twice with two separate keys, can a single key decrypt both steps?

It is possible with the old Pohlig-Hellman cipher.

Here's how it works:

The global parameter is a prime $p$
A secret key is a value $k$ which is relatively prime to $p-1$
To encrypt a message $M$, you compute $C = M^k \bmod p$, and that's you
To decrypt a ciphertext $C$, you compute $k^{-1} \bmod p-1$, and then compute $M = C^{k^{-1}} \bmod p-1$

With this system, if you encrypt with $k_1$, and then with $k_2$, the resulting ciphertext is $C = (M^{k_1} \bmod p)^{k_2} \bmod p = M^{k_1k_2} \bmod p$; hence, this is identical to encrypting with the key $k_1k_2 \bmod p-1$, and so can be decrypted by that key.


Hierarchical access control using CP-ABE

I can discern two cases here:

A strict hierarchy
A partial hierarchy

Using 1, "Hierarchical access control" as a term used with encryption implies that some users have more decryption power than others. Especially in access control modelling, hierarchy is usually "strict". This means that if A > B (A is "higher", and has "more" decryption power than B) then A can decrypt everything B can. If there are items B can decrypt but A cannot, A and B would not be on the same path in the hierarchy tree (i.e. A and B are in this case always comparable).

Using 2, the hierarchy would not be strict: there would be cases where A and B are not comparable, but in most cases it can be stated whether A > B or B < A.

For case 1, CP-ABEs offer a feature called "delegation". In a CP-ABE terms, this is relatively straightforward: if A > B, then the secret (attribute) key set of B will be a subset of that of A. (Remember though, that the mapping of real-life attributes to the scheme access structure may not be straightforward). Thus it should be easy to create a strict hierarchy.

Additionally, monotone CP-ABEs have the property that for an arbitrary scheme-supported set of users it is always possible to construct a hierarchy (possibly by adding virtual users).

However, if you want to use just cryptography to implement a strict access control hierarchy, hierarchical identity-based encryption (HIBE, e.g. https://eprint.iacr.org/2005/015.pdf) would be conceptually simpler, and probably more efficient).

Case 2 does not seem a matter of the cryptographic scheme, but a matter of the actual access control policy. If the policy does not include negative statements, most CP-ABE schemes will be able to support it (per encryption).

A completely another question is, what kind of access control features it is in general possible to enforce by content encryption only (Blu-Ray IPR yes, to some extent, but not for example general workflows).


salt usage for hashed password storage - design consideration

The main purpose of a Salt is for identical passwords to be hashed differently. Options 1 and 2 fail at this, they modify the hash function slightly but in the end do not add a Salt in any meaningful sense.
Rainbow tables still work, naive identification of identical passwords work, brute forcing all password simultaneously work.

Options 1 and 2 add no security over unsalted passwords, except perhaps a negligible slowdown in hash computation.

Option 3 provides real security, it prevents all 3 attack methods I mentioned earlier. If the Salt is saved with the password it would not be fragile, and corruption won't propagate. Nor would deleting an entry be an issue.

Essentially the basic premise of the problem lacking a random number generator is problematic when you have both storage and hash. If you have a hash function, building a good PRNG is trivial. An external entropy source is nice, but hardly required, even hashing the numbers 1,2,3,... would be reasonable for the purpose of producing salts(far better than options 1 or 2) despite predictability.

Clearly option 3.


Is CBC mode with a fixed IV secure, if a counter is prepended to the plaintext?

Assuming that the nonce values are unique and generated according to some fixed public counter sequence that is not under the attacker's control, is the encryption scheme described above (i.e. pad the nonce to a full cipher block, prepend it to the plaintext, and encrypt the result using CBC mode with an all-zero IV) actually IND-CPA secure?

Yes, nonce-based CBC has reasonable IND-CPA security bounds just like traditional CBC.

  If so, is there a published proof of this?  If not, is there a known attack under the IND-CPA model that doesn't assume the attacker can choose the nonces?

Yes: there is a published proof just below.  (I leave it to the asker to specify restrictions on venue that would exclude pseudonymous feathery bloviators on the internet.)

  How does the quantitative security (e.g. attacker's advantage as a function of the number of encryption oracle queries) compare to standard CBC mode with random IVs?  AFAICT, both are basically only secure up to the birthday bound, but a more detailed analysis could be useful.

Quantitatively, the security drops with the number of queries times the number of blocks, because there is a potential for a ciphertext-chaining block to coincide with a nonce.  But the security of CBC itself already drops with the square of the total number of blocks, which is larger than that already (unless every message is a single block long).

  As a bonus, what if the nonce is padded to some fixed length that is less than a full cipher block?  Is the resulting scheme still IND-CPA secure (assuming that the nonce doesn't overflow, of course) and if so, how does this affect the number of messages that can be safely encrypted?

How you format the nonce is inconsequential as long as nonces are distinct.  The crux is that in case (2) below, $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ is uniform random, so it has equal probability of coinciding with any fixed nonce.  Although stated in terms of the nonce $n_0$, the proof really assumes only that the first block fed to the cipher is unique.

Details.
An attack $A$ on a cipher is random algorithm that submits a sequence $m_0, m_1, \dots, m_{q-1}$ of $q$ queries (possibly adaptively), for messages up to $\ell$ blocks long, to an encryption oracle; for the last two queries the oracle returns the encryption of only one of them, determined by a fair coin toss, and the attack wins if it guesses correctly which face the coin landed on.  The IND-CPA advantage of an attack $A$ is defined to be $$\operatorname{Adv}^{\operatorname{IND-CPA}}_{\mathcal O}(A) := |\Pr[A(\mathcal O)] - 1/2|,$$ where $\Pr[A(\mathcal O)]$ is the success probability of $A$ on the oracle $\mathcal O$.  (The oracle is assumed to know how to count.)

Fix a block size $b$.  Each message $m_n = m_{n,0} \mathbin\| m_{n,1} \mathbin\| \cdots$ will be an integral number of $b$-bit blocks.  For a function $F$ and a block $\mathit{iv}$, define $$\operatorname{CBC}_F(\mathit{iv}, m_n) := F(\mathit{iv} \oplus m_{n,0}) \mathbin\| F(F(\mathit{iv} \oplus m_{n,0}) \oplus m_{n,1}) \mathbin\| \cdots.$$

In traditional CBC mode for a random function $F\colon \{0,1\}^b \to \{0,1\}^b$ of blocks, to answer a query for the $n^{\mathit{th}}$ message $m_n$, the encryption oracle samples $\mathit{iv}_n$ uniformly at random and reveals $$\operatorname{TCBC}_F(m_n) := \mathit{iv}_n \mathbin\| \operatorname{CBC}_F(\mathit{iv}_n, m_n).$$  The success probability $\Pr[A(\operatorname{TCBC}_F)]$ of any attack $A$ against traditional CBC is bounded by the standard CBC theorem: for uniform random $f$, $$\Pr[A(\operatorname{TCBC}_f)] \leq 1/2 + O(q^2 \ell^2/2^b).$$  To allow decryption one usually instantiates traditional CBC with $F = E_k$ for a block cipher $E$ and a uniform random key $k$; the standard permutation-for-function substitution lemma just adds $O(q^2/2^b)$ to the probability.
Define the following alternative scheme, where $G\colon \{0,1\}^b \to \{0,1\}^b$ is another random function of blocks: To answer a query for the $n^{\mathit{th}}$ message $m_n$, the oracle reveals $$\operatorname{NCBC}_{F,G}(m_n) := G(n) \mathbin\| \operatorname{CBC}_F(G(n), m_n).$$  If $F = G$, call it $\operatorname{NCBC}_F$.  Consider the following cases:

$G = g$ is a uniform random function $g$ independent of $F$.  Obviously, this is identical to traditional CBC mode for any $F$, because each output $g(n)$ is independent uniform random for distinct $n$ just like $\mathit{iv}_n$, so $$\Pr[A(\operatorname{NCBC}_{F,g})] = \Pr[A(\operatorname{TCBC}_F)].$$
$F$ and $G$ are the same uniform random function $f$.  This case is distinguishable from the preceding one only in the event that $n_0$ coincides with $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ for some $n_0$, $n_1$, $i$ among the messages submitted to the oracle, which happens with probability bounded by $O(q^2 \ell/2^b)$ where $\ell$ is the mean query length.  Thus, if $R$ is the event of this coincidence,
\begin{align*}
   \Pr[A(\operatorname{NCBC}_f)]
     &= \Pr[A(\operatorname{NCBC}_f) \mathrel| R] \Pr[R] \\
     &\quad + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \Pr[\lnot R] \\
     &\leq \Pr[R] + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \\
     &= O(q^2 \ell/2^b) + \Pr[A(\operatorname{NCBC}_{f,g})].
 \end{align*}
(Exercise for reader: Write down a concrete formula for a bound on $\Pr[R]$.  To make it simpler, replace $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ by, say, $m_{n_1,i+1} \oplus f(n_1\mathbin\|i)$: ensuring distinct inputs to $f$ can only raise the probability that one of the chaining values coincides with one of the nonces, and every output of $f$ on distinct inputs is independent uniform random.)
$F = G = \pi$ for a uniform random permutation $\pi$.  By a standard theorem about substituting uniform random permutations for uniform random functions, for any algorithm $A$ making $q$ queries,
\begin{align*}
   \Pr[A(\operatorname{NCBC}_\pi)]
     &\leq \Pr[A(\operatorname{NCBC}_f)] + q(q - 1)/2^{b + 1} \\
     &= \Pr[A(\operatorname{NCBC}_f)] + O(q^2/2^b).
 \end{align*}
(Alternatively, one can use the somewhat better but less standard bound $\Pr[A(\operatorname{NCBC}_\pi)] \leq \delta \cdot \Pr[A(\operatorname{NCBC}_f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.)
$F = G = E_k$ for a uniform random key $k$ and a block cipher $E$.  The distance between $\Pr[A(\operatorname{NCBC}_{E_k})]$ and $\Pr[A(\operatorname{NCBC}_\pi)]$ is the PRP advantage $\operatorname{Adv}^{\operatorname{PRP}}_E(A')$ of $A'(\phi) := A(\operatorname{NCBC}_\phi)$ to distinguish the block cipher $E$ from a uniform random permutation; presumably $E$ was chosen by years of cryptanalysis to put a confident bound on this distance for all reasonable numbers $q \ell$ of block cipher evaluations.

Thus, the success probability of an attack on nonce-based CBC making $q$ queries of mean length $\ell$ is bounded by:

\begin{align*}
  \Pr[A(\operatorname{NCBC}_{E_k})]
&\leq \Pr[A(\operatorname{NCBC}_\pi)]
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq \Pr[A(\operatorname{NCBC}_f)]
    + O(q^2/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq \Pr[A(\operatorname{NCBC}_{f,g})]
    + O(q^2 \ell/2^b)
    + O(q^2/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&= \Pr[A(\operatorname{TCBC}_f)]
    + O(q^2 \ell/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq 1/2 + O(q^2 \ell^2/2^b)
    + O(q^2 \ell/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&= 1/2 + O(q^2 \ell^2/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A'),
\end{align*}

or

\begin{equation}
  \operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{NCBC}_{E_k}}
  \leq O(q^2 \ell^2/2^b)
   + \operatorname{Adv}^{\operatorname{PRP}}_E(A'),
\end{equation}

i.e. essentially the same as for traditional CBC with a block cipher $E$.


How to know the difference between two ciphertexts without key stream in stream ciphers

Let's say $C_1 = P_1 \oplus K$ and $C_2 = P_2 \oplus K$ where $P$ is a plaintext, $K$ is the key stream and $C$ is the ciphertext.

Then if you XOR the two ciphertext together you get:

$$C_1 \oplus C_2 =\\
P_1 \oplus K \oplus P2 \oplus K =\\
P_1 \oplus P_2$$

There are all kinds of interesting properties of the XOR of two plaintext together. For instance, one of the most common characters is the space, so you can easily guess many characters by just flipping a bit (space is 0x20 or 0b0010_0000 after all). You can see that a lot of combinations are not possible or unlikely and you can perform frequency analysis.

This becomes even more powerful if you have 3 or more ciphertexts, as you can compare each and every pair, and if there are $n$ ciphertext then there are ${n \cdot (n - 1)} \over 2$ combinations to be made.


Why does DES implement so much Cross Wiring?

Inside each round, DES has a permutation that is used for diffusion and is crucial for security. However, you rightly point out that the initial and final permutations on the block of input/output and on the key have no effect whatsoever on security. Formally, it's not difficult to show that if you have an attack on DES without these initial and final permutations, then the attack also works when you do have.

So why does DES do this? Well, we can only guess. However, the assumption in the cryptographic community is that permutations are really really fast in hardware and really really slow in software. (In fact, a good percentage of the encryption time in software goes on these permutations. In hardware, it's just a matter of moving wires so it's almost zero cost.) This therefore slows down brute force search in software, relative to what can be done in hardware.

Why was this done? My guess is that this gives an advantage to certain very large organizations who have the resources to build special-purpose hardware. One such organization was instrumental in making DES secure (helping in the design of the S-boxes). However, they also pushed to make the key 56 bits long instead of 64 bits long. I guess that by making the software implementation slow, they felt that this could enough security (since most of the world would only have software) while enabling them to do brute force searches.

One could of course go for a less exciting theory which is that this was an additional level of security to slow down brute force searches in the future. But, I don't really buy it since if this was the concern at the time, then a bigger key would have been the right solution.