Когда я впервые заинтересовался шифрованием, я знал о шифрах только то, что в них время от времени находят уязвимости. Чтобы хоть как-то разобраться в этой теме без наставника, специальной литературы и (поначалу) без доступа к интернету, я решил проводить опыты над самодельным шифром. Одни идеи сменялись другими, а новые знания из разных источников заставляли многое пересматривать снова и снова. Шифр многократно менялся, пока не приобрёл более-менее стабильные черты. Целью же данной статьи является описание истории создания этого шифра и реализованных в нём принципов, а также выставить на суд читателю полученный результат.
Первые опыты
В самом начале было понимание, что в хорошем шифре недостаточно просто заменить по таблице один байт другим и что нужно что-то посложнее. Например, заменить значение шифруемого байта результатом некоторого вычисления над самим собой, соседним байтом и одним из байтов ключа. А потом ещё «перемешать» байты, выбирая пары индексов и обменивая значения байтов по этим индексам. Позже мне попалось утверждение, что «замены и перестановки являются основой хорошего шифра». Похоже, начало пути выбрано правильно.
Если выполнять перестановки, то шифруемые данные нужно разбивать на блоки, внутри которых эти перестановки и будут происходить. А если блок неполный? Тогда можно шифровать столько байтов, сколько имеется в блоке, и не обменивать с байтами, которые выходят за пределы неполного блока (позже я от этого подхода отказался, а пока просто описываю как историю). Полный же блок имеет длину, равную длине ключа, чтобы для каждого байта блока был свой байт ключа.
Какой длины брать ключ? Интуитивно казалось, что лучше взять ключ большей длины (позже я узнал, что это не всегда на пользу), а ещё лучше брать несколько ключей: один для замен, второй для перестановок, а байты третьего просто прибавлять к байтам блока. Для усложнения возможного взлома было решено изменять эти ключи перед или после шифрования каждого блока, а функция изменения пригодилась также для первичной генерации ключа по паролю пользователя. И полученный алгоритм я для себя назвал ESCK (от Encrypting System with Changing Keys — Шифрующая Система с Меняющимися Ключами).
Нужно также упомянуть, что быстро пришло понимание: замены и перестановки в блоке должны несколько раз чередоваться. Сначала я взял 3 повтора, но смутно подозревал, что этого мало. А сколько надо? Я не знал и потому разместил повторы внутри тела цикла for, а количество повторов задавал переменной Cycles, которую можно было выбирать самостоятельно. Благо у меня изначально не было раундовых ключей и каждый раунд (повтор цикла) был вполне самодостаточным.
Дальнейшее развитие
Поиграв немного с вариантами реализации изменения ключей, я начал ловить себя на мысли, что три отдельных ключа неудобны для шифрования, а функция их изменения слишком громоздкая. Также напрягала необходимость постоянно менять ключи при переходе от блока к блоку. Нельзя ли как-то обойтись одним ключом и сделать его изменение необязательным? И почему бы заодно не отказаться от побайтной обработки в пользу 32-битных операций, которые эффективнее на современных платформах?
Идея для новой версии шифра была следующая. Раньше на шифрование каждого элемента блока влияли соседний с ним элемент и один элемент ключа, а потом всё в блоке перемешивалось по заранее вычисленным индексам. Теперь же все элементы блока должны оставаться на своих местах, а «перемешиваться» должны связи между ними — по индексам, вычисляемым прямо в процессе шифрования. То есть, в каждой итерации цикла для каждого элемента блока нужно вычислить несколько индексов, по которым будут взяты другие элементы блока и ключа, и по ним будет шифроваться текущий.
Если индексы вычислять одним 32-битным числом, то это число удобно разбивать на четыре 8-битных индекса. Каждый подобный индекс может иметь 256 возможных значений, поэтому казалось логичным принять блок и ключ по 256 элементов. Взятые по вычисленным индексам 4 элемента блока или ключа с помощью операций AND, OR, NOT, XOR и циклических сдвигов преобразовывают текущий элемент блока. Для неполного блока принимаются меры, чтобы элементы за пределами фактического размера не участвовали в шифровании.
Изменение одного ключа вместо трёх теперь тоже стало проще и было реализовано похожим на шифрование блока способом, только в нём вместо элементов блока шифруются сами элементы ключа. Чтобы изменение ключа сделать опциональным, я стал запускать его функцию только при установке соответствующего флага. И по-прежнему с участием этой функции генерировал ключ по введённому паролю.
Доработки и улучшения
32-битная версия мне понравилась, но ненадолго. А если попробовать 64-битную и получать 8 индексов вместо 4? В 32-битной версии я брал 4 элемента блока или ключа, но каждый из них применял несколько раз из-за операций AND и OR (в них изменения отдельных битов могут не повлиять на результат). Значит, в 64-битной версии можно брать 8 элементов, но применять каждый из них однократно, исключив операции AND и OR, оставив XOR, NOT, сложения и сдвиги.
Поскольку я отказался от побайтного шифрования, то зачем теперь блок плавающей длины (его всё равно выравнивать по размеру 64-битного элемента)? Проще взять блок с фиксированным количеством элементов (например, 2) и полностью отказаться от проверок выхода за пределы фактического размера. По индексам теперь брать только элементы ключа, а соседнее число в блоке должно влиять только на вычисление индексов. И похоже, что так достигается неплохой лавинный эффект, если все элементы ключа разные.
Чего не хватает? Например, участия номера цикла (итерации, раунда) в шифровании, чтобы избежать блоков, которые остаются неизменными после каждой отдельной итерации. Также можно включить в шифрование зависимость от опционального номера блока, чтобы разные блоки шифровать по-разному. И да, величины циклических сдвигов можно сделать разными, а не одинаковыми (я подбирал их так, чтобы эти величины не совпадали между собой, а их последовательное сложение по модулю 64 не давало сумму, равную любой отдельной величине).
Что получилось?
После исключения всех громоздких частей, проверок и ветвлений шифрование свелось к следующему: на основе соседнего элемента в блоке вычислить 8 индексов внутри одной адресной переменной Adr, взять по ним элементы ключа K и с помощью операций XOR, NOT, сложений и сдвигов модифицировать текущий элемент блока M. И так элемент за элементом, раунд за раундом. Как это реализовано в функции EncryptBlock(), показано ниже:
void ESCK7::EncryptBlock(uint64_t* M, const uint64_t* K, int Cycles,uint64_t BlNum){// исключение в случае нулевого указателяif (M == nullptr || K == nullptr)throw std::invalid_argument("Нулевой указатель на блок или ключ");// многоцикличное шифрованиеfor (int C = 1; C <= Cycles; C++){// основной цикл шифрованияfor (int i = 0; i < 2; i++){// копирование текущего Muint64_t Mi = M[i];// вычисление адресной переменнойuint64_t Adr = ROL64(M[(i + 1) & 1] + BlNum, 37);Adr = ROL64(Adr + K[Adr & 0xff], 43);// последовательное преобразование MiMi += ROL64(~Adr + M[(i + 1) & 1], 15);Mi += ROL64(K[Adr & 0xff], 11); Adr >>= 8;Mi += ROL64(K[Adr & 0xff], 26); Adr >>= 8;Mi += ~ROL64(K[Adr & 0xff], 10); Adr >>= 8;Mi = ROL64(Mi, 39) ^ (~K[Adr & 0xff]); Adr >>= 8;Mi += ROL64(K[Adr & 0xff], 25); Adr >>= 8;Mi += ROL64(K[Adr & 0xff], 3); Adr >>= 8;Mi += ROL64(~K[Adr & 0xff], 29); Adr >>= 8;Mi = ROL64(Mi ^ K[Adr & 0xff], 54) + C;// возврат Mi в рабочий массивM[i] = Mi;}}}
Функцию изменения ключа приводить не буду, поскольку она очень похожа на EncryptBlock(), только в ней изменяются элементы самого ключа, а не блока (и на всякий случай взяты другие величины сдвигов). Реализованную генерацию ключа тоже описывать не буду, поскольку ключ можно генерировать сторонними алгоритмами. Но для желающих ознакомиться с полной реализацией текущей версии шифра исходный код на C++ доступен на GitFlic. Предыдущие версии (на Free Pascal) также доступны в архиве.
И это ещё не всё. В качестве эксперимента был создан ещё один алгоритм, в котором вместо ключа K применяется заданная таблица констант T, а ключ Key (одинакового с блоком размера) вместе с соседом по блоку участвует в вычислении адресной переменной Adr. Исходный код этого шифра также доступен на GitFlic.
Эксперименты и взломы
Признаюсь, я уже писал статью об этих шифрах, но приводил в ней много кода и мало пояснений. Также я не включил в ту статью важное упоминание: все константы в шифре и даже сама реализация не являются «железобетонными». Я пытался разобраться в шифровании и развивал идею шифра, а полученная в итоге реализация является лишь одной из возможных. Это значит, что любой желающий может создать собственную модификацию и экспериментировать с другими величинами сдвигов, другими способами вычисления адресной переменной, другим способом генерации ключа и так далее. Буду только рад, если у кого-то получится из этого что-то интересное.
О взломах. Я старался сделать хороший шифр, но делал как умел (в условиях ограниченных знаний). Я знаю, что зависящие от промежуточных состояний шифра динамические связи сложно анализировать, и потому они не приветствуются. С другой стороны, сложность анализа (предположительно) может помочь избежать взлома. Также в шифре есть заведомо слабые ключи (в которых все элементы равны между собой), но я исхожу из того, что вероятность их генерации пренебрежимо мала.
Как автору мне было бы интересно узнать о способах взлома полученного шифра. Существует ли возможность для произвольно взятого ключа восстановить сам ключ по некоторому количеству пар открытого и зашифрованного текста (при 10 и более циклах/раундах)? Или восстановить открытый текст без знания ключа? Сколько данных для этого нужно, какое количество операций будет затрачено и насколько это реализуемо технически? Эти вопросы пока остаются открытыми.
Заключение
В общем, хороший ли получился шифр или плохой, судить не мне. Я прошёл определённый путь опытов и исследований, развивал и проверял различные идеи и теперь просто делюсь результатами своей работы. А в качестве итогов статьи ещё раз сформулирую заложенные в шифр основные принципы:
-
неограниченное количество самодостаточных раундов шифрования без необходимости вычисления раундовых ключей;
-
простая логика шифрования: текущий элемент в блоке изменяется при участии нескольких элементов ключа, взятых по вычисленным индексам;
-
индексы вычисляются на основе соседнего в блоке элемента, который непредсказуемо меняется после каждого раунда;
-
для удобства вычислений индексы упакованы в одну 64-битную переменную;
-
для шифрования применяются только простые операции: XOR, NOT, сложения, сдвиги;
-
приведённая в статье реализация принципов не является единственно возможной и модификации допускаются и даже приветствуются (с осторожностью);
-
вопрос о возможности взлома остаётся открытым.
ссылка на оригинал статьи https://habr.com/ru/articles/1044174/