Патент на изобретение №2172075

(54) ИТЕРАТИВНЫЙ СПОСОБ БЛОЧНОГО ШИФРОВАНИЯ

(57) Реферат:

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

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

В совокупности признаков заявляемого способа используются следующие термины:
– секретный ключ представляет из себя двоичную информацию, известную только законному пользователю;
– подключ – часть секретного ключа;
– шифрование есть процесс, преобразования информации, который зависит от секретного ключа и преобразует исходный текст в шифртекст (криптограмму), представляющий собой псевдослучайную последовательность знаков, из которой получение информации без знания секретного ключа практически неосуществимо;
– дешифрование есть процесс обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании секретного ключа;
– шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием секретного ключа;
– двоичный вектор – это некоторая последовательность нулевых и единичных битов, например (101101011); двоичный вектор может быть интерпретирован как двоичное число, если считать, что позиция каждого бита соответствует двоичному разряду;
– криптоанализ – метод вычисления секретного ключа для получения несанкционированного доступа к зашифрованной информации или разработка метода, обеспечивающего доступ к зашифрованной информации без вычисления секретного ключа;
– криптоаналитик – лицо, выполняющее криптоанализ;
– криптостойкость является мерой надежности защиты зашифрованной информации и представляет собой трудоемкость, измеренную в количестве элементарных операций, которые необходимо выполнить для восстановления информации по криптограмме при знании алгоритма преобразования, но без знания секретного ключа;
– двуместная операция – это операция выполняемая над двумя операндами; результат выполнения некоторой данной двуместной операции зависит от значения каждого операнда; примером двуместных операций являются операции сложения, вычитания, умножения и др.;
⁶ H 04 L 9/28, БИ N 30 от 27.10.1999]; в формулах управляемую двуместную операцию будем обозначать записью B: = Q_V (А, В), где А, В – операнды, V – управляющий код;
– модификация управляемой двуместной операции – двуместная операция, соответствующая преобразованию двух операндов при фиксированном значении управляющего кода.

Известны итеративные способы блочного шифрования, см. например, способ, используемый в шифре DES [B.Schneier, “Applied Cryptography”, Second Eddition, John Wiley fe Sons, Inc., New York,1966, p.270-277]. В данном способе шифрование блоков данных выполняют путем формирования секретного ключа, разбиения преобразуемого блока данных на два подблока L и R и поочередного изменения последних путем выполнения операции поразрядного суммирования по модулю два над подблоком L и двоичным вектором, который формируется как выходное значение некоторой функции F от значения подблока R. После этого подблоки переставляются местами и указанные процедуры, составляющие один раунд шифрования, повторяются. В шифре DES выполняются 16 раундов шифрования. Функция F в указанном способе реализуется путем выполнения операций перестановки и подстановки, выполняемых над подблоком R. Данный способ обладает высокой скоростью преобразования при реализации в виде специализированных электронных схем. Однако известный способ-аналог использует секретный ключ малого размера (56 бит), что делает его уязвимым к криптоанализу на основе подбора ключа. Последнее связано с высокой вычислительной мощностью современных ЭВМ.

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

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

Однако способ прототип имеет недостатки, а именно, во всех раундах шифрования наложение преобразованного двоичного вектора F на подблок В осуществляется с помощью одной и той же двуместной операции, а именно, с помощью операции что создает предпосылки для атаки этого шифра методом дифференциального криптоанализа [B.Schneier, “Applied Cryptography”, Second Eddition, John Wiley fe Sons, Inc., New York,1966, p.285-290]. Поэтому для обеспечения высокой стойкости к дифференциальному криптоанализу требуется выполнить большое число раундов шифрования, что снижает скоростные показатели шифра.

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

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

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

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

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

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

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

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

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

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

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

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

Обобщенная схема итеративного способа блочного шифрования данных на основе заявляемого способа представлена фиг. 1, где
– операционный блок, выполняющий управляемую двуместную операцию,
V – управляющий код,
A и B – подблоки преобразуемого блока данных,
E – операционный блок, обозначающий процедуры преобразования двоичного вектора F, после формирования последнего в соответствии с формулой F:=A.

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

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

Могут быть сконструированы операционные блоки, выполняющие управляемую двуместную операцию, со значением m, удовлетворяющим следующим условиям: 1) m < n, 2) m = n и 3) m > n. Для практического построения устройств шифрования наибольший интерес представляют блоки со значением n = 32,64,128 и значением m равным или в два и более раз превышающем значение n. Например, могут быть заданы значения m = 32,64,128,256. В случае m > n управляющий код может быть сформирован, например, путем:
1) повторения подблока данных: V = A|A|…|A,
2) объединения нескольких подключей: V = K₁|K₂|…|K_w, где w – натуральное число,
3) объединения подключей и подблока данных: V = K₁|A|K₂|…|A
После такого объединения управляющий код может быть подвергнут дополнительному преобразованию, например, над ним может быть осуществлена операция перестановки битов. Таким образом, в качестве управляющего кода V могут использоваться (1) подключи, формируемые по секретному ключу и (2) подблоки информационного блока.

⁶ H 04 L 9/28, БИ N 30 от 27.10.1999]. Современная микроэлектронная технология позволяет изготавливать недорогие электронные устройства шифрования, основанные на управляемых двуместных операциях и обеспечивающие высокую скорость шифрования.

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

Пример 1. Шифрование 64-битового блока данных Т. Пример 1 поясняется на фиг. 1б, где – операционный блок, выполняющий управляемую двуместную операцию над двумя n-битовыми операндами – подблоком данных В и преобразованным значением двоичного вектора F – в зависимости от 32-битового управляющего кода, сформированного по подблоку данных А. Секретный ключ формируется в виде следующей совокупности 32-битовых подключей: K₁, K₂,…, K₁₆. Блок данных разбивается на два подблока А = Т div 2³² и B = Т mod 2³². Шифрование блока данных выполнить в соответствии со следующим алгоритмом.

1. Установить счетчик числа раундов шифрования r:=1.

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

3. Используя подключ K_r, преобразовать двоичный вектор F в соответствии с процедурами преобразования двоичного вектора, выполняемыми в способе-прототипе: F:= E(F, К_r).

4. Сформировать по подблоку данных А управляющий код V: V:= А.

5. В зависимости от значения V преобразовать подблок В путем выполнения управляемой двуместной операции, используя в качестве операндов подблок В и преобразованный двоичный вектор F:
B: = Q_V(B,F).

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

10. Стоп.

Дешифрование блока криптограммы осуществляется с помощью этого же алгоритма, за исключением того, что при выполнении шага 3 используется подключ K_17-r вместо подключа K_r, а на шаге 5 вместо двуместной операции Q_V(B,F) выполняется обратная ей управляемая двуместная операция Q^–_V¹ (B,F).

Пример 2. Шифрование 64-битового блока данных Т. Пример 2 (см. фиг. 2а) совпадает с примером 1 за исключением того, что в приведенном выше алгоритме шаг 4 соответствует формированию управляющего кода по соответствующему подключу. В примере 2 этот шаг преобразования имеет следующий вид: V:=K_r.

4. Сформировать по подключу K_r управляющий код V: V:= K_r.

При дешифровании блока криптограммы в примере 2 на шагах 3 и 4 используется подключ K_17-r вместо подключа K_r, а на шаге 5 вместо двуместной операции Q_V(B,F) выполняется обратная ей управляемая двуместная операция Q^–_V¹

Пример 3. Шифрование 64-битового блока данных Т. Пример 3 поясняется на фиг. 2б, где операционный блок выполняет управляемую двуместную операцию над подблоком данных В и преобразованным значением двоичного вектора F в зависимости от 64-битового управляющего кода, сформированного по подблоку данных А и по подключу, используемому на соответствующем раунде шифрования. Возможная структура операционного блока, выполняющего управляемую двуместную операцию в данном примере, показана на фиг. 3, где
– полный сумматор;
& – логический элемент, выполняющий операцию И;
b_h (h = 1,2,…32) – биты операнда B = (b₃₂,.., b₂, b₁);
f_h (h = 1,2,…32) – биты операнда F = (f₃₂,.. f₂, f₁);
v_j (j = 1,2,…64) – биты управляющего кода V =(v₆₄,…,v₂,v₁).

Операционный блок на данном чертеже реализует управляемую двуместную операцию, выполняемую над 32-битовыми операндами и имеющую 2⁶⁴ различных модификаций, задаваемых 64-битовым управляющим кодом.

Секретный ключ в примере 3 формируется в виде следующей совокупности 32-битовых подключей: K₁, K₂,…,K₁₆. Блок данных разбивается на два подблока А = Т div 2³² и В = Т mod 2³². Шифрование блока данных выполняется в соответствии со следующим алгоритмом.

1. Установить счетчик числа раундов шифрования r:= 1.

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

3. Используя под ключ K_r, преобразовать двоичный вектор F в соответствии с процедурами преобразования двоичного вектора, выполняемыми в способе прототипе: F:=E(F,K_r).

4. Сформировать по подключу K_r и подблоку А управляющий код V: V:= K_r|A .

5. Используя управляемую двуместную операцию, наложить преобразованный двоичный вектор F на подблок В: B:= Q_V(B,F).

6. Если r < 16, то прирастить r:= r + 1, переставить подблоки А и В и перейти к шагу 2.

7. Стоп.

Для осуществления дешифрования блока криптограммы используется этот же алгоритм, за исключением того, что при выполнении шагов 3 и 4 используется подключ K_17-r вместо подключа К_r, а на шаге 5 вместо двуместной операции Q_V(B, F) выполняется обратная ей управляемая двуместная операция Q^–_V¹(B,F) В общем случае процедуры шифрования и дешифрования выполняются с помощью разных электронных схем, поскольку в этих двух режимах используются взаимно обратные управляемые двуместные операции. Упрощение аппаратной реализации может быть достигнуто применением одной и той же электронной схемы для выполнения прямой и соответствующей обратной управляемой двуместной операции. Выбор режима выполнения прямой управляемой двуместной операции или режима выполнения обратной управляемой двуместной операции задается некоторым управляющим битом i, который одновременно задает также и очередность использования подключей. Например, при i = 1 устанавливается прямой порядок использования подключей и прямая управляемая двуместная операция, а при i = 0 – обратный порядок использования подключей и обратная управляемая двуместная операция.

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

На фиг. 4 использованы следующие обозначения:
– элемент, выполняющий операцию суммирования по модулю два над двумя входными битами;
& – логический элемент, выполняющий операцию И.

a и f – биты операндов А и F, относящиеся к соответствующим разрядам;
g – бит переноса, передаваемый на вход обратимого сумматора следующего разряда;
u – бит переноса, поступающий с выхода обратимого сумматора предыдущего разряда.

Обратимый сумматор на фиг. 4 при фиксированном значении u и i = 1 реализует некоторую операцию Q’_u над двумя входными битами b и f, т.е. он формирует выходной бит, y = Q’_u(b,f) и бит переноса g. Для того же значения u при i = 0 обратимый сумматор реализует операцию над двумя битами являющуюся обратной по отношению к первой операции, т.е. по y и f она позволяет вычислить бит b:b = (y,f), причем формируемый при этом бит переноса g равен биту переноса, формируемому при выполнении прямой операции Q’ для соответствующих значений битов b, f и u.

На фиг. 5 использованы следующие обозначения:
_i – обратимый сумматор;
& – логический элемент, выполняющий операцию И;
b_h (h = 1,2,…,n) – биты операнда В = (b_n,…, b₂, b₁);
f_h (h = 1,2,…,n) – биты операнда F = (f_n,…, f₂, f₁);
v_h (h = 1,2,…,n) – биты управляющего кода V = (v_n,…,v₂, v₁).

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

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

Современная микроэлектронная технология позволяет легко изготовить быстродействующие операционные блоки, выполняющие управляемую двуместную операцию над 32-, 64- и 128-битовыми операндами. Заявляемый способ может быть реализован, например, в специализированных устройствах, обеспечивающих скорость шифрования более 1 Гбит/с, достаточную для обеспечения защиты данных, передаваемых по скоростным оптоволоконным каналам связи, в масштабе реального времени.

Формула изобретения

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

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

3. Способ по п. 1, отличающийся тем, что управляющий код формируют по секретному ключу.

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

РИСУНКИ

MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 28.12.2001

Номер и год публикации бюллетеня: 11-2003

Извещение опубликовано: 20.04.2003