Extended Euclidean algorithm issue.

Question

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'

Answer 1

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.