Путаница и диффузия

В криптографии выявленными путаница и диффузия являются двумя свойствами надежного шифра, Клодом Шенноном в его секретном докладе 1945 года «Математическая теория криптографии» . Эти свойства, если они присутствуют, вместе мешают применению статистики и других методов криптоанализа .

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

Определение

Путаница

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

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

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

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

В сетях подстановки-перестановки путаницу создают блоки подстановки .

Диффузия

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

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

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

Теория

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

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

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

Практическое применение

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

Путаница неизбежно влечет за собой некоторую диффузию, поэтому конструкция с очень широким входным S-box может обеспечить необходимые диффузионные свойства, но будет очень дорогостоящим в реализации. Поэтому практические шифры используют относительно небольшие S-блоки, работающие с небольшими группами битов («пачками»). ). Например, конструкция AES имеет 8-битные S-блоки, Serpent — 4-битные, BaseKing и 3-way — 3-битные. Маленькие S-блоки практически не обеспечивают диффузии, поэтому ресурсы тратятся на более простые диффузионные преобразования. Например, стратегия широкого следа, популяризированная дизайном Рейндала , включает в себя линейное преобразование смешивания, которое обеспечивает высокую диффузию, хотя доказательства безопасности не зависят от линейности диффузионного слоя.

Одна из наиболее исследованных структур шифра использует сеть подстановки-перестановки (SPN), где каждый раунд включает в себя слой локальных нелинейных перестановок ( S-блоков ) для путаницы и линейное диффузионное преобразование (обычно умножение на матрицу над конечным полем ). . Современные блочные шифры в основном следуют модели слоя путаницы/диффузионного слоя, при этом эффективность диффузионного слоя оценивается с использованием так называемого числа ветвей , числового параметра, который может достигать значения $s+1$ для s входных пакетов для идеального диффузионного преобразования. Поскольку преобразования, которые имеют большое число ветвей (и, следовательно, требуют большого количества пакетов в качестве входных данных), являются дорогостоящими в реализации, диффузный уровень иногда (например, в AES) состоит из двух подуровней, «локальной диффузии», которая обрабатывает подмножества пакеты в стиле каменщика (каждое подмножество преобразуется независимо) и «дисперсия», которая делает биты, которые были «близкими» (внутри одного подмножества пакетов), становиться «отдаленными» (распространяются на разные подмножества и, таким образом, локально распределяются внутри этих пакетов). новые подмножества в следующем раунде).

Анализ АЭС

Усовершенствованный стандарт шифрования (AES) отличается как превосходной путаницей, так и распространением. Его таблицы поиска путаницы очень нелинейны и хорошо справляются с разрушением шаблонов. На этапе диффузии каждая часть входных данных распределяется по всем частям выходных данных: изменение одного бита входных данных приводит к изменению в среднем половины выходных битов. И путаница, и диффузия повторяются несколько раз для каждого входа, чтобы увеличить количество скремблирования. Секретный ключ смешивается на каждом этапе, поэтому злоумышленник не может заранее рассчитать, что делает шифр.

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

См. также

• Алгоритмическая теория информации
• Лавинный эффект
• Сеть замены-перестановки

Источники

• Клод Э. Шеннон, «Математическая теория криптографии» , Техническая записка системы Bell MM 45-110-02, 1 сентября 1945 г.
• Клод Э. Шеннон, « Теория связи секретных систем », Технический журнал Bell System , том. 28–4, страницы 656–715, 1949. [1] Архивировано 5 июня 2007 г. в Wayback Machine.
• Уэйд Трапп и Лоуренс К. Вашингтон, Введение в криптографию с теорией кодирования. Второе издание. Пирсон Прентис Холл, 2006.
• Ли, Чаоюнь; Ван, Цинджу (2017). «Проектирование легких линейных диффузионных слоев из матриц, близких к МДС» (PDF) . Транзакции IACR по симметричной криптологии . 1 : 129–155. дои : 10.13154/tosc.v2017.i1.129-155 .
• Саджади, Махди; Дахилалян, Мохаммед; Мала, Хамид; Сепердад, Пуян (2012). «Рекурсивные диффузионные уровни для блочных шифров и хэш-функций». Быстрое программное шифрование (PDF) . Шпрингер Берлин Гейдельберг. стр. 385–401. дои : 10.1007/978-3-642-34047-5_22 . eISSN   1611-3349 . ISSN   0302-9743 .
• Дэмен, Джоан; Реймен, Винсент (9 марта 2013 г.). Конструкция Rijndael: AES — расширенный стандарт шифрования (PDF) . Springer Science & Business Media. ISBN  978-3-662-04722-4 . OCLC   1259405449 .
• Штамп, Марк; Лоу, Ричард М. (15 июня 2007 г.). Прикладной криптоанализ: взлом шифров в реальном мире . Джон Уайли и сыновья. ISBN  978-0-470-14876-1 . OCLC   1044324461 .
• Лю, Юньвэнь; Реймен, Винсент; Леандер, Грегор (20 января 2018 г.). «Нелинейные диффузионные слои» (PDF) . Проекты, коды и криптография . 86 (11): 2469–2484. дои : 10.1007/s10623-018-0458-5 . eISSN   1573-7586 . ISSN   0925-1022 .