0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If you're literally only interested in solving $3001d\equiv 1\bmod18209$, there are only 18209 possibilities for $d$. A for loop will find the right one in milliseconds. $\endgroup$ – David Richerby Apr 1 '15 at 10:20
3
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Yeah I came to the same conclusion shortly after asking and I forgot to come back to update this question. $\endgroup$ – KrispyK Apr 2 '15 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.