0
$\begingroup$

So I'm doing some cryptography assignment and I'm dealing with a modular arithmetic in hexadecimal. Basically I have the values for $n$ and the remainder $x$, but I need to find the original number $m$, e.g.

$$m \mod 0x6e678181e5be3ef34ca7 = 0x3a22341b02ad1d53117b.$$

I just need a formula to calculate $m$.

Edit: ok, let's put it this way, $x = K^e \mod n$, I know the values for $x$, $e$ and $n$. Does that help?

Ok, I realized I was approaching the problem in a wrong way, basically I had the RSA public key and I should have used RSA problem to decrypt the file without having the private key. Sorry for the stupid question.

$\endgroup$
  • $\begingroup$ You need some hypotesis on $m$, otherwise the solution is not unique (in fact, there are infinite solutions) $\endgroup$ – Exodd Feb 28 '15 at 11:47
  • $\begingroup$ Basically, $x\equiv a\bmod m$ implies $x=a+mk$ for any integer $k$. This should generate all the solutions. $\endgroup$ – rah4927 Feb 28 '15 at 12:48
0
$\begingroup$

Unfortunately, I believe that there will be a set of infinite solutions unless specifying some conditions for the solutions.

Consider this example for clarity: 5 mod 2 = 1 ; 7 mod 2 = 1

You see why now? (You can make examples in Hexadecimal also to confirm this)

$\endgroup$
0
$\begingroup$

There are infinitely many solution for $m$ and you need additional information to determine its value.

$\endgroup$
  • $\begingroup$ ok, let's put it this way, (x = K^e mod n), I know the values for x, e and n. does that help? $\endgroup$ – Keivan Feb 28 '15 at 11:50
  • $\begingroup$ @Keivan Consider $x=1, n=p\in\mathbb P, e=p-1$. Then every single natural $K$ such that $p\not\mid K$ will satisfy your congruence. $\endgroup$ – user26486 Feb 28 '15 at 11:55

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.