Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
5  
There is no mistake. In your toy example it just !accidentially! happens that $e$ is self-inverse, i.e., it happens that $e=d$. –  DrLecter Jun 25 at 16:45
3  
No mistake. A number can be it's own inverse. Just pick a different $e$. –  mikeazo Jun 25 at 16:45
2  
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. –  Thomas Jun 26 at 1:26
    
Have a look here, that's the same problem with different numbers ($e=d=5, N=15,\phi(N)=12$) –  tylo Jun 26 at 13:04
1  
@tylo maybe these two represent classmates separated by a year in school :) –  mikeazo Jun 26 at 19:48

1 Answer 1

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.

share|improve this answer
2  
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}$ –  poncho Jun 27 at 13:24
    
@poncho, thanks! Updated accordingly. I always forget about $\lambda$ when thinking about RSA. –  mikeazo Jun 27 at 13:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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