1

I have been given the question:

"Decrypt this message using RSA: 072 062 120 129 (Hint you will need to convert your final answer from ASCII to plain text. The public key used to encrypt the message was (n, e) = (143, 7)."

I don't have any clue how to decrypt it, and this is the only information we have been given. However, I do know that p and q are 13 and 11, which you can get from finding 2 primes that multiply to make n.

Does anyone know how to decrypt this?

Thanks in advance, this has been kind of overwhelming.

Ismaeel Ali
  • 57
  • 1
  • 1
  • 6

1 Answers1

2

You can use the wikipedia article as a guide.


From p and q you can compute λ(n):

λ(n) = lcm(p-1, q-1) = lcm(12, 10) = 60


Once you know λ(n), you can use it to calculate d, the multiplicative inverse of e modulo λ(n):

d = e⁻¹ (mod λ(n))

This essentially means finding a natural number d, such that d*e = 1 (mod 60).

The following snippet of Python code does that:

d = next(d for d in range(60) if d*7 % 60 == 1)

The value of d is 43.


Once we have d, we can use that to decrypt the individual numbers of the message:

decrypted_ascii = [(x**d) % 143 for x in [72, 62, 120, 129]]
decrypted_text = ''.join(chr(x) for x in decrypted_ascii)

The decrypted text is Text.

kyrill
  • 986
  • 10
  • 27
  • 2
    Your modular inverse is very bad in educational sense and not effective. See this [answer](https://stackoverflow.com/a/9758173/1820553) that how it can be calculated by using EXT-GCD. Also, it is clearly **homework** and you are supplying a full answer! – kelalaka Nov 07 '19 at 15:53
  • 1
    My modular inverse calculation is perfect for didactic purposes. If I had used the one you provided, the OP would probably be even more confused after reading my answer than he was when he asked the question. As for whether this is a homework or not ‒ it is not my intention to solve a homework so that the OP doesn't have to; rather I wanted to help OP understand how the RSA algorithm works. Feel free to flag my answer if you want to. – kyrill Nov 07 '19 at 16:19
  • 1
    +1, this is an excellent answer for learning the basics. The rule on stackoverflow for homework problems is slightly nuanced: we're happy to help, but we expect to see the questioner demonstrate *some* effort in the body of the question. A homework dump with no additional info should be closed as "needs more focus" or something similar. Of course not everyone believes this. Perhaps in time you will come around to this view yourself. Either way, thanks for contributing. – President James K. Polk Nov 07 '19 at 21:30