Обратный оператор умножения в С++
Я пытаюсь отменить десериализатор приложения, и я в основном закончил, но я застрял в этой проблеме. Приложение по какой-то причине декодирует 4-байтовые числа, умножая их на ключ кодирования (или ключ декодирования, если на то пошло).
int decoded_number = (encode_key * encoded_number);
Это работает для декодирования их номеров, однако меня больше интересует кодирование чисел, поэтому я могу сериализовать данные. Я попытался закодировать число, умножив декодированное число на ключ кодирования.
int encoded_number = (encode_key * decoded_number);
Однако, когда я сравниваю его с исходным закодированным числом, оно совершенно другое. Я также попытался закодировать число методом грубой силы, и это работает, но для генерации числа требуется вечность, что невозможно при сериализации большого количества чисел.
for (int i = INT_MIN; i < INT_MAX; i++){
if (i * encode_key == decoded_number)
return i; /* "i" is the encoded number */
}
На данный момент я понятия не имею, что еще попробовать. Мой код ниже:
#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;
}
Сама концепция должна работать на C, а не только на C++.
Обратите внимание, что если бы (encode_key * encoded_number) переполнился во время хэширования, это было бы неопределенным поведением (может быть, это не было сделано в С++?). То же самое верно и для ваших попыток обратить хэш. Редактировать: Итак, если encode_key больше 1, i * encode_key == decoded_number имеет неопределенное поведение.
@Barmar результат умножения превышает ограничение в 4 байта, поэтому деление в этом случае не сработает.
@JanaSchweizer В С++ для интегральных типов signed это так. Поскольку любой результат умножения, который будет переполняться, в любом случае не определен. Изменить. Если вы хотите реализовать некоторую форму умножения по модулю с целыми числами signed, вам сначала нужно решить, как вы хотите, чтобы оно работало, а затем реализовать его самостоятельно.
@JanaSchweizer Тогда умножение приводит к неопределенному поведению. Вам нужно использовать unsigned int, если вы хотите модульную арифметику.
также encode_key * i будет переполняться в вашем цикле (фактически для большинства значений i)
Модульное умножение не может быть легко инвертировано. См. модульное деление
@FrançoisAndrieux Я действительно просто ищу почти мгновенный способ воссоздать аналогичный encoded_number без грубой силы, потому что существует множество различных комбинаций от INT_MIN до INT_MAX, которые можно использовать.
Как правило, хэши являются односторонними операциями и не могут быть однозначно отменены.
не в том ли весь смысл шифрования, что трудно вычислить обратное?
@EricPostpischil Чтобы узнать больше, я пытаюсь создать данные сохранения для приложения. Ничего со зла.
@Barmar А, моя ошибка. Я пытаюсь сериализовать данные, а не хэш. :)
Зачем вам использовать умножение на ключ кодирования при сериализации?
Из того, что я собрал до сих пор, я полагаю, что он там для защиты данных сохранения, поэтому вам нужен ключ, чтобы прочитать его. Однако мне сказали, что сериализатор был выпущен где-то в Интернете, но он не обновлен. В любом случае, действительно трудно претендовать на умножение как на собственный алгоритм кодирования. @Бармар
Мультипликативная инверсия -381784151 по модулю 2^32 равна 491758745. Это означает, что если y является результатом умножения x на -381784151 и взятия младших 32 битов результата, то умножение y на 491758745 и взятие младших 32 битов результата результат дает х. (Эта арифметика обычно выполняется с целыми числами без знака. Если вы используете целые числа со знаком, вы должны убедиться, что они переносятся по модулю 2^32. C и C++ не определяют поведение переполнения целых чисел со знаком.)
@Barmar: модульное умножение либо можно инвертировать (информация не теряется), либо нельзя (информация теряется). Если можно, то легко. Метод нахождения мультипликативного обратного является простым расширением алгоритма Евклида и требует всего несколько строк кода.
@EricPostpischil Я признаю, что на самом деле я не специалист по математике, я думал, что уникального результата может не быть. Но я же дал ссылку на сайт с кодом.
Ответы 1
Спасибо @EricPostpischil за отличный ответ. Чтобы обратить умножение, все, что вам нужно сделать, это умножить декодированное число на мультипликативное значение, обратное ключу. Вот пример кода с решением.
#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;
}
Обратным умножению является деление.