Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 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 или использовать незаконченное бинарное дерево в зависимости от применения.) жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|