MicroMint
MicroMint (при вольной интерпретации это выражение можно перевести как микромонетный двор) представляет собой еще одну платежную систему, базирующуюся на модели электронных монет. Здесь не используется общедоступный ключ шифрования. Электронные монеты в этой схеме формируются брокером, который продает их пользователям. Пользователи передают эти монеты продавцам в качестве оплаты товаров или услуг. Продавцы возвращают эти монеты брокеру, который осуществляет перевод реальных денег на счет продавца.
Электронная монета представляет собой последовательность бит, которая может быть легко проверена, но которую достаточно трудно сформировать. Алгоритм 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 млн. долларов США (эквивалентно примерно 227 центов/месяц). Пусть доходы брокера составляют 10%, это означает, что продавец получает 0,9 цента при выкупе монеты. Таким образом, брокер должен продать миллиард монет в месяц. Если обычный клиент покупает 2500 монет в месяц, необходимо иметь 500000 клиентов. Пусть k=4 (4-кратные столкновения). Для того чтобы сформировать 230 монет, надо будет закупить специализированное оборудование стоимостью около 100000$ (что менее 10% месячного дохода). Для целей вычисления хэш-функций могут использоваться специализированные ИС, применяемые для DES-шифрования или ИС FPGA - программируемые логические матрицы. Подготовка брокером нового набора монет может продолжаться в течение всего месяца. Нетрудно понять, что злоумышленнику, использующему обычную рабочую станцию, сформировать самостоятельно достаточное число монет не по плечу. При продаже монет клиенту брокер запоминает, какому клиенту какие монеты проданы, что позволяет в будущем проконтролировать попытки злоупотреблений. Неиспользованные монеты ликвидируются в конце месяца. Ограничение времени действия монет создает определенные трудности для клиента. Но за то это ограничивает требуемые объемы баз данных, хранящих информацию о выпущенных и использованных уже монетах. Монетная система по своей природе предполагает определенное доверие между плательщиком и получателем платежа. Получатель может присвоить монету и заявить, что она уже была использована, а плательщик может предъявить претензии получателю (банку или продавцу), утверждая, что повторного использования не было, а монета просто присвоена. В сущности, это является общим свойством любых монет и сертификатов на предъявителя. Каждый раз, когда клиент осуществляет покупку, он пересылает продавцу одну или несколько монет (х1, х2, …, хk). Это может осуществляться автоматически программой WEB-броузера.
Продавец проверяет корректность монет путем вычисления k функций H(xi), что занимает совсем немного вычислительных ресурсов. При возвращении монет продавцом брокеру проверка повторяется. Существуют методы формирования монет специфических для клиента или для продавца, что снижает риски злоупотреблений (смотри “PayWord and Micromint: Two simple micropayment schemes” Ronald L. Riverst и Adi Shamir, 7 мая 1996). Мелкомасштабная атака малоэффективна, и по этой причине недостойна серьезного внимания (злоумышленник должен понести большие издержки из-за нескольких центов). Для такого рода атак для k=4 и n=54 при использовании стандартной рабочей станции требуются десятки лет. Крупномасштабное мошенничество легко детектируется из-за следующих обстоятельств.
- Все фальшивые монеты теряют силу в конце месяца.
- Фальшивые монеты могут быть сформированы после того, как брокер выбросил на рынок новую партию монет в начале месяца.
- Брокер может обнаружить присутствие фальшивок из-за того, что некоторые фальшивые монеты неизбежно не соответствуют ни одной из настоящих, которые все зарегистрированы.
- Брокер может в любой момент объявить об истечении срока годности выпущенных в оборот монет и запустить в оборот новую партию.
Данное решение может оказаться не слишком хорошим для больших групп, где вор всегда сможет найти клиента, желающего приобрести украденные монеты. При малых же группах брокер будет вынужден производить слишком большую вычислительную работу. Другим вариантом может быть обобщение понятия столкновения. Монета (х1, х2, …, хk) будет считаться корректной для клиента U, если образы y1=(x1), y2=(x2),…, yk=(xk) удовлетворяют условию yi+1 - yi = di (mod 2u) для i =. 1,2,..,k-1, где (d1,d2,…,dk-1)=h(U). Стандартный алгоритм формирования монет соответствует случаю, когда все значения d равны нулю. Формирование монет специфических для продавца может осуществляться согласно алгоритму, схожему с выше описанным. Существуют алгоритмы, которые позволяют сократить вычислительные издержки при массовой генерации монет сразу на несколько месяцев. Другие системы для осуществления небольших платежей, например, NetBill предлагают дополнительные возможности (например, заказы товара и шифрование информации о покупке), но они относительно дороже.
