Encrypt array of int for individual retrieval

As CodesInChaos comments, your basic idea seems sound, although a 64-bit block size leaves you with a rather low security margin.

Personally, I'd be more comfortable using a cipher with a 128-bit block size (like AES), zero-padding the IDs to 64 bits, appending 64 random bits and encrypting the resulting 128-bit block.  This means that:

even with the birthday paradox, an adversary must retrieve about 232 encryptions of a given ID in order to have even odds of finding one duplicate, and
the probability of a random encrypted block decrypting to a valid ID is N out of 264, where N ≤ 232 is the number of valid IDs in your database.

Now, you also ask whether there is a standard cryptographic scheme for achieving your goals.  In fact, there is: it's called authenticated encryption, and can be implemented either by combining a traditional encryption mode such as CBC, CTR or OFB with a message authentication code in the Encrypt-then-MAC construction, or by using a specialized authenticated encryption mode such as EAX, OCB or GCM.

Authenticated encryption provides IND-CCA2 security, which is short for indistinguishability under an adaptive chosen-ciphertext attack.  This is a rather strong security property, and, in particular, subsumes your goals that an adversary should not be able either to guess a valid ciphertext or to determine that two ciphertexts correspond to the same plaintext.

The main disadvantage of standard authenticated encryption modes, for your purposes, is that they normally impose an overhead of at least two whole cipher blocks: one for the IV and one for the MAC.  That said, their security margin is also correspondingly larger; for a standard AE mode using a 128-bit block cipher, the number of encryptions needed for a collision is around 264, and the probability of a successful forgery is at most one in 2128.

For some modes, it may be possible to reduce this overhead by making the IV implicit.  For example, with GCM (or, say, CTR mode with HMAC), you could just transmit a random initial counter value for the first item in your list, and then use successive counter values for the rest of the list.  Also, some modes support truncating the MAC to reduce the output length at the expense of the security margin.  Thus, combining an implicit IV with, say, a 32-bit truncated MAC, you could achieve security comparable to the 128-bit single block method described above (i.e. forgery probability less than one in 232) with a 64-bit output per item.


How can a hash function be suitable for hashing passwords, but not for deriving enctyption keys, and vice versa?

So the requirements to a hashing function for hashing passwords seem to be the same as the requirements to a hashing function whose output is used as encryption key

This is correct only when the encryption key is derived from a password.

The similarity you observe is due to the fact that a password is the input, and passwords tend to be relatively easy to guess.

Other circumstances where encryption keys are derived do not require key stretching, because the input is already an unguessable (psuedo)random value.

As an example, when using a key agreement scheme the resultant shared secret is typically hashed with a fast cryptographic hash function such as SHA256 to protect the private keys in the case that the shared secret key is compromised. Since the value is already random and large enough to be unguessable, there is no need to apply a slow hash to prevent the adversaries ability to guess it.

tl;dr

If the input is a password, then the hash needs to be slow to prevent an adversaries ability to perform exhaustive search on the entire password space.

If the input to the hash is already a large random value, then slow hashing is not required.


Is knowing the private key of RSA equivalent to the factorization of $N$?

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$.

Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.


OT extensions paper: Why is $G_{m+1} \nleq m \times AND_B$?

First, what is $AND_B$? $AND_B$ is the asymmetric AND protocol, in which Alice and Bob each has a bit $x$ and $y$, at the end Alice always learns nothing (get output 0) and Bob learns $x \land y$. In Lemma 4 it says $AND_B$ can be realized by 1 invocation of $(^2_1)OT$.

Then what is $G_{m+1}$? $G_{m}$ is a protocol in which Alice has a $m$-bit long string $x$, and Bob has a bit $y$. At the end, Alice always learns nothing (gets output $0^m$ -- $m$-bit string with all 0s), and Bob gets $0^m$ if $y=0$ or $x$ if $y=1$. Lemma 6 says $G_{m}$ can be realized by $m$ invocation of $AND_B$. It is simple: for the $i$-th invocation of $AND_B$, Alice uses $x_i$, the $i$-th bit in $x$, as the input to $AND_B$, and Bob uses $y$ as the input to get either 0 or $x_i$. After $m$ invocations, Bob get either $0^m$ or $x$.

Lemma 7 then shows $G_{m+1}$ cannot be realized by $m$ invocation of $AND_B$ (in the presence of a computationally unbounded adversary). Now $x$ is Alice's input that is an $m+1$ bit string and $y$ is Bob's input that is a bit. One thing immediately clear is that if Alice and Bob continue to do what they did above, there is no way Bob can get all $m+1$ bits securely because there is always the last bit that cannot be securely transferred to Bob.

So they have to do things differently. But how? One possibility is that instead of always using $y$ as the input to $AND_B$, Bob may use $y'\ne y$ as input, with some probabilities. The first part in the proof simply tries to say "no, Bob has to always use $y$". In the proof ``Bob applies 1 | y=0'' means Bob uses $y'=1$ as input to the invocation of $AND_B$ even though $y=0$. There are 3 cases, in the first case Bob gets nothing from the invocation -- so no point doing this; in the second case Bob gets things he should not know (violation of Alice's privacy); in the third case it is secure and Bob gets what he is entitled, but he has to use $1$ when $y=1$ and $0$ when $y=0$. In conclusion, Bob cannot do anything differently.

Then can Alice do something differently? Alice can encode her message $x$ into something $(\tau,\sigma)$ such that $\tau$ is given to $Bob$ in clear, and $\sigma$ is $m$-bit long. So if $y=1$, Bob can receive $\sigma$ using $m$-invocation of $AND_B$. Then Bob can decode $x$ back using $(\tau,\sigma)$. However, $\tau$ is not independent of $x$, thus giving $\tau$ to Bob will leak information about $x$ when $y=0$. Note that Alice cannot give $\tau$ to Bob only when $y=1$ because that implies Alice knows $y$. Thus Alice cannot do this encoding thing and has to act as before.

Now since Bob and Alice cannot do anything differently, there is no way $G_{m+1}$ can be realized by $m$ invocation of $AND_B$.


Adding some more information to fkraiem's answer:

The encryption in the Rabin cryptsystem is basically textbook RSA with an exponent of $2$.

  1) Neither p nor q are equal to 2. This means they are odd. The product of (p−1)(q−1) would be even i.e. not coprime with 2.

Well, yes. That is one of the basic problems in Rabin's cryptosystem. If we want that
$$c=m^e$$
is a bijection, $e$ has to be coprime to the order of the multiplicative group. In your scenarios you realized, for normal RSA-moduli this is not true for $e=2$(and $N=2\cdot p$, with $p$ prime, is quite useless cryptographically).

Soo... why are there 4 square roots then? Let's look at the square roots of $1$ for simplicity. Now we could have the following solutions:

$$x_1 = 1 \mod p; x_1=1 \mod q$$
$$x_2 = 1 \mod p; x_2=-1 \mod q$$
$$x_3 = -1 \mod p; x_3=1 \mod q$$
$$x_4 = -1 \mod p; x_4=-1 \mod q$$

With the help of the Chinese Remainder Theorem we can calculate those four solutions mod $N=pq$. For arbitrary elements, this works pretty much the same: Calculate the roots in both $\mod p$ and $\mod q$, then combine the result. And this is the decryption in Rabin.

So with $e=2$ we get 4 possible roots. But the choice which root was the correct one has to be done outside the encryption scheme.

As a final note, there is a crucial difference between RSA and Rabin, when it comes to security property:

If you have a decryption oracle, then the result of the Rabin decryption (even if it just outputs one of the roots every time), reveal the integer factorization. How to do this: Pick a random number, square it and give it to the oracle. The oracle can't know which of the roots you started with and will return a random root. In 1/2 of the cases this reveals the factorization.
This means, that breaking Rabin is actually equivalent to factorization (unknown for RSA). Thus making it "stronger".
On the other hand, a decryption oracle for RSA does not reveal the factorization (as far as we know yet).
For IND-CPA security, Rabin as well as plain RSA are insecure. However, with a proper padding scheme RSA can be made IND-CPA. For Rabin we can apply adaptions (e.g. redundancy or error detection codes), but so far it is unknown if those are CPA secure.

As a final note for RSA: Knowing both $e$ and $d$ is deterministic polynomial to factorization. What is unknown: Can a decryption oracle (with $d$ fixed) help you find $d$ in polynomial time (or equivalent information, e.g. a nontrivial root of $1$, a zero divisor, etc.)


Does AES-ECB with random padding added to each block satisfy IND-CPA?

First, I would not call this AES-ECB, since adding randomness means that it is not ECB. Second, when limiting the message space to what fits into one block, asymptotically -- meaning for a pseudorandom permutation with block size $n$ -- this construction is actually even CCA-secure (and so non-malleable, since indistinguishability and non-malleability are equivalent under CCA attacks). This is actually Exercise 4.2.5 in Introduction to Modern Cryptography, 2nd edition. (When using multiple blocks as in the question, it would be CPA-secure and certainly malleable.)

I just want to note (with respect to @poncho's answer) that this is asymptotically secure. This means that when considering a pseudorandom permutation with block size $n$, no adversary running in time polynomial in $n$ can succeed with probability that is more than negligible in $n$. In practice, with a 128-bit block cipher, this construction will give very poor bounds. However, $2^{32}$ is really here $2^{n/4}$ which is super-polynomial. Thus, there is no contradiction.

In conclusion, this isn't a great idea in practice (unless you have a very large block cipher). However, it works in theory.


Your setup is secure. However it is largely "unneccessarily" secure.

First the generation method: You're using the RNG-CSP which is (I guess) Microsoft's software interface to the Windows secure PRNG, so this is fine.

Now for your tokens:
You're restricting the character set, which reduces the possible entropy per byte, but is fine if you're in a Web-Context. Note that you "only" have about 6 bits of entropy per byte (8 bits).
Your tokens are however too large. The standard security levels are 128, 192 and 256 bit security with 256 being considered secure as long as we're stuck in our solar system and don't discover any fancy energy source except our sun. Your current token sizes provide 192, 384 and 1536 bit security which is unneccessarily large in the latter two cases. I'd suggest changing the token's lengths to 384 bit. If you want, you can keep your short-time tokens at 256 bit or you can also raise the size if you feel 192-bit security (secure for a few decades at least) isn't enough.

Your choice of the hash is fine, SHA-256 provides 256 bit pre-image resistance which is just what you seem to want. Larger hash functions may be an option for you if you want to have more than 128-bit security against quantum computers, which would require you to use SHA(-3)-512

TL;DR: The long tokens may be shortened to 384 / 256 bit length, the rest is fine.


The multiplicative group $\mathbb{Z_{67}}^*$ has 66 elements. By Lagrange theorem, we can say that the order of any subgroup $G$ of $\mathbb{Z_{67}}^*$ must divide the order of the group, 66. The inverse of the theorem doesn't need to be held, therefore one must check that there are subgroups of order 2,3, and 11, and their products.
With the below SageMath you can list the generators and their order;
def findOrder(a,G):
    temp = a
    for i in range (G.order()):
        if temp == G(1):
            return i+1
        temp = temp*a

R = Zmod(67)
grouplist = R.multiplicative_subgroups()
print(grouplist)
for x in grouplist:
    print(x, "order = ", findOrder(R(x[0]),R))

Don't try this code for large groups! This code outputs below with an error for the empty subset!.
( 2,) order =  66
( 4,) order =  33
( 8,) order =  22
(64,) order =  11
(38,) order =  6
(37,) order =  3
(66,) order =  2

Therefore, we have all possible subgroups, no counterexample for the inverse of the Lagrange Theorem.
The only prime orders are 2,3, and 11. For simple security, you need to choose 11. And actually prime is not necessary since ElGamal encryption can be defined over any cyclic group $G$. The security, on the other hand, relies on the Discrete Logarithm problem and when the group is not in prime order, the Pohlig-Hellman enters the game and we are not more secure than the largest prime order.
Ok, let stick with $p=11$ and it has a generator as $g=64$.

Choose a random integer $\alpha$ from $\{1,\ldots, 10\}$
Now, compute $\beta = g^{\alpha}$
The public key $(G,q,g,\beta)$ and the private key is $\alpha$


Ideal way to profile/performance-measure cipher implementations

It is unfeasible with newer CPUs to just count instructions, as newer CPUs can do multiple per cycle, and have multiple cores and likewise.

Cycles per byte is the usual way to measure performance these days.
Of course, to make it as fair as possible and comparable to others, the code is only ideally run on one core, turboboost and hyperthreading is turned off, etc.


This is a matter of computing square roots in $\mathbb Z/p\mathbb Z$.

If $p \equiv 3 \pmod 4$ is prime and $a$ is a quadratic residue so that the Legendre symbol $(a|p) \equiv a^{(p - 1)/2} \pmod p$ is 0 or 1, then $4 \mid p + 1$ and $$\bigl(\pm a^{(p + 1)/4}\bigr)^2 \equiv a^{(p + 1)/2} \equiv a^{(p - 1)/2 + 1} \equiv a^{(p - 1)/2} a \equiv a \pmod p.$$  Consequently, the square roots of $a$ are $\pm a^{(p + 1)/2}$.  (If the Legendre symbol $(a|p)$ is -1, then $a$ is not a quadratic residue.)
If $p \equiv 5 \pmod 8$ is prime, then either $\pm a^{(p + 3)/8}$ or $\pm a^{(p + 3)/8} 2^{(p - 1)/4}$ are the square roots of $a$, depending on whether $a$ is a quartic residue modulo $p$ or not.  Proof left as an exercise for the reader.
If $p \equiv 1 \pmod 8$ is prime, then there's no nice closed-form expression or deterministic algorithm for computing square roots in $\mathbb Z/p\mathbb Z$, but the Tonelli–Shanks or Cipolla algorithms can do it in constant expected number of multiplications in $\mathbb Z/p\mathbb Z$.
If $p$ is not prime, then finding square roots modulo $p$ is as hard as factoring $p$.  But in discrete log systems, we usually worry about prime moduli.  Proving relations between DLOG, CDH, SDH, SQRT, and FACTOR for a composite modulus is left as an exercise for the reader.


Why does the Gameboy Advance serial encryption include the destination byte address?

Quoting the linked source:

 if normal_mode    then c=C387h:x=C37Bh:k=43202F2Fh
 if multiplay_mode then c=FFF8h:x=A517h:k=6465646Fh
 m=dword(pp,cc,cc,cc):f=dword(hh,rr,rr,rr)
 for ptr=000000C0h to (file_size-4) step 4
   c=c xor data[ptr]:for i=1 to 32:c=c shr 1:if carry then c=c xor x:next
   m=(6F646573h*m)+1
   send_32_or_2x16 (data[ptr] xor (-2000000h-ptr) xor m xor k)
 next
c=c xor f:for i=1 to 32:c=c shr 1:if carry then c=c xor x:next
wait_all_units_ready_for_checksum:send_32_or_1x16 (c)

 pp    palette_data
 cc    random client_data[1..3] from slave 1-3, FFh if slave not exists
 hh    handshake_data, 11h+client_data[1]+client_data[2]+client_data[3]

I read the question as asking the role of xor (-2000000h-ptr).

It ads a small layer of security by obscurity, but does not strengthen the algorithm from a cryptographic standpoint, since a passive eavesdropper can know ptr by merely counting the octets exchanged.

The algorithm is a stream cipher for encryption (with the keystream obtained as the XOR of a Linear Congruential Generator m, the aforementioned (-2000000h-ptr), and key k); and a MAC for integrity (using a Cyclic Redundancy Check c with feedback polynomial defined by x). The whole thing is more security by obscurity than real crypto.

Update: The ptr term can not be naturally considered as the counter of the CTR mode of operation. For this we would need chunks of the keystream to be expressable as a function of key and counter, without other internal state evolving sequentially. Here we have other such internal state m. Otherwise said, it is easy to convert a cipher operating in CTR mode for direct access, when here the iterated LCG makes that uneasy. I see no natural way to consider this as a block cipher in any mode.

On the other hand, if we really wanted that, it is possible to express the state of the LCG m as a function F of the current value of ptr and the initial m0=dword(pp,cc,cc,cc), and then the keystream becomes (-2000000h-ptr) xor F(ptr,m0) xor k, or $E_{(\mathtt{m_0},\mathtt{k})}(\mathtt{ptr})$, and we have a CTR mode with a block cipher $E$, having extremely weak diffusion of its plaintext input. That would be grossly inefficient if we implemented F iteratively, but there are ways around.


Why do we append the length of the message in SHA-1 pre-processing?

Wikipedia has a reasonably good explanation about the Merkle–Damgård construction. The idea is the following: SHA-1 is built around an internal "compression function" which takes as input the 160-bit state and a 512-bit message block, and returns a new state. The padding is designed so that it can be proven that a collision over the hash function necessarily implies at some point a collision in one of the calls to the compression function.

For instance, imagine that the padding merely consisted in appending zeros, up to the next block boundary. Then you could imagine getting a collision between a one-block message $m_1$ and a two-block message $m_2$, where the second block of $m_2$ is exactly $m_1$ (this would require the processing of the first block of $m_2$ to end up with exactly the initial state). In this case, there is no collision in the compression function per se.

This does not mean that the all-zero padding is weak; but the padding used in SHA-1 and other Merkle-Damgård schemes ensures that we can concentrate on the compression function alone, without taking into account multi-block messages: if we can "prove" the compression function to be collision-free, then so is the whole hash function. That's what the padding is for: to turn a collision-free compression function into a collision-free hash function.


Which attacks are possible against raw/textbook RSA?

This describes some attacks against textbook RSA (also known as raw RSA), where the public function $x\mapsto y=x^e\bmod N$ or private function $y\mapsto x=y^d\bmod N$ are applied directly to the integer $m$ representing the message. Per standard assumption, the public key $(N,e)$ is known.
Encryption / Decryption
Per standard assumption, ciphertext $c\gets m^e\bmod N$ is known.

Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext.
Determinism also leads to traffic analysis. It is possible to distinguish if the same encrypted message is sent, and when the message changes. This could reveal information. For example, if an attacker sees $E(\text{stay put})$, $E(\text{stay put})$, $E(\text{stay put})$, $E(\text{stay put})$, and finally $E(\text{attack})$, an attacker will know something has changed.
$e$th root attack: For short messages $m$ and low $e$ (e.g. $e=3$), it may happen that $m^e<n$ so that the ciphertext $c=m^e$, and then it is possible to implement the decryption function as $e$-th root extraction. This attack has extensions to $\log_2(m)$ somewhat above $\log_2(n)/e$.
Broadcast Attack: When the same message is sent encrypted to at least $e$ different correspondents, it can (with high likelihood) be recovered without knowing any private key.
Meet in the middle attack; this is an improvement of 1 above that allows searching plaintext faster than brute force; if the message is assumed to be writable as $m=a\cdot b$ with $\max(a,b)\le u$ and $\min(a,b)\le v$, the effort is $\mathcal O(u)$ with memory $\mathcal O(v)$ for constant $N$.
Leak of Jacobi: if $c=m^e\bmod N$, then $\big({c\over N}\big)=\big({m\over N}\big)$. In other words, the Jacobi symbol of plaintext $m$ relatively to $N$ leaks from the ciphertext $c$. This can be a problem in some (rather hairy) protocols built on top of RSA, or/and for some constructions of message $m$; for example $m=4r^2+b$ with $r$ a 500-bit random secret, $b$ a single-bit secret, and 1024-bit $N$: when it is observed that $\big({c\over N}\big)=-1$, it is known with certainty that $b=1$.

Signature Generation / Verification
Per standard assumption, verification of signature $s$ computes $s^e\bmod N$ and either checks that against $m$, or checks that's a sensible $m$.

Eve can pick a random $s$, compute $m=s^e\bmod N$, and pretend $s$ is the signature for $m$. With a little trial an error, she can choose some of $m$, e.g. make it print as OK if it's displayed as a C string, with an expected $2^{24}$ attempts.
An attacker can combine signatures to create a new signature. For example - given a signature of $2$ (i.e., $2^d\bmod{N}$) - it is possible to create a signature for $4$ ($2^d\cdot 2^d\equiv 4^d\bmod{N}$).
Say Alice implements a signing service using her RSA private key. In particular, anyone can send Alice a message, she checks the message contents to make sure there isn't anything too bad in it. If the message isn't bad, she signs it. Let $m_b$ be a bad message. Eve can send $km_b$ for some constant $k$ to Alice. Since $km_b$ isn't bad, Alice will sign it. Giving Eve $(km_b)^d\bmod{N}$. Eve can also get a valid signature for $k$ from Alice since it isn't bad $k^d\bmod{N}$. Using those two, Eve can now get a valid signature for $m_b$, something that Alice would have never signed before, by multiplying the inverse of the second signature.
Eve knows the signature of some messages; e.g. the signature of $0$ is $0$, the signature of $1$ is $1$, the signature of $n-1$ is $n-1$, the signature of $k^e\bmod N$ is $k$ for $0\le k<N$. This could be a nuisance by itself, or could help attacks 1 and 2.

More attacks are described in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem (in Notices of the AMS, 1999; or this other version with a few more references).


Why we need pixel data encryption (perceptual encryption), not the complete file encryption (conventional encryption)?

The one "obvious limitation" of conventional encryption applied to multimedia data is that once encrypted, multimedia data no longer is compressible, or recognized as multimedia data (with metadata) by non-decrypting devices. This is solved by compressing before encryption, and accordingly decrypting before decompression and rendering. Confidentiality of multimedia data is a problem fully solved by conventional encryption.

There however might be practical reasons for perceptual encryption, including

We want the encrypted version to pass thru devices designed exclusively for multimedia data, including compressing perhaps with perceptually acceptable loss, or/and lacking error-correction.
We want a subset of the true data (e.g. metadata, sound but not image, a low-definition version..) to remain accessible by non-decrypting devices (which goes straight against the normal objective of encryption: that an adversary without key can not learn anything).
As an interesting specialization of the previous point, we might want that the non-encrypted low-definition version and the encrypted high-definition version share as much bandwidth as possible, which implies some perceptual model.


Hardware Random Numbers - How to convert Voltage signal into binary?

What you want to do depends on your objective.

If you only want to make a good RNG from the values you have, so that it passes a Diehard test (passing the test being the objective), that's fine and easy. You do not need to know, or care, about how the values are obtained; essentially, you can take whatever form the "floating numbers" reach you (be it characters coding numbers in decimal separated by newline character, words in whatever IEEE 754 format..) and feed that to a CSPRNG. Here is one of the simplest possible implementation: you decide a number $n$ of values to process (or a duration during which values will be processed), and hash whatever form the "floating numbers" representing these values reach you using SHA-256, giving a 256-bit $H$. You then produce random bits using HMAC-SHA-256, with key $H$, and input some counter initialized to zero and large enough to never repeat. This output will pass DieHard or any pre-existing RNG test (that works and is correctly interpreted). That's including if $n=0$ (illustrating that passing such test is not a good argument that a RNG is a good TRNG).

A very different objective is estimating how likely it is that a RNG made according to the above sound principle (feeding a CSPRNG with your source) gives the same output for $m$ uses (especially: on power-up of some device under some well-defined and attacker-controlled conditions), and how large $n$ should be to make this practically impossible. To do this accurately based on an analysis of a stream of the "floating numbers" (rather than on actual data gathered at numerous power-up), a good model of the physical setup and data processing chain leading to the "floating numbers" would be required.

But what you get with LabView from a modern digital scope (or worse, voltmeter) has gone through much undocumented preprocessing, so you can't do this. It remains a reasonable objective to give a lower bound on the actual entropy gathered. Update 2: A RNG test such as DieHard  is not intended for this, but here is something derived that should do: replace each pair of "floating number" by bit 1 if the first number is more than the other, or 0 otherwise. If the resulting sequence pass the DieHard test, then it is likely that each "floating number" has at least $1/2$ bit of entropy (thus feeding all the bits in $n=512$ consecutive representations of "floating number" will seed any sound CSPRNG with at least 256 bit of entropy). If not (that'll depend on the source), try again replacing each set of $k$ bits by the XOR of these bits, increasing $k$ until the test pass; then it is likely that each "floating number" has at least $1/2k$ bit of entropy, so that $n=512k$ will do.


Which asymmetric cipher provides the highest performance?

I prefer a ~128 bit security level. With ECC this means a curve with ~256 bits, with DH or RSA this corresponds to around 3000 bits. If you can accept a lower security level, the advantage of ECC over DH/RSA gets smaller.

My favourite is Curve25519, which has easily available high performance implementations. An alternative is P256 which is a NIST standard, but a bit slower. There are also some other curves/implementations which are faster than Curve25519, but those seem more academic.


As indicated in Forward Secrecy Article of Wikipedia;

  In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key agreement protocols that gives assurances your session keys will not be compromised even if the private key of the server is compromised.  Forward secrecy protects past sessions against future compromises of secret keys or passwords. By generating a unique session key for every session a user initiates, even the compromise of a single session key will not affect any data other than that exchanged in the specific session protected by that particular key

$$\text{perfect forward secrecy} = \text{forward secrecy}$$

  how can lack of PFS, create a security flaw if the pre-master key and master key are random and different for each session?

Generating a unique session key that cannot be reconstructed then it is already forward secrecy. The process of key generation, as a result, requires a randomly generated numbers, as in Diffie–Hellman key exchange

  how can knowledge of the private key, helps the hacker to decrypt old communication? are the pre-master key and master keys stored by the server?
  In forward secrecy,

There is no way if the forward secrecy is applied since one cannot construct old (randomly generated) keys from the pre-master and master keys.

  I read like PFS, works by using an ephemeral/time-varying key.

Yes, your reading is correct. The key is called ephemeral if generated for each key exchange protocol. Note the little difference, Wikipedia states a case that ephemeral keys in some cases used more than once.

  So could any key exchange/ encryption algorithm which ensures keys are discarded after each session be called as PFS?

You need to discard once the key is used, otherwise, you let the attacker decrypt the old messages that he stored before attacking your machine to steal the master key.

What is the reason for storing the old cryptographic keys when you don't need them? Delete them as soon as the usage is finished. In this way, you are betraying the Forward secrecy, forget them!


how this is done in practice

You always can change "starting point" for timestamp.

This site says that current timestamp is 1529950851 seconds since Jan 01 1970. (UTC). Count seconds from some reference point $T_{ref}$, e.g. $$T_{current} + T_{ref} = T_{real}$$

Depending on the available timestamp size, you can setup different schemes. Lets say, you have 2 bytes for timestamp:

Remember current timestamp $T_{ref}$ at both sides, $A$ and $B$, it must be equal.
In $2^{16}$ seconds, update $T_{ref}$ on both sides, simply adding $2^{16}$

$$T_{ref} = T_{ref} + 2^{16}$$

This scheme is not reliable, and will fail after long period of time, because of clock skew. To mitigate this issue, you need to sync $T_{ref}$ of both $A$ and $B$ periodically.


Difference between DER encoded signatures in JavaScript, Java, and C++

Is there a reason for these differences

You do realize that ECDSA is randomized [1], that is, signing the same message twice with the same private key will generate two different signatures.  This is normal, and not due to you using three different ECDSA implementations.

All three signatures are DER-encodings of 'a list of two integers, both of which are 32 byte positive values', which is the expected encoding of an ECDSA signature.  Note: in DER, if you encode a value between $2^{255}$ and $2^{256}-1$, that uses an additional byte.  That happens about half the time (for both integers) in an ECDSA secp256k1signature, and accounts for the slight length differences in your examples.

  because signing it in one language and verifying it in another language will give an error.

Have you tried it?

  I'm trying to understand the DER-encoded signatures for the secp256k1 (ECDSA) curve better,

Ok, here is the break down (using the first signature as an example)

30 - This is a magic number that says "this is a list of objects"

45 - This signifies that the list of objects takes up 45 hex (69 decimal) bytes (not counting the magic number or the length field itself)

02 - This is a magic number that says "this is an integer"

20 - This says that this integer takes up 20 hex (32 decimal) bytes

65A67F8FF9CB5EA8BE899E94CB338FE09E2E596BC047D936FC2B96DC013B5DFC - These 32 bytes are the integer (in bigendian notation)

02 - This is a magic number that says "this is an integer"

21 - This says that this integer takes up 21 hex (33 decimal) bytes.  This is one byte longer because DER states that "if the top bit of an integer is a 1, the integer is negative", and so to encode a positive integer with a msbit of 1, we need to prepend a 00 byte (increasing its length by 1)

00BE123D3F143AF91E4551AAFAE49C9187F64E323F5660D6C6198A9446C3F818A1 - These 33 bytes are the integer (again, in bigendian notation).

The two encoded integers are the r, s values of the ECDSA signature

[1]: actually, there are deterministic versions of ECDSA, where the message and the private key are used to generate the 'randomness' used to generate the ECDSA signature - I assume that's not in play here, or at least, your three examples don't use the exact same method of doing determinism.


Does observing amount of changes in encrypted disk ciphertext have a well-known attack name?

I'm not sure about a formal name but I can comment on your other questions. A lot depends on the level at which you do the encryption. There are three main approaches I'm aware of:

The disk data itself is encrypted,
The file system encrypts data stored in it but is itself stored in plain text on the disk (e.g. CryFS),
Individual files are encrypted but directory structure and file system level meta data (size, timestamps, etc) is not (e.g. EncFS). This is basically what ransomware does.

Generally speaking, none of these approaches encrypt an entire disk worth of data as one long cipher text. They break it down to some degree, whether by sector (in the case of 1), by file (in the case of 3) or arbitrary chunks (in the case of 3). There's a practical reason for this: all the cipher text within an encryption unit (block, sector, chunk, file, etc.) should change if any part of it is changed. If your entire disk were one encryption block then simply viewing a file (modifying the access time) could result in the entire disk being rewritten.

You can generally assume that an OS will put some metadata onto a disk as soon as it's mounted (and maybe even periodically) so the cipher text will change from day to day. However, it won't be the entire disk that changes, just certain portions that become predictable to a diligent observer after a while.

Now...the disappearance of 100MB of clear text coinciding with the appearance of 100+MB (a sane disk encryption system will have data authentication overhead) of ciphertext is a pretty strong indicator that you encrypted the sensitive file. There are things that will complicate this depending on the exact scheme used. First, the amount of change on the encrypted partition will be rounded to the smallest encryption unit (which can be quite large). Second, if a scheme does not store your new file contiguously (is fragmented, intentionally or unintentionally) then significantly more than 100MB of new ciphertext will be created/changed. The last factor can make it much more doubtful whether the sensitive file has just been encrypted but does not apply at all to scheme #3.

Of course, if the attacker is aware of the scheme you're using and are only missing the key then they'll know with high confidence that you simply moved the file. The only way I can think of that would make it doubtful whether you still have the file is if you were able to store the file in a different form by:

compressing it to reduce the written size
padding it arbitrarily to increase the size

You would still have the timing signal though. That is more an operational issue than anything. You have to avoid unlikely coincidences like that if you are to be able to meaningfully use the encrypted partition in a hostile environment. Even if the file weren't on the other partition, the release of a controversial file online coinciding with the appearance of a similar amount of cipher text on your partition is quite revealing.

You could have a script randomly creating, deleting and touching files, rotating encryption IVs, moving data across block boundaries, etc so you end up with a few hundred MB of changed ciphertext daily without anything really happening from your perspective. If you're clever enough you could have this system gradually create an opening for your sensitive file through various blank hidden files and then slowly "garbage collect" this back into one contiguous file again over time. You'd have to be exceedingly clever to have this process not become a side channel for information about the clear text of the partition though.

P.S.: If someone has a way of extracting an entire disk image on a regular basis without your knowledge it's probably just as feasible for them to replace it with a file system that's more convenient for them (think "decrypts on mounting then only pretends to encrypt thereafter") just as discreetly.


Is it true that 7zip doesn't use any salt with its KDF?

From looking at the source or 7zip that seems to be the case. The format has a place for a salt, as SEJPM's link shows. It is mixed into the homebrewn iterated SHA-256 hash before the key. The 7zip decoder even seems to support salts. However, the encoder never uses a salt.

Oddly there is even code for generating a random 4-byte salt, but it is commented out. In the latest release of the code at least: I do not know if previous versions may have had it enabled.

For example, below is the salt generation part from the encoder (from 7zAes.cpp). Code calling this has also been commented out in various places.

/*
STDMETHODIMP CEncoder::ResetSalt()
{
  _key.SaltSize = 4;
  g_RandomGenerator.Generate(_key.Salt, _key.SaltSize);
  return S_OK;
}
*/


Does the nonce really have to be hashed as part of the challenge in a Schnorr signature?

A signature under a public key $P$ is a pair $(R,s)$ such that $[s]G = R + [e]P$, where $G$ is the standard base point, and $e$ is the challenge.

If $e = H(P, m)$ doesn't involve $R$, then I can just pick $s$ arbitrarily and compute $R = [s]G - [e]P$ to forge any signature I want.

The motivation for the Schnorr signature scheme is the Schnorr identification protocol, whereby a prover named Peggy aims to convince a verifier named Victor that she knows the secret $k$ such that $P = [k]G$—that is, $\log_G P$, the discrete log of $P$.  The dialogue goes something like this:

  VICTOR (given $P$): Hey Peggy, do you know $\log_G P$?

  PEGGY (chooses $r$ uniformly at random, computes $R = [r]G$): Yes, but I can't tell you directly.  Instead, here's another point I know the discrete log of: $R$.

  VICTOR (chooses $e$ uniformly at random): OK.  Can you tell me what $\log_G R + e \log_G P$ is?

  PEGGY (computes $s := r + e k$): Why, yes, in fact—it's $s$.

  VICTOR (confirms $[s]G \stackrel?= R + [e]P$): whoa…OK, I guess maybe you do know $\log_G P$.

This protocol is guaranteed not to leak $k$ as long as Peggy chooses $r$ and Victor chooses $e$ independently and uniformly at random each time—in other words, it's an honest-verifier zero-knowledge protocol.

This protocol is convincing to Victor because, if you think of Peggy as a machine (typical of a man like Victor to do in a patriarchal society!), and you suspend the computation in the middle and run it forward with two different challenges $e$ and $e'$, then the resulting values $s$ and $s'$ lead to recovery of $k$ by $(s - s')/(e - e')$, so unless Peggy just got astonishingly lucky for one run (we work with a space of possibilities for $e$ so large that this is not plausible), she must know $k$.

On the other hand, if Peggy doesn't choose $R$ until she already knows what the challenge is, she could just choose $s$ arbitrarily and then derive $R := [s]G - [e]P$.  That's why it's crucial that she commit to $R$ by sharing it with Victor first.

We turn this protocol into a signature scheme by the Fiat–Shamir heuristic: We simulate the challenge that Victor would have chosen, by a random oracle; then instead of an interaction, we get a noninteractive receipt that Peggy can compute on her own, and that anyone in the world can verify later on requiring no further interaction with Peggy.  For the Fiat–Shamir heuristic to work, though, we have to pass in everything Peggy would have committed to Victor so far in the protocol.  That means, in this case, that we have to pass in $R$ and whatever message $m$ Peggy wants to attest to.

You're not the first person to wonder about this!  This trick—forgetting to hash in $R$ along with everything else—was used recently by the Swiss election authority to fail to convince cryptographers that their newfangled electronic voting system is verifiable—along with some other tricks—despite reams of paper on cryptidigitation to prove their software correct.  Also the New South Wales election authority, with the same software, despite being alerted to the problem at the same time.


How to convert AES to a PRNG in order to run NIST Statistical Test Suite?

The answer is simple. AES is in itself a pseudorandom function, so an output from a single block encryption will produce 128-bits of pseudorandom numbers.

Now to use AES to generate longer sequences, you will have to use a block-cipher mode that lets you do the same.

Here is a small list of a few very popular modes ment for PRNGs:

Counter(CTR): Counter mode turns a block cipher into a synchronous stream cipher. It requires an IV or nonce which is combined with a counter and encrypted with a block cipher. The counter can be any non repeating function, however a simple increment by one is secure enough, and not to mention, the most efficient.

Output Feedback (OFB): This also turns a block cipher into a synchronous stream cipher. It starts encryption with an IV, and operates by encrypting the previous block.

Cipher Feedback (CFB): This one converts a block cipher into a self-synchronous stream cipher. It starts with an IV, XORs the output to get the first ciphertext block, and uses every previous ciphertext block as the next IV.

You could also use other modes too, but they might not be well suited for use in stream ciphers, so they will be slow. Otherwise, the ultimate answer to your question is to use a secure block cipher mode. And, not to mention, they work well with hash functions as well.


What is the appropriate public key encryption for secure coin flipping?

There is no asymmetric encryption scheme which would work here. Whatever algorithm is used, $B$ can always send the exact same message than $A$ (i.e. set $c_B = c_A$); when $T$ decrypts both messages, he gets the same value both times, and $b_A \oplus b_B$ ends up being zero.

ElGamal encryption just makes it a bit easier for $B$ to game the protocol inconspicuously: $B$ can send the same encrypted bit than $A$ (without knowing it) under a random guise, making it indistinguishable from an honestly encrypted bit. But the core issue is still there: this coin flipping protocol is inherently broken.


An Elliptic curve cryptography implementation which can be terminated

If discrete logarithm on the curve over $\mathbb{Z}_n$ is easy then $n$ can be as easily factored, precisely by using the Elliptic Curve Factorization Method, in which we indeed work with a curve over the ring $\mathbb{Z}_n$ and fervently hope for the computation to fail, i.e. to hit a non-invertible value. With figures: in practice, ECM works well when the smallest factor is no longer than 200 bits, but an "easy" discrete logarithm on an elliptic curve requires a much smaller field (an effort at breaking a single discrete logarithm on a 128-bit curve has begun, but it will take several years).


No, $X = \{X_n\}_{n \in \mathbf{N}}$ means $X = X_1, X_2, \ldots$ where each $X_i$ is a distribution.

So one could let each $X_i$ be the uniform distribution on strings of length $i$.

That means there is a polynomial $q$ such that for all $n$ and $x$, if $X_n$

assigns non-zero probability to $x$ then the length of $x$ is at most $q(i\hspace{.02 in})$.

The distributions do "take $n$ as some sort of input".

See these two questions for $1^n$.


Using a hash function as a random number generator

Caveat: that answer is written with my mind in Vulcan mode. That is, I'm answering the question as taken literally (in the first part); or in only a minor variant (second part); and ignoring the question's title, which I find unrelated, especially given the limited span of $n$.
The probability considered is $0$ for each of the many different common ways to define $\text{hash}_{64}(n)$ as the first 64 bits of the MD5 or SHA-1 of integer $n$. Whether $0$ is "close to $1/2^{64}$" is a matter of opinion.
For a few other definitions of $\text{hash}_{64}(n)$, that probability is $1$, which is not "close to $1/2^{64}$" by many accounts.
Justification: it is considered the probability $p$ that for every $n$ in $\big[1,2^{64}\big]$ it holds $\text{hash}_{64}(n)=\text{hash}_{64}(n+1)$.
For fixed function $\text{hash}_{64}$ this is a probability that a certain determined fact holds or not, and thus $p$ is either $0$ or $1$ depending on the function $\text{hash}_{64}$. This also holds (perhaps with a different $p$) if we change every to some.
For the many different common ways to define the function $\text{hash}_{64}$ for an integer parameter as the first 64 bits of the MD5 or SHA-1 of that integer, that probability is $0$. For example, if we define $\text{hash}_{64}$ to be the first 64 bits of the SHA-1 of the shortest big-endian decimal representation of $n$ encoded in ASCII, then $\text{hash}_{64}(1)$ is the SHA-1 of the single byte 0x31, that is b6589…8410ch, while $\text{hash}_{64}(2)$ is the SHA-1 of the single byte 0x32, that is da4b…0b0ch, thus they do not match.
We could try with MD5 and SHA-1, various common bases (including 2, 8, 10, 16, 64, 256, 232), common suitable alphabets (ASCII, EBCDIC, binary, bytes) and common variants (uppercase or lowercase hex, various base64 idioms), endianness (big, little, various mixed), and width for $n$ (fixed to say 64 with some exception for $n=2^{64}$, 65, 72 or 96 bits, adaptive according to $n$ with various steps like even which is common with hex). But I'm not convinced that we would find any such $\text{hash}_{64}$ with $\text{hash}_{64}(1)=\text{hash}_{64}(2)$. And I'm ready to bet the house $\text{hash}_{64}(2)=\text{hash}_{64}(3)$ won't hold in addition.
When we average the probability asked over all the possible definitions of $\text{hash}_{64}$, we get $2^{\left(64-2^{70}\right)}$. That's a ludicrously small number, yet not zero.

Now perhaps we should instead consider the probability $p$ that for a random $n$ in $\big[1,2^{64}\big]$ it holds $\text{hash}_{64}(n)=\text{hash}_{64}(n+1)$.
That probability $p$ is $k/{2^{64}}$ for some integer $k$, which can be computed with significant but feasible effort from the exact definition of $\text{hash}_{64}$.
When we average $p$ over all the possible definitions of $\text{hash}_{64}$, we get $1/2^{64}$; thus "close to $1/2^{64}$" for sure.
We can also define the probability $p_k$ that $p$ is $k/{2^{64}}$ for a random function $\text{hash}_{64}$, which is a plausible model for the various $\text{hash}_{64}$ that the question considers. The largest $p_k$ is $p_1$ (meaning $p=1/{2^{64}}$ is the most likely), with $p_0$ extremely close second, both extremely close to $1/e\approx36.8\%$. $p_2$ is about half that, and $p_k$ goes down fast as $k$ grows, down to $p_{2^{64}}=2^{\left(-2^{70}\right)}$, then $p_k=0$ for $k>2^{64}$. It holds $1=\sum p_k$.
We see that $p$ is in the 3-element set $\{0,1/2^{64},1/2^{63}\}$ with probability about $5/2e\approx92.0\%$. We can say $p$ is very often "close to $1/2^{64}$".


Encrypting a key with the same key, for instance using AES

I'm taking the question as: given some cryptosystem using AES-128 with some random secret key $K$, what are benefits and drawbacks of computing and making public $\hat K=\operatorname{AES}_K(K)$?

Benefit - $\hat K$ can be used as a KCV: A legitimate holder of $K$ could do the same calculation with the $K'$ he holds, and compare $\operatorname{AES}_{K'}(K')$ to the public $\hat K$. If there's no match, then one of $K'$, $K$, or the copy $\hat K$ used in the test is altered. If there's a match, it is almost as certain that $K'=K$ that it is certain that $\hat K$ is genuine. In this usage, $\hat K$ would be a Key Check Value (and far from the worst KCV ever used). And if the purpose of such a KCV and test is to guard against alteration of $K$, or of the AES encryption engine, and $\hat K$ is not made public but rather stored secretly along $K$, that seems a byzantine but effective idea (caveat emptor: side channel leakage considerations may apply).

Drawback 1 - $\hat K$ enables an attack on a reduced-round version of AES: A passive attacker knowing $\hat K$ has the same test as above to determine (with high confidence) if a guess of $K$ is right. That test is slightly more useful than just a random plaintext/ciphertext pair would be, because, in AES-128, the first computational step is to XOR the input and key; that gives zero in case of computation of $\hat K$; and thus the result of the first AES round is a constant (0x6363636363636363). Revealing $\hat K$ is like revealing a plaintext/ciphertext pair for a variant of AES-128 with 9 rounds instead of 10. This saves close to 10% of the work in an attack by brute force; and might conceivably open to a cryptanalytic attack that has a benefit at 9 rounds, but not the full 10; I do not see either as truly worrying in practice, though.

Drawback 2 - in some protocol, $K$ can leak: An active attacker might trick a legitimate party holding $K$ into revealing $K$, if that legitimate party uses $K$ to compute the function $\operatorname{AES}^{-1}_K()$. For example, assume a (dumbed down) authentication protocol where Alice draws a random $R$; computes $C=\operatorname{AES}_K(R)$; sends that to Bob, who computes $R'=\operatorname{AES}^{-1}_K(C)$ and sends that back to Alice (which compares $R$ to $R'$). An active adversary knowing $\hat K$ can obtain $K$ from Bob by submitting $\hat K$ instead of $C$, and will get $K$ as $R'$ (because $\operatorname{AES}^{-1}_K(\hat K)=K$). More generally, availability of $\hat K$ could entirely ruin the security of any protocol or encryption mode where $\operatorname{AES}^{-1}_K()$ is used anywhere, and invalidate the security argument of others.


A block cipher is pretty much a substitution cipher. So let's look at a simple alphabetic substitution cipher. There are 26 different plaintexts and 26 different ciphertexts. The cipher is a permutation of these 26 values. But that does not mean there are 26 different permutations, it means that there are $26! \approx 2^{88.4}$ different permutations, which allows an 88-bit key without equivalent keys.

If you transfer this to an n bit block cipher, which has $2^n$ different inputs/outputs, then there are $(2^n)!$ different permutations, which is ridiculously large ($\approx 2^{2^{135}}$) for $n = 128$, much larger than the $2^{256}$ different permutations addressed by a 256 bit key.

So even a 256-bit key only uses a tiny fraction of the available permutations, and thus there are (probably) no equivalent keys if the cipher is ideal.


Finding subgroup in elliptic curve over finite field $ \mathbb{F}_{11}$

In elliptic curve algebra, operations are computed over a field.
In your case, the field is $\mathbb{F}_{11}$.

$\mathbb{F}_{11}$ is a finite field containing 11 elements ($\{0,1,2,...,10\}$), and like every field there is and addition and multiplicative law.
Theses two laws work other the ring of integers modulo 11 (often noted $\mathbb{Z}/11\mathbb{Z}$).

In $\mathbb{F}_{11}$, when we write ${(\frac{39}{2})}^2 - 10 = \frac{1481}{4} = \frac{7}{4}$ it is in fact 7 times the inverse of 4 modulo 11, which is 3 because $3*4 = 1$ modulo 11.

Calculating an inverse modulo an integer can be done with the Extended Euclidian Algorithm. The below is the inverse table;

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
x \in \mathbb{F}_{11}&1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline
x^{-1} &1& 6 & 4 & 3 & 9 & 2 & 8 & 7 & 5 & 10\\\hline
\end{array}

In your example, the x-coordinate of $[2]P$ is then $7*3 = 10$, an element of $\mathbb{F}_{11}$.


Show that $\text{FACTORING} \le_P \text{SQROOT}$

Your proof is essentially correct.
You may improve rigor by either calculating exactly or giving a bound on it's expected runtime.

If we take the simple case(which is also the worst case) where k=2 we get a probability of 1/2 to get a different root.

It should be noted that since our root x was uniformly random over Z/nZ it is also uniformly random over the roots of a. And therefor the probability of success at each attempt is 1/2 regardless of how our SQROOT algorithm chooses which root to provide.

If the probability is 1/2 per iteration the expected number of iterations is 2. This can be as 1/2+1/4+1/8... With probability 1/2 it takes 1 iteration with probability 1/4 it takes exactly 2 (fail, success) with probability 1/8 it takes exactly 3 (fail,fail, success) etc.

For k>2 the probability of success only increases and the expected invocation count is lower.

Therefor the expected runtime is 2 invocations of SQROOT + O(log(n)).
The additional element is for the gcd and random selection part (or even receiving input and giving output).


Help me about Advanced Encryption Standard (AES)

I'm going to assume that the comma $,$ operator used in your question means 'concatenate' (normally written $a||b||c$). Moreover, I'm assuming that $a,b,c$ are distinct.

In that case, With incredibly high probability, No: $V_1$ and $V_2$ will not be equal.

Think of it this way: if they were equal, then what would $D_k(V_1)$ be? Supposing $V_1=V_2$, we have:
$$a||b||c=D_k(E_k(a||b||c))=D_k(V_1)=D_k(V_2)=D_k(E_k(b||a||c))=b||a||c$$

That is, we would have to deduce that $a||b=b||a$ and thus $a=b$.


Twofish vs. Serpent vs. AES (or a combo)

None of Twofish, Serpent and AES are currently known as broken, so as far as security is concerned, you can use any of them. AES has a slight advantage because it's very widely used, so if it gets broken you're more likely to hear about it and get relevant software updates quickly.
The Snowden postings haven't changed much as far as cryptography usage is concerned. They confirmed what was generally suspected before, which is that the generally-accepted cryptographic primitives are safe even from NSA-level adversaries¹; it's the systems and sometimes the protocols that are insecure. What's important is not your choice of primitive (as long as it's one of the generally-accepted ones, e.g. one approved by a NIST standard), but your choice of software.
AES has the advantage that high-end x86 and ARM CPUs include hardware acceleration for it.
If you're a user of cryptography, as opposed to an implementer of software like GPG, keep in mind that if you're typing the letters A-E-S into your code, you're doing it wrong.
¹  You might consider Dual_EC_DRBG to be an exception, but few people used it because it had no obvious security benefit, and its potential to be backdoored was known, and it was slow.


Could ANY cipher serve as the foundation for a public key cryptosystem?

Your reasoning is flawed. Producing a cipher text for a given key from plaintext without the key is no easier than the reverse for symmetric ciphers.
Without the key k, producing ciphertext $Enc_k(x)$ is every bit as hard as $Dec_k(x)$ for many ciphers it is the same operation entirely (e.g anything in CTR mode). And even for common block ciphers there is great similarity between encrypt and decrypt.

For a public key system I need some operation which can be done without the private key. AES etc. do not supply one. If you have the key both operations are easy, without the key they are darn near impossible.


Encryption scheme like RSA where encryption is the inverse of decryption

What you seem to be looking for is a scheme like the following: It consists of two algorithms, a key generation algorithm $K$ and a "key use" algorithm $U$.

The key generation algorithm outputs a pair of keys $(k_0, k_1)$. The "key use" algorithm takes as input a key and an element from some set $S$ (which may depend on $k_0$ and $k_1$), and outputs an element of a set $S$, and satisfies $$U(k_b, U(k_{1-b}, s)) = s$$ for all key pairs $(k_0,k_1)$ output by $K$, all $b \in \{0,1\}$ and all $s \in S$.

Security-wise, for $b = 0$ and $b=1$, given a random $s \in S$ and the key $k_b$, it should be hard to find $t$ such that $U(k_b, t) = s$.

You can trivially turn this into a public key encryption scheme by choosing one of the keys as the encryption key and the other as the decryption key. Ditto for signature scheme.

To get secure schemes, you need to include padding schemes, hash functions or any of the usual stuff.

I don't off-hand know of any examples of such schemes, except for RSA with random exponents or RSA look-alikes. (RSA with small $e$ is not secure.) Diffie-Hellman is certainly not like this.

I don't know if this is a useful concept. It is somewhat similar to trapdoor one-way permutation, which you don't hear so much about anymore.


Encryption and decryption with Diffie-Hellman

The purpose of Diffie-Hellman is solely to establish a shared key, $K$.  Taken from Wikipedia:

  Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

I bolded the segments above to point out two things that I think are worth calling out here:

$K$ is being created over a public, insecure channel.  That is really the core benefit of a Diffie-Hellman key exchange.
There is no requirement that you use the shared key for anything in particular.  $K$ could be used to encrypt further communication, but could also be used as a seed to a pseudorandom number generator, or in any other case where establishing a shared piece of secret data might be useful (and, again, where it is beneficial to do so effectively in public).

So while Diffie-Hellman is often used to permit encryption and decryption of data, the actual use of $K$ is left to the two parties involved to decide.

Additionally, as pointed out by @fgrieu in a comment, it is often wise to pass $K$ through a key derivation function in order to limit any weakness caused by the mathematical nature of the shared secret, or to expand the shared secret to a desired length (e.g. so it can be split it into several keys to be used for different purposes).  So even where $K$ is used to facilitate encryption, it is often not used directly as a symmetric key.

As pointed out by @ComFreek, Diffie-Hellman does not inherently provide authentication of the other party, opening it up to the possibility of man-in-the-middle attacks.  If the keys involved are previously known or able to be verified through a PKI system, Diffie-Hellman is sufficient.  But if you are not able to directly verify the authenticity of the public key, the rest of your protocol should include some form of authentication that the other party is the who you believe it to be.


What are the dangers of predictable (repeated) plaintext structures?

Well, no, modern ciphers (such as AES) do not share that weakness; they are designed specifically to be secure without any assumption of what the plaintext looks like.  You can encrypt the same message with multiple keys; in fact, you can encrypt the same message a bunch of times with the same key, and the attacker still cannot deduce any information for what the plaintexts look like (or indeed verify that all those ciphertexts did in fact correspond to the same plaintext).

As for specific terminology for an attack that, given a large number of messages, attempts to find some information about them, I have seen the term "statistical cryptanalysis"; I don't know how commonly that is used.

As for resistance to AES with a secure mode to statistical cryptanalysis, one way to derive it is indeed based on ciphertext indistinguishability.  If the cipher mode does provide ciphertext indistinguishability (that is, the ciphertexts corresponding to chosen plaintexts are indistinguishable from random outputs), then any process that gains any information on the plaintexts based on the ciphertexts leads immediately to a distinguisher (as doing the same analysis on truely random outputs can't give any information about the plaintext), and such a distinguisher contradicts the assumption of ciphertext indistinguishability.


IBM described the exact padding with random bytes as in your message as ANSI X9.23.

ANSI X9.23 is a withdrawn standard called "X9.23-1988 (Financial Institution Encryption of Wholesale Financial Messages" from ASC X9 (Accredited Standards Committee X9) which is part of ANSI (American National Standards Institute).

It's very old, it may be that you could only order a paper version before it was withdrawn.

That means that:

the padding X.923 does not exist, it is just X9.23 with the dot at the wrong location;
the padding does exist and the Bouncy Castle padding generated during encryption is correct.

Bouncy Castle also allows you to not specify a random number generator in which case zero valued bytes are used instead. You can do this by not calling the init method, or by calling it with null instead of a SecureRandom instance. That's not an option that I see anywhere mentioned for this standard.

The X9.23 padding on Wikipedia is a relatively new addition by an author with just an IP address. My guess is that the author simply used the Bouncy Castle provider and specified "X923PADDING" which (incorrectly) doesn't call the init method and therefore generates zero bytes. And the name lacks the dot, of course.

Notes:

Obviously you should not use this padding for new protocols; in general you should try and avoid block cipher modes that require padding all together.
You should make sure that the padding byte has a value between 1 and the block size. Especially in languages with pointer arithmatic / unbounded arrays accepting values such as negative values for unpadding can be pretty dangerous.
Ciphertext should of course be authenticated before it is being deciphered and - where required - unpadded.


RSA Encryption Time with Different Block Sizes

The maximum payload for each encryption using RSA OAEP is displayed here. For any message up to that size a complete RSA operation needs to be performed. Of course, if you encrypt each byte separately then you won't get much performance, and your ciphertext will expand enormously. You need to make sure that you use the entire possible payload for each encryption.

Encryption for RSA is a relatively fast operation compared to decryption. The RSA public exponent is generally kept small (and to a specific value with just two bits set, 65537 or 0x10001 in hexadecimals, often called F4). So encryption may still be pretty fast even with larger key sizes. Key generation and decryption however will take much more time. As the relative OAEP padidng overhead is also much lower for larger key sizes, I'd expect the encryption speed to initially grow and then quickly degrade again when the RSA modulus start to get really large. Decryption speed will have degraded long before that in all likelihood. For generation of 16,384 bit key pairs I definitely suggest to use a fast CPU....


What is the signature scheme with the fastest batch verification protocol for multiple signers?

Rabin signatures have a very fast verification algorithm: a simple squaring modulo some integer. RSA signature verification (with a public exponent equal to 3) is also very fast. These signature algorithms are simple to implement and will beat ECDSA for verification speed, even if batch verification is used for ECDSA.

The Niederreiter digital signature scheme should also have a very fast verification (but with a mammoth-sized public key); schemes based on Hidden Field Equations (Quartz and Sflash, notably) also offer a fast verification, albeit with a questionable security (the last decade of research on HFE-based schemes has been a long sequence of break-and-repair cycles). NTRUSign is also supposed to be very fast.

Bottom-line is that ECDSA signature verification is quite slow, compared to other signature schemes (it is still fast in practice, because elliptic curves can be optimized in many ways), so there are many signature schemes which will offer faster verification even without batching.

Another kind of batching can be done with ECDSA, when using a binary curve (a curve defined over the $\mathbb{F}_2^m$ field of characteristic 2, for some $m$) and bitslice code: you represent the complete verification process as a circuit of elementary operations on bits (XOR, AND... ECDSA in a binary field is quite appropriate for that); then you use big registers (e.g. 128-bit SSE2 registers) to perform many such computations in parallel, with bitwise operators (when you XOR together two 128-bit registers, you are performing 128 XOR operations in parallel). Writing out such code is difficult, but can offer some impressive speed-ups; see for instance this article (it will still not beat RSA signature verification, though).

Yet another possible ways to speed up ECDSA is by using Koblitz curves (curves in $\mathbb{F}_2^m$ with equation $y^2+xy=x^3+ax^2+1$ where $a$ is $0$ or $1$) which allow for very fast implementations: the doublings in a double-and-add algorithm can be replaced with simple squarings of both coordinates (in mathematical terms, applying the Frobenius endomorphism), something which can be implemented very efficiently. There are some standard Koblitz curves defined by NIST in FIPS 186-3 (the DSA / ECDSA standard), and the whole thing is described in details in the Guide to Elliptic Curve Cryptography (a very good book which I warmly recommend). Combine that with a recent enough x86 CPU with the AES-NI instruction set (not because of the AES things, but for the pcmulqdq instruction for "carryless multiplication"), and you could get some record-breaking ECDSA code which may be competitive even with RSA verification.

So there are many things which can be done with ECDSA; "mathematical" batching is just one of them, and not the one which may yield the biggest speedup in practice.


First off, the values above that are showing as AvgDist are actually Normalized Average Hamming Distances, not Average Hamming Distances.

I wrote a quick script to do some testing around this issue. Details are here, http://trustedsignal.blogspot.com/2015/06/xord-play-normalized-hamming-distance.html, and I won't rehash it all. Multiples of the actual key size come out as more probable to be the actual key size because of the way normalization is done. When the average Hamming Distance is divided by the key size, that's what normalization is, that larger key size generally results in a smaller Normalized Average Hamming Distance -- see the blog post for an example.

For instance, if the Average Hamming Distance with a XOR key size of 3 is 7 and you divide 7 by 3, you get 2.333. If an Average Hamming Distance with a XOR key size of 9 is 19, when you divide by 9, you get 2.111.

In my testing across an admittedly limited sample set, I ended up using random text samples from 80 different English language texts from Project Gutenberg, the XOR key size with the smallest Normalized Average Hamming Distance was the correct key size in about 40% of the cases, where I calculated Normalized Average Hamming Distance for key sizes up to four times the size of the actual key size.

I also found a relatively simple way to improve the probability of returning the correct key size by calculating the frequency of occurrence of the greatest common denominator for the top n probable key sizes. So you take each of the top n key sizes, I was playing around with using the top five or six and you get the GCD for each pair in that list, if one value occurs more frequently than the others, isn't 1 or 2 and is in the list of the top 5 or 6 values, then that's likely to be the correct key size. Using this method, I was able to get the correct key size more than 90% of the time.

Again, I'm a relative noob when it comes to all things crypto, so it's entirely possible my results are bogus and the result of a flawed testing methodology, flawed programming logic, bad sample size, etc.

It would be great if smart folks would read the post and tell me where I went wrong.


How long will brute force of salted SHA-512 hash will take, if salt is known and possible characters in password are known?

So your alphabet is 26 + 26 + 10 = 62 characters. If they are completely random (they often are not completely random, but OK) then each time you add a character the brute forcing will be 62 times more difficult.

So if you have a 8 characters then you will need a maximum of 218,340,105,584,896 tries. As the password could be any of these, the average search time would be half that number.

If you need to search for multiple passwords then you would still only need a single pass - so testing more password hashes at once is more efficient. If each password is salted separately then this speedup doesn't apply though.

You can simply calculate the table using a WolframAlpha query.

Notes:

How long each try will take depends of course on the speed to check each possibility;
This problem is "embarrassingly parallel", so if you've got more computers you can simply throw them in;
The hash algorithm itself doesn't make a difference when it comes to the order of the tests (the number of tests to perform), although it of course does influence the time it takes to test each possibility.
The salt will not make a difference during testing of one password hash, except if it triggers another block to be hashed; for SHA-512 this is not likely.


Why it is not recommended to create your own random generator number?

So, you use integrated Python random, instead of CSPRNG. The problem is here: integrated random functions in programming languages are designed to be very fast, and they have some small period. For example, in C#, standard Random class is seeded by 32 bit integer. Let imagine I use it to generate 256 bit number, like you.

In this case, it can generate only 2^32 different numbers (one for each seed). But we know, there are 2^256 such numbers. If I have generated 256 bit number with this method, anyone can hack my number. He just have to run generator for all possible seeds. 4 billions is very small number and anyone with PC can brute force it.

In case with bitcoins, that means, anyone can restore your private key and steal your bitcoins. Because you used weak random.


What info should be signed with a digital signature to provide entity authenticaton for DH?

Typical signatures start by hashing the message. Thus including more data in a signature doesn't increase the size of the signature, if the recipient knows what you signed (in this case, remembered what they sent in step 1).

You need to hash more data if you include $g^x$, but the cost of hashing a public key is quite low.
If you didn't include some kind of challenge value in the signature a compromised session key would allow impersonation in future sessions, which is undesirable.
I recommend signing all the data exchanged so far (transcript hashing). This leaves much less room for an attacker to manipulate an exchange, which is important, especially for complex protocols like TLS.


ECDSA Signature R|S to ASN1 DER Encoding question

The ASN.1 DER format is deterministic; i.e. there is only a single sequence of bytes that validly encodes given $r$ and $s$ values. Mind the details, though: the encodings of $r$ and $s$ are minimal-sized signed big-endian. Since $r$ and $s$ are positive values, this means that the top bit of the first byte of each encoding must be zero. In your example, the top byte of $r$ is 0xB2, whose top bit is a 1, so an extra 0x00 byte is added, while the top byte of $s$ is 0x22, whose top bit is a 0, so no extra 0x00 byte here.

However, there are some buggy implementations that produce wrong encodings in some cases (e.g. not including a leading 0x00 byte where necessary, or adding an unnecessary leading 0x00 byte). Thus, ECDSA signature verifiers are often a bit lenient in what they accept.

The ECDSA standards (ANSI X9.62, FIPS 186-4) don't define an ECDSA signature as a sequence of bytes, but as a pair of values $(r,s)$. Encoding of signatures is considered to be out of scope; the protocol that uses ECDSA signatures is responsible for defining which encoding will be used. Different protocols used different conventions. In practice, you will encounter two main encodings for ECDSA signatures:

The ASN.1 DER format, described above. It's the one used in X.509 certificates and related protocols.
The "raw" format in which $r$ and $s$ are merely concatenated. In that format, $r$ and $s$ must first be represented as sequences of bytes with some convention (usually big-endian), possibly with some extra padding bytes (of value 0x00) so that both $r$ and $s$ encodings have the same size. The "same size" requirement is important because verifiers must know where to split. OpenPGP uses the "raw" format.


Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305?

OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a secure PRF when the first input is the key.

So now that we know what ChaCha is, for the three desired functionalities:

MAC. Of course a PRF is also immediately a secure MAC,  but ChaCha only accepts 128 bits of input. So you could only MAC messages that are exactly 128-bit long, which isn't practically useful in itself. So this would mean you'd have to build a secure MAC around ChaCha which is certainly possible but needs to be standardized so everyone is doing the same and can talk to each other.
 Possible variants include running ChaCha in CBC-MAC mode, in OMAC-mode, with Poly1305, or using a using a cascade-style construction where a subset of the output is the next iteration's input.
 One could also build a Merkle-Damgard HMAC out of ChaCha but there you face the significant problems, that

each iteration only consumes 128-bit of data,
the HMAC security proof requires a PRF that can use either input as the key which doesn't immediately follow from our above model, and
ChaCha only takes 384-bit of input but produces 512-bit, how do you map this for the iteration?

As for why it's paired with Poly-1305 that mostly due to the fact that this construction is even faster than any of the above other options because the evaluation of Poly1305 is one polynomial multiplication per 128-bit of data, much less work than 20 ChaCha rounds. The speed estimate is 125 cycles / byte on 8-bit low-end platforms and much faster on wider platforms.

For Collision-Resistant Hashing, see my other answer.

AEAD. Again, using a mode like CCM or EAX you can build an AEAD scheme from any PRF like ChaCha. Or alternatively you can use the more efficient ChaCha-Poly construction, but there's no "immediately obvious way" to build AEAD from a PRF short of making use of predefined modes like the above.


Key Confirmation Attack [Key Distribution Center (KDC)]

$ID_a, ID_b, ID_o$ are public information

Oscar sends to $KDC$ a legitimate (encrypted) request to communicate with Alice: $RQST(ID_o,ID_a)$
Oscar gets $Y_o, Y_a$
Oscar sends $Y_a, Y_o$ back to Alice.

Alice cannot tell if she got $Y_b$ or $Y_o$, that's the problem. So, I would say the order of $ID_o$ and $ID_a$ are mixed up in the slide. It would be clearer if it was $RQST(ID_o, ID_a)$ instead of $RQST(ID_a, ID_o)$.


How to decrypt a substitution cipher using a Base64 alphabet

Base64 encoding regroups three consecutive 8-bit values (0-255) into four 6-bit values (0-63). Each value is used to index of a small ASCII array which is typically sequential, such as,

var base64Map = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=';

Base64 decoding is the reverse process. Each character's position is an indexof a matching ASCII array which results in a 6-bit value. Four of these are regrouped into three 8-bit values.

In your case, I suspect the base64Map was shuffled, rather than a separate shuffle operation of the encoded plaintext. If this is the case, then you need to match the order of the encoding array. If truly random, this would become a monumental effort. Perhaps try a Caesar Shift of the array.


Zero Knowledge auth schemes with weak secret

I believe that you are talking about one specific version of EKE, which is one of several known Password authenticated key agreement methods (which is the general category of methods that do a key agreement with the property that someone listening into the exchange can't learn anything, and an attacker that poses as one of the two sides can learn no more from a single exchange than whether a specific password was correct).

Now, with that background, here is the answer to your question.  With DH-based EKE, yes, both sides exchange their $E_k( g^x )$ and $E_k( g^y)$ values, and yes, the attacker can decrypt both values with a potential password, giving $g^x$ and $g^y$ if his guess is correct, and $D_{k'}(E_k(g^x))$ and $D_{k'}(E_k(g^y))$ if his guess is incorrect.  However, EKE uses a special encryption method such that $D_{k'}(E_k(g^x))$ and $D_{k'}(E_k(g^y))$ are also valid public values; possibly $g^z$ and $g^w$, for some $z$ and $w$.  This prevents the attacker from learning anything; he cannot test if a specific $g^x$ and $g^y$ generates the correct shared secret (because the DH problem is hard), and checking if they are valid public value tells him nothing (because they're all valid).  So, while the attacker can make a list of potential decryptions, there's nothing that distinguishes the correct one from all the wrong ones.


In the full version of Delegating Computation: Interactive Proofs for Muggles on the bottom of page 18 it says that it is well known that interactive protocols with input size $n$, completeness $2/3$, and soundness $1/3$, are equivalent to interactive protocols with completeness $1-2^{-n}$ and soundness $2^{-n}$. Though soundness $1/3$ differs from $1/2$ mentioned in the question, a similar equivalence likely exists. Apparently the equivalence is proven somewhere in Goldreich's lengthy paper Modern cryptography, probabilistic proofs and pseudorandomness, volume 17 of Algorithms and Combinatorics.


Why is Blum-Goldwasser not IND-CCA-2 secure?

The randomness is not enough for IND-CCA-2. If we get a message (so $L$ bits of data plus the $y$ to reconstruct the random seed), we can modify it, say flip the first bit, and ask the decryption oracle for a decryption of the modified message (which will have the same $y$!), which we will get. Then the original message can easily be obtained: we get the same key stream for the message (because we have the same $y$ in the modified message), we xor the plain text of the modified message with the modified message and we get the key stream for both the original challenge and (by construction) the modified message. So now we can decrypt the original message too.

Or in a more usual game: we choose a message $p$ to be encrypted and we get back either random or the actual encryption. We do out procedure from above and see if what we got back decrypts to our $p$, and if not, we "expose" the player as having "played" random.

In short, we can ask for a modified message decryption and get useful info. This is not allowed to happen in a IND-CCA-2 secure system.


How to estimate the hardness of SIS instances?

The value $\delta$ characterizes, how short a vector you can expect to find using an algorithm (typically used in the context of lattice reduction).
In particular, for a vector $\mathbf{v} \in \Lambda$ (where $\Lambda$ is a lattice), the associated $\delta$ (often also denoted by $\delta_0$) is defined to be such that $\| \mathbf{v} \| = \delta^n \det(\Lambda)^{1/n}$.
For those don't know how to take the determinant of lattices, see page 4 of this introduction lecture in the course "Lattices in Computer Science" given by Oded Regev.
This was introduced in GN08 in the context for lattice reduction, because it was observed that the $\delta$ for output vectors returned by lattice reduction converges (for growing $n$) to a constant for every type and parametrization of reduction.
Generally, reduction algorithms are parameterized and allow for a trade-off between output quality (i.e. size of $\delta$) and running time. The exact trade-off is still a subject to research, especially as reduction algorithms continue to improve, but a good summary of the state-of-the-art is given in APS15 (Section 3). Roughly speaking, translating a SIS instance to a $\delta$ required to break it, is relatively easy, but translating the $\delta$ to a running time is not as straight-forward. The reason is that the behavior of lattice reduction, the most efficient approximation algorithms to date, is not very well understood and the community has not converged on a model yet.
One issue with lattice reduction is that it uses an exact SVP solver (in lower dimension). In order to instantiate these solvers there are different algorithms, some behaving better in practice and others being asymptotically more efficient. This makes it hard to analyze exactly, how long it will take to obtain a short vector of quality $\delta$.


Does Grover's algorithm effect block size or only key size?

It depends on the application. If you are using the block cipher as a hash function or for a MAC (say in CBC-MAC fashion), then it very well could create problems. Preimage attacks would be much easier than they should.

For normal encryption, however, there wouldn't be a problem since the key is not known to the attacker. As evidence of this, consider Triple DES which has a 64 bit block size yet is still sufficiently secure for use today (though I wouldn't recommend it in newer designs).


In some ways, PuTTY's private key format is more concise as it doesn't include the "reduced" private exponents. BUT, because it includes the OpenSSH formatted public key, it basically has the modulo twice. See this URL for details.

Beyond that I don't think there's any standardized / widely used format that format stores keys in the way that you're proposing. Not MSBLOB, not PKCS1, not PKCS8 (which, for RSA, is basically a wrapper for PKCS1) and not XKMS. If there's a widely used RSA private key format that I missed lmk but of the ones I know about none support the kind of minimalist key you're describing.


Choosing between hash functions instead of providing a salt for a password hash

Generally you don't want to switch algorithms in cryptography. You'd have to deal with different workloads. Furthermore, the choice of algorithm would be just another salt, if a tiny one. However, your approach doesn't disallow the building of 5 separate rainbow tables. So the reason for a salt isn't met.

It is unclear why you would not be able to use a general Password Based Key Derivation Function (PBKDF) / password hash. So yes, using a well known good scheme with a a salt is indeed more secure.

A pepper can certainly be helpful; if the DB is stolen minus the pepper then it will be next to impossible for an adversary to start guessing passwords without the pepper. Of course the pepper should then not be kept in the DB, because that would negate the whole idea.


Why use an RSA public key exponent of form $2^n+1$ instead of $2^n-1$?

The keys of form $2^n + 1$ only contain two bits set (the ones in your question are also short prime values, in case you didn't notice). The public exponents of form $2^n - 1$ on the other hand contain a lot of bits set when $n$ grows (the value 3 is obviously both 10 + 1 in binary as well as 100 - 1 in binary).

Modular exponentiation is usually deemed more efficient if only a few bits are set. At least it is easier to see how to implement it efficiently. The public exponent is usually a prime to make it easier to find a value of $p$ where the public exponent is relative prime to $p - 1$.

Note that $2^{16}+1= 1\ 0000\ 0000\ 0000\ 0001b$ and $2^{16}-1=1111\ 1111\ 1111\ 1111b$. So there is quite a difference in the number of bits set (2 against 16). As the value is 65535 in decimal, it is quite obviously not a prime either as it divides by 5. Then again, $2^{17} - 1 = 1\ 1111\ 1111\ 1111\ 1111b$ is prime and contains as many bits.

The primes with just 2 bits set (the first and last one) are called Fermat primes. There are currently five known Fermat primes:
$$F_0 = 2^{1} + 1 = 3$$
$$F_1 = 2^{2} + 1 = 5$$
$$F_2 = 2^{4} + 1 = 17$$
$$F_3 = 2^{8} + 1 = 257$$
$$F_4 = 2^{16} + 1 = 65537$$
if there are any others (this is an open math problem) they will most definitely not be small primes.

For comparison, try to calculate both $6\times999$ and $6\times1001$ in normal decimals. It is easy to see why this calculation is efficient.

[EDIT] I did do some performance measurements on Java 8 build 71 and I did not find a (consistent) difference between Fermat and Mersenne primes. This could be due to the information that Poncho provided:

  Note: $e=2^{16}+1$ can be computed with 16 squarings and 1 multiplication; $e=2^{16}−1$ can be computed with 15 squarings and 4 multiplications; calling the former 'much more efficient' appears to be a bit of an exaggeration...

But it could also be due to side channel protection in the Java runtime. In the end it will depend on the implementation as well. It does seem to show a common misconception that Fermat primes should always be (much) faster than other primes. I would not be surprised if Fermat primes are just more entrenched than other values.

The following are the known Mersenne primes (values that are both prime and of form $2^{n}-1$) up to $2^{31}-1$.

$$2^{3}-1 = 7$$
$$2^{5}-1 = 31$$
$$2^{7}-1 = 127$$
$$2^{13}-1 = 8191$$
$$2^{17}-1 = 131071$$
$$2^{19}-1 = 524287$$
$$2^{31}-1 = 2147483647$$

I'll be surprised if I see a use for these Mersenne primes as public exponent within RSA though.


Is format preserving encryption suitable for use with words or names?

The obvious way to FPE strings of $N$ characters of [A-Za-z] is to treat the string as a base-52 value (with each character being a digit, say, A=0, B=1, ..., y=50, z=51); do a base conversion of that to an integer between 0 and $52^N-1$; use a standard FPE technique to encrypt that value into another integer between 0 and $52^N-1$, and do a base conversion back into a string of $N$ characters of [A-Za-z].

Because you're encrypting the string as a whole, you don't have the data leakage you would have if you encrypted each character individually.


Randomness in generation of Virtual Machines from pre-built Image

Low entropy for PRNGs is bad.
If you set up a VM by automatized software, you won't have entropy for your PRNG which is not good.

What would be the risk level? Weak cryptographic keys (pretty bad if this is f.ex. a SSH log-in key or someting like this).

Seeding the VM with entropy rich data from the host is the standard solution and will solve the problem.

In my edition of "Cryptography Engineering: Design principals and Practical Applications by Schneier, Fergueson and Kohno" the following solutions are described (for seeding the Fortuna-CSPRNG):

Make the VM-creating system (originally the backup system) PRNG aware -> let it update the PRNG's seed file.
Hash the current time. (originally, again backup system: hash the current time along with the seed file). This works unless the clock's reset and will prevent the PRNG from outputting the same bits. (no high entropy :-( )
Same as 2. but use a counter for each VM you create and hash that instead of the time. (again originally for backups)
Provide entropy via a randomly generated seed file.
Just wait for random events to take place. (if your PRNG implementation is good you can't fully reproduce things like RDRAND output or hard-drive noise) This might take some time and should be last line of defense.

Conclusion: Entropy feeding from the outside is the best option.

I hope this gives you some answers.


How many primitive cryptography operations are there?

Actually the list is large.  You're only describing the old stalwarts that have been around for donkey's years in say DES. Substitution and permutation form what is termed confusion and diffusion. These aren't always required as there are alternatives.  Your sentence regarding entropy as a function is inaccurate as in cryptography the entropy is external to the primitive, eg. in a key or password.

If you consider all primitives and not just ciphers, Keccak hash uses a quite elegant permutation of bits in it's $\pi$ permutation which isn't   like a traditional P box as it does not distribute active bits between multiple S boxes.  Whirlpool hash uses Galois field multiplication to achieve diffusion, as does Rijndael /AES.

Stream ciphers operate differently, and a stream of pseudo random numbers are used.  ISAAC and RC4 are examples that use various array transpositions /indirections and bitwise rotations. I guess if you had a lot of time, Blum Blum Shub could be seeded to product a (slow) cipher stream of pseudo random numbers that is based upon prime multiplication and quadratic residues.

If you then expand the scope to asymmetric techniques, that are all manner of other mathematically hard trap door problems that can be used in things like lattice and elliptic curve cryptography, key exchange etc.

There are even alternatives to XOR, such as modular addition used in Speck. Speck also extensively features the bit rotate operator.

So you see that the list is longer than you thought, and I've only included a few of the operations that underpin cryptography.  I hope that by listing these, it's proved by deduction that S and P boxes and XOR are not the only tools.


It's a defense against the BEAST attack.

This attack is against TLS 1.0 (and SSLv3) and CBC mode; in CBC mode, TLS always uses the previous ciphertext block as the next IV, and hence the attacker can always predict the IV that will be used to encrypt the next block.  So, what the attacker does is convince the sender to send a specific piece of data; that data, combined with the IV, causes AES (or DES/3DES) to encrypt an attacker chosen block, and that allows the attacker to tell whether previous blocks of encrypted data corresponded to a specific plaintext.

So, for this attack to work, the attacker needs to know the IV that will be used when he chooses the data to encrypt.

What this empty record does is mess this attack up.  The attacker knows the IV that will be used to encrypt the empty record, but he can't control the data that is encrypted (as it is empty).  TLS then sets the 'next IV' to the last ciphertext block of that record; then, TLS encrypts the real record (including the plaintext that the attacker has potentially chosen); however it uses an IV that the attacker could not predict when he selected the plaintext, and so the attack doesn't work.

An easier defense would be to use TLS 1.1 or latter (which selects the CBC mode IV for each record unpredictably), however if you're stuck with TLS 1.0, this is the sort of thing you need to do


How can I store asymmetric keys server-side, so that they are only readable by devices?

Problem Statement:
I will answer this question as I think I understand your problem. I will write down what I've understood from your problem:

Your system is comprised of a central server and some nodes/devices/computers.
You need a digital signature of the devices as well as the server tying them to non-repudiation constraint (They can't deny having taken action.).
The public and private key pairs between devices shouldn't be exchanged between them but rather setup by the server.
The devices should be able to communicate with each other using those asymmetric key pair.

Assumptions:

You can't change packet format or constitution.
Every device obtains its asymmetric key pair from the server.

Solution:
Let every device have a global unique identifier (e.g Medium Access Control address), the configuration of the server takes place like this:

The server opens itself to requests (time-slotted) and creates a table of all the devices (IP, MAC, parameters based on design) then creates 2n keys (Public and Private) for n devices and communicates it to them.
Any device A which intends to communicate to any other device B requests B's public key from the server and locks the message using its (A's) private key.
The message is then passed on to the server which identifies the communicating parties A, B and passes it on to B.
B reads the message by unlocking it using its private key and finds it digitally signed using A's public key.

I would have liked to comment and verify a few details to make this answer  better catered to your problem but I need to gain some rep before commenting.
There are several security issues which will still remain but I will only solve them when you care enough about them.


ECDSA where the group order is larger than the hash size?

What happens when the hash output is smaller than the group size is perfectly defined by FIPS 186-4; namely, nothing special. The hash output is still interpreted as an integer (using big-endian notation). Yes, that integer is in a range that is naturally smaller than the complete range of integers modulo the group order. For all we know, this does not seem to be that much an issue, from a security point of view (contrary to the generation of the per-signature secret value $k$, which must be uniform among the whole range).

The general process is the following: if the curve (sub)group order is $n$, of length $z = \lceil \log_2 n \rceil$ bits, the hash output, if larger than $z$ bits, is first truncated to its first (leftmost) $z$ bits. The possibly truncated result is interpreted as an integer using big-endian notation; that integer, which is then necessarily less than $2^z$, is further reduced modulo $n$. Thanks to the truncation, this modular reduction is inexpensive, since the value to reduce is less than $2n$, so it can be done with a single conditional subtraction. When the hash output length is strictly less than $z$ bits, e.g. with SHA-256 used with secp384r1, then there is no truncation (it's already small enough) and the modular reduction is trivial (the value is already smaller than $n$).

It shall be noted that FIPS 186-4 and ANSI X9.62 recommend using with each curve a hash function with a somewhat "matching" strength. NIST defines 15 curves: for each of five formal "strengths" (80, 112, 128, 192 and 256 bits), the recommended hash function has output length exactly twice the strength, and there are three standard NIST curves whose subgroup order length is at least twice the strength. Thus, when using the recommended hash function for a curve, there is never any truncation. On the other hand, the curve subgroup order nay be quite larger than the hash output; for instance, curve B-283, the binary non-Koblitz standard NIST curve for strength 128, the subgroup order has length 282 bits, i.e. quite larger than the 256-bit output of the recommended hash function for that curve (SHA-256).


This isn't just limited to asymmetric schemes; in any chosen-plaintext attack, even for symmetric ciphers, the attacker can (by definition of the CPA game) compute as many encryptions as they like (limited to polynomial time, of course). Formally, we say the adversary is given access to an "encryption oracle."

Anyway, you have stumbled across a necessary property for CPA security: any cipher that has IND-CPA security has to be nondeterministic. That is, every time a value is encrypted, the ciphertext should be (with overwhelming probability) different. Hence, an attacker can compute $E(m_1)$ and $E(m_2)$, but the challenge ciphertext will be different from either of those thanks to nondeterminism.

As a concrete example, look at the CBC mode for a block cipher. In this mode, each encryption uses an unpredictable IV which is XORed with the first block. Hence, each time you encrypt the same message, it will be (again, with overwhelming probability) a different ciphertext. So, you can't compare ciphertexts to learn if the plaintexts are equal.

In the case of RSA, a careful padding scheme has to be used to transform RSA into a nondeterministic scheme. One such popular padding scheme is Optimal Asymmetric Encryption Padding, often abbreviated as OAEP.

  Does this mean classic hash functions like SHA1, MD5, etc are not
  IND-CPA secure?

Hash functions aren't encryption schemes, so the notion of indistinguishable encryptions doesn't really apply. However, I suppose you could say they don't have "indistinguishable digests" under chosen-plaintext attacks because they are deterministic: if you wanted to build a distinguisher under CPA, you'd do exactly as you suggest in your question, namely compute $H(m_1)$ and $H(m_2)$ and compare that to the "challenge digest."

Actually, there is no secret associated with a hash function, so hash functions don't have indistinguishable digests under any model. If the attacker gets to know the messages, they can just compute the digest of the messages and compare them directly. So, in some sense, an attacker always has access to a "hashing oracle" by the nature of the algorithm. Instead of "indistinguishable digests", a hash function's quality is usually judged on how collision-resistant it is, how hard it is to find pre-images, and so forth.