1

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?

Douglas S. Stones
  • 21,079
SSMath
  • 49
  • 4
  • 7
    Welcome to Math.SE. Thank you for your question. It will help us to better answer it if you share the context of the problem, as well as what you've tried so far. For this particular problem, there's an algorithm that needs to be followed. Are you having trouble with a particular step, or do you need a pointer to learn about RSA in general? – vadim123 May 15 '13 at 13:32
  • 2
    This site says the message will be 051 in plaintext and 306 in numeric. I DONT KNOWZ TEH RSA. – Soham Chowdhury May 15 '13 at 13:35
  • 6
    Alice goofed. RSA requires $p$ and $q$ to be primes. 57 isn't prime, since it's obviously divisible by 3. – Rick Decker May 15 '13 at 13:58
  • 5
    @RickDecker, maybe Grothendieck posed the exercise. – Peter Taylor May 15 '13 at 14:10
  • 1
    @SSMath: You can see my answer here for the process, but as Rick pointed out, $q$ is not a prime. That may be salvageable for this problem. Regards – Amzoti May 15 '13 at 14:44
  • 1
    so rsa works only with prime numbers and this exercise is wrong or we can solve it with a diffrent way.. @vadim123: what algorith do you mean can you explain –  May 16 '13 at 19:25
  • The excercise is not wrong and i must solve it with this numbers... The difficulty is that q is not prime. So there is another algorithm to follow? or i will follow the classic algorithm filling it with not prime number? – SSMath May 17 '13 at 08:58

1 Answers1

2

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

Peter Taylor
  • 13,425