Устройство и способ шифрования и дешифрования блока данных

008183 Область техники Настоящее изобретение относится к устройству и способу шифровки и дешифровки блоков данных,известным под названием блочного шифра, в которых размеры входного и выходного блоков совпадают. Данная операция производится с использованием ключа, который может иметь тот же размер, что и блок данных, или другой размер, как правило, больший. Предшествующий уровень техники Изобретение касается симметричного способа шифровки/дешифровки, в отличие от асимметричного способа. Симметричный способ отличается тем, что для шифровки и дешифровки данных используют один и тот же ключ, в то время как при использовании асимметричного способа для шифровки данных применяют первый ключ, а для дешифровки - второй ключ. Хорошо известны способы DES (с 56-битовым ключом), CAST (со 128-битовым ключом), BlowfishAES, с 256-битовым ключом). В зависимости от конкретного приложения каждый из этих способов обладает определенными достоинствами и недостатками. Эти способы были описаны в нескольких патентных публикациях. Патент США 5214703 описывает способ, известный под названием IDEA, основанный на процессе шифровки из 8,5 циклов для блоков длиной в 64 бита, причем в каждом цикле используются 6 подключей, полученных на базе основного ключа. Ядро образовано схемой Lai-Massey, в которой используется сложение по модулю 216, умножение по модулю 216+1 и побитовое логическое сложение типа исключающее ИЛИ. Два основных требования, предъявляемых к любому способу шифровки, - это его устойчивость к любым формам криптоанализа и скорость вычислений. Одним из ключевых факторов обеспечения устойчивости является использование диффузионного эффекта, при котором в случае изменения одного бита входных данных все биты выходных данных изменяются непредсказуемым образом. Скорость вычислений, в основном, определяется типом требуемых математических и логических операций. Использование большего количества сложных операций (деления или умножения) может увеличить время, необходимое для осуществления операции шифровки. Сущность изобретения Задача, на решение которой направлено настоящее изобретение, заключается в предложении нового способа шифровки, в котором высокий уровень безопасности сочетается с высокой скоростью вычислений. Для решения поставленной задачи предлагается способ шифровки или дешифровки блоков данных Х в Y, основанный на основном ключе R, использующий несколько последовательно соединенных основных модуля, причем каждый из основных модулей использует подключ RA, полученный из основного ключа R, и включающий этапы: ввода по меньшей мере двух значений X0L и X0R,смешивания по меньшей мере двух значений X0L и X0R для образования смешанного значения Х 1,получения значения Х 2 путем смешивания первой части RAH подключа RA со значением Х 1,получения значения Х 3 путем обработки значения Х 2 в слое подстановки, причем слой подстановки содержит по меньшей мере один блок (sbox) подстановки, причем каждый блок подстановки содержит таблицу констант, для которой входное значение служит указателем, а указанная константа служит выходным значением,получения значения Х 4 на основе значения Х 3 при помощи диффузионного блока мультиперестановочного типа,получения значения Х 5 путем смешивания второй части RAL подключа RA со значением Х 4,получения значения Х 6 путем обработки значения Х 5 слоем подстановки,получения значения Х 7 путем смешивания первой части RAH подключа RA со значением Х 6,смешивания значения Х 7 с по меньшей мере двумя исходными значениями X0L и X0R для получения по меньшей мере двух значений X8L и X8R, причем значения X8L и X8R составляют выходное значение Х 8 модуля,причем в способе используют по меньшей мере два модуля, для каждого основного модуля из основного ключа R генерируется новый подключ RA, исходные значения Х 0 первого модуля являются подмножеством входных данных X, выходные значения X8L и X8R последнего модуля образуют выходные данные Y, а способ дополнительно включает этап применения к по меньшей мере одному из значений X8L и X8R ортоморфической функции перед направлением данных значений во входные каналыX0R и X0L следующего основного модуля. Двумя основными частями способа являются слой подстановки и мультперестановочная матрица. Слой подстановки предназначен для преобразования входного значения в выходное значение без использования простых алгебраических соотношений. Поэтому наиболее быстрый метод заключается в использовании таблицы соответствий, содержащей константы, при помощи которой можно получить требуемое смешение значений. Поскольку в описываемом варианте осуществления входные данные имеют длину в 32 бита, количество констант равно 232, а длина каждой из них равна 32 битам.-1 008183 В соответствии с предпочтительным вариантом осуществления входные данные разбивают на группы длиной по 8 битов, что сокращает количество констант до 256 байтов. Затем 32- или 64-битовые входные данные разбивают на байты по 8 битов и направляют в подстановочный блок для получения 8-битовых выходных данных. Входные данные используют в качестве указателя адреса, а определенная указателем константа представляет собой выходные данные. В соответствии с одним из вариантов осуществления изобретения таблицы констант могут быть одинаковы для всех групп входных данных (32- или 64-битовых). В другом варианте осуществления таблицы констант могут быть различны для всех групп входных данных. Константы, содержащиеся в такой таблице, представляют собой фиксированную перестановку различных (уникальных) чисел, закодированную по числу битов, равному ширине таблицы. Вторая основная часть способа представляет собой мультиперестановочную матрицу. Мультиперестановочная матрица представляет собой квадратную матрицу, в которой определитель любой возможной квадратной подматрицы не равен нулю, а элементы матрицы являются элементами конечного поля. Операция смешивания сводится к умножению вектора входных элементов на матрицу, в результате которого получают вектор, представляющий собой выходные данные. Краткое описание чертежей Фиг. 1 изображает блок-схему основного модуля в 64-битовой версии. Фиг. 2 иллюстрирует основной процесс с примером использования двух модулей. Фиг. 3 изображает внутреннюю часть основного модуля в 64-битовой версии. Фиг. 4 изображает блок-схему основного модуля в 128-битовой версии. Фиг. 5 изображает блок-схему ортоморфической функции. Фиг. 6 изображает подсистему генерации блока подстановки. Фиг. 7 изображает внутреннюю часть основного модуля в 128-битовой версии. Фиг. 8 иллюстрирует основной процесс с примером использования двух модулей в 128-битовой версии. Фиг. 9 изображает альтернативный вариант блока подстановки. Сведения, подтверждающие возможность осуществления изобретения На фиг. 1 изображен каркас процесса шифровки (или дешифровки), которому соответствует модульMOD. Входные данные Х 0 размером 64 бита, составленные из двух частей X0L и X0R, каждая из которых имеет размер 32 бита, сначала смешивают при помощи смешивающего элемента MX и получают значение Х 1. Смешивающий элемент предназначен для получения 32-битового образа двух 32-битовых наборов данных. Эта операция может быть выполнена различными методами, например с использованием функции X0R (исключающего ИЛИ), сложения по модулю или любого группового правила. Следующий шаг проиллюстрирован блоком f32, который содержит 32-битовые входные данные Х 1 и 32-битовые выходные данные Х 7, а также использует подключ RA. Подробное описание данного блока приведено со ссылками на фиг. 3 (см. ниже). Выходные данные Х 7 блока f32 поступают в два смешивающих блока MX, соединенных с двумя входами X0L и X0R. Итоговые данные X8L и X8R представляют собой два 64-битовых набора Х 8 выходных данных модуля MOD. На фиг. 2 представлена схема всего процесса, в котором используются по меньшей мере два модуляMOD. Входные данные Х сначала поступают в разделяющий модуль SP, преобразующий 64-битовый входной набор Х в два выходных набора X0L1 и X0R1, каждый из которых имеет длину в 32 бита. Действие разделяющего модуля SP может быть основано на различных принципах; например отбора младших битов для набора X0L1, а старших битов - для набора X0R1 или каждого нечетного бита для набора X0L1, а каждого четного бита - для набора X0R1. Также могут использоваться и другие методы разделения входных данных X, если они обеспечивают полное распределение всех битов набора Х между наборами X0L1 и X0R1. Выходные данные X0L1 и X0R1 затем используют в качестве входных данных первого модуляMOD1. Этот первый модуль обрабатывает данные, используя первый подключ RA1. Обработка данныхX0L1 и X0R1 производится так же, как описано со ссылками на фиг. 1. На выходе первого модуля MOD1 получают два набора X8L1 и X8R1 выходных данных. Как показано на фиг. 2, к одному из этих наборов выходных данных, например X8L1, применяют ортоморфическую функцию. Выходные данные, полученные в результате действия этой ортоморфической функции, обозначены как X0L2. Второе значениеX8R1, полученное в результате обработки данных первым модулем MOD1, так же, как и выходные данные X0L2, полученные в результате действия ортоморфической функции, используют в качестве входных данных второго обрабатывающего модуля MOD2. Второй модуль MOD2 обрабатывает входные данные с использованием второго подключа RA2. Выходные данные этого второго модуля обозначены на фиг. 2 как X8L2 и X8R2. Эти выходные данные собирают в шифрованные данные Y при помощи собирающего модуля AS. Собирающий модуль AS имеет те же функции, что и разделяющий модуль SP, но действует в обратном направлении. Следует отметить, что метод восстановления набора Y выходных-2 008183 данных может отличаться от метода разделения данных, используемого в модуле SP, однако, цель его остается неизменной. Все биты данных X8L2 и X8R2 должны присутствовать в данных Y. На фиг. 3 подробно проиллюстрированы функции блока f32, изображенного на фиг. 1. На вход этого блока поступает 32-битовый набор Х 1 данных. Данные разбивают на блоки длиной по 8 битов (Х 1 а,X1b, X1c, X1d) при помощи разделяющего модуля SPMU, также обозначенного на фиг. 3 как Х 1'. Этот блок выполняет ту же функцию, что и блок SP, изображенный на фиг. 2. Каждый из этих 8-битовых блоков смешивают с первой частью RAH подключа RA, чтобы получить значения Х 2 а, X2b, X2c, X2d (составляющие значение Х 2). Эта операция смешивания аналогична той, что описана для блока MX, изображенного на фиг. 1. Два подключа RAH и RAL генерируются разделяющим модулем SP. Этот модуль имеет функцию,аналогичную описанной выше со ссылками на фиг. 1. Каждое из значений X2a-X2d обрабатывают в слое подстановки, содержащем по меньшей мере один блок (sbox) подстановки, причем каждый из блоков подстановки содержит таблицу констант, для которой входящее значение служит указателем, а определенная указателем константа служит выходным значением. Выходные значения обозначены на фиг. 3 как Х 3 а, Х 3b, Х 3 с, X3d и составляют значение Х 3. Один из методов генерирования таблицы констант заключается в использовании генератора псевдослучайных чисел. Повторяющиеся значения должны быть исключены так, чтобы каждая константа в таблице была уникальна. Эти данные вводят в диффузионный блок Мu4, относящийся к типу мультиперестановочных матриц (4,4). Выходные данные диффузионного блока обозначены как Х 4 а, Х 4b, Х 4 с, X4d и составляют значение Х 4. Операция, производимая диффузионным блоком, заключается в умножении вектора (Х 4 а, Х 4b,Х 4 с, X4d) входных данных на квадратную матрицу Мu4 размером 4 х 4, элементы которой принадлежат к конечному полю из 256 элементов и обозначены как Mu(i, j), где индекс i обозначает номер строки, а индекс j - номер столбца. В результате умножения вектора (Х 4 а, Х 4b, Х 4 с, X4d) на матрицу Мu4 получают вектор (Y4a, Y4b, Y4c, Y4d), элементы которого вычисляют следующим образом:Y4d=Mu4(4,1)X4a+Mu4(4,2)X4b+Mu4(4,3)X4c+Mu4(4,4)X4d Символ + обозначает здесь сложение в конечном поле, а символ- умножение в нем же. Элементы матрицы Мu4 подобраны так, чтобы количество вычислений, необходимых для получения четырех вышеуказанных значений, было минимальным. Поэтому количество умножений на константу 1(далее называемых тождествами) выбирается максимальным. Затем данные смешивают со второй частью RAL подключа RA для получения значений Х 5 а, X5b,X5c, X5d, которые составляют значение Х 5. Каждое из значений X5a-X5d обрабатывают в при помощи блока (sbox) подстановки и получают значения Х 6 а, X6b, X6c, X6d, которые составляют значение Х 6. Эти значения смешивают с первой частью RAH подключа RA для получения новых значений Х 7 а, X7b, X7c, X7d, которые составляют значение Х 7. Затем из значений Х 7 а, X7b, X7c, X7d собирают выходной набор Х 7 данных при помощи собирающего модуля AS, описанного выше со ссылками на фиг. 2. Эти данные соответствуют выходным данным Х 7 блока f32, изображенного на фиг. 1. В процессе шифровки основной ключ R разделяют на несколько подключей, каждый из которых приходится на один модуль MOD. В примере, представленном на фиг. 3, первый подключ RA1 используется в сочетании с модулем MOD1, а второй подключ RA2 - в сочетании с модулем MOD2. Для получения данных Х по данным Y и ключу R применяют тот же процесс, что описан со ссылками на фиг. 3, с тем единственным отличием, что подключи генерируются в обратном порядке. Затем подключ RA2 применяют к первому модулю MOD1, а подключ RA1 - ко второму модулю MOD2. В соответствии с общими принципами настоящего изобретения количество последовательно соединенных модулей MOD не ограничено двумя. Как показывает опыт, для получения хорошего уровня устойчивости оптимальным является использование 9 циклов, при котором получаемый результат может быть назван процессом шифровки. Для повышения устойчивости количество циклов может быть увеличено до 12 или более. Фиг. 4 иллюстрирует осуществление модуля MOD64, разработанного для обработки наборов данных длиной по 128 битов. Входные данные X0LL и X0LR смешивают при помощи смешивающего элемента MX для получения выходного значения Х 1L, а входные данные X0RL и X0RR смешивают аналогичным образом для получения выходного значения Х 1R. Следующий шаг проиллюстрирован слоем f64, который содержит два 32-битовых входных набора данных X1L и X1R и два 32-битовых выходных набора данных, а также использует подключ RA. Подробное описание этого блока приведено со ссылками на фиг. 7 (см. ниже). Каждый из этих выходных наборов данных смешивают с двумя входными наборами данных модуляMOD64 в одном и том же смешивающем элементе MX. В представленном примере выходное значениеX7L смешивают соответственно с входными данными X0LL и X0LR, а выходное значение X7R смешивают соответственно с входными данными X0RL и X0RR. Также возможны другие комбинации для смешивания: например, перекрестная конфигурация со смешиванием выходного значения X7L с данными X0LL и X0RR. На фиг. 5 проиллюстрировано осуществление ортоморфической функции. Входные данные обозначены как ZI, а выходные данные - как ZO. Длина данных для этой функции не важна. Входные данные ZI сначала разделяют при помощи разделяющего модуля SP на два набора данных ZL и ZR одинаковой длины. Затем два набора данных смешивают при помощи так называемого смешивающего элемента MX,а выходные данные этого элемента вводят в собирающий модуль AS. Второе из разделенных значенийZR прямо направляют в собирающий модуль AS без изменений. Этот модуль содержит два входных канала и собирает эти данные в выходные данные ZO. Этот модуль работает по принципу, обратному принципу работы разделяющего модуля SP. Особенность данного осуществления заключается в том, что входные каналы собирающего модуля расположены перекрестно относительно выходных каналов разделяющего модуля SP. Данные из правого выходного канала ZR разделяющего модуля SP направляют в левый входной канал собирающего модуля AS, а данные из левого выходного канала ZR разделяющего модуля SP после смешивания с другими выходными данными разделяющего модуля SP направляют в правый входной канал собирающего модуля AS. Для осуществления блока подстановки существует несколько возможностей. Выше был описан метод, основанный исключительно на использовании таблицы констант. Первый шаг, предпринимаемый для уменьшения размеров таблицы, заключается в разделении входных данных и обработки части данных при помощи таблицы гораздо меньшего размера. На фиг. 3 приведен пример блока подстановки, работающего с наборами данных длиной в 8 битов,для чего требуется таблица из 256 констант. В некоторых случаях, в частности, если объем памяти является важным фактором, используются альтернативные варианты. Один из таких вариантов описан со ссылками на фиг. 6-9. На фиг. 6 изображена подсистема Сbох блока подстановки, содержащая один входной канал С, разделенный на два входных канала CL и CR, а также два выходных канала CL' и CR'. Основным элементом этой системы является модуль ТА, который содержит таблицу констант из 2(n/2) элементов, каждый размером по n/2 битов, где n - длина исходного набора данных С. Если входные данные имеют длину в 8 битов, таблица констант содержит 16 (24) элементов, каждый длиной по 4 бита. Эти элементы генерируются случайным образом с учетом того, что каждый элемент должен иметь уникальное значение. Фиг. 9 иллюстрирует использование модуля Сbох для создания блока подстановки. Сначала входное значение CI разделяют на две части CL1 и CR1 и направляют в первый модуль Сbох 1, как описано со ссылками на фиг. 3. Выходные данные модуля Сbох 1 направляют в следующий модуль Сbох 2. Один из выходных наборов данных первого модуля, в данном случае данные CL1', перед направлением во второй модуль Сbох 2 обрабатывают при помощи ортоморфической функции OR (ИЛИ). В работе модуля подстановки обычно используют по меньшей мере две подсистемы Сbох, каждая из которых имеет свою таблицу констант ТА. В представленном примере в модуле подстановки используются три подсистемы Сbох, причем в соответствии с данным вариантом осуществления изобретения выходные данные последней из этих подсистем не обрабатывают при помощи ортоморфической функции OR. На фиг. 7 представлен вариант осуществления, альтернативный варианту по фиг. 3 и предназначенный для работы с данными длиной в 64 бита. В целом, для обработки 64-битовых данных дублируют схему, разработанную для обработки 32-битовых данных. Входные данные Х 1 разбивают на вектор с элементами длиной по 8 битов (Х 1 а-Х 1h) и обрабатывают так же, как было описано выше со ссылками на фиг. 3. Главное отличие заключается в использовании диффузионного блока Мu8, представляющего собой матрицу из 8 х 8 элементов, выбранных из конечного поля 256 элементов. Элементы матрицы обозначены как Mu8(i, j), где индекс i обозначает номер строки, а индекс j - номер столбца. Умножение входного вектора (Х 3 а, , Х 3h) на матрицу Мu8 дает выходной вектор (Y3a, , Y3h) по следующим формулам (в которых символ + обозначает сложение, а символ- умножение в конечном поле):Mu8(8,7)X3g+Mu8(8,8)X3h; Фиг. 8 полностью иллюстрирует весь процесс, в котором использованы два цикла работы модуляMOD64. Разделяющий модуль SP разделяет входные данные Х длиной в 128 битов на четыре части, а именно X0LL1, X0LR1, X0RL1 и X0RR1 (которые вместе составляют значение Х 0). Две части выходных данных модуля MOD64-1 затем обрабатывают при помощи ортоморфической функции OR, а затем направляют на вход следующего модуля MOD64-2. Положение ортоморфической функции OR относительно выходных каналов модуля MOD64 не является решающим фактором. Для обработки этой функцией могут быть выбраны два левых выходных канала или два правых выходных канала в зависимости от конкретного варианта осуществления данного способа. Выходные данные Y получают прямо из последнего модуля MOD64 без использования ортоморфической функции OR в одном из его выходных каналов. Если используется более двух модулей MOD64, ортоморфическую функцию OR предусматривают между каждыми двумя модулями MOD64. Хотя в предпочтительном варианте осуществления изобретения положение ортоморфических функций OR остается неизменным независимо от номера модуля, в других вариантах осуществления положение этих ортоморфических функций OR может изменяться с соединением функции с другими выходными каналами модуля MOD64. ФОРМУЛА ИЗОБРЕТЕНИЯ 1. Способ шифровки или дешифровки блоков данных Х в Y, основанный на основном ключе R, использующий по меньшей мере два последовательно соединенных основных модуля (MOD), причем каждый из основных модулей (MOD) использует подключ (RA), полученный из основного ключа (R), и включающий этапы: вводят по меньшей мере два исходных значения X0L и X0R,смешивают по меньшей мере два значения X0L и X0R для образования смешанного значения Х 1,получают значение Х 2 путем смешивания первой части RAH подключа RA со значением Х 1,получают значение Х 3 путем обработки значения Х 2 в слое подстановки, причем слой подстановки содержит по меньшей мере один блок (sbox) подстановки, причем каждый блок подстановки содержит таблицу констант, для которой входное значение служит указателем, а указанная константа служит выходным значением,получают значение Х 4 на основе значения Х 3 при помощи диффузионного блока мультиперестановочного типа,получают значение Х 5 путем смешивания второй части RAL подключа RA со значением Х 4,получают значение Х 6 путем обработки значения Х 5 блоком подстановки,получают значение Х 7 путем смешивания первой части RAH подключа RA со значением Х 6,смешивают значение Х 7 по меньшей мере с двумя исходными значениями X0L и X0R для получения по меньшей мере двух значений X8L и X8R, причем значения X8L и X8R составляют выходное значение Х 8 модуля,причем для каждого основного модуля (MOD) из основного ключа (R) генерируется новый подключ (RA), исходные значения X0L и X0R первого модуля являются подмножеством входных данных X,выходные значения X8L и X8R последнего модуля образуют выходные данные Y, а способ дополнительно включает этап применения по меньшей мере к одному из значений X8L и X8R ортоморфической функции перед направлением данных значений во входные каналы X0R и X0L следующего основного модуля. 2. Способ шифровки или дешифровки по п.1, отличающийся тем, что входные данные имеют длину 64 бит, причем входные данные Х разделены на два исходных значения X0L и X0R длиной по 32 бит, а два выходных значения X8L и X8R образуют выходные данные Y. 3. Способ шифровки или дешифровки по п.1, отличающийся тем, что входные данные имеют длину 128 бит, причем входные данные Х разделены на четыре исходных значения X0LL, X0LR, X0RL и X0RR длиной по 32 бит, а четыре выходных значения X8LL, X8LR, X8RL и X8RR образуют 128-битовые выходные данные Y, первая часть X1L значения Х 1 получена смешиванием значения X0LL с X0LR, а вторая часть Х 1R значения Х 1 получена смешиванием значения X0RL с X0RR, первая часть X7L значения Х 7 смешана с двумя из четырех исходных значений X0LL, X0LR, X0RL и X0RR, а вторая часть X7R значения Х 7 смешана с оставшимися двумя частями исходных значений X0LL, X0LR, X0RL и X0RR.-5 008183 4. Способ шифровки или дешифровки по п.1, отличающийся тем, что слой подстановки содержит несколько блоков (sbox) подстановки, каждый из которых имеет 8-битовый входной канал и 8-битовый выходной канал, причем входные данные слоя подстановки разбиты на части длиной по 8 бит. 5. Способ шифровки или дешифровки по п.4, отличающийся тем, что таблица (ТА) констант блока(sbox) подстановки на определенное входное значение выдает определенное выходное значение. 6. Способ шифровки или дешифровки по п.4, отличающийся тем, что таблицы констант всех блоков(sbox) подстановки одинаковы. 7. Способ шифровки или дешифровки по п.4, отличающийся тем, что таблицы констант всех блоков(sbox) подстановки различны. 8. Способ шифровки или дешифровки по п.4, отличающийся тем, что таблица констант блока (sbox) подстановки изменяется при каждом цикле работы основного модуля. 9. Способ шифровки или дешифровки по п.1, отличающийся тем, что длина данных равна 64 битам, а диффузионный блок представляет собой матричную функцию Y3 = МХ 4, где аргумент М определяет 44 операции сложения, умножения или тождества, причем по меньшей мере одна строка и один столбец содержат по три тождества. 10. Способ шифровки или дешифровки по п.9, отличающийся тем, что остальные строки и остальные столбцы аргумента М содержат по два тождества. 11. Способ шифровки или дешифровки по п.1, отличающийся тем, что длина данных равна 128 битам, а диффузионный блок представляет собой матричную функцию Y3 = NХ 3, где аргумент N определяет 88 операций сложения, умножения или тождества, причем по меньшей мере одна строка и один столбец содержат по семь тождеств.