Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 54 из 78

23.15 Вероятностное шифрование
Понятие вероятностного шифрования было изобретено Шафи Голдвассером (Shafi Goldwasser) и Сильви- ей Микали [624]. Хотя их теория позволяет создать самую безопасную из изобретенных криптосистем , ранняя реализации была неэффективной [625]. Но более поздние реализации все изменили .
Идеей вероятностного шифрования является устранение утечки информации в криптографии с открытыми ключами. Так как криптоаналитик всегда может расшифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифротекст C = E
K
(M), и он пытается получить открытый текст M, он может выбрать случайное сообщение M' и зашифровать его: C' = E
K
(M'). Если
C' = C, то он угадал правильный открытый текст. В противном случае он делает следующую попытку .

Кроме того, вероятностное шифрование позволяет избежать даже частичной утечки информации об ориг и- нальном сообщении. При использовании криптографии с открытыми ключами криптоаналитик иногда может узнать кое-что о битах: XOR 5-го, 17-го и 39-го битов равно 1, и т.п.. При вероятностном шифровании остается скрытой и такая информация.
Таким способом можно извлечь не много информации, но потенциально возможность криптоаналитика расшифровывать случайные сообщения вашим открытым ключом может создать определенные проблемы . Ка- ждый раз, шифруя сообщение, криптоаналитик может извлечь немного информации . Никто не знает, насколько значительна эта информация.
Вероятностное шифрование пытается устранить эту утечку . Цель этого метода состоит в том, чтобы ни в ы- числения, проводимые над шифротекстом, ни проверка любых других открытых текстов не смогли дать кри п- тоаналитику никакой информации о соответствующем откр ытом тексте.
При вероятностном шифровании алгоритм шифромания является вероятностным, а не детерминированным .
Другими словами, многие шифротексты при расшифровке дают данный открытый текст , и конкретный шифро- текст, используемый в любом конкретном шифровании, выбирается случайным образом .
C
1
= E
K
(M), C
2
= E
K
(M), C
3
= E
K
(M), . . . C
i
= E
K
(M)
M = D
K
(C
1
) = D
K
(C
2
) = D
K
(C
3
) = . . . = D
K
(C
i
)
При вероятностном шифровании криптоаналитику больше не удастся шифровать произвольные открытые тексты в поисках правильного шифротекста . Для иллюстрации пусть у криптоаналитика есть шифротекст C
i
=
E
K
(M). Даже если он праильно угадает M, полученный при шифровании E
K
(M) результат будет совершенно дру- гим шифротекстом C: C
j
. Сравнивая C
i и C
j
, он не может по их совпадению определить правильность своей д о- гадки.
Это поразительно. Даже если у криптоаналитика есть открытый ключ шифрования, открытый текст и ши ф- ротекст, он не может без закрытого ключа дешифрирования доказать, что шифротекст является результатом шифрования конкретного открытого текста . Даже выполнив исчерпывающий поиск, он может доказать только,
что каждый возможный открытый текст является возможным открытым текстом .
В этой схеме шифротекст всегда будет больше открытого текста . Этого невозможно избежать, это является результатом того, что многие шифротексты расшифровываются в один и тот же открытый текст . В первой схеме вероятностного шифрования [625] шифротекст получался настолько больше открытого текста, что он был бе с- полезным.
Однако Мануэль Блюм (Manual Blum) и Голдвассер (Goldwasser) получили эффективную реализацию веро- ятностного шифрования с помощью генератора псевдослучайных битов Blum Blum Shub (BBS), описанного в разделе 17.9 [199].
Генератор BBS основан на теории квадратичных остатков . Существуют два простых числа, p и q, конгруэнт- ных 3 по модулю 4. Это закрытый ключ. Их произведение, pq = n, является открытым ключом. (Запомните свои p и q, безопасность схемы опирается на сложность разложения n на множители.)
Для шифрования сообщения M сначала выбирается случайное x, взаимно простое с n. Затем вычисляется x
0
= x
2
mod n x
0
служит стартовой последовательностью для генератора псевдослучайных битов BBS, а выход генератора используется в качестве потокового шифра . Побитно выполняется XOR M с выходом генератора. Генератор выдает биты b i
(младший значащий бит x i
, где x i
= x i-1 2
mod n), поэтому
M=M
1
, M
2
, M
3
, . . . M
t c = M
1
? b
1
, M
2
? b
2
, M
3
? b
3
, . . . M
t
? b t
где t - это длина открытого текста
Добавьте последнее вычисленное значение, x t
, к концу сообщения, и дело сделано.
Расшифровать это сообщение можно только одним способом - получить x
0
и с этой стартовой последова- тельностью запустить генератор BBS, выполняя XOR выхода с шифротекстом. Так как генератор BBS безопасен влево, значение x t
бесполезно для криптоаналитика. Только тот, кому известны p и q, может расшифровать со- общение. Вот как на языке C выглядит алгоритм получения x
0
из x t
:
int xO (int p, int q, int n, int t, int xt) {
int a, b, u, v, w, z;
/* мы уже знаем, что НОД(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;
}
При наличии x
0
дешифрирование несложно. Просто задайте стартовую последовательность генератора BBS
и выполните XOR результата с шифротекстом.
Эту схему можно сделать еще быстрее, используя все известные безопасные биты x i
, а не только младший значащий бит. С таким улучшением вероятностное шифрование 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 процентам .
Поляризацию можно измерить в любой системе координат: двух направлениях, расходящихся под прямым углом. Примерами систем координат являются прямоугольная - горизонтальное и вертикальное направления - и

диагональная - левая и правая диагонали . Если импульс фотонов поляризован в заданной системе координат, то при измерении в той же системе координат вы узнаете поляризацию . При измерении в неправильной системе координат, вы получите случайный результат. Мы собираемся использовать это свойство для генерации секре т- ного ключа:
(1) Алиса посылает Бобу последовательность фотонных импульсов . Каждый из импульсов случайным обра- зом поляризован в одном из четырех направлений: горизонтальном, вертикальном, лево- и праводиаг о- нальном.
Например, Алиса посылает Бобу:
| | / — \ — | — /
(2) У Боба есть детектор поляризации. Он может настроить свой детектор на измерение прямоугольной или диагональной поляризации. Одновременно мерить и ту, и другую у него не получится, ему не позволит квантовая механика. Измерение одной поляризации не даст измерить другую . Итак, он устанавливает свои детекторы произвольным образом:
X + + X X X + X + +
Теперь, если Боб правильно настроит свой детектор , он зарегистрирует правильную поляризацию . Если он настроит детектор на измерение прямоугольной поляризации, и импульс будет поляризован прямоугольно ,
он узнает, какую поляризацию фотонов выбрала Алиса. Если он настроит детектор на измерение диаг о- нальной поляризации, а импульс будет поляризован прямоугольно, то результат измерения будет случа й- ным. Боб не сможет определить разницу. В приведенном примере он может получить следующий резул ь- тат:
/ | — \ / \ — / — |
(3) Боб сообщает Алисе по незащищенному каналу, какие настройки он использовал .
(4) Алиса сообщает Бобу, какие настройки были правильными . В нашем примере детектор был правильно ус- тановлен для импульсов 2, 6, 7 и 9.
(5) Алиса и Боб оставляют только правильно измеренные поляризации. В нашем примере они оставляют:
* | * * * \ — * — *
С помощью заранее приготовленного кода Алиса и Боб преобразуют в биты эти результаты измерений поляризации. Например, горизонтальная и леводиагональная могут означать единицу, а вертикальная и праводиагональная - ноль. В нашем примере они оба получат:
0 0 1 1
Итак, Алиса и Боб получили четыре бита. С помощью этой системы они могут генерировать столько битов,
сколько им нужно. В среднем Боб правильно угадывает в 50 процентах случаев , поэтому для генерации n битов
Алисе придется послать 2n фотонных импульсов. Они могут использовать эти биты как секретный ключ си м- метричного алгоритма или обеспечить абсолютную безопасность, получив достаточно битов для использования в качестве одноразового блокнота.
Замечательным является то, что Ева не сможет подслушать. Как и Бобу, ей нужно угадать тип измеряемой поляризации, и, как и у Боба, половина ее догадок будет неправильной . Так как неправильные измерения изме- няют поляризацию фотонов, то при подслушивании она неминуемо вносит ошибки в передачу . Если это так,
Алиса и Боб получат различные битовые последовательности . Итак, Алиса и Боб заканчивают протокол подоб- ными действиями:
(6) Алиса и Боб сравнивают несколько битов своих строк . По наличию расхождений они узнают о подсл у- шивании. Если строки не отличаются, то они отбрасывают использованные для сравнения биты и и с- пользуют оставшиеся.
Улучшения этого протокола позволяют Алисе и Боб использовать свои биты даже в присутствии Евы [133,
134, 192]. Они могут сравнивать только четность битовых подмножеств. Тогда, если не обнаружено расхожд е- ний, им придется отбросить только один бит подмножества. Это обнаруживает подслушивание с вероятностью
50 процентов, но если они сверят таким образом n различных битовых подмножеств, вероятность Евы подсл у- шать и остаться незамеченной будет равна 1/2
n
В квантовом мире не бывает пассивного подслушивания. Если Ева попытается раскрыть все биты, она об я- зательно разрушит канал связи.
Бенне и Брассар построили работающую модель квантового распределения ключей и обменялись безопа с- ными битами на оптической скамье. Последнее, что я слышал, было сообщение о том, что в British Telecom по-

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

Часть 18
Реальный мир

Глава 24
Примеры реализаций
Одно дело разрабатывать протоколы и алгоритмы, и совсем другое дело встраивать их в операционные си с- темы. В теории практика и теория не отличимы, но на практике между ними огромные различия . Часто идеи замечательно выглядят на бумаге, но не работают в реальной жизни . Может быть слишком велики требования к скорости канала, может быть протокол слишком медлителен . Некоторые из вопросов использования криптогр а- фии рассматриваются в главе 10, в этой главе обсуждаются примеры того, как криптографические алгоритмы реализуются на практике.
24.1 Протокол управления секретными ключами компании IBM
В конце 70-х годов IBM, используя только симметричную криптографию, разработала законченную систему управления ключами для передачи данных и безопасности файлов в компьютерных сетях [515, 1027]. Не так важны реальные механизмы протокола, как его общая философия : за счет автоматизации генерации, распред е- ления, установки, хранения, изменения и разрушения ключей этот протокол далеко продвинулся, обеспечивая безопасность лежащих в его основе криптографических алгоритмов .
Этот протокол обеспечивает три вещи: безопасную связь между сервером и различными терминалами , безо- пасное хранение файлов на сервере и безопасную связь между серверами. Протокол не обеспечивает настоящего прямого соединения терминал-терминал, хотя его модификация может реализовать такую возможность .
Каждый сервер сети подключен к криптографической аппаратуре , которая выполняет все шифрование и де- шифрирование. У каждого сервера есть Главный ключ (Master Key), KM
0
, и два варианта, KM
1
и KM
2
, кото- рые являются упрощенными вариантами KM
0
. Эти ключи используются для шифрования других ключей и для генерации новых ключей. У каждого терминала есть Главный ключ терминала (Master Terminal Key), KMT,
который используется для обмена ключами с другими термин алами.
KMT хранятся на серверах, зашифрованные ключом KM
1
. Все остальные ключи, например, используемые для шифрования файлов ключей (они называются KNF), хранятся в зашифрованной форме, закрытые ключом
KM
2
. Главный ключ KM
0
хранится в энергонезависимом модуле безопасности . Сегодня это может быть либо ключ в ПЗУ, либо магнитная карточка, или ключ может вводиться пользователем с клавиатуры (возможно как текстовая строка, преобразуемая в ключ). KM
1
и KM
2 не хранятся где-нибудь в системе, а, когда понадобится,
вычисляются по KM
0
. Сеансовые ключи для связи между серверами генерируются на сервере с помощью псе в- дослучайного процесса. Аналогичным образом генерируются ключи для шифрования хранимых файлов (KNF).
Сердцем протокола служит устойчивый к вскрытию модуль, называемый криптографической аппарату- рой (cryptographic facility). И на сервере, и на терминале все шифрование и дешифрирование происходи именно в этом модуле. В этом модуле хранятся самые важные ключи, используемые для генерации действительных ключей шифрования. После того, как эти ключи записаны, считать их становится невозможным . Кроме того,
они помечены для конкретного использования : ключ, предназначенный для решения одной задачи, не может случайно быть использован для решения другой . Эта концепция векторов управления ключами возможно является самым значительным достижением этой системы . Дональд Дэвис (Donald Davies) Вильям Прайс
(William Price) подробно рассматривают этот протокол управления ключами в [435].
Модификация
Модификацию этой схемы главного и сеансовых ключей можно найти в [1478]. Она построена на базе сете- вых узлов с аппаратурой проверки подлинности ключей, которая обслуживает локальные терминалы . Эта мо- дификация была разработана, чтобы:
— Обезопасить дуплексный канал между двумя пользовательскими терминалами .
— Обезопасить связь с помощью шифрованной почты .
— Обеспечить защиту личных файлов.
— Обеспечить возможность цифровой подписи .
Для связи и передачи файлов между пользователями в этой схеме используются ключи, генерированные в аппаратуре проверки подлинности ключей, отправляемые пользователям после шифрования с помощью главн о- го ключа. Информация о личности пользователя встраивается в ключ, предоставляя доказательство того, что сеансовый ключ используется конкретной парой пользователей . Возможность проверки подлинности ключей является главной в этой системе. Хотя в системе не используется криптография с открытыми ключами , она под- держивает возможность, похожую на цифровую подпись : ключ может быть прислан только из конкретного и с- точника и прочитан только в конкретном месте назначения .