3
$\begingroup$

I am trying to understand public key encryption. I found the table below in a paper online. I am struggling to understand the meaning of this. From the bits and pieces read, I am tempted to think that the first column is just the encryption done on a secure channel with key lengths as a row. And the premise is that I and recipient have managed to share the key with each other securely. Now, if I were to do that same encryption and share the key with recipient on an insecure channel, I have to beef the key up to the numbers in second column with RSA as a method of hiding my key. Similar for EC keys.

Now AES is a symmetric key algorithm. So does that mean AES-128 requires 256 bit of ECDH key? I am trying to implement this on STM32F chip. I would appreciate any help on better understanding this.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Please always try to include a reference to the paper. $\endgroup$ – Maarten Bodewes Aug 1 '18 at 22:05
  • $\begingroup$ Note: There is a typo in the chart, the final entry for ECC keys should surely read 512 instead of 521 $\endgroup$ – Ella Rose Aug 1 '18 at 22:09
  • 2
    $\begingroup$ @EllaRose Depends. It may be a list for specific implementation that performs Elliptic Curve crypto using the NIST curves. The P-521 curve has a size of 521 bits. Which is awkward, which is why the corresponding brainpool curve does use 512 bits. On the other hand, the brainpoolP512R1 is with an order rather smaller than $2^{512}$, which may slow down the creation of the private key and other calculations. $\endgroup$ – Maarten Bodewes Aug 1 '18 at 22:23
  • 2
    $\begingroup$ @EllaRose No worries, you're not the first one thinking it's a typo ;) $\endgroup$ – e-sushi Aug 2 '18 at 0:11
4
$\begingroup$

No, you are not understanding this correctly. The table shows the required effective key sizes for the different cryptographic primitives.

A cryptographic primitive could for instance be AES, which is a symmetric block cipher. So an AES key should have an effective key size of 128 bits to achieve around 128 bits of security. The best way to attack AES is close to brute forcing the key. So the effective size and strength of the AES key is about the same. This is true for any unbroken symmetric cipher: the effective key size is identical to the key strength.

RSA - an asymmetric algorithm - requires a larger key size because the number calculations are on large numbers. For RSA an attacker can try and refactor the modulus to try and find the private key components. It is therefore much easier to attack RSA than to try $2^X$ values for an $X$-bit key. In the table you can see that it will take about $2^{128}$ tests to break a 3072 bit key. So an AES key of 128 bit and a RSA key of 3072 bits both have a strength of 128 bits.

Elliptic Curve cryptography allows for smaller key sizes than RSA to deliver the same strength asymmetric key pair. Generally the effective key size of the key pair needs to be double the size to achieve the same strength as a symmetric key. So we see the value 256 for ECC in that same row. The curve sizes listed are of the named curves first created by Certicom and later standardized by NIST as P-160, P-224, P-256, P-384 and P-521 (that's not a typo, it's not 512).

Note that for RSA the key size is identical to the size of the modulus; encoding all parts of an RSA key will result in a key that is larger than the modulus and thus the key size. The same goes for ECC keys: the size is the size of the order of the curve, it is not the size of an encoded key.


How the keys are used and if you need symmetric or asymmetric (RSA, DH or ECC) depends on your protocol. RSA is not used because RSA keys are larger, it is because RSA keys are asymmetric, which - for instance - allows you to create a public key infrastructure. AES, RSA and DH keys are all used for different purposes.

When creating a protocol it does make sense to use relating key sizes. So you would use symmetric keys of 128 bit or over, RSA keys of 3072 bits or over and ECC keys (and hashes) of 256 bits or over to achieve an overall strength of 128 bits. This is what you can use the table for.

Using AES-256 (strength: 256 bit) with an RSA key of 1024 bits (strength 80 bits) doesn't make too much sense; an adversary will try and factor the RSA key because it is much easier to do than to brute force AES. So the strength of the protocol would be limited to 80 bits.


You may be wondering about the 80 bit strength for the symmetric key. There are few symmetric ciphers that use an 80 bit key. There are however known meet-in-the-middle attacks for triple DES. An encoded 128 bit key for (three key) triple DES contains 112 bits that are used within the algorithm but that key only contains about 80 bits of security. This was already known when triple-DES was specified.

It's recommended to use a three key triple DES key or to move on to AES. Three key triple DES unsurprisingly has a key strength of 112 bits, explaining the second row.


Your table can be found in the second table of the NIST recommendations of 2016 on keylength.com. Keylength.com also contains pointers to the source material (which may be harder to read).

Note that the last Elliptic Curve size in that table reads 512 bits. NIST however only specifies a 521 bit prime curve, so your table likely references the P-521 curve.

$\endgroup$
  • $\begingroup$ Thank you a million Maarten. That was really helpful. I apologize for a late comment. If I say that for 128 bits security level P-256 is the curve to be used with a key greater than or equal to 32 bytes, would that be a correct implication of your statement - "The same goes for ECC keys: the size is the size of the order of the curve, it is not the size of an encoded key."? Thank you for your time! $\endgroup$ – Jon Aug 14 '18 at 21:10
  • $\begingroup$ No problem, it's not like I was waiting for anything to happen :) Yes, for 128 bit security you can use a curve P-256 or higher. The size of the encoded key (in any form) will be at least the key size so that's correct as well. $\endgroup$ – Maarten Bodewes Aug 14 '18 at 22:36
  • $\begingroup$ Really nice and enlightening answer! $\endgroup$ – GreenScape Feb 23 at 9:13
1
$\begingroup$

It would be helpful if you included a link to the source of that table, in order to understand what exactly the table is supposed to help with.

My guess is that this table compares security of algorithms. For each algorithm you can have a certain key length, which can be compared to the security of a different key length for a different algorithm.

From Elliptic-Curve cryptography on Wikipedia:

a 256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key.

And looking at the corresponding values on symmetric keys - they are half the size of that of elliptic curves. That is due to something known as the Birthday Paradox. Let's not go into it here - but just make note of the meaning of the table. If you want a certain level of security, the number of bits you need in the key depends on the algorithm.

Take a step back now. This is probably not the angle you should look at to understand the fundamentals of public key encryption. From what you write I reckon you need to start with the concepts. For that - just google your way with "introduction to asymmetric encryption" or "..public key incryption". Make sure you understand the difference of symmetric vs asymmetric.

$\endgroup$
  • $\begingroup$ Thank you for your time and comment. I will be careful next time. $\endgroup$ – Jon Aug 14 '18 at 21:11

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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