## RSA

Rivest, Shamir, Aldeman works this way:

- Choose two large prime numbers p and q (we’ll use p=29 and q=37 for this example, even though they’re small)
- Set n=pq. (n=1073 for us)
- Choose a random number e such that 1≤e<n (for this, I picked e=407)
- Set d=e
^{-1}(mod (p-1)(q-1)). In this case, d=743 - Give out e and n to the world, keep d to yourself, and throw out p and q.

Now, anyone who wants to send you a secret message, and, again for example, let’s pick, say, a telephone number, “764”, as our message. This is convenient because it is a number. To keep it secret, the sender computes c=m^{e} (mod n), and sends “947” instead. You have d and n available to you, so you take c^{d} (mod n) and, voila, m!

Say someone intercepts the message. They know what e and n are—you blabbed that to everyone (on purpose). But they want to know what “947” means. But because of the modulo, something like exp((log c)/e) doesn’t work (it’d give them 1.01698… if they tried it). If they know how the message was encrypted, and the mathematics behind it, their best bet is to factor n into p and q. Once they know that, they can figure out what d is (see step 4) and discover the message. But since we used small numbers, it’s easy to come up with the factorization.

Another disadvantage of using small numbers is that it limits the number of possible messages. We can only offer up 1071 possibilities (“0” encrypts to “0”, so it’s useless as a possibility, and 1073≡0 (mod n)). That limits you to roughly 10 bits of information—barely bigger than a single ASCII character per “chunk” sent. So another possibility for the person who intercepted the message would be to simply use e and n to encrypt every possible message. Then, when they grab “947”, they just look it up in their table, and they know the message that was sent.

That’s why we use big numbers. Like p=37975227936943673922808872755445627854565536638199 and q=40094690950920881030683735292761468389214899724061. The bigger, the better. As a matter of fact, common lengths of the individual factors is 150-300 digits (1024-2048). The more paranoid you are, the bigger the numbers you can use, and the harder it will be to crack. And the bigger the chunks of message you send can be, so there’s more possible messages, and less opportunity to make a lookup table—there’d be an awful lot of messages to attempt if n was 617 digits long.