Путаница и расплывчатость - Confusion and diffusion

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

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

Определение

Путаница

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

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

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

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

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

Диффузия

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

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

В сетях замещения-перестановки распространение обеспечивается блоками перестановок .

Теория

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

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

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

Применяется к шифрованию

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

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

Анализ AES

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

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

Смотрите также

использованная литература

Процитированные работы