Механизм электронных наличных

Электронные деньги

Шифр Эль-Гамаля

Пусть имеются абоненты А, В, С, …, которые хотят передавать друг другу секретные сообщения, но не имеют защищенных каналов связи. Шифр Шамира использует для этого три пересылки.

В отличие от шифра Шамира шифр Эль-Гамаля использует только одну пересылку сообщения. Фактически используется схема Диффи-Хеллмана, чтобы сформировать секретный ключ, общий для двух абонентов, а затем сообщения шифруются и расшифровываются с помощью этого ключа.

Для всей группы выбирается большое простое число p, например, содержащее 90 цифр, и числоgтакое, что все числа от 1 до р-1 представляются как различные степени g^x mod p. Числа p и g передаются всем в открытом виде. Затем каждый абонент выбирает секретное число с_i<p-1 и хранит его в секрете. Затем он вычисляет d_i = g^Cimod p и открыто рассылает всем.

В результате получается следующая таблица.

Абонент	Секретный ключ	Открытый ключ
A	cA	dA
B	cB	dB
C	cC	dC
	Каждый знает только свой	Знают все

Протокол Эль-Гамаля:

Шаг 1. Абонент А выбирает случайно число k<р-2 и вычисляет 2 числа

r = g^k mod p,

e = (m*d_B)^kmod p,

где m – исходное сообщение и передает пару чисел (r,e) абоненту В.

Шаг 2. Абонент В вычисляет

m’^/ = (e*r^p-1-CB)mod p.

Свойства протокола Эль-Гамаля:

1) m’ =m.

2) противник, зная p, g, d_B, r, e, не может вычислить число m, т.к. ему неизвестно c_B. Он не может его вычислить - это практически невозможно.

Аналогично могут передавать сообщения все абоненты сети. Любой абонент может послать к B свое сообщение, зашифровав его открытым ключом d_B. Но только абонент B может расшифровать его с помощью секретного ключа c_B. Отметим также, что требуется только одна пересылка, но объем шифрованного сообщения в 2 раза больше, чем исходного.

Пример.

Пусть A хочет передать к B сообщение m = 15. Для всей системы выбирается p = 23 и g = 5. Пусть B выбрал для себя c_B = 13 и вычислил d_B = 21.

Шаг 1. Абонент A выбирает k = 7 и вычисляет

r = 5⁷ mod 23 = 17.

e = (15*21 ⁷)mod 23 = 15*10mod 23 = 12,

Шаг 2. Абонент B вычисляет

m^/ = 12*17^23-1-13mod 23 = 12*17⁹mod 23 = 12*7mod 23 = 15.

Таким образом, B получил исходное сообщение m = 15.

Еще примеры для p = 53, g = 20, c_B = 47, d_B = 14, k = 40.

m = 29, r = 36, e = 43, m^/ = 29.

m = 30, r = 36, e = 39, m^/ = 30.

Заметим, что противник Е может послать к B свое сообщение (дезинформацию), используя открытый ключ d_B. Избежать этого позволяет ЭЦП по Эль-Гамалю.

Во многих странах люди оплачивают покупки при помощи электронных карточек, заказывают авиабилеты через Интернет, покупаюттовары в Интернет-магазинах. Сведения о покупках накапливаются в магазинах и банках. Поэтому появилась новая проблема, называемая «проблема Большого Брата».

Суть проблемы Большого Брата состоит в том, что исчезает анонимность процесса покупки, т.е. информация о покупках любого человека можетстать известной третьим лицам и использоваться против него. Например, сведения о покупке билета на поезд или самолет могут представлять интерес для преступников, информация о закупках алкогольных напитков политическим деятелем может быть использованапротив него его противниками и т.п.

Поэтому возникла идея разработать такие схемы электронных платежей, которые сохраняли бы анонимность покупателя в той же степени, что и при расчете наличными деньгами. Такие протоколы называются электронными деньгами или цифровыми наличными (digital cache),что подчеркивает их основное свойство — они обеспечивают ту жестепень анонимности, что и обычные деньги. В 1993 году изобретены механизмы практической реализации электронных денег. В 2013 году Швеция полностью отказывается от наличных денег и переходит на электронные.

Описываемая ниже схема былапредложена Д. Чаумом.

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

1) покупатель снимает нужную сумму со своего счета в банке;

2) покупатель «пересылает» деньги в магазин;

3) магазин сообщает об этом в банк, соответствующая сумма денег зачисляется на счет магазина, а покупатель забирает товар.

Наша цель — разработать такую схему, чтобы

· она была надежна;

· банк не знал, кто купил товар, т.е. была сохранена анонимность обычных денег.

Мы рассмотрим две «несовершенные» схемы, а затем «хорошую», чтобыбыло легче попять суть метода.

Схема 1. Первая схема базируется на RSA. Банк имеет следующую информацию: секретные числа с, Р, Q и открытые числа N, d.

N = PQ,

d = с^-1mod (Р - 1)(Q - 1). (11.1)

Допустим, покупатель решил израсходовать сумму 100$. Покупатель высылает в банк сведения о себе и случайное число n<N, которое будет номером банкноты.

Банк вычисляет число

s = n^с mod N (11.2)

и формирует банкноту (n, s), которую возвращает покупателю, уменьшив его счет на 100$. Параметр s в банкноте —это подпись банка. Никто не может подделать подпись, так как число «с» секретно.

Покупатель предъявляет банкноту (n, s) в магазине, чтобы купить товар. Магазин отправляет эту банкноту в банк для проверки. Прежде всего, банк проверяет правильность подписи. Эту проверку мог бы сделать и магазин, используя открытые ключи банка. Но кроме этого банк хранит все номера возвратившихся к нему банкнот и проверяет, нет ли числа n в этом списке. Если n есть в списке,то платеж не принимается (кто-то пытается использовать банкноту повторно). Если же все проверки прошли успешно, то банк добавляет 100$ на счет магазина, а магазин отпускает товар покупателю. Схема показана на рисунке 11.1.

П

Б

М

1.О себе, n

2.s

3.(n,s)

4.(n,s)

6.товар

5.да

Рис 11.1. Схема 1 электронных денег

Недостаток этой схемы — отсутствует анонимность. Банк, сопоставив n, полученные от покупателя и от магазина, может выяснить магазин покупки и с помощью магазина выяснить товар покупки и связать товар с покупателем.

Схема 2. Рассмотрим вторую «несовершенную» схему, которая уже обеспечивает анонимность. Эта схема базируется на так называемой «слепой подписи».

Снова покупатель хочет купить товар. Он генерирует число n, которое теперь не будет посылаться в банк. Затем он генерируетслучайное число r, взаимно простое с N, и вычисляет число

ň = (n* r^d) mod N. (11.3)

Число ň и сведения о себе покупатель отправляет в банк.

Банк вычисляет число

š = ň^cmod N (11.4)

и отправляет š обратно покупателю (не забыв при этом снять 100$с его счета).

Покупатель находит число r^-1mod N и вычисляет

s = (š • r^-1) mod N. (11.5)

Заметим, что с учетом соотношений (11.5), (11.4) и (11.1) имеем

s = ň^c • r^-1 = (n*r^d)^c•r^-1= n^cr^dc•r^-1 = n^c r¹ r^-1= n^c mod N.

Т.е. мы вычислили правильную подпись банка к n (см. (11.2)), но самого числа n ни банк, ни кто-либо другой не видел. Вычисление (11.4) называется «слепой подписью», так как реальное сообщение (n) подписывающий не видит и не может узнать.

Таким образом, покупатель имеет число n, которое никому неизвестно и никогда не передавалось по каналам связи, и подпись банка s, совпадающую с вычисленной по (11.2). Покупатель формирует банкноту (n, s) и действует так же, как в первой «плохой» схеме. Но теперь никто не знает, кому соответствует эта банкнота, т.е. онастала анонимной, как обычная бумажная банкнота. Номера банкнот, полученные банком от покупателя и от магазина, теперь разные и банк не может их сопоставить.

Схема 2 показана на рис 11.2.

П

Б

М

1.О себе, ň

2.(ň š)

3.(n,s)

4.(n,s)

6.товар

5.да

Рис 11.2.Схема 2 электронных денег

Действия магазина и банка после предъявления покупателем банкноты (n, s) ничем не отличаются от действий, описанных в первой схеме.

Почему же данная схема несовершенная? Она имеет следующий недостаток: можно сфабриковать фальшивую банкноту, если известны две настоящие. Делается это так. Пусть злоумышленник (будь топокупатель или магазин) имеет две настоящие банкноты (n₁, s₁) и (n₂, s₂). Тогда он легко сможет изготовить фальшивую банкноту (n₃, s₃), вычислив числа

n₃= n₁n₂ mod N,

s₃ = s₁ s₂ mod N.

Действительно,

n₃^c= (n₁n₂) ^c = n₁ ^cn₂ ^c = s₁s₂=- s₃mod N. (11.6)

Т.е. s₃ является правильной подписью для n₃, и у банка нет никаких оснований, чтобы не принять эту фальшивую банкноту (он просто не сможет отличить ее от подлинной). Это так называемое «мультипликативное свойство» системы RSA.

Схема 3. Опишем, наконец, третью, «хорошую» схему, в которой устранены всенедостатки первых двух.

Есть простой способ борьбы с мультипликативным свойством системы RSA — внесение избыточности в сообщение. Допустим, что длина модуля N - 1024 бита. Такой же может бытьи длина числа n. Будем записывать случайный номер банкноты только в младшие 512 бит n, а в старшие 512 бит n запишем некоторое фиксированное число. Это фиксированное число может нести полезную информацию, такую, как номинал банкноты и наименование банка. Теперь банк при предъявлении ему банкноты будет проверять наличие фиксированного заголовка в параметре n. Вероятность того, что при перемножении двух чисел по модулю N результат совпадет с ними в 512 битах, пренебрежимо мала. Поэтому получить фальшивую банкноту по формуле (11.6) не удастся.

Пример 11.1. Пусть в качестве секретных параметров банкавыбраны числа Р = 17, Q = 7, с = 77. Соответствующие им открытые параметры будут N = 119, d = 5. Для исключения возможностиподделки банкнот их допустимыми номерами считаются только числа, состоящие из двух одинаковых десятичных цифр, например, 11,77, 99.

Когда покупатель хочет получить банкноту, он вначале случайным образом выбирает ее номер (из числа допустимых). Предположим, он выбрал n — 33. Затем он находит случайное число г, взаимно простое со 119. Допустим, r = 67, gcd(67,119) = 1. Далее,покупатель вычисляет

ň = (33 • 67⁵) mod 119 = (33 • 16) mod 119 = 52.

Именно число 52 он посылает в банк.

Банк списывает со счета покупателя 100$ и отправляет ему число

š = 52⁷⁷mod 119 = 103.

Покупатель вычисляет r^-1= 67^-1mod 119 = 16 и s = 103•16 mod 119 = 101 и получает платежеспособную банкноту

(n, s) = (33,101).

Эту банкноту он посылает в магазин, чтобы купитьтовар.

Магазин предъявляет банкноту в банк. Банк делает следующиепроверки:

1) номер банкноты (n = 33) состоит из двух одинаковых десятичных цифр (т.е. содержит требуемую избыточность);

2) ранее банкнота с таким номером не предъявлялась;

3) подпись банка верна, т.е. 33⁵mod 119 = 101.

Так как все проверки прошли успешно, банк зачисляет 100$ на счет магазина, о чем ему и сообщает. Магазин отпускает товар покупателю.

Дата добавления: 2014-01-04