I\'m a little stuck trying to figure out how to decrypt some messages and could

Question

I'm a little stuck trying to figure out how to decrypt some messages and could use some hints as to what I may be doing wrong.

I was given a series of integer values that make up my cipher text. Here are just a few of them:

6584 15650 16198 11003

I was given the following public key b = 3001 n = 18209

So to encrypt a message M, you would use the formula:

C = M^3001 mod 18209

I understand to encrypt, I need to find a 'd' value that satisfies:

bd = 1 mod 18209

3001d = 1 mod 18209

Any hints on a technique or algorithm to help me find a suitable value for 'd'?

Explanation / Answer

If you want to decode a message encoded with RSA, you need to get the private key. The "simplest" method is to find the primes p,q with n=p?q.

In your case, n=18209 is the product of the primes 131 and 139. Now, you can follow the value of Euler's phi function for n, which is ?(18209)=130?138=17940.

The private key d suffices the following equation

b?d?1mod?(n).

To get d with this property, you can use the extended euclidean algorithm for b and ?(n), which produces x and y with

1=x?b+y??(n)

Now, the value x is your private key d. In your case, I get d=4621. To finally decode the message m, you have to compute

mdmodn

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.