Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА 5.11
| РИСУНОК 5.5 : Дерево Меркле.
Фиксируя какую-то хэш-функцию H, мы обозначаем как MT t функцию, ко- торая принимает t входные значения x1, . . . , xt, вычисляет в итоге дерево Мер- кле и выводит значение корня дерева. (Ключевая хэш-функция дает ключевую функцию MT t очевидным способом.) Мы имеем: ТЕОРЕМА 5.11 Пусть (GenH, H) будет стойкой к коллизиям. Тогда (GenH, MT t) является также стойкой к коллизиям для любых фиксированных t. Дерво Меркле таким образом обеспечивает альтернативу преобразованию Меркле-Дамгорда для достижения расширения области для стойких к коллизи- ям хэш-функций. (Как было сказано, однако, деревья Меркле не являются стой- кими к коллизии, если число входных значений t может варьироваться.) Деревья Меркле обеспечивают эффективное решение нашей первоначальной проблемы, поскольку они позволяют изменять любое оригинальные входные дан- ные t с использованием связи O(log t). Клиент вычисляет h := MT t(x1, . . . , xt), загру- жает x1, . . . , xt на сервер и хранит h (вместе с числом файлов t) на локальном ресур- се. Когда клиент извлекает файл i, сервер посылает xi вместе с «доказательством»πi того, что это правильное значение. Это доказательство состоит из значений узлов на дереве Меркле, которые расположены рядом с путем из xi в корень. Посредством этих значений клиент может пересчитать значение корня и проверить, что это зна- чение было равным сохраненному значению h. В качестве примера рассмотрим дерево Меркле на Рисунке 5.5. Клиент вычисляет h1...8 := MT 8(x1, . . . , x8), загру- жает x1, . . . , x8 на сервер и ъранит h1...8 на локальном ресурсе. Когда клиент из- влекает x3, сервер отправляет x3 вместе с x4, h1...2 = H(x1, x2) и h5...8 = H(H(x5, x6), H(x7, x8)). (Если файлы большого размера, мы можем пожелать избежать отправки 203 любого другого файла, кроме того, который был запрошен клиентом. Это можно с легкостью сделать, если мы определим дерево Меркле по хэшам файлов, а не по самим файлам. Детали опустим.) Клиент вычисляет hr := H(h1...2, H(x3, x4)) и hr?r1...4, h5...8) и затем проверяет, чтобы h1...8 = hr Если H является стойкой к коллизиям, для сервера невозможно отправлять неправильные файлы (и любое доказательство), которые пройдут успешную верификацию. Используя данный подход, локальное хранилище клиента яв- ляется постоянным (независимо от количества файлов t), и связь от сервера к клиенту пропорциональна log t. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|