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

(3).

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

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

(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=xi, где 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-битовых случайных чисел, В1, В2, . . . Sk, и сообщает их Кэрол. Кэрол генерирует k n-битовых случайных чисел, C1, C2, . . . Ck, и сообщает их Бобу.

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

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

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

Алисе.

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

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

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

(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-битовых чисел, С1= 1708, С2 = 711, С3= 1969, С4 = 3112, С5 = 4014, С6 = 2308, С7 = 2212 и С8 = 222, и сообщает их Бобу.

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

Теперь:

2212=0100010100100

5928 = 1011100101000

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

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

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

B2= 111111000100 = 1988

B2 = 011001111100 = 1660

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

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

С7 = 0100010100100 = 2212

С7 = 1011100101000 = 5928

Она посылает С1, С2, . . . С8 Алисе.

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

, = 7:

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

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

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

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

2212 © 342=2546

Кэрол вычисляет S2, выполняя XOR В2 и второго числа, полученного ей от Алисы. 1988 © 1555 = 471

Протокол работает для любого количества покупателей . Если Боб, Кэрол и Дэйв хотят купить секреты, Алиса выдает каждому покупателю два открытых ключа, по одному на каждого другого покупателя . Каждый покупатель получает набор чисел от каждого другого покупателя . Затем они выполняют протокол с Алисой для каждого из своих наборов номеров и выполняют XOR всех полученных от Алисы результатов, получая свои секр е-ты. Более подробно это описано в [1374, 1175].

К сожалению, пара нечестных участников могут смошенничать . Алиса и Кэрол, действуя на пару, могут легко понять, какой секрет получил Боб: если они знают FBI Cb и алгоритм шифрования Боба, они могут подыскать такое b, что у Cb будет правильный FBI. А Боб и Кэрол, действуя вместе, могут легко заполучить все секреты Алисы.

Если вы считаете, что участники честны, можно использовать протокол попроще [389].

(1) Алиса шифрует все секреты RSA и посылает их Бобу: Ci = Si" mod n

(2) Боб выбирает свой секрет Cb, генерирует случайное число r и посылает Алисе. C = Cbre mod n

(3) Алиса посылает Бобу P = mod n

(4) Боб вычисляет P

Sb = Pr-1 mod n

Если участники могут жульничать, Боб может доказать с нулевым знанием, что он знает некоторое r, такое что C = Cbre mod n, и хранить в b секрете, пока Алиса не передаст ему на этапе (3) P [246).

23.10 Честные и отказоустойчивые криптосистемы

Честная схема Diffie-Hellman

Честные криптосистемы представляют собой программный способ условного вручения документов (см. раздел 4.14). Этот пример взят из работ Сильвии Микали (Silvia Micali) [1084, 1085]. Он запатентован [1086, 1087].

В базовой схеме Diffie-Hellman группа пользователей использует общее простое число p и генератор g. Закрытым ключом Алисы является s, а ее открытым ключом t = gs mod Вот как сделать схему Diffie-Hellman честной (в этом примере используется пять доверенных лиц ).

(1) Алиса выбирает пять целых чисел, s1, s2, s3, s4, s5, меньших p-1. Закрытым ключом Алисы является s = (s1+ s2+ s3+ s4+ s5) mod p-1

а ее открытым ключом t = gs mod p

Алиса также вычисляет

ti =gsi mod p, для i = 1, . . . 5.

Открытыми частями Алисы являются ti, а закрытыми - si.

(2) Алиса посылает закрытую и соответствующую открытую части каждому доверенному лицу . Например, она посылает s1 и t2 доверенному лицу 1. Она посылает t в KDC.

(3) Каждое доверенное лицо проверяет, что

ti = gsi mod p

Если это так, доверенное лицо подписывает ti и посылает его в KDC. Доверенное лицо сохраняет si в безопасном месте.

(4) Получив все пять открытых частей, KDC проверяет, что