Главная страница  |  Описание сайта  |  Контакты
ШИФРУЮЩИЙ БЛОК
ШИФРУЮЩИЙ БЛОК

ШИФРУЮЩИЙ БЛОК

Патент Российской Федерации
Суть изобретения: Изобретение относится к области электросвязи и вычислительной техники, а конкретно к области криптографических способов и устройств для шифрования данных. Блок шифрования содержит по крайней мере один узел перестановок и W ≥ 2 n-разрядных, где n - четное натуральное число последовательно соединенных сумматоров, причем первый вход первого сумматора является информационным входом шифрующего блока, выход W-го сумматора является выходом шифрующего блока, отличающийся тем, что узел перестановок выполнен в виде узла управляемых перестановок, информационный вход которого является управляющим входом шифрующего блока, выход узла управляемых перестановок является вторым входом P-го сумматора, где I ≅ P ≅ W, а управляющий вход узла управляемых перестановок соединен с первым входом G-го сумматора, где I ≅ G ≅ W, чем обеспечивается повышение криптостойкости к диффренциальному криптоанализу. 2 з.п. ф-лы, 7 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2140715
Класс(ы) патента: H04L9/28
Номер заявки: 98111642/09
Дата подачи заявки: 18.06.1998
Дата публикации: 27.10.1999
Заявитель(и): Молдовян Александр Андреевич
Автор(ы): Зима В.М.; Молдовян Н.А.; Молдовян А.А.; Савлуков Н.В.
Патентообладатель(и): Открытое акционерное общество "Московская городская телефонная сеть"; Государственное унитарное предприятие Специализированный центр программных систем "СПЕКТР"; Молдовян Александр Андреевич
Описание изобретения: Изобретение относится к области электросвязи и вычислительной техники, а конкретнее к области криптографических способов и устройств для шифрования сообщений (информации). В совокупности признаков заявляемого способа используются следующие термины:
- секретный ключ представляет из себя комбинацию битов, известную только законному пользователю;
- ключ шифрования представляет из себя комбинацию битов, используемую при шифровании информационных сигналов данных; ключ шифрования является сменным элементом шифра и используется для преобразования данного сообщения или данной совокупности сообщений; ключ шифрования формируется по детерминированным процедурам по секретному ключу; в ряде шифров в качестве ключа шифрования используется непосредственно секретный ключ;
- шифр представляет собой совокупность элементарных шагов преобразования входных данных с использованием шифрключа; шифр может быть реализован в виде программы для ЭВМ или в виде отдельного электронного устройства;
- подключ представляет собой часть ключа шифрования, используемую на отдельных элементарных шагах шифрования;
- шифрование есть процесс, реализующий некоторый способ преобразования данных с использованием шифрключа, переводящий данные в криптограмму, представляющую собой псевдослучайную последовательность знаков, из которой получение информации без знания ключа шифрования практически невыполнимо;
- дешифрование есть процесс, обратный процедуре шифрования; дешифрование обеспечивает восстановление информации по криптограмме при знании ключа шифрования;
- криптостойкость является мерой надежности защиты информации и представляет собой трудоемкость, измеренную в количестве элементарных операций, которые необходимо выполнить для восстановления информации по криптограмме при знании алгоритма преобразования, но без знания ключа шифрования.
Известны устройства шифрования, выполненные в виде механических машин и электромеханических устройств [В. Жельников. Криптография от папируса до компьютера. -М., ABF, 1996, 336 с.]. Кроме того, известны электронные устройства шифрования, реализующие способ шифрования, описанный в Российском стандарте криптографической защиты данных [Стандарт СССР ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования]. Устройство, реализующее Российский стандарт шифрования, включает в себя шифрующий блок, состоящий из нескольких операционных узлов: сумматора по модулю 232, поразрядного сумматора по модулю 2, операционного узла, выполняющего циклический сдвиг влево на 11 бит, и операционного узла, выполняющего операцию подстановки.
Наиболее близким по своей технической сущности к заявляемому шифрующему блоку является шифрующий блок, используемый в устройстве шифрования, реализующем способ шифрования в соответствии с американским федеральным стандартом DES [National Bureau of Standards. Data Encryption Standard. Federal Information Processing Standards Punlication 46, January 1977]. Данный способ включает в себя формирование секретного ключа, разбиение входной информации, представленной в виде двоичного кода, на участки длиной по 64 бит, формирование на их основе 64-битовых блоков данных и преобразование блоков под управлением секретного ключа. Перед преобразованием каждый блок данных разбивается на две 32-битовых подблока L и R, которые поочередно преобразуются путем выполнения 16 однотипных раундов преобразования. Один раунд преобразования заключается в выполнении операций расширения, подстановки, перестановки и суммирования по модулю 2, реализующих раундовую функцию шифрования над подблоком R, что записывается в виде формулы R: = F(R), где знак ": =" обозначает операцию присваивания, F - раундовая функция шифрования. Каждый раунд завершается перестановкой подблоков R и L: T: = R, R: = L, L: = T.
Устройство шифрования (VIII), реализующее стандарт шифрования DES, представлено в виде блок-схемы на фиг. 1 и содержит 64-разрядный информационный вход 1, состоящий из двух 32-разрядных информационных входов 1.а и 1.б, на которые подаются два 32-битовых подблока L и R, 64-разрядный выход 2, состоящий из двух 32-разрядных выходов 2.а и 2.б, с которых снимаются преобразованные 32-битовые подблоки L и R, управляющий вход 9, шифрующий блок 3 (ШБ), блок генерации раундового подключа (БГРП), блок управления БУ и управляющую шину 10. Шифрующий блок содержит 32-разрядный информационный вход 6, 32-разрядный выход 4 и 80-разрядный управляющий вход 5, состоящий из 32-разрядного управляющего входа 5.1 и 48-разрядного управляющего входа 5.2. Информационный вход шифрующего блок 6 соединен с информационным входом 1.б и выходом 2. а устройства шифрования. Выход шифрующего блока 4 соединен с выходом 2.б устройства шифрования. Управляющий вход 5.1 шифрующего блока соединен с входом 1.а устройства шифрования. Управляющий вход 5.2 шифрующего блока соединен с выходом 7 блока генерации раундового ключа. Вход блока генерации раундового ключа 8 соединен с управляющим входом устройства шифрования 9.
Устройство шифрования (фиг. 1) работает следующим образом. На вход устройства шифрования подается 56-битовый ключ, который преобразуется в последовательность 48-битовых раундовых подключей Kr, r = 1,2,...,16. Для текущего r-го раунда на выходе блока генерации раундового ключа устанавливается двоичный код, соответствующий значению подключа Kr. Шифруемый 64-битовый блок данных B подается на вход устройства шифрования. Старше 32 бита блока B, обозначаемые как подблок L, подаются на вход 1.а. Младшие 32 бита блока B, обозначаемые как подблок R, подаются на вход 1.б. Обозначим начальные значения подблоков индексом "0", а их значения после выполнения r-го раунда шифрования - индексом "r". Шифрующий блок на r-м раунде преобразует значение подблока Rr-1 в значение Rr = F(Rr-1, Kr), которое зависит от типа функции F и значения раундового подключа Kr. Выходное значение подблока L в текущем раунде устанавливается равным входному значению подблока R. Таким образом, устройство шифрования выполняет следующее преобразование, которое может быть записано с помощью следующих итеративных формул
Lr = Rr-1, (1)
Rr = F(Rr-1, Lr-1, Kr), (2)
где вычисление функции F от значения Rr-1 осуществляется шифрующим блоком в зависимости от значения Lr-1, подаваемого на вход 5.1, и значения Kr, подаваемого на вход 5.2. Блок управления синхронизирует работу блока генерации раундового подключа и шифрующего блока и осуществляет контроль числа выполненных раундов преобразования. Если текущий номер раунда не равен 16, то блок управления текущие значения подблоков Lr и Rr на выходе устройства шифрования подает на вход устройства шифрования для выполнения следующего раунда. Значения L16 и R16 составляют выходной блок шифртекста.
Шифрующий блок представлен на фиг. 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-битового подблока данных Rr-1 в 48-битовый подблок R'. Операционный узел 3.2 выполняет поразрядное суммирование по модулю 2 значение R' с подключом Kr и выдает на входе значение Rʺ = Rʹ⊕ Kr, где знак ⊕ обозначает операцию поразрядного суммирования по модулю 2. Операционный узел 3.3 выполняет операцию подстановки над 48-битовым значением R'' и заменяют его на 32-битовое значение R''' в соответствии с таблицами замены, приведенными в стандарте шифрования DES. Операционный узел 3.4 осуществляет перестановку битов двоичного значение R'''и выдает на выход преобразованное значение R*. Операционный узел 3.5 выполняет операцию поразрядного суммирования по модулю два над значением R*, подаваемым на его информационный вход, и значением Lr-1, подаваемым на его управляющий вход. Значение на выходе операционного узла 3.5 Rr = R*⊕ Lr-1 является значением функции F(Rк-1, Lr-1, Kr), вычисляемой шифрующим блоком.
Устройство шифрования, осуществляющее шифрование в соответствии со стандартом DES, обладает высокой скоростью преобразований при реализации в виде специализированных электронных схем.
Однако это устройство имеет недостатки, а именно оно не обеспечивает высокой криптостойкости к дифференциальному криптоанализу [Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems// Journal of Cryptology. 1991. V. 4. N. 1. pp. 3-72]. Этот недостаток связан с тем, что все операционные узлы выполняют фиксированные операции преобразования для всех преобразуемых блоков данных.
В основу изобретения положена задача разработать шифрующий блок, осуществляющий преобразования, зависящие от преобразуемого блока данных, благодаря чему повышается криптостойкость к дифферанциальному криптоанализу.
Поставленная цель достигается тем, что в шифрующем блоке, содержащем n-разрядный, где n - четное натуральное число, информационный вход, n-разрядный выход, m-разрядный управляющий вход и W ≥ 2 операционных узлов, одноразрядные информационные входы первого операционного узла являются одноразрядными информационными входами шифрующего блока, одноразрядные выходы V-го, где 1 ≅ V < W, операционного узла соединены с одноразрядными входами (V + 1)-го операционного узла, одноразрядные выходы W-го операционного узла являются одноразрядными выходами шифрующего блока, причем по крайней мере один операционный узел содержит одноразрядные управляющие входы, соединенные с одноразрядными управляющими входами шифрующего блока, новым согласно изобретению является то, что шифрующий блок дополнительно содержит по крайней мере один операционный узел, выполненный в виде узла управляемых перестановок, одноразрядные информационные входы которого соединены с одноразрядными управляющими входами шифрующего блока, одноразрядные выходы узла управляемых перестановок соединены с одноразрядными управляющими входами P-го, где P ≅ W, операционного узла, одноразрядные управляющие входы узла управляемых перестановок соединены с одноразрядными входами G-го, где G ≅ 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 представлена функциональная схема шифрующего блока, включающая два узла управляемых перестановок, один из которых осуществляет зависящее от входного блока данных преобразование подблока данных L, а другой - преобразование раундового подключа.
Узел управляемых перестановок, представленный функциональной схемой на фиг. 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 - i, что задает число управляющих одноразрядных входов 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, где представлена функциональная схема шифрующего блока с одним узлом управляемых перестановок P. Шифрующий блок включает операционные узлы 3.1, 3.2 и 3.3. Операционный узел 3.1 выполняет операцию перестановки битов n-разрядного раундового подключа Kr в зависимости от значения подблока данных Rr-1, вырабатывая на выходе подблок данных n-разрядный двоичный вектор где Pr-1(Kr) обозначает операцию перестановки, выполняемую над значением Kr в зависимости от значение Rr-1. Операционный узел 3.2 выполняет операцию суммирования по модулю 2n над n-битовым подблоком данных Rr-1 и n-битовым двоичным вектором K', представляющим собой преобразованное значение раундового подключа Kr, вырабатывая на выходе n-разрядный подблок данных.
R' = (Rr-1 + K') mod 2n.
Операционный узел 3.3 выполняет операцию поразрядного суммирования по модулю 2 над n-битовым подблоком данных R' и n-битовым подблоком данных Lr-1, вырабатывая на выходе n-разрядное значение
Rr = Rʹ⊕ Lr-1.
Последовательное выполнение операций, задаваемых узлами 3.1, 3.2 и 3.3, определяет раундовую функцию шифрования Rr = F(Rr-1, Lr-1, Kr). Данный шифрующий блок может быть использован, например, в устройстве шифрования, представленном на фиг. 1, для осуществления 16 раундов преобразования в соответствии с итеративными соотношениями (1) и (2).
Пример 2. Пример реализации шифрующего блока с двумя блоками управляемых перестановок представлен на фиг. 7, где операционный узел 3.1 выполняет перестановку битов раундового подключа Kr в зависимости от значение подблока Rr-1, операционный узел 3.2 представляет собой поразрядный сумматор по модулю 2, операционный узел 3.3 представляет собой узел управляемых перестановок, осуществляющий перестановку битов подблока Lr-1, формируя на выходе значение L' = PR'(Lr-1), операционный узел 3.4 представляет собой сумматор по модулю 2n. Раундовая функция шифрования Rr = F(Rr-1, Lr-1, Kr), задаваемая шифрующим блоком, показанным на фиг. 7, описывается следующей последовательностью преобразований:

2. Rʹ = Rr-1⊕ Kʹ,
3. L' = PR'(Lr-1),
4. Rr = (R' + L') mod 232.
Шифрующий блок, рассмотренный в примере 1 может быть использован, например, в составе устройства шифрования, показанном на фиг. 1.
Приведенные примеры показывают, что предлагаемый шифрующий блок технически реализуем и позволяет решить поставленную задачу.
Заявляемый шифрующий блок может быть реализован, например, в специализированных криптографических микропроцессорах, обеспечивающих скорость шифрования до 1 Гбит/с, достаточную для шифрования в масштабе реального времени данных, передаваемых по скоростным оптоволоконным каналам связи.
Формула изобретения: 1. Шифрующий блок, содержащий по крайней мере один узел перестановок и W≥2 n-разрядных, где n-четное натуральное число, последовательно соединенных сумматоров, причем первый вход первого сумматора является информационным входом шифрующего блока, выход W-го сумматора является выходом шифрующего блока, отличающийся тем, что узел перестановок выполнен в виде узла управляемых перестановок, информационный вход которого является управляющим входом шифрующего блока, выход узла управляемых перестановок является вторым входом Р-го сумматора, где 1≅P≅W, а управляющий вход узла управляемых перестановок соединен с первым входом G-го сумматора, где 1≅G≅W.
2. Шифрующий блок по пп.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-ым одноразрядным выходом узла управляемых перестановок.
3. Шифрующий блок по п.1, отличающийся тем, что в каждую j-ю, где j = 1,2, ..., n/2, строку узла управляемых перестановок введен дешифратор, одноразрядные выходы которого являются одноразрядными управляющими входами элементарных переключателей в соответствующих строках, одноразрядные входы дешифраторов являются одноразрядными управляющими входами узла управляемых перестановок.