In (m mod n = x) how to find m when you know n and x?

940 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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)

2
On

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