Deterministic outputs based on non-connected inputs

"public shared data" $\:$ = $\:$ the ordered pair whose entries are

[a key for a full-domain statistically injective PRF] and [a signature verification key]

$\hspace{.04 in}f$ is an arbitrary one-way function.

For each positive integer $j$, [$o_j$ is the value of the PRF at $j\hspace{.03 in}$] and [$i_j$ is [[the signature for $o_j$] concatenated with [the string of zeros whose length equals the length of that signature]]]

and $\hspace{.04 in}f_j$ is given by

if $\hspace{.04 in}f_j$'s input has even length and its left half is a valid signature for $o_j$

and its right half is all-zero then output $o_j$ else output $\hspace{.04 in}f$ of $\hspace{.04 in}f_j$'s input.


Worst-case one-way functions exist if and only if P ≠ NP, therefore, if I were you, I would not expect to get a definitive answer to your question any time soon :).

On the other hand, if you are willing to assume that P ≠ NP, then it is not hard to construct such a function (that is actually exactly a half of the proof of the theorem I stated in the previous paragraph).


Is XORing a random stream of bytes a secure way to obscure a file?

XORing a plaintext with a random stream of the same size is a secure way to encrypt it. A stream cipher works in this way.

The issue in your design is the random source. If the random stream does not have the security properties one expects, the systems is not secure.
In your implementation, the seed has the role of the key (and potentially the initialization value) of a regular stream cipher.

If someone can encrypt something with your method (or recover a couple plaintext/ciphertext) he will be able to decrypt every past/present/future encryption generated with the same key. Only for messages shorter than known one (but the remaining part could be guessed if the file is, e.g.:, an english text).


Request for 1024-bit primes $p$ , subgroup $q$ and subgroup generator $g$

Suitable values are
$q=2^{159}+9593, p=2^{1023-159}*q+1, g=2^{2^{1023-159}}\mod p$

I have checked the values given in section 2.1 of RFC 5114 and they seem fine too.

Whether "it's safe to use them" depends entirely on how they're being used, what you're trying to prevent, against whom and for how long and what the consequences of getting it wrong are.


Number of keys when using symmetric and asymmetric encryption?

For the symmetric key, you can approach this problem as a complete graph with order 1000. With the vertexes representing people and the edges representing the symmetric keys. Then each vertex would have degree 999 and, applying the Handshaking lemma, the number of edges would be:

$(1000 \times 999)/2 = 499500$

So they would need 499500 symmetric keys to have a secure communication between all of them.

For the asymmetric keys, each one would have 2 keys, so a total of 2000 keys.


Is there anything wrong with swapping SHA2 for Keccak for use in PBKDF2?

There are 2 main issues. Performance and implementation.

Performance

The performance issue is from an attacker-defender scenario, where the attacker is able to provide FPGA or ASIC resources. In this scenario, Keccak is several times faster than SHA-2. I will use a Blake comparison for SHA-256, as they perform similarly. Both Blake and SHA-2 are ARX type hash functions.

STM 90nm ASIC
Keccak-256 = 33333 Mbit/s @ 51 Kgates, Blake-256 = 4763 Mbit/s @ 37K gates, a 7X performance advantage with a 37% area disadvantage, 5.1X overall advantage

UMC 90nm ASIC
Keccak-256 = 43011 Mbit/s @ 50 Kgates, Blake-256 = 6966 Mbit/s @ 47.5K gates, a 6.17X performance advantage with a 5% area disadvantage, 5.86X overall advantage

Xilinx Virtex 5 FPGA
Keccak-256 = 12817 Mbit/s @ 1272 slices, Blake-256 = 2245 Mbit/s @ 1523 slices, a 5.7X performance advantage with a 20% area advantage, 6.83X overall advantage

It can be seen an attacker with hardware resources has a performance advantage of 6 times on average vs Blake. In software, Keccak can average half the speed of SHA-512 at the same security level, and can be faster vs SHA-256. This is dependent on the message size, as the block sizes are not the same.

Newer processors will also contain additional instructions to improve the performance of SHA-256 hashing, the level of improvement is yet to be determined.

Implementation

The main implementation issue is centered around the design and purpose of HMAC.

HMAC is designed specifically for MD type hash functions like SHA and MD5. Its purpose is to change the initial values to something other than those in the specification. MD type hashes work like a block cipher, with the message the key, and the initial values the plaintext. The ciphertext is then the hash digest. With longer messages, the cipher works in OFB mode, with a key change. The final ciphertext block is then the hash. HMAC works by cycling $[key \oplus ipad]$ for 1 iteration to get a new secret IV, then it processes the message. The output is then processed as the new message using $[key \oplus opad]$ to generate a different secret IV.

Keccak is not an MD type hash function, so the entire purpose of HMAC is lost. Keccak works using the sponge construction with a large internal state. The general rule is to simply prefix the message with the secret key in order to create a keyed hash construction. It is suggested that this would actually be stronger than HMAC because of the large internal state that is kept secret, vs HMAC where an attacker can see the entire state unless there is truncation.

Using Keccak in an HMAC construction is of course possible, but will be much slower than key prefixing, and may not have a security advantage.

The other implementation issue is with code size. On 32-bit systems, SHA-256 will have a massive advantage over Keccak, since blitsliced Keccak is larger and more complex. On 64-bit systems, SHA-512 is a better fit, and Keccak in native 64-bit code is quite compact. The fact that the round constants can be derived at runtime is an advantage, but is usually only used when small code is required, such as an RFID card.

NSA

I hesitated putting this section here, but since the comments on the question are a hot topic, I figured it would be pertinent.

Just because the NSA designed something, does not mean it is bad, or secretly backdoored. The NSA is not some super boogeyman, the employees are human beings, and their computers need to obey the laws of thermodynamics. They can not easily sneak something by the cryptographic community. Almost everyone suspected Dual_EC_DRBG was tainted, and advised against its use, even before it became a standard. The only reason it got used was either bribery or incompetence.

I know nobody who suspects the same about SHA-2. Additionally, SHA is one of the most widely studied hash families, with decades of analysis by cryptographers all over the world, including the Russians, Chinese, Iranians, etc. It has stood the test of time better than MD5 and RIPEMD. The only exploitable issues are those common to all MD type hash functions, and if used in HMAC they are mostly irrelevant. SHA-2 is used by the US government to protect state secrets from its enemies, confidently.

If you want to use PBKDF and still don't trust the cryptographic community's view on SHA-2 and all the public analysis for whatever reason, use Blake-512 instead. It has far inferior attacker advantage numbers, excellent software performance, and well analyzed security. I am a fan of truncating the output, I would only keep 256 to 320-bits.

  I am postulating that SHA3 may preserve the entropy in the salt and password better than SHA2

Not enough to compensate for the performance advantage of an attacker, if that is even the case..


Zero knowledge-proof for discrete log that is not honest-verifier

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is only HVZK.

Another answer is to reduce the size of the challenge space from $p$ (the group order) to $\log(p)$. This gets you full ZK, but your soundness error drops to $\frac1{\log(p)}$ too so you have to repeat the whole protocol $O(\log(p))$ times to get the same soundness as one HVZK Schnorr execution. This repetition doesn't destroy your ZK property however.

Jan Camenisch's work contains a good description of these issues if I remember well.


Your property of what I would call "improvable" is actually considered undesirable for PoWs. It would allow a prover to make continuous progress
toward a solution that satisfies the difficulty threshold. Which would
mean that a prover that's twice as fast as another, has more than double
the chance to win the race, which is considered unfair. Being twice as fast should just double your expected wins.

So in fact a PoW should be what is known as "progress free",
which would seem to require not having your property.


How to generate a permutation of n numbers using secret sharing scheme?

If you are just lacking a function from some random number to permutations, this is easy:

Consider the set of all permutations of $\{1,\dots,n\}$, put them in lexicographical order and assign natural numbers. There are $n!$ permutations, so let's say $x$ is some random number from $\mathbb{Z}_{n!}$, and here's an algorithm how to get the matching permutation:

Generate list $L = [1,\dots,n]$ and empty list $O = [\;]$
$a = (|L| - 1)!$
$b = \lfloor x / a\rfloor $
Remove $L[b]$ from $L$ and append it to $O$
$x = x \mod a$
if $L$ is not empty: GOTO 2.
output $O$

List indices are starting from $0$ as usual.

It wasn't stated in the question from which set the private inputs were taken, and ideally this would be from $\mathbb{Z}_{n!}$ (or alternatively $\{a, a+1, \dots ,a + n! - 1\}$). Then all you need is to use MPC to calculate the sum $x = s_1 + \dots + s_n \mod n!$, and use above algorithm to calculate the matching permutation. If the entropy of the inputs is not enough, use can use a PRG to expand this input and use $s'_i = PRG(s_i)$ instead (for party $P_i$).


Design for file transfers to a new party

Point 1 since I figure some form of user input would be good, otherwise it's basically just a random key and doesn't require any previous knowledge so anyone can generate it.

Nothing wrong with that. A long random value is the best kind of key there is, much better than anything dependent on user input.

However, as mentioned in the comments, the key material must be from a secure RNG. If you generate the UUID as e.g. a 128 or 256-bit random number using OS randomness, you should be fine.

  Point 6 since it's an out-of-bounds method which likely means they'll likely e-mail or sms in cleartext potentially defeating the whole encryption.

You cannot avoid this. The recipient must know everything needed to request the file, so anyone who finds out what they know will also be able to do the same. By making download links work only once you can at least prevent silent compromise.

(Some sort of email confirmation could also require a compromise of the email specifically, rather than just any random out-of-band channel used. Coupled with warning "do not use email for sending UUID" you have a light 2FA-like system.)

  Point 7 since at that point my server will know the unencrypted file, which I'd like to avoid.

The server does not necessarily need to know it, only the client program. I.e. you can make the user download a generic client that asks for the UUID and identify the file using some derived information. E.g. derive encryption key from the UUID $u$ using $H(u, \text{e})$ and file identifier using $H(u, \text{i})$, then send the latter to the server with the encrypted file. The server will be unable to find $u$ or the encryption key.

Of course, you can always offer a malicious client program anyway, so the server must be trusted.


what exactly are the tradeoffs made when choosing between the two, or
  choosing other sizes?

The triangle of performance , area and security. Smaller sboxes requires less resouces for implementation but it comes with lesser cryptographic properties (compared to larger size) therefore higher number of rounds to achieve minimum security requirement for the cipher (higher number of rounds , lesser speed performance).

One method used to merge the benefits of smaller and larger boxes sizes by constructing larger s-boxes from smaller s-boxes such as one of Clefia cipher sboxes, skinny etc. This type of construction allows implementation of 4-bit (for example) goes into "mini-cipher" structure to generate 8-bits boxes . The resulted 8-bit sbox has higher cryptographic properties but not as good as AES s-box.

Most of block ciphers come in 64 or 128 bit size  which is divisible by 4 or 8  and friendly to software implementation( minimum cpu register size is 8-bit).

However , I have seen other sizes mostly in authenticated encryption , for example , FIDES is the first cipher that uses 5-bit (almost bent) and 6-bit (APN) s-boxes due to their optimal differential and linear probability.moreover , with bitslice implementation of butterfly APN s-box  is advantage  ref

Ascon uses 5-bit sbox but they claim because of mathematical and threshold-implementation properties.


Secure Deduplication and Encryption in a data store

If Alice, Bob et al. can share a secret, for example, using some sort of key exchange protocol, it is possible to use convergent encryption in a way that fulfills the requirements. Otherwise it probably isn't.

First, assume the users know a secret key $s$. They use convergent encryption with the  key derived using $s$. For example, $k = \operatorname{HMAC}_s(\operatorname{HMAC}_s(p))$ and $c = (\operatorname{HMAC}_s(p), E_k(p))$ to encrypt plaintext $p$. $E$ could be AES in a suitable mode.

To upload a file, Alice calculates $\operatorname{HMAC}_s(p)$ and checks if the store has it. If it does, no need to transfer again, she is done. If it isn't, she uploads the encrypted file so that it can be queried using $\operatorname{HMAC}_s(p)$ which she stores as $key$. Bob goes through the same process.

Eve knows they have uploaded the same file, but knows nothing else. She cannot test if the file is $A$ because she does not know $s$. Neither can she decrypt it.

Now, assuming sharing $s$ is not possible:

  Eve wants to know who inserts file A, and has a copy of file A as well as read access to the whole store and connection sniffing on all other users

This implies that $f$ must not send the same thing over to the store when Eve sends $A$ as when Alice does. Otherwise Eve could simulate $f$ and compare the traffic to Alice's. The store can also not deduplicate the data in any way, because it has no more information than Eve does.

Thus, this is impossible:

  Is there a suitable definition for f and g that:

  Doesn't store A multiple times
  Doesn't let Eve know that Alice and Bob inserted file A.

So $f$ must store duplicate copies, and must give each user a different access key. Now, assuming that's the case and Joe has Alice and Bob's keys:

  Can Joe deduplicate the two copies of A:

  Without Eve knowing who has A?
  Without causing future retrievals of A by Alice or Bob reveal that they have A.

Joe could be allowed to say replace one of the copies with a pointer to the other + some token that allows that user to decrypt the first copy (e.g. $E_b(a)$ where $a$ is Alice's key to $A$ and $b$ Bob's). However, Eve would now know at least that the two files match.

In this case $f$ would just be encryption with a random key $r$, and $key$ would include both that key and some identifier that $g$ would use to request for the data.


Is MD5 particularly vulnerable when given multiple MD5 hashes using a common, secret suffix?

is there a better than brute-force way of finding the value of suffix?  Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this?

The best attack better than brute-force I could found is described in this paper, it has a complexity of 2^123.4 and a memory complexity of 2^45×11 words. AFAIK this is not practical

  Or, equivalently, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

This is not equivalent to your first question. Your first question is a preimage attack, meaning finding the original value (prefix + suffix) that generated the hash.

This question can be interpreted in two ways:

You're asking for an algorithm that can generate a second pre-image, meaning a second value different from the original one that produces the same hash. In this case there is no known second pre-image attack against MD5
You're asking if it's possible to find a collision for a given hash using a fixed part in the message. To this question I only know there are algorithms to efficiently find collisions for a given MD5 but I don't know if those methods can be adapted to use a fixed part in the message (The suffix)


Is it possible to compress random sequence with high entropy

Random data can not be compressed. Good pseudo random data can not be compressed(with generic algorithm).
As Paul commented if you use an inefficient encoding such as hexadecimal or Decimal ASCII characters you are using a full 8 bit character to represent less information. Hexadecimal is compressible to 50% and decimal to $\log_2(10)/8$ which is approx 41%.
If your data is in binary or compresses significantly more than the inherit encoding used.  This is a significant flaw in your random number generator.
A compression test with a Lempel-Ziv based compression algorithm is a good important but not sufficient test. It essentially tests for repeating sequences of arbitrary length. So it can find all sorts of biases in your algorithm.

However for cryptographic security, the chances your homegrown algorithm is secure are slim even it passes all generic statistical tests with flying color.


What's the maximum length for AAD in GCM?

From the GCM specification:

  Additional authenticated data (AAD), which is denoted as A. This data is authenticated, but not encrypted, and can have any number of bits between $0$ and $2^{64}$ .


How does Dragonfly key exchange work, in non-white-paper terms?

Dragonfly is resistant to dictionary attacks, meaning that rather than an attacker being able to identify the use of a password in their dictionary with passive computation, they are forced to interact with one of the parties to make guesses.

Actually, the goals are a bit more than that; even if you have an active attacker that can either modify the exchanges taking place, or can impersonate one of the end points (and attempt to negotiate with someone who does know the password), the best they can do from $N$ exchanges is to test $N$ entries from their dictionary.
We know that such an adversary can do at least that much; with a single exchange, they can take an entry from the dictionary, and (assuming that entry is the password) perform the exchange honestly with the valid endpoint, and see if the exchange fails or not.  The goal of a PAKE (such as Dragonfly) is that they can't do any better than that generic attack.

How do Dragonfly's properties arise from the arithmetic? Is it some property of the "hunting-and-pecking" that only the non-attacker parties can perform the computation?

No, the hunting-and-pecking procedure $P = \text{HuntAndPeck}(\text{Password})$ is a public method of mapping a password to a 'group element' so that:

The group element $P$ generates a prime sized subgroup; that is (using Finite Field terminology) the values $P^x \bmod p$ (for various values of $x$) can take up exactly $q$ values (where $q$ is a large prime).

For two different passwords $\text{Password1}$ and $\text{Password2}$, the two values $P1 = \text{HuntAndPeck}(\text{Password1})$ and $P2 = \text{HuntAndPeck}(\text{Password2})$ are unrelated; that is, no one knows the value $x$ for which $P1^x \equiv P2 \pmod p$.

Instead, the PAKE properties arise from the actual protocol.
The RFC format is a horrid way to describe cryptography, and so here is the protocol in a nutshell in the honest case (still using the Finite-Field terminology, and eliminating sanity tests both sides run):
Alice and Bob run the Hunt-and-Peck procedure to convert their password into a group member $P$ (and since this is the honest case, we'll assume they have the same password).  Then, Alice picks random values $p, m$, and transmits the values $s = p + m \bmod q$ and $E = P^{-m}$, and sends those to Bob.  Bob also selects values $p', m'$ and sends $s' = p' + m' \bmod q$ and $E' = P^{-m'}$ to Alice.
Alice then computes $(E' \times P^{s'})^p$; this is $(P^{-m'} \times P^{p' + m'})^p = P^{p p'}$.  Bob does the same computation, and gets $P^{p' p}$, which is the same value, and so we have our shared secret.
Now, why is this secure?  The attacker is allowed to submit any $s', E'$ value it wants to Alice (subject to the sanity test that Alice runs); however (because of how the hunt-and-peck procedure works), he does not know a value $E'$ where he knows the values $x, y$ for $E' = P1^x$ and $E' = P2^y$ for two different passwords; hence if he can predict the value $(E' \times P1^{s'})^p$ for $P1$, he cannot know the value $(E' \times P2^{s;})^p$, and so he is effectively limited to testing one password (which we know he can do).
One final note: reviewing the Dragonfly RFC, I see that it would (as written) leak some information if you run in on an elliptic curve that doesn't have a prime number of points (that is, has a cofactor $h > 1$).  If you're using (say) the NIST curves, that's not an issue; if you try to adapt it to run over (say) Curve25519, that would need to be addressed...


Understanding SSL vulnerability within Apple's GOTOFAIL

I am not quite sure which portion of the SSL Key Exchange protocol this belongs to.

The webpage you link to shows this call in a function named SSLVerifySignedServerKeyExchange. Given that ServerKeyExchange is a message in the SSL/TLS handshake that is normally signed (except for "anonymous" suites that don't authenticate the server which are rare), I'll go out on limb and guess that function does the verify logic for a signed ServerKeyExchange in SSL (and TLS). Especially since the full code performs exactly the logic specified in the protocol standards through TLSv1.1 for verifying a ServerKeyExchange (except for the bug).

  It seems like it is trying to verify the public key, date signed, and signature, however I don't think I can recall any portion of the SSL protocol with these three components in one transmission.

It is using the public key to (try to) verify the signature on the data signed, which has nothing to do with any date. If you look at the preceding code, dataToSign and dataToSignLen are the address and length of space that at this point contains (or would without the bug) for RSA concatenated MD5 and SHA1 hashes of (apparently) clientRandom serverRandom and signedParams, or for DSA or ECDSA the SHA1 hash. This is exactly the computation specified by TLSv1.1 et pred modified by TLS-ECC. The clientRandom serverRandom and signedParams come from outside this function so we'd have to look elsewhere to be 100% certain they are correct, but it seems very unlikely the programmer(s) would have used exactly the names in the protocol standards for something different.

The server public key is part of its certificate, which was received in the prior server Certificate message. The signature is part of the current ServerKeyExchange message. The actual data to sign is the hash(es), which are computed from the signed params which are in the ServerKeyExchange message and the client random and server random where were in the prior ClientHello and ServerHello messages respectively.

  As this is known to deny the certificates, it would make sense that this portion came across before(or during) the time when server sends the certificate over to the client

That's backwards. This bug causes the client to accept the server signature as valid, and thus the server as authentic, even if the signature is forged by an imposter that does not have (and use) the correct private key. Since it uses the public key from the server cert, it must come after the server cert is received (and usually validated) and ServerKeyExchange does come after server Certificate in the handshake sequence.


No IV for one off symmetric file encryption

As already mentioned by fgrieu in a comment, you seem to be mixing up the initialization vector for the cipher with the salt for the key derivation. They play similar roles — both are here to insure that different values of the IV/salt lead to different keys/ciphertext — but they are used in different ways and they have different security properties in this scenario.

When you generate a key from a password, the number of likely passwords is far less than the total number of possible keys. A pretty good password may have 44 bits of entropy; a password used in the wild tends to have a lot less. Compare to 128 bits of entropy in a randomly-generated AES-128 key. This makes the key space vulnerable to brute force search (“I'll derive the key for password1 and try to decrypt. Nope. swordfish? Nope. Tr0b4dor&3? Nope. Tr0b4dor&4? Win!”).

In order to mitigate this problem, deriving a key from a password must include two elements:

Slowness, because spending .1s instead of .1ms to derive the key when the user types his password isn't a performance problem, but it multiplies the work needed by an attacker by 1000.
Uniqueness, so that an attacker cannot precompute all the keys derived from likely passwords and then crack a lot of password-encrypted files by a simple table lookup.

The issues are the same as password hashing — and indeed most password hashing schemes are password-based key derivation algorithms.

To derive a key from a password, you need a password-based key derivation function, which includes a step of key stretching for slowness and uniqueness. The salt, which provides uniqueness, is an input to the KDF, alongside the password. bcrypt, PBKDF2 and scrypt are the three recommended password-based key derivation algorithms nowadays; scrypt has the nicest properties (it's less easy to brute-force with dedicated hardware) but is still a bit new.

The salt must be unique for everybody who uses the same KDF, not just among your files. The best way to ensure this is to have a sufficiently long random salt.

All message encryption algorithms use an IV or nonce to ensure that if you encrypt the same message twice, this isn't visible in the ciphertext (at least the algorithms that are semantically secure — it is occasionally useful to sacrifice this property in the interest of deterministic encryption but that applies to specialized scenarios). If you only ever encrypt one message with the same key, you don't need an IV — the standard thing to do in this case is to use an all-bits-zero IV.

If you only ever encrypt one file with the same key, you don't need an IV. Do consider that if you use the same key for multiple versions of the file, you should use an IV. You may want to derive a new key with a new salt in this situation, though.


$\chi^2$ measures the uniformity of a sample distribution. It's commonly used to test samples for randomness (I don't want any hassle on this), to do with true and pseudo random number generators. Uniformity is absolutely necessary for cryptography which you can  read about elsewhere herein.
E.g.
$dd if=/dev/urandom of=/tmp/urandom bs=1000 count=1000

$ent /tmp/urandom
Entropy = 7.999799 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 278.05, and randomly
would exceed this value 15.37 percent of the times.

Arithmetic mean value of data bytes is 127.3541 (127.5 = random).
Monte Carlo value for Pi is 3.141468566 (error 0.00 percent).
Serial correlation coefficient is 0.000781 (totally uncorrelated = 0.0).

A mean value is about 255 for an eight bit window (byte) if a thing is randomesque, or properly encrypted. So yes, generally the thing's information entropy increases to ~8 bits/byte or ~1 bit/bit when encrypted.


Derived keys usable by threshold signatures

There are two mainstream ways of doing this. Using Schnorr or BLS signatures. The Schnorr formulations are more complex, but if you are willing to use bilinear pairings, the BLS solution is straighforward to understand.

Assuming the existence of a set of Shamir's Secrets Shares $\{(x_i, y_i) \in \mathbb{F}^2_p: i \in [1, n] \cap \mathbb{Z}\}$, where the Lagrange interpolation $L(x) = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}(x)$ and $L(0) = y$ is the secret. Normally $x_i$ are public parameters and simplified to $x_i = i$.

Defining the bilinear pairing as $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{F}^{*}_{p^{k}}$, in type-3 settings, and a hash-to-curve $H: \{0,1\}^* \mapsto \mathbb{G}_2$.

Also $y \times G \mapsto Y$ is the corresponding public key, with $G,Y \in \mathbb{G}_1 $.

The BLS signature is defined as:

$Sign(y, m) \mapsto \mathbb{G}_2$ with the output $y \times H(m) \mapsto S$

And verified with:

$Verif(Y, m) \mapsto \{0,1\}$, result in 1 if $e(Y, H(m)) = e(G, S)$

To transform this in a threshold scheme just apply the Lagrange interpolation directly:

$S = y \times H(m) = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}(x) \times H(m)$

From a client, you can collect $t+1$ partial signatures $y_{i} \times H(m)$ and interpolate to construct $S$. Verification is unchanged.

However, this simple procedure cannot prevent parties from sending wrong results $y^{'}_i \times H(m^{'})$. It can result in a valid signature for an unkwon message. Although this is not a big concern for most practical purposes, it's something you should be aware.


First, it's not said that AES is unbreakable, merely that none of the currently known attacks reduce the computational cost to a point where it's feasible. The current best attack on AES-128 takes 2^126.1 operations, if we had a computer (or cluster) several million times more efficient than any current computer and could operate at the thermodynamic Landauer limit, it would take 234 petajoules just to increment a counter through every key value. That's about half of the annual electricity consumption of Norway. Actually computing an AES round takes several times that much energy.

Now consider a round. A round in an optimized implementation takes 16 table lookups and 16 exclusive-or operations. Let's just say each operation is fundamental and takes the same energy as incrementing a bit in a counter, so 32 operations per round, times 10 rounds means you're at the annual electricity production of the USA.

Remember that that was with a computer operating at the minimum possible thermodynamic energy requirements. So you probably want to multiply that by a few million, at which point you're reaching the total energy from the sun which hits the earth each year.

Thus, for any practical computer the energy costs are too high, and even for a theoretical computer the costs would be large enough that it would take several years to brute force a single key, even for a very large nation.


Generating a random point on an elliptic curve over a finite field

is there an algorithm to generate a random point on the curve?

By having a good random source like /dev/urandom you can generate a random point $R$ on a curve at least by two methods;

By using random scalar and scalar multiplication

Choose a generator point $P$ on the curve
Get random integer between $0 < k < \text{Order of the Group}$
Calculate $R =[k]P$ by scalar multiplication, prefably executing by double-and-add algorithm.

Using random element with sample rejection on the curve equation.

Choose a random element $x \in \mathbb{Z_{25}}$.

Check the equation $y^2 = x^3 + x + 1$ has a solution, i.e. it is a quadratic residue.
If there is no solution return to 1. step ( reject the sample)
Else, we have two solutions, $y$ and $-y$ (or one $y=-y$). These values can be found using the Tonelli-Shank algorithm and its generalizations.

Now use the random source to select $\bar{y}$ as $y$ or $-y$, or toss a coin.

Form the random point on the curve as $R=(x,\bar{y})$

Note that, the point at infinity cannot be expressed in affine-coordinates without some tricks. Therefore, this method cannot return the point at infinity. If the point at infinity is also required on the random selection, one can select it with an initial random. Select it within $\frac{1}{\text{Order of The Group}}$ probability. Then use the above.

If you are using SageMath then it has a function
random_element() and the explanation is given as
Return a random point on this elliptic curve, uniformly chosen among all rational points.
SageMath random_element() function uses the 2. method with an addition that it can also return the point at infinity, $\mathcal{O}$

In my implementation points on this field are represented by polynomials, if that is relevant.

The $\mathbb{F}_{25}$ is an Extension Field and it is usual to represent the elements of the field by the polynomial representation which is very advantageous on operations. As a result, the coordinates of points have polynomial representation.
From comments of OP

I used Sage to calculate the order of each point: (sagecell.sagemath.org/…) and it can be seen that even though the cardinality of the group is 32 the biggest order is 16. Is it just a matter of choosing an EC with prime cardinality?

The SageMath construction is not correct;
E = EllipticCurve(GF(25, 'x'),1, 1) provides this curve $y^2 = x^3 + x + 2$ not $y^2 = x^3 + x + 1$
One can construct as below;
    E = EllipticCurve(GF(25, 'x'), [1, 1])
    print(E)
    print(E.abelian_group())
    print ( E.cardinality())
    for i in E.points():
        print (i.order())

The construction EllipticCurve(Finite Field,[a,b]) is for the standard Weierstrass from $y^2 = x^3+ a x + b$ where $a,b \in F$ in which the curve defined. You only need to provide $a,b$, and $F$. The set of points commonly represented as $E_{a,b}(F)$
The abelian_group() functionality prints the abelian group structure of the group of points on this elliptic curve. The result is
$$\mathbb{Z_3} \oplus \mathbb{Z_9}$$
One should not call this function for a large group. There is a theory behind this and this can be found in a book such as Washington's book, however, the reference can go back to J. W. S. Cassels, 1966, Diophantine Equations with Special Reference To Elliptic Curves
Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_n} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.


Is ISAAC considered secure as a cryptographic random number generator?

I had a short look at the page - it contains only some implementations, no specification.

The page ISAAC and RC4 from the same author contains some theoretical elaboration about ISAAC and its relatives IA and IBAA, but I'm not sure if this can be called specification.

Non-existence of a formal specification is a major drawback for anything which claims to be a serious cryptographic algorithm, and might be the deciding reason that nobody really looked at the security of this primitive.

So my recommendation would be to use other, better documented algorithms instead, if security is of importance (and not only speed).


How can you derive a P-256 public key from the X and Y points

There are multiple ways of encoding a EC public key in binary as well.

Probably the most compatible one is a description of the generic SubjectPublicKeyInfo as used in X.509 certificates. The encoding scheme with the ASN.1 description can be found in RFC 5480. Now you "just" need an implementation for encoding / decoding such structures (using the ASN.1 distinguished encoding rules or DER).

Note that the most compatible public point encoding is the uncompressed point encoding, consisting of an identifer byte with value 04, followed by a statically sized (32 byte) encoding of the X coordinate as unsigned big integer, followed by the identically encoded Y coordinate.

Here is the encoding of a EC key:

SEQUENCE (2 elem)
  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.10045.2.1 ecPublicKey (ANSI X9.62 public key type)
    OBJECT IDENTIFIER 1.2.840.10045.3.1.7 prime256v1 (ANSI X9.62 named elliptic curve)
  BIT STRING (520 bit) 0000010011011011100101100101010011000111100010000110001111111011011100…

Here is the hexadecimal encoding, with the X and Y coordinate shown:

30 59
    30 13
        06 07 2A 86 48 CE 3D 02 01
        06 08 2A 86 48 CE 3D 03 01 07
    03 42 00

        04

        DB 96 54 C7 88 63 FB 73 26 BD C8 2A A4 28 8F 3B
        B6 9C 96 4C B2 E1 8F 39 A4 3A 96 6F 87 2E 9C 79

        B1 F8 FB F7 84 A4 9C AF 10 17 92 4D F6 8E D7 43
        63 9F 9C 76 01 2C AC DE 86 72 7D 85 FD 23 F3 DF

As all the sizes are static, you should be able to simply create a statically sized, unsigned, big endian encoding of X and Y and place them after the header - which is anything before the X and the Y coordinates above, of course.

Possibly you may only require the encoding of the point, 04 with the X and Y coordinate following that as displayed above. That's a binary encoding as well, that can be used if the algorithm and curve is already known.

Beware that the statically encoded size of the points very much depends on the field size of the curve; this answer is therefore only valid for this particular curve.


Can we design a block cipher based on SP-network without loss of E/D similarity theoretically?

Actually, to deal with the conflict between the inverse SBOX and E/D similarity, we can just expand the original SP network into something like "$S$->$P$->(entangled with key)->$P^{-1}$->$S^{-1}$". Then we can have a E/D similar block cipher. Some standard ciphers like PRINCE were designed this way.
However, it seems that we still can not make SPN itself to be of E/D similarity so we have to place extra components in it.


Representations of secret keys on Curve25519

I'm pretty sure this is an endianness issue.  Specifically, taking the S_a value from the Josefsson draft and reversing the order of the bytes (i.e. pairs of hex digits) in it gives:

70076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c6a

which is almost the same as the value of a given in RFC 7748 § 6.1.  In fact, XORing the values shows that they differ at only four bits:

  70076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c6a
⊕ 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a
------------------------------------------------------------------
= 0700000000000000000000000000000000000000000000000000000000000040

The remaining difference seems to come down to canonicalization; in particular, RFC 7748 § 5 says (emphasis mine):

  For X25519, in order to decode 32 random bytes as an integer scalar, set the three least significant bits of the first byte and the most significant bit of the last to zero, set the second most significant bit of the last byte to 1 and, finally, decode as little-endian.

The S_a value given in the Josefsson draft appears to have this canonicalization correctly pre-applied (after accounting for the byte reversal, that is), whereas the a value in RFC 7748 § 6.1 has the three least significant bits of the first byte set to one, and second most significant bit of the last byte set to zero.

Alternatively, one could simply interpret this as a from RFC 7748 § 6.1 being the raw input sequence of 32 random bytes (written as 32 pairs of hex digits concatenated together), whereas S_a from the Josefsson draft is the corresponding 256-bit number (written as a hexadecimal integer literal) obtained after those random bytes have been canonicalized as described above and decoded in little-endian order.


What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?

I don't consider the following a complete answer, but it is a start, and best I can do with  my very limited knowledge. I hope someone could fix it or improve it.

These type of attacks are only possible against specific implementation of higher level protocols.
I will start by describing an invalid-curve attack against a specific ECDH based protocol.

Simple Pairing protocol:
Entity A wants to establish an encrypted and authenticated channel with Entity B, and both support the same pairing protocol, based on ECDH using P-224

Entity A sends its own ECC public key ($pub_A$) to B
Entity B sends its own ECC public key ($pub_B$) to A
Both devices computes ECDH, thus generating a shared point ($SP = priv_A*pub_B = priv_B*pub_A$)
Individually they run this shared point through a KDF, generating $K_{ENC}$ and $K_{MAC}$
Entity A starts communicating to B using AES CTR to encrypt the communication and AES CMAC to authenticate the ciphertext.

Let's now suppose B is malicious and wants to recover A's private key.

Conditions for the attack to succeed:

A doesnt't check if the B's public key, or computed shared point, actually lie on P-224.
Public keys are exchanged with both $x$ and $y$ coordinates and both are used in the scalar multiplication algorithm.
The scalar multiplication algorihtm doesn't use the value of $b$ in the computation (this is very common for short Weierstrass curves)

B generates elliptic curves $EC'$ over the same field $F_p$ of P-224 with the same $a$ parameter but different value for the $b$ parameter. B computes the order of those curves, and factor it, looking for small primes divisors.
Let's suppose he finds a suitable curve with order of form $17*h$ where $h$ is a composite not divisible by $17$. This means that there is a subgroup of $EC'$ with order $17$.
B finds a point of this small subgroup, calls it $pub_B$ (his public key) and sends it to A.

A will compute $SP = priv_A*pub_B$, derive $K_{ENC}$ and $K_{MAC}$ and starts the secured communication.
Note that A will in fact compute the scalar multiplication over $EC'$ and therefore $SP$ has only $17$ possible values.
In this way he finds the value of $priv_A\mod17$

He repeats the attack with other small groups having order coprime to each other (he can use several $EC'$), and then uses the $CRT$ to recover $priv_A$.

Let's now discuss the case where the scalar multiplication doesn't use the $y$ coordinate.
Premise: Hereafter I will assume that a x-coordinate only ladder can be used on the original curve and on the twist. The answer to this question explains how a twist curve can be used for short Weierstrass curves.

Now the job of B is much more complicated because he can't easily provide to A a public key on a generic $EC'$ since the $y$ coordinate is key for this, as without the $y$ A will compute the scalar multiplication on $EC$ and not on $EC'$. But, since A algorithm will work for the twist also (as in our premise) then B can use a non trivial quadratic twist of $EC$.

There is one set of isomorphic curves, each curve within the set is defined through a $c$ that is not a quadratic residue in $F_P$, by $y^2 = x^3 + c^2ax + c^3b$.
$a$ and $b$ are the original curve's parameter, and this set is the $twist$.
These curves have order different from the order of $EC$, namely $p+1+t$ where $t$ is the trace of $EC$. If the order factors in many (relative) small primes then it opens the door to an invalid curve attack, where B sends public keys lying on small subgroups of the twist.

For P-224 the order of the twist factors to:
$$3^2 * 11 * 47 * 3015283 * 40375823 * 267983539294927 *
177594041488131583478651368420021457$$
So he can use the small subgroups of orders $3,11,47,3015283,40375823,267983539294927$.
He needs to bruteforce on $K_{MAC}$ for each subgroup so this attack requires about $2^{log(267983539294927)} = 2^{47.93}$ operations to get by CRT the value of: $$priv_A \mod(3 * 11 * 47 * 3015283 * 40375823 * 267983539294927) $$
Now B can computes the actual value of $priv_A$ by Pollard's kangaroo. He uses the information he just got, limiting the search to $n/(3 * 11 * 47 * 3015283 * 40375823 * 267983539294927)$ which is about $2^{105.32}$. Due to Pollard's kangaroo complexity it requires about $2^{105.32/2}=2^{59.34}$ operations, which dominates the complexity analysis.

Note this number is close but not equal to Dr. Bernstein's number of $2^{58.4}$ operations.
In this page he shows that he calculates the complexity of the combined attack as $log(\pi/4*l)/log(4)$ where $l$ is the largest prime in the divisors of the order (that is exacly our $n/(3*11*47*3015283*40375823*267983539294927)$, which approximate to the $2^{58.4}$ value of the question. I don't know where his formula come from, most likely from a much better knowledge of Pollard's Kangaroo running time.

Edit1: understood calculation from bernestein, modified the premise since my question was answered.


Isn't the security of EC curve 25519 126 bits?

In the usual definition of security of Elliptic Curves, curve25519 security is in fact 126 bits.

If look at safecurves's rho page you can see the rho complexity for curve25519 is $2^{125.8}$ in accordance to what you say.

Curve25519 author basically doesn't accept that definition of security.
In the Curve25519 paper he states in section 1:

  Every known attack is more expensive than performing a brute-force search on a typical 128-bit secret-key cipher

Which, accordingly to the usual definition of security, would provide 128 bit security.

He provides a little bit more details in Section 3, subsection "Generic discrete logarithms by the rho and kangaroo methods". But the best paper describing his critics to standard definition of security is Non-uniform cracks in the concrete: the power of free precomputation.


I'll assume the right 16 in the question's figure is to tell that the LFSR is unloaded 16 bits at a time; and unless otherwise stated I'll assume that's done every 16 clock cycles of the LFSR.

Is the LFSR sufficient to unbias the input?

Mostly yes, but that's not enough in crypto. It's desired to make the output undistinguishable from random (no just unbiased) for an adversary who knows the design of the system (here, that there is a 16-bit LFSR, and even which). That's per Kerckhoffs's (second) principle.

Is a LFSR sufficient for post-processing a biased TRNG?

Positively no, in an unspecified cryptographic context, and assuming full use of the output (see first paragraph).
Problem is that from the output of the LFSR, and it's design (feedback polynomial mostly), and perhaps it's initial state (see below), it's trivial to get back at the exact input of the LFSR, and from that take advantage of the bias for a distinguisher. If the LFSR output is used for something critical (e.g. generating a One Time Pad), that can be a disaster.
If the LFSR is in "scrambler" configuration, an adversary can feed the LFSR's output in the corresponding "descrambler", and that will output what was the scrambler's input. Exactly so if the descrambler starts in sync with the scrambler, or after the first 16 bits otherwise (a descrambler for and $n$-bit LFSR self-synchronizes after $n$ bits). In other words, that descrambler trick, that the adversary can apply, undoes what the LFSR in the question's generator did, thus the LFSR is not sufficient.
This is illustrated below. On top of the picture is the question's LFSR, simplified (serial output scrambled, $n=4$ stages). The bottom is the descrambler, added/simulated by the attacker. It should be apparent that after $n=4$ clocks, the bottom circuit is in sync with the top's, and descrambled is the input, with whatever detectable bias.

If the LFSR was in some other configuration (descrambler or "additive scrambler"), an adversary needs to guess the LFSR's initial state, if not known in the context (e.g. zero at reset). Even with no clue, attack remains easy: there are only $2^{16}$ possible initial states, and we can select whatever one gives the most marked bias for the reconstructed input, again making the LFSR not sufficient.
For something that works and still only uses a relatively small LFSR, we want to heavily undersample ("decimate") the output of a LFSR in scrambler configuration; e.g. keep one output bit out of 64 (almost equivalently, unload the 16 bits of the LFSR every 1024 clocks instead of 16). The general idea is the entropy is gathered/mixed in the LFSR between outputs. There's a trade-doff between quality of the output and output rate, controlled by the undersampling/decimation rate.
There's a simple theory for how much decimation is too little: if there is $h<1$ bit of entropy per bit out of the sampler, then anything less than $1/h$ bits into the LFSR stage for each bit out is too few. So if when in an experiment we capture the output of the sampler and feed that to a lossless compressor like bzip2, and it compresses by a factor of $c$ (e.g. $c=4$ for 100MiB compressed to 25MiB), then any decimation less then $c=4$ sampled bits in for one bit out of the LFSR stage is too little. Also, if at the output of the sampler we have bits with average $a\ne1/2$, anything less than $c=-1/(a\log_2(a)+(1-a)\log_2(1-a))$ is too few (beware this formula does not account for correlation between bits, and thus is next to useless except for extremely biased input).
Unfortunately I have no simple theory for how much decimation is enough, or how LFSR size matters! The standard recommendation is to be extremely conservative if the LFSR is the only mean to condition the sampler's output, or (better) conservative and use the LFSR to seed a Cryptographically Secure Pseudo Random Number Generator, using the output of that in the end. Also see last paragraph about the need to detect field failures.
I wish I knew exactly what condition (if any) on the LFSR in scrambler mode is necessary to insure no long term bias in the output (assuming no feedback from output to input, and independent bits in input [or even much weaker and plausible assumptions]). But even a 1-stage LFSR in scrambler configuration (feedback polynomial $x+1$, single D gate, 2-input XOR including input) does that. Followed by ample decimation, that's one of the simplest correct RNG post-processing.

Would unbiasing the input with e.g. a Von Neumann extractor be beneficial?

Most likely it would be beneficial. It would even work perfectly if the bits at the output of the sampler are independent. But

Absent that insurance, there can remain a detectable bias.
Output rate becomes irregular, with no minimum, and that can be a serious problem¹.

The first issue could be dealt with by cascading several Von Neumann extractors, but each state halves the average thruoutput and worsens the second issue. An LFSR in scrambler configuration followed by heavy under-sampling is more robust, and at least the throughput is predictable.
Beware that the hardest part in designing a Cryptographically Secure True Random Number Generator is not making it secure² when it works, but detecting when it does not work as intended (like because an attacker pours liquid nitrogen, or just some mundane corollary of Murphy's law), so that the overall gizmo remains secure.

¹ I once was involved with finding why some Smart Card accepting devices sometime got bricked on the field with some type of cards, degenerating into expensive consequences. It ended up being an overreaction by the accepting device to a failure in the ISO/IEC 7816-3 protocol, following a timeout: the card was sometime too slow to answer. According to the Smart Card manufacturer, that was due to random operating delays induced by a Von Neumann extractor (I doubt this is the full story of the card misbehavior but trust it involved irregular RNG throughput).
² It's still hard! Potential problems among many include unwanted feedback loops from conditioned output to the source/sampler.


If they have a pre-shared key $K$ and want to authenticate public keys, the simplest way would be for Alice to compute $T = HMAC(K, PubKeyAlice)$ and send $(PubKeyAlice,T)$ to Bob.
This authenticates the public key of Alice. There is no need to encrypt it, since it is a  public value anyway.


How does recovering a message from a signature, as described by RSA, prove that the message was signed with a private key?

How then does merely recovering $M$ from $S$, as described by the authors, prove that $D_B$ was applied to $M$ to produce $S$?

It does not¹. As pointed in the question, $M$ could have been produced from a random $S$.

Is legibility alone a strong enough proof of $M$ having been signed by $D_B$?

No. It's easy to build counterexamples, for various plausible definitions of legibility. My favorite is that it can efficiently be built four pronounceable ASCII² byte strings $M_i$ of same sizable length with $M_0\,M_1=M_2\,M_3$, and then it is trivial to find $S_0$ from $S_1,S_2,S_3$. Thus the private key holder having signed $M_1,M_2,M_3$ can be wrongly accused of having signed $M_0$.

If $M$ (or a hash of $M$ if you want to nitpick) were included in the message alongside $S$, then you'd have something to compare the result of $E(S)$ to.

No. Sending $(M,S)$ and/or $(H(M),S)$ with $S$ computed as $S\gets M^d\bmod N$ does not help at all improve security: again, just pick a random $S$, compute $M\gets S^e\bmod N$, send $(M,S)$ or $(H(M),S)$. The verifier will accept it.
What does help is sending $(M,S')$ with $S'$ computed as $S'\gets H(M)^d\bmod N$, when $H$ is a wide hash. Verifier checks $S'\bmod N=H(M)$. That's the principle of Full Domain Hash, aka RSA-FDH. It's secure; but because an earlier (quantitatively weaker) security proof of RSA-FDH was deemed not strong enough, it was devised RSA-PSS, and its derivative  RSASSA-PSS is used in practice.

¹ Academic cryptography was in its infancy, and back then it was considered acceptable to present as fact some bold, unproven, and occasionally wrong statement. Another claim in the paper was later disproved by ElGamal and Schnorr signature:

To implement signatures the public-key cryptosystem must be implemented with trap-door one-way permutations (…)

² That could perhaps even be made borderline meaningful. It would actually make a nice CTF, that I have not seen implemented: server textbook-RSA-signs (with 2048-bit and $e=2^{16}+1$ ) any ASCII/UTF8 byte string that some criteria (or "AI") deems acceptable, but not if it's on the tune of IOU$ followed by digits; the winner is who get the highest amount signed.


How to attack a fixed LCG with partial output?

Notations:

$v=u\bmod m$ means $m$ divides $u-v$ and $0\le v<m$, including if $u<0$.
All variables are non-negative integers (except for the above).
$a=214013$, $b=2531011$ are the LCG parameters.
$X_n$ is the 31-bit state with $X_{n+1}=(a\cdot X_n+b)\bmod 2^{31}$.
$R_n=\lfloor X_n/2^{16}\rfloor$ is the 15-bit output.
$S_n=X_n-2^{16}\cdot R_n$ is the hidden 16-bit portion of the state.

Assume we have the first few outputs $R_0$, $R_1$.. and want to find $X_0$.

We derive:
$$\big((2^{16}\cdot R_1+S_1)\bmod 2^{31}\big)=\big((a\cdot (2^{16}\cdot R_0+S_0)+b)\bmod 2^{31}\big)$$
$$2^{16}\cdot R_1-a\cdot2^{16}R_0-b+S_1\equiv a\cdot S_0\pmod{2^{31}}$$
Using that $S_1<2^{16}$ and defining $r=2^{16}-1-S_1<2^{16}$, that becomes:
$$2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1\equiv a\cdot S_0+r\pmod{2^{31}}$$
Defining $K$ as the quotient of the Euclidean division of $a\cdot S_0+r$ by $2^{31}$, it comes:
$$\big((2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod2^{31}\big)+2^{31}\cdot K=a\cdot S_0+r$$
Using that $r<2^{16}\le a$, we find that $S_0$ must be the quotient of the Euclidean division of the new left side of the equation by $a$, and $r$ the reminder; we derive:
$$S_0=\Big\lfloor{{\big((2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod 2^{31}\big)+2^{31}\cdot K}\over a}\Big\rfloor$$

Therefore the following outputs the possible values for $X_0$ given the first two outputs $R_0$ and $R_1$, by trying all possible values of $K$:

Compute $T=(2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod 2^{31}$
Notice that $T+2^{31}\cdot K=a\cdot S_0+r$ with $S_0<2^{16}$ and $r<2^{16}$
For $K$ from $0$ to $\big\lfloor\big((2^{16}-1)\cdot(a+1)-T\big)/2^{31}\big\rfloor$

If $\big((T+2^{31}\cdot K)\bmod a\big)<2^{16}$

Output $\big\lfloor(T+2^{31}\cdot K)/a\big\rfloor+2^{16}\cdot R_0$

The quantity $(T+2^{31}\cdot K)\bmod a$ tested in the loop is $r$, hence the test's bound. $\big\lfloor(T+2^{31}\cdot K)/a\big\rfloor$ is $S_0$. What's output is a candidate $X_0$, since $S_n=X_n-2^{16}\cdot R_n$. It is easy to filter these candidates using $R_2$.

This works for any $a\ge2^{16}$. With the parameters at hand, the loop is performed at most $7$ times, with typically $2\pm1$ outputs. I can run the algorithm with pen and paper, and some would be able to perform it mentally.

The method works regardless of the bit size $x$ of $X$, an output $R$ with $x/2$ high bits (give or take a constant), and $a$ big enough that the attack works: the cost is $O(x^2\cdot a/2^{x/2})$ using standard arithmetic algorithms. I think we could avoid most values of $K$ that do not pass the test, bringing the cost to $O(x^2)$ even for huge $a$ (and quoting Bruce Schneier attributing that saying to the NSA: "Attacks always get better; they never get worse").

When $a$ is too small to carry that attack, a trivial attack applies, recovering the state $X_0$ from most to least significant bits, at a rate of about $\log_2a$ additional bits for each additional $R_n$.

Improvement: if $a$ is small or otherwise unfavorable, we can use $R_j$ rather than $R_1$, replacing $a$ with $a_j=a^j\bmod2^{31}$ for some $j>1$ giving a favorable $a_j$ (a small maximum $K$), and replacing $b$ with $b_j=b\cdot(1+a+\dots+a^{j-1})\bmod2^{31}$. That allows to efficiently tackle much larger modulus!

Generally speaking, Linear Congruential Generators are very poor from a cryptographic standpoint, even when some post-processing is applied; see this answer for an example.

More often than not, Linear Congruential Generators are not even suitable for simulation purposes. To demonstrate this to the incredulous, generate a million values using the LCG in the question; count how many times each of the 32768 values is reached; and either compute the standard deviation of that, or graph the counts sorted by increasing values; repeat with a sound RNG, and compare.


Optimized Garbled Circuit Algorithmic Description

Not all optimizations of garbled circuits are compatible with each other. Are you interested in implementing all of the different combinations? If not, the Half Gates paper already gives a formal description of the scheme, which includes point-permute, fixed-key block cipher, free-XOR. This should represent the state-of-the-art combination of GC optimizations. There is a good implementation of half-gates in the Ivory project.


If I understand correctly, you want a function that for each input string $p$ assigns a permutation over an alphabet $L$.

If the number of elements in $L$ is small enough, the permutation set $P(L)$ will be enumerable. More precisely, $|P(L)| = |L|!$. There exists a surjective function $f:\{0,1\}^k \to P(L)$ that for each bit string $s$ of length $k$ assigns a permutation over $L$, where $k \gt log_2(|L|!)$. For instance, $f(s) = g(BS2I(s) \bmod n!)$ and

function g
  Input: Large integer
  Output: array [L] of L
  x := Input;
  for i := 0 to (n-1) do
    z[i] := i;
  for i := n downto 1 do
  begin
    t := x mod i;
    x := x div i;
    y[n-i] := z[t];
    for j := t+1 to i-1 do
      z[j-1] := z[j];
  end;
  for a in L do
    Output[a] := I2E(y[E2I(a)]);

will work, provided that $2^k$ is sufficiently much larger than $n!$ to make the bias insignificant. Note: Surjectivity follows from the observation that each $x$ in the range $0..n-1$ will result in a unique sequence of $t$ values. At each step, a change in $t$ will result in a different value from the remaining $z$ values being picked. The algorithm closely follows the conventional proof that the number of permutations of $n$ elements equals $n!$.

However, as pointed out by fgrieu in a comment below, a more efficient algorithm is:

function g
  Input: Large integer
  Output: array [L] of L
  x := Input;
  for i := 1 to n do
  begin
    t := x mod i;
    x := x div i;
    y[i-1] := i-1;
    y[i-1] := y[t];
    y[t] := i-1;
  end;
  for a in L do
    Output[a] := I2E(y[E2I(a)]);

The second algorithm will also output unique permutations for $x \in \{0..n-1\}$. Informally, this is because each permutation of $n$ elements might be expressed as a sequence of at most $n$ pairwise substitutions. This algorithms happens to result in sequences of $n$ such pairwise substitutions that are guaranteed to result in unique permutations.

To ensure that two related input passwords will not map to two related permutations, you first pass the password through a PBKDF (as suggested by fgrieu in a comment) before applying $f$. If $|L| = 26$ then $k = 256$ will be sufficient (because $log_2(26!) \lt 89$ the bias of $f$ will be significantly less than $2^{-128}$).

Hence:

Pass the input password $p$ through a PBKDF to produce a bit string $s$ of bit length $256$.
Convert $s$ to a 256 bit integer $x$ using a standard $BS2I$ function.
Map $x$ to a permutation over the 26 element alphabet $L$ using function $g$


Computational indistinguishability and example of non polynomial algorithm

I am not a complexity theorist, but I believe this fits the requirements.

The best known algorithms for factoring are superpolynomial time algorithm so they are not polynomial time. An example of something th superpolynomial time algorithm could distinguish are outputs from the Blum-Blum-Shub PRNG.


Baring an improbable tremendous theoretical breakthrough, any odd of any kind of collision among SHA-512 hashes, for any cause except identical input or computing failure, is negligible in practice; we'll thus handle this from a theoretical standpoint.

Let $s=512$ be the hash width; $k=1000$ the number of hash iterations; and $q>0$ the number of stored iterated hashes.

The question worries about chances of collision, I assume in the stored hashes. Such collisions, even if they occurred, have little potential to help an adversary to get access or recover a password, but for the sake of the argument let's consider them anyway (say, the login system searches among all iterated hashes without using the salt as primary index).

If there was no iteration, odds of collisions would be $\approx q\cdot(q-1)/2^{s+1}$. That's also about the odds considering iterations if the salt is rehashed at each step (which is common and would match the question's statement).

With iteration and just re-hashing the previous hash, we have to worry that collisions among the result of the $q\cdot k$ total hashes could also cause a collision of the stored hashes. Because we can neglect that a cycle also gets involved and has just one of the few length that could matter, only collisions occurring after the same number of iteration need to be accounted for, and the odds of collisions among stored hashes are $\approx q\cdot(q-1)\cdot k/2^{s+1}$.

Thus with the worse possible interpretation of the question's quote, odds of collision among stored hashes grow only about linearly with the number of iterations.

The main issues to worry about:

1000 iterations is MUCH insufficient; that might have been useful when PBKDF2 was created, but no longer provides adequate protection against brute force password search in the event of a leak of the password hashes.
Better slow key derivation functions provide much better protection at equal computing cost, see scrypt.


Are there any Cryptography Algorithms that involve Lots of Number Theory?

The Falcon digital signature algorithm is as "meaty" as one can be.

It has an NTRU-like key generation procedure and public key lattice structure;

its security is based on conjectured difficulty of lattice reduction in classical and quantum computers;

its efficiency is based on number-theoretic transformation and fast discrete normal distribution sampling;

its compactness is based on entropy coding.

Some more to be listed.


What is the difference between PRF and a Random Oracle?

$\newcommand{\str}[1]{\{0,1\}^{#1}}$

Roughly speaking, a pseudo-random function is to a random oracle what computational encryption scheme is to one-time pad -- the former is a computational analogue of the information theoretic latter.

For simplicity, let's fix the domain and co-domain to be the set of all $n$-bit strings. Let's consider the set $\mathcal{F}_n$ of all functions that map $n$ bits to $n$ bits, i.e.,
  $$\mathcal{F}_n=\left\{f:\str{n}\rightarrow\str{n}\right\}.$$
A random oracle on $n$ bits is a function sampled uniformly at random from $\mathcal{F}_n$ that is presented as an oracle. That is, any machine that has access to the random oracle can (by writing on its oracle tape) query it on inputs and will receive the value of the function in return (written back on the oracle tape).
Note that since there are $|\mathcal{F}_n|=(2^n)^{2^n}$ such functions, the probability that a particular $f\in\mathcal{F}$ is chosen is $1/|\mathcal{F}_n|$. Moreover, as it is picked uniformly at random, a random oracle is incompressible and the only way to explicitly represent it is via its function table (which has a size of $n2^n$ bits). (This is why it is presented as an oracle.)

A pseudorandom function, on the other hand, is a family of functions that "appear" random to a computationally bounded machine. More formally, it is a family of explicit, efficiently-computable keyed functions on $n$-bit strings
  $$\mathcal{G}_n=\{g_k:\str{n}\rightarrow\str{n}\}_{k\in\str{n}}$$
that is pseudo-random: for any computationally bounded machine the worlds with  oracles
$$f(\cdot):f\leftarrow\mathcal{F}_n ~~(\text{random})$$
and
$$g_k(\cdot):g_k\leftarrow\mathcal{G}_n\stackrel{\Delta}{=}k\leftarrow\str{n}~~(\text{real})$$
appear indistinguishable. In other words, it is indistinguishable from a random oracle for computationally-bounded machines. Note that $\mathcal{G}_n\subset\mathcal{F}_n$ and, more importantly, the number of functions in $\mathcal{G}_n$ is much smaller than that in $\mathcal{F}_n$: $$|\mathcal{G}_n|=2^n\ll|\mathcal{F}_n|=(2^n)^{2^n}$$
However, by pseudo-randomness, a computationally-bounded machine should not be able to tell this.

The advantage of using pseudo-random functions instead of random functions is that they have a succinct representation: once the family $\mathcal{G}_n$ (which we require to be explicit and efficiently-computable) is fixed the function is represented by the key $k$ and therefore its explicit representation is simply $n$ bits long.

Now, to answer the questions

  Is the difference only about the domain of PRFs and Random Oracles,
  former having a fixed domain and latter can act on any input as long
  as it is well formatted?

Not necessarily, one usually talks about an ensemble of PRFs, that is one for every bit length: $\{\mathcal{G}_n\}_{n\in\mathbb{N}}$.

  Having a Random Oracle is a stronger assumption, why is that?

That question can be interpreted in different ways. Assuming an object $B$ is said to be stronger than assuming another object $A$ if $B$ implies $A$ (but the other direction does not hold or is unknown). For example, DDH is a stronger assumption than CDH, or IND-CCA is a stronger assumption than IND-CPA. In this sense, it is not possible to directly compare a random oracle to a PRF since the former lives in a relativised world (i.e., a world with oracles), whereas the latter need not. It unlikely that a construction of PRF from random oracle could be explicitly and succinctly described (as @Ievgeni points out) because of the incompressibility of the random oracle. On the other hand, one could talk about simulating a random oracle using a PRF -- however, to an unbounded adversary this would appear distinguishable.

That said, a protocol that is based on a PRF is preferred to one that is based on random oracles since in practice we do not know how to instantiate random oracles. One could replace it with a concrete hash function like SHA3 (i.e., the random-oracle methodology), but this protocol only has heuristic guarantees (discussions here and here) and in some cases known to be insecure (discussion here). However we do know how to (explicitly) construct pseudo-random functions from the mild assumption that one-way functions exist (discussion here).


Tiny Encryption Algorithm (TEA) weakness


How to get exact number of slots in HElib? Such as 256, 4096

The number of slots is $\varphi(m)/\text{ord}(p)$, where $\varphi(m)$ is the totient of $m$ and $\text{ord}(p)$ is the multiplicative order of $p$ mod $m$ (and hence divides $\varphi(m)$).
In order for the number of slots to be 256, it must be the case that $\varphi(m)$ is divisible by 256. Recall that $\varphi(m)$ is the product of the totients of all the maximal prime powers that divide $m$, i.e., $\varphi(m) = \prod_i (p_i-1)p_i^{e_i-1}$ where $m=\prod p_i^{e_i}$ is the factorization of $m$ into powers of distinct primes $p_i$.
To make $\varphi(m)$ divisible by $256=2^8$, observe that for odd $p_i$, the corresponding term $(p_i-1)$ in $\varphi(m)$ is divisible by some power of two, and these powers combine across the primes. However, higher powers of such primes don’t give us any high powers of two (nor do they hurt). Alternatively, if one of the $p_i=2$, then it contributes a factor of $2^{e_i-1}$ to the totient. As an extreme example, we could take $m=512$ and immediately get $\varphi(m)=256$.
The divisibility condition is necessary but not sufficient; we also need to choose a prime modulus $p$ whose order is $\varphi(m)/256$, i.e., the cyclic subgroup of $\mathbb{Z}_m^*$ generated by $p$ should have that order. This is a bit more subtle. One method that can work is to use the Chinese Remainder Theorem: we know that $\mathbb{Z}_m^*$ is isomorphic to the product of the groups $\mathbb{Z}_{p_i^{e_i}}^*$, so we can find a suitable condition in each component and then use CRT to find a suitable prime $p$.
An extreme example is when $m=512$ (so $\varphi(m)=256$). Then it is necessary and sufficient to take a prime $p$ of order 1, i.e., $p=1 \pmod m$. More generally, for odd $p_i$ the component $\mathbb{Z}_{p_i^{e_i}}^*$ is cyclic, so we can find an element $g_i$ of any order that divides the order of the component, and we want the product of these orders (of the $g_i$) to be 256. Finally, then, we can seek a prime $p$ that is congruent to $g_i \pmod{p_i^{e_i}}$ for all $i$. This may give us what we want overall, but beware that the order of $p$ may not be the product of its orders in each CRT component,
so some trial and error may be needed.


How does failing to square a value in this version libcrypt++ cause a timing attack vulnerability?

In CVE-2015-2141 something as simple as failure to call r =
  modn.Square(r); in a single func seems to have caused a timing attack
  vulnerability in libcrypt++ in 2015.

Actually no. That's not what CVE-2015-2141 is about. What it is actually about is that the loop originally did not have the squaring and this would result in sometimes not having the blinding removed in a later step after the private key operation which would leak enough information in about 2 signatures on the same message to recover the private key.

  First it seems like you'd need some special helper func designed to
  produce random timing results called in each subroutine to blind a
  func, why is the process of squaring a value sufficient?

The blinding here is achieved by the fact that computing a signature in rabin-williams is "effectively equivalent" to computing a square root of the message. So it kinda works like this:

Pick $r\gets_\$ \{1,...,n-1\}$, compute $r^2\bmod n$ and $r^{-1}\bmod n$
Let $m$ be a message, compute $m'=r^2\cdot m$
Now compute the signature on $s'=\sqrt {m'}\bmod n=\sqrt {r^2\cdot m}\bmod n=r\cdot\sqrt {m}\bmod n$
Finally unblind the signature to recover the actual signature $s=r^{-1}\cdot s'\bmod n$

Now what this achieves is prevent an attacker from knowing on which value exactly the private key operation was applied, which should thwart quite a few timing attacks.

  Is the goal to make every subroutine take exactly the same amount of
  time to complete, or a random unpredictable time?

The standard strategy to thwart timing attacks is to either

ensure the timing doesn't actually depend on the private value in question or
ensure the timing doesn't actually correlate to known inputs and / or the private key in a meaningful way.

Randomizing the input to the private key operation is part of the second strategy.


Does the authentification in GCM serve the same purpose as CRC32?

I do read some article saying, the hacker is able to alter the data which can still result the same CRC computed value in the end.

Obviously, yes.  The CRC32 function is completely public, with no secret inputs.  Hence, the attacker can compute the CRC32 of any modified data he wants, insert the tag, and it would validate.  In contrast, GCM does have a secret input (that we need to assume the attacker does not know).  Hence, the attacker cannot evaluate the GCM on his modified data in the same way.

Actually, the real answer is a bit deeper (and makes the contrast even stronger); CRC32 has a lot of symmetric internal properties that make it easy to compute the tag on modified data (even if the attacker doesn't see all of the data).  In addition, with GCM, if we assume that the attacker does not know the key, and cannot break AES (and we never repeat nonces), then he has a provably tiny probability of being successful with any modification.

  May I know if they are serving for similar purpose.

Similar?  Well, CRC32 is a fine function if you want to detect accidental (not generated by an intelligent adversary) modifications with pretty decent probability.  In fact, if most of the accidental modifications are burst errors (that is, the errors are limited to a few consecutive bits, and the rest of the message is unmodified), then it is actually better - CRC32 will detect all errors that are contained within a sequence of 32 consecutive bits.  However, once you start talking about strength against an intelligent adversary, that's a completely different story.

  Does this mean Galois Field multiplication is doing better job for this?

It's not about the multiplication, per se.  Actually, you could modify CRC to have similar integrity properties as GCM (you'd need to expand the CRC, make the feedback polynomial secret, and stir in a per-message secret xor-mask).  Instead, it's both the secret key, and the structure (that makes it so that if the attacker makes a modification to an existing message, the change that makes to the tag is unpredictable).


How can we prove that two discrete logarithms are equal?

Are you limited to working with $g$ and $h$ being generators of the entire group $\mathbb{Z}_p^*$? In that case
you have a problem with knowledge extraction in the proof of knowledge (basically, since you are not working in a field "in the exponent", but in $\mathbb{Z}_{p-1}$, the required multiplicative inverses might not exist).

However, when you work in a large
prime order $q$ subgroup of $\mathbb{Z}_p^*$ and $g$ and $h$ are
generators of the order $q$ subgroup, you can use a standard honest-verifier zero-knowledge proof of knowledge
that you know $x\in \mathbb{Z}_q$ such that $\log_g a = \log_h b$ (i.e., $a$ and $b$ contain the same discrete logarithm w.r.t. $g$ and $h$ respectively) without revealing anything about $x$. This proof is quite standard and based on Schnorr's proof of
knowledge of a discrete logarithm.

The idea proof between a prover and
a verifier on common input $(p,q,g,h,a,b)$ runs as follows (where $x$ is only known to the prover):

$P$: choose uniformly at random $r\in \mathbb{Z}_q$ and send $(k,k')=(g^r,h^r)$ to
the verifier $V$
$V$: choose uniformly at a random challenge $c\in \mathbb{Z_q}$
and send $c$ to $P$ (I took the set $\mathbb{Z_q}$ as challenge space, the
set size depends on the soundness error you are tolerating)
$P$: compute
the response $z=r+x\cdot c \bmod q$ and send $z$ to $V$
$V$: Verify
whether $g^z=k\cdot a^c$ and $h^z=k'\cdot b^c$ holds and accept if this
is true or reject otherwise.

Correctness is easy to verify and special soundness as well as
honest-verifier zero-knowledge is also quite straightforward to show.


Questions about the certificate authority procedures

 1. The answer cited states

  2) the client generates a CSR (Certificate Signing Request) including attributes like Common Name and the Public key. Signs it with the private key and sends it to the server

Notice that the client signs the CSR; the client does not encrypt the CSR. This leaves the data in the CSR (mostly, the public key and its attribute) in clear form, directly readable. The signature of the CSR can be verified against the public key in the CSR (this acts as a verification of consistency, and prevents an entity asserting that it generated the private key from pretending not having issued the CSR).

The CSR is defined in RFC 2986:

   CertificationRequest ::= SEQUENCE {
        certificationRequestInfo CertificationRequestInfo,
        signatureAlgorithm AlgorithmIdentifier{{ SignatureAlgorithms }},
        signature          BIT STRING
   }

The signature field is the RSA signature of the CertificationRequestInfo according to the AlgorithmIdentifier (which must be compatible with the type of key for which the certificate is requested from the CA). In the context of RSA, the big picture is that the CertificationRequestInfo is hashed, some padding is added (per RSASSA-PKCS1-v1_5 or RSASSA-PSS of PKCS#1), then the RSA private key function $x\to x^d\bmod N$ is applied to form the signature (with some conversions between integer and bytestring). Notice that signing uses the private key, which is usually kept private to the party asking for the certificate; and signature verification by the CA will use the public key for which it is asked the certificate, which is embedded in clear in CertificationRequestInfo. There is no encryption involved (RSA encryption uses a different padding, the public key for encryption, and the private key for decryption).

 2. The usual way for client B to obtains A's public key is to

obtain A's certificate (as issued to A by the CA server), usually from A, or from a public registry (not necessarily trusted).
check that certificate using the CA server's public key, assumed authentic/trusted,
extract A's public key from the certificate

 3. See point 2) in reference, cited above. The hard part is convincing the CA to issue the certificate, which typically requires proof of control of the domain(s) in the Common Name field.

 4. We don't do recommendations.


How AES-CTR is used in AES-GCM to generate cipherText and a authTag to authenticate the cipherText and authData?

AES-GCM,or more generally GCM is a mode of operation for a symmetric block cipher. It stands for Galois/Counter Mode. It provides Authenticated Encryption, guaranteeing both confidentiality (data secrecy) and integrity (data authenticity).

Confidentiality is provided by the Counter Mode: roughly a counter is encrypted and the output is xored with the plaintext. If more than one block has to be encrypted, the counter is incremented.

To be secure, GCM requires that the counter is used only once (See here for details Nonce reuse vulnerability). It is usually generated as the concatenantion of a NONCE and an actual counter (e.g.: $NONCE || 0...0)$.

Please note that the standard GCM construction uses the encryption of the counter from 1 to do the actual encryption, while the encryption of the zero-counter is used in the AuthTag computation

From a confidentiality point of view they are the same. Indeed, AES-GCM is defined as AES-CTR + GMAC as authentication code.

The difference is that AES-CTR does not provide integrity protection and an AuthTag has to be added (could be HMAC, or CBC-MAC for example); on the other side the AES-GCM provides both protection (confidentiality and integrity).


How is padding oracle attack mitigated by encrypt-then-MAC?

The biggest issue with padding oracle attacks are when the padding is not very carefully implemented (for example if using EtM you must calculate the MAC over everything - including the padding). To pre-empt references to the classic Belare-Namprempre paper, be wary - their results do not apply to modern primitives, since nowadays we prove security differently. See instead the relevant Namprempre-Rogaway-Shrimpton paper from Eurocrypt 2014 (discussed here).

Padding oracle attacks are (supposed) to be mitigated by only presenting a single error. This is pretty well standard now (in that a sensible scheme will just say 'invalid' rather than 'padding wrong' etc), but timing errors exist that allow you to differentiate padding errors from other errors.

The idea is the in Encrypt-then-HMAC, you are always calculating the MAC over the entire message. So, let Bob receive a message, which he will parse as $(C||T)$. He will calculate $HMAC(C)=^?=T$. He can do this without caring how $C$ was put together, and as such calculating/checking the MAC won't leak any information about what's within $C$.

Conversely, suppose we have MtE. Then he receives $C$, for which he believes $C=E(M||T)$, with $T=HMAC(M)$. Having decrypted $C$ to get $M′||T′$, he now has to work out how to calculate a MAC over $M′$. This is where the padding oracle occurs, because the decryption algorithm has to work out how much padding there should be, leaking information about the message.


How well does breaking multiple DH key exchanges over the same group scale?

The simplest index-calculus attack on discrete logarithms is the following. You have a generator $g$, a target $y$ and a bunch of small primes $\ell_1, \dots, \ell_k$. The computation proceeds in three phases.

First generate lots of relations of the form
$$g^{r_i} = \prod_j \ell_j^{s_{ij}}.$$

These relations give you a set of linear equations in $r_i$, $s_{ij}$ and unknown $\log_g \ell_j$. Solve this system for the unknown $log_g \ell_j$.

Now find one relation of the form
$$y g^u = \prod_j \ell_j^{v_j}.$$
From this, the logarithm of $y$ is easily recovered.

The third phase is much, much cheaper than the two first phases. Notice also that the two first phases do not involve $y$, so when you want to compute the logarithms of multiple elements, you only have to repeat the third phase.

I believe these essential characteristics are shared with the more advanced d.log.algorithms, so the cost of computing $n$ logarithms is not $n$ times the cost of computing one logarithm, but merely somewhat larger than computing one logarithm.

Typically, our goal is to make it impossible to compute even one logarithm, so this does not have to be a reason for using different groups. There are good reasons for everyone to use the same group. For prime finite fields, you can use carefully chosen primes that make arithmetic fast and/or secure implementation easy. For elliptic curves, you can use carefully chosen primes and curves that make arithmetic fast and/or secure implementation easy. (Note that index calculus doesn't work for elliptic curves, but I think there are speedups for Pollard $\rho$ when computing multiple discrete logarithms.)


If you read all of the RF 8032 you will see that there is a compression (endcodings) of the points.
def point_compress(P):
    zinv = modp_inv(P[2])
    x = P[0] * zinv % p
    y = P[1] * zinv % p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little")

Compression just stores the sign and restores it back with this information
def point_decompress(s):
    if len(s) != 32:
        raise Exception("Invalid input length for decompression")
    y = int.from_bytes(s, "little")
    sign = y >> 255
    y &= (1 << 255) - 1

    x = recover_x(y, sign)
    if x is None:
        return None
    else:
        return (x, y, 1, x*y % p)

The above has been defined for Ed25519, there is no code for Ed448 in the RFCs as I can see. However NIST.FIPS.186-5-draft defined it for both;

For a curve point $(x,y)$ with coordinates in the range $0 \leq x, y < p,$ first encode the $y$-coordinate as
a little-endian string of 32 octets for Ed25519 or 57 octets for Ed448. For Ed25519, the most significant bit of the final octet is always zero, while for Ed448, the final octet is always zero. To
form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit of the final octet

As we can see, the LSB of the $x$-coordinate is placed in the MSB of the final octet (byte) of the $y$ coordinate. Therefore, the total size of the public-key is 57 bytes.
Although the compression has a time-consuming and little advantage on the storage/transmission it also helps in the point validation. The second and third options are verified during decompression.

The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
$P$ satisfies the curve equation - against the twist attack.


random mask reversible after homomorphic encryption

It sounds like you're looking for a way to do blinded encryption (that is, encryption in such a way that the encryptor does not know what he is encrypting).
It is certainly possible with Paillier.  Here is one way:

The (op) will be multiplication modulo $n$ the Paillier modulus (which is in the public key).

To mask, we pick a random $r$ relatively prime to $n$, and compute $Am = A \cdot r \bmod n$.  We can see that, if we selected $r$ uniformly, then $Am$ is distributed independently of $A$ (except for values not relatively prime to $n$)

We ask the encryptor to take $Am$ to compute $E(Am)$

To unmask, we compute $rinv = r^{-1} \bmod n$, and then homomorphically compute $E(rinv \cdot Am)$; this Paillier, this is done by computing $E(Am)^{rinv} \bmod n = E(A)$.

One drawback to this is that it doesn't actually mask the value $A=0$; is that a concern?
If it is, you can still do it by asking the encryptor to perform two masked encrypted operations.
First, you generate two random values $r, s$, making sure that neither is $0$
Then, you have the encryptor encrypt the values $A-s$ and $r\cdot s$, producing $E(A-s)$ and $E(r \cdot s)$.  Then, you use the above procedure to recover $E(s)$ from $E(r \cdot s)$.  Then, you homomorphically add $E(s)$ to $E(A-s)$, producing $E(A)$
You could just generate $E(s)$ yourself with $s$ and the public key.  However, if you could perform encryption yourself, you could just generate $E(A)$ from $A$, and it would appear you wanted to avoid that...


What is the totient function for an RSA modulus has several factors due to incorrect setup?

$\phi(p \cdot q \cdot r \cdot ... \cdot s) = (p-1)(q-1)(r-1)...(s-1)$ (for $p, q, r, ..., s$ distinct primes)

In addition, the technically correct modulus for which $e \cdot d \equiv 1$ must hold is commonly known as $\lambda(n)$; in this case,

$\lambda(p \cdot q \cdot r \cdot ... \cdot s) = \text{lcm}(p-1, q-1, r-1, ..., s-1)$


For security in Shamir secret sharing we need that the coefficients of the polynomial are independent and uniformly random in the field. Multiplying the polynomial by a constant from the field does not change this, so yes, you can do it and still be secure.

In fact, in multiparty computation, something akin to this is done when we want to privately multiply a secret shared value by a known, public constant. We multiply each share by that constant. The effect of this is multiplying the polynomial by the constant.

Obviously there are some corner cases to consider. The secret cannot be $0$. If the constant term of the polynomial is $0$, you might also run into problems (depending on the application).

It is important that the secret you multiply by is in fact a single element from the field and not a polynomial itself. If it is a polynomial, then two problems occur. The coefficients are no longer independent and the degree of the polynomial changes.

Without knowing your application, however, it it hard to say whether or not this is useful. Can you still recover the original secret? Only if you know the constant term of the original polynomial, right?


This cannot be used to compromise $P_0$. Suppose that, instead of generating $C_0$ and $C_1$ as $R_0\oplus R_1$ and $R_2\oplus R_1$, the attacker instead picked $C_0$ and $C_1$ at random from the set of bit strings the length of $C_2$. This situation is indistinguishable from yours; in both cases, $R_0$ and $R_2$ are independent and follow a uniform probability distribution, and the same is true for $C_0$ and $C_1$. If you can compromise $P_0$ in your case, you can compromise it if the sender had actually generated $C_0$ and $C_1$. But that would mean that sending two completely random strings alongside an OTP message somehow helps compromise the message. Obviously, that's not true; the attacker could otherwise create his own random strings and break the OTP that way.


The paper writes $z^r \cdot G$; however $z^r$ is a member of the extension group $\mathbb{F}_{q^{12}}$, while point multiplication is formally defined over the integers; you ask "what are we supposed to do here?"
Well, going through the paper, it appears that if we rewrite that equation to $h(z^r) \cdot G$, where $h$ is a function from $\mathbb{F}_{q^{12}}$ to $\mathbb{F}_{q}$, that works (assuming, of course, we rewrite the decryption process similarly), so we have:
$\text{Encrypt}(pk, m) = (r \cdot pk, h(z^r) \cdot G + Pm)$
$\text{Decrypt}^1(C, sk) = B - h( e( A, sk^{-1}G )) \cdot G$
$\text{Decrypt}^2(C, sk) = B - h( A^{1/b} ) \cdot G$
(see the paper for explanation of the various notations, and the reencrypt process doesn't change)
Any deterministic $h$ would work (in the sense that the protocol will work), as can be seen by going through encryption/reencryption/decryption steps.  My inclination would be to use a hash function.


What are the pros and cons of deterministic site-specific password generation from a master pass?

The above scheme does have a very important drawback against schemes that encrypt a password store. If you randomly generate the site  specific passwords then there is no relation to the master password. You would need the complete password store to perform e.g. dictionary attacks to find the master password. This is not true for the deterministic password generator you've described; one single leaked site specific password would enable an attacker to launch an attack on the master password. In the following two paragraphs I'll focus on the security without regard of this observation.

It seems that the scheme above is just an application of a Password Based Key Derivation Scheme (PBKDF), coupled with a deterministic method of mapping the result to a new password in step 5. As long as step 5 only maps to an array of characters in a specific alphabet without loosing entropy, the security of the scheme depends on the PBKDF used. KDF's commonly already include parameters specific to the secret that is to be generated (in this case that would be the site name).

So for the security of the scheme you should simply study security of PBKDF's and - if possible - the security of the specific PBKDF that is being used. Maybe you can compare the scheme against well known variants like PBKDF1, PBKDF2, bcrypt, scrypt or e.g. the proprietary OpenSSL PBKDF.


Why not the one-time pad with pseudo-number generator

It's a good question. As pg1989 said, this is the basis behind stream ciphers, which are very fast in practice.

I thought I'd quickly expand upon your statement that "the one-time pad is the perfect cipher and impossible to crack." This is true, in a sense, but it's worth pointing out that sometimes an attacker wants to do something simpler than "cracking" the encryption scheme in order to recover all plaintexts.

For instance, an attacker may just want to change the message so that the honest recipient decrypts something else. As a simple example, suppose that the attacker knew for sure that the message was either "yes" or "no!" and just wants to change the message to the other value. Note that:

This is simple to do for messages encrypted using a one-time pad. The linked Wikipedia page describes why this is true, but it's probably more fun to figure it out for yourself.
The attacker can do this without learning the plaintext. Hence, the original claim of a one-time pad being uncrackable is still true.

There are some other issues with a one-time pad construction too, such as the fact that usually some state will be required to make sure that you don't re-use the seed during the next encryption. Hence, while your question is definitely not silly, and stream ciphers are very useful in certain circumstances, they also have their limits.


Can Montgomery ladder multiplication be used with secp256k1?

The Montgomery ladder, in particular Montgomery's fast doubling and differential addition formula in $(X : Z)$ coordinates on p. 261, works only for curves which admit a Montgomery form $B y^2 = x^3 + A x^2 + x$.  Any curve over a field $k$ with a Montgomery form necessarily has a point of order 2 among the $k$-rational points, namely $P = (0, 0)$: the negation map sends $(x, y)$ to $(x, -y)$, so since $-P = (0, -0) = (0, 0) = P$, we must have $[2]P = P + P = P - P = \mathcal O$.

secp256k1 is the curve $y^2 = x^3 + 7$ over the field $\mathbb F_p$ where $p = 2^{256} - 2^{32} - 977$.  Its group of $\mathbb F_p$-rational points has large prime order, so by Lagrange's theorem it has no points of order 2, and hence it does not have a Montgomery form.

That said, there is a much slower single-coordinate ladder that encourages constant-time arithmetic, namely the Brier–Joye ladder, which works for any short Weierstrass curve $y^2 = x^3 - a x + b$ including secp256k1.  It is so much slower that the standard variable-time addition chains for short Weierstrass curves are tempting, which is why SafeCurves recommends, for Diffie–Hellman protocols, the use of $x$-restricted DH functions in Montgomery curves instead to avoid a conflict between efficiency and security in implementation.

This doesn't matter as much for signature, which is what Bitcoin etc. use secp256k1 for, because most signature schemes—ECDSA as used by Bitcoin and Ethereum, and by those who are forced to comply with bureaucratic standards; EdDSA as used by everyone else—involve the $y$ coordinate, which neither ladder computes; fixed-base-point scalar multiplication, which can be done faster than variable-base-point scalar multiplication; and multiple-point scalar multiplications, which can be done faster than multiple single-point scalar multiplications.  There are signature schemes computed with single-coordinate ladders, such as qDSA, but these are a little exotic and not much used—certainly not in Bitcoin or Ethereum!


why can't someone generate another private key that will match your
  public key and fool the whole process?

Because in most schemes, this is equivalent to recovering the private key from the public key (this can be somewhat easily seen for RSA and trivially for ECC-based schemes). And as we assume that recovering the private key from the public key is hard, finding a secondary private key that matches a given public key can be considered hard as well.


The following apply to all DES Sboxes.

Note that $\overline{a}\cdot \overline{x}$ and $\overline{b}\cdot \overline{S(x)}$ are both linear boolean functions which thus have truth tables with even Hamming weight.  The xor of the two quantities is also even, since if they have hamming distance $d$ this is 64 minus (the difference of two even hamming weights) by inclusion exclusion.
The $a=1,32,33$ masking patterns are the ones where either LSB or MSB or both of input bits in the corresponding vector $\overline{a}$ are set to one while the remaining bits are set to zero. Recall that for each of the four such possibilities ($a=0$ as well) the DES Sbox output is a permutation of four bits. This also gives a balanced hamming weight, for all output masks $b$.


How to encrypt this using caesar cipher?

The formula reads:

C: ciphertext of a character
E(P): encryption using Caesar of plaintext character =
(Pi + 3) mod 26: index of character in alphabet, plus 3 (the key) and then  modulus 26, the size of the alphabet

So basically for A you encode the value to 0 and add 3, which gets you the value 3, which decodes back to D. For Y you use 24, add 3 and get 27. However, when you do mod 26 you get the value 2, which decodes back to B. So basically you go 3 characters to the right, wrapping around to A after you've reached Z.

Decryption is simply the reverse.


Using the Babai's Naive Rounding algorithm to decode, in the conditions of the SIS problem, is secure?

The Nguyen-Regev attack on GGH and NTRU works because those schemes were "leaking" the trapdoor S while signing. So after observing a certain number of signatures, their algorithm could recover S. So their attack had nothing to do with solving SIS, but rather with how to use the leaked information to recover a trapdoor (which can then be used to solve SIS). In the regular SIS problem, the S is unknown to the adversary and there is of course no "leakage" coming from anywhere.


As I've rewritten your question:

  What is the purpose for and distinction between each of the following keys commonly used in cryptocurrencies?

Public keys

  Address

You may think of your address like a mailbox that receives money. Anyone can put money into the mailbox, but they cannot take it out.

  Tracking key

A variant of the address that derives many addresses for a single identity. This enables you to check the balance for all of your addresses without using your secret keys, which enable you to spend the money. This is useful to isolate your secret keys, or to use a less trusted device like your phone to check your balance, without enabling it to spend.

Secret keys

  Passphrase

If this is a 12-word phrase you didn't choose, it is the seed. This seed is a convenient way to derive the next key.

  Private key

The secret variant of the tracking key. Deriving the secret keys for all addresses under the same identity. You may prefer to keep this key cold (offline), or on a dedicated hardware device.