600% less cryptographic overhead for X.509 certificates

Running asymmetric PKI cryptography on modern servers and high-end clients is not a hassle for more than a decade. Recently all relevant systems are running into a dilemma, as RSA 2048-bit keys are obsolete.

Why a dilemma? The reason is that prime number factorization is extremely time consuming and RSA key operations exponentially increase with its key length.

RSA keys with a length of 1024 bit are recommended by NIST since 2002
Since 2015 NIST recommends a minimum of 2048-bits for RSA keys.
Nowadays the German Federal Office for Information Security (BSI) recommends in its BSI TR-02102-1 Technical Guideline – Cryptographic Algorithms and Key Lengths dated March 24, 2021, a minimum of 3000-bits for RSA keys for use from year 2024 onwards.

Federal Office for Information Security (BSI), Technical Guideline – Cryptographic Algorithms and Key Lengths dated January 28, 2022

Note: As RSA 3072 keys are rarely supported by IT systems our further considerations are based on RSA 4096-bit keys.

For new cryptographic environments you need to comply to latest international standards and implement key length according to authorities like German Federal Office for Information Security (BSI). The following crypto safe options exist: block cipher (AES-keys) with 128-bit, RSA keys with 3000-bits, or ECDSA keys with at least 250-bit length.

ECDSA keys, also called EC or ECC keys, are a great alternative to RSA 3000-bit keys and do offer many advantages:

Much faster key generation
Smaller keys size due to less bits
Faster key operations, especially on low-end CPUs like 16-bit or 32-bit microprocessors or low-power IoT devices

What’s the cost of RSA 4096 keys?

Running a Certificate Authority (CA) with RSA cryptography requires that by the end of 2023 the full certificate trust chain is based on RSA 4096-bit keys. Typically, this trust chain consists of a root CA, an issuing CA and the key inside the client certificate.

Two-tier certificate authority based on RSA 4096-bit keys.

Sizing considerations for RSA keys and certificates

A typical RSA trust chain consists of three files:

RSA-4096 PKI Files	File Size
Root Certificate	2569 bytes
Issue Certificate	2596 bytes
P12-Container	5114 bytes
Total	10252 bytes

There is not much you can optimize in an RSA CA to reduce the memory amount (in RAM and on flash) of the required keys and certificates. Reducing the naming attributes and extended key usages and eliminating the CRL reference may give you an advantage of 150-200 bytes only.

CPU usage by RSA operations

Widely known RSA key generation is a resource costly task. Using my favorite crypto-tool I generated some hundreds RSA keys with different key lengths and measured the time used. The keys were generated on a mid-size server hardware, so I’m sure you may have better results in your multi-core server environment.

Keygen OPs	RSA-1024	RSA-2048	RSA-4096
100	1,76 sec	8,3 sec	57,9 sec
200	3,52 sec	16,6 sec	115,8 sec
300	5,28 sec	24,9 sec	173,7 sec
400	7,04 sec	33,2 sec	231,6 sec
500	8,8 sec	41,5 sec	289,5 sec

Bringing a light-footed rival to the crypto battlefield: “Brainpool”

Elliptic curve cryptography (ECC) is an asymmetric method for digital signature, verification, and key exchange. Even as ECC is much younger than RSA cryptography, nowadays it’s widely implemented in Microsoft’s ecosystem and open-source solutions including OpenSSL and Python.

ECC eliminates the need of prime number factorization reducing the key size and CPU operations dramatically. Let’s check its vitals!

The size of ECC keys and certificates

Generating a Certificate Authority (CA) with Brainpool ECC keys fulfils latest guidelines of regulating authorities. In our example we use BrainpoolP256R1 a Brainpool curve specified in RFC 5639.

Again, our setup builds a two-tier trust chain consists of a root CA, an issuing CA and the key inside the client certificate.

ECC Certificate Chain (Windows 10)

In our Brainpool CA example we use se.SAM™ PKI build-in IoT certificate template to deduct any certificate overhead in the issued certificates. Still the certificates are meaningful and can be verified in operating systems including Windows 10.

We removed the following certificates attributes to reduce its size:

Eliminate unnecessary fields like address, city, country
Reduce length of name fields like common name, organization name, etc.
Remove CRL distribution point
Skip Authority Information Access (AIA) information

Brainpool files: size matters!

Our Brainpool CA trust chain consists of three files:

RSA-4096 PKI Files	File Size
Root Certificate	562 bytes
Issue Certificate	570 bytes
P12-Container	558 bytes
Total	1690 bytes

Keep in mind that 10K for RSA files compared to 1,7K for Brainpool files does not matter on an Intel server or Windows 10 environment, but definitely it does on a 32-bit microprocessor with as little as 32 KByte of SRAM.

Save CO₂ and CPU heating with ECC operations…

Let’s get straight to the point: Brainpool keygen operations require a fraction of the CPU time consumed by RSA operations, here the timetable.

Keygen OPs	Brainpool-256
100	0,3 sec
200	0,6 sec
300	0,9 sec
400	1,2 sec
500	1,5 sec

Honestly speaking this time gain is not a unique advantage of Brainpool ECC. All other elliptic curves implemented in OpenSSL will result in similar performance measurements, I quick checked:

secp256k1 SECG curve over a 256-bit prime field
secp521r1 NIST/SECG curve over a 521-bit prime field
prime256v1 X9.62/SECG curve over a 256-bit prime field
sect283r1 NIST/SECG curve over a 283-bit binary field
sect571r1 NIST/SECG curve over a 571-bit binary field

The overall result for all curves is 100 operations will take about 0.3 seconds.

The 5-star winner in the CA race: Brainpool elliptic curve!

Brainpool elliptic curve is a modern successor in todays PKI. Offering a key length from 160-bit to 512-bit, Brainpool is already available in modern cryptographic toolkits and libraries.

Brainpool ECC saves memory:

PKI-Files	RSA-4096	Brainpool
Root Certificate	2569 bytes	562 bytes
Issue Certificate	2569 bytes	570 bytes
P12-Container	5114 bytes	570 bytes
Total	10252 bytes (600% in size)	1690 bytes (100% in size)

Brainpool offers you great performance, compared to RSA:

Seconds	RSA-1024	RSA-2048	RSA-4096	Brainpool-256
1 sec	57	12	2	357
2 sec	114	24	3	714
3 sec	170	36	5	1071
4 sec	227	48	7	1429
5 sec	284	60	9	1786
6 sec	341	72	10	2143

RSA/Brainpool key generate comparison on a mid-size Intel server platform.

Brainpool allows to generate about 2100 keys within 6 seconds, compared to 10 RSA-4096 keys.Brainpool allows to generate about 2100 keys within 6 seconds, compared to 10 RSA-4096 keys.

Also, ECC signature processing is much faster than RSA operations:

Crypto-Operations	RSA-4096	Brainpool
Signature (1000x)	10,2 sec	3,0 sec
Verification (1000x)	2,7 sec	2,7 sec
Total	12,7 sec (220% time)	5,7 sec (100% time)

In current crypto-tools and operating systems you find a variety of ECC algorithms, including SECG, NIST, Koblitz, Brainpool and others, see the result of OpenSSL 1.1.1q (July 2022):

openssl ecparam -list_curves

(truncated) 
  brainpoolP160r1: RFC 5639 curve over a 160 bit prime field
  brainpoolP160t1: RFC 5639 curve over a 160 bit prime field
  brainpoolP192r1: RFC 5639 curve over a 192 bit prime field
  brainpoolP192t1: RFC 5639 curve over a 192 bit prime field
  brainpoolP224r1: RFC 5639 curve over a 224 bit prime field
  brainpoolP224t1: RFC 5639 curve over a 224 bit prime field
  brainpoolP256r1: RFC 5639 curve over a 256 bit prime field
  brainpoolP256t1: RFC 5639 curve over a 256 bit prime field
  brainpoolP320r1: RFC 5639 curve over a 320 bit prime field
  brainpoolP320t1: RFC 5639 curve over a 320 bit prime field
  brainpoolP384r1: RFC 5639 curve over a 384 bit prime field
  brainpoolP384t1: RFC 5639 curve over a 384 bit prime field
  brainpoolP512r1: RFC 5639 curve over a 512 bit prime field
  brainpoolP512t1: RFC 5639 curve over a 512 bit prime field

Now its time to compare compatibility and results of Brainpool EC.

Fact #1: PKIs based on Brainpool keys with 250+ bits are compliant to latest regularities of authorities

Fact #2: Brainpool and other elliptic curves are already widely supported in operating systems including Windows and Linux.

Fact #3: Signature and verification are about 220% faster with Brainpool ECDSA than RSA sign/verify.

Fact #4: Brainpool ECC can reduce the size of keys and certificates by more than 600% compared to equal strength RSA keys, saving bandwidth, flash and RAM.

Fact #5: Brainpool allows you to generate 357 keys per seconds, while RSA-4096 generate only 2 keys. Given you a performance gain of 17800%.

All measurements are not taken in calibrated environments, but repeatedly measured on a latest Linux Debian OS with no other applications interfering.

Keep an eye on:

se.SAM™ U110 and U210 USB ModulesPlug and Play Crypto Modules, ECC/Brainpool ready
se.SAM™ P210 and P220 MiniPCIe ModulesPlug and Play Crypto Modules, ECC/Brainpool ready
se.SAM™ EmbeddedSoftware library and Embedded hardware chip for PCB mount, ECC/Brainpool ready
se.SAM™ N200 19″ Network Crypto ApplianceGUI and REST-API ECC/Brainpool ready
se.SAM™ N200X Industrial Crypto ApplianceDIN-rail network HSM, 24-48V DC, GUI and REST-API ECC/Brainpool ready

We are happy to support you migration to ECC with this article or in a joint project.