I have that $N = 798$, $p=2$, and $q=399$. I choose $e$ such that $\gcd(e,(p-1)(q-1))=1$ where $e=7$. I, then, choose $m = 123$. Thus, $c=123^{7}\bmod798=669$, which is my ciphertext. After, I try $d=7^{-1}\bmod398=57$. I, then, get the wrong result that $m'=669^{57}\bmod798=729$ which is not my original message $m$.

Why is this? I can't seem to understand why RSA would break. Does RSA break if either $p$ or $q$ is 2 and the other is a composite?

  • $\begingroup$ I edited the question to use the correct formulas for RSA encryption and decryption. That's not $c\equiv m^e\pmod N$ (meaning that $m^e-c$ is a multiple of $N$ ), because it does not uniquely define $c$, and for example allows $c=m^e$. We need $0\le c<N$, and the notation for that is $c=m^e\bmod N$, where $\bmod$ is an operator computing the remainder of the Euclidean division. As pointed in answer, the issue in the question's calculations is that $q$ is composite, and $\varphi(p\,q)\ne(p-1)(q-1)$. $\endgroup$ – fgrieu Mar 2 '18 at 7:43

Since your q is composite with factors 3,7,19 we get $\phi(q)=(3-1)*(7-1)*(19-1)=216$ and not 398 The rest of the calculation follow as in the question.

And since $p=2$ we get also $\phi(n) = 216$

As a result we also get $d=e^{-1}=7^{-1}=31 \bmod 216$

And we can verify that $669^{31} \bmod 798 =123$ as expected.

  • $\begingroup$ I see. So, when using RSA, $\phi$($q$) is only ($q$-1) when $q$ is prime. Thank you! $\endgroup$ – Phoenixdeath Mar 3 '18 at 4:18

Yes, RSA is defined for $N$ being the product of two primes.

There have been multi-prime RSA defined, for some other specific purposes, but the decryption functions would be different since $\phi(N)\neq (p-1)(q-1)$ anymore if $q$ is composite. Let $N$ be a product of distinct primes $N=p_1\cdot p_2 \cdots p_m,$ then the correct Euler's totient is $$\phi(N)=(p_1-1)(p_2-1)\cdots (p_m-1).$$

  • $\begingroup$ Does 2 being a factor have a special case for it, though? It seems like when I choose any other prime and composite (say $p = 11$ and $q=300$) it does not break it; only when it is 2 and a composite. $\endgroup$ – Phoenixdeath Mar 2 '18 at 6:57
  • $\begingroup$ No, it has failed for me on the first experiment. $\endgroup$ – kodlu Mar 2 '18 at 7:26
  • $\begingroup$ n:=11*300; "eulerphi", EulerPhi(n); phi:=10*299;phi;"wrongphi", phi; e:=7; GCD(e,phi); m:=101; "plaintext", m; c:= m^7 mod phi; "ciphertext under wrong phi", c; d:=Modinv(7,phi); "wrong decryption key", d; "decryption", c^d mod phi; d:=Modinv(7,EulerPhi(n)); "correct d",d; c:=m^7 mod EulerPhi(n); "correct ciphertext", c; "decryption", c^d mod EulerPhi(n); this magma code gives $\endgroup$ – kodlu Mar 2 '18 at 7:29
  • $\begingroup$ eulerphi 800 2990 wrongphi 2990 1 plaintext 101 ciphertext 2051 wrong decryption key 2563 decryption 231 correct d 343 correct ciphertext 301 decryption 101 $\endgroup$ – kodlu Mar 2 '18 at 7:29

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.