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