0
$\begingroup$

So I was casually practicing RSA on paper for an exam, I did the whole process I wrote bellow, and when I tried the encryption and decryption I got distracted and instead of doing $m^e \mod n$

I did $m^e \mod {\phi(n)}$ and both the decryption and encryption worked. Is this normal?

Here are the numbers: $$ p = 11\\ q = 23\\ n = (p\cdot q) = (7 \cdot 23) = 253\\ \phi(n) = (p-1) \cdot (q-1) = 220\\ e = 7\\ d = 63 \\ $$ I got d using the Extended Euclidean Algorithm: $$ gcd(220, 7)\\ 220 = 7 * 31 + 3 \\ 7 = 3 * 2 + 1 \\ $$ $$ 1 = 7 + 3(-2)\\ 1 = 7 + (220 + 7(-31))(-2)\\ 1 = 7(63) + 220(-2)\\ $$

$\endgroup$
3
  • 1
    $\begingroup$ Nope. Could could you show your work? $\endgroup$
    – kelalaka
    May 13 at 3:23
  • 1
    $\begingroup$ I don't think it's normal. It's probably the numbers you used just happen to work, so can you show us the numbers you used? $\endgroup$
    – DannyNiu
    May 13 at 3:28
  • $\begingroup$ thanks for your response, I edited my post and added the numbers $\endgroup$
    – frog
    May 13 at 4:34

1 Answer 1

1
$\begingroup$

In general a pair of RSA decryption exponents calculated in this way for a modulus $N$ will also work for any modulus $M$ that satisfies $\lambda(M)|\phi(N)$ where $\lambda$ is the Carmichael function.

In your example $M=\phi(N)=220$ and $\lambda(M)=\mathrm{lcm}(\phi(4),\phi(5),\phi(11))=\mathrm{lcm}(2,4,10)=20$ does indeed divide $\phi(N)=220$. This set of circumstances was helped by the fact that 11 divides $\phi(23)$. In general if the RSA modulus $pq$ has $p|q-1$ then $\phi(p)|\phi(\phi(q))$ and this helps a great deal.

This sort of phenomenon is less likely to happen when $p-1$ and $q-1$ have large prime divisors. However, it should be possible to construct other examples by choosing $p$ and $q$ where $p-1$ and $q-1$ are not divisible by any large primes, but are divisible by all small prime powers.

$\endgroup$

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.