БЛОК ШИФРОВАНИЯ Российский патент 1999 года по МПК H04L9/18 

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

Известны устройства шифрования, выполненные в виде механических машин и электромеханических устройств [В. Жельников. Криптография от папируса до компьютера. -М., ABF, 1996, 336 с.]. Кроме того, известны электронные устройства шифрования, реализующие способ шифрования, описанный в Российском стандарте криптографической защиты данных [Стандарт СССР ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования]. Устройство, реализующее Российский стандарт шифрования, включает в себя блок шифрования, состоящий из нескольких операционных узлов: сумматора по модулю 2³², поразрядного сумматора по модулю 2, операционного узла, выполняющего циклический сдвиг влево на 11 бит, и операционного узла, выполняющего операцию подстановки.

Наиболее близким по своей технической сущности к заявляемому блоку шифрования является блок шифрования, используемый в устройстве шифрования, реализующем способ шифрования в соответствии с американским федеральным стандартом DES [National Bureau of Standards. Data Encryption Standard. Federal 1nformation Processing Standards Publication 46, January 1977]. Данный способ включает в себя формирование секретного ключа, разбиениe входной информации, представленной в виде двоичного кода, на участки длиной по 64 бит, формированиe на их основе 64-битовых блоков данных и преобразованиe блоков под управлением секретного ключа. Перед преобразованием каждый блок данных разбивается на два 32-битовых подблока L и R, которые поочередно преобразуются путем выполнения 16 однотипных раундов преобразования. Один раунд преобразования заключается в выполнении операций расширения, подстановки, перестановки и суммирования по модулю 2, реализующих раундовую функцию шифрования над подблоком R, что записывается в виде формулы R:= F(R), где знак ": =" обозначает операцию присваивания, F - раундовая функция шифрования. Каждый раунд завершается перестановкой подблоков R и L:
T:=R,
R:=L,
L:=T.

Устройство шифрования (УШ), реализующее стандарт шифрования DES, представлено в виде блок-схемы на фиг. 1 и содержит 64-разрядный информационный вход 1, состоящий из двух 32-разрядных информационных входов 1.а и 1.б, на которые подаются два 32-битовых подблока L и R, 64-разрядный выход 2, состоящий из двух 32-разрядных выходов 2.а и 2.б, с которых снимаются преобразованные 32-битовые подблоки L и R, управляющий вход 9, блок шифрования 3 (БШ), блок генерации раундового подключа (БГРП), блок управления БУ и управляющую шину 10. Блок шифрования содержит 32-разрядный информационный вход 3, 32-разрядный выход 4 и 80-разрядный управляющий вход 5, состоящий из 32-разрядного управляющего входа 5.1 и 48-разрядного входа 5.2. Информационный вход блока шифрования 6 соединен с информационным входом 1.б и выходом 2.а устройства шифрования. Выход блока шифрования 4 соединен с выходом 2.б устройства шифрования. Управляющий вход 5.1 блока шифрования соединен с входом 1. а устройства шифрования. Управляющий вход 5.2 блока шифрования соединен с выходом 7 блока генерации раундового ключа. Вход блока генерации раундового ключа 7 соединен с управляющим входом устройства шифрования 8. Блок генерации раундового ключа содержит вход 8, соединенный с управляющим входом 9 устройства шифрования, и выход 7.

Устройство шифрования (фиг. 1) работает следующим образом. На вход устройства шифрования подается 56-битовый ключ, который преобразуется в последовательность 48-битовых раундовых подключей K_r, r = 1, 2,..., 16. Для текущего r-го раунда на выходе блока генерации раундового ключа устанавливается двоичный код, соответствующий значению подключа K_r. Шифруемый 64-битовый блок данных B подается на вход устройства шифрования. Старшие 32 бита блока B, обозначаемые как подблок L, подаются на вход 1.а. Младшие 32 бита блока B, обозначаемые как подблок R, подаются на вход 1.б. Обозначим начальные значения подблоков индексом "0", а их значения после выполнения r-го раунда шифрования - индексом "r". Блок шифрования на r-ом раунде преобразует значение подблока R_r-1 в значение R_r = F(R_r-1, K_r), которое зависит от типа функции F и значения раундового подключа K_r. Выходное значение подблока L в текущем раунде устанавливается равным входному значению подблока R. Таким образом, устройство шифрования выполняет преобразование, которое может быть записано с помощью следующих итеративных формул:
L_r=R_r-1, (1)
R_r = F(R_r-1, L_r-1, K_r), (2)
где вычисление функции F от значения R_r-1 осуществляется блоком шифрования в зависимости значения L_r-1, подаваемого на вход 5.1, и значения K_r, подаваемого на вход 5.2. Блок управления синхронизирует работу блока генерации раундового подключа и блока шифрования и осуществляет контроль числа выполненных раундов преобразования. Если текущий номер раунда не равен 16, то блок управления текущие значения подблоков L_r и R_r на выходе устройства шифрования подает на вход устройства шифрования для выполнения следующего раунда. Значения L₁₆ и R₁₆ составляют выходной блок шифр-текста.

Блок шифрования представлен на фиг. 2 и содержит операционные узлы 3.1, 3.2, 3.3, 3.4 и 3.5. Информационный вход операционного узла 3.1 является информационным входом блока шифрования, а выход операционного узла 3.1 соединен с входом операционного узла 3.2. Выход операционного узла 3.2 соединен с информационным входом операционного узла 3.3 и т.д. Выход операционного узла 3.5 является выходом блока шифрования. Операционные узлы 3.2 и 3.5 содержат управляющие входы, соединенные с управляющими входами 5.1 и 5.2, соответственно. Операционный узел 3.1 выполняет процедуру расширения 32-битового подблока данных R_r-1 в 48-битовый подблок R'. Операционный узел 3.2 выполняет поразрядное суммирование по модулю 2 значения R' с подключом K_r и выдает на входе значение R″ = R′⊕ K_r, , где знак ⊕ обозначает операцию поразрядного суммирования по модулю 2. Операционный узел 3.3 выполняет операцию подстановки над 48-битовым значением R'' и заменяет его на 32-битовое значение R''' в соответствии с таблицами замены, приведенными в стандарте шифрования DES. Операционный узел 3.4 осуществляет перестановку битов двоичного значения R''' и выдает на выход преобразованное значение R^*. Операционный узел 3.5 выполняет операцию поразрядного суммирования по модулю два над значением R^*, подаваемым на его информационный вход, и значением L_r-1, подаваемым на его управляющий вход. Значение на выходе операционного узла 3.5 R_r = R^*⊕ L_r-1 является значением функции F(R_r-1, L_r-1, K_r), вычисляемой блоком шифрования.

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

Однако это устройство имеет недостатки, а именно оно не обеспечивает высокой криптостойкости к дифференциальному криптоанализу [Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems//Journal of Cryptology, 1991, V. 4, N 1, p. 3-72]. Этот недостаток связан с тем, что все операционные узлы выполняют фиксированные операции преобразования для всех преобразуемых блоков данных.

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

Поставленная задача достигается тем, что в блоке шифрования, содержащем n-разрядный, где n - четное натуральное число, информационный вход, n-разрядный выход, m-разрядный управляющий вход и W≥2 операционных узлов, одноразрядные информационные входы первого операционного узла являются одноразрядными информационными входами блока шифрования, одноразрядные выходы V-го, где 1≤V≤W, операционного узла соединены с одноразрядными входами (V+1)-го операционного узла, одноразрядные выходы W-го операционного узла являются одноразрядными выходами блока шифрования, причем по крайней мере один операционный узел содержит одноразрядные управляющие входы, соединенные с одноразрядными управляющими входами блока шифрования, новым согласно изобретению является то, что по крайней мере один операционный узел выполнен в виде узла управляемых перестановок, одноразрядные управляющие входы которого соединены с одноразрядными входами блока шифрования.

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

Новым является также то, что узел управляемых перестановок выполнен в виде матрицы элементарных переключателей, каждый из которых содержит схему коммутации, первый и второй одноразрядные информационные входы, первый и второй одноразрядные выходы и одноразрядный управляющий вход, причем матрица содержит n-1 строку, j-я, где j = 1,2,3,...,n-1, строка содержит n-j элементарных переключателей, управляющие одноразрядные входы которых соединены с управляющими одноразрядными входами узла управляемых перестановок, первый одноразрядный информационный вход которого соединен с первым одноразрядным информационным входом первого элементарного переключателя в первой строке матрицы, остальные n-1 одноразрядных информационных входов узла управляемых перестановок соединены поразрядно со вторыми одноразрядными информационными входами элементарных переключателей первой строки, первый одноразрядный информационный вход первого элементарного переключателя j-й, где j ≠ 1, строки соединен со вторым одноразрядным выходом первого элементарного переключателя (j-1)-й строки, в j-й, где j ≠ n - 1 строке матрицы первый одноразрядный информационный вход i-го, где 1 < i ≤ n-j, элементарного переключателя соединен с первым одноразрядным выходом (i-1)-го элементарного переключателя этой строки, в j-й, где j ≠ 1 строке матрицы второй одноразрядный информационный вход i-го элементарного переключателя соединен со вторым одноразрядным выходом (i+1)-го элементарного переключателя (j-1)-й строки, первый одноразрядный выход (n-j)-го элементарного переключателя соединен с j-м одноразрядным выходом узла управляемых перестановок, второй одноразрядный выход переключателя (n-1)-й строки соединен с последним одноразрядным выходом узла управляемых перестановок.

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

Новым является также то, что в каждую j-ю, где j = 1, 2,..., n/2, строку узла управляемых перестановок введен дешифратор, одноразрядные выходы которого соединены с одноразрядными управляющими входами элементарных переключателей в соответствующих строках, одноразрядные входы дешифраторов соединены поразрядно с одноразрядными управляющими входами узла управляемых перестановок.

Благодаря такому решению сокращается число одноразрядных управляющих входов узла управляемых перестановок.

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

На фиг. 1 представлена блок-схема устройства шифрования, реализующего способ шифрования стандарта DES.

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

На фиг. 3 представлена функциональная схема узла управляемых перестановок.

На фиг. 4 представлена функциональная схема узла управляемых перестановок с использованием дешифраторов.

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

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

На фиг. 7 представлена блок-схема устройства шифрования на основе блока шифрования примера 1.

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

Узел управляемых перестановок, представленный функциональной схемой на фиг. 3, включает матрицу элементарных переключателей, которая обеспечивает коммутацию заданного входного и заданного выходного разряда. Функциональная схема элементарного переключателя (фиг. 4 (а)) приведена в книге [Каляев А. В. Микропроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1984, с. 219, рис. 6.51]. Таблица истинности и цоколевка элементарного переключателя приведены в таблицах (б) и (в) на фиг. 4. Управляемые перестановки осуществляются в зависимости от значений управляющих входов элементарных переключателей. Каждый элементарный переключатель обеспечивает поразрядную или перекрестную коммутацию двух входных информационных одноразрядных каналов и двух выходных одноразрядных каналов и работает в соответствии с таблицей истинности (таблица (б) на фиг. 4). При нулевом значении управляющего одноразрядного входа (U=0) происходит поразрядная коммутация информационных входных и выходных каналов: X1 - Y1 и X2 - Y2; при единичном значении управляющего входа (U= 1) происходит перекрестная коммутация информационных входных и выходных каналов X1 - Y2 и X2 - Y1. Элементарные переключатели в матрице соединены таким образом, что одноразрядные информационные входы i.l, где l = 1,2,...,n, узла управляемых перестановок коммутируются с одноразрядными выходами o.l, где l = 1,2,...,n, узла управляемых перестановок, причем конкретная коммутация определяется значениями всей совокупности управляющих одноразрядных входов u.k узла управляемых перестановок, которыми являются управляющие одноразрядные входы U элементарных переключателей S. Число управляющих одноразрядных входов узла управляемых перестановок равно числу элементарных переключателей в матрице и составляет n(n-1)/2. Поскольку число управляющих одноразрядных входов узла управляемых перестановок больше разрядности управляющего входа блока шифрования, то к одному разряду управляющего входа блока шифрования соединены многие разряды управляющего входа узла управляемых перестановок. Конкретное соединение задает конкретную зависимость операции перестановки битов, выполняемую над подблоком данных R в зависимости от подблока данных L и подключа K. Таким образом, каждая строка L.j, где j = 1,2,...,n-1, матрицы формирует значение соответствующего одноразрядного выхода узла управляемых перестановок. Последняя (n-1)-я строка формирует значения на одноразрядных выходах o.(n-1) и o. n. Каждой строке соответствует группа одноразрядных управляющих входов u.k узла управляемых перестановок. Число элементарных переключателей в строке L. j равно n-j, что задает число управляющих одноразрядных входов u.k, соответствующих данной строке.

С целью сокращения числа управляющих одноразрядных входов узла управляемых перестановок могут быть введены двоично-n-ричные дешифраторы D.h, где h = 1,2,...,(n-2)/2, одноразрядные входы которых являются управляющими одноразрядными входами узла управляемых перестановок, а одноразрядные выходы которых соединены с группой одноразрядных управляющих входов соответствующих двух строк (h-й и (n-h)-й строк) элементарных переключателей (см. фиг. 5). Одноразрядные входы строки с номером h соединены поразрядно с n-h выходами дешифратора D.h. Оставшиеся h одноразрядных выхода этого дешифратора соединены поразрядно с одноразрядными управляющими входами (n-h)-й строки, число которых равно h. В строку с номером n/2 вводится двоично-(n/2)-ричный дешифратор, n/2 одноразрядных выхода которого соединены поразрядно с управляющими одноразрядными входами соответствующих элементарных переключатели строки с номером n/2. В зависимости от кодовой комбинации значений их одноразрядных входов устанавливается единичное значение только на одном из его одноразрядных выходов, а на остальных его выходах устанавливается нулевое значение. Благодаря тому, что число одноразрядных входов дешифратора существенно меньше числа его одноразрядных выходов существенно сокращается число управляющих одноразрядных входов узла управляемых перестановок. Например, для n=32 могут быть использованы 15 двоично-тридцатидвухричных дешифраторов с пятиразрядным входом и один двоично-шестнадцатиричный дешифратор (с четырехразрядным входом), входы которых составляют 79-разрядный управляющий вход узла управляемых перестановок, что значительно меньше разрядности этого узла без использования дешифраторов (в последнем случае число управляющих одноразрядных входов составляет n(n-1)/2=491).

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

Пример 1.

Данный пример поясняется на фиг. 6, где представлена функциональная схема блока шифрования с одним узлом управляемых перестановок Р. Блок шифрования включает операционные узлы 3.1, 3.2 и 3.3. Операционный узел 3.1 выполняет операцию суммирования по модулю 2" над n-битовым подблоком данных R_r-1 и раундовым n-битовым подключом K_r, вырабатывая на выходе n-разрядный подблок данных R'= (R_r-1 + K_r) mod 2ⁿ. Операционный узел 3.2 выполняет операцию перестановки битов n-разрядного подблока данных R' в зависимости от значения подблока данных L_r-1, вырабатывая на выходе подблок данных Операционный узел 3.3 выполняет операцию поразрядного суммирования по модулю 2 над n-битовым подблоком данных R'' и n-битовым подблоком данных L_r-1, вырабатывая на выходе n-разрядное значение R_r = R″⊕ L_r-1. Последовательное выполнение операций, задаваемых узлами 3.1, 3.2 и 3.3, определяет раундовую функцию шифрования
R_r = F(R_r-1,L_r-1,K_r),
которая осуществляется устройством шифрования Q раз, где Q - число раундов преобразования. Данный блок шифрования может быть использован, например, в составе устройства, показанного на фиг. 7, где использованы обозначения такие же, как и для фиг. 1. В этом случае шифрование осуществляется в соответствии со следующими итеративными соотношениями:
R_r = L_r-1
L_r = F(R_r-1,L_r-1,K_r).

Пример 2.

Этот пример реализации блока шифрования представлен на фиг. 8, где операционный узел 3.1 выполняет перестановку битов подблока данных R_r-1 в зависимости от значения раундового подключа K_r, операционный узел 3.2 представляет собой поразрядный сумматор по модулю 2, операционный узел 3.3 представляет собой узел управляемых перестановок, осуществляемых в зависимости значения подблока R_r-1, операционный узел 3.4 представляет собой сумматор по модулю 2ⁿ. Раундовая функция шифрования R_r = F(R_r-1,L_r-1,K_r), задаваемая блоком шифрования, показанным на фиг. 7, описывается следующей последовательностью преобразований:

R″ = R′⊕ K_r,

R_r = (R'''+L_r-1)mod2ⁿ
Блок шифрования, рассмотренный в примере 2 может быть использован, например, в составе устройства шифрования, показанного на фиг. 1 и осуществляющего шифрование в соответствии с итеративными соотношениями (1) и (2).

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

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

Изобретение относится к области электросвязи и вычислительной техники, а конкретно к области криптографических способов и устройств для шифрования данных. Блок шифрования содержит W ≥ 2 n-разрядных, где n - четное натуральное число, последовательно соединенных операционных узлов, одни из которых выполнены в виде сумматоров, а другие - в виде узлов перестановок, причем вход первого операционного узла является информационным входом блока шифрования, выходом которого является выход W-го операционного узла, а одним из управляющих входов является другой вход каждого из сумматоров, причем по крайней мере один узел перестановок выполнен в виде узла управляемых перестановок, управляющий вход которого соединен либо с одним из входов одного из сумматоров, либо со входом первого операционного узла. Технический результат заключается в повышении стойкости шифрования. 2 c. и 2 з.п. ф-лы, 8 ил.

1. Блок шифрования, содержащий W ≥ 2 n-разрядных, где n - четное натуральное число, последовательно соединенных операционных узлов, одни из которых выполнены в виде сумматоров, а другие - в виде узлов перестановок, причем вход первого операционного узла является информационным входом блока шифрования, выход W-го операционного узла является выходом блока шифрования, другой вход каждого из сумматоров является одним из управляющих входов блока шифрования, отличающийся тем, что по крайней мере один узел перестановок выполнен в виде узла управляемых перестановок, управляющий вход которого соединен с одним из входов одного из сумматоров. 2. Блок шифрования, содержащий W ≥ 2 n-разрядных, где n - четное натуральное число, последовательно соединенных операционных узлов, одни из которых выполнены в виде сумматоров, а другие - в виде узлов перестановок, причем вход первого операционного узла является информационным входом блока шифрования, выход W-го операционного узла является выходом блока шифрования, другой вход каждого из сумматоров является одним из управляющих входов блока шифрования, отличающийся тем, что по крайней мере один узел перестановок выполнен в виде узла управляемых перестановок, управляющий вход которого соединен со входом первого операционного узла. 3. Блок шифрования по п.1 или 2, отличающийся тем, что узел управляемых перестановок выполнен в виде матрицы элементарных переключателей, содержащей n - 1 строку, j-я, где j = 1, 2, 3, ..., n - 1, строка содержит n - j элементарных переключателей, управляющие одноразрядные входы которых являются управляющими одноразрядными входами узла управляемых перестановок, первый одноразрядный информационный вход которого является первым одноразрядным информационным входом первого элементарного переключателя первой строки, остальные n - 1 одноразрядных информационных входов узла управляемых перестановок являются вторыми одноразрядными информационными входами элементарных переключателей первой строки, первый одноразрядный информационный вход первого элементарного переключателя j-й, где j ≠ 1, строки является вторым одноразрядным выходом первого элементарного переключателя (j - 1)-й строки, первый одноразрядный информационный вход i-го, где 1 < i ≤ n - j, элементарного переключателя j-й, где j ≠ n - 1, строки является первым одноразрядным выходом (i - 1)-го элементарного переключателя этой строки, второй одноразрядный информационный вход i-го элементарного переключателя j-й, где j ≠ 1, строки является вторым одноразрядным выходом (i + 1)-го элементарного переключателя (j - 1)-й строки, первый одноразрядный выход (n - j)-го элементарного переключателя j-й строки является j-ым одноразрядным выходом узла управляемых перестановок, второй одноразрядный выход переключателя (n - 1)-й строки является n-ым одноразрядным выходом узла управляемых перестановок. 4. Блок шифрования по п.1, отличающийся тем, что в каждую j-ю, где j =1, 2, ..., n/2, строку узла управляемых перестановок введен дешифратор, одноразрядные выходы которого являются одноразрядными управляющими входами элементарных переключателей в соответствующих строках, одноразрядные входы дешифраторов являются одноразрядными управляющими входами узла управляемых перестановок.