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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
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$ Commented Jul 8, 2016 at 4:52