Asymmetric Cryptosystems

This week, we will be diving a bit deeper into how asymmetric cryptosystems work to answer common questions about key size and key type.

This article is part of an ongoing series on using X.509 encryption on SmartOS.  It's recommended to read the previous article before continuing.

Overview

Asymmetric cryptosystems are a combination of game theory and number theory, namely a combination of information asymmetry and a math problem that is easy to solve with the right information and difficult to solve without it.

In the case of the RSA cryptosystem, the basic principle is that it's practical to find large positive integers \(e\), \(d\) and \(n\) such that:

\[ m \equiv \left ( m^e \right )^d \pmod n \]

For all \(m\), and that even while having \(e\),\(n\) or \(m\) it can be extremely difficult to determine \(d\).  Specifically, this comes down to the difficulty of quickly factoring large numbers with the relationship:

\[ n \equiv pq \]

It's easy to find \(n\) when you have \(p\) and \(q\), but difficult to find \(p\) and \(q\) when all you have is \(n\).

In ECC cryptosystems, the core difficulty is determining the discrete logarithm of a random elliptic curve element with respect to a publicly known base point.  The curve element is expressed by the following equation:

\[ y^2 \equiv x^3 + ax + b \]

Consider a line intersecting three points along the curve: \(P\), \(Q\) and \(R\).  Knowing \(P\) and \(Q\) makes it relatively trivial to determine \(R\).  It is nearly impossible to determine \(P\) and \(Q\) knowing just \(R\).

If there is interest, I may go into more detail onto the internal function of RSA, ECC, and DH as well as techniques for breaking these cryptosystems.

RSA vs ECC

Currently, both RSA and ECC (ECDSA) are available for use as digital signature algorithms and key agreement in common X.509 implementations (such as OpenSSL).

Size

One of the first things noticed when comparing RSA to ECC is that ECC keys are much smaller for the same relative strength.  This is due to the nature of the differences between the core problems of RSA and ECC, and the perceived difficulty of cracking ECC.  Additionally, as key sizes increase linearly, the difficulty of cracking an ECC key increases exponentially, indicating that an exponential regression is appropriate to determine the relationship between RSA and ECC key strength (with respect to key size).

This is illustrated in the following table, with symmetric key sizes thrown in for comparison:

And the exponential regression for anyone curious.  \(size_{ecc}\) is the size of an ECC key and \(size_{rsa}\) is the size of a roughly equivalent in difficulty RSA key:

\[ size_{rsa} = (389.646)(1.00737)^{size_{ecc}} \]

Performance

Key generation performance isn't even a competition for ECC, which wins by obvious orders of magnitude.

For signature generation and signature verification, we turn to OpenSSL's benchmarking functionality.

$ openssl speed rsa1024 rsa2048 rsa4096 ecdsap160 ecdsap224 \
ecdsap256 ecdsak283 ecdsap384 ecdsak409 ecdsap521
...
<results>

Please note that this takes a while to run as it will benchmark everything.  Also, the results are displayed in tables based on encryption type, we want to see them as a unified table showing both results in one table

From these results, we can make several assertions about performance:

• Smaller RSA keys outperform larger RSA keys with regards to both signature generation and verification.
• It is significantly cheaper to verify an RSA signature than it is to generate one.  The difference gets more significant as the key-size increases.
• Larger ECC keys are generally lower performance than smaller ECC keys.  However, some larger key sizes perform better than smaller ones (256-bit outperforms 160-bit and 224-bit, 384-bit outperforms 283-bit, 521-bit outperforms 409-bit).
• It is marginally cheaper to generate an ECC signature than it is to verify one.  This shows very little variance with respect to key-size.
• ECC signature generation performance is better than RSA signature generation performance for a given key strength.  ECC has better relative performance as key size increases.
• RSA signature verification performance is better than ECC signature verification performance for a given key strength.

In researching the topic before performing my own benchmarks, I found several white papers which confirm my own subsequent experimental findings:

• Performance Comparison of Elliptic Curve and RSA Digital Signatures (2004-04-28) by Nicholas Jansma and Brandon Arrendondo for the performance comparison of common RSA and ECC crypto functions on standard x86 architecture hardware, specifically an Intel Pentium4 2.0GHz processor with 512MB of RAM.
• Comparison and Evaluation of Digital Signature Schemes Employed in NDN Network (2015) by Al Imem Ali for the performance comparison of common RSA and ECC crypto functions on standard AMD64 architecture hardware, specifically an Intel i5-2450M 2.5GHz processor with 4096MB of RAM.

Unfortunately, I was unable to find a suitable study analyzing the performance difference of RSA vs ECC on ARM hardware.

These assertions should be considered when making decisions about which cryptographic algorithms or key sizes should be used in certain contexts.  For instance, a web server which is generating signatures to verify it's identity may benefit more from ECC over RSA since the signature generation cost will be focused on a small number of computers (the servers) and the signature verification costs will be distributed to a large number of computers (the clients).

Maturity

RSA's maturity provides it more stability as an encryption algorithm over the relatively unproven ECC.

The core problem of RSA: Factoring a product of two large prime numbers, is well documented and well understood.  A lot of time and effort has been put into increasing factoring speed, with most researchers settling on the General Number Field Sieve as the most efficient classical algorithm for factoring large integers.

The core problem of ECC: Calculating a discrete logarithm of a random elliptic curve, is not nearly as well understood.  Namely, much less time has been spent addressing this problem, and there is no known efficient algorithm for performing this task.  With the increased utilization of ECC, the incentives to explore possible efficient algorithms may become great enough for the field to be explored more thoroughly.

Availability

While ECC is well supported with modern browsers on standard computers.  As mentioned before, it's also fully supported by OpenSSL and GnuTLS.  Its performance takes a significant hit on architectures with less developed ECC implementations, most notably when using Bouncy Castle, the Java implementation used on Android.

While both ECC and RSA face specific size and performance limitations on cryptographic hardware, this is more of an issue for ECC, which due to its immaturity, is more likely may be subject to improved cryptanalysis techniques in the future.

Appropriate Key Size

The first thing to understand about key length is that there is no such thing as a safe length.  The longer a key is, the more resistant to cracking it will be over time.  However, due to the uncertainty of the future in regards to cryptanalysis algorithms and available computer hardware (discrete vs quantum computing), accurate predictions of safe key lengths should not be trusted beyond 20-25 years out.  A brief survey of trusted root certificates in my local stores showed a common maximum period of valid use to be 28-30 years, which I would consider an absolute maximum given how volatile technology is.

With that having been said, there are several organizations which make predictions as to the viability of key lengths into the near (and mid) future.

According to RSA Security, 2048-bit keys are sufficient until 2030, with 3072-bit keys being the recommendation for any system which needs to be viable past 2030.

Additionally, one can graph and extrapolate public factorizations of RSA keys to get a rough idea of where the current state of the art in RSA cryptanalysis is.  Take into account the following table which outlines the Year and Key-size of successfully factored RSA keys (omitting keys that had been factored after a larger key in the challenge), representing the state of the art in the scope of academia:

These events can be graphed (in blue) next to their linear regression (graphed in sand) to produce the following graph:

The linear regression is as follows (for years greater than 1990):

\[ size_{rsa} = 22.1066 \left ( year \right ) - 43674.2 \]

Additionally, It is not unreasonable to assume that a state-level adversary with access to a significantly larger pool of resources than a single university would be at least a decade ahead of any academic attempts.  That line has been graphed above in red.

Rather than attempting to forecasting the future, an arguably better strategy is to select a key length that makes sense for your use case.

Your maximum security RSA key size is the largest RSA key that can be used by all of your entities (clients and servers).  Your minimum RSA key size should be a point above either the sand or red lines of the above graph, depending on who you're likely adversary is.