Assignment 20: Theodore

How to Create an Unbreakable Code

Suppose that a modern-day Romeo wants to express his feelings to Juliet. Unfortunately, he can’t meet her in person; he must send her an email. Worse, her evil cousin Tybalt has hacked into the Internet connection and is reading every email sent to and from Juliet. He’s too clever to be fooled by a message written backwards: “uoy evol I.” To thwart Tybalt, Romeo needs an unbreakable code. Here’s the problem: He and Juliet can’t set up a secret key for the code because Tybalt would read that email.

    But Romeo has a secret weapon: He and Juliet are both math majors, so they know about a code that doesn’t need a private key. It’s called RSA; every credit card, spy agency, and encrypted email in the world uses it. Here’s how they establish secure communications:

1. Romeo informs Juliet that she is going to receive a message. Meanwhile, Romeo composes a romantic message: “Did my heart love till now? Forswear it, sight!”

2. Juliet chooses two prime numbers at random called P and Q. A prime number is only evenly divisible by itself and 1. Suppose that Juliet chooses 41 and 53. She multiplies P and Q to get N, which is 2173.

3. Juliet calculates M, which is (P-1)*(Q-1), or 2080. In case you’re wondering, M is the number of integers less than N that share no factors with N.

4. To compete the preparation, Juliet chooses a random integer E — the encoding number — that is less than M. In this case, E is 957. She checks that E shares no factors with M. Using Euclid’s algorithm, she finds D — the decoding number — which is the integer less than M such that D*E-1 is divisible by M. Her computer easily calculates that D is 213. Juliet will keep P, Q, M, and D secret from everyone.

5. Juliet emails E=957 and N=2173 to Romeo. However, Tybalt intercepts the message and also learns the values of E and N.

6. Romeo translates his message into a list of numbers. This step is not difficult; all computers have a standardized table connecting letters and numbers. For instance, consider the phrase “Did my heart love till now?” The word “Did” becomes 68, 105, 100. (The capital and lowercase d correspond to different numbers.) Romeo calls the first number R, so R=68. Anyone who knows 68 can instantaneously translate it back into “D.”

7. Romeo encodes each number in the list using the formula   . What does this mean? X is the encoded version of R. “Mod N” just means divide by N and find the remainder. For the first letter of the message, Romeo tells his computer to compute , which is 1531. Thus, X=1531.

8. Romeo encodes the rest of the message likewise, letting each number in the list be R. 

9. Romeo sends the encoded number to Juliet. The first few numbers are 1531, 2013, 1636. Tybalt will also receive the encoded message, but he will not be able to decode it. While computers can easily raise numbers to powers, reversing the process is time-consuming. Tybalt needs to test every possible letter in order to guess that 1531 is an encoded version of “D.” This task becomes impossible if Romeo encoded blocks of letters; Tybalt cannot test each of the trillions of combinations.

10. But how does Juliet decode the message? She has an advantage that Tybalt lacks: Only she knows the secret decoding number D. If Juliet evaluates , the result is R — the original number Romeo wanted to send her. For instance, is indeed 68. This decoding formula relies on the work of Euler and Fermat, two mathematicians who died hundreds of years before the invention of computers and RSA. Juliet can easily decode the rest of the message and translate the numbers back to letters: “Did my heart love till now? Forswear it, sight!”

 RSA is magical. Juliet can tell anyone to how to encode messages to her, but only she knows how to decode them. If Tybalt wants to find the decoding number D, he first needs to know M, P, and Q. However, it is far from easy to factor N into P and Q. You could work out that 41*53 is 2173 by pencil and paper in a minute if you really wanted to know. But factoring 2173 into 41 and 53 requires you to divide 2173 by every possible factor. For modern communications, P and Q will each be over a hundred digits long, so factoring N — and breaking the code — could take thousands of years. Thus RSA, not to mention Romeo and Juliet’s secret romance, is secure.

The tide may turn in Tybalt’s favor soon, as researchers around the world try to break RSA. The first country to do so will have an enormous advantage; they could literally read almost every secret that passes through the Internet. Currently, the most promising approach is a quantum computer, which could easily factor N by asking its copies in parallel universes for help. While quantum computers already exist, the largest number that they can factor so far is 15. So RSA remains unbreakable — for now.

Notes: I first learned about RSA in Sarah Flannery’s book In Code, which I highly recommend. RSA is named for Ronald Rivest, Adi Shamir, and Leonard Adleman, who invented the algorithm in 1979. If you doubt that a computer could handle the calculations in this blog, visit wolframalpha.com and type in “1531^213 mod 2173.” The quote from Romeo and Juliet can be found at I.v.52.