Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Параметры Конструкции 4.24
| ТЕОРЕМА 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 посредством, например, дополнения сообщений нулями. Вторая проблема может также быть решена; см. ссылки в конце данной главы. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|