СПОСОБ ИТЕРАТИВНОГО БЛОЧНОГО ШИФРОВАНИЯ ДВОИЧНЫХ ДАННЫХ Российский патент 2003 года по МПК H04L9/16 

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

В совокупности признаков заявляемого способа используются следующие термины:
- шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием секретного ключа;
- секретный ключ представляет из себя двоичную информацию, известную только законному пользователю;
- подключ - часть секретного ключа;
- шифрование есть процесс преобразования информации, который зависит от секретного ключа и преобразует исходный текст в шифротекст (криптограмму), представляющий собой псевдослучайную последовательность знаков, из которой получение информации без знания секретного ключа практически неосуществимо;
- дешифрование есть процесс обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании секретного ключа;
- двоичный вектор - это некоторая последовательность нулевых и единичных битов, например (101101011);
- вес Хемминга от двоичного вектора - это целочисленная функция, значение которой равно числу единиц в двоичном векторе;
- криптоанализ - метод вычисления секретного ключа для получения несанкционированного доступа к зашифрованной информации;
- криптостойкость является мерой надежности защиты зашифрованной информации и представляет собой трудоемкость, измеренную в количестве элементарных операций, которые необходимо выполнить для восстановления информации по криптограмме при знании алгоритма преобразования, но без знания секретного ключа;
- одноместная операция - это операция, выполняемая над двоичным вектором; двоичный вектор, формируемый на выходе одноместной операции, зависит только от входного двоичного вектора; примером одноместных операций являются операции циклического сдвига;
- двуместная операция - это операция выполняемая над двумя операндами; результат выполнения некоторой данной двуместной операции зависит от значения каждого операнда; примером двуместных операций являются операции сложения, вычитания, умножения и др.;
- операнд - это двоичный вектор, над которым выполняется двуместная или одноместная операция;
- управляемая двуместная операция - это операция, выполняемая над двумя операндами под управлением некоторого двоичного вектора, называемого управляющим кодом; результат выполнения некоторой управляемой двуместной операции при фиксированном управляющем коде зависит от значения каждого операнда, а при фиксированных значениях операндов - от значения управляющего вектора; примеры реализации управляемых двуместных операций описаны в патенте РФ N 2140716 [Молдовян А. А., Молдовян Н.А., Молдовяну П.А. Способ криптографического преобразования блоков цифровых данных // БИ N 30 от 27.10.1999]; в формулах управляемую двуместную операцию будем обозначать записью Z:=Q_V(A, B), где А, В - операнды, V - управляющий код, Z - двоичный вектор, являющийся результатом выполнения управляемой двуместной операции Q_V;
- управляющий код (или управляющий двоичный вектор) - совокупность единичных и нулевых сигналов на управляющем входе управляемого операционного блока;
- модификация управляемой двуместной операции - двуместная операция, соответствующая преобразованию двух операндов при фиксированном значении управляющего кода;
- управляемая перестановка - это операция, заключающаяся в перестановке битов операнда в зависимости от значения управляющего кода; примеры реализации управляемых перестановок описаны в патенте N 2140714 [Алексеев Л.Е., Белкин Т. Г. , Молдовян А.А., Молдовян Н.А. Способ итеративного шифрования блоков данных // БИ N 30 от 27.10.1999] и в статье [Гуц Н.Д., Изотов Б.В., Молдовян Н. А. Управляемые перестановки с симметричной структурой в блочных шифрах // Вопросы защиты информации, 2000, N 4, с.57-64]; в формулах управляемую перестановку будем обозначать записью Р_V, а преобразование операнда А путем выполнения над ним управляемой перестановки - записью А:=Р_V(A), где V - управляющий код; управляемая перестановка является частным случаем управляемой одноместной операции;
- модификация управляемой перестановки - фиксированная перестановка битов операнда, соответствующая заданному фиксированному значению управляющего кода;
- обратная управляемая двуместная операция (по отношению к некоторой данной управляемой двуместной операции Q - это такая управляемая двуместная операция (обозначаемая как Q^-1), которая для любого заданного значения управляющего кода V и любого заданного значения операнда В удовлетворяет условию A=Q_V ^-1, если Z=Q_V(A.,B); варианты реализации двух взаимно обратных управляемых двуместных операций описаны в работе [Гуц Н.Д., Молдовян А.А., Молдовян Н. А. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации, 2000, N 1, с.8-15];
- обращаемая управляемая двуместная операция Q* - это такая управляемая двуместная операция, которая контролируется специальным битом инвертирования е; разные значения е задают два разных варианта управляемой двуместной операции, причем эти варианты являются взаимно обратными; например, если при е= 0 выполняется операция Q*_[e=0], а при е=1 - операция Q*_[e=1], то для этих управляемых двуместных операций имеет место соотношение Q*_[e=1]=Q*_[e=0] ^-1; вариант реализации обращаемой управляемой двуместной операции описан в работе [Гуц Н. Д. , Молдовян А.А., Молдовян Н.А. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации, 2000, N 1, с.8-15];
- операция конкатенации - это операция объединения нескольких двоичных векторов, в результате которой формируется новый двоичный вектор, включающий все биты каждого из объединяемых двоичных векторов, причем взаимное расположение битов, соответствующих исходным двоичным векторам не изменяется; например, конкатенация двоичных векторов W₁=(101101011) и W₂=(011101010) записывается в виде W₁\W₂=(101101011011101010).

Известны способы блочного шифрования данных, см., например, шифр DES [B. Schneier. Applied Cryptography. Second Eddition. - New York: John Wiley & Sons, Inc., 1966, p.270-277]. В данном способе шифрование блоков данных выполняют путем формирования секретного ключа, разбиения преобразуемого блока данных на два подблока L и R и поочередного изменения последних путем выполнения операции поразрядного сложения по модулю 2 (которую будем обозначать знаком ⊕) над подблоком L и двоичным вектором, который формируется как выходное значение некоторой функции Е от значения подблока R. После этого подблоки переставляются местами. Функция Е в указанном способе реализуется путем выполнения операций перестановки и подстановки, выполняемых над подблоком R.

Однако известный способ-аналог использует секретный ключ малого размера (56 бит), что делает его уязвимым к криптоанализу на основе подбора ключа. Последнее связано с высокой вычислительной мощностью современных ЭВМ. Другим известным способом итеративного блочного шифрования двоичных данных является способ, реализованный в шифре RC5 [B.Schneier. Applied Cryptography. Second Eddition. - New York: John Wiley & Sons, Inc., 1966, p.344-346]. Данный способ включает в себя формирование секретного ключа в виде совокупности подключей, разбиение двоичного кода информации блоки данных и их шифрование путем разбиения блока данных на подблоки А и В, и поочередное преобразование подблоков.

Подблоки преобразуются путем выполнения над ними одноместных и двуместных операций. В качестве двуместных операций используются операции сложения по модулю 2³² (+) и операция поразрядного сложения по модулю 2. В качестве одноместной операции используется операция циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока, что определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Двуместная операция выполняется над подблоком и подключом, а также над двумя подблоками.

Характерным для способа RC5 является использование операции циклического сдвига, зависящей от значения входного блока. Подблок, например подблок В, преобразуют путем наложения подблока А на подблок В с помощью операции поразрядного сложения по модулю 2, т.е. выполняется операция поразрядного сложения по модулю 2 над подблоками А и В и значение, получаемое после выполнения этой операции присваивается подблоку В. Это записывается в виде соотношения В:=В⊕А, где знак ":=" обозначает операцию присваивания.

После этого над подблоком В выполняют операцию циклического сдвига влево на число бит, равное значению подблока А:В:=В<<<А. Затем над подблоком В и одним из подключей S выполняют операцию суммирования по модулю 2ⁿ, где n - длина подблока в битах: В:=(В+S) mod 2ⁿ. После этого аналогичным образом преобразуется подблок А. Выполняется несколько таких шагов преобразования обоих подблоков. Недостатком шифра RC5 является недостаточная стойкость к дифференциальному криптоанализу.

Наиболее близким по своей технической сущности к заявляемому способу итеративного блочного шифрования двоичных данных является способ, описанный в патенте РФ N 2140710 [Масловский В.М., Молдовян А.А., Молдовян Н.А. Способ блочного шифрования дискретных данных // МПК 6 Н 04 L 9/00, БИ N 30, 27.10.99] . Способ-прототип включает в себя формирование ключа шифрования в виде совокупности подключей, разбиение входного блока двоичных данных на два подблока А и В, которые поочередно преобразуются путем выполнения нескольких раундов преобразования (итераций). Один раунд преобразования заключается в выполнении следующих шагов преобразования.

1. По первому подблоку (подблоку А) формируется управляющий код V₁.

2. Над первым подключом К' выполняется операция перестановки: K':= P_V1(K').

3. Преобразованный подключ К' накладывается с помощью операции поразрядного сложения по модулю два на второй подблок (подблок В): В:=В⊕К'.

4. Затем подблок В накладывается на подблок А с помощью операции сложения по модулю 2³²(+): А:=A+В.

5. По подблоку В формируется управляющий код V₂.

6. Над вторым подключом К" выполняется операция перестановки: K'':= P_V2(K'').

7. Преобразованный подключ К" накладывается на подблок А: А:=А⊕К".

8. Затем подблок А накладывается на подблок В: В:=В+А.

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

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

Поставленная задача достигается тем, что в способе итеративного блочного шифрования двоичных данных, заключающемся в формировании секретного ключа в виде совокупности подключей, разбиении блока данных на m≥2 подблоков B₁, B₂, . .., В_m и поочередном преобразовании подблоков, причем преобразование подблока B_j, где 1≤j≤m, осуществляют путем выполнения, по крайней мере, над одним подключом управляемой операции, зависящей от подблока B_h, где 1≤h≤m и h≠j, и наложения с помощью двуместной операции преобразованного подключа на подблок B_j, новым согласно изобретению является то, что в качестве управляемой операции используют управляемую двуместную операцию.

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

Новым является и то, что управляемую двуместную операцию выполняют над двумя подключами одновременно.

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

Кроме того, новым является то, что управляемую двуместную операцию выполняют одновременно над подключом и подблоком В_g, где 1≤g≤m и g≠j.

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

Ниже сущность заявляемого изобретения более подробно разъясняется примерами его осуществления со ссылками на прилагаемые чертежи (фиг.1, 2).

Обобщенная схема итеративного шифрования блоков данных на основе заявляемого способа представлена фиг.1а, где
Q - операционный блок, осуществляющий управляемую двуместную операцию, модификация которой задается значением управляющего кода V=A, подаваемого на управляющий вход операционного блока Q;
А и В - подблоки преобразуемого блока данных;
"⊕" - операция поразрядного сложения по модулю два.

Х - операционный блок, обозначающий операцию, используемую для формирования управляющего кода V, зависящего от подблка A; например, Х может обозначать операцию присваивания (т.е. V:=А) или процедуру наложения подключа W_r на подблок А (т.е. V:=А⊕W_r);
F - второй операнд, используемый при выполнении управляемой двуместной операции над подключом; в качестве F может быть использован подблок данных А или дополнительный подключ.

Фиг.1а соответствует выполнению одного раунда шифрования. После выполнения каждого раунда шифрования, кроме последнего, осуществляется перестановка подблоков. Дешифрование осуществляется по этой же схеме, но при использовании подключей в обратном порядке. Варианты построения электронных схем, реализующих управляемую двуместную операцию Q описаны в работе [Гуц Н.Д. и др. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации, 2000, N 1, с.8-15]. При выполнении дешифрующих преобразований подключи используются в обратном порядке, т.е. подключи К_r и W_r, использованные на r-м раунде шифрования, при осуществлении дешифрования используются на (R-r+1)-м раунде, где R - число раундов шифрования. Таким образом, для подключей K'_r и W'_r, используемых на r-м раунде дешифрования, имеем соотношения K'_r=K_R-r+1 и W'_r=W_R-r+1. После выполнения последнего (R-го) раунда шифрования или дешифрования перестановка подблоков данных не выполняется.

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

В конкретных примерах реализации заявляемого способ итеративного блочного шифрования двоичных данных в качестве процедуры преобразования двоичного вектора F используется операция управляемой перестановки с 32-битовым входом для преобразуемых данных и 96-битовым управляющим входом, на который поступает управляющий код, в зависимости от которого выбирается модификация управляемой перестановки. Вариант построения операционного блока для реализации такой управляемой перестановки описан в статье [Гуц Н.Д. и др. Управляемые перестановки с симметричной структурой в блочных шифрах // Вопросы защиты информации, 2000, N 4, с.62-63].

Пример 1
Данный пример поясняется на фиг.1б. Он соответствует шифрованию 64-битовых блоков данных. Ключ шифрования формируется в виде множества из 16 K₁, K₂, K₃, . .. A₁₆, каждый из которых имеет длину 32 бит. Входной блок данных разбивается на два 32-битовых подблока А и В. Процедура шифрования входного блока описывается следующим алгоритмом:
1. Установить счетчик числа раундов r=1.

2. Преобразовать подключ К_r путем наложения на него подблока А с помощью управляемой двуместной операции Q, используя в качестве управляющего кода значение подблока А:
K_r:=Q_A(K_r,A).

3. Преобразовать подблок В: В:=В⊕К_r.

4. Если r≠16, то прирастить счетчик r:=r+1, переставить подблоки А и В (т. е. взять двоичный вектор А в качестве двоичного вектора В, а двоичный вектор В - в качестве двоичного вектора А) и перейти к шагу 2, в противном случае СТОП.

Блок криптограммы С формируется путем объединения преобразованных двоичных векторов А и В: С= А|В. Дешифрование блока криптограммы осуществляется с помощью этого же алгоритма, за исключением того, что при выполнении шагов 2 и 3 используется подключ K_17-r вместо подключа К_r.

Пример 2
Пример 2 поясняется на фиг.1в и соответствует шифрованию 64-битовых блоков данных. Ключ шифрования формируется в виде множества из 16 подключей K₁, К₂, К₃,... K₁₆, каждый из которых имеет длину 32 бит. В каждом раунде преобразования используются два подключа, а именно в r-м раунде используются подключи К_r и W_r, где W_r=K_r+8 для r=1, 2,..., 8 и W_r=K_r-8 для r=9, 10,..., 16. Входной блок данных разбивается на два 32-битовых подблока А и В. Процедура шифрования входного блока описывается следующим алгоритмом:
1. Установить счетчик числа раундов r=1.

2. В зависимости от подблока А сформировать управляющий код V:
V:=А⊕W_r
3. Преобразовать подключ К_r путем наложения на него подключа W_r, с помощью управляемой двуместной операции Q:
K_r:=Q_V(K_r,W_r).

4. Преобразовать подблок В: В:=В⊕К_r.

5. Если r≠16, то прирастить счетчик r:=r+1, переставить подблоки А и В (т.е. взять двоичный вектор А в качестве двоичного вектора В, а двоичный вектор В - в качестве двоичного вектора А) и перейти к шагу 2, в противном случае СТОП.

Блок криптограммы С формируется путем объединения преобразованных двоичных векторов А и В: С=А|В. Дешифрование блока криптограммы осуществляется с помощью этого же алгоритма, за исключением того, что при выполнении шага 2 используется подключ W_17-r вместо подключа W_r, при выполнении шага 3 используются подключи W_17-r и K_17-r вместо подключей W_r и К_r соответственно, а при выполнении шага 4 используется подключ К_17-г вместо подключа К_r.

Пример 3
Пример 3 поясняется на фиг.1г и соответствует шифрованию 64-битовых блоков данных. Ключ шифрования формируется в виде множества из 16 подключей К₁, К₂, K₃, ... К₁₆, каждый из которых имеет длину 32 бит. В каждом раунде преобразования используются два подключа, а именно в r-м раунде используются подключи К_r и W_r, где W_r=K_r+8 для r=1, 2,..., 8 и W_r=K_r-8 для r=9, 10,..., 16. Входной блок данных разбивается на два 32-битовых подблока А и В. Процедура шифрования входного блока описывается следующим алгоритмом:
1. Установить счетчик числа раундов r=1 и значение параметра режима шифрования z=0 (шифрование).

2. По подблоку А сформировать управляющий код V₁:
V₁:=A⊕W_r.

3. Преобразовать подключ К_r путем наложения на него подключа W_r, с помощью управляемой двуместной операции Q:
K_r:=Q_V1(K_r,W_r).

4. Преобразовать подблок В с помощью обращаемой управляемой двуместной операции Q*_[e=z], используя в качестве управляющего кода значение подблока А:
B:=Q*_A,[e=z](B,K_r).

5. Если r≠16, то прирастить счетчик r:=r+1, переставить подблоки А и В (т.е. взять двоичный вектор А в качестве двоичного вектора В, а двоичный вектор В - в качестве двоичного вектора А) и перейти к шагу 2, в противном случае СТОП.

Дешифрование блока криптограммы осуществляется с помощью этого же алгоритма, за исключением того, что на первом шаге устанавливается значение z= 1 (режим дешифрования) и при выполнении шага 2 используется подключ W_17-r вместо подключа W_r, при выполнении шага 3 используются подключи K_17-r и W_17-r вместо подключей К_r и W_r соответственно, а при выполнении шага 4 используется подключ К_17-r вместо подключа К_r.

Пример 4
В данном примере поясняется шифрование 96-битовых блоков данных. Ключ шифрования формируется в виде 24 подключей K₁, К₂ K₃,... A₂₄, каждый из которых имеет длину 32 бит. Входной блок данных разбивается на три 32-битовых подблока A, В и С. Процедура шифрования входного блока описывается следующим алгоритмом:
1. Установить счетчик числа раундов r=1.

2. Преобразовать подключ К_3r-2: К_3r-2:=Q_C(K_3r-2,B).

3. Преобразовать подблок А: А:=А⊕K_3r-2.

4. Преобразовать подключ K_3r-1: K_3r-1:=Q_A(K_3r-1, C).

5. Преобразовать подблок В: В:=В⊕K_3r-1.

6. Преобразовать подключ K_3r: K_3r:=Q_B(К_3r,А).

7. Преобразовать подблок C: С:=С⊕K_3r.

8. Если r≠8, то прирастить счетчик r:=r+1 и перейти к шагу 2, в противном случае СТОП.

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

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

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

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов для шифрования данных. Способ итеративного блочного шифрования двоичных данных заключается в формировании секретного ключа в виде совокупности подключей, разбиении блока данных на m≥2 подблоков B₁, B₂,..., В_m и преобразовании подблоков, причем преобразование подблока B_j, где 1≤j≤m, осуществляют путем преобразования, по крайней мере, одного подключа с помощью управляемой операции, зависящей от подблока В_h, где 1≤j≤m и h≠j, и наложения с помощью двуместной операции преобразованного подключа на подблок B_j, при этом в качестве управляемой операции используют управляемую двуместную операцию. Технический результат, достигаемый при осуществлении данного способа, состоит в увеличении скорости шифрования. 2 з.п.ф-лы, 2 ил.

1. Способ итеративного блочного шифрования двоичных данных, заключающийся в формировании секретного ключа в виде совокупности подключей, разбиении блока данных на m≥2 подблоков B₁, В₂,..., В_m и преобразовании подблоков, причем преобразование подблока B_j, где 1≤j≤m, осуществляют путем преобразования, по крайней мере, одного подключа с помощью управляемой операции, зависящей от подблока B_h, где 1≤h≤m и h≠j, и наложения с помощью двуместной операции преобразованного подключа на подблок B_j, отличающийся тем, что в качестве управляемой операции используют управляемую двуместную операцию. 2. Способ по п.1, отличающийся тем, что управляемая двуместная операция выполняется над двумя подключами одновременно. 3. Способ по п.1, отличающийся тем, что управляемую двуместную операцию выполняют одновременно над подключом и подблоком B_q, где 1≤g≤m и g≠j.