ИТЕРАТИВНЫЙ СПОСОБ БЛОЧНОГО ШИФРОВАНИЯ Российский патент 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, а преобразование операнда А путем выполнения над ним управляемой перестановки - записью А := P_V(A), где V - управляющий код;
-модификация управляемой перестановки - фиксированная перестановка битов операнда, соответствующая заданному фиксированному значению управляющего вектора;
-обратная управляемая двуместная операция (по отношению к некоторой данной управляемой двуместной операции Q - это такая управляемая двуместная операция (обозначаемая как Q^-1), которая для любого заданного значения управляющего вектора V и любого заданного значения операнда В удовлетворяет условию А = Q_V ^-1(Z,B), если Z = Q_V(A,B); варианты реализации двух взаимно обратных управляемых двуместных операций описаны в работе [Гуц Н.Д., Молдовян А. А. , Молдовян Н.А. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации. 2000. N 1. С.8-15];
-обращаемая управляемая двуместная операция Q* - это такая управляемая двуместная операция, которая контролируется специальным битом инвертирования е; разные значения е задают два разных варианта управляемой двуместной операции, причем эти варианты являются взаимно обратными; например, если при е = 0 выполняется операция Q*[e=0]

, а при е = 1 - операция Q*[e=1], то для этих управляемых двуместных операций имеет место соотношение Q*[e=1] = Q*-1[e=0]; вариант реализации обращаемой управляемой двуместной операции описан в работе [Гуц Н.Д., Молдовян А.А., Молдовян Н.А. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации. 2000. N 1. С.8-15];
- операция конкатенации - это операция объединения нескольких двоичных векторов, в результате которой формируется новый двоичный вектор, включающий все биты каждого из объединяемых двоичных векторов, причем взаимное расположение битов, соответствующих исходным двоичным векторам, не изменяется; например, конкатенация двоичных векторов W₁ = (101101011) и W₂ = (011101010) записывается в виде W₁|W₂ = (101101011011101010); данные двоичные вектора могут быть объединены операцией конкатенации еще одним способом: W₂|W₁ = (011101010101101011).

Известны способы блочного шифрования данных, см. например, шифр DES [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1966, pp.270-277]. В данном способе шифрование блоков данных выполняют путем формирования секретного ключа, разбиения преобразуемого блока данных на два подблока L и R и поочередного изменения последних путем выполнения операции поразрядного суммирования по модулю два над подблоком L и двоичным вектором, который формируется как выходное значение некоторой функции Е от значения подблока R. После этого подблоки переставляются местами. Функция Е в указанном способе реализуется путем выполнения операций перестановки и подстановки, выполняемых над подблоком R. Данный способ обладает высокой скоростью преобразований при реализации в виде специализированных электронных схем. Однако известный способ-аналог использует секретный ключ малого размера (56 бит), что делает его уязвимым к криптоанализу на основе подбора ключа. Последнее связано с высокой вычислительной мощностью современных ЭВМ. Другим известным способом блочного шифрования данных является способ, реализованный в шифре RC5 [B.Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1966, pp. 344-346]. Способ-аналог включает в себя формирование секретного ключа в виде совокупности подключей, разбиение двоичного кода информации на g-битовые информационные блоки и поочередное преобразование g-битовых блоков. Преобразование g-битовых блоков осуществляют путем разбиения g-битового блока данных на n-битовые подблоки A и В, и поочередное преобразование подблоков. Подблоки преобразуются путем выполнения над ними одноместных и двуместных операций. В качестве двуместных операций используются операции сложения по модулю 2ⁿ, где n= g/2= 8,16,32,64, и операция поразрядного суммирования по модулю 2. В качестве одноместной операции используется операция циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока, что определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Двуместная операция выполняется над подблоком и под ключом, а также над двумя подблоками. Характерным для способа RC5 является использование операции циклического сдвига, зависящей от значения входного блока. Подблок, например подблок В, преобразуют путем наложения подблока А на подблок В с помощью операции поразрядного суммирования по модулю 2, т.е. выполняется операция поразрядного суммирования по модулю 2 (обозначаемая знаком "⊕") над подблоками A и В и значение, получаемое после выполнения этой операции, присваивается подблоку В. Это записывается в виде соотношения B: = B⊕A, где знак ":=" обозначает операцию присваивания. После этого над подблоком В выполняют операцию циклического сдвига влево на число бит, равное значению подблока А: В:= В <<<А. Затем над подблоком В и одним из подключей S выполняют операцию суммирования по модулю 2ⁿ, где n - длина подблока в битах: В := (В + S) mod 2ⁿ. После этого аналогичным образом преобразуется подблок А. Выполняется несколько таких шагов преобразования обоих подблоков. Недостатком шифра RC5 является недостаточная стойкость к дифференциальному криптоанализу.

Наиболее близким по своей технической сущности к заявляемому итеративному способу блочного шифрования является способ, описанный в патенте Российской Федерации 2140714 [Алексеев Л.Е., Белкин Т.Г., Молдовян А.А., Молдовян Н. А. Способ итеративного шифрования блоков данных. Бюл. N 30 от 27.10.99]. Способ-прототип включает в себя формирование ключа шифрования, разбиение входного блока двоичных данных на два подблока А и В, которые поочередно преобразуются путем выполнения нескольких раундов преобразования (итераций). Один раунд преобразования заключается в следующем. По первому подблоку (подблоку А) формируется двоичный вектор F и два управляющих кода V и U, преобразование двоичного вектора F путем выполнения над ним функции преобразования Е, преобразование второго подблока (подблока В) с помощью первой операции управляемой перестановки, модификация которой выбирается в зависимости от значения первого управляющего кода V, наложение с помощью операции суммирования преобразованного с помощью функции Е двоичного вектора F на второй подблок и преобразование второго подблока с помощью второй операции управляемой перестановки, модификация которой выбирается в зависимости от значения второго управляющего кода U. Процедуры преобразования, реализующие функцию Е, включают выполнение операции сложения по модулю 2³² над подблоком данных и подключом, операции подстановки и операцию циклического сдвига.

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

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

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

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

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

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

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

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

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

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

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

Обобщенная схема итеративного шифрования блоков данных на основе заявляемого способа представлена фиг. 1а, где Q₁ и Q₂ - операционные блоки, осуществляющие управляемые двуместные операции, модификации которых задаются значениями управляющих кодов V и U, подаваемых на управляющий вход соответствующих операционных блоков. А и В - подблоки преобразуемого блока данных; операционный блок Е обозначает процедуры преобразования двоичного вектора F, формируемого в соответствии с формулой F := А. Операционные блоки X₁ и Х₂ обозначают операции, используемые для формирования управляющих кодов V и U вектора. Блоки Х₁ и Х₂ реализуются, например, в виде операционных блоков, выполняющих поразрядное суммирование по модулю два. В данном случае формируются управляющие коды V = A⊕K_r и U = A⊕W_r.
Фиг. 1а соответствует выполнению шифрующих преобразований, а фиг. 1б - выполнению дешифрующих преобразований. В схеме, выполняющей дешифрование, используются операционные блоки, осуществляющие управляемые двуместные операции Q₁ ^-1 и Q₂ ^-1. Варианты построения электронных схем, реализующих управляемые двуместные операции Q₁ и Q₂ и соответствующие им обратные операции Q₁ ^-1 и Q₂ ^-1, описаны в работе [Гуц Н.Д. и др. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации. 2000. N 1. С.8-15]. При выполнении дешифрующих преобразований подключи используются в обратном порядке, т.е. подключи К_r и W_r, использованные на r-том раунде шифрования, при осуществлении дешифрования используются на (R-r+1)-ом раунде. Таким образом, для подключей К'₁ и W'_r, используемых на r-том раунде дешифрования, имеем соотношения К'_r=К_R-r+1 и W'_r = W_R-r+1. После выполнения последнего (R-го) раунда шифрования или дешифрования перестановка подблоков данных не выполняется, что на фиг. 1а и 1б показано горизонтальной пунктирной линией.

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

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

Пример 1: шифрование 64-битового блока данных T
Пример 1 поясняется на фиг. 2а, где Q и Q^-1 - операционные блоки с 32-битовым информационным входом и 32-битовым управляющим входом. Вначале формируется секретный ключ, представленный в виде следующей совокупности n-битовых раундовых подключей: K₁, K₂,..., K₁₆ и W₁, W₂,..., W₁₆. Затем блок данных развивается на два подблока А = Т div 2³² и В = Т mod 2³². После этого шифрование блока данных выполняется в соответствии со следующим алгоритмом:
1. Установить счетчик числа раундов шифрования r := 1.

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

4. Сформировать двоичный вектор F: F:= А.

5. Сформировать по подблоку А и по подключам К_r и W_r управляющий код V′:V′: = A⊕K_r⊕W_r.
6. С помощью операционного блока расширения Х сформировать расширенный 96-битовый управляющий код V″ = V′|V′|V′.
7. Преобразовать двоичный вектор F, выполнив над ним операцию управляемой перестановки: F := P_V"(F).

8. Используя операцию поразрядного суммирования по модулю 2, наложить преобразованный двоичный вектор F на подблок B: B: = B⊕F.
9. Сформировать по подблоку А и подключу W_r управляющий код U: = W_r⊕A.
10. В зависимости от значения V преобразовать подблок В путем выполнения над ним двуместной управляемой операции Q^-1: В := Q_V ^-1 (B,K_r).

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

12. СТОП.

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

Пример 2: шифрование 64-битового блока данных T
Пример 2 поясняется на фиг. 2б, где Q*, - управляемые операционные блоки с 32-битовым информационным входом и 32-битовым управляющим входом. Сформировать секретный ключ, представленный в виде следующей совокупности 32-битовых раундовых подключей: K₁, K₂,..., K₁₀ и W₁, W₂,..., W₁₀. Разбить блок данных на два подблока А = T div 2³² и В = T mod 2³². Шифрование блока данных выполнить в соответствии со следующим алгоритмом:
1. Установить счетчик числа раундов шифрования r := 1 и параметр режима преобразования z = 0 (шифрование).

2. Сформировать по подблоку А и подключу К_r управляющий код V:V: = K_r⊕A.
3. В зависимости от значения V преобразовать подблок В путем выполнения над ним обращаемой управляемой двуместной операции Q^*:B: = Q*V,[e=z]

(B,W_r).
4. Сформировать двоичный вектор F: F := А.

5. Сформировать по подблоку А и по подключам К_r и W_r управляющий код V′:V′: = A⊕K_r⊕W_r.
6. С помощью операционного блока расширения Х сформировать расширенный 96-битовый управляющий код V″ = V′|V′|V′.
7. Преобразовать двоичный вектор F, выполнив над ним операцию управляемой перестановки: F := P_V"(F).

8. Используя операцию поразрядного суммирования по модулю 2, наложить преобразованный двоичный вектор F на подблок B: B: = B⊕F.
9. Сформировать по подблоку А и подключу W_r управляющий код U:U: = W_r⊕A.
10. В зависимости от значения V преобразовать подблок В путем выполнения над ним обращаемой управляемой двуместной операции Q^*: B: = Q*V,[e=z]

(B,K_r).
11. Если r <10, то прирастить r := r + 1, переставить подблоки А и В (т. е. взять двоичный вектор А в качестве двоичного вектора В, а двоичный вектор В - в качестве двоичного вектора A) и перейти к шагу 2.

12. СТОП.

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

Прямые и обратные управляемые двуместные операции, а также обращаемые двуместные операции реализуются с помощью комбинационных электронных схем, обладающих высоким быстродействием. Возможные варианты реализации таких операций описаны в статье [Гуц Н.Д. и др. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации. 2000. N 1. С. 8-15] . Благодаря упрощению процедур преобразования, соответствующих функции Е, повышается скорость шифрования.

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

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

1. Итеративный способ блочного шифрования, включающий формирование секретного ключа, разбиение блока данных на два подблока и выполнение R≥2 раундов шифрования, каждый из которых заключается в формировании по первому поблоку двоичного вектора и двух управляющих кодов, преобразовании двоичного вектора, преобразовании второго подблока с помощью первой управляемой операции, зависящей от значения первого управляющего кода, наложении с помощью операции суммирования преобразованного двоичного вектора на второй подблок и преобразовании второго подблока с помощью второй управляемой операции, зависящей от значения второго управляющего кода, отличающийся тем, что в качестве управляемых операций используют управляемые двуместные операции. 2. Способ по п. 1, отличающийся тем, что в качестве управляемых двуместных операций используют обращаемые управляемые двуместные операции. 3. Способ по п. 1, отличающийся тем, что в качестве управляемых двуместных операций используют взаимно обратные управляемые двуместные операции. 4. Способ по п. 1, отличающийся тем, что управляющий код формируют по секретному ключу и по значению одного из подблоков.