Шрифт:
Закладка:
Новички в криптографии часто полагают, что шифр достаточно надежен, если он может выдержать атаку первого типа (только зашифрованный текст). Такое предположение весьма наивно. Во многих случаях криптоаналитик может догадаться, как будут выглядеть определенные фрагменты зашифрованного текста. Например, после загрузки большинство компьютеров выводит на экран приглашение для ввода имени пользователя. Наличие нескольких пар сопоставленных друг с другом фрагментов зашифрованного и открытого текста может существенно упростить стоящую перед криптоаналитиком задачу. Для надлежащей защиты криптограф должен предусмотреть некоторый запас прочности и убедиться, что систему нельзя взломать, даже если его оппонент зашифрует произвольно выбранные фрагменты открытого текста.
Исторически методы шифрования разделились на две категории: метод подстановки и метод перестановки. Мы кратко рассмотрим их в качестве введения в современную криптографию.
8.4.2. Два базовых принципа криптографии
Хотя далее мы рассмотрим много различных криптографических систем, в основе каждой из них лежат два важнейших для понимания принципа. Обратите особое внимание — нарушать их очень опасно.
Избыточность
Первый принцип гласит, что все зашифрованные сообщения должны содержать некую избыточность, то есть информацию, которая не требуется для понимания сообщения. Приведем пример. Представьте компанию «Домосед», торгующую по почте товарами 60 000 наименований. Радуясь, что им удастся так экономно распорядиться ресурсами, программисты компании решили, что весь бланк заказа будет состоять из 16 байт для имени клиента, за которым последует поле товара из 3 байт (1 байт для обозначения количества и 2 байта для идентификатора товара). Последние 3 байта решено закодировать с помощью очень длинного ключа, известного только клиенту и компании «Домосед».
На первый взгляд эта схема кажется надежной, в частности потому, что пассивные злоумышленники не смогут расшифровать сообщения. К сожалению, в этой схеме имеется критический недостаток, полностью ее обесценивающий. Предположим, какой-нибудь недавно уволенный сотрудник захочет отомстить компании «Домосед» за увольнение. Перед уходом ему удается забрать с собой часть списка клиентов. За ночь он создает программу, отправляющую фиктивные заказы с настоящими именами клиентов. Поскольку списка ключей у него нет, он просто помещает в последние 3 байта случайные числа и отсылает сотни заказов компании «Домосед».
Получив эти сообщения, компьютер компании «Домосед» находит ключ для дешифрования по имени клиента. К несчастью для компании, почти все 3-байтные сообщения могут восприниматься как достоверные, поэтому компьютер начинает печатать заявки на доставку товаров. Может показаться странным, что клиент заказал 837 сидений для детских качелей или 540 песочниц, но вполне возможно, что он занимается строительством детских игровых площадок. Таким образом, активный злоумышленник (уволенный сотрудник) способен доставить очень много неприятностей, даже не вникая в смысл сообщений, отсылаемых его компьютером.
Эту проблему можно решить, добавив избыточную информацию к каждому сообщению. Если добавить к трем шифруемым байтам еще девять (например, нулевых), бывший сотрудник уже не сможет сформировать серьезный поток сообщений, которые достоверно выглядят. Мораль истории в том, что все сообщения должны содержать достаточное количество избыточной информации, чтобы активный злоумышленник не смог выдать случайный мусор за настоящие сообщения. Итак:
Криптографический принцип номер 1: сообщения должны содержать избыточные данные.
С другой стороны, наличие избыточной информации облегчает работу криптоаналитика по взлому шифра. Предположим, что конкуренция в бизнесе почтовых заказов чрезвычайно высока и что главный конкурент «Домоседа», фирма «Лежебока», очень хочет узнать объем продаж песочниц «Домоседа» в месяц. Для этого «лежебоки» подключились к телефонной линии «домоседов». В исходной схеме с 3-байтными номерами криптоанализ был почти невозможен, поскольку, предположив значение ключа, криптоаналитик не мог проверить правильность догадки, ведь почти все сообщения были технически корректны. С введением новой 12-байтной схемы криптоаналитик легко сможет отличить допустимое сообщение от недопустимого.
Другими словами, при расшифровке сообщения получатель должен иметь возможность проверить его подлинность путем анализа и, возможно, выполнения несложных вычислений. Избыточность требуется для того, чтобы можно было противостоять попыткам активных злоумышленников обмануть получателя фальшивыми сообщениями, содержащими мусор.
Вместе с тем добавление избыточной информации облегчает пассивным злоумышленникам задачу взлома системы, так что здесь есть определенное противоречие. Кроме того, избыточные данные никогда не должны принимать форму последовательности нулей в начале или в конце сообщения, так как при зашифровке таких сообщений некоторые алгоритмы дают более предсказуемые результаты, что облегчает работу криптоаналитиков. Многочлен циклического избыточного кода CRC (см. главу 3) намного больше подходит для этих целей, чем просто ряд нулей, ведь получатель может легко проверить его корректность, и это несколько усложняет задачу взломщика. Еще лучше использовать криптографическую хеш-функцию, речь о которой пойдет ниже. Пока просто запомните, что это более надежный вариант CRC.
Ограниченный срок годности
Второй принцип криптографии состоит в следующем. Необходимо принять меры и удостовериться, что входящее сообщение является свежим, то есть было отправлено недавно. Этот принцип направлен на борьбу с активными злоумышленниками, которые воспроизводят перехваченные ими старые сообщения. Если этого не сделать, уволенный сотрудник может подключиться к телефонной линии компании «Домосед» и просто повторить отправленные ранее настоящие сообщения. Итак, сформулируем утверждение:
Криптографический принцип номер 2: нужен способ борьбы с повторной отправкой старых сообщений.
Один из способов — включить в каждое сообщение временную метку, которая действительна, скажем, только 60 с. Получатель просто хранит принятые сообщения в течение этого времени, отсеивая дубликаты. Сообщения старше 60 с игнорируются. Этот интервал не должен быть слишком коротким (например, 5 с), ведь не исключено, что системные часы отправителя и получателя работают с некоторым рассогласованием. Другие меры защиты от дубликатов представлены ниже.
8.4.3. Подстановочные шифры
При использовании подстановочного шифра (substitution cipher) каждый символ или группа символов заменяются другим символом или группой символов. Один из древнейших шифров такого рода — шифр Цезаря (Caesar cipher), изобретение которого приписывают римскому императору. Этот шифр заменяет все буквы алфавита на другие с помощью циклического сдвига на три позиции. Так, буква a становится буквой D, b — E, c — F, … и z — C. К примеру, слово attack превращается в DWWDFN. Мы будем обозначать открытый текст строчными символами, а зашифрованный — прописными.
Некоторое обобщение шифра Цезаря представляет собой сдвиг алфавита не на три символа, а на произвольное число символов k. В этом случае k становится ключом к общему методу циклически сдвигаемых алфавитов. Может, шифр Цезаря
