помощью очень длинного ключа, известного только клиенту и компании «Домосед».
На первый взгляд эта схема кажется надежной, в частности потому, что пассивные злоумышленники не смогут расшифровать сообщения. К сожалению, в этой схеме имеется критический недостаток, полностью ее обесценивающий. Предположим, какой-нибудь недавно уволенный сотрудник захочет отомстить компании «Домосед» за увольнение. Перед уходом ему удается забрать с собой часть списка клиентов. За ночь он создает программу, отправляющую фиктивные заказы с настоящими именами клиентов. Поскольку списка ключей у него нет, он просто помещает в последние 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 становится ключом к общему методу циклически сдвигаемых алфавитов. Может, шифр Цезаря и обманул жителей Помпеи, но с тех пор ему уже никого не удалось ввести в заблуждение.
Следующее усовершенствование заключается в установлении соответствия между каждым символом в открытом тексте (для простоты, скажем, это 26 букв) и каким-либо другим. Например,
открытый текст:
a b c d e f g h i j k l m n o p q r s t u v w x y z
зашифрованный текст:
Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Такая система называется моноалфавитным подстановочным шифром (monoalphabetic substitution cipher), ключом к которому является 26-символьная строка, соответствующая полному алфавиту. В нашем случае открытый текст attack будет преобразован в зашифрованный текст QZZQEA.
На первый взгляд эта система может показаться надежной, ведь даже если криптоаналитику известен общий принцип шифрования (подстановка одного символа вместо другого), он все равно не знает, какой из 26! ≈ 4 × 1026 возможных вариантов ключа следует применить. В отличие от шифра Цезаря применение метода простого перебора в данном случае весьма сомнительно. Даже при затратах 1 нс на проверку одного варианта ключа миллиону параллельно работающих процессорных ядер понадобится около 10 000 лет, чтобы перепробовать их все.
Тем не менее подобный шифр легко взламывается даже при наличии довольно небольших фрагментов зашифрованного текста. Для атаки может быть использовано преимущество статистических характеристик естественных языков. Например, в английском языке буква e встречается в тексте чаще всего. Следом за ней по частоте использования идут буквы t, o, a, n, i и т.д. Самыми распространенными комбинациями из двух символов, биграммами (digrams), являются th, in, er, re и an. Наиболее часто встречающимися комбинациями из трех символов, триграммами (trigrams), являются the, ing, and и ion.
Криптоаналитик, пытающийся взломать моноалфавитный шифр, прежде всего сосчитает относительные частоты всех символов алфавита в зашифрованном тексте. Затем он попробует заменить наиболее часто встречающийся символ буквой e, а следующий по частоте — буквой t. Затем он найдет триграммы самой распространенной формы tXe, где, скорее всего, X — это h. Аналогичным образом, если последовательность thYt встречается достаточно часто, то, вероятно, Y обозначает символ a. Обладая этой информацией, криптоаналитик может поискать часто встречающуюся триграмму вида aZW, что, скорее всего, означает and. Продолжая угадывать буквы, биграммы и триграммы и зная, какие последовательности символов являются наиболее вероятными, криптоаналитик побуквенно восстанавливает исходный текст.
Другой метод заключается в угадывании слова или фразы целиком. Например, рассмотрим следующий зашифрованный текст, полученный от бухгалтерской фирмы (разбитый на блоки по пять символов):
CTBMN BYCTC BTJDS QXBNS GSTJC BTSWX CTQTZ CQVUJ QJSGS TJQZZ MNQJS VLNSX VSZJU JDSTS JQUUS JUBXJ DSKSU JSNTK BGAQJ ZBGYQ TLCTZ BNYBN QJSW
В сообщении бухгалтерской фирмы, скорее всего, есть слово financial. Используя тот факт, что в этом слове буква i встречается дважды, разделенная четырьмя другими буквами, мы будем искать в зашифрованном тексте повторяющиеся символы, отстоящие друг от друга на это расстояние. В результате мы найдем 12 таких мест в тексте в позициях 6, 15, 27, 31, 42, 48, 56, 66, 70, 71, 76 и 82. Однако только в двух случаях, в позициях 31 и 42, следующий символ (соответствующий букве n в открытом тексте) повторяется в соответствующем месте. Из этих двух вариантов символ a имеет правильное расположение только для позиции 31. Теперь нам известно, что слово financial начинается в позиции 30. С этого момента выяснить ключ проще, применяя лингвистическую статистику английского языка и угадывая целые слова.
8.4.4. Перестановочные шифры
Подстановочные шифры «маскируют» символы открытого текста, но не меняют порядок их следования. Перестановочные шифры (transposition ciphers), наоборот, меняют порядок следования символов, но не «маскируют» их. На илл. 8.10 показан простой перестановочный шифр с колоночной перестановкой. Ключом к такому шифру служит слово или фраза, в которых нет повторяющихся букв. В данном примере в качестве ключа используется слово MEGABUCK. Цель ключа — пронумеровать колонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т.д. Открытый текст записывается горизонтально в строках. Зашифрованный текст читается по колонкам, начиная с колонки с младшей ключевой буквой.