Steps occur when you enter your credit card number online
RSA - Rivest, Adi Shamir,
and Leonard Adleman,
This idea firstly came to the scientist named Pierre Fermat.
Prime Numbers 1 , 3, 5, ... play a major and important key role in our lives knowing or unknowingly.
I can tell something’s up when random
people start asking me about the randomness
of primes—without even knowing that I’m a mathematician! In the past couple
of weeks we’ve heard about a beautiful result on the gaps
between primes and about cicadas’ prime-numbered life cycles.
Our
current love affair with primes notwithstanding, many people have wondered
whether this is all just abstract theoretical stuff or whether prime numbers
have real-world applications.
In
fact, they have applications to something as ubiquitous and mundane as making a
purchase online.
Every
time you enter your credit card number on the Internet, prime numbers spring
into action. Before your card number is sent over the wires, it must be
encrypted for security, and once it’s received by the merchant, it must be
decrypted.
One
of the most common encryption schemes, the RSA algorithm, is based on prime
numbers. It uses a “public key,” information that is publicly available, and a
“private key,” something that only the decoding party (merchant) has. Roughly
speaking, the public key consists of a large number that is the product of two
primes, and the private key consists of those two primes themselves. It’s very
difficult to factor a given large number into primes. For example, it took
researchers two years recently to factor a 232-digit number, even with hundreds of parallel
computers. That’s why the RSA algorithm is so effective.
Definition: Prime
numbers are whole numbers greater than 1 that are not divisible by any whole
number other than 1 and itself. The first few are 2, 3, 5, 7, 11, 13 …
To
explain how the RSA algorithm works, I need to tell you first about something
called Fermat’s little theorem. It was discovered by Pierre Fermat, the same
French mathematician who came up with the famous Fermat’s
last theorem.
Fermat had a penchant for being cryptic; in the case of his
last theorem, he left a note on the margin of a book stating his theorem and
adding: “I have discovered a truly marvelous proof of this, which this margin
is too narrow to contain.” Call it the 17th-century version of a
Twitter proof. Many professional mathematicians and amateurs tried to reproduce
Fermat’s purported proof, and it took more than 350 years to come up with a real one.
About Andrew Wiles in the next post
To
understand what Fermat’s little theorem means, we need to learn how to do
arithmetic “modulo N.” This is something, in fact, we do all the time when adding
angles. If you rotate an object by 180 degrees, and then by another 270
degrees, the net result will be rotation by 90 degrees.
That’s because 180 +
270 = 450, and then we subtract 360 from it, because rotation by 360 degrees
means no net rotation at all. This is what mathematicians call addition “modulo
360.” Likewise, we can do addition modulo any whole number N instead of 360.
And we can also do multiplication modulo N.
Now
suppose that N is a prime number. Then we have the following remarkable fact:
Raising any number to the Nth power modulo N, we get back
that same number. For example, if N = 5, then the 5th power of 1 is
1 and the 5th power of 2 is 32, which is equal to 2 modulo 5 because
after you subtract the closest multiple of 5 (in this case, you subtract 30, or
5 × 6), you are left with 2 (because 32 = 5 × 6 + 2). Likewise, the 5th
power of 3 is equal to 3 modulo 5, and so on. This is Fermat's little theorem.
Fermat first divulged it in a letter to a friend. “I would send you a proof of
it,” he wrote, “but I am afraid it’s too long.” He was such a tease, this
Fermat. Unlike the proof of his last theorem, however, the proof of the little
one is surprisingly simple—it could even fit in the margin of a book. I would
write it here, but my editor tells me that my article is already too long.
No
worries though, you can read the proof in this
excerpt from my book Love and Math.
This
is neat, but what does it have to with Internet security?
We
need to devise a two-step procedure:
First
encrypt a credit card number and then decrypt it, so that if we follow both steps
we get back the original number. The good news from Fermat’s little theorem is
that raising a card number to a prime power modulo that prime is a procedure
that gives us back the original number. The bad news is that because a prime is
not divisible by anything, there is no way to break this procedure into two
steps. However, Ron Rivest, Adi Shamir,
and Leonard Adleman, after whom the RSA algorithm is named, were not
discouraged. They took Fermat’s idea one step further. They asked: What if we
take N which is the product of two primes—call them p and q.
Then we have the following analogue of Fermat’s little theorem:
Raising
any number to the power (p – 1)(q – 1) + 1 will give us back
the same number modulo N. For example, N = 15 is the product of p = 3
and q = 5. Then (p – 1)(q – 1) + 1 = (3 – 1)(5 – 1)
+ 1 = 9. If you raise any number to the 9th power, you get back the
same number modulo 15. It looks like a miracle, but in fact the proof is
no more complicated than that of Fermat’s little theorem.
And
now we can use it for encryption: For the given prime numbers p and q,
the combination (p – 1)(q – 1) + 1 will typically be a number
that is not a prime. Hence it can be represented as the product of two whole
numbers, call them r and s. (In our example, (p –
1)(q – 1) + 1 = 9, so we can take r = 3 and s = 3.)
Raising a number to the power (p – 1)(q – 1) + 1 can now be
broken into two steps: raising it to the rth power and then
raising it to the sth power.
Here’s
how it works in practice: The merchant picks two large prime numbers p
and q (there are various algorithms for generating
primes), takes their product N, and chooses r and s. He
or she then makes r and N known to everyone; this is the public key.
The encryption consists of raising a credit card number to the rth
power modulo N. Anyone can do it (on a computer, because the numbers involved
are quite large).
The
decryption, on the other hand, consists of raising the resulting number to the sth
power modulo N. This gives back the original credit card number (see here for
more details). The merchant keeps the number s secret. Therefore
the transmission of the credit card numbers is secure. The only way to find s,
and hence to be able to decrypt the card numbers, is to determine the prime
factors p and q of the number N. For sufficiently large N,
however, using known methods of prime factorization, it may take many months to find p and q,
even on a network of powerful computers. But if one could come up with a more
efficient way to factor numbers into primes (for example, by using a quantum computer), then one would have a tool for breaking
the RSA algorithm. That’s why a lot of research is directed toward factoring
numbers into primes. Scores of legitimate mathematicians are working on this,
and perhaps not so legitimate ones as well.
To
an outsider, the RSA algorithm appears like a card trick: You pick a card from
a stack, hide it (this is like encryption), and after some manipulations the
magician produces your card—adbraka! Well, that's pretty much what the RSA
algorithm does … except that the role of magic is now played by math.
