СПОСОБ ИТЕРАТИВНОГО КРИПТОГРАФИЧЕСКОГО ПРЕОБРАЗОВАНИЯ ДАННЫХ

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

В совокупности признаков заявленного изобретения используются следующие термины:

Стохастическое преобразование - непредсказуемое преобразование данных; примером стохастического преобразования может являться криптографическое преобразование;

Генератор псевдослучайных чисел (ГПСЧ) - генератор последовательности чисел, статистически не отличимой от последовательности случайных чисел с равномерным законом распределения; наиболее жесткие требования (по непредсказуемости, статистической безопасности, периоду формируемых последовательности и эффективности реализации) предъявляются к ГПСЧ, ориентированным на решение задач криптографической защиты информации;

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

Подключ - часть ключа;

Раунд - последовательность шагов, образующих одну итерацию итеративного (многораундового) стохастического преобразования;

Раундовый ключ (RoundKey) - ключевая информация, использующаяся при выполнении одного раунда преобразования, существует два способа формирования раундовых ключей: раундовый ключ может являться частью секретного ключа (пример - Российский стандарт криптозащиты ГОСТ 28147-89), последовательность раундовых ключей может получаться в результате работы процедуры «разворачивания» исходного ключа (пример - американский стандарт криптозащиты AES);

Раундовый подключ - часть раундового ключа;

Двоичный вектор - некоторая последовательность нулевых и единичных бит, например (01101010), двоичный вектор разрядности n может быть интерпретирован как элемент конечного поля GF(2ⁿ);

Замена (Substitution) - операция, выполняемая над двоичным вектором i∈GF(2ⁿ), при этом результат операции равен содержимому ячейки с индексом i таблицы замен размерности n×2ⁿ;

Перемешивание (Mix) - операция, выполняемая над двоичным вектором разрядности n, результат разрядности n которой зависит от всех входных бит и от их взаимного расположения; качественное перемешивание обладает свойствами рассеивания и перемешивания.

Известен способ нелинейного многораундового преобразования данных с архитектурой «Сеть Фейстеля», описанный в Российском стандарте криптографической защиты информации [Стандарт СССР ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования]. Способ аналог включает в себя формирование ключа в виде последовательности из 8 подключей длиной 32 бита. Перед преобразованием 64-разрядный блок данных разбивается на два 32-разрядного подблока L и R, которые поочередно преобразуются путем выполнения 32 раундов преобразования. Один раунд преобразования заключается в следующем. По подблоку L формируется двоичный вектор F в соответствии с выражением F:=L, который преобразуется в зависимости от одного из подключей в соответствии с раундовой функцией преобразования Е. Преобразование двоичного вектора на i-м раунде записывается в виде F:=E{F, K_i), где K_i - подключ, используемый на i-м раунде. Полученное значение F:=E(F, K_i) поразрядно суммируется по модулю два ⊕ с подблоком R в соответствии с выражением R:=R⊕F. Вычисление раундовой функции E(F, K_i) осуществляется в соответствии со следующими шагами преобразования. Первоначально сформированный двоичный вектор F:=L преобразуется путем наложения на него текущего подключа K_i, являющегося фиксированным для данного раунда, с помощью операции сложения по модулю 2³² в соответствии с формулой F:=(F+K_i) mod 2³², после чего над двоичным вектором F выполняют операцию замены F:=S(F), затем операцию циклического сдвига влево (в сторону старших разрядов) на 11 разрядов F:=F<<<11. После каждого раунда шифрования, за исключением последнего, подблоки переставляются. Операция замены выполняется следующим образом. Двоичный вектор F разбивается на 8 двоичных векторов длиной по 4 бит каждый. Каждый 4-разрядный двоичный вектор заменяется двоичным вектором из соответствующей таблицы замен. Выбранные из таблиц замен восемь 4-разрядных векторов объединяются в преобразованный двоичный вектор F.

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

Одним из путей решения проблемы построения быстродействующего итеративного криптографического преобразования является использование гибридных вычислительных технологий. Наиболее подходящей для реализации на GPU является архитектура Квадрат, предложенная авторами криптоалгоритмов Square и Rijndael, при этом последний в 2001 г. победил в конкурсе на принятие нового Американского стандарта криптозащиты AES (Advanced Encryption Standard).

Наиболее близким по своей технической сущности к заявленному способу итеративного криптографического преобразования данных является принятый за прототип способ многораундового 2D-преобразования с архитектурой «Квадрат», описанный в версии стандарта AES-128 [Daemen J., Rijmen V. AES Proposal: Rijndael. URL: http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ainmended.pdf или Иванов M.A., Ковалев А.В., Чугунков И.В. и др. Стохастические методы защиты информации в компьютерных системах и сетях. М.: Кудиц-Пресс, 2009, с.241]. В данном способе все входные и выходные блоки данных, все промежуточные результаты преобразований, все раундовые ключи представляются в виде квадратного массива байтов 4×4, таким образом, разрядность всех блоков данных равна 128 битам. Преобразование выполняется путем формирования из секретного ключа с помощью процедуры разворачивания ключа последовательности раундовых ключей K₀, K₁,…, K_R, где R - число раундов преобразования. По входному блоку М формируется блок State в соответствии с выражением State:=М. Затем выполняется операция начального поразрядного сложения по модулю два (XOR) блока State и раундового ключа (AddRoundKey) K₀ в соответствии с выражением State:=State⊕K₀, после чего выполняются R раундов преобразования. Преобразование блока данных на i-м раунде записывается в виде State:=E(State, K_i), где Е() - раундовая функция преобразования, K_i - раундовый ключ, используемый на i-м раунде. Полученное значение State:=E(State, K_i) поступает на вход следующего раунда. В состав каждого i-го раунда кроме последнего входят последовательно выполняемые преобразования замены байтов State:=SubBytes(State), циклического сдвига строк State:=ShiftRows(State), перемешивания столбцов State:=MixColimns(State) и сложения по модулю два (XOR) с раундовым ключом (AddRoundKey) Ki в соответствии с выражением State:=State⊕K_i. В состав последнего раунда входят последовательно выполняемые преобразования замены байтов, циклического сдвига строк и сложения (XOR) с раундовым ключом K_R. Операция замены байтов выполняется следующим образом. Блок State разбивается на 16 байтов. Каждый байт заменяется байтом из фиксированной таблицы замен размерностью 8×256. Выбранные из таблицы замен 16 байтов объединяются в преобразованный блок State. Операция сдвига строк выполняется следующим образом. Блок State разбивается на 4 строки. Каждая j-я строка (j=0, 1, 2, 3) циклически сдвигается на j байтов. Сдвинутые строки объединяются в преобразованный блок State. Операция перемешивания столбцов выполняется следующим образом. Блок State разбивается на 4 столбца. При выполнении перемешивания байты столбца рассматриваются как коэффициенты многочлена А(х) степени 3 над полем GF(2⁸). Суть операции перемешивания столбца - умножение по модулю х⁴+1 многочлена А(х) на многочлен 03х³+х²+х+02. Перемешанные столбцы объединяются в преобразованный блок State.

Таким образом, последовательность 10-раундового преобразования AES-128 имеет следующий вид: начальный шаг сложения с раундовым ключом, 9 раундов, каждый из которых состоит из четырех шагов (замены байтов, циклического сдвига строк, перемешивания столбцов и сложения с раундовым ключом), последний 10-й раунд, состоящий из трех шагов (замены байтов, циклического сдвига строк и сложения с раундовым ключом).

Недостатком известного решения является низкая криптостойкость и недостаточно высокое быстродействие.

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

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

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

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

формирование из секретного ключа с помощью процедуры разворачивания ключа последовательности раундовых ключей K₁, K₂,…, K_R, где R - число раундов преобразования;

формирование по входному блоку М блока С в соответствии с выражением С:=М;

выполнение R раундов преобразования, при этом преобразование блока данных на i-м раунде записывается в виде С:=Е(С, K_i), где Е() - раундовая функция преобразования, К_i - раундовый ключ, используемый на i-м раунде, полученное значение С:=Е(С, K_i) при i<R поступает на вход следующего раунда, а результат действия последнего раунда С:=Е(С, K_R) является результатом преобразования;

новым согласно изобретению является то, что дополнительно

из каждого раундового ключа K_i формируют N раундовых подключей K_i1, K_i2,…, K_iN, где N - число траекторий раундовых преобразований в каждом раунде;

при выполнении каждого i-го раунда создают N копий С_i1, С_i2,…, С_iN входного блока данных С, каждую копию C_ij подвергают стохастическому преобразованию Е_ij, которое записывается в виде С_ij:=E_ij(C_ij, K_ij), преобразованные значения C_ij поступают на входы комбинационной схемы F, функцией которой является параллельная композиция различных траекторий раундовых преобразований, результат действия комбинационной схемы С:=F(C_i1, С_i2,…, С_iN) объявляют результатом раунда.

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

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

Новым является то, что в частном случае стохастическое преобразование E_ij включает

представление входного блока C_ij, промежуточных результатов преобразования и раундового подключа K_ij в виде квадратного массива бит размерностью 8×8;

сложение по модулю два (XOR) входного блока C_ij и раундового подключа К_ij;

разбиение результата на строки r₁, r₂,…, r₈ и выполнение для каждой строки операции замены с использованием таблицы S размерностью 8×256;

разбиение результата на столбцы с₁, с₂,…, с₈ и выполнение для каждого столбца операции замены с использованием таблицы S размерностью 8×256.

Благодаря совокупности перечисленных решений увеличивается криптостойкость преобразования за счет выполнения последовательной и параллельной композиции раундовых преобразований и повышается быстродействие за счет появления возможности сокращения числа раундов и выполнения всех раундовых преобразований C_ij:=Е_ij(С_ij, K_ij) параллельно.

Суть предлагаемого способа иллюстрируют фиг.1-3.

На фиг.1 изображена структура итеративного криптографического преобразования.

На фиг.1 показаны входы 1_i и выходы 2_i последовательно выполняемых раундов 6_i, а также раундовые ключи 3₁, 3₂,…, 3_R, которые формируются из секретного ключа с помощью процедуры разворачивания ключа, где R - число раундов преобразования, i=1, 2,…, R. Последовательность шагов итеративного криптографического преобразования:

формирование по входному блоку 1₁ М блока С в соответствии с выражением С:=М;

выполнение R раундов преобразования, при этом преобразование блока данных 1_i на i-м раунде записывается в виде С:=Е(С, K_i), где K_i - раундовый 3_i ключ, используемый на i-м раунде, полученное значение 2_i С:=Е(С, K_i) при i<R поступает на вход следующего раунда, а результат действия 2_R последнего раунда С:=Е(С, K_R) является результатом преобразования входного блока 1₁М.

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

На фиг.1 показаны раундовые 3_ij подключи, i=1, 2,…, R, j=1, 2,…, N, использующиеся при выполнении стохастических преобразований 4_i1, 4_i2,…, 4_iN, которые выполняются внутри каждого раунда 6_i, а также комбинационная схема 7.

Внутри каждого раунда происходит формирование N копий входного блока 1_i, каждая копия C_ij подвергается стохастическому преобразованию 4_ij, которое записывается в виде C_ij:=E_ij(C_ij, K_ij), преобразованные значения C_ij поступают на входы комбинационной 5_i схемы F, функцией которой является параллельная композиция различных траекторий раундовых преобразований, результат действия комбинационной 5_i схемы С:=F(C_i1, С_i2,…, С_iN) объявляется результатом 2_i раунда 6_i.

На фиг.2 показан вариант построения комбинационной 5 схемы на основе N-входового блока поразрядного сложения 7 по модулю два. На входы блока 7 поступают результаты преобразований с выходов блоков, осуществляющих стохастические преобразования 4_i1, 4_i2,…, 4_iN. С выхода блока 5 снимается результат 2_i i-го раунда.

На фиг.3 показан пример преобразования 4. Рассматривается случай, когда все блоки 1_i, 2_i, все раундовые подключи 3_ij, все промежуточные результаты преобразований в блоках 4_ij представляются в виде квадратного массива бит 8×8, т.е. имеют разрядность 64 бита. На фиг.3 показана операция сложения 8 по модулю два, отдельные строки 9 и столбцы 10 блока данных.

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

- Формирование по входному 1_i блоку М блока С в соответствии с выражением С:=М.

- 1-й раунд преобразований. Преобразование блока данных на первом раунде записывается в виде С:=Е(С, K₁), где K₁ - раундовый ключ первого раунда. Полученное значение 2₁ поступает на вход 1₂ второго раунда.

- 2-й раунд преобразований. Преобразование блока данных на втором раунде записывается в виде С:=Е(С, K₂), где K₂ - раундовый ключ второго раунда. Полученное значение 2₂ поступает на вход 1₃ третьего раунда.

- R-й раунд преобразований. Преобразование блока данных на последнем раунде записывается в виде С:=Е(С, K_R), где K_R - раундовый ключ последнего раунда. Полученное значение 2_R является результатом итеративного криптографического преобразования блока данных 1₁М.

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

- Формирование по входному 1₁ блоку М блока С в соответствии с выражением С:=М.

- 1-й раунд преобразований. При выполнении первого раунда создается N копий С₁₁, С₁₂,…, С_1N входного 1₁ блока данных С, каждая копия С_1j подвергается стохастическому преобразованию 4_ij, которое записывается в виде C_ij:=E_1j(C_1j, K_1j), где K_1j - раундовые подключи первого раунда, j=1, 2,…, N, преобразованные значения C_1j поступают на входы комбинационной 5₁ схемы F, функцией которой является параллельная композиция результатов выполнения различных траекторий раундовых преобразований, результат действия комбинационной 5₁ схемы С:=F(C₁₁, С₁₂,…, C_1N) объявляется результатом 2₁ первого раунда. Полученное значение 2₁ поступает на вход 1₂ второго раунда.

- 2-й раунд преобразования. При выполнении второго раунда создается N копий С₂₁, С₂₂,…, С_2N входного 1₂ блока данных С, каждая копия С_2j подвергается стохастическому преобразованию 4_2j, которое записывается в виде С_2j:=Е_2j(С_2j, K_2j), где K_2j - раундовые подключи второго раунда, j=1, 2,…, N преобразованные значения C_ij поступают на входы комбинационной 5₂ схемы F, функцией которой является параллельная композиция результатов выполнения различных траекторий раундовых преобразований, результат действия комбинационной 5₂ схемы С:=F(C₂₁, С₂₂,…, C_2N) объявляется результатом 2₂ второго раунда. Полученное значение 22 поступает на вход 1₃ третьего раунда.

- R-й раунд преобразований. При выполнении последнего раунда создается N копий C_R1, C_R2,…, C_RN входного 1_R блока данных С, каждая копия C_Rj подвергается стохастическому преобразованию 4_Rj, которое записывается в виде C_Rj:=E_Rj(C_Rj, K_Rj), где K_Rj - раундовые подключи последнего раунда, j=1, 2,…, N, преобразованные значения C_Rj поступают на входы комбинационной 5_R схемы F, функцией которой является параллельная композиция результатов выполнения различных траекторий раундовых преобразований, результат действия комбинационной 5_R схемы С:=F(C_R1, C_R2,…, C_RN) объявляется результатом 2_R второго раунда. Полученное значение 2_R является результатом итеративного криптографического преобразования блока данных 1₁М.

Рассмотрим пример реализации стохастического преобразования 4_ij, показанный на фиг.4. Все блоки 1_i входных данных, все промежуточные результаты, раундовые подключи 3_ij имеют разрядность 64 бита и представляются в виде квадратного массива бит 8×8.

Последовательность операций при выполнении простейшего преобразования 4_ij имеет следующий вид:

сложение 8 по модулю два (XOR) входного блока 1_i и раундового подключа 3_ij;

разбиение результата на строки 9 r₁, r₂,…, r₈ и выполнение для каждой строки операции замены с использованием таблицы S размерностью 8×256;

разбиение результата на столбцы 10 с₁, с₂,…, c₈ и выполнение для каждого столбца операции замены с использованием таблицы S размерностью 8×256.

При таком способе выполнения преобразования 4_ij дополнительно появляется возможность повысить быстродействие за счет параллельного выполнения операций замены строк и столбцов.

Одним из известных путей повышения криптостойкости нелинейной функции шифрования является использование для ее построения последовательной и параллельной композиции простейших функций ƒ шифрования. Параллельная композиция суть побитовый XOR последовательностей с выходов двух блоков ƒ, в последовательной композиции выход одного блока ƒ является входом другого. Такой подход к построению шифра впервые был использован У. Маурером при создании самосинхронизирующегося поточного шифра [Иванов М.А., Ковалев А.В., Чугунков И.В. и др. Стохастические методы защиты информации в компьютерных системах и сетях. М.: Кудиц-Пресс, 2009, с.263]. Базовый компонент схемы Маурера - 3-битовый регистр сдвига с зависящей от ключа функцией ƒ выхода. Четыре таких компонента образуют блок следующего уровня - пару параллельно соединенных цепочек из двух базовых компонентов. На следующем уровне четыре таких блока собраны в последовательную композицию. На двух следующих уровнях эта конструкция повторяется. Результирующая последовательностная машина (ПМ) имеет входную память объемом 192 бита и 4 бита-компонента на каждый бит памяти. Внутреннее состояние ПМ служит входом для зависящей от ключа функции шифрования F_c. Для задания конструкций булевых функций ƒ ключ шифрования «разворачивается» в 256 байтов, каждый из которых определяет таблицу истинности соответствующей функции. Основная идея данной конструкции - построение ПМ, количество элементов памяти которой превышает разрядность входной памяти. Подобный подход к построению блочных итеративных шифров ранее не применялся, его использование при программной реализации криптографических преобразований стало возможным в связи с появлением гибридных суперкомпьютерных технологий. В результате стало возможным в пределах раунда параллельно (иначе говоря, без ущерба для быстродействия) выполнять различные траектории сложных преобразований, а затем на выходе осуществлять параллельную композицию полученных результатов. В результате задача инвертирования функции шифрования становится вычислительно неразрешимой при меньшем числе раундов преобразования. В том случае, когда число раундов остается неизменным, применение последовательной и параллельной композиции раундовых преобразований приводит к повышению криптостойкости шифра.

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

В последние годы все большую популярность завоевывают гибридные вычислительные системы, сочетающие удобство классических вычислений на центральных процессорах (CPU) с массово-параллельными вычислениями на графических процессорах (GPU) [Боресков А.В., Харламов А.А. Основы работы с технологией CUDА. М.: ДМК Пресс, 2011], [CUDA Zone. URL http://developer.nvidia.com/ category/zone/cuda-zone]. Особенностью GPU является наличие большого числа (десятки и сотни) вычислительных ядер, работающих параллельно. В задачах, допускающих распараллеливание обработки потока исходных данных, выигрыш в производительности для системы CPU/GPU составляет до нескольких десятков раз по сравнению с классической CPU-системой. Многие из наиболее производительных современных суперкомпьютеров также имеют гибридную архитектуру CPU/GPU.

В гибридных системах CPU решает задачи управления выполнением программы в целом и проведения не очень "тяжелых" вычислений; наиболее критичные по производительности участки программы оформляются в виде специальных функций-ядер (kernel), которые запускаются на GPU. Современные производители графических процессоров, в частности, компания NVIDIA, предоставляют разработчикам программ для систем CPU/GPU мощные инструментальные средства. Полезной и приятной особенностью таких средств является то, что они являются бесплатными. В качестве примеров можно указать CUDA Toolkit [CUDA Toolkit. URL http://developer.nvidia.com/cuda-toolkit] и Parallel NSight [NVIDIA Parallel Nsight. URL http://developer.nvidia.com/ nvidia-parallel-nsight], которые интегрируются с современными популярными системами разработки ПО, такими как Microsoft Visual Studio и NetBeans.

Для программной реализации предложенного способа построения итеративного криптографического преобразования наиболее целесообразной представляется технология CUDA (Compute Unified Device Architecture - вычислительная унифицированная архитектура устройств) от компании NVIDIA [Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М.: ДМК Пресс, 2011], [CUDA Zone. URL http://developer.nvidia.com/category/zone/cuda-zone]. Минимальной вычислительной единицей в CUDA является нить (thread). По сути, нить есть набор конкретных действий над элементом данных, нити группируются в пучки (warp); все нити одного пучка физически параллельно выполняются на потоковом мультипроцессоре; из потоковых мультипроцессоров состоит графический процессор. Очень важной особенностью CUDA является то, что при программировании нити образуют трехмерные структуры, именуемые блоками (block). Блоки, в свою очередь, группируются в еще более крупную многомерную структуру, именуемую сеткой (grid). Другими словами, сетка есть совокупность всех нитей, выполняющих параллельную обработку данных, и вместе с тем представляющая собой гибкую многомерную иерархическую структуру. Таким образом, CUDA-программист может оперировать с одно-, двух- или трехмерными структурами для параллельной обработки исходных данных, в том числе комбинируя размерности этих структур.

Очевидно, что в пределах каждого раунда все траектории могут быть обработаны параллельно, а применение CUDA позволит существенно упростить процесс разработки ПО.