1 TB Encryption Key?
1 TB Encryption Key?
The RSA method has stood the test of time, and is still the most popular digital signature method for Web trust. Overall, ot has tried its hardest to keep up, and has continually expanded its prime number sizes (with a 2,048 bit public modulus now seen as being secure). Anything signed with 512-bit public modulus should definitely be defined as insecure. But quantum computing is likely to be the method that truly ends the 40-year reign of RSA.
One of the strangest papers you’ll read about RSA is from the famous Daniel J Bernstein (djb) [here]:
Daniel invented the Salsa stream encryption method [here], and also proposed Curve 25519 elliptic curve [here]. In the 1990s, he fought against US export controls for cryptography in the design of secure email and DNS services, and, in 1995, he ended up suing the US Government. Bernstein’s objective for the paper is to “Make RSA Great Again!”, and sets about testing the limits of Shor’s algorithm for RSA, and pushes it further so that a quantum computer could not crack it within a reasonable cost.
The paper
Before we start, here is an outline of the RSA method:
The PQRSA paper is rather weird. In it, the authors focus on extending the RSA method by using an exponent of just 3 (e=3), and also using a public modulus (N) which is made up of many prime numbers. The resulting key size is … wait for it … 1 Terabyte. Yes. One Terabyte.
The 1 TB key with a public exponent of 3 requires 2³¹ (2,147,483,648) 4,096-bit primes (they are extremely large by today’s standards), and which takes around 1,975,000 core-hours to compute (which is four months to generate on a 1,400 core cluster). On my Mac, I have four cores, so it would take over 20,000 days to generate a key. And then you are left scratching your head when you read that for 256GB encryption, the total time to encrypt was over 100 hours (362015 seconds) — see the table below. For decryption, a 32 GB file took over 17 hours. The N value is thus created from multiple prime numbers, and the Chinese Remainder Theorem (CRT) is then used for encryption and decryption. Their method also used 3.166TB of RAM and 2.5 TB of swap storage.
RSA … a 40-year reign
With these kinds of figures is RSA nearing the end? It seems unbelievable these days, but the original RSA method from 1977 was based on two 63-digit prime numbers that are multiplied to create a 126-digit value [here]:
Contrast this with the difficulty of finding the two prime factors of a 125- or 126-digit number obtained by multiplying two 63-digit primes. If the best algorithm known and the fastest of today’s computers were used, Rivest estimates that the running time required would be about 40 quadrillion years’
A 256-bit number, at its maximum, generates 78-digits [here]:
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936
The 40 quadrillion years has not quite happened, and where 512-bit keys are easily broken in Cloud. If you are interested, here is a 512-bit integer value and which has 148 digits, such as [example]:
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,5 92,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,9 03,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,096
The search for prime numbers, too, has been progressive since 1977, and by 2014, the world discovered a 17,425,170-digit prime number. The finding of prime numbers make the finding of them in the RSA method must easier.
So the RSA method has been under attack for years, from both discovering prime numbers and also in factorizing. Along with this computing power has increased massively. If think that 40 years that have passed, and take a quick assumption that computing power doubles every year then we get:
1977 4 Quadrillion Years (4,000,000,000,000,000)
1978 2 Quadrillion Year
1979 1 Quadrillion Year
...
2015 3,600 years
2016 1,300 years
2017 650 years
2018 325 years
and if we get an NVIDIA card with 4,000 processors, we take it to less than a year, and we get of few of them today into a cluster, and we crack it within one day! The FREAK vulnerability was actually caused by the limiting of RSA keys, due to US Export controls, to 512-bits [view].
The factorising of prime numbers too has generated methods which can quickly find the prime number factors [here].
Conclusions
The objective of Bernstein is to “Make RSA Great Again!”, and he hopes to rely on Moore’s Law on make 1TB seem like 1MB is today, and that 3.166TB of RAM will be like 16GB of memory. He also thinks that many of the proposed methods for quantum computing robust crypto might be cracked, and that RSA is at least better than QKD (Quantum Key Distribution).
But I may have missed something with this paper, but there are better quantum robust out there that do not require us to keep scaling RSA. A key size of 1TB just seems unmanageable, and we need to break our dependency on it. Newer methods create relatively small key sizes, and are likely to be robust against quantum methods.
So what’s the alterative? Well, the Post Quantum Cryptography (PQC) is looking to replace RSA for both public key encryption (PKE) and digital signing (DS):
This move to PQC for PKE and DS is likely towards CRYSTALS-Dilithium, Falcon and SPHINCS+. While, for key exchange, PQC is looking to replace our reliance on ECC (Elliptic Curve Cryptography). Currentl the main method for this is CRYSTALS-Kyber.
Reference
Bernstein, D. J., Heninger, N., Lou, P., & Valenta, L. (2017, June). Post-quantum RSA. In International Workshop on Post-Quantum Cryptography (pp. 311–329). Springer, Cham.