Jump to content

Путаница и диффузия

(Перенаправлено с Путаница (криптография) )

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

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

Определение

[ редактировать ]

Путаница

[ редактировать ]

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

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

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

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

В сетях подстановки-перестановки путаницу создают блоки подстановки . [4]

Диффузия

[ редактировать ]

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

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

В сетях замены-перестановки диффузия обеспечивается ящиками перестановок (также известными как слой перестановок). [4] ). В начале XXI века возник консенсус, согласно которому дизайнеры предпочитали, чтобы уровень перестановок состоял из линейных булевых функций , хотя можно использовать и нелинейные функции. [4]

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

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

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

Практическое применение

[ редактировать ]

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

Путаница неизбежно влечет за собой некоторую диффузию, [6] поэтому конструкция с очень широким входным S-box может обеспечить необходимые диффузионные свойства, [ нужна ссылка ] но будет очень дорогостоящим в реализации. Поэтому практические шифры используют относительно небольшие 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] На этапе диффузии каждая часть входных данных распределяется по всем частям выходных данных: изменение одного бита входных данных приводит к изменению в среднем половины выходных битов. И путаница, и диффузия повторяются несколько раз для каждого входа, чтобы увеличить количество скремблирования. Секретный ключ смешивается на каждом этапе, поэтому злоумышленник не может заранее рассчитать, что делает шифр.

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

См. также

[ редактировать ]
  1. ^ «Теория информации и энтропия». Выводы, основанные на моделях, в науках о жизни: основы фактических данных . Спрингер Нью-Йорк. 01 января 2008 г. стр. 51–82. дои : 10.1007/978-0-387-74075-1_3 . ISBN  9780387740737 .
  2. ^ Jump up to: а б с Штамп и Лоу 2007 , с. 182.
  3. ^ Jump up to: а б Шеннон, CE (октябрь 1949 г.). «Теория связи секретных систем*» . Технический журнал Bell System . 28 (4): 656–715. дои : 10.1002/j.1538-7305.1949.tb00928.x .
  4. ^ Jump up to: а б с Лю, Реймен и Леандер, 2018 г. , стр. 1.
  5. ^ Столлингс, Уильям (2014). Криптография и сетевая безопасность (6-е изд.). Река Аппер-Седл, Нью-Джерси: Прентис-Холл. стр. 67–68. ISBN  978-0133354690 .
  6. ^ Jump up to: а б Даемен и Реймен 2013 , с. 130.
  7. ^ Daemen & Rijmen 2013 , с. 20.
  8. ^ Daemen & Rijmen 2013 , с. 21.
  9. ^ Daemen & Rijmen 2013 , с. 126.
  10. ^ Лю, Реймен и Леандер 2018 , стр. 2.
  11. ^ Ли и Ван 2017 .
  12. ^ Саджади и др. 2012 .
  13. ^ Daemen & Rijmen 2013 , с. 131.
  14. ^ Уильям, Столлингс (2017). Криптография и сетевая безопасность: принципы и практика, глобальное издание . Пирсон. п. 177. ИСБН  978-1292158587 .

Источники

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 11f61f0881709125837e437a7af1c9bf__1722265500
URL1:https://arc.ask3.ru/arc/aa/11/bf/11f61f0881709125837e437a7af1c9bf.html
Заголовок, (Title) документа по адресу, URL1:
Confusion and diffusion - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)