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.