Basics: Elliptic curves with regard to their use in the public key infrastructure

With Windows Vista and Windows Server 2008, the Cryptography API: Next Generation (CNG) was introduced into the Windows systems.

This term refers to a collection of modern cryptographic functions. Among other things, the CNG enables the use of certificates that use keys based on elliptic curves (also called Elliptic Curve Cryptography, ECC) with the Microsoft Certification Authority and the Windows operating system.

Reasons for using elliptic curves

While the SHA2 hash algorithm, which was also implemented with the CNG, has long since become the de facto standard, and it also increasingly prevail on websiteselliptical curves have not yet been widely adopted in corporate public key infrastructures.

However, there are good reasons for their use and early adaptation:

  • With the same cryptographic strength, they require significantly less computing power compared to RSA keys. This can be of great importance when using low-power embedded devices (keywords: microcontrollers and Internet of Things), but it can also have a significant impact on everyday life. It is now clear that TLS/SSL handshakes are significantly faster, which reduces the perceived loading time of websites.
  • With RSA, the security comparable to ECC increases only with exponentially increasing key length. The 4096 bits, which are currently still regarded as a sensible maximum, provide only a small increase in security compared to 2048 bits. For security comparable to symmetric encryption of 256 bits, 15,360-bit RSA keys would already be needed, i.e. with increasing demand for key strength, RSA will become increasingly inefficient and computationally intensive in the foreseeable future.
  • Technical reasons can also speak in favor of using ECC keys. For example, the Trusted Platform Module (TPM) 2.0 standard specifies a maximum of 2048 bits for RSA keys, but allows ECC keys of up to 384 bits. Thus - if keys are to be protected with a TPM - an increase in cryptographic strength can only be achieved with ECC keys.

The following is a comparison of the cryptographic strength of RSA and ECC keys compared to a symmetric method such as AES.

Key length (RSA)Key length (ECC)Comparable symmetric key length
15360512 (521)256
Source: The Case for Elliptic Curve Cryptography (National Security Agency, archive link)

The comparison of symmetric and asymmetric methods means that the key lengths shown as comparable in the table have a comparable theoretical resistance to brute force attacks, i.e. trying all combinations.

The following is a comparison of the computational effort required between RSA and ECC.

symmetrical bit lengthComputational effort in comparison RSA vs ECC
803 : 1
1126 : 1
12810 : 1
19232 : 1
25664 : 1
Source: The Case for Elliptic Curve Cryptography (National Security Agency, archive link)

Safety of ECC and the curves used

Keys based on elliptic curves are not per se "more secure" or "less secure" than keys based on RSA, as long as a comparable key strength (see above) is chosen.

While at current security levels elliptic curves do not offer significant benefits over existing public key algorithms, as one scales security upwards over time to meet the evolving threat posed by eavesdroppers and hackers with access to greater computing resources, elliptic curves begin to offer dramatic savings over the old, first generation techniques.

The Case for Elliptic Curve Cryptography (National Security Agency, archive link)

The curves used are also not per se "safer" or "more insecure" than others, but the implementations in software may differ: Some curves are easier to implement safely, others only with greater effort and higher susceptibility to errors.


NSA Suite B

The algorithms contained in the "Suite B" specified by the National Security Agency (NSA) can be considered the lowest common denominator among PKI implementations that support ECC.

PurposeAlgorithmSecret" levelTop Secret" level
EncryptionAdvanced Encryption Standard (AES)AES-128AES-256
Digital signatureElliptic Curve Digital Signature Algorithm (ECDSA)ECDSA_P256ECDSA_P384
Key exchangeElliptic Curve Diffie-Hellman (ECDH)ECDH_P256ECDH_P384
ChecksumsSecure Hash Algorithm (SHA)SHA256SHA384

The Microsoft CNG has implemented the algorithms defined in Suite B. Conversely, this does not mean that all newly implemented algorithms are part of NSA Suite B.

The secp521r1 curve (used by ECDSA_P521 and ECDH_P521) is thus not Part of the NSA Suite B. The same applies to the SHA512 hash algorithm, see RFC 5759.

As can be seen, the NSA (with the exception of the AES algorithm) aims for a maximum "Bitness" of 192 bits with Suite B.

Commercial National Security Algorithm Suite" (CNSA)

Suite B has since been replaced by the Commercial National Security Algorithm Suite (CNSA). This also includes RSA again with correspondingly large keys (3072 bits for "Top Secret" protection class).

In the meantime, however, the NSA is distancing itself from efforts to use Suite B or CNSA and to rely on quantum-resistant algorithms that will be available in the foreseeable future, also due to current advances in the field of quantum cryptography:

For those partners and vendors that have not yet made the transition to Suite B algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.

Cryptography Today, National Security Agency (NSA)

Thus, we will probably not see the large-scale use of elliptic curves in the field of corporate PKIs.

Elliptic Curves in Windows and Active Directory Certificate Services

A serious factor for the successful use of certain curves is the Support by common operating systems and crypto libraries.

The following algorithms can be used for digital certificates with Microsoft Active Directory Certificate Services and the Windows operating system:

Elliptic Curve Diffie-Hellman key exchange algorithmNIST SP800-56A
Elliptic Curve Digital Signature AlgorithmNIST FIPS 186-2
ANSI X9.62

The algorithms each use the NIST curves P256 (secp256r1), P384 (secp384r1), or P521 (secp521r1). See also RFCs 3279 and 5480.

It should be noted that each variant is an independent algorithm, i.e. something like "RSA with key length X" does not exist here. Rather, "ECDSA or ECDH with curve X".

Support is not (...once in the Windows ecosystem) given everywhere

Although Microsoft has implemented elliptical curves since Windows Vista, they cannot be used across the board everywhere. Whether they can be used in the Windows world depends (besides the end application that is to process the certificates) also on whether the Key storage is possible.

Some examples:

Separation between signature and key exchange procedures

An interesting feature of the use of ECC keys is the fact that no hybrid keys (signature and encryption) can be used as with RSA.

With Suite B, the ECC key for a given certificate can only be used for either signature or encryption, but not both. Be sure not to select the option for both Signature and Encryption. If both signature and encryption are selected, then only ECDH algorithms will be available and the key will only be valid for encryption.

Microsoft, Suite B PKI in Windows Server 2008 (archive link)

So, for common use cases, the key algorithm selection would look something like this:

Use CaseAlgorithm family
Web serverECDSA
Code signatureECDSA
KDC AuthenticationECDSA
Email signatureECDSA
Email encryptionECDH
Private Key ArchivingECDH
Key Recovery AgentECDH

Consequently, when switching S/MIME from RSA to elliptic curves, you would now have to issue two certificates to users - one for signing, one for encrypting (if you previously used only one for both purposes).

Assessment for practicality

As of today (2022), most enterprise PKIs continue to use the RSA algorithm for their certificate authority and end certificates. In the coming years, at least the Key length increase on the schedule.

In some cases, such as when one private key with the Trusted Platform Module (TPM) of the end device.If you want to increase their cryptographic strength (since TPM can usually only protect RSA keys with a maximum strength of 2048 bits), you will not be able to avoid using elliptic curve-based keys.

On the opposite side, however, there is still uncertainty as to whether all systems participating in the PKI can handle keys based on elliptic curves. It is therefore illusory for the time being to be able to work with a PKI based purely on these key algorithms.

For certification authority certificates, one will therefore have to continue using large RSA keys for the foreseeable future if one does not want the luxury of two productive certification authority hierarchies (one with RSA keys, one with ECC keys) and the associated disadvantages would like to perform.

The fact that standardization authorities such as the NSA now advise against investing in Suite B algorithms also underscores this thesis.

If you still want to or have to use them, it is nevertheless advisable to use Suite B as a guide in order to achieve the greatest possible compatibility. Algorithms that are not included in Suite B (namely SHA512 and the secp521r1 curve) should therefore not be used.

Related links

External sources