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


Ограничение информационно-теоретических MAC



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

4.6.2 Ограничение информационно-теоретических MAC 
В данном разделе мы изучим ограничения информационно-теоретической аутентифи-
кации сообщений. Мы покажем, что любой 2−n-защищенный MAC должен иметь клю-
чи длиной как минимум 2n. Расширение доказательства показывает, что любой A-time 
2−n-защищенный MAC (где защита определяется посредством естественной модифика-
ции Определения 4.23) требует ключи длиной как минимум (A+1)•n. Вывод в том, что ни 
один MAC ключами ограниченной длины не сможет обеспечить информационно-теоре-
тическую защиту при аутентификации неограниченного числа сообщений.
В дальнейшем, мы предположим, что пространство сообщений содержит по 
крайней мере два сообщения; если нет, смысла в общении вообще нет, и тем 
более в аутентификации.
ТЕОРЕМА 4.27 Пусть Π = (Gen, Mac, Vrfy)  будет 2−n-защищенным MAC
где все ключи выведенные Gen одинаковой длины. Тогда ключи, выведенные Gen 
должны быть длиной как минимум 2n.
ДОКАЗАТЕЛЬСТВО Зафиксируйте два разных сообщения m0, m1 в про-
странстве сообщений. Интуиция подсказывает, что должно быть как минимум 


162
2n p вариантов для тега m0 (и вообще злоумышленник может угадать его с ве-
роятностью большей, чем 2−n); более того, даже будучи обусловленным значе-
нием тега для m0, должно быть 2n возможностей для тегаm1 (ии вообще злоу-
мышленник мог бы подделать тег на m1 с вероятность большей, чем 2−n). Так 
как каждый ключ определяет теги для m0 и m1, это означает, что ключи должны 
быть как минимум 2n × 2n . Мы сделаем это формальным ниже.
Пусть K обозначает пространство ключей (то есть набор всех возможных клю-
чей, которые могут быть выведены Gen). Для любого возможного тега t0, пусть 
K(t0) означает набор ключей, для которых t0 является верным тегом на m0; то есть
K(t0) {k | Vrfyk (m0, t0) = 1}.
Для любого t0 мы должны иметь |K(t0)| ≤ 2−n • |K|. Иначе злоумышленник мо-
жет просто вывести (m0, t0) в качестве его подлог; это будет верный подлог с ве-
роятностью как минимум |K(t0)|/|K| > 2−n, что противоречит заявленной защите.
Рассмотрим теперь злоумышленника A , который запрашивает тег на сообще-
ние m0, получает в ответ тег t0, подбирает универсальный ключ k ∈ K(t0) и вы-
водит (m1, Mack (m1)) в качестве его подлога. Вероятность того, что A выведет 
верный подлог как минимум
При заявленой защите схемы вероятность того, что злоумышленник выведет вер-
ный подлог максимум 2−n. Таким образом, мы должны иметь |K| ≥ 22n. Так как все 
ключи имеют одинаковую длину, каждый ключ должен иметь длину как минимум 2n.


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




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

    Басты бет