1
$\begingroup$

I was reviewing RSA by hand.
I picked 53 and 59 as my primes.
For e I picked 5.
When I solved for d using extended euclid, I got 1 which obviously doesn't decrypt anything.
I checked my answers online using calculators and got the same result.
Did I pick e or a prime wrong? How do I make sure I don't get 1 as d?

$\endgroup$
6
$\begingroup$

No, your values for $e$ and primes are fine (well, at least for a toy example); $e$ is relatively prime to both $p-1$ and $q-1$, and that's the only hard requirement (not counting the security related ones, of course).

I get $d=905$, as $5 \times 905 \equiv 1 \pmod{ \operatorname{lcm}((53-1),(59-1))}$; alternatively, you might get $d=2413$, if you do the computation $\bmod (53-1) \cdot (59-1)$.

I can only suspect that you're doing Extended Euclidean wrong; however without knowing exactly what you did, I really can't say exactly where you erred.

$\endgroup$
  • 1
    $\begingroup$ I was just being dumb and using the coefficient of the bigger integer. For some reason in my head I thought I wasn't allowed to use negative numbers. Thanks for answering. I didn't know you could use the lcm of p-1 and q-1 rather than the totient. $\endgroup$ – Firelemons Jul 8 '16 at 4:52

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.