Введение в современную криптографию


Хэш-функции из блочных шифров



Pdf көрінісі
бет188/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   184   185   186   187   188   189   190   191   ...   249
Криптография Катц

6.3.1 Хэш-функции из блочных шифров
Может показаться удивительным, что можно создать устойчивую к колли-
зиям функцию сжатия из блочного шифра, который обладает определенными 
дополнительными свойствами. Есть несколько способов сделать это; один из 
наиболее распространенных с помощью конструкции Дэвиса-Мейера (Davies–
Meyer). Пусть F будет блочным шифром с длиной ключа n-битов и длиной бло-
ка A- битов. Тогда можно определить функцию сжатия h : {0, 1}n+A → {0, 1}A
by h(k, x) F (x) ⊕ x. (См. рис. 6.11.)
РИС. 6.11:  Конструкция Мейера-Дэвиса.
Мы не знаем, как доказать устойчивость к коллизиям результирующей функции 
сжатия, основанной только на предположении, что F является строгой псевдослу-
чайной перестановкой, и на самом деле, есть основания предполагать, что такое до-
казательство невозможно. Однако мы можем доказать устойчивость к коллизиям, 
если мы хотим смоделировать F в качестве идеального шифра. Модель идеального 
шифра представляет собой усиление модели случайного прогноза (см. раздел 5.5), в 
которой мы постулируем, что все стороны имеют доступ к прогнозу для случайной 
ключевой перестановки F : {0, 1}n × {0, 1}A → {0, 1}A а также к ее инверсии F 
−1 (т.е., такой как F −1(k, F (k, x)) = x для всех k, x). Другой способ придумать это 
состоит в том, что каждый ключ k ∈ {0, 1}n указывает независимую равномерную 
перестановку F (k, •) на A-битных строках. Как и в модели случайного прогноза 
есть только один способ вычислить F (или F −1) – это явным образом запросить 
прогноз с (k, x) и получить обратно F (k, x) (или F −1(k, x)).
Анализ конструкций в модели идеального шифра обладает всеми достоин-
ствами и недостатками работы в модели случайного прогноза, как подробно 
обсуждается в разделе 5.5. Мы только добавим здесь, что модель идеального 
шифра предполагает отсутствие атак, связанных с ключом, в том смысле, что 
(как мы только что сказали) перестановки F (k, •) и F (kr, •)должны вести себя 
независимо друг от друга даже, если, например, k и kr отличаются только од-


256
ним битом. Кроме того, не должно быть никаких «плохих ключей» k (скажем, 
все нулевые кнопки), для которых F (k, •) легко отличить от случайных. Это 
также означает, что F (k, •) должны «вести себя случайно»даже когда k извест-
но. Для любого реального шифра F эти свойства не обязательно поддержива-
ются (и даже четко не определены), даже если F является строгой псевдослу-
чайной перестановкой и читатель может заметить, что мы не обсуждаем эти 
свойства в любом нашем анализе реальных конструкций блочных шифров. (На 
самом деле, DES и тройной DES не соответствуют этим характеристикам). Лю-
бой блочный шифр, используемый для создания образца идеального шифра, 
должен быть оценен относительно этих более жестких требований.
Докажем следующую теорему для конкретных условий, однако доказатель-
ство может быть легко адаптировано и для асимптотических условий.


Достарыңызбен бөлісу:
1   ...   184   185   186   187   188   189   190   191   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет