Интегрированные сети ISDN


Модель электронных переводов - часть 6


Продавцы возвращают эти монеты брокеру, который осуществляет перевод реальных денег на счет продавца.

Электронная монета представляет собой последовательность бит, которая может быть легко проверена, но которую достаточно трудно сформировать. Алгоритм MicroMint устроен так, что формирование большого числа монет стоит дешевле (из расчета на одну монету), чем формирование одной или нескольких. Брокер формирует партию монет, например раз в месяц. При этом действие прежней партии монет истекает, и они не могут более использоваться. Продавцы возвращают полученные монеты в конце каждого дня.

Монеты MicroMint формируются с использованием кратных столкновений хэш-функций. Однопроходная хэш-функция H ставит в соответствие m битам строки х n бит строки y. Строка х называется исходным образом y, если H(x)=y. Пара строк (х1,х2) называются двойным столкновением, если H(x1)=H(x2)=y, где строка y имеет n бит. Если хэш-функция гарантирует достаточно высокий уровень рэндомизации, то для получения одного двойного столкновения необходимо вычислить для строки х примерно 2n/2 xэш-функций. Но при ограниченном n вычисление двойных столкновений является относительно простой задачей и для злоумышленника, по этой причине для формирования монет чаще используется вычисление k-кратных столкновений.

k-кратным столкновением называется набор строк х1, х2, …, хk для которых H(x1)=H(x2)=…=H(xk)=y. Для получения k-кратного столкновения необходимо выполнить вычисление примерно 2n(k-1)/k хэш-функций. В дальнейшем будем считать, что монета характеризуется k-кратным столкновением (х1, х2, …, хk). Корректность монеты может проверить кто угодно, вычислив k хэш-функций и проверив условие.

H(x1)=H(x2)=…=H(xk)=y

Если в ходе вычисления хэш-функций просматривать результат, то можно выявить определенное число k-кратных столкновений, что во много раз увеличивает производительность генерации электронных монет. Еще большего выигрыша в скорости можно достичь, применяя специфические аппаратные реализации.

Предположим, что брокер хочет иметь чистый доход размером в 1 млн.


Начало  Назад  Вперед