Thursday 20 October class

Topic:
Outlining the "proof" that the RSA works, for the example given in my notes.

This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)

The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.

In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).

To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.

The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).

What we want to prove in the example is that if we encode the message 71 by taking 71⁷ (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.

In other words, we want to prove (without actually computing it) that
(71⁷)¹⁰³  ≡ 71 (mod 143)

Here are the essential steps of the proof:

• Prove that 71⁷  ≡ 124 (mod 143) means that  71⁷  ≡ 124 (mod 11) and 71⁷  ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent  modulo any prime factor of n.]

• Prove that (71⁷)¹⁰³  ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that  (71⁷)¹⁰³  - 71 is divisible by 11 (division algorithm)

• Prove that (71⁷)¹⁰³ ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that  (71⁷)¹⁰³  - 71 is divisible by 13 (division algorithm0

• Since (71⁷)¹⁰³  - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)

• So (71⁷)¹⁰³  ≡ 71 (mod 143)