[Из песочницы] Управляемый перестановочно-подстановочный шифр
Хочу поделиться с вами своей старой работой в области криптографии. Данный алгоритм был разработан в 2000 году совместно с Жуковым Алексеем Евгеньевичем. В данной статье представлен базвовый алгоритм. Частная его реализация получила название «Grinder». Интересующиеся могут скачать описание в PDF и консольное приложение. Статья представлена as is, в том виде, в котором она появилась в 2000 году. Если у кого-то возникнут проблемы с html версией, вот ссылка на PDF.Итак. Шифрование является, пожалуй, наиболее важным механизмом защиты информации от несанкционированного доступа. Поэтому от характеристик подсистемы шифрования (скорости, криптостойкости и др.) зависят характеристики системы защиты информации в целом. С развитием компьютерной техники, актуальной становится задача разработки универсальных программно-ориентированных шифров, параметры которых (длина ключа, размер обрабатываемого блока, количество циклов шифрования) легко варьировались бы в зависимости от конкретной задачи, для достижения максимальной производительности и требуемой защищенности. На сегодняшний день существует множество шифров. В качестве наиболее известных можно привести следующие: DES, ГОСТ 28147–89, IDEA, FEAL, BLOWFISH, RSA, PGP. Большинство алгоритмов работают с фиксированным размером блока, ключа и других параметров. Это не всегда удобно, так как накладывает некоторые ограничения при их применении. Так же ключ и подключи шифрования жестко заданы и не изменяются в процессе шифрования, а операции проводятся над блоком небольшого размера. Все это позволяет криптоаналитику использовать такие методы, как, например, дифференциальный и линейный криптоанализ для раскрытия информации и ключа.Предлагаемый шифр лишен многих из выше перечисленных недостатков. В основу положен принцип: «подключи после применения изменяются». Подключи изменяются в зависимости от шифруемого текста. Причем изменяется как текущий, так и следующий по порядку использования подключ, следовательно, уже на втором шифруемом блоке используется другой ключ шифрования. Одновременно может обрабатываться текст большого объема, размер которого сравним с размером оперативной памяти компьютера. Если размер шифруемой информации превышает размер оперативной памяти, то шифрование происходит по кускам. В процессе шифрования блоки текста переставляются псевдослучайным образом. Для изменения блоков текста используются дополнительные блоки, которые выбираются псевдослучайным образом из массива проинициализированного в начале работы алгоритма. Изначально массив заполняется любыми данными, например, текстом или псевдослучайной последовательностью. На размер блоков, которыми оперирует алгоритм, не накладываются ограничения. При изменении размера блока перемешивающая характеристика шифра практически не изменяется, а использование блоков большего размера существенно увеличивает скорость шифрования. На текущий момент оптимальным является размер 32 бита, который обеспечивает максимальную скорость работы шифра на 32-х разрядных системах.
Общая схема работы алгоритма
Открытый текст: 
n — число информационных блоков.My — текущий информационный блок. 0 ≤ y ≤ n-11÷N — число циклов шифрования, 1 ≤ i ≤ N
— ключ шифрования блока My на i-м цикле.
— вычисление подключа.
При вычислении 
считать 
При вычислении 
считать 
φ () — номер второго блока текста
— модифицированное 
Текущий блок текста и псевдослучайно выбранный изменяются и меняются местами: 
Функции 
при фиксированных значениях подчеркнутых аргументов являются подстановками на соответствующих множествах булевых векторов (т.е. обратимы). На основе предлагаемой схемы может быть построено множество алгоритмов, параметры которых будут зависеть от конкретных требований. Для достижения высокой скорости работы можно, например, упростить используемые функции, зафиксировать размер ключа, дополнительного массива и обрабатываемого текста, а для повышения криптостойкости наоборот — усложнить функции и увеличить число циклов шифрования. На предлагаемом принципе может быть построен и поточный шифр.
Общая схема поточного шифра
-изменение ключа шифрованияОбратимость 
не требуется.
— блок шифр-текстаа) Изменение блока текста: 
б) Другой вариант (более общий) преобразования текста, где F обратима при фиксации подчеркнутых переменных: 
Вариант алгоритма шифрования
Операции выполняются в порядке их следования.
— однократная инициализация дополнительного массива в зависимости от ключа шифрования.Обработка текста: 
— изменение текущего подключа в зависимости от текущего блока текста.
-изменение следующего по порядку подключа в зависимости от текущего подключа.
-изменение текущего подключа в зависимости от следующего по порядку использования подключа.
-циклический сдвиг следующего подключа вправо на количество разрядов, определяемое текущим подключом.
-циклический сдвиг текущего подключа вправо на количество разрядов, определяемое следующим подключом.Сложение текущего и псевдослучайно выбранного (в зависимости от текущего подключа) блока текста с блоком, псевдослучайно выбранным (в зависимости от текущего подключа) из дополнительного массива, циклический сдвиг вправо на количество разрядов, определяемое текущим подключом, и их взаимная перестановка: 
Где операция + это либо XOR, либо сложение по модулю 2n, где n — размер блоков в битах.
Тестирование
Алгоритм был реализован на языке Object Pascal в среде разработки приложений Delphi 3.0. для работы под управлением операционной системы Windows 9x или Windows NT. Реализованный вариант алгоритма был ориентирован на обеспечение высокой криптостойкости. Но даже в этом случае скорость алгоритма составила примерно 20 Мбит/сек для процессора Intel Celeron с тактовой частотой 374 МГц. Благодаря тому, что в алгоритме используются простые (быстрые) операции, возможно значительное увеличение скорости шифрования, путем упрощения используемых функций, при незначительной потере криптостойкости. Для определения характеристик алгоритма был проведен ряд основных тестов. Проверка равномерности распределения байтов шифр-текста производилась с помощью критерия согласия хи-квадрат К.Пирсона. Квантиль распределения 
: 
≈294. Можно принять гипотезу о том, что значения байтов равномерно распределены в том случае, если вычисленное значение окажется меньше 294. Проведенные тесты показали, что уже при двух циклах шифрования достигаются значения 256 и 274 для текстового и бинарного файла размером 1 Мб соответственно. Другой важной характеристикой является эффект размазывания. Проверялось изменение шифр-текта в зависимости от изменения 1 бита открытого текста или 1 бита ключа на любой позиции. В идеале должна измениться примерно половина битов шифр-текста. Тест показал »50% изменение. Тестировались данные различных типов. Не имеет значения позиция измененного бита. Имитостойкость проверялась путем определения влияния изменения одного бита шифр-текста на расшифрованный текст. Разница побитового сравнения файлов после расшифрования, в одном из которых был предварительно изменен 1 бит, составила 50%. Не имеет значения позиция измененного бита. Так как на блоки текста накладываются блоки, псевдослучайным образом выбранные из дополнительного массива, т.е. фактически гамма, необходимо проанализировать накладываемую последовательность. В работе [7] авторами были предложены пять основных, по их мнению, тестов для проверки псевдослучайных последовательностей. Тестировалась последовательность размером 3 Кбайта, т.е. 24000 бит, что удовлетворяет требованиям тестов. 1. Monobit testНазначение данного теста — определить, что количество нулевых и единичных значений битов в S примерно равное, как должно быть в случайной последовательности. Пусть n0, n1 — количество нулевых и единичных значений битов соответственно. Тогда оценочное значение
должно приблизительноследовать распределению хи-квадрат с одной степенью свободы, если n ≥ 10.Результаты теста: 0: 1.2Е4, 1: 1.2Е4, Х: 0.
2. Two-bit testВ данном тесте проверяется равенство количеств подпоследовательностей длины 2 в последовательности S, как это должно быть в случайной последовательности.Это подпоследовательности 00, 01, 10, 11. Пусть n0, n1 — количество нулевых и единичных значений битов соответственно, и пусть n00, n01, n10, n11 — количество подпоследовательностей 00, 01, 10 и 11 соответственно. Подпоследовательности могут пересекаться, поэтому 
. Тогда для случайной последовательности величина
должна приблизительно следовать распределению хи-квадрат с 2 степенями свободы, если n ≥ 21.Результаты теста: 00: 5,91Е3; 01: 6,09Е3; 10: 6,09Е3; 11: 5,92Е3; Х: 5.
3.Poker testПусть m — положительное целое, такое, что выполняется условие
Последовательность S делится на k непересекающихся частей длины m, и пусть ni — число подпоследовательностей i-го типа длины m, при этом 
.Тест подсчитывает количество подпоследовательностей длины m каждого типа.Количества должны быть примерно одинаковыми для случайной последовательности. Тогда для случайной последовательности величина
должна приблизительноследовать распределению хи-квадрат с 2m-1 степенями свободы.
Результаты теста: Х: 70.
4.Runs test Данный тест подсчитывает количество цепочек единичных и нулевых битов различной длины. В случайной последовательности длины n ожидаемое число цепочек длины i равно
. Пусть k равно наибольшему целому i для которогоei ≥ 5. Обозначим число единичных и нулевых цепочек длины i как Bi и Gi соответственно.Для случайной последовательности статистика 
приблизительно следует распределению хи-квадрат с 2k-2 степенями свободы.Число цепочек различной длины в исследуемой последовательности представлено в табл. 2. Интервалы этих величин для случайной последовательности отражены в табл. 1. Для целей теста цепочки с длинами более 6 считаются имеющими длину 6. Длина исследуемой последовательности равна 20000 битам.
Табл. 1. Интервалы длин цепочек для случайной последовательности.
Длина цепочки
Количество цепочекединиц
Количество цепочекнулей
1
2581
2473
2
1319
1394
3
532
666
4
321
256
5
175
131
6
136
143
Табл. 2. Длины цепочек для исследуемой последовательности.5.Autocorrelation testЗадача данного теста — проверить связь между последовательностью s и ее сдвинутой версией. Пусть d — фиксированное целое, причем 1 < d < [n/2].
Тогда число битов в последовательности s не совпадающих с битами сдвинутой версии s равно 
. Тогда для случайной последовательности значение статистики
должно следовать распределению N (0, 1), при условии, что n-d ≥ 10. Квантили нормального распределения представлены в табл. 3.
Табл. 3. Квантили нормального распределения. Уровень значимости — α.Результаты теста: Х: 0.
Исследуемая последовательность прошла все тесты кроме Poker test. Но и в этом тесте отклонение результата теста от граничной величины незначительное. Это говорит о том, что исследуемая последовательность близка по своим свойствам к случайной и вполне удовлетворяет требованиям данного алгоритма.Для определения сложности исследуемой последовательности использовался алгоритм Берлекемпа-Месси. Тест показал, что математическое ожидание сложности исследуемой последовательности длины n рвно n/2, как и у случайной последовательности.Проведенные тесты показали, что шифр лишен так называемых «слабых» ключей.Основные ограничения данной реализации: длина ключа — не менее 5 байт, длина дополнительного массива — не менее 45 байт, число циклов шифрования — не менее 2-х.
Основные нововведения Происходит перемешивание информации в пределах всего текста. Совершается одновременное преобразование двух блоков текста, причем вместе с текущим по очереди блоком преобразуется блок, номер которого выбран псевдослучайным образом (в зависимости от текущего состояния рабочего ключа). При этом преобразованные блоки переставляются. Рабочий ключ изменяется после обработки каждого блока текста, причем его изменение зависит от самого текста. Изменение одного бита открытого текста ведет к изменению рабочего ключа и, следовательно, к изменению всех последующих преобразований. Ключ расшифрования зависит от ключа шифрования и открытого текста. В каждом случае открытого текста он свой. Раскрытие подключа не определяет даже части ключа, так как в дальнейшем он пересчитывается. Дифференциальный и линейный анализы не работают, так как одновременно обрабатывается весь текст. Частичное совпадение двух открытых текстов не дает совпадения соответствующих шифр-текстов. Изменение открытого текста даже в одном бите ведет к лавинному изменению шифр-текста (≈50%). Причем лавинный эффект происходит не на уровне одного блока, а на уровне всего текста. Конечное значение рабочего ключа является ключом расшифрования, а сложенное с ключом шифрования (или преобразованное иным способом) играет роль хэш-функции (которая изменяется на 50% при изменении одного бита открытого текста). Заключение Данный алгоритм может использоваться в качестве симметричного алгоритма шифрования для защиты как текстовой, так и бинарной информации. Благодаря своим качествам, а именно: универсальности, скорости, простоте реализации, он может использоваться для построения широкого спектра защищенных информационных систем с различными требованиями к криптографическим средствам защиты.В силу своих особенностей алгоритм стоек ко всем известным видам криптоанализа.Список источников и литературы Аносов В.Д., Леонов В.А., Логачев О.А., Лунин А.В. Исследованиеспособов построения алгоритмов хеширования данных. Безопасность информационныхтехнологий. МИФИ, 1997. № 3 Ивченко Г.И., Медведев Ю.И. Математическая статистика: Учебное пособиедля втузов. Высшая школа. Москва, 1992 Молдовян А.А., Молдовян Н.А. Программные шифры: криптостойкость и имитостойкость. Безопасность информационныхтехнологий. МИФИ, 1996. № 2 Молдовян А.А., Молдовян Н.А. Скоростные шифры нового поколения. Мат. конф. РусКрипто»99 Шеннон К.Э. Теория связи в секретных системах. В кн.: ШеннонК.Э. Работы по теории информации и кибернетике., 1963 Garon G., Outerbridge R. DES watch: an examination of the sufficiencyof the Data Encryption Standard for financial institution in the 1990«s.Cryptologia. 1991 Menezes А., P. van Oorschot, S. Vanstone. Handbook of applied cryptography. CRC Press, 1996 Miyaguchi Sh. The FEAL cipher family. Lect. Notes Comput.Sci. 1991
