Having access to multiple servers, would additional usage of “Secret Sharing” for password storage enhance security?

How would such a scheme work?  You'd have to:

Split the password database (or is it individual entries?) into multiple shares;
Distribute those shares across many servers;
Have a system for those servers to peer together to reconstruct the password entries;
Support live additions and modifications of user password entries.  When a user changes their password, this is now a distributed transaction that must succeed or fail atomically (otherwise the user can't log in afterwards!).
Make sure that the reconstructed password entries are never written out to disk, or at least not in the clear.
Make sure that multiple database shares never get aggregated into the same backups.
Other problems I'm probably not considering.

It sounds like a very complex solution.  Lots of moving parts and lots of things that could go wrong.  Not just in terms of security, but also basic functionality.

And what are we supposed to gain from all this complexity?  The idea is that if an attacker steals one share (or fewer than the threshold), they can't mount a brute force attack on the database.  But I think that gain is put at risk by the fact that this would be a system of homogeneous, cooperative, automated peers:

If an attacker finds a software vulnerability that allows them to steal password shares from one server, there's a high probability that the same vulnerability can be used to steal shares from other servers, because of the system's homogeneity.
If an attacker can impersonate a peer, can't they just ask the true peers for the password shares needed to reconstruct the hashes?  After all, the peers freely cooperate with each other to hand over their shares.

Maybe there's a way to mitigate the latter by designating, for each password entry, one peer that "owns" it, so that peer will never share its share with any other.  But now the idea is getting pretty complex, more so when you throw availability requirements—when a peer goes down, can users whose entries are "owned" by that peer log in anymore?  If each entry has a "primary" owner and a "standby" to take over if the primary fails, can we fool the standby into thinking that the primary failed, and does that allow us to bypass the measures?

As a contrast, many applications of secret sharing involve humans who:

Are adversaries who are trying to prevent at least some of the others from learning the secret.
Store their shares in heterogeneous environments that the others don't control.
Store their shares in offline environments where extraordinary measures are required to retrieve them.
Come together to reconstruct the secret manually in a carefully regulated ceremony designed to prevent any participants or other parties from learning the secret.

See, for example:

The DNSSEC root signing ceremony
HashiCorp's Vault tool's initialization process has a PGP integration designed to encrypt the newly generated master key's shares in memory with the recipients' public keys, so that no person ever sees the plaintext of the master key shares.

Dropbox recently wrote a blog post detailing their password storage strategy.  They articulate a strategy that encrypts every hash with a global AES key, which looks much simpler than what you propose and arguably no less secure in practice.  I'll let the quotes speak for themselves:

  Finally, the resulting bcrypt hash is encrypted with AES256 using a secret key (common to all hashes) that we refer to as a pepper. The pepper is a defense in depth measure. The pepper value is stored separately in a manner that makes it difficult to discover by an attacker (i.e. not in a database table). As a result, if only the password storage is compromised, the password hashes are encrypted and of no use to an attacker.

  [...]

  Why is the global pepper used for encryption instead of hashing?

  Recall that the global pepper is a defense in depth measure and we store it separately. But storing it separately also means that we have to include the possibility of the pepper (and not the password hashes) being compromised. If we use the global pepper for hashing, we can’t easily rotate it. Instead, using it for encryption gives us similar security but with the added ability to rotate. The input to this encryption function is randomized, but we also include a random initialization vector (IV).

  Going forward, we’re considering storing the global pepper in a hardware security module (HSM). At our scale, this is an undertaking with considerable complexity, but would significantly reduce the chances of a pepper compromise.


Is $f(K, f(K, x))$ a pseudorandom function?

I'm responding to:

  "If the oracle accessed by B is truly random, how to prove the oracle B constructs for A is truly random, too?" I'd like to know if a solution to (or a construction which avoids) this problem exists.

This is a "good" thing to get stuck on, because it's not something you can just push under the rug.
Concretely, let $f_k(\cdot)$ be a random function, so for any $x_i$, you have that $y_i = f_k(x_i)$ is uniformly random (and independent of any other $y_j$).
If we knew that $z_i = f_k(y_i)$ was also uniformly random, and independent of all other $z_j$'s, we'd be done!

Is this the case? The answer is almost. Specifically, provided that $\forall i : y_i\neq y_j$, it shouldn't be hard to prove that all of the $z_i$'s are uniformly random (and independent), so everything works out well.

Intuitively, a random function can be expressed as a lookup table (and this is the most compact way to express it), so to compute $f_k(0)$ we lookup some value $U_0$.
The entries in this table are uniformly random, independent variables.
We can think about using this lookup table for $f_k$ to compute $f_k\circ f_k$ by doing two lookups (so precisely the way you'd expect to).

Now consider computing $q$ values $((f_k\circ f_k)(1),\dots, (f_k\circ f_k)(q))$.
This will all be uniformly random values, but there's a risk there's some dependence between them.
Specifically, if $f_k(i) = f_k(j)$ for $i\neq j$, then we'll have that $(f_k\circ f_k)(i) = (f_k\circ f_k)(j)$, so the random variables $(f_k\circ f_k)(i)$ and $(f_k\circ f_k)(j)$ will be correlated (and therefore not independent).
In terms of our lookup table analogy, the event $f_k(i) = f_k(j)$ happening means that our lookup table for $f_k\circ f_k$ ends up having $i$ and $j$ point to the same "slot" in the lookup table for $f_k$, which is the cause of the problem.

So, we want to bound the probability $\Pr[\exists (i,j)\in[q]^2\setminus\{(i,i)\mid i\in[q]\} : f_k(i) = f_k(j)]$.
This can be done with the birthday bound (which you should look up if you're not familiar with it), and can be upper bounded by $q^2/2^n$, which is where the term that was mentioned in the comments comes from.


Randomness and increment of nonce in GCM

Is it safe to use non-random nonce in GCM? Say I use 0x1 for m1, 0x2 for m2, so on.

It is perfectly safe to use a non-random nonce in GCM, as long as you never reuse a nonce for two different messages.  So, if you use the message count for the nonce, that's fine; if you accidentally forget that you used nonce 0x5 for a message, and use that again, well, that's not so fine.

  How much should a nonce increased for a file?

The file size doesn't matter; use any increment you want (other than 0).  You don't have to increment the nonce more for large files.


Why do we use encryption modes of operation to convert block ciphers into stream ciphers?

A block cipher in itself can - as the name implies - only transform one block. The ECB mode, which is basically the reapplication of the block cipher for each plaintext - is insecure, as it leaks information about the plaintext. The reason for this is that repetition in the plaintext blocks would lead to repetition in the ciphertext blocks. Block ciphers are deterministic, i.e. given a key and plaintext block as input they will always generate the same output.

So we need to have a mode of operation to convert fewer or more bytes than the block into ciphertext and back again. This mode needs to be non-deterministic. For this reason an Initialization Vector needs to be used. The IV makes sure that we never have the same ciphertext block even when encrypting multiple plaintext messages. We also like the property of the mode of operation to be online: it can process plaintext data when it becomes available, and the data size doesn't need to be known in advance.

There are basically two block modes of operation: ECB and CBC. ECB has already been discussed, it's just the reapplication of the block cipher over consecutive plaintext blocks. CBC uses the IV and then the ciphertext as vector for the next block encryption. As CBC still operates on blocks it cannot handle randomly sized plaintext. For this CBC needs to be paired with either a padding mode of operation or ciphertext stealing. Ciphertext stealing however isn't completely generic; it requires at least one block of plaintext. Padding modes open up the ciphertext to padding oracle attacks. Finally CBC also requires an unpredictable IV.

A stream cipher (mode of operation on a block cipher) has the nice property that it is secure and it can handle single bits or bytes at a time. It is online, which means that it is always ready to process data. Because it operates on bytes it doesn't require a padding mode. They generally just require a unique IV.

A stream cipher may offer more advantages such as being able to encrypt/decrypt in the middle of the stream, to use the cipher only in encrypt/decrypt mode and to pre-compute the key stream used for encrypting /decrypting the plaintext. Counter mode (CTR or SIC mode, to use a specific term) offers all of these advantages.

So basically we need a block cipher mode of operation to be able to encrypt / decrypt messages of any size and any content without opening ourselves to attack. And stream ciphers have nice properties that make them more applicable / secure for many problems.

CTR mode is used as underlying mode of operation for many AEAD (authenticated cipher modes) because of these properties. CTR mode is part of GCM, CCM and EAX modes of operation and even for SIV (which uses a deterministic IV which doubles as an authentication tag).


Java's internal secure random generator works along similar principles, just uses the older SHA1. By rehashing a starting point (seed), you create a ersatz cryptographically secure pseudo random number generator (CSPRNG).  Albeit, you're only creating one output per seed.

The entropy isn't really affected and truncation is okay as we consider all of the SHA256 output bits as independent.  Unless you have very particular requirements and used a true random number generator, the likelihood is that the UUIDs were originally generated by some form of CSPRNG from the underlying OS.  You're just adding another round of processing.

The number of random  UUIDs (of 122 random bits) which need to be generated in order to have a 50% probability of at least one collision is $\approx 2^{\frac{n}{2}}$ or $\approx 2 \times 10^{18}$. There's a little bit more in the wiki article.


First of all, there's no such thing as a secure 8-bit block cipher, at least not as such things are conventionally used.

That's because there are only 256 possible values for an 8-bit byte, and a block cipher will map each of these values to a different fixed value.  Thus, an attacker who can even occasionally guess the unencrypted value of some bytes (or, worse yet, can control the bytes to be encrypted) can easily learn which unencrypted byte corresponds to many, if not all, the encrypted bytes.  In fact, even if the attacker only had access to the encrypted data, they could most likely still decrypt much of it simply by comparing the frequencies of different encrypted bytes, and the patterns in which the bytes occur, with known examples of typical BIOS contents.

If you had a fast, key-agile block cipher, you could in theory make this attack a lot harder by using a separate key (typically, generated "on the fly" from a master key and the byte address) to encrypt each byte.  If the data never changed, and assuming that the keys were effectively independent (or at least independent enough to avoid related-key attacks), this could be secure; indeed, even if the data did sometimes change, all that observing multiple versions of the encrypted data would leak is whether the value of a particular byte matched an earlier value of the same byte.

Alas, I'm not aware of any fast, key-agile 8-bit block ciphers with a good track record of resisting cryptanalysis.  (That doesn't prove that there aren't any, of course.)

However, you could instead go further, and encrypt each bit separately.  Of course, there's only one possible 1-bit block cipher*, and it has only two possible keys: 0, which leaves the bit unchanged, and 1, which flips it.  Thus, "1-bit block cipher" is really just a fancy name for XOR.

You still need to generate an independent key bit to XOR each of your data bits with, of course.  For that, you need a stream cipher.  In particular, since you say you need random access to the data, I'd suggest using a (conventional, wide-block) block cipher in CTR mode as your stream cipher.

As long as your data never changes, XORing it with a keystream generated by a conventional block cipher (e.g. AES) in CTR mode actually is semantically secure.

With CTR mode, you can generate any (e.g.) 128-bit block of the keystream any time you like, without having to generate all the preceding bits of the keystream first.  As a simple performance optimization, consider caching the most recently computed keystream block in a register, just in case the next byte to be requested falls inside the same block.  You could even optimistically start pre-calculating the next block before you actually need it, if you expect a lot of sequential reads in practice.

However, note that CTR mode (and stream ciphers in general) may be insecure if the data can change.  In particular, as soon as an attacker learns both the encrypted and the unencrypted value of a given byte (or even a given bit), they'll learn the corresponding bits of the keystream.  Further, even just observing two different encrypted values read from the same address will reveal the bitwise difference of the corresponding plaintext values.

Avoiding such attacks is the domain of disk encryption theory, and can get rather tricky in general, especially if you demand that no extra storage space be used.

However, if you can set aside a bunch of (say, 16 or 32) bits in each Flash memory block to store a write counter, and are fine with the value of this counter being leaked if someone inspects the encrypted data, there may be a simple solution: just use this write counter together with the byte address (truncated to cipher block boundaries, of course) as the counter value.  That way, every time a Flash block is rewritten, the keystream for that block changes completely.

Of course, this means that you can't store data in the bits used for the counter, which, in particular, could complicate addressing, since the "logical block size" seen by the CPU will be slightly smaller than the physical block size of the Flash memory.  There are various tricks you might be able to use to get around that, but they depend on the specs of the system you're working with.

Also note that CTR mode encryption (like stream ciphers in general) is particularly malleable, and therefore potentially culnerable if an attacker may modify the encrypted data in the Flash memory.  To prevent such attacks, you may also want to store a (possibly per-block) MAC of the encrypted data, and verify it before allowing any data to be read.  (Note that the MAC input should include the block number and the write counter / IV, to protect against attacks involving swapping blocks or resetting the counter.  If you're using per-block MACs, you may also wish to compute a global "MAC of MACs" to prevent an attacker from mixing blocks from different versions of the data.)

*) Technically, there are two 1-bit block ciphers, but they differ only by a trivial rearrangement of the key space.


Are there shortcuts for computing ECC Point multiplication?

It is called "double-and-add". For instance, take a point, and add it to itself. Then take the result, and add it to itself. Do that again. And again. After ten additions, what you get is $2^{10} = 1024$ times the original point: in just 10 additions, not 1023. That's the "shortcut".

More generally, with $k$ successive doublings (a "doubling" is the addition of a point with itself), starting from a point $P$, you get $2^k P$. Now, all you have to do is to consider your multiplier $n$ in binary: this is about writing it as a sum of powers of two. For instance, if $n = 224965$, then, in binary, it becomes $110110111011000101$, which means that:
$$ n = 2^0 + 2^2 + 2^6 + 2^7 + 2^9 + 2^{10} + 2^{11} + 2^{13} + 2^{14} + 2^{16} + 2^{17} $$
And therefore:
$$ nP = 2^0P + 2^2P + 2^6P + 2^7P + 2^9P + 2^{10}P + 2^{11}P + 2^{13}P + 2^{14}P + 2^{16}P + 2^{17}P $$
So all you have to do to compute $nP$ is to compute these $2^kP$ (with successive doublings) and then add them together.

$2^0P$ is just $P$, so you already have it. Double it twice, and you get $2^2P$. Double that one four times, and you get $2^6P$. And so on. With $17$ doublings, you'll get all $2^kP$ for $k$ up to $17$, so in particular you'll get all the values you are interested in. As the formulas above show, ten extra additions, between the eleven $2^kP$ that are needed, will yield the result. In total, you got $224965 P$ with $17$ doublings and $10$ additions, i.e. much fewer than $224964$.

In all generality, if $n$ is a number of $t$ bits (i.e. less than $2^t$), then $t-1$ doublings and at most $t-1$ extra additions are enough.

There are many variations upon this mechanism, depending on how you interleave the doublings and the additions, and possibly reuse some addition results. You'll still need to compute the $t-1$ doublings, but you may save on some of the extra additions. How many intermediate results you need to keep in RAM is also a consideration. Moreover, if $n$ is a secret value, then you'll want to avoid side-channel attacks that may result in leaking some of the bits of $n$, and this impacts the kinds of double-and-add algorithms you can tolerate.


In a safe finite field elliptic curve, why is p not n?

Also, I'd understand that if p is smaller than n, but why sometimes we have a larger p than n? It won't be possible to have up to p private keys when the subgroup has order n right?

I suspect you're using an analogy with more normal discrete log problem, where the value is a value between 0 and $p-1$; obviously, you can't have more than $p$ values.

In contrast, the standard way of viewing an elliptic curve point is that is a solution $(x, y)$ to an equation such as $y^2 \equiv x^3 + ax + b \pmod p$ for fixed values $a, b, p$ (or a special "point at infinity", an artificial group member that's needed to make the group closed).

As a point consists of two values, each of which are between 0 and $p-1$, we have $p^2+1$ values that are potential candidates to be group members.  It should be obvious that the vast majority of those potential solutions aren't actually solutions to the equation; it turns that that there will always be approximately $p$ solutions (within the "Hasse interval"); and this "approximately" can be slightly larger or slightly smaller than $p$ (but always within $\sqrt{2p}$)

  given n, how would I choose p for a safe curve?

At your level of understanding, you don't.  The issues in selecting a curve are subtle, and you currently don't know nearly enough.  Instead, you should rely on someone who does know what they are doing to choose a good curve (which specifies $p$ and $n$) for you.

  Lastly, I see some tutorials referring to p as the characteristic of the curve, what does that mean?

Elliptic curves are defined using an equation over a field; for cryptography, we always use a finite field (as we generally prefer our ciphertexts to be expressible in a bounded number of bits).  A finite field always has exactly $p^k$ elements, where $p$ can be any prime, and $k$ any positive integer. We define the characteric as the value $c$ where we always have $\underbrace{x+x\ +...+\ x}_{c\text{ times}} = 0$ for all field elements $x$ (and where addition is the field addition operation).  It turns out that, for all finite field, we have $c=p$ (even if $k>1$).

Currently, it is most common to have elliptic curves with $p$ being a large prime and $k=1$; in this case, you can perform the field addition and multiplication operations modulo $p$ (for $k>1$, it gets more complicated), and the modulus $p$ is the characteristic.


Elliptic Curve Cryptography - When to use p and when to use n

A possible analogy is two layers in a communication protocol, with $p$ and $n$ the maximum packet payload for the lower and upper layer. They need not be equal (in communication protocols, typically due to overhead added by the upper layer, reducing its maximum packet payload compared that of the lower layer). We use limit $p$ or $n$ depending on if we deal with payload of the lower or higher layer.

In the question's example of ECDSA with a prime field, the lower layer is the base field $(\mathbb Z/p\mathbb Z,+,\cdot)$ with $p$ prime, where $+$ is modular addition modulo $p$, and $\cdot$ is modular multiplication modulo $p$.

The higher layer is the elliptic curve group $(E,+)$ (or a subset of that generated by a particular $G$, but for the curve considered there is no such restriction and I discard it for simplicity). Elements of $E$ are points of the elliptic curve (when using rational coordinates: defined by two coordinates in the base field matching the curve's equation, or as the neutral element), and $+$ is point addition. While doing point addition, we are dealing with coordinates, which belong to the base field, and thus must use $p$ as the modulus.

The order $n$ of $E$ depends on the curve, and there's no reason that it would be exactly $p$. One way to look at it is that we are starting from $p^2$ pairs of coordinates, filtering these per the curve's equation, and adding the neutral element. We can define scalar multiplication $\times$ on that group, and the natural modulus for the scalar multiplicand is the order of the group, that is $n$, rather than $p$.


Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation

The problem was that there was one additional thing I left out....if I'm increasing the loop iteration count and the number of bits from 2048 to 2050, then I had to choose a new R to satisfy the preconditions of Walter's optimization.

$R=2^{bitwidth} $ so I needed to have $R=2^{2050}$ instead of $R=2^{2048}$.

I'd now like to modify this to use multiple word scanning, as suggested by @Ruggero, and have a few follow up questions so will open another thread.


The obvious weakness when one sees a square is
$$(a)^{2} = (-a)^{2},$$ This is not a problem in the Rabin Cryptosystem since it requires an additional mechanism to resolve the message from possible 4 candidates. Here, however, this is can cause a direct collision.
Also, as noted by fgrieu, the calculation of the square root is not hard in the prime case by the Tonelli-Shanks. This algorithm work for prime $p$ and generalized for $p^k$, too.

Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

Take
$$h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$ So there is no reason for $A$ and $B$ to be a prime. Since it is not a keyed hash, we should know all values, like $A,B,C$ then
$$V^2 = \frac{h}{(A+B)^2} \bmod C$$ this has two solutions in the range $[0,C{-1}]$ and infinitely many solutions in the $\mathbf{Z}$. We can find these first two with the Tonelli-Shanks and the rest with modular arithmetic.
Therefore, one-can find pre-images, secondary pre-images, and collisions very easily. Remember in the pre-image attack we don't need to find the actual value $V$, and any value $V'$ that produces the given hash value $h$ will be enough for this attack to be successful.
Not even close to being a secure hash function at all.


Has anyone heard of matrix-based "Russian Doll" encryption techniques?

This seems to be a derivative of the techniques presented in 1997.

Exploratory Factor Analysis, by Ledyard R Tucker and Robert C. MacCallum


The proof (courtesy of M. Skorski) relies on the so-called "smoothing" technique [Cac97,RW,Sko15].

For some $0<\epsilon<1$, let $B$ be the subset of heaviest points in $X$ whose mass add up to $\epsilon$ -- i.e.:
  $$\sum_{x\in B} p_X(x)=\epsilon, \text{ and } \min_{x\in B}p_X(x)\geq\max_{x\in\bar{B}}p_X(x).$$
Let $X'$ denote the conditional distribution of $X$ on $\bar{B}$ -- i.e.:
  $$
  p_{X'}(x):=
    \begin{cases}
      0 & x\in B,\\
      \frac{p_{X}(x)}{(1-\epsilon)} & x\in\bar{B}.
    \end{cases}
  $$
Note that the statistical distance between $X$ and $X'$, $\Delta(X,X')=\epsilon$.$^1$ Let $m:=\max_{x\in\bar{B}}p_X(x)$. Now, let's consider the collision entropy of $X$:
  $$H_2(X):=-\log\sum_{x\in X} p_X^2(x)\leq-\log\sum_{x\in B} p_X^2(x)\leq^2-\log (m\epsilon).$$
It follows that $-\log(m)\geq H_2(X)-\log(1/\epsilon)$, and the results follows as $H_\infty(X')=-\log(m/(1-\epsilon))$.

A similar argument can be made for a joint distribution too.

References:
[Cac97]: C. Cachin. Smooth Entropy and Renyi Entropy, EUROCRYPT'97.
[RW]: R. Renner and S. Wolf. Smooth Renyi Entropy and its Applications.
[Sko15]: M. Skorski. How to Smooth Entropy? SOFSEM'16

Footnotes:
1. Proof:
  \begin{align}
    \Delta(X,X')
      &=\frac{1}{2}\cdot\sum_{x\in X}\left|p_X(x)-p_{X'}(x)\right|\\
      &=\frac{1}{2}\cdot\sum_{x\in B}\left|p_X(x)\right|+\sum_{x\in \bar{B}}\left|p_X(x)-p_{X'}(x)\right|\\
      &=\frac{1}{2}\cdot\left(\epsilon+ \sum_{x\in \bar{B}}p_X(x)\left|1-\frac{1}{1-\epsilon}\right|\right)\\
      &=\frac{1}{2}\cdot\left(\epsilon+ (1-\epsilon)\left|1-\frac{1}{1-\epsilon}\right|\right)=\epsilon
  \end{align}
2. Proof: $\sum_{x\in B} p_X^2(x)\geq \sum_{x\in B}m\cdot p_X(x)= m\cdot\epsilon$


If you are using random numbers and letters (upper and lower case) for salts, you can make the assumption that each character has 5.9 bits of entropy, assuming they are actually random.

A salt needs to be unique enough never to be used by 2 users that happen to have the same password. Rather than calculate some value on how likely that is, it is better to just assume that every password entry in the database should have a unique salt. It is even better that EVERY salt used for password hashing on every system on earth be unique.

Lets assume that 8 billion people all have a password for something. I have about 100 passwords for various systems, we can round to 33 bits of uniqueness for people, and 7 bits for password count.

Thus you want a bare minimum of 40 bits of uniqueness, which requires an 80-bit salt. The current trend is to simply use a 128-bit random number, making the chance of a salt collision "cryptographically unlikely" for the near term. 80 bits would require random 14 alphanumeric characters. 128 bits requires 22 characters.

There are generally standard methods on combining the salt and hashed password into a single string, I would suggest using that format. And of course, there will be mentions that a cryptographic hash is unsuitable for passwords and you need a memory/compute hard Password Based Key Derivation Function or a Password Hashing Scheme, which is true; read How to securely hash passwords? or one many posts on this site on how to properly choose and utilize one of these. MD5 is not even close to suitable for this, or any secure system.


Where does the range of possible values in Bleichenbacher's attack against PKCS #1 come from?

if $c'$ is PKCS conforming, that means that $2 \times 16^{k-2} \leq c' < 3 \times 16^{k-2}$

Uh, no. $k$ is the number of bytes, not hexadecimal nibbles. That must be made
$$2 \times 256^{k-2} \leq c' < 3 \times 256^{k-2}$$
where $256=2^8$ because a byte holds 8 bits. And then it comes
$$2 \times {(2^8)}^{k-2} \leq c' < 3 \times {(2^8)}^{k-2}$$
and from that
$$2\times2^{8(k-2)} \leq c' < 3\times2^{8(k-2)}$$
Finally, with $B\ =\ 2^{8(k−2)}$ and $c'\ =\ ms\bmod n$ it comes
$$2\times B \ \leq\  ms \bmod n \ <\ 3\times B$$
which is the intended meaning of
$$2B \ \leq\  ms \bmod n \ <\ 3B$$


It's definitely possible, but the standard needs some amendment to make it formal.
It's interesting to know that, KangarooTwelve is even faster, but nonetheless, not yet formallized.
Also that NIST intends approve SHAKE XOFs as MGF in RSA in FIPS 186-5, but not yet included in PKCS#1


Construct rainbow table to break DES for a fixed plaintext

Your formulas look somewhat strange to me, are you assuming perfect rainbow tables where you removed all collisions?
If you don't need a very high success rate, building perfect tables is feasible, but as you move up your success rate collisions become a real issue (even with multiple tables and or rainbow tables)
If you are not using perfect tables the math is more complicated.
You can choose m and t any way you like.
Also rainbow tables usually come instead of building multiple (distinguishing point) tables  (though you still can build several). In many cases it is simple and preferable to build one rainbow table.

You can choose m and t anyway you like but normally you choose m to be as big as your memory (or disk) and then choose t to be as high as you need for your success rate, or according to your table building budget.
for non-perfect tables table building is simply m*t, for perfect tables it can be much more (for high success rate).

So for high success rate you either pay a lot in table building throwing out colliding chains. Or you keep all the partially colliding and get an effective coverage of significantly less then m*t.


To give this question its deserved answer, I’ll repeat what Ricky Demer noted in his comment:

$$G(x \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s)  \\
\downarrow  \\
F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s)  \\
\downarrow  \\
F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s) = F(k,x \oplus 1^s) \oplus F(k,x)  \\
\downarrow  \\
F(k,x \oplus 1^s) \oplus F(k,x) = F(k,x) \oplus F(k,x \oplus 1^s)  \\
\downarrow  \\
F(k,x) \oplus F(k,x \oplus 1^s) = G(x)$$

As tylo commented: This shows G is not a secure PRG.


What is the difference between various modes in FPE?

Ff1,2,3 are basically inspired by LubyRack off constructions . At the core they differ in their round functions and key scheduling

FF1 supports greater range of lengths and a tweak

FF2 generates subkey for each iteration to thwart any side channel attacks

FF3 has tweaks is split and used in rounding function, also the reverse the sub-strings of given input string while using in round function,

Both FF1,FF2 has 10 rounds FF3 has only 8 rounds

Read more at NIST's 800 38 G draft


Generate random in secure message transfer

You can use the well established TLS (Transport Layer Security) protocol to achieve the first three properties and modify it to include a digital signature for non-repudiation*. However, strictly speaking, non-repudiation requires the use of certificates from a CA so that the signature can be verified by any third party.


Caution: White Box Cryptography is out of my comfort zone, and I have not been following the latest developments in the field. The following is my current opinion, which I present in hope of seeing it challenged, and learning in the process.

As I see it, the traditional goal of White Box Cryptography (and the one the industry would like most) is to design software that computes a standard public keyed cryptographic transformation (such as a keyed PRP, ideally AES) with a particular instance of the secret key embedded in the software, such that leaking the software does not leak the key.
I know no serious claim that this is even close to be achieved. On the contrary, WBC competitions that focused on the above goal with AES as the PRP have AFAIK all ended with quick key extraction.
With respect to that goal, it seems we do not even have practically secure WBC, and thus much less theoretically secure WBC. Contrast with the better situation in symmetric crypto, where we have practically secure PRPs and PRFs, but arguably no theoretically secure construction from first principles.

Yet a variant of WBC as defined above is practically feasible if we allow to construct the keyed transformation with WBC in mind: for example it's trivial to make a practically secure WBC implementation of the AES-256 lookalike WES-256, defined as:
$$\begin{align}
\text{WES-256}:\quad&\{0,1\}^{256}\times\{0,1\}^{128}\to\{0,1\}^{128}\\
&P\mapsto\text{WES-256}(K,P)\underset{\text{def}}=\text{AES-256}(\text{SHA-256}(K),P)
\end{align}$$
If we take that variant definition, security of WBC follows from that of more traditional constructs.

My conclusion is that I know no good definition of the theoretical goal of WBC, thus can't answer the question!


So you want them to practice using the CRT and Wiener's attack. I can now explain you how I would create a challenge in this direction.
As a side note please tell your students that they have to approach these problems with CRT / Wiener or they'll be very frustrated and maybe post here to ask for solutions which we can't offer because we don't which attack has to be applied which leads to frustration on all sides.

CRT
The main benefit of the CRT is that it provides a speed-up when we can piece our modulus into many small prime factors. As such I'd like to propose the following methodology:
Pick a small bound $B$ (less than $2^{20}$ so even trial division works). Pick your desired modulus size that rules out anything but small-factor-based factoring attacks (something like 100k bits, please also tell your students that they should use a small-factor attack here). Successively pick 100-10000 random primes smaller than $B$ and apply small exponents to each of them until you are satisfied with the resulting size of the modulus. Pick a valid $e$ and a message and textbook-encrypt the message. Provide the students with $e$, the modulus and the ciphertext and ask them to recover the message. Now to get the decryption done, they'll have to factor first and then use CRT. If they're not using CRT they'll have to wait a significantly longer amount of time (minutes as opposed to seconds at least). To fine-tune these parameters I suggest you try them out with and without CRT on your personal machine until you're satisfied with the time difference.
Wiener's attack
Pick an ordinary RSA modulus, ie a 2048-bit modulus with balanced primes that withstands all known factoring attacks just like you would for a production keypair. Now pick the private exponent first, such that it satiesfies the condition for Wiener's attack, i.e. it is small enough. Then construct $e$ as you normally would $d$, encrypt a message and provide the students with the ciphertext, $e$ and the modulus. Their task is then to recover the message. Test it yourself that one can actually recover the private exponent from this given set of data. And tell your students that they need to apply Wiener's attack or "one of the attacks we discussed in class previously".


Is it a good idea to use Lagrange/Newtonian interpolation for encryption?

I don't think this scheme would make sense, either from a performance or a crypto-design perspective.

From a crypto-design perspective, simply encrypting with a block cipher would be better.  Encrypting with a block cipher, or other suitable symmetric-key encryption scheme, takes running time that is linear in the length of the data to be encrypted (not $O(n^2)$).  You can encrypt data faster than you can send it out over the network.  So, there is no need for such a fancy construction.

From a database performance perspective, I also suspect this won't make sense.  You are not reducing the total amount of I/O; instead of storing data in the database, you are sending it over the network (at least twice, and probably many times).  This seems like a horrible tradeoff.


Is there way to combine secrets first and later split them?

On the information theoretic level you can not get a shorter result than the concatenation if you want to be able to recover the original inputs: If there are $k$ shares from a set with $2^{x}$ elements (represented as $x$ bit array), an injective function requires at least $(2^{x})^k = 2^{xk}$ different function values, which requires at least $xk$ bit. If the function combining the different shares has a shorter function value, it is not injective and you can not recover the original shares.

However, since the chosen string has a specific bit representation, you might be able to work with encodings to save space, e.g. Huffman codes, etc.

You might be able to choose your common secret and shares in a way, where the shares are not compressible by much but the common secret is.


As indicated in the comments, using PBKDF2 instead of e.g. PSS is replacing the padding scheme with another padding scheme. PBKDF2 is used as a key derivation scheme that accepts a password. Although that password needs to be encoded as bytes first, it does mean that you use PBKDF2 differently from how it is intended.

If PBKDF2 is used without a salt then you would have a deterministic scheme. If you do use a salt, then you'd need to somehow put it in your signature scheme. That's not necessarily a huge problem, but your current scheme is not fully described at best.

Similarly, you probably simply mask out the most significant (leftmost) bit of the PBKDF2 result to zero. That's fine as long as you describe it correctly and perform verification correctly. It's slightly awkward that the result is within the range $[0, 2^{(l - 1)})$ rather than $[0, {N - 1})$ to create a full domain hash but I guess we can look past that.

PSS is provable secure (given the usual pre-conditions, such as RSA and the used hashes being secure of course). Your padding scheme on the other hand lacks any kind of security proof (although, as SEJPM already commented, it would probably be easy to show that it generates a full domain hash, and that's considered secure). I don't see why it would not be secure - I think it is even likely that it is rather secure. However, with any cryptanalysis on a fully described scheme, that's just an educated guess.

The question is why you would need it since PKCS#1 v1.5 padding (for signature generation) only requires a prefix / postfix in addition to the hash value and PSS can be configured to use a single hash function (or any combination of two secure hash functions, one for the data and one as configuration parameter for MGF1).

If you'd study PSS you'll probably conclude that it is not that different from your scheme at all...


Possibility of factorisation of rsa modulus due to vulnerability in java implementation code

No, this is not a safe implementation; from the modulus and the public exponent, it would be possible to factor the modulus.

The reason is that you pick the private exponent to be small; one-fifth the size as the modulus.  It's known that knowledge of a public exponent corresponding to that is sufficient to factor.

The obvious question is "why are you picking the private exponent?".  Instead, why don't you pick the public exponent (65537 is a popular choice), and derive the private exponent from that.


Is a cryptographic key of size $N$ equivalent to $N$ bits of entropy?

Yes, there are caveats.

The key 982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224 is 256 bits long but has zero bits of entropy to anyone who knows you are using it.

Suppose you designed a cryptosystem where every legitimate user's secret AES-256 key started with a 192-bit prefix known to you, the designer, which which you chose uniformly at random.  To an adversary who doesn't have access to the system, the keys have 256 bits of entropy.  But to you, each key has at most 64 bits of entropy.  The United States government imposed this kind of requirement on Lotus in the international editions of its proprietary Lotus Notes software system in the 1980s, albeit with much smaller key sizes, back in the days when men were men and they all agreed that encryption was a munition used outside the United States only by terrorists and that 56 bits oughta be enough for anyone who's not a terrorist.

The number of bits in an RSA modulus may be 2048 (not counting the exponent bits, the private key, and any ASN.1 formatting or what-have-you to store it in a practical system), but it may reasonably be generated from a 256-bit seed.

Entropy is a property of a process or state of knowledge when the process or unknown may have many possible outcomes.  For a cryptosystem to be useful, from the adversary's perspective, in the adversary's state of knowledge, the legitimate user's key has to have a distribution of possible values with a nonnegligible min-entropy, which is formally defined as $-\max_k \log p(k)$ where $k$ ranges over all possible keys and $p(k)$ is the probability of the key $k$.  If the min-entropy is too small, then the adversary has a good chance of guessing the key on the first try.

But the length of the key is necessarily related to its entropy only in that the length in bits cannot be smaller than the entropy in bits, because you need to have at least $2^n$ possibilities in order to have an entropy of $n$ bits.


DROWN Attack - Which is the SSLv2 vulnerability exploited?

SSLv2 has the property that after it receives an encryption of the pre-master secret, the server sends a message that uses the derived key. (This is unlike SSLv3 where the server first checks the MAC from the client.) Now, when using a ciphersuite with 40-bit keys, it is possible to brute force and find the derived key. Importantly, in SSLv2, the derived key is just 40 bits of the pre-master secret (no hashing or anything). So, this gives an oracle for finding 40 bits of the pre-master secret. It is possible to use this to quickly find all of the bits of the pre-master secret, 40 bits at a time.

Some more details. In SSLv2 the RSA encryption uses PKCS#1 v1.5 padding. In order to prevent Bleichenbacher's attack, if the padding is incorrect the server just chooses a random secret and uses that instead (this fix was used throughout SSL versions). Thus, an attacker modifying the ciphertext cannot know if the padding was incorrect and this is a random value or if the padding was correct and this is the real value. The DROWN attack works by sending the SSLv2 server the same modified ciphertext twice. If the same key is used to compute the server reply both times, then the attacker knows that the padding was correct. (It also gets more information since as I wrote it gets 40 bits of the plaintext.) If the same result is not received both times, then the attacker knows that the padding was incorrect. The attacker knows if the same key was used since it just needs to brute force one of the messages in $2^{40}$ time to get the key. It can then try and see if that key matches the other ciphertext. All of this works since the server replies immediately and the attacker does not need to send a message with a correct MAC in order to get the server reply.

Note that this isn't the exact Bleichenbacher oracle, but it's a "Bleichenbacher-type" oracle.


Is using /dev/hwrng for raw key material secure?

Isn't that a contradiction in terms?
/dev/hwrng could be a  block device to anything at all.  If you trust the hardware, then yes. If you don't' trust the hardware, then no. The thing is that you can't tell. Nano scale technology has to be taken on trust. See Can any part of Intel's (RdRand) random number generator be visually inspected?

rngtest

Irrelevant. The Mersenne Twister is a pseudo random number generator. And it will ace most randomness tests. Yet it's deterministic depending on the seed, and can be inverted by only looking at 624 outputs. You could simply reseed it with every restart and it will look really random. Like seeding with the time. Yet it will offer no cryptographic security. Prove that your hardware if not just:-
$$ \text{E}_{k  \oplus  id} (x) $$
where k = some shadowy agency’s key, id = a device identification/serial number and x is some counter and/or time. Perhaps using AES, or some other CSPRNG? Some form of NIST 800-90A HMAC_DRBG? It can’t be mathematically disproved by any analysis of the output data.
How can you confirm that what your generator is giving you is truly random? You can't. Last year's US intelligence budget was $60 billion. What did they spend it on?

Trumpet sounds! Build your own. It's relatively easy and the only way to have 100% certainty.


First an important point of terminology: the real question should be phrased "Why not just sign the whole message with the private key of Bob, send it to Alice, and verify it with Bob's public key?". Signature and encryption are very different things. We use "encryption" only when the goal is confidentiality; and encryption is performed with the public key of the receiver, rather than with the private key of the sender (as is the case for signature).

With that terminology issue set aside, what the question describes is the rough principle of signature with RSA, where the encryption operation can be carried with the private key instead of the public one. However that does not transpose to arbitrary asymmetric ciphers: their public and private key is often so different that there's no way to encrypt with the private key.

Further, there are security issues with what's proposed:

  if someone else sends the message we simply couldn't decrypt it.

Not true. If an attacker prepares the message as a legitimate sender but a different key, the message could be decipherable, only most likely into gibberish. So at least we need a procedure to recognize real messages from gibberish, and that's not easy (it might be impossible if what's signed was already encrypted, which is common practice).

Also, an attacker is not restricted to applying a proposed protocol with a different key. S/he can alter or combine existing cryptograms, and that opens to attacks. That's a reason why secure RSA encryption and secure RSA signature differ by more than an exchange of the role of keys.

We usually sign a hash of the message, rather than the message, primarily because the signature schemes that we use can only directly sign small amounts of data (in the order of tens to a few hundreds bytes). A hash reduces an arbitrarily large message to a small size (32 or 64 bytes are common), that we can sign in a single chunk. Signing the hash is as secure as signing the message, because (for a good hash algorithm) we do not know how to make two different messages with the same hash (collision resistance). Without this hash trick, we could still sign, but we'd need to break the message into numbered pieces, and sign each piece individually. Signatures tends to be several times larger than what they can directly sign, and at least one of signature generation or verification is typically compute-intensive; thus hashing saves bandwidth and improves performance except for very small messages.

For many signature schemes, there's another reason: hashing the message is necessary for security. Otherwise, some property of the signature scheme would allow forgery: perhaps some few messages would have a trivial signature, or the signature of a message could be derived from the signature(s) of some related message(s). With addition of the hash step, messages allowing such attacks can not be exhibited, because (for a good hash algorithm) we do not know how to make a message with a particular hash value (preimage resistance), or more generally with a special property.


Yes, you can certainly construct this with zero-knowledge proofs of knowledge, some one-way function $OW$ (lets say bijective for simplicity), and a signature schemes $\Sigma$.

A simple protocol

Citizens choose a random preimage $x$ of the one-way function. Their secret key is $x$, their public key is $y = OW(x)$.
Citizens also store a state-issued signature $\sigma$ on $y$.
You can prove arbitrary NP statements in zero-knowledge, i.e. statements of the form "I know $a,b,c$ such that [poly-time checkable statement about $a,b,c$]".
So assume the citizen is approached with a list of $y_1,\dots,y_n$ of wanted criminals' public keys.
Both parties can then set up a zero-knowledge proof in which the citizen proves

  "I know $x,y,\sigma$ such that $y = OW(x)$, and $\sigma$ is a valid
  signature on $y$, and $y\notin \{y_1,\dots,y_n\}$".

Zero-knowledge guarantees that the vigilante does not learn the values of $x,y,\sigma$. The proof of knowledge property guarantees that the citizen can only make the vigilante accept if he actually knows $x,y,\sigma$ with these properties. This (kinda) prevents a person on the list from winning the proof - they need some honest/unlisted person's secret $x$ and their signature $\sigma$, which only the honest person knows.

Drawbacks

In practice, this simple scheme has limited applicability because wanted persons only need to convince any unlisted person to give them a copy of their $x,\sigma$. If they have that, they can easily pass the police check.
The underlying problem is that while physical IDs are (ideally) hard to copy, a digital identity is just a bunch of bits that is easily duplicated and handed over to another person.
You can probably make all of this more elaborate and give each person a trusted device that stores $x,\sigma$ in an unclonable way. But as soon as you have that, the zero-knowledge protocol becomes somewhat overkill - the police could just ask the trusted device whether it sees its identity on the list.

Hiding the list

In the scheme listed above, the list contains no identifying information about the listed people (just a random value). You can however recognize values you have already seen before (e.g., friends). You could hide the list, for example, as follows:

Assume for concreteness that the one-way function maps an integer $x$ to $OW(x) = g^x$ for some fixed $g$ in some prime-order group $\mathbb{G}$ where decisional Diffie-Hellman is hard.
The signature stuff stays the same and the list is comprised of the criminals' public keys $g^{x_1},\dots,g^{x_n}$.
Before showing the list to the citizen, the vigilante now randomizes the list to look random:

The vigilante chooses a random $r\leftarrow\mathbb{Z}_p$.
He then hands $h = g^r$ and $h^{x_1},\dots,h^{x_n}$ to the citizen.
Under the decisional Diffie-Hellman assumption, the elements $h^{x_i}$ are indistinguishable from random group elements. [1]
The citizen can still prove in a zero-knowledge proof of knowledge that he knows $x,y,\sigma$ such that $y = g^x$, $\sigma$ is a signature on $y$, and $h^x \notin \{h^{x_1},\dots h^{x_n}\}$.

[1]: of course, this only holds if the secret key $x_i$ of the entry is unknown to the citizen. Necessarily, each citizen must be able to recognize himself on the list. It's just all other entries that now look random.


Should we use IANA groups 14 (MODP), 25, and 26 (ECP)?

It appears that our firewall supports DH group 25, and 26. Almost
  everywhere I've seen, they've recommended DH group 20-24 (we don't
  have DH group 24).

  Should we use these groups?

NO, stick to groups 19-21 if possible!

According to the linked resource, DH group 25 is a prime-based 192-bit elliptic curve and group 26 is a prime-based 224-bit elliptic curve. These provide a security level of 96 and 112-bit respectively, that is the best known attack will require about $2^{96}$ or $2^{112}$ curve operations. I suppose these curves were standardized as enough people complained they can't computationally or by bandwidth or storage afford to use group 19 and the probably did so after 19-21 were standardized.

Now compare this to the groups 19, 20 and 21 which use 256-, 384- and 512- bit elliptic curves which respectively offer 128, 192 and 256-bit security. This is much better at a minor cost of performance. If you really can't afford to use these groups for performance reasons, then the 224-bit group should be fine, as its security is comparable to 2048-bit classic DH / RSA and the 192-bit group is risky as its security could be broken by a sufficiently determined attacker with sufficient funding, usually this is attributed to nation-state attackers.

  DH group 21 is also "only" a 512 bit algorithm compared to DH group
  14, which is a 2048 bit algorithm. However I read that DH group 21 is
  still better than 14, because it uses elliptical curve.

Group 14 uses classic finite-field diffie-hellman, i.e. $g^x\bmod p$ for a 2048-bit prime $p$. Because this operation exposes so much structure, there are attacks that are more efficient than the generic ones, which is all that works against elliptic curves. These attacks are so good, that a 2048-bit prime modulus for DH has roughly a 112-bit security level, which roughly corresponds to a 224-bit elliptic curve, e.g. group 26.

Also note that due to these more scalable attacks, group 1 is actually breakable, even by academics and group 2 which has a 80-bit security level due to its 1024-bit modulus has a decent chance of being breakable by a determined attack with sufficient funding. Also due to the nature of these attacks, it is sufficient if the attacker once does one big pre-computation for the parameter set and can then break individual DH instances very easily, think 1 week of pre-computation to solve each instance in 90 seconds afterwards.


Random oracle model proofs and programmability

Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's called the Fiat-Shamir heuristic; it's a nice trick to make non-interactive zero knowledge proofs.
Before getting to Fiat-Shamir, consider how your favorite basic zero-knowledge proof works. Since this is Crypto SE, not CSTheory SE, hopefully you are thinking about proving knowledge of discrete logarithms and quadratic residues, not graph isomorphisms or 3-coloring graphs. ;)
[Aside: technically these are not true zero-knowledge proofs, they are honest-verifier zero-knowledge proofs (sometimes called $\Sigma$-protocols) but we don't care about that distinction here]
Schnorr's proof of knowledge of a discrete logarithm
$P$ (for prover) comes along with two values $g$ and $y$ in some group $\mathbb{G}_q$ where the discrete logarithm is hard. She claims: I know the value $x$ such that $y=g^x$. As $x$ is the discrete logarithm of $y$ base $g$, computing $x$ directly is infeasible so $V$ (verifier) cannot initially be sure if she really knows $x$ or not.
The Schnorr protocol lets $P$ prove knowledge of $x$ to $V$ in a way that does not disclose anything about $x$. It goes as follows:

$P$ generates a random value $a$, computes $b=g^a$, and sends $b$ to $V$
$V$ generates a random value $c$ and sends $c$ back to $P$
$P$ computes $d=a+cx$ and sends $d$ to $V$
$V$ accepts $\langle b,c,d\rangle$ as proof for $\langle g,y \rangle$ iff $g^d=by^c$

Security Analysis
We can ask ourselves, what do you we want in terms of security from such a protocol? $V$ is concerned that sending a bunch of numbers back and forth might not actually constitue a proof that $P$ knows such an $x$. If he can actually conclude that $P$ must know $x$ if $P$ can produce many accepting $\langle b,c,d\rangle$ transcripts, the proof is said to be sound.
$P$ may be concerned that $V$ might learn some information about $x$ from seeing one or more accepting transcripts. This is supposed to be a proof that leaks zero information about $x$ (glossing over the honest verifier technicality). If it leaks zero information, it is said to be zero-knowledge.
Soundness (via Extraction)
To show the Schnorr protocol is sound, we are actually going to do it indirectly. We are first going to show it is something called "extractable" and then show that extractability implies soundness. I'm not going to give actual definitions or proofs, just a sketch of what is going on.
Schnorr protocols have a special soundness property (called, you guessed it, special soundness): if there are two accepting transcripts $t_1=\langle b,c,d \rangle$ and $t_2=\langle b,c',d' \rangle$ where $t_1$ shares the same value of $b$ with $t_2$ but $c$ (and thus $d$) are different, then it is possible to calculate the value of $x$: $x=(d-d')/(c-c')$. If $P$ can reliably generate accepting transcripts, then there is no reason to suppose she couldn't generate $t_1$. Likewise $t_2$. And if she can produce both, then she "knows" $x$ in the sense that the knowledge required to produce $t_1$ and $t_2$ is sufficient to produce $x$ itself.
When we eventually get to Fiat-Shamir, it will be important to have formalized this notion of "extractability" a little bit. Consider the situation where $P$ is a compiled binary program instead of a person. You can run $P$ which will perform the protocol and you can rewind $P$ to a previous internal state, but you can't decompile it or look at the internal state (this is called rewindable blackbox access; why these special powers are allowed in proving extractability is a topic for another time).
We say that a protocol is extractable if you can get $x$ from interacting with such a black box. And we say a protocol is sound if it is extractable in this way (a blackbox that you can rewind). Both of these propositions have proofs in the literature with lots of fine-print I am omitting. Note that you can prove soundness in other ways than extractability or other flavours than blackbox-rewindable extractability (extractability is sufficient but not necessary).
For Schnorr, it should be obvious how, but you do the following:

Let $P$ output $b$
Give $P$ a random $c$ as input
Let $P$ output $d$
Rewind $P$ to after step 1 and before step 2
Give $P$ a different random $c'$ as input
Let $P$ output $d'$
Compute $x$ from $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$

Zero-knowledge (via Simulation)
Similarly, we can indirectly prove the protocol is zero-knowledge by showing it has a different property: simulatability. In this case, we get a compiled binary of $V$ and have to reliably supply it with acceptable $b$ and $d$ values for the $c$'s it gives us. However the protocol is for knowledge of an $x$ we do not actually know! If we can simulate acceptable protocol runs without knowing $x$, then the values in the protocol must not really be leaking any information about $x$. So if the protocol is simulatable in this regard, then it is zero-knowledge.
I mentioned before that Schnorr is not actually a zero-knowledge protocol. This creates some problems with simulating Schnorr transcripts that will get resolved when we use a random oracle with Fiat-Shamir. To simulate Schnorr protocols, we do the following:

Generate random value $d$
Guess the value of $c$
Supply $b=g^dy^{-c         }$ as input to $V$
Let $V$ output $c'$
If $c'\neq c$ (you guessed wrong), rewind to step 2. Else continue
Supply $d$ to $V$ which will accept

If the values of $c$ are really short (say a bit), then the simulator is efficient. For longer values, you can't prove the zero-knowledgeness of Schnorr with this method. There are a handful of tricks to convert Schnorr into something that is true zero-knowledge.
Fiat-Shamir Heuristic
Reading the above, you might do a double-take: on one hand, you can show that $x$ must be known if transcripts accept and on the other, you can generate transcripts that accept without $x$: what gives? If you look closely, you'll see that the simulated transcripts are generated out of order while the extractable ones are generated in order. In fact, by generating out of order, we cannot produce $\langle b,c,d \rangle$ and $\langle b,c',d'\rangle$ transcripts since the value of $b$ is no longer being chosen: it is determined by $d$ and $c$.
The idea of Fiat-Shamir is to make Schnorr (and related) protocols non-interactive. This means $P$ can produce all three values $\langle b,c,d \rangle$ instead of relying on $V$ to provide $c$. Furthermore, since we know transcripts are simulatable, $P$ can produce a value of $c$ that has to have been generated after the value $b$ thus ruling out any simulation. How? It is really easy actually: set $c=\mathcal{H}(b)$. The verifier additionally checks that $c=\mathcal{H}(b)$. [Aside: there is actually a neat optimization here where you don't have to send the value $b$ at all but leave that aside].
Finally we can introduce random oracles. It turns out that if you use regular hash functions, you can't wrestle extractability or simulation out of the protocol. We'll try but ultimately we will require a random oracle that can be programmed.
Extraction with Fiat-Shamir heuristic
Recall that extraction relies on pairs of transcripts like $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$. With Fiat-Shamir, $c=\mathcal{H}(b)$ so if the values of $b$ between two transcripts are identical, then $c$ and thus $d$ will be as well. Therefore, we cannot get two such transcripts with a regular deterministic hash function. But if $\mathcal{H}$ is a programmable random oracle, we can get it to produce different values for the same input. Once again, we play the game of having rewindable blackbox access to $P$ but this time we also get the random oracle:

Let $P$ generate $b$
See $P$ query $O$ with $b$ for $\mathcal{H}(b)$
Generate random $c$ and program $c=\mathcal{H}(b)$ in $O$
Let $O$ answer query
Let $P$ compute $d$
Let $P$ output $\langle b,c,d \rangle$
Rewind to end of step 2
Generate random $c'$ and program $c'=\mathcal{H}(b)$ in $O$
Proceed as before and eventually let $P$ output $\langle b,c',d' \rangle$

A few notes: (1) because this is non-interactive, $P$ does not output $b$ after step 1, so we rely on the ability to see queries to the random oracle; (2) if the oracle generates answers "on the fly" (instead of entering the protocol with a codebook of all queries/responses), we don't actually have to program it with different values of $c$. We just rewind to before the point it is about to generate a response and let it generate a random value (which will overwhelmingly be different than in the first execution). This sheds some light on the original poster's third question.
Simulation with Fiat-Shamir
Similarly to extraction, the use of a random oracle makes simulation a breeze. Assuming you've read this far, you can probably see how so I will just say it in a sentence: Set a random value for $c$, compute $\langle b,c,d \rangle$ by choosing $d$ first, and when the verifier checks with the oracle that $c=\mathcal{H}(b)$, program $c$ as the response.


How to attack a general polyalphabetic cipher?

A general polyalphabetical cipher is just a combination of several general monoalphabetical ciphers, each applied on every $n$-th letter of the message.

So the first thing is to find out what $n$ is (i.e. the key length). For this we can use the index of coincidence just like for Vigenere.

Then we can split the message into $n$ parts (columns), and try to break each of it as an individual monoalphabetic cipher, starting with frequency analysis. (We'll have to correlate information from the individual columns to do bigram frequency analysis, too.)


What is the difference between Scrypt and PBKDF2?

Both PBKDF2 and scrypt are key derivation functions (KDFs) that implement key stretching by being deliberately slow to compute and, in particular, by having an adjustable parameter to control the slowness.

The difference is that scrypt is also designed to require a large (and adjustable) amount of memory to compute efficiently.  The purpose of this is to make cracking it harder to parallelize using devices like GPGPUs or custom ASIC / FPGA hardware.
Such devices may have hundreds or even thousands of parallel processing units, each capable of hashing a different password using traditional KDFs like PBKDF2, which don't require much memory.  However, it turns out that, at least using current technology, providing each of these parallel units with large amounts of memory space is a lot more difficult and expensive than making the units themselves.

Another difference between PBKDF2 and scrypt is that PBKDF2 is a generic construction for turning any cryptographic hash function (actually, a pseudorandom function, but the most common way to obtain a PRF for PBKDF2 is to build one out of a hash function using the HMAC construction) into a key-stretching KDF.  Thus, the actual KDF you use might be e.g. PDFKD2-HMAC-SHA256, meaning PBKDF2 built on HMAC built on the SHA-256 hash function.

Scrypt, on the other hand, is a specific key derivation function with "no user-replaceable parts inside".  While scrypt does make use of some standard functions and constructions (in fact, it internally uses PBKDF2-HMAC-SHA256 for the state expansion and compression stages), the scrypt specification doesn't make any allowances for, say, changing the hash function to something other than SHA-256.  It's a "take it or leave it" deal.

That said, it would, in principle, be possible to define a new KDF using the priciples described in the scrypt paper, but with different components.  In particular, the scrypt paper defines scrypt as an instance of a more general construction called MFcrypt, instantiated with HMAC-SHA256 and the memory-hard mixing function SMix (also defined in the paper).  It would be possible to use an MFcrypt instance with, say, SHA-3 instead of SHA-256, but that function would no longer be "scrypt" as defined in the paper.


What are the implications of XORing ciphertext with plaintext?

This is not a correct encryption scheme because it cannot be properly decrypted. Consider $E_k$ to be the one-time pad (OTP), the key being all zeroes. Then, for any message, you have:

$$C = E_{0^{|m|}}(m) \oplus m = (m \oplus 0^{|m|}) \oplus m = m \oplus m = 0^{|m|}$$

Or consider encrypting some random string $r$, then you have:

$$C = E_k(r) \oplus r$$

Which is basically the OTP. How would you expect to decrypt that?

The PCBC mode also does not output this construct as part of the ciphertext but feeds it as input to the block cipher encryption XORed with a plaintext block.


Miller Rabin - Error probability of .5 a possibility?

The problem is that you got the algorithm wrong.  You use it to generate an integer (which is one of 1, $x-1$, or $y^{x-1} \bmod x$, and then say "prime" if that integer is prime.

That's not correct; in fact, the three integers you list (90007 91571 94343) are each prime, and Miller Rabin should always return prime when given a prime.

Instead, the correct implementation of MR should:

if the initial computation is $y^{(x-1)/2^u}$ is 1 or $x-1$, conclude probably prime.
do $u-1$ square operations, if the result of any of them is $x-1$, conclude probably prime, if it is 1, conclude "composite"
if, after the $u-1$ square operations, you never hit $x-1$, conclude "composite"


Encryption with Web Crypto API (SubtleCrypto)

Is it a good idea [from a security perspective] to use the first 16 bytes of SHA-1 (20 bytes long) as IV?

It depends.
For CBC, the main requirements is the IV are that it should be unpredictable for the attacker. In particular, you should never ever use the same IV more than once for encrypting messages under the same key.
This implies that, in your system, it should be impossible to edit or overwrite these items. If editing an item is ever possible, then deriving the IV from the item identifier is definitely a bad idea.
If you want to support the editing of items, you should always generate a (pseudo-random) IV. (I.e. it should not be predictable for an attacker.)


With EC secp256k1 is there a way of transforming a function of the private key to a function of the public key?

We aren't aware of any sich relations. In fact, one assumes that the group of elliptic curve points behave like a Generic Group.
A generic group is a group, where the encoding of the elements are chosen as a random values.


How to best obtain bit sequences from throwing normal dice?

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon.

Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple methods like

1 -> 00
2 -> 01
3 -> 10
4 -> 11
5 -> 0
6 -> 1

is quite simple and produces $1+\frac23 = \frac53 \doteq 1.667$ bits per roll. AFAIK, this is the maximum you can get without aggregating the rolls.

You can apply this idea to two rolls and obtain $5$ bits with probability of $\frac{32}{36}$ and $2$ bits otherwise thus getting

$$2 + (5-2) \cdot \frac{32}{36} = 2 + \frac{3 \cdot 8}9 = 2 + \frac83
= \frac{14}3 = 4\frac23$$

bits for two rolls, i.e., $2\frac13 \doteq 2.333$ bits per roll, which is quite close to the theoretical maximum of $\log_2 6 \doteq 2.585$.

For a simple "implementation without computer", note that you can extract 1 bit directly from each roll and need to process the "rest" only (e.g. you can get the bit via $n \bmod 2$ and the rest via $\lfloor \frac{n-1}3 \rfloor$). This makes even combining 3 or 4 rolls using a small table easy.

The exact procedure for two rolls

For simplicity, let's assume, each roll produces a number $n_i$ from the set $\{0, 1, \ldots, 5\}$.

Extract one bit from each roll as $n_i \bmod 2$.
Compute $3 \cdot \lfloor \frac {n_1}2 \rfloor + \lfloor \frac {n_2}2 \rfloor$, which is number $x \in \{0, \ldots, 8\}$
In case of $x = 8$, you're out of luck and get nothing but the two bits from the first step.
Otherwise, use $x \in \{0, \ldots, 7\}$ as the next three bits.

So, most of the time you get five bits. On the average, you get

$$\frac19 \cdot 2 + \frac89 \cdot 5 = \frac{42}9 = 4\frac23$$

bits as stated above.

There are nearly 5.170 bits in two rolls, but you can't extract 5 bits from them on the average without further aggregation.


How to generate unique (random) numbers that can be traced back to a unique source number?

The numbers $n$ (coding source) and $m$ (coding index for a given source) can be combined into a single  bitstring; e.g. with  $0\le m<2^u$ and $0\le n<2^v$, as a bitstring of $\lceil u+v\rceil$ bits. Then, converting that single bitstring into a unique random-like number can be done by encryption with a secure block cipher with block width $w\ge u+v$ bits and a fixed secret key (prefixing input with $w-\lceil u+v\rceil$ zero bits in order to reach the width $w$ of the block cipher). The random-like number will be an integer corresponding to the ciphertext bitstring, thus in range $[0\dots2^w-1]$.

Distinct pairs $(n,m)$ inputs allways lead to distinct output, because a block cipher is a permutation of its block space. Decryption (requiring the key) allows recovering the original bitstring from the random-like number, and from that $n$ and $m$. If one checks that what's deciphered could have been obtained from a valid $(n,m)$ (including $w-\lceil u+v\rceil$ zero leading bits), residual odds that a random bitstring is acceptable are $2^{u+v-w}$.

Using AES ($w=128$, regardless of key width) and $u=v=40$ ($n$ and $m$ up to about a trillion), these residual odds are $2^{-48}$. Problem is, the random-like number is up $2^{128}$ (about $39$ decimal digits). The classic 3DES ($w=64$) or the relatively unproven Speck ($w\in\{32,48,64,96,128\}$) are alternatives.

If you want a shorter unique random-like number (with as a counterpart higher residual odds that a random bitstring will be acceptable), or more choices for $w$, use format-preserving encryption; we have a number of questions about that.


Your best bet is running the General Number Field sieve (implemented by e.g. CADO-NFS or msieve) on a bunch of beefy computers. The GNFS is the only algorithm to have ever been used to factor 512-bit integers and in fact there is an open-source script (collection) Factoring-as-a-Service that will automatically factor a given number using AWS EC2 for about 100USD (in 2015, now it can probably be adjusted to use newer, faster instances which are cheaper).

Of course using the GNFS should always stay the last resort option. What you have tried so far (without luck it seems):

An optimized variant of Pollard-Rho, which finds small factors quite fast.
An optimized variant of the quadratic sieve (single-threaded), which brute-force-factors numbers up to about 250-300 bit faster than the GNFS.
Pollard p-1 and William's p+1 factoring which work quite well if either of p-1 or p+1 has a smooth factorization
The Elliptic Curve Method (ECM) which should find small factors up to about 200 bit (larger if more time).

What I could still imagine to maybe work is some Fermat-Factoring or maybe the Special Number field sieve.
But then, the proper strategy probably depends on the context in which you encountered this. If it was during e.g. a security review and you want to demonstrate the insecurity, then the GNFS is probably the way to go, if you encountered this during some homework, then some algorithm you learned prior is probably the way to go.


The answer rather depends on what you mean by 'entropy'; if you mean 'Shannon Entropy', then no, a deterministic function cannot increase entropy.

For example, if the unhashed password has only 7 different possible values, then the hashed version of the password will also have (at most) 7 different possible values; you've made things look more obscure, but you haven't actually changed anything as far as entropy is concerned.

The standard definition of Shannon entropy is:

$H(X) = \sum -p_i\  log_2 p_i$

Where $p_i$ is the probability of the $i$th possible sample value.  That is, the Shannon entropy is defined solely in terms of probability distribution, and not how that probability distribution appears.

If we have a Hash function $SHA$ which doesn't have any collisions, then it has no effect on entropy; that is, $H(X) = H(SHA(X))$; that's because the probabilities involved in the probability distributions are precisely the same; if a specific password $x_i$ had a certain probability, then the hashed form of that password $SHA(x_i)$ will appear with that exact probability in the hashed distribution.

And, if the Hash function $SHA$ does have a collision, that is, if $SHA(x_i) = SHA(x_j)$, then (assuming both $x_i$ and $x_j$ have nonzero probability), then $SHA$ will actually reduce the entropy.  And, this is not a violation of collision resistance; collision resistance only states that it is hard to find such a collision, not that one does not exist.

This is easier to see in the extreme case; suppose we have two possible passwords ("Mary" and "Susan"), and both of those passwords have probability $0.5$; this means that the entropy of the password is 1 bit; an attacker can perform go through all possible values by checking on two different passwords.  If you hash the password, you may come up with two images (39e74b4e80ba656f773669ed60315a and 98e15403b2b1ea5022fc42b3490cc76e in hex) that look different, however there are still only two possible values, and so the effort an attacker would have in trying those two values in unchanged.


How to derive two keys from one password

Yes, scrypt achieves this.  Scrypt has a variable-length output, so just generate as much output as you need.  For instance, you can ask it for 256 bits of output, then use the first 128 bits for one key and the second 128 bits for the other key.

While PBKDF2 also has a variable-length output, I do not recommend that you use it in the same way.  It has a subtle disadvantage/weakness which slightly reduces its available security if you ask it to generate more than one block of output.  Instead, I recommend that you use PBKDF2 like this:

Kt = PBKDF2(..., passphrase, salt, n, 128)
(K1, K2) = PBKDF2(..., Kt, salt, 1, 256)

In other words, use PBKDF2 with lots of iterations (choose $n$ to be large) to generate a 128-bit temporary key $Kt$; then use PBKDF2 a second time to stretch $Kt$ into 256 bits of pseudorandom output, and use that to form the keys.

What's wrong with just asking PBKDF2 to give you 256 bits of output?  It turns out that, due to a subtle issue, this may let an attacker get a 2x speedup.  Or, another way to think about: it forces legitimate users to do twice as much work as they ought to, which means you can't push the iteration count up quite as high as you should, so you get weaker security than you could have gotten.  The subtle issue is described at a high level in this Ars Technica article; a blog post has more technical details, as does an explanation from 1password.

Basically, the issue is that with PBKDF2, an attacker who wants to test a guess at your password can generate just the first 128 bits of the 256-bit output twice as fast as generating the whole thing, and the first 128 bits may be enough to verify whether the guess is correct.  Scrypt does not have this issue (when used with typical parameters), so with scrypt, you can just ask it for 256 bits and you'll be fine.

Don't try to use both.  There's no need to use both scrypt and PBKDF2; and if you do use both (scrypt to generate one key, PBKDF2 to generate the other), then you will have introduced the same subtle weakness described above, just in a slightly different guise.

Bottom line recommendation. If this sounds too complicated: just use scrypt, and ask scrypt for as much output as you need.  You can ignore all the rest.


I just found the "round constants" which hopefully are sufficiently unique to allow identification of the algorithm.


RSA encryption/decryption process is not working correctly

The RSA definition requires $n = p q$ where $p$ and $q$ are distinct primes.
In your example $n=4802$ has a factorization as;
$$ n = 2 \cdot 7^4$$ with 10 divisors. Also, your $q=8$ is not a prime.

Here a working example for you with  fips.186-4 standard, or see $\lambda$ versus $\varphi$ in RSA;

Select two distinct random primes;  $p = 47, q = 43$
compute $n = 47*43 = 2021 $
compute $\lambda(n)=\operatorname{lcm}(p-1,q-1)= \operatorname{lcm}(62,42)= 966$
select $e$;

$e=3$;
$gcd(3,966) = 3 \neq 1$ chose another;
$e=5$
check $gcd(5,966) = 1$, ok.

$d = 773$ by $d = e^{-1} \bmod{\lambda(n)}$

As noted by Fgrieu on the comments, make sure that you are using efficient methods. For example;

For finding prime numbers probabilistic Miller–Rabin primality test, should be enough. Note that Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations.
For modular multiplication there are various chocies as  $2^k$-ary sliding window algorithm used by GNU GMP, left-to-right or right-to-left modular multiplications.
Modular inverse by the extended-gcd algorithm.

Calculating with Wolfram Alpha
One can use the highlighted text to enter at WolframAlpha with your paramaters:

$\lambda(n):$   CarmichaelLambda(2021) result is 966
$gcd(5,966):$   gcd(5,966) result is 1
$d:$            5^-1 mod CarmichaelLambda(2021) result is 773
encrypt $m=65:$ 65^5 mod 2021 result is c=168
decrypt $c=168:$ 168^773 mod 2021 result is 65

Note: if you are using textbook RSA then change CarmichaelLambda() with phi()


Finding the IV values of SHA-256 given all message blocks

With the question as asked, no, there it is not possible to recover the missing part of $h_0^0,h_1^0,\ldots,h_7^0$ faster than brute force search.
The question states:

$\operatorname{SHA256}_{w}^{-64}(h_0^{64},h_1^{64},\ldots,h_7^{64})=(h_0^0,h_1^0,\ldots,h_7^0)$ can be constructed analytically

Most probably, this not even a function, because the true SHA-256 compression function $\operatorname{SHA256}_{w}$, hereafter $F$, is most probably not a bijection, hence $F^{-1}$ not a function, due to the construction of $F$ as
$$\begin{align}F: \{0,1\}^{256}&\longmapsto\{0,1\}^{256}\\
h'\quad&\longrightarrow\;F(h)\;\underset{\text{def}}=\;G(h)\boxplus h\end{align}$$
where

$h$ denotes vector $h_0,h_1,\ldots h_7$ assimilated to a 256-bit bitsring from $\{0,1\}^{256}$
$G$ is a bijection, fully determined by the 512-bit padded message block (taken from $w$) at this compression step, and the specification of SHA-256. $G$ is essentially a 64-rounds block cipher with known sub-keys. A useful mental model of $G$ is an arbitrary bijection of the set $\{0,1\}^{256}$.
$\boxplus$ is addition modulo $2^{32}$ of 32-bit words, a regular group operation of the set $\{0,1\}^{256}$.

Knowing $h'=G(x)\boxplus h$, we know no method to find unknown $h$ better than brute force search, and there's demonstrably no better one under the simple model of $G$ as an oracle implementing an arbitrary bijection.
If we additionally know part of $h$ [e.g. $h_7$ as in the question for the first compression step, or even $h_1,h_2\ldots,h_{7}$ ], the best that it does is simplify slightly the combinatorial problem we face, but again the best known method to solve it is essentially brute force, and demonstrably so under the random oracle model.
Therefore, even if the question was asked for a single compression step and the full output known, there's no known method to solve it more efficiently than searching the unknown input bits, with cost $\mathcal O(2^n)$. More compression steps make the situation even more hopeless.

This late comment introduces a radical variant with the compression function simplified to $F=G$. Now $F^{−1}$ is a function, easily computed by inverting each of the 64 rounds in $G$ in reverse order.
Wikipedia's compression main loop pseudocode:
for i from 0 to 63
    S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch := (e and f) xor ((not e) and g)
    temp1 := h + S1 + ch + k[i] + w[i]
    S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    maj := (a and b) xor (a and c) xor (b and c)
    temp2 := S0 + maj
    h := g        g := f        f := e
    e := d + temp1
    d := c        c := b        b := a
    a := temp1 + temp2

can be inverted as:
for i from 63 downto 0
    S1 := (f rightrotate 6) xor (f rightrotate 11) xor (f rightrotate 25)
    ch := (f and g) xor ((not f) and h)
    S0 := (b rightrotate 2) xor (b rightrotate 13) xor (b rightrotate 22)
    maj := (b and c) xor (b and d) xor (c and d)
    temp2 := S0 + maj
    temp1 := a - temp2
    a := b        b := c        c := d
    d := e - temp1
    e := f        f := g        g := h
    h := temp1 - S1 - ch - k[i] - w[i]

Note: when going backward, S1, ch, S0, maj and temp2 are computed from different variables using otherwise the same formulas as forward; and temp1 (resp. d and h) are computed by reversing with basic algebra the formulas used to forward-compute a (resp. e and temp1).
If we knew the whole output $h^{64}$, we could efficiently walk back from it to $h^0$ with 64 evaluations of the $F^{−1}$ functions determined by the 64 known fragments of $w$, as efficiently as hashing forward. The partial knowledge of the IV would be of little help.
But in the question we only know $n$ out of 256 bits of $h^{64}$. The best attack is educated brute force as suggested in the question, with a cost of $\mathcal O(2^{\min(n,256-n)})$. This is obtained by searching unknown input bits for small $n$, and unknown output bits for large $n$. Argument: the whole chain of (modified) compression functions forms a bijection, and in the random oracle model for that the best attack is such brute force.


Bob has an EC key pair. How can he receive a small integer in the least compute intensive way?

Suppose there are many different Alices: Alice 0, Alice 1, Alice 2, etc.  Suppose each Alice sends Bob not just one number, but a lot of numbers.

Bob has a secret Diffie–Hellman key $b$ and a corresponding public key $B$.  The $i^{\mathit{th}}$ Alice has a secret key $a_i$ and a corresponding public key $A_i$.  For some subset of Alices, Bob additionally stores a cache mapping $A_i$ to the shared secret $k_i = \operatorname{DH}(b, A_i)$.

For the $i^{\mathit{th}}$ Alice to transmit a number $m$, she generates a nonce $n$ uniformly at random and sends $A_i \mathbin\Vert n \mathbin\Vert c$, where $c$ is the authenticated encryption under key $k_i = \operatorname{DH}(a_i, B)$ of $m$.  When Bob receives $A_i \mathbin\Vert n \mathbin\Vert c$, he consults his cache to find $k_i$ from $A_i$, or computes $k_i = \operatorname{DH}(b, A_i)$ if it's not cached, and caches the result, with some cache eviction policy if you want to limit the cache size.

This way, if there are $\ell$ different Alices, Bob is required to compute only $\ell$ different DH computations—no matter how many numbers he may be receiving.  Depending on the cache eviction policy, he may need to recompute some of them from time to time.  With a good cache eviction policy, if the number of numbers received is much greater than $\ell$, you can save a lot of computation.

The NaCl crypto_box API enables this by separating the per-peer DH computation, crypto_box_beforenm, from the per-message authentication and decryption, crypto_box_afternm.  The control flow looks something like:

unsigned char k[crypto_box_BEFORENMBYTES];
unsigned char m[...];

if (!probe_cache(theirpub, k)) {
  crypto_box_beforenm(k, theirpub, mypriv);
  store_cache(theirpub, k);
}
if (crypto_box_afternm(m, c, clen, n, k) == -1) {
  bad();
}

You may have to be careful transferring key material intended for Ed25519 to the X25519 computations in NaCl crypto_box—figuring out how to do that safely, like XEdDSA does the other way around—is left as an exercise for the reader.


Encrypt UDP packet with time-generated encryption key

Setup a DTLS proxy that invokes your server program to respond to requests should work. You don't need to put security and functionality in a single monolithic bundle.

This is called the Unix philosophy - write multiple programs that works together instead of trying to solve everything at once.

I don't know about NodeRTC you've mentioned in the comment, but there's another archtypical program called "ssh" we use everyday. At its minimal, it's a program that establishes secure channels between client and server, the channels can carry anything from stdio, tty, x11, to just any data. (which by the way is much easier to setup than a DTLS proxy if you may consider).

SSH saves its configs and keys in local files protected by permissions - had it been encrypted, it can't automatically start itself and would require user to input passphrase.

Since this site is about cryptography, the software part of the question should be kept out or it will be off-topic.


Why do we only encrypt nounce + counter in Counter Mode?

This should prevent flipping a bit without destroying the entire
  block, right?

Yes it does that, but at the cost of loosing security similar to ECB.

So let's go through through the security game for eavesdroppers and for the sake of simplicity choose $n_1=0$ and $n_2=2^{32}$.

The challenger generates a key $k$.
The adversary generates two messages of the same length $m_0=m\parallel (m+1)$ and $m_1=m\parallel m$ for an arbitrary choice of $m$ and submits them.
The challenger encrypts them and returns $c_b=n_b\parallel \operatorname{CTR'}_k(m_b)=n_b\parallel c'\parallel c''$ for a uniformly chosen $b\in\{0,1\}$.
The adversary checks whether $c'=c''$, if yes, 0 is returned, else 1 and this answer is always right and thus security against eavesdroppers (!) is fully broken.

While the above is nice and simple, it requires predictable nonces to work. A variant for unpredictable nonces has been suggested by fgrieu in the comments, with the following modifications to the above:

$m_0=0\parallel 1 \parallel 0$ (that is the first and the third block are all-zero, the second block has only the LSB set) and $m_1=0\parallel 0\parallel 0$ (that is three all-zero blocks)
The encryption now is $c_b=n_b\parallel c'\parallel c''\parallel c'''$
The adversary now returns 1 iff all three $c',c''$ and $c'''$ are pair-wise different, else the adversary returns 0.


Perl DES PCBC as protection against decryption/crypt analysis

This is actually a good question, about how a mode of operation will affect analysis of a data stream.

In regards to an implementation of AES-PCBC, if you have AES-ECB you can build a wrapper for PCBC around it with the appropriate block size. It is not too difficult, but unnecessary...

In regards to security analysis, PCBC is no more resistant than CBC with an unknown Initialization Vector, since upon decryption the only difference between the modes is that the previous block input is only 1 value.

This will make decryption slower since it can not be decoded in parallel, but brute forcing the key space CAN be done in parallel. Once the correct combination of mode input and key are found, the entire remaining data stream will be correctly decrypted. The brute force of the IV/prior block is faster than the key, since no key change is required. DES is a 64-bit block, which means it has a small IV, and that makes your Key/IV search combination theoretically feasible with appropriate hardware (not now, but in the future yes).

The error propagation aspect of the mode was desired before widespread use of message authentication codes, modern cryptography sees error propagation through a mode as unnecessary. There are other applications that may prefer error propagation, but data at rest is not one of them. The downsides of error propagating modes (mostly performance) do not make up for any perceived advantage in security.

A bad mode is bad, but a good mode does not make a good cipher any better, and DES just isn't good enough anymore.


eXtended Merkle Signature Scheme (XMSS) vs Leighton-Micali Signature (LMS)

I'm asking this in the context of my article here.

I don't see how your article has any reference to stateful signatures at all.

In any case, the differences are:

They have provable security in different models; XMSS in the concrete model, LMS in the random oracle model
LMS is about 3 to 5 times faster than XMSS (assuming that the messages are short)

I suspect that, if you use a stateful signature scheme in a block chain solution, neither difference is that significant.

The two standards also allow different sets of tree heights/Winternitz parameters, but there's nothing inherent in the two ideas to restrict things. I'm pretty sure that if have your heart set on one parameter set that works great for your application, you can ask the authors for it.


How can I generate cryptographic-quality 1/f noise, aka “pink noise”?

The problem with answering this question as posed is that one would need to have a definition of "cryptographic quality" that applies to 1/f noise.  You'd need to talk about something like how many data points an intelligent adversary would need to observe to be able to distinguish your pseudorandom 1/f noise generator from truly random 1/f noise.

I suspect there isn't such a thing—in cryptography people normally want to transform non-white noises into white, not the other way around!  If you're designing, say, a stream cipher, it'd be catastrophic if keystream bytes are closely correlated to their neighbors!

But to me it doesn't sound like your question is fundamentally cryptographic, but rather statistical, in that you'd be happy with an insecure solution as long as it passed certain statistical tests (that you don't define):

  All the references to 1/f noise I can find are from the audio/dsp world where they tend to use very crude approximations to convert white noise to 1/f noise which would introduce unwanted patterns.

Without describing the patterns that you're seeing, it's hard to say anything.  But from previous experience, the challenges I've seen with simulating 1/f noise on a computer are:

You're generating samples, so there's a Nyquist frequency, and no energy above it no matter what you do.
1/f noise has progressively greater energy the lower down you look in the frequency spectrum.  Audio guys have the advantage that humans can't hear below 20Hz, so they come up with algorithms that have a lower frequency cutoff.

I've had decent success with the randomized algorithm from this page (the randomized but unweighted version), as long as the number of octaves fits the application. But I can tell that the upper octave in that algorithm is consistently a bit whiter than it should be.

Other than that I think the best I can do is suggest that you look at publications from the time and frequency field instead of audio/DSP.  For example, the NIST Time and Frequency Division has a lot of freely-available publications, some of which may be relevant:

http://tf.boulder.nist.gov/general/pdf/5.pdf
http://tf.boulder.nist.gov/general/pdf/190.pdf
http://tf.boulder.nist.gov/general/pdf/29.pdf
http://tf.boulder.nist.gov/general/pdf/2795.pdf

You should have better luck with the time and frequency literature because they don't have a 20Hz cutoff escape hatch like the audio people do.


I'll assume that you have many clients talking to a single server (having many servers would only tend to exacerbate the differences). With raw public keys, the server has to have the public key of each client handy. Exposure of these public keys may be a privacy violation, but does not compromise the confidentiality and integrity of the communication. With pre-shared keys, the server has to have the secret key of each client handy. Exposure of these secret keys makes it impossible to communicate securely with the clients (unless you have an out-of-band protocol to revoke the key and generate a new one). This gives public keys a huge security advantage.

I do not recommend using pre-shared keys except in a small network where the pre-shared key is generated during an enrollment phrase for very limited client devices on which asymmetric cryptography is unrealistic, and either the loss of a client is not a big deal or all the devices are in the same physical area so a physical compromise of a single client is not a relevant threat.


Why is 128-bit considered "medium term" security?

Why is 128-bit encryption considered good enough for medium term
  security only?

Because in the long term it is expected that mankind will be able to carry out $2^{128}$ operations because it's not physically as impossible as $2^{256}$ operations.

  Quantum computing or brute force attack?

Assuming quantum computers work at a speed comparable to classical computers nowadays, they can break 128-bit encryption using $2^{64}$ operations (Grover's algorithm) which is considered feasible in the long-term, of course this should be considered additional to classical brute-force which may also be feasible at some point.


Blowfish encryption with different keys produces same ciphertext

It looks like the library is treating the string as the key to Blowfish, which has a veriable key size; the way the keysetup is done (with a cyclical use of the key bytes, see more details on the Wikipedia page) implies that key $k$ of length $n$ and key $k||k$ of length $2n$ have the same expanded key and thus an equivalent encryption/decryption function. Your "Test" example also illustrates this.

Usually from a string a key is "derived" using a KDF, which is then input to an algorithm that accepts keys of some fixed sizes like 128 bits etc. But Blowfish can accept 1 byte keys, and 300 byte keys too, so libraries often don't do this an accept the key input 'as is', without KDF being compulsory. Or they "pad" a string like 'Test' to 16 bytes with 0-bytes etc. Be sure you know what a library does before using it. Keys should be random and unpredictable, not dictionary words.


bcrypt collision probabilities assuming same password and work factor?

What is the likelihood of 2 bcrypt hashes colliding if they use the
  same work-factor and input?

You're describing this: $\tau_1,\tau_2=\text{bcrypt}(pw,cost), \Pr[\tau_1=\tau_2]$. This means that the collision probability comes down to the length of the salt. bcrypt uses 128-bit salts. So you expect to find a collision after doing roughly $2^{64}$ hashings (assuming you're PRNG is good).

If you really want to find a collision, $2^{64}$ is feasible. Especially if you'd use FPGAs / ASICs. The practical relevance of this is low though as you rarely see password database (with the same password) beyond $2^{35}$ and even then collision resistance isn't an all that important property of password hashing (what can you do if the tags collide?).


How to compare the time of encryption, cracking and verification elliptic curve problem in the same framework？

Let $n$ be the number of points in the curve group and $p$ the size of the field. The quoted estimate for Pollard $\rho$ is $\sqrt {\pi n/2}$ which is the number of elliptic curve group operations required. To sign a ECDSA message (assuming that you already have your key pair) is an elliptic curve scalar point multiplication which takes (using windowed double-and-add) $(1+\epsilon)\log n$ elliptic curve group operations. To verify is 2 elliptic curve scalar multiplications which is $(2+\epsilon)\log n$ elliptic curve group operations. If you have to generate a key pair, that adds another elliptic curve scalar multiplication.
The elliptic curve group operation will get harder with $p$ as well and the exact complexity is subject to a range of variant algorithms. An estimate of $O(\log^2p)$ for each elliptic curve group would not be hugely inaccurate though.