Without a doubt, this week has been interesting from a cryptography aspect. On 3rd March, German cryptographer and mathematician Claus Peter Schnorr published a paper, titled „Factoring Integers by CVP and SVP Algorithms” which title in itself is not only interesting, but essentially bad news from a CA viewpoint. Even worse, that the abstract contains a sentence such as „This destroys the RSA cryptosystem”. But has RSA been in fact destroyed? Very possibly not.

As we look at this, it is a very harsh claim; there are methods that can be used to break plain RSA, such as the Håstad attack and Coppersmith’s attack. Note that these only work without proper padding and with insufficent parameters (i.e. the public exponent e=3). But for going against proper RSA, one’s best bet is to factor large numbers, for which, there is no currently known method; this paper claims this is not the case anymore.  

As a PKI expert and not a mathematican, my first thought was „OK, how large are we talking about?”. The abstract states that „These new algorithms factor integers N≈2⁴⁰⁰ and N≈2⁸⁰⁰ using 7·10¹⁰ and 4.3·10¹² arithmetic operations, much faster then the quadratic sieve QS and the number field sieve NFS”. This is far from real-world RSA implementations as they are mostly 2048 and 4096 bit ones. The other thought that arose was that if this works in practice as well, why not include the factoring of some challenges, from which there are quite a lot available?

Several experts have pointed out flaws in the paper since, one of the most critical ones is an issue of the R_n,f matrix determinant which is bounded as Nⁿ⁺¹ (n(n+1))/2 N, instead of Nⁿ⁺¹ n! ln N. This may result in high inaccuracy of the numerical estimates as several suggested.

Also, there quickly became a practical Sage implementation of the theory, made by Leo Ducas, who is one of the top experts in lattice-based cryptography. The GitHub repository is available at the following link to try and test the theory yourself:

https://github.com/lducas/SchnorrGate

Ducas’ findings are that in several tests, using b as the to-be-factored numbers’ bit size, n as the factor basis’ number of elements and t as the trial time, some results are:

Running b=10, n=47, t=1000, we obtained 353 Factoring Relation found out of 1000 trials.
Running b=20, n=47, t=1000, we obtained 65 Factoring Relation found out of 1000 trials.
Running b=40, n=47, t=1000, we obtained 0 Factoring Relation found out of 1000 trials.

This implies „that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21]”. Our team has ran some tests as well using the script, and also came to similar results. It is to be also noted that the tested bitsizes are still small, and for small bitsizes, various attack methods already exist.

Summarized, Schnorr’s findings are not likely to break RSA with the current widely-used parameters (there is a new version dated 4th March, where the part about breaking the RSA system is not included), however, they serve as a warning to remember that cryptographic algorithms - no matter how strong they seem - are not meant to be used forever. If one really wants to make sure to have really secure cryptographic basis regarding their certificates, a precaution may be to upgrade to ECC-based solutions.