Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 229
Текст из файла (страница 229)
Подробности см. в соответствующих источниках. 1. Выберем два больших простых числа Р и д (обычно длиной 1024 бита). 2. Сосчитаем и =рд иг=(Р— 1)(Ч 1). З. Выберем число И, являющееся взаимно простым с числом г. 4 Найдем такое число е, что остаток от деления произведения ед на число г равен 1. Вычислив заранее эти параметры, можно начинать шифрование. Сначала разобьем весь открытый текст (рассматриваемый в качестве битовой строки) на блоки так, чтобы каждое сообщение Р попадало в интервал 0 < Р < п.
Это несложно сделать, если разбить открытый текст на блоки по Е бит, где Š— максимальное целое число, для которого 2г < и. Чтобы зашифровать сообщение Р, вычислим С = Р' (тог1 л). Чтобы расшифровать С, сосчитаем Р = Сг (шос п). Можно доказать, что для всех значений Р в указанном диапазоне функции шифрования и дешифрации являются взаимно обратными. Чтобы выполнить шифрование, нужны е и п.
Для дешифрации тре- Алгоритмы с открытым ключом 881 буются кт' и и. Таким образом, открытый ключ состоит из пары (е, и), а закрытый ключ — из пары (4 и). Надежность метода обеспечивается сложностью нахождения множителей больших чисел. Если бы криптоаналитик мог разложить на множители (открытое) число и, он мог бы тогда найти значения р и д, а следовательно, и число к После этого числа е и т( можно найти при помощи алгоритма Евклида.
К счастью, математики пытались решить проблему разложения на множители больших чисел по меньшей мере 300 лет, и накопленный опыт позволяет предположить, что эта проблема чрезвычайно трудна. Ривест (К(чезс) с коллегами утверждает, что для разложения на множители числа из 500 цифр необходимо 10" лет, если применять грубую силу. Предполагается, что задействованы лучший известный алгоритм и компьютер, выполняющий одну инструкцию за 1 мкс. Даже прн сохранении экспоненциального роста скоростей компьютеров потребуются века, чтобы найти множители числа из 500 цифр, а к этому времени наши потомки могут просто выбрать еще большие р н т).
Тривиальный учебный пример работы алгоритма ВБА приведен на рис. 8.14. Для этого примера мы выбрали р = 3, а т) = 11, что дает значения п = ЗЗ, а г = 20. Число г( можно выбрать равным 7, так как числа 20 и 7 не имеют общих делителей. При таком выборе значение е можно найти, решив уравнение 7е = 1 (щоб 20), откуда следует, что е = 3. Зашифрованный текст С получается из открытого сообщения Р по формуле С = Рк (щоб ЗЗ).
Получатель расшифровывает сообщение по формуле Р = С' (тог( 33). В качестве примера на рисунке показано шифрование слова «8()ЕА)ЧХЕ», Зашифрованный текст (С) Ре(глоб 33) После дешифрации Открытый текст (Р) Ст 13492928512 1801088541 1280000000 1 78125 78125 8031810176 Ст(вод 33) Символ Р 6859 9261 17576 1 2744 2744 125 Символ Число В 0 2 А ы м Е 19 21 26 01 14 14 05 28 21 20 1 5 5 26 19 21 26 1 14 14 5 Вычисление получателя Вычисление отправителя Рис.
8.14. Пример работы алгоритма НЗА Поскольку выбранные для данного примера простые числа так малы, Р должно быть менее 33, поэтому каждый блок открытого текста может содержать лишь одну букву. В результате получается моноалфавитный подстановочный шифр, что не очень впечатляет. Если бы мы вместо этого выбрали числа р и д порядка 2мт, тогда число л было бы около 2'м'. В этом случае каждый блок мог бы содержать до 1024 бит, или 128 восьмиразрядных символов, против 8 символов шифра ВЕЗ или 16 АЕЗ.
852 Глава 8. Безопасность в сетях Следует отметить, что использование алгоритма ЮА в описанном ранее виде аналогично использованию симметричного алгоритма в режиме ЕСВ (Е!есггоп!с Соде Воой — электронный шифроблокнот), в котором одинаковые блоки на входе преобразуются в одинаковые блоки на выходе. Таким образом, для шифрования данных требуется сцепление блоков в каком-либо виде. Однако на практике алгоритм КВА с открытым ключом используется только для передачи одноразового секретного ключа, после чего применяется какой-нибудь алгоритм с симметричным ключом типа АЕЯ или тройного ПЕ8. Система ЮА слишком медленная, чтобы шифровать большие объемы данных, однако она широко применяется для распространения ключей.
Другие алгоритмы с открытым ключом Хотя алгоритм КЯА получил широкое распространение, он нн в коей мере пе является единственным известным алгоритмом с открытым ключом. Первым алгоритмом с открытым ключом стал «алгоритм ранца» (Мегй)е и Не!!тап, 1978). Его идея состоит в том, что имеется большое количество объектов различного веса. Владелец этих объектов кодирует сообщение, выбирая подмножество объектов и помещая их в ранец. Общий вес объектов в рюкзаке известен всем, как и список всех возможных объектов. Список объектов, находящихся в рюкзаке, хранится в секрете. При определенных дополнительных ограничениях, задача определения возможного списка объектов по известному общему весу считалась неразрешимой для вычисления, то есть считалось, что решение можно найти только полным перебором различных сочетаний предметов списка. Поэтому она была положена в основу алгоритма с открытым ключом.
Изобретатель алгоритма Ральф Меркле (Ка!РЬ Мегй!е) был настолько уверен в надежности своего алгоритма, что предложил 100 долларов любому, кто сумеет его взломать. Ади Шамир (Ад! 8Ьаш|г), «Я. в группе ЮА, мгновенно взломал его и получил награду. Это не смутило Меркле. Он усилил алгоритм и предложил за его взлом уже 1000 долларов. Рон Ривест (Коп К1чезг), «К» в КВА, тут же взломал улучшенную версию алгоритма и получил награду. Меркле не Рискнул предложить 10 000 долларов за следующую версию, поэтому «А», Леонарду Эйдлману (1еопагг! Аб!ешап), не повезло. Несмотря на то, что алгоритм ранца был в очередной раз исправлен, он не считается надежным и редко используется. Другие схемы с открытым ключом основаны на сложности вычисления дискретных логарифмов.
Алгоритмы, использующие этот принцип, были разработаны Эль-Гамалем (Е! Саша), 1985) и Шнорром (ЯсЬпогг, 1991). Существуют и некоторые другие методы, например, основанные на эллиптических кривых (Мепегез и Чапзгопе, 1993). Однако две основные категории составляют алгоритмы, основанные на сложности нахождения делителей больших чисел и вычислений дискретных логарифмов. Эти задачи считаются особенно сложными, так как математики уже много лет пытаются их решить без особых успехов. Цифровые подписи 853 Цифровые подписи Подлинность различных бумажных документов (юридических, финансовь>х и др.) определяется наличием или отсутствием авторизованной рукописной подписи.
Фотокопии документами не считаются. Чтобы системы компьютерных сообщений могли заменить физическое перемещение документов, написанных чернилами на бумаге, нужно решить проблему подписи. Проблема разработки замены рукописной подписи довольно сложна. По существу, требуется система, с помощью которой одна сторона могла бы послать другой стороне «подписанное» сообщение так, чтобы: + получатель мог проверить объявленную личность отправителя; + отправитель не мог позднее отрицать содержимое сообщения; + получатель не мог позднее изменить подписанное сообщение.
Первое требование существенно, например, для финансовых систем. Когда компьютер клиента заказывает компьютеру банка купить тонну золота, банковский компьютер должен быть уверен, что компьютер, пославший заказ, действительно принадлежит компании, со счета которой следует снять денежную сумму. Другими словами, банк должен иметь возможность установить подлинность клиента (а клиент — подлинность банка). Второе требование необходимо для защиты банка от мошенничества.
Предположим, что банк покупает тонну золота, и сразу после етого цена на золото резко падает. Бесчестный клиент может подать в суд на банк, заявляя, что он никогда не посылал заказа на покупку золота. Банк может показать сообщение в суде, но клиент будет отрицать, что посылал его. Таким образом, должно быть обеспечено требование невозможности отречения от данных ранее обязательств. Методы составления цифровых подписей, которые мы изучим далее, предназначены в том числе и для етого. Третье требование нужно для защиты клиента в случае, если цена на золото после его покупки банком взлетает вверх и банк пытается создать подписанное сообщение, в котором клиент просит купить не одну тонну золота, а один слиток.
При таком сценарии банк, совершив мошенничество, забирает оставшуюся часть золота себе. Подписи с симметричным ключом Один из методов реализации цифровых подписей состоит в создании некоего центрального авторитетного органа, которому все доверяют, — назовем его, например, Большим Братом (В>й ВгогЬег, ВВ). Затем каждый пользователь выбирает секретный ключ и лично относит его в офис Большого Брата. Таким образом, например, секретный ключ Алисы, К„известен только Алисе и Большому Брату. Когда Алиса хочет послать открытым текстом своему банкиру Бобу подписанное сообщение Р, она формирует сообщение, зашифрованное К„(ключом 864 Глава 8. Безопасность в сетях Алисы), Кд(В, В„й Р), где  — идентификатор Боба, Вд — случайное число, выбранное Алисой, г — временной штамп, подтверждающий свежесть сообщения.
Затем она посылает его Большому Брату, как показано на рис. 8.15. Большой Брат видит, что это сообщение от Алисы, расшифровывает его и посылает Бобу, Сообщение, посылаемое Бобу, содержит открытый текст сообщения Алисы и подпись Большого Брата К (А, й Р). Получив подписанное сообщение, Боб может выполнять заказ Алисы. Рис.
В.15. цифровая подпись Большого Брата Что случится, если позднее Алиса станет отрицать отправку этого сообщения? Естественно, в случае возникновения подобных конфликтов конфликтующие стороны первым делом подают друг на друга в суд (по крайней мере, в Соединенных Штатах). Наконец, когда дело попадает в суд, Алиса энергично утверждает, что она не отправляла Бобу обсуждаемое. Судья спрашивает Боба, почему он уверен, что данное сообщение пришло именно от Алисы, а не от злоумышленницы Труди.
Боб сначала заявляет, что Большой Брат не принял бы сообщения от Алисы, если бы оно не было зашифровано ее ключом Кд, — у злоумышленника просто нет возможности послать Большому Брату фальшивое сообщение от Алисы. Затем Боб элегантным жестом демонстрирует суду сообщение А: Квв(А, Д Р). Боб заявляет, что это сообщение подписано Большим Братом, что доказывает, что Алиса послала сооб|цение Р Бобу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
