Modular inverse examples
Refer to the RSA slides for the overall use of RSA. Here, I will concentrate on finding the modular inverse mod phi(n).
For our examples, we will use the homework problem in class.
Suppose we know the following:
- p = 7
- q = 11
- phi(n) = (p-1)(q-1) = 60
- n = pq = 77
We want to pick an encryption exponent, e, such that:
gcd(e,phi(n)) = 1.
So, for an encryption exponent e (e becomes the public key), the gcd of e and phi(n) must equal 1. Having the gcd = 1 is the same as the 2 numbers being relatively prime.
Note: We do not factor phi(n). We use the gcd instead.
So returning to our example,
- We randomly pick e between 1 and phi(n) (What if we chose an e greater than phi(n)?)
- Next, we check the gcd(e, phi(n)) to be equal to 1 by using the Euclidean Algorithm. If not 1, goto step 1. If 1, continue.
- Last, we find the inverse mod phi(n) of e by using backwards substituion on the remainders. This method is known as the Extended Euclidean Algorithm.
Returning to our example, we randomly pick an e, say 11. So check the gcd.
| 60 | = | (5)11 + 5 |
| 11 | = | (2)5 + 1 |
| 5 | = | 5(1) + 0 |
We stop once our remainder is 0, so the gcd(11,60) = 1.
However, the following equation must hold:
By the above equation, we now solve for d. Using our work from finding the gcd, we can now use the extended euclidean algorithm to find the modular inverse of 11 mod 60.
| 1 | = | 11 - (2)5 |
| = | 11 - 2(60 - (5)11) |
| = | 11-(2)60+10(11) |
| = | -(2)60+(11)11 |
The number in bold is the inverse. 11-1mod 60 = 11.
For our last example, we choose e = 17. Again, we start out by finding the gcd.
| 60 | = | (3)17 + 9 |
| 17 | = | (1)9 + 8 |
| 9 | = | (1)8 + 1 |
| 8 | = | (8)1 + 0 |
Now, we find the modular inverse of 17 mod 60.
| 1 | = | 9 - (1)8 |
| = | 9 - 1(17 - (1)9) |
| = | 9 - 17 + (1)9 |
| = | (2)9 - 17 |
| = | -17 + 2(60 - (3)17) |
| = | -17 + (2)60 - (6)17 |
| = | (2)60 - (7)17 |
17-1 mod 60 = -7 mod 60 = 53.
Other pairs of valid e and d:
13,37
31,31
7,43
Last updated at: 2:27 PM, Oct. 19, 2002