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

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

В совокупности признаков заявляемого способа используются следующие термины:
- секретный ключ представляет собой двоичную информацию, известную только законному пользователю;
- криптографическое преобразование - это преобразование цифровой информации, которое обеспечивает влияние одного бита исходных данных на многие биты выходных данных, например, с целью защиты информации от несанкционированного чтения, формирования цифровой подписи, выработки кода обнаружения модификаций; важными видами криптографического преобразования являются одностороннее преобразование, хэширование и шифрование;
- хэширование информации есть некоторый способ формирования так называемого хэш-кода, размер которого является фиксированным (обычно 128 бит) для сообщений любого размера; процедуры хэширования обеспечивают зависимость хэш-кода от каждого бита сообщения;
- шифрование есть процесс, преобразования информации, который зависит от секретного ключа и преобразует исходный текст в шифртекст (криптограмму), представляющий собой псевдослучайную последовательность знаков, из которой получение информации без знания секретного ключа практически неосуществимо;
- дешифрование есть процесс, обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании секретного ключа;
- шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием секретного ключа; шифр может быть реализован в виде программы для ЭВМ или в виде отдельного устройства;
- двоичный вектор - это некоторая последовательность нулевых и единичных битов, например (101101011); конкретная структура двоичного вектора может быть интерпретирована как двоичное число, если считать, что позиция каждого бита соответствует двоичному разряду, т.е. двоичному вектору может быть сопоставлено численное значение, которое определяется однозначно структурой двоичного вектора;
- криптоанализ - метод вычисления секретного ключа для получения несанкционированного доступа к зашифрованной информации или разработка метода, обеспечивающего доступ к зашифрованной информации без вычисления секретного ключа;
- одностороннее преобразование - это такое преобразование g-битового входного блока данных в g-битовый выходной блок данных, которое позволяет легко вычислить выходной блок по входному блоку, а вычисление входного блока, который бы преобразовывался в случайно выбранный выходной блок, является практически невыполнимой задачей;
- криптостойкость является мерой надежности защиты зашифрованной информации и представляет собой трудоемкость, измеренную в количестве элементарных операций, которые необходимо выполнить для восстановления информации по криптограмме при знании алгоритма преобразования, но без знания секретного ключа; в случае односторонних преобразований под криптостойкостью понимается сложность вычисления входного значения блока по его выходному значению;
- операции циклического сдвига, зависящие от преобразуемых подблоков или зависящие от двоичного вектора, - это операции циклического сдвига на число бит, задаваемое значением подблока или значением двоичного вектора; операции циклического сдвига влево (вправо) обозначаются знаком "<<<" (">>>"), например запись B <<< A обозначает операцию циклического сдвига влево подблока B на число бит, равное значению двоичного вектора A; подобные операции являются базовыми для шифра RC5;
- одноместная операция - это операция, выполняемая над одним операндом (блоком данных или двоичным вектором); значение подблока после выполнения некоторой данной одноместной операции зависит только от его начального значения; примером одноместных операций являются операции циклического сдвига;
- двуместная операция - это операция, выполняемая над двумя операндами; результат выполнения некоторой данной двуместной операции зависит от значения каждого операнда; примером двуместных операций являются операции сложения, вычитания, умножения и др.;
- операция конкатенации - это операция объединения нескольких двоичных векторов, в результате которой формируется новый двоичный вектор, включающий все биты каждого из объединяемых двоичных векторов, причем взаимное расположение битов, соответствующих исходным двоичным векторам, не изменяется; например конкатенация двоичных векторов 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 и К и поочередного изменения последних путем выполнения операции поразрядного суммирования по модулю два над подблоком L и двоичным вектором, который формируется как выходное значение некоторой функции F от значения подблока R. После этого подблоки переставляются местами. Функция F в указанном способе реализуется путем выполнения операций перестановки и подстановки, выполняемых над подблоком 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 и B и поочередного преобразования подблоков. Подблоки преобразуются путем выполнения над ними одноместных и двуместных операций. В качестве двуместных операций используются операции сложения по модулю 2ⁿ, где n = g/2 = 8, 16, 32, 64, и операция поразрядного суммирования по модулю 2. В качестве одноместной операции используется операция циклического сдвига влево, причем число бит, на которое сдвигается преобразуемый подблок, зависит от значения другого подблока, что определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Двуместная операция выполняется над подблоком и подключом, а также над двумя подблоками. Характерным для способа RC5 является использование операции циклического сдвига, зависящей от значения входного блока. Подблок, например подблок B, преобразуют путем наложения поблока A на подблок B с помощью операции поразраядного суммирования по модулю 2, т.е. выполняется операция поразрядного суммирования по модулю 2 (обозначаемая знаком "⊕" ) над подблоками A и B и значение, получаемое после выполнения этой операции, присваивается подблоку B. Это записывается в виде соотношения B:= B ⊕ A, где знак ":=" обозначает операцию присваивания. После этого над подблоком B выполняют операцию циклического сдвига влево на число бит, равное значению подблока A: B: = B <<< A. Затем над подблоком B и одним из подключей S выполняют операцию суммирования по модулю 2ⁿ, где n - длина подблока в битах: B: = (B + S) mod 2ⁿ. После этого аналогичным образом преобразуется подблок A. Выполняется несколько таких шагов преобразования обоих подблоков. Недостатком шифра RC5 является недостаточная стойкость к дифференциальному криптоанализу.

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

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

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

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

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

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

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

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

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

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

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

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

Конкретный вид (или тип) управляемой операции перестановки P длины n характеризуется упорядоченным множеством где π_V - фиксированные перестановки длины n, которые в общем случае являются различными, V - значение управляющего кода, m - разрядность управляющего кода. Могут быть сконструированы управляемые операционные блоки перестановок со значением m, удовлетворяющим следующим условиям: 1) m < n, 2) m = n и 3) m > n. Для практического построения устройств криптографического преобразования наибольший интерес представляют P-блоки со значением n = 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:= π(V). Таким образом, в качестве управляющего кода V могут использоваться (1) подключи шифрования, формируемые по секретному ключу и (2) подблоки информационного блока.

Управляемая перестановка действует на информационный блок T следующим образом. По значению управляющего кода V выбирается модификация π_V, в соответствии с фиксированной перестановкой π_V осуществляется перестановка битов информационного блока T, в результате которой формируется значение P_V(T).

Управляемые операционные блоки перестановок могут быть легко реализованы в виде несложных быстродействующих комбинационных электронных схем, использующих в качестве базового узла элементарный переключатель. На фиг. 2а показана блок-схема элементарного переключателя P_2/1, где u - управляющий сигнал, а и b - входные сигналы данных, c и d - выходные сигналы данных. При u = 1 линия a коммутируется с линией c, а линия b - с линией d. При u = 0 линия a коммутируется с линией d, а линия b - с линией c. Таким образом, при значении управляющего бита u = 0 осуществляется перестановка двух входных битов, а при u = 1 входные биты не переставляются.

На фиг. 2 представлены P-блоки следующих видов: P_4/4 (б), P_16/32 (в) и P_32/80 (г), где использована запись P_n/m для обозначения P-блока с n-битовым информационным входом и m-битовым управляющим входом. Для блока P_4/4 на фиг. 2б предусмотрено использование 4-разрядного управляющего кода. Он реализует 16 уникальных перестановок из 24 существующих перестановок четырех битов. Из схемы этого блока легко установить, что он реализует перестановки равновероятного смещения, т. е. для случайного значения управляющего кода каждый входной бит с одинаковой вероятностью может переместиться в любой разряд выходного двоичного вектора. Операционный блок P_16/32 (фиг. 2в) построен на основе восьми блоков P_4/4. В блоке P_16/32 16 бит преобразуемого двоичного вектора поступают на вход четырех блоков P_4/4 первой ступени. Выход первой ступени соединен со входом второй таким образом, что все выходные биты каждого из четырех блоков P_4/4 первой ступени поступают на вход разных блоков P_4/4 второй ступени. Поскольку для случайного значения управляющего кода любой входной бит на выходе первой ступени с равной вероятностью может оказаться на входе любого 4-битового блока второй ступени, то на выходе второй ступени этот бит может оказаться с одинаковой вероятностью в любом из 16 двоичных разрядов. Легко показать, что блок P_32/80 (фиг. 2г) также формирует перестановки равновероятного смещения. Он состоит из двух ступеней. Первая ступень включает два блока P_16/32, вторая - 16 элементарных переключателей, на вход которых подаются биты с выхода двух разных блоков P_16/32. Рассмотренные выше P-блоки типа P_4/4, P_16/32, P_32/80 реализуют уникальные перестановки для каждого значения управляющего кода. Аналогичным способом могут быть построены 64- и 128-битовые управляемые P-блоки.

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

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

Пример 1: шифрование 64-битового блока данных T. Пример 1 поясняется на фиг. 3а, где P и P^-1 - управляемые операционные блоки с 32-битовым информационным входом и 64-битовым управляющим входом. Сформировать секретный ключ, представленный в виде следующей совокупности n-битовых раундовых подключей: K₁, K₂, ..., K₁₆ и Q₁, Q₂, ..., Q₁₆. Разбить блок данных на два подблока: A = T div 2³² и B = T mod 2³². Шифрование блока данных выполнить в соответствии со следующим алгоритмом.

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

2. Сформировать по подключу K_r управляющий код V: V:= K_r|K_r, где | - операция конкатенации.

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

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

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

6. Используя операцию поразрядного суммирования по модулю 2, наложить преобразованный двоичный вектор F на подблок В: B:= B ⊕ F.
7. Сформировать по подключу Q_r управляющий код V : V:= Q_r|Q_r.
8. Преобразовать подблок В, выполнив над ним управляемую операцию перестановки, осуществляемую операционным блоком P^-1, в зависимости от значения управляющего кода: B:= P-1V

10. СТОП.

Преобразования, соответствующие шагам 3 и 5, выполняются параллельно. Блок криптограммы C формируется путем объединения преобразованных двоичных векторов A и B: C = A|B. Дешифрование блока криптограммы осуществляется с помощью этого же алгоритма, за исключением того, что при выполнении шагов 2 и 5 используется подключ K_17-r вместо подключа K_r, а при выполнении шага 7 - подключ Q_17-r вместо Q_r.

Пример 2: шифрование 64-битового блока данных T. Пример 2 поясняется на фиг. 3б, где P, P', P'' и P^-1 - управляемые операционные блоки с 32-битовым информационным входом и 64-битовым управляющим входом. Сформировать секретный ключ, представленный в виде следующей совокупности n-битовых раундовых подключей: K₁, K₂, ..., K₁₀ и Q₁, Q₂, .., Q₁₀. Разбить блок данных два подблока: A = T div 2³² и B = T mod 2³². Шифрование блока данных выполнить в соответствии со следующим алгоритмом.

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

2. Сформировать по подключу K_r и подблоку A управляющий код V₁: V₁:= K_r|A.
3. В зависимости от значения V₁ преобразовать подблок B путем выполнения управляемой операции перестановки: .

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

5. Сформировать по двоичному вектору F управляющий код V₂: V₂:= F|F.
6. Сформировать по подключу Q_r управляющий код V₃: V₃:= Q_r|Q_r.
7. Преобразовать подключ K_r, выполнив над ним управляемую операцию перестановки, осуществляемую операционным блоком P', в зависимости от значения управляющего кода V₂:
8. Преобразовать двоичный вектор F, выполнив над ним управляемую операцию перестановки, осуществляемую операционным блоком P'', в зависимости от значения управляющего кода V₃:
9. Преобразовать двоичный вектор F, наложив на него с помощью операции суммирования по модулю 2³² преобразованный подключ K_r: F:= F+K_r mod 2³².

10. Используя операцию поразрядного суммирования по модулю 2, наложить преобразованный двоичный вектор F на подблок B: B:= B ⊕ F.
11. Сформировать по подключу Q_r и подблоку данных A управляющий код V₄: V₄:= Q_r|A.
12. Преобразовать подблок B, выполнив над ним управляемую операцию перестановки, осуществляемую операционным блоком P^-1 в зависимости от значения управляющего кода V₄:
13. Если r < 10, то прирастить r:=r+1, переставить подблоки A и B и перейти к шагу 2.

14. СТОП.

Шаги 3, 7 и 8 выполняются параллельно. Блок криптограммы C представляет собой конкатенацию преобразованных подблоков A и B: C = A|B. Дешифрование блока криптограммы осуществляется с помощью этого же алгоритма, за исключением того, что при выполнении шагов 2, 7 и 9 используется подключ K_11-r вместо подключа K_r, а при выполнении шагов 6 и 11 - подключ Q_11-r вместо Q_r.

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

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

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

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