Prime-factor mathematical foundations of RSA cryptography ‘broken’, claims cryptographer

Not so fast on those ‘fast factoring’ boasts

Claims by a respected German mathematician that the widely used RSA algorithm has been cracked by an advance in cryptoanalysis have received a respectful but cautious response.

One-way functions that form the basis of most cryptographic algorithms rely for their security on the difficulty of solving some problems even with access to a powerful computer. The security of RSA, for example, relies on the difficulty of factoring the product of two large prime numbers.

Other types of cryptography use the mathematics of elliptic curves to create a one-way function that is impractical to unravel except through a brute force attack that involves trying every possible key.

‘Shortest vector’

A paper from mathematician and cryptographer Claus Schnorr claims that prime factorization can be reduced to a much less intractable ‘shortest vector’ problem.

The abstract to the paper (PDF), entitled ‘Fast Factoring Integers by SVP Algorithms’, claims that this process “destroys the RSA cryptosystem”.

If verified, the technique would work even if longer key values were deployed. Increasing the key length is the standard response to making sure algorithms stay ahead of advances in computing technology.

If true, a great number of secure systems that rely on RSA would become insecure or at least vulnerable to a previously well defended vector of attack.

Catch up with the latest encryption news

The finding is yet to comprehensively demonstrated much less proved, and cautious interest rather than alarm was the general reaction from cryptoanalysis-savvy social media users.

Cryptographer Matthew Green commented on Twitter: “I think the general consensus (paraphrasing a few things people have said) is that this is an exciting approach that unfortunately has no practical evidence of efficacy, and the association of a particular researcher’s name with it should not be viewed as changing any of that.”

Professor Alan Woodward, a computer scientist at the University of Surrey, told The Daily Swig that the paper deserves “careful consideration”.

“I don’t believe the paper proves the claims made about RSA but that doesn’t mean the idea is fundamentally wrong,” he added.