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'
You made a mistake in the last line of your calculation: $8\cdot 45 + 7$ is not equal to $343$.
There is an easier and less error-prone way to do this calculation.
The idea is to write equations $z = 780x + 17y$ and to combine them until we get an equation with $z=\gcd(780,17)=1$
You start with the obvious two equations:
$780 = 780\cdot 1 + 17\cdot 0$
$17 = 780\cdot 0 + 17\cdot 1$
Since $\lfloor 780/17\rfloor=45$, subtract $45$ times the second equation from the first:
$15=780\cdot 1 - 17\cdot 45$
and continue doing this until the left-hand side becomes $1$.
In fact, you don't need to write all the equations in full; you can simply make a table with the values of $z$, $x$ and $y$.
Note that $-367\equiv 413\pmod{780}$
Concerning the value of $n$.
In the article, $n = pq$ is the public modulus. It is used for encryption and decryption: you encrypt $M$ as $M^e\pmod{n}$. The value $\mbox{lcm}(p-1,q-1)$ is used when you prepare your public key: after you choose $p$ and $q$, you choose a public key $e$ and compute your private key $d$ as you did. You do this only once.
You need to have $M^{ed}\equiv M\pmod{pq}$, which is equivalent to $M^{ed}\equiv M\pmod{p}$ and $M^{ed}\equiv M\pmod{q}$.
By Fermat's Little theorem, if $p$ is prime and $\gcd(a,p)=1$, $a^{p-1}\equiv 1\pmod{p}$.
This means that you must have $ed\equiv 1\pmod{p-1}$ and $ed\equiv 1\pmod{q-1}$. This implies that you must have $ed\equiv 1\pmod{\mbox{lcm}(p-1,q-1)}$.
On the other hand, if you find $ed\equiv 1\pmod{(p-1)(q-1)}$, this will imply the previous condition. However, you may find a larger value for $d$, but the value will be the same $\pmod{\mbox{lcm}(p-1,q-1)}$. In that case, the algorithm will still work. However, the number of operations required to compute $M^d\pmod{pq}$ will be larger. As we are dealing with very large numbers, this is significant.