why is breaking a (asymmetric) 1024 bit RSA key less difficult than breaking a 128 bit (symmetric) AES key? Breaking RSA key involves finding the prime factors of a large number. What is involved in breaking an AES key?
3
-
$\begingroup$ I should say: Breaking RSA key involves finding the prime factors of a 1024-bit semi-prime. What is involved in breaking an 128-bit AES key? $\endgroup$– george sCommented Nov 11, 2021 at 12:36
-
$\begingroup$ You might think about the different ways an AES key can be created. $\endgroup$– SwashbucklerCommented Nov 11, 2021 at 13:31
-
$\begingroup$ For AES, almost all are listed here: Has AES-128 been fully broken?. And, you are comparing apples and oranges. $\endgroup$– kelalakaCommented Nov 11, 2021 at 16:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The bitlength of an algorithm does not reflect security in a 1:1 relation.
The reason for this is, that for security we consider the most efficient algorithm known. security "bits" is not so much a measure of how long any specific number is, but it is a measure of the complexity for the attack.
For your specific case:
- The most efficient attack on RSA is factoring the modulus with the General Number Field Sieve. The complexity is $L_n\left[1/3, \sqrt[3]{64/9} \right]$, for a number of length $log(n)$. For large numbers, this is super-polynomial, but much, much less than exponential in the number of bits of $n$.
- For AES, the most efficient attacks are quite close to the actual bitlength of the key. The best known attack on AES 128 has complexity $2^{126}$, which is usually called "126 bits" of security.
As a final note: The website https://www.keylength.com/ is a very good site, which references the recommendations from science and governance. Those papers give the current recommendations for the different systems, put them in relation and provide extensive arguments for those recommendations. It's definately worth following up on your question there.
