Different ways of building a ChaCha20-based RNG

How often should I replace the key?  The SUPERCOP implementation replaces the 32-byte key every 768 bytes.

It's a latency/throughput tradeoff.  Generating a longer batch of output raises the maximum latency of any query to the PRNG but also increases the throughput by using proportionally more CPU cycles for generating data and fewer for generating intermediate keys.  Pick the rate that serves your needs.  Maybe you should replace it after every 32-byte output so the latency is guaranteed to be bounded by a single ChaCha call.  Maybe you should replace it after every kilobyte of output to get better throughput.  Or just use 768 bytes like SUPERCOP.

  What about the nonce and counter?  The SUPERCOP implementation sets the nonce to zero and resets the counter to zero every time the key is replaced.  What about treating the nonce/counter similar to the key and periodically replacing them with ChaCha20 output?  (Except for a few counter bits that we need to crank to get 768 bytes of output.)

Additional implementation complexity for no security benefit.

  The SUPERCOP implementation replaces the key with the first 32 byte of the 768-byte sequence.  Can I use the last 32 bytes instead?  That would allow my implementation to keep less state.

Yes, but your results won't be compatible with SUPERCOP which may matter if you ever care about reproducibility or interoperability.

  What about replacing the key incrementally?  For example, instead of fully replacing the key with the first 32 bytes of every 768, what if I used the first 4 bytes of every 96 and incrementally replaced the key?

No.  Bad.  Do not.  My head hurts.


What's the best block cipher mode of operation for RSA?

The question is asking for a block cipher mode of operation usable with RSA.

Caveat: this is unusual and (almost certainly) not a right or valid solution to the problem at hand. See last section for the secure, common, simple, fast alternative.

RSA with proper random encryption padding (like RSAES-OAEP) is believed to give IND-CPA and even IND-CCA2 confidentiality. But it has limited capacity: like 190-byte message for 256-byte cryptogram (using RSA-2048 and SHA-256). Above that limit, ECB can safely be used if one does not care about the large speed penalty (especially for decryption) and significant size penalty due to repeated use of RSAES-OAEP.

RSA without random encryption padding (textbook RSA) is not secure. In particular, it allows to check a guess of the plaintext. Also, care must be taken that a plaintext block should be at least 1 bit less than than the public modulus is.

None of the modes of operation used for symmetric block ciphers make RSA secure:

ECB, CBC, PCBC all inherit the weakness of textbook RSA that a guess of a plaintext block can be trivially verified by re-performing the encryption of that block (which requires the public key only), and comparing with the actual ciphertext block.
CTR, CFB and OFB are totally insecure. Anyone can trivially decipher, since decryption uses the block cipher in encryption mode only.

Secure variations would amount to a specialized random padding. I'll refrain from suggesting any.

An efficient (and the most used in practice) solution to the problem of encrypting large messages with RSA is hybrid encryption: symmetric encryption with a random key, and encryption of that key per RSA. A slightly different option is RSA-KEM, where the key is secured (not encrypted) using RSA.


Does perfect secrecy imply uniform ciphertext distribution?

For a nonuniform construction with perfect secrecy, consider this scheme, with 2 bits of plaintext $(b_1, b_0)$, and four bits of key $(k_3, k_2, k_1, k_0)$.

The ciphertext consists of the three bits:
$$(k_3 \land k_2) \oplus b_0 \oplus k_0$$
$$b_1 \oplus k_1$$
$$b_0 \oplus k_0$$

This has perfect secrecy, in that for each ciphertexts, there is the same number of keys that map to any particular plaintext.  For example, for the ciphertext $(0,0,0)$, there are three keys that it to any plaintext, say, the plaintext $(1,0)$

This is nonuniform; as for random keys, the ciphertext $(0,0,0)$ will occur with probability three times that the ciphertext $(0,0,1)$ occurs at.


Sigma protocol to prove that the prover knows how open a commitment

Let $a \gets y^{u}g^{v}$, where $(u,v)$ are uniformly random exponents. $P$ sends a in the first flow, then receives a bit $e$ from $V$.

If $e = 0$, $P$ reveals $(u,v)$ and $V$ checks that $a$ is indeed $y^{u}g^{v}$ (hence that $P$ knows how to open $a$). If $e = 1$, $P$ reveals $z_0 = r + u \bmod q$ and $z_1 = b + v \bmod q$ ($q$ being the order of the group generated by $g$), and the verifier checks that $a\cdot c = y^{z_0}g^{z_1}$.

The intuition is the following: when $e=0$, $P$ proves that he can open $a$, and when $e=1$, he proves that he can open $a\cdot c$. As $P$ cannot anticipate the $e$ in advance, if this step is repeated many times, then $V$ is convinced that $P$ knows how to open $c$ with overwhelming probability. In other words, the protocol has soundness $1/2$.

To prove the soundness, you have to exhibit an extractor, id est, a simulator that will play the role of $V$, interacting with $P$, and that can extract $(r,b)$ from this interaction. This is what it means to "know" something: it can be learned from you. Of course, this simulator cannot just play as an honest verifier, because an honest verifier cannot learn the witness. The common method is to use rewinding: the simulator can run the prover, and rewind it to some intermediate step. By doing so, the simulator will ensure that the same first flow $a$ is the same in, say, two different executions, one with challenge $0$ and one with challenge $1$. From then it's easy to recover $r$ and $b$.

Things get slightly more complicated when you interact with a prover that succeeds with some noticeable probability $\varepsilon$, and not "always", but the same ideas work right, you just have to figure out the probability that $P$ succeeds twice in two runs of the protocol that are not really independent (as they share the same $a$); you can get the probability from standard probability lemmas (see the splitting lemma, for example).


"A has that generates digest" seems wrong because a hash can not do much. You need a function to make something.
"A one-way deterministic hash function" is correct. In theoretic computer engineering, it is not known whether "one-way"-functions really exist. But in common sense hash is called a "one-way"-function. And they are deterministic. For the same input, you get the same output.
"symmetric hash function" is correct. Hash algorithms are part of symmetric cryptography.
"a hash function that generates a digest" is correct. See 1.


To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.

If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key)
public_key = timestamp + public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision.
https://github.com/micahflee/trollwot


X509 CertificatePolicies, IssuerAlternativeNames, BasicConstraints extensions. What is done when Issuer signs?

The certificate policies are generally set by the CA. It is not something that is present within a certificate request (and if you would include it your request would hopefully be rejected or the included policies ignored).

Yes, the issuer alternative name would generally be identical to the subject alternative name of the parent certificate. But as the extension cannot be critical and isn't explicitly mentioned for certificate path validation, I see little reason to validate that it is.

You actually forgot to tell us that this is for a self signed certificate that you want to have signed.

This is not something you would usually do; in general you would generate a new key pair and certificate request and use that. Reusing the key pair is possible but should generally not be performed. It is not possible to change the issuer of a certificate without invalidating the previously set signature which includes this data element.

As for the criticality of the basic constraints: if you set the constraints it for a self signed leaf certificate rather than a root CA certificate I would set "is critical" to true (anything will parse these two constraints by now), "is CA" to false and finally path length constraint simply to 0.

If you do send your self signed cert to a CA and it will process your cert, then it will probably simply ignore the values set.


What is meant by a 'tag' with regards to transmitting a MAC?

A tag or authentication tag is something that is attached to (tagged along with) a message. It provides integrity and authenticity to the message.

Tags are also calculated for authenticated ciphers (AEAD ciphers, such as GCM). They can in that case be calculated by an internal MAC algorithm, but this does not have to be the case.

The size of an authentication tag can usually be configured. The size must be predetermined before use however (or an attacker can simply try and crack a shorter authentication tag). Usually the size is between 64 and 128 bits (128 bits being the block size of e.g. AES), although hash based tags may be larger than that.

A tag is usually placed at the end of the ciphertext. It can however in principle be communicated or placed separate from the ciphertext.

I'm not aware of any other meaning of the word "tag" or "authentication tag" within cryptography.


Cryptographic function that can 'pack' numbers

It seems we can use commitment schemes with homomorphic hiding and binding properties here. Often these commitment schemes are used for secure multiparty computation, and zero knowledge proof generation purposes.
A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding.
Commitment schemes are a way for one counterparty to commit to a value such that the value committed remains private, but can be revealed at a later time when the committing party divulges a necessary parameter of the commitment process. Strong commitment schemes must be both information hiding and computationally binding.
There are different types of commitment schemes.Pedersen commitment scheme is a popular one. There are other approaches such as Polynomial commitment schemes as well.
EDIT based on Comments
The purpose of commitment scheme here would be to commit on the existence of a number ( a packed number ) and then keeping the output hidden until there is a requirement for revealing it. An algorithm for packing the numbers can be implemented using arithmetic circuits, functional encryption etc. The advantage of secure multi-party computation will be to delegate the packing operation to multiple parties and aggregating the result of the operations. This is the perspective on recommending commitment schemes and multi-party computation.


Security proof for CBC as a prefix-free PRF

The answer is in the last sentence of the proof: "Once we have established that there are no collisions of these types, it will follow that all values associated with non-root nodes are random and independent, and this holds in particular for the values associated with the leaves, which represent the outputs of FCBC seen by the adversary."

To explain: we are only interested in the leaves which is the last invocation. However, the way to prove it is by proving it for all invocations. This seems quite natural because once there is an internal collision, the question of whether or not this leads to a final collision depends on the query contents, and this is unknown.


All standard literature on DES, including FIPS 46-3, number data bits starting from 1 for the most significant bit of the first word in reading order, incrementing by 1 as we go to lower-order bit, and moving to the next word after each multiple of the word size in bit. Here word can be 8-bit (for data and key), 32-bit (state formed by L/R), 28-bit (internal key formed by C/D).

For an implementer manipulating an array of 8 bytes at indexes 0 to 7 as input of IP, bit $i$ is for byte at index $\left\lfloor(i-1)/8\right\rfloor$ and has weight $2^{(-i)\bmod 8}$. In C, it might be testable as

Buffer[(i-1)>>3] & (128>>((i-1)&7))

Bit 58 belongs to the last of 8 bytes, Buffer[7], with weight 64 ( 0x40 ).


What is the NIST recommended maximum bias for random number generators?

Yes, NIST recommends $\epsilon \le 2^{-64}$. They consider such a sequence to have "full entropy".  It's in the definitions (page 4) of SP800-90C.

Converting that to a probability bias, $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$.
The interesting thing is that if the Leftover Hash Lemma is used, $\epsilon$ can be set by the designer.  ID Quantique TRNGs are designed with extractors such that $\epsilon \approx  2^{-100}$.


Finding Small Roots of Multivariate Polynomial Modulo an Integer in Sage (Coppersmith's Attack on RSA)

If you calculate modulo $8$, your polynomial becomes constant: $f(x, y) = 1-N \pmod{8}$

So something is wrong about what you are trying to do!


inverse element in Paillier cryptosystem

Yes. $r^n$ needs to be coprime with $n^2$. The only elements which have don't an inverse modulo $p^2 q^2$ are all multiples of $p$ and all multiples of $q$, so we just require $\gcd{(r^n, p)} = \gcd{(r^n, q)} = 1$.

$\implies \gcd{(r^n, n}) = 1$

Clearly, if $r$ is coprime to $n$, then $r \times r \times \cdots \times r ~ (n ~ \mathrm{times})$ will also be coprime to $n$, so:

$\gcd{(r, n)} = 1$

The probability of a random $r \in \mathbb{Z}_n^*$ not satisfying the above is equal to $\frac{n - 1 - \varphi{(n)}}{n - 1} \to 0$.

Assuming you use sufficiently large $n$, the probability of selecting a bad $r$ (one that cannot be inverted, according to your criterion) is smaller than the probability of your hardware failing and screwing up the calculation while you getting hit by a dozen lightning bolts simultaneously. I think you'll be fine.


With RSA or ECC, if I encrypt my private key with my public key, is there a way to recover my private key?

Although there is an answer here saying "no" for usual definitions, I want to strongly warn that there is no rigorous basis for that. Specifically, it is true that there is no known way of recovering a private key from an encryption of it with its associated public key. However, there is also no proof whatsoever that it isn't possible. Security of this kind is called "circular security" and there has been researching understanding it. In general, it is possible to achieve this in the random oracle model (quite easily - since the random oracle breaks the mathematical connection between the keys). Specifically, the encryption ${\sf enc}'_{pk}(m) = ({\sf enc}_{pk}(r), H(r) \oplus m)$ is circular secure when $H$ is modelled as a random oracle (meaning that it's secure when taking $m=sk$ or the like), as shown by Camenisch-Lysyanskaya in their EUROCRYPT 2001 paper titled An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. However, in general, there are no reductions from the security of the encryption scheme in general to the case of encrypting the private key, and one should be careful.


If the order of g is a prime number, is Pollard-rho the best?

Yes, Pollard-rho is the best algorithm known for solving hard instances of ECDLP (those where the generator is of prime order).

The current (public) record seems to be order $2^{117.35}$ for sect113r2 by Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar,  Peter Schwabe and Ralf Zimmermann in Faster elliptic-curve discrete logarithms on FPGAs (eprint, 2016). Notice that this is for a curve over a binary field, and prime fields are noticeably harder at equal size (because cary-less arithmetic is cheaper).


Why is $S(y) = y^{2^8-2} = y^{254}$ a one-to-one function and a permutation on $GF(2^8)$

Fact 1: the order of the field $GF(2^8)$ is $2^8$, hence the order of its multiplicative group $GF(2^8)^{\times} := GF(2^8) \setminus \{0\}$ is $2^8-1 = 255$.

Fact 2: For a group $G$ of order $q$, any element $g \in G$, when raised to the power of $q$ is equal to 1: mathematically put,  $g^q =1$.

Fact 3: for any element in a group there exists a unique inverse. An inverse to $g$ is an element (denoted by $g^{-1}$) that satisfies $g \cdot g^{-1} = 1$. In other words, the function $g \mapsto g^{-1}$ is one-to-one.

In our case, any element $g \in GF(2^8)^{\times}$ satisfies $g^{255} = 1$. Another, useful way to write this is that for any $g$ we have $g \cdot g^{254} =1$. Since $g \cdot g^{254}= g^{255} = 1$ we have that $g^{254}$ is equal to $g^{-1}$.

We conclude that the function $g \mapsto g^{254}$ is equal to the function $g \mapsto g^{-1}$ which is one-to-one, hence it is a permutation of the group  $GF(2^8)^{\times}$.

I'd be happy to elaborate on any unclear part.


Breaking RSA, given a special kind of oracle that decrypts related ciphertexts for us

Hint 1: what's the binomial expansion of $E_e^{RSA}(w+r)$?  That is, how can that be expressed as a polynomial in variables $w$ and $r$?  What degree are those polynomials, in terms of $w$?

Hint 2: suppose we ask for $E_e^{RSA}(w+r)$ for $0 < r < e$ (and we also know $E_e^{RSA}(w)$); what can we do with the corresponding $e$ polynomials?


Information leakage from the ecryptfs filesystem

(Disclosure: I'm the author of the functionality that you're asking about (good question!).)

Ubuntu's Encrypted Home Directory feature uses eCryptfs as the filesystem encryption technology.  eCryptfs is a layered filesystem built directly into the Linux kernel.  It mounts one directory on top of another.  The top directory is really just a "virtual" mountpoint.  Applications (and humans) can operate within that directory and read and write data without needing to know or be bothered by the encryption that's happening underneath.  The lower directory is where the actual encrypted files are stored on disk.

This approach has several advantages.  Unlike dmcrypt or full disk encryption, you don't have to pre-allocate a fixed amount of space dedicated to encryption.  You can also limit what gets encrypted a bit more to the information that's truly unique to you (improving overall system performance and power consumption).  There is some privilege separation between users, with each user having their own unique mount point and encryption keys.  And this particular feature is hooked into PAM, so that your directory is mounted automatically when you login, and unmounted when you logout.  Also, each and every file is encrypted with a unique, randomly generated key called the 'fek' (which is stored in the header of the file, and wrapped with the MOUNT passphrase).  What this means is that two cleartext files that are binary equivalent encrypt to two completely different ciphertexts!

On the flip side, there are a few things that you should be aware of -- now to the meat of your question!

The upper and lower file structure is pretty much identical, and some file names might be deduced (based on the default Ubuntu home directory skeleton)
File permissions, file ownerships, and file timestamps are not encrypted (so files with weird permissions, like 0123 might stand out)
Encrypted filenames limit the upper cleartext filename to about 160 characters (as the filename encryption requires some padding)
Swap should absolutely be encrypted, if you're using Ubuntu Encrypted Home, as anything in memory can be swapped to disk at any time (and certainly is, if you hibernate a system)
When the filesystem is actively mounted, only Unix run time Discretionary Access Controls  protect you from other users on the system (note that the home directory is permission 0700)
When the filesystem is actively mounted, eCryptfs does NOT protect you from the root user
Unless you move your ~/.ecryptfs/wrapped-passphrase off the local system and onto removable media (like a usb stick or flash disk), your LOGIN passphrase is the weak point of the encryption

Now, all that said, I still believe that Ubuntu's Encrypted Home delivers an outstanding balance of security and usability.  It's trivial to setup, and with a good login password, it provides extremely strong protection of all of your data in $HOME against off line attacks.  In other words, if someone physically steals your laptop, boots a live CD and starts digging around your $HOME/.Private encrypted data, they might glean some information about your filenames, directory structure, and timestamps.  But to obtain the contents of any particular file, they will need one of:

your LOGIN passphrase and your wrapped-passphrase file
the cleartext, 128-bit long, random MOUNT passphrase (stored inside of the wrapped-passphrase file)
enough time to brute force the 128-bit key in 2.
flaws in AES256

For more information, I've written magazine articles and a running series of blog posts on eCryptfs.


Is there a way to cleanse a picture of information from steghide?


We start with the definition of textbook RSA encryption: $c = m^e \bmod n$. From your first equation

$$c^{e^k} = c \pmod{n},$$ we have that if $c^{e^k} = c \pmod{n}$, then $e^k = 1 \pmod{\phi(n)}$ (Euler's theorem). Dividing both sides by $e$, we get

$$e^{k-1} = e^{-1} \pmod{\phi(n)}.$$

By definition, $d = e^{-1} \pmod{\phi(n)}$. Thus, $$c^{e^{k-1}} = c^d = m \pmod{n}.$$


Why should the factors $p,q$ of $n$ be half the bit length of $n$ in RSA?

They don't need to be restricted to that range. It's just a safe and convenient choice with no downsides.

Having a small p or q enables easier factorization using the elliptic curve method. To avoid ECM being faster than GNFS you need the primes to be larger than about 30% of the modulus (depends on the key size).
Having a large p or q reduces performance, because the Chinese remainder theorem based speedup becomes less efficient.
Having a nice power-of-two size for both factors is convenient for the implementer, especially in hardware
If you restrict them to the range $[2^{(n-1)/2} ... 2^{n/2}]$, you get the nice property that you can generate p and q independently and get modulus of exactly the desired size.
It only marginally reduces the number of available primes, which has no security impact.

Personally I'd go even one step further and restrict to $[\frac{3}{4} \cdot 2^{n/2} ... 2^{n/2}]$ because it simplifies key generation (just set the two most significant bits to 1)


Cipher that interleaves rounds from other ciphers?

kodlu mentions the interactions of the key schedules; with such a design, I would worry far more about the interaction between the round functions themselves.

A single round of AES, Serpent, Twofish, RC6 has high probability linear and differential characteristics; there's a reason why we have multiple rounds.  Now, the round functions within these ciphers are designed so that they play nicely with themselves; that while (say) a single round of AES has high probability characteristics, these high probability characteristics do no apply to multiple rounds.  That is, while we can find a high probability characteristic for a single round, we cannot join these high probability characteristics across multiple rounds.  This isn't by happenstance, the designers of these ciphers deliberately set things up this way.

This is not necessarily true while you mix-and-match round functions; while we can't find a high-probability characteristic that goes through several AES round functions in succession, there's nothing that says we can't find a characteristic that goes through an AES round function, followed by a Serpent round function, followed by a Twofish round function.  I'm not saying there is such a characteristic; I am saying it would appear foolish without doing a whole lot of analysis first.

If you feel an absolute need to do this sort of thing, it would make a lot more sense to keep the round functions from the same cipher together; do a bunch of AES round functions, followed by a bunch of Serpent round functions, followed by a bunch of Twofish round functions.  There, we can at least leverage some of the security proofs inherent within the separate ciphers.


A Simple Provably Secure Key Exchange Scheme Based on the LWE

Lemma 3 in this paper gives a better explanation regarding to your question 1 and 2.

For a simple answer for question 3, because we have equally divided region, this gives us even change on $k_i$ and $k_j$ be even or odd number, thus the output of function $E$ is uniform random.


The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be.
But ignoring this fact for a moment, one of your observations was indeed crucial.
A MAC does in general not hide it's input message.
As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure.
However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values.
And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle.
The CBC-MAC for our query will be computed as follows:
\begin{align*}
  t_1 :=& F_k(0^n)\\
  t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1)
\end{align*}
and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery.
We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$:
\begin{align*}
  t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\
  t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1
\end{align*}
And, given that $F$ is a secure MAC and it's output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$?
The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preseving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC.
Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$.
I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack.
For this, observe the values of $t_1,t_2$ in this instantiation.
\begin{align*}
  t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\
  t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1)
\end{align*}
I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$.
Therefore the attack sketched above works with this instantiation.


Is the concatenation of PRG output still a PRG?

The function $G'$, as you intuited, is indeed a PRG. The standard way to establish such results is through the hybrid argument. Details follow.

Let $G_n:\{0,1\}^n\rightarrow\{0,1\}^{n+1}$ be an $\epsilon(n)$-secure PRG; that is:
  $$G_n(U_n)\approx_{\epsilon(n)}U_{n+1},~~~~~(1)$$
where $\approx_{\epsilon(n)}$ denotes computational distance$^*$ of $\epsilon(n)$, and $U_n$ is the uniform distribution on $\{0,1\}^n$.

Given $(1)$, we show that $G'_n$ is an $2\epsilon(n/2)$-secure PRG (for even $n$ for the moment); that is:
  $$G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})\approx_{2\epsilon(n/2)}U_{n+2}.~~~~~(2)$$
This is accomplished in two steps using a hybrid (intermediate) distribution $U_{n/2+1}\|G_{n/2}(U_{n/2})$. We first show that
  $$G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})\approx_{\epsilon(n/2)}U_{n/2+1}\|G_{n/2}(U_{n/2}),~~~~~(3)$$
and then that
$$U_{n/2+1}\|G_{n/2}(U_{n/2})\approx_{\epsilon(n/2)}U_{n+2}.~~~~~(4)$$
$(2)$ follows by an application of the triangle inequality to $(3)$ and $(4)$. Since the arguments for $(3)$ and $(4)$ are similar, we prove just $(3)$.

Suppose for contradiction that $G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})$ is not $\epsilon(n/2)$-close to $U_{n/2+1}\|G_{n/2}(U_{n/2})$; then we show that $G_{n/2}(U_{n/2})$ is not $\epsilon(n/2)$-close to $U_{n/2}$ contradicting $(1)$. To be precise, given a distinguisher $\mathsf{D}$ for the former, we construct a distinguisher $\mathsf{D}'$ for the latter. The construction of $\mathsf{D}'$ is straightforward: given a challenge $y\in\{0,1\}^{n/2+1}$ (which is either $G_{n/2}(U_{n/2})$ or $U_{n/2+1}$), run $\mathsf{D}$ on $y\|G_{n/2}(U_{n/2})$ and return whatever $\mathsf{D}$ returns. If $y=G_{n/2}(U_{n/2})$ then $\mathsf{D}'$ presents  $G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})$ to $\mathsf{D}$; otherwise, it presents $U_{n/2+1}\|G_{n/2}(U_{n/2})$. Thus, $\mathsf{D}$'s ability to distinguish the distributions in $(3)$ helps $\mathsf{D}'$ distinguish the distributions in $(1)$.

A similar argument can be made for odd values of $n$, and together you get that $G'$ is a PRG. The argument can be extended for $G'(s)=G(s_1)||G(s_2)||\ldots G(s_m)$ for $s=s_1||s_2||\ldots s_m$: one has to define a $m-1$ hybrid distributions, where the $i^{th}$ hybrid replaces the first $i$ calls of $G$ with a uniformly random string; i.e., assuming $m$ divides $n$,
  $$\underbrace{U_{n/m+1}\|\cdots\|U_{n/m+1}}_{i \text{ terms}}\|G_{n/m}(U_{n/m})\|\cdots\|G_{n/m}(U_{n/m}).$$
Also, this PRG is only $m\cdot\epsilon(n/m)$-secure.

$^*$A distribution $X=\{X_n\}$ is $\epsilon(n)$-computationally-close from another distribution $Y=\{Y_n\}$ if for every computationally-bounded distinguisher $\mathsf{D}$,
 $$\big|\Pr[\mathsf{D}(X_n)=1]-\Pr[\mathsf{D}(Y_n)=1]\big|\leq\epsilon(n).$$
In particular $X$ is computationally indistinguishable from $Y$ if $\epsilon(n)$ is negligible in $n$.


The IV for GCM mode, in this case the thing we call the Nonce, is different from the IV used for the CTR mode inside of GCM.

Additionally as per the wording of your question, AES256 has a 256-bit key and a 128-bit block, not a 256-bit block, and encrypts plaintext in 128-bit increments.

For GCM, you MUST use a unique Nonce for every message. Inside GCM, the Nonce is turned into the CTR IV. If you look at kelalaka's answer, if the Nonce is 96-bits, the CTR IV is the exact same thing. If it is some other size, it converts it to a 96-bit IV using the referenced algorithm. CTR mode uses the IV plus a counter starting at 1 to generate the stream. The 96-bit IV plus the 32-bit counter equal the 128-bit input block to the cipher.

([     IV     ][ctr1]) -----> [AES] -----> ([      STREAM1      ])

The output 128-bit stream block is used to encrypt the plaintext blocks. If there are multiple blocks of plaintext, only one can be encrypted with a given counter, so it is incremented by 1, and the same operation is repeated to generate the next 128-bit stream block. If the final plaintext block is shorter than 128-bits, the unused stream bits are discarded.

MESSAGE = ([     PLAINTEXT1    ][     PLAINTEXT2    ][ PLAINTEXT3 ])
AUTHDAT = additional data to authenticate
LEN_T = desired length of authentication tag
L = length_64(AUTHDAT) || length_64(MESSAGE)
NONCE = 96-bits, therefore IV=NONCE
H = AES_K(0x00000000000000000000000000000000)
ctr0 = 0x00000001, ctr1 = 0x00000002, and so on

([     IV     ][ctr0]) -----> [AES] -----> ([      STREAM0      ])

([     IV     ][ctr1]) -----> [AES] -----> ([      STREAM1      ])
([     IV     ][ctr2]) -----> [AES] -----> ([      STREAM2      ])
([     IV     ][ctr3]) -----> [AES] -----> ([      STREAM3      ])

([     PLAINTEXT1    ]) XOR ([      STREAM1      ]) = ([     CIPHERTXT1    ])
([     PLAINTEXT2    ]) XOR ([      STREAM2      ]) = ([     CIPHERTXT2    ])
([ PLAINTEXT3 ])        XOR ([      STREAM3      ]) = ([ CIPHERTXT3 ])

CIPHERTEXT= ([     CIPHERTXT1    ][     CIPHERTXT2    ][ CIPHERTXT3 ])

H = GHASH(H,AUTHDAT,CIPHERTEXT,L)
TAG = truncate_LEN_T( H XOR STREAM0 )

As many blocks are generated as required to encrypt all the plaintext, as long as the limit of GCM is not reached, which is 549,755,813,632 bits, or 256 bits less than 64GiB, as explained here.


A chemical simulation based proof of work? Interesting, but let's ignore how the mathematics work for generating a solution based on my input key being "rhubarb". And zero knowledge based verification of said vegetable? Seems tricky. Must we assume that a 'simulation' is akin to a one way function/hash/mining?

But I would focus on #8, valuation.  A floating currency is set by the market environment, not individual consumers on a per contract basis.  How can Bob set a realistic price for your ChemiCoin(TM)? Especially as they're not underwritten by tangible assets.  I think that I'd mow your lawn for 100 ChemiCoin(TM). But if no one else values them similarly, I've effectively consumed my resources for no reward.  That's bad capitalism and realisation would be neigh on impossible.

#8, part 2. How can Alice validate execution of the contract if the other party is not reciprocating with ChemiCoin(TM) transactions on the ledger?  Did I really mow your lawn?

And on #13.  What use treasure if it can't be spent? At least the Pharaohs could spend their accumulated gold and jewels in the Underworld.  The more ChemiCoin(TM) I possess, the more I want to spend them. But they depreciate accordingly.  So why amass them in the first place?  I may be getting poorer the richer I get, and don't mean  morally.

It all seems very tricky mathematically and economically, with a highly divisive set of cryptographic ideas.


Output of a Linear Shift Register given Plaintext and intial state

Read the drawing assuming:

each of the four (about) square boxes $a_j$ initially (at $t=0$) holds one of the four  bits of $S_0$ (in reading order, unless otherwise stated);
information follows arrows (almost) instantly, except when getting into a square box where that is delayed until $t$ has grown by $1$ (in time unit or clock period); notice this implies that the content of the left square box is also (with negligible delay) on the arrowhead going straight down and the one going right-down;
there are three implicit short arrows between the four square boxes, oriented as the rightmost arrowhead;
each $\oplus$ symbol performs the exclusive-OR of all the ingoing arrows, and outputs that result to outgoing arrow, with no significant delay;
the plaintext bits are made available one by one (starting at $t=0$, and in reading order, unless otherwise stated) on the input side of the arrow marked "plaintext";
the ciphertext bits are what's at the arrowhead marked "Cipher-text" (with the same convention as for plaintext).

You can now manually compute what there is in each of the boxes, arrowheads, "plaintext", "Cipher-text", at any integer value of $t\ge0$ (or, more precisely, shortly after). Assuming increasing time matches reading order, you might want to format this as a table with $t$ increasing from left to right, so that the lines with "plaintext" and "Cipher-text" will contain the plaintext and ciphertext in reading order.


Find private key from knowing random exponents are an arithmetic series

We don't know if $s_1r_2−s_2r_1$ is coprime to $p−1$ so we can't immediately get $u$, but is it true that it would be coprime?

I don't believe coprimality is guarranteed, however we don't need it.

If they're not coprime, it means that there are multiple solutions to the linear equations we have; however:

The number of solutions are likely to be small; bounded by $\text{gcm}( s_1r_2−s_2r_1, p-1)$
We can list all those solutions efficiently

So, what we do is go through the list of possible $u, k$ solutions, plug each one into the $r_1 = g^k \pmod p$ relation, and see which one satisfies it; our work is done.


Relation between attack and attack model for signatures

I hope I got your point and try to answer your question. Actually, if I understand you right, then what you call an attack actually means an adversary acting in a specific attack model.

To clarify this, we need to review the security models for digital signature schemes and when we have discussed this we can clarify issues. Basically, we have to discuss what an adversary tries to achieve and which environment is given to him.

Goal of an adversary:

We start by discussing the goals of an adversary beginning with the strongest and ending up with the weakest attack goal.

Total break: The adversary is able to obtain the secret signing key. Thus, he is then able to impersonate the signer by signing arbitrary messages in the name of the signer.
Selective forgery: The adversary is able to produce valid signatures for some selected messages or a particular class of messages.
(Weak) Existential forgery: The adversary is able to produce at least one valid signature for a message, for which he has not been given a signature yet (the adversary typically has no control over the choice of this forged message).
Strong existential forgery: The adversary is able to produce a valid signature different from any signature he has seen. In contrast to weak existential unforgeability, the message corresponding to the forged signature may already have been signed. Think of a second valid signature for a message that has already been signed (signatures that are publicly re-randomizable - such as Camenisch Lysyanskaya signatures - can never achieve this level).

Power of an adversary:

After defining the goals, we will take a closer look at the adversary and define his ability or power. This basically defines the environment he is acting in. Thereby, we start with the weakest and end up with the strongest one.

Key-only attack: The adversary solely knows the public-key corresponding to the secret signing key of the signer.
Known-message attack: The adversary has additionally access to a list of message-signature pairs from the signer, whereas he has no influence on the choice of the messages.
Random-message attack: The adversary can obtain signatures for message, whereas the adversary has no control how the messages are chosen (they are randomly chosen by the signer).
Chosen-message attack: The adversary has access to a list of message-signature pairs, whereas the messages were chosen by the adversary before attempting to break the signature scheme.
Adaptively chosen-message attack: The adversary is able to adaptively choose the messages which are signed by the signer during the attack. Thus, he may choose messages depending on the public-key of the signer and also previous messages or signatures, which were obtained during the attack. In other words, the adversary can use the signer as a signing black-box (oracle) throughout the entire attack.

Security as a combination of goals and power:

Now, the combination of the goal and the power of an adversary gives the type of security of a specific scheme. In general, a digital signature scheme is said to be secure if the most powerful adversary cannot even achieve the weakest goal.

Secure Signatures:

In the notation introduced above, a digital signature scheme is considered secure if it is existentially unforgeable under adaptively chosen-message attacks. Typically, here, existentially unforgeable refers to weak existential unforgeability (but there are also some signature schemes whose security is proved with respect to strong existential unforgeability).

Coming back to your question:

Actually, what you describe as an attack, is a total break under a key-only attack. Or you may see it as an adversary mounting an attack (key-only) with this goal (total break).


Why is verification using DSA slower than verification with RSA?

If you compare DSA with SHA-256 and a 2048 bit group modulus $p$, to RSA with SHA-256, a 2048 bit modulus $n$ and public exponent $e = 65537$, on you will at least perform the following operations:

DSA

$g^{u_1}y^{u_2}$ - 2*256 squares $\mod p$, up to on average 2*128 multiplications $\mod p$, depending on implementation optimizations.

RSA

$s^e$ - 16 squares $\mod n$, 1 multiplication $\mod n$.


How to generate a good symmetric secret key

A "good" secret key should have the same probability as any other possible key to be chosen.

No matter what extractor you will be using, if your entropy source is limited to the current timestamp, this is very unlikely to be the case.

Unless you have access to a hardware random number generator, you should combine as many independent entropy sources as possible.

As to the actual entropy collection, answering your question is impossible without knowing what your environment is.


How do people know decryption is successful?

It depends on the encryption scheme if the correctness of the result is verified or not.

For instance, the output of an asymmetric scheme such as raw RSA decryption (just modular exponentiation) is just a number; you cannot directly distinguish between a correct and incorrect answer.

However a secure padding scheme such as OAEP then a possible output of OAEP can be "decoding error". Decoding error shows that something went wrong when removing the padding, which would happen if the resulting (padded) plaintext message contains is not encoded correctly. And that situation would arise (with high certainty) if either the ciphertext or the private key was incorrect.

The same goes for symmetric decryption. Decryption with AES-CTR always succeeds, the result is just a bit string. AES-GCM is however an authenticated cipher and will result in an error if the key is incorrect.

There are schemes in which the result does sometimes result in an error and sometimes it doesn't. A perfect example of this is AES in CBC mode with PKCS#7 padding and PKCS#1 v1.5 padding for RSA encryption. In that case the scheme sometimes results in an error and sometimes it doesn't. This leaks information about the plaintext which can be exploited by a padding oracle attack.

If your scheme doesn't return an error (with high certainty) then you can protect it with a signature (for asymmetric crypto) or MAC (for symmetric crypto). Usually sign-then-encrypt is used for asymmetric crypto and encrypt-then-MAC for symmetric crypto.

As an attacker you can use any information about the (padded) plaintext to see if the result is (partially) correct. This could include information about padding, formats of data structures (and therefore files), frequency analyzes of text etc. etc. etc.

An attacker may also use errors returned from the decrypting party to obtain information. This is called a plaintext oracle attack (a padding oracle attack is usually seen as a specific plaintext oracle attack).

Notes:

an error is often indicated as $\bot$ in scientific papers on cryptography (falsum)


Real-world offline phase implementation in MPC setting

I don't think there are some guidelines as such. However, different approaches have been considered.
A common consideration across several implementations that aim at making these things more accessible in practice (e.g. TF-Encrypted, or PySyft) is to consider a third trusted party that distributes the necessary preprocessing material before the computation starts. This, however, introduces different security assumptions and generates new potential points of failure.
Another approach that has been suggested in the literature consists of letting a set of servers produce triples "as a service" towards the servers requiring the computation. This would reduce the single point of failure that an individual preprocessing producer would imply.
This is all, however, research literature. I am not aware of any actual deployment of protocols with heavy preprocessing, nor any guidelines about how to do so. Also, there is an argument that this idea of the preprocessing not "mattering" so much, due to it being input-independent, is not that valid in practice. For actively secure 2-party protocols, the preprocessing can really take a large amount of time with respect to the online phase, so in a real scenario in which you get a constant flow of computation requests, it is more accurate to count end-to-end running times.
Finally, heavy preprocessing times are common in the dishonest majority setting, but when you're willing to assume that the adversary corrupts at most a strict minority of the parties, we can find protocols with very cheap preprocessing, or even no preprocessing at all. This is common in the $3$-party setting (with $1$ corruption), so I'd expect a real deployment in practice to make use of one of these settings, instead of, say, $2$ parties.


Is there some way to generate a non-predictable random number in a decentralised network?

The classic way to do this is to have all parties commit to individual random values by publishing a secure hash of a suitably random-nonce-padded number. Once the commitments have been distributed, the parties open the commitments by publishing the nonce and the number. The numbers are combined in some previously agreed suitable fashion such as adding them modulo some number or xoring them together. As long as your value was included then you are confident that the result is random. If the numbers used are large enough, the nonce is not required.


Testing hardware random number generators?

NIST has a lot of information on testing random number generators at http://csrc.nist.gov/groups/ST/toolkit/rng/index.html that might be of value to you.


Secure blinding factor switching at malicious server-side (Switching in One Time pad)

I'll answer question 2, leaving the first as an exercise to the reader. I'll do this on intuitive grounds, rather than using explicit conditional probabilities.

The adversary is free to compute $v_1\cdot v_2$ regardless of what we ask, therefore removing everything about that and $v_3$ does not change the problem, which reduces to:

  We somewhat have chosen some $a\in\mathbb F_p$. We draw a random uniform secret $z_1\in\mathbb F_p^*$ (so that it's inverse ${z_1}^{-1}$ is well-defined) and a random uniform secret $z_2\in\mathbb F_p$, and compute and reveal $v_1=a\cdot z_1$ and $v_2={z_1}^{-1}\cdot z_2$ to the adversary; what does that reveal about $a$?

Lemma 1: for unknown $u\in\mathbb F_p^*$, drawing a random uniform secret $z\in\mathbb F_p$, and revealing $v=u\cdot z$, reveals nothing about $u$.

Lemma 2: for unknown $u\in\mathbb F_p^*$, drawing a random uniform secret $z\in\mathbb F_p^*$, and revealing $v=u\cdot z$, reveals nothing about $u$.

Proof follows from the fact that $z\to u\cdot z$ is a mapping over $\mathbb F_p$ (for lemma 1) or over $\mathbb F_p^*$ (for lemma 2).

Notice that neither $v_2$ nor $z_2$ are involved when we compute and reveal $v_1=a\cdot z_1$. Therefore, we can consider in isolation the part of the protocol where we draw a random uniform secret $z_2\in\mathbb F_p$ and reveal $v_2={z_1}^{-1}\cdot z_2$. We apply lemma 1 with $u={z_1}^{-1}$ (which belongs to $\mathbb F_p^*$), and conclude that revealing $v_2$ reveals nothing about ${z_1}^{-1}$, hence nothing about $z_1$.

Thus the part of the protocol where we compute and reveal $v_2={z_1}^{-1}\cdot z_2$ has revealed nothing about any quantity in the part of the protocol where we compute and reveal $v_1=a\cdot z_1$. If our choice of $a$ was not zero, by lemma 2, that part of the protocol has revealed nothing about $a$. If our choice of $a$ was $0$, $v_1$ will be $0$.

Hence the answer to question 2 is: the protocol reveals precisely whether $a=0$ or not. No other information about $a$ leaks.

With the statement disallowing $z_1=0$ (or if we reject that as having vanishing odds since $p$ is large), it can be shown that no (or vanishingly few) information about $z_1$ in isolation leaks, and that the only (or almost the only) information that leaks about $z_2$ in isolation is whether $z_2=0$ hold.


What does (06) in "CRL Signing (06)" mean?

The Key Usage field is represented as a bit string, where each bit represents one of the options, so that multiple options can be set. The value 6 it's just the constant of the bit position that identifies "CRL Signing". From RFC 5280:

KeyUsage ::= BIT STRING {
     digitalSignature        (0),
     nonRepudiation          (1),  -- recent editions of X.509 have
                                -- renamed this bit to contentCommitment
     keyEncipherment         (2),
     dataEncipherment        (3),
     keyAgreement            (4),
     keyCertSign             (5),
     cRLSign                 (6),
     encipherOnly            (7),
     decipherOnly            (8) }


Questions about updating the secret key of RSA?

if the adversary knows $m^{e_1}$, $m^{e_2}$ and $d_1e_2$, is it able to guess m?

Obviously not; if he could, then they could break RSA.

Here's the RSA problem, given $m^e$, $e$ (and the modulus $N$), recover $m$.

Suppose that we can solve your problem, that is, we had a black box that, given $m^{e_1}$, $m^{e_2}$ and $d_1e_2$, could recover $m$.

Then, given the RSA problem parameters $m^e$ and $e$, we would pick a value $\lambda$ which is relatively prime to $\phi(N)$ (and this can be done simply by picking $\lambda$ prime), and compute $(m^e)^\lambda$.  If we assume $e_1 = e$ and $e_2 = e \cdot \lambda \pmod{\phi(N)}$, we then have $e_2 \cdot d_1 = \lambda \pmod{\phi(N)}$ (as $d_1 = e_1^{-1}$)

We then have $m^{e_1} = m^e$, $m^{e_2} = (m^e)^\lambda$ and $d_1e_2 = \lambda$, we then give these parameters to the black box, and recover $m$, solving the RSA problem.

On the other hand, this argument assumes that (at least) $e_2$ is large (because the above procedure effectively selects a random $e_2$).  If you selected $e_1$, $e_2$ small (say, 16 bits or so), then what the attacker could do is go through the possible $e_1, e_2$ combinations, and recover a billion possible $m$ values, one of which is correct.

  Is the key-update is resistant against leaking old secret keys? If the adversary knows $m^{e_2}, d_1e_2$ and $(e_1,d_1)$, is it able to guess $m$?

No, the key-update is not resistant; the adversary can recover $m$. The values $e_1$, $d_1$ are sufficient to allow him to factor $N$ efficiently, with the knowledge of $d_1e_2$ and $d_1$ and $\phi(N)$, he can recover $e_2$, and with that and $m^{e_2}$ (and again, the factorization of $N$), he can recover $m$.


Clarification of Proof: Proving perfect secrecy for One Time Pads

As you have shown, the number of keys such that $E(k,m)=c$ for given $m$ and $c$ is $1$. So the probability

$$Pr[E(k, m) = c] = \frac{1}{number\,of\,keys}$$

with $k$ chosen randomly from $K$ is the same for any plain text and any cipher text, so

$$Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]$$

for all $c \in C$ and $m_0, m_1 \in M$ with $|m_0| = |m_1|$, and thus by definition the OTP has perfect secrecy.


Is it possible to use the RSA algorithm, or a variant, for software licensing?

The answer to the question in the title is: Yes, it is possible to use RSA signature for software licensing (e.g. in the context either RSASSA-PKCS1-V1_5 or RSASSA-PSS in PKCS#1 as defined here, or any of the three schemes in ISO/IEC 9796-2 free but partial preview). One minor issue is that, for a decent security level, what protects the license file will be much too big to be keyed in.

There are a lot of terminology errors in the body of the question:

What's wanted is distribute a crypted encrypted signed license file to many customers
What's needed is use the RSA public private key to encrypt sign that license file; in signature schemes with message recovery (e.g. ISO/IEC 9796-2) this will have the (perhaps desirable) side effect of making at least some of the signed content not directly intelligible, though recoverable without any secret information;
The software that will be licensed to customers will have inside the private public key in order to be able to decrypt verify the license content (and recover what portion of the signed information was not directly intelligible, if applicable)
The question is if it can be possible to know obtain the public private key giving given the encrypted signed file, the private public key and the final plain text signed data.

The short answer to that other question is: No, there is not a reason to worry that the private key (or anything allowing to generate new signed license files) could be obtained, provided the legitimate private key is kept and used securely, and was adequately drawn.

You'll get one private key to sign (and perhaps, with message recovery, make not directly intelligible some or all of) the data forming the license file, and an associated public key to verify the integrity (and perhaps, with message recovery, recover all) of that data; and where it will not be possible to obtain the private key (or some equivalent mean) given the public key and the data in any of its form.

On the other hand, no amount of cryptography will really prevent that someone skilled modify the software to bypass the license check, or allow the use of a license duplicated from an authorized one even if the software attempts to lock a license to a particular computer. Without temper-resistant hardware, the best you could do is that some portion of the software is unusable without access, at least temporarily, to a valid license to use that portion of the software.


Is it possible to derive an asymmetric algorithm from a symmetric one?

Besides the hash based signature constructions mentioned by @CodesInChaos in the comments, it is entirely possible to build an asymmetric cryptosystem from a secret key one. Granted, the secret key ciphers in question are not typical, such as AES, but ones that support homomorphic operations on ciphertexts.

Homomorphic Encryption

A cipher supports a homomorphic operation on ciphertexts if $D(E(m1) * E(m2)) \equiv m1 * m2$, where $*$ is some operation such as addition or multiplication.

Note that the operation performed on the ciphertexts does not necessarily have to be the "plaintext" operation: For example, the Paillier cryptosystem utilizes multiplication on ciphertexts to compute the addition of plaintexts.

Additionally, some such ciphers also offer the following property: $D(E(m1) + m2) \equiv m1 + m2$.

These properties can be used to create public key encryption systems.

An example

One example is provided in Fully Homomorphic Encryption Over The Integers:

A public key consists of many secret-key encryptions of 0
Random elements of the public key are summed together to form a ciphertext, and the message is added to the ciphertext

$ciphertext := pb_{r_0} + pb_{r1} + pb_{r2} + ... + pb_{rn} + m$

Decryption applies the decryption operation of the secret key cipher to obtain the plaintext message

In the above example, inverting a public key ciphertext without the private key is equivalent to solving a subset sum problem.

Acquiring the private key from the public key requires analyzing the secret key cipher that is used to instantiate the scheme. In the above design, they base the hardness of their secret key cipher on the Approximate Greatest Common Divisor problem.

However, you can instantiate such a scheme with any cipher that can perform the specified operations.

Now, the security of the constructed schemes is another question. But the mechanisms can be constructed. Additionally, many such schemes are not nearly as efficient as they would need to be in order to be utilized in practice: The ciphertexts and public keys can get huge.

More examples

Merkle's original knapsack cryptosystem can be deconstructed similarly.
Aside from encryptions of 0, you can also release encryptions of $1, 2, 3, ... N$ and sum elements randomly, with a final adjustment to set the message equal to your plaintext. (This requires a modular reduction step in order to function)
Or, there is another encoding still: release encryptions of powers of 2, as well as some 0s. Then, sum together some 0s randomly, then combine appropriate powers-of-2 such that the plaintext equivalent is equal to the message. (Powers of 2 are weight-1 words; They consist of a single set bit)
The last scheme that I know of is to release some encryptions of 0. Then, to encrypt, multiply each element of the public key by a large random (plaintext) integer, sum the results, then add the message to the ciphertext. This one seems to offer the prospect of smaller public keys then the alternatives.

$pb_0 r_0 + pb_1 r_1 + pb_2 r_2 + ... + m$

I have yet to encounter such a scheme that is built using multiplication as the homomorphic operation; All of the above require only addition. By that I do not mean such schemes do not exist, I just don't know of any.

(Note: multiplication by plaintext is supported when ciphertexts support addition: $E(m) + E(m) \equiv E(m) * 2$

Why doesn't AES work with any of these?

"Normal" symmetric primitives are designed to destroy any semblance of structure. It's just a lot easier and faster to drown the information in impossibly complicated equations then it is to formulate something simple enough to provide the required properties while still providing security. Since the constructions need to be simple, it usually means the numbers need to be big, and this comes with a cost.


List of post quantum cryptography protocols

First, a pedantic point: be careful with terminology: there currently are no Post-Quantum "protocols" (TLS, S/MIME, CMP, etc). From your question, I'm assuming you are interested in PQ "schemes", or PQ "primitives" (XMSS, R-LWE, etc). This may seem like nit-picking, but we can expect NIST to standardize primitives in the next 3 - 5 years, protocols will take longer than that!

Now for your actual question. As @SEJPM points out, the research is still very young and is rapidly changing, so any links to actual schemes will very quickly go out of date. What I will do instead is link to the organizations that you should be following.

NIST

Link to their talk from the recent PQCrypto2016 conference outlining their upcoming call for applications for candidate PQ signature and encryption schemes.
See their February 2016 report, basically a "What we know at this point".
pqc-forum@nist.gov is the mail-list for discussion of post-quantum schemes and their standardization. This went live very recently so I can't find any references to it online, but you can get yourself onto it by sending an empty email to pqc-forum-request@nist.gov with subject:subscribe

NSA

See their Suite B page (at time of writing, it was last updated in August 2015).
See their January 2016 announcement of the replacement of Suite B.

PQCrypto Project

Group funded by the European Union to research and recommend PQ schemes.
pqcrypto.eu.org

IETF / IRTF's Crypto Forum Research Group (CFRG)

Draft standard for XMSS hash-based signatures.
irtf.org/cfrg


two public keys with same passphrase insecure? | can two hashes be compared?

No.

The passphrase you use creates a symmetric key that is used to encrypt the private key. You're not uploading the private key to the server, at least let's hope you aren't.

But even if you are doing that, the password is salted and iterated in hashing, and that means that the visible encrypted private key is radically different even if the password is the same, because the same password produces two different symmetric keys.


Encrypt your ECDSA signature with NTRU to make them quantum secure, does that work?

So you want to encrypt the message's ECDSA signature with NTRU.

Firstly, if the NTRU is secure against the quantum computers, then anything under NTRU encryption is secure against the quantum computers.

Secondly, NTRU has also digital signature, instead of ECDSA use NTRUSign.

Depending on different mathematical and computational problems are not considered a good practice.

update: by the comments of Maarten Bodewes

Remember that, public key encryption and signature require two separate keys; public key and private key. In your case;

the public encryption keys generated by the receiver as $PK_{rec},SK_{rec}$
the digital signature keys are generated by the signer as $PK_{sign},PK_{sign}$.

As a result, the two public keys, $PK_{rec}$ and $PK_{sign}$, are generated by different people.


Please prove distinguishability given a non-perfectly secure cipher

The proof in the question is not about the perfect secrecy $\implies$ indistinguishability. It is about proving that; if perfect secrecy than we have $$ Pr[C=c| M=m] = Pr[C=c]$$ Also, we don't need the $\wedge$ step, just use Bayes' Theorem directly. The reverse (1) of this also true that is if we have $$ Pr[C=c| M=m] = Pr[C=c]$$ that we have perfect secrecy.

Now assuming that we have indistinguishability. That is; for every probability distribution over the message space $\mathcal{M}$ and every $m_0,m_1 \in \mathcal{M}$, and for every $c \in \mathcal{C}$;

$$Pr[C=c| M=m_0] = Pr[C=c | M=m_1] $$ we will show that we have prefect secrecy.

Since, the equation holds for ever $m_0,m_1$ we can say $Pr[C=c| M=m_0] = Pr[C=c | M=m_1] = p$ (2).

Now, write $Pr[C=c]$ as;

\begin{align}
Pr[C=c] & = \sum_{m\in\mathcal{M}} Pr[C=c | M=m] \cdot Pr[M=m] \\
 & = \sum_{m\in\mathcal{M}} p \cdot  Pr[M=m] \\
 & = p \sum_{m\in\mathcal{M}} Pr[M=m] \quad\quad\quad\quad \\
 & = p \\
 & = Pr[C=c| M = m_0]  \quad\quad\quad\quad\quad\quad//(\text{use }2)
\end{align}
we have;

$Pr[C=c] = Pr[C=c| M = m_0]$ ,

now use (2);

$$Pr[M=m | C=c] = Pr[M = m_0]$$ therefore, indistinguishability $\implies$ perfect cipher


Determining if at least 1 bit is set in the output of SHA256

No, the output of the hash is indistinguishable from random. If there was a shortcut to determine the value of an output bit given a certain input (other than executing the hash) then the hash would be broken.


Password as it relates to various encryption schemes

If the password is salted and is long enough to begin with, then yes, using the same password should be fine. (Though a bit riskier than using different passwords --- say, if you have one password stolen by e.g. a keylogger)

The reason for the recommendation "don't reuse passwords" is that it's often hard (or sometimes impossible) to know if the underlying software is properly using salts.


Elliptic curves in Edwards form (or Edwards curve) and addition formulas

I think this is a good question, but not one with an easy answer. Let me give it a go anyway.

First of all, let's focus on the classic Weierstrass case. The points on an elliptic curve $E$ in this shape form a group. We can do this by the standard way (in most cases): draw a line between two points $P$ and $Q$, intersect at a unique third point, and invert across the $x$-axis. The resulting point $R$ is defined to be $P+Q$. Many standard texts indeed provide proofs that the points with this operation form a group.

Now, as you may have noticed, this way of defining the group depends very much on the way we represent the elliptic curve. That is, it assumes that we write $E$ as the set of solutions to $y^2=x^3+ax+b$. Can we also define the group law without making this assumption? The answer is yes.

How to do this, is quite complicated. Think of an elliptic curve $E$ as a very abstract object, not even assuming how to represent its points. It can be shown, that there exist some group attached to $E$, which is the degree-0 group of something called the Picard group. We denote it by $\operatorname{Pic}^0(E)$. Even more, it can be shown that there is a bijection between the points of $E$ and elements of $\operatorname{Pic}^0(E)$. Because $\operatorname{Pic}^0(E)$ is a group, so are the points on $E$.

So, we know that the points on $E$ form a group. How do we compute it? Well, it depends on how we represent points on $E$. If we choose to write points as $(x,y)$, where $y^2=x^3+ax+b$, then it is the classical way. If we choose to write points on $E$ as $(u,v)$ where $u^2+v^2=1+du^2v^2$, then it is done in the way you described.

TLDR How do we prove that your $x_3$ and $y_3$ are correct? As above, we need to prove that they correspond to a point on $E$ such that it corresponds exactly to the group law defined by $\operatorname{Pic}^0(E)$. For this specific case, your best bet is the original paper or the cryptographic application paper. In particular I would look at section 3 of the latter paper.


Any good links to learn the maths behind AES?

I think Lenstra's short document Rijndael for Algebraists is fantastic to get started on the maths behind AES:

https://math.berkeley.edu/~hwl/papers/rijndael0.pdf

You can find some information on finite fields on Wikipedia have a look at the example of $GF(4)$.

For a detailed overview of the cipher see the book  The Design of Rijndael:The AES Standard by its designers.

There is also The Stick Figure Guide to AES, at a more informal and descriptive level.


The few cipher suites you mention don't have PFS since they all use RSA as key exchange. Only the ECDHE ciphers from the list have PFS since they use ECDH as key exchange.


Multiple rounds of (Committed) Oblivious Transfer

The most straightward approach is to have Bob select two random symmetric keys $k_0$ and $k_1$ and have Bob publish $Encrypt_{k_0}( x_0^i )$ and $Encrypt_{k_1}( x_1^i)$.

Then, Bob does an OT with Alice, allowing Alice to select between $k_0$ or $k_1$.

She learns $k_b$, and then is able to decrypt all the $Encrypt_{k_b}( x_b^i )$ values, resulting in her learning $x_b^1, x_b^2, …, x_b^n$

Because she learns only one of $k_0, k_1$, the value she learns all come from the same half.


Secret sharing scheme with ability to add or update share number

With Shamir's Secret Sharing you can add as many shares as you want, as long as the threshold and the secret is unchanged.

You can see that neither the generation of the polynomial that produces the shares nor the reconstruction of the secret by polynomial interpolation require the parameter $N$ (number of shares), but only the threshold $k$.

Of course the number of shares $N$ should obey $N\leq p-1,$ since they need to be obtained as polynomial values at distinct points of the field $F_p$ and one point, usually zero, is reserved for the secret. You can increase $p$ if needed, but shares need to then be recomputed modulo the new prime you choose.


You said in the comments, that $H$ can be a random oracle, but in this case it needs to be a random oracle. Basically your protocol is a Schnorr protocol in disguise, and you throw in the Fiat Shamir heuristic to make it noninteractive.

But considering your questions:

Well, the basic Schnorr protocol is not zero-knowledge. There exists no simulator for this, because the simulator can't (more or less) reliably pick the correct commited value. If you choose $\rho$ as single bit, you might end up with a ZK protocol, which you then can turn into NIZK with the Fiat Shamir heuristic, like D.W. suggested in the comments.
Well, actually there is no $s$ in your protocol. You never use $s$ alone. You don't let anyone know $g^s$. All you use is the product "$st_i$", which is from the verifier's point of view a single value. And since it has the index $i$, it will change from round to round. And no, you can't prove that to get to that value you used some common $s$, if you don't give out any information about $s$ alone (e.g. $g^s$).


Let's first get rid over two parameters that only have one option: the Mask Generation Function (MGF) and the trailer field. These can only be configured to MGF1 and 1 respectively in RFC 3447 which specifies RSA-PSS.

You won't find a generic standard that chooses one hash over the other for MGF1 because any hash will be considered secure, including the default (SHA-1). On the other hand, there will be many higher level protocols or applications that will have chosen one specific set of configuration parameters.

If we take a look at RFC 4055 where the PSS is used for X.509v3 certificates (the ones you will find used for TLS in e.g. your browser) we'll find that the configuration options can be indicated for a specific public key within a certificate:

RSASSA-PSS-params  ::=  SEQUENCE  {
     hashAlgorithm      [0] HashAlgorithm DEFAULT
                               sha1Identifier,
     maskGenAlgorithm   [1] MaskGenAlgorithm DEFAULT
                               mgf1SHA1Identifier,
     saltLength         [2] INTEGER DEFAULT 20,
     trailerField       [3] INTEGER DEFAULT 1  }

As you can see, all values have their default, so this would be an easy set of rules to comply with. Within certificates the public key and its parameters are signed, so the security of the parameters should be guaranteed.

However, there is one additional detail:

  The maskGenAlgorithm field identifies the mask generation
           function.  The default mask generation function is MGF1 with
           SHA-1.  For MGF1, it is strongly RECOMMENDED that the
           underlying hash function be the same as the one identified by
           hashAlgorithm.

Of course that would mean changing the default by specifying the MaskGenAlgorithm and mgf1SHA1Identifier for field [1]: maskGenAlgorithm. As SHA-1 is considered broken and therefore not an option for hashAlgorithm, that means that another hash algorithm should be chosen.

As all other parameters are set, that means the hash function becomes the only configuration parameter.

Now as SHA-2 is in common use is it probably the best family of hash algorithms to choose from. SHA-224 and SHA-384 are simply shorter output functions of SHA-256 and SHA-512 and they don't make much sense for signatures. So that leaves the choice of one of the two. SHA-256 is used most and has hardware support on many chips. SHA-512 is using 64 bit operations and is both fast and secure on 64 bit chips.

For compatibility reasons and the hardware support I'd probably slightly favor SHA-256. It still has plenty of security and hashes data at over twice the speed using hardware support.

So there we are: SHA-256, MGF-1 with SHA-256, 20 byte salt and a trailer field set to 1. Just communicate this with your friend by explicitly describing it in your protocol and you're all set when it comes to PSS.

That just takes care of the PSS parameters. You'd also want to specify how you're going to trust the public key (oh dear, did I mention X.509 certificates?), and what (minimum) key size to use. Any key size of 3072 bits or over is OK, but I'd stick to 3072 bits which has the same security level as SHA-256's collision resistance at ~128 bits of security.


Decoding Base64 message encoded with a key. I only know the ciphertext and code

I have briefly looked at the code. It is not well readable, but it looks like it is Vigenère cipher. It seems to operate on Unicode values of the characters, but it probably does not expect the Unicode value to be over 255 or lower than 16, so it can have troubles with some unicode characters. Finally, it is encoded to base64 in order to produce ASCII characters.

So, you can use known cryptanalysis for Vigenère cipher. There are probably also some tools, but you will likely need to adjust the input.


The title of your question is wondering why you often see $a = 1$ in the form of the elliptic curve you specified. I would first check the top answer (Thomas Pornin's) to this question.

This form of the curve is called non-supersingular. If $b=1$ and $a \in \{0,1\}$, it's called a Koblitz curve or anomalous binary curve.

The short, quick answer is: if your curve is of the form you specified over $\mathbb{F}_2$, with $a = 0$ or $a = 1$, and $b=1$, it allows you to use the Frobenius endomorphism $\tau: \mathbb{F}_{2^m} \rightarrow \mathbb{F}_{2^m}, \alpha \mapsto \alpha^2$ to very quickly calculate $2P$ for a point $P$; you just square coordinates instead of having to use the usual doubling or addition formula. This is much more efficient than the usual method of doubling.

For a point in $\mathbb{F}_{2^m}$, $\tau$ satisfies $2 = \mu \tau - \tau^2$, where $\mu = (-1)^{1-a}$. So if you want to compute $nP$, with $P \in \mathbb{F}_{2^m}$, first write $n$ as a sum of powers of $\tau$ and then apply those terms to your point $P$: $\tau(P) = (\tau(x), \tau(y))$.

I'm not sure if this is the mapping you're looking for, but you can see you get a lot of mileage out of  $a \in \{0,1\}$ on an elliptic curve over $\mathbb{F}_{2^m}$!


FIPS 140-2 compliance across symmetric and asymmetric primitives

Start with Annex A: Approved Security Functions.  That will give you a good idea of the approved functions.  A few caveats:

Not all modules support all approved functions, e.g. OpenSSL doesn't support quite a few of them (OpenSSL's validation isn't active anymore anyway)
FIPS 140 is a constantly evolving target, so today's validated module is tomorrow's no longer validated module.  For instance, the reason OpenSSL's validation is no longer active is because FIPS 140 changed to disallow the generation of RSA keys with 1024 bits and signatures that used 1024 bit keys, though it still allows signature verification with 1024 bit keys.
Just because an algorithm is FIPS 140 approved doesn't mean customers will accept it.
Both 3DES and SHA1 are still FIPS approved algorithms, but customers will complain about the use of either (both have been deprecated by NIST).


Can a digital money system exist, that's secure, anonymous and allows offline transactions?

Depends on what you mean by secure. If you merely want the ability to detect and then presumably punish double spending, you can do that in a way that is secure and anonymous: double spending reveals enough information to provably identify the user. Since honest users don't double spend, they are still anonymous. This is used in Camenisch et al.'s Compact E-cash paper
These systems use techniques related to blind signatures and and similar to anonymous credentials ---e.g. signatures over committed values and zero knowledge proofs about those signatures --- which make it impossible to link the issue of a unit of currency to its spending or the spending of another unit of currency unless it is double spent. As a result, unlike bitcoin, they really are completely anonymous if the cryptographic assumptions hold.
If you mean prevent double spending. No, it's impossible without trusted hardware*. You run up against, among other things, the cap theorem. What stops me from making a clone of my data and executing the same protocol on other ends of the world ( or the galaxy)?
*
As others have pointed out, it might be possible in the quantum setting. Certainly you can make non-cloneable quantum "objects", but its unclear how you would transfer them.  (update) in fact you can potentially do it with quantum knots3


blockcipher-based MACs with variable length that are UF-CMA secure?

Are there any other blockcipher-based (blockcipher and hash combined included) MACs that is UF-CMA secure with variable length messages?

Sure.
The most famous one is probably CMAC (a.k.a. OMAC1) which is essentially CBC-MAC but with a key-dependent secret random value XOR'ed with the last message block1.
Alternatively there is a general theorem that $F_k(H_\kappa(m))$ is a PRF (and thus a secure MAC) as long as $F$ is a secure fixed-length PRF and $H$ is a collision-resistant (potentially-keyed) hash function. You can find a proof of this e.g. in the Boneh-Shoup book (section 7). This e.g. brings the (parts of) the security proofs for HMAC and PMAC. Additionally you can somewhat easily define MACs based on this, e.g. $\operatorname{AES}_{k_1}(\operatorname{GHASH}_{k_2}(m\|\operatorname{len}(m)))$.

1: This is an accurate enough simplification of CMAC. It actually uses more than one such random value for messages that are not a multiple of the block length


Boolean XOR function a valid way to verify the integrity of a message

It really depends how you use it.

Per se the XOR operation is not a good way to perform any kind of integrity check because it is very easy to "cancel" a change by doing another change equal to the XOR with the value you want to obtain.

A lot of integrity checks are relying on the XOR operation under the hood to "combine" blocks together, but not without performing further operations on the said blocks.

For instance the CRC-32 algorithm, an error-detecting code is working as follows (pseudo code from Wikipedia):

Function CRC32
   Input:
      data:  Bytes
   Output:
      crc32: UInt32

crc32 ← 0xFFFFFFFF

for each byte in data do
   nLookupIndex ← (crc32 xor byte) and 0xFF;
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] //CRCTable is an array of constants

crc32 ← crc32 xor 0xFFFFFFFF
return crc32

CRC-32 and the way it uses XOR is good to detect errors in a communication channel, but it is not good to provide an integrity check that would resist intentional, malicious alteration of data.

To resist such cases, you have to use cryptographic schemes, such as the ones discussed in that question. Also notice that hash function do not provide integrity, unlike MAC functions, hash-functions are only about collision resistance, pre-image resistance and second pre-image resistance.


Montgomery Ladder with affin/projective Coordinates

Maybe one day someone finds this Post again and has the same questions. To you: I hope you're having a great day!

Questions: The projective Arithmetic is faster, because there are only multiplications, squarings, additions to do. The affine Artihmetic is slower, because it takes a lot of time to compute the division. Especially for the big numbers used in modern cryptographie. BUT: That is not the answer to the constant time ladder. Yes affin coordinates with division can't be computed with constant time, but the reason for the projective ladder is a different. You can tranform different types of elliptic curve into the projective form, but for them you can't always use the montgomery ladder. For a long time ( at least when montgomery published his work ) elliptic curve scalar multiplikation on weierstraß was only possible with double and add algorithms. Those algorithms tranformed the scalar into the binary form and had different operations for 1 and 0. Therefor one could approximate how many 1 and 0 there are. The Montgomery ladder has the same operations for both. So there is no difference in time.
Question: With projective coordinates it is only possible to add/double multiples of the same point. The montgomery ladder starts with a given scalar $n$ and Point $P$. In each step two results are calculates $R0$ and $R1$. The important point here is, that those results are either of the form $(n')R0$, $(n'+1)R1$ or $(n'+1)R0$, $(n')R1$. That means the difference between them is always 1. (When you look at the definition for the projective Arithmetic it is clear what that means). For the ladder this means, that $x1$ is always the x coordinate of the starting Point $P$. Therefore it is always the same and must not be computed!

Note: I still can't say, whether my pseudocode is correct or not.


Is it possible to recover AES-GCM plaintext when having everything but the additional data?

GCM is an authenticated wrapper around CTR mode. The authenticated data is only considered when verifing the authentication tag - after decrypting the data.

If your adversary has the $(\text{iv}, \text{key}, \text{ciphertext})$ they can recover the $\text{message}$ but they cannot detect tampering.

I recommend that you use Argon2i with a user's passphrase, running inside a WebWorker instead of the main thread such that you do not freeze the browser while computing the key. Do not store the key in localstorage. Similarly, do not store the key in any globally accessible variables I.e. not in window.mysecretkey!

Libsodium has an argon2i implementation and has been compiled to JavaScript/asm.js and WebAssembly.


Is scrypt a hashing function, encryption, or PBKDF?

Scrypt is most certainly a password-based-key-derivation-function.  So is PBKDF2, although it can be confusing since PBKDF2 is an eponym.  To add to the confusion, Scrypt uses PBKDF2 internally (which may be the hashing function you refer to), as well as the Salsa20/8 Core function (which may be the encryption function you refer to).  Further reading here.


While it is possible to encrypt using elliptic curves, typically some form of hybrid encryption is used (for performance reasons or because the algorithm supports only a few bytes of data). Typically an Integrated Encryption Schemes is used.

In these systems, another symmetric (AEAD) algorithm (AES in some modern and strong mode, Chacha+Poly1305, or a symmetric cipher and a MAC) is used to do the encryption, and the asymmetric algorithm is used to do a key agreement (typical in case of ECC) or key exchange (typical in case of RSA).

The key agreement process typically employed is based on Diffie-Hellman key exchange.

If you want an off-the-shelve program to encrypt data using ECC as key agreement, have a look at GPG. Versions beyond 2.1 have support for a handful of curves.

If you want to write a program that uses ECC, you will have to find a library that does ECC DH, or better yet, have a library that does the combination of key exchange and symmetric encryption for you (the so called seal and open operations), like NaCl or libsodium.


In secure transport protocols, the authentication tag (i.e. MAC value) is usually calculated with a session key. This session key is not linked to the data that is send, it is just used to protect the records within the transport protocol. Hence after processing the records, the tag is stripped off to retrieve the actual data that was send. Furthermore, after the session ends the session key gets destroyed - it is often not available at application level.

So although the authentication tag does protect the data while it is "in transit" it doesn't offer any protection afterwards. This is not because the MAC algorithm is not strong enough, it's just that the authentication tag and session key are not available anymore to validate the integrity/authenticity (as explained above). HMAC's are actually one of the most reliable schemes out there.

As example take the various TLS libraries. I don't know any where the TLS records or the session key is passed on to the application layer. TLS always protects the data with an authentication tag regardless.

To protect the data outside the transport protocol it is required to add protection in an application level protocol. For instance it is possible to send enveloped messages using the Cryptographic Message Syntax. For this long term keys are required. It is certainly possible to use a MAC to do add integrity to application level messages for long term storage.

Signatures are more common though. This is because a MAC requires a shared secret; symmetric cryptography is cumbersome when it comes to key management between different parties.

As it is now seems common to add a tl;dr: It's not so much the properties of the MAC rather than how it is used within a protocol that makes it just protect messages in transit.


Does this hash have any known collisions?

Of course; any value with 96 leading zeros (that is, between $0$ and $2^{32}-1$) will middle square to 0, hence that gives a $2^{32}$-wide collision right there.


Show that if a fixed key MAC is not collision resistant then the MAC function is not computation resistant for every key K

By my read of the question, I don't see why this is even correct. It does depend on how one interprets that "H is not computation resistant for every key K". I assume that this just means that $H$ is not computation resistant for a randomly chosen key $K$. Otherwise, I'm not sure what it would mean.

According to this understanding, I don't see why the statement is true. From here on, I will use the term "a secure MAC" rather than "computation resistant", since this is more standard terminology.

Now, the straightforward way you would try to prove this is to find a collision in $H_K$ and use this to break the MAC. However, the fact that $H_K$ is not collision resistant for a fixed $K$ means that when you are given the function description, you can find a collision. However, this doesn't mean that you can also do it when you are not given the function description. To be very concrete, define $H_K$ as follows. Parse $K$ into a key for a PRF and into the description of a group where the discrete log is assumed to be hard, along with a generator $g$ and random value $a$ and value $h=g^a$. The function works by first hashing the message using $hash(x_1\|x_2)=g^{x_1}\cdot h^{x_2}$ (using Merkle-Damgård based on this compression function, you get a full-blown hash function) and then applying the PRF. Now, if you know the value $a$, then it's easy to find collisions. Thus, $H_K$ is not collision resistant for any fixed key, since in the fixed-key setting you know $K$. However, in the standard MAC setting where you don't know $K$ and so don't know $a$, this will be a secure MAC (under the assumption that the discrete log problem is hard in this group).

So, I must be misreading the question somewhere. Either there is something in the quantifiers with the "for every key $K$" that I am misreading, or the intention of what a fixed-keyed hash function is is different to what I understand. Or there's an error in the question...

In any case, I wrote this out in detail since I think it has value.


Independent parameters basis for torsion-groups in SIDH: Is the Weil-pairing necessary?

As you mentioned, computing the discrete logarithm is an easy way to check for linear dependency. The usual way to compute discrete logs over elliptic curves relies on some pairing, but there are ways to do so without any pairing. See for instance "Isogeny-based key compression without pairings" at PKC'21 (https://eprint.iacr.org/2021/272.pdf), where pairing-less discrete logs are used for key compression.


Am I correctly understanding TLS 1.2 PRF (Pseudorandom Function)?

Simply by substituting A(0) in A(1), and then A(1) in P_hash, one obtains your second suggestion. I don't understand how you came up with the first one?


Yes, given a random 92-bit string, you will on average need to perform $2^{92}$ MD5 calculations to find a password whose MD5 hash begins with that 92-bit string.

However, if the passwords are not salted before they're hashed, then attacking multiple password hashes in parallel is only slightly less efficient than attacking one hash.  Indeed, if you only care about finding one of the passwords, having $n$ different hashes to target actually makes the attack about $n$ times faster.

Also, if the passwords are chosen by users, simply generating and testing strings that resemble common password choices will likely turn up the correct password in far less than $2^{92}$ attempts.  While it's possible to generate and memorize a password with 92 bits of entropy*, few people will actually take the time to do that.

(If the hashing scheme is indeed just plain (truncated) MD5, you may also be able to just look up the prefixes in a precomputed table of MD5 hashes of common passwords, several of which can be found online.)

This, not the size of the theoretical keyspace, is the reason for the recommendation to use a key-stretching KDF (like PBKDF2 or scrypt or Argon2) for password hashing.  Basically, it doesn't really matter if the hashes are 92 or 128 or 256 or 512 bits long, if the passwords they're computed from only have less than 30 bits of entropy.

*) For example, a seven word Diceware passphrase would have a little over 90 bits of entropy, while adding an eighth word would push it well over 100 bits.


I had a similar conundrum myself when I accepted a position doing very crypto-specific engineering work in industry. They asked me what my title should be, and I didn't really know. I asked my undergrad advisor and he said, effectively, that someone who

builds cryptosystems, and
proves them secure in a precise way, using
modern proof techniques and security reductions

is a cryptographer. Cryptographers also publish attacks from time to time, but most people would call an attack-focused researcher a 'cryptanalyst'.

In my mind, the important difference between a cryptographer and someone who otherwise works in security is precision in definitions and arguments.

I should state, though, that this distinction is rarely useful in practice, because really good ideas can come from pretty much anywhere. Don't get hung up on terminology.


You have four equations and two unknowns.  Any two of those equations should therefore be solvable, and all pairs that don't include the cheater should yield the same solution.

(You don't actually need to solve all six possible pairs of equations if you know there's at most one cheater.  It's sufficient to e.g. just solve equations 1 & 2, and check which of 3 & 4 fails to fit the solution.  If both fail, solve 3 & 4 instead, and check which of 1 & 2 fails to fit.)

Also, remember that you will need to solve all those equations in $\mathbb Z_{11}$, i.e. using arithmetic modulo 11.


How exactly is "true randomness" defined in the realms of cryptography?

Randomness is not a property of strings of bits (or characters of any sort).  Rather it is a property of the process that generates those strings.  However, it is convenient to conflate the string with the thing that produced the string, and thus to speak about strings being “random” or “not random”.

The string 00000, for example, is random if it was the outcome of “random process”, such as a coin being tossed five times and landing on tails five times in a row.  Similarly, the string 1,2,3,4,5,6 is random if it was the outcome from rolling a die six times.  Note, the random process does not need to be “fair” to be random, though processes that deviate substantially from the uniform distribution are not as useful for cryptographic purposes.

What is a “random process”?  As I think about it, a random process is either an indeterministic process (if any actually exist), or a deterministic process for which the entropy of what we don't know (that is germane to the outcome) is greater than the entropy of the generated string.  There is a lot we don't know (and can never know, given the Uncertainty Principle) about the state of the flipped coin – e.g. the exact position and momentum of every particle in the coin, the air around it, and the hand that flips it (all of which are germane, in that we presumably would need to know them to accurately predict the outcome of the flip).

If the string 00000 was the outcome of a number-generating algorithm, where the entropy of what was unknown and germane about the algorithm was less than 5 bits (e.g. we knew the algorithm and all but four bits of information about the seed), then the string would be “not-random”. At best it could be “pseudorandom”, meaning computationally difficult to distinguish from random.


Do the elliptic curves over prime fields must always contain prime number of elements (prime order)?

In general, an elliptic curve over $\mathbb{F}_p$ can have a nonprime order.
Much more is known.

As mentioned in Stinson's book Cryptography:Theory and Practice, 2nd Edition, Theorem 6.1, the additive group of an Elliptic curve $E$ over $\mathbb{F}_p$ with $p>3,$ and prime, is isomorphic to $Z_{n_1}\times Z_{n_2}$ with $$n_2|n_1,\quad n_2|(p-1).$$


How do ZK-STARKs, ZK-SNARKs, and Bulletproofs compare in size and speed for range proofs?

The paper in this address provides some more precise evaluations of various ZK proof techniques, including zk-STARKs, zk-SNARKs and Bullet proofs.

The have evaluation for a proof of membership for a Merkle tree with different number of leaves.


Bulletproofs range proof of value provided from trusted third party

I think the example that you saw was just a simple example of how a range proof would work in theory.

Range proofs could be used for encrypting transactions in cryptocurrencies, specifically the amount of the transaction.

A very simplified mathematical notation would look like this:

$\text{E}(a) - \text{E}(b) = 0$

where $a$ is the amount of coins you "spend" and $b$ is the amount the receiver gets. $\text{E}$ indicates that the values are encrypted. This simple calculation here only indicates, that $a$ and $b$ are equal, so you didn't somehow create coins out of thin air.

Bulletproofs are a new addition to range proofs, they basically prove the same thing but bulletproofs can prove something with less overhead than a normal range proof, which again makes them desirable for cryptocurrencies. You can find more information in this PDF of the published paper.

Now to your actual question:

You can't really prove that your age is a certain number without a trusted party. Range proofs (and bulletproofs) just prove that the encrypted input is equal to the encrypted output.

You technically could do this with your government as you suggested. You would need to create a commitment. The commitment comes from anyone who is trusted by the verifier. So to prove your age, this value would have to come from a government issued ID.


How does RSA signature verification work?

Why is it common practice to create a hash of the message and sign that instead of signing the message directly?

Well, the RSA operation can't handle messages longer than the modulus size.  That means that if you have a 2048 bit RSA key, you would be unable to directly sign any messages longer than 256 bytes long (and even that would have problems, because of lack of padding).

In contrast, a cryptographical hash can take an arbitrarily long message, and 'compress' it into a short string, in such a way that we cannot find two messages that hash to the same value.  Hence, signing the hash is just as good as signing the original message; without the length restrictions we would have if we didn't use a hash.

  The important part and this is where I really started scratching my head: How can the recipient verify that I own the private key if the public key seems to be enough to recreate the signature?

What made you think that the public key is enough to recreate the signature?  It is sufficient to verify a signature that you're given, but it is not sufficient to generate new ones (or so we hope; if that's not true, the signature scheme is broken).

If you're using RSA, the signature verification process is (effectively) checking whether:

$S^e = \operatorname{Pad}(\operatorname{Hash}(M))\pmod N$

Definitions: $S$ is the signature; $M$ is the message; $e$ and $N$ are the public exponent and modulus from the public key; $\pmod N$ means that equality is checked modulo $N$; $\operatorname{Pad}$ is the padding function; and $\operatorname{Hash}$ is the hashing function. Note I say "effectively" because sometimes the padding method is nondetermanistic; that makes this check slightly different, but not in a way that matters for this discussion.

Now, if we were trying to forge a signature for a message $M'$ (with only the public key), we could certainly compute $P' = \operatorname{Pad}(\operatorname{Hash}(M'))$; however, then we'd need to find a value $S'$ with:

$S'^e = P' \pmod N$

and, if $N$ is an RSA modulus, we don't know how to do that.

The holder of the private key can do this, because he has a value $d$ with the property that:

$(x^e)^d = x \pmod N$

for all $x$.  That means that:

$(P')^d = (S'^e)^d = S' \pmod N$

is the signature.

Now, if we have only the public key, we don't know $d$; getting that value is equivalent to factoring $N$, and we can't do that.  The holder of the private key knows $d$, because he knows the factorization of $N$.


Is there any block cipher which is also a pseudo-random-permutation over the key

I am not sure about the "more generally" since in the latter definition you are applying a function of the key. This now makes it related to circular security. Regarding the basic question, this is not true in general, and I don't know if it's possible to build such a construction. What I can say is that there is a construction where the pseudorandomness property holds if the key is random OR if the data is random. This notion is studied in the paper Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of an HMAC Assumption by Mihir Bellare and Anna Lysyanskaya. This paper would be a good starting point for research.


Simple commitment scheme using secure hash function

Yes.
If you publish such a commitment. And you model the hash as a random function it willl not only be preimage resistant but there will be many possible pairs of random string and message which will match the commitment.
If the random string is as big as the hash output most possible message values can produce the commitment for some random string. So even an attacker with infinite compute power will not be able to consistently discover the message, while an attacker with bounded computing power won't be able to learn anything about the message.

When the commitment is revealed, we know the attacker didn't cheat because collision resistance means the committer (With bounded conputing resources) won't be able to produce a commitment which matches two distinct known messages.