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

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

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

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

Известны способы блочного шифрования данных, см. например стандарт США DES (У.Диффи, М.Э.Хеллмэн. Защищенность и имитостойкость: Введение в криптографию// ТИИЭР. 1979, т, 67, N 3, с. 87-89), способ шифрования по патенту США N 5222139, от 22 июня 1993 г., шифр FEAL-1 и криптоалгоритм B-Crypt (С. Мафтик. Механизмы защиты в сетях ЭВМ, М.: Мир, 1993, с. 49-52). В известных способах шифрование блоков данных выполняют путем формирования ключа шифрования в виде совокупности подключей, разбиения преобразуемого блока данных на подблоки и поочередного преобразования последних с помощью операций подстановки, перестановки и арифметических операций, выполняемых над текущим подблоком и текущим подключом.

Однако, известные способы-аналоги не обладают достаточной стойкостью к дифференциальному криптоанализу (Berson T.A. Differential Cryptanalysis Mod 2³² with application to MD5// EUROCRYPT'92. Hungary, May 24-28, 1992. Proceedings, p. 67-68), так как расписание использования подключей является фиксированным для всех преобразуемых входных блоков.

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

Однако, способ-прототип имеет недостатки, а именно, при программной реализации он не обеспечивает высокой скорости шифрования, необходимой для построения программных систем защиты компьютерной информации, работающих в масштабе реального времени. Например, для микропроцессора Intel 486/100 скорость шифрования не превышает 3 Мбит/с. Этот недостаток связан с тем, что для обеспечения стойкости к дифференциальному криптоанализу задано большое число операций подстановок, медленно выполняемых микропроцессором.

Цель изобретения - разработка способа криптографического преобразования блоков данных, обеспечивающего повышение скорости криптографического преобразования при использовании ЭВМ.

Поставленная цель достигается тем, что в известном способе блочного шифрования, заключающемся в формировании ключа шифрования в виде совокупности K подключей, разбиении блока данных на N подблоков и поочередном преобразовании подблоков, дополнительно формируют двоичные вектора двух типов. Выбирают номер l, где l = 1,2,3,...,K, подключа по структуре двоичного вектора первого типа и с помощью бинарной операции накладывают l-ый подключ на двоичный вектор второго типа. После этого преобразуют очередной подблок (например, i-ый подблок B_i, где i ≤ N путем наложения на данный подблок двоичного вектора второго типа с измененной структурой.

Под формированием двоичного вектора первого типа понимается выделение в структуре подблока или в структуре двоичного вектора второго типа группы разрядов, численное значение которых берется в качестве номера подключа, накладываемого на подблок, или явное формирование двоичного вектора первого типа в отдельном регистре или ячейке памяти вычислительного устройства. Например, неявное формирование двоичного вектора первого типа заключается в следующем: подблок B имеет структуру {10110...11010011} и 8 младших двоичных разрядов, а именно двоичный вектор {11010011} используется в качестве номера выбираемого подключа без записи этого двоичного вектора в отдельный регистр или ячейку памяти.

Могут быть использованы следующие три варианта формирования двоичного вектора первого типа:
1. Двоичный вектор первого типа формируют по структуре j-го подблока B_j, где 1 ≤ j ≤ N. Например, используют значение 8 младших разрядов в качестве номера выбираемого подключа.

2. Двоичный вектор первого типа формируют по структуре двоичного вектора второго типа. Например, вычисляют значение l = (V, mod 2⁸), где операция mod A обозначает остаток от деления численного значения двоичного вектора второго типа V на число A. Значение l используют в качестве номера выбираемого подключа.

3. Двоичный вектор первого типа формируют по структуре j-го подблока B_j, где 1 ≤ j ≤ N, и по значению номера подключа, наложенного на подблок на предыдущем шаге наложения. Например, в качестве номера выбираемого подключа используют число, получаемое в результате наложения на номер l подключа, наложенного на предыдущем шаге наложения на подблок, значения остатка от деления значения B_j на 2⁸:l:= l ⊕ (B_jmod 2⁸) .

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

Могут быть использованы следующие два варианта формирования двоичного вектора второго типа:
1. Двоичный вектор второго типа формируют по структуре подблока B_j, где j ≤ N. Например, выделяют 32-разрядный регистр для хранения значения двоичного вектора второго типа V, записывают в него некоторое начальное число, используя операцию поразрядного суммирования по модулю два (oplus), преобразуют значение V путем наложения подблока B_j на V : V:= V ⊕ B_j. . Возможен вариант, в котором структура подблока B_j предварительно записывается в дополнительную ячейку, соответствующую переменной G, после чего на V накладывают G : V:= V ⊕ G.

2. Двоичный вектор второго типа формируют по структуре, которую он имел на предыдущем шаге наложения на подблок. Например, выделяют 32-разрядный регистр для хранения значения двоичного вектора второго типа V, записывают в него некоторое начальное число A: V := A. Используя операцию поразрядного суммирования по модулю два (oplus), накладывают на V подключ . Затем накладывают V на подблок B_i: B_i:= B_i⊕ V. . Структура, которую имел вектор V на этом шаге наложения на подблок, сохраняется и на V накладывают следующий подключ . После наложения V на очередной подблок структура V опять сохраняется, на V накладывается очередной подключ и т.д. до завершения преобразования всех подблоков.

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

Возможность технической реализации заявляемого способа блочного шифрования поясняется следующим образом. Заявляемый способ ориентирован на шифрование входных блоков с помощью не повторяющихся комбинаций подключей, а именно на задание зависимости расписания использования подключей от структуры блока данных и от ключа шифрования, т.е. на задание псевдослучайной выборки подключей. Этот способ позволяет получить высокую скорость шифрования при использовании ключей шифрования длиной, например, от 256 до 2050 байт. Формирование шифрключа можно осуществить непосредственно вводя его в шифрующую систему, например со съемного носителя информации. Формирование шифрключа можно также осуществить путем ввода пароля с клавиатуры или с машинного носителя информации в генератор псевдослучайных чисел, получая на выходе шифрключ необходимого размера. Известен ряд способов построения генераторов псевдослучайных чисел, см. например (Брикелл Э.Ф., Одлижко Э.М. Криптоанализ: Обзор новейших результатов// ТИИЭР. 1988, т. 76, N 5, с. 87-89). Сложность процедур формирования ключа не влияет на скорость шифрования, поскольку эту процедуру выполняют однократно при идентификации пользователя по паролю в момент включения шифрующего устройства или вызова шифрующей программы.

Заявляемый способ может быть реализован с помощью ЭВМ или вычислительного устройства, представленного блок-схемой на фиг. 1, где блок 1 - устройство ввода пароля пользователя; блок 2 - блок генерации шифрключа; блок 3 - блок памяти устройства шифрования; блок 4 - операционный блок устройства шифрования, содержащий несколько регистров, например три регистра; блок 5 - устройство шифрования; 6 - шина передачи информационных сигналов пароля пользователя; 7 - шина передачи информационных сигналов шифрключа; 8 - шина передачи информационных сигналов подключей и передачи информационных сигналов входных данных и информационных сигналов преобразуемых подблоков; 9 - шина адресации; 10 - шина ввода входных данных; 11 - шина вывода шифртекста.

Используя блок 1 вводят секретный ключ, информационные сигналы которого 6 подают на вход блока 2. В блоке 2 формируют шифрключ и соответствующие ему информационные сигналы по шине 7 передают в блок памяти 3. После этого устройство шифрования 5 содержит в памяти шифрключ и готово к выполнению операций шифрования. Данное инициализированное состояние устройства сохраняется в течение всего времени работы законного пользователя. Входной блок вводят по шине 10 в операционный блок 4 и затем по шине 8 в блок памяти 3.

Входной блок данных представляют в виде совокупности подблоков, записанных по фиксированным адресам в блок памяти 3. Информационные сигналы подблока B_j по шине 8 вводят в первый регистр операционного блока 4 (в случае ЭВМ - в один из регистров микропроцессора). Во втором регистре формируют двоичный вектор первого типа, например, записывая в него содержимое 8 младших разрядов подблока B_j. В четвертый регистр вводят подблок B_i. В третьем регистре блока 4 формируют двоичный вектор второго типа, например путем записи в регистр 1-го подключа. Информационные сигналы двоичного вектора первого типа подают на шину адресации 9 и тем самым задают выбор номера l текущего подключа Q_l по значению двоичного вектора первого типа. На двоичный вектор второго типа накладывают с помощью бинарной операции под ключ, расположенный по адресу, установленному во втором регистре, т.е. по значению двоичного вектора первого типа. Подблок B_i преобразуют путем наложения на него с помощью бинарной операции двоичного вектора второго типа, структура которого была предварительно изменена наложением на него подключа. После этого переходят к преобразованию следующего подблока. На каждом новом шаге преобразования текущего подблока в третьем регистре аккумулируется значение еще одного подключа, выбираемого по текущей структуре подблока B_j. Под наложением понимается выполнение бинарной операции между двумя операндами, например подблоком B_i и двоичным вектором второго типа V, и заменf исходного значения первого операнда на значение результата выполнения бинарной операции. Аналитически процедура наложения записывается в виде формулы B_i := B_i * V, где знак * обозначает бинарную операцию, знак := - операцию присваивания. Схема наложения показана на фиг. 2, где 12 - подблок B_i с исходной структурой; 13 - двоичный вектор второго типа V; 14 - блок, выполняющий бинарную операцию *; 15 - подблок B_i с измененной структурой.

В качестве бинарной операции могут быть использованы простые арифметические операции сложения (+) и вычитания (-) по модулю 2³², поразрядного суммирования по модулю 2(⊕) , которые быстро исполняются микропроцессором. Могут быть использованы также более сложные бинарные операции, определенные на основе перечисленных и на основе быстро выполняемых унарных операций, т.е. операций над одним двоичным вектором, например на основе операции циклического сдвига ^>>d>> на d бит, где 1 ≤ d ≤ b-1, где b - размер подблока в битах. Например, операцию * над 32-битовыми векторами можно определить в следующих вариантах, соответствующих формулам:
.

На фиг. 3 показана структура бинарной операции, задаваемой формулой (3), где блоки 16 и 17 - это входные операнды X и Y, блок 18 выполняет операцию циклического сдвига на 1 бит вправо, блок 19 выполняет операцию циклического сдвига на 7 бит вправо, блок 20 выполняет операцию поразрядного суммирования по модулю два, блок 21 выполняет составную бинарную операцию ^'*'. Использование в заявляемом способе более сложных бинарных операций является допустимым, поскольку в этом случае также обеспечивается высокая скорость шифрования, а увеличение числа типов используемых операций дополнительно повышает стойкость шифра.

Формируемый двоичный вектор первого типа имеет структуру зависящую от подблока B_j или от структуры двоичного вектора второго типа. В вариантах заявляемого способа, в которых задано формирование двоичного вектора первого типа по структуре двоичного вектора второго типа, используется вариант формирования двоичного вектора второго типа по структуре подблока B_j. Это задает зависимость выбора текущего под ключа, накладываемого на подблок B_i, от структуры подблока B_j. Поскольку структура B_j в ходе преобразования изменяется в зависимости от выбираемых подключей, то это обусловливает псевдослучайный характер изменения номера подключа, выбираемого на текущем шаге выборки. Формируемый двоичный вектор второго типа имеет структуру, зависящую от совокупности подключей выбранных на предыдущих шагах выборки, поэтому он принимает значения, отличные от значений подключей, причем двоичный вектор второго типа принимает число различных значений, равное примерно 2³², если его длина составляет 32 бита, тогда как число подключей обычно составляет не более 2¹².

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

Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области способов и устройств для криптографического преобразования данных. Целью изобретения является повышение скорости криптографического преобразования при использовании ЭВМ. Способ включает формирование ключа шифрования в виде совокупности подключей, разбиение блока данных на подблоки и поочередное преобразование подблоков. Отличается от известных способов тем, что дополнительно формируют двоичные вектора двух типов, с помощью бинарной операции накладывают l-ый подключ, где l = 1,2,3,...,K K ≥ 8- число подключей, на двоичный вектор первого типа, двоичный вектор первого типа с помощью бинарной операции накладывают на i-ый подблок B_i, где i = 1,2,3, . . . N, N ≥ 2 - число подблоков, причем номер l подключа выбирают по значению двоичного вектора второго типа. Двоичный вектор первого типа формируют, например, по структуре j-го подблока B_j, где j = 1,2,3,...N. Двоичный вектор второго типа формируют, например, по структуре двоичного вектора первого типа. 5 з.п.ф-лы, 3 ил.

1. Способ криптографического преобразования блоков данных, заключающийся в формировании ключа шифрования в виде совокупности K подключей, разбиении блока данных на N подблоков и поочередном преобразовании подблоков, отличающийся тем, что дополнительно формируют двоичные векторы двух типов, выбирают номер l, где l ≤ K, подключа по структуре двоичного вектора первого типа, с помощью бинарной операции накладывают l-ый подключ на двоичный вектор второго типа и преобразуют i-ый подблок, где i ≤ N, путем наложения на него с помощью бинарной операции двоичного вектора второго типа с измененной структурой. 2. Способ по п.1, отличающийся тем, что двоичный вектор первого типа формируют по структуре j-го подблока. 3. Способ по п.1, отличающийся тем, что двоичный вектор первого типа формируют по структуре двоичного вектора второго типа. 4. Способ по п.1, отличающийся тем, что двоичный вектор первого типа формируют по структуре j-го подблока и по значению номера подключа, использованного на предыдущем шаге наложения. 5. Способ по п.1, отличающийся тем, что двоичный вектор второго типа формируют по структуре j-го подблока. 6. Способ по п.1, отличающийся тем, что двоичный вектор второго типа формируют по структуре, которую он имел на предыдущем шаге наложения на подблок.