Exactly how bad is using 'mod' to clamp reduce numbers to a given range?

The answer is that it depends on how much larger $n$ is than $m$, and also depends on the application. If $n$ is much larger than $m$ (say 64-128 bits longer) then you are fine, as pointed out by @Ricky Demer. However, otherwise, you will have bits that have a bias.

If you are using this key in HMAC, then it doesn't matter. However, in general, it can matter and can matter a lot. Thus, I strongly recommend against doing this without making $n$ at least 64-128 bits longer than $m$. If you want to see a work where small biases are used to recover plaintext, then Analysing and Exploiting the Mantin Biases in RC4 is a good place to start.


Is AES still secure considering all this NSA/Snowden scandal?

Let's clear some bullshit first:

  Now as the NSA GCHQ et al know very well the more efficient you make the implementaiton of crypto code the more side channels it has unless extream caution is observed. One thing we do know is that optomised for speed and minimized number of gates is an almost certain guarentee of side channels no matter how clever you are.

The horrendous spelling issues aside, this is absolute bullshit. On almost any CPU there are only three things in symmetric crypto that introduce side-channels:

Branches dependent on secret data.
Table lookups with an index dependent on secret data.
CPU instructions that take non-constant time/power.

AES suffers from potential side-channel attacks because the obvious implementation of the S-box violates #2, and the obvious implementation of polynomial multiplication violates #1. Both issues can be avoided using trickery, though.

But in general you can optimize all you want as long as you don't branch on secret data, don't do table lookups with secret data and make sure that the CPU instructions you use always take the same amount of power and time (notable violaters of this are multiplication instructions in many lesser-known CPUs).

As to the question in the title, AFAIK Snowden has not published any documents that show cryptanalysis against AES, so AES is still as secure as before. I do not know whether Snowden published documents of the NSA abusing side-channels, however I wouldn't be surprised (or worried) at all if he did. Side-channels were long overlooked and many old implementations suffer from them. Modern day implementations are much more aware and as such don't suffer from them.


Proving a user's identity after the user has forgotten his private key and password

The easiest way to manage this sort of situation is to send people an email confirming that they signed a document.  This is akin to the standard password reset pattern of "if this was not you, please notify us immediately."

If you try to make it stronger, you run into the issue that the server is the only party here that is verifying identity.  It is the entity that is saying "this signature came from someone who can read XYZ's email address."  If the server cannot be trusted, then there is no trustable entity verifying anything.  And, given your situation, its unlikely the users themselves are adding any verification into the system.

One other tool you can use to build up trust is to use a blockchain like approach for the records.  When people sign contracts, they also sign the chain of contracts.  That would make it much harder to forge a single signature from years ago without invalidating every other signature in that time.  You could also require the users to review recent signatures, building more belief into the blockchain.

But in general, if you're not going to take the time to build in a full identification system (which involves an in-person meeting), then the strength of your system is built on its auditing, not in its initial signing algorithm.


How should I incrementally sign a large set of documents?

a new signature incrementally (in the sense of Bellare, et al.) which may be verified incrementally

IMHO this seems to be related to long content, where for a (relatively) small update, the "re-reading" the whole content may be not practical. If you have a large set of smaller documents (4kB) I see no reason why you should treat them as one large content.

I don't know if it will help you, but this is what I've see in one big publishing organization, where they need to ensure integrity of the published (legal) content.

a hash is computed for each content
there a list of published documents and a composite hash of the hashes of each document (sorted list)
the composite hash is signed

using a HSM it requires user intervention (manual PIN entry) to sign anything, so they sign only the whole list ensuring integrity on level of the whole list of documents. In this case the list is more or less static (it doesn't change)

  Sign H' with the private key.

effectively that's what the publishing organization is doing - just skipping steps 2 and 3. If a new content is added / removed / updated, just content of the small document is to be hashed and the list of document hashes is updated (and signed) yes, you will need to maintain a sorted list of the documents


Zero knowledge proof of the sum of two values

For this, it suffices to use additively homomorphic encryption. There are two possibilities for this: Paillier and ElGamal in the exponent.

For Paillier, given an encryption of $v$, $m$ and $n$, one can compute an encryption of zero by $v - m - n$. In the Damgard-Jurik paper, there is a very efficient zero-knowledge proof for proving that a ciphertext is an encryption of 0. So, this solves your problem.

For ElGamal, typical encryption is $(g^r,h^r\cdot m)$ where $h$ is the public-key. This is not additively homomorphic. However, you can change this to $(g^r,h^r\cdot g^m)$ and now you can add and subtract ciphertexts. With the same method as above, one can compute $v-m-n$ inside the ciphertext and then get an encryption of 0 which is just $(g^r,h^r)$. This implies that $(g,h,g^r,h^r)$ is a Diffie-Hellman tuple and this can be easily proved using known techniques for Sigma protocols. Note that this scheme is not efficiently decryptable, since decrypting only gives $g^m$ and you need to solve the discrete log problem to find $m$. Thus, if $m$ is from a small range, you can do this. Otherwise you cannot. However, it is an additively homomorphic commitment scheme, which may suffice for your application.


How to encrypt plain-text message using Diffie-Hellman algorithm

If you look at the Wikipedia page of Diffie–Hellman key exchange you will see that, the algorithm is actually a key exchange protocol.

That is; two parties agree on a new key such that any of the two parties doesn't know before the protocol.

We use this protocol to generate a new key, and transfer the messages by using a symmetric encryption algorithm like AES with the generated key.

If you are looking for an encryption based on the Diffie-Hellman assumption you should check ElGamal Encryption


Once you have computed a DH shared secret, $g^{ab}$, you always hash the result, $k = H(g^{ab})$, before (authenticating it and) using it as a secret key—and preferably, hash the entire transcript of the conversation so far that went into it, like $k = H(g^a, g^b, g^{ab})$, to prevent an adversary from tweaking any part of the handshake that is not authenticated.

The hash $H$ is sometimes called a key derivation function, and there are standard examples like HKDF, often with an extract/expand structure: let $k = \operatorname{HKDF-Extract}(g^a, g^b, g^{ab})$ be the master shared secret key, and then derive subkeys for different purposes by $k_1 = \operatorname{HKDF-Expand}_k(\text{‘first purpose’})$, $k_2 = \operatorname{HKDF-Expand}_k(\text{‘second purpose’})$, etc.


Distinguishing two sets of pseudorandom values when their keys differ by one

Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

No, that is not guaranteed by standard security notions.

AES for example is considered a secure PRP (and thus PRF up to a bound), but has related-key attacks. Granted, the known attacks have more complex key-dependence between a large number of keys, but still, in theory an otherwise secure PRF may be insecure if you see outputs for such related keys. They are only required to be secure with a randomly chosen key.


Using a PRNG for a stream cipher instead of a dedicated algorithm

Rather than giving the advantages of purpose build stream cipher I'll give the disadvantages of using a PRNG / DRBG (you are using a PRNG for the use case of a stream cipher after all):

Implementation details (including reseeding) may differ between systems (this is less likely if the DRBG is well defined and tested, but as they have been designed to retrieve random numbers given some entropy, you never know);
Often deterministic stream ciphers are retrieved from the system. That means that they may be reseeded. You could argue that this is mainly what makes them different from a stream cipher in the first place.
PRNG's often contain additional counter measures to decouple the state from the input (seeding material) & output, making them slower;
PRNG's are often more complex than just a stream cipher (code size, number of instructions). They are indeed often created from stream cipher-like constructions (such as CTR_DRBG you mentioned);
PRNG's are simply not defined for this kind of functionality in mind, making implementation and code maintenance more complex (considering, for instance, the principle of least surprise, which using a PRNG as stream cipher definitely violates);
PRNG's often do not contain implementation details like buffering, the final XOR operation etc. build into them; you may have to wrap a DRBG to create the same experience of a stream cipher operation encrypt / decrypt (and in e.g. Java you cannot simply add a Cipher without implementing and signing a provider).


NaCl allows decryption with the same public key as for encryption

Alice and Bob's keys are used to compute a shared key.

Both parties compute the same key, which is used both encryption and decryption.

This is a traditional, hybrid encryption system.

Using only asymmetric cryptography for encryption would be painfully slow.

As a mitigation, the sender can create an ephemeral key pair, deleted right after the message has been encrypted. See ECIES or libsodium's crypto_box_seal() construction.


By narrowing the space of messages and ciphertexts you are willing to consider to a tiny fraction of fewer than $1/2^{1000}$ of them, you cannot prove that an algorithm for breaking this translates to an algorithm for computing cube roots modulo $n$ in general.

Consequently you can't rely on the decades of work that have been put into failing to find a way to compute cube roots modulo $n$, and you have to redo those decades of failure anew in order to get confidence in the system's security.


Name of the hash algorithms and create an unhash function

EDIT - Per the helpful comments, this question involves a sort of broken base19 conversion with redundant characters from t through z.  As such the below does not reverse for any letters after 's'.  It could be fixed but I presume the question is just an intellectual exercise of some kind anyway.  It obviously is NOT a hash, nor is it an efficient coding system, snugly fitting 8 characters in a less than handy 34 bits.
From my rather layman point-of-view, it was difficult to initially spot as a base19 conversion due to the fact it's backwards (we treat the initial string as base19) and because of the way it multiplies 19 in a loop rather than explicitly $19^i$ (yeah I know...).

To reverse up to 's':
$61752 \mod 19 = 2$
We then take the rounded down result of 61752/19
Were left with $3250 \mod 19 = 1$
We then take the rounded down result of 3250/19
Were left with $171 \mod 19 = 0$
Here it is in Javascript
function rehash(str){
const letters = "abcdefghijklmnopqrstuvwxyz";var out="";

while (str>9) {
  out = letters.charAt(str%19) + out;
  str=Math.floor(str/19)
}
return out}


How many rounds cannot really be answered as it depends on the design of a (block) cipher. As many as required to withstand attacks found by crypt-analysis, plus quite few more in case the attacks are enhanced is the best we can do.
AES-128 has a mere 10 rounds, but those rounds are rather complex. Threefish has a less complex inner structure, but uses 72 rounds for the 256 bit version. There are attacks on Threefish that break 53 of 72 rounds. If the rounds could be compromised that easily for AES then it would be utterly broken. Fortunately the best known attack against AES-128 covers 8 rounds out of 10 - and because it is a key distinguishing attack it doesn't give all that much power to an attacker either.
So for your own cipher you'll have to try to find out how well it withstands all known attacks. This is very  hard thing to do and it is unlikely that you will succeed without help. This is one of the reasons why it is hard to design a cipher. Another is to avoid meet-in-the-middle attacks between the rounds of the cipher.


Is AES in XTS mode insecure for data stream encryption?

From Ptaeck's site (here) (You linked this)

It’s complicated. It’s a wide-block tweakable mode built out of a narrow-block tweakable mode, it uses two keys unnecessarily, and it uses ciphertext stealing to handle variable-length inputs. Another way to say “complicated” is “hard to prove correct”.

This essentially means that it's easy to implement incorrectly, and might not be as secure as is thought in the first place.

It’s unclear what XTS’s goals are. It’s ECB-like. It can’t do a perfect job of providing privacy. It’s not authenticated. Attackers can rewrite plaintexts. It’s hard for a cryptographer to know what they’d be trying to prove. “behavesLikeXTS”? OK, and?

The lack of authentication is a big issue when not used for disk encryption: if an attacker can modify the ciphertext in transit that can't be detected by the recipient. The classic example of this would be rewriting a transaction's recipient or amount to get an attacker the money.

The wide-block-of-narrow-blocks property weakens XTS unnecessarily. As the disk rewrites a given sector, attackers can collect fine-grained (16 byte) ciphertexts. They get to manipulate ciphertexts surgically. It would have been possible to define a “native” wide-block tweakable cipher without that property, but that wouldn’t have been as performant.

The bit about ECB-like means that patterns in the plaintext data at certain scales are detectable in the ciphertext. That's bad, in some cases it can allow an attacker to determine the content of the plaintext.

This is also an issue due to the lack of authentication. The attacker can observe changes in the state of the ciphertext, and responses to their changes to the ciphertext. This makes attacks easier. Not necessarily practical, but not something you want to do if possible.

An ideal cipher should be computationally infeasible for an attacker to modify without detection (authenticated, integrity-preserving), should reveal nothing about the plaintext other than its size (confidential), and uniquely bound to a given origin (authentication). XTS provides no authentication, doesn't preserve integrity, and has some weaknesses in its confidentiality. It's the best we have for disk encryption without a specialized filesystem, but it's a terrible choice for anything without the constraints of full disk encryption on a general-purpose filesystem.


Reducing the output of AES MixColumns to one byte per entry

For the second cell of the second row, I have the following logic: (01 X CA) + (02 X 92) + (03 X CA) + (01 X 5A), with + used here as a symbol denoting the exclusive or operation. The above simplifies to CA + 124 + 25E + 5A, which evaluates to 3EA.

You have a couple of problems here.  You're doing all your evaluations of these as integers; the problem is that they're not integers, they're elements of $GF(2^8)$.  The field $GF(2^8)$ does have "addition" and "multiplication" operations defined, however they're not the standard integer operations (and in fact, the "addition" operation is the same as exclusive-or').  The standard way of looking at it is that multiplication in $GF(2^8)$ is not integer multiplication followed by an integer modulo operation; one way of implementing it would be a "carryless multiplication" followed a 'binary modulo' operation.  You could do the carryless multiplication first, xor all the results, and then do your binary reduction; however a) 03 X CA isn't 25E (this isn't integer multiplication), instead, it's (CA<<1) + CA = 15E, and b) for the modulo operation, you don't subtract 11B, you exclusive or 11B (or 11B shifted left).

However, instead of getting into all that, for your purposes, the three multiplications within the MixCollumn operation can be simplified to:

$$X \times 1 = X$$

$$X \times 2 = \left\{
\begin{array}{rl}
x<<1 & \text{if } x < 128,\\
(x<<1) \oplus 11B & \text{if } x \ge 128.
\end{array} \right.
$$

$$X \times 3 = (X \times 2) \oplus (X \times 1)$$


How does the random oracle model simplify proofs versus using the standard model?

Yes, there are examples where the random oracle model has been first used, then removed, Yes, the proof becomes, in the end, much (much) more complex. But in fact, simplicity of the proof is not the reason why we initially prove security in the ROM. The main reason is that we don't even know what security property our hash function must satisfy!

Intuitively, a random oracle models an idealized hash function that would satisfy all the security properties you can dream of. So, consider a protocol that uses a hash function $H$. It is often the case in cryptography that this protocol seems secure, in the sense that we do not know how to break it. However, to prove that it is secure, we need a security reduction: an efficient reduction from the existence of an adversary that breaks the protocol to the existence of an algorithm that contradicts some security property of our hash function.

But then the question becomes: which security property? Do we want $k$-wise independence? one-wayness? Collision-resistance? Multi-collision-resistance? Output intractability? Correlation intractability? Correlation robustness? Extractable collision resistance?

All the properties I list above are actually security properties of hash functions which have been used in security proofs of various cryptographic construction. But there are many more. Dozen of them, at least.

Because of the hardness of finding the right security notion, cryptographers usually like to argue security in the random oracle model. If you can do so, intuitively, this guarantees that we are likely to be able, someday, to prove the security of our protocol under some assumption about our hash function. If you fail, it might simply mean that your protocol is insecure - so that's a nice sanity check. Proofs in the ROM are usually very simple: the adversary sees nothing at all about the function, it's behavior is perfectly random, so you can just count the information accumulated by the adversary about the random oracle, and compute the exact probability that he finds some specific information. You have also access, in the proof, to all the queries made by the adversary to the oracle - and you can even manipulate the oracle if you like.

  Is there an example where the random oracle has been used to prove security, then removed to shows this?

Many. Here are a few such examples:

Oblivious transfer extension is a core cryptographic primitive in the area of secure computation, which allows to achieve much more efficient protocols by transforming a small number of "oblivious transfers" into a much larger number, using only a few hashes for each new oblivious transfer generated. An efficient OT extension protocol was first given in this paper. The security is proven in the ROM, but it can also be proven assuming that the hash function statisfies correlation robustness, a property which they introduce in the same paper.
The free-XOR trick is a method to improve the efficiency of garbled circuits, also a core primitive in secure computation. It was first introduced here and proven secure in the ROM, and later proven secure in the standard model in this paper by replacing the hash by a special symmetric encryption secure against a certain type of related-key attacks.
The Fiat-Shamir transform is, arguably, one of the most famous applications of the ROM. It allows to transform interactive zero-knowledge protocols into non-interactive zero-knowledge protocols. Proving security of non-interactive protocols obtained through the Fiat-Shamir heuristic has been a major open problem for more than 3 decades, one which attracted a lot of attention from the cryptographic community. The first results in this respect were mainly negative, proving the uninstantiability of the Fiat-Shamir transform in the standard model, for some class of protocols. However, things have changed recently: it has been shown that a large class of interactive protocol can be made non interactive with the Fiat-Shamir transform, if the hash function satisfies correlation intractability for an appropriate class of samplers. Then, hash functions satisfying correlation intractability for important class of samples have been constructed from various assumptions, culminating with a very recent construction of such hash functions from the LWE assumption, which finally solved the long standing open problem of constructing non-interactive zero-knowledge proofs from LWE.
Other situations include building point function obfuscation with auxiliary inputs, or very strong forms of leakage resilient pseudorandom generators, both known in the ROM, but which were only recently obtained in a beautiful paper with a security analysis in the standard model.
RSA-OAEP has been analyzed and proven IND-CPA secure in the standard model here, under the $\phi$-hiding assumption, and assuming that the underlying hash function was $k$-wise independent. It was previously only known to be secure under the RSA assumption when modeling the hash function as a random oracle.

This is just a sample of the things that come directly to my mind, there are many more.


Leading 00 in RSA public/private key file

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers.

ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types.  It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially telecommunications. When it encodes an integer, it has the ability to represent a negative integer.

When we use the BER encoding rules for ASN.1 (which is how ASN.1 are usually encoded in practice), here is how it may represent an integer:

<Tag> <Length> <Value of the integer>

where:

<Tag>: 02 is the magic value for "this is an integer"
<Length>: 81 81 is a variable sized length field that says how many bytes are in the binary value
<Value of the integer>: 00 da ff ... 5f f1 is the binary encoded integer value, in signed big endian form

This is called a Tag-Length-Value encoding or TLV in short.

Now, the rules say that if the most significant bit of the <Value of the integer> field is a 1, the encoded integer is negative (using two's-complement encoding); if it is 0 then the integer is positive (or zero).

Here are the implications of that; if we were to encode the modulus you state as a 256 byte binary value, we would have the binary value as da ff 24 ... 5f f1.  However, if we were to use that as the representation, the decoder would look at the most significant bit of the first byte (da), see that the most significant bit is 1, and interpret that as a negative integer.

In this case, it is required to encode this as a 257 byte binary value, and have the binary value include a leading 0, that is, as 00 da ff 24 ... 5f f1.  In this case, the decoder would look at the most significant bit of the first byte (00 in this case), see that the most significant bit is 0, and interpret that as a positive integer.  And, since adding a leading zero doesn't change the represented value, the decoded integer would be the one we want.

This happens whenever the encoded integer is a multiple of 8 bits in length.

We typically select RSA modulus sizes which are powers of two or small multiples thereof (1024, 1536, 2048, 3072, etc), and so this typically happens there.

And, when we select the primes, we typically split the primes evenly.  For example, when we generate a 2048-bit RSA key, we would typically select two 1024 bit primes; these primes are hence typically multiples of 8 bits in length. And at least one, usually both, must be towards the higher end of the noninclusive range $(2^{1023}, 2^{1024})$ to ensure $n$ is over $2^{2047}$.

The other CRT parameters ($d \bmod p-1$, $d \bmod q-1$, $q^{-1} \bmod p$) are for practical purposes random numbers up to nearly $p$ or $q$, so given the typical values for $p$ and $q$ above, roughly 1/3 of the time these are the same number of bits (1024) and need the extra 00, roughly 2/3 of the time they are 1 to 7 bits smaller and need the same number of octets but no extra 00 or 8 bits smaller and need one less octet for the magnitude plus the 00, and roughly 1/400 of the time they are small enough to need fewer octets.

This rule about an 'extra' 00 applies to both BER and DER, a commonly used subset of BER; see 8.3.2 in X.690. BER gives a choice to include 'redundant' information while DER does not; DER only allows one well defined encoding for a specific type and value combination.

One case where the 00 is typically not included is the public exponent $e$.  The most common value for that is 65537, or 01 00 01 in binary.  The leading bit here is 0, and so a leading 00 byte is not required; hence the typical encoding for this exponent is 02 03 01 00 01.


Krack WPA2 decrypt only some small pieces of packets

It's depressingly practical. And you can reset the key multiple times, getting the same key stream every time. So if the third or forth time you get guessable plain text content in different parts of the key stream you can combine this until you have everything.
Your computer does all kinds of communications, it polls stuff, it makes DNS lookups it uses standard headers and standard protocols all of this produce lots of guessable data. On a not busy network we can also use packet sizes to help us find our guessable data.
In reality finding known plain-text is not difficult.


Why are Fortuna entropy pools reset after a reseed?

If nothing else, it makes the output of the pool irrecoverable. One of Fortuna's goals is to make prior Fortuna outputs safe from a compromise (the discovery of all of Fortuna's current data by an adversary). If the pool continued on without a reset, with little or no entropy added before the compromise took place, the adversary could more easily calculate the past contents of the master pool.

Edit: Per M. Grieu (Merci!), let's make that "more easily verify guesses of past inputs to the master pool".

Also, I believe the OP's question is less about LibTomCrypt than about the Fortuna algorithm itself.


Why is the vector sampled from Gaussian or Subgaussian distribution in lattice-based cryptography?

You can't directly sample uniformly modulo a lattice unless you know what the lattice is. The Gaussian distribution can be sampled independently of knowledge of the lattice. This distinction is important in situations where the lattice is part of a cryptographic secret.


How is HKDF-Expand better than a simple hash?

Short: In some simple cases, hash could be adequate. However, HKDF is intended to be a generic construct you can commonly apply for needs requiring Extract-Expand (such as when you have a shared secret agreed using DH or ECDH). It aims to be largely compatible with existing practices and thus makes it easy to apply the same pattern to multiple uses. It allows simple extensibility (for instance if you need to output more key material in future)

HMAC-based key derivation is commonly used instead of Hash-based key derivation because:

In some uses of Hash-based key derivation there is risk of length extension attack (by choosing $OtherInfo$ field correctly).
When using hash for key derivation there are often multiple fields to concatenate (like previous hash, secret, info, counter). This is bad, because it kind of mixes together key data that is to be protected and other non-critical data (which is often known by the attacker). With PRF (pseudo-random function), it is possible to keep key and the other data separate.
The standard constructs for key expansion, the ones defined in standards like NIST SP 800-108 or IKEv2 already are PRF-based (use HMAC function).
Security features of PRF-based constructs can be easily proven using Random Oracle. (Though such proofs are only approximations of reality if using HMAC-SHA-X.)

In case of HKDF-Expand, using HMAC to implement HKDF-Extract means that both extraction and expansion stages are more similar if both of them are based on HMAC. For using HMAC in HKDF-Extract stage, Krawczyk has provided good rationale in Cryptographic Extraction and Key Derivation: The HKDF Scheme. Especially interesting may be the chapter 8, which compares HKDF against more traditional constructs.

In case of using, HKDF-Expand when the output size is just one block and no info is used (it is empty string), the function will reduce to (assuming 32 bytes output is needed):

$HKDF\text{-}Expand(PRK, info, L) =
HKDF\text{-}Expand(PRK, "", 32) = HMAC\text{-}SHA256(PRK, 0x01)$

This is somewhat more complex, than e.g. $SHA256(PRK)$, but using such as key derivation function would no longer be compliant with the most important standards (NIST SP 800-108, RFC 5869/HKDF).

Overall, this way of doing key expansion appears extensible, good practice, well proven and deployed in practice. I would use HKDF-Expand (or NIST SP 800-108 KBKDF) instead of any home-baked scheme, and feel more secure on selection of algorithm, and know that it will better serve me even if needs will change in the future.


Key Derivation Functions vs. Password Hashing Schemes

Key-stretching key derivation functions must produce results that have certain randomness properties, and be very difficult to reverse. Password hashes only need to satisfy the property "difficult to reverse", without randomness requirements. This is why all key-stretching key derivation functions work as password hashes but not the other way around.
Note that there are also key derivation functions that are non-stretching. Stretching functions are inherently slow, and this is necessary for password hashing. Fast key derivation functions such as HKDF are not suitable when the input has a low entropy, for example a password, regardless of whether the goal is to derive key material or a password hash.


The obvious problem with Shortcut 1 is that the same keystream will be used to encrypt all the messages.  That is, an attacker can exclusive-or two ciphertexts together, and the result will be the exclusive-or of the two plaintexts; this may very well allow the attacker to recover both messages.  How easy this is depends on the language the messages are in; if we assume they are in ASCII-English, this is fairly straight-forwarding as long as the messages aren't extremely brief.

There are two obvious problems with Shortcut 2:

How cryptographically secure is the operating system "random" function?  Quite often, such operating system functions are only statistically random, this might not be good enough.
You say that Alice "securely" sends Bob the array; is she sending a separate array for each message?  If so, why doesn't she use that secure method to send the message?  If not (that is, she reused the same array for different messages), she runs into exactly the same problem as Shortcut 1.

Also, in shortcut 2, your pseudocode says "Assign a random S[] element to S[i]", while your comment says to swap them.  Which do you mean?  What you really want to do is swap the elements (it's important that S[] remain a permutation).


Scrypt's maximum strength to increase entropy of lame passwords

You have to test it on the hardware you'll be using. I tried CryptSharp's implementation with a cost of 262144 and it took about 7 seconds.
The reason it costs more is cause of the memory it uses, and my process that was running the Scrypt was eating up 340ish MB.

How much of that was from the KDF? Don't know.

How would my box handle 100 people authenticating at the same time? Very good question.

This is something you need to performance tune to specific hardware.


How do zero knowledge protocol with vertex-3-coloring work?

Zero knowledge in general

  What are they good for? What is a typical scenario?

This is an interesting question. One application is authentication: You can choose the secret yourself and not even the server will know it, and it will never be transmitted in any way. You just prove you know the secret again and again. However, in practice this is rarely used. Another application is.... security theory. If a protocol can be shown to hold some zero knowledge property, you are sure the correct protocol execution will not reveal any information about the secrets.

Vertex 3-coloring

  How can I be sure that the prover actually has a three-coloring?

You mixed up two essential steps in your description: The color permutation is chosen and applied FIRST, and then the verifier chooses the edge. And therefore, the prover has to send the entire graph with commitments of the colors to the verifier first (or he could still be cheating).

  How can he make sure that it is actually difficult to get a three coloring for this graph?

He can make sure that it's difficult to find a coloring if the graph is huge. It's an NP problem, so it can be solved in exponential time. But if the parameter $n$ is small, then $x^n$ is still manageable.

  How can the prover efficiently generate a big graph with a valid three coloring?

You should not use the word "efficient" with this problem/proof at all. That is not possible. The main problem is that the probability of detecting cheating is $1/e$, where $e$ is the number of edges.Therefore, with $n$ rounds the probability of successful cheating is $(\frac{e-1}{e})^n$. It does go towards 0, but VERY slowly in a big graph. A common goal for error in cryptography is around $(\frac{1}{2})^{80}$, which would imply an incredibly huge amount of rounds.

About generating a 3-colored graph: Start with 1 node and then add random nodes and edges in a way, which doesn't break the 3 coloring. This should take $O(n)$ time.


Question about discrete logarithm problem

To convert every protocol based on DPL to ECDPL based protocol there is a limitation as EC uses generators from a very large prime(or binary) fields. For an instance consider ECDSA which is an EC analogy of DSA, in ECDSA there is a Generator G (used in calculating public key) is from a large prime subgroup of EC where as in DSA the private key (x) is just a random number such that  0 < x < q where q is N-bit prime number.


This is about a misunderstanding. RC4 is a stream cipher. That means that it takes an (input) key and generates a key stream. The bits of this key stream are then XOR'ed with the plaintext. The size of the key stream is not dependent on the size of the (input) key. The input key is not XOR'ed with the plaintext.

Generally RC4 implementations only handle bytes. That's OK, you can just give any input key you want between 40–2048 bits in steps of 8 bits.

Then you can encrypt with the resulting key stream, which means the XOR'ing with the key stream. You can just use 3 bytes / 24 bits of plaintext: say one byte with the least significant bit set (the other bits can have any value) followed by  two bytes with the rest of the 16 bits. Then you encrypt those bytes.

Finally you retrieve back the 17 bits at the same position. Now you've encrypted 17 bits; the other 7 bits can be ignored or removed. When XOR'ing the bits of each byte are fully independent of each other, so the other bits are not needed.

Decryption is identical, so you can just ignore the same 7 bits again.

As indicated by others, RC4 is not considered secure. There are plenty of stream ciphers to choose from that are secure. You could also use AES in counter mode, although AES-CTR obviously does have specific input key sizes; the key stream will however work as expected.


Are ciphertext-only attacks on LFSRs possible?

For text known to be ASCII encoded as octets with high-order bit of octets at zero, that reveals one bit of the output of the LFSR out of 8. It allows finding the original state of the LFSR from (say) the first 51 octets of the ciphertext by merely solving a system of linear boolean equations; then decipher the rest. There is no guesswork involved.

For 7-bit plus parity (where the high-order bit of each octet is the eXlusive-OR of the 7 others, or the complement of that), linear algebra works too.

Things get more difficult as the plaintext becomes less redundant. With 7-bit ASCII, noticing that space, digits, common punctuation and all lowercase letters are in range $[\mathtt{0x20}\dots\mathtt{0x3F}]\cup[\mathtt{0x60}\dots\mathtt{0x7F}]$, we know that every such 7-bit symbol has bit with weight 5 set, and there is fair chance that 51 such characters occur in a row somewhere in the 800-character plaintext. A guess of where allows to decode the rest, and it is easy to detect if the guess was right or not, thanks to characteristics of English text.

More generally, if 51 bits at almost any position can be guessed, then the rest is uniquely determined with basic linear algebra, and the guess is verifiable by checking that the resulting plaintext is appropriately redundant. An LFSR is such that a bad guess is weeded out with very high likelihood using very simple tests, unlikely to falsely rule out a bad guess. We can even do with a lenient chi-squared test that the plaintext resulting from a guess is random, and when it's not, it will be correct. This has the advantage of working regardless of language.

As long as enough bits can be guessed, these techniques work with LFSRs of hundreds of bits, including with unknown feedback polynomial (just add the taps as additional unknowns).


Would it be safe to store GCM nonce in the encrypted output?

Yes, and it is quite common to do this. As long as the nonce is unique for the given key you should be all right. Note that it is best to keep the nonce at 12 bytes (the default). No need to store the size.

Note that there is no need to put the nonce in the Additional Authenticated Data (AAD or AD) as it is already included in the calculation of the authentication tag.

Note as well that GCM does have some limitations to the number of bytes that can be encrypted ($2^{32}$ blocks of 16 bytes).

You could store a magic string and version info before encrypting so you can switch to another scheme later on.


Conditioning Component in Entropy Source

The Ways Things Should Be is that when one tests data, one knows (independently of the data) from what this data came from, and therefore if the origin of the data is the output of a Conditioning Component (including, a source with Conditioning Component), or not (source with Raw data output).

There is no reliable way to determine that from the data. If any correct standard entropy test consistently fails (low p-value), then the data is not from the output of a properly functioning Conditioning Component. I do not see that anything else can be safely asserted (save contraposition).

In particular, if in the following model the Noise source detects particles from a radioactive source; Digitization outputs 1 for event and 0 for no event, sampling at fixed rate several times above the average disintegration period; and Post-processing computes delays between pairs of events (in periods of the sampling), with output 0, 1 or nothing based on comparing the delays (with nothing for equality); then it is practically impossible to distinguish presence or absence of a properly functioning Conditioning final stage.

Entropy source per NIST SP 800-90B 2nd draft:


In RSA, why is it important to choose e so that it is coprime to φ(n)?

It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely.

Let us take the example you give: $N=65$ and $e=3$.

Then, if we encrypt the plaintext $2$, we get $2^3 \bmod 65 = 8$.

However, if we encrypt the plaintext $57$, we get $57^3 \bmod 65 = 8$

Hence, if we get the ciphertext $8$, we have no way of determining whether that corresponds to the plaintext $2$ or $57$ (or $32$, for that matter); all three plaintexts would convert into that one ciphertext value.

Making sure $e$ and $\phi(N)$ are relatively prime ensures this doesn't happen.

BTW: when you generate an RSA key, common practice nowadays is to select $e$ first, and then when you select the primes $p$, $q$, you make sure that $p-1, q-1$ are relatively prime to $e$; this is equivalent to making sure that $e$ and $\phi(N)$ are relatively prime.


Identification of Confusion Component in a Cipher

You can express the output of a cipher in terms of XOR and AND gates applied to the ciphers input bits.

"Confusion" implies an increase in the degree of the equations that represent the bits of cipher output. Basically, the goal of confusion is to make the expressions that represent the bits of the cipher too complex to be able to work with, and to make it to where there is no linear expression that can be used to approximate the actual expression; A linear approximation would imply a % chance that a given set of inputs will make the expressions easy to work with.

For a boolean circuit (i.e an s-box), AND and OR gates will increase the degree of the equations. XOR and shift/rotations will not increase the degree of the equations. (They increase the number of terms in a given equation, which is helpful in making more complex expressions).

Another technique to obtain non-linearity is to interleave operations from different fields, for example mixing bitwise XOR and integer ADD operations. However, if you were to pull apart the adder circuit, you would find AND/OR gates providing the non-linearity yet again.

So look for the AND/OR gates, and you should find the source of confusion in the design.


Is there a security analysis of CryptDB?

A quick glance at their most recent paper shows some security analysis. Secton 2 talks about some different threats, what guarantees they can provide, etc. Section 8.3 also evaluates the security of the system. This may or may not be what you are looking for, you'd have to decide for your self.


Is this simple memory-hard function good?

TL;DR: No, this is not memory-hard and may not even be as computationally intense as you would have thought.

Suppose we have a hash function $H:\{0,1\}^*\to\{0,1\}^n$, for example SHA-256. Now we can construct $H':\{0,1\}^*\to\{0,1\}^n:m\mapsto H(M\parallel m)$ for some fixed, pre-defined message $M$ and where $\parallel$ denotes concatenation. Note how $H'$ is a normal hash function.

Now the task is to find $r_1\neq r_2$ such that $\Delta (H'(r_1),H'(r_2))\leq n-d$ for some work-factor $d$ with $\Delta(\cdot,\cdot)$ denoting the Hamming-Distance. If you have such $r_1,r_2$, this is called a near-collision with a difference of $k:=n-d$.

Now note that for $d=n$ this equals having to find a collision on $H'$, which can be done in time $2^{n/2}$ with negliglible memory. The algorithms for this are Floyd's cycle finding (to see that it can actually be done with negligible memory) and Pollard-$\rho$ (which is state-of-the-art and descriptions can be found in this PDF by Bernstein, even though it mostly talks about how classical collision finding is better than quantum-based). Also see Section 9.7 of the Handbook of Applied Cryptography (PDF).

Now the first obvious optimization one can make is to only consider the first $d$ bits of $H'$ and try to find a collision on them, ie try to find a collision on $H'':\{0,1\}^*\to\{0,1\}^d$ where $H''(m)$ is the first $d$-bits of $H'(m)$. Now we can do the proof-of-work with $2^{d/2}$ instead of $2^{n/2}$ operations and without memory.

Now if we wanted to optimize for time a bit more, we could notice that essentially all bits of $H'$ are independent random variables that take the values $0,1$ with 50% probability each and pretty much independently of each other. So we basically get $d/2$ for free! Furthermore we can apply the math of Binomial-Disitributions to get an estimate for the required amount of samples for 2nd-pre-images. The details of this are explained in this answer, but the TL;DR is $l:=\frac{2^n}{\sum_{i=0}^k\binom{n}{i}}$ messages are needed for a 2nd-pre-image for a fixed message and and $\sqrt l$ messages for a "simple" near-collision. Of course this requires the storage you hoped for, but it's probably less than expected. The complexity $\sqrt l$ is actually proven as Lemma 1 in the second paper below.

Now if we want to leave the land of "simple" strategies to this, there is academic research on how to find such near-collisions with "Using Random Error Correcting Codes in Near-Collision Attacks on Generic Hash-Functions" by Inna Polak and Adi Shamir seeming to be the newest contribution (which also uses a bit of memory) and "Memoryless Near-Collisions via Coding Theory" by Mario Lamberger, Florian Mendel, Vincent Rijmen and Koen Simoens (PDF) being a somewhat older one. Complexities for the algorithms of these papers are hard to estimate, but it's brought up that $n=160,k=33,d=127$ was carried out with a single PC.


Negligible is a human term, not a precise definition.  It refers to things which are sufficiently small that one is willing to ignore it in the interests of expediency.  The threshold varies from person to person: a NSA mathematician will have a different threshold for a property than a CEO of a startup will).  It also varies from topic to topic: $2^{-64}$ solar masses is still a solid quarter of the entire biomass of humans put together!

In my experience, the proof of negligability is often not how small the number is, but how large its inverse is.  Its inverse is often highly associated with some real practical number, like how much energy it takes to crack an algorithm, or how many years.

For example, the risk associated with the brute forcing of a 256-bit key is negligibly small.  This is because we can calculate how much energy it would take to count that high, much less run the algorithm that many times.  I did the numbers once, with ultra-idealized hardware running in the cold of space, it takes about 3/4 of the energy in the galaxy to run that counter from 0 to $2^{255}$


Recently I've found out on this website that brainpoolP256t1 and brainpoolP384t1 aren't secure.

Actually, that website doesn't say that, it says they aren't safe, where their definition of "safe" means it meets all of a series of requirements.

If you go through the table they give, brainpoolP384t1 fails the safe requirements at three points:

ladder; there is a fairly simple algorithm for doing point multiplication for certain curves; this algorithm is moderately fast, and also tends to be resistant to timing and cache-based side channel attacks (but not DPA-style attacks); that algorithm as listed doesn't work for brainpoolP384t1 (actually, it does, it's just a bit more complicated).  One can certainly make the case for simplicity; however just because a curve doesn't implement it as easily as others doesn't necessarily mean that the curve can't be implemented securely.
complete; does the curve allow the implementation of a point addition algorithm that works without branches in all cases (point doubling, adding the neutral element); brainpoolP384t1 does not (at least, not without complicating the algorithm).  However, some point multiplication algorithms don't require unified addition/doubling algorithms and avoid the neutral element; again, simplicity is a good goal, however just because a curve doesn't allow this specific simplification doesn't mean that it's not secure.
indistinguishability; is the representation of a point distinguishable from random; for brainpoolP384t1, it is.  On the other hand, unless you're implementing a PAKE, that's usually not important (and even with PAKE, there are ways around it), and a curve can not implement this, and still be considered secure.

I believe that brainpoolP512r1 has the same properties, and so this page needn't be considered evidence that it isn't secure.

As for whether it is secure, well, the best I can say is "there's no known cryptanalytic result suggesting that it is not" (which is ultimately the best we can say about most cryptographic algorithms).

  When I'm using brainpool, my public keys encoded in base64 have around 210 chars, but for curve25519, they expand into 410 chars which causes a few problems.

Now, that sounds odd; a curve25519 ECDH and EdDSA (you can't use standard ECDSA with curve25519, at least, not with the ladder algorithm) have public keys of 43 bytes (Base64 encoded); it sounds like you're doing something wrong here.


You could probably have answered your own question with a quick look at the Wikipedia definition: a function $\mu(\cdot)$ is negligible if for every positive $c$, there is an integer $N_c$ such that for all integers $x > N_c$, $|\mu(x)| < 1/x^c$. The function $f : x \mapsto -1.5$ is clearly non-negligible according to this definition.

Moreover, even without looking at the exact definition, if you think of the (cryptographic) purpose of a negligible function (bounding the probability that an adversary does something he should not be able to do), it would have made no sense to define it so that any negative function is negligible. One can therefore guess that cryptographers try to use definitions that make sense :)


Where can I download a database of RSA keys?

If RSA keys in PGP format are fine, you can download them from any keyserver.

Many keyservers, at least MIT, have a robots.txt that disallows automated downloads, so be sure to check that before attempting to bulk download anything.

If you need a large collection, you could download a keyserver dump and filter out what you need.


OAEP is likely to be secure as long as the underlying primitives - RSA using modular exponentiation and the hash function to generate the padding - are considered secure. So the OAEP padding in itself should not pose any problems.

That said, we don't know if your protocol is secure, nor if the RSA / OAEP implementation is secure. It could for instance be vulnerable to timing or other side channel attacks.

Currently it seems that OAEP is your best bet for performing RSA encryption. Yes, OAEP is standardized and well used. RSA encryption with PKCS#1 v1.5 padding is still used, arguably too much.

As the RFC encapsulating the PKCS#1 standard specifies:

  In addition, the running time for Inv is approximately t^2, where t
     is the running time of the adversary.  The consequence is that we
     cannot exclude the possibility that attacking RSAES-OAEP is
     considerably easier than inverting RSA for concrete parameters.
     Still, the existence of a security proof provides some assurance that
     the RSAES-OAEP construction is sounder than ad hoc constructions such
     as RSAES-PKCS1-v1_5.

  Hybrid encryption schemes based on the RSA-KEM key encapsulation
     paradigm offer tight proofs of security directly applicable to
     concrete parameters; see [30] for discussion.  Future versions of
     PKCS #1 may specify schemes based on this paradigm.

This was based on the following:

  E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern.  RSA-OAEP
           is Secure under the RSA Assumption.  In J. Kilian, editor,
           Advances in Cryptology - Crypto 2001, volume 2139 of Lecture
           Notes in Computer Science, pp. 260 - 274.  Springer Verlag,
           2001.

As specified in the RFC, RSA-KEM could also be an option. RSA-KEM couples RSA encryption with a (Key Based) Key Derivation Function and symmetric encryption. RSA-KEM may be easier to implement securely. Not many libraries offer direct support for RSA-KEM though (or KDF's for that matter) and it will require some overhead.


Bernstein and Lange regard any curve in Weierstraß form as "not safe" because they assume, implementers of ECC with these curves will make stupid mistakes.
You can see a more detailed discussion on this point here:Safety of ECC-point addition.

So you should pick a subset of their criteria if you want the Weierstraß form(I don't see any reason not to). IMHO the most important criterion is that their creation was "stiff" i.e. there was no unexplained way to fill degrees of freedom in the creation process.
The NIST curves do not fullfill this criterion. They somehow fell from heaven and the community is suspicious. You might use the "stiffly" created ECC-brainpool elliptic curves(up to 512 bit), or my stiffly created curves ECC-curves_anders (up to 1024 bit).


Given a ciphertext $c$ and a public string, how do we check whether $c$ encrypts something that is roughly equal to the string without decryption?

In short: ZKP does not help mostly if you keep your scheme like that. But your scheme can be fixed if you don't need to rely on public encryption.

ZKP do help if a problem can be efficiency calculated if a witness is known and otherwise it is hard to compute. And that's the problem here since anyone can generate such proofs in some cases.

If we talk about encryption schemes, there will be three kind of schemes:

(1) One-Time based: An adversary chooses any m which g(m, m') returns true and compute $k = m \oplus c$. Now anyone can create the desired proof.

(2) Symmetric-key based: An adversary randomly chooses a key k and computes $m = f_k^{-1}(c)$ and outputs k, m, if g(m, m') returns true and otherwise repeats with a different k (algorithms used in practice might have simpler attacks too). Especially if the pattern function has a wide range the likelyhood to find a true returning pattern will break the ZKP since anyone can could generate such a prove then.

(3) Public-crypto: I'm not sure myself here, but I would not rule out attacks like in (2).

The attacks I described here works because the key can be chosen by an adversary. If you rely on the random oracle model, you can use a hash function as commitment (e.g. SHA256) to commit your key using $com \leftarrow H(k|decom)$. Now an adversary must generate a prove so that he knows a key k, a message m and a decommitment decom so that $H(k|decom) = com \land f_k(m) = c \land g(m, m') = 1$ which is hard to compute if you don't know the key and the message.

I would recommend you to use a generic  zero-knowledge protocols which proves the computation of a boolean circuit like presented here and here. The authors first paper even published a reference implementation of SHA256 on github. Hopefully your encryption scheme does not rely on public encryption, since otherwise the proof becomes impractical.


The magic box puzzle: How to implement a verifiable self-contained secret system?

HMAC is what you need:

The HMAC of the secret is provided at the start of the round
The box gives out the HMAC key at the end of the round
If someone guessed the word correctly in the round, then the box gives the HMAC key out to all the contestants, so everyone can verify that the box is telling the truth that a contestant was correct
If no-one gets the answer by the end of the round, then the box can share the key, and the contestants can then verify that the secret is in fact what the box claimed it to be, and that the box isn't lying.

HMAC is hash based, and relies on a symmetric key, which satisfies your requirements


Where is the SSH RSA modulus actually sent?

The modulus is part of the public key. For RSA, the public key consists of the pair $(n,e)$ where $n$ is the modulus and $e$ is the public exponent.

The SSH public key file contains both, typically one after the other. There's a number of ways to encode this information. The gory details of these encodings I leave to this in-depth answer (it includes a section on SSH).

The SSH private key file contains pretty much all numbers associated with the key generation process. If you want to take a look yourself, try running the following command

openssl rsa -in test.key -text

where test.key is your private key file.


Re-encryption without knowing the secret

This is possible with the Integrated Encryption System

In this system, there are global values $p$ (a large prime) and $g$ (a generator of a prime subgroup in $\mathbb{Z}_p^*$).  A private key is a value $x$ and the corresponding public key is the value $y = g^x \bmod p$.

To encrypt a message $M$ using the public key $y$, you select a random value $r$, and publish the pair $(C, D)$ with $C = g^r \bmod p$ and $D = E_{y^r \bmod p}( M )$ (where $E_k(M)$ is the message $M$ encrypted using the key $k$ with some symmetric cipher).

To decrypt a message $(C, D)$ using the public key $x$, you just compute $C^x \bmod p$; this is the value $y^r \bmod p$, which you can then use as the key for the symmetric cipher in $D$.

Now, here comes the interesting part; to update the key from $x$ to $x'$, what the holder of the private key would do is compute $s = x x'^{-1} \bmod p-1$; he then sends it to the user.  The user then replaces $(C, D)$ with $(C^s \bmod p, D)$

We can see that the updated ciphertext $(C^s \bmod p, D)$ is a valid ciphertext to the new public key $y' = g^{x'} \bmod p$; the decryption computes $(C^s)^{x'} = C^{x}$, which is the same key that was originally used to encrypt D, hence decryption works as expected.


Are there any differences between PIR, oblivious transfer and differential privacy?

The other answers are good but I thought I would systemize the differences with a single example. Say Bob has a database with 10 entries of the form {name, salary} and Alice would like to query it.

With PIR, Alice can retrieve any entry or entries of her choosing (say the 8th entry) without Bob learning which one. The trivial PIR is Alice just retrieves the entire database. In this case, Bob doesn't know which entry she was interested in. PIR protocols aim to reduce the amount of information Alice has to retrieve from 10 entries in this trivial case to something like the size of 4 entries.

With OT, Alice can retrieve a single entry of her choosing (again say the 8th) without Bob learning which one. Bob is additionally guaranteed she can only see the single entry she chose and gets no information about the others.

With differential privacy, Alice is not retrieving entries themselves but is instead getting an aggregate statistic for all the entries. For example, say she wants to learn the average salary. With differential privacy, the true average salary is not returned. Instead enough noise is added to the average such that it masks the contribution of each individual entry. Put another way, the number returned would still be plausible if you dropped any single entry from the database.

OT and PIR are similar: cryptographic protection against information disclosure. Differential privacy is more of a statistical approach.


Can you use ECDSA on pairing-friendly curves?

You can. Low-embedding degree may be bad due to the MOV attack, but pairing-friendly curves are particularly chosen so that the embedding degree is low but still enough to not decrease security. So any elliptic curve algorithm should be safe on the curve, not only pairing-based ones.
Some observations:

ECDSA if often used with NIST curves with cofactor 1. However, some pairing-friendly curves have larger cofactors, so you need to take that into account. For example, the BLS12-381 curve has a 381-bit prime but the main subgroup has 255 bits, therefore is has around $255/2 \approx 128$ bits of security (and not $381/2$)
It's still a bit riskier than using high-embedding degree curves. If there are advances in attacks against discrete logs in finite fields then the curve security can decrease. In fact, this has already happened once: for example, the BN256 curve security was reduced from 128 bits to 110 bits.


How to submit a new method of encryption?

Write documentation / a paper:

An overview

What kind of cipher it is and an outline of how it works.
Advantages of your algorithm

Why should somebody use it, over existing designs? Possible advantages include:

A simple and elegant design
Being faster or cheaper on certain platforms
Having features or security properties other designs lack

Specification of the cipher

It should be possible to implement your cipher from the specification, without looking at the reference implementation.
Security claims

There are many security definitions, which of those apply to your design?

For a block cipher you might aim for a strong pseudo-random-permutation. For a stream cipher you might claim that its output is indistinguishable from truly random data. Make sure to use the standard names and definitions for those properties, not just an informal description.

One important purpose this section has is to show that you're aware of and aiming for strong modern security definitions. Too many beginners argue that their cipher isn't broken because the attacks don't demonstrate full plaintext recovery in a ciphertext only scenario.
Benchmarks

How fast is your algorithm on different platforms? For symmetric algorithms this is typically given as CPU-cycles per byte (cpb). Make sure to disable Turbo Boost on Intel CPUs and to mention that you did so.
Design rationale

Why does your algorithm look like it does?
Your own crypto-analysis, if you did it.

For example you might describe how to break a round-reduced version of your cipher
Test vectors

Example tuples containing key, plaintext and ciphertext, to help implementers check if their implementation is correct.
Typeset it properly, using LaTeX. People will see if you did it in Word and that will leave a bad impression.

Implement it:

A reference implementation which focuses on clarity
An optimized implementation, which you use to determine the performance of your algorithm

For symmetric algorithms I recommend including a C implementation.

Now the hard part is getting somebody to look at it:

If there is an upcoming competition, submit it.
Upload the paper to https://eprint.iacr.org.
Submit it to a peer reviewed conference or journal.
Make a name for yourself, for example by attacking other people's ciphers

You won't make any money selling or patenting a cipher. There are too many good and free algorithms available. Even great designs like OCB mode weren't adopted due to being patented.


Security of S/MIME in case of CA compromise

No, since

compromising the communication $\:\implies\:$ compromising the PKI setup $\:\implies$

falsely claiming that a party generated a particular public key $\:\implies\:$ "if Alice … immediately."

.

Yes, we might assume that.

Note that, if the channel can carry voice, then faking a comparison can require voice impersonation.

This is the idea behind ZRTP (which admittedly is not for email).


Minimal Hamming distance of SHA512 hashes at bit flip

We strongly hope that $m_0=0$ as we wish for the SHA512 compression function to perform as a random oracle. Thus for example, if we were to pick a $2^{521}$ long string $s$ there are $2^{521}$ other strings whose Hamming distance from $s$ is 1. The coupon collecting estimate would return all possible outputs with high probability, including the value that matches $\mathrm{SHA512}(s)$. Thus for any fixed, really long string we hope that there is one bit that you can flip that doesn't change the final value.
We strongly hope not to be able to constructively demonstrate that $m_0=0$ as this would be an example of a hash collision. To demonstrate that $m_0=0$ non-constructively seems to require more mathematical structure than is provided in its design.
Interestingly, the related value
$$m_1=\mathrm{min}\{d_H(h(x),h(y)):(\exists n\in\mathbb N,(x,y\in \{0,1\}^n))\wedge (d_H(x,y)=2)\}$$
can be shown to be zero by the pigeon hole principle. We pick a string of length $2^{512}+1$ and compute the hashes of its one-bit flips. Two of these must match and are a pair of strings with Hamming distance 2.

ETA: @poncho points out that SHA512 is limited to inputs of length at most $2^{128}-1$(!) and so these long string arguments do not apply to the standard version of SHA512, only the abstraction of the question. For the probabilistic argument with the standardised version, then instead we consider all strings of length 522 and fix some bit position these provide $2^{521}$ pairs that differ in that bit position and whose differences should be statistically independent. We should anticipate a full set of differences including 0.
Although the pigeonhole principle no longer delivers $m_1$ it does deliver an upper bound of 10 flips of input to produce matching output. We consider a string of length $2^{127}$ and the set of inputs produced by 5 flips. There are more than $2^{512}+1$ of these and so again by pigeonhole there must be two with the same value. The Hamming distance between this pair is at most 10 by the triangle inequality applied to the Hamming metric.


How does converting character set affect hash entropy?

In general, if a function $f$ has collisions, then it may reduce entropy: $$H[f(X)] \leq H[X].$$  The inequality applies to any notion of entropy—min-entropy, Shannon entropy, Hartley entropy, Rényi entropy, etc.  This happens because if $f(x_i) = f(x_j)$ for $x_i \ne x_j$, the probability masses $\Pr[X = x_i]$ and $\Pr[X = x_j]$ both contribute toward the probability mass $\Pr[f(X) = y]$ where $y$ is the common value of $f(x_i)$ and $f(x_j)$.  In particular, the min-entropy is $$-\log_2 \max_y \sum_{x \in f^{-1}(y)} \Pr[X = x].$$  Here the outputs with the most colliding inputs are $\{\mathtt a, \mathtt b, \mathtt c, \mathtt d, \mathtt e, \mathtt f, \mathtt g, \mathtt h\}$, each having five distinct inputs ($f^{-1}(\mathtt a) = \{0,62,124,186,248\}$, etc.), so in the best case, if $X \in \{0,1,2,\dots,255\}$ has uniform distribution, the min-entropy of $f(X)$ is $-\log_2 5/256 \approx 5.678$.  For a string of independent inputs $X_1 \mathbin\| X_2 \mathbin\| \cdots \mathbin\| X_n$, the concatenation $f(X_1) \mathbin\| f(X_2) \mathbin\| \cdots \mathbin\| f(X_n)$ has min-entropy about $5.678n$.  Thus a 64-character string from this will have at most about 363 bits of min-entropy.

Note that this is a bit less than a uniform random string from the same alphabet, which has $\log_2 62$ bits of entropy per character, or about $5.954n$ bits of entropy in a string of $n$ independent characters, which for a 64-character string gives about 384 bits of min-entropy as you calculated.

There are other ways to do roughly what you're doing:

Use base64.  This is an injective map from octet strings to strings of $\{\mathtt a, \mathtt b, \mathtt c, \dots, \mathtt z, \mathtt A, \mathtt B, \mathtt C, \dots, \mathtt Z, \mathtt0, \mathtt1, \mathtt2, \dots, \mathtt9, \mathtt+, \mathtt/\}$ with optional padding.  Of course, you can change the exact character set if need be to comply with mandatory and forbidden special characters.
Use rejection sampling.  From the infinite stream $\operatorname{SHA512}(k \mathbin\| 0) \mathbin\| \operatorname{SHA512}(k \mathbin\| 1) \mathbin\| \operatorname{SHA512}(k \mathbin\| 2) \mathbin\| \dots$, take the acceptable octets (which encode, say, graphic US-ASCII characters) and reject the unacceptable ones until you have a password as long as you want.


Why exactly Blowfish max key length is 448

Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in proceedings of the first FSE conference, held Dec. 1993) defines that Blowfish's key is of 4 to 56 bytes (32 to 448-bit), with this rationale for the maximum:

  The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of $P_{15}$, $P_{16}$, $P_{17}$, and $P_{18}$ does not affect every bit of the ciphertext, and that any S-box entry only has a $.06$ probability of affecting any single ciphertext block.)

Using more than 56 bytes of key for Blowfish is against its definition and design rationale: key bytes beyond the 72th have no effect whatsoever, and the few ones before may have somewhat less diffusion (though not nearly as badly as the above quote suggests). Some Blowfish implementations nevertheless accept keys with any positive number of bytes.


Can I use my own implementation of a widely used, supposedly secure cryptographic algorithm for securing data at rest?

The big problem with RYO is the unknown unknowns. With popular implementations, there are fewer unknowns, more opportunities to find and fix flaws (more eyes on the code), and more guidance if something bad happens.
Think of it like an Ikea dresser; fine in the design studio, fine in the factory, fine in the store, deadly in a toddler's room. Without widespread dice-rolling, you might not find out about a flaw until it's too late and something bad happens to you alone. Also consider that the Maginot Line held as intended, yet still completely failed it's original purpose.
With a "real" AES, there's almost certainly targets juicer than your online backups to fall first, buying you time to fix vulnerabilities. There's no compelling reason stated that mitigates these risks or makes an important trade off, eg: lower battery usage than existing solutions. All i see is risk, no reward, and that makes it a no-brainer.
That said, if your implementation is interoperable with common tools, that suggests that your attack profile for at-rest data is likely similar to those common tools. That is, as long as you don't have mistakes or weaknesses, but that again is something of an unknown at this point; is the reward worth the risk?


What attacks does future secrecy protect against?

It seems like an attacker would have to have exploited one of the messaging devices and read those temporary private keys from its memory - but then couldn't it just read the decrypted messages from memory and not bother with a cryptographic attack?

It is assumed that the messaging devices erase the decrypted messages (and expired private keys) from memory, hence there's nothing to read.


Secure MAC and secure encryption schemes combined to form insecure Authenticated Encryption?

Consider MAC-and-encrypt with a cipher of AES-CTR using sequential nonces, and a MAC of HMAC-SHA256 on the plaintext of the message.

Obviously these are respectively a secure cipher and MAC, but send the same plaintext twice, and the adversary learns that it's the same plaintext.  (Authenticate the nonce too, and this particular problem goes away, though.)
For a 128-bit string $m$, define $E_{k_1}(m) = \operatorname{AES}_{k_1}(m)$, and $M_{k_2}(m) = \operatorname{AES}_{k_2}(m)$.

Obviously these are respectively a secure cipher and (as a PRP approximation to a PRF) a secure MAC, but if $k_1 = k_2$, rather than using independent keys for MAC and encrypt as you should (or keys apparently independent, derived from a master key by a PRF, e.g. HKDF), bad things will happen when you try to compose these.

The standard reference on the security of generic composition of ciphers and MACs is Bellare and Namprempre 2004.  There are various standard security notions for a putative authenticated cipher: indistinguishability (IND-) or nonmalleability (NM-), under chosen-plaintext attack (-CPA) or adaptive chosen-ciphertext attack (-CCA2); unforgeability of plaintexts (INT-PTXT) or of ciphertexts (INT-CTXT).

Bellare and Namprempre prove or provide counterexamples for all implications and nonimplications between these security properties.  They also prove or provide counterexamples for the security properties generically attained or not by MAC-then-encrypt (MtE), encrypt-and-MAC (E&M), and encrypt-then-MAC (EtM), composed out of a cipher indistinguishable under chosen-plaintext attack (IND-CPA) and a MAC unforgeable or strongly unforgeable under chosen-message attack (UF-CMA, SUF-CMA).*  The results hold for any deterministic or stochastic, stateless or stateful, cipher and MAC, as long as decryption and verification are deterministic and stateless.

If, like me, you find this menagerie of security notions dizzying, you may find it reassuring that they can be gathered into a single notion of authenticated encryption meaning IND-CCA2 and INT-CTXT (which collectively imply all the others, and are equivalent to another notion of IND-CCA3), which in turn can be extended to authenticated encryption with associated data.  But the Bellare and Namprempre paper is helpful for studying the relations between the notions, and counterexamples for generic compositions where intuition might lead us astray into a false sense of security not provided by the standard definitions.

Beware that the story may be a little more complex than simply choosing a ‘mode of operation’ for a block cipher and choosing a MAC, as everything is in the misbegotten nonsense paradigm that is choosing modes of operation for a block cipher, a confusing paradigm that should have been left in the dumpster of history out back.

Example.  If you pick CBC mode, then you need to decide what to do with messages that are not exactly multiples of 128 bits long.  You might choose AES-CBC-PKCS7.  But if you try to apply that in (say) MAC-then-encrypt, you effectively have MAC-then-format-then-encrypt, and the reverse procedure is decrypt-then-parse-then-verify.  A lot happens before the verify stage, so this exposes opportunities for padding oracle attacks, because the adversary may have more than just a decryption oracle as is posited in the adaptive chosen-ciphertext attack model.

Even if you had only a UF-CMA MAC and not an SUF-CMA MAC, you are better off remembering encrypt-then-MAC as your go-to composition than you are with MAC-then-encrypt.  Although perfectly safe use of EtM and MtE give the same security properites (IND-CPA and INT-PTXT), anything other than EtM exposes you to the cryptographic doom principle, because you are tempted to touch unauthenticated data, which is pure evil.

* Spoiler alert: Only EtM with IND-CPA cipher and SUF-CMA MAC generically provides all the security properties.  EtM and MtE with IND-CPA cipher and UF-CMA MAC generically provide IND-CPA and INT-PTXT.  With SUF-CMA instead of UF-CMA, MtE still doesn't provide IND-CCA2 or INT-CTXT because the cipher may be malleable.  E&M doesn't even generically provide IND-CPA.


The DES specification numbers bits form 1 to 64, in reading order of big-endian data.

Bit 58 belongs to the second rightmost hex digit of the plaintext, which contains bits 57 to 60. This hex digit is 3, that is 0011 in binary, and bit 58 is the second 0 in that.


Size of Parameters in Polynomial Key-Splitting Algorithm

All of this arithmetic must be done modulo $p$ (for some prime $p$ that is large enough so that it'll be larger than any conceivable $K$ you might ever want to use).  You need to pick $p$ in advance.

Once you've picked $p$, then you choose $a$ and $b$ uniformly at random from the set of integers modulo $p$, i.e., uniformly at random from the set $\{0,1,2,\dots,p-1\}$.

The values $x_i$ can be, so long as they are distinct.  A simple choice is to set $x_i=i$, i.e., $x_1=1$, $x_2=2$, $x_3=3$, $x_4=4$.  That suffices.

(Working modulo $2^n$ is not secure.  You need to work modulo a prime $p$.)

(Technically, you can work in any finite field; working modulo $p$ is just one way to get a finite field.  However, if you don't know what a finite field is, you can ignore this remark.  I'm adding this remark only to keep my fellow cryptographers happy.)


521-bit ECC keys are the same strength as RSA 15,360-bit keys

When it comes to asymmetric cryptosystems like RSA and ECC, security in bits is not the figure quoted in bits for key size (which itself has no universal relationship with the number of bits in the actual form taken by either the public or private key, which I won't further discuss in this answer).

Oversimplifying, and sticking to attacks using classical computers (because quantum computers usable for cryptanalysis are only an uncertain possibility for a remote future)

$n$-bit security means that $2^n$ operations of some kind are believed needed on a classical computer to attack the system from ciphertext or other intercepted data. 96-bit security seems practically secure today (even 80-bit was never broken in a public attack), and each additional bit doubles the difficulty, making 128-bit safe for perhaps one or more decades, depending on one's wilderness of imagination. Anything above is for long-term security, or as a margin for attacks not envisioned in evaluation of the security level.
With ECC, $n$-bit security requires a curve on a finite field which elements need at least about $2n$ bits for their representation, and that $2n$-bit field size is usually what's quoted as size or key size. Thus 256-bit ECC gives at most about 128-bit security, 521-bit ECC gives at most about 260-bit security, rounded to 256-bit because that's a common symmetric key size.
With RSA, the public modulus size as found in (or derivable from) the public key is what's quoted as size, or key size (like, 2048-bit or 15360-bit). Its relationship to security level is more complex than in ECC. NIST SP 800-57 Pt 1 gives these very rough figures, which indeed tell (bottom line, leftmost and two rightmost columns) that 256-bit security is roughly obtained for 15360-bit RSA or 521-bit ECC.

  Is there a really much difference between 128bits 256bit and 512bits as it comes to security implemented in messaging apps or is t more important the way it has been implemented?

For data becoming of no value after less than a decade, there is not really much difference between 128-bit security and higher grades (but in the unlikely case that in the above "128bit" was an ECC field size, or if any of "128bits 256bit and 512bits" was an RSA modulus size, these numbers would be too low for decent security).

For key sizes giving decent security level (with the limit perhaps somewhere between 72 to 112-bit security these days depending on a variety of factors), what matters most to security of a messaging apps is who can get at the keys and ancillary data (like, most importantly, who communicates with who), what's done with the crypto, and the quality of the implementation.


Is simple XOR with secret key using DHE secure?

In addition to the problems that user595228 has mentioned, well, an attacker can easily solve a discrete log modulo a 256 bit prime; from that, he can recompute the shared secret, and that would give him the entire message.  To be secure, you really need at least a 1024 bit prime; with a 2048 bit prime being greatly preferred.


representing binary finite fields in ASN.1

For a binary field $\mathbb{F}_{2^m}$, the polynomial necessarily has degree $m$ (otherwise the field would not have cardinal $2^m$), and its least significant coefficient must be $1$, not $0$ (otherwise the polynomial would not be irreducible, and the field would not be a field).

Therefore, for $\mathbb{F}_{2^{193}}$, if the polynomial is a trinomial, then it is already known that is is $x^{193}+x^j+1$ for some integer $1<j<193$. Only that integer $j$ needs to be encoded, which is why you only have one INTEGER. In other words, when trying to encode $x^{193}+x^{15}+1$, only the "15" needs to be encoded; the "193" and the "0" are implicit.

Similarly, for a pentanomial, you only have to encode three exponents, since the two extremes (0 and the field size) are implicit.


Deterministic Encryption with AES GCM - how to choose the IV (nonce)

Your proposed solution will work, mostly. The only thing that you have to change is, to use a different key in your calculation of $C1$ and $C2$. Both keys may be derived from a common master key but they must not be the same.

Your solution is a bit complicated, though. It would be a lot easier, to just calculate your deterministic IV as a MAC of the plain text (and the additional data, if there is any).

Putting this together, my suggestion would be:

encrypt

Input value: $S$ (password), $M$ (message)

$MK = scrypt(password), K_1 = HKDF(MK, "IV Key"), K_2 = HKDF(MK, "Enc Key")$

$IV = MSB_{96}(HMAC(K_1, M)), C=ENC(K_2, IV, M)$

Return Value: $IV, C$

decrypt

Input value: $S$ (password), $C$, $IV$

$MK = scrypt(password), K = HKDF(MK, "Enc Key")$

$M = DEC(K, IV, C)$

Return Value: $M$


if a cipher operates on fixed length blocks it has to be a permutation by definition since a one to one function is automatically a permutation on the finite domain $\{0,1\}^n.$

This gives the Electronic Codebook Mode, which uses a key to choose which pseudorandom permutation to use, but it leaks information, so modes of operation were invented for block ciphers, to stop equal messages resulting in equal ciphertexts.

Stream ciphers are not permutations in general. Stream ciphers don't have modes of operation in general.

Permutations play a significant role in asymmetric ciphers as well, and the discrete log map over the multiplicative group $Z_{p}^{\ast}$, for example,  is a permutation.


Number of different substitution alphabet ciphers possible with given conditions?

Iterate through the alphabet (using a smaller alphabet is always a good way to start). So you take letter A and you can combine it with letter B..Z. Now if you take B, then you can combine it with letter A and C..Z. But the combination (A,B) is equivalent to (B,A). So you only have C..Z to consider. Thus you would get (n - 1) + (n - 2) + ... pairs, leaving you with 26 * (25 / 2) = 325 combinations.


Is compressing data prior to encryption necessary to reduce plaintext redundancy?

There is at least one way in which compression can weaken security; it has to do with the fact that essentially all methods of encrypting arbitrarily long message will inevitably leak information about the length of the input.  The only way to avoid this leak is to pad all messages to a constant length before encrypting them — but if the messages are compressed, the compression will change their length in a way that will depend on their content, which may allow an attacker to obtain information about the content based on the length of the ciphertext.

For a practical example of such an attack, see e.g. "Uncovering Spoken Phrases in Encrypted Voice over IP Conversations" by Wright et al. (2010).


What is the difference between these two TLS suites?

There is no difference. It’s just the way the devs described it; which actually makes sense because X25519 implies ECDH is used.

Also, X25519 is not the curve… it’s the function (to be used with Curve25519).

Quoting RFC 7748, Elliptic Curves for Security, January 2016, Page 7:

  The "X25519" and "X448" functions perform scalar multiplication on  the Montgomery form of the above curves.  (This is used when implementing Diffie-Hellman.)

So, to recap: The curves are named Curve25519 and Curve448, while the according functions are called X25519 and X448. And since X25519 implies ECDH, one might regard the additional mentioning of ECDH or ECDHE_ECDSA to be superfluous.


What does perfect mean within perfect forward secrecy and why do some cryptographers disagree with the term?

Forward secrecy of key-establishment (KE) protocol means, that compromising of long-term keys of parties doesn't affect secrecy of established keys in the past.
Example to clarify what PFS means.
Say parties A and B have private keys $s_B$ and $s_B$.
Today they run KE and establish a key $k_1$.
They use this key during a session, and then destroy this key.
During this session, attacker eavesdropped all the messages and remembers the transcript $T$ of the session. Obviously, $T$ includes messages of KE,
and subsequent "data" messages, encrypted with key $k_1$.
Tomorrow, attacker somehow gets keys $s_A$ and $s_B$, but not $k_1$ (because $k_1$ was destroyed and forgotten by $A$ and $B$).
And here comes PFS property of KE: even having $T$, $s_A$ and $s_B$, attacker is unable to find $k_1$ and decrypt messages hidden in $T$.
Then answering your question, why in PFS word "perfect" is ambiguous.
It's an opinion of M.Green obviously, but I will try to guess what he means.
Actually I feel pretty the same regarding this term. "Perfect" is ambiguous here.
E.g., we don't use "perfectly secure signature scheme", we just use "secure".
Moreover, in cryptography word "perfect" appears sometimes in order to describe
that some property (usually some sort of secrecy) is based not on computational assumptions, but it's perfect - i.e., unconditional and doesn't require any assumptions/hypotheses.
Examples:

perfect zero-knowledge vs zero-knowledge (which could be just statistical or computational)
Perfect secrecy of encryption - term introduced by Shannon https://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy

So, in cryptography "perfect" is usually a synonym to
https://en.wikipedia.org/wiki/Information-theoretic_security.
But for some stupid reason - not in this case (in case of KE).
So, more clear would be to have a term "Forward Secrecy", and then, additional "Perfect" would mean that it doesn't require any assumptions and it's unconditional.
But for some historic reason, in literature PFS is used for regular forward secrecy.


Is it always the case that static DH means that the client will send the static DH in a client Certificate? What is the client does not have a certificate?

If the client does not have a certificate, then the requirement you quoted doesn't apply, as the condition "If the client is sending a certificate ..." is not met.

Instead, the DH public key is sent in the ClientKeyExchange handshake (exactly as if your DH wasn't static).


Is perfect forward secrecy (PFS) possible without public key cryptography

Yes, perfect forward secrecy is possible using symmetric primitives alone.

Take for instance a set of one time pads:

Alice generates two identical stacks of one time pads and hands one of the stacks to Bob.
Alice encrypts a message with the first one time pad and then passes the ciphertext to Bob.
Bob decrypts the message with the first one time pad and then both Alice and Bob destroy the first one time pad. So long as all copies of the one time pad are destroyed the ciphertext is now undecipherable.
The next message is passed using the second one time pad and at the conclusion of that protocol round all copies of the second one time pad are destroyed. And so on.

This basic protocol achieves perfect forward secrecy.

Of course it's likely not a practical protocol for many applications as, for instance, it requires secure advance exchange of a set of one time pads and the message length is limited by the length of a one time pads which much be agreed in advance. Nevertheless you can start from this model and apply some basic cryptographic improvements such as:

replace each one time pad with a key and a stream cipher so now we just need to exchange a set of keys
replace the set of keys with a single key and a one way function to obtain the next key so now we just need one key (and of course you simply destroy the previous key each time you derive the next key).

It's not difficult obtain a relatively practical scheme assuming pre-shared keys. The security of this construction is not too difficult to bound (How secure is the stream cipher? How secure is the one way function?).


If you want $N$ serial numbers, your serial numbers will have to use $n$ bits for uniqueness, where $n = \log_2 N$. So if you have 100 bits to use for the serial, you could use 20 to get about a million serials and have 80 bits to use for a cryptographic MAC or signature.

Now there are two approaches, the symmetric and the asymmetric.

In the symmetric approach, you have a key $k$ and calculate a $b$-bit MAC for each $n$-bit ID: $S = I||MAC_k(I)$.

This is very easy and allows an arbitrary split between $b$ and $n$ by truncating a longer MAC if needed. However, if the program can be easily studied, you may find the key and be able to use that for a key generator.

With $b = 80$ this is quite secure as long as the key remains secret. (Within the realm of plausibility if the adversary is dedicated, but very unlikely against a random CD key.)
In the asymmetric approach, you have a key-pair $(s, p)$ and calculate a signature for the ID that can be verified with the public key.

Here you would need a public key system with exactly $b$-bit signatures. OTOH, it would prevent even someone who can find the public key from creating serials... but wouldn't prevent someone from overwriting the public key with their own.

However, with $b = 80$ you'd need an 80-bit elliptic curve, which is not secure (nor would a 100-bit one be). It's only approximately as secure as a 40-bit symmetric key would be, and can be broken relatively easily without special hardware.

Therefore, if you need only 100-bit serials, I would recommend the former route. It's just security through obscurity, but the alternative isn't secure either.

There is a workaround to make an asymmetric scheme work, but then you need to shift bits from the "signatures" into the "public key".

For each ID you could create an $80$-bit MAC (or a random number, but a MAC allows you to recover serials), but instead of including the key in your program, you'd include hashes for each such MAC. E.g. $H(MAC_k(I))$ for some preimage resistance hash function $H$. The program would verify a serial $I|M$ by calculating $H(M)$, then comparing that to the hash it has for $I$. With $2^{20}$ serials, you'd need to store 10MB of "public key" to verify the serials with $80$-bit security.

Now the enterprising attacker could still overwrite (one of) those hashes to whatever they like... so it's not necessarily much better than the one where you just stored the key. (This is always the case with DRM, unless you involve some kind of hardware module.)


Flexibility in $RSA$ and $DLOG$ standards?

How large can RSA and DLOG keys be before the standard gives up?

In theory, they can be indefinitely long using some implementation adaptions. However, they would become too impractical compared to post-quantum algorithms which do not require such key lengths that no one will use them.

  Is it reasonable to assume $10^9$ bit keys are possible with next generation internet?

I am not sure what you mean with "next generation internet", but the answer is most likely no, independently of what you mean with this.
The reasoning for this is as follows: the hardness assumptions of RSA and ECC, on which the security of these schemes relies, are indeed based on factorization and the dlog problem. Hardness is here defined as: "there exists no polynomial-time algorithm which can solve this problem". However, with a sufficiently large error-corrected quantum computer and using Shor's algorithm, these hardness assumptions are not hard anymore. I.e.: this algorithm (and for d-log a slightly modified one) can solve these problems in polynomial time.

Solving this issue with keys of $10^9$ will never happen, because there exists plenty of algorithms which are based upon other hardness problems for which no polynomial solving algorithm is known in the presence of such quantum computers. Therefore: no, $10^9$ bit keys will most likely not be used anytime soon (next ~50 years).

If you are interested in public-key post-quantum algorithms which are in a competition by NIST to become the next standard, take a look here: https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions


The idea of "safe curve" is somewhat overrated. What you really want is a safe implementation which won't leak secret information when employed in some practical context. Leakage may occur in a variety of ways; some examples include timing attacks and implementation behaviour when encountering anomalous input. This is not an exhaustive list, and, depending on the context, such leakages may or may not apply.

The so-called "safe curves" are curves with equations which, supposedly, make it easier to implement them safely. Note the operational term: easier. A "safe curve" does not automatically imply that any implementation will be sound and safe (a prime example is how OpenSSL botched at least twice their code for binary curves, while using the "safe" Montgomery ladder as adapted by López and Dahab to binary curves). Conversely, an "unsafe curve" can still be implemented safely. It would be wrong to place some anathema on "unsafe curves", as DJB's site seems to imply with its "safe/unsafe" terminology and conspicuous green and red labels (but only seems, mind you).

For an elliptic curve user, e.g. the designer of some protocol which relies on some elliptic curve cryptography implemented by a third-party library, the important matter is that the library is good, which is only loosely correlated with whether the base curve is called "safe" or "unsafe".

As for translation between curve equations, this may or may not be feasible, depending on the actual curves. For instance, proponents of "safe curves" usually mean using Montgomery curves whose equation is: $$By^2 = x^3 + Ax^2 + x$$ for two constants $A$ and $B$. A curve which follows this equation necessarily accepts the point $(0,0)$ which has order $2$ (that point, when doubled, yields the "point at infinity"). It follows that the order of a Montgomery curve must be even. Therefore, standard curves like P-256 with a prime order (thus odd) cannot be converted to a Montgomery equation. Other curves might be convertible, or not.

The Handbook of Elliptic and Hyperelliptic Curve Cryptography describes Montgomery curves in section 13.2.3. It discusses the conversions from Weierstraß to Montgomery equations and back, when that is possible at all. Notably, while Montgomery curves allow for a point multiplication algorithm which is both efficient and relatively easily amenable to "safe" implementation (the famous "ladder"), section 13.2.3.b points to an article from Brier and Joye who showed how a ladder algorithm can be applied to the generic case of the Weierstraß equation $$y^2 = x^3 + ax + b$$ albeit with a somewhat higher computational cost -- but nothing critical in most usages. This would make P-256 a "safe curve" as well, if we want to cling to that terminology (there are other criteria for a curve to be called "safe" but the main point remains: "safety" is ultimately a property of the implementation, not of the curve).

Indeed, if a basic PC or even a smartphone is implied, then the hardware can do thousands of point multiplications per second. For most if not all applications running on that kind of hardware, it makes no detectable difference whether a given ECC implementation can do 3000 or 30000 signatures or decryptions per second (if it did a difference for you, you would not even contemplate using a Java-based implementation like BouncyCastle; you would have gone straight to optimized assembly code).


You can't convert the signature output from one algorithm to another, especially not ones relying on random oracles.


If I don't use XOR in Davies–Meyer, does it remain collision resistant?

Let $h=E_{x_i}(z_{i-1})$ in your suggestion. Let $z'=E^{-1}_{x'}(h)$. This gives a collision between between $(x_i,z_{i-1})$ and $(x',z').$

The XOR makes this attack difficult.


Is nonce-less Encrypt-then-HMAC as secure as poly1305

Even though they have slightly different properties, both Poly1305 and HMAC take a key and a message, and return an authenticator. A nonce is not a parameter they have.
The nonce is a parameter of the encryption and decryption functions. For a given key, different nonces are likely to generate different ciphertexts. And in an encrypt-then-MAC construction, different ciphertexts are consequently likely to produce different authenticators.
So, using a HMAC doesn’t prevent usage of a nonce. The nonce is not used by the MAC function itself, especially in an encrypt-then-MAC construction.
It also means that a static (or reused) nonce can be catastrophic no matter what MAC is being used.


Proof that counter mode of operation and CBC mode are CPA secure when pseudorandom permutations?

Standard security proofs for CTR and CBC deal with pseudo-random permutations (or pseudo-random functions). Relevant references can be found in Sections 4 and 5 of Rogaway's survey. However, it is unclear what you mean by a proof with random permutations. Where is the key then?


Rainbow tables, where have I got it wrong?

Note that for Rainbow tables you should use different reduction functions for each column.

Once you have a match on chain endpoint, you should get the start point of this chain and regenerate chain up to hash value you're looking for. This will give you the plaintext you're looking for.

To search for a matching chain, you guess the column $i$ where you think password is located and compute the chain from column $i$ to the end. In practice, $i$ is chosen to minimise attack runtime, i.e. $i=(N-1, N-2, ..., 0)$ ("walking" the chain backwards).

To check a particular column you re-compute remaining part of the chain by applying reduction and hash functions the same way you do during table generation (Note: remember that in Rainbow tables each column uses different reduction function, so to recompute chain you have to guess position in the chain). Once you have obtained a candidate endpoint, you check if it matches any of the endpoints from a table. If it doesn't, you take next $i$ and repeat the above process. If you've tried all columns with no luck, then password you're looking for is not covered by the table and the search have failed.

Once matching endpoint is found, you get corresponding starting point and recompute the chain up to column $i$. What you will get is the password you're looking for. Or maybe not because there might be collisions, in which case you go to a previous step and continue with next $i$.

In your particular simplified example (with identical reduction functions):

You start with $h=$`03010f7d7933a011782c10faf91c4fca`, compute $H(R(h))=H(05853)$=a6864772e19671240f491bc2c89a36e0
You locate a6864772e19671240f491bc2c89a36e0 in the table and get corresponding starting point – 12345.
You recompute the chain, starting with 12345, to get plaintext for the column where you've got a match, which will be 03010.