Введение в современную криптографию
Хэш-функции из блочных шифров
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 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 не соответствуют этим характеристикам). Лю- бой блочный шифр, используемый для создания образца идеального шифра, должен быть оценен относительно этих более жестких требований. Докажем следующую теорему для конкретных условий, однако доказатель- ство может быть легко адаптировано и для асимптотических условий. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|