The RSA algorithm

RSA assumes first of all a way of translating strings of letters and other symbols into blocks of numbers and back again. We can do this using a table like the one on the right, where A corresponds to 11, B to 12, etc. Thus the word Attack! becomes 115656373947. From now on encrypting and decrypting becomes a matter of computing with large integers.

Let p and q be large prime numbers and let N = pq. Let e be a positive integer which has no factor in common with (p-1)(q-1). Let d be a positive integer such that ed - 1 is divisible by (p-1)(q-1). Let 

f(x) = xe mod N,

where a mod N means "divide N into a and take the remainder." Let 

g(x) = xd mod N,

Use f(x) for encryption, g(x) for decryption.

What makes RSA so hard to break? Well, think first about what Alice, the person who designs the code, does. First she generates the large primes p and q, then she chooses e. Finally she solves an equation to find d: 

de + (p-1)(q-1)y = 1,

where all the letters are integers. Alice makes e and N public. This is all anyone needs to send secret messages to her. Now think about what Bob, who wants to decrypt messages sent to Alice, needs to know. First he must factor N to find p and q so as to set up the equation. Then he solves the equation to find d. At this point he can decrypt Alice's messages. The problem is that the factoring problem takes huge amounts of computer time — for large enough p and q so much time that it would take millions of years, given current mathematical theory and current computer technology, to crack the code.

Conversion table

0  1  2  3  4  5  6  7  8  9
0 XX XX XX XX XX XX XX XX XX XX
1 SP A  B  C  D  E  F  G  H  I
2 J  K  L  M  N  O  P  Q  R  S
3 T  U  V  W  X  Y  Z  a  b  c
4 d  e  f  g  h  i  j  k  l  m
5 n  o  p  q  r  s  t  u  v  w
6 x  y  z  .  ,  :  ;  '  "  `
7 !  @  #  $  %  ^  &  *  -  +
8 (  )  [  ]  {  }  ?  /  <  >
9 0  1  2  3  4  5  6  7  8  9

Notes

The fact that g undoes what f does, i.e., the fact that g decrypts messages encrypted by f, is a consequence of Fermat's little theorem:

If a is not divisible by p, where p is prime, then ap-1 - 1 is divisible by p.

Fermat (1605-1661) was a French mathematician whose work is the foundation of modern number theory. See the historical references and the notes on Fermat's last theorem. Some time around 1630 Fermat wrote in the margin of his copy of Diophantus' Arithmetica that he had a wonderful proof of the fact that the equation

xn + yn = zn

has no solutions in the positive integers for n > 2. This statement was finally proved by Andrew Wiles in 1993.