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



Pdf көрінісі
бет148/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   144   145   146   147   148   149   150   151   ...   249
Криптография Катц

5.6.2 Деревья Меркле 
Возьмите клиента, который загружает файл x на сервер. Когда клиент позже из-
влекает x, он хочет быть уверен, что сервер вернет ему оригинальный, неизмененный 
файл. Клиент мог бы просто сохранить x и проверить, чтобы извлеченный файл был 
равным x, но это в первую очередь разрушает саму цель использования серве ра. Мы 
занимаемся поиском решений, при которых хранилище клиента будет небольшим.
Естественное решение - это использовать подход «проверки отпечатков паль-
цев», описанный выше. Клиент может на локальном ресурсе хранить короткий 
дайджест h := H(x); когда сервер возвращает искомый файл xr , клиенту необхо-
димо только проверить, чтобы H(xr) ? h. 
Что случается, если мы хотим расширить данное решение до множества фай-
лов x1, . . . , xt? Существует два способа сделать это. Один из способов - это про-
сто хэшировать каждый файл отдельно; клиент на локальном ресурсе хранит 
дайджесты h1, . . . , ht и проверяет извлеченные файлы как и раньше. Недостаток 
этого способа в том, что хранилище клиента растет линейным образом в t. Еще 
одна возможность - это хешировать все файлы вместе. То есть клиент может 
вычслить h := H(x1, . . . , xt) и сохранить только h. Теперь недостаток заключа-
ется в том, что, когда клиент хочет извлечь и проверить правильность файла (i) 
(xi), ему необходимо извлечь все файлы, чтобы рассчитать дайджест.
Деревья Меркле, представленные Ральфом Меркле, предоставляют компро-
мисс между этими двумя крайностями. Дерево Меркле высчитанное по введен-


202
ным значениям x1, . . . , xt - это просто бинарное дерево глубиной log t, в котором 
входные данные расположены на листах, и значение каждого внутреннего узла 
- это хэш значений ее двух дочерних записей; см. Рисунок 5.5. (Мы предпо-
лагаем, что t - это степень числа 2; если нет - мы можем исправить некоторые 
входные значения на null или использовать незаконченное бинарное дерево в 
зависимости от применения.)


Достарыңызбен бөлісу:
1   ...   144   145   146   147   148   149   150   151   ...   249




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

    Басты бет