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.
Best Answer
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.