и посылает z Алисе.

(3)Алиса вычисляет четыре квадратных корня z (mod n). Она может сделать это, так как она знает разлож е-ние n на множители. Назовем их +x, -x, +у и -у. Обозначим как x меньшее из следующих двух чисел:

x mod n

-x mod n

Аналогично, обозначим как у меньшее из следующих двух чисел: у mod n -у mod n

Обратите внимание, что r равно либо x, либо у.

(4)Алиса делает пытается угадать, какое из значений равно r - x или у, и посылает свою догадку Бобу.

(5)Если догадка Алисы правильна, результатом броска монеты является "орел", а если неправильна -"решка". Боб объявляет результат броска монеты .

Подпротокол проверки:

(6)Алиса посылает p и q Бобу.

(7)Боб вычисляет x и у и посылает их Алисе.

(8)Алиса вычисляет r.

У Алисы нет возможности узнать r, поэтому она действительно угадывает. Она на этапе (4) сообщает Бобу только один бит своей догадки, не давая Бобу получить и x, и у. Если Боб получит оба этих числа, он сможет изменить r после этапа (4).

Бросание "честной" монеты с помощью возведения в степень по модулюp

В этом протоколе в качестве однонаправленной функции используется возведение в степень по модулю пр о-стого числа p [1306]:

Подпротокол бросания честной монеты :

(1)Алиса выбирает простое число p так, чтобы множители p-1 были известны, и среди них было по крайней мере одно большое простое число.

(2)Боб выбирает два примитивных элемента, h и t, в GF(p). Он посылает их Алисе.

(3)Алиса убеждается, что h и t являются примитивными элементами, и затем выбирает случайное число x, взаимно простое с p-1. Затем она вычисляет одно из двух значений :

у = hx mod p, или у = tx mod p

Она посылает у Бобу.

(4)Боб пытается угадать, вычислила Алиса у как функцию h или как функцию t, и посылает свое предположение Алисе.

(5)Если догадка Боба правильна, результатом бросания монеты является "орел", в противном случае -"решка". Алиса объявляет результат броска монеты.

Подпротокол проверки:

(6)Алиса раскрывает Бобу значение x. Боб вычисляет hx mod p и tx mod p, убеждаясь, что Алиса играла честно и проверяя результат броска. Он также проверяет, что x и p-1 - взаимно простые числа.

Чтобы Алиса могла смошенничать, она должна знать два целых числа, x и x, для которых выполняется hx-tx mod p Для того, чтобы узнать эти значения, ей нужно вычислить :

logth =xx-1 mod p-1 и logth =xxr1 mod p-1.

Это трудные проблемы.

Алиса смогла бы сделать это, если бы она знала logth, но Боб выбирает h и t на этапе (2). У Алисы нет другого способа кроме, как попытаться вычислить дискретный логарифм . Алиса может также попытаться смоше н-ничать, выбрав x, которое не является взаимно простым с p-1, но Боб обнаружит это на этапе (6).

Боб может смошенничать, если h и t не являются примитивными элементами в поле in GF(p), но Алиса сможет легко проверить это после этапа ( 2), так как ей известно разложение p-1 на простые множители.

Удачным в этом протоколе является то, что если Алиса и Боб захотят бросить несколько монет, он7и смогут использовать одни и те же значения p h и t. Алиса просто генерирует новое x, и протокол продолжается с этапа

Бросание "честной"монеты с помощью целых чисел Блюма

В протоколе бросания монеты можно использовать челые числа Блюма .

(1)Алиса генерирует целое число Блюма n, случайное x, взаимно простое с n, x0 = x2 mod n и x1 = x02 mod n. Она посылает Бобу n и x1.

(2)Боб угадывает, четным или нечетным является x0.

(3)Алиса посылает x Бобу.

(4)Боб проверяет, что n является целым числом Блюма (Алиса нужно передать Бобу множители n и доказательства того, что они являются простыми , или выполнить некоторый протокол с нулевым знанием, убе ж-дающий Боба, что n - это целое число Блюма), и что x0 = x2 mod n и x1 = x02 mod n. Если все проверки выполняются, и Боб угадал правильно, он выигрывает бросок .

Это важно, чтобы n было числом Блюма. Иначе Алиса сможет найти такое x0, что x02 mod n = x02 mod n=xb где x0 также является квадратичным остатком . Если бы x0 был четным, а x0 - нечетным (или наоборот), Алиса могла бы мошенничать.

23.8 Однонаправленные сумматоры

Существует простая функция однонаправленного сумматоры [116] (см. раздел 4.12.): A(x,-, y) = x,-y mod n

Числа n (являющееся произведением двух простых чисел) и x0 должны быть заранее согласованы. Тогда суммированием y1, y2 и y3 будет

((x0yq mod n)y2 mod n)y3 mod n

Это вычисление не зависит от порядка y1, y2 и y3.

23.9 Раскрытие секретов "все или ничего"

Этот протокол позволяет нескольким сторонам (для работы протокола нужно не меньше двух участников ) покупать различные секреты у одного продавца (см. раздел 4.13) [1374, 1175]. Начнем с определения. Возьмем две строки битов, x и y. Фиксированным битовым индексом (fixed bit index, FBI) x и y называется последовательность номеров совпадающих битов этих строк.

Например:

x = 110101001011

y = 101010000110

FBI(x, y) = {1, 4, 5, 11}

(Мы читаем биты справа налево, считая нулевым крайний правый бит .)

Теперь вот как выглядит протокол. Алиса будет продавцом. Боб и Кэрол - покупателями. У Алисы есть k n-битовых секретов: S1, S2, . . . Sk. Боб хочет купить секрет Sb, Кэрол - секрет Sc.

(1)Алиса генерирует пару "открытый ключ/закрытый ключ"и сообщает Бобу (но не Кэрол) открытый ключ. Она генерирует другую пару "открытый ключ/закрытый ключ"и сообщает Кэрол (но не Бобу) открытый ключ.

(2)Боб генерирует k n-битовых случайных чисел, B1, B2, . . . Bk, и сообщает их Кэрол. Кэрол генерирует k n-битовых случайных чисел, C1, C2, . . . Ck, и сообщает их Бобу.

(3)Боб шифрует Cb (напомним, он хочет купить секрет Sb) открытым ключом, полученным от Алисы. Он вычисляет FBI для Cb и только что зашифрованного результата. Он посылает этот FBI Кэрол.

Кэрол шифрует Bc (напомним, она хочет купить секрет Sc) открытым ключом, полученным от Алисы. Она вычисляет FBI для Bc и только что зашифрованного результата. Она посылает этот FBI Бобу.

(4) Боб берет каждое из n-битовых чисел B1, B2, . . . Bk и заменяет каждый бит, номера которого нет в FBI, полученном от Кэрол, его дополнением. Он посылает этот новый список n-битовых чисел B2, . . . Bk

Кэрол берет каждое из n-битовых чисел C1, C2, . . . Ck и заменяет каждый бит, номера которого нет в FBI, полученном от Боба, его дополнением. Она посылает этот новый список n-битовых чисел C1, C2, . . . Ck Алисе.

(5)Алиса расшифровывает все C,- закрытым ключом Боба, получая k n-битовых чисел C"1, C"2, . . . C"k. Она вычисляет S © C" для i = 1, . . . k, и посылает результаты Бобу.

Алиса расшифровывает все Bi закрытым ключом Кэрол, получая k n-битовых чисел B"2, . . . B"k. Она вычисляет Si © B"i для i = 1, . . . k, и посылает результаты Кэрол.

(6)Боб вычисляет Sb, выполняя XOR Cb и b-го числа, полученного от Алисы. Кэрол вычисляет Sc, выполняя XOR Bc и c-го числа, полученного от Алисы..

Все так сложно. Поясним эти долгие действия на примере .

У Алисы есть для продажи восемь 12-битовых секретов : S1 = 1990, S2 = 471, S3 = 3860, S4 = 1487, S5 = 2235, S6 = 3751, S7 = 2546 и S8 = 4043. Боб хочет купить S7, а Кэрол - S2.

(1)Алиса использует алгоритм RSA. В диалоге с Бобом она использует следующую пару ключей : n = 7387, e = 5145 и d = 777, а в диалоге с Кэрол - n = 2747, e = 1421 и d = 2261. Она сообщает Бобу и Кэрол их открытые ключи.

(2)Боб генерирует восемь 12-битовых чисел, B1= 743, B2= 1988, B3= 4001, B4= 2942, B5= 3421, B6= 2210, B7=2306 и B8= 222, и сообщает их Кэрол. Кэрол генерирует восемь 12-битовых чисел, C1= 1708, C2 = 711, C3= 1969, C4 = 3112, C5 = 4014, C6 = 2308, C7 = 2212 и C8 = 222, и сообщает их Бобу.

(3)Боб хочет купить S7, поэтому он открытым ключом, выданным Алисой, шифрует C7. 22125145 mod 7387 = 5928

Теперь:

2212=0100010100100

5928 = 1011100101000

Следовательно, FBI этих двух чисел равен {0, 1, 4, 5, 6}. Он посылает его Кэрол.

Кэрол хочет купить S2, поэтому она открытым ключом, выданным Алисой, шифрует B2 и вычисляет FBI B2 и результата шифрования. Она посылает Бобу {0, 1, 2, 6, 9, 10}.

(4)Боб берет B1, B2, . . . B8 и заменяет каждый бит, индекс которого отсутствует в наборе {0, 1, 2, 6, 9, 10} его дополнением. Например:

B2= 111111000100 = 1988

B2 = 011001111100 = 1660

Он посылает B2, . . . B8 Алисе.

Кэрол берет C1, C2, . . . C8 и заменяет каждый бит, индекс которого отсутствует в наборе {0, 1, 4, 5, 6}его дополнением. Например:

C7 = 0100010100100 = 2212

C7 = 1011100101000 = 5928

Она посылает C1, C2, . . . C8 Алисе.

(5)Алиса расшифровывает все Ci закрытым ключом Боба и выполняет XOR результатов с Si. Например, для

5 9 2 8 777 mod 7387 = 2212; 2546 © 2212 = 342 Она посылает результат Бобу.

Алиса расшифровывает все Bi закрытым ключом Кэрол и выполняет XOR результатов с Si. Например, для i = 2:

166 02261 (mod 2747) = 1988; 471 © 1988 = 1555 Она посылает результат Кэрол.

(6)Боб вычисляет S7, выполняя XOR C7 и седьмого числа, полученного им от Алисы: