Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Определение [ править ]

Путаница [ править ]

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

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

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

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

Распространение [ править ]

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

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

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

Теория [ править ]

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

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

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

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

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

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

Анализ AES [ править ]

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

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

См. Также [ править ]

  • Сеть подстановки-перестановки
  • Эффект лавины

Ссылки [ править ]

  1. ^ "Теория информации и энтропия". Вывод на основе моделей в науках о жизни: учебник по доказательствам . Springer Нью-Йорк. 2008-01-01. С. 51–82. DOI : 10.1007 / 978-0-387-74075-1_3 . ISBN 9780387740737.
  2. Перейти ↑ Stallings, William (2014). Криптография и сетевая безопасность (6-е изд.). Река Аппер Сэдл, штат Нью-Джерси: Прентик-Холл. С. 67–68. ISBN 978-0133354690.
  3. ^ Уильям, Столлингс (2017). Криптография и сетевая безопасность: принципы и практика, глобальное издание . Пирсон. п. 177. ISBN. 978-1292158587.

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

  • Клод Э. Шеннон, "Математическая теория криптографии" , Техническая записка Bell System MM 45-110-02, 1 сентября 1945 г.
  • Клод Э. Шеннон, " Коммуникационная теория секретных систем ", Bell System Technical Journal , вып. 28-4, страницы 656–715, 1949. [1]
  • Уэйд Трапп и Лоуренс С. Вашингтон, Введение в криптографию с теорией кодирования. Второе издание. Пирсон Прентис Холл, 2006.