# Why does my attempt at RSA break?

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?

• 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)$. – 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.

• I see. So, when using RSA, $\phi$($q$) is only ($q$-1) when $q$ is prime. Thank you! – 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).$$

• 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. – Phoenixdeath Mar 2 '18 at 6:57
• No, it has failed for me on the first experiment. – kodlu Mar 2 '18 at 7:26
• 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 – kodlu Mar 2 '18 at 7:29
• eulerphi 800 2990 wrongphi 2990 1 plaintext 101 ciphertext 2051 wrong decryption key 2563 decryption 231 correct d 343 correct ciphertext 301 decryption 101 – kodlu Mar 2 '18 at 7:29