The Last Theorem - Arthur Charles Clarke [86]
Slightly confused by the abrupt change in both subject and demeanor—but a little encouraged by the fact that the conversation had suddenly entered into an area he knew something about—Ranjit said, “Public-key cryptography, of course. The Diffie-Hellman-Merkle procedures.”
“Exactly,” Bledsoe said. “I don’t think I need tell you that Diffie-Hellman is in serious trouble, because of the quantum computers.”
He didn’t. Although Ranjit had never taken any particular interest in codes or code-cracking himself—not counting his exploits in learning one professor’s computer password—every mathematician in the world had a pretty good idea of what had gone on.
Diffie-Hellman was based on a very simple idea, but one that had been so difficult to execute that the idea had been useless until the age of really powerful computers. The first step in encoding any message that one wished to keep private was to represent it as a series of numbers. The simplest way to do that, of course, would be to replace the letter A with a one, the B with a two, and so on through Z equals twenty-six. (Naturally, no cryptographer in the world, or at least none over the age of ten, would take seriously such a trivial system of substitutions.) Then these numbers could be combined with an enormous number—call it “N”—in such a way that the original simple substitution was concealed. Simply adding the substituted numbers to giant N might do the trick by itself.
But N had a secret of its own. The way it was generated by cryptographers was by multiplying two large prime numbers together. Any decent computer could do that kind of multiplication in a fraction of a second, but once the two large primes were multiplied together, trying to discover what the primes themselves had been was a brutal job that, even with the best computers, could take many years. Hence the description “trapdoor cipher”—easy to get into, virtually impossible to get out of again. Still, public-key cryptography, as it was called, possessed one great virtue. Anybody could encrypt any message from the product of the primes—even, say, some harried member of the French Resistance in World War II, one step ahead of the Gestapo, with some crucial knowledge of where a bunch of panzer divisions were moving to. But only the people who knew what both those primes were could read the message.
Bledsoe took a sip of his rapidly cooling coffee. “The thing is, Subramanian,” he said, “we have some pretty important traffic going around the world right now—don’t ask me what it is. I have only a bare glimmering of a notion, and I can’t tell you even that much. But at this moment it is more important than ever that our code be unbreakable. Maybe there’s some way of decrypting that doesn’t involve all this factoring of prime numbers hocus-pocus. And if there is, we would like you to help us figure out what it is.”
Ranjit tried his best not to laugh. What he was being asked to do was what every code agency in the world had been working on ever since Diffie-Hellman had published their paper way back in 1975. “Why me?” he asked.
Bledsoe looked pleased with himself. “When I saw the news stories about your proof of Fermat’s Last Theorem, it rang a bell. All those mathematicians that work on this public-key stuff use what they call the Fermat test, right? So who would know more about that than the man who just proved his theorem? And there were others around who liked you, so we started the machinery going to recruit you for our team.”
When Ranjit considered all the ways in which Bledsoe’s notion was ridiculous, he was tempted to get up and walk away. Fermat’s test was certainly the basis for many more recent ways of identifying prime numbers. But to leap from that to the notion that the man who proved Fermat’s theorem would be any good at public-key