Брюс Шнайер. Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С. СОДЕРЖАНИЕ.
RuTracker.org » Математика » Скачать торрент Brus Shnayer / Брюс Шнайер - Прикладная криптография [2002, PDF, RUS].
Брюс Шнайер
Брюс Шнайер — сын Мартина Шнайера, верховного судьи Бруклина. Он вырос В 1994 году Шнайер опубликовал книгу « Прикладная Криптография ».
Автор: Шнайер Брюс, Книга: Прикладная криптография, Серия: Название: Прикладная криптография Скачать эту книгу (1722k) в формате: doc.
Прикладная криптография Год выпуска: 2002 Автор: Brus Shnayer / Брюс Шнайер Жанр: Криптография, компьютерная безопасность Издательство: Триумф ISBN: 5-89392-055-4 Формат: PDF Качество: OCR без ошибок Количество страниц: 816 Описание: Криптография бывает двух типов: криптография, которая помешает читать ваши файлы вашей младшей сестре, и криптография, которая помешает читать ваши файлы дядям из правительства. Эта книга о втором типе криптографии. Аннотация к книге.
Brus Shnayer / Брюс Шнайер - Прикладная криптография [2002, PDF, RUS] :: RuTracker.org
Брюс Шнайер. Прикладная криптография. Математические основы криптографических алгоритмов. Стандарт шифрования данных DES. Скачать.
Брюс Шнайер Прикладная криптография 2-е издание Протоколы, алгоритмы и исходные тексты на языке С СОДЕРЖАНИЕ Уитфилд Диффи. Предисловие Введение Глава 1 Основные понятия 1.1 Терминология 1.2 Стеганография 1.3 Подстановочные и перестановочные шифры 1.4 Простое XOR 1.5 Одноразовые блокноты 1.6 Компьютерные алгоритмы 1.7 Большие числа Часть 1\u0014\u0014\u0014\u0014Криптографические протоколы Глава 2 Элементы протоколов 2.1 Введение в протоколы 2.2 Передача информации с использованием симметричной криптографии 2.3 Однонаправленные функции 2.4 Однонаправленные хэш-функции 2.5 Передача информации с использованием криптографии с открытыми кл ючами 2.6 Цифровые подписи 2.7 Цифровые подписи и шифрование 2.8. Генерация случайных и псевдослучайных последовательностей Глава 3 Основные протоколы 3.1 Обмен ключами 3.2 Удостоверение подлинности 3.3 Удостоверение подлинности и обмен ключами 3.4 Формальный анализ протоколов проверки подлинности и обмена ключами 3.5 Криптография с несколькими открытыми ключами 3.6 Разделение секрета 3.7 Совместное использование секрета 3.8 Криптографическая защита баз данных Глава 4 Промежуточные протоколы 4.1 Службы меток времени 4.2 Подсознательный канал 4.3 Неотрицаемые цифровые подписи 4.4 Подписи уполномоченного свидетеля 4.5 Подписи по доверенности 4.6 Групповые подписи 4.7 Подписи с обнаружением подделки 4.8 Вычисления с зашифрованными данными 4.9 Вручение битов 4.10 Подбрасывание "честной" монеты 4.11 Мысленный покер 4.12 Однонаправленные сумматоры 4.13 Раскрытие секретов "все или ничего" 4.14 Условное вручение ключей Глава 5 Развитые протоколы 5.1 Доказательства с нулевым знанием 5.2 Использование доказательства с нулевым знанием для идентификации 5.3 Слепые подписи 5.4 Личностная криптография с открытыми ключами 5.5 Рассеянная передача 5.6 Рассеянные подписи 5.7 Одновременная подпись контракта 5.8 Электронная почта с подтверждением 5.9 Одновременный обмен секретами Глава 6 Эзотерические протоколы 6.1 Безопасные выборы 6.2 Безопасные вычисления с несколькими участниками 6.3 Анонимная широковещательная передача сообщений 6.4 Электронные наличные Часть 11\u0014\u0014\u0014\u0014Криптографические методы Глава 7 Длина ключа 7.1 Длина симметричного ключа 7.2 Длина открытого ключа 7.3 Сравнение длин симметричных и о ткрытых ключей 7.4 Вскрытие в день рождения против однонаправленных хэш-функций 7.5 Каков должны быть длина ключа ? 7.6 Caveat emptor Глава 8 Управление ключами 8.1 Генерация ключей 8.2 Нелинейные пространства ключей 8.3 Передача ключей 8.4 Проверка ключей 8.5 Использование ключей 8.6 Обновление ключей 8.7 Хранение ключей 8.8 Резервные ключи 8.9 Скомпрометированные ключи 8.10 Время жизни ключей 8.11 Разрушение ключей 8.12 Управление открытыми ключами Глава 9 Типы алгоритмов и криптографические режимы 9.1 Режим электронной шифровальной книги 9.2 Повтор блока 9.3 Режим сцепления блоков шифра 9.4 Потоковые шифры 9.5 Самосинхронизирующиеся потоковые шифры 9.6 Режим обратной связи по шифру 9.7 Синхронные потоковые шифры 9.8 Режим выходной обратной связи 9.9 Режим счетчика 9.10 Другие режимы блочных шифров 9.11 Выбор режима шифра 9.12 Прослаивание 9.13 Блочные шифры против потоковых шифров Глава 10 (Текст главы на английском, sorry. Переводчик, похоже, устал :-) Использование алгоритмов 10.1 Выбор алгоритма 10.2 Криптография с открытым ключом против симметричной криптографии 10.3 10.4 10.5 10.6 10.7 10.8 10.9 Шифрование коммуникационных каналов Шифрование хранимых данных Аппаратное шифрование против программного шифрования Компрессия, кодирование и шифрование Выявление шифрования Скрытие шифртекста в шифртексте Разрушение информации Часть 111\u0014\u0014\u0014\u0014Криптографические алгоритмы Глава 11 Математические основы 11.1 Теория информации 11.2 Теория сложности 11.3 Теория чисел 11.4 Разложение на множители 11.5 Генерация простого числа 11.6 Дискретные логарифмы в конечном поле Глава 12 Стандарт шифрования данных DES 12.1 Введение 12.2 Описание DES 12.3 Безопасность DES 12.4 Дифференциальный и линейный криптоанализ 12.5 Реальные критерии проектирования 12.6 Варианты DES 12.7 Насколько безопасен сегодня DES? Глава 13 Другие блочные шифры 13.1 LUCIFER 13.2 MADRYGA 13.3 NewDES 13.4 FEAL 13.5 REDOC 13.6 LOKI 13.7 KHUFU и KHAFRE 13.8 RC2 13.9 IDEA 13.10 MMB 13.11 CA-1.1 13.12 SKIPJACK Глава 14 И еще о блочных шифрах 14.1 ГОСТ 14.2 CAST 14.3 BLOWFISH 14.4 SAFER 14.5 3-WAY 14.6 CRAB 14.7 SXAL8/MBAL 14.8 RC5 14.9 Другие блочные алгоритмы 14.10 Теория проектирования блочного шифра 14.11 Использование однонаправленных хэш-функций 14.12 Выбор блочного алгоритма Глава 15 Объединение блочных шифров 15.1 Двойное шифрование 15.2 Тройное шифрование 15.3 Удвоение длины блока 15.4 Другие схемы многократного шифрования 15.5 Уменьшение длины ключа в CDMF 15.6 Отбеливание 15.7 Многократное последовательное использование блочных алгоритмов 15.8 Объединение нескольких блочных алгоритмов Глава 16 Генераторы псевдослучайных последовательностей и потоковые шифры 16.1 Линейные конгруэнтные генераторы 16.2 Сдвиговые регистры с линейной обратной связью 16.3 Проектирование и анализ потоковых шифров 16.4 Потоковые шифры на базе LFSR 16.5 A5 16.6 Hughes XPD/KPD 16.7 Nanoteq 16.8 Rambutan 16.9 Аддитивные генераторы 16.10 Gifford 16.11 Алгоритм M 16.12 PKZIP Глава 17 Другие потоковые шифры и генераторы настоящих случайных последовательностей 17.1 RC4 17.2 SEAL 17.3 WAKE 17.4 Сдвиговые регистры с обратной связью по переносу 17.5 Потоковые шифры, использующие FCSR 17.6 Сдвиговые регистры с нелинейной обратной связью 17.7 Другие потоковые шифры 17.8 Системно-теоретический подход к проектированию потоковых шифров 17.9 Сложностно-теоретический подход к проектированию потоковых шифров 17.10 Другие подходы к проектированию потоковых шифров 17.11 Шифры с каскадом нескольких потоков 17.12 Выбор потокового шифра 17.13 Генерация нескольких потоков из одного генератора псевдослучайной последовательности 17.14 Генераторы реальных случайных последовательностей Глава 18 Однонаправленные хэш-функции 18.1 Основы 18.2 Snefru 18.3 N-хэш 18.4 MD4 18.5 MD5 18.6 MD2 18.7 Алгоритм безопасного хэширования ( Secure Hash Algorithm, SHA) 18.8 RIPE-MD 18.9 HAVAL 18.10 Другие однонаправленные хэш-функции 18.11 Однонаправленные хэш-функции , использующие симметричные бло чные алгоритмы 18.12 Использование алгоритмов с открытым ключом 18.13 Выбор однонаправленной хэш-функции 18.14 Коды проверки подлинности сообщения Глава 19 Алгоритмы с открытыми ключами 19.1 Основы 19.2 Алгоритмы рюкзака 19.3 RSA 19.4 Pohlig-Hellman 19.5 Rabin 19.6 ElGamal 19.7 McEliece 19.8 Криптосистемы с эллиптическими кривыми 19.9 LUC 19.10 Криптосистемы с открытым ключом на базе конечных автоматов Глава 20 Алгоритмы цифровой подписи с открытым ключом 20.1 Алгоритм цифровой подписи (DIGITAL SIGNATURE ALGORITHM , DSA) 20.2 Варианты DSA 20.3 Алгоритм цифровой подписи ГОСТ 20.4 Схемы цифровой подписи с использованием дискретных логарифмов 20.5 ONG-SCHNORR-SHAMIR 20.6 ESIGN 20.7 Клеточные автоматы 20.8 Другие алгоритмы с открытым ключом Глава 21 Схемы идентификации 21.1 FEIGE-FIAT-SHAMIR 21.2 GUILLOU-QUISQUATER 21.3 SCHNORR 21.4 Преобразование схем идентификации в схемы подписи Глава 22 Алгоритмы обмена ключами 22.1 DIFFIE-HELLMAN 22.2 Протокол "точка-точка" 22.3 Трехпроходный протокол Шамира 22.4 COMSET 22.5 Обмен зашифрованными ключами 22.6 Защишенные переговоры о ключе 22.7 Распределение ключа для конференции и секретная широковещательная передача Глава 23 Специальные алгоритмы для протоколов 23.1 Криптография с несколькими открытыми ключами 23.2 Алгоритмы разделения секрета 23.3 Подсознательный канал 23.4 Неотрицаемые цифровые подписи 23.5 Подписи, подтверждаемые доверенным лицом 23.6 Вычисления с зашифрованными данными 23.7 Бросание "честной" монеты 23.8 Однонаправленные сумматоры 23.9 Раскрытие секретов "все или ничего" 23.10 Честные и отказоустойчивые криптосистемы 23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE 23.12 Слепые подписи 23.13 Передача с забыванием 23.14 Безопасные вычисления с несколькими участниками 23.15 Вероятностное шифрование 23.16 Квантовая криптография Часть 18\u0014\u0014\u0014Реальный мир Глава 24 Примеры реализаций 24.1 Протокол управления секретными ключами компании IBM 24.2 MITRENET 24.3 ISDN 24.4 STU-III 24.5 KERBEROS 24.6 KRYPTOKNIGHT 24.7 SESAME 24.8 Общая криптографическая архитектура IBM 24.9 Схема проверки подлинности ISO 24.10 Почта с повышенной секретностью PRIVACY-ENHANCED MAIL (PEM) 24.11 Протокол безопасности сообщений 24.12 PRETTY GOOD PRIVACY (PGP) 24.13 Интеллектуальные карточки 24.14 Стандарты криптографии с открытыми ключами 24.15 Универсальная система электронных платежей 24.16 CLIPPER 24.17 CAPSTONE 24.18 Безопасный телефон AT&T MODEL 3600 TELEPHONE SECURITY DEVICE (TSD) Глава 25 Политика 25.1 Агентство национальной безопасности (NSA) 25.2 Национальный центр компьютерной безопасности (NCSC) 25.3 Национальный институт стандартов и техники 25.4 RSA Data Security, Inc. 25.5 PUBLIC KEY PARTNERS 25.6 Международная ассоциация криптологических исследований 25.7 Оценка примитивов целостности RACE (RIPE) 25.8 Условный доступ для Европы (CAFE) 25.9 ISO/lEC 9979 25.10 Профессиональные и промышленные группы, а также группы защитн иков гражданских свобод 25.11 Sci.crypt 25.12 Шифропанки 25.13 Патенты 25.14 Экспортное законодательство США 25.15 Экспорт и импорт криптографии за рубежом 25.16 Правовые вопросы Мэтт Блейз. Послесловие Часть 8\u0014 Исходные коды 1. DES 2. LOKI91 3. IDEA 4. GOST 5. BLOWFISH 6. 3-WAY 7. RC5 8. A5 9. SEAL Библиография Прикладная криптография 2-е издание Протоколы, алгоритмы и исходные тексты на языке С Брюс Шнайер Предисловие Уитфилд Диффи История литературы по криптографии довольно любопытна . Секретность, конечно же, всегда играла важную роль, но до Первой мировой войны о важных разработках время от времени сообщалось в печати и криптогр афия развивалась также, как и другие специализированные дисциплины. В 1918 году в виде научного отчета ч астной Лаборатории Ривербэнк вышла в свет монография Вильяма Ф. Фридмана Показатель совпадений и его применения в криптографии (Index of Coincidence and Its Applications in Cryptography ) [577], одна из определяющих работ 20-го столетия. И это несмотря на военный заказ, по которому была сделана эта работа. В том же году Эдвард Х. Хеберн из Окленда, Калифорния, получил первый патент [710] на роторную машину, устройство, на котором основывалась военная криптография в течение почти 50 лет. После Первой мировой войны, однако, все изменилось. Организации армии и флота Соединенных Штатов, полностью засекретив свои работы, добились фундаментальных успехов в криптографии. В течение 30 -х и 40-х годов в открытой литературе по данному предмету появлялись только отдельные основные работы и моногр афии, но чем дальше, тем меньше они соответствовали реальному положению дел. К концу войны переход по лностью завершился. Открытая литература умерла за исключением одного заметного исключения, работы Клода Шэннона "The Communication Theory of Secrecy systems" ( Теория связи между секретными системами ), напечатанной в 1949 году в Bell System Technical Journal [1432]. Эта статья, как и работа Фридмана в 1918 году, явилась результатом исследований Шэннона во время войны. После окончания Второй мировой войны она была рассекречена, возможно по ошибке. С 1949 по 1967 литература по криптографии была бессодержательной. В 1967 году она пополнилась работой другого типа, историей Дэвида Кана Дешифровщики (The Codebreakers ) [794]. В этой книге не было новых идей, но она содержала достаточно полную историю предмета, включая упоминание о некоторых вещах, все еще засекреченных правительством. Значение Дешифровщиков заключалось не только в значительном охвате предмета, книга имела заметный коммерческий успех и познакомила с криптографией тысячи людей, раньше и не задумывавшихся о ее существовании. Тоненьким ручейком начали появляться новые работы по криптогр афии. Почти в то же время Хорста Фейстела, ранее работавшего над прибором "свой/чужой" для ВВС, на всю дальнейшую жизнь охватила страсть к криптографии, и он перешел в Уотсоновскую Лабораторию фирмы IBM, расположенную в Йорктаун Хайтс, Нью-Йорк. Там он начал разработку того, что затем стало стандартом DES (U.S. Data Encryption Standard , Стандарт шифрования данных Соединенных Штатов). В начале 70-х годов IBM опубликовала ряд технических отчетов по криптографии, выполненных Фейстелом и его коллегами [1482, 1484, 552]. Таково было положение, когда в конце 1972 года я начал работать в этой области. Литература по крипт ографии обильной не была, но в ней можно было найти ряд сверкающих самородков. В криптографической науке есть особенность, отсутствующая в обычных академических дисциплинах: нео бходимость взаимодействия криптографии и криптоанализа. Причиной этого является отсутствие требований к передаче реальной информации, следовательно, нетрудно предложить систему, которая кажется непогрешимой. Многие академические разработки настолько сложны, что будущий криптоаналитик не знает с чего начать. О бнаружить дыры в этих проектах намного сложнее, чем разработать их. В результате невозможно соревнование, являющееся одним из сильнейших мотивов в академических исследований. Когда Мартин Хеллман и я в 1975 году предложили криптографию с открытыми ключами [496], одним из косвенных аспектов нашего предложения было появление проблемы, решение которой не кажется простым. Теперь честолюбивый проектировщик мог создать что-то - вполне разумную криптосистему, решающую более обширные задачи, чем простое превращение значимого текста в чепуху. В результате значительно возросло число людей, занимающихся криптографией, число проводимых встреч и число опубликованных книг и статей. В речи по поводу присуждения мне совместно с Мартином Хеллманом премии Дональда Е. Финка (присуждаемой за лучшую пояснительную статью в журнале IEEE) я сказал, что, написав "Privacy and Authentication" ("Секретность и удостоверение подлинности"), я получил опыт, который необычен даже для выдающи хся ученых, получивших премии IEEE. Я написал статью, которую я хотел бы изучить, когда я впервые серьезно заинтересовался криптографией, и которую не смог найти. Если бы я сегодня отправился в Стэнфордскую би блиотеку и собрал бы современные работы по криптографии, я, возможно, получил бы представление о предмете гораздо раньше. Но осенью 1972 года были доступны только несколько классических работ и ряд туманных технических отчетов. У сегодняшнего исследователя нет такой проблемы. Сегодня основная сложность состоит в выборе, с чего начать среди тысяч статей и десятков книг. А сегодняшние программисты и инженеры, которые просто хотят использовать криптографию? К каким источникам им обращаться? До сих пор необходимо было проводить долгие часы, выискивая научную литературу и изучая ее, прежде чем удавалось начать разработку криптогр афических приложений, так гладко описанных в популярных статьях. Именно этот промежуток и призвана заполнить Прикладная криптография Брюса Шнайера. Начав с целей засекречивания передачи данных и элементарных примеров программ для достижения этих целей, Шнайер ра зворачивает перед нами панораму результатов 20 лет открытых исследований. Содержание книги полностью определяется ее названием, вы найдете в ней описание различных приложений, от засекречивания телефонного разговора до электронных денег и криптографического обеспечения выборов. Не удовлетворенный простым изложением алгоритмов и описанием кода, Шнайер включил в книгу обсу ждение различных мировых организаций, связанных с разработкой и применением криптографических средств, от Международной ассоциации криптологических исследований до NSA (National Security Agency, Агентство национальной безопасности). Когда на рубеже 70-х и 80-х годов возрос общественный интерес к криптографии, NSA, официальный криптографичекий орган США, предприняло ряд попыток подавить этот интерес. Первой такой попыткой было письмо старого сотрудника NSA, по видимому действовавшего по своему усмотрению. Письмо было послано в IEEE и предупреждало, что публикация материалов по криптографии является нарушением Правил междун ародной продажи оружия ( International Traffic in Arms Regulations, ITAR) . Эта точка зрения, как оказалось, не поддерживаемая самими правилами, в явном виде содержащими льготы для публикуемых материалов, создала неожиданную рекламу использованию криптографии и Семинару по теории информации 1977 года. Более серьезная попытка была предпринята в 1980 году, когда NSA финансировало изучение вопроса Ам ериканским советом по образованию с целью убедить Конгресс узаконить контроль над публикациями в области криптографии. Результаты, оказавшиеся далекими от ожиданий NSA, привели к программе добровольного р ецензирования работ по криптографии. От исследователей потребовали перед публикацией запрашивать мнение NSA, не принесет ли раскрытие результатов исследований вред национальным интересам. К середине 80-х годов основным объектом внимания стала не теория, а практика криптографии. Сущес твующие законы дают NSA право с помощью Госдепартамента регулировать экспорт криптографического об орудования. Так как бизнес все больше и больше принимает международный характер и американская часть м ирового рынка уменьшается, возрастает желание использовать единый продукт и для внутреннего, и для внешн его рынка. Такие продукты являются субъектами контроля над экспортом, и поэтому NSA получило возможность контролировать не только экспортируемые криптографические продукты, но и продаваемые в Соединенных Штатах. В то время, когда писались эти строки, возникло новое препятствие для общественного использования кри птографии. Правительство дополнило широко опубликованный и используемый алгоритм DES засекреченным алгоритмом, реализованным в микросхемах памяти, независящей от времени. Эти микросхемы будут содержать кодифицированный механизм правительственного контроля. Отрицательные аспекты такой програ ммы-троянского коня простираются от потенциально губительного раскрытия тайны лич ности до высокой стоимости аппаратной модернизации продуктов, ранее реализованных программно. Таким образом, предлагаемое нововведение не вызвало энтузиазма и подверглось широкой критике, особенно со стороны независимых кри птографов. Ряд людей, однако, видят свое будущее в программировании, а не в политике и удваивают свои ус илия, стремясь представить миру мощные средства криптографии. Значительное отступление от возможности того, что закон о контроле над экспортом отменит Первую п оправку1, казалось было сделан в 1980 году, когда в опубликованные в Federal Register исправления ITAR вошло следующее положение: "...положение было добавлено с целью показать, что регулирование экспорта технич еских данных не приведет к конфликту с правами личности, определяемыми Первой поправкой". Но то, что ко нфликт между Первой поправкой и законами о контроле над экспортом не разрешен окончательно, должно быть очевидно из заявлений, сделанных на конференции, проводимой RSA Data Security. Представитель NSA из отдела контроля над экспортом выразил мнение, что люди, публикующие криптографические программы, нах одятся " в серой зоне" по отношению к закону. Если это так, то именно эту "серую зону" немного осветило первое издание этой книги. Экспорт приложений для этой книги был разрешен с подтверждением того, что опублик ованные материалы не попадают под юрисдикцию Совета по контролю над вооружением. Однако, экспортир овать опубликованные программы на диске было запрещено. Изменение стратегии NSA от попыток контролировать криптографические исследования к усилению регул ирования в области разработки и развертывания криптографических продуктов по видимому обусловлено осо знанием того, что все величайшие криптографические работы не защитили ни одного бита информации. Будучи 1 К конституции США поставлен в шкаф, этот том не сделает ничего нового по сравнению с предшествующими книгами и работами, но использование его содержания на рабочей станции, где пишется криптографический код, может привести к иному результату. Уитфилд Диффи Маунтэйн Вью, Калифорния. Введение Криптография бывает двух типов: криптография, которая помешает читать ваши файлы вашей младшей с естре, и криптография, которая помешает читать ваши файлы дядям из правительства. Эта книга о втором типе криптографии. Если я беру письмо, кладу его в сейф где-нибудь в Нью-Йорке, затем велю Вам прочитать это письмо, то это не безопасность. Это непонятно что. С другой стороны, если я беру письмо и кладу его в сейф, затем передаю этот сейф Вам вместе с детальным описанием, передаю также сотню подобных сейфов с их комбинациями, чт обы Вы и лучшие "медвежатники" мира могли изучить систему замков, а вы все равно не сможете открыть сейф и прочитать письмо - вот это и есть безопасность. В течение многих лет этот тип криптографии использовался исключительно в военных целях. Агентство н ациональной безопасности Соединенных Штатов Америки (National Security Agency, NSA) и его аналоги в бывшем Советском Союзе, Англии, Франции, Израиле и прочих странах тратили миллиарды долларов на очень серьезную игру в обеспечение безопасности собственных линий связи, одновременно пытаясь взломать все о стальные. Отдельные личности, обладающие значительно меньшими средствами и опытом, были беспомощны защитить свои секреты от правительств. В течение последних 20 лет значительно вырос объем открытых академических исследований. Пока обычные граждане использовали классическую криптографию, со времен Второй мировой войны компьютерная крипт ография во всем мире применялась исключительно в военной области. Сегодня искусство компьютерной крипт ографии вырвалось из стен военных ведомств. Непрофессионалы получили возможность средства, позволяющие им обезопасить себя от могущественнейших противников, средства, обеспечивающие защиту от военных в едомств. А нужна ли обычному человеку такая криптография? Да. Люди могут планировать политическую кампанию, обсуждать налоги, вести незаконные действия. Они могут разрабатывать новые изделия, обсуждать рыночную политику или планировать захват конкурирующей фирмы. Они могут жить в стране, которая не соблюдает з апрета на вторжение в личную жизнь своих граждан. Они могут делать что-либо, что не кажется им незаконным, хотя таковым и является. По многим причинам данные и линии связи должны быть личными, тайными и з акрытыми от постороннего доступа. Эта книга выходит в свет в беспокойное время. В 1994 году администрация Клинтона приняла Стандарт у словного шифрования (Escrowed Encryption Standard), включая микросхему Clipper и плату Fortezza, и превратило Билль о Цифровой телефонии в закон . Эти инициативы пытаются увеличить возможности правительства проводить электронный контроль. Вступают в силу некоторые опаснейшие домыслы Оруэлла: правительство получает право прослушивать личные переговоры, а с человеком, пытающимся скрыть свои секреты от правительства, может что-нибудь сл учиться. Законодательство всегда разрешало слежку по решению суда, но впервые люди сами должны предпр инимать какие-то шаги, чтобы сделаться доступными для слежки. Эти инициативы не просто предложения пр авительства в некой туманной сфере, это упреждающая и односторонняя попытка присвоить прежде принадл ежащие людям права. Законопроекты о микросхеме Clipper и Цифровой телефонии не способствуют сохранению тайны, но беспо чвенно заставляют людей считать, что правительство уважает их тайны. Те же самые власти, которые незаконно записывали телефоны Мартина Лютера Кинга, могут легко прослушать телефон, защищенный микросхемой Clipper. В недавнем прошлом полицейские власти на местах были привлечены к гражданской или уголовной ответственности за незаконное прослушивание во многих судах - в Мэриленде, Коннектикуте, Вермонте, Джорджии, Миссури и Неваде. Идея развернуть технологию, которая может привести к появлению полице йского государства - это плохая идея. Дело в том, что недостаточно защитить себя законами, нам нужно защитить себя математикой. Шифров ание имеет слишком большое значение, чтобы оставить ее использование только правительствам . Эта книга снабдит Вас инструментарием, позволяющим защитить ваши тайны. Передача криптографич еских продуктов может быть объявлена незаконной, передача информации - никогда . Как читать эту книгу Я написал Прикладную криптографию как живое введение в криптографию и как всеобъемлющий спр авочник. Я пытался сочетать читаемость текста с жертвенной точностью, но эта книга писалась не как математическая работа. Хотя я не искажал информацию умышленно, торопясь, я опускал теорию . Для интересующихся теоретическими выкладками приведены обширные ссылки на академическую литературу . Глава 1 представляет собой введение в криптографию, описывает множество терминов, в ней кратко ра с- сматривается докомпьютерная криптография . Главы со 2 по 6 (Часть I) описывают криптографические протоколы - что люди могут сделать с помощью криптографии - от простых (передача шифрованных сообщений от одного человека другому) до сложных (щелканье монетой по телефону) и тайных (секретное и анонимное обращение электронных денег ). Некоторые из этих протоколов очевидны, другие - удивительны . Множество людей и не представляет многие из проблем, которые может решить криптография . Главы с 7 по 10 (Часть II) содержат обсуждение методов криптографии. Все эти четыре главы важны для самых распространенных применений криптографии. В главах 7 и 8 рассказывается о ключах: какова должна быть длина безопасного ключа, как генерировать, хранить и распределять ключи, и т.д. Управление ключами представляет собой труднейшую часть криптографии и часто является ахиллесовой пятой систем, безопасных во всем остальном. В главе 9 рассматриваются различные способы использования криптографических алгоритмов, а глава 10 описывает особенности и цели использования этих алгоритмов - как их выбирать, реализовывать и применять. Главы с 11 по 23 (Часть III) описывают эти алгоритмы. Глава 11 представляет собой математическую базу и является обязательной только, если вы интересуетесь алгоритмами с открытыми ключами . Если вы собираетесь использовать DES (или что-то похожее), ее можно пропустить. В главе 12 обсуждается алгоритм DES, его история, безопасность и разновидности. В главах 13, 14 и 15 рассказывается о других блочных алгоритмах. Если вам нужно что-то более надежное чем DES, сразу переходите к разделам о IDEA и тройном DES. При желании узнать о группе алгоритмов, некоторые из которых могут быть безопаснее DES, прочитайте всю главу. В главах 16 и 17 обсуждаются потоковые алгоритмы . В главе 18 подробно рассматриваются однонаправленные хэш-функции, среди которых самыми являются MDS и SHA, хотя я останавливаюсь и на многих других . В главе 19 рассматриваются алгоритмы шифрования с открытым ключом , а в главе 20 - алгоритмы цифровой подписи с открытым ключом. В главе 21 обсуждаются алгоритмы идентификации с открытым ключом , а в главе 22 - алгоритмы обмена с открытым ключом . Самыми важными являются алгоритмы RSA, DSA, Фиат-Шамира (Fiat-Shamir) и Диффи-Хелмана (Diffie-Hellman). Глава 23 содержит ряд эзотерических алгоритмов и проток олов с открытым ключом, математика в этой главе достаточно сложна, так что пристегните ремни . Главы 24 и 25 (Часть IV) переносят вас в реальный мир криптографии. В главе 24 обсуждаются некоторые современные применения алгоритмов и протоколов, в то время как глава 25 касается некоторых политических аспектов криптографии. Несомненно, эти главы не являются всеохватывающими . В книгу также включены исходные коды 10 алгоритмов, рассмотренных в Части III. Я не смог включить весь код, который хотел, из-за его большого объема, кроме того, криптографические коды в любом случае нельзя экспортировать. (Любопытно, что Госдепартамент разрешил экспортировать первое издание этой книги с и сходным кодом, но не разрешил экспортировать компьютерный диск с теми же исходными кодами. Смотри р исунок.) Соответствующий набор дисков с исходным кодом содержит существенно больше исходных кодов, чем я смог включить в эту книгу, возможно, это самая большая подборка криптографических исходных кодов, по явившаяся за пределами военных ведомств . Сейчас я могу переслать эти диски с исходным кодом только гра жданам США и Канады, живущим в этих странах, но, возможно, когда-нибудь все изменится. Если вы собира етесь использовать или попробовать эти алгоритмы, добудьте диск . Подробности на последней странице книги. . К недостаткам этой книги относится то, что из-за ее энциклопедической природы пострадала читаемость книги. Я хотел написать единый справочник для тех, кто мог встретиться с каким-либо алгоритмом в академ ической литературе или при использовании какого-то продукта , и заранее извиняюсь перед теми, кто разыскивает учебное пособие. Впервые все множество сделанного в криптографии собрано под одной обложкой . Несмотря на это, соображения объема заставили меня оставить многое за пределами этой книги, я включил те темы, которые мне показались важными, практическими или интересными. Если я не мог полностью охватить тему, я приводил ссылки на соответствующие работы и статьи . Я сделал все, что мог, пытаясь выловить и исправить все ошибки в книге, но многие люди уверяли меня, что это все равно невозможно. Конечно, во втором издании ошибок меньше, чем в первом . Перечень ошибок можно получить у меня, он также периодически рассылается в телеконференции Usenet sci.crypt. Если ктонибудь из читателей обнаружит ошибку, пожалуйста, пусть сообщит мне об этом. Каждому, кто первый обн аружит данную ошибку в книге, я бесплатно пошлю диск с исходным кодом . Благодарности Перечень людей, приложивших руку к созданию этой книги, может показаться бесконечным, но все они до стойны упоминания. Мне хотелось бы поблагодарить Дона Альвареса ( Don Alvarez), Росса Андерсона (Ross Anderson), Дэйва Бейленсона (Dave Balenson), Карла Бармса (Karl Barms), Стива Белловина (Steve Bellovin), Дэна Бернстайна (Dan Bernstein), Эли Байем (Ell Biham), Джоан Бояр (Joan Boyar), Карен Купер (Karen Cooper), Вита Диффи (Whit Diffie), Джоан Фейгенбаум (Joan Feigenbaum), Фила Кана (Phil Karn), Нила Коблица (Neal Koblitz), Ксуейа Лай (Xuejia Lai), Тома Леранта (Tom Leranth), Майка Марковица (Mike Markowitz), Ральфа Меркла (Ralph Merkle), Билла Паттена (Bill Patten), Питера Пирсона (Peter Pearson), Чарльза Пфлегера (Charles Pfleeger), Кена Пиццини (Ken Pizzini), Барта Пренела (Bart Preneel), Марка Риордана (Mark Riordan), Йоахима Шурмана (Joachim Schurman) и Марка Шварца (Marc Schwartz) за чтение и редактирование всего первого и здания или его частей; Марка Воклера (Marc Vauclair) за перевод первого издания на французский ; Эйба Абрахама (Abe Abraham), Росса Андерсона (Ross Anderson), Дэйва Бенисара (Dave Banisar), Стива Белловина (Steve Bellovin), Эли Байем (Ell Biham), Мэтта Бишопа (Matt Bishop), Мэтта Блэйза (Matt Blaze), Гэри Картера (Gary Carter), Жана Комениша (Jan Comenisch), Клода Крепо (Claude Crepeau), Джоан Дэймон (Joan Daemon), Хорхе Давила (Jorge Davila), Эда Доусона (Ed Dawson), Вита Диффи (Whit Diffie), Карла Эллисона ( Carl Ellison), Джоан Фейгенбаум (Joan Feigenbaum), Нильса Фергюсона (Niels Ferguson), Матта Франклина (Matt Franklin), Розарио Сеннаро (Rosario Cennaro), Дитера Колмана (Dieter Collmann), Марка Горески (Mark Goresky), Ричарда Грэйвмана (Richard Graveman), Стюарта Хабера (Stuart Haber), Джингмана Хе (Jingman He), Боба Хэйга (Bob Hague), Кеннета Айверсона (Kenneth Iversen), Маркуса Джекобсона (Markus Jakobsson), Берта Калиски (Burt Kaliski), Фила Кана (Phil Karn), Джона Келси (John Kelsey), Джона Кеннеди (John Kennedy), Ларса Кнудсена (Lars Knudsen), Пола Кочера (Paul Kocher), Джона Лэдвига (John Ladwig), Ксуейа Лай (Xuejia Lai), Аджена Ленстры (Arjen Lenstra), Пола Лейланда (Paul Leyland), Майка Марковица (Mike Markowitz), Джима Мэсси (Jim Massey), Брюса МакНейра (Bruce McNair), Вильяма Хью Мюррея (William Hugh Murray), Роджера Нидхэма (Roger Needham), Клифа Неймана (Clif Neuman), Кейсу Найберг (Kaisa Nyberg), Люка О'Коннора (Luke O'Connor), Питера Пирсона (Peter Pearson), Рене Перальта (Rene Peralta), Барта Пренела (Bart Preneel), Израиля Радай (Yisrael Radai), Мэтта Робшоу (Matt Robshaw), Майкла Роу (Michael Roe), Фила Рогуэя (Phil Rogaway), Эви Рубина (Avi Rubin), Пола Рубина (Paul Rubin), Селвина Рассела (Selwyn Russell), Казуе Сако (Kazue Sako), Махмуда Салмасизадеха (Mahmoud Salmasizadeh), Маркуса Стадлера (Markus Stadler), Дмитрия Титова (Dmitry Titov), Джимми Аптона (Jimmy Upton), Марка Воклера (Marc Vauclair), Сержа Воденея (Serge Vaudenay), Гидеона Ювала (Gideon Yuval), Глена Зорна (Glen Zorn) и многих безымянных правительственных сл ужащих за чтение и редактирование всего второго издания или его частей ; Лори Брауна (Lawrie Brown), Лизу Кэндл (Leisa Candle), Джоан Дэймон (Joan Daemon), Питера Гутмана (Peter Gutmann), Алана Инсли (Alan Insley), Криса Джонстона (Chris Johnston), Джона Келси (John Kelsey), Ксуейа Лай (Xuejia Lai), Билла Лейнингера (Bill Leininger), Майка Марковица (Mike Markowitz), Ричарда Аутбриджа (Richard Outerbridge), Питера Пирсона (Peter Pearson), Кена Пиццини (Ken Pizzini), Кэлма Пламба (Calm Plumb), RSA Data Security, Inc., Майкла Роу (Michael Roe), Майкла Вуда (Michael Wood) и Фила Циммермана (Phil Zimmermann) за предоставленные исходные коды; Пола МакНерланда (Paul MacNerland) за создание рисунков к первому издания ; Карен Купер (Karen Cooper) за редактирование второго издания ; Бота Фридмана (Both Friedman) за сверку второго издания; Кэрол Кеннеди (Кэрол Kennedy) за работу над предметным указателем для второго издания ; читателей sci.crypt и почтового списка Cypherpunks за комментирование идей, ответы на вопросы и поиск ошибок первого издания; Рэнди Сюсс (Randy Seuss) за предоставление доступа к Internet; Джеффа Дантермана (Jeff Duntemann) и Джона Эриксона (Jon Erickson) за то, что помогли мне начать; семью Insley (в произвольном порядке) за ст имуляцию, воодушевление, поддержку, беседы, дружбу и обеды ; и AT&T Bell Labs, зажегшей меня и сделавшей возможным все это. Все эти люди помогли создать гораздо лучшую книгу, чем я бы смог создать в одиночку . Брюс Шнайер Оак Парк, Иллинойс schneier@counterpane.com Об авторе БРЮС ШНАЙЕР - президент Counterpane Systems, Оак Парк, Иллинойс, фирма-консультант, специализ ирующаяся в криптографии и компьютерной безопасности . Брюс также написал E-Mail Security , John Wiley & Sons, 1995, (Безопасность электронной почты ) и Protect Your Macintosh , Peachpit Press, 1994, (Защити свой Макинтош ). Он является автором дюжин статей по криптографии в основных журналах . Он также соредактор Dr. Dobb's Journal (Журнал доктора Добба ), где он редактирует колонку "Аллея алгоритмов" , и соредактор Computer a nd Communications Security Reviews (Обзор безопасности компьютеров и линий связи) . Брюс входит в совет директоров Международной Ассоциации Криптологических Исследований ( International Association for Cryptologic Research), является членом Консультационного совета Центра Секретности Электронной Информации (Electronic Privacy Information Center ) и входит в комитет программы Семинара по Новым парадигмам Безопасности (New Security Paradigms Workshop ). К тому же, он находит время для частых лекций по крипт ографии, компьютерной безопасности и секретности . Глава 1 Основные понятия 1.1 Терминология Отправитель и получатель Предположим, что отправитель хочет послать сообщение получателю . Более того, этот отправитель хочет послать свое сообщение безопасно : он хочет быть уверен, что перехвативший это сообщение не сможет его пр очесть. Сообщения и шифрование Само сообщение называется открытым текстом (иногда используется термин клер ). Изменение вида сообщения так, чтобы спрятать его суть называется шифрованием. Шифрованное сообщение называется шифротекстом. Процесс преобразования шифротекста в открытый текст называется дешифрированием. Эта последовательность показана на 0th. (Если вы хотите следовать стандарту ISO 7498-2, то в английских текстах используйте термины "enchipher" вместо " encrypt" ( "зашифровывать") и "dechipher" вместо " decrypt" ("дешифровывать")). Искусство и наука безопасных сообщений, называемая криптографией, воплощается в жизнь криптографами. Криптоаналитиками называются те, кто постоянно используют криптоанализ, искусство и науку взламывать шифротекст, то есть, раскрывать, что находится под маской . Отрасль математики, охватывающая криптографию и криптоанализ, называется криптологией, а люди, которые ей занимаются, - криптологами. Современным криптологам приходится неплохо знать математику . Открытый текст Шифротекст Первоначальный открытый текст Шифрование Дешифрирование Рис. 1-1. Шифрование и дешифрирование Обозначим открытый текст как M (от message, сообщение), или P (от plaintext , открытый текст). Это может быть поток битов, текстовый файл, битовое изображение, оцифрованный звук, цифровое видеоизображение… да что угодно. Для компьютера M - это просто двоичные данные. (Во всех следующих главах этой книги ра ссматриваются только двоичные данные и компьютерная криптография .) Открытый текст может быть создан для хранения или передачи. В любом случае , M - это сообщение, которое должно быть зашифровано . Обозначим шифротекст как C (от ciphertext ). Это тоже двоичные данные, иногда того же размера, что и M, иногда больше. (Если шифрование сопровождается сжатием, C может быть меньше чем M. Однако, само шифрование не обеспечивает сжатие информации .) Функция шифрования E действует на M, создавая C. Или, в математической записи: E(M) = C В обратном процессе функция дешифрирования D действует на C, восстанавливая M: D(C) = M Поскольку смыслом шифрования и последующего дешифрирования сообщения является восстановление пе рвоначального открытого текста, должно выполняться следующее равенство : D(E(M)) = M Проверка подлинности, целостность и неотрицание авторства Кроме обеспечения конфиденциальности криптография часто используется для других функций : — Проверка подлинности. Получатель сообщения может проверить его источник, злоумышленник не сможет замаскироваться под кого-либо. — Целостность. Получатель сообщения может проверить, не было ли сообщение изменено в процессе доставки, злоумышленник не сможет подменить правильное сообщение ложным. — Неотрицание авторства. Отправитель не сможет ложно отрицать отправку сообщения. Существуют жизненно важные требования к общению при помощи компьютеров, также как существуют ана- логичные требования при общении лицом к лицу. То, что кто-то является именно тем, за кого он себя выдает … что чьи-то документы - водительские права, медицинская степень или паспорт - настоящие … что документ, полученный от кого-то, получен именно от этого человека… Как раз это обеспечивают проверка подлинности, целостность и неотрицание авторства . Алгоритмы и ключи Криптографический алгоритм, также называемый шифром, представляет собой математическую фун кцию, используемую для шифрования и дешифрирования . (Обычно это две связанных функции: одна для ши фрования, а другая для дешифрирования .) Если безопасность алгоритма основана на сохранении самого алгоритма в тайне, это ограниченный алгоритм. Ограниченные алгоритмы представляют только исторический интерес, но они совершенно не соответс твуют сегодняшним стандартам. Большая или изменяющаяся группа пользователей не может использовать такие алгоритмы, так как всякий раз, когда пользователь покидает группу, ее члены должны переходить на другой алгоритм. Алгоритм должен быть заменен и, если кто-нибудь извне случайно узнает секрет. Что еще хуже, ограниченные алгоритмы не допускают качественного контроля или стандартизации. У ка ждой группы пользователей должен быть свой уникальный алгоритм . Такие группы не могут использовать о ткрытые аппаратные или программные продукты - злоумышленник может купить такой же продукт и раскрыть алгоритм. Им приходится разрабатывать и реализовывать собственные алгоритмы. Если в группе нет хорошего криптографа, то как ее члены проверят, что они пользуются безопасным алгоритмом? Несмотря на эти основные недостатки ограниченные алгоритмы необычайно популярны для приложений с низким уровнем безопасности. Пользователи либо не понимают проблем, связанных с безопасностью своих систем, либо не заботятся о них. Современная криптография решает эти проблемы с помощью ключа K. Такой ключ может быть любым значением, выбранным из большого множества. Множество возможных ключей называют пространством ключей. И шифрование, и дешифрирование этот ключ (то есть, они зависят от ключа, что обозначается инде ксом K), и теперь эти функции выглядят как : EK(M)=C DK(C)=M При этом выполняется следующее равенство (см -1-й): DK(EK(M))=M Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи (см -2-й). То есть ключ шифрования, К1, отличается от соответствующего ключа дешифрирования, K2. В этом случае: E K1 (M)=C DK2 (C)=M DK2 (E K1 (M))=M Безопасность этих алгоритмов полностью основана на ключах, а не на деталях алгоритмов. Это значит, что алгоритм может быть опубликован и проанализирован. Продукты, использующие этот алгоритм, могут широко тиражироваться. Не имеет значения, что злоумышленнику известен ваш алгоритм, если ему не известен ко нкретный ключ, то он не сможет прочесть ваши сообщения . Криптосистема представляет собой алгоритм плюс все возможные открытые тексты, шифротексты и ключи . Ключ Открытый текст Шифротекст Ключ Первоначальный открытый текст Шифрование Дешифрирование Рис. 1-2. Шифрование и дешифрирование с ключом Ключ шифрования Открытый текст Шифротекст Ключ дешифрирования Первоначальный открытый текст Шифрование Дешифрирование Рис. 1-3. Шифрование и дешифрирование с двумя различными ключами Симметричные алгоритмы Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом . Симметричные алгоритмы, иногда называемые условными алгоритмами , представляют собой алгоритмы, в которых ключ шифрования может быть рассчитан по ключу дешифрирования и наоборот . В большинстве симметричных алгоритмов кличи шифрования и дешифрирования одни и те же . Эти алгоритмы, также называемые алгоритмами с секретным ключом или алгоритмами с одним ключом, требуют, чтобы отправитель и получатель согласовали используемый ключ перед началом безопасной передачи сообщений . Безопасность симметричного алгоритма определяется ключом, раскрытие ключа означает, что кто угодно сможет шифровать и дешифрир овать сообщения. Пока передаваемые сообщения должны быть тайными, ключ должен храниться в секрете . Шифрование и дешифрирование с использованием симметричного алгоритма обозначается как : EK(M)=C DK(C)=M Симметричные алгоритмы делятся на две категории . Одни алгоритмы обрабатывают открытый текст побитно (иногда побайтно), они называются потоковыми алгоритмами или потоковыми шифрами. Другие работаю с группами битов открытого текста. Группы битов называются блоками, а алгоритмы - блочными алгоритмами или блочными шифрами. Для алгоритмов, используемых в компьютерных модемах, типичный размер блока составляет 64 бита - достаточно большое значение, чтобы помешать анализу, и достаточно небольшое и удобное для работы. (До появления компьютеров алгоритмы обычно обрабатывали открытый текст посимвольно . Такой вариант может рассматриваться как потоковый алгоритм, обрабатывающий поток символов .) Алгоритмы с открытым ключом Алгоритмы с открытым ключом (называемые асимметричными алгоритмами ) разработаны таким образом, что ключ, используемый для шифрования, отличается от ключа дешифрирования . Более того, ключ дешифрирования не может быть (по крайней мере в течение разумного интервала времени ) рассчитан по ключу шифрования. Алгоритмы называются "с открытым ключом", потому что ключ шифрования может быть открытым: кто угодно может использовать ключ шифрования для шифрования сообщения, но только конкретный ч еловек с соответствующим ключом дешифрирования может расшифровать сообщение . В этих системах ключ шифрования часто называется открытым ключом, а ключ дешифрирования - закрытым. Закрытый ключ иногда называется секретным ключом, но чтобы не было путаницы с симметричными алгоритмами, этот термин не используется в данной книге. Шифрование с открытым ключом K обозначается как: EK(M)=C Хотя открытый и закрытый ключи различны, дешифрирование с соответствующим закрытым ключом об означается как: DK(C)=M Иногда сообщения шифруются закрытым ключом, а дешифрируются открытым, что используется для ци фровой подписи (см. раздел 2.6). Несмотря на возможную путаницу эти операции, соответственно, обозначаю тся как: EK(M)=C DK(C)=M Криптоанализ Смысл криптографии - в сохранении открытого текста (или ключа, или и того, и другого) в тайне от зл оумышленников (также называемых взломщиками , соперниками, врагами, перехватчиками ). Предполагается, что злоумышленники полностью контролируют линии связи между отправителем и получателем . Криптоанализ - это наука получения открытого текста, не имея ключа . Успешно проведенный криптоанализ может раскрыть открытый текст или ключ . Он также может обнаружить слабые места в криптосистемах, что в конце концов приведет к предыдущему результату . (Раскрытие ключа не криптологическими способами наз ы- вается компрометацией.) Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сфо рмулированное в девятнадцатом веке Датчманом А. Керкхофсом ( Dutchman A. Kerckhoffs), iсостоит в том, что безопасность полностью определяется ключом [794]. Керкхофс предполагает, что у криптоаналитика есть по лное описание алгоритма и его реализации . (Конечно же, у ЦРУ не в обычае сообщать Моссад о своих крипт ографических алгоритмах, но Моссад возможно все равно добудет их .) Хотя в реальном мире криптоаналитики не всегда обладают подробной информацией, такое предположение является хорошей рабочей гипотезой . Если противник не сможет взломать алгоритм, даже зная, как он работает, то тем более враг не сможет вскрыть а лгоритм без этого знания. Существует четыре основных типа криптоаналитического вскрытия . Для каждого из них, конечно, предп олагается, что криптоаналитик обладает всей полнотой знания об используемом алгоритме шифрования : 1. Вскрытие с использованием только шифротекста. У криптоаналитика есть шифротексты нескол ьких сообщений, зашифрованных одним и тем же алгоритмом шифрования . Задача криптоаналитика состоит в раскрытии открытого текста как можно большего числа сообщений или, что лучше, получ ении ключа (ключей), использованного для шифрования сообщений, для дешифрировании других с ообщений, зашифрованных теми же ключами . Дано: C1=Ek(P1), C2=Ek(P2), . . . Ci =Ek(Pi ) Получить: Либо P1, P2, . . . Pi ; k; либо алгоритм, как получать Pi+1 из Ci+1=Ek(Pi+1) 2. Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифр отекстам нескольких сообщений, но и к открытому тексту этих сообщений . Его задача состоит в получении ключа (или ключей), использованного для шифрования сообщений, для дешифрировании др угих сообщений, зашифрованных тем же ключом (ключами) . Дано: P1, C1=Ek(P1), P2, C2=Ek(P2), . . . Pi , Ci =Ek(Pi ) Получить: Либо k; либо алгоритм, как получать Pi+1 из Ci+1=Ek(Pi+1) 3. Вскрытие с использованием выбранного открытого текста . У криптоаналитика не только есть доступ к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать о ткрытый текст для шифрования. Это предоставляет больше вариантов чем вскрытие с использованием открытого текста, так как криптоаналитик может выбирать шифруемые блоки открытого текста, что может дать больше информации о ключе . Его задача состоит в получении ключа (или ключей), и спользованного для шифрования сообщений, или алгоритма, позволяющего дешифрировать новые с ообщения, зашифрованные тем же ключом (или ключами) . Дано: P1, C1=Ek(P1), P2, C2=Ek(P2), . . . Pi , Ci =Ek(Pi ) где криптоаналитик может выбирать P1, P2, . . . Pi Получить: Либо k; либо алгоритм, как получать Pi+1 из Ci+1=Ek(Pi+1) 4. Адаптивное вскрытие с использованием открытого текста . Это частный случай вскрытия с использованием выбранного открытого текста . Криптоаналитик не только может выбирать шифруемый текст, но также может строить свой последующий выбор на базе полученных результатов шифрования. При вскрытии с использованием выбранного открытого текста криптоаналитик мог выбрать для шифрования только один большой блок открытого текста, при адаптивном вскрытии с и спользованием выбранного открытого текста он может выбрать меньший блок открытого текста, затем выбрать следующий блок, используя результаты первого выбора и так далее . Существует по крайней мере еше три типа криптоаналитической вскрытия . 5. Вскрытие с использованием выбранного шифротекста . Криптоаналитик может выбрать разли чные шифротексты для дешифрирования и имеет доступ к дешифрированным открытым текстам . Например, у криптоаналитика есть доступ к "черному ящику", который выполняет автоматическое д ешифрирование. Его задача состоит в получении ключа . Дано: C1, P1=Dk(C1), C2, P2=Dk(C2), . . . Ci , Pi =Dk(Ci ) Получить: k Такой тип вскрытия обычно применим к алгоритмам с открытым ключом и обсуждается в разделе 19.3. Вскрытие с использование выбранного шифротекста иногда также эффективно против симме тричных алгоритмов. (Иногда вскрытие с использованием выбранного открытого текста и вскрытие с использованием выбранного шифротекста вместе называют вскрытием с использованием выбранного текста.) 6. Вскрытие с использованием выбранного ключа. Такой тип вскрытия означает не то, что крипто аналитик может выбирать ключ, а что у него есть некоторая информация о связи между различными ключами. Этот странный, запутанный и не очень практичный тип вскрытия обсуждается в разделе 12.4. 7. Бандитский криптоанализ. Криптоаналитик угрожает, шантажирует или пытает кого-нибудь, пока не получит ключ. Взяточничество иногда называется вскрытием с покупкой ключа. Это очень мощные способы вскрытия, часто являющиеся наилучшим путем взломать алгоритм . Вскрытия с известным открытым текстом и с использованием выбранного открытого текста встречаются чаще, чем можно подумать. Не является невозможным для криптоаналитика добыть открытый текст шифр ованного сообщения или подкупить кого-нибудь, кто зашифрует выбранное сообщение . Может и не потребоваться никого подкупать - передав письмо послу, вы, возможно, обнаружите, что письмо будет зашифровано и отправлено в его страну для изучения . Многие сообщения имеют стандартные начало и окончание, что может быть известно криптоаналитику. Особенно уязвим шифрованный исходный код из-за частого использования ключевых слов: #define, struct, else, return. Те же проблемы и у шифрованного исполнимого кода : функции, циклические структуры и так далее . Вскрытия с известным открытым текстом (и вскрытия с выбранным шифротекстом) успешно использовались в борьбе с немцами и японцами в ходе Второй мировой войны . Исторические примеры вскрытий такого типа можно найти в книгах Дэвида Кана [794,795,796]. И не забывайте о предположении Керкхофса : если мощь вашей новой криптосистемы опирается на то, что взломщик не знает, как работает алгоритм, вы пропали . Если вы считаете, что хранение принципа работы а лгоритма в секрете лучше защитит вашу криптосистему, чем предложение академическому сообществу проан ализировать алгоритм, вы ошибаетесь . А если вы думаете, что кто-то не сможет дезассемблировать ваш исхо дный код и восстановить ваш алгоритм, вы наивны . (В 1994 году такое произошло с алгоритмом RC4, см. раздел 17.1.) Нашими лучшими алгоритмами являются те, которые были разработаны открыто, годами взламыв ались лучшими криптографами мира и все еще несокрушимы . (Агентство Национальной Безопасности хранит свои алгоритмы в секрете, но у них работают лучшие криптографы мира, а у вас - нет. Кроме того, они обсу ждают свои алгоритмы друг с другом, полагаясь на способность товарища обнаружить все слабости в своей р аботе.) У криптоаналитиков не всегда есть доступ к алгоритмам (например, вскрытие в ходе Второй мировой войны Соединенными Штатами японского дипломатического кода PURPLE [794]), но часто они его получают. Если алгоритм используется в коммерческой программе безопасности, то это просто вопрос времени и денег, удас тся ли дезассемблировать программу и раскрыть алгоритм . Если же алгоритм используется в военной системе связи, то это просто вопрос времени и денег купить (или украсть) аппаратуру и реконструировать алгоритм . Те, кто стремится получить нераскрываемый шифр, считая этот шифр таковым только потому, что они сами не смогли его взломать, либо гении, либо дураки . К несчастью, последних в мире достаточно много . Остерегайтесь людей, расхваливающих надежность своих алгоритмов, но отказывающихся их опубликовать. Дов ерять таким алгоритмам нельзя. Хорошие криптографы опираются на мнение других, отделяя хорошие алгоритмы от плохих . Безопасность алгоритмов Различные алгоритмы предоставляют различные степени безопасности в зависимости от того, насколько трудно взломать алгоритм. Если стоимость взлома алгоритма выше, чем стоимость зашифрованных данных, вы, скорее всего, в безопасности . Если время взлома алгоритма больше, чем время, в течение которого заши фрованные данные должны сохраняться в секрете, то вы также, скорее всего, в безопасности . Если объем данных, зашифрованных одним ключом, меньше, чем объем данных, необходимый для взлома алгоритма, и тогда вы, скорее всего, в безопасности . Я говорю "скорее всего", потому что существует вероятность новых прорывов в криптоанализе . С другой стороны, значимость большинства данных падает со временем . Важно, чтобы значимость данных всегда ост авалась меньше, чем стоимость взлома системы безопасности, защищающей данные . Ларс Кнудсен (Lars Knudsen) разбил вскрытия алгоритмов по следующим категориям, приведенным в п орядке убывания значимости [858]: 1. Полное вскрытие. Криптоаналитик получил ключ, K, такой, что DK(C) = P. 2. Глобальная дедукция. Криптоаналитик получил альтернативный алгоритм, A, эквивалентный DK(C) без знания K. 3. Местная (или локальная) дедукция. Криптоаналитик получил открытый текст для перехваченного шифротекста. 4. Информационная дедукция. Криптоаналитик получил некоторую информацию о ключе или откр ытом тексте. Такой информацией могут быть несколько бит ключа, сведения о форме открытого текста и так далее. Алгоритм является безусловно безопасным, если, независимо от объема шифротекстов у криптоаналитика, информации для получения открытого текста недостаточно . По сути, только шифрование одноразовыми бло кнотами (см. раздел 1.5) невозможно вскрыть при бесконечных ресурсах . Все остальные криптосистемы по двержены вскрытию с использованием только шифротекста простым перебором возможных ключей и прове ркой осмысленности полученного открытого текста . Это называется вскрытием грубой силой (см. раздел 7.1). Криптография больше интересуется криптосистемами, которые тяжело взломать вычислительным способом . Алгоритм считается вычислительно безопасным (или, как иногда называют, сильным ), если он не может быть взломан с использованием доступных ресурсов сейчас или в будущем . Термин "доступные ресурсы" явл яется достаточно расплывчатым. Сложность вскрытия можно измерить (см раздел 11.1) различными способ ами: 1. Сложность данных. Объем данных, используемых на входе операции вскрытия . 2. Сложность обработки. Время, нужное для проведения вскрытия . Часто называется коэффициентом работы. 3. Требования к памяти. Объем памяти, необходимый для вскрытия . В качестве эмпирического метода сложность вскрытия определяется по максимальному из этих трех коэфф ициентов. Ряд операций вскрытия предполагают взаимосвязь коэффициентов : более быстрое вскрытие возможно за счет увеличения требований к памяти . Сложность выражается порядком величины . Если сложность обработки для данного алгоритма составляет 2128, то 2128 операций требуется для вскрытия алгоритма . (Эти операции могут быть сложными и длительными .) Так, если предполагается, что ваши вычислительные мощности способны выполнять миллион операций в с екунду, и вы используете для решения задачи миллион параллельных процессоров, получение ключа займет у вас свыше 10 19 лет, что в миллиард раз превышает время существования вселенной . В то время, как сложность вскрытия остается постоянной (пока какой-нибудь криптоаналитик не придумает лучшего способа вскрытия), мощь компьютеров растет . За последние полвека вычислительные мощности ф еноменально выросли, и нет никаких причин подозревать, что эта тенденция не будет продолжена . Многие криптографические взломы пригодны для параллельных компьютеров: задача разбивается на миллиарды маленьких кусочков, решение которых не требует межпроцессорного взаимодействия . Объявление алгоритма безопасным просто потому, что его нелегко взломать, используя современную технику, в лучшем случае ненадежно. Хор ошие криптосистемы проектируются устойчивыми к взлому с учетом развития вычислительных средств на много лет вперед. Исторические термины Исторически термин код относится к криптосистеме, связанной с лингвистическими единицами: словами, фразами, предложениями и так далее. Например, слово "ОЦЕЛОТ" может кодировать целую фразу "ПОВОРОТ НАЛЕВО НА 90 ГРАДУСОВ", слово "ЛЕДЕНЕЦ" - фразу "ПОВОРОТ НАПРАВО НА 90 ГРАДУСОВ", а слова "ПОДСТАВЬ УХО" могут кодировать слово "ГАУБИЦА". Коды такого типа не рассматриваются в данной кн иге, см. [794,795]. Коды полезны только при определенных обстоятельствах . Если у вас нет кода для "МУРАВЬЕДЫ", вы не сможете передать это понятие. А используя шифр можно сказать все. 1.2 Стеганография Стеганография служит для передачи секретов в других сообщениях, так что спрятано само существование секрета. Как правило отправитель пишет какое-нибудь неприметное сообщение, а затем прячет секретное соо бщение на том же листе бумаги. Исторические приемы включают невидимые чернила, невидимые простому гл азу пометки у букв, плохо заметные отличия в написании букв, пометки карандашом машинописных символов, решетки, покрывающие большую часть сообщения кроме нескольких символов и тому подобное. Ближе к сегодняшнему дню люди начали прятать секреты в графических изображениях, заменяя младший значащий бит изображения битом сообщения. Графическое изображение при этом менялось совсем незаметно большинство графических стандартов определяют больше цветовых градаций, чем способен различить челов еческий глаз - и сообщение извлекалось на противоположном конце . Так в черно-белой картинке 1024х1024 пи ксела можно спрятать можно спрятать сообщение в 64 Кбайт . Многие общедоступные программы могут прод елывать подобный фокус. Имитационные функции Питера Уэйнера (Peter Wayner) маскируют сообщения. Эти функции изменяют сообщение так, что его статистический профиль становится похожим на что-нибудь еще: раздел The New York Times, a пьесу Шекспира или телеконференцию в Internet [1584,1585]. Этот тип стеганографии не одурачит ч еловека, но может обмануть большой компьютер, ищущий нужную информацию в Internet. 1.3 Подстановочные и перестановочные шифры До появления компьютеров криптография состояла из алгоритмов на символьной основе . Различные криптографические алгоритмы либо заменяли одни символы другими, либо переставляли символы. Лучшие алгоритмы делали и то, и другое, и по много раз. Сегодня все значительно сложнее, но философия остается прежней. Первое изменение заключается в том, что алгоритмы стали работать с битами, а не символами. Это важно хотя бы с точки зрения размера алфавита с 26 элементов до двух. Большинство хороших криптографических алгоритмов до сих пор комбинирует подст ановки и перестановки. Подстановочные шифры Подстановочным шифром называется шифр, который каждый символ открытого текста в шифротексте з аменяет другим символом. Получатель инвертирует подстановку шифротекста, восстанавливая открытый текст . В классической криптографии существует четыре типа подстановочных шифров : — Простой подстановочный шифр, или моноалфавитный шифр, - это шифр, который каждый символ открытого текста заменяет соответствующим символом шифротекста . Простыми подстановочными ши фрами являются криптограммы в газетах . — Однозвучный подстановочный шифр похож на простую подстановочную криптосистему за исключ ением того, что один символ открытого текста отображается на несколько символов шифротекста . Например, "A" может соответствовать 5, 13, 25 или 56, "B" - 7, 19, 31 или 42 и так далее. — Полиграмный подстановочный шифр - это шифр, который блоки символов шифрует по группам . Например, "ABA" может соответствовать "RTQ", "ABB" может соответствовать "SLL" и так далее. — Полиалфавитный подстановочный шифр состоит из нескольких простых подстановочных шифров . Например, могут быть использованы пять различных простых подстановочных фильтров ; каждый символ открытого текста заменяется с использованием одного конкретного шифра . Знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящег ося тремя символами правее по модулю 26 ("A" заменяется на "D," "B" - на "E", ... "W" - на " Z ", "X" - на "A", "Y" - на "B", "Z" - на "C"), представляет собой простой подстановочный фильтр . Он действительно очень прост, так как алфавит шифротекста представляет собой смещенный, а не случайно распределенный алфавит открыт ого текста. ROTI3 - это простая шифровальная программа, обычно поставляемая с системами UNIX. Она также является простым подстановочным шифром . В этом шифре "A" заменяется на "N," "B" - на "O" и так далее. Каждая буква смещается на 13 мест. Шифрование файла программой ROTI3 дважды восстанавливает первоначальный файл. P = ROT13 (ROT13 (P)) ROTI3 не используется для безопасности, она часто применяется в почте, закрывая потенциально неприя тный текст, решение головоломки и тому подобное . Простые подстановочные шифры легко раскрываются, так как шифр не прячет частоты использования ра зличных символов в открытом тексте . Чтобы восстановить открытый текст, хорошему криптоаналитику требуе тся только знать 26 символов английского алфавита [1434]. Алгоритм вскрытия таких шифров можно найти в [578, 587, 1600, 78, 1475, 1236, 880]. Хороший компьютерный алгоритм приведен в [703]. Однозвучные подстановочные шифры использовались уже в 1401 году в герцогстве Мантуа [794]. Они более сложны для вскрытия, чем простые подстановочные шифры, хотя и они не скрывают всех статистических свойств языка открытого текста. При помощи вскрытия с известным открытым текстом эти шифры раскрыв аются тривиально. Вскрытие с использованием только шифротекста более трудоемко, но и оно занимает на ко мпьютере лишь несколько секунд. Подробности приведены в [1261]. Полиграмные подстановочные шифры - это шифры, которые кодируют сразу группы символов . Шифр Playfair ("Честная игра"), изобретенный в 1854 году, использовался англичанами в Первой мировой войне [794]. Он шифрует пары символов, и его криптоанализ обсуждается в [587,1475,880]. Другим примером полиграмного подстановочного шифра является шифр Хилла ( Hill) [732]. Иногда можно видеть как вместо шифра используе тся кодирование по Хаффману (Huffman), это небезопасный полиграмный подстановочный шифр . Полиалфавитные подстановочные шифры были изобретены Лином Баттистой ( Lean Battista) в 1568 году [794]. Они использовались армией Соединенных Штатов в ходе Гражданской войны в Америке . Несмотря на то, что они легко могут быть взломаны [819, 577, 587, 794] (особенно с помощью компьютеров ), многие коммерческие продукты компьютерной безопасности используют такие шифры [1387,1390, 1502]. (Подробности того, как вскрыть эту схему шифрования, используемую программой WordPerfect, можно найти в [135,139].) Шифр Вигенера (Vigenere), впервые опубликованный в 1586 году, и шифр Бофора (Beaufort) также являются примерами полиалфавитных подстановочных шифров . У полиалфавитных подстановочных шифров множественные однобуквенные ключи, каждый из которых и спользуется для шифрования одного символа открытого текста . Первым ключом шифруется первый символ о ткрытого текста, вторым ключом - второй символ, и так далее . После использования всех ключей они повтор яются циклически. Если применяется 20 однобуквенных ключей, то каждая двадцатая буква шифруется тем же ключом. Этот параметр называется периодом шифра. В классической криптографии шифры с длинным периодом было труднее раскрыть, чем шифры с коротким периодом. Использование компьютеров позволяет легко раскрыть подстановочные шифры с очень длинным периодом . Шифр с бегущим ключом (иногда называемый книжным шифром), использующий один текст для шифр ования другого текста, представляет собой другой пример подобного шифра . И хотя период этого шифра равен длине текста, он также может быть легко взломан [576,794]. Перестановочные шифры В перестановочном шифре меняется не открытый текст, а порядок символов. В простом столбцовом перестановочном шифре открытый текст пишется горизонтально на разграфленном листе бумаги фиксирова нной ширины, а шифротекст считывается по вертикали (см. -3-й). Дешифрирование представляет собой запись шифротекста вертикально на листе разграфленной бумаги фиксированной ширины и затем считывание откр ытого текста горизонтально. Криптоанализ этих шифров обсуждается в [587,1475]. Так как символы шифротекста те же, что и в откр ытом тексте, частотный анализ шифротекста покажет, что каждая буква встречается приблизительно с той же частотой, что и обычно. Это даст криптоаналитику возможность применить различные методы, определяя пр авильный порядок символов для получения открытого текста . Применение к шифротексту второго перестаново чного фильтра значительно повысит безопасность . Существуют и еще более сложные перестановочные фильтры, но компьютеры могут раскрыть почти все из них . Немецкий шифр ADFCVX, использованный в ходе Первой мировой войны , представлял собой перестановочный фильтр в сочетании с простой подстановкой . Этот для своего времени очень сложный алгоритм был раскрыт Жоржем Пенвэном (Georges Painvin), французским криптоаналитиком [794]. Хотя многие современные алгоритмы используют перестановку, с этим связана проблема использования большого объема памяти, а также иногда требуется работа с сообщениями определенного размера . Подстановка более обычна. Роторные машины В 1920-х годах для автоматизации процесса шифрования были изобретены различные механические устро йства. Большинство использовало понятие ротора, механического колеса, используемого для выполнения по дстановки. Роторная машина, включающая клавиатуру и набор роторов , реализует вариант шифра Вигенера . Каждый ротор представляет собой произвольное размещение алфавита, имеет 26 позиций и выполняет простую подст ановку. Например, ротор может быть использован для замены "A" на " F", "B" на "U", "C'' на "I" и так далее. В ыходные штыри одного ротора соединены с входными штырями следующего ротора. Открытый текст:COMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST IT'S EXPENSIVE. COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE Шифротекст:CAELP OPSEE MHLAN PIOSS UCWTI TCBIV EMUTE RATSG YAERB TX Рис. 1-4. Столбцовый перестановочный фильтр. Например, в четырехроторной машине первый ротор может заменять "A" на " F", второй - "F" на "Y", третий - "Y" на "E" и четвертый - "E" на "C", "C" и будет конечным шифротекстом . Затем некоторые роторы смещаются, и в следующий раз подстановки будут другими . Именно комбинация нескольких роторов и механизмов, движущих роторами, и обеспечивает безопасность машины. Так как роторы вращаются с различной скоростью, период для n-роторной машины равен 26n. Некоторые роторные машины также могут иметь различные положения для каждого ротора, что делает криптоан ализ еще более бессмысленным. Самым известным роторным устройство является Энигма ( Enigma). Энигма использовалась немцами во Второй мировой войне. Сама идея пришла в голову Артуру Шербиусу ( Arthur Scherbius) и Арвиду Герхарду Дамму (Arvid Gerhard Damm) в Европе. В Соединенных Штатах она была запатентована Артуром Шербиусом [1383]. Немцы значительно усовершенствовали базовый проект для использования во время войны . У немецкой Энигмы было три ротора, котроые можно было выбрать из пяти возможных, коммутатор, кот орый слегка тасовал открытый текст, и отражающий ротор, который заставлял каждый ротор обрабатывать о ткрытый текст каждого письма дважды . Несмотря на сложность Энигмы, она была взломана в течение Второй мировой войны. Сначала группа польских криптографов взломала немецкую Энигму и объяснила раскрытый алгоритм англичанам. В ходе войны немцы модифицировали Энигму , а англичане продолжали криптоанализ новых версий. Объяснение работы роторных шифров и способов их раскрытия можно найти в [794, 86, 448, 498, 446, 880, 1315, 1587, 690]. В двух следующих отчетах увлекательно рассказывается о взломе Энигмы [735, 796]. Для дальнейшего чтения Данная книга не является книгой по классической криптографии, поэтому далее я не буду подробно остана вливаться на этих предметах. Прекрасными книгами по докомпьютерной криптологии являются [587, 1475]. [448] содержит современный криптоанализ шифровальных машин . Дороти Деннинг (Dorothy Denning) рассматривает многие из этих шифров в [456], а [880] содержит беспристрастный сложный математический анализ тех же самых шифров. Другим описанием старой криптографии, описывающим аналоговую криптографию, являе тся [99]. Прекрасный обзор выполнен в статье [579]. Великолепны также книги по исторической криптографии Дэвида Кана [794, 795, 796]. 1.4 Простое XOR XOR представляет собой операцию "исключающее или" : '^' в языке C или Q в математической нотации. Это обычная операция над битами: 0⊕0=0 0⊕1=1 1⊕0=1 1⊕1=0 Также заметим, что: a⊕a=0 a⊕b⊕b=a Казалось бы, запутанный алгоритм простого XOR по сути является ничем иным, как полиалфавитным ши фром Вигенера. Здесь он упоминается только из-за распространенности в коммерческих программных продуктах, по крайней мере в мире MS-DOS и Macintosh [1502, 1387]. К сожалению, если о программе компьютерной безопасности заявляется, что это "патентованный" алгоритм шифрования, значительно более быстрый, чем DES, то скорее всего используется какой-то вариант следующего . /* Использование: crypto key input_file output_file */ void main (int argc, char *argv[]) { FILE *fl, *fo; char *cp; int c; if ((cp = argv[l]) && *cp!= '\\0') { if ((fi = fopen(argvl[2], "rb")) != NULL) { if ((fo = fopen(argv[3], "wb")) != NULL) { while ((c = getc(fi)) != EOF) { if (!*cp) cp = argv[1]; c^= *(cp++); putc(c,fo); } fclose(fo); } fclose(fi); } } } Это симметричный алгоритм. Открытый текст подвергается операции "исключающее или" вместе с ключ евым текстом для получения шифротекста . Так как повторное применение операции XOR восстанавливает оригинал для шифрования и дешифрирования используется одна и та же программа : P⊕K=C C⊕K=P Настоящей безопасности здесь никогда не было. Этот тип шифрования легко вскрывается, даже без компь ютера [587, 1475]. Его взлом на компьютере занимает несколько секунд . Предположим, что открытый текст использует английский язык. Более того, пусть длина ключа любое н ебольшое число байт. Ниже описано, как взломать этот шифр: 1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений [577]. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещ ениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут др угими). Это называется показателем совпадений. Минимальное смещение от одного значения, кра тного длине ключа, к другому и есть длина ключа . 2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального ши фротекстов. Результатом операции будет удаления ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа . Так как в английском языке на один байт приходится 1.3 бита действительной информации (см раздел 11.1), существующая значительная изб ыточность позволяет определить способ шифрования . Несмотря на это, количество поставщиков программного обеспечения, навязывающих этот игрушечный а лгоритм в качестве "почти такого же безопасного как DES", впечатляет [1387]. Именно этот алгоритм (с 160-битным повторяющимся "ключом") NSA в конце концов разрешило использовать в цифровых телефонных сотовых сетях для закрытия голоса . XOR может защитить ваши файлы от младшей сестры, но настоящего криптоаналитика задержит лишь на считанные секунды . 1.5 Одноразовые блокноты Поверите или нет, но идеальный способ шифрования существует. Он называется одноразовым блокнотом и был изобретен в 1917 году Мэйджором Джозефом Моборном ( Major Joseph Mauborgne) и Гилбертом Вернамом (Gilbert Vernam) из AT&T [794]. (Фактически одноразовый блокнот представляет собой особый случай порог овой схемы, см. раздел 3.7.) В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и приклеенных к листу блокнота . Первоначально это была одноразовая лента для телетайпов . Отправитель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста . Шифрование представляет собой сложение по модулю 26 символа открытого текста и символа ключа из одн оразового блокнота. Каждый символ ключа используется только единожды и для единственного сообщения . Отправитель шифрует сообщения и уничтожает использованные страницы блокнота или использованную часть ленты . Получатель, в свою очередь, используя точно такой же блокнот, дешифрирует каждый символ шифротекста . Расшифровав сообщение, получатель уничтожает соответствующие страницы блокнота или часть ленты . Новое сообщение новые символы ключа. Например, если сообщением является: ONETIMEPAD а ключевая последовательность в блокноте: TBFRGFARFM то шифротекст будет выглядеть как: IPKLPSFHGQ так как Q + T mod 26 = I N + B mod 26 = P E + F mod 26 = K и т.д. В предположении, что злоумышленник не сможет получить доступ к одноразовому блокноту, использова нному для шифрования сообщения, эта схема совершенно безопасна. Данное шифрованное сообщение на вид соответствует любому открытому сообщению того же размера. Так как все ключевые последовательности совершенно одинаковы (помните, символы ключа генерируются случайным образом), у противника отсутствует информация, позволяющая подвергнуть шифротекст криптоан ализу. Кусочек шифротекста может быть похож на : POYYAEAAZX что дешифрируется как: SALMONEGGS или на: BXEGBMTMXM что дешифрируется как: GREENFLUID Повторю еще раз: так как все открытые тексты равновероятны , у криптоаналитика нет возможности опред елить, какой из открытых текстов является правильным . Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный шифротекст, и никакие вычислительные мощн ости не смогут это изменить. Необходимо напомнить, что символы ключа должны генерироваться случайным образом . Любые попытки вскрыть такую схему сталкиваются со способом, которым создается последовательность символов ключа . Использование генераторов псевдослучайных чисел не считается, у них всегда неслучайные свойства . Если вы используете действительно случайный источник - это намного труднее, чем кажется на первый взгляд, см. ра здел 17.14 - это совершенно безопасно. Другой важный момент: ключевую последовательность никогда нельзя использовать второй раз. Даже если вы используете блокнот размером в несколько гигабайт, то если криптоаналитик получит несколько текстов с перекрывающимися ключами, он сможет восстановить открытый текст . Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. Если шифротексты смещены пр авильно, соотношение совпадений резко возрастет - точное значение зависит от языка открытого текста . С этой точки зрения криптоанализ не представляет труда . Это похоже на показатель совпадений, но сравниваются два различных "периода" [904]. Не используйте ключевую последовательность повторно . Идея одноразового блокнота легко расширяется на двоичные данные. Вместо одноразового блокнота, с остоящего из букв, используется одноразовый блокнот из битов . Вместо сложения открытого текста с ключом одноразового блокнота используйте XOR. Для дешифрирования примените XOR к шифротексту с тем же одноразовым блокнотом. Все остальное не меняется, и безопасность остается такой же совершенной . Все это хорошо, но существует несколько проблем . Так как ключевые биты должны быть случайными и не могут использоваться снова, длина ключевой последовательности должна равняться длине сообщения . Одноразовый блокнот удобен для нескольких небольших сообщений, но его нельзя использовать для работы по каналу связи с пропускной способностью 1.544 Мбит/с. Вы можете хранить 650 Мбайт случайных данных на CD-ROM, но и тут есть проблемы. Во первых, вам нужно только две копии случайных битов, но CD-ROM экономичны только при больших тиражах. И во вторых, вам нужно уничтожать использованные биты . Для CD-ROM нет другой возможности удалить информацию кроме как физически разрушить весь диск . Гораздо больше подходит цифровая лента. Даже если проблемы распределения и хранения ключей решены, вам придется точно синхронизировать р аботу отправителя и получателя. Если получатель пропустит бит (или несколько бит пропадут при передаче ), сообщение потеряет всякий смысл . С другой стороны, если несколько бит изменятся при передаче (и ни один бит не будет удален или добавлен - что гораздо больше похоже на влияние случайного шума ), то лишь эти биты будут расшифрованы неправильно . Но одноразовый блокнот не обеспечивает проверку подлинности . Одноразовые блокноты используются и сегодня, главным образом для сверхсекретных каналов связи с ни зкой пропускной способностью. По слухам "горячая линия" между Соединенными Штатами и бывшим Сове тским Союзом (а действует ли она сейчас?) шифруется с помощью одноразового блокнота . Многие сообщения советских шпионов зашифрованы с использованием одноразовых блокнотов . Эти сообщения нераскрыты сегодня и навсегда останутся нераскрытыми . На этот факт не повлияет время работы суперкомпьютеров над этой проблемой. Даже когда враги из созвездия Андромеды приземлят свои тяжелые корабли с компьютерами н емыслимой мощности, и они не смогут прочесть сообщения советских шпионов, зашифрованные с помощью о дноразовых (если, конечно, они не смогут вернуться в прошлое и добыть нужные одноразовые блокноты ). 1.6 Компьютерные алгоритмы Существует множество компьютерных алгоритмов. Следующие три используются чаще всего : — DES (Data Encryption Standard , стандарт шифрования данных ) - самый популярный компьютерный алг оритм шифрования, является американским и международным стандартом . Это симметричный алгоритм, один и тот же ключ используется для шифрования и дешифрирования . — RSA (назван в честь создателей - Ривеста (Rivest), Шамира (Sharnir) и Эдлмана (Adleman)) - самый популярный алгоритм с открытым ключом . Используется и для шифрования, и для цифровой подписи . — DSA (Digital Signature Algorithm, алгоритм цифровой подписи, используется как часть стандарта цифр овой подписи, Digital Signature Standard) - другой алгоритм с открытым ключом . Используется только для цифровой подписи, не может быть использован для шифрования . Именно эти и подобные алгоритмы описываются в этой книге . 1.7 Большие числа На протяжении всей книги я использую различные большие числа для описания различных вещей в крипт ографии. Так как легко заблудиться в этих числах и их значениях, физические аналоги некоторых чисел прив едены в 0-й. Эти числа оцениваются по порядку величины и были отобраны из различных источников. Многие астроф изические значения объясняются в работе Фримана Дайсона ( Freeman Dyson), "Время без конца: физика и биология в открытой Вселенной" ("Time Without End: Physics and Biology in an Open Universe") в Reviews of Modem Physics, v. 52, n. 3, July 1979, pp. 447-460. Смертность в результате автокатастроф рассчитана с помощью стат истики Министерства транспорта (163 смерти миллион человек в 1993 году и для средней продолжительности жизни 69.7 года. Табл. 1-1. Большие числа Физический аналог Вероятность быть убитым молнией (в течение дня) Вероятность выиграть главный приз в государственной лотерее США Вероятность выиграть главный приз в государственной лотерее США и быть убитым молнией в течение того же дня Вероятность утонуть (в США в течение года) Вероятность погибнуть в автокатастрофе (в США в году) Вероятность погибнуть в автокатастрофе (в США в течение времени жизни) Время до следующего оледенения Время до превращения Солнца в сверхновую звезду Возраст планеты Возраст Вселенной Число атомов планеты Число атомов Солнца Число атомов галактики Число атомов Вселенной Объем Вселенной Если Вселенная конечна: Число 1 из 9 миллиардов (2 33) 1 из 4000000 (2 22) 1 из261 1 из 59000 (2 16) 1 из 6100 (213) 1 из 88 (2 7) 14000 (214) лет 109 (230) лет 109 (230) лет 1010 (234) лет 1051 (2170) 1057 (2190) 1067 (2223) 1077 (2265) 1084 (2280) см 3 Полное время жизни вселенной 1011 (237) лет 1018 (261) секунд Если Вселенная бесконечна: Время до остывания легких звезд Время до отрыва планет от звезд Время до отрыва звезд от галактик Время до разрушения орбит гравитационной радиацией Время до разрушения черных дыр процессами Хокинга Время до превращения материи в жидкость при нулевой температуре Время до превращения материи в твердое тело Время до превращения материи в черную дыру 1014 (247) лет 1015 (250) лет 1019 (264) лет 1020 (267) лет 1064 (2213) лет 1065 (2216) лет 1010 лет 1010 лет 76 26 Часть 1 КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ Глава 2 Элементы протоколов 2.1 Введение в протоколы Смысл криптографии - в решении проблем . (По сути, в этом состоит и смысл использования компьютеров, о чем многие пытаются забыть.) Криптография решает проблемы секретности, проверки подлинности, целостн ости и человеческой нечестности. Вы можете выучить все о криптографических алгоритмах и методах, но они представляют только академический интерес, если не используются для решения какой-нибудь проблемы . Именно поэтому мы собираемся сначала взглянуть на протоколы . Протокол - это порядок действий, предпринимаемых двумя или более сторонами, предназначенный для р ешения определенной задачи. Это важное определение. "Порядок действий" означает, протокол выполняется в определенной последовательности, с начала до конца . Каждое действие должно выполняться в свою очередь и только после окончания предыдущего . "Предпринимаемых двумя или более сторонами " означает, что для реализации протокола требуется по крайней мере два человека, один человек не сможет реализовать протокол . Человек в одиночку может выполнить некоторые действия, решая задачу (например, покупая торт), но это не пр отокол. (Для того, чтобы получился настоящий протокол, кто-то должен съесть торт .) Наконец, "предназначенный для решения определенной задачи " означает, что протокол должен приводить к какому-то результату. Что-то, похожее на протокол, но не решающее никакой задачи - это не протокол, это потеря времени. У протоколов есть также и другие характеристики : — Каждый участник протокола должен знать протокол и последовательность составляющих его действий . — Каждый участник протокола должен согласиться следовать протоколу . — Протокол должен быть непротиворечивым, каждое действие должно быть определено так, чтобы не было возможности непонимания. — Протокол должен быть полным, каждой возможной ситуации должно соответствовать определенное де йствие. В этой книге каждый протокол организован как некоторый порядок действий . Выполнение протокола происходит по действиям, линейно, пока не будет команды перейти к следующему действию . Каждое действие включает по крайней мере одно из двух : вычисления, выполняемые одной или несколькими сторонами, или сообщения, которыми обмениваются стороны . Криптографический протокол - это протокол, использующий криптографию . Стороны могут быть друзьями и слепо доверять друг другу или врагами и не верить друг другу даже при сообщении времени суток . Криптографический протокол включает некоторый криптографический алгоритм, но, вообще говоря, предназначение протокола выходит за рамки простой безопасности . Участники протокола могут захотеть поделиться секретом друг с другом, совместно генерировать случайную последовательность, подтвердить друг другу свою подли нность или подписать контракт в один и тот же момент времени. Смысл использования криптографии в проток оле - в предотвращении или обнаружении вредительства и мошенничества . Если вы никогда не сталкивались с подобными протоколами, они могут радикально изменить ваше представление о том, что недоверяющие друг другу стороны могут выполнить, используя компьютерную сеть . Общее правило можно сформулировать сл едующим образом: — Невозможно сделать или узнать больше, чем определено в протоколе . Это гораздо сложнее, чем кажется . В следующих нескольких главах я рассматриваю множество протоколов . В некоторых из них один из участников может обмануть другого . В других, злоумышленник может взломать протокол или узнать секретную информацию . Ряд протоколов проваливаются, так как их разработчики недост аточно тщательно определяли требования . Другие проваливаются из-за того, что их разработчики недостаточно тщательно анализировали свои протоколы . Как и для алгоритмов, гораздо легче доказать возможную небез опасность протокола, чем его полную безопасность . Смысл протоколов В повседневной жизни почти для всего существуют неформальные протоколы : заказ товаров по телефону, игра в покер, голосование на выборах . Никто не задумывается об этих протоколах, они вырабатывались в теч ение длительного времени, все знают, как ими пользоваться и они работают достаточно хорошо . Сегодня все больше и больше людей общаются не лично, а используя компьютерную сеть . Для тех же вещей, которые люди делают не задумываясь, компьютерам нужны формальные протоколы . Когда вы переезжаете из государства в государство и обнаруживаете кабинку, совершенно отличающуюся от той, к которой вы пр и- выкли, вы легко адаптируетесь. Компьютеры далеко не так гибки . Честность и безопасность многих протоколов человеческого общения основаны на личном присутствии . Разве вы дадите незнакомцу кучу денег, чтобы он купил для вас что-нибудь в бакалее ? Сядете ли вы играть в покер с тем, кто жульничает, сдавая карты? Пошлете ли вы свой избирательный бюллетень правительству, не будучи уверенным в тайности такого голосования? Наивно считать, что пользователи компьютерных сетей всегда честны. Также наивно считать, что всегда ч естны разработчики компьютерных сетей. Для большинства из них это именно так, но даже несколько жуликов могут принести много вреда. Формализируя протоколы, можно проверить способы, используемые жуликами для взлома протоколов. Так мы можем разработать протоколы, устойчивые к взлому. Кроме формализации действий, протоколы позволяют абстрагироваться при решении задачи от способа р ешения. Протокол связи один и тот же и на PC, и на VAX. Можно проверить протокол, не вдаваясь в детали его реализации. Когда мы убедимся в надежности протокола, его можно будет реализовать где угодно от компьют еров до телефонов и интеллектуальных тостеров . Игроки Для демонстрации работы протоколов я использую несколько игроков (см. 1-й). Первые двое - это Алиса и Боб. Они участвуют во всех двусторонних протоколах . Как правило, Алиса (Alice) начинает все протоколы, а Боб (Bob) отвечает. Если для протокола нужна третья или четвертая сторона, в игру вступают Кэрол (Кэрол) и Дэйв (Dave). Другие игроки играют специальные вспомогательные роли, они будут представлены по зже. Протоколы с посредником Посредник - это незаинтересованная третья сторона, которой доверено завершение протокола (см. 1-й (а)). Незаинтересованность означает, что у посредника нет заинтересованности в результате работы протокола и склонности к одной из сторон. "Доверено" означает, что все участники протокола принимают все, что скажет посредник за истину, все его действия - как правильные, и уверены в том, что посредник выполнит свою часть протокола. Посредники помогают реализовать работу протоколов взаимодействия недоверяющих друг другу сторон. В реальном мире в качестве посредников часто выступают юристы . Например, Алиса продает незнакомому ей Бобу машину. Боб хочет заплатить чеком, но у Алисы нет способа проверить, действителен ли чек . Алиса хочет, чтобы расчет по чеку был произведен прежде, чем право собственности перейдет к Бобу . Боб, который верит Алисе не больше, чем она ему , не хочет передавать чек, не получив права собственности . Табл. 2-1. Действующие лица Алиса Боб Кэрол Дэйв Ева Мэллори Трент Уолтер Пегги Виктор Первый участник всех протоколов Второй участник всех протоколов Третий участник в протоколах с участием трех и четырех сторон Четвертый участник в протоколах с участием трех и четырех сторон Злоумышленник (eavesdropper) Взломщик протоколов Заслуживающий доверия посредник Контролер, защищает Алису и Боба в ряде протоколов Свидетель Проверяет подлинность Трент Алиса Боб (а) протокол с посредником Алиса Боб Трент Доказательство Доказательство (б) арбитражный протокол после случившегося Алиса Боб (в) самодостаточный протокол Рис. 2-1. Типы протоколов Посредничество юриста устроит обоих . С его помощью Алиса и Боб могут выполнить следующий протокол, чтобы защитить себя от обмана: (1) Алиса передает право собственности юристу. (2) Боб передает чек юристу. (3) Алиса депонирует чек. (4) Дождавшись оплаты чека юрист передает право собственности Бобу. Если чек не оплачен в течение опр еделенного времени, Алиса доказывает этот факт юристу, и тот возвращает право собственности Алисе. В этом протоколе Алиса верит, что юрист не передаст Бобу право собственности до тех пор, пока чек не б удет оплачен, и вернет право собственности Алисе, если чек оплачен не будет. Боб верит, что юрист будет обладать правом собственности до тех пор, пока чек не будет оплачен, и передаст право собственности Бобу сразу же после оплаты чека. Юрист не заботится об оплате чека. Он в любом случае выполнит свою часть протокола, ведь ему заплатят в любом случае . В этом примере юрист играет роль посредника . Юристы часто выступают в роли посредников при завещ аниях и иногда при переговорах о контракте . Различные биржи выступают в качестве посредников между пок упателями и продавцами. В качестве посредника может выступить и банк - для покупки машины : (1) Боб заполняет чек и передает его в банк. (2) Если на счету Боба достаточно денег для покрытия чека, банк заверяет чек и возвращает его Бобу. (3) Алиса передает Бобу право собственности, а Боб передает Алисе заверенный чек. (4) Алиса депонирует чек. Этот протокол работает, потому что Алиса верит банковскому свидетельству . Алиса верит, что банк сохранит деньги Боба для нее и не использует их для финансирования сомнительных операций с недвижимостью в банановых республиках. Другим общепринятым посредником является нотариус . Когда Боб получает от Алисы заверенный нотари усом документ, он убежден, что Алиса подписала документ по своему желанию и собственноручно . При необходимости нотариус может выступить в суде и засвидетельствовать этот факт . Понятие посредника старо как мир. Всегда существовали определенные люди - вожди, жрецы и тому подо бное - обладавшие влиянием, позволяющим им действовать справедливо. Посредники играют определенную роль в нашем обществе, обман доверия подорвал бы занимаемое ими положение . Юристы-посредники, нарушающие правила игра, подвергаются наказанию - например, исключению из коллегии адвокатов . Это идеальная картина, в реальном мире положение, к сожалению, может отличаться от нее . Этот идеал можно перенести на мир компьютеров, но с компьютерными посредниками существует ряд пр облем: — Легко найти нейтральную третью сторону, которой можно доверять, если вы знаете посредника и можете лично увидеть его. Две стороны, относящиеся друг к другу с подозрением, с тем же подозрением отнесу тся и к безликому посреднику, затерянному где-то в сети . — Компьютерная сеть должна обеспечить поддержку посредника. Занятость юристов общеизвестна, на кого в сети лягут дополнительные накладные расходы ? — Существует задержка, присущая всем протоколам с посредником . — Посредник должен принимать участие в каждой транзакции, являясь узким местом в крупномасштабных реализациях любого протокола. Рост числа посредников смягчит эту проблему, но вырастет и цена этой услуги. — Так как каждый в сети должен доверять посреднику, то посредник представляет собой слабое место сети при попытке ее взлома. Несмотря на это посредничество все еще активно используется. В протоколах с использованием посредника эту роль будет играть Трент. Арбитражные протоколы Используемый из-за высокой стоимости найма посредников арбитражные протокол может быть разбит на два подпротокола нижнего уровня. Первый представляет собой протокол без посредника, используемый при желании сторон выполнить протокол . Другой представляет собой протокол с посредником, приглашаемым в исключительных обстоятельствах - при наличии разногласий между сторонами . Соответствующий специальный посредник называется арбитром (см. 1-й(б)). Арбитр, как и посредник, представляет собой незаинтересованного участника протокола, которому доверяют обе стороны. В отличие от посредника он непосредственно не принимает участия в каждой отдельной реализ ации протокола и приглашается только для проверки честности выполнения протокола сторонами . Профессиональными арбитрами являются судьи. В отличие от нотариусов к судьям обращаются только при появлении разногласий. Алиса и Боб могут заключить контракт без участия судьи . Судья никогда не узнает о контракте, если одна из сторон не подаст на другую в суд . Протокол подписания контракта можно формализ овать следующим образом: Подпротокол без посредника (выполняется всегда) : (1) Алиса и Боб договариваются об условиях контракта. (2) Алиса подписывает контракт. (3) Боб подписывает контракт. Подпротокол с использованием арбитра (выполняется при наличии разногласий) : (4) Алиса и Боб предстают перед судьей. (5) Алиса предоставляет свои доказательства. (6) Боб предоставляет свои доказательства. (7) Судья принимает решение на основании доказательств. Различие используемых в этой книге понятий посредника и арбитра состоит в том, что участие арбитра пр оисходит не всегда. Стороны обращаются к судье только при разногласиях. Если разногласий нет, судья не н ужен. Существуют арбитражные компьютерные протоколы. Они предполагают, что участвующие стороны честны, но при подозрении о возможном мошенничестве по существующему набору данных третья сторона, которой доверяют участники, сможет обнаружить факт мошенничества . Хороший арбитражный протокол позволяет а рбитру установить и личность мошенника . Арбитражные протоколы обнаруживают, а не предупреждают моше нничество. Неотвратимость обнаружения выступает в качестве предупредительной меры, предотвращая моше нничество. Самодостаточные протоколы Самодостаточный протокол является лучшим типом протокола . Он полностью обеспечивает честность сторон (см. 1-й(в)). Для выполнения протокола не нужен ни посредник, не решающий споры арбитр . Само построение протокола обеспечивает отсутствие споров. Если одна из сторон попытается смошенничать, мошенн ичество будет немедленно обнаружено другой стороной, и протокол прекратит выполняться. Чего бы не пыталась добиться мошенничающая сторона, этому не суждено случиться. В лучшем мире любой протокол должен быть самодостаточным, но, к несчастью, не существует самодост аточных протоколов для каждой ситуации . Попытки вскрытия протоколов Криптографические попытки взлома могут быть направлены против криптографических алгоритмов, и спользуемых в протоколах, против криптографических методов, используемых для реализации алгоритмов и протоколов или непосредственно против протоколов. Поскольку в этом разделе книги обсуждаются именно пр отоколы, я предполагаю, что криптографические алгоритмы и методы безопасны , и рассматриваю только попытки вскрытия протоколов. Люди могут использовать множество способов взломать протокол. Некоторые, не являясь участниками пр отокола, могут "подслушивать" какую-то часть или весь протокол . Это называется пассивным вскрытием, так как взломщик не воздействует на протокол . Все, что он может сделать - это проследить за протоколом и поп ытаться добыть информацию. Этот тип вскрытия соответствует вскрытию с использованием только шифротекста, обсуждавшемуся в разделе 1.1. Так как пассивные вскрытия трудно обнаружить, протоколы стремятся предо твращать, а не обнаруживать их. В этих протоколах роль злоумышленника будет играть Ева . В другом случае взломщик может попытаться изменить протокол для собственной выгоды . Он может выдать себя за другого, ввести новые сообщения в протокол, заменить одно сообщение другим, повторно передать ст арые сообщения, разорвать канал связи или изменить хранящуюся в компьютере информацию . Такие действия называются активным вскрытием, так как они требуют активного вмешательства . Эти формы вскрытия зависят от вида сети. Пассивные взломщики стараются получить информацию об участниках протокола . Они собирают сообщения, переданные различными сторонами, и пытаются криптоанализировать их . Попытки активного вскрытия, с другой стороны, преследуют более широкий набор целей. Взломщик может быть заинтересован в получении информации, ухудшении работы системы или получении несанкционированного доступа к ресурсам . Активные вскрытия более серьезны, особенно в отношении протоколов, в которых стороны не обязательно доверяют друг другу. Взломщик не обязательно кто-то совсем посторонний, он может быть зарегистрированным пользователем системы и даже системным администратором . Может быть даже несколько активных взломщ иков, работающих вместе. В этой книге роль злонамеренного активного взломщика будет играть Мэ ллори. Взломщиком может быть и один из участников протокола . Он может обманывать, выполняя протокол, или вовсе не следовать правилам протокола . Такой взломщик называется мошенником. Пассивные мошенники выполняют правила протокола, но стараются получить больше информации, чем предусмотрено протоколом . Активные мошенники нарушают работу протокола, пытаясь смошенничать . Очень трудно поддерживать безопасность протокола, если большинство его участников - активные моше нники, но иногда активное мошенничество может быть обнаружено законными участниками . Конечно, протоколы должны быть защищены и от пассивного мошенничества . 2.2 Передача информации с использованием симметричной криптографии Как двум сторонам безопасно обмениваться информацией? Конечно же, шифрую свои сообщения . Посмотрим, что должно произойти, когда Алиса посылает шифрованное сообщение Бобу (полный протокол гораздо сложнее). (1) Алиса и Боб выбирают систему шифрования. (2) Алиса и Боб выбирают ключ. (3) Алиса шифрует открытый текст своего сообщения с использованием алгоритма шифрования и ключа, п олучая шифрованное сообщение. (4) Алиса посылает шифрованное сообщение Бобу. (5) Боб дешифрирует шифротекст сообщения с использованием алгоритма шифрования и ключа, получая о ткрытый текст сообщения. Что может Ева, находясь между Алисой и Бобом, узнать, подслушивая этот протокол ? Если она может подслушать только передачу на этапе (4), ей придется подвергнуть шифротекст криптоанализу . Это пассивное вскрытие представляет собой вскрытие с использованием только шифротекста, применяемые алгоритмы усто йчивы (насколько нам известно) по отношению к любым вычислительным мощностям, который может запол учить Ева для решения проблемы . Ева, однако, не глупа. Она может также подслушать и этапы (1) и (2). Тогда ей станут известны алгоритм и ключ - также как и Бобу. Когда она перехватит сообщение на этапе (4), то ей останется только дешифровать его самостоятельно. В хорошей криптосистеме безопасность полностью зависит от знания ключа и абсолютно не зависит от зн ания алгоритма. Именно поэтому управление ключами так важно в криптографии . Используя симметричный алгоритм, Алиса и Боб могут открыто выполнить этап (1), но этап (2) они должны сохранить в тайне . Ключ должен оставаться в секрете перед, после и в течение работы протокола - до тех пор, пока должно оставаться в тайне передаваемое сообщение - в противном случае сообщение тут же будет раскрыто . (О криптографии с открытыми ключами, решающей эту проблему иначе, рассказывается в разделе 2.5 .) Мэллори, активный взломщик, может сделать кое-что другое. Он может попытаться нарушить линию связи не этапе (4), сделав так, что Алиса вообще не сможет передавать информацию Бобу . Мэллори также может перехватить сообщение Алисы и заменить его своим собственным .