Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
(9) Кэрол вычисляет T = D v J d mod n. Затем она вычисляет d' = H(M,T'). Если d ? d', то множественная под- пись действительна. Этот протокол может быть расширен на любое количество людей . Для этого подписывающие сообщение люди должны перемножить свои значения T i на этапе (3), и свои значения D i на этапе (7). Чтобы проверить множественную подпись, нужно на этапе (8) перемножить значения J i подписывающих (8). Либо все подписи правильны, либо существует по крайней мере одна неправильная подпись . 21.3 SCHNORR Безопасность схемы проверки подлинности и подписи Клауса Шнорра [1396,1397] опирается на трудность вычисления дискретных логарифмов. Для генерации пары ключей сначала выбираются два простых числа , p и q так, чтобы q было сомножителем p-1. Затем выбирается a, не равное 1, такое что a q ? 1 (mod p). Все эти числа могут быть свободно опубликованы и использоваться группой пользователей . Для генерации конкретной пары ключей выбирается случайное число, меньшее q. Оно служит закрытым ключом, s. Затем вычисляется открытый ключ v = a -s mod p. Протокол проверки подлинности (1) Пегги выбирает случайное число r, меньшее q, и вычисляет x = a r mod p. Эти вычисления являются пред- варительными и могут быть выполнены задолго до появления Виктора . (2) Пегги посылает x Виктору. (3) Виктор посылает Пегги случайное число e, из диапазона от 0 до 2 t-1 . (Что такое t, я объясню чуть позже.) (4) Пегги вычисляет y = (r + se) mod q и посылает y to Виктору. (5) Виктор проверяет, что x = a y v e mod p. Безопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна 2 t . Шнорр советует использовать p около 512 битов, q - около 140 битов и t - 72. Протокол цифровой подписи Алгоритм Schnorr также можно использовать и в качестве протокола цифровой подписи сообщения M. Пара ключей используется та же самая, но добавляется однонаправленная хэш-функция H(M). (1) Алиса выбирает случайное число r, меньшее q, и вычисляет x = a r mod p. Это стадия предварительных вычислений. (2) Алиса объединяет M и x и хэширует результат: e = H(M,x) (3) Алиса вычисляет y = (r + se) mod q. Подписью являются значения e и y, она посылает их Бобу. (4) Боб вычисляет x' = a y v e mod p. Затем он проверяет, что хэш-значение для объединения M и x' равно e. e = H(M,x') Если это так, то он считает подпись верной. В своей работе Шнорр приводит следующие новые свойства своего алгоритма : Большая часть вычислений, нужных для генерации подписи и независящих от подписываемого сообщения, может быть выполнена на стадии предварительных вычислений . Следовательно, эти вычисления могут быть выполнены во время пр о- стоя и не влияют на скорость подписания . Вскрытие, направленное против стадии предварительных вычислений, рассматр и- вается в [475], я не думаю, что оно имеет практическую ценность . При одинаковом уровне безопасности длина подписей для Schnorr короче, чем для RSA. Например, при 140-битовом q длина подписей равна всего лишь 212 битам , меньше половины длины подписей RSA. Подписи Schnorr также намного коро- че подписей EIGamal. Конечно, из практических соображений количество битов, используемых в этой схеме, может быть умен ь- шено: например, для схемы идентификации, в которой мошенник должен выполнить диалоговое вскрытие всего лишь за несколько секунд (сравните со схемой подписи, когда мошенник может годами вести расчеты, чтобы выполнить подлог). Модификация, выполненная Эрни Брикеллом (Ernie Brickell) и Кевином МакКерли (Kevin McCurley), повы- сила безопасность этого алгоритма [265]. Патенты Schnorr запатентован в Соединенных Штатах [1398] и многих других странах. В 1993 году PKP приобрело обще мировые права на этот патент(см. раздел 25.5). Срок действия патента США истекает 19 февраля 2008 года. 21.4 Преобразование схем идентификации в схемы подписи Вот стандартный метод преобразования схемы идентификации в схему подписи : Виктор заменяется однона- правленной хэш-функцией. Перед подписанием сообщение не хэшируется, вместо этого хэширование встраив а- ется в алгоритм подписи. В принципе, такую манипуляцию можно проделать с любой схемой идентификации . Глава 22 Алгоритмы обмена ключами 22.1 DIFFIE-HELLMAN Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году [496]. Его безо- пасность опирается на трудность вычисления дискретных логарифмов в конечном поле (в сравнении с легк о- стью возведения в степень в том же самом поле . Diffie-Hellman может быть использован для распределения ключей - Алиса и Боб могут воспользоваться этим алгоритмом для генерации секретного ключа - но его нельзя использовать для шифрования и дешифрирования сообщений . Математика несложна. Сначала Алиса и Боб вместе выбирают большие простые числа n и g так, чтобы g было примитивом mod n. Эти два целых числа хранить в секрете необязательно, Алиса и Боб могут договорить- ся об из использовании по несекретному каналу . Эти числа даже могут совместно использоваться группой пол ь- зователей. Без разницы. Затем выполняется следующий протокол: (1) Алиса выбирает случайное большое целое число x и посылает Бобу X = g x mod n (2) Боб выбирает случайное большое целое число y и посылает Алисе Y = g y mod n (3) Алиса вычисляет k = Y x mod n (4) Боб вычисляет k' = X y mod n И k, и k' равны g xy mod n. Никто из подслушивающих этот канал не сможет вычислить это значение, им и з- вестно только n, g, X и Y. Пока они не смогут вычислить дискретный логарифм и раскрыть x или y, они не смо- гут решить проблему. Поэтому, k - это секретный ключ, который Алиса и Боб вычисляют независимо . Выбор g и n может заметно влиять на безопасность системы . Число (n-1)/2 также должно быть простым [1253]. И, самое главное, n должно быть большим: безопасность системы основана на сложности разложения на множители чисел того же размера, что и n. Можно выбирать любое g, которое является примитивом mod n; нет причин, по которым нельзя было бы выбрать наименьшее возможное g - обычно одноразрядное число. (К тому же, на самом деле, g не должно даже быть примитивом, оно только должно генерировать достаточно большую подгруппу мультипликативной группы mod n.) Diffie-Hellman с тремя и более участниками * Протокол обмена ключами Diffie-Hellman легко можно расширить на случай с тремя и более участниками . В приводимом примере Алиса, Боб и Кэрол вместе генерируют секретный ключ. (1) Алиса выбирает случайное большое целое число x и вычисляет X = g x mod n (2) Боб выбирает случайное большое целое число y и посылает Кэрол Y = g y mod n (3) Кэрол выбирает случайное большое целое число z и посылает Алисе Z = g z mod n (4) Алиса посылает Бобу Z'=Z x mod n (5) Боб посылает Кэрол * X'=X y mod n (6) Кэрол посылает Алисе Y'=Y z mod n (7) Алиса вычисляет k = Y' x mod n (8) Боб вычисляет k = Z' y mod n (9) Кэрол вычисляет k = :' z mod n Секретный ключ k равен g xyz mod n, и никто из подслушивающих каналы связи не сможет вычислить это значение. Протокол можно легко расширить для четверых и более участников, просто добавляются участники и этапы вычислений. Расширенный Diffie-Hellman Diffie-Hellman также работает в коммутативных кольцах [1253]. З. Шмули (Z. Shmuley) и Кевин МакКерли (Kevin McCurley) изучили вариант алгоритма, в котором модуль является составным числом [1441, 1038]. В.С. Миллер (V. S. Miller) и Нил Коблиц (Neal Koblitz) расширили этот алгоритм, используя эллиптические кривые [1095, 867]. Тахер ЭльДжамаль (Taher ElGamal) использовал основополагающую идею для разработки алг о- ритма шифрования и цифровой подписи (см. раздел 19.6). Этот алгоритм также работает в поле Галуа GF(2 k ) [1442, 1038]. В ряде реализаций используется именно этот подход [884, 1631, 1632], так как вычисления выполняются намного быстрее . Но и криптоаналитические вычисления выполняются намного быстрее , поэтому важно тщательно выбирать поле, достаточно большое, чтобы обеспечить нужную безопасность. Hughes Этот вариант алгоритма Diffie-Hellman позволяет Алисе генерировать ключ и послать его Бобу [745]. (1) Алиса выбирает случайное большое целое число x и генерирует k = g x mod n (2) Боб выбирает случайное большое целое число y и посылает Алисе Y = g y mod n (3) Алиса посылает Бобу X = Y x mod n (4) Боб вычисляет z = y -1 k' = X z mod n Если все выполнено правильно, k = k'. Преимуществом этого протокола над Diffie-Hellman состоит в том, что k можно вычислить заранее, до взаи- модействия, и Алиса может шифровать сообщения с помощью k задолго до установления соединения с Бобом. Она может послать сообщение сразу множеству людей, а передать ключ позднее каждому по отдельности . Обмен ключом без обмена ключом Если у вас сообщество пользователей, каждый может опубликовать открытый ключ , X = g x mod n, в общей базе данных. Если Алиса захочет установить связь с Бобом, ей понадобится только получить открытый ключ Боба и генерировать их общий секретный ключ . Она может зашифровать сообщение этим ключом и послать его Бобу. Боб извлечет открытый ключ Алисы и вычислит общий секретный ключ . Каждая пара пользователей может использовать уникальный секретный ключ , не требуется никаких предва- рительных обменов данными между пользователями . Открытые ключи должны пройти сертификацию, чтобы предотвратить мошеннические вскрытия, и должны регулярно меняться, но в любом случае это очень умная идея Патенты Алгоритм обмена ключами Diffie-Hellman запатентован в Соединенных Штатах [718] и Канаде [719]. Груп- па, называющаяся Public Key Partners (PKP, Партнеры по открытым ключам), получила вместе с другими па- тентами в области криптографии с открытыми ключами получила лицензию на этот патент (см. раздел 25.5). Срок действия патента США истекает 29 апреля 1997 года . 22.2 Протокол "точка-точка" Обмен ключами Diffie-Hellman чувствителен к вскрытию "человек в середине" . Одним из способов предот- вратить это, является необходимость для Алисы и Боба подписывать сообщения, которые они посылают друг другу [500]. Этот протокол предполагает, что у Алисы есть сертифицированный открытый ключ Боба, а у Боба есть се р- тифицированный открытый ключ Алисы . Эти сертификаты подписаны некоторым заслуживающим доверия органом власти, непосредственно не участвующим в протоколе . Вот как Алиса и Боб генерируют секретный ключ k. (1) Алиса генерирует случайное число x и посылает его Бобу. (2) Боб генерирует случайное число y. Используя протокол Diffie-Hellman, он вычисляет общий ключ k на ба- зе x и y. Он подписывает x и y и шифрует подпись ключом k. Затем он посылает получившееся вместе с y Алисе. y,E k (S B (x,y)) (3) Алиса также вычисляет k. Она расшифровывает оставшуюся часть сообщения Боба и проверяет его под- пись. Затем она посылает Бобу подписанное сообщение, состоящее из x и y, зашифрованных общим клю- чом k. E k (S A (x,y)) (4) Боб расшифровывает сообщение и проверяет подпись Алисы. 22.3 Трехпроходный протокол Шамира Этот изобретенный Ади Шамиром но никогда не опубликованный протокол позволяет Алисе и Бобу безо- пасно обмениваться информацией, не используя предварительного обмена ни секретными, ни открытыми кл ю- чами [1008]. Он предполагает использование коммутативного симметричного шифра , для которого: E A (E B (P)) = E B (E A (P)) Секретный ключ Алисы - A, а Боба - B. Алиса хочет послать сообщение M Бобу. Вто этот протокол. (1) Алиса шифрует M своим ключом и посылает его Бобу C 1 = E A (M) (2) Боб шифрует C 1 своим ключом и посылает Алисе C 2 = E B (E A (M)) (3) Алиса расшифровывает C 2 своим ключом и посылает Бобу C 3 = D A (E B (E A (M))) = D A (E A (E B (M))) = E B (M) (4) Боб расшифровывает C 3 своим ключом, получая M. Коммутативны и обладают совершенной безопасностью одноразовые блокноты, но с этим протоколом они работать не будут. При использовании одноразового блокнота три шифротекста будут выглядеть следующим образом be: C 1 = M ? A C 2 = M ? A ? B C 3 = M ? B Ева, записав эти три сообщения, которыми обмениваются Алиса и Боб, просто выполнит XOR всех этих шифротекстов и восстановит сообщение: C 1 ? C 2 ? C 3 =(M ? A) ? (M ? A ? B) ? (M ? B) = M Очевидно, что такой способ работать не будет . Шамир (и независимо Джим Омура (Jim Omura)) описал похожий на RSA алгоритм шифрования, который будет работать с этим протоколом. Пусть p будет большим большим простым числом, причем множитель p-1 является большим простым. Выберем ключ шифрования e, взаимно простой с p-1. Вычислим d, для которого выполняется de = 1 (mod p - 1). Для шифрования сообщения вычисляем C = M e mod p Для дешифрирования сообщения вычисляем M = C d mod p По видимому, у Евы нет способа получить M, не решив проблему дискретного логарифма, но это никогда не было доказано. Как и Diffie-Hellman, этот протокол позволяет Алисе начать секретный обмен информацией с Бобом, не зная ни одного из его ключей. При использовании алгоритма с открытым ключом Алиса должна знать открытый ключ Боба. Применяя трехпроходный алгоритм Шамира, она просто посылает Бобу шифротекст сообщения . То же действие с помощью алгоритма с открытым ключом выглядит следующим образом : (1) Алиса запрашивает у Боба (или у KDC) его открытый ключ. (2) Боб (или KDC) посылает Алисе свой открытый ключ. (3) Алиса шифрует M открытым ключом Боба и посылает его Бобу. Трехпроходный алгоритм Шамира не может устоять перед вскрытием "человек в середине" . 22.4 COMSET COMSET (COMmunications SETup, установление связи) это протокол одновременной идентификации и о б- мена ключом, разработанный для проекта RIPE [1305] (см. раздел 25.7). С помощью криптографии с открыты- ми ключами он позволяет Алисе и Бобу идентифицировать друг друга, при этом обмениваясь секретным кл ю- чом. Математической основой COMSET служит схема Rabin [1283] (см. раздел 19.5). Сама схема впервые была предложена в [224]. См. подробности в [1305]. 22.5 Обмен зашифрованными ключами Протокол обмена зашифрованными ключами (Encrypted Key Exchange, EKE) был разработан Стивом Бел- ловином (Steve Bellovin) и Майклом Мерриттом (Michael Merritt) [109]. Он обеспечивает безопасность и про- верку подлинности в компьютерных сетях , по новому используя и симметричную криптографию, и криптогр а- фию с открытыми ключами: общий секретный ключ используется для шифрования генерированного случа й- ным образом открытого ключа. Базовый протокол EKE Алиса и Боб (два пользователя, клиент и сервер, или кто угодно) имеют общий пароль P. Используя сле- дующий протокол, они могут проверить подлинность друг друга и генерировать общий сеансовый ключ K. (1) Алиса Случайным образом генерирует пару "открытый ключ/закрытый ключ" . Она шифрует открытый ключ K' с помощью симметричного алгоритма, используя P в качестве ключа: E P (K'). Она посылает Бобу A, E P (K') (2) Боб знает P. Он расшифровывает сообщение, получая K'. Затем он генерирует случайный сеансовый ключ K шифрует его открытым ключом, который он получил от Алисы, а затем используя P качестве ключа. Он посылает Алисе E P (E K' (K) (3) Алиса расшифровывает сообщение, получая K. Она генерирует случайную строку R A , шифрует ее с помо- щью K и посылает Бобу E K (R A ) (4) Боб расшифровывает сообщение, получая R A . Он генерирует другую случайную строку, R B , шифрует обе строки ключом K и посылает Алисе результат. E K (R A ,R B ) (5) Алиса расшифровывает сообщение, получая R A и R B . Если строка R A , полученная от Боба, - это та самая строка, которую она послала Бобу на этапе (3), она, используя K, шифрует R B и посылает ее Бобу. E K (R B ) (6) Боб расшифровывает сообщение, получая R B . Если строка R B , полученная от Алисы, - это та самая строка, которую он послал ей на этапе (4), завершен. Теперь обе стороны могут обмениваться информацией, и с- пользуя K в качестве сеансового ключа. На этапе (3) и Алиса, и Боб знают K' и K. K - это сеансовый ключ, он может быть использован для шифров а- ния всех других сообщений, которыми обмениваются Алиса и Боб. Ева, сидя между Алисой и Бобом, знает только E P (K'), E P (E K' (K) и несколько сообщений, зашифрованных K. В других протоколах Ева могла бы попро- бовать угадать P (люди все время любят выбирать плохие пароли , и если Ева достаточно умна, она может этот пароль) и затем проверить свои предположения. В рассматриваемом протоколе Ева не может проверять свои предположения, не вскрыв при этом и алгоритм с открытым ключом . И, если K' и K выбираются случайным образом, то эта проблема будет непреодолимой. Ответная часть протокола, этапы (3) - (6), обеспечивает подтверждение. Этапы (3) - (5) доказывают Алисе, что Боб знает K, этапы (4) - (6) доказывают Бобу, что Алиса знает K. Обмен метками времени, используемый в протоколе Kerberos, решает ту же задачу. EKE может быть реализован с множеством алгоритмов с открытыми ключами : RSA, ElGamal, Diffie- Hellman. Проблемы с безопасностью возникают при реализации EKE с алгоритмом рюкзака (даже без учета проблем безопасности, присущих самим алгоритмам рюкзака ): нормальное распределение шифротекста соо б- щений сводит на нет преимущества EKE. Реализация EKE с помощью RSA Алгоритм RSA кажется идеальным для такого использования, но есть ряд тонких проблем . Авторы рекомен- дуют шифровать на этапе (1) только показатель степени, посылая модуль . Объяснение этого совета и другие тонкости, связанные с использованием RSA, можно найти [109]. Реализация EKE с помощью ElGamal Реализация EKE на базе алгоритма ElGamal проста, можно даже упростить основной протокол . Используя обозначения из раздела 19.6, g и p служат частями открытого ключа, общими для всех пользователей . Закры- тым ключом является случайное число r. Открытым - g r |