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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

К широко известным блочным криптографическим алгоритмам с симметричным ключом относятся DES (стандарт шифрования данных (Data Encryption Standard)), применявшийся в США раньше, и AES (улучшенный стандарт шифрования (Advanced Encryption Standard)), используемый в США сегодня. Сегодня предлагаются и другие разнообразные способы блочной криптографии с симметричным ключом, а стандарт CLEFIA, предложенный корпорацией Sony в 2007, также является одним из способов блочной криптографии с симметричным ключом.

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

В качестве конкретной структуры, реализующей такой алгоритм, известна структура, многократно вычисляющая раундовую функцию и содержащая модуль линейной трансформации и модуль нелинейной трансформации. Типовой пример такой структуры содержит структуру Файстеля (Feistel) и обобщенную структуру Файстеля. Эти структуры - структура Файстеля и обобщенная структура Файстеля - имеют каждая структуру, преобразующую открытый текст в зашифрованный текст посредством простого многократного применения раундовой функции, включающей F-функции в качестве функций преобразования данных. В каждой F-функции осуществляют линейную трансформацию и нелинейную трансформацию. Непатентный документ 1 и непатентный документ 2 представляют собой примеры документов, рассматривающих криптографическую обработку данных с использованием структуры Файстеля.

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

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

Список литературы

Непатентные документы

Непатентный документ 1: К. Найберг, «Обобщенные сети Файстеля» (K. Nyberg, "Generalized Feistel networks", ASIACRYPT 96, SpringerVerlag, 1996, pp.91-104).

Непатентный документ 2: Юлянь Жень, Цутому Мацумото, Нидеки Имаи: О построении доказуемо надежных блочных шифров без опоры на недоказанные гипотезы (Yuliang Zheng, Tsutomu Matsumoto, Hideki Imai: On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. CRYPTO 1989:461-480).

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

Проблемы, которые должно решать изобретение

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

Решение проблем

Первый аспект настоящего изобретения состоит в устройстве для криптографической обработки данных, которое содержит

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

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

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

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

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

(1) Последовательности данных на входной стороне F-функции неизменным способом распределяют в последовательности данных на стороне XOR (функции «исключающее ИЛИ») в составе следующей раундовой функции,

(2) Последовательности данных на стороне функции «исключающее ИЛИ» (XOR) неизменным способом распределяют в последовательности данных на входной стороне F-функции в составе следующей раундовой функции, и

(3) Каждую единицу из последовательности данных, разбитой на сегменты d/2, распределяют в последовательность d/2 данных следующей раундовой функции без наложений.

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

Далее, в одном из вариантов устройства для криптографической обработки данных согласно настоящему изобретению указанный модуль криптографической обработки выполняет операцию, в процессе которой генерируют d×(d/2) сегментов повторно разбитых данных путем повторного разбиения n/d-битовых данных в каждой из d линеек, имеющей выходные данные раундовых вычислений на сегменты d/2 данных, затем сегменты d/2 повторно разбитых данных, выбранных из разных линеек из совокупности d линеек, соответствующих числу d разбиения рекомбинируют для реконструкции d сегментов n/d-битовых данных, отличных от выходных данных раундовых вычислений предыдущего этапа, и задают реконструированные данные в качестве входных данных для раундовых вычислений следующего этапа.

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

(Условие 1) все входные биты включены в относительное выражение, и

(Условие 2) все входные биты прошли через раундовую функцию по меньшей мере однажды.

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

Далее, в одном из вариантов устройства для криптографической обработки данных согласно настоящему изобретению соединительная структура, определяющая соотношение вход-выход между выходными данными раундовых вычислений предыдущего этапа и повторно разбитыми данными раундовых вычислений следующего этапа, представляет собой соединительную структуру, выбранную из совокупности соединительных структур, имеющих (d/2) сегментов 2n/d-битовых данных в качестве единиц, являющихся данными, генерируемыми путем соединения d×(d/2) сегментов повторно разбитых данных, полученных посредством операции повторного разбиения n/d-битовых данных в линейках, имеющих выходные данные раундовых вычислений.

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

Далее, в одном из вариантов устройства для криптографической обработки данных согласно настоящему изобретению операция реконструкции повторно разбитых данных от соответствующих раундовых вычислений в модуле криптографической обработки данных включает: распределение повторно разбитых данных последовательностей на входной стороне раундовой функции предыдущего этапа в последовательности на стороне функции «исключающее ИЛИ» (XOR) следующего этапа в соответствии с заданным правилом; и распределение повторно разбитых данных последовательностей на стороне функции «исключающее ИЛИ» (XOR) предыдущего этапа в последовательности на входной стороне раундовой функции следующего этапа в соответствии с заданным правилом.

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

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

этот способ криптографической обработки данных включает

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

здесь этап криптографической обработки данных включает: ввод n/d-битовых данных, полученных путем разбиения n-битовых входных данных согласно числу d разбиения, в соответствующие линейки и многократное выполнение вычислений в качестве раундовых вычислений, включая операцию преобразования данных с использованием раундовой функции, и

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

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

в соответствии с этой программой модуль криптографической обработки данных выполняет

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

здесь этап криптографической обработки данных включает: ввод n/d-битовых данных, полученных путем разбиения n-битовых входных данных согласно числу d разбиения, в соответствующие линейки и многократное выполнение вычислений в качестве раундовых вычислений, включая операцию преобразования данных с использованием раундовой функции, и

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

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

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

Преимущества изобретения

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

В частности, модуль криптографической обработки данных разбивает и вводит биты, составляющие данные, подлежащие обработке, в линейки, и многократно осуществляет операцию преобразования данных с использованием раундовых функций применительно к данным в соответствующих линейках. Этот модуль криптографической обработки данных вводит n/d-битовые данные, полученные путем разбиения n-битовых данных в качестве входных данных в соответствии с числом d разбиения, в каждую линейку и многократно выполняет раундовые вычисления, включая операцию преобразования данных с использованием раундовых функций. Указанные n/d-битовые данные в каждой линейке, имеющей выходные данные раундовых вычислений, разделяют на d/2 сегментов данных и разделенные данные рекомбинируют для реконструкции d сегментов n/d-битовых данных, отличных от выходных данных раундовых вычислений предыдущего этапа. Реконструированные данные задают в качестве входных данных для раундовых вычислений следующего этапа. В такой структуре можно реализовать криптографическую обработку с улучшенными диффузионными свойствами и высоким уровнем защищенности.

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

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

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

Фиг.3 представляет схему для пояснения соотношения между модулем планирования ключей и модулем шифрования данных.

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

Фиг.5 представляет схему для пояснения примера раундовой функции, имеющей структуру SPN.

Фиг.6 представляет схему для пояснения примера раундовой функции, имеющей структуру Файстеля.

Фиг.7 представляет схему для пояснения примера расширенной структуры Файстеля.

Фиг.8 представляет схему для пояснения примера расширенной структуры Файстеля.

Фиг.9 представляет схему для пояснения примера структуры модуля нелинейной трансформационной обработки данных.

Фиг.10 представляет схему для пояснения примера структуры модуля линейной трансформационной обработки данных.

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

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

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

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

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

Фиг.16 представляет схему для пояснения обычной обобщенной структуры Файстеля в случае, когда число d равно 6.

Фиг.17 представляет схему для пояснения примера путей, которыми достигается полное диффузионное состояние в обычной обобщенной структуре Файстеля в случае, когда число d равно 6.

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

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

Фиг.20 представляет схему для пояснения структуры криптографической обработки данных в качестве варианта настоящего изобретения.

Фиг.21 представляет схему для пояснения примера случая, где число d равно 4, в качестве варианта настоящего изобретения.

Фиг.22 показывает пример путей, которыми достигается полное диффузионное состояние с использованием предлагаемого способа для случая, где число d равно 4.

Фиг.23 представляет схему для пояснения примера случая, где число d равно 6, в качестве варианта настоящего изобретения.

Фиг.24 показывает пример путей, которыми достигается полное диффузионное состояние с использованием предлагаемого способа для случая, где число d равно 6.

Фиг.25 представляет схему для пояснения примера структуры, в которой каждый сегмент n/d-битовых данных разделен на 2 в случае, когда число d равно 6.

Фиг.26 представляет диаграмму, показывающую часть соотношения между числом d разбиения n-битовых входных данных, числом р разбиения каждого сегмента n/d-битовых данных и числом раундов для достижения полного диффузионного состояния.

Фиг.27 представляет схему для пояснения примера структуры, в которой последовательности данных на входной стороне F-функции и последовательности данных на стороне функции «исключающее ИЛИ» (XOR) разбиты способами, отличными один от другого.

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

Фиг.29 представляет схему для пояснения более эффективного способа распределения данных.

Фиг.30 представляет схему для пояснения более эффективного способа распределения данных.

Фиг.31 представляет схему для пояснения более эффективного способа распределения данных.

Фиг.32 представляет схему для пояснения инволюционных свойств структуры Файстеля.

Фиг.33 представляет схему для пояснения инволюционных свойств структуры Файстеля.

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

Фиг.35 представляет схему для пояснения операций с целью достижения инволюционных свойств.

Фиг.36 представляет схему для пояснения примера структуры, обладающей инволюционными свойствами, в имеющей 4 линейки (d=4) структуре.

Фиг.37 представляет схему для пояснения примера структуры, обладающей инволюционными свойствами, в имеющей 6 линеек (d=6) структуре.

Фиг.38 представляет схему для пояснения примера структуры, обладающей инволюционными свойствами.

Фиг.39 представляет схему для пояснения примера структуры, обладающей инволюционными свойствами.

Фиг.40 представляет схему для пояснения примера структуры модуля 700 интегральных схем в качестве устройства для криптографической обработки данных.

Способы осуществления изобретения

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

1. Очерк блочной криптографии с симметричным ключом

2. Очерк диффузионных свойств

(2-1) Описание диффузионных свойств

(2-2) Пример обычной структуры с учетом диффузионных свойств

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

4. Пример структуры с более эффективным распределением данных

5. Пример структуры, обладающей инволюционными свойствами

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

7. Краткая характеристика структур согласно настоящему изобретению

[1. Очерк блочной криптографии с симметричным ключом]

Сначала будет вкратце описана блочная криптография с симметричным ключом.

(1-1. Блочная криптография с симметричным ключом)

Блочная криптография с симметричным ключом (далее именуемая «блочное шифрование») определена следующим образом.

В системе блочного шифрования получают в качестве входных сигналов открытый текст Р и ключ K и передают на выход зашифрованный текст С. Длина открытого текста и зашифрованного текста в битах называется размером блока и здесь обозначена n. Хотя величина n может быть равна любому целому числу, обычно эту величину n однозначно определяют для каждого алгоритма блочного шифрования. Блочное шифрование с использованием n в качестве длины блока может также называться «n-битовое блочное шифрование».

Длина ключа в битах обозначена буквой k. Ключ может иметь любую целочисленную величину. Каждый блочный криптографический алгоритм с симметричным ключом совместим с одним или несколькими размерами ключей. Например, некий алгоритм блочного шифрования А имеет размер блока, равный n=128, и может быть совместим с ключами размером k=128, 192 и 256.

Открытый текст Р: n бит

Зашифрованный текст С: n бит

Ключ K: k бит

На фиг.1 представлена схема n-битового алгоритма Е блочного шифрования с симметричным ключом, совместимого с длиной ключа, равной k бит.

Алгоритм D дешифровки, совместимый с алгоритмом Е блочного шифрования, может быть определен обратной функцией Е^-1 относительно алгоритма Е шифрования. Зашифрованный текст С и ключ K в этом случае принимают в качестве входных сигналов, а открытый текст Р передают на выход. На фиг.2 представлена схема, показывающая алгоритм D дешифровки, совместимый с алгоритмом Е шифрования, изображенным на фиг.1.

(1-2. Внутренняя структура)

Блочное шифрование может быть разделено между двумя модулями.

Один модуль - "модуль планирования ключей", который получает на вход ключ K и передает на выход расширенный ключ K′ (длина k′ в битах), образованный путем увеличения длины исходного ключа в битах с заданным шагом, а другой модуль - "модуль шифрования данных", который принимает на входы открытый текст Р и расширенный ключ K′ от модуля планирования ключей, преобразует данные и передает на выход зашифрованный текст С.

Соотношение между этими двумя модулями показано на фиг.3.

(1-3. Модуль шифрования данных)

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

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

(1-4. Раундовые функции)

Раундовые функции могут принимать разнообразные формы в зависимости от алгоритмов блочного шифрования. Раундовые функции можно классифицировать на основе структур, используемых соответствующими алгоритмами шифрования. Примерами типовых структур являются структура SPN (подстановочно-перестановочная сеть (Substitution-Permutation Network)), структура Файстеля и расширенная структура Файстеля.

(a) Раундовая функция со структурой SPN

Эта структура выполняет операцию «исключающее ИЛИ» с раундовым ключом, нелинейную трансформацию и линейную трансформацию применительно ко всем n-битовым входным данным. Какой-либо конкретный порядок соответствующих операций не задан. На фиг.5 представлен пример раундовой функции, имеющей структуру SPN.

(b) Структура Файстеля

В такой системе n-битовые входные данные разбивают на два сегмента данных по n/2-бит в каждом. Один из этих сегментов данных и раундовый ключ подают на входы функции (F-функция), а над выходными данными этой функции и другим из указанных сегментов данных выполнят операцию «исключающее ИЛИ». После этого правый и левый сегменты данных меняют местами для формирования выходных данных. Внутренняя структура F-функции может быть различной, но обычно эта структура реализует сочетание операции «исключающее ИЛИ» с использованием данных раундового ключа, нелинейной операции и линейной трансформации, как и структура SPN. На фиг.6 представлен пример раундовой функции, имеющей структуру Файстеля.

(c) Расширенная структура Файстеля

Расширенная структура Файстеля отличается от обычной структуры Файстеля в том, что в расширенной структуре число разбиения данных может быть равно 3 или более вместо 2. Если число разбиения данных обозначить буквой d, величина этого числа d может определять различные расширенные структуры Файстеля. Поскольку размер входных/выходных данных для F-функции становится относительно меньше, такая структура считается подходящей для реализации с малой размерностью. На фиг.7 представлен пример расширенной структуры Файстеля для случая числа d, равного 4, и двух F-функций, используемых параллельно в одном раунде. На фиг.8 представлен пример расширенной структуры Файстеля для случая числа d, равного 8, и одной F-функции, используемой в одном раунде.

(1-5. Модуль обработки данных с нелинейной трансформацией)

Модуль обработки данных с нелинейной трансформацией отличается тенденцией к росту стоимости реализации по мере увеличения размера данных, которые должны поступать на вход этого модуля. Во избежание этого целевые данные во многих случаях разбивают на две или более единиц и осуществляют нелинейную трансформацию применительно к каждой из этих единиц. Например, когда входные данные имеют размер ms бит, эти входные данные разбивают на m сегментов s-битовых данных и осуществляют нелинейную трансформацию с размерностью s бит и на входе, и на выходе применительно к каждому из m сегментов s-битовых данных. Такие s-битовые нелинейные трансформации здесь именуются S-ячейки. Пример показан на фиг.9.

(1-6. Модуль обработки данных с линейной трансформацией)

С точки зрения характеристик модуль обработки данных с линейной трансформацией может быть определен в виде матрицы. Элементы этой матрицы могут быть обычно выражены в различных формах, таких как элементы поля Галуа GF(2⁸) или элементы поля Галуа GF(2). На фиг.10 представлен пример модуля обработки данных с линейной трансформацией, получающего ms-битовые входные данные и передающего ms-битовые выходные данные и определенного матрицей размером m×m в поле Галуа GF(2^s).

[2. Очерк диффузионных свойств]

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

(2-1) Описание диффузионных свойств

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

Далее определены термины «диффузионное состояние» («diffusion state»), «полное диффузионное состояние» («full diffusion state») и «число раундов для достижения полного диффузионного состояния» («number of full diffusion rounds»).

Если выходной бит записан в виде некоторого выражения относительно входных битов и если это относительное выражение удовлетворяет приведенным ниже условиям, состояние выходного бита определено как «диффузионное состояние».

(Условие 1) В это относительное выражение входят все входные биты.

(Условие 2) Все входные биты прошли через раундовую функцию (F-функцию) по меньшей мере однажды.

Далее, состояние, в котором все выходные биты находятся в диффузионном состоянии, определено как «полное диффузионное состояние».

Минимальное число раундов (число повторений), необходимое для достижения полного диффузионного состояния, определено как «число раундов для достижения полного диффузионного состояния».

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

Как видно на фиг.12, n/2-битовые данные X i + 1 1 , X i + 2 1 и X i + 3 1 на левых сторонах выходов i-го, (i+1)-го и (i+2)-го раундов (или на левых сторонах (i+1)-го, (i+2)-го и (i+3)-го входов) и n/2-битовые данные X i + 1 2 , X i + 2 2 и X i + 3 2 на правых сторонах выходов i-го, (i+1)-го и (i+2)-го раундов (или на правых сторонах (i+1)-го, (i+2)-го и (i+3)-го входов) могут быть каждые выражены следующим образом с использованием входных данных X i 1 и X i 2 i-го раунда и раундовых ключей R K i 1 , R K i 2 и R K i 3 .

В приведенном выше выражении F(K, X) обозначает данные, получаемые посредством трансформации данных Х с применением F-функции, использующей параметр K, а (+) обозначает операцию «исключающее ИЛИ» над каждым битом.

Результат X i + 1 1 , выражения с входными данными X i 1 и X i 2 не находится в диффузионном состоянии, поскольку данные X i 2 еще не проходили через F-функцию. Данные X i + 2 1 выражены через входные данные X i 1 и X i 2 , и эти входные данные поданы на входы F-функции. Соответственно, можно сказать, что данные X i + 2 1 находятся в диффузионном с