Understanding Cryptographic Algorithms: ECC vs RSA

According to records, the ancient Greeks invented substitution ciphers around 400 BC. The world’s first telephone secrecy patent appeared in 1881. During World War II, the German military used the “Enigma” cipher machine, and cryptography played a very important role in the war. With the development of information and digital society, people’s awareness of the importance of information security and confidentiality has continuously increased. Therefore, in 1997, the National Institute of Standards and Technology (NIST) of the United States announced the implementation of the “Data Encryption Standard (DES)”. Civil forces began to fully engage in the research and application of cryptography, using encryption algorithms such as DES, RSA, SHA, etc. With the increasing demand for encryption strength, new algorithms like AES and ECC have emerged recently.

Using cryptography can achieve the following purposes:

Modern cryptography can be divided into two categories based on the type of key: Symmetric Encryption Algorithms and Asymmetric Encryption Algorithms. Symmetric key encryption systems use the same secret key for both encryption and decryption, and both parties must obtain this key and keep it secret. (This article will not elaborate further on this.)

The asymmetric key encryption system uses different keys for encryption (public key) and decryption (private key).

Common asymmetric encryption algorithms are as follows:

In 1976, due to the inadequacy of symmetric encryption algorithms, Diffie and Hellman published an article titled “New Directions in Cryptography,” introducing the concept of public key encryption, and Rivest, Shamir, and Adleman proposed the RSA algorithm. RSA is formed by combining the initials of their last names.

With advancements in methods for factoring large integers, improvements in computer speed, and the development of computer networks, to ensure data security, the key size for RSA needs to continuously increase. However, the increase in key length significantly reduces the speed of encryption and decryption, and hardware implementation becomes increasingly burdensome, which poses a heavy load on applications using RSA. Therefore, a new algorithm is needed to replace RSA.

In 1985, N. Koblitz and Miller proposed using elliptic curves for cryptographic algorithms, known as Elliptic Curve Cryptography (ECC), based on the discrete logarithm problem over points on elliptic curves in finite fields (ECDLP). ECDLP is a problem that is harder than the factorization problem and has exponential difficulty.

Currently, SSL certificates commonly use the RSA algorithm. Due to the shortcomings of the RSA algorithm mentioned above, the development of using ECC as its public key algorithm for digital certificates has also gained significant attention in recent years: around 2008, CAs began to reserve ECC root certificates; around 2012, CAs began to publicly sell ECC certificates; in 2014, ECC certificates were widely used abroad; and in 2015, ECC certificates began to be accepted domestically.

Compared to RSA, ECC has absolute advantages in many aspects, mainly reflected in the following areas:

As the security level increases, the current encryption algorithm’s key length will also increase exponentially, while the ECC key length only increases linearly. For example, a 128-bit secure encryption requires a 3,072-bit RSA key but only a 256-bit ECC key. Increasing to 256-bit secure encryption requires a 15,360-bit RSA key but only a 512-bit ECC key. ECC has such outstanding bit-to-bit encryption performance that its features are expected to become the focus of security systems.

Having discussed so much, we now focus on testing the performance differences between the two algorithms. Warning: Multiple images ahead:

4.1 Server Performance Metrics

The tests were conducted on two major cloud hosts. In this test case, two different authentication algorithms were used:

We see that the ECC-256 hierarchy outperforms RSA-2048 and RSA-3072

4.2 Comparison of Response Time and Throughput Metrics

The entries in the table below and the following sections detail the tests we conducted for the cloud hosts: The test “0K GET, 0% reuse” runs on an XLarge server for Apache and IIS web servers, with session reuse at 0%, meaning each SSL handshake is a complete handshake rather than a simplified handshake. It should also be noted that 0K files do not represent an empty load; there are still HTTP headers transmitted during the process.

Test cases and scenarios

With a session reuse of 0%, indicating each handshake is a complete handshake, involving the required CPU processing, we have found that the cloud host running Apache experienced CPU saturation limits, with RSA-3072 around 500 requests/second; RSA-2048 around 1300, while ECC-256 has been confirmed to present strong adaptability at around 2800 requests. Importantly, ECC-256 can adapt to a significantly high number of transactions. Although the data points behind Apache and IIS (such as those in throughput and wait time) are completely different, the conclusion drawn is the same and favors ECC-256. Note that ECC-256 is equally secure as RSA-3072, but the efficiency can differ greatly.

The reason for hosting web servers on cloud hosts is to reduce the required number of clients so that the server can maximize CPU utilization. The results trend the same as “0K GET, 0% reuse”.

The result of a session reuse of 68% indicates that two-thirds of the handshakes were simplified. Compared to previous tests, the average response time decreased while throughput increased, narrowing the saturation gap between the three. If the percentage of reuse increases and is plotted, we can see the gap narrowing.

An interesting phenomenon is that in the case of Apache, we observed that ECC-256 and RSA-2048 began to saturate network transmission, while RSA-3072 reached CPU utilization limits. For IIS, all three reached CPU utilization limits.

The characteristics of ECC will inevitably lead to its replacement of RSA as the universal public key encryption algorithm. For example, the creators of the SET protocol have adopted it as the default public key cryptographic algorithm in the next generation of the SET protocol.

ECC certificate compatibility: