Reversing multiplication operator in c++

Question

I am attempting to reverse an application's deserializer, and I'm mostly finished, but I'm stuck at this issue. The application, for whatever reason, decodes 4-byte numbers by multiplying it by an encode key (or decode key for that matter)

int decoded_number = (encode_key * encoded_number);

This works for decoding their numbers, however, I am more interested in encoding numbers, so I can serialize data. I have tried encoding the number by multiplying a decoded number with the encode key

int encoded_number = (encode_key * decoded_number);

However, when I compare it to the original encoded number, it's completely different. I have also attempted to bruteforce-encode the number, and it works, but takes forever to generate the number, which is not feasible when serializing lots of numbers.

for (int i = INT_MIN; i < INT_MAX; i++){
  if (i * encode_key == decoded_number)
    return i; /* "i" is the encoded number */
}

At this point, I have no idea what else to try. My code is below:

#include <iostream>
using namespace std;

int encode_key = -381784151; /* Key I took from the application */
int encoded_numbers[2] = {-810310503, 1520670208}; /* Numbers I took from the app */

int bruteforce(int decoded_number){
    for (int i = -2147483648; i < 2147483647; i++){ /* min and max int*/
        if (encode_key * i == decoded_number){ /* brute comparison */
            return i;
        }
    }
}

int main()
{
    for (int i = 0; i < 2; i++){
        int encoded_number = encoded_numbers[i];
        int decoded_number = encode_key * encoded_number;
        int attempt_encode = encode_key * decoded_number;
        int brute_encode = bruteforce(decoded_number);

        cout << "STARTING WITH NUMBER" << i+1 << "\n";
        cout << "Encoded Number: " << encoded_number << "\n";
        cout << "Decoded Number: " << decoded_number << "\n";
        cout << "Attempt to Re-Encode (FAIL): " << attempt_encode << "\n";
        cout << "Bruteforce Encode (SLOW!): " << brute_encode << "\n\n";
    }
    return 0;
}

Click here to run the code in your browser

Answer 1

Thanks to @EricPostpischil for a great answer. To reverse the multiplication, all you need to do is multiply the decoded number with the multiplicative inverse of key. Here is a code example featuring the solution.

#include <iostream>
using namespace std;

int encode_key = -381784151;
int encoded_numbers[2] = {-810310503, 1520670208};

int getinverse(int key){
    for (int i = -2147483648; i < 2147483647; i++){ /* min and max int*/
        if (key * i == 1){ /* brute comparison */
            return i;
        }
    }
}

int main()
{
    int inverse = getinverse(encode_key); /* Grab the multiplicative inverse of encode_key */

    for (int i = 0; i < 2; i++){
        int encoded_number = encoded_numbers[i];
        int decoded_number = encode_key * encoded_number;
        int attempt_encode = inverse * decoded_number; /* multiply inverse and decoded_number */

        cout << "STARTING WITH NUMBER" << i+1 << "\n";
        cout << "Encoded Number: " << encoded_number << "\n";
        cout << "Decoded Number: " << decoded_number << "\n";
        cout << "Attempt to Re-Encode (CORRECT!): " << attempt_encode << "\n\n";
    }
    return 0;
}