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!