Related to \"Is it possible to derive the encryption method from encrypted text?
ID: 651712 • Letter: R
Question
Related to "Is it possible to derive the encryption method from encrypted text?".
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?
Explanation / Answer
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.