Устройство криптографической обработки, способ криптографической обработки

Устройство криптографической обработки, способ криптографической обработки

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Уровень техники

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

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

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

Также в криптографической системе с общим ключом существуют различные алгоритмы. Один из них представляет собой систему, в которой множество ключей генерируют с использованием общего ключа в качестве основания, и обработку преобразования данных многократно выполняют для каждого модуля блока (64 бита, 128 бит и т.д.) с использованием множества сгенерированных ключей. Типичный алгоритм, в котором используется такой способ генерирования ключа, и обработка преобразования данных представляет собой криптографический способ общий-ключ-блок.

В качестве типичного алгоритма криптографической обработки общий-ключ-блок, например, используется алгоритм DES (Стандарт шифрования данных), который представляет собой стандартный федеральный способ шифрования в Соединенных Штатах Америки и широко используется в различных областях.

Любой алгоритм, применяемый для криптографической обработки общий-ключ-блок, в соответствии со стандартом DES, в основном, может быть разделен на блок функции цикла, который выполняет преобразование входных данных, и блок планирования ключа, предназначенный для генерирования ключа, применяемого в каждом цикле части функции цикла (F-функции). Ключ (подключ) цикла, который должен применяться в каждом цикле в блоке функции цикла, генерируют в блоке планирования ключа, в который вводят один мастер-ключ (главный ключ), и применяют в каждой части функции цикла.

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

Простота анализа ключа средствами криптоанализа приводит к низкой безопасности криптографической обработки. В обычном алгоритме DES возникает проблема, состоящая в том, что поскольку обработка (матрица преобразования), применяемая в блоке линейного преобразования блока функции цикла (F-функции), эквивалентна в цикле каждого этапа, упрощается криптоанализ, и, следовательно, облегчается анализ ключа.

Сущность изобретения

Проблема, решаемая изобретением

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

Средство решения проблемы

В первом аспекте настоящее изобретение направлено на устройство криптографической обработки, предназначенное для выполнения криптографической обработки общий-ключ-блок типа Фейстеля, имеющее структуру, которая повторно выполняет F-функцию SPN-типа, имеющую блок нелинейного преобразования и блок линейного преобразования в течение множества циклов, в котором каждый из блоков линейного преобразования F-функций, соответствующий каждому из множества циклов, выполнен с возможностью выполнения обработки линейного преобразования для входных n битов, выводимых из каждого из m блоков нелинейного преобразования, в сумме составляющих mn битов, в качестве обработки линейного преобразования, в которой используется квадратная матрица РМР, причем, по меньшей мере, в последовательных циклах с нечетными номерами и в последовательных циклах с четными номерами применяют разные квадратные матрицы РМР L_a, L_b, и матрица, состоящая из m векторов колонок, выбранных произвольно из векторов колонок, составляющих обратные матрицы L_a ^-1, L_b ^-1 для квадратных матриц РМР, является линейно независимой.

Кроме того, в одном варианте выполнения устройства криптографической обработки в соответствии с этим изобретением, устройство криптографической обработки отличается тем, что матрица, состоящая из m векторов колонок, выбранных произвольно из векторов колонок, составляющих обратные матрицы L_a ^-1, L_b ^-1, представляет собой квадратную матрицу РМР.

Кроме того, в одном варианте выполнения устройства криптографической обработки в соответствии с этим изобретением, устройство криптографической обработки отличается тем, что алгоритм криптографической обработки общий-ключ-блок типа Фейстеля представляет собой криптографический алгоритм с количеством циклов 2r, и блок линейного преобразования F-функции выполнен с возможностью выполнения линейного преобразования, в котором последовательно и повторно применяют q различных видов 2≤q≤r квадратных матриц РМР во всех r циклах с четными номерами и во всех r циклах с нечетными номерами.

Кроме того, в одном варианте выполнения устройства криптографической обработки в соответствии с этим изобретением устройство криптографической обработки отличается тем, что каждая из множества различных квадратных матриц РМР, предназначенных для применения в блоке линейного преобразования F-функции, представляет собой квадратную матрицу РМР, которая состоит из m векторов колонок, выбранных произвольно из векторов колонок, составляющих множество квадратных матриц РМР, и является линейно независимой.

Кроме того, в одном варианте выполнения устройства криптографической обработки в соответствии с этим изобретением, устройство криптографической обработки отличается тем, что каждая из множества разных квадратных матриц РМР, предназначенных для применения в блоке линейного преобразования F-функции, представляет собой квадратную матрицу РМР, в результате чего матрица, состоящая из m векторов колонок, выбранных произвольно из векторов колонок, составляющих множество квадратных матриц РМР, также представляет собой квадратную матрицу РМР.

Кроме того, в одном варианте выполнения устройства криптографической обработки в соответствии с этим изобретением, устройство криптографической обработки отличается тем, что каждая из множества разных квадратных матриц РМР, предназначенных для применения в блоке линейного преобразования F-функции, составлена из матрицы, которая составлена из векторов рядов, выделенных из матрицы M', которая состоит из векторов рядов, выбранных из квадратной матрицы М РМР, включающей все элементы, составляющие множество квадратных матриц РМР.

Во втором аспекте данное изобретение направлено на криптографический способ выполнения криптографической обработки общий-ключ-блок типа Фейстеля, содержащий следующие этапы: выполнения F-функции SPN-типа, предназначенной для выполнения обработки нелинейного преобразования и обработки линейного преобразования повторно в течение множества циклов; и при обработке преобразования F-функции, соответствующей каждому из множества циклов, выполнения линейного преобразования для n битов, поступающих с выхода m блоков нелинейного преобразования, что в сумме составляет mn битов, в качестве обработки линейного преобразования, в которой применяют квадратные матрицы РМР; в котором обработку линейного преобразования с квадратными матрицами РМР выполняют так, что, по меньшей мере, в последовательных циклах с четными номерами и в последовательных циклах с нечетными номерами применяют разные квадратные матрицы РМР L_a, L_b, и матрица, составленная из m векторов колонок, выбранных произвольно из векторов колонок, составляющих обратные матрицы La^-1, Lb^-1 для квадратных матриц РМР, является линейно независимой и составляет квадратную матрицу РМР.

Кроме того, в одном варианте выполнения способа криптографической обработки в соответствии с этим изобретением, способ криптографической обработки отличается тем, что обработку линейного преобразования с использованием квадратных матриц РМР выполняют так, что матрица, состоящая из m векторов колонок, выбранных произвольно из векторов колонок, составляющих обратные матрицы L_a ^-1, L_b ^-1, представляет собой квадратную матрицу РМР.

Кроме того, в одном варианте выполнения способа криптографической обработки в соответствии с этим изобретением, способ криптографической обработки отличается тем, что алгоритм криптографической обработки общий-ключ-блок типа Фейстеля представляет собой криптографический алгоритм с количеством циклов, равным 2r, и при обработке линейного преобразования F-функции последовательно и повторно выполняют обработку линейного преобразования с использованием q видов разных квадратных матриц РМР 2≤q<r.

Кроме того, в одном варианте выполнения способа криптографической обработки в соответствии с этим изобретением, способ криптографической обработки отличается тем, что каждая из множества разных квадратных матриц РМР, предназначенных для применения при обработке линейного преобразования F-функции, выполнена так, что матрица, которая состоит из m векторов колонок, выбранных произвольно из векторов колонок, составляющих множество квадратных матриц РМР, является линейно независимой и составляет квадратную матрицу РМР.

Кроме того, в одном варианте выполнения способа криптографической обработки в соответствии с этим изобретением, способ криптографической обработки отличается тем, что каждая из множества разных квадратных матриц РМР, предназначенных для применения при обработке линейного преобразования F-функции, представляет собой квадратную матрицу РМР так, что матрица, составленная из m векторов колонок, выбранных произвольно из векторов колонок, составляющих множество квадратных матриц РМР, становится квадратной матрицей РМР.

Кроме того, в одном варианте выполнения способа криптографической обработки в соответствии с этим изобретением, способ криптографической обработки отличается тем, что каждая из множества разных квадратных матриц РМР, предназначенных для применения при обработке линейного преобразования F-функции, состоит из матрицы, составленной из векторов колонок, выделенных из матрицы M', состоящей из векторов рядов, выбранных из квадратной матрицы М РМР, включающей в себя все элементы, составляющие множество квадратных матриц РМР.

Настоящее изобретение также направлено на компьютерную программу, предназначенную для выполнения криптографической обработки общий-ключ-блок типа Фейстеля, которая содержит этап повторного выполнения F-функции SPN-типа, состоящий в выполнении обработки нелинейного преобразования и обработки линейного преобразования для множества циклов, в которой обработка линейного преобразования F-функции, соответствующей каждому из множества циклов, представляет собой этап линейного преобразования, состоящий в выполнении обработки линейного преобразования для входных n битов, поступающих из каждого из m блоков нелинейного преобразования, в сумме составляющих mn битов, в качестве обработки линейного преобразования, в которой применяют квадратные матрицы РМР (разделяемые с максимальным расстоянием). На этапе линейного преобразования, по меньшей мере, в последовательных циклах с четными номерами и в последовательных циклах с нечетными номерами используют разные квадратные матрицы РМР L_a, L_b, и каждая из квадратных матриц РМР является такой, что матрица, составленная из m векторов колонок, выбранных произвольно из векторов колонок, составляющих обратные матрицы L_a ^-1, L_b ^-1 для квадратных матриц РМР, является линейно независимой.

Следует отметить, что компьютерная программа в соответствии с настоящим изобретением представляет собой компьютерную программу, которая установлена, например, в компьютерной системе, которая может выполнять различные программные коды с использованием любого из носителей данных и среды передачи данных в компьютеры, в форме, считываемой с ,например, носителей данных типа CD (компакт-диск), FD (гибкий диск), МО (магнитооптический диск) и т.д., или путем передачи по среде передачи данных, такой как сеть и т.д. Благодаря предоставлению такой программы в считываемой компьютером форме обработка, которая соответствует программе, может быть реализована в компьютерной системе.

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

В соответствии с конфигурацией этого изобретения, криптографическую обработку выполняют в соответствии с криптографической обработкой общий-ключ-блок типа Фейстеля, состоящей в выполнении F-функции SPN-типа, которая имеет блок нелинейного преобразования и блок линейного преобразования, повторно в течение множества циклов обработку линейного преобразования F-функции, соответствующую каждому из множества циклов, выполняют как обработку линейного преобразования, в которой используются квадратные матрицы РМР (разделяемые с максимальным расстоянием). И она выполнена с возможностью выполнения обработки линейного преобразования с квадратными матрицами РМР, в которых применяют квадратные матрицы PMP L_a, L_b, которые отличаются, по меньшей мере, в последовательных циклах с четными номерами и в последовательных циклах с нечетными номерами, и матрица, состоящая из m векторов колонок, произвольно выбранных из векторов колонок, составляющих обратные матрицы L_a ^-1, L_b ^-1 квадратных матриц PMP, является линейно независимой или составляет квадратную матрицу PMP. В соответствии с этим повышается устойчивость к атакам линейного криптоанализа в шифре общий-ключ-блок, и увеличивается трудность при анализе ключа шифрования и т.д.; поэтому обеспечивается возможность реализации криптографической обработки с высоким уровнем защиты.

Кроме того, в соответствии с конфигурацией этого изобретения, при обработке, состоящей в криптографической обработке общий-ключ-блок типа Фейстеля, в которой повторно выполняют F-функцию SPN-типа, имеющую блок нелинейного преобразования и блок линейного преобразования в течение множества циклов, причем обработку линейного преобразования F-функции, соответствующую каждому из множества циклов, выполняют как обработку линейного преобразования, в которой используются квадратные матрицы PMP (разделяемые с максимальным расстоянием), в то время как обработку выполняют таким образом, что применяют квадратные матрицы PMP, которые отличаются, по меньшей мере, в последовательных циклах с нечетными номерами и в последовательных циклах с четными номерами, и сами эти квадратные матрицы PMP выполнены так, что проявляют линейную независимость или составляют квадратные матрицы PMP. Поэтому становится возможным гарантировать, что не будет возникать одновременное сокращение различий в результате вклада активных S-блоков, и следовательно, становится возможным увеличить минимальное количество активных S-блоков во всей криптографической функции, что представляет собой один из показателей устойчивости к атакам дифференциального криптоанализа в шифре общий-ключ-блок. Такая конфигурация повышает устойчивость как к атакам линейного криптоанализа, так и к атакам дифференциального криптоанализа, и позволяет реализовать криптографическую обработку с высокой степенью защиты.

Краткое описание чертежей

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

На фиг.2А и 2В показаны схемы, поясняющие структуру F-функции, установленной как блок функции цикла. На фиг.2А показана схема, представляющая вход и выход F-функции 120 в одном цикле. На фиг.2В показана схема, подробно представляющая структуры F-функции 120.

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

На фиг.4 показана схема, поясняющая одновременное сокращение различий трех этапов в шифре 128-битном блоком m=8 и n=8.

На фиг.5 показана схема, поясняющая конкретный пример генерирования выходного различия ΔY_i F-функции путем выполнения линейного преобразования с квадратной матрицей РМР.

На фиг.6 показана схема, поясняющая одновременное сокращение различий на пяти этапах в шифре с 128-битным блоком при m=8 и n=8.

На фиг.7 показана схема, поясняющая определение одновременного сокращения различий для произвольного этапа в криптографической обработке общий-ключ-блок.

На фиг.8 показан пример квадратной матрицы РМР.

На фиг.9 показана схема, поясняющая пример установки квадратных матриц РМР в виде матриц линейного преобразования F-функций соответствующих циклов в криптографическом алгоритме общий-ключ-блок в соответствии с этим изобретением.

На фиг.10 показана блок-схема последовательности выполнения операций, поясняющая последовательность обработки установки квадратных матриц РМР в качестве матриц линейного преобразования F-функций соответствующих циклов в криптографическом алгоритме общий-ключ-блок, в соответствии с этим изобретением.

На фиг.11 показана блок-схема последовательности выполнения операций, поясняющая пример а1 обработки, состоящий в генерировании квадратных матриц РМР, которые реализуют улучшенную устойчивость к атакам дифференциального криптоанализа, в качестве методики генерирования квадратных матриц РМР, которые представляют собой матрицы линейного преобразования, предназначенные для установки в F-функциях соответствующих циклов.

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

На фиг.13 показана блок-схема последовательности выполнения операций, поясняющая пример а3 обработки, состоящий в генерировании квадратных матриц РМР, которые реализуют улучшенную устойчивость к атакам дифференциального криптоанализа, в качестве методики генерирования квадратных матриц РМР, которыепредставляют собой матрицы линейного преобразования, предназначенные для установки в F-функциях соответствующих циклов.

На фиг.14 показана схема, поясняющая конкретную методику примера а3 обработки, состоящую в генерировании квадратных матриц РМР, которые представляют собой матрицы линейного преобразования, предназначенные для установки в F-функциях соответствующих циклов.

На фиг.15 показана блок-схема последовательности выполнения операций, поясняющая пример b1 обработки, состоящей в генерировании квадратных матриц РМР, которые реализуют улучшенную устойчивость к атакам линейного криптоанализа, в качестве методики генерирования квадратных матриц РМР, которые представляют собой матрицы линейного преобразования, для установки в F-функциях соответствующих циклов.

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

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

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

Подробное описание изобретения

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

1. Обработка дифференциального анализа в криптографическом алгоритме общий-ключ-блок.

2. Обработка линейного анализа в криптографическом алгоритме общий-ключ-блок.

3. Криптографический алгоритм на основе этого изобретения:

(3-а) Пример генерирования квадратных матриц РМР, которые реализуют улучшенную устойчивость к атакам дифференциального криптоанализа, и установки их в F-функциях,

(3-b) Пример генерирования квадратных матриц РМР, которые реализуют улучшенную устойчивость к атакам линейного криптоанализа, и установки их в F-функциях,

(3-е) Пример генерирования квадратных матриц РМР, которые реализуют улучшенную устойчивость к атакам дифференциального криптоанализа и атакам линейного криптоанализа, и установки их в F-функциях.

[1. Обработка дифференциального анализа в криптографическом алгоритме общий-ключ-блок]

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

Алгоритм криптографической обработки общий-ключ-блок, в основном, может быть разделен на блок функции цикла, предназначенный для выполнения преобразования входных данных, и блок планирования ключа, предназначенный для генерирования ключа, который следует применять в каждом цикле части функции цикла. Ключ (подключ), применяемый в каждом цикле функции цикла, генерируют с помощью блока планирования ключа, в который вводят один мастер ключ (главный ключ), на основе него и используют в каждом цикле. Среди типичных систем такой криптографической системы с общим ключом можно назвать систему DES (Стандарт шифрования данных), используемую, как Федеральная стандартная система США.

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

Структура Фейстеля имеет конфигурацию преобразования открытого текста в зашифрованный текст путем простого повторения функции преобразования. Длина открытого текста установлена равной 2 mn(2×m×n) битов. Здесь m и n представляют целые числа. Вначале открытый текст размером 2mn битов разделяют на две части входных данных, P_L (Открытая-левая) 101 из mn битов и P_R (Открытая-правая) 102, содержащие mn битов, и их используют как входные значения.

Структуру Фейстеля выражают путем повторения основной структуры, и функцию преобразования данных, включаемую в каждом цикле, называют F-функцией 120. На фиг.1 показан пример конфигурации, состоящей из F-функций (функций цикла) 120, повторяемых для r-этапов.

Например, в первом цикле входные данные Х размером mn битов и ключ K₁ 103 цикла размером mn битов, подаваемый из блока генерирования ключа (не показан на чертеже), вводят в F-функцию 120, на выходе которой получают данные Y размером mn битов после выполнения в ней преобразования данных. Блок 104 исключающее ИЛИ выполняет операцию исключающее ИЛИ в отношении выходных данных и других частей входных данных, полученных на предыдущем этапе, и выводит результат операции размером mn битов в следующую функцию цикла. Криптографическую обработку заканчивают путем применения этой обработки, то есть F-функции, повторно в течение заданного количества (r) циклов, и выводят разделенные данные CL (Зашифрованные левые) и данные CR (Зашифрованные правые) в виде зашифрованного текста. Приведенная выше конфигурация приводит к тому, что для выполнения декодирования с использованием структуры Фейстеля необходимо только выполнить в обратном порядке последовательность ввода ключей цикла, которые не нужны для конфигурации обратной функции.

Структура F-функции 120, установленная как функция каждого цикла, будет описана со ссылкой на фиг.2. На фиг.2А показана схема, представляющая вход и выход F-функции 120 в одном цикле. На фиг.2В показана схема, подробно представляющая структуру F-функции 120. F-функция 120 имеет так называемую структуру SPN-типа, состоящую из уровня нелинейного преобразования и уровня линейного преобразования, соединенных вместе, как показано на фиг.2В.

F-функция 120 SPN-типа имеет множество S-блоков 121, предназначенных для выполнения обработки нелинейного преобразования, как показано на фиг.2В. Операцию исключающее ИЛИ выполняют в отношении входной величины Х размером mn бит из предыдущего этапа блока функции цикла, вместе с ключом K_i цикла, вводимым из блока планирования ключа, и ее вывод подают во множество (m) S-блоков, каждый из которых выполняет обработку нелинейного преобразования для n битов. Каждый из S-блоков выполняет обработку нелинейного преобразования, в которой применяют, например, таблицу преобразования.

Выходное значение Z размером mn битов, которое представляет собой выходные данные S-блока 121, вводят в блок 122 линейного преобразования 122 для выполнения обработки линейного преобразования, в ходе которой выполняют обработку линейного преобразования, например, обработку смены положений битов и т.д., и выводят выходное значение Y размером mn битов. Выходное значение Y вместе с входными данными из предыдущего этапа подвергают операции исключающее ИЛИ, и ее результат назначают входному значению F-функции следующего цикла.

В F-функции 120, показанной на фиг.2, битовая длина входа-выхода равна m×n (m, n - целые числа), уровень нелинейного преобразования имеет конфигурацию, в которой m S-блоков 121, каждый из которых выполняет функцию уровня нелинейного преобразования, вход и выход которых представляют n битов, расположенных параллельно, и блок 122 линейного преобразования, в качестве уровня линейного преобразования, выполняет обработку линейного преобразования на основе m-ой квадратной матрицы, которая имеет элементы в поле расширения GF (2ⁿ), определенные по n-ному несокращаемому полиному, как его элементы.

На фиг.3 показан пример квадратной матрицы, применяемой при обработке линейного преобразования в блоке 122 линейного преобразования. Квадратная матрица 125, показанная на фиг.3, представляет собой пример n=8 и m=8. Линейное преобразование выполняют для данных m n битов Z [1], Z [2]…,Z [m], выводимых из блока нелинейного преобразования (S-блок 121), в котором применяют заданную квадратную матрицу 125, и определяют Y [1], Y [2]…,Y [m] как выход F-функции (функции цикла). Следует отметить, что линейную операцию элементов матрицы каждых данных выполняют для заданного поля расширения GF (2ⁿ), равного 2.

Поскольку в используемом до настоящего времени шифре типа Фейстеля используют один и тот же уровень линейного преобразования для F-функций на всех этапах, он имеет свойство, состоящее в том, что множество различий сокращают одновременно, когда распространяют различия. Как было описано в параграфе "Уровень техники", в качестве типичной методики криптоанализа известен дифференциальный анализ (или методика дешифрования различий), в котором прикладной ключ для каждой функции цикла анализируют путем анализа множества входных данных (открытого текста) и ее выходных данных (зашифрованного текста). При обычной криптографической обработке общий-ключ-блок, такой как криптографический алгоритм DES, поскольку обработка (матрица преобразования), применяемая в блоку 122 линейного преобразования F-функции, 120 установлена эквивалентной в цикле на каждом этапе, легко выполнить дифференциальный анализ и в результате легко выполнить анализ ключа.

Пример, в котором множество различий сокращают одновременно во время распространения различий, поясняется со ссылкой на фиг.4. В этом описании, при выражении различий, различие обозначают путем добавления символа Δ (дельта).

На фиг.4 показана схема, поясняющая одновременное сокращение различий в трех этапах в блоке шифра 128-битов (m=8 и n=8). Следует отметить, что на чертеже данные размером 64 бита должны быть разделены побайтно, причем каждый из них должен быть выражен как вектор, и каждый элемент должен быть представлен в виде шестнадцатеричного числа.

Одновременное сокращение различий F-функции, имеющей структуру из трех этапов, происходит, например, на основе механизма установки следующих состояний 1-4 данных. Состояния данных, генерируемые механизмом, который поясняется ниже, представляют собой состояния данных, которые могут быть сгенерированы путем установки множества входных данных различия, то есть они могут быть сгенерированы при анализе ключа (ключа цикла) в так называемом дифференциальном анализе.

(Состояние 1)

Предположим, что левая половина входного различия для цикла i состоит из входных различий, всех равных нулю (ΔХ_i-1=(00, 00, 00, 00, 00, 00, 00, 00)), и правая его половина состоит из входных различий, всех равных нулю, за исключением входа только в один S-блок

(ΔХ_i-1=(34, 00, 00, 00, 00, 00, 00, 00)). Это состояние данных показывает, что путем установки множества различных входных данных, такое состояние данных может быть получено в цикле i.

Восемь элементов в ΔX_i=(34, 00, 00, 00, 00, 00, 00, 00) соответствуют входным различиям соответствующих S-блоков (m=8), структурированных в F-функции. Различие (34) вводят в первый S-блок ((S1) по фиг.4), и (00) представляют собой входные различия в блоках со второго по восьмой.

Здесь выходное различие S-блока, имеющего входное различие, равное нулю (00), равно нулю (00). Что касается данных различия, S-блок, имеющий входное различие, равное нулю (00), не создает какой-либо эффект и, соответственно, называется S-блоком, который не является активным, то есть неактивным S-блоком. С другой стороны, S-блок, имеющий входное различие, не равное нулю (в примере по фиг.4, различие =34), генерирует результат нелинейного преобразования, соответствующий входному различию, не равному нулю и, соответственно, называется активным S-блоком.

В примере, показанном на фиг.4, генерируют выходное различие (b7) одного активного S-блока (S1), для которого вводят входное различие (34), не равное нулю. Другие неактивные S-блоки S2-S8 генерируют выходные различия (00) на основе их входных различий (00), равных нулю, соответственно, предоставляемых им, как входы различий в блоке линейного преобразования.

(Состояние 2)

Выходное различие S-блока, имеющего входное различие, не равное нулю, для цикла i (ниже называется активным S-блоком) рассеивают в уровне линейного преобразования и выводят из F-функции (выходное значение =ΔY_i), которое становится входным различием ΔX_i+1 для следующего цикла, в том виде, как оно есть.

Линейное преобразование в примере по фиг.4 выполняют таким образом, что линейное преобразование с использованием определенной конкретной квадратной матрицы 125, например, как показано на фиг.5, общей в F-функциях в соответствующих циклах, выполняют для вывода различия ΔY_i=(98, с4, b4, d3, ас, 72, 32), в качестве выходного различия F-функции цикла i. Как можно понять по структуре линейного преобразования, показанной на фиг.5, выходное различие ΔY_i=(98, с4, b4, d3, ас, 72, 32) определено как значение, зависящее только от выходного элемента Z [1]=b7 одного активного S-блока(S1).

Такие значения ΔY_i=(98, с4, b4, d3, ас, 72, 32), используемые в качестве выходных различий F-функции в этом цикле i вместе с входными различиями, всеми равными нулю (ΔХ_i-1=(00, 00, 00, 00, 00, 00, 00, 00)), подвергают операции исключающее ИЛИ (XOR) в блоке 131 исключающее ИЛИ, показанном на фиг.4, и результат операции задают как ΔX_i+1 для следующего цикла i+1.

Поскольку результаты операций исключающее ИЛИ (XOR) в отношении ΔY_i=(98, с4, b4, d3, ас, 72, 32) в качестве выходных различий функции F цикла i и входных различий, всех равных нулю ΔХ_i-1=(00, 00, 00, 00, 00, 00, 00, 00), представляют собой ΔY_i, входные различия ΔХ_i+1 для следующего цикла i+1 принимают равными ΔY_i=(98, с4, b4, d3, ас, 72, 32).

(Состояние 3)

Выходное различие ΔY_i+1 F-функции цикла i+1 имеет ненулевое значение только в положении активного S-блока в цикле i. Такое состояние данных обозначает, что такое состояние данных может быть получено путем установки множества входных данных различий.

То есть ΔY_i+1=(ad, 00, 00, 00, 00, 00, 00, 00), и выходное различие ΔY_i+1 имеет ненулевое значение только в положении S-блока (первого S-блока (S1)), который имеет ненулевое значение различия, аналогично циклу i. В частности, при этом понятно, что ad≠00.

(Состояние 4)

В случае, когда выходное различие активного S-блока (S1) в цикле i+2 соответствует выходному различию активного S-блока (S1) в цикле i, как показано на фиг.4, выходное различие активного S-блока (S1) в цикле i+2 становится равным b7 и соответствует выходному различию (b7) активного S-блока (S1). Это состояние данных показывает, что такое состояние данных может быть получено путем установки множества входных данных различий.

Когда возникает такое состояние данных, выходное различие ΔY_i+2=(98, с4, b4, d3, ас, 72, 32) F-функции цикла i+2 будет соответствовать выходному различию ΔY_i=(98, с4, b4, d3, ас, 72, 32), которое представляет собой F-функцию цикла i, представляющую собой предыдущий цикл через один цикл.

В качестве результата блок 133 исключающее ИЛИ будет выполнять операцию исключающее ИЛИ для ΔX_i+1=ΔY_i=(98, с4, b4, d3, ас, 72, 32) и ΔY_i+2=(98, с4, b4, d3, ас, 72, 32), при этом они оба представляют одно и то же значение и выводят значения, все равные нулю, в результате операции исключающее ИЛИ.

В результате левое входное различие ΔХ_i+33 из предыдущего этапа (цикла i+2), которое приводит к получению выходного различия для следующего этапа (цикла i+3) становится равным ΔХ_i+3=(00, 00, 00, 00, 00, 00, 00,00).

Левый вход ΔХ_i+3=(00, 00, 00, 00, 00, 00, 00, 00) для этого цикла i+3 состоит из всех нулей, так же, как и у левого входного разли