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

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

В совокупности признаков заявляемого способа используются следующие термины:
- секретный ключ представляет из себя двоичную информацию, известную только законному пользователю;
- криптографическое преобразование - это преобразование цифровой информации, которое обеспечивает влияние одного бита исходных данных на многие биты выходных данных, например, с целью защиты информации от несанкционированного чтения, формирования цифровой подписи, выработки кода обнаружения модификаций; одними из важных видов криптографических преобразований являются одностороннее преобразование, хэширование и шифрование;
- хэширование информации есть некоторый способ формирования так называемого хэш-кода, размер которого является фиксированным (обычно 128 бит) для сообщений любого размера; широко применяются способы хэширования, основанные на итеративных хэш-функциях с использованием блочных механизмов криптографического преобразования информации [см. Lai X., Massey J.L. Hash Functions Based on Block Ciphers/Workshop on the Theory and Applications of Cryptographic Techniques. EUROCRYPT'92. Hungary, May 24-28, 1992. Proceedings. P. 53-66.].

- шифрование есть процесс преобразования информации, который зависит от секретного ключа и преобразует исходный текст в шифртекст, представляющий собой псевдослучайную последовательность знаков, из которой получение информации без знания секретного ключа практически неосуществимо;
- дешифрование есть процесс, обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании секретного ключа;
- шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием секретного ключа; шифр может быть реализован в виде программы для ЭВМ или в виде отдельного устройства;
-двоичный вектор - это некоторая последовательность нулевых и единичных битов, например 101101011; конкретная структура двоичного вектора может быть интерпретирована как двоичное число, если считать, что позиция каждого бита соответствует двоичному разряду, т. е. двоичному вектору может быть сопоставлено численное значение, которое определяется однозначно структурой двоичного вектора;
- криптоанализ - метод вычисления секретного ключа для получения несанкционированного доступа к зашифрованной информации или разработка метода, обеспечивающего доступ к зашифрованной информации без вычисления секретного ключа;
- одностороннее преобразование - это такое преобразование L-битового входного блока данных в L-битовый выходной блок данных, которое позволяет легко вычислить выходной блок по входному блоку, а вычисление входного блока, который бы преобразовывался в случайно выбранный выходной блок, является практически невыполнимой задачей;
- односторонняя функция - это функция, значение которой легко вычисляется по данному аргументу, однако вычисление аргумента по данному значению функции является вычислительно трудной задачей; односторонние функции реализуются как последовательность процедур одностороннего преобразования некоторого входного блока (аргумента), выходное значение которого принимается за значение функции;
- криптостойкость является мерой надежности защиты зашифрованной информации и представляет собой трудоемкость, измеренную в количестве элементарных операций, которые необходимо выполнить для восстановления информации по криптограмме при знании алгоритма преобразования, но без знания секретного ключа; в случае односторонних преобразований под криптостойкостью понимается сложность вычисления входного значения блока по его выходному значению;
- операции циклического сдвига, зависящие от преобразуемых подблоков или зависящие от двоичного вектора - это операции циклического сдвига на число бит, задаваемое значением подблока или значением двоичного вектора; операции циклического сдвига влево (вправо) обозначаются знаком "<<<" (">>>"), например, запись B₁<<<B₂ обозначает операцию циклического сдвига влево подблока В₁ на число бит, равное значению двоичного вектора B₂; подобные операции являются базовыми для шифра RC5;
- одноместная операция - это операция, выполняемая над одним операндом (блоком данных или двоичным вектором); значение подблока после выполнения некоторой данной одноместной операции зависит только от его начального значения; примером одноместных операций являются операции циклического сдвига;
- двухместная операция - это операция, выполняемая над двумя операндами; результат выполнения некоторой данной двухместной операции зависит от значения каждого операнда; примером двухместных операций являются операции сложения, вычитания, умножения и др.

Известны способы блочного шифрования данных, см. например стандарт США DES [National Bureau of Standards. Data Encryption Standard. Federal Information Processing Standards Publication 46, January 1977; см. также: С. Мафтик. Механизмы защиты в сетях ЭВМ.- М.: Мир, 1993, с. 42-47]. В данном способе шифрование блоков данных выполняют путем формирования секретного ключа, разбиения преобразуемого блока данных на два подблока L и R и поочередного изменения последних путем выполнения операции поразрядного суммирования по модулю два над подблоком L и двоичным вектором, который формируется как выходное значение некоторой функции F от значения подблока R. После этого блоки переставляются местами. Функция F в указанном способе реализуется путем выполнения операций перестановки и подстановки, выполняемых над подблоком R. Данный способ обладает высокой скоростью преобразований при реализации в виде специализированных электронных схем.

Однако известный способ-аналог использует секретный ключ малого размера (56 бит), что делает его уязвимым к криптоанализу на основе подбора ключа. Последнее связано с высокой вычислительной мощностью современных ЭВМ массового применения.

Наиболее близким по своей технической сущности к заявляемому способу криптографического преобразования блоков двоичных данных является способ, реализованный в шифре RC5, описанный в работе [R.Rivest, The RC5 Encryption Algorithm/Fast Software Encryption, Second International Workshop Proceedings (Leuven, Belgium, December 14-16, 1994), Lecture Notes in Computer Science, v. 1008, Springer-Verlag, 1995, pp. 86-96]. Способ-прототип включает в себя формирование секретного ключа в виде совокупности подключей, разбиение входного блока данных на подблоки A и B и поочередное преобразование подблоков. Подблоки преобразуются путем выполнения над ними одноместных и двухместных операций. В качестве двухместных операций используются операции сложения по модулю 2ⁿ, где n = 8, 16, 32, 64, и операция поразрядного суммирования по модулю 2. В качестве одноместной операции используется операция циклического сдвига влево, причем число бит. на которое сдвигается преобразуемый подблок, зависит от значения другого подблока, это определяет зависимость операции циклического сдвига на текущем шаге преобразования подблока от исходного значения входного блока данных. Двухместная операция выполняется над подблоком и подключом, а также над двумя подблоками. Характерным для способа прототипа является использование операции циклического сдвига, зависящей от значения входного блока.

Подблок, например подблок B, преобразуют следующим путем. Выполняется операция поразрядного суммирования по модулю 2 над подблоками A и B и значение, получаемое после выполнения этой операции присваиваются подблоку В. Это записывается в виде соотношения B ←_ B⊕V, где знак "<---" обозначает операцию присваивания и знак "⊕" обозначает операцию поразрядного суммирования по модулю 2. После этого над подблоком В выполняют операцию циклического сдвига на число бит, равное значению подблока A: В<---В<<<A. Затем над подблоком и одним из подключей S выполняют операцию суммирования по модулю 2ⁿ, где n - длина подблока в битах: B<---B+S mod 2ⁿ. После этого аналогичным образом преобразуется блок A. Выполняется насколько таких шагов преобразования обоих подблоков.

Данный способ обеспечивает высокую скорость шифрования при реализации в виде программы для ЭВМ. Однако способ-прототип имеет недостатки, а именно, при программной реализации для ЭВМ с 32-разрядными микропроцессором он не обеспечивает высокой стойкости криптографического преобразования данных к дифференциальному и линейному криптоанализу [Kaliski В. S., Yin Y.L. On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm. Advances in Cryptology - CRYPTO'95 Proceedings, SprInger-Verlag, 1995, pp. 171-184]. Этот недостаток связан с тем, что эффективность использования операций зависящих от преобразуемых данных с целью усложнения известных методов криптоанализа снижается тем, что число возможных вариантов операции циклического сдвига равно числу двоичных разрядов подблока n и не превышает 64.

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

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

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

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

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

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

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

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

На фиг. 1 представлена обобщенная схема криптографического преобразования согласно заявляемому способу.

На фиг. 2 схематично представлена структура блока управляемых перестановок.

На фиг. 3 представлена блок-схема элементарного переключателя.

На фиг. 4 представлена таблица входных и выходных сигналов элементарного переключателя при высоком потенциале управляющего сигнала.

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

Изобретение поясняется обобщенной схемой криптографического преобразования блоков данных на основе заявляемого способа, которая представлена фиг. 1, где: P - блок управляемых перестановок; A и B - преобразуемые подблоки; K_4r, K_4r-1, K_4r-2, K_4r-3 - элементы секретного ключа (подключи); V - двоичный вектор, формируемый в зависимости от входных данных; знак ⊕ обозначает операцию поразрядного суммирования по модулю два; знак - операцию суммирования по модулю n, где n - длина подблока данных в битах. Жирные сплошные линии обозначают шину передачи n-битовых сигналов, тонкие сплошные линии - передачу одного бита, тонкие пунктирные линии - передачу одного управляющего бита. Жирные пунктирные линии - шину передачи n управляющих сигналов, в качестве которых используются биты подключей. Использование дополнительной зависимости перестановок от секретного ключа повышает стойкость криптографического преобразования.

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

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

Пример 1.

Данный пример относится к использованию способа для шифрования данных. Секретный ключ представлен в виде четырех подключей K_4r, K_4r-1, K_4r-2 и K_4r-3. Один раунд шифрования описывается следующей последовательностью процедур:
1. Преобразовать подблок A в соответствии с выражением:
A ←_A⊕K_4r-3,
где "<---" - обозначение операции присваивания.

2. Преобразовать подблок B в соответствии с выражением:

3. В зависимости от значения подблока A и от подключа K_4r-1 осуществить перестановку битов подблока B.

4. Преобразовать подблок A в соответствии с выражением:

5. В зависимости от значения подблока B и от подключа К_4r осуществить перестановку битов подблока A.

6. Преобразовать подблок B в соответствии с выражением:
B ←_ B⊕A.
Пример 2.

Данный пример описывает один раунд односторонних преобразований в соответствии со следующей последовательностью процедур:
1. Сформировать двоичный вектор V:
V <--- A <<< B.

2. Преобразовать подблок B в соответствии с выражением:

3. Сформировать двоичный вектор V в зависимости от его значения на предыдущем шаге и от значения подблоков A и B в соответствии с формулой:
V ←_(V<<<A)⊕(B<<<13).
4. Преобразовать подблок A в соответстствии с выражением:
A ←_ A⊕V.
5. В зависимости от значений A и V осуществить перестановку битов подблока B.

6. Преобразовать подблок A в соответствии с выражением:

7. Сформировать двоичный вектор V:
V ←_(V<<<A)⊕(B<<<11).
8. В зависимости от значений В и V осуществить перестановку битов подблока A.

9. Преобразовать подблок B в соответствии с выражением:
B ←_ B⊕A.
На фиг. 2 показана возможная реализация блока управляемых перестановок, использующая совокупность элементарных переключателей s. Данный пример соответствует блоку P с 8-битовым входом для сигналов данных и 8-битовым входом для управляющих сигналов, обозначенных пунктирными линиями аналогично обозначению на фиг. 1.

Число различных вариантов операции перестановки равно числу возможных кодовых комбинаций на входе управления и составляет для блока P со структурой, представленной на фиг. 2, 2⁸=256, что превышает число операций циклического сдвига, используемых в способе-прототипе. Аналогичным способом может быть составлена схема для блока P с произвольными размерами входа для данных и входа для управляющих сигналов, в частности для блока P с 32-битовым входом данных и 32-битовым входом для управляющих сигналов. В последнем случае достигается число различных вариантов операции перестановки, равное 2³² > 10⁹.

Фиг. 3, 4 и 5 поясняют работу элементарного переключателя, где u - управляющий сигнал, а и b - входные сигналы данных, с и d - выходные сигналы данных. Таблицы на фиг. 4 и 5 показывают зависимость выходных сигналов от входных и управляющих сигналов. Из данных таблиц видно, что при u = 1 линия а коммутируется с линией с, а линия b - с линией d. При u = 0 линия а коммутируется с линией d, а линия b - с линией d. Благодаря простой структуре современная планарная технология изготовления интегральных схем позволяет легко изготовит криптографические микропроцессоры, содержащие управляемые блоки перестановок с размером входа 32, 64 и 128 бит.

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

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

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

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