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

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

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

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

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

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

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

Наиболее близким по своей технической сущности к заявляемому способу блочного шифрования является способ, описанный в патенте США N 5222139, от 22 июня 1993 г. , в котором для противодействия наиболее сильным способам криптоанализа, которые основаны на предварительном анализе свойств конкретных наборов шифрующих процедур, совокупность используемых процедур шифрования (составляющих уникальный для данного пользователя алгоритм шифрования) выбирается в зависимости от секретного ключа пользователя. Криптоаналитику являются известными правила формирования алгоритма шифрования, однако ему не известен секретный ключ пользователя, а следовательно является неизвестной и конкретная модификация алгоритма шифрования, сформированного в зависимости от секретного ключа.

Способ-прототип включает в себя формирование ключа шифрования в виде совокупности подключей, генерацию машинного кода программы шифрования, разбиение входного 64-битового блока данных на два 32-битовых подблока и поочередное преобразование подблоков. Способ-прототип реализуется на базе библиотеки заранее описанных шифрующих процедур, являющихся возможными фрагментами программы шифрования. Библиотека шифрующих процедур включает в себя таблицы операций подстановок (или операций замещения в терминах описания патента США N 5222139) и перестановок элементов преобразуемого блока данных, операции циклического смещения вправо и влево битов преобразуемых подблоков, а также операции поразрядного сложения по модулю два или сложения по модулю 2³², выполняемых между подблоком и одним из подключей. Генерация машинного кода состоит в следующем. В зависимости от секретного ключа пользователя выбираются некоторые шифрующие процедуры, устанавливается очередность их выполнения и число циклов выполнения каждой из них. После этого генерируется машинный код, который соответствует выполнению установленного по секретному ключу алгоритма преобразования блоков данных. В наборах шифрующих процедур расписание использования подключей является фиксированным, т.е. в формируемых модификациях шифрующих процедур подключи входят в процедуры преобразования независимо от преобразуемых данных (для всех блоков данных на заданных шагах использования подключей выбираются одни и те же подключи). Задание непредопределенности (недетерминированности) алгоритма шифрования существенно повышает стойкость шифра. Чем больше число потенциально реализуемых модификаций процедур шифрования, тем выше стойкость шифра, поскольку выбор конкретной модификации является случайным (т.к. зависит от случайно выбираемого секретного ключа).

Однако, способ-прототип имеет недостатки, а именно, при программной реализации при числе возможных модификаций алгоритма шифрования более 10⁹ он не обеспечивает высокой скорости шифрования, необходимой для построения программных систем защиты компьютерной информации, работающих в масштабе реального времени. Данный недостаток связан с тем, что в способе-прототипе число модификаций зависит от скорости шифрования: при скорости шифрования около 4 Мбит/с (для вычислительного комплекса HITTACHI Workstation 2050/32, являющегося более производительным по сравнению с ЭВМ на базе массового процессора Intel 486/100), число потенциально возможных модификаций составляет около 10¹⁹. Повышение скорости шифрования может быть достигнуто сокращением числа последовательно выполняемых составных шифрующих процедур, однако уменьшение их числа приводит к снижению неопределенности в выборе модификации алгоритма шифрования. При увеличение скорости, например, до 8 Мбит/с число возможных модификаций составляет всего около 10⁹, т.е. вклад того фактора, что алгоритм шифрования не является предопределенным, в стойкость шифра резко падает.

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

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

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

Изменение структуры двоичного вектора в процессе шифрования блока данных не является предопределенным, а зависит от структуры блока данных и от ключа шифрования. Могут быть использованы следующие два варианта формирования двоичного вектора. В первом варианте двоичный вектор формируют по структуре j-того подблока B_j, где i≤j≤N, причем i≠j. Во втором варианте двоичный вектор формируют по структуре j-того подблока B_j, где i≤j≤N, причем i≠j, и по значению номера подключа, наложенного на подблок на предыдущем шаге наложения. Например, пусть на предыдущем шаге наложения был использован подключ с номером {10111011}, записанным в регистре адресации A, а текущим значением подблока B_j является {0101...01011001}. Восемь младших разрядов подблока B_j поразрядно суммируются по модулю два со значением двоичного вектора в регистре A, а полученный результат {11100010} записывают в регистр A и используют в качестве номера l подключа, накладываемого на подблок B_i.

Перечисленная совокупность существенных признаков обеспечивает более высокую скорость шифрования при равном или большем числе возможных модификаций алгоритма шифрования благодаря следующему. Расписание использования подключей для каждого блока данных является непредопределенным и уникальным, что обеспечивает высокую стойкость ко всем известным способам криптоанализа, включая дифференциальный криптоанализ, при использовании даже простых арифметических операций, которые быстро выполняются микропроцессором. Смысл выбора подключа, который накладывается на подблок на текущем шаге, по специально формируемому двоичному вектору состоит в том, чтобы сделать выбор подключа непредопределенным для каждого шага преобразования подблоков. Это обеспечивает высокую стойкость шифрования при любых наборах операций, используемых для наложения подключей на подблоки, и поэтому позволяет произвольно модифицировать операции преобразования. При использовании такого механизма выборки подключей модифицирование алгоритма шифрования можно выполнить путем выбора конкретной совокупности операций преобразования подблоков в зависимости от секретного ключа пользователя. Генерирование машинного кода программы шифрования соответствует наборам операций преобразования, выбираемых по заданному правилу. При этом каждая возможная модификация алгоритма шифрования обладает высокой стойкостью к известным способам криптоанализа, поскольку для всех возможных модификаций алгоритма шифрования выборка подключей зависит от преобразуемого блока и от шифрключа. Непредопределенность для криптоаналитика выбора конкретной модификации и большое число модификаций делают практически невозможным предварительное исследование статистических свойств каждой из них. Этим обусловливается существенное дополнительное повышение стойкости шифра в целом. Предлагаемый способ позволяет построить недетерминированные шифры с числом возможных модификаций алгоритма шифрования более 10²⁰, при этом каждая модификация обеспечивает скорость шифрования не менее 20 Мбит/с.

Отличительные признаки предлагаемого способа совпадают с отличительными признаками способа шифрования, описанного в заявке 'Способ блочного шифрования данных, авторов Молдовяна А.А., Молдовяна Н.А. (вх. N. 001918, N. гос. регистр. 97101622 от 10 февраля 1997 г.), однако, использование этих признаков для получения технического результата, заключающегося в получении большого числа неэквивалентных модификаций алгоритма шифрования, каждая из которых обладает высокой скоростью, не является очевидной.

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

Дополнительную псевдослучайную последовательность можно использовать для формирования алгоритма шифрования следующим образом. Предварительно составляется программа-шаблон, в которой зарезервированы места, в которых предусмотрена возможность записи любой из некоторого набора операций (например, бинарных операций). Все зарезервированные места (под операции преобразования) нумеруют. Поочередно, начиная с первой, все операции настраивают в зависимости от значения элемента дополнительной псевдослучайной последовательности, имеющего номер совпадающий с номером настраиваемой операции. Например, бинарная операция, используемая для наложения подключа на подблок, устанавливается как операция поразрядного суммирования по модулю два (⊕) , если d_i mod 3 = 0, где d_i - значение соответствующего элемента дополнительной псевдослучайной последовательности, либо как операция суммирования по модулю 2³² (+), если d_i mod 3 = 1, либо как операция вычитания по модулю 2³² (-), если d_i mod 3 = 2. В процедурах настройки алгоритма дешифрования настраиваются операции, являющиеся обратными по отношению к соответствующим операциям, настраиваемым в алгоритме шифрования. Для этого бинарная операция в алгоритме дешифрования устанавливается как операция поразрядного суммирования по модулю два (⊕) , если d_i mod 3 = 0, либо как операция вычитания по модулю 2³² (-), если d_i mod 3 = 1, либо как операция суммирования по модулю 2³² (+), если d_i mod 3 = 2. После того, как в программе шифрования, записанной на алгоритмическом языке (например, на языке СИ или Паскаль), установлены операции преобразования во всех зарезервированных местах, генерируется машинный код, соответствующий программе шифрования, используя, например, транслятор преобразующий программу, составленную на алгоритмическом языке, в последовательность машинных команд. Шифрключ и машинный код программы шифрования записываются в оперативную память ЭВМ (или специализированного шифрующего устройства) и находятся там постоянно в течение всего времени работы данного пользователя, выполняя преобразование поступающих для шифрования блоков данных. Сложность процедур формирования ключа шифрования и генерирования машинного кода программы шифрования не влияет на скорость шифрования, поскольку эту процедуру выполняют однократно при идентификации пользователя по паролю в момент включения шифрующего устройства или вызова шифрующей программы.

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

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

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

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

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

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

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

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