CODEWITHSUNDEEP
encryptionrsa
Ismaeel Ali
Ismaeel Ali

Reputation: 57

How to decrypt an RSA encryption?

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.

Upvotes: 1

Views: 19960

Answers (1)

kyrill
kyrill

Reputation: 1056

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.

Upvotes: 3

Related Questions