5
$\begingroup$

I am a bit confused. I just calculated manually the single steps of RSA for an implementation with small numbers and suddenly $d$ was equal $e$. Please help me understand what I am doing wrong.

Here’s my example:

  1. I chose: $q = 7$ and $p = 11$
  2. $N = 77$
  3. $phi(N) = 60$
  4. I chose: $e = 29$
  5. $e \times d + k \times phi(N) = 1 \rightarrow$ Extended Euclidean algorithm
    $$k = -14\\ d = 29$$

Test: $29 \times 29 + (-14) \times 60 = 1$

Where is the mistake?

|improve this question
$\endgroup$
  • 5
    $\begingroup$ There is no mistake. In your toy example it just !accidentially! happens that $e$ is self-inverse, i.e., it happens that $e=d$. $\endgroup$ – DrLecter Jun 25 '14 at 16:45
  • 3
    $\begingroup$ No mistake. A number can be it's own inverse. Just pick a different $e$. $\endgroup$ – mikeazo Jun 25 '14 at 16:45
  • 2
    $\begingroup$ Note that $e$ cannot be its own inverse unless $e > \sqrt{\varphi(n)}$ (or $\lambda(n)$), or $e = 1$ of course, so in real usage with a normal public exponent $e$ this cannot happen. $\endgroup$ – Thomas Jun 26 '14 at 1:26
  • $\begingroup$ Have a look here, that's the same problem with different numbers ($e=d=5, N=15,\phi(N)=12$) $\endgroup$ – tylo Jun 26 '14 at 13:04
  • 1
    $\begingroup$ @tylo maybe these two represent classmates separated by a year in school :) $\endgroup$ – mikeazo Jun 26 '14 at 19:48
6
$\begingroup$

The only reason you are seeing this is because you are dealing with such small primes. With primes like we would use in practice (1024 bits), the probability of this happening is very, very small. And, it can only happen when $e>\sqrt{\lambda(n)}$. Since we typically use $e=65537$ in practice, it is guaranteed to not happen.

Anyways, there is no mistake in your calculations, you just happened to pick an $e$ which is its own inverse.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Actually, the correct condition is $e > \sqrt{\lambda(n)}$. For a quick counterexample of your condition, consider $n = 2501$ and $e=11$. Here, $e=11 < \sqrt{\phi(n)} = \sqrt{2400}$ $\endgroup$ – poncho Jun 27 '14 at 13:24
  • $\begingroup$ @poncho, thanks! Updated accordingly. I always forget about $\lambda$ when thinking about RSA. $\endgroup$ – mikeazo Jun 27 '14 at 13:27

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.