1

First of all, I know how to solve the following exercise; the problem is that there is no solution. "In RSA, Alice chooses $p=53$, $q=63$, public key ($n=3339, e=13$). When Bob sends the message $m=5$, what is the message that Alice will read?"

$φ(n) = 3224$

For encoding I have $ C = 5^{13} \mod(3339) = 1454$

The problem start's when I decode the message: First I have to calculate the secret key $d$ s.t. $$13d = 1 \mod(3224)$$, for which there is no solution (I know that $q$ should be prime and I assume this is the problem). I contacted my professor and the answer i got is that the mistake is on purpose and have to comment what is going on. I really do not understand what i should answer.

nicolasmanic
  • 129
  • Where did you get $\phi(3339)$, I get $52\times 6 \times 6$, also yes, both p and q are supposed to be prime and the public key is supposed to be relatively prime to both $(p-1)$ and $(q-1)$, right? – Random Excess May 22 '14 at 20:13
  • I am not sure i get what you mean but it is given that $n = 3339$ and $φ(n)=(p-1)(q-1) = 52* 62=3224$ – nicolasmanic May 22 '14 at 20:18
  • $63 = 9\times 7$ is not prime! – fkraiem May 22 '14 at 20:29
  • @fkraiem I know that, but this does not interfer with me being unable to calculate the correct secret key d. – nicolasmanic May 22 '14 at 20:35
  • Yes, it does, because $\phi(pq) = (p-1)(q-1)$ only works if $p$ and $q$ are distinct primes. – fkraiem May 22 '14 at 20:36
  • I see, so t let's say that this is a real world example Alice will not read anything (not even a wrong message?) – nicolasmanic May 22 '14 at 20:44
  • 1
    Indeed, Alice will not be able to decrypt this message, because she used a public exponent which is not relatively prime with $\phi(n) = 1872$. – fkraiem May 22 '14 at 20:49
  • Oh ok thanks one last question why $φ(n) = 1872$ I think $φ(n) =(p−1)(q−1)=52∗62=3224$ am i wrong? – nicolasmanic May 22 '14 at 20:54
  • 1
    Again, $\phi(n) = (p-1)(q-1)$ only works if $p$ and $q$ are two distinct primes. Otherwise, it has some other value. See http://en.wikipedia.org/wiki/Euler%27s_totient_function – fkraiem May 22 '14 at 21:01

1 Answers1

2

Just so this question has an answer...

There are two problems here. The first is that the Euler totient $\phi(n)$, for $n = pq$, equals $(p-1)(q-1)$ if and only if $p$ and $q$ are two distinct prime. Here we have $q = 63 = 9\times 7$ so $q$ is not prime.

We have in fact $n = 53\times 63 = 53\times 7\times 3^2$ so $\phi(n) = \phi(53)\phi(7)\phi(3^2) = 52\times 6\times 6 = 1872$.

The second is that the public exponent $e = 13$ is not relatively prime with $\phi(n) = 1872 = 2^4\times 3^2\times 13$, so there is no $d$ such that $de\equiv 1 \pmod{\phi(n)}$.

fkraiem
  • 3,129