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



Pdf көрінісі
бет117/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   113   114   115   116   117   118   119   120   ...   249
Криптография Катц

КОНСТРУКЦИЯ 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 всегда).


Достарыңызбен бөлісу:
1   ...   113   114   115   116   117   118   119   120   ...   249




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

    Басты бет