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



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

РИСУНОК 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.


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




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

    Басты бет