2
$\begingroup$

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.

$\endgroup$

marked as duplicate by Squeamish Ossifrage, AleksanderRas, kelalaka, Maarten Bodewes encryption Jun 3 at 9:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\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$ – Squeamish Ossifrage Jun 3 at 2:45
  • $\begingroup$ (How do you get $2^{47}$ possible 256-bit primes or moduli?) $\endgroup$ – Squeamish Ossifrage Jun 3 at 2:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.