2

If our message is 204, our public RSA-key is (e, N) = (47, 221) but the private key is unknown.

is it possible to retrieve the message without the private key and what would be the steps to do so?

Courtney Mill
  • 107
  • 2
    In this case, couldn't you use the fact that $$N = 221 = 13 \times 17?$$ – Moo Jun 26 '18 at 14:22
  • @Mo comments states that N = 13 * 17. I think I can calculate d using : e × d ≡ 1 (mod(12*16)) which comes out as d= 23. does this make sense? – Courtney Mill Jun 26 '18 at 16:18
  • 1
    I am not sure how you got that result for $d$, please recheck that. I get $d = 143$. – Moo Jun 26 '18 at 16:25
  • @Moo Now I can simply decrypt the message using 204^143 mod 221, right? Thank you for taking the time to help out!! – Courtney Mill Jun 26 '18 at 17:01
  • 1
    Were you told how the message was encoded? For example, one digit at time, two digits at a time,...? – Moo Jun 26 '18 at 17:04
  • @Moo I made the question up. Could be one digit at a time :) – Courtney Mill Jun 26 '18 at 19:51
  • 1
    Then, you would also decrypt one digit at a time - this is critical to do it both encoding and decoding using the same number of bits and also any methodology. So, you would do $$m_i = c_i^d \pmod {((p-1)(q-1))}$$ You would perform that operation three separate times to get back your message $m$. – Moo Jun 26 '18 at 20:03
  • Awesome! Thanks a lot for your help and guiding me through this! :) – Courtney Mill Jun 26 '18 at 21:11

2 Answers2

2

This is a special situation you can easily test. In your case a private key is just the public key: $$204^{47} \equiv 68 \pmod {221}, \quad 68^{47} \equiv 204 \pmod {221}$$

The reason for this is, that $$47^{-1} \equiv 47 \pmod {\lambda(N)}$$ where $\lambda(N)$ is the Carmichael function. The often used private key via $\varphi(N)$ would be $d=143.$

gammatester
  • 18,827
  • Hmm I don't get. As @Moo comments states that N = 13 * 17. I think I can calculate d using : e × d ≡ 1 (mod(12*16)) which comes out as d= 23. Am i doing anything wrong here? – Courtney Mill Jun 26 '18 at 16:17
  • 1
    No, $47^{-1} \equiv 143 \pmod {192} $ where as your $23$ gives $23*47 \equiv 29 \pmod {192} $ – gammatester Jun 26 '18 at 16:24
  • 1
    Are you sure that $$23*47 \equiv 29 \pmod {192}$$ – Moo Jun 26 '18 at 16:32
  • yes true, I made a silly mistake and calculated n = 13*7, sorry.. Now I can simply decrypt the message using 204^143 mod 221, right? Thank you for taking the time to help out!! – Courtney Mill Jun 26 '18 at 16:51
  • 1
    @moo: Yes you are wright, it is 121. I accidentally computed 23*43. But the crucial point is that is $\not \equiv 1$. – gammatester Jun 26 '18 at 17:21
  • 1
    @courtney-mill: Yes $d=143$ works, but as written, this is the normal private exponent found by factorization. $d=47$ works too, and the check 'is $d=e?$' can always be done, even for large $N.$ But normally this special case should be excluded during key generation. – gammatester Jun 26 '18 at 17:27
  • Awesome! Thanks a lot for your help and guiding me through this! :) – Courtney Mill Jun 26 '18 at 21:11
0

In this case the rather obscure cycle attack works very well, by coincidence (or not; it's an exercise after all, with small parameters)

This works as follows: suppose the public key is $(N,e)$ and we receive the message $c$. Then compute $c_0 = c, c_{n+1} = c^e \pmod{N}$ until $c = c_k$ for some $k \ge 1$ (this will always happen, only normally $k$ will be very large, but with small parameters its doable). Then $c_{k-1}$ is the original message (as its encryption is $c_k =c$).

Doing it here already gives $c_2 = 204$ and $c_1 = 68$ which is the plaintext.

This paper explains why this is normally not a realistic attack in practice .

Henno Brandsma
  • 242,131