Your public key, please3 min read . Updated: 27 Oct 2011, 10:43 PM IST
Your public key, please
Your public key, please
I’ll go out on a limb and guess that you were once a kid. More, that when you were that kid, you loved babbling in the “p" language. You know, insert the letter “p" into every spoken syllable and exult, because only you, your best friend and about a billion other kids know what you’re saying.
Example: “Thipis ipis sopo stupupipid."
It’s a code, of course. All kids love codes. So do many adults, especially during wars, when they need to pass information in ways that enemies cannot understand. Though during wars, as you might guess, the “p" language falls some way short of being acceptable. Why? Not because it looks stupid, but because it is far too easily “cracked".
Also read |Dilip D’Souza’s previous columns
The business of encoding information securely is called cryptography, a scientific pursuit that must be nearly as old as recorded history. For much of that time, cryptography was essentially about secret keys. You use the key—example, “insert p into each syllable"—to encode your message, and then you send the coded message. Your recipient uses the same key to decode your message.
So what’s to be done?
Came the 1970s, and this revolutionary idea: forget about secrecy. Three scientists at MIT—Ron Rivest, Adi Shamir and Leonard Adleman—proposed what’s now called public key cryptography. This was undoubtedly the single most influential step forward the field has seen, and won them computer science’s greatest prize, the Turing Award. At its root, no surprise, is a simple mathematical idea: some operations are much easier when performed in one direction than the other.
For example, it’s easy to multiply 7, 11 and 13 to get 1001. But what if I asked: “Which three numbers, when multiplied, produce 1001?" Answering that is harder, and takes longer (try it). With numbers much larger than 1001, the time difference becomes significant; reversing such “one-way functions" takes so long that they are effectively impossible to solve.
So imagine two prime numbers, each 100 digits long. A computer can quickly multiply them to produce a number about 200 digits long. But given that 200-digit number, how long will it take to find the 100-digit factors? Probably at least several hours. With even larger primes, we’re talking weeks, months, years: effectively impossible. Use more powerful computers, you say? Well, as Euclid showed (see my last column), there’s an endless supply of primes, so all we need to do is to move on to larger ones. 500 digits, why not?
So public key systems work something like this. Ramdulari, who wants to receive coded messages, picks two large prime numbers and multiplies them. With some further calculations, she produces two more numbers. She announces to an expectant world her personal public key: the product, and one of these two. The other number is Ramdulari’s private key.
Nijalingappa decides to send Ramdulari a message. He encrypts it with a formula that uses her public key. When Ramdulari receives the coded message, she uses her private key in another formula that restores Nijalingappa’s original.
Of course, Ramdulari never reveals her original pair of primes.
In theory, this is not a safe procedure. Given an indefinite amount of time, code breaker Pappu could take Ramdulari’s public key, calculate the two prime factors and thus crack the code. But Pappu doesn’t have that kind of time. Long before he found the primes, he’d be pushing up the rajnigandha. So Ramdulari’s key is secure, as is Nijalingappa’s message.
There are some wrinkles to all this, of course. But the algorithm is so conceptually simple that it opened to all the possibility of cheap, yet secure, communication. (It’s what commercial transactions on the Web use, for example).
Naturally, this was anathema to governments that long to eavesdrop on what their citizens say to one other. In the ’90s, the US government’s discomfort over public key cryptography led them to propose an encryption system based on their own secret algorithm, called Skipjack.
And, naturally, this secrecy was anathema to cryptographers. Their outrage persuaded the US government to declassify Skipjack on 24 June 1998. And it’s a delicious aside to this story that two researchers promptly decoded Skipjack itself, and one of those two was Shamir, and they published their findings on 25 June 1998. One day later.
Meanwhile, I have here two 100-digit primes to multiply. One is 4900776548933884091718415095552836172318990178782311114790623710293015928042243863388836910016337832. Hmm, where did the other one go?
Once a computer scientist, Dilip D’Souza now lives in Mumbai and writes for his dinners. A Matter of Numbers will explore the joy of mathematics, with occasional forays into other sciences. Comments are welcome at firstname.lastname@example.org