foundations_chap_2 (1027396), страница 7
Текст из файла (страница 7)
Сертификат открытого ключа представляет собой подписанный цифровой подписью центра сертификации набор данных, включающий идентификатор владельца сертификата, его открытый ключ и, возможно, некоторую дополнительную информацию (время выдачи и периoд действия сертификата, информация о владельцеи центре сертификации, выдавшем сертификат, и т.
п.). В настоящеевремя наиболее распространенной является форма сертификата, соответствующая стандарту Х.509, принятому Сектором стандартизацииэлектросвязи Международного союза электросвязи (JTU-l). АбонентВ, получив от абонента А его открытый ключ в виде сертификата,может легко проверить его подлинность с помощью открытого ключацентра сертификации. Если цифровая подпись сертификата верна, тоключ подлинный. Злоумышленник С в этом случае не сможет подменить сертификат, не зная закрытого ключа центра сертификации.При использовании такой схемы распределения открытых ключейабонентам сети для организации обмена подписанными и шифрованными сообщениями достаточно иметь доверенный канал связи с центром сертификации.Если абоненты географически удалены друг от друга им можетбыть неудобно обращаться в один и тот же центр сертификации.
Вэтом случае могут быть созданы региональные центры сертификации,приближенные к абонентам.Чтобы абоненты, получившие сертификаты в разных центрахсертификации, смогли проверить подлинность сертификатов другдруга, региональные центры сертификации получают сертификат уцентра сертификации более высокого уровня. В этом случае абонентыдолжны получить: свой сертификат, сертификат центра сертификации в который они обратились и сертификат центра сертификации,выдавшего сертификаты региональным центрам сертификации.Центры сертификации могут объединяться в древовидную иерархию нескольких уровней.
Самый верхний центр сертификации в такойиерархии называют корневым. Он выдает сертификат сам себе, т. е.подписывает сертификат своего открытого ключа на своем закрытомключе. Такой сертификат называют самоподписанным.162КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫЕсли два центра сертификации из разных древовидных иерархийвыдадут друг другу сертификаты, то возникнет перекрестная иерархия. в такой иерархии один и тот же центр сертификации можетвыступать и как корневой, и как подчиненный.Иерархия центров сертификации позволяет не только приблизиться к абонентам. Многоуровневая организация является более безопасной, так как при компрометации закрытого ключа отдельногоцентра сертификации, выдающего ключи абонентам, не нарушаетсяработа всей системы связи.
Кроме того, с помощью иерархии сертификатов можно решить организационные проблемы. Например, выделить отдельные центры сертификации для различных направленийдеятельности (смарт-карты, электронная почта и т. п.) или разделитьцентры сертификации согласно тому, кто получает сертификаты (дляпостоянных и временных сотрудников, организаций и частных лиц ит.
п.).Совокупность технологий, стандартов, протоколов и служб, позволяющих обеспечивать управление ключами с использованиемцифровых сертификатов, называют Инфраструктурой открытогоключа (Public Кеу Jnfrastructure, PKJ).§ 2.4. RSA — криптосистема с открытым ключомОдной из наиболее распространенных криптосистем с открытымключом является система RSA, предложенная Ривестом, Шамиром иЭдлеманом (Rivest, Shamir, Adleman).
Ее стойкость основана на большой трудоемкости известных алгоритмов разложения произведениядвух простых чисел на сомножители.Чтобы организовать передачу шифрованных сообщений с помощью криптосистемы RSA, получатель должен сделать следующее:1. С помощью специального алгоритма сгенерировать два больших простых числа p, q, которые необходимо держать в секрете.2. Сообщить отправителю (или поместить в некоторый общедоступный каталог) число n, равное произведению p и q, а также случайным образом выбранное целое число E, взаимно простое с произведением (p − 1)(q − 1).3. Для расшифрования сообщений, зашифрованных на открытомключе n, E, получателю необходимо иметь число D, являющееся мультипликативным обратным числа E по модулю (p − 1)(q − 1), то естьостаток от деления произведения DE на (p − 1)(q − 1) должен бытьравен единице: DE ≡ 1( mod(p − 1)(q − 1)). Найти такое число получателю легко, так как наибольший общий делитель E и (p − 1)(q − 1)равен единице по выбору E.§ 2.4.RSA — КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ163Таким образом, отправитель знает закрытый ключ: n и E, а получатель, кроме этого, имеет секретный ключ D.Любое передаваемое сообщение можно представить в виде последовательности целых чисел из заданного интервала.
Будем считать,что отправитель передает секретное сообщение, представленное последовательностью чисел X1 , . . . , Xk , 0 ≤ Xi ≤ n − 1, для всех i от 1до k.Отправитель для каждого блока Xi передаваемого сообщения вычисляетECi = (Xi ) mod nи передает Ci по открытому каналу связи.Имея n, E и Ci , получатель может расшифровать сообщение, воспользовавшись соотношениемDXi = (Ci ) mod n.(2.2)Докажем сначала выполнение равенства (2.2) для чисел Xi , взаимно простых с n.Так как числа E и D связаны соотношением ED ≡ 1( mod(p −1)(q − 1)), то для некоторого целого k справедливо равенство ED =DED1 + k(p − 1)(q − 1). Отсюда и из соотношения Ci ≡ Xi ( mod n)вытекает, чтоD1+k(p−1)(q−1)Ci ≡ Xi( mod n).(2.3)Из теоремы Эйлера следует, что в случае, если числа Xi и n взаимнопросты,k(p−1)(q−1)Xi≡ 1( mod n).Отсюда и из (2.3) следует выполнение соотношения (2.2) для случая,когда Xi взаимно просто с n.Предположим теперь, что Xi имеет общий делитель с числом n,не совпадающий с единицей.
В этом случае Xi делится либо на p, либона q, так как n у нас равно произведению двух простых чисел p и q.Для определенности будем считать, что Xi делится на p и Xi = kp,где k — некоторое целое число. Тогда Xi взаимно просто с q и потеореме ЭйлераEDXi ≡ Xi ( mod q).(2.4)EDОбозначим через s остаток от деления Xi на q. Так как X = kp,EDдля некоторого целого r справедливо представление Xi = kp(rq +s).Отсюда и из (2.4) вытекает соотношениеkprq + kps ≡ Xi ( mod q).164КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫСледовательно, kps ≡ kp( mod q).
Тогда (s − 1)pk делится на q, откудаs = 1, так как k < q и s < q.EDВ итоге, имеем представление Xi = kprq + kp, из которого выEDтекает выполнение соотношения Xi ≡ Xi ( mod pq), эквивалентного(2.2).DТаким образом, получатель, вычислив Ci mod n, действительнополучит i-й блок первоначального сообщения.Рассмотрим в качестве примера случай p = 3, q = 11, n = 3×11 =33, E = 7 и D = 3. Легко убедиться, что каждое из чисел E = 7 иDE = 21 взаимно просто с (p−1)(q −1) = 20.
Для передачи сообщения7M=«02» отправителю необходимо вычислить C = (2 ) mod 33. Получатель может расшифровать сообщение C = 29, возведя его в степень3D по модулю n: 2 = 29 ( mod 33). Пусть, как и ранее, наш алфавитсостоит из букв русского языка (без буквы Ё) и пробела. Занумеровав элементы этого алфавита числами от 0 до 32, можно зашифровать произвольное сообщение на русском языке. Например, сообщение«ПРОВЕРИМ ЗНАНИЕ АРИФМЕТИКИ» в зашифрованном виде наключе n = 33, E = 7 будет выглядеть следующим образом:«27 25 20 29 14 25 02 12 32 28 07 00 07 02 14 32 00 25 02 26 12 1406 02 10 02».Очевидно, что шифр в нашем примере является шифром простойзамены. Мы уже знаем, что такой шифр можно вскрыть, исследовав частоты встречаемости и взаимное расположение чисел в криптограмме.
Однако в данном случае дешифровать получившуюся криптограмму можно гораздо быстрее, если составить полную таблицузашифрования (см. таблицу 2.5). При таком маленьком значении nпротивнику легко это сделать, так как по предположению открытыйключ: n = 33, E = 7 — ему известен.Таблица 2.5А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч ШЩ Ъ Ы Ь Э Ю Я0001 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 320001 29 09 16 14 30 28 02 15 10 11 12 07 20 27 25 08 06 13 26 21 22 23 18 31 05 03 19 17 24 04 32Из этой таблицы зашифрования легко получить таблицу расшифрования, отсортировав столбцы таблицы 2.5 по последней строке.Таблица 2.60001 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 320001 08 27 31 26 18 13 17 03 10 11 12 19 05 09 04 29 24 28 14 21 22 23 30 16 20 15 07 02 06 25 32А Б И Ы Я Ъ Т Н С Г К Л М У Е Й Д Э Ш Ь О Х Ц Ч Ю Р Ф П З В ЖЩ§ 2.4.RSA — КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ165Сложность составления такой таблицы дешифрования пропорциональна количеству различных блоков, которые могут встретиться вшифруемом сообщении.
Поэтому для того чтобы шифр, основанныйна криптосистеме RSA, не допускал дешифрование при неизвестномключе, необходимо (но не достаточно) выполнение следующих двухусловий. Во-первых, должно быть большим число n, которое ограничивает максимальный размер блока, а, следовательно, и количестворазличных блоков. Во-вторых, шифруемые сообщения должны бытьдостаточно разнообразны. Недопустимо использование системы RSA(а также других криптосистем с открытым ключом) в случае, еслисообщения являются комбинацией относительно небольшого количества стандартных фраз.
При выполнении указанных выше требований невозможно будет также дешифрование на основе анализа частоты встречаемости и взаимного расположения различных блоков шифрованного сообщения.Возможность описанной выше атаки служит дополнительным аргументом в пользу того, чтобы системы с открытым ключом применять не для шифрования непосредственно сообщений, а только дляпередачи секретного ключа, на котором сообщение шифруется с помощью обычной системы шифрования с симметричным ключом.Другим известным приемом дешифрования системы RSA является метод дешифрования итерациями, заключающийся в повторномшифровании до тех пор, пока вновь не будет получен открытый текст.П р и м е р2.1. Пусть p = 383, q = 563, n = 215629, E = 49.В этом случае открытый текст полностью восстанавливается уже через 10 шагов повторного шифрования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
