В криптографии путаница и диффузия являются двумя свойствами работы надежного шифра , выявленными Клодом Шенноном в его секретном докладе 1945 года «Математическая теория криптографии ». [1] Эти свойства, если они присутствуют, вместе мешают применению статистики и других методов криптоанализа .
Путаница в симметричном шифре скрывает локальную корреляцию между входом ( открытый текст ) и выходом ( зашифрованный текст ) за счет изменения применения ключа к данным, тогда как диффузия скрывает статистику открытого текста, распространяя ее по большей области зашифрованного текста. [2] Хотя шифры могут быть только путаными ( шифр замены , одноразовый блокнот ) или только диффузионными ( транспозиционный шифр ), любой «разумный» блочный шифр использует как путаницу, так и диффузию. [2] Эти концепции также важны при разработке криптографических хэш-функций и генераторов псевдослучайных чисел , где декорреляция генерируемых значений является основной особенностью, диффузия (и ее лавинный эффект ) также применима к некриптографическим хеш-функциям .
Путаница означает, что каждая двоичная цифра (бит) зашифрованного текста должна зависеть от нескольких частей ключа, скрывая связи между ними. [3]
Свойство путаницы скрывает связь между зашифрованным текстом и ключом.
Это свойство затрудняет поиск ключа в зашифрованном тексте, и если изменить один бит ключа, это повлияет на вычисление большинства или всех битов в зашифрованном тексте.
Путаница увеличивает неоднозначность зашифрованного текста и используется как блочными, так и потоковыми шифрами.
В сетях подстановки-перестановки путаницу создают блоки подстановки . [4]
Диффузия означает, что если мы изменяем один бит открытого текста, то должна измениться около половины битов зашифрованного текста, и аналогичным образом, если мы изменяем один бит зашифрованного текста, то должна измениться около половины битов открытого текста. [5] Это эквивалентно ожиданию того, что схемы шифрования проявят лавинный эффект .
Целью диффузии является сокрытие статистической взаимосвязи между зашифрованным текстом и открытым текстом. Например, диффузия гарантирует, что любые шаблоны в открытом тексте, такие как избыточные биты, не будут видны в зашифрованном тексте. [3] Блочные шифры достигают этого за счет «распространения» информации о структуре открытого текста по строкам и столбцам шифра.
В сетях замены-перестановки диффузия обеспечивается ящиками перестановок (также известными как слой перестановок [4] ). В начале XXI века возник консенсус, согласно которому дизайнеры предпочитали, чтобы уровень перестановок состоял из линейных булевых функций , хотя можно использовать и нелинейные функции. [4]
В первоначальных определениях Шеннона путаница означает создание максимально сложной и запутанной связи между зашифрованным текстом и симметричным ключом ; Диффузия означает рассеивание статистической структуры открытого текста по большей части зашифрованного текста . Эта сложность обычно реализуется посредством четко определенной и повторяемой серии замен и перестановок . Под заменой понимается замена определенных компонентов (обычно битов) другими компонентами с соблюдением определенных правил. Перестановка относится к изменению порядка битов в соответствии с некоторым алгоритмом. Чтобы быть эффективным, любую неравномерность битов открытого текста необходимо перераспределить по гораздо более крупным структурам зашифрованного текста, что значительно затрудняет обнаружение этой неравномерности.
В частности, для случайно выбранного входного сигнала, если перевернуть i -й бит, то вероятность того, что j -й выходной бит изменится, должна составлять половину для любых i и j — это называется строгим лавинным критерием . В более общем смысле можно потребовать, чтобы переворот фиксированного набора битов менял каждый выходной бит с вероятностью, равной половине.
Одна из целей путаницы состоит в том, чтобы очень затруднить поиск ключа, даже если имеется большое количество пар открытый текст-зашифрованный текст, созданных с помощью одного и того же ключа. Следовательно, каждый бит зашифрованного текста должен зависеть от всего ключа, причем по-разному от разных бит ключа. В частности, изменение одного бита ключа должно полностью изменить зашифрованный текст.
В конструкции современного блочного шифра используются как путаница, так и диффузия, [2] при которой путаница изменяет данные между входными и выходными данными путем применения зависимого от ключа нелинейного преобразования (линейные вычисления легче обратить вспять и, следовательно, их легче взломать).
Путаница неизбежно приводит к некоторой диффузии, [6] поэтому конструкция с очень широким входным S-блоком может обеспечить необходимые диффузионные свойства, [ нужна ссылка ] , но будет очень дорогостоящей в реализации. Поэтому практические шифры используют относительно небольшие S-блоки, работающие с небольшими группами битов («пачками» [7] ). Например, в конструкции AES предусмотрены 8-битные S-блоки, Serpent — 4-битные, BaseKing и 3-way — 3-битные. [8] Маленькие S-блоки практически не обеспечивают диффузии, поэтому ресурсы тратятся на более простые диффузионные преобразования. [6] Например, стратегия широкого следа, популяризированная дизайном Рейндала , включает в себя преобразование линейного смешивания, которое обеспечивает высокую диффузию, [9] хотя доказательства безопасности не зависят от линейности диффузионного слоя. [10]
Одна из наиболее исследованных структур шифра использует сеть подстановки-перестановки (SPN), где каждый раунд включает в себя слой локальных нелинейных перестановок ( S-блоков ) для путаницы и линейное диффузионное преобразование (обычно умножение на матрицу над конечным полем ). . [11] Современные блочные шифры в основном следуют модели слоя путаницы/диффузионного слоя, при этом эффективность диффузионного слоя оценивается с использованием так называемого числа ветвей - числового параметра, который может достигать значения для s входных пакетов для идеального диффузионного преобразования. [12] Поскольку преобразования, которые имеют большое число ветвей (и, следовательно, требуют большого количества пакетов в качестве входных данных), являются дорогостоящими в реализации, диффузионный слой иногда (например, в AES) состоит из двух подуровней, «локальной диффузии», которые обрабатывает подмножества пакетов методом каменщика (каждое подмножество преобразуется независимо) и «дисперсию», которая делает биты, которые были «близкими» (внутри одного подмножества пакетов), становиться «удаленными» (распространяются на разные подмножества и, таким образом, локально распределяются внутри этих новых подмножеств в следующем раунде). [13]
Усовершенствованный стандарт шифрования (AES) отличается как превосходной путаницей, так и распространением. Его таблицы поиска путаницы очень нелинейны и хорошо справляются с разрушением шаблонов. [14] На этапе диффузии каждая часть входных данных распределяется по всем частям выходных данных: изменение одного бита входных данных приводит к изменению в среднем половины выходных битов. И путаница, и диффузия повторяются несколько раз для каждого входа, чтобы увеличить количество скремблирования. Секретный ключ смешивается на каждом этапе, поэтому злоумышленник не может заранее рассчитать, что делает шифр.
Ничего из этого не происходит, когда простая одноэтапная шифровка основана на ключе. Входные шаблоны будут передаваться прямо на выход. На первый взгляд это может показаться случайным, но анализ обнаружит очевидные закономерности, и шифр может быть взломан.
