If a hash function $H$ is collision resistant, is it true that $H(x)\neq H(x')$ for all messages $x, x'$ with $x \neq x'$?

As you correctly observed, for any function $H\colon \{0,1\}^\ast\to\{0,1\}^n$ collisions must exist, simply because $\{0,1\}^\ast$ is an infinite set and $\{0,1\}^n$ is finite.
One could define "hash function" to mean something else (e.g., taking only a bounded input length), but this is non-standard.

However, the term "collision resistance" denotes something different from what you seem to think: It just means that collisions are hard to find, in a computational sense.
We expect from a good hash function that nobody is able to find two inputs that lead to the same hash value, but we do not care about their abstract existence, which is a necessary evil.

Thus, no: Collision resistance does not mean that $H(x)\neq H(x')$ for any $x\neq x'$. It rather means that practically, nobody should ever find $x\neq x'$ with $H(x)=H(x')$.


Derive a key from a password and another key?

So the advantage of the keyfile in addition to the password is that it is basically a form of two factor authentication: You have a password (something you know), and a token (something you have).

The problem is that your salt must be available in order to derive your password based secret, which would mean your token (the salt) is not really separable from your password - this means you don't really have two factor authentication anymore, as the salt can't be separate from the password. So using the salt as the keyfile would not really improve security at all.

One way to accomplish what you are looking for is to generate your keyfile using /dev/urandom or equivalent to generate an appropriately sized token (128-256 bits). Then keep this keyfile on a USB drive. This way, whenever you need to access your secret, you require both knowledge of your password, and possession of the physical token.

After validating the password and keyfile, you could generate a single master key via something like hash(keyfile || password_derived_secret).


Proven secure scheme under random oracle

Indeed, this question is answered by What is the "Random Oracle Model" and why is it controversial?. However, I would like to add a few more thoughts on this. (Please read the other answer as well, since I will not repeat the very important things said there.)

First and foremost, the random oracle is a model and not an assumption. We do not assume that hash functions are random oracles (until proven otherwise) because they are provably not random functions, and they are trivially distinguished from such. Rather, we prove a scheme secure when a random oracle is used instead of the hash function. This is all that the proof of security says. It says nothing whatsoever about the security of the scheme with a concrete hash functions instead.

The claim to security of the real scheme with a concrete hash function is then a "leap of faith" that if the scheme cannot be broken in the random oracle model, then it is very unlikely that it will not be broken with a real hash function. In other words, this is a heuristic argument. Although highly unsatisfactory from a theoretical perspective, this has proven itself quite well over the past decade or two in that real protocols proven secure in the random oracle model are rarely (if ever) broken.

Some people claim that the random oracle model is no different from assuming things like that the discrete log problem or RSA problem is hard. I completely disagree with this. If someone breaks a protocol that is proven secure under the RSA assumption then this will be translated into an attack on RSA. Thus, this is a rigorous proof of security that holds under a given assumption. In contrast, as I have mentioned, the random oracle is a model and not an assumption.

Finally, consider a MAC defined by $h(k||m)$. This is secure in the random oracle model but not secure for any Merkle-Damgård based hash function. Thus, there is clearly a separation.

Personally, I am happy to live with a random oracle in practice when there are not efficient enough alternatives. However, I will always prefer to get rid of a random oracle, and view doing so as an important research goal. We only have IBE since the first constructions used a random oracle, and afterwards future research managed to get rid of this use. Thus, as with many cryptographers, I have a love-hate relationship with the model.


Is the new preprint "An Algorithm For Factoring Integers" by Yingpu Deng and Yanbin Pan worth reading?

If you have to ask, you are probably not the intended audience. Quoting the introduction of the paper:

  We implemented our method on a PC using Shoup’s NTL library version 5.4.1 [7].
  Unfortunately, we have to say that the practical effect of our method is not good on a
  single PC, it is worse than many known algorithms on this problem. However, we believe
  that our method yields interesting phenomena, and it is worth for further study.


how to get the file used to brute force any encryption method

If I'm understanding your question right, you're asking "How to brute-force the Bitlocker encryption without being able to install stuff and without using "backdoors" and without having the key-file (if used)?"

You can't brute-force AES-128 without the said key-file.
The reason for this is that the key file contains the 128-bit keys which are too hard to guess by themselves. If you don't have access to this file at all you can't break AES / bitlocker in a passive sense. You could still run evil-maid attacks though...

If you have access to the encrypted key file and it uses a password there is a chance you can break the encryption scheme.
The reason for this that you'd guess the password used to encrypt the key-file and then properly decrypt it and use the embedded key to decrypt the encrypted data. You can guess the password by simply trying all possible ones out until you hit the lucky one which is feasible because there are only usually "a few" passwords possible ($\approx2^{40}$ compared to $2^{128}$)

Note that the inability to install custom software isn't a restriction in the usual threat model for drive encryption. Usually it is assumed to have physical access to the drive and being able to read sectors while at rest. So one could look for a known structure to perform the brute-force attack so this is feasible (in the right scenario).

TL;DR: You can't break AES, but a password if used, so the password may be weakest point to attack.


Is my implementation of a PRG at least intuitively secure?

PRNGs are a difficult and hot topic.

Some tests can be found here: What tests can I do to ensure my PRNG is working correctly?

But they do not tell you (or others) if your PRNG is really secure. A PRNG must be build in a way, that a third party is not able to "calculate" former or upcoming PRNG output based on some random data from the PRNG.


Is there a known vulnerability when using identical key and salt with PBKDF2?

Using the password itself (or anything similar predictable) instead of an independent random value as the salt denies the whole benefit of salt:

Same passwords (passphrases) give now the same key, instead a different one. So, if two users happen to choose the same favorite image as their password, they get the same key, and thus an attacker can use this fact to easier get the key.
If an attacker bruteforces your "password" database, he can attack multiple passwords in parallel, since they don't use different (independent) salts.

If you have a way to generate good quality random numbers (which should be the case on every normal personal computer), generate a random salt and put it at the start of your encrypted file (like a normal initialization vector).


If a key is used to encrypt that same key, is the computational cost to brute force it decreased?

Depends on the encryption scheme.

In the IND-CPA (or even IND-CCA) security game, the adversary is not given the secret key $d$ (obviously) and hence cannot ask for $\mathrm{Enc}(d,d)$.

In other words: an encryption scheme where $\mathrm{Enc}(d,d) = d$ for all keys $d$ can still be IND-CPA(/CCA) secure (but they'd be completely useless for your scenario).


questions about sensitivity in differential privacy

$D$ is the database at hand. Differential Privacy is a property of a randomized algorithm, which is associated with a domain. So, DP holds for any neighboring databases in the domain. However, when you have a true database $D$, in some cases you don't need to add a noise whose distribution is associated with the global sensitivity to ensure privacy. You can add a smoothened version of the  local sensitivity to add a smaller noise, where local sensitivity is roughly the sensitivity of the function restricted to the neighbors of $D$.


How to better generate large primes: sieving and then random picking or random picking and then checking?

Both methods, of course, will work.

However, from an efficiency standpoint, (1) is considerably better.  Here's why:

The general strategy of both methods is to pick random numbers $R$, check to see that they have no small prime factors (smaller than a value $Q$), and then apply a rather expensive primality test (such as Miller-Rabin) to them.
The probability of a random number $R$ that we have already tested to have no prime factors smaller than $Q<R$ is about $log(Q)/log(R)$, and hence the number of expensive primality tests we expect to need is about $log(R)/log(Q)$.

Now, with method 2, after we pick a number $R_1$ at random, you will check to make sure it has no small factors smaller than some $Q$.  If it didn't, you'll run the expensive primality test on it, and if it wasn't prime, you'll go and pick another random number $R_2$ and try again, checking if that small number had no small factors.  The key point is that the effort you put into checking whether number $R_1$ had factors smaller than $Q$ cannot be reused when checking number $R_2$.  Therefore, we cannot make $Q$ that large (as we'll start spending a large amount of time just testing small factors).

On the other hand, with method 1, we set up a sieve that lists which numbers within the range have no factors smaller than some value $Q$, and then test those numbers that have no such factors.  Here, we pick the first number $R_1$ within the sieve, and run the expensive primality test on it, and if it wasn't prime, we'll go to the second number with no small factors in the sieve.  Here's the point: almost all the time taken in checking for small factors was taken setting up the sieve; once we've done that, going to the next number is essentially free.  That is, this method gets to reuse the effort in checking our test numbers for small factors.

Because of this, we can make the value $Q$ in method 1 considerably larger before it starts to become counterproductive; and because of this larger $Q$ value, fewer of the expensive tests are needed.

Now, as for security; method (2) has the obvious advantage that each prime of the correct size will be chosen with exactly equal probability, while with method (1), primes that sit over a long sequence of composites will be chosen with somewhat greater probability.  On the other hand, while (1) does choose primes with unequal probability, there's no know way that a factorization method can take advantage of that.  Because of this, method (1) is considered safe.


How to generate a random integer in interval $[1, 2^n-1]$ from random integer in interval $[0, 2^n-1]$?

Assuming that $n > 1$ so as to avoid a trivial special case,
there is no function $g(\cdot)$ (linear or otherwise)
that will transform a discrete random
variable $X$ uniformly distributed on $\{0,1, 2, \ldots, 2^{n}-1\}$
into a discrete random variable $Y$ uniformly distributed in
$\{1, 2, \ldots, 2^{n}-1\}$. This is because each value of $X$ has probability $2^{-n}$
attached to it, and this gets mapped onto the $Y$ value $g(X)$. Thus, for any
$m \in \{1, 2, \ldots, 2^{n}-1\}$, $P\{Y=m\}$ is necessarily an integer multiple
of $2^{-n}$ including, possibly, a zero multiple.  It follows that the best
one could do is to get a random variable $Y$ that takes on
all values in $\{1, 2, \ldots, 2^{n}-1\}$ except one with equal probability
$2^{-n}$, and this exceptional value occurs with probability $2\times2^{-n}=2^{-(n-1)}$.

On the other hand, if $X$ were a continuous random variable uniformly
distributed on the interval $[0,2^n-1]$, the answer would
be easy: $Y = 1+\frac{2^n-2}{2^n-1}X$ is a continuous random variable uniformly
distributed on the interval $[1,2^n-1]$.


So a hash can have different messages with the exact same output?

Yes; that's true of any function with inputs longer than the output.

What collision resistance of a hash function doesn't mean that there aren't two messages $X$ and $Y$ that hash to the same value; instead, it means that it's hard to find them.


Which US standard includes a signature based on Ed25519?

In December 2015 there has been a followup on FIPS 186-4 where multiple organizations could respond to a few questions about that document from NIST. Many of them indicated that they would like Ed25519 to be supported (and Brainpool curves and Goldilocks-curve as well). There has been no followup 186-4 yet, so that means it is not in there (yet).

ANSI X9.62 and X9.63 were heavily influenced by Certicom (that use the same set of P-256 etc. curves). It's darn unlikely that they contain Ed2219 by now. There is no sign of it anyway, and the latest official X9.62 predates the official release of the curve by D.J. Bernstein.

In other words, it hasn't been standardized by these US based organizations yet.


Can I generate OTP secrets by using a hash?

Say the adversary is giving you $m_0$ and $m_1$, two arbitrary messages. You draw a random $sk$ and a random $b\gets\{0,1\}$ and output $E_{sk}(m_b)$.

So the adversary takes $ct=E_{sk}(m_b)$ and computes the XOR between the first $n$ bits of $ct$ and the $n$ first bits of $m_0$ (where $n$ is the original key length). Then, he does the same thing for $m_1$, so now he has two options for the secret key, $sk_0$ or $sk_1$. So far everything is good, because they are both equally possible, but now the problems begin: the adversary computes $md5(sk_1)$ and $md5(sk_2)$ and XOR the results with the bits $ct[n+1:n+\texttt{md5-length}]$. With a very high probability, only one of the options will make sense, meaning it would be the bits $m_i[n+1:n+\texttt{md5-length}]$ of some message, so he will know what you encrypted.


Formal relationship between encryption and random number generators?

Yes (loosely) and no (depending on your definition of a CSRNG).

A random number generator (restricting ourselves to Cryptographically Secure Random Number Generators) is actually a class of algorithms that produce a sequence of random numbers/bits - i.e. any sequence of numbers that is generated where the next part of the sequence cannot be predicted even with knowledge of the entire sequence to that point (with any non-negligible probability after a feasible amount of computation) can be a CSRNG, but a CSRNG can be constructed from cryptographic primitives in many different ways.

Symmetric encryption algorithms are generally either:

Stream ciphers, which are formally modeled as a Pseudo Random Generator or PRG. Technically these are usually a keystream produced by a PRG combined, e.g. by XOR, with the plaintext.
Block ciphers, which are formally modeled as a Pseudo Random Permutation or PRP.

Also in the general area of symmetric cryptography are Pseudo Random Functions or PRFs, which are often used as message authentication codes.

CSRNGs can be (and are) constructed from:

PRGs - a PRG is already a PRNG by definition.
PRPs - e.g. CTR_DRBG from NIST SP 800-90A
PRFs - e.g. HMAC_DRBG from NIST SP 800-90A. This also includes PRPs since a PRP is a pair of PRFs and you can just use the forward direction of the PRP.
(and also) hash functions - e.g. HASH_DRBG from NIST SP 800-90A

In practice a deployed CSRNG also involves gathering of entropy from the environment (otherwise it would use a static or predictable seed value, which would break the CSRNG contract) and other defensive measures to prevent the reverse-engineering of the internal state of the RNG.

Ignoring the entropy/seeding/defensive measures, if you consider a PRG to be equivalent to a CSRNG, then you can show a formal relationship to other symmetric cryptographic primitives since a PRG can be trivially constructed from any PRF (simply by using the PRF to encrypt an incrementing counter value).

As an interesting aside, PRGs, PRFs and PRPs can all be converted into each other using formal (although not necessarily efficient) constructions.


set of integers modulo an integer q in lattice

Well, these lattice schemes need to define a 'small vector' $\epsilon$ in such a way that the multiplication of two small vector elements $\epsilon_0 \times \epsilon_1$ is still small; that is, for a random element $A$, we still have $A \approx A + \epsilon_0 \times \epsilon_1$

One way to do this is to define a 'small vector' as one whose elements all have small absolute values; if you define 'small absolute value' tightly enough, then the elements of $\epsilon_0 \times \epsilon_1$ (ignoring the modulus operation) will still probably [1] have terms with absolute values less that $q/k$ (which is 'close enough' - the original schemes had $k=4$).

Of course, you might ask "why don't they define small vectors to have elements with small nonnegative terms?".  Well, if they defined the ring over $x^n+1$ (for example), then something strange happens.  Element $i$ of $A \times B$ can be expressed as

$$A_iB_0 + A_{i-1}B_1 + … + A_0B_i - A_{n-1}B_{i+1} - A_{n-2} B{i+2} - … - A_{i+1} B_{n-1}$$

Specifically, there are $n-i$ terms which are added to the final product, and $i$ terms which are subtracted from the final product.

For small $i$, there are a large number of added terms; if $A, B$ consists of small nonnegative elements, then the result will be strongly weighted toward the positive.  For large $i$ (just a bit smaller than $n$), the result will be strongly weighted toward the negative.  Hence, the result will have a distinct slant, and that's harder to reason with.

In contrast, if with generate $A, B$ with small absolute values (with no bias between positive and negative), no such bias exists; the distribution of the elements of the result is independent of the position within the vector.

[1]: This is where the probability of decryption failure comes in; most systems don't define the error terms small enough that decryption failure can't happen


Fully homomorphic encryption (over addition and multiplication) library in python

Most of the homomorphic encryption schemes work

over integers modulo some value, say n
or over bits.

In the first case, you can try to simulate floating-point numbers by first scaling all your original data to integers and keeping tracking of the scaling factors during homomorphic evaluation so that you can divide by the correct value after decryption. But this is generally not efficient.

In the second case, you can encrypt each bit of the floating-point numbers and implement circuits to add, multiply, etc, floating-point numbers using the homomorphic binary gates provided by the scheme, but this is very laborious.

The only scheme that I am aware of which works natively on (something very close to) floating-point numbers is this scheme by Cheon et al, which is implemented in this Github reposiroty.


Memory-hard proof-of-work: are they ASIC-resistant?

What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip?

DRAM memory is already pretty optimized for random memory accesses per second per dollar. Since a memory bound PoW spends more time waiting for memory than doing computation, there's little point in using an ASIC to speed up the computation. The bottleneck is DRAM latency. The ASIC is just a very expensive way to spend a larger fraction of time waiting for memory...

Also see related discussion at reddit.com/r/Bitcoin/.
For reference purposes (and in the unlikely case Reddit shuts its doors), here’s a copy of my post there:

hashcash functions must be cheap to verify to achieve their purpose.

  And thus memory hardness can only be achieved by going beyond the hashcash proof of work, as I wrote about in “Beyond the Hashcash Proof-of-Work (there’s more to mining than hashing)”, published at  cryptorials.io.

  The desirability of a memory hard PoW for a high market cap crypto currency is an open question with no easy answers and one that deserves more study.

  I think it could be desirable if it can radically change the economics of mining, to the point where mining is profitable for no one. That means that even the (hypothetically) most energy-efficient ASIC with custom memory technology, would still not have a positive ROI, due to the following reasons:

  fabrication costs are going to be much larger than for whatever memory technology is used for commodity computing devices, which still enjoy much larger economies of scale.
  electricity costs, while lower than for commodity memory, are unlikely to to be more than an order of magnitude lower.

  and the main reason:

  huge numbers of people could be willing to mine at a loss, just as they are happy to play the lottery. this requires a very low barrier to entry, like one click to install a mining app on your phone that will make it mine overnight while charging. it helps to know that your mining efficiency is not more than (roughly) an order of magnitude worse than with custom hardware.

  Of course I'm not claiming this is a likely scenario, but I think it's at least imaginable...

  Another possibility to consider is having 2 PoWs: one compute bound, and one memory bound, splitting the blocks between them. Mining the compute bound one would be (barely) profitable with ASICs, while the mining the memory bound one would be unprofitable, but help decentralization.

  Still, unprofitable mining is by no means a requirement for making memory hard PoWs desirable.

  It is conceivable that any memory technology developed to make the PoW's memory accesses as energy efficient as possible, will benefit many other classes of computation especially in mobile, solar powered, and other low-powered settings, as thus inevitably lead to commoditization.

  This argument works best for PoWs that do as little computation as possible apart from memory accesses, and I believe this is where Cuckoo Cycle's edge trimming shines.


Ensuring integrity of a client side script

In short any proposed solution to this problem would be a violation of CWE-602: Client Side Enforcement of Server Side Security.

Even if what you are suggesting where possible in some bizzaro universe it would be insecure.  A client (or an attacker) doesn't just execute scripts,  they are able to view and modify everything in memory,  as well as intercept,  modify and create any request transmitted over the network.  Thus checking the integrity of the script doesn't even close to solving the root of the problem.  In short this proposal is a fundamental violation of modern security and there never will be a solution to this problem. (And no one should need to do this)


Exactly two of the four roots must be greater than N/2

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

By simple arithmetic, one can see that $r < n/2 \iff n-r > n/2$.  Thus, assuming that $n$ is odd (which rules out the possibility that $r = n/2$), it follows that exactly one of each conjugate pair of roots is grater than $n/2$.


Galois Field multiplication instead of Diffie Hellmans discrete logarithm

The inverse is easy, it can be done by the extended Euclidean algorithm, thus polynomial in complexity compared to the others which are exponential.


How to require two PRIVATE keyholders to decrypt a document?

Yes, you can use a symmetric secret sharing scheme, where the parts required for secret sharing are encrypted with the keys of B and C. Once B and C decrypt the parts they can combine their parts to create a symmetric data key, which is the key that is used to encrypt the document.

The very simplest way of sharing a key between two parties is to create a random data key and encrypt the document. Then create a random byte array with the same size as the data key, call it the key part of B. XOR this key part with the data key; the result is key part of C.

Now simply encrypt the key parts of the respective parties with their public keys. Now they can only access it using their private keys. For sharing, they can decrypt their part and send their key part to the other party, if required encrypted with the other parties public key. That way the final party that gets the ciphertext and both key parts encrypted with their public key. They can decrypt, combine the key parts using XOR, giving the data key. Finally they can decipher the ciphertext.

This will also solve the issue with the size of the plaintext message. RSA is limited to a certain amount of data, so in case of a 1024 bit key, you only get 117 bytes of plaintext message. However, if you use AES/GCM and RSA/OAEP in the secret sharing scheme above, then you can encrypt a message of any size with the symmetric cipher.

Note that 1024 keys are not considered all that secure anymore; you should use a key size of 3072 bits or higher. PKCS#1 v1.5 padding, that you are using, is also considered less secure nowadays due to the Bleichenbacher attacks on it.


Authenticating Very Short (Sub-Block) Data

First, the fact that the data is "easy" to guess (in the sense that an attacker has a one-in-2^32 or a one-in-2^64 chance of guessing correctly) doesn't mean much if the attacker has no way of checking if his guess is correct. Or at least, it's not a problem with the cryptography.

Second, even if he does have that ability, the problem of protecting your data's secrecy is separate from the problem of protecting its authenticity. For example, it might be bad if an attacker can deduce that a message says "Yes", but it might be even worse if he can then tamper with the message so it now says "No".

In this example, the message itself was effectively only one bit long, but it definitely would make sense to have a long (e.g., 128 bit) authentication tag!

To answer your final question: No. As long as each key is random, then periodically changing your key is not a problem. In fact, in many situations it's recommended in order to limit how much data gets compromised if an attacker manages to obtain the current key.


Yes, it should be Ai, or more exactly A_i denoting subscript. Note that i (the chunk subscript) is not I (the salted password input). I submitted this to rfc-editor in Feb (see https://security.stackexchange.com/questions/112627/what-password-based-key-derivation-does-pkcs-12-use) and they said they were going to fix it; I guess it got lost.

For confirmation you can see the source document from RSAlabs-now-EMC linked there, at least as long as Dell doesn't start mangling the EMC website(s) the way EMC for years mangled the RSAlabs website.

And that PKCS12 PBE is still used, even though PBES2/PBKDF2 from PKCS5v2 is now recommended (and other options like bcrypt, scrypt, Argon2 even more).


Is there any way to check signed documents in a group of people without knowing who signed which?

There is more than 1 way to do it.
You can use Group signatures or Ring signature which allow anyone in a predefined collection to sign a message on behalf of a group. Group signatures require a group manager who creates the group and can de-anonymise the signer.
Ring signatures do not have such an entity and the signer cannot be de-anonymised.
There are variations of ring signatures like the linkable ring signature where the signer cannot be de-anonymised but signatures by a signer can be linked, i.e looking at 2 signatures $s1$ and $s2$, it can be determined if the same signer created them or not. More in the wikipedia article.

You can also use threshold signatures as M-of-N, i.e. M out of N parties have to sign and M <= N. In your case M will be 1 and N will be 3. One such scheme is BLS signature, section 5.3


Hash function without avalanche effect but with few collisions

Sure. The probability of collisions depends on:

How your symbols in the messages are distributed: Do messages have particular structure? Do some elements occur more often than the others?
How long the hash code is.
The structure of the hash code algorithm itself: Does it produce some hash codes more often than the others?

If all symbols are equally distributed and algorithm produces hash codes that are also equally distributed, then collision depends only on the hash code length. If hash code length is 512 bits, then the collision probability (with above mentioned assumptions) is $2^{-512}$.

The simplest function that fits your requirements is following:

hash(M) = M mod 2^512

If fits your requirements fully. To calculate it, you only need the last 64 bytes of the message. It means it is extremely fast. And the collision rate is the same as that of SHA-512.

If it is extremely fast, why nobody uses it? Namely because of your requirements: If has no avalanche effect. Hash codes are used normally to detect changes in the message. If there is no avalanche effect, changes will not be detected (in my example changes will be detected only in the last 64 bytes of the message, not in the previous bytes). I'm wondering for what purpose would you use such hash code.

To brute-forcing: If you exclude the avalanche effect, it means you will use only small part of the message to create the hash code. This means that also an attacker will consider only a small part of the message to brute-force. Means, brute-forcing will pretty easy.


Security of Pohlig-Hellman exponentation cipher?

You need a large random prime modulus where the discrete log is hard.  Read about how to choose a prime so the discrete log is hard.  Also, you want $p-1$ to have as few small factors as possible.  Therefore, the short version is, I suggest you choose a large random 2048-bit prime $p$ such that $(p-1)/2$ is prime.

However, Pohlig-Hellman has some serious issues.  It has very poor performance, compared to other symmetric-key ciphers.  Also, it has no randomization, so it is not semantically-secure (it is not IND-CPA secure) in its standard form.  I don't know of anyone who uses the Pohlig-Hellman cipher in practice, in its standard form; it is more of theoretical interest than practical interest.

What exactly do you want to do with the Pohlig-Hellman cipher?  What exactly is your application?  Why do you want to use the Pohlig-Hellman cipher?  There might be better solutions.


why just signing Ni and Nr is not enough?

Because we want to make sure that man-in-the-middle can modify (or hijack) the initial messages without being detected.
Consider this attack:

Alice sends an IKE_SA_INIT request to Bob

Mallet intercepts that message; he forwards his own IKE_SA_INIT message to Bob, using Alice's Ni value, but his own KE payload

Bob replies with an IKE_SA_RESP message, which his Nr value.

Mallet intercepts that message; he forwards his own IKE_SA_RESP message to Alice, using Bob's Nr value, but his own KE payload

Essentially, Mallet is establishing two separate IKE connections, one with Alice and one with Bob.
Alice then authenticates herself; if she just signed the Ni, Nr values she saw, Mallet could just resend that signature to Bob (which saw the exact same Ni, Nr) values, and so Bob would assume he's talking to Alice.
By appending the prf(SK_pi, IDi') value, this is not possible (because Alice and Bob don't have the same SK_pi value)


Cross correlation of two Boolean functions

In theoretical computer science literature, boolean functions are defined as
$$
f\colon \operatorname{GF}(2)^n \to \{\pm 1\},
$$
and the usual link with functions defined as
$$
\tilde{f}\colon \operatorname{GF}(2)^n \to \{0,1\}
$$
is via $$f(x)=(-1)^{\tilde{f}(x)}.$$

Edit Here's a standard reference from the Boolean function literature.


What, exactly, are your trying to accomplish with this construction?

Yes, you're correct in that, given a sequence of messages $m_0, m_1, m_2, \dotsc$ and a fixed ciphertext $c$ (assumed to be all of the same length), we can easily calculate a sequence of keys $k_i = c \oplus m_i$ such that $k_i \oplus m_i = c$.

However, I don't see any way to get a useful cryptosystem out of this.  If you don't transmit the keys $k_i$ to the recipient, there's no way for them to recover the messages $m_i$ just from $c$; indeed, that would be clearly absurd, since $c$ may be chosen to be completely random and independent of all $m_i$.  Conversely, if you do transmit the keys $k_i$, then the system is easily broken by an adversary who intercepts the "keys" — it's basically just a many-time pad.

Also note that you can't transmit the keys in advance, since, once $c$ is fixed, each key $k_i$ will depend on the corresponding message $m_i$.  So, unlike a traditional one-time pad, your scheme isn't even good for the "have secure channel now, need to communicate securely later" scenario.


I do many searches but can't find any explanation about "AES analysis using entropy"

Natural language has a nonuniform distribution. If a character $x$ appears $N_x$ times in a candidate decryption with $N$ characters, the sample entropy estimate will be
$$
\sum_{x \in X} (N_x/N) \log (N/N_x)
$$
by Shannon’s formula, where $X$ is the set of characters.
If the decryption is incorrect (wrong key guess) this value will be high, nearly equal to the maximum of $N \log |X|$ due to the fact that a wrong decryption results in random nearly uniform characters.
If $N$ is large enough and the message is in a natural language, it is very likely that the decryption with the lowest entropy is the one with the right key guess.
The cryptool site points to a help functionality but it seems that you need to download the package, the entropy reference does not appear in the online version.
Edit: So, this approach would only work in ECB (Electronic Codebook) mode for AES since it fails Ind-CPA. This basically means that the plaintext is divided into blocks 128 bits long, with no padding or randomized padding. Therefore the plaintext characters are distributed according to, say English, and have low entropy.


Why is the polynomial of an LFSR called so?

The polynomial $X^i$ is a delay operator, so formally $X^i(s_t)=s_{t-i}$.

It's also a linear operator so $X^i(a s_t)=a s_{t-i}$.

Let's apply this to the following simple LFSR in Fibonacci configuration

At each clock cycle, a new state $s_t$ is computed from delayed states $s_{t-1}$ and $s_{t-3}$, as $s_t=s_{t-1}+s_{t-3}$. That recurrence can be rewritten as $s_{t-3}+s_{t-1}-s_t=0$, and represented as the polynomial $X^3+X-1=0$ (the $1$ is a shorthand for $X^0$).  In binary, both $+$ and $-$ are eXlusive-OR $\oplus$ and we write the polynomial modulo 2, as $X^3+X+1.$

Moreover, not only is there a one to one correspondence between recurrences (equivalently LFSRs) and polynomials, but the roots of the polynomial feature in the solutions, i.e., the sequence generated.


Recombination thresholds in degree reduction of multiplied Shamir shares

This is the correct behavior. Since the degree of the multiplication sharing is $2t$, it will take $2t+1$ shares of either it directly or the subshares. If done on the subshares, the resulting sharing is of degree $t$.

Shamir secret sharing is commutative with respect to polynomial evaluation.

Let $\sigma_1^t$ be the polynomial for sharing $s$ with degree $t$. So, multiplying shares generated by $\sigma_1^t$ and $\sigma_2^t$ (which shares some $s'$), we get a share of $\sigma_3^{2t}$, which shares $ss'$. To reconstruct $ss'$ it would take $2t+1$ shares.

In the degree reduction step, we create subshares with a threshold of $t$, or $\sigma_4^{t}\circ\sigma_3^{2t}$, in other words, we have a degree $t$ sharing of a degree $2t$ share. Due to commutativity, we can rearrange things to get $\sigma_3^{2t}\circ\sigma_4^{t}$, then apply the inverse operation $(\sigma_3^{2t})^{-1}$, to get $(\sigma_3^{2t})^{-1}\circ\sigma_3^{2t}\circ\sigma_4^{t}$, which gives you $\sigma_4^{t}$.

So I have probably thoroughly abused notation, but hopefully that makes sense. You are doing the inverse operation on a $2t$ degree sharing in order to get back to the degree $t$ sharing.

Some consequences of this are 1) in MPC we assume that everyone will participate in the protocol. If one party refuses to participate, the degree reduction won't work. 2) This is used to establish the theoretic upper bound on information theoretic honest-but-curious MPC protocols.


Is there a point to having a large IV in AES

I've always known that the IV should be 128 bits, because that's the block size of AES, regardless of the key.

The IV depends on the mode of operation. It may well be that the block mode of operation specifies to use the block size, but this is not a given. For instance, AES-GCM defaults to 96 bits.
For CTR mode it is rather common to supply an IV, but in reality that consists of a nonce and a starting counter value; you could have implementations / protocols that only expect the nonce as input, which would then be smaller than 128 bits.

However, I just saw one vendor advertising AES-256 with a 256 bit IV.

Not many modes support that, so I'm wondering how they accomplished that. AES-GCM does support it, but at the expense of additional calculations. Furthermore, it doesn't increase security at all. It doesn't make much sense for AES-CBC mode either, as the second ciphertext block will be the IV, i.e. the effective IV would still be 128 bits.
The other more likely option is that they use Rijndael with a block size of 256 bits. In that case it is not AES (which is Rijndael with a block size of 128 bits and only 3 key sizes with the default number of rounds configured). In that case they really don't know what they are doing.

Is there any point to that? Does a 'double' IV bring additional guarantees? For example, reducing the probability of having the same IV with the same key?

No generally it doesn't bring any benefits. As it is hard to use AES in such a way that the block size of 128 bits isn't a limiting factor (e.g. when it comes to processing a huge amount of blocks), I don't see how a larger IV would alleviate that issue.

Will it even work with standard AES implementations, or they'll reject it? The Java implementation rejects it, for example.

Again, it depends on the mode; GCM may grog it. Java simply keeps to the standards, I've not seen Oracle deviate all that much yet.

Effectively, it adds another block of plaintext to throw away, but if it works, does it have negative effects (apart from having one more block to process)

Again, depends on the mode and how it is configured.

Or is it just a marketing mistake...

I might well be a marketing mistake. That's pretty likely actually. An engineering mistake (AES vs Rijndael) is also likely. It could however also be snake oil although you should not attribute to malice that which is adequately explained by stupidity.
However, definitive statements can only be made after more detailed analysis, and for that we need the source. I'd have them explain it to you.


Note: While writing this answer, I discovered what seems to be a gap in the proof given in the cited lecture notes.  I'll thus present a slightly modified version of the proof below, and discuss the discrepancy a bit at the end.

Let's start with a quick recap, since your quote and summary of the lecture notes leaves out some important bits.
The formal definition of a one-way function, slightly expanded from Definition 5 in your lecture notes, is:

A function (family) $f: \{0,1\}^n \to \{0,1\}^m$ is one-way if and only if it can be computed by a polynomial-time algorithm, and if there is no probibilistic polynomial-time algorithm capable of finding preimages for it with non-negligible probability.
In other words, for $f$ to be one-way, there can be no probabilistic algorithm $A$ that could, given the output $y = f(x)$ for some randomly chosen input $x \in \{0,1\}^n$ and a maximum run-time polynomial in $n+m$, find an input $x'$ (possibly, but not necessarily, equal the original input $x$) such that $f(x') = y$ with a probability that is more than a negligible function of $n$.

An informal summary of this, dispensing with all the formalism of asymptotic complexity theory, would simply be that $f$ is one-way if there is no practical way, given a random output of $f$, to find an input that yields that output when given to $f$.
Based on this definition, we can show that:

Padding the output of $f$ with, say, a bunch of zeroes doesn't affect whether it is one-way.  (By definition, the adversary will always receive a valid output, so they can just strip away the zeros and then proceed as if they were attacking the original, unpadded function.)

Also, adding a bunch of extra dummy bits to the inputs of $f$, which don't affect the output, doesn't change whether $f$ is one-way.  (Since the dummy input bits don't affect the output, the adversary can choose those dummy bits any way it likes; but finding the correct values for the other, non-dummy input bits is still exactly as hard as finding a preimage for the original, unmodified function.)

(These technically hold only if the amount of padding / ignored bits added is a polynomial function of the original input + output length, but that's plenty enough for our purposes: $n \mapsto 2n$ is certainly a polynomial function.)
So, given an (arbitrary) one-way function $f$ with $n$-bit inputs and outputs, we can construct another one-way function $h$ with twice the input and output length like this:

Let $x^*$ be the first $n$ bits of the input $x$ to $h$.  Ignore the rest of the input.

Compute $y^* = f(x^*)$.

Prepend an arbitrary constant $n$-bit string $c$ (e.g. $c = 000...0$) to $y^*$, and output the resulting $2n$-bit string $y = c \,\|\, y^*$ as $h(x)$.

Now, by construction, this function $h$ is one-way, since finding preimages for it is at least as hard as finding preimages for $f$.  (Of course, the security parameters for $f$ and $h$ differ by a factor of 2, but that makes no difference asymptotically; a polynomial function of $2n$ is a polynomial function of $n$.)
But also by construction, the first $n$ bits of the output of $h$ are always constant, while the remaining output bits depend only on the first $n$ bits of the input.  Thus, $h(h(x)) = c \,\|\, f(c)$ for all $x$, and so finding preimages for $h(h(x))$ is trivial (since literally any input will do).

Now, the construction given in the lecture notes you cite goes a little bit further, explicitly defining $h$ to yield an all-zero output whenever the first $n$ input bits are zero (and always setting the first $n$ bits of the output to zero otherwise).
While not strictly necessary (we'll get constant output from $h(h(x))$ anyway), this doesn't actually harm the one-wayness of $h$ either.  In fact, we can show that modifying $h$ so that it always outputs a constant value for a negligibly small fraction of the total input space doesn't affect its one-wayness (and that $1/2^n$ is, indeed, a negligibly small fraction as $n$ tends to infinity).
However, where the lecture notes go wrong is when they try to justify this by claiming that:

"A generalization of the previous theorem (fixing values in a one-way function) shows that $h$ is also a one-way function.  (In short, we are only fixing the values of $\frac{2^n}{2^{2n}} = \frac1{2^n}$ of all of the possible values of $x$.  Since we are only fixing a negligible fraction of the possible values of $x$, the same proof with slight modifications still applies.)"

In fact, this claim is false.  As a simply counterexample, consider the modified function $h'$ defined as:

Split the $2n$-bit input $x$ into two $n$-bit strings $x_1$ and $x_2$.

If $x_1 = c$, return $h'(x) = c \,\|\, x_2 = x$.

Otherwise, return $h'(x) = c \,\|\, f(x_1)$.

Clearly, $h'(x) = h(x)$ for all but a negligibly small fraction of the inputs (namely, those that begin with the $n$-bit constant string $c$).  Yet $h'$ is obviously not a one-way function, since any valid output $y = h'(x)$ always begins with $c$, and so is its own preimage!
Of course, this doesn't invalidate the actual claim, since the function $h$ actually constructed in the notes is in fact one-way (provided that $f$ is one-way).  Still, if these notes are from a course you're studying in, you might want to mention this gap in the proof to your instructor.


How to decrypt a short ciphertext that is said to be immune to attacks?

So Vigenere is similar to caesar. So you start decrypting it like you do with caesar:

S - +2 --> U
O - +3 --> R
M - +5 --> R
E - +7 --> L
B - +11 -> M
O - +13 -> B
D - +17 -> U
Y - +19 -> R

So you may have noticed, that the text is decrypt via using the next bigger prime. Just subtract the primes from the decrypted text and you get the original message.

I did not decrypt the whole message, but i have a strong guess "Somebodyoncetoldmetheworldisgonnarollme" is the result...


How does the nonlinear function of KeeLoq work?

Suppose you want to compute $F(0,0,0,1,0)$, then note that $00010_2 = 2_{10}$ so the result is bit $2$ (counted from $0$ from right to left) of 0x3A5C742E, or in C terms just (3A5C742E >> 2) & 1 = 1 This is the standard convention when encoding such Boolean functions.

As another example F(1,1,1,1,1) = (0x3A5C742E >> 31) & 1 = 0 as $11111_2 = 31_{10}$ etc.


Is BBS used for generation of keys for any modern cryptosystem?

I don't know of any implementations that use BBS.  I hope no important system is using BBS.  BBS is a poor choice for practical use.  The only benefit it has is that it comes with some security proofs -- but it turns out that those proofs are useless for all practical instantiations of BBS (for realistic parameter settings), so they're pretty much irrelevant in practice.  See Blum Blum Shub vs. AES-CTR or other CSPRNGs for details.


My pencil and paper One Time Pad works fine without modular math ...... or does it?

If you are not using modular arithmetic and an eavesdropper observes the ciphertext 64, they immediately know that the plaintext is 39 (encrypted with the key 25). With modular arithmetic, if the ciphertext 39 is observed, the plaintext can range from 14 (with key 25) to 39 (with key 0).

Note also that, since in your system the key space is smaller than the plaintext space, it is not perfectly secret even if you use modular arithmetic. As above, a ciphertext of 39 ensures the plaintext is between 14 and 39, not below (there is no key that encrypts 13 to 39).


Why are elliptic curve variants of RSA "chiefly of academic interest"?

The generic discrete logarithm problem is this:

  Given a group $(G, ·)$ with generator $g$ and $y \in G$, find $x \in \mathbb N$ such that $y = g^x$.

The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e. $(\mathbb Z/p \mathbb Z)^*$:

  Given a prime number $p$, a generator $g$ (of some large subgroup) and $y \in \left<g\right>$, find $x \in \mathbb N$ such that $y = g^x \bmod p$.

The elliptic curve discrete logarithm problem is this with a subgroup of an elliptic curve group:

  Given an elliptic curve $(E, +)$, a generator $G$ of some large subgroup, and $y \in \left<G\right>$, find $x \in \mathbb N$ such that $y = x · G$.

There are generic algorithms (such that the baby-step giant-step algorithm) for solving the discrete logarithm in any group (assuming a computable group law, or even just oracle access to the group law), and these work just fine for elliptic curve groups, as well as for the classic prime field. The average running time of these algorithms usually depends on the size of the group, like $O(\sqrt{|G|})$ for baby-step-giant-step. This is still exponential in the input size (since the input size is in $O(\log|G|)$, if one doesn't select really stupid encodings).

But for some special groups the discrete logarithm is easier, since they have some more (and known) structure. As an extreme case, consider the additive group $(\mathbb Z/n \mathbb Z, +)$ (for any positive integer $n$), with any generator. It is very easy to solve this problem even for quite large $n$ – we need only a single modular division, i.e. one execution of the extended euclidean algorithm. (And if the generator is fixed, we even can calculate its multiplicative inverse once and reuse it later, then it gets down to one multiplication per problem.)

The multiplicative group of the prime fields is harder. There is no known polynomial time algorithms, but there are still algorithms faster than the generic ones, using subexponential time. (Yes, there is some gap between exponential and polynomial.) The number field sieve for factoring integers can actually also be used to calculate discrete logarithms in prime groups (and needs similar running time for similar input sizes of both problems).

Thus we need larger prime field groups than we would need for a generic group for a same "security level".

For some elliptic curves, it looks like the discrete logarithm is almost as hard as for a generic group of the same size, which means that there are no specialized algorithms which are much faster than the generic ones. (When there are, one calls the corresponding group "broken". )

The effect is that for a similar security level, we can use quite smaller elliptic curve groups than prime groups (and it turns out that for these smaller groups, the calculation is also faster).

On the other hand, have a look at the RSA problem. It is about this:

  Given $n$ (a product of two large unknown primes), $e$ (with $\operatorname{gcd}(m,e) = 1)$ and $x < n$, we look for $m$ such that $x = m^e \bmod n$.

The most efficient known method to solve this (other than maybe a brute force attack on $m$ when it comes from a small sub space) is by factoring the modulus, then calculating the private key $d$ and decrypt it. So the hard problem here is factoring the modulus.

It is not really clear how to generalize this to any group (or what other kind of structure). I found A semantically secure elliptic curve RSA scheme with small expansion factor (2002), and it refers to (and includes an description of) an earlier work (N. Demytko. A new elliptic curve based analogue of RSA. EUROCRYPT ’93,
LNCS 765 40–49 (1993).)

Demytko's scheme works on an elliptic curve (and its twists) over the ring $\mathbb Z/n\mathbb Z$ (where $n$ is still a product of two large primes), and encrypts using $c = e \star m$, which is the $x$-coordinate of $e·(m,y)$ for some $y$ such that this is on the curve, and decrypts a ciphertext $c$ as $m = d \star c$, where $d$ is one of four inverses of $e$, and it depends on $c$ which one to use.

The second one even works in a curve over $\mathbb Z/n^2 \mathbb Z$ (but claims to be semantically secure, as it incorporates a random component).

In both cases it looks like the easiest way to break this is to factor $n$ (in the natural numbers), not some analogous problem in an elliptic curve based structure.

This means $n$ must be just as large as for RSA, and thus we have correspondingly large curves – not really an advantage of using elliptic curves here.


Soundness of Trevisan’s Extractor Against Quantum Side Information

In quantum key distribution communicators can bound the amount of information (quantum side channel entropy) that an eavesdropper can obtain about the transmitted key based on the fidelity of the transmissions. If an $n$-bit key has been transmitted and at most $n-m$ bits of information are available to an eavesdropper then a strong extractor (such as the Trevisan construction) can then used to produce an $m$-bit key about which the eavesdropper has essentially no information and which is therefore ideally suited as strong cryptographic key. This process is called privacy amplification by quantum key distribution practitioners.
UPDATE in response to query 7/3: Not all strong extractors can be proven resilient to quantum side-channel information. Also, an instance of an extractor must be chosen uniformly at random from a strong family. The advantage of the Trevisan extractor is that good extraction can be shown from a small family and so choosing an extractor from the family consumes less strong random information. In particular most families resilient to quantum information consume strong random seeds of length $O(n)$, but the Trevisan family consumes seeds of length $O((\log n)^3)$. The down side is that the computational overhead of the Trevisan family is markedly worse than its competitors.
It is possible that other extractors are resilient to quantum information, but we can prove this for the Trevisan construction. The ability to form this proof is largely because the construction is really $m$ independent 1-bit extractors. This means that significant information about the whole output can be used to deduce significant information about a single bit and so we only need to prove the resilience of an individual bit. This argument is very heuristic, a full technical argument is in appendix B of De et al.


Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate?

I think there is not necessarily immediate relationship between security of zk-SNARKs and the size of the arithmetic circuit. Mostly the security of zk-SNARKs depends on your security parameter, your cryptographic assumptions and what kind of security properties you want to achieve. In contrast, the size of the arithmetic circuit is more related to the efficiency of zk-SNARKs, such as prover/verifier running time and proof size. For sure sometimes if you need some stronger security property, for example, you want to achieve universal and updatable CRS, this would lead to a larger arithmetic circuit


Can we proxy-re-encrypt using homomorphic encryption schemes?

YES. It is pointed out by Gentry (in his thesis) when he consider bootstrapping and re-encryption.

Let us denote the old key pair by $(PK, SK)$ and the new key pair by $(PK^1, SK^1)$.

What the user wants is to re-encrypt an old ciphertext $C = \mathsf{Enc}(PK, M)$ into a new ciphertext $C^1$ which is decrypted into $M = \mathsf{Dec}(SK^1,C^1)$.

To do so without direct decryption, we virtually decrypt $C$ in the draft chamber guarded by $PK^1$, that is, we evaluate a decryption circuit with $PK^1$.
Correctly speaking, we do the following:

Generate $\widetilde{SK}_i = \mathsf{Enc}(PK^1,SK_i)$, where $SK_i$ denotes the i-th bit of $SK$.
Compute $\widetilde{C}_i = \mathsf{Enc}(PK^1,C_i)$, where $C_i$ denotes the i-th bit of $C$.
Evaluate the decryption circuit. That is, $C^1 = \mathsf{Eval}(PK^1, \mathsf{Dec}, (\widetilde{SK}_1,\dots,\widetilde{SK}_n,\widetilde{C}_1,\dots,\widetilde{C}_m))$.

From the correctness of evaluation, we have
$$
\begin{align}
\mathsf{Dec}(SK^1,C^1)
 &= \mathsf{Dec}(\mathsf{Dec}(SK^1,\widetilde{SK}_1),\dots,\mathsf{Dec}(SK^1,\widetilde{SK}_n),\mathsf{Dec}(SK^1,\widetilde{C}_1),\dots,\mathsf{Dec}(SK^1,\widetilde{C}_m))\\
 &= \mathsf{Dec}(SK_1,\dots,SK_n,C_1,\dots,C_m) \\
 &= \mathsf{Dec}(SK,C)\\
 &= M
\end{align}
$$
as we want.

This is just re-encryption Gentry suggested in his thesis.


Do storage encryption systems care about size of data?

It's common for encryption algorithm specs to specify a hard limit of how much data you should encrypt with the same key.  For example, consider the AES-XTS encryption algorithm, which was designed specifically for full-disk encryption:

The IEEE specification recommends that the length of a "data unit" (e.g., disk sector or block) encrypted with a single key should not exceed $2^{20}$ AES blocks.
The NIST recommendation upgrades this to a hard requirement.

Since each AES block is 16 bytes, and $2^{20}$ bytes is 1 MiB, that's a limit of 16 MiB ($2^{24}$ bytes) per data unit.  You need $2^{44}$ such data units to hit the $2^{64}$-block birthday bound, but 1 TiB ($2^{40}$ bytes) is only $2^{40} \div 2^{24} = 2^{16}$ times the size of the 16 GiB maximum data unit.  So disks don't appear to be big enough yet to hit this limit.

But note that this limit is per encryption key.  If you use multiple encryption keys then you get to reset the limit for each key that you use.  It's already common to use individual keys for each disk volume, and some filesystems (e.g, Apple's APFS) already support per-file encryption keys.


How can there be insecure elliptic curves if the discrete logarithm problem is hard?

Discrete Logarithm on elliptic curves is hard in the following sense: on an $n$-bit curve, solving DL has cost $2^{n/2}$. Thus, this is infeasible only as long as $n$ is large enough to make that cost prohibitive. A 256-bit curve is large enough; a 60-bit curve is not.

Also, some curves have a special structure which can be leveraged to compute DL faster. Notably:

If the curve order is not prime or does not have a big prime factor, then DL is easier (the same applies to normal non-curve DL).
Some curves have a low embedding degree, which allows for converting DL on the curve into a comparatively easier DL in the multiplicative subgroup of a finite field extension. This is very heavy in maths. If the curve is somewhat weakened but not too much, then it can still be safe while allowing computation of a pairing, an algebraic operation which is useful for some complicated cryptographic protocols (e.g. identity-based encryption).
Some curves make it easier to implement them securely, e.g. without leaking secret information through side channels.

Generating a new curve entails trying out equation parameters and checking that the resulting curve is not one of the known “bad cases”. In practice, a non-prime order is the most frequent case; for 256-bit curves, you need to try a hundred curves or so before getting one with a prime order. Curves with a low embedding degree are extremely rare, and easy to check for.


If I'm reading your specs correctly, you do this:
$IV||VAL||K_E||K_A=KDF(PBKDF(PW,Salt,Iterations))$. (Order doesn't matter here)

As far as I know this is common practice and shouldn't pose any security threats, as the IV is in fact unpredictable as it needs to be.

If I may I'd suggest you using EAX, CCM GCM mode if available, as this is easier than using CBC+AES and HMAC. If you can't use EAX/GCM/CCM, you may want to use CTR, as this poses you at less severe constraints regarding the IV (unique instead of unpredictable).


Problems with Matsui's Linear Cryptanalysis on round reduced DES

On 1: I have not seen the 14 bit claim disputed. Can you provide more details about how what you did corresponds to his paper and what goes wrong?
On 2: Since his attack complexity is larger than $O(2^{42})$ this brute force step is negligible, so acceptable. He actually improved his original attack to $O(2^{43})$ in a second paper.
Also $2^{42}$ encryptions is definitely doable even without special purpose hardware (see comment) these days. Even back then people railed against export restrictions which handicapped ciphers to 40 bits.


Sha256 has not long been cracked, but it's not useful for human-generated passwords. You want a key stretching function. SubtleCrypto provides PBKDF2 (documentation), which is fine. Other libraries might support bcrypt, scrypt, or Argon2, any of which would be better.
Salts should be unique per user. This is so that when two users have the same password, the hashes will be different. This prevents a variety of attacks, like rainbow tables or looking at the frequency of hashes. Having a constant value appended to the password doesn't make these attacks any more difficult.


Service to expose all encrypted messages its users sent. How protected would this data be?

To answer your primary question: Making encrypted messages accessible to everyone can be a security risk. A messaging system is typically asynchronous (meaning that you can send a message to someone that is currently offline), which makes it very difficult to provide perfect forward secrecy (great article how TextSecure solves this issue here). So an attacker with great storage capabilities (for example with a huge datacenter in Utah) could simply collect all messages that flow through your server and store them. Whenever the PGP private key of a user gets compromised, the attacker can simply go back to the recorded messages and decrypt all the messages that user received.
However, you also mention that you are assuming an adversary that can compromise the server itself. In that scenario, it doesn't matter whether or not every user can access all messages. I think it is important to first understand the goals of your messaging system as well as the different security building blocks you want to use.
Security Goals

Receiver Anonymity: By making the server a public repository for encrypted messages, you are basically creating a broadcast channel where everyone can potentially receive the message but only the intended receiver(s) can decrypt it. There exists a great body of research around receiver anonymity (e.g., this), but I am not sure whether this is actually the right approach to building your system. The problem that any kind of broadcast channel solution has is that each party has to attempt the decryption of each message, which does not scale very well (ironically, the receiver anonymity  increases with the amount of participants in the system). So regardless of whether or not the exposure of the encrypted messages to all participants poses a security risk from a cryptographic standpoint, I would not recommend this approach for a messaging system due to performance reasons.

Privacy: Using PGP will indeed provide confidentiality for your messages. However, it also requires the participants of your messaging system to have an authentic channel to retrieve each other's public keys. This cannot be the server itself, since you are assuming a potentially malicious/ compromised server setting. Threema thought of a good workaround for this problem where the server distributes the public keys but the user can verify the key's fingerprint via an out-of-band method (phone call, scanning the QR code, ...). Even if a malicious server would replace the public key of the receiver with its own, the sender could spot this by verifying the fingerprint.

Existing Building Blocks

Mixes: You can read about mix networks here. You basically achieve that a passive attacker can learn the identity of all sender and receiver but cannot link them together. This is the same level of anonymity as in your setting, as the malicious server knows who is connecting but does not learn which messages can be read by whom.

Implementation Recommendations
Have a look at XMPP/ Jabber. There exist great extensions for the protocol to offer end-to-end encryption and even OTR messaging.


Meet-in-the-middle probability of success

In the sentence, the "probability of success" of «1 in $2^{2m - 2n}$» or «1 in $2^{3m - 2n}$» really is an approximation of the probability of concluding that the key was found, when in fact another key that happens to give the same result as the true key for 2 or 3 blocks was found.

It should be read "probability of wrongly concluding success" instead; or "probability of false positive".


Can libsodium's X25519 encryption construction be generalized?

Yes. The general construction is called IES (Integrated Encryption Scheme), most often practiced as ECIES (elliptic curve IES). The principle is the same: use the “key agreement” primitive (DH, ECDH, X25519, …) to construct a secret that is shared by two parties, each of which knows both sides' public keys but only their own private key. The shared secret is then used to derive a secret key for symmetric authenticated encryption.
I don't know if libsodium's crypto_box conforms exactly to an official ECIES standard (there are many) in terms of how it formats the data. ECIES standards have a lot of options in terms of the group (DH group or EC curve), on what data is included in the derivations, and on the freshness of parameters (e.g. ephemeral vs multiple-use keys). Depending on these options, the resulting constructions may have different properties in terms of nonce-misuse-resistance, resistance to a compromise of the private key, resistance to side channels, etc. But the basic principle of hybrid encryption constructed on top of a key agreement is the same.
Some reading on how the details of how IES is done influences secondary security properties:

Neil Madden, Public key authenticated encryption and why you want it (Part II) — “Option 2: Authenticated Encryption from Diffie-Hellman” ff.
A short discussion of ECIES vs. crypto_box for zcash


What does this advantage statement signify?

It means exactly what is written, the advantage of the adversary is a quantity which is defined as the difference between the probability that $b = b'$ and $1/2$. For example if the probability that $b = b'$ is $3/4$, then the advantage of the adversary is $3/4-1/2 = 1/4$.


What is this "finite field cryptography"?

"Finite field cryptography" is fancy language for group-based cryptography done over the integers modulo a prime (instantiating a field) to distinguish this more "classic" approach from the new fancier elliptic curve cryptography.

Example:
Finite Field Diffie-Hellman: Diffie-Hellman done in $\mathbb F_p$.


Issue implementing Pollard's Rho for discrete logarithms

First of all, Pollard Rho finds an essentially random solution $(B - b) \gamma \equiv (a - A) \pmod{N}$.  This randomness implies that if $N$ has a prime factor $p$, then $B - b$ has a probability $1/p$ of having $p$ as a multiple (and hence it will fail in precisely the way you've seen).

Pollard Rho is normally used with $N$ being a large prime; the only prime factor $N$ has is, in fact, $N$, and so it has a tiny change ($1/N$) of failing. You, of course, are using it with toy parameters, and so the chance of failure is much higher.

This does being up a nontrivial point; in the group $Z_p^*$, $N = p-1$ is always even; doesn't this mean that Pollard-Rho always have a 50% probability of failing?

Well, it would, if we used it in the straight-forward manner.  However, what we do is perform the operation in a prime subfield (or, at least, a subfield with no small factors); this makes the failure probability tiny.

If we do have to do the work in a group with a size that has small factors, say, $N = hq$, where $h$ is smooth, and $q$ has no small factors, then what we can do is compute $a^h$ and $b^h$, and use Pollards-Rho to compute $\gamma'$ such that $(a^h)^{\gamma'} \equiv (b^h)$; this is in the $q$-sized subgroup, and so has a high probability of success.  Given $\gamma'$, it's easy to reconstruct $\gamma$, as $\gamma \equiv \gamma' \pmod q$


Does AES 256 really make sense in hybrid crypto systems when the PKI is the bottleneck?

It's possible to use much larger key sizes than 2048 bit RSA for TLS. So the argument that 256 bit RSA provides much more security than 2048 bits RSA may not apply.

If used with a 2048 bit RSA key then using AES-256 may not make too much sense. But don't forget that AES-256 will be used to encrypt large amounts of plaintext, and that attacks on AES will be quite different from attacks on RSA. Furthermore, AES-256 is not that much slower than AES-128 - and certainly not twice as slow as you may expect.

In general using AES-128 or AES-256 won't make much of a difference. Using EDH for perfect forward secrecy or the application of strong(er) authentication will arguably have more of an impact on security.


Recovering key in AES - Infinitely many known plaintext ciphertext pairs

For any given AES key there are only $2^{128}$ possible plaintext-ciphertext pairs, so you can never have arbitrarily many such pairs.  Moreover, if the attacker has access to all $2^{128}$ such pairs for a given key they can mount a "code-book" attack, whereby they don't need the key at all to decrypt any message that they want to decrypt.  For example, if they see any particular 128 bit block of ciphertext the attacker can simply query their database of possible plaintext-ciphertext pairs and directly find the corresponding plaintext, without ever needing to go through the trouble of breaking the key.


How to perform homomorphic multiplication in ElGamal?

Assume we are working in a cyclic group $G$ with generator $g$ and let $A$ denote the public key in use.

From the definition of ElGamal encryption, we have $R_i = g^{r_i}$ and $c_i=A^{r_i}\cdot m_i$, where $r_i$ is some random number, for $i\in\{1,2\}$. Hence, with $R:=R_1\cdot R_2$ and $c:=c_1\cdot c_2$ (where $\cdot$ denotes $G$'s operation), we have obtained
$$ R = g^{r_1}\cdot g^{r_2} = g^{r_1+r_2} $$
and
$$ c = A^{r_1}m_1\cdot A^{r_2}m_2 = A^{r_1+r_2}\cdot m_1m_2 \text, $$
so $(R,c)$ is precisely an encryption of the message $m_1\cdot m_2$.


Are there any SSL cipher suites that will not be affected by the post-quantum world?

Symmetric algorithms are secure post-quantum, only with less bits of security (usually about half). That means you only need to care about the authentication and key exchange parts of the cipher suite. Suites that don't use public key authentication or key exchange, i.e. preshared key suites, are post-quantum secure, but not useful in most usecases.

There are post-quantum ways to do key exchange, but SSL/TLS does not currently support any.

(In practice, at least. There is an old draft for NTRU in TLS, and apparently even some implementation(s), but the usual SSL libraries do not support it.)


Diffie-Hellman relies on a mathematical problem on positive integers. To use it with bytes you just have to convert the bytes to - or use the bytes as - an integer. Usually this would be a unsigned big-endian (or network order) integer.

For Diffie-Hellman the parameters consist of the modulus and the base. The public value could be 1024 bits (128 bytes). 1024 bit cryptography is considered "legacy strength" for discrete logarithm related problems though.

With Java for instance the conversion can be as easy as new BigInteger(1, data) where 1 indicates a positive integer and data is a byte array.


risk of attacker decrypting RSA ciphertext without public or private key

When we say "RSA is broken" do we mean that a practical attack is discovered to retrieve the private key from the public, or do we mean that given a ciphertext and no knowledge of either the private or the public key the attacker can decrypt the data?

First off, we always assume the attacker has the public key. Someone saying "RSA is broken" could mean either. The first is a key recovery attack; the second is a message recovery attack. The second (finding $p$ from $c=p^e\bmod{n}$) is what is known as the RSA Problem. It just so happens that currently the fastest way to solve the RSA problem is to recover the private key (think factoring) and then recover the plaintext. It has never been shown that there doesn't exist a better way to find $p$ however (for more on this, see this question).


Understanding the groups used in bilinear Ate-pairing

$E(\mathbb{F}_{p^k})[r]$: all elements $P$ of $E(\mathbb{F}_{p^k})$ such that $rP = 0$. In other words, all points whose order divide $r$. In protocols $r$ is usually prime, so that means all points with order $r$ and the point at infinity.

$\pi_p$: the Frobenius endomorphism. This is a function that takes an elliptic curve point such that $\pi_p((x, y)) = (x^p, y^p)$.

$[1]$: the identity function, i.e. $[1](P) = P$

$\pi_p - [1]$: the function $(\pi_p - [1])(P) = \pi_p(P) - [1]P$

$Ker(\pi_p - [1])$: the kernel of the given function. The kernel of a function is composed of all elements that map to the identity element. In our cases, all points $P$ such that $\pi_p(P) - [1]P = 0$, i.e., $\pi_p(P) = P$. In non-extension finite fields (i.e. $k = 1$) it is true that $x^p = x$ and therefore $\pi_p(P) = P$ for every point with coordinates in a non-extension field. Therefore $Ker(\pi_p - [1]) = E(\mathbb{F}_{p})$ and that was a huge roundabout way to write that $G_1$ is the same as $E(\mathbb{F}_{p})[r]$.

$Ker(\pi_p - [p])$: following the same reasoning, in this case, these are all the points $P$ such that $\pi_p(P) = pP$, i.e. the Frobenius mapping is a much faster way to compute $pP$, which is a much more interesting mapping. Therefore $G_2$ are all the $r$-torsion points in $E(\mathbb{F}_{p^k})$ where that equality is true.

$\mathbb{F}_{p^k}^*$: the multiplicative subgroup of the finite field $\mathbb{F}_{p^k}$ (i.e. all non-zero elements under the multiplication operation).

$(\mathbb{F}_{p^k}^*)^r$: the multiplicative subgroup where all elements are raised to the $r$-th power.

$\mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r$: this is the confusing part. This is a quotient group, and its elements are cosets (sets of field elements). Elements $x,y$ are in the same coset if $x/y = h^r$ for some element $h$. There will be $r$ such cosets, each with $(q^k-1)/r$ elements. However, since it is difficult to work with cosets in cryptographic protocols, in the end they select a "canonical" element by raising the element of the coset (which is the intermediate result of the pairing computation) by $(q^k-1)/r$, the so-called "final exponentiation". This implies that the set of canonical coset elements are the $r$-th roots of unity, i.e. all elements $x$ such that $x^r = 1$ (because $x$ was already the result of exponentiation by $(q^k-1)/r$, if we raise that by $r$, we are computing the full exponentiation by $q^k-1$ which is the order of the multiplicative subgroup and we get back to $1$).


Explaining modulo reduction of curve25519, multiply hi bits with 38 trick?

Let $p = 2^{255} - 19$.

Clearly $p \equiv 0 \pmod p$, meaning $p$ (the modulus) divides $p - 0$ (the two sides of the equation), or equivalently: there exists some integer $k$ such that $p - 0 = k\cdot p$.  (Here $k = 1$.)

So $2^{255} - 19 \equiv 0 \pmod p$, and thus $2^{255} \equiv 19 \pmod p$, meaning there exists some $k$ such that $2^{255} - 19 = k\cdot p$.  (Here, again, $k = 1$.)

If we multiply both sides of the equation by $2$, then we get $2\cdot 2^{255} \equiv 2\cdot 19 \pmod p$, meaning there exists some integer $k$ such that $2\cdot 2^{255} - 2\cdot 19 = k\cdot p$.  (Here $k = 2$.)

But this equation is just $2^{256} \equiv 38 \pmod p$.

Hence, whenever you are doing arithmetic modulo $p$, the quantities $2^{256}$ and $38$ are equivalent.  Since reduction modulo $p$ is a ring homomorphism—that is, $$[(a + b) \bmod p] \equiv [(a \bmod p) + (b \bmod p)] \pmod p,$$ and likewise with multiplication—we can split a number $n$ into the low 256 bits $n_{\mathrm{lo}}$ and the rest $n_{\mathrm{hi}}$ so that $n = n_{\mathrm{lo}} + 2^{256} n_{\mathrm{hi}}$.  Then $$n = n_{\mathrm{lo}} + 2^{256} n_{\mathrm{hi}} \equiv n_{\mathrm{lo}} + 38 n_{\mathrm{hi}} \pmod p.$$


AES/GCM/PKCS5Padding giving issues while AES/CBC/PKCS5Padding works fine for my use case

AES-GCM uses AES-CTR to create confidentiality internally. Counter mode turns AES into a stream cipher, where the plaintext is XOR'ed with a generated key stream. This key stream can be applied bit by bit or - practically speaking - byte by byte (with the leftover key stream bytes after encrypting the last counter simply being discarded). Specifying any padding at all is a waste of effort for a stream cipher. Instead you should be using "AES/GCM/NoPadding" for Java.
I would not bet that other implementations allow GCM with PKCS#5 padding. Furthermore, it is the question if that mode would always be using no padding (as it isn't required), 1 byte of padding (since a stream cipher works with "blocks" of a single byte) or up to 16 bytes of padding (because the block size of AES is 16 bytes).
GMAC, the internal MAC operation of GCM also requires padding as it operates on 128 bit values. But as common with MAC algorithms, only one particular padding is used, so it doesn't need to be specified - it is not a configuration option.


Brute force against computational security

For a (fixed-length) cipher to meet your first condition, it needs to be the case that it's no easier to guess the plaintext if you have the ciphertext than it is to guess the plaintext without the ciphertext. Now, suppose I send a random 1024-bit string XORed with $G(k)$ for some 128-bit $k$ and computationally secure $G$. The probability that my message is $0\ldots0$ is exactly $2^{-1024}$. I encrypt my message with a 128-bit key selected uniformly at random from the space of 128-bit keys to get $c$. Now suppose you intercept $c$. You know it's encrypted with some key $k$; you know there are $2^{128}$ such keys. That means that there are only $2^{128}$ possible decryptions -- at most 1 per key. This is why the keyspace of a perfectly secure scheme must be at least as big as the message space: knowing the ciphertext means that the number of possible messages is reduced to the number of possible keys, and if there are fewer keys than messages we've eliminated a lot of messages. That means that knowing "this ciphertext can decrypt to $m$" tells us that it's much more likely to be $m$ than we had suspected beforehand.

If $K=k$, then $M=c\oplus G(k)$. So, $$\Pr[M=c \oplus G(k)|C=c] \ge \Pr[K=k]=2^{-128}\ne 2^{-1024}$$ for any $k$. Suppose, for instance, that you try $k=1\ldots1$ and find that $c\oplus G(k)=0\ldots0$. You now know that $$\Pr[M=0\ldots0|C=c]\ge\Pr[K=1\ldots1]=2^{-128}\ne 2^{-1024}=\Pr[M=0\ldots0]$$ after a very quick computation (just one evaluation of $G$). That means that even with a computationally secure cipher, given $c$ an attacker can easily find a message $m$ such that $\Pr[M=m|C=c]\ge 2^{|k|}$ -- specifically, $\mathsf{Dec}(c,0...0)$. And that violates $\Pr[M=m|C=c]=\Pr[M=m]$ in a single evaluation of $\mathsf{Dec}$.


Hash Function representation in identity-based encryption

The authors describe it that way because the functions operate on different inputs and produce different outputs. In your first example $H$ outputs an $n$ bit string, while in the second $H$ outputs an element of the field $F_q$. Clearly, one can represent an element of a field $F_q$ by a bitstring of size $n$ for some $n$ (using some suitable encoding). However, I guess that the authors who use the second definition use the output of $H$ for some computation in $F_q$, while the authors that use the first one use it to compute an XOR with some other $n$ bit string or the like.

The product just means that the function takes as input a pair $(a,b)$ where $a$ comes from the first domain ($F_q$ or $\{0,1\}^*$) and $b$ comes from the second domain ($G_2$ or $\{0,1\}^*$). The details how $H$ exactly looks like is not specified by this notation. For instance, if $H$ has two inputs $(a,b)$ one way of implementing it is as $H'(a\|b)$ with $a$ and $b$ being some encodings to bitstrings and $\|$ denotes concatenation and $H'$ takes inputs from $\{0,1\}^*$.


Passphrases, Dictionary attacks and 'bit shift'

If you ask a computer to pick a sequence of four words out of 10 000 (with replacement) uniformly at random, there are about $2^{53}$ possibilities; an attacker can expect to guess $2^{52}$ of them before getting the right one.  (For scale comparison, the Bitcoin network guesses and tries thousands of times more possible inputs than that to a hash every second.)

If you ask a computer to pick a sequence of four words out of 10 000, and one of the 24 permutations of four elements from the symmetric group $S_4$, then there are about $2^{53} * 24 \approx 2^{57}$ possibilities, although the number of distinct outcomes will dwindle once you account for alliteration.

If you ask a computer to pick a sequence of five words out of 10 000, there are $2^{66}$ possibilities, all distinct.

Which would you rather memorize: a permutation in $S_4$ causing words to be spelled differently, or another word?  I'd take the other word—in fact, I'd take six other words and invent a mnemonic for myself, to raise the number of possibilities above $2^{128}$ so an attacker has no hope of ever trying anywhere near enough passwords to guess correctly even in an offline parallel attack.

But whatever you do, don't try to pick the words and permutations yourself in your head.  Your mind is a terrible source of entropy.


CSPRNG generation vs asymmetric encryption performance

It costs a median of about 300 cycles on a modern x86 system to compute the ChaCha pseudorandom function, generating 64 bytes of output from a 32-byte reusable key and a 16-byte input.

It costs a median of about 50000 cycles on a modern x86 system to compute a 64-byte Ed25519 signature.

These numbers are from https://bench.cr.yp.to/.  The fastest signature schemes reported there still cost over 1000 cycles.

But what on earth are you doing where there is any question of whether you should use a PRNG or a public-key signature?  This is like going to a bicycle shop and asking whether you should buy a wheel or a handlebar.  You should identify what your application's goals, threat model, and security needs are first before you try picking the fastest handlebar for your bicycle.

If I screw up my eyes and stand on my head and take your inquiry to mean that you want some properties of a pseudorandom function and some properties of a signature, maybe you want a VRF—but causing onlookers to have to stand on their heads is no way to build a secure system!

P.S.  Signature is a fundamentally different concept from ‘encrypting with the private key’.


How can I combine Quorum and Zero Knowledge Range Proofs

Now there are a lot of interesting variants of Zero Knowledge Proofs with and without trusted setups. The traditional ZK SNARKS had a requirement for a trusted setup and demanded larger proof size and prover time and verifier times. However in the recent times Bullet Proofs have reduced the proof size significantly. ZK STARK is a recent Zero Knowledge Proof technique that has introduced transparent Zero Knowledge Proofs. Please find reference to two Zero Knowledge Proof based Toolsets implemented on JPMorgan Quorum protocol in the recent times.

ZSL on QUORUM

Anonymous ZETHER


Is this mentally computable password system, cryptographically secure? And anything like this out there I can find?

Firstly, you shouldn't really invent your own password manager, except for fun/experimentation/learning purposes.  Especially if you are a beginner.
Regarding your comments, I don't really see how managing your own in your head can be less hassle than managing a standard one on a machine.  I use google/chrome's (BOO!) so can use across devices and could give away passwords to certain accounts, for whatever reason.
You may find this interesting reading.  It seems very similar to your idea.  It uses a pin as well as a cue for each site.  It also goes into detail about the reduction in security as you use the system to "generate" more passwords.
Your scheme gives away bits of the master key in each password, and has virtually no real entropy.  There is a 23.5% chance the letters in your passwords will be 'g'.
If we change the lyrics to something tasteful like the opening verse of Dylan's Subterranean homesick blues, we still have 0% chance of a 'z'.
There are 256 possible values in a random byte.
Imagine another scheme I invent which uses a cryptographically secure salted hash, where the salt is the website address/master key/time added to database, and the input to the hash is the master key. My master key is "never gonna give you".

Each of my website passwords might be anything.  They are not all based on the letters in my master key.
If websiteX password is breached, it gives an attacker nothing about the password for websiteY, or the master key.
When I change my password for websiteX, I don't need to change my master key.
The basic security of my system relies on a cryptographically secure hash that wasn't designed by me.

Obviously (as mentioned) I wouldn't use my own scheme because there are already better existing schemes designed (and implemented) by people who know better.


Factoring large $N$ given oracle to find square roots modulo $N$

What I have come up with till now is, first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a\equiv\pm b\pmod N$. Repeat this for all points.

This has (at least) two problems:

For a fixed input, $S$ will always return the same square root.
You can not "repeat this for all points" since there are $\mathcal O(N)$ of them, hence your algorithm $F$ will not be (probabilistic) polynomial-time.

As to how we can fix this: Since $S$ will only give us one square root, we somehow have to obtain the other one (modulo negation) ourselves. A good (efficient) way to do this is to simply construct the number given to $S$ in a way that we already know one of its square roots, and hope that $S$ will give us the other one. Here's an algorithm:

Choose $x\in\mathbb Z_N^\ast$ at random.
Pass its square $x^2$ to $S$; call the result $y$.
If $x\equiv\pm y\pmod N$, we were unlucky: Start over with a new $x$.
At this point, we know from
$$ x^2\equiv y^2\pmod N $$
that
$$ x^2-y^2=(x+y)(x-y) $$
is a non-zero multiple of $N$ while neither $x+y$ nor $x-y$ alone is, hence we can recover a factor of $N$ by computing
$$ \gcd(x+y,N) \text. $$

Now we would like to prove that this algorithm is (probabilistically) efficient. Our choice of $x$ is equivalent to first choosing some square $r$ at random and then choosing $x$ as one of $r$'s square roots also at random. The oracle $S$ is deterministic, hence will always return the same square root $y$ of $r$. Therefore we have a probability of $\frac12$ that our choice of $x$ is not in the same "class" as $y$, i.e. $x\not\equiv\pm y\pmod N$, thus yielding a factorization. Clearly one iteration of this algorithm runs in polynomial time, and the expected number of iterations to succeed is only $1+\frac12+\frac14+\dots=2$. Therefore $F$ efficiently factors $N$.


Clarification regarding multiple modular exponentiation

Here's one approach that, assuming $x, y, z$ are random, takes approximately the same time as two exponentiations.

The general idea is to treat x, y, z as base 4 values, which we scan from the lsbit direction.  We keep running values for $R1, R2, R3$, which are initially 1.  At iteration $i$, we have the value $b^{4^i}$ and $b^{2 \cdot 4^i}$ (which takes two modular squarings to compute); if any of $x, y, z$ have a 3 in the digit $i$ position, we also compute the value $b^{3 \cdot 4^i}$ (this happens with probability 0.578, and takes one modular multiplication when it does).  Then, for each of $x, y, z$, if their digit $d$ is not 0, then we multiply in $b^{d \cdot 4^i}$ into the corresponding $R$ value; for each variable, this takes one modular multiply with probability 0.75, for a total of 2.25 expected multiplies.

If we add everything up, we have 2 modular squarings, and 2.828 modular multiplications per step; for 160 bit exponents, there are 80 steps.  If we remove one squaring (for the initial computation of $b^{4^0}$), and the 3 initial modular multiplications of $R1, R2, R3$, we get a total of 159 squarings, and 223 multiplications; this is in the same ballpark as twice the number of operations a good modular exponentiation for a 160 bit exponent would take.

I suspect that this isn't the best possible; it does show that some speed up can be achieved.  On the other hand, I rather suspect that it'd be impossible to compute all three $R1, R2, R3$ in the same time that it takes to compute one of them; some slow down would appear to be inevitable.


What security checks do I need for SRP-6a?

This is a good question, but I would consider hardcoding a known good group. There does not seem to be an advantage to letting the server decide if you can afford to use high enough parameter values.

The SRP paper lists the following checks:

"n is a large safe prime" (this is your first three points)
"g is a primitive root of GF(n)" (your next point)
"A > 0" (modulo n, which you make sure of by checking the upper bound)
"B > 0" (ditto)
"a, b > log[g] n" (missing)

(The ordering constraint in your last point is mentioned elsewhere.)

You are missing the last one from the paper, but it is not essential:

  The probability of this happening is infinitesimal (less than 2^-1014 for 1024-bit n), but the check is trivial.

One of your checks is unnecessary:

  Verify that $u \neq 0$.

This will never happen with a secure hash, and if the hash allows finding inputs that force this, you will have worse problems. (But it is a fast check, so no problem.)

  Regarding the primality checks, what algorithm should I use?

Miller–Rabin is common. AKS is too slow in an interactive protocol. I would follow the recommendations from standards like FIPS 186 (pdf), if you must do this.

  Should I randomize the parameters during the primality check in order to prevent a false server from finding a composite that passes what the client checks?

Miller–Rabin uses random numbers anyway. Also, by choosing the correct number of rounds (see above) you should be able to make the probability of a false positive low enough to make finding one impossible.


Multi-party decryption, no central decrypter

I just wanted to give you a hint, but since I cannot write comments under your question, I write it here:
I think you are searching for a scheme that whenever the secret is reconstructed, the participant's keys dont reveal. We have such schemes, please see this Lecture Note Chaper 6.

Lecture Note information: Lecture Notes, Cryptographic Protocols, Version 1.21
September 13, 2016, Berry Schoenmakers
The name of the protocol is: Threshold Elgamal Cryptosystem  But the whole chapter that I mentioned is more informative than just this protocol.


RFC6979: error in reference implementation?

The RFC specifies things in terms of bits. Each call to HMAC outputs hlen bits. tlen is the count of bits obtained so far; when at least qlen bits have been obtained, this step is finished.

The sample code is written in Java in which the elementary unit of information is the octet ("byte" in usual terminology). The supported hash functions always output a given number of bytes, and there is no fractional byte. In other words, within that code, hlen is always a multiple of 8. This implies that tlen is also a multiple of 8.

The rolen value is the length of q in octets; that is, it is equal to qlen/8, rounded up. This is OK in the code, since hlen is a multiple of 8. For instance, with a curve such that qlen is 252, the generation needs 252 bits of output from HMAC; but since hlen is a multiple of 8, you cannot get 252 bits of output without getting at least 256 bits of output. Thus, the code can keep track of things counting octets (hence, rolen) instead of bits. With HMAC/SHA-256, you get 32 bytes of output per HMAC call; and rolen is 32. Thus, one call will be enough to get rolen bytes, and there won't be a second one.


Do hash functions need to "look random"?

The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.

The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.

However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n\|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)


For the scrypt HMAC storage format, why run the input of the hash and the hash itself into the HMAC

Since any change in bytes 0 to 47 would change bytes 48 to 63. Why bother providing bytes 0 to 47 as input into the HMAC. Would the security be the same if the HMAC used bytes 48 to 63 as input?

No, because that would be taking the HMAC of a 16-byte, i.e. 128-bit hash, rather than the 48-byte actual value. The HMAC has 256-bit security, while taking the HMAC of the hash would only have 128-bit preimage resistance and 64-bit collision resistance.

Now, whether that could lead to a practical attack, I am not so sure. A collision attack on the hash could be within reach, but I cannot immediately see any benefit to an attacker from it. Still, if you are going to take a 256-bit HMAC, there is no need to reduce the security with an initial hash.


PBKDF2-SHA256+SHA256 for password storage

Thanks to @Stephen Touset for the solution.

In order to avoid tying the session cookie to the user's password (and avoid using PBKDF2-SHA256+SHA256), we can simply create a random $key$ for the user upon login. $SHA256(key)$ is then stored in the db, along with a session ID that ties the session to a specific user.

$key$ is then used as the preimage in the session cookie. Upon each request, we calculate $SHA256(key)$, and compare it to the value stored in the db.


How to combine $n$ 'less random' bits to generate one 'more random' bit?

If the outputs of badrand are independent and identically distributed you can use a randomness extractor function with $m=1$ and $k=-n\lg 0.9$.
If you're prepared to have a non-deterministic waiting time for an output, the von Neumann extractor is good way to get probability exactly 0.5 out of i.i.d. bit outputs. Sample pairs of bits until you get a pair with precisely one zero; if your pair is 01 return 0 and if it is 10 return 1. The i.i.d property means that the probability of these two events is equal (in your example both have probability 0.09 and resampling has probability 0.82, leading you to expect around 100/9 badrand outputs to produce one betterrand output).


Using a Unix Timestamp as the sole source for the nonce would make me nervous.

In addition to forged NTP replies (and legitimate operators deliberately resetting the clock for some reason, and I'm not sure whether leap seconds would pose a risk), you also would need to worry about "what if I send two messages within the same second"

On the other hand, you have 12 bytes to play with; if you use four of the bytes to hold the Unix timestamp, and use another four as a counter (which you increment every time you send a message), and the other four as something else, that'd be a system which would be more resilient against nonce repeats.