I'm working on understanding the RSA encryption system and one of the steps is to find a value d such that d*e mod m = 1. In my particular problem, e = 17 and m = 288. How would I use Euclid's extended algorithm to find the value d? I have an understanding of how to step through the algorithm but I just don't know which values I would use for this problem.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
Euclid's algorithm
- Thread starter colerelm
- Start date
The assumption in RSA is that (e,m)=1. So there are integers x and y such that ex+my=1.
So if you find x,y you know d = x (mod m).
So how would I find x and y with only one equation?
So how would I find x and y with only one equation?
You just said you knew how to use the algorithm, or did I miss something? This algorithm gives you x and y.
1) use standard EA to show gcd(e,m)=1.
2) use extended part to "go backwards" and obtain a linear combination of e and m equal to 1.
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
de= 1 (mod m) means de= 1+ im for some integer m. That is the same as de- im= 1. Of course, the "Eucidean Algorithm" says that, for d and m relatively prime, there exist i satisfying that equation. A standard way of finding it is to start dividing: if e divides into m a times with remainder p, then m- ae= p. And we can continue that way.
For example, to solve 7e= 1 (mod 11) we can write 7e= 1+ 11i so that 7e- 11i= 1. y divides into 11 once with remainder 4: 11- 7= 4. 4 divides into 7 once with remainder 3: 7- 4= 3. 3 divides into 4 once with remainder 1: 4- 3= 1. replacing that with "3" with "7- 4", 4- (7- 4)= 2(4)- 7= 1. Then replace that 4 with 11- 7: 2(11- 7)- 7= 2(11)- 3(7)= 1. That's almost what we want but has the wrong signs: instead (-3)7)- (-2)(11)= 1 so that e= -3 (mod 11). Of course, that is the same as e= 11- 3= 8 (mod 7) if we want to stay between 0 and 11.
Because those are relatively small numbers, we could also have done this: there is NO integer, e such that 7e= 1 so we look at 11+ 1= 12. 7 does not evenly divide 12 so we look at 11+ 12= 23. 7 does not evenly divide 23 so we look at 11+ 23= 34. 7 does not evenly divide 34 so we look at 11+ 34= 45. 7 does not evenly divide 45 so we look at 11+ 45= 56. And finally, we see that 7 divides 8 times: 7e= 1 (mod 11) gives e= 8 (mod 11).
For example, to solve 7e= 1 (mod 11) we can write 7e= 1+ 11i so that 7e- 11i= 1. y divides into 11 once with remainder 4: 11- 7= 4. 4 divides into 7 once with remainder 3: 7- 4= 3. 3 divides into 4 once with remainder 1: 4- 3= 1. replacing that with "3" with "7- 4", 4- (7- 4)= 2(4)- 7= 1. Then replace that 4 with 11- 7: 2(11- 7)- 7= 2(11)- 3(7)= 1. That's almost what we want but has the wrong signs: instead (-3)7)- (-2)(11)= 1 so that e= -3 (mod 11). Of course, that is the same as e= 11- 3= 8 (mod 7) if we want to stay between 0 and 11.
Because those are relatively small numbers, we could also have done this: there is NO integer, e such that 7e= 1 so we look at 11+ 1= 12. 7 does not evenly divide 12 so we look at 11+ 12= 23. 7 does not evenly divide 23 so we look at 11+ 23= 34. 7 does not evenly divide 34 so we look at 11+ 34= 45. 7 does not evenly divide 45 so we look at 11+ 45= 56. And finally, we see that 7 divides 8 times: 7e= 1 (mod 11) gives e= 8 (mod 11).