Способ криптографического преобразования l-битовых входных блоков цифровых данных в l-битовые выходные блоки

 

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

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

Предшествующий уровень техники В совокупности признаков заявляемого способа используются следующие термины: - секретный ключ представляет собой двоичную информацию, известную только законному пользователю; - криптографическое преобразование - это преобразование цифровой информации, которое обеспечивает влияние одного бита исходных данных на многие биты выходных данных, например, с целью защиты информации от несанкционированного чтения, формирования цифровой подписи, выработки кода обнаружения модификаций; одними из важных видов криптографических преобразований являются одностороннее преобразование, хэширование и шифрование; - хэширование информации есть некоторый способ формирования так называемого хэш-кода, размер которого является фиксированным (обычно 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₂; подобные операции являются базовыми для шифра RC5 [R. Rlvest, 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];
- одноместная операция - это операция выполняемая над одним операндом (блоком данных или двоичным вектором); значение подблока после выполнения некоторой данной одноместной операции зависит только от его начального значения; примером одноместных операций являются операции циклического сдвига:
- двухместная операция - это операция, выполняемая над двумя операндами; результат выполнения некоторой данной двухместной операции зависит от значения каждого операнда; примером двухместных операций являются операции сложения, вычитания, умножения и др.

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

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

Наиболее близким по своей технической сущности к заявляемому способу криптографического преобразования L-битовых входных блоков цифровых данных в L-битовые выходные блоки является способ, описанный в работе [Kaliski B.S., Robshaw M. J. B. Fast Block Cipher Proposal/ Fast Software Encryption. Proceedings of the Cambridge Security Workshop. Lecture Notes in Computer Science, v. 809, Springer-Verlag, 1994, pp. 26-39; см. также B. Schneier, "Applied Cryptography". Second Eddition. John Wiley & Sons, Inc., New York, 1966, pp. 342-344]. Способ-прототип включает в себя формирование секретного ключа, разбиение входного 1024-байтового блока данных на 32-битовые подблоки ₀, В₁, В₂. . .В₂₅₅ и поочередное преобразование подблоков. Секретный ключ формируется в виде таблицы перестановки и упорядоченной последовательности из 2048 подключей Q₀, Q₁, Q₂...Q₂₀₄₇, каждый из которых имеет длину 32 бит. Шифрование блока данных выполняется в виде четырех раундов преобразований. Один раунд шифрования заключается в следующем. В соответствии с таблицей перестановки, задаваемой секретным ключом, выполняется перестановка подблоков данных. Затем поочередно преобразуются все подблоки. Подблок, например подблок В₁, преобразуют следующим путем. Формируется 32-битовый двоичный вектор V по значениям подблоков B_h, B_k, B_j, где h, i, j, k являются разными номерами, в соответствии с аналитическим выражением V = В_h + F(B_h,B_k,B_j)+Q_q, где знаком "+" обозначена операция суммирования по модулю ³², q - номер текущего подключа. Номера h, i, j, k выбираются в зависимости от номера раунда шифрования и номера шага преобразования подблока. Сформированный двоичный вектор используется при преобразовании подблока B_i следующим образом. Выполняется операция поразрядного суммирования по модулю 2 над подблоком B_i и V и значение, получаемое после выполнения этой операции, присваивается подблоку В_i. Это записывается в виде соотношения B_i← B_i⊕ V, где знак "<--" обозначает операцию присваивания и знак "⊕" обозначает операцию поразрядного суммирования по модулю 2. После этого аналогичным способом выполняется преобразование другого подблока и т.д., пока не будут преобразованы все подблоки. Каждый новый шаг формирования 32-битового двоичного вектора выполняется независимо от значения двоичного вектора, сформированного на предыдущем шаге. В одном раунде шифрования индекс i принимает в некоторой очередности 256 различных значений, соответствующих всем номерам подблоков (от 0 до 255).

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

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

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

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

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

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

Благодаря такому решению обеспечивается дополнительное повышение криптостойкости преобразования блоков информации длиной L = 512, 1024, 2048, 4096 и 8192 бит, поскольку операции циклического сдвига такого типа являются нелинейными и задают более сложную функцию формирования двоичного вектора.

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

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

Новым является также то, что при преобразовании подблоков используют таблицы подстановок, число которых Т≥2, при этом по двоичному вектору вычисляют номер (v) таблицы и подблок изменяют с помощью операции подстановки, задаваемой v-той таблицей.

Благодаря такому решению обеспечивается дополнительное повышение криптостойкости преобразования блоков информации длиной L = 64 и 128 бит, поскольку операции подстановки являются нелинейными и эффективны для реализации при сравнительно малом размере преобразуемого блока информации. Использование заранее не предопределенных операций подстановки является способом достижения высокой криптостойкости к наиболее сильным методам криптоанализа, в частности к дифференциальному криптоанализу, описанному, например, в работе [Biham E. , Shamir A. Differential Cryptanalysis of DES-like Cryptosystems/Journal of Cryptology, v.4, n.1, 1991, pp.3-72].

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

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

На фиг. 2 представлена схема шифрования, соответствующая примеру 2.

На фиг. 3 представлена схема одностороннего преобразования, соответствующая примеру 3.

Лучшие варианты осуществления изобретения
Изобретение поясняется обобщенной схемой криптографического преобразования блоков данных на основе заявляемого способа, которая представлена фиг. 1,
где В - преобразуемый блок, b₁, b₂....b_n - преобразуемые подблоки, F - операционный блок, осуществляющий изменение подблоков, f - операционный блок, осуществляющий формирование двоичного вектора, V₀ - начальное значение двоичного вектора. Входной L-битовый блок цифровых данных, где L - число двоичных разрядов в блоке, разбивается на N≥2 подблоков, каждый из которых имеет размер L/N бит. Сплошная линия соответствует передаче преобразуемых подблоков, пунктирная - передаче двоичного вектора.

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

В частных случаях реализации заявляемого способа перестановка подблоков может не использоваться. Выполнение N шагов изменения подблока, N шагов формирования двоичного вектора и перестановка подблоков, показанные на фиг. 1, составляют один раунд преобразования. Значение двоичного вектора после N-го шага формирования двоичного вектора служит начальным значением двоичного вектора для следующего раунда преобразования при построении односторонних функций преобразования L-битовых блоков цифровых данных. При построении шифров начальное значение двоичного вектора для каждого раунда формируется в зависимости от секретного ключа. Количество раундов преобразования может быть задано в зависимости от конкретных вариантов построения операционных блоков F и f. Важным в приведенной схеме является то, что двоичный вектор формируют в зависимости от его структуры на предыдущем шаге преобразования подблока с использованием двоичного вектора.

Под преобразованием подблока с использованием двоичного вектора понимается (1) выполнение двухместной операции, операндами которой являются подблок и двоичный вектор, или (2) выполнение над подблоком одноместной операции (например, подстановки или перестановки битов), модификация которой выбирается в зависимости от значения двоичного вектора, или (3) выполнение двухместной операции, выполняемой над подблоком и подключом, номер которого зависит от значения двоичного вектора. Например, в первом случае это может быть преобразование 32-битового подблока В, когда данному подблоку присваивается значение, равное результату сложения по модулю 2³² подблока В и двоичного вектора V: B<--B+V. Во втором случае это может быть операция циклического сдвига влево, выполняемая над подблоком В, на число разрядов, равное значению двоичного вектора, аналитически выражаемая соотношением B<--В <<< V. В третьем случае это может быть, например, преобразование, задаваемое выражением B ← B⊕Q_v, где Q_v - подключ с номером v, вычисляемым по значению двоичного вектора: v = V mod 2¹¹. Последнее соотношение задает выбор номера, равного значению 11 младших разрядов двоичного вектора.

Важным частным случаем второго варианта использования двоичного вектора в преобразованиях подблока является выполнение зависящей от двоичного вектора операции подстановки над подблоком. Такой тип подстановок может быть использован при задании множества различных таблиц подстановок, каждой из которых присвоен порядковый номер, и для выполнения операции подстановки над подблоком используют таблицу номер которой выбирают в зависимости от значения V, например, если используются 32 таблицы подстановки, то номер таблицы можно вычислить по формуле v = V mod 2⁵. Смысл выбора таблицы подстановки, которая используется для выполнения операции подстановки над подблоком на текущем шаге, по специально формируемому двоичному вектору состоит в том, чтобы сделать выбор таблицы подстановки непредопределенным для каждого шага преобразования подблоков, что повышает стойкость криптографического преобразования.

Под формированием двоичного вектора мы понимаем запись, например, в регистр или ячейку памяти вычислительного устройства некоторой последовательности единичных или нулевых битов. Под формированием двоичного вектора в зависимости от его структуры на предыдущем шаге преобразования подблока с использованием двоичного вектора мы понимаем задание зависимости текущего значения формируемого двоичного вектора от значения, которое двоичный вектор имел на предшествующем шаге использования при преобразовании подблока данных. Например, пусть подблок _i был преобразован с использованием значения двоичного вектора V. Перед использованием двоичного вектора на некотором другом шаге преобразования, например, подблока В_j двоичный вектор может формироваться в соответствии с выражением V <-- V+Q_b, где b = B_i mod 2¹¹ - номер подключа, вычисляемый в зависимости от значения подблока В_i.

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

Пример 1.

Данный пример является вариантом заявляемого способа, выполняющим шифрование блоков данных по 512-байт (4096 бит). Использование такого размера входных блоков обусловлено тем, что в компьютерных системах этот размер блоков является стандартным. При использовании блочных шифров, обрабатывающих блоки такого размера, сохраняется возможность произвольного доступа к данным, хранящимся на встроенном магнитном носителе в зашифрованном виде. В этом примере используется 8192-байтовый секретный ключ, представленный в виде совокупности из 2048 пронумерованных 32-битовых подключен {Q_v}, где v = 0, 1, 2...2047. Секретный ключ формируют, например, путем его копирования с магнитного носителя в оперативную память ЭВМ. Криптографическое преобразование по примеру 1 описывается следующим алгоритмом.

Алгоритм 1: Шифрование 4096-битовых блоков.

ВХОД: 4096-битовый блок, представленный в виде совокупности 128 32-битовых подблоков {B₁, B₂...B₁₂₈}.

1. Установить номер обрабатываемого блока i = 1 и начальные значения двоичных векторов V₁, V₂, V₃ и v: V₁ <-- Q₁; V₂ <-- Q₂; V₃ <-- Q₃; v <-- 79.

2. Сформировать двоичный вектор v по структуре двоичного вектора V₁: v ← v⊕(V₁ mod 2¹¹), где "⊕" - операция суммирования по модулю 2.

3. Сформировать двоичный вектор V₂: V₂← [(V₂+Q_v)⊕V₁]>>>11, где "+" - операция суммирования по модулю 2³².

4. Сформировать двоичный вектор v по структуре двоичного вектора V₂: v ← v⊕(V₂ mod 2¹¹).
5. Сформировать двоичный вектор V₃: V₃← {[V₃>>>V₂)⊕Q_v]-V₁}>>>22, где "-" обозначает операцию вычитания по модулю 2³².

6. Сформировать двоичный вектор v по структуре двоичного вектора V₃: v ← v⊕(V₃ mod 2¹¹).
7. Сформировать двоичный вектор V₁: V₁<--V+Q_v.

8. Преобразовать подблок В_i: B_i ← [(B_i<<)⊕V₃]+V₁.
9. Сформировать двоичный вектор V₁: V₁ <-- B_i.

10. Преобразовать подблок В_i: В_i <-- В_i+V₂.

11. Если i≠128, то изменить значение номера i: i <-- i+1 и перейти к п. 2.

12. Переставить подблоки в обратном порядке.

ВЫХОД: 4096-битовый блок шифртекста в виде совокупности преобразованных подблоков {В₁, В₂...В₁₂₈}.

Алгоритм 1 описывает один раунд шифрования. После первого раунда выполняют второй раунд шифрования, беря выходной блок первого раунда в качестве входного для второго раунда. Затем выполняют последний (третий) раунд шифрования, беря выходной блок второго раунда в качестве входного блока для третьего раунда. При программной реализации скорость шифрования при использовании трех раундов преобразования составляет около 30 Мбит/с для микропроцессора Pentium/200.

Пример 2.

Рассмотрим вариант заявляемого способа с использованием операций подстановок, задаваемых таблицами подстановок. Пусть операции подстановки выполняются над подблоками цифровых данных длиной k бит, где k - целое число. Тогда для задания операции подстановки, преобразующей k-битовый входной подблок в k-битовый выходной подблок, требуется использование таблицы, содержащей две строки чисел:
0 1 2 ... N-1
a₀ a₁ a₂ ... a_N-1
где N = 2^k.

В данной таблице в нижней строке присутствуют все возможные значения k-битового блока ровно по одному разу, но в произвольном порядке. Очередность расположения чисел в нижней строке определяет конкретный вариант таблицы подстановки, а следовательно, и конкретный вариант операции подстановки, выполняемой с использованием этой таблицы. Выполнение операции подстановки осуществляется следующим образом. Выбирается в верхней строке число, которое равно значению входного блока. Находящееся под этим числом значение в нижней строке берется в качестве выходного блока. Таким образом, таблицу подстановки можно разместить в оперативной памяти ЭВМ как последовательную запись k-битовых компьютерных слов, размещенных в ячейках с адресами w₀, w₁, w₂. . . w_N-1. В этом случае значение входного блока b служит для вычисления адреса w₀+b слова, которое берется в качестве выходного блока. Этот способ представления таблицы подстановки требует использования объема памяти, равного kN бит.

Выберем количество таблиц подстановки, равное 2^L (объем требуемой памяти составит при этом 2^LkN бит), и разместим таблицы подстановок непрерывно друг за другом. В качестве адреса таблицы с номером v возьмем значение адреса w₀ ее первого k-битового слова. Пусть адрес таблицы с номером 0 есть s. В этом случае адрес таблицы подстановки с произвольным номером v равен s+vN. Если задан двоичный вектор, определяющий номер текущей таблицы подстановки v и текущий входной подблок для выполнения операции подстановки, то oна выполняется заменой текущего входного блока на k-битовое слово, расположенное по адресу s+vN+b, где b - значение подблока, над которым выполняется текущая операция подстановки. Используя это соотношение легко задать выбор таблицы подстановки с номером v и выполнить подстановку над подблоком со значением b. В рассмотренном случае задание зависимости таблиц подстановок от значения двоичного вектора и выполнение операции подстановки осуществляются микропроцессором очень быстро при выборе соответствующих значений параметров L и k, например при L = 5 и k = 8. При указанных параметрах для размещения таблиц подстановки требуется 8 Кбайт оперативной памяти, что является приемлемым, поскольку современные ЭВМ обладают объемом оперативной памяти на многие порядки больше этой величины (от 1 до 64 Мбайт и более).

Пусть L = 5 и k = 8, т.е. даны 32 таблицы, задающие операции подстановки над 8-битовыми подблоками данных. Сформируем секретный ключ, представленный в виде совокупности из 7R 8-битовых подключей:

где R - число раундов шифрования. На r-том раунде шифрования используется r-тая строка подключей.

Обозначим используемые таблицы подстановки следующим образом: Т₀, Т₁, Т₂...Т₃₁, а операцию подстановки, задаваемую таблицей Т_v, как S_v, где v = 0, 1, 2...31. Таблицы подстановок Т₀, Т₁, Т₂...Т₁₅ могут быть выбраны произвольными, а таблицы Т₁₆, Т₁₇...Т₃₁ берутся такими, чтобы операции подстановок S_v и S_31-v были взаимно обратными. Последнее условие выполняется, если пары таблиц Т₁₆ и Т₁₅; Т₁₇ и Т₁₄; Т₁₈ и Т₁₃;...; Т₃₁ и Т₀ будут задавать взаимно обратные операции подстановки. Для набора произвольных таблиц подстановки Т₀, Т₁, Т₂...Т₁₅ легко составить таблицы, соответствующие обратным операциям подстановки. Например, для операции подстановки, задаваемой следующей таблицей
0 1 2 ... 255
а₀ а₁ а₂ ... а₂₅₅
а обратная подстановка задается таблицей
0 1 2 ... 255
z₀ z₁ z₂ ... z₂₅₅
где строка (z₀, z₁, z₂...z₂₅₅) получается как верхняя строка после упорядочения столбцов предыдущей таблицы в порядке возрастания чисел в нижней строке.

На фиг. 2 показана схема первого раунда шифрования. На фиг. 2 сплошная вертикальная линия соответствует передаче 8-битовых подблоков данных, пунктирная линия соответствует передаче 5-битовых подблоков, горизонтальная сплошная линия соответствует передаче 8-битового подключа. Операция поразрядного суммирования по модулю два обозначена знаком "⊕", v обозначает номер выбранной таблицы подстановки, блок S обозначает операцию подстановки, k₁₁, k₁₂. . . k₁₇ - подключи, используемые на первом раунде. Стрелки на линиях обозначают направление передачи сигналов. Пример 2 соответствует шифрованию блоков цифровых данных размером 64 бит. Шифрование выполняют следующим путем. Входной блок разбивают на 8 подблоков b₀, b₁, b₂...b₇ размером 8 бит каждый. После этого формируют двоичный вектор v, имеющий значение 5 младших двоичных разрядов подблока b₀: v <-- b₀ mod 2⁵. Потом над подблоком b₁ и подключом k₁₁ выполняют операцию поразрядного суммирования по модулю 2 и выходное значение этой операции присваивают блоку b₁, что можно записать аналитически следующим образом: b₁← b₁⊕r₁₁. Затем по таблице подстановки с номером v выполняют операцию подстановки над подблоком b₁: b₁ <-- S_v(b₁). Затем по значению b₁ формируют двоичный вектор v: v ← v⊕ (b₁ mod 2⁵), причем новое значение двоичного вектора зависит от его предыдущего значения. После этого выполняют преобразование подблока b₂: b₂← b₂⊕k₁₂ и затем b₂ <-- S_v(b₂).

Аналогично выполняют преобразования подблоков b₃, b₄, b₅, b₆ и b₇. На последнем шаге каждого раунда шифрования выполняют перестановку подблоков в обратном порядке, т.е. попарно меняются местами блоки b₇ и b₀, b₆ и b₁, b₅ и b₂, b₄ и b₃.

Второй раунд выполняется аналогично, за исключением того, что вместо первой строки подключей используется вторая строка подключей. Затем выполняется третий раунд шифрования с использованием третьей строки подключей и т. д. Всего выполняется R раундов шифрования, где R = 4. При программной реализации данный пример реализации заявляемого способа обеспечивает скорость шифрования около 25 Мбит/с для микропроцессора Pentium/200. При необходимости может быть задано и другое число раундов, например R = 2, 3, 5, 6.

Пример 2.

Пример описывается следующим алгоритмом.

Алгоритм 2.

Вход. 64-битовый входной блок цифровых данных, представленный как конкатенация 8-битовых подблоков b₀|b₁|b₂|b₃|b₄|b₅|b₆|b₇, где знак "|" обозначает операцию конкатенации.

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

2. Установить счетчик i = 1.

3. Сформировать двоичный вектор v: v <-- b_i-1 mod 2⁵.

4. Преобразовать подблок b_i: b_i← b_i⊕k_ri, b_i <-- S_v(b_i), где операция подстановки S_v выполняется с помощью таблицы подстановки с номером v.

5. Сформировать двоичный вектор v: v ← v⊕ (b_i mod 2⁵).

6. Если i≠7, то прирастить i <-- i+1 и перейти к п. 4.

7. Если r≠R, то прирастить r <-- r+1. В противном случае СТОП.

8. Переставить подблоки в обратном порядке и перейти к п. 3.

Выход: 64-битовый блок шифртекста.

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

Алгоритм 3.

Вход: 64-битовый входной блок шифртекста b₀|b₁|b₂|b₃|b₄|b₅|b₆|b₇.
1. Установить число раундов шифрования R = 4 и счетчик числа раундов r = 1.

2. Установить счетчик i = 1.

3. Сформировать двоичный вектор v: v <-- b_i-1 mod 2⁵.

4. Сохранить значение b_i в переменной g: g <-- b_i. Преобразовать подблок b_i: b_i <-- S_31-v(b_i), b_i← b_i⊕k_rʹ1, где r' = 5-r.

5. Сформировать двоичный вектор v: v ← v⊕(g mod 2⁵)].
6. Если i≠7, то прирастить i <-- i+1 и перейти к п. 4.

7. Если r≠R, то прирастить r <-- r+1. В противном случае СТОП.

8. Переставить подблоки в обратном порядке и перейти к п. 3.

Выход: 64-битозый блок исходного текста.

Приведенные алгоритмы шифрования и дешифрования могут быть легко модифицированы для преобразования блоков данных другого размера, например 128 и 256 бит.

Пример 3.

Данный пример относится к построению односторонней функции, основанной на заявляемом способе криптографического преобразования. Так же, как и в примерах 1 и 2, предполагается использование 32 таблиц подстановки Т₀, Т₁, Т₂...Т₃₁. Таблицы подстановок предполагаются известными и секретные ключи не используются. Односторонняя функция задается алгоритмом 4. Последовательность операций преобразования подблоков данных для одного раунда преобразования показана на фиг. 2.

Алгоритм 4.

Вход. 64-битовый входной блок данных, представленный как конкатенация 8-битовых подблоков b₀|b₁|b₂|...|b₇.
1. Установить число раундов преобразования R = 8, счетчик числа раундов r = 1 и начальное значение двоичного вектора v = 13.

2. Установить счетчик i = 1.

3. Сформировать двоичный вектор v: v ← v⊕(b_i-1mod 2⁵).
4. Преобразовать подблок b_i-1: b_i-1 <--b <<< r, b_i-1 <-- S_v(b_i-1).

6. Если i≠8, то прирастить i <-- i+1 и перейти к п. 3.

7. Переставить подблоки b₀, b₁...b₇ в обратном порядке.

8. Если r≠R, то прирастить r <-- r+1 и перейти к п. 2. В противном случае СТОП.

Выход; 64-битовое значение функции F.

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

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

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

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

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3