# Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)?

Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts be distinguished from random noise? Justify why, why not?

That is do the major asymmetric ciphers have any statical bias?

If you knew which asymmetric algorithm was used and you had a ciphertext of a random plaintext number and the public key that generated that ciphertext. Would it be easier than random chance to find the plaintext? Doesn't the fact that RSA requires extremely large keys imply that finding the plaintext is easier than guessing? If it is the case that finding a random plaintext is easier than randomly guessing a plaintext does this fact have any implications for the case in which the public key is not known and the attacker only has the ciphertext?

-

Asymmetric encryption requires some mathematical structure (to enable the magic of asymmetry), and some of that structure is readily apparent to anybody. For instance, with RSA, the encrypted messages are numbers modulo n (the modulus, from the public key), and thus in the range 0 to n-1. This implies that values for the first byte will be quite biased (RSA uses big-endian encoding, so the first byte is the most significant byte). For anything with elliptic curves, this is even easier, since the usual representation of a curve point will be a pair of coordinates (X,Y) in a finite field, matching the curve equation. Random noise has almost zero chance of producing values which will match the curve equation.

It is normally assumed that everybody knows which algorithm was used and with what encryption key (this is a public key and we mean it). The algorithm exists as software in many places (on every machine which uses that application, as source code on the developers' systems, ...) so it seems quite hard to conceal that information anyway. Asymmetric encryption algorithms are thus designed so that this is not a problem.

In particular, asymmetric encryption includes random data. Indeed, since the public key is public, an attacker could try to guess the plaintext by encrypting potential plaintexts until one matches the actual ciphertext. The random data defeats that: even if he has guessed the right plaintext, the attacker will get something different and will not know that he has guessed correctly.

Note that in practice, an asymmetric encryption algorithm has a lot of overhead (computational cost, enlarged ciphertext...) so nobody encrypts a large file with that; instead, we encrypt a random symmetric key (aka "a bunch of random bytes") with the asymmetric encryption algorithm, and then we use that symmetric key to actually encrypt the file with a fast and lean symmetric encryption algorithm like the AES -- and that will give you a sequence of bytes indistinguishable from random noise.

-
Is bias required by any asymmetric algorithm? Is there a proof for this? –  Ethan Heilman Jul 20 '11 at 11:08
@e501: presence of a bias is not a necessity. It is just that we do not know how to make an asymmetric encryption algorithm which will output sequences of bits indistinguishable from random strings of the same size. Also, we do not (usually) care: this is not an issue with regards to how asymmetric encryption algorithms are used. –  Thomas Pornin Jul 20 '11 at 12:20
Is it unimportant in the sense that given two asymmetric ciphers where one cipher has bias and the other cipher does not you would not prefer one without bias over the other? AES is used because it is significantly faster than RSA, but it introduces more surface area since a break in either RSA or AES results in decryption of your message. Is the idea that RSA + AES is good enough born out of the fact that we don't have a fast unbiased asymmetric cipher? –  Ethan Heilman Jul 20 '11 at 12:45
@e501: security of an asymmetric encryption algorithm is not defined in how it looks like noise or not. On the other hand, trying to use an asymmetric encryption algorithm for the job of a block cipher, in particular encrypting a "long message", looks like a recipe for failure (you cannot just slap CBC over RSA, for instance). The critical part is that public key encryption necessarily enlarges the data (because randomness must be included at some point), and this makes all the work on encryption modes of operation unapplicable. –  Thomas Pornin Jul 20 '11 at 12:52
@e501: considering that RSA with a 1024-bit key accepts messages up to 117 bytes each, but outputs 128-byte ciphertext, XORing each input with the output of the previous block is not immediate: two XOR two sequences together, they must have the same length. At which point you would need to XOR each block with parts of the previous ciphertext, and knowing which part to use does not seem to be completely obvious. This is uncharted territory. Which means: no more benefits from the three decades of analysis by hundreds of cryptographers. You are on your own. –  Thomas Pornin Jul 20 '11 at 16:18

It may be useful to define what is meant by noise. Noise is data that is selected randomly from some distribution. @Thomas deals with comparing to random bitstrings (where each bit is equally likely 0 or 1) and notes that because not all bitstrings of an appropriate length are possible values in most asymmetric encryption functions, real ciphertexts will be distinguishable from randomly generated bitstrings.

A different approach to defining noise might be to take the set of all valid values in the encryptions scheme and randomly choose one of them (with equal probability). For example, pick a random integer in [0,n-1] for RSA, a random point on the curve for Elgamal on elliptic curves, a random number in subgroup Gq for Elgamal over the integers, etc. For these distributions, we can ask, is an actual ciphertext distinguishable from a randomly chosen but plausible value for a ciphertext?

If you are given a ciphertext only (with zero information about the plaintext), then both RSA and ELgamal are indistinguishable from a randomly chosen but plausible value. However if you are given a plaintext and either its corresponding ciphertext or a random plausible value (and you need to decide which), then things are more interesting.

Textbook RSA (e.g., RSA without padding) is distinguishable from a random plausible value. This is for two reasons: (1) RSA is deterministic, meaning it is simple to encrypt the plaintext and see if it matches and (2) RSA leaks one bit of information about the plaintext.

Textbook Elgamal (e.g., Elgamal as originally proposed over the integers mod p) resolves the first issue with RSA. It is a randomized encryption algorithm meaning if you encrypt the same plaintext twice, you get different, indistinguishable results. However it does not resolve the second issue and still leaks one bit of information about the ciphertext (whether it is a quadratic residue or not).

Elgamal and RSA-OAEP both resolve the shorting-comings of their respective textbook versions. Textbook Elgamal is already randomized, so it is simply a matter of using it in a proper setting (in this case a subgroup of the integers between 1 and p-1 where they all have the same value for the leaked bit, or such a group on an elliptic curve). For RSA, padding adds both randomness and destroys the correspondence between the plaintext and ciphertext that is leaked in its textbook version. For both of these encryption methods, a ciphertext is indistinguishable from a random plausible ciphertext, even when given the corresponding plaintext.

-
If a given public_key can generate n possible ciphertexts for any message (this is what you mean by plausible ciphertexts right?), and the first bit of that plaintexts reduces the space of possible (plausible) ciphertexts, given that public_key, to n-1 doesn't that imply a bias in the possible (plausible) ciphertexts. If the first bit of the message does not reduce the number of possible ciphertexts I'm not sure how the process can possibly be reversible. –  Ethan Heilman Jul 20 '11 at 21:23
For a fixed plaintext and key pair, we can consider three sets: (1) invalid ciphertexts: numbers/bitstrings that are of the wrong form, (2) plausible ciphertexts: numbers of the right form but do not necessarily decrypt to the plaintext, (3) actual ciphertext(s): the set of ciphertexts that actually decrypt to the plaintext with the key. What I am addressing in my answer is your ability to tell (2) and (3) apart and what I omitted, which may clarify, is telling them apart without the secret key using today's level of computational ability. They can be distinguished with unlimited computation. –  PulpSpy Jul 21 '11 at 16:13

Actually, it is possible to define RSA in such a way that the RSA ciphertexts are indistinguishable from random bit strings of the same length. The method is quite simple:

• When you select the RSA key, you deliberately pick a modulus that is just under a power of 256; for example, if you are generating a 2048 bit key, you select a modulus between $2^{2048} - 2^{1920}$ and $2^{2048}$. That is easy to do; when generating the modulus, you select your first prime $p$ as normal, and then search for your second prime in the range $(2^{2048} - 2^{1920})/p$ to $2^{2048}/p$

• You use a randomized padding method (and not one that creates a bias in the Jacobi symbol of the padded message); any of the standard RSA encryption padding methods meet this criteria.

The first ensures that the bias in the first byte that Thomas mentioned is too small to be detectable; the second ensures that someone can't gain any information from computing the Jacobi symbol of the ciphertexts (which would be the Jacobi symbol of the padded plaintext).

Now, as Thomas mentions, there is little reason to do so; however, it is possible.

-