Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
mod p. На этапе (1) Алиса посылает Бобу следующее сообщение Алиса, g r mod p Обратите внимание, что этот открытый ключ не нужно шифровать с помощью P. В общем случае это невер- но, но это так для алгоритма ElGamal algorithm. Подробности в [109]. Боб выбирает случайное число R (для алгоритма ElGamal, независимо от других случайных чисел, выбира е- мых для EKE), и сообщение, которое он посылает Алисе на этапе (2), выглядит так E P (g R mod p, Kg rR mod p) Существующие ограничения на выбор переменных для ElGamal были приведены в разделе 19.6. Реализация EKE с помощью Diffie-Hellman При использовании протокола Diffie-Hellman K генерируется автоматически. Окончательный протокол еще проще. Значения g и n определяются для всех пользователей сети . (1) Алиса выбирает случайное число r A и посылает Бобу A, g r A mod n При использовании Diffie-Hellman Алисе не нужно шифровать с помощью P свое первое сообщение. (2) Боб выбирает случайное число r B и вычисляет K= g r r A B * mod n Он генерирует случайную строку R B , затем вычисляет и посылает Алисе: E Р ( g r B mod n),E K (R B ) (3) Алиса расшифровывает первую половину сообщения Боба, получая g r B mod n. Затем она вычисляет K и использует его для шифрования R B . Она генерирует другую случайную строку R A ,, шифрует обе строки ключом K и посылает результат Бобу. E K (R A ,,R B ) (4) Боб расшифровывает сообщение, получая R A , и R B . Если полученная от Алисы строка R B совпадает с той, которую он посылал ей на этапе (2), он шифрует R A ключом K и посылает результат Алисе. E K (R A ) (5) Алиса расшифровывает сообщение, получая R A . Если полученная от Боба строка R A совпадает с той, кото- рую она посылала Бобу на этапе (3), протокол завершается. Теперь стороны могут обмениваться сообще- ниями, используя K в качестве сеансового ключа . Усиление EKE Белловин (Bellovin) и Мерритт (Merritt) предложили улучшение запросно-ответной части алгоритма , которое позволяет избежать возможного вскрытия при обнаружении криптоаналитиком ста рого значения K. На базовый протокол EKE. На этапе (3) Алиса генерирует другое случайное число S A и посылает Бобу E K (R A , S A ) На этапе (4), Боб генерирует другое случайное число S B и посылает Алисе E K (R A ,,R B ,S B ) Теперь Алиса и Боб могут вычислить истинный сеансовый ключ , S A ? S B . Этот ключ в дальнейшем исполь- зуется для сообщений, которыми обмениваются Алиса и Боб, K используется в качестве ключа обмена ключами. Посмотрим на уровни защиты, предоставляемые EKE. Восстановленное значение S не дает Еве никакой ин- формации о P, так как P никогда не используется для шифрования чего-то такого, что ведет непосредственно к S. Криптоаналитическое вскрытие K также невозможно, K используется только для шифрования случайных данных, а S никогда не шифруется отдельно. Расширенный EKE Протокол EKE страдает одним серьезным недостатком: он требует, чтобы обе стороны знали P. В большин- стве систем авторизации доступа хранятся значения однонаправленной хэш-функции паролей пользователей, а не сами пароли (см. раздел 3.2). Протокол Расширенный EKE (Augmented EKE, A-EKE) использует в варианте EKE на базе Diffie-Hellman значение однонаправленной хэш-функции пароля пользователя в качестве ключа сверхшифрования. Затем пользователь посылает дополнительное сообщение, основанное на реальном пароле, это сообщение удостоверяет заново выбранный сеансовый ключ . Вот как это работает. Как и обычно, Алиса и Боб хотят проверить подлинность друг друга и генерировать общий ключ. Они выбирают какую-нибудь схему цифровой подписи, в которой в качестве закрытого ключа может использоваться любое число, а открытый ключ получается из закрытого, а не генерируется отдельно . Прекрасно подходят алгоритмы ElGamal и DSA. Пароль Алисы P (или, может быть, какое-нибудь простое хэш- значение этого пароля) будет использоваться в качестве закрытого ключа и как P'. (1) Алиса выбирает случайный показатель степени R a и отправляет E Р ( g r B mod n) (2) Боб, который знает только P' и не может получить из него P, выбирает R b и посылает E Р ( g r B mod n) (3) Алиса и Боб вычисляют общий сеансовый ключ K= g r r A B * mod n. Наконец Алиса доказывает, что она сама знает P, а не только P', посылая E K (S P (K)) Боб, который знает K и P', может расшифровать и проверить подпись . Только Алиса могла прислать это со- общение, так как только она знает P. Самозванец, добывший копию файла паролей Боба, может попытаться P, но он не сможет подписать сеансовый ключ . Схема A-EKE не работает с вариантом EKE, использующим открытые ключи, так как в этом протоколе одна сторона выбирает сеансовый ключ и навязывает его другой . Это позволяет взломщику, заполучившему Р', вы- полнить вскрытие "человек в середине". Применения EKE Белловин и Мерритт предлагают использовать этот протокол для безопасной телефонной связи [109]: Предположим, что развернута сеть шифрующих телефонных аппаратов . Если кто-нибудь хочет воспользоваться таким телефоном, то понадобится определенная ключевая информация . Общепринятые решения. . . требуют, чтобы у звонящего был физический ключ. Во многих ситуациях это нежелательно. EKE позволяет использовать короткий, вводимый с клавиат у- ры пароль, обеспечивая гораздо более длинный сеансовый ключ . EKE мог бы быть полезен и для сотовой связи . Мошенничество представляет собой большую проблему сотовой телеф о- нии, EKE может помочь защититься от него (и обеспечить закрытость звонка) за счет продажи телефонов, бесполезных без введения PIN-кода. Так как PIN-код не хранится в телефоне, его невозможно извлечь из украденного экземпляра. Главная сила EKE состоит в том, что криптография с открытыми ключами и симметричная криптография объединяются и усиливают друг друга: В общей перспективе EKE работает как усилитель секретности. То есть, его можно использовать для усиления сравн и- тельно слабых симметричных и асимметричных систем, используемых вместе . Рассмотрим, например, размер ключа, необхо- димый для обеспечения безопасности при использовании обмена ключом - показателем степени . Как показали ЛаМачча (LaMacchia) и Одлыжко (Odlyzko) [934], даже модули с размерами, считавшимися безопасными, (а именно, 192 бита) чувст- вительны к вскрытию, занимающему несколько минут компьютерного времени . Но их вскрытие становится невозможным, если необходимо перед применением вскрытия угадать п ароль. С другой стороны, сложность вскрытия обмена ключами - показателями степени может быть использована для срыва п о- пыток угадать пароль. Возможность вскрытия угадыванием пароля зависит от скорости проверки каждого предположения . Если для выполнения такой проверки необходимо выполнить обмен ключами - показателями степени , то общее время эф- фектно возрастает. EKE запатентован [111]. 22.6 Защишенные переговоры о ключе Эта схема также защищает переговоры о ключе от плохого выбора паролей и вскрытий "человек в середине" [47, 983]. В ней используется хэш-функция двух переменных, обладающая особенным свойством : она часто приводит к столкновениям по первой переменной, и практически никогда - по второй . H'(x,y) = H(H(k,x) mod 2 m , x), где H(k,x) - обычная функция k и x Вот как выглядит этот протокол. Алиса и Боб используют общий секретный пароль P и уже обменялись сек- ретным ключом K, используя обмен ключом Dime-Hellman. Они используют P для проверки, что их сеансовые ключи одинаковы (и что Ева не предприняла вскрытие "человек в середине" ), не позволяя Еве получить P. (1) Алиса посылает Бобу H'(P,K) (2) Боб вычисляет H'(P,K) и сравнивает результат со значением, присланным Алисой . Если они совпадают, он посылает Алисе H'(H(P,K)) (3) Алиса вычисляет H'(H(P,K)) и сравнивает результат со значением, полученным от Боба . Если Ева пытается выполнить вскрытие "человек в середине", она использует один ключ, K 1 , общий с Али- сой, и другой, K 2 , общий с Бобом. Чтобы обмануть Боба на этапе (2), ей придется вычислить общий пароль и затем послать Бобу H'(P,K 2 ). При использовании обычной хэш-функции она может перебирать часто встреча ю- щиеся пароли, пока не угадает правильный , и затем успешно проникнуть в протокол. Но при использовании предлагаемой хэш-функции, многие пароли дают одно и то же значение при хэшировании с ключом K 1 . Поэто- му, когда она находит совпадение, то скорее всего это неправильный пароль, и в этом случае Боба обмануть не удастся. 22.7 Распределение ключа для конференции и секретная широковещательная передача Алиса хочет передать сообщение M сразу нескольким получателям. Однако она совсем не хочет, чтобы кто угодно смог прочесть его. В действительности, ей нужно, чтобы только получатели из определенного подмнож е- ства могли правильно раскрыть M. У всех остальных должна получиться чепуха . Алиса может использовать для каждого получателя отличный ключ (секретный или открытый) . Она шифру- ет сообщение каким-нибудь случайным ключом K. Затем она шифрует копию K каждым из ключей выбранных получателей сообщения. Наконец она широковещательно посылает зашифрованное сообщение , а затем все за- шифрованные K. Слушающий передачу Боб либо пытается расшифровать все K своим секретным ключом, пы- таясь найти правильный, либо, если Алиса не забыла перечислить получателей своего сообщения, он ищет свое имя, сопровождаемое зашифрованным ключом . Также будет работать и ранее рассмотренная криптография с несколькими ключами. Другой способ предлагается в [352]. Сначала каждый из получателей договаривается с Алисой об общем для них двоих ключе, который длиннее любого возможного шифрованного сообщения . Все эти ключи должны быть взаимно простыми. Она шифрует сообщение случайным ключом K. Затем она вычисляет одно целое число R, которое по модулю секретного ключа конгруэнтно K, если этот секретный ключ предполагается использовать для расшифровки сообщения, и конгруэнтно нулю в противном сл учае. Например, если Алиса хочет, чтобы секрет получили Боб, Кэрол и Эллен, но не Дэйв и Фрэнк, она шифрует сообщение ключом K и затем вычисляет такое R, что R ? K (mod K B ) R ? K (mod K C ) R ? 0 (mod K D ) R ? K (mod K E ) R ? 0 (mod K F ) Это простая алгебраическая проблема, которая легко может быть решена Алисой . Когда это сообщение бу- дет принято получателями, они вычислят значение полученного ключа по модулю их секретного ключа . Те, ко- му предназначалось это сообщение, в результате вычисления получат нужный ключ. В противном случае р е- зультатом будет 0. Еще один, третий, путь, использующий пороговую схему (см. раздел 3.7), предлагается в [141]. Как и в дру- гих способах каждый потенциальный получатель получает секретный ключ . Этот ключ является тенью в еще не созданной пороговой схеме. Алиса сохраняет ряд секретных ключей для себя, внося некоторую непредсказу е- мость в систему. Пусть всего существует k возможных получателей. Тогда для широковещательной передачи M Алиса шифрует M ключом K и делает следующее. (1) Алиса выбирает случайное число j. Это число призвано замаскировать количество получателей сообщения. Оно не должно быть слишком большим и даже может равняться нулю . (2) Алиса создает пороговую схему (k + j + 1, 2k + j + 1), в которой: K - это секрет. Секретные ключи адресатов сообщения служат тенями . Секретные ключи пользователей, которых нет среди получателей сообщения, не являются тенями . j теней выбираются случайным образом, не совпадая ни с одним секретным ключом. (3) Алиса широковещательно передает k + j случайно выбранных теней, ни одна из которых не совпадает с тенями этапа (2). (4) Каждый из слушателей, принявших широковещательное сообщение, добавляет свою тень к полученным k + j теням. Если добавление своей тени позволяет пользователю вычислить секрет, то ему удалось открыть ключ. В противном случае - не удалось. Другой подход можно найти в [885, 886, 1194]. И еще один - в [1000]. Распределение ключей для конференции Этот протокол позволяет группе из n пользователей договориться о секретном ключе, используя только н е- секретные каналы. Группа использует два общих больших простых числа p и q, а также генератор g той же дли- ны, что и q. (1) Пользователь i, где i от 1 до n, выбирает случайное число r i , меньшее q, и широковещательно отправляет z i = g r i mod p (2) Каждый пользователь проверяет, что z i q ? 1 (mod p) для всех i от 1 до n. (3) i-ый пользователь широковещательно передает xi = (z i+1 /z i-1 ) r i mod p (4) i-ый пользователь вычисляет K = (z i-1 ) nr i *x i n-1 *x i+1 n-2 * . . . *x i-2 mod p Все вычисления индексов в приведенном протоколе - i-1, i-2 и i+1 - проводятся mod n. По окончании прото- кола у всех честных пользователей окажется один и тот же K. А все остальные ничего не получат. Однако этот протокол не может устоять перед вскрытием "человек в середине" . Другой протокол, не такой хороший, приве- ден в [757]. Tateboyashi-Matsuzaki-Newman Этот протокол распределения ключей подходит для использования в сетях [1521]. Алиса хочет с помощью Трента, KDC, генерировать ключ для сеанса связи с Бобом. Всем участникам известен открытый ключ Трента n. Тренту известны два простых множителя n, и, следовательно, он может легко вычислять квадратные корни по модулю n. Следующий протокол не содержит некоторых деталей, но позволяет получить общее представление . (1) Алиса выбирает случайное число r A и посылает Тренту r A 3 mod n (2) Трент сообщает Бобу, что кто-то хочет обменяться с ним ключом . (3) Боб выбирает случайное число r В и посылает Тренту r В 3 mod n (4) Трент, используя свой закрытый ключ, расшифровывает r A и r В . Он посылает Алисе r A ? r В (5) Алиса вычисляет (r A ? r В ) ? r A = r В Она использует r В для безопасного сеанса связи с Бобом. Протокол выглядит хорошо, но содержит заметный изъян. Кэрол может подслушать этап(3) и использовать эту информацию, воспользовавшись помощью доверчивого Трента и своего сообщника Дэйва, чтобы раскрыть [1472]. (1) Кэрол выбирает случайное число r С и посылает Тренту r В 3 r С 3 mod n (2) Трент сообщает Дэйву, что кто-то хочет обменяться с ним ключом . (3) Дэйв выбирает случайное число r , и посылает Тренту r , 3 mod n (4) Трент, используя свой закрытый ключ, расшифровывает r С и r , . Он посылает Кэрол (r В r C mod n) ? r , (5) Дэйв посылает r , Кэрол. (6) Кэрол использует r C и r , для получения r В . Она использует r В для расшифровывания переговоров Алисы и Боба. Это плохо. Глава 23 Специальные алгоритмы для протоколов 23.1 Криптография с несколькими открытыми ключами Это обобщение RSA (см. раздел 19.3) [217, 212]. Модуль n является произведением двух простых чисел p и q. Однако вместо e и d, для которых ed ? 1 mod ((p-1)(q-1)), выбирается t ключей K i , для которых выполняется K 1 * K 2 *. . . *K t ? 1 mod ((p-1)(q-1)) Так как M M K K K t 1 2 * *...* = то эта схема оказывается схемой с несколькими ключами, описанная в разделе 3.5. Если, например, используется пять ключей, то сообщение, зашифрованное ключами K 3 и K 5 , может быть расшифровано с помощью K 1 , K 2 и K 4 C = M K K 3 5 * mod n M = C K K K 1 2 4 * * mod n Одним из применений этой схемы является подписание документа несколькими людьми . Представим ситуа- цию, когда для того, чтобы документ был действителен, он должен быть подписан и Алисой, и Бобом . Исполь- зуются три ключа: K 1 , K 2 и K 3 . Алиса и Боб получают по одному ключу из первых двух , а третий опубликовыва- ется. (1) Сначала Алиса подписывает M и посылает его Бобу. M' = M K 1 mod n (2) Боб может восстановить M по M'. M = M K K ' * 3 5 mod n (3) Он может также добавить свою подпись. M'' = M K ' 2 mod n (4) Проверить подписи можно при помощи открытого ключа K 3 M = M K '' 3 mod n Обратите внимание, что для работоспособности этой системы нужна заслуживающая доверия сторона, кот о- рая установила бы систему и выдала ключи Алисе и Бобу . Та же проблема существует и в схеме [484]. Более тонкая схема описана в [695, 830, 700], Но усилия, предпринимаемые для проверки, пропорциональны колич е- ству подписывающих. Новые схемы [220, 1200], основанные на схемах идентификации с нулевым знанием, преодолевают эти недостатки предшествующих си стем. 23.2 Алгоритмы разделения секрета В разделе 3.7 я рассматривал идею, используемую в схемах разделения секрета . Четыре приведенных ниже различных алгоритма представляют собой частные случаи общего теоретического подхода [883]. Схема интерполяционных многочленов Лагранжа Для создания пороговой схема Ади Шамир воспользовался уравнениями для многочленов в конечном поле [1414]. Выберем простое число p, которое больше количества возможных теней и больше самого большого из возможных секретов. Чтобы сделать секрет общим, сгенерируем произвольный многочлен степени m-1. Напри- мер, если нужно создать пороговую схему (3,n) (для восстановления M потребуется три тени), генерируется квадратичный многочлен (ax 2 + bx + M) mod p где p - это случайное простое число, большее любого из коэффициентов . Коэффициенты a и b выбираются случайным образом, они хранятся в тайне и отбрасываются после того, как распределяются тени . M - это сооб- щение. Простое число должно быть опубликовано . Тени получаются с помощью вычисления многочлена в n различных точках: |