This question is related to RSA cryptosystem.
For simplicity I will work through the example given on Wikipedia on the following address: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example (under the example header)
under the subheading: "Compute d, the modular multiplicative inverse of e (mod λ(n))" I have done the following which has given me the wrong answer.
Can someone please correct me in stating what I've done wrong or not yet done. Thank you.
p=61 and q=53
n = pq = 3233
(this other value confuses me, why is it calculated?) LCM of (60,52) = 780. I'm sure other examples used n for this??
e= 17
calculating d
To do this the modular multiplicative inverse of e(mod(n)) must be found.
The worked example give the formula d * e % n = 1
Thus d * 17 % 780 = 1
To solve d here I tried to use Extended Euclidean algorithm here is what I get:
GCD(17, 780)
780 = 45 * 17 + 15
17 = 1 * 15 + 2
15 = 7 * 2 + 1 <<<< Final one as the next remainder is 0
1 = 15 - 7 * 2
1 = 15 - 7 * (17-1*15)
1 = 8 * 15 - 7 * 17
1 = 8 * (780 - 45 * 17) - 7 * 17
1 = 8(780) - 367(17)
This is not what I need for d
edit: d in this instance should be 413
Edit 2, let me run through a whole example I had earlier and set out my concerns more clearly:
P1 picks two primes p and q
p=17 q=19 n = pq = 323
P1 chooses another prime e
e = 7
P1 makes n and e public
P2 wants to send P1 'H', 'H' in Ascii is 72
- P2 does the following 72^e % 323 = c. 72^7 % 323 = c = 13
P2 sends P1 c
P1 needs to use p and q to decrypt c
- P1 calculates D in order to do so.
- (7xD)(mod((p-1)*(q-1)))=1
- (7xD)(mod((16)*(18))) = 1
- (7xD)(mod(288) = 1
- which is the same as 7*D = 1 mod 288 << Am I correct there?
Extended Euclidean algorithm
GCD(7, 288) 288 = 41 * 7 + 1 7 = 7 * 1 + 0 288 = 41 * 7 + 1 << (no winding up??)
(Something happens here which I am unsure of)
- D = 247
- To decode the message c^D mod n is used
- 13^247 mod 323 = 72
- 72 in Ascii = 'H'