1
$\begingroup$

I have found from the values of P (11) and Q(7) that n=77, (p-1)(q-1)=60 and that e=43 as it is relatively prime with 60.

However, I believe the value I got for d (7) is wrong. Here is my workings out:

60x + 43y = 1

60=1(43)+17
43=2(17)+9
17=1(9)+8
9=1(8)+1

Then:

1=9 - 1(8)
1=9 - 1(17 - 1[9])
1=1(9) - 1(17) + 1(1[9])
1=1(9) + 1(1[9]) - 1(17)
1=2(9) - 1(17)

1=2(43 - 2[17]) - 1(17)
1=2(43) - 4(17) - 1(17)
1=2(43) - 5(17)

1=2(43) - 5(60 - 1[43])
1=2(43) - 5(60) + 5(1[43])
1=7(43) - 5(60)

therefore d=7, right? It seems to not work in practice and I can't figure out why :(


The issue is when I apply these values into these formulas:

$$C = M^e \bmod n$$ $$M = C^d \bmod n$$

For example, when I make M=2 (for B) the result is C = 53.0009765625... But using the formula to decrypt it doesn't return back to the original value


I would really appreciate any advice and apologies if I have worded it badly.

$\endgroup$
  • $\begingroup$ I'm voting to close this question as off-topic because it's about math with no immediate connection to cryptography. So it is more suitable for one of the math stackexchanges. $\endgroup$ – Ella Rose Sep 6 '18 at 17:18
  • 2
    $\begingroup$ For $M = 2$ we have $C = 2^{43} \bmod{77} = 30$. Therefore $M = 30^7 \bmod{77} = 2$. So your $N, e, d$ are correct. If $C$ is coming back as a float you're doing modular exponentiation wrong. $\endgroup$ – puzzlepalace Sep 6 '18 at 19:31
3
$\begingroup$

$d=7$ is correct; this can easily be verified by computing:

$$43 \times 7 \bmod 60 = 301 \bmod 60 = 1$$

So, the source of the problem lies somewhere in your "practice"; as you didn't share the details of what that was, I can't point out exactly where the problem is.

| improve this answer | |
$\endgroup$

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.