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

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

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

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

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

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

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

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

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

У2 = Db{15+2) = 18

У3 = Db{15+3) =2

У4 = 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 ), то i > j.

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

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

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

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

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

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

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

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

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

С1 = Ek(M), С2 = Ek(M), С3 = Ek(M), . . . С, = Ek(M)

M = Dk(C1) = Dk(C2) = Dk(C3) = . . . = Dk(C,)

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

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

В этой схеме шифротекст всегда будет больше открытого текста . Этого невозможно избежать, это является результатом того, что многие шифротексты расшифровываются в один и тот же открытый текст . В первой схеме вероятностного шифрования [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 с выходом генератора. Генератор выдает биты b; (младший значащий бит x;, где x; = 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);

u = modexp ((p+l)/4, t, p-l); v = modexp ((q+l)/4, t, q-l); w = modexp (xt%p, u, p); z = modexp (xt%p, v, q); return (b*q*w + a*p*z) % n;

При наличии x0 дешифрирование несложно. Просто задайте стартовую последовательность генератора BBS и выполните XOR результата с шифротекстом.

Эту схему можно сделать еще быстрее, используя все известные безопасные биты xi, а не только младший значащий бит. С таким улучшением вероятностное шифрование Blum-Goldwasser оказывается быстрее RSA и не допускает утечки информации об открытом тексте . Кроме того, можно доказать, что сложность вскрытия этой схемы равна сложности разложения n на множители.

С другой стороны, эта схема совершенно небезопасна по отношению к вскрытию с выбранным шифроте к-стом. По младшим значащим битам правильных квадратичных остатков можно вычислить квадратный корень любого квадратичного остатка. Если это удастся, то удастся и разложение на множители . Подробности можно найти в [1570, 1571, 35, 36].

23.16 Квантовая криптография

Квантовая криптография вводит естественную неопределенность квантового мира. С ее помощью можно создавать линии связи, которые невозможно послушать, не внося помех в передачу . Законы физики надежно защищают такой квантовый канал, даже если подслушивающий может предпринимать любые действия, даже если он имеет доступ к неограниченной вычислительной мощности, даже если P = NP. Шарль Бенне (Charles Bennett), Жиль Брассар (Gilles Brassard), Клод Крепо (Claude Crepeau) и другие расширили эту идею, описав квантовое распределение ключей, квантовое бросание монеты, квантовое вручение бита , квантовую передачу с забыванием и квантовые вычисления с несколькими участниками . Описание их результатов можно найти в [128, 129, 123, 124, 125, 133, 126, 394, 134, 392, 243, 517, 132, 130, 244, 393, 396]. Лучшим обзором по квантовой криптографии является [131]. Другим хорошим нетехническим обзором может служить [1651]. Полную библиографию по квантовой криптографии можно найти в [237].

Эти идеи так и остались бы предметом обсуждения фанатиков криптографии , но Бенне и Брассар разработали действующую модель [127, 121, 122]. Теперь у нас есть эксйермленотйльнал квантовая криптография.

Итак устройтесь поудобнее, налейте себе чего-нибудь выпить и расслабьтесь. Я попробую объяснить вам, что это такое.

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

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

Пусть у вас есть импульс горизонтально поляризованных фотонов . Если они попробуют пройти через горизонтальный фильтр, то у них у всех прекрасно получится. Если медленно поворачивать фильтр на 90 градусов, количество пропускаемых фотонов будет становиться все меньше и меньше, и наконец ни один фотон не про й-дет через фильтр. Это противоречит здравому смыслу. Кажется, что даже незначительный поворот фильтра должен остановить все фотоны, так как они горизонтально поляризованы . Но в квантовой механике каждая частица с определенной вероятностью может изменить свою поляризацию и проскочить через фильтр . Если угол отклонения фильтра невелик, эта вероятность высока, а если он равен 90 градусам, то вероятность равна нулю . А если угол поворота фильтра равен 45 градусам , вероятность фотона пройти фильтр равна 50 процентам .

Поляризацию можно измерить в любой системе координат: двух направлениях, расходящихся под прямым углом. Примерами систем координат являются прямоугольная - горизонтальное и вертикальное направления - и