Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА 4.25
- ДОКАЗАТЕЛЬСТВО
| КОНСТРУКЦИЯ 4.24
Пусть h : K × M → T будет строго универсальной функцией. Определим MAC для сообщения в M следующим образом: • Gen: подберите универсальный k ∈ K и выведите его в качестве ключа. • Mac: при вводе ключа k ∈ K и сообщения m ∈ M, выведите тег t := hk (m). • Vrfy: при вводе ключа k ∈ K сообщения m ∈ M и тега t ∈ T, выведите 1, если и только если t =? h (m). (If m ƒ∈ M, затем выведите 0.) k MAC из любой строго универсальной функции . ____________________________________________________________ 6Их часто называют строго универсальными хэш функциями, но в криптографических кон- текстах термин «хэш» имеет другое значение, которое мы увидим далее в книге. 160 Вышеописанную конструкцию мож но рассматривать как аналогичную Кон- струкции 4.5. Это потому что строго универсальная функция h идентична слу- чайной функции, так как она определяется только дважды. ТЕОРЕМА 4.25 Пусть h : K × M → T будет строго универсальной функ- цией. Конструкция 4.24 является 1/|T |-защищенным MAC для сообщений в M. ДОКАЗАТЕЛЬСТВО Пусть A будет злоумышленником. Как правило, в информационно-теоретических условиях мы можем предположить, что A явя- лется детерминированным без потери обобщенности. Поэтому сообщение mr , которое выводит A в начале эксперимента зафиксировано. Более того, пара (m, t), которую A выводит в конце эксперимента, является детерминированной функцией тега tr на mr , которые A получает. Таким образом, мы имеем Это доказывает теорему. Теперь мы вернемся к классической конструкции строго универсальной функции. Мы предположим некоторые основные знания об арифметически мо- дульно простым числом ; читатели могут обратиться к Разделу 8.1.1 и 8.1.2 для необходимой правочной информации. Зафиксируйте несколько простых чисел p, и пусть Zp {0, . . . , p − 1}. Мы берем как наше пространство сообщений M = Zp; пространство возможных тегов тоже будет T = Zp. Ключ (a, b) состоит из пары элементов из Zp; таким образом, K = Zp × Zp. Определим h как ha,b(m) [a • m + b mod p], где обозначение [X mod p] относится к редукции целого числа X по модулю p (и поэтому [X mod p] ∈ Zp всегда). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|