RSA Decryption from Simple Public Key Values

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'?

Answer 1

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\cdot 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 $\varphi(18209)=130\cdot138=17940$.

The private key $d$ suffices the following equation

$b\cdot d\equiv 1\mod\varphi(n)$.

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

$1=x\cdot b+y\cdot\varphi(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

$m^d\mod n$