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

Question

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

Answer 1

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$.