I have been reading that RSA has to do with math (prime numbers), while symmetric key encryption deals with blocks of data and modifying the blocks with replacements and remappings, but I still don't understand why asymmetric encryption has to have longer keys because of that, or whether that's even the reason.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ @Jane Doe Consider that a symmetric key could be very long, even longer than most of the asymmetric keys you might be used to dealing with. Here, of course, the words "long" and "short" are relative. $\endgroup$– PatriotJun 1, 2019 at 15:59
-
1$\begingroup$ Also consider ECC keys which are about as short as symmetric keys (2x or so, not 10x -20x for RSA). $\endgroup$– SAI PeregrinusJun 1, 2019 at 18:48
-
$\begingroup$ Actually, one could design a hash-based signature method with both private and public keys as short as the corresponding symmetric key; Gravity-Sphincs comes close... $\endgroup$– ponchoJun 1, 2019 at 19:03
-
1$\begingroup$ Dupe crypto.stackexchange.com/questions/6236/… crypto.stackexchange.com/questions/8687/… crypto.stackexchange.com/questions/46852/… and more on security.SX. $\endgroup$– dave_thompson_085Jun 2, 2019 at 1:09
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Asymmetric algorithms
Asymmetric algorithms rely on mathematical structure. Keys for asymmetric algorithms typically have some kind of structure, as opposed to being uniformly random bit strings. This structure can be exploited to reduce the cost of breaking the system.
Additionally, with asymmetric cryptography, there is more information to work with; The public key has some known relation to the private key, and everyone has the public key. This is in addition to the usual information that you might have from what the system is used for, e.g. plaintext-ciphertext pairs or message-signature pairs.
Symmetric algorithms
Keys for symmetric algorithms do not have structure - They are simply a uniformly random block of bits.
Other than plaintext-ciphertext pairs, you typically do not have any more information about the key. The relation of the key to the bits of the plaintext/ciphertext are extremely complex with no regular or helpful structure to speak of.
Of course, you could have a cipher with a 256-bit key that is vulnerable to an attack that recovers the key in negligible time from a single ciphertext.
Key size
Key size isn't really what is relevant. What is important is the cost of the best attack to break the system.
With a strong symmetric algorithm, the best attack will be brute force guessing the key. So the size of the key more or less directly controls the cost of the best attack against the system.
The structure used by asymmetric algorithms typically results in the existence of attacks better than brute force guessing the key. So the key size has to be increased to compensate. This is visible in RSA as each prime $p, q$ is much much larger than the size required to prevent brute force guessing; Brute force guessing is not the best attack, so the keys are not scaled against the cost estimate that brute force would have.
Note
The above are generalizations that are only approximately true - it is possible to design symmetric algorithms that have structure - But those are not what people usually mean when they say "symmetric encryption".
Additionally, it's also possible to generate at random an AES key that happens to be the product of two somewhat sizable primes; But that won't tend to help cryptanalysis of AES much because that structure doesn't appear to be helpful.
answered Jun 1, 2019 at 14:53
$\begingroup$
$\endgroup$
2
Suppose you use for symmetric encryption a key of 256 bit. Any of 256-bit numbers can be used as a password. That's why there are 2^256 password candidates that an attacker has to test in a brute force attack.
Where as for RSA not every number can be used. RSA keys are based on prime numbers with special properties. In any given range only a small part of numbers fit these criteria, all others can be easily filtered out before brute force attack. For instance, out of all 256-bit numbers only 2^47 can be used for RSA. This is essentially less than in case of symmetric encryption.
That's why for RSA to get the same number of password candidates you have to use a bigger range. For instance, to get 2^256 candidates for RSA you have to use bigger range, about 13500 bits.
You can find more details here: Security strength of RSA in relation with the modulus size
-
$\begingroup$ The mere number of candidate keys doesn't really explain this. If we used 140-bit primes to make a 280-bit modulus, and used a fixed exponent like $e = 3$ so the modulus completely determines the key, the approximation $\pi(x) \approx x/\log x$ to the prime-counting function $\pi$ suggests that there are well over $2^{128}$ candidate primes and therefore well over $2^{256}$ candidate keys. But a 280-bit modulus is hopelessly insecure for RSA—larger moduli were demonstrated to be breakable a quarter century ago! You could probably factor a 280-bit modulus on your laptop today in hours. $\endgroup$ Jun 3, 2019 at 2:45
-
$\begingroup$ (How do you get $2^{47}$ possible 256-bit primes or moduli?) $\endgroup$ Jun 3, 2019 at 2:49