RSA: What message will Alice receive?

244 Views Asked by At

In RSA, Alice chooses $p=47$, $q=57$, public key ($n=2679$, $e=11$). When Bob sends the message $m=3$, what is the message that Alice will read?

1

There are 1 best solutions below

0
On

It's not entirely clear what the question is asking, especially because (as noted in the comments), Alice has made a mistake. I suspect that the point of the exercise is to drive home the relevance of picking $p$ and $q$ which are primes (or, more precisely, of correctly computing $\varphi(n)$), and that we're assuming "academic" RSA rather than "real-world" RSA.

Bob will send $3^{11} \pmod{2679}$ which is $333$.

If Alice computes $d$ such that $11d = 1\pmod{(p-1)(q-1)}$, then what is $333^d \pmod{2679}$? (Hint: it isn't $333$. I suspect that this is the answer you're looking for).

On the other hand, if Alice was deliberately using a three-prime RSA (with the horrifically small $3$ as one of them), she will compute $d$ such that $11d = 1 \pmod{\textrm{what?}}$ and get $333^d = 3 \pmod{2679}$.