159
4.6.1 Построение информационно-теоретических MAC
В данном разделе мы покажем как построить ε-защищенный MAC на основании
строго универсальной функции.6 Затем мы покажем простую конструкцию последней.
Пусть h : K× M → T будет ключевой функцией, первый
входной элемент
которой будет ключ k ∈ K, а второй входной элемент,
которы й будет взят из
некоей области M. Как обычно, мы пишем hk(m) вместо h(k, m). Тогда h явля-
ется строго универсальной (или попарно-независимой), если для любых двух
разных входных элементов m, mr значения hk(m) и hk (mr) являются универ-
сальными и независимо распределенными в T , где k является универсальным
ключом. Это эквивалентно тому, что вероятность того, что hk (m), hk (mr) возь-
мут на себя какие-либо
определенные значения t, tr, равняется 1/|T |2. То есть:
ОПРЕДЕЛЕНИЕ 4.23 Функция h : K× M → T яаляется строго универсаль-
ной, если для всех разных m, mr ∈
M и всех t, tr ∈
T справедливо, что
где вероятность берется выше универсального выбора k ∈ K.
Вышеописанное должно объяснить конструкцию одноразового кода аутентифи-
кации сообщений из любой строго универсальной функции h.
Тег t на сообщении
m полечен путем вычисления hk (m), где ключ k является универсальным; см. Кон-
струкцию 4.24. Очевидно, даже после того, как злоумышленник видит тег tr := hk
(mr) для любого сообщения mr, правильный тег hk(m) для любого другого сообще-
ния m все еще единообразно распространяется в T с точки зрения злоумышленни-
ка.
Таким образом, злоумышленник не может сделать ничего, кроме как в слепую
угадывать тег, и такое гадание будет правильным только с вероятностью 1/|T |.
Достарыңызбен бөлісу: