Cryptography · Chapter 2 of 3
Easy Forwards, Hard Backwards
On a gap between two costs, and the fact that nobody has proved it is there.
2 min read
Multiply 2,038,074,743 by 1,000,003. Tedious, and a few seconds of work.
Now take 2,038,296,955,236,229 and find the two primes that multiply to make it. Same two numbers, same arithmetic, and the only known approach is to look. Make the numbers a few hundred digits long and multiplying stays instant while finding the factors would occupy every computer that exists for longer than the universe has run.
That gap between the forward cost and the backward cost is what encryption is made of.
A function that is cheap forwards and expensive backwards is called one-way, and the honest thing to say about one-way functions is that they are believed to exist. Nobody has proved it. If it turned out that no function has this property, cryptography as a field would end, and not gradually.
Factoring is the standard example because it is the clearest. Multiplying is a procedure; factoring is a search. But notice precisely what is being claimed.
The claim is not that factoring is impossible. It is that no efficient method has been found, after fifty years of serious, well-funded, mathematically sophisticated attempts. There is no theorem saying a fast method cannot exist. It might be published next year by someone who has had a good idea.
This is a weaker foundation than most people assume when they see a padlock in a browser, and it is a stronger one than that sentence makes it sound.
Weaker, because the word unbreakable is doing work it has not earned. The system rests on an open problem. If the problem is solved, the system fails everywhere at once, retroactively, including for every message anybody recorded and kept.
Stronger, because decades of attempts by very capable people with large budgets and strong incentives, all failing, is real evidence about how hard something is. It is the same evidence a lock has. Nobody has proved a lock cannot be picked; a great many people have tried to pick that model and not managed it.
The hardness is tied to the biggest open question in computer science, whether P equals NP, which asks roughly whether every problem whose answers are easy to check is also easy to solve. Factoring has answers that are trivial to check: multiply the factors and see. If checking and solving are the same thing in general, the gap this chapter is about does not exist.
There is one known way to collapse the gap, and it is being built.
Shor's algorithm factors efficiently on a quantum computer. The machines that exist are nowhere near large enough, and the mathematics is not in doubt: if a sufficiently large one is made, every system in this chapter fails. Standards bodies have been migrating for years to problems believed hard for quantum machines too, which is the right response and tells you what kind of claim the original one was. The bet is being re-placed. It is not being replaced with a certainty, because there is not one available.
The security is not that nobody can undo it. It is that nobody has worked out how, and people have been trying for fifty years.
Where you'll meet this
A large enough quantum computer would factor efficiently using Shor's algorithm, which is why standards bodies are already migrating to problems believed hard for quantum machines too. The bet is being re-placed, not abandoned.