s = td/k mod n (4) Результатом является s = md mod n

Это можно легко показать

td - (mke)d - mdk (mod n), поэтому td/k = mdk/k - md (mod n).

Чаум придумал целое семейство более сложных алгоритмов слепой подписи [320, 324], называемых неожиданными слепыми подписями. Схемы этих подписей сложнее, но они дают больше возможностей .

23.13Передача с забыванием

В этом протоколе, предложенном Майклом Рабином (Michael Rabin) [1286], Алиса с вероятностью 50 процентов удается передать Бобу два простых числа, p и q. Алиса не знает, успешно ли прошла передача (См. раздел 5.5.) (Этот протокол можно использовать для передачи Бобу любого сообщения с 50-процентной вероятностью успешной передачи, если p и q раскрывают закрытый ключ RSA.)

(1)Алиса посылает Бобу произведение двух простых чисел: n = pq.

(2)Боб выбирает случайное число x, меньшее n и взаимно простое с n. Он посылает Алисе: a = x2 mod n

(3)Алиса, зная p и q, вычисляет четыре квадратных корня a: x, n-x, у и n-y. Она случайным образом выбирает любой из этих корней и посылает его Бобу.

(4)Если Боб получает у или n-у, он может вычислит наибольший общий делитель x+у и n, которым будет либо p, либо q. Затем, конечно же, n/p = q. Если Боб получает x или n-x, он не может ничего вычислить.

У этого протокола может быть слабое место : возможна ситуация, когда Боб может вычислить такое число a, что при известном квадратном корне a он сможет все время раскладывать n на множители.

23.14Безопасные вычисления с несколькими участниками

Этот протокол взят из [1373]. Алиса знает целое число i, а Боб - целое число j. Алиса и Боб вместе хотят узнать, что правильно - i<j или i>j, но ни Алиса, ни Боб не хочет раскрыть свое число партнеру. Этот особый случай безопасных вычислений с несколькими участниками (см. раздел 6.2) иногда называют проблемой миллионера Яо [162, 7].

В приводимом примере предполагается, что i и j выбираются из диапазона от 1 до 100. У Боба есть открытый и закрытый ключи.

(1)Алиса выбирает большое случайное число x и шифрует его открытым ключом Боба. c = Eb(x)

(2)Алиса вычисляет c-j и посылает результат Бобу.

(3)Боб вычисляет следующие 100 чисел: у,, = DB(c-i+u), для 1<u<100

DB обозначает дешифрирование закрытым ключом Боба.

Он выбирает большое случайное число p. (Размер p должен быть немного меньше x. Боб не знает x, но Алиса может легко сообщить ему размер x.) он вычисляет следующие 100 чисел:

zu = (Vu mod p), для 1<u<100

Далее он проверяет, что для всех uv

zu - > 2

и что для всех u

0 < zu < p1

Если это не так, то Боб выбирает другое простое число и пробует снова.

(4)Боб посылает Алисе эту последовательность чисел, соблюдая их точный порядок:

zl, z2, . . . zj, zj+1 + 1, zj+2+1, . . . z100+1, p

(5)Алиса проверяет, конгруэнтен ли ,-ый член последовательности x mod p Если это так, она делает вывод, что ,<j В противном случае она решает, что ,> j.

(6)Алиса сообщает Бобу свои выводы.

Проверка, которую Боб выполняет на этапе (3), должна гарантировать, что ни одно число не появится дважды в последовательности, генерированной на этапе (4). В противном случае, если za = zb, Алиса узнает, что a < j < b.

Недостатком этого протокола является то, что Алиса узнает результаты вычислений раньше Боба. Ничто не помешает ей завершить протокол на этапе (5), отказавшись сообщать Бобу результаты . Она даже может солгать Бобу на этапе (6).

Пример протокола

Пусть они используют RSA. Открытым ключом Боба является 7, а закрытым - 23. n = 55. Секретное число Алисы, равно 4, секретное число Боба, j - 2. (Предположим, что числа , и j могут принимать только значения 1, 2, 3 и 4.)

(1)Алиса выбирает x = 39 и c = EB(39) = 19.

(2)Алиса вычисляет c-,=19-4=15. Она посылает 15 Бобу.

(3)Боб вычисляет следующие четыре числа: y1 = Db{15+1) =26

y2 = Db{15+2) = 18

y3 = Db{15+3) =2

y4 = Db{15+4) = 39

Он выбирает p = 31 и вычисляет:

z1 = (26 mod 31) = 26

z2 = (18 mod 31) =18

z3 = (2 mod 31) = 2

Z4 = (39 mod 31) = 8

Он выполняет все проверки и убеждается, что последовательность правильна .

(4)Боб посылает Алисе эту последовательность чисел, соблюдая их порядок : 26, 18, 2+1, 8+1, 31, т.е., 26, 18, 3, 9, 31

(5)Алиса проверяет, конгруэнтно ли четвертое число X mod p Так как 9 Ф 39 (mod 31 ), то , > j.

(6)Алиса сообщает об этом Бобу.

Этот протокол можно использовать для создания намного более сложных протоколов . Группа людей может проводить секретный аукцион по сети . Они логически упорядочивают себя по кругу и, с помощью попарных сравнений, определяют, кто предложил большую цену . Чтобы помешать людям уже изменять сделанные предложения в середине аукциона должен использоваться какой-то протокол вручения битов. Если аукцион проводится по голландской системе, то предложивший наивысшую цену получает предмет за предложенную цену . Если аукцион проводится по английской системе, то он получает предмет за вторую высшую цену. (Это может быть выяснено во время второго круга попарных сравнений .) Аналогичные идеи применимы при заключении сделок, переговорах и арбитраже.

23.15 Вероятностное шифрование

Понятие вероятностного шифрования было изобретено Шафи Голдвассером (Shafi Goldwasser) и Сильвией Микали [624]. Хотя их теория позволяет создать самую безопасную из изобретенных криптосистем , ранняя реализации была неэффективной [625]. Но более поздние реализации все изменили.

Идеей вероятностного шифрования является устранение утечки информации в криптографии с открытыми ключами. Так как криптоаналитик всегда может расшифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифротекст C = E(M), и он пытается получить открытый текст M, он может выбрать случайное сообщение M и зашифровать его: C = EK(M). Если C = C, то он угадал правильный открытый текст. В противном случае он делает следующую попытку .

Кроме того, вероятностное шифрование позволяет избежать даже частичной утечки информации об ориг и-нальном сообщении. При использовании криптографии с открытыми ключами криптоаналитик иногда может узнать кое-что о битах: XOR 5-го, 17-го и 39-го битов равно 1 , и т.п.. При вероятностном шифровании остается скрытой и такая информация.

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

Вероятностное шифрование пытается устранить эту утечку. Цель этого метода состоит в том, чтобы ни в ы-числения, проводимые над шифротекстом, ни проверка любых других открытых текстов не смогли дать кри п-тоаналитику никакой информации о соответствующем откр ытом тексте.

При вероятностном шифровании алгоритм шифромания является вероятностным, а не детерминированным . Другими словами, многие шифротексты при расшифровке дают данный открытый текст , и конкретный шифро-текст, используемый в любом конкретном шифровании, выбирается случайным образом .

C1 = EKM), C2 =C3 =. . . Ci =

M = Dk(C1) = Dk(C2) = Dk(C3) = . . . = ZMC)

При вероятностном шифровании криптоаналитику больше не удастся шифровать произвольные открытые тексты в поисках правильного шифротекста. Для иллюстрации пусть у криптоаналитика есть шифротекст Ci = EKM). Даже если он праильно угадает M, полученный при шифровании EKM) результат будет совершенно другим шифротекстом C: Cj. Сравнивая Ci и Cj, он не может по их совпадению определить правильность своей д о-гадки.

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

В этой схеме шифротекст всегда будет больше открытого текста . Этого невозможно избежать, это является результатом того, что многие шифротексты расшифровываются в один и тот же открытый текст . В первой схеме вероятностного шифрования [625] шифротекст получался настолько больше открытого текста, что он был бе с-полезным.

Однако Мануэль Блюм (Manual Blum) и Голдвассер (Goldwasser) получили эффективную реализацию вероятностного шифрования с помощью генератора псевдослучайных битов Blum Blum Shub (BBS), описанного в разделе 17.9 [199].

Генератор BBS основан на теории квадратичных остатков. Существуют два простых числа, p и q, конгруэнтных 3 по модулю 4. Это закрытый ключ. Их произведение, pq = n, является открытым ключом. (Запомните свои p и q, безопасность схемы опирается на сложность разложения n на множители.)

Для шифрования сообщения M сначала выбирается случайное x, взаимно простое с n. Затем вычисляется

x0 = x2 mod n

x0 служит стартовой последовательностью для генератора псевдослучайных битов BBS, а выход генератора используется в качестве потокового шифра. Побитно выполняется XOR M с выходом генератора. Генератор выдает биты bi (младший значащий бит xi, где xi = xi-12 mod n), поэтому

M=M1, M2, M3, . . . Mt

c = M1 © b1, M2 © b2, M3 © b3, . . . Mt © bt

где t - это длина открытого текста

Добавьте последнее вычисленное значение, xt, к концу сообщения, и дело сделано.

Расшифровать это сообщение можно только одним способом - получить x0 и с этой стартовой последовательностью запустить генератор BBS, выполняя XOR выхода с шифротекстом. Так как генератор BBS безопасен влево, значение xt бесполезно для криптоаналитика. Только тот, кому известны p и q, может расшифровать сообщение. Вот как на языке C выглядит алгоритм получения x0 из xt:

int xO (int p, int q, int n, int t, int xt) { int a, b, u, v, w, z;

/* мы уже знаем, что HOfl(p,q) == 1 */ (void)extended euclidian(p, q, &a, &b);