Войти
В криптографии, путаница и диффузия - два свойства операции безопасного шифра, идентифицированные Клодом Шенноном в его секретном отчете 1945 года «Математическая теория криптографии». Эти свойства, при их наличии, препятствуют применению статистики и других методов криптоанализа.
. Эти концепции также важны при разработке надежных хэш-функций и генераторы псевдослучайных чисел, где декорреляция сгенерированных значений имеет первостепенное значение.
Путаница
Путаница означает, что каждая двоичная цифра (бит) зашифрованного текста должна зависеть от нескольких частей ключа, скрывая связи между ними.
Свойство путаницы скрывает связь между зашифрованным текстом и ключом.
Это свойство затрудняет поиск ключа из зашифрованного текста, и если один бит в ключе изменяется, это влияет на вычисление значений большинства или всех битов зашифрованного текста.
Путаница увеличивает неоднозначность зашифрованного текста, и он используется как блочными, так и потоковыми шифрами.
Распространение
Распространение означает, что если мы изменим один бит открытого текста, то (статистически) половина битов в зашифрованном тексте должна измениться, и аналогично, если мы изменим один бит зашифрованного текста, то примерно половина бит открытого текста должны измениться. Поскольку бит может иметь только два состояния, когда все они переоцениваются и меняются с одного, казалось бы, случайного положения на другое, половина битов изменит состояние.
Идея распространения заключается в том, чтобы скрыть связь между зашифрованным текстом и открытым текстом.
Это затруднит злоумышленнику, который пытается найти простой текст, и увеличивает избыточность обычного текста, распределяя его по строкам и столбцам; это достигается путем транспонирования алгоритма и используется только блочными шифрами.
В исходных определениях Шеннона путаница относится к тому, чтобы сделать взаимосвязь между зашифрованным текстом и симметричным ключом как можно более сложной и сложной; Распространение относится к рассеянию статистической структуры открытого текста по большей части зашифрованного текста. Эта сложность обычно реализуется посредством четко определенной и повторяемой серии замен и перестановок. Под заменой понимается замена определенных компонентов (обычно битов) другими компонентами в соответствии с определенными правилами. Под перестановкой понимается изменение порядка битов согласно некоторому алгоритму. Чтобы быть эффективным, любая неоднородность битов открытого текста должна быть перераспределена по гораздо более крупным структурам зашифрованного текста, что значительно затрудняет обнаружение этой неоднородности.
В частности, для случайно выбранного входа, если один инвертирует i-й бит, то вероятность того, что j-й выходной бит изменится, должна быть равна половине для любых i и j - это называется строгий лавинный критерий. В более общем смысле, можно потребовать, чтобы переключение фиксированного набора битов изменяло каждый выходной бит с вероятностью, равной половине.
Одна из целей путаницы - очень затруднить поиск ключа, даже если имеется большое количество пар открытого текста-зашифрованного текста, созданных с одним и тем же ключом. Следовательно, каждый бит зашифрованного текста должен зависеть от всего ключа и по-разному от разных битов ключа. В частности, изменение одного бита ключа должно полностью изменить зашифрованный текст. Самый простой способ добиться как распространения, так и путаницы - использовать сеть замещения-перестановки. В этих системах открытый текст и ключ часто играют очень похожую роль в создании вывода, поэтому один и тот же механизм обеспечивает как распространение, так и путаницу.
При разработке метода шифрования используются оба принципа смешения и распространения. Путаница означает, что процесс кардинально меняет данные от входа к выходу, например, путем преобразования данных через нелинейную таблицу, созданную из ключа. Есть много способов отменить линейные вычисления, поэтому чем более нелинейным он является, тем больше инструментов анализа он не работает.
Распространение означает, что изменение одного символа ввода приведет к изменению многих символов вывода. Если все сделано правильно, каждая часть ввода влияет на каждую часть вывода, что значительно усложняет анализ. Нет идеального процесса диффузии: он всегда пропускает какие-то узоры. Хорошая диффузия разбрасывает эти паттерны по всему выходу, и если их несколько, они зашифровывают друг друга. Это значительно усложняет выявление закономерностей и значительно увеличивает объем данных для анализа с целью взлома шифра.
Расширенный стандарт шифрования (AES) имеет как отличную путаницу, так и распространение. Его таблицы поиска путаницы очень нелинейны и хороши для разрушения шаблонов. Его этап распространения распространяет каждую часть ввода на каждую часть вывода: изменение одного бита ввода изменяет в среднем половину выходных битов. И путаница, и диффузия повторяются несколько раз для каждого входа, чтобы увеличить количество скремблирования. Секретный ключ подмешивается на каждом этапе, чтобы злоумышленник не мог заранее вычислить, что делает шифр.
Ничего из этого не происходит, когда простое одноэтапное скремблирование основано на ключе. Шаблоны ввода будут перетекать прямо на выход. На первый взгляд это может показаться случайным, но анализ обнаружит очевидные закономерности и шифр может быть взломан.
Цитированные работы
