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