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.

Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$ always equals the decryption exponent $d$?

What I have so far:

$n = 35$

Therefore $p = 5$ and $q = 7$ or vice versa, which means Euler's phi function is

$\varphi = (5-1) \cdot (7-1) = 24$

Then to find $e$ we need the fact that $\gcd(e,\varphi) = 1$

$\gcd(e, 24) = 1$

Therefore the possible values of $e$ are only prime. $e = 5, 7, 11, 13, 17, 19, 23$

Then $d$ must follow the equation $d \equiv e^{-1} \mod \varphi$ or $(d\cdot e) \equiv 1 \mod 24$

Then I've tried for all those values which solve that equation. Why is that true? How can I explain this?

share|improve this question
    
$\gcd(3,24) \ne 1$. –  Ilmari Karonen Dec 15 '11 at 1:18
    
For extra credit, show that $n=91$ has the same property; that is, if $d=e$ is relatively prime to $\phi(91)$, then $(M^e)^d = M \mod 91$ for all $M$ (and hence, the encryption exponent $e$ always equals the decryption exponent $d$) –  poncho Dec 15 '11 at 16:04

1 Answer 1

up vote 8 down vote accepted

The number 24 has the curious property that, for any prime $p > 3$, $p^2 - 1$ is divisible by 24. (In fact, this holds for any odd number $p$ not divisible by 3.)

This follows simply from the fact that $p^2 - 1 = (p-1)(p+1)$; since $p$ is not divisible by either 2 or 3,

  • the factors $p-1$ and $p+1$ must both be even,
  • one of them must be divisible by 4, and
  • one of them must be divisible by 3.

Thus, their product must be divisible by $2\cdot4\cdot3 = 24$.

share|improve this answer

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.