# How to find a modulo inverse

### What happens

Hi! I am working on a CTF crypto challenge and I’ve found the source code of an asymmetric encryption implementation. The generation of both the private and public keys are based on large random numbers. I am trying to figure out how to “clear the unknown value” within the encrypting function in order to discover the original message.

### What do you understand or find about that problem

The encryption function is simple, it consists of the following formula: c = (m * f) % h where c, f and h are known values, my aim is to get “m” (the original message). I know that it would not be possible to find it through the decryption function as there is another variable missing (the private key).

### You make any workaround? What did you do?

I have tried to generate m by “reversing” the function in order to clear it. So the resulting function is: m = nh +c/f where h is a variable factor that essentially produces the same number, as in modular arithmetic this nh is going to give the same results. So, I have tried to take n = 0 and increase it but it does not work because when I pass this message through the encryption function again, it generates a different number than the original c (the encrypted one)

### (Optional) Why fails your workaround?

I think this could be a precision error because the numbers used in the keys and in the message are very large and the division followed by the multiplication used in the made-up decryption function and in the original encryption one may throw unexpected results that differ a lot. I have tried with modulo calculators, floor, ceiling functions, truncation and other techniques without success.

### Evidences

Different results in one of the python implementations I’m working on:

Source code of original asymmetric encryption implementation:

### I need help with

I would like to know if this is the right path that I should take in order to solve this challenge or if I should try to think of another way of approximation. Thanks in advance for any advice!