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

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

(1) Алиса генерирует целое число Блюма п, случайное х, взаимно простое с п, х₀ = х² mod пмх= х₀² mod п. Она посылает Бобу и и х_ь

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

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

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

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

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

Существует простая функция однонаправленного сумматоры [116] (см. раздел 4.12.):

А(х„ у) = х,У mod n

Числа п (являющееся произведением двух простых чисел) и х₀ должны быть заранее согласованы. Тогда суммированием у_ъу₂и у₃ будет

((x/^q modnY² тойп)^Уз modn

Это вычисление не зависит от порядка у_ъу₂иу₃.

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

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

Например:

х= 110101001011

у= 101010000110

FBI(je,j;) = {1, 4, 5, 11}

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

Теперь вот как выглядит протокол. Алиса будет продавцом. Боб и Кэрол - покупателями. У Алисы есть к п-битовых секретов: S_h S₂, . . . S_k. Боб хочет купить секрет S_b, Кэрол - секрет S_c.

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

(2) Боб генерирует к и-битовых случайных чисел, В_ъ В₂, . . . В_к, и сообщает их Кэрол. Кэрол генерирует к 71-битовых случайных чисел, C_h С₂, . . . С_к, и сообщает их Бобу.

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

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

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

Алисе.

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

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

Алиса расшифровывает все В', закрытым ключом Кэрол, получая к й-битовых чисел В"_и В"₂, . . . В"_к. Она вычисляет St © В", для i = 1, . . . к, и посылает результаты Кэрол.

(6) Боб вычисляет S_b, выполняя XOR С_ъ и й-го числа, полученного от Алисы.
Кэрол вычисляет S_c, выполняя XOR В_с и с-го числа, полученного от Алисы..

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

У Алисы есть для продажи восемь 12-битовых секретов : & = 1990, S₂ = 471, S₃ = 3860, S₄ = 1487, S₅ = 2235, S₆ = 3751, S₁ = 2546 и S₈ = 4043. Боб хочет купить S₇, а Кэрол - S₂.

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

(2) Боб генерирует восемь 12-битовых чисел, В_г= 743, В₂= 1988, S₃= 4001, В_л= 2942, £₅= 3421, £₆= 2210, £₇=2306 и S₈= 222, и сообщает их Кэрол. Кэрол генерирует восемь 12-битовых чисел, d= 1708, С₂ = 711, С₃= 1969, С₄ = 3112, С₅ = 4014, С₆ = 2308, С₇ = 2212 и С₈ = 222, и сообщает их Бобу.

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

Теперь:

2212 = 0100010100100

5928 = 1011100101000

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

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

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

В₂= 111111000100 = 1988

В'₂ = 011001111100 = 1660

Он посылает В, В'₂, . . . В Алисе.

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

С₇ = 0100010100100 = 2212

С"₇ = 1011100101000 = 5928

Она посылает С, С₂, . . . С Алисе.

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

5928⁷⁷⁷ mod 7387 = 2212; 2546 © 2212 = 342

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

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

для i = 2:

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

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

2212 © 342=2546

Кэрол вычисляет S₂, выполняя XOR В₂ и второго числа, полученного ей от Алисы.

1988 ©1555 = 471

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

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

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

(1) Алиса шифрует все секреты RSA и посылает их Бобу: С, = 5*,^е mod n

(2) Боб выбирает свой секрет С_ь, генерирует случайное число г и посылает Алисе. С = C_br^e mod n

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

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

S_b-PY^l mod n

Если участники могут жульничать, Боб может доказать с нулевым знанием, что он знает некоторое г, такое что С = C_br^e mod п, и хранить в Ъ секрете, пока Алиса не передаст ему на этапе (3) Р' [246).

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