RSA

Ronald Rivest, Adi Shamir, and Leonard Adleman, 1977.

Setup:

Pick two primes p and q.

Compute n=pq.

Pick encryption exponent e such that e and (p-1)(q-1) don't have any common prime factors.

Make n and e public. Keep p and q private.

Example:

Modular Arithmetic

Karl Friedrich Gauss, 1801.

Modular Arithmetic = "Wrap-around" computations

Example: start at 12 o'clock. 5 hours plus 8 hours equals 1 o'clock

Example: start at 12 o'clock. 11 hours times 5 equals 7 o'clock.

Encryption:

Anyone can encrypt, because n and e are public.

To encrypt, convert your message into a set of plaintext numbers P, each less than n.

For each P, compute

The numbers C are your ciphertext.

Example: send the message "cats and dogs"

Trap Door

Leonhard Euler, 1736.

Let

be the number of positive integers less than or equal to n which don't have any common factors with n.

Example: If n=15, then the positive integers less than or equal to n which don't have any common factors with n are 1, 2, 4, 7, 8, 11, 13, 14. So

In the RSA system n=pq, so

is the number of positive integers less than or equal to n which don't have p or q as a factor.

How many positive integers less than or equal to n do have p as a factor?
p, 2p, 3p, ..., n=qp
so there are q of them.

Similarly, there are p positive integers less than or equal to n with q as a factor.

Only one positive integer less than or equal to n has both p and q as factors, namely n=pq. So we should only count this once.

Therefore,

This is private! You can't calculate it without knowing p and q.

Euler's Theorem: if x is an integer which has no common prime factors with n, then

Why is Euler's Theorem true?

Number Theory idea: We consider the positive integers less than or equal to n which don't have any common factors with n, and multiply each of them by x modulo n. Compare them to the same integers without multplying by x.

Example.

For n=15, consider x, 2x, 4x, 7x, 8x, 11x, 13x, 14x (mod 15), and compare them to 1, 2, 4, 7, 8, 11, 13, 14. If we multiply all of the first set we get

and if we multiply all of the second set we get

What if we do all of this for x=11? The first set will be

which is the same as the second set, only in a different order! In fact, this always happens. So

or

Arthur Cayley, 1878.

Group Theory idea: We make a Cayley diagram for the numbers less than n.

Example.

Say x=11. Follow the arrows from 1 to 11. This is one x14 arrow and two x2 arrows. If you do this 7 more times, you will be following a total of eight x14 arrows and sixteen x2 arrows, and you should end up at 11 to the eighth. However, eight x14 arrows and sixteen x2 arrows clearly ends you up back where you started! (Note that it doesn't matter in what order you follow the arrows....)

So how do we use the trap door?

Decryption:

We need one more piece of (private) information.

Euclid, about 300 B.C.E.

If a and b don't have any common prime factors, then there are integers c and d such that

Since we picked e such that e and (p-1)(q-1) don't have any common prime factors, then there are integers c and d such that

or

Euclid also tells us how to find c and d, using the Euclidean Algorithm.

Once we have found the decryption exponent d, which is private, we can decrypt.

For each C, compute

What will this give you?

We know

although we don't yet know what P is. So

but

by Euler's Theorem! So

and we get our original plaintext back.

Example:

Breaking RSA:

So why do we think RSA is secure?

As far as we know, the only way to break RSA is to find p and q by factoring n. The fastest known factoring algorithm takes something about like

time units to factor n. (The size of the time unit depends on things like how fast the computer is!) For the fastest computers in 1992, it would have taken about 4 million years to factor a number with 200 decimal digits.

On the other hand, finding p and q and multiplying them together is very fast. Finding a number p which is (probably) prime takes about

time units. This looks large, but it isn't really; for a 200-digit number this should only take a few minutes. (Multiplying p and q together is even faster.)

Digital Signatures:

As a bonus, RSA gives us a way to digitally "sign" messages, thereby proving who wrote them. This uses the same public n and e and private d as before.

For each plaintext P, compute

The numbers S are your signed message.

Since only you know the decryption d, only you can sign a message. The person you send it to can prove it was you by computing

(since e is public) and getting back

which we know is congruent to P. If this matches the P you sent separately, then the message was correctly signed, so it must have come from someone who knows d.

Example: suppose that instead of encrypting the message "cats and dogs" we wanted to sign it.

Then anyone who looked up our public n and e could prove that we had sent it:

One can even sign an encrypted message this way. Suppose Alice wants to send Bob an encrypted message. Then she first encrypts with Bob's public n(B) and e(B). Secondly, she signs the message with her n(A) and private d(A). Since her d(A) is different from Bob's d(B), they don't cancel out. Then Bob can "unsign" the message with Alice's public n(A) and e(A) and finally decrypt the message with his n(B) and private d(B)!

Example:

Alice

(private)

(public)

(public)

(private)

Bob

(private)

(public)

(public)

(private)

Alice encrypts the message with Bob's public information:

Alice signs the message with her private information and send the result to Bob:

Bob "unsigns" the message using Alice's public information:

and then decrypts it using his private information:

Attacks on RSA:

Finding out someone's private d is probably as hard as factoring n. But sometimes we can find out a particular message without breaking the general code. Usually this is because e is too small --- small e makes the encrypting faster, but can weaken security.

Small message attack

Common exponent attack

Suppose we're sending the same message to Alice, Bob, and Carol, and they all have the same small exponent.

Message to Alice:

Message to Bob:

Message to Carol:

Eve (an eavesdropper) hears the messages. Eve knows

and similarly for the second half of the message. (Everything here except P is public information!) Then the Chinese Remainder Theorem (c. 1st century C.E.) says Eve can recover

using the magic formula

But now Eve can use the small message attack:

This is guaranteed to work if there are at least e messages. Moral: don't send identical messages!