# How to solve the reverse of an equation that uses MOD?

I've been tasked with reverse engineering an unknown crypto function. The function uses the following constants:

• $a=380951$: I noticed that this is a prime number
• $b=3182$: I noted that this is a prime number + 1

The math function applied is as follows: $\mathrm{result}=((\mathrm{value} \bmod a) \cdot b) \bmod a$

The value is a 24 bit number, as is the result (obviously). The result is subsequently fed into a lookup table of which bits it represents. My plan is to find an efficient algorithm to determine what number $\mathrm{value}$ needs to be to achieve a desired $\mathrm{result}$. If this answer is not within the 24 bit limit, then retry with one of the others that result in the same answer through the lookup table data.

If someone can identify possible algorithm names then I can use that directly, I just can't figure out what this scheme is...

Here is an example:

1434758 becomes 83172 -> lookup table results in 0x37e5 (decrypted 2 bytes of data)

Better answer: 291905 becomes 83172 -> lookup table results in 0x37e5 (decrypted 2 bytes of data)

Lookup table: 7, 15, 23, 47, 93, 186, 372, 744, 1488, 2976, 5952, 11904, 23808, 47616, 95233, 190465

The algorithm used for that is if the result is >= the lookup table then the bit in that position is 1, its number is subtracted and we move to the next bit.

Does anyone recognize this routine?

Alternatively:

Let $x=((y \bmod 380951) \cdot 3182) \bmod 380951$.

How can I efficiently find $y$ given a value of $x$?

-

## 1 Answer

If $a$ is a prime number and you know $r$ and $b$, and want to solve $v$ given the equation $r = v*b\mod a$, all you have to do is to apply the extended Euclidean algorithm for finding the multiplicative inverse $b^{-1}\mod a$, and then calculate $v = r*b^{-1}\mod a$. Alternatively, you could apply Fermat's little theorem and calculate $v = r*b^{a-2}\mod a$.

-
Sadly I don't even have a method of calculating a number as large as 3182^(380951-2). I'm hoping to find a method shorter than calculating the approx 3000 possible multipliers. –  hsikcah Mar 2 '13 at 6:01
–  Thomas Mar 2 '13 at 6:20
Ok, so I implemented the modular exponentiation function using the right to left binary method. 3182^380949 mod 380951=200354 so 200354*83172 mod 380951 = 284246 not the 1434758 I was expecting. Any ideas where I've gone wrong? –  hsikcah Mar 3 '13 at 0:29
Incidentally through experimentation I have determined that 83172+380951*2438=928841710 then 928841710/3182=291905 then 291905 mod 380951 is 291905 so I suspect if I could somehow calculate the 2834 versus exhaustively searching for it then that could be workable solution. –  hsikcah Mar 3 '13 at 0:42
@hsikcah: You have r=83172, b=3182, a=380951. b**(a-2)=62135 mod a. So v=r*62135=291905 mod a, and v*b=83172=r mod a, as required. –  Mok-Kong Shen Mar 3 '13 at 10:59