Breaking RSA’s Hegemony: Elliptic Curve Cryptography in GPG’s New Defaults

Sefik Serengil

In the world of cryptography, few algorithms have held as much dominance and trust as RSA. For decades, RSA (Rivest-Shamir-Adleman) has been the cornerstone of public-key cryptography, powering everything from digital signatures to secure communications. However, as the digital landscape evolves and computational power increases, RSA’s once-unassailable position is now being challenged.

The recent version of GPG (GNU Privacy Guard) has made a significant shift by adopting elliptic curve-based algorithms as the default—specifically, ECDH (Elliptic Curve Diffie-Hellman) for encryption and EdDSA (Edwards-curve Digital Signature Algorithm) for signatures. Actually, GPG has supported elliptic curve cryptography (ECC) since version 2.1, but starting with version 2.3, it began generating ECC key pairs by default. This change marks the end of RSA’s hegemony, as elliptic curve cryptography (ECC) promises the same security level with much greater efficiency.

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

Public Key Cryptography From Scratch

While RSA’s mathematical simplicity made it easy to understand, and its ability to use the same algorithm for both encryption and digital signatures are its key advantages. However, its real-world implementation is computationally expensive. On the other hand, ECC—though more complex to grasp for humans—runs much more efficiently on modern computers, offering smaller keys and faster computations without compromising security.

ECC is the new default of GPG

This blog post will dive into the technical reasons behind GPG’s shift, exploring how ECC works, the advantages it offers over RSA, and why it is the future of cryptography.

The Shift from RSA to ECC in GPG

For decades, RSA has been the go-to algorithm for securing digital communications and verifying signatures. One of the reasons for its widespread adoption is the simplicity of its underlying math. RSA relies on the difficulty of factoring large numbers as the basis for its security—an idea that is relatively easy to understand at a high level.

However, this simplicity comes at a cost. RSA’s security is directly tied to key size; the larger the key, the more secure the algorithm. But as computational power has increased over time, so has the required key size. For example, to achieve a comparable level of security to a 256-bit ECC key, an RSA key would need to be 3072 bits or larger, making RSA computationally expensive and slower.

This computational bottleneck has become more pronounced as modern systems, mobile devices, and IoT devices demand more efficient cryptographic solutions. Additionally, RSA’s signature and encryption operations consume more energy, which becomes an issue for battery-powered devices.

Encryption

ECDH is actually a key exchange algorithm, meaning its primary purpose is to securely establish a shared secret between two parties. Even though ECDH requires computation by both parties (Alice and Bob), GPG manages this process seamlessly in the background. It ensures that both parties can securely establish a shared secret and use it for encrypting messages, all while providing the efficiency and security benefits of elliptic curve cryptography (ECC).

Key Generation

In the ECDH (Elliptic Curve Diffie-Hellman) key exchange protocol, both Alice and Bob generate their own private and public keys based on elliptic curve mathematics.

  • Alice’s private key: da – a random integer
  • Bob’s private key: db – a random integer
  • G: a predefined public point on a public elliptic curve E

Curves

GPG is using Curve 25519 as default where E is



-x2 + y2 = 1 – (121665/121666) x2y2 (mod 2255 – 19)

Here, name 25519 is coming from the prime modulus.

Using Edwards curves is not mandatory. For instance, GPG also supports NIST curves, which are defined using the Weierstrass form of elliptic curves. Essentially, an elliptic curve E is just a mathematical equation.

The multiplier of x2y2 in Curve 5519 is a fractional value, but the equation is defined over integers due to the modulus operation. To handle this, the denominator 121666 is moved to the numerator by finding its multiplicative inverse modulo 2255 – 19. However, this results in a very large number, which can appear unwieldy. For simplicity and clarity, many tutorials prefer to represent the equation using the division constant instead.

Secondly, the base point G of Curve 25519 is a pre-defined value

G = (
   15112221349535400772501151409588531511454012693041857206046113283949847762202,
   46316835694926478169428394003475163141307993866256225615783033603165251855960
)

Calculating Public Keys

Using their respective private keys, Alice and Bob compute their public keys:

  • Alice’s public key: Qa = da x G
  • Bob’s public key: Qb = db x G

In the calculation Qa = da x G, it’s important to note that G is a point on the elliptic curve, represented by its x and y coordinates. This might be confusing at first, as it seems like a simple multiplication of a scalar and a point.

However, this operation is actually a scalar multiplication on the elliptic curve, which involves adding the point G to itself multiple times. To compute da x G, we use the addition law of elliptic curves. This law defines how two points on the curve can be added together to produce another point, and by repeating this addition process, we can multiply the point G by the scalar da.

In summary, Qa is another point on the elliptic curve. If you wonder how that calculation is performed, check out these posts:

  • The math of the addition law of elliptic curves in Weierstrass form, Koblitz form, Edwards form, Twisted Edwards form.
  • Once you have the addition and doubling formulas for given elliptic curve form, you can calculate the da x G for given k and G easily with the double and add method.
  • On the other hand, restoring da from given Qa and G is a hard problem. Notice that the both Qa was the public key of Alice and G was the pre-defined public point, but da was the private key of Alice and it was not public.

Alice’s Side

Let’s say Alice wants to send a secure, encrypted message to Bob using ECDH for encryption. Even though ECDH is primarily a key exchange algorithm, the shared secret derived from it is used for encryption.



  • Alice generates a random AES key (let’s call it K), which will be used to encrypt the message she wants to send to Bob.
  • Alice encrypts the message with the randomly generated AES key (let’s call this Cm).
  • Alice computes a shared secret using her private key da and Bob’s public key Qb. This shared secret will act as a key to encrypt the AES key. Alice computes: Sa = da x Qb.
  • Alice encrypts the random AES key K using the shared secret Sa (let’s call this Ck). This encrypted AES key is sent along with the encrypted message and her public key to Bob.

In summary, Alice sends this tuple to Bob: (Cm, Ck, Qb)

Bob’s Side

  • When Bob receives Alice’s encrypted message, encrypted AES key and Alice’s public key, he uses his private key db and Alice’s public key Qa to compute his own shared secret: Sb = db x Qa.
  • Since ECDH ensures that Sa and Sb are identical (because of the mathematical properties of elliptic curves), Bob now has the same shared secret that Alice used to encrypt the AES key. He uses this shared secret to decrypt the AES key.
  • Once Bob has the AES key K, he can use it to decrypt the original message that Alice sent.

The New Signature Algorithms

In addition to ECDH, GPG’s shift also introduces elliptic curve-based signature algorithms, namely ECDSA (Elliptic Curve Digital Signature Algorithm) and EdDSA (Edwards-curve Digital Signature Algorithm). Both of these signature schemes are based on elliptic curve cryptography, providing the same security as RSA but with better performance.

  • ECDSA: ECDSA has been widely adopted for digital signatures in systems like Bitcoin and TLS/SSL. While it offers strong security, it has certain performance limitations, such as susceptibility to side-channel attacks.
  • EdDSA: EdDSA is a more modern, secure, and efficient algorithm compared to ECDSA. It provides better resistance to side-channel attacks, and it’s designed for high performance in both hardware and software. GPG’s decision to adopt EdDSA as one of its default signature algorithms enhances the security and performance of the system.

Conclusion

The decision to move towards ECDH and EdDSA as defaults in GPG marks a critical evolution in cryptographic practices. By embracing Elliptic Curve Cryptography, GPG has not only improved performance but also aligned itself with modern cryptographic standards that offer greater security and efficiency.

While RSA has served us well for decades, its limitations in the face of increasing computational power make it less suited for future-proofing our cryptographic systems. The transition to ECC and its derivatives like ECDH and EdDSA ensures that GPG remains a relevant and secure solution in the ever-changing landscape of digital communication and data privacy.

As we continue to move towards a more interconnected world, where speed, efficiency, and security are paramount, ECC-based cryptography will be at the forefront of ensuring that our communications remain private, safe, and efficient.

Support this blog if you do like!

Buy me a coffee      Buy me a coffee