0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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 ♦
    Commented Mar 2, 2018 at 7:43

2 Answers 2

Reset to default
4
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
4
  • $\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
    Commented Mar 2, 2018 at 6:57
  • $\begingroup$ No, it has failed for me on the first experiment. $\endgroup$
    – kodlu
    Commented Mar 2, 2018 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
    Commented Mar 2, 2018 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
    Commented Mar 2, 2018 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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