1
$\begingroup$

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'
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Amended, thanks $\endgroup$ – Joe Blogs Oct 25 '17 at 13:01
  • $\begingroup$ Can you see why I'm not getting the correct values for d? $\endgroup$ – Joe Blogs Oct 25 '17 at 13:06
  • $\begingroup$ Seems now correct. Then $-367\equiv 17\mod 780$. $\endgroup$ – Wuestenfux Oct 25 '17 at 13:23
  • $\begingroup$ Maybe this is the wrong place to ask this question, but maybe my issue is my value for n. I have seen two values being used 1) 'n = LCM(p,q)' 2) 'n = ((p-1)*(q-1))'. D I believe is found by 'd*e%n = 1' then using Extended Euclidean algorithm on that. Am I correct? and what should I be using for n $\endgroup$ – Joe Blogs Oct 25 '17 at 13:42
  • $\begingroup$ I updated the answer to give additional information (it is too long for a comment). $\endgroup$ – wsj84 Oct 25 '17 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.