Протоколы Internet


SET и другие системы осуществления платежей - часть 7


Монеты 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 млн. долларов США (эквивалентно примерно 227 центов/месяц). Пусть доходы брокера составляют 10%, это означает, что продавец получает 0,9 цента при выкупе монеты. Таким образом, брокер должен продать миллиард монет в месяц. Если обычный клиент покупает 2500 монет в месяц, необходимо иметь 500000 клиентов.

Пусть k=4 (4-кратные столкновения). Для того чтобы сформировать 230 монет, надо будет закупить специализированное оборудование стоимостью около 100000$ (что менее 10% месячного дохода). Для целей вычисления хэш-функций могут использоваться специализированные ИС, применяемые для DES-шифрования или ИС FPGA – программируемые логические матрицы. Подготовка брокером нового набора монет может продолжаться в течение всего месяца. Нетрудно понять, что злоумышленнику, использующему обычную рабочую станцию, сформировать самостоятельно достаточное число монет не по плечу.




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