АБДРАХМАНОВ Р.Г.
Московский Инженерно-Физический Институт,
кафедра "Защита информации", rus_ab@inbox.ru

ЖУКОВ А.Е.
Московский Государственный Технический Университет им. Н.Э.Баумана,
кафедра "Информационная безопасность", azhukov@iu8.bmstu.ru

В настоящей работе приводится алгоритм GRINDER, представленный на конкурс РусКрипто, а также новый подход к построению шифрующих алгоритмов, лежащий в его основе.

Разработанный алгоритм является алгоритмом шифрования, который работает с блоком данных и ключом произвольной длины. В алгоритме используется перестановка m-битных блоков внутри обрабатываемого массива данных большого размера (сравнимого с объемом системной памяти компьютера), бинарная операция XOR m-битных блоков и их циклический сдвиг, причем каждое последующее преобразование зависит от предыдущего. Шифр сочетает в себе элементы блочных шифров, поточных шифров и шифров перестановки. Алгоритм может оперировать m-битными блоками любого размера. От размера блока зависят скорость и перемешивающие характеристики алгоритма. На данный момент написаны реализации алгоритма, работающие с 16-ти и 32-х битными блоками, что, по-видимому, является оптимальным выбором.

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

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

Подстановочно-перестановочные шифры

Цель данного исследования – получение способа шифрования данных, легко реализуемого программным способом и обеспечивающего рассеивание и перемешивание информации в пределах всего шифруемого массива данных, размер которого ограничивается, вообще говоря, лишь размерами системной памяти используемой ЭВМ.

В основу метода положена идея соединения двух типов преобразований: псевдослучайных преобразований отдельных блоков шифруемого массива данных (информационного массива) и псевдослучайных перестановок преобразованных блоков в пределах всего информационного массива. Поставленная задача достигается тем, что при преобразовании очередного блока данных вначале вычисляется новое значение рабочего ключа, которое зависит как от значения рабочего ключа на предыдущем этапе работы, так и от значения информационного блока, преобразуемого в данный момент. Затем по вычисленному значению рабочего ключа выбирается еще один блок массива данных, номер которого является псевдослучайной величиной. Оба блока подвергаются совместным псевдослучайным преобразованиям, после чего их образы меняются местами в информационного массива данных. Под псевдослучайностью понимается то, что без знания текущего значения рабочего ключа невозможно определить совместно с каким блоком будет преобразовываться данный информационный блок и каким преобразованиям они будут подвержены.

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

Будем обозначать через функцию (отображение) множества X^x Y₁^x…^x Y_nв множество Z,обладающую тем свойством, что при любых фиксированных значениях элементов y₁,…, y_n ,где y_i Y_i, соответствующее отображение множества X в множество Z обратимо. Если зафиксировать значения элементов y₁,…, y_n ,(y_i Y_i), то соответствующее обратное отображение будем обозначать через , т.е. если , то .

Пусть М – двоичный массив данных, подлежащий криптографическому преобразованию; пусть объем этого массива – n*m бит, где m – некоторая фиксированная величина. Размер массива данных может быть произвольным и ограничивается лишь размером системной памяти ЭВМ.

Вначале весь массив данных М размера n*m бит разбивается на n блоков (М₀, М₁, …, М_n-1) по m бит в каждом блоке.

Алгоритм шифрования состоит из T >= 1 циклов шифрования: сначала выполняется 1-й цикл шифрования, затем 2-й и т.д. до Т-го цикла. Каждый цикл шифрования состоит из n итераций: при выполнении t-го цикла шифрования в начале выполняется 0-я итерация, затем 1-я итерация и т.д. до (n-1)-й итерации. После выполнения (n-1)-й итерации t-го цикла шифрования алгоритм начинает выполнять 0-ю итерацию (t+1)-го цикла. После выполнения (n-1)-й итерации Т-го цикла шифрования алгоритм заканчивает работу.

Пусть К – секретный ключ. В начале работы алгоритма ключевая информация помещается в рабочий массив, содержимое которого в процессе работы алгоритма постоянно изменяется. Будем обозначать заполнение этого массива при i-ой итерации t-го цикла работы алгоритма через К_i^(t) и называть его значением рабочего ключа при i-ой итерации t-го цикла. Преобразование, которому алгоритм шифрования подвергает массив данных М в результате i-ой итерации t-го цикла задается (определяется) следующим образом:

1. Вычисляется значение рабочего ключа для i-ой итерации t-го цикла шифрования:

К_i^(t) = f(К_i-1^(t) | M_i) для всех i >= 1,

При этом: для i = 0, t >= 2, полагаем К_-1^(t) = К_n-1^(t-1);

для i = 0, t = 1, полагаем К_-1⁽¹⁾ = K



2. Определяется номер блока, который будет преобразовываться совместно с блоком M_i:

j = j ( К_i^(t))



3. Вычисляются новые значения блоков M_i и M_j:

А = F₁(M_j | M_i, К_i^(t))

B = F₂(M_i | К_i^(t))

M_i = A

M_j = B



4. Если i < n-1, то осуществляется переход к итерации i+1 того же цикла t;

Если i = n-1 и t < T, то осуществляется переход к итерации 0 цикла t+1;

Если i = n-1, t = T, то работа алгоритма заканчивается.

Значения блоков М₀, М₁, …, М_n-1 после завершения последней итерации последнего цикла шифрования образуют массив шифртекста, который передается (хранится) вместе со значением хэш-функции

K' = k(K_n-1^(T)|K), которая одновременно служит для получения ключа расшифрования К_n-1^(t-1).

Алгоритм расшифрования преобразует массив данных М, который также разбит на блоки М₀, М₁, …, М_n-1 по m бит в каждом и начинается с определения значения рабочего ключа K_n-1^(T):

K_n-1^(T) = k^-1(K' |K).

Затем проделывается Т циклов расшифрования, начиная с Т-го цикла расшифрования и заканчивая 1-м циклом расшифрования. Каждый цикл расшифрования состоит из n итераций, начиная с выполнения (n-1)-й итерации и заканчивая выполнением 0-й итерации. После 0-й итерации t-го цикла расшифрования выполняется (n-1)-я итерация (t-1)-го цикла расшифрования. После выполнения 0-й итерации 1-го цикла расшифрования алгоритм расшифрования заканчивает работу.

Преобразование, которому алгоритм расшифрования подвергает массив данных М в результате i-ой итерации t-го цикла расшифрования задается следующим образом:

1. Определяется номер блока, который будет преобразовываться совместно с блоком M_i:

j = j ( К_i^(t))

2. Вычисляются новые значения блоков M_i и M_j:

А = F₂^-1(M_j | К_i^(t))

B = F₁^-1 (M_i | А, К_i^(t))

M_i = A

M_j = B

3. Вычисляется значение рабочего ключа для (i-1)-ой итерации t-го цикла шифрования:

К_i-1^(t) = f ^-1(К_i^(t) | M_i) для всех i >= 1;

При этом для i = 0, t < T, полагаем К_n-1^(t) = К_-1^(t+1);

для i = n-1, t = T, полагаем К_n-1^(T) = k^-1(K' | K)

Если i < 0, то осуществляется переход к итерации i-1 того же

цикла t;

Если i = 0 и t > 1, то осуществляется переход к (n-1)-й итерации

цикла t-1;

Если i = 0, t = 1, то работа алгоритма расшифрования заканчивается.

Значения блоков М₀, М₁, …, М_n-1 после завершения 0-й итерации 1-го цикла расшифрования образуют массив исходного открытого текста.

Отметим еще раз следующие особенности предлагаемого алгоритма:

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

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

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

f(К_i-1^(t)| M_i), F₁(M_j | M_i, К_i^(t)),

F₂(M_i | К_i^(t)), k(K_N-1^(T) |K),

а также легко реализуемую функцию выбора номера блока j (К_i^(t)).

Одним из вариантов выбора указанных выше функций, является следующий.

Пусть М – двоичный массив данных, подлежащий криптографическому преобразованию, в дальнейшем этот массив будет называться информационным массивом; пусть объем этого массива – n*m бит, где m – некоторая фиксированная величина. Размер информационного массива может быть произвольным и ограничивается лишь размером системной памяти ЭВМ. Весь массив данных М размера n*m бит разбивается на n блоков (М₀, М₁, …, М_n-1) по m бит в каждом блоке, в дальнейшем эти блоки будут называться информационными блоками.

Пусть K – двоичный массив данных, образующих секретный ключ, в дальнейшем этот массив будет называться ключевым массивом; пусть объем этого массива – s*m бит, где m – та же величина, что и выше. Весь массив K разбивается на s блоков (K₀, K₁, …, K_s-1) по m бит в каждом блоке, в дальнейшем эти блоки будут называться подключами. В процессе работы алгоритма заполнение массива K меняется при переходе к каждой следующей итерации; его заполнение при выполнении i-ой итерации t-го цикла работы алгоритма является значением рабочего ключа К_i^(t) . Рабочим подключем называется блок массива K, используемый в преобразованиях на i-ой итерации t-го цикла работы алгоритма.

Для изменения информационных блоков и подключей в процессе работы алгоритма используются дополнительные блоки, которые выбираются псевдослучайным образом из проинициализированного в начале работы алгоритма дополнительного массива G, называемого массивом гаммы. Пусть объем этого массива – p*m бит, где m – та же величина, что и выше. Весь массив G разбивается на p блоков (G₀, G₁, …, G_p-1) по m бит в каждом блоке, в дальнейшем эти блоки будут называться блоками гаммы.

На начальном этапе происходит инициализация массива гаммы. Данная процедура необходима для того, чтобы обеспечить выработку качественной гаммы в процессе шифрования. Изначально массив гаммы заполняется любыми данными, например, текстом или псевдослучайной последовательностью. Инициализация представляет собой многократное однонаправленное изменение начального заполнения массива гаммы (например операциями циклического сдвига, векторного сложения, поразрядного XOR и т.д.) с использованием секретного ключа. Инициализация снимает жесткие ограничения на длину и начальное заполнение массива гаммы, что позволяет использовать в качестве начального заполнения как текстовые, так и бинарные фрагменты.

Инициализация гаммы: – однократная инициализация дополнительного массива в зависимости от ключа шифрования.

Зашифрование

Зашифрование информационного массива производится последовательным считыванием информационных блоков и подключей (из соответствующих массивов) с их последующим преобразованием. При преобразовании очередного блока данных вначале вычисляется новое значение рабочего ключа, которое зависит как от значения рабочего ключа на предыдущем этапе работы, так и от значения информационного блока, преобразуемого в данный момент. Затем по вычисленному значению рабочего ключа выбирается еще один блок массива данных, номер которого является псевдослучайной величиной. Оба блока подвергаются совместным псевдослучайным преобразованиям, после чего их образы меняются местами в информационном массиве данных.

Будем пользоваться следующими обозначениями:

• X' – преобразованный массив X;
• – циклический сдвиг X вправо на Y позиций
• – циклический сдвиг X влево на Y позиций;
• Операция + это либо Å (XOR), либо (сложение по модулю 2^m, где m – размер блоков в битах).
• n ₁, n ₂, p ₁, p ₂ : (Z₂)^m® Z_m
• l _1, m ₁ : (Z₂)^m® Z_s
• l ₂, m ₂, y ₁, y ₂ : (Z₂)^m® Z_p
• j : (Z₂)^m® Z_n