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



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

ТЕОРЕМА 4.26  Для любого простого числа p функция h является строго 
универсальной.
ДОКАЗАТЕЛЬСТВО Зафиксируйте и распознайте m, mr∈Zp и любойy t, 
tr∈Zp. Для которых ключи (a, b) это справедливо, что оба ha,b(m) = t и ha,b(mr) 
= tr? Это справедливо только, если a • m + b = t mod p и a • mr + b = tr mod p.
Таким образом, мы имеем два линейных уравнения с двумя неизвестными 
a, b. Эти оба уравнения выполняются точно, если a = [(t − tr) • (m − mr)−1 mod 


161
p] и b = [t − a • m mod p]; при этом [(m − mr)−1 mod p] имеет место, потмоу что 
m ƒ= mr , и поэтому m − mr ƒ= 0 mod p. Другими словами, это означает, что 
для любого m, mr, t, tr , как показано выше, имеется уникальный ключ (a, b) с 
ha,b(m) = t и ha,b(mr) = tr. Так как существуют ключи |T | , мы сделали вывод, 
что вероятность (по выбору ключа) того, что ha,b(m) = t и ha,b(mr) = tr является 
ровно 1/|K| = 1/|T |2 , как и было необходимо .
Параметры Конструкции 4.24 . Мы кратко обсудили параметры Конструкции 
4.24, когда она реализуется со строго универсальной функцией, описанной выше, иг-
норируя факт, что p не в степени 2. Конструкция является 1/|T |-защищенным MAC 
с тегами длиной log |T |; длина тегов оптимальная по уровню достигнутьй защиты.
Пусть M будет каким-то фиксированным пространством сообщений, для кото-
рого мы хотим сконструировать одноразовый защищенный MAC. Вышеописан-
ная конструкция дает 1/|M|-защищенный MAC с ключами, которые вдвое длиннее 
сообщений. Читатель может заметить две проблемы здесь, на противоположном 
конце спектра. Во-первых, если |M| меньше, чем 1/|M| , вероятность подделки не-
ожиданно большая. С другой стороны, если |M| больше чем 1/|M| , вероятность 
подделки может ыт ькатастрофической; можно было бы принять (каким-то обра-
зом) большую вероятность подделки, если тот уровень безопасности может быть 
достигнут более короткими ключами. Первая проблема (когда значение |M| малень-
кое) является легкой для решения простым заложением M в большое пространство 
сообщений Mr посредством, например, дополнения сообщений нулями. Вторая 
проблема может также быть решена; см. ссылки в конце данной главы.


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




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

    Басты бет