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 717 (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
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 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 (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 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 (717)103 ≡ 71 (mod 143)
Showing posts with label Fermat's Little Theorem. Show all posts
Showing posts with label Fermat's Little Theorem. Show all posts
20 October 2016
13 October 2016
Activity for Thursday 13 October
Fermat's Little Theorem: for any prime number p, and any natural number a which is not divisible by p,
$a^{p-1} \equiv 1$ (mod p)
For example, $4^{10} \equiv 1$ (mod 11)
because 11 is a prime number and 4 is not divisible by 11.
Based on your viewing of the video, assigned last time, from Maths by Jay, which discussed Fermat's Little Theorem and how it can be used to simplify some calculations:
Use the above-mentioned fact to find the value of
$4^{1357}$ (mod 11)
Hint: You'll use the division algorithm on the exponent 1357
You want to rewrite $4^{1357}$ as a power of $4^{10}$, times another power of 4
$a^{p-1} \equiv 1$ (mod p)
For example, $4^{10} \equiv 1$ (mod 11)
because 11 is a prime number and 4 is not divisible by 11.
Based on your viewing of the video, assigned last time, from Maths by Jay, which discussed Fermat's Little Theorem and how it can be used to simplify some calculations:
Use the above-mentioned fact to find the value of
$4^{1357}$ (mod 11)
Hint: You'll use the division algorithm on the exponent 1357
You want to rewrite $4^{1357}$ as a power of $4^{10}$, times another power of 4
29 September 2016
Thursday 29 September class
• Warmup activity: finding a pattern in the powers of 8 mod 5, and in the powers of 5 mod 3
We observed that in each case the powers cycled through all the possible nonzero residues, ending with 1:
Next time I will show you how you can exploit modular arithmetic to keep the numbers small when doing this type of computation - which will partially answer the question of what happens in RSA when the numbers get too big for even a computer to handle.
These are examples of Fermat's Little Theorem:
If p is a prime number, and a is any integer which does not have p as a factor, then
ap-1 ≡ 1 (mod p)
In the two examples we had
a=8, p=5: 85-1 = 84 ≡ 1 (mod 5)
a=5, p=3: 53-1 = 52 ≡ 1 (mod 3)
This Theorem plays a role in proving that the RSA algorithm works. (see the notes)
• We showed how the two public keys and the private key are found, first by the example in my notes, and then by the example in this reading (Serge Matovic's homepage: see Section 1). We showed how his method for finding the private key is really the same as the method in my notes.:
In a sense the RSA algorithm is a generalization of the Little Fermat Theorem, as discussed in the background article.
Homework:
• Journal assignment:
• Problems related to the RSA algorithm: (corrected problem number references)
1) Choosing the prime numbers p=3 and q=5, compute m [as in my notes on RSA] and then find possible values for e and d, using trial and error. Record your trial and error or other reasoning to explain how you got them! And try to keep them small.
2) Using the public and private keys you found in problem (1), encode the message 809.
3) Using the private key you found in problem (1), decode the encoded message from problem (4) and show that the decoded message is the original message 809.
• For future use: you will be asked to write a short essay on some aspect of the RSA algorithm. Start thinking about this and doing research on the area you would like to write about. Here are some suggestions (pick ONE, or make up one of your own):
• The history of the RSA algorithm: how and why it came to be developed by Rivest, Shamir, and Adleman
• How RSA is used today
• How long would it take the fastest computer to factor large numbers? What progress has been made on this problem in recent years?
Next up: Explaining why the RSA algorithm works, and how to exploit modular arithmetic to keep the numbers for getting too large when we take those powers. This will involve using Fermat's Little Theorem: please view this video which gives an example and then shows you how it can be used!
We observed that in each case the powers cycled through all the possible nonzero residues, ending with 1:
| 81 ≡ 3 (mod 5) | 51 ≡ 2 (mod 3) |
| 82 ≡ 4 (mod 5) | 52 ≡ 1 (mod 3) |
| 83 ≡ 2 (mod 5) | 53 ≡ 2 (mod 3) |
| 84 ≡ 1 (mod 5) | 54 ≡ 1 (mod 3) |
| 85 ≡ 3 (mod 5) | 55 ≡ 2 (mod 3) |
| ... etc. ... | ... etc. ... |
Next time I will show you how you can exploit modular arithmetic to keep the numbers small when doing this type of computation - which will partially answer the question of what happens in RSA when the numbers get too big for even a computer to handle.
These are examples of Fermat's Little Theorem:
If p is a prime number, and a is any integer which does not have p as a factor, then
ap-1 ≡ 1 (mod p)
In the two examples we had
a=8, p=5: 85-1 = 84 ≡ 1 (mod 5)
a=5, p=3: 53-1 = 52 ≡ 1 (mod 3)
This Theorem plays a role in proving that the RSA algorithm works. (see the notes)
• We showed how the two public keys and the private key are found, first by the example in my notes, and then by the example in this reading (Serge Matovic's homepage: see Section 1). We showed how his method for finding the private key is really the same as the method in my notes.:
In my notes, to find the private key d, we solve the Diophantine equation ed - my = 1 for integers d and y (actually, we want them to be natural numbers in fact)
So in Serge's example, we would be solving 7d - 20y =1 for natural numbers d and y
In Serge's webpage, he does this by solving the modular equation 7d ≡ 1 (mod 20)
By the division algorithm, this is the same as saying that 7d = 20q + 1 for some whole number q.
If you take our Diophantine equation and add 20y to both sides, you get exactly this - it doesn't matter whether you call the quotient q or y.
So these are actually the same procedure written in different ways. It's an equally difficult or easy problem either way. It is just a matter of taste which way to go.
In a sense the RSA algorithm is a generalization of the Little Fermat Theorem, as discussed in the background article.
Homework:
• Journal assignment:
• Problems related to the RSA algorithm: (corrected problem number references)
1) Choosing the prime numbers p=3 and q=5, compute m [as in my notes on RSA] and then find possible values for e and d, using trial and error. Record your trial and error or other reasoning to explain how you got them! And try to keep them small.
2) Using the public and private keys you found in problem (1), encode the message 809.
3) Using the private key you found in problem (1), decode the encoded message from problem (4) and show that the decoded message is the original message 809.
• For future use: you will be asked to write a short essay on some aspect of the RSA algorithm. Start thinking about this and doing research on the area you would like to write about. Here are some suggestions (pick ONE, or make up one of your own):
• The history of the RSA algorithm: how and why it came to be developed by Rivest, Shamir, and Adleman
• How RSA is used today
• How long would it take the fastest computer to factor large numbers? What progress has been made on this problem in recent years?
Next up: Explaining why the RSA algorithm works, and how to exploit modular arithmetic to keep the numbers for getting too large when we take those powers. This will involve using Fermat's Little Theorem: please view this video which gives an example and then shows you how it can be used!