I've read a lot about this subject, about Euclidean algorithm, and I have all references needed for this subject right here:
(Best source for my question) -> Math Explanation
Another great example -> Math Explanation 2
Wiki -> Extended Euclidean
Great answer for adding values -> Add Operation
This is where I completely lost it -> AFFINE CIPHERS
However, out of all these sources, I'm still failing to understand how to implement it by code (or pseudo code), or at least find the way to write it.
So I'll write the basics, let's assume I have this formula:
(x * key) % mod = result
0 <= X <= mod
0 <= key <= mod
0 <= result<= mod
key and mod are constants.
* means multiplication operation
% means remainder operation (edited to clarify)
x and result are dynamic.
I want to create a formula that will give me x through code in Java.
The function that calculates result for me is:
private int MultModulus(int num, int key, int mod)
{
return (num * key) % mod;
}
how can I find X? what should I write in order to calculate it? this is the point where I didn't understand, let's assume that my function signature would be:
private int InverseMultModulus(int result, int key, int mod)
{
x = ...
return x;
}
If, as described in comments on @ergonaut's answer, you need to be able to solve this problem only for a relatively small number of original values x, and a relatively small value of mod, then one reasonable approach would be to build a decoding table in advance: perform the forward computation on every possible x, and record the starting x in an array, indexed on the result. Then you can perform a simple array lookup to get an x for each result. That will certainly outperform computing x separately for each value in a long enough sequence of values (i.e. the characters in a long enough enciphered message). Of course, if you're doing this in the spirit of a Vignere cipher, i.e. with a multibyte key, then that will multiply the input length required for pre-computing a decoding table to be a win.
Do be aware, however, that using the function you describe to define a viable cipher depends on every valid input value yielding a distinct result. As we already discussed, however, some combinations of key and mod afford duplicate results. Moreover, if the space of possible result values is the same size as the space of possible input values, then you must choose a combination of key and mod that results in all possible result values being used, else you cannot avoid duplicates.
If you want to encipher bytes as bytes, and if you want to be able to handle general files, then the only possible mod is 256. If you choose a smaller one, then there has to be at least one pair of input bytes that map to the same cipherbyte. On the other hand, if you choose a larger mod then the range of result values cannot be mapped 1:1 into the range of type byte. You must furthermore be certain to choose keys that are relatively prime with 256, but that's easy: since 256 is a power of 2, any odd key will do. As long as you choose such a key, no two input values in any range of 256 consecutive integers will map to the same result.