tanenbaum_seti_all.pages (525408), страница 228
Текст из файла (страница 228)
В то же время, ключи должны были быть у всех пользователей системы. Таким образом, казалось, что эта проблема неустранима: ключи должны быть защищены от кражи, и в то же время нх нужно распространять среди пользователей, поэтому их нельзя просто хранить в банковском сейфе. В 1976 году два исследователя из Стэнфордского университета, Диффи (01П>с) и Хеллман (Не!!лап), предложили радикально новую криптосистему, в которой ключ шифрования и ключ дешифрации были различными, кроме того, ключ дешифрации нельзя было получить из ключа шифрования. Предложенные имн алгоритм шифрования Е и алгоритм дешифрации 0 (оба параметризованные ключом) должны были удовлетворять следу>ощим трем требованиям: 1.
0(Е(Р)) = Р. 2. Крайне сложно вывести 0 из Е. 3. Е нельзя взломать при помощи произвольного открытого текста. Первое требование состоит а там, что если применить алгоритм дешифрации 0 к зашифрованному сообщению Е(Р), то мы опять получим открытый текст Р. Без этого авторизованный получатель просто не сможет расшифровать сообщение. Второе требование говорит само за себя. Третье требование необходимо, потому что, как мы скоро увидим, злоумышленники могут экспериментировать с алгоритмом столько, сколько пожелают. При таких условиях нет никаких причин, по которым ключ шифрования нельзя было бы сделать общедоступным. Этот метод работает следующим образом.
Некто, например Алиса, желая получать секретные сообщения, сначала формирует два алгоритма, удовлетворяющие перечисленным выше требованиям. Затем алгоритм шифрования и его кл>оч открыто объявляются, отсюда название — шифрование с открытым ключом. Зто можно сделать, разместив открытый кл>оч, например, ца домашней страничке Алисы. Для обозначения алгоритма шифрования, параметризованного открытым ключом Алисы, мы будем использовать запись Е . По аналогии (секретный) алгоритм дешифрации, параметризованный персональным ключом Алисы, мы будем обозначать 0,.
Боб лелает то же самое, открыто объявляя Е„, но храня в тайне 0 . Теперь посмотрим, сможем ли мы решить проблему установки надежного канала между Алисой и Бобом, которые ранее никогда не встречались. Оба ключа шифрования Алисы и Боба, Е, и Е„, являются открытыми. (Вооб>цс, все пользователи сети могут, становясь пользователями, опубликовать свои ключи шифрования.) Теперь Алиса берет свое первое сообщение Р, вычисляет Е (Р) и посылает его Бобу. Боб расшифровывает его с помощью своего секретного ключа 0„, то есть вычисляет 0э(Еэ(Р)) = Р. Больше никто не может прочитать это зашифро- 860 Глава 8. Безопасность в сетях ванное сообщение Е,(Р), так как предполагается, что система шифрования достаточно надежна, а получить ключ Р„на основании известного кл|оча Е, очень трудно, Посылая ответ, Боб передает Е,(Е). Таким образом, Алиса и Боб получают надежный секретный канал связи.
Обратите внимание на используемую здесь терминологию. Шифрование с открытым ключом предполагает у каждого пользователя наличие двух ключей— открытого ключа, используемого всеми для шифрования сообщений, посылаемых этому пользователю, и закрытого ключа, требующегося пользователю для дешифрации приходящих к нему сообщений. Мы будем и далее называть эти ключи открытым и закрытым, чтобы отличать их от секретных ключей, используемых для шифрования и дешифрации в обычной криптографии с симметричным ключом. Алгоритм йЗА Единственная загвоздка состоит в том, чтобы найти алгоритмы, удовлетворяющие всем трем требованиям.
Поскольку преимущества шифрования с открытым ключом очевидны, многие исследователи неустанно работали над созданием подобных алгоритмов, и некоторые из них уже опубликованы. Один хороший метод был разработан группой исследователей Массачусетского технологического института (К(чезт и др., 1978).
Он назван по начальным буквам фамилий трех разработчиков: КВА (К(чезц БЬаш1г, АсПешап). Этот метод вот уже четверть века выдерживает попытки взлома и считается очень прочным. На его основе построены многие практические системы безопасности. Главный недостаток КЯА заключается в том, что для обеспечения достаточного уровня защищенности требуется ключ длиной, по крайней мере, 1024 бита (против 128 бит в алгоритмах с симметричными ключами). Из-за этого алгоритм работает довольно медленно. В основе метода КБА лежат некоторые принципы теории чисел. Опишем в общих чертах, как пользоваться этим методом, Подробности см, в соответствующих источниках.
1. Выберем два больших простых числа р и о (обычно длияой 1024 бита), 2 Сосчитаем и = рд и г = (р — 1)(о — 1). 3. Выберем число о', являющееся взаимно простым с числом г. 4 Найдем такое число е, что остаток от деления произведения еИ на число г равен 1. Вычислив заранее эти параметры, можно начинать шифрование. Сначала разобьем весь открытый текст (рассматриваемый в качестве битовой строки) на блоки так, чтобы каждое сообщение Р попадало в интервал 0 < Р< и. Это несложно сделать, если разбить открытый текст на блоки по Е бит, где и — максимальное целое число, для которого 2' < и.
Чтобы зашифровать сообщение Р, вычислим С = )ь (шод и). Чтобы расшифровать С, сосчитаем Р = С" (щи и). Можно доказать, что для всех значений Р в указанном диапазоне функции шифрования н дешифрации являются взаимно обратными. Чтобы выполнить шифрование, нужны е и и. Для дешифрации тре- Алгоритмы с открытым ключом 881 буются Ы и и. Таким образом, открытый ключ состоит из пары (е, п), а закрытый ключ — из пары (с(, и), Надежность метода обеспечивается сложностью нахождения множителей больших чисел. Если бы криптоаналитик мог разложить на множители (открытое) число п, он мог бы тогда найти значения р и 9, а следовательно, и число к После этого числа е и Ы можно найти при помаши алгоритма Евклида. К счастью, математики пытались решить проблему разложения на множители больших чисел по меньшей мере 300 лет, и накопленный опыт позволяет предположить, что эта проблема чрезвычайно трудна.
Ривест (К(чезт) с коллегами утверждает, что для разложения на множители числа из 500 цифр необходимо 10м лет, если применять грубую силу. Предполагается, что задействованы лучший известный алгоритм и компьютер, выполняющий одну инструкцию за 1 мкс. Даже при сохранении экспоненциального роста скоростей компьютеров потребуются века, чтобы найти множители числа из 500 цифр, а к этому времени наши потомки могут просто выбрать еще большие р и к).
Тривиальный учебный пример работы алгоритма КБА приведен на рис. 8.14. Для этого примера мы выбрали р = 3, а с = 11, что дает значения п = 33, а г = 20. Число и' можно выбрать равным 7, так как числа 20 и 7 не имеют общих делителей. При таком выборе значение е можно найти, решив уравнение 7е = 1 (той 20), откуда следует, что е = 3, Зашифрованный текст С получается из открытого сообщения Р по формуле С = Р' (шаг) 33). Получатель расшифровывает сообщение по формуле Р = С' (лад 33). В качестве примера на рисунке показано шифрование слова «8()2АХХЕ».
После дешифрации Открытый текст (Р) Зашифрованный текст (С) Рв(,„) 33) 6859 28 9261 21 17578 20 1 1 2?44 5 2744 5 125 26 ~С 13492928512 1801088541 1260000000 1 78125 78125 8031810178 С?(тоо 33) Символ 8 () 2 А М М Е Символ Число В 0 2 А М М Е 19 21 26 1 14 14 5 19 21 26 01 14 14 05 Вычисление отправителя Вычисление получателя Рис. 8.14. Пример работы алгоритме ЙЗА Поскольку выбранные для данного примера простые числа так малы, Р должно быть менее 33, поэтому каждый блок открытого текста может содержать лишь одну букву. В результате получается моноалфавитный подстановочный шифр, что не очень впечатляет.
Если бы мы вместо этого выбрали числа р и д порядка 2мв, тогда число и было бы около 2 "~'. В этом случае каждый блок мог бы содержать до 1024 бит, или 128 восьмиразрядных символов, против 8 символов шифра 1)ЕЯ или 18 АЕ8. ВБ2 Глава 8. Безопасность в сетях Следует отметить, что использование алгоритма КВА в описанном ранее виде аналогично использованию симметричного алгоритма в режиме ЕСВ (Е!ессгошс СоДе Воо!г — электронный шифроблокнот), в котором одинаковые блоки на входе преобразуются в одинаковые блоки на выходе.
Таким образом, для шифрования данных требуется сцепление блоков в каком-либо виде, Однако на практике алгоритм КВА с открытым ключом используется только для передачи одноразового секретного ключа, после чего применяется какой-нибудь алгоритм с симметричным ключом типа АЕ8 или тройного 1)Е8. Система КВА слишком медленная, чтобы шифровать большие объемы данных, однако она широко применяется для распространения ключей. Другие алгоритмы с открытым ключом Хотя алгоритм КЯА получил широкое распространение, он ни в коей мере не является единственным известным алгоритмом с открытым ключом. Первым алгоритмом с открытым ключом стал «алгоритм ранца» (Мег!г!е и НеПшап, 1978).
Его идея состоит в том, что имеется большое количество объектов различного веса. Владелец этих объектов кодирует сообщение, выбирая подмножество объектов и помещая их в ранец. Общий вес объектов в рюкзаке известен всем, как и список всех возможных объектов. Список объектов, находящихся в рюкзаке, хранится в секрете. При определенных дополнительных ограничениях, задача определения возможного списка объектов по известному общему весу считалась неразрешимой для вычисления, то есть считалось, что решение можно найти только полным перебором различных сочетаний предметов списка.
Поэтому опа была положена в основу алгоритма с открытым ключом, Изобретатель алгоритма Ральф Меркле (Ка!рЬ Мсгй!е) был настолько уверен в надежности своего алгоритма, что предложил 100 долларов любому, кто сумеет его взломать. Ади Шамир (Аг!! 8Ьаш!г), «Я» в группе КЯА, мгновенно взломал его и получил награду. Это не смутило Мсркле, Он усилил алгоритм и предложил за его взлом уже 1000 долларов. Рон Ривест (Коп К1тсэг), «К» в КВЛ, тут же взломал улучшенную версию алгоритма и получил награду. Меркле не рискнул предложить 10 000 долларов за следующую версию, по;лому «А», Леонарду Эйдлману (Ьеопагд Ад!ешап), не повезло.
Несмотря па то, что алгоритм ранца был в очередной раз исправлен, оц не считается надежным и редко используется. Другие схемы с открытым ключом основаны на сложности вычисления л»шкретных логарифмов. Алгоритмы, использух>щие этот принцип, были разработаны Эль-Гамалем (Е! Сшпа1, 1985) и Шнорром (ВсЬпогг, 1991). Существуют и некоторые другие методы, например, основанные на эллиптических кривых (Мепегеэ и Ъ'апзтопс, !993).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
