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

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

(1) Алиса выбирает х — 39 и с — Е_в(39) = 19.

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

(3) Боб вычисляет следующие четыре числа: y₁ = D_B{l5+l) =26

y₂ = D_B{l5+2) = l8

y₃ = D_B {15+3) =2

y₄ = D_B{l5+4) = 39

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

_Zl= (26 mod 31) = 26

z₂ = (18 mod 31) =18

z₃ = (2 mod 31) = 2

z₄ = (39 mod 31) = 8

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

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

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

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

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

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

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

Идеей вероятностного шифрования является устранение утечки информации в криптографии с открытыми ключами. Так как криптоаналитик всегда может расшифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифротекст С = ЕцЦМ), и он пытается получить открытый текст М, он может выбрать случайное сообщение М' и зашифровать его: С" = Е_Е{М'). Если С" = С, то он угадал правильный открытый текст. В противном случае он делает следующую попытку.

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

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

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

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

d = ЕцЦЩ С_г = ЕцЦЩ С₃ = ЕцЦМ),... С, ■ = ЕцЦМ)

М = AdTi) = ЩС₂) = Дс(Сз) =... = ЩС)

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

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

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

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

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

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

x₀ = x² modH

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

м=м_ъ м₂, м₃,... м,

с = М_х © Ь_и М₂ © Ь₂, М₃ © из, • • • М,® Ъ,

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

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

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

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-1); v = modexp ((q+l)/4, t, q-1); w = modexp (xt%p, u, p); z = modexp (xt%p, v, q); return (b*q*w + a*p*z) % n; }

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

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

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

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

Квантовая криптография вводит естественную неопределенность квантового мира. С ее помощью можно создавать линии связи, которые невозможно послушать, не внося помех в передачу. Законы физики надежно защищают такой квантовый канал, даже если подслушивающий может предпринимать любые действия, даже если он имеет доступ к неограниченной вычислительной мощности, даже если Р = 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 процентам.

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

диагональная - левая и правая диагонали. Если импульс фотонов поляризован в заданной системе координат, то при измерении в той же системе координат вы узнаете поляризацию. При измерении в неправильной системе координат, вы получите случайный результат. Мы собираемся использовать это свойство для генерации секрет­ного ключа:

(1) Алиса посылает Бобу последовательность фотонных импульсов. Каждый из импульсов случайным обра­
зом поляризован в одном из четырех направлений: горизонтальном, вертикальном, лево- и праводиаг о-
нальном.

Например, Алиса посылает Бобу:

| | / — \ —I— /

(2) У Боба есть детектор поляризации. Он может настроить свой детектор на измерение прямоугольной или
диагональной поляризации. Одновременно мерить и ту, и другую у него не получится, ему не позволит
квантовая механика. Измерение одной поляризации не даст измерить другую. Итак, он устанавливает свои
детекторы произвольным образом:

Х+ +ХХХ+Х+ +

Теперь, если Боб правильно настроит свой детектор, он зарегистрирует правильную поляризацию. Если он настроит детектор на измерение прямоугольной поляризации, и импульс будет поляризован прямоугольно, он узнает, какую поляризацию фотонов выбрала Алиса. Если он настроит детектор на измерение диаго­нальной поляризации, а импульс будет поляризован прямоугольно, то результат измерения будет случа й-ным. Боб не сможет определить разницу. В приведенном примере он может получить следующий резул ь-тат:

/ | — \ / \ — / — |

(3) Боб сообщает Алисе по незащищенному каналу, какие настройки он использовал.

(4) Алиса сообщает Бобу, какие настройки были правильными. В нашем примере детектор был правильно ус­тановлен для импульсов 2, 6, 7 и 9.

(5) Алиса и Боб оставляют только правильно измеренные поляризации. В нашем примере они оставляют:

* | * * * \ — * — *

С помощью заранее приготовленного кода Алиса и Боб преобразуют в биты эти результаты измерений поляризации. Например, горизонтальная и леводиагональная могут означать единицу, а вертикальная и праводиагональная - ноль. В нашем примере они оба получат:

0 0 1 1

Итак, Алиса и Боб получили четыре бита. С помощью этой системы они могут генерировать столько битов, сколько им нужно. В среднем Боб правильно угадывает в 50 процентах случаев, поэтому для генерации п битов Алисе придется послать 2и фотонных импульсов. Они могут использовать эти биты как секретный ключ сим­метричного алгоритма или обеспечить абсолютную безопасность, получив достаточно битов для использования в качестве одноразового блокнота.

Замечательным является то, что Ева не сможет подслушать. Как и Бобу, ей нужно угадать тип измеряемой поляризации, и, как и у Боба, половина ее догадок будет неправильной. Так как неправильные измерения изме­няют поляризацию фотонов, то при подслушивании она неминуемо вносит ошибки в передачу. Если это так, Алиса и Боб получат различные битовые последовательности. Итак, Алиса и Боб заканчивают протокол подоб­ными действиями:

(6) Алиса и Боб сравнивают несколько битов своих строк. По наличию расхождений они узнают о подслу­шивании. Если строки не отличаются, то они отбрасывают использованные для сравнения биты и и с-пользуют оставшиеся.

Улучшения этого протокола позволяют Алисе и Боб использовать свои биты даже в присутствии Евы [133, 134, 192]. Они могут сравнивать только четность битовых подмножеств. Тогда, если не обнаружено расхожд е-ний, им придется отбросить только один бит подмножества. Это обнаруживает подслушивание с вероятностью 50 процентов, но если они сверят таким образом п различных битовых подмножеств, вероятность Евы подслу­шать и остаться незамеченной будет равна 1/2".

В квантовом мире не бывает пассивного подслушивания. Если Ева попытается раскрыть все биты, она об я-зательно разрушит канал связи.

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

сылали биты по 10-километровому оптоволокну [276, 1245, 1533]. Они считают, что достижимо и расстояние в 50 километров. Это поражает воображение.