Как написать функцию расшифровки этого алгоритма?

Question

[Dmitry81923]

Есть такая вот функция для шифрования каждых двух байтов на С:

// state = два байта из файла
for (r = 0; r < 34567890; r = r + 1) {
            state = state ^ 27569;
            state = state * -1635 - 16196;
            state = state * 31663;
            state = state + 14122;
            state = state * 25561;
            state = state ^ 17548;
            state = state * 18199 - 11258;
            state = state * 21727;
        } // (для удобства разбил действия на строки)

Нужно написать функцию расшифровку.
Пробовал много разных способов - умножение заменить на деление, минус на плюс и вверх ногами перевернуть - не получается...
UPD: в алгоритме скорее всего переполнение

Comments

[Vindicar]

Покажи свой код для начала.
А вообще посоветую полностью разбить на отдельные операции.

for (r = 0; r < 34567890; r = r + 1) {
            state ^= 27569;
            state *= -1635;
            state -= 16196;
            state *= 31663;
            state += 14122;
            state *=  25561;
            state ^= 17548;
            state *= 18199; 
            state -= 11258;
            state *= 21727;
        }

И учти, что для xor обратная операция - тот же самый xor.

[Dmitry81923]

Vindicar,
Вот так последний раз пробовал:

state = state / 21727;
            state = state / 18199 - 11258;
            state = state ^ 17548;
            state = state / 25561;
            state = state - 14122;
            state = state / 31663;
            state = state / -1635 - 16196;
            state = state ^ 27569;

[Василий Дёмин]

Все операции обратимы, другой вопрос, что может произойти переполнение и, судя по условию цикла, оно таки происходит. В таком случае обратить уже ничего не выйдет

[calculator212]

Сначала зашифруйте с 1 шагом и расшифруйте, потом с 2 шагами и тд., и зачем вам нужен цикл на 34567890 операций, тут большая вероятность что просто переполнение произошло и всё как упоминали выше.

[Wataru]

Dmitry81923, Василий Дёмин, переполнение - это взятие по модулю 2^16. У нечетных чисел есть обратные по этому модулю. Все обратимо.

[MaxKozlov]

Dmitry81923,

state = state / 21727;
state = state / 18199 - 11258;

А вам не кажется, что это не соответствует обратным действиям для

state *= 18199;
state -= 11258;
state *= 21727;

?

[profesor08]

Dmitry81923 оригинал кода в студию, вполне возможно код разбит на шаги не верно, из-за чего не сходится.

[Dmitry81923]

profesor08, MaxKozlov,
(Дублирую)
Текст: "AAA BBB CCC DDD AAA"
Зашифровано: 09d3 30d3 10b0 8eb0 47d5 ecd5 474a 734a 09d3 3ad3
Функция зашифровки:

for (round = 0; round < 0x20f76d2; round = round + 1) {
            state ^= 27569;
            state *= -1635;
            state -= 16196;
            state *= 31663;
            state += 14122;
            state *=  25561;
            state ^= 17548;
            state *= 18199; 
            state -= 11258;
            state *= 21727;
        }

Но когда пытаюсь расшифровать вот так:

for (round = 0; round < 0x20f76d2; round = round + 1) {
            state /= 21727;
            state += 11258;
            state /= 18199;
            state ^= 17548;
            state /= 25561;
            state -= 14122;
            state /= 31663;
            state += 16196;
            state /= -1635;
            state ^= 27569;
        }

Получаю вот это: 9446 9446 9446 9446 9446 9446 9446 9446 9446 9446

[profesor08]

Dmitry81923, это не функция зашифровки, это лишь небольшой кусочек функции/программы.

[Dmitry81923]

profesor08, Нет, это функция зашифровки.
Каждые два байта (state = два байта из файла) в файле проходят вот таким циклом.

[profesor08]

Dmitry81923, нет, это не функция зашифровки, это просто какой-то цикл, который работает с какими-то данными, которые непонятно откуда и каким образом берутся.

[Dmitry81923]

profesor08, Эти данные берутся из файла. Читаются через fread.
Вот полностью цикл (arg1 это и есть текст прочитанный из файла, arg3 - это хендл FILE* выходного зашифрованного файла):

for (i = 0; i < length >> 1; i = i + 1) {
        state = *(unsigned short *)((int64_t)arg1 + i * 2);
        for (round = 0; round < 0x20f76d2; round = round + 1) {
            state ^= 27569;
            state *= -1635;
            state -= 16196;
            state *= 31663;
            state += 14122;
            state *=  25561;
            state ^= 17548;
            state *= 18199; 
            state -= 11258;
            state *= 21727;
        }
        *(unsigned short *)((int64_t)arg1 + i * 2) = state;
        fwrite((void *)((int64_t)arg1 + i * 2), 2, 1, arg3); // Записываются данные в (filename).encrypted
        fflush(arg3);
    }

[profesor08]

Dmitry81923, в чем сложность показать рабочий код? Он не секретный. Ценности в нем ноль. Но это исключит любые предположения и любое гадание.

[Dmitry81923]

profesor08, Господи, да это и есть рабочий код.
Смотрите, в arg1 заносите текст:
char* arg1 = "123123123123";
В length - длину:int length = strlen(arg1);
В arg3 заносите хендл выходного файла:FILE* arg1 = fopen("file.encrypted", "wb");

Запускаете алгоритм и всё работает!

[profesor08]

Dmitry81923, даже не скомпилируется

[Dmitry81923]

profesor08, У меня всё компилируется. Код точь-в-точь такой. Это я из декомпилятора взял, компилирую GCC. Всё отлично. Вы зачем флудите тут я не пойму?

[Василий Дёмин]

Wataru, Всё так, надо будет восполнить свои пробелы в математике. Прочитал ссылку, которую вы в своём ответе скинули, и написал дешифратор.

[Wataru]

Dmitry81923, Позвольте прокоментировать. Ваш код очень плох. Никогда не надо работать с адресами через int64_t. Это непереносимо, разные версии компиляторов и уровни оптимизации могут вам все сломать.

Погуглите про "арифметику указателей" в C. К char* можно прямо прибавлять 1, не надо его для этого приводить к int64_t.

Далее, ваш метод прочитать 2 байта из arg1 - вот так вот просто читая unsigned int по какому-то адресу - это тоже неправильно. Или делайте memcpy, или вручную через сдвиги и битовые операции:

unsigned int b1 = *text++;
  unsigned int b2 = *text++;
  state = (b1 << 8) | b2;

То, что ваш код компилируется и работает на вашей машине вот сейчас - не гарантирует, что он сработает где-то еще. Может там версия компилятора другая, или настройки другие (уровень оптимизации особенно).

Ну и далее, названия arg1, arg3 - это очень и очень плохо. Вы там сами не путаетесь? Я понимаю в условиях соревнования, когда код надо писать быстрее называть переменные text, t, n, i, a. Это тоже не очень хорошо, но хоть устаявшиеся нормы есть (a - массив входных чисел, t - текст, n - количество входных чисел, i, j - индексы).

Answer 1

[Wataru]

Нужно обратить все операции и делать их задом наперед.

Шифрование делает 34567890 итераций, вам надо сделать столько же. Внутри порядок операций надо развернуть, чтобы отмены выполнялись в обратном порядке. Если в строке 2 операции, например умножение и вычитание, то сначала надо выполнить обратное к вычитанию и только потом обратное к умножению.

Обратные к вычитанию и сложению - сложение и вычитание соответственно. Если шифрование прибавляет 12345, то вам надо 12345 вычитать в дешифраторе. Побитовое исключающее ИЛИ обратно само себе, ведь если его применить 2 раза, то получится исходное число.

С умножением все гораздо сложнее. Я предполагаю, что тип state - unsigned int. Если он знаковый, то умножение с переполнением - это undefined behavior вообще. В безнаковых целых умножение с переполнением есть просто умножение и взятие по модулую 2^32. Т.е вам нужно найти операцию, обратную умножению по модулю 2^32.

Это будет умножение на обратное по модулю.

Для его нахождения вам надо будет использовать расширенный алгоритм эвклида (в статье по ссылке выше оно расписано). Его можно или реализовать отдельно для нахождения обратных к 31663 (и другим множителям). Или можно его руками на бумажке прогнать.

Отдельно вам надо разобратсья с отрицательным множителем. Вам надо найти положительный множитель, который будет давать точно такой же результат шифрования. Подсказка.

Edit, только заметил в вопросе, что state - двубайтовый. Значит, все происходит по модулю 2^16.

Comments

[Dmitry81923]

Это я понял, что нужно всё обратно сделать. Но там происходит переполнение, из-за чего восстановить не получается. Всё, что я пробовал - не работает...

[Wataru]

Dmitry81923, Вот вам сильно упрощенный пример. Пусть это у вас 4 бита. Умножение по модулю 16.

Так вот, обратное к умножению на 3 - умножение на 11.

5 * 3 % 16 = 15
15 * 11 % 16 = 165 % 16 = 5

8 * 3 % 16 = 24 % 16 = 8
8 * 11 % 16 = 88 % 16 = (5*16 + 8) % 16 = 8

11 * 3 % 16 = 33 % 16 = 1
1 * 11 % 16 = 1.

Вот - если бы шифрование состояло только из state = state * 3, (а state был 4-битный), то в расшифровке было бы просто домножение на 11.

[Василий Дёмин]

Dmitry81923 Почитал статью по ссылке, смог написать рабочий дешифратор. Интересная задачка оказалась

void decrypt(char *str, size_t len) {
    for(size_t i = 0; i < len; i += 2) {
        uint16_t state = *(uint16_t*)&str[i];
        for (size_t r = 0; r < 34567890; r++) {
            state *= 26399;
            state += 11258;
            state *= 24743;
            state ^= 17548;
            state *= 60521;
            state -= 14122;
            state *= 47951;
            state += 16196;
            state *= 21685;
            state ^= 27569;
        }
        *(uint16_t*)&str[i] = state;
    }
}

[Dmitry81923]

Василий Дёмин, Спасибо!

[Dmitry81923]

Василий Дёмин, Я по ссылкам перешёл, но всё равно не понял, откуда взялись 26399 вместо 27569 и т.д? Можно кратко и простыми словами, пожалуйста?

[Wataru]

Dmitry81923, Вот, допустим, мы работаем с вещественными числами. Чтобы отменить умножение на 2 надо поделить на 2. Но как вообще определить деление? Математики определили его как домножение на обратное - на 0.5. 2*0.5=1. Точно так же 5*0.2 = 1 и поэтому для отмены умножения на 5 надо домножить на 0.2. А для отмены умножения на 3 надо домножить на 0.3333... Пока понятно?

Это было среди вещественных чисел. Но у вас-то в программе операции среди целых чисел помодулю 65536. Потому что state 16-битный и переполнение просто обрезает старшие биты. Те же самые числа можно получать, если перемножать в 32-битные и брать остаток от деления на 65536 (на самом деле процессор скорее всего так и работает).

Обратите внимание, в группе по модулю сложение и умножение работают похоже на обычные числа. Но вот деление - совсем нет. Потому что тупо не все числа можно делить по обычным школьным правилам. Вот как поделить 3 на 27569 и получить целое число в 16 бит? По школьным правилам оно тупо не делится. А из математики груп получается, что операция должна быть применима ко всем членам группы. Надо придумать такое "деление", что бы любое число от 0 до 65535 можно было "поделить".

Так вот, вам надо почитать про группы, операции по модулю и потом ссылку в ответе про "обратные по модулю".

И вот так получается, что у некоторых чисел есть обратные по модулю. 26399*27569 = 1 (mod 65536). Напишите программу, которая эти два числа перемножит в 16-битных. Получите 1. Точно так же, как 2*0.5 = 1 среди вещественных чисел, по модулю 65536 эти два числа обратны к друг другу.
Поэтому можно домножить на обратное, чтобы отменить домножение:
(x*26399)*27569 = x*(26399*27569) = x*1 = x (mod 65536).
Найти эти обратные можно, например, с помощью расширенного алгоритма эвклида.

Обратимы все множители, взаимнопростые (не имеющие общих делителей) с модулем. В вашем случае - нечетные, потому что модуль - степень двойки.

[Dmitry81923]

Wataru, Теперь понял. Спасибо!
А есть какой-то сайт, который эти числа может находить? Вы написали, что расширенный алгоритм Эвклида, но на сайтах по этому алгоритму мне выдавало только 15.
Или самому писать? Вроде не сложно

[Wataru]

Dmitry81923, Вряд ли есть сайты. Но не надо самому писать. Там по ссылке даже код есть с объяснением.

Но вообще, если оно вам не понятно, то можно проще. Вам же всего один раз обратные найти, можно сделать более медленным методом. Для каждого множителя A просто переберите все числа X от 0 до 65535 в цикле. Найдите то единственное, при котором A*X == 1:

uint16_t a = 26399;
    uint16_t x = 0;
    while(true) {
        uint16_t t = a;
        t *= x;
        if (t == 1) {
            cout << x << "\n";
            break;
        } 
        ++x;
    };

[Dmitry81923]

Wataru, Да, я так уже и сделал. Написал банальную программку, теперь буду держать её у себя. Раньше тоже писал алгоритмы шифрования, но не знал, что можно так даже с переполнением расшифровывать. Спасибо ещё раз

Answer 2

[Vindicar]

А не факт что это вообще обратимо, так как при умножении на 31663 гарантированно произойдёт переполнение 16-разрядного целого, и старшие разряды будут потеряны.

Можешь попробовать так, конечно: создай массив всех возможных 16-разрядных чисел: 0, 1, 2, ..., 65535.
Затем каждый элемент этого массива зашифруй этим алгоритмом.
Если в полученном массиве какие-то элементы повторяются, то полностью обратить операцию невозможно - только частично, только для уникальных элементов в массиве.
Если же все элементы массива уникальны, то можно обратить операцию, просто определив индекс входной пары байт в этом массиве. Этот индекс и будет исходным значением. Тут уже есть простор для оптимизации.

Comments

[Dmitry81923]

Спасибо. Действительно в зашифрованном варианте очень много элементов повторяются. Я так и дума, что алгоритм сломан

[Vindicar]

Dmitry81923, я вообще подозреваю что это не алгоритм шифрования, а что-то типа хэш-суммы.
Ну и да, повторы проверяй не в зашифрованном файле, а в массиве который я описал. Может, у тебя в исходном файле тоже были повторы. =)

[Wataru]

Dmitry81923, Вроде как джомножение идет только на нечетные числа. А значит там все обратимо. Перепроверьте ваш код, результаты для разных чисел не должны повторяться.

[Dmitry81923]

Vindicar, Wataru, Василий Дёмин,
Я вот зашифровал, вроде повторов нет:
Текст: "AAA BBB CCC DDD AAA"
Зашифровано: 09d3 30d3 10b0 8eb0 47d5 ecd5 474a 734a 09d3 3ad3
Функция зашифровки:

for (round = 0; round < 0x20f76d2; round = round + 1) {
            state ^= 27569;
            state *= -1635;
            state -= 16196;
            state *= 31663;
            state += 14122;
            state *=  25561;
            state ^= 17548;
            state *= 18199; 
            state -= 11258;
            state *= 21727;
        }

Но когда пытаюсь расшифровать вот так:

for (round = 0; round < 0x20f76d2; round = round + 1) {
            state /= 21727;
            state += 11258;
            state /= 18199;
            state ^= 17548;
            state /= 25561;
            state -= 14122;
            state /= 31663;
            state += 16196;
            state /= -1635;
            state ^= 27569;
        }

Получаю вот это: 9446 9446 9446 9446 9446 9446 9446 9446 9446 9446

Почему? Должно же работать..

[Vindicar]

Dmitry81923, попробуй построить lookup-таблицу, как я советовал.

[Wataru]

Dmitry81923, Потому что деление нацело не является обратной операцией по модулю. Обратной операцией является домножение на обратное по модулю (это самое обратное можно найти расширенным алгоритмом евклида).

[Dmitry81923]

Wataru, Не совсем понимаю, что нужно сделать

[Wataru]

Dmitry81923, Прочитали мой ответ? Прочитали ссылку на обратне по модулю?

Понимаете, что значит "по модулю"?
Вы, вроде, понимаете, что вам надо обратить операции. Если в шифраторе стоит +65530, то в дешифраторе будет -65530, что то же самое, что +6 (потому что по модулю же все). Т.е. чтобы обратить прибавление 65530 вам надо прибавить обратное относилельно сложения.

Чтобы обратить умножение - вам надо домножить на обратное относительно умножения. Что бы найти конкретные множители вам надо пройтись по ссылке, написать расширенный алгоритм эвклида, и скормить ему все множители из вашего шифратора. Выданные алгоритмом числа и надо использовать в качестве множителей в дешифраторе.

[MaxKozlov]

Так, для информации. Все числа, на которые state домножается - простые
даже *-1635, из-за переполнения эквивалентен *63901
если таки предположить что state - 16bit signed
который просто в финале, видимо, кастуется в unsigned

[Wataru]

MaxKozlov, если он signed, то там undefined behavior при перепрлнении. А так, важно, что множители взаимнопросты с модулем (65536). Обратимо было бы даже если бы они не были простыми, а просто нечетными.