Digital security depends on the difficulty of factoring large numbers.
A new proof shows why one method for breaking digital encryption won’t work.
“… it’s nearly impossible to find polynomials of that length that can be factored” (*) (**)
(*) ‘nearly’ (**) with today’s computers – not tomorrow’s QC
by Hannah Li
My recent story for Quanta explained a newly proved phenomenon that might seem surprising from a naive perspective: Virtually all polynomials of a certain type are “prime,” meaning they can’t be factored.
The proof has implications for many areas of pure mathematics. It’s also great news for a pillar of modern life: digital encryption.
The main technique we use to keep digital information secure is RSA encryption. It’s a souped-up version of the encryption scheme a seventh grader might devise to pass messages to a friend: Assign a number to every letter and multiply by some secretly agreed-upon key. To decode a message, just divide by the secret key.
RSA encryption works in a similar fashion. In simplified form, it goes like this: A user starts with a message and performs arithmetic on it that involves multiplication by a very large number (hundreds of digits long). The only way to decode the message is to find the prime factors of the resulting product. The security of RSA encryption rests on the fact that there’s no fast way to identify the prime factors of very large numbers. If you’re not the intended recipient of a message — and if you therefore lack the right key to decode it — you could search for a thousand years with the best computers and still not find the right prime factors.
But there is a back door, and it has to do with polynomial equations. Every number can be represented as a unique polynomial equation. While it’s hard to find the prime factors of a number, it’s easy to find the factors of a polynomial. And once you know the factors of a polynomial, you can use that information to find the prime factors of the number you started with.
Here’s how it works.
Step One: Pick a number whose prime factors you’d like to know. To take a simple example, let’s use the number 15.
Step Two: Convert 15 into binary notation:
1111.
Step Three: Turn that binary expression into a polynomial by treating the binary digits as coefficients of a polynomial:
x3 + x2 + x + 1.
(Note that this polynomial equals 15 when x = 2, because 2 is the base of binary notation.)
Step Four: Factor the polynomial:
(x2 + 1) × (x + 1).
Step Five: Plug x = 2 into each of those factors:
(22 + 1) = 5
(2 + 1) = 3.
Conclusion: 5 and 3 are the prime factors of 15.
This seems like a complicated way to find the prime factors of a small number like 15, whose factors are easy to spot straightaway. But with very large numbers — numbers with hundreds of digits — this polynomial method gives you a remarkable advantage. There’s no fast algorithm for factoring large numbers. But there are fast algorithms for factoring large polynomials. So once you convert your large number to a large polynomial, you’re very close to finding the number’s prime factors.
Does this mean RSA encryption is in trouble? Actually, no. The reason for this has to do with the new proof about polynomials. The mathematicians Emmanuel Breuillard and Péter Varjú of the University of Cambridge proved that as polynomials with only 0 and 1 as coefficients get longer, they’re less and less likely to be factorable at all. And if a polynomial can’t be factored, it can’t be used to identify the prime factors of the number it’s based on.
Breuillard and Varjú’s proof effectively slams shut the polynomial back door for breaking RSA encryption. The very large numbers used in RSA encryption correspond to very long polynomials. Breuillard and Varjú proved that it’s nearly impossible to find polynomials of that length that can be factored. Mathematicians and cryptographers alike have long suspected this is the case. But when the cybersecurity of the entire world depends on some mathematical hack not working, it’s good to have proof that it doesn’t.
from: https://www.quantamagazine.org/mathematicians-seal-back-door-to-breaking-rsa-encryption-20181217/