3.2 Построение алгоритма
Принимая во внимание опыт построения блочных алгоритмов шифрования, их криптоанализ и тенденции развития, становится возможным построение прозрачного по структуре и обладающего достаточной криптостойкостью блочного алгоритма.
3.2.1 Общая схема алгоритма
Общую схему алгоритма можно назвать синтезом алгоритмов RC6, Twofish и Camellia. Тем самым алгоритм должен быть простым и надежным (как RC6), не иметь «линейности» (как Twofish) и строится на основе Вложенных Сетей Фейстеля (как Camellia).
Алгоритм оперирует блоками длиной 128 бит. Для гибкости использования в структуру алгоритма – расписание подключей и основной функции – предусматривается использование ключей различной длины: 128, 256 и 512 бит (с 5/7/9 раундами соответственно). При этом с уменьшением длины ключа увеличивается скорость работы алгоритма и несколько снижается криптостойкость.
До и после обработки входных данных происходит отбеливание от ключевой информации. Для достижения гетерогенности (неоднородности) структуры алгоритма, применяют обработку параллельных данных (двух частей одного блока) разными функциями (FL- и FR-сети) с последующим перемешиванием (линейное преобразование). Общая структура алгоритма представлена на рисунке 10.
Рисунок 10 – Главная схема алгоритма
Каждый раунд шифрования выполняет разбиение входных 128 бит данных на две части по 64 бита и независимо друг от друга обрабатывает их различными сетями Фейстеля типа FL и типа FR. После чего происходит линейное преобразование, целью которого является максимальная диффузия обработанных на предыдущем этапе данных. При этом каждая сеть Фейстеля (FL и FR) применяется по четыре раза (рисунки 11, 12).
Рисунок 11 – Сеть Фейстеля FL
Рисунок 12 – Сеть Фейстеля FR
Функция ff() представляется как ff():= (temp2 xor Ti) + Ki .
Под функцией f() здесь понимается представление поступающего на вход 32-битного числа по модулю 31 плюс 1 (f():= temp2 <<< ((temp1 mod 31)+1)).
Схема линейного преобразования представлена на рисунке 13.
Рисунок 13 – Линейное преобразование
Для реализации циклических сдвигов в линейном преобразовании, в качестве аргумента функции выступают раундовые ключи шифрования. Параллельно с вычислением подключей осуществляется расчет раундовых констант (Т). Вместе с тем, раундовые константы могут храниться в памяти уже рассчитанные, поскольку никак не зависят от ключа шифрования.
3.2.2 Тестирование выходной последовательности алгоритма
Если рассматривать секретную систему как совокупность отображений шифруемых элементов из одного множества в другое, то основной задачей алгоритма шифрования является «перемешивание» шифруемых данных. Быстрое и многократное смешение бит шифруемой информации существенно затруднит криптоанализ шифруемых данных. Такая особенность алгоритма шифрования называется «диффузией» шифруемых данных [18]. Равномерное изменение половины битовой информации выходных данных при изменении одного бита исходных данных, лишает криптоаналитика возможности отследить закономерности изменения выходной информации при манипулировании входными данными.
Изменение одного младшего бита данных в алгоритме ГОСТ 28147-89 распространяется на весь блок данных через четыре раунда, а в алгоритме AES – через 2. В совокупности после всех циклов шифрования данные в алгоритме ГОСТ 28147-89 перемешиваются 6 раз, а в AES – 7 раз (при использовании «усиленной» версии алгоритма).
Результаты тестирования «диффузии» алгоритма в первом раунде со структурой использования Вложенных Сетей Фейстеля отображены на рисунке 14 и таблице 1. Стоит отметить, что в тестировании принимал участие алгоритм с ключом в 512 бит (9 раундов). Ключ шифрования – «нулевой». При этом сравнивались результаты шифрования двух наборов входных данных: все битовые нули и все битовые нули за исключением младшего бита.
Рисунок 14 – Диффузия изменения исходных данных при прохождении через FR-сеть
Таблица 1 – Результаты тестирования алгоритма способность диффузии шифруемых данных
|
FL-сеть
|
FR-сеть
|
Биты 1..16
|
Биты 17-32
|
Биты 33-48
|
Биты 48-64
|
Биты 1..16
|
Биты 17-32
|
Биты 33-48
|
Биты 49-64
|
Раунд 1
|
-
|
-
|
-
|
-
|
9/16
|
10/16
|
0/16
|
1/16
|
Раунд 2
|
-
|
-
|
-
|
-
|
10/16
|
13/16
|
9/16
|
8/16
|
Раунд 3
|
-
|
-
|
-
|
-
|
4/16
|
7/16
|
5/16
|
8/16
|
Раунд 4
|
-
|
-
|
-
|
-
|
9/16
|
3/16
|
10/16
|
10/16
|
Суммарное изменение
|
-
|
12/32
|
20/32
|
32/64
|
Линейное преобразование
|
10/16
|
6/16
|
8/16
|
9/16
|
11/16
|
6/16
|
7/16
|
6/16
|
Суммарное изменение
|
33/64
|
30/64
|
Суммарное изменение
|
63/128
|
Из результатов тестирования видно, что уже после первого раунда преобразований FR-сети, первое слово входных данных (старшие 32 бита) претерпели существенное изменение. После четырех раундов FR-сети выходная последовательность отличалась ровно на половину бит. Линейное преобразование – смешение выходных данных сетей FL и FR – равномерно перемешало биты, о чем говорит равное количество битовых нулей и единиц на каждом из участков.
Можно сделать выводы, что обрабатываемые данные успевают полностью перемешаться всего за один раунд. Таким образом, после проведения всех девяти раундов шифрования, данные перемешаются девять раз. Данный показатель лучше, нежели у алгоритмов ГОСТ 28147-89 и AES [18].
Результаты проведенных статистических тестов алгоритма данной структуры приведены в таблице 2. Тестирование проводилось согласно условиям предлагаемых NIST [4], за исключением количества повторений: 100000 против предлагаемых 10000, что давало 12800000 бит данных для каждого теста.
В таблице 2 в скобках указаны значения тестов для алгоритма, использующего фиксированный циклический сдвиг на один бит влево. При сходных показателях четырех тестов, один тест «Последовательность одинаковых бит» показал заведомо худшие результаты. Показатели данного теста говорят о наличии структурированности выходных данных. Характеристики версии тестируемого алгоритма: 9 раундов шифрования, 512 бит ключевой информации, 128 бит данных.
Таблица 2 – Статистические тесты исследуемого алгоритма
Режим (входные данные)
|
Максимальное отклонение от теоретического распределения при прохождении тестов (%)
|
|
Битовый
|
Частотный блочный
|
Последовательность одинаковых бит
|
Кумуля-тивные суммы
|
Произволь-ное отклонение
|
Случай-
ные
|
0,006 (0,003)
|
0,02 (0,019)
|
7,4 / 3,7 / 1,8
(7,7 / 3,8 / 1,8)
|
0,2 (0,21)
|
0,2 (0,2)
|
Битовые единицы
|
0,04 (0,04)
|
0,06 (0,05)
|
7,4 / 3,7 / 1,8
(7,7 / 3,8 / 1,9)
|
0,4 (0,2)
|
0,19 (0,3)
|
Битовые
нули
|
0,03 (0,03)
|
0,08 (0,07)
|
7,4 / 3,7 / 1,8
(7,7 / 3,8 / 1,9)
|
0,2 (0,2)
|
0,19 (0,2)
|
Поиск битовых последовательностей большей размерности в оригинальной версии алгоритма показал результаты, сравнимые с поиском в случайно последовательности бит: 0,2% для десяти и более битовых единиц подряд.
В таблице 3 представлены соотношения бит нулей и единиц в выходной последовательности после шифрования (применено: 9 раундов, 512 бит ключевой информации, 128 бит данных). Примечание: во второй и третьей колонке указаны битовые данные для 32-битных слов, т.е. запись «1-сл-сл-сл» говорит о том, что первое 32-битное слово состоит полностью из битовых единиц, а остальные три слова – случайны.
Таблица 3 – Соотношение бит нулей и единиц в выходной последовательности
№ п/п
|
Ключ шифрования
|
Входные данные
|
Нулей (%)
|
Единиц (%)
|
Отклонение от 50%
|
1
|
случайный
|
1-сл-сл-сл
|
50,0069%
|
49,9930%
|
0,0069
|
2
|
случайный
|
сл-1-сл-сл
|
50,0002%
|
49,9998%
|
0,0002
|
3
|
случайный
|
сл-сл-1-сл
|
49,9949%
|
50,0050%
|
0,005
|
4
|
случайный
|
сл-сл-сл-1
|
49,9977%
|
50,0022%
|
0,0022
|
5
|
случайный
|
1-1-1-1
|
49,9899%
|
50,0100%
|
0,01
|
Показатели битового теста из таблицы 3 не превышают допустимые отклонения от вероятностных 50%, что позволяет говорить о выходной последовательности как о случайной.
Согласно выводам Шеннона [19] алгоритм шифрования должен выдавать абсолютно случайную битовую последовательность вне зависимости от входных данных и ключевой информации.
Проведенные тесты показывают, что выходные данные тестируемого алгоритма по своим вероятностным характеристикам неотличимы от случайной последовательности.
Шифрование данных увеличивает энтропию выходных данных с тем, чтобы криптоаналитик не имел возможности использовать статистические зависимости шифротекста для проведения успешного криптоанализа [1]. Поэтому в качестве еще одного теста алгоритма с предлагаемой структурой был выбран тест выходных данных на возможность компрессии. Для тестирования был выбран литературный текст (544 КБ, файл формата *.txt) и после шифрования «сжат» компрессором WinRAR v.3.50 с параметром «максимальное сжатие». Итог теста: зашифрованный текстовый файл не был сжат ни на один бит.
Из проведенных тестов предложенного алгоритма можно сделать выводы, что благодаря применению структуры вложенных сетей Фейстеля удалось добиться лавинного эффекта диффузии бит входных данных. При этом важную роль играет линейное преобразование, применение которого вне структуры вложенных сетей невозможно. Использование циклических сдвигов зависимых от функции входных данных также способствует равномерной диффузии бит, что делает невозможным предсказывать выходную последовательность алгоритма при манипулировании входными данными.
После проведения тестов, можно сделать вывод, что при прозрачной структуре алгоритма удалось добиться выходной последовательности данных, которая соответствует случайной последовательности бит и не зависит от входных данных и ключевой информации.
|
