Итак, в путь.

8.1. Криптография

Слово криптография (cryptography) происходит от греческих слов, означающих «скрытное письмо». У криптографии долгая и красочная история, насчитывающая несколько тысяч лет. В данном разделе мы всего лишь кратко упомянем некоторые отдельные моменты в качестве введения к последующей информации. Желающим ознакомиться с полной историей криптографии рекомендуется (Kahn, 1995). Для получения всестороннего представления о текущем положении дел см. (Kaufman и др., 2002). С математическими аспектами криптографии можно познакомиться, прочитав книгу (Stinson, 2002). Менее формальным (с математической точки зрения) языком ведется изложение в (Burnett и Paine, 2001).

С профессиональной точки зрения понятия «шифр» и «код» отличаются друг от друга. Шифр (cipher) представляет собой посимвольное или побитовое преобразование, не зависящее от лингвистической структуры сообщения. Код (code), напротив, заменяет целое слово другим словом или символом. Коды в настоящее время не используются, хотя история у них, конечно, славная. Наилучшим считается код, использовавшийся американскими войсками в Тихом океане во время Второй мировой войны. Просто-напросто для ведения секретных переговоров использовались носители языка индейцев навахо, словами из которого обозначались военные термины. Например, слово чаи-дагахи-найл-цайди (chay-dagahi-nail-tsaidi — буквально: убийца черепах) означало противотанковое оружие. Язык навахо тоновый (для различения смысла используется повышение или понижение тона), весьма сложный, не имеет письменной формы. Но самое большое его достоинство заключалось в том, что ни один японец не имел о нем ни малейшего представления.

В сентябре 1945 года газета San Diego Union так описывала этот код: «В течение трех лет, где бы ни высаживались военные моряки, уши японцев различали лишь странный булькающий шум, перемежающийся с другими звуками. Все это напоминало клич тибетского монаха или звук опустошаемой бутылки с горячей водой». Японцы так и не смогли взломать этот код, и многие носители языка индейцев навахо были удостоены высоких воинских наград за отличную службу и смелость. Тот факт, что США смогли расшифровать японский код, а японцы так и не узнали язык навахо, сыграл важную роль в американской победе в Тихом океане.

8.1.1. Основы криптографии

Исторически использовали и развивали искусство криптографии представители четырех профессий: военные, дипломатический корпус, люди, ведущие дневник, и любовники. Из них наиболее важную роль в развитии этой области сыграли военные. В военных организациях секретные сообщения традиционно отдавались для зашифровки и передачи плохо оплачиваемым шифровальщикам. Сам объем сообщений не позволял выполнить эту работу небольшим количеством элитных специалистов.

До появления компьютеров одним из основных сдерживающих факторов в криптографии была возможность шифровальщика выполнить необходимые преобразования, часто на поле боя, с помощью несложного оборудования. Кроме того, достаточно сложной задачей было быстрое переключение с одного криптографического метода на другой, так как для этого требовалось переобучение большого количества людей. Тем не менее опасность того, что шифровальщик может быть захвачен противником, заставила постоянно развивать способы смены криптографических методов при необходимости. Эти противоречивые требования приводят к модели процесса шифрования-дешифрации⁸, показанной на рис. 8.1.

Сообщения, подлежащие зашифровке, называемые открытым текстом (plaintext), преобразуются с помощью функции, вторым входным параметром которой является ключ (key). Результат процесса шифрования, называемый зашифрованным текстом (ciphertext), передается обычно по радио или через связного. Предполагается, что противник или злоумышленник (intruder) слышит и аккуратно копирует весь зашифрованный текст. Однако в отличие от получателя, которому предназначается данное

сообщение, злоумышленник не знает ключа дешифрации, и поэтому расшифровка сообщения представляет для него большие трудности, а порой она просто невозможна. Иногда злоумышленник может не только прослушивать канал связи (пассивный злоумышленник), но способен также записывать сообщения и воспроизводить их позднее, вставлять свои сообщения или модифицировать оригинальные сообщения, прежде чем они достигнут получателя (активный злоумышленник). Искусство взлома шифров называется криптоанализом (cryptanalysis). Искусства изобретать шифры (криптография) и взламывать их (криптоанализ) называются вместе криптологией (cryptology).

Рис. 8.1. Модель процесса шифрования-дешифрации (для шифра с симметричным ключом)

Обычно для обозначения открытого текста, зашифрованного текста и ключей полезно использовать специальную нотацию. Мы будем использовать формулу C = EK(P), обозначающую, что при зашифровке открытого текста P с помощью ключа K получается зашифрованный текст C. Аналогично формула P = DK(C) означает расшифровку зашифрованного текста C для восстановления открытого текста. Из этих двух формул следует, что

Такая нотация предполагает, что E и D являются просто математическими функциями. Они в действительности таковыми и являются. Единственная хитрость состоит в том, что обе эти функции имеют по два параметра, один из которых (ключ) мы написали не в виде аргумента, а в виде нижнего индекса, чтобы отличать его от сообщения.

Основное правило криптографии состоит в предположении, что криптоаналитику (взломщику шифра) известен используемый метод шифрования. Другими словами, злоумышленник точно знает, как работают методы шифрования E и дешифрации D на рис. 8.1. Из-за огромных усилий, необходимых для разработки, тестирования и внедрения нового метода, каждый раз, когда старый метод оказывался или считался скомпрометированным, хранить алгоритм шифрования в секрете просто непрактично. А предположение, что метод остается секретным, когда это уже не так, могло бы причинить еще больший вред.

Здесь на помощь приходит ключ шифрования. Ключ состоит из относительно короткой строки, определяющей один из огромного количества вариантов результата шифрования. В отличие от самого метода шифрования, который может изменяться только раз в несколько лет, ключ можно менять так часто, как это нужно. Таким образом, наша базовая модель представляет собой постоянный и известный общий метод, в котором в качестве параметра используется секретный и легко изменяемый ключ. Идея, заключающаяся в предположении о том, что криптоаналитику известен метод и краеугольным камнем секретности является эксклюзивный ключ, называется принципом Керкгофа (Kerckhoff’s principle). Его в 1883 году впервые высказал фламандский военный криптограф Аугуст Керкгоф (Auguste Kerckhoff, 1883). Таким образом, принцип Керкгофа гласит:

Алгоритмы шифрования общедоступны; секретны только ключи.

Секретности алгоритма не стоит придавать большого значения. Попытка сохранить алгоритм в тайне, называемая в торговле безопасностью за счет неясности (security

by obscurity), обречена на провал. К тому же, опубликовав свой алгоритм, разработчик получает бесплатную консультацию от большого количества ученых-криптоанали-тиков, горящих желанием взломать новую систему и тем самым продемонстрировать свой ум и ученость. Если никто не смог взломать алгоритм в течение долгого времени после его опубликования, то, по-видимому, этот алгоритм достаточно прочен.

Поскольку реально в тайне хранится только ключ, основной вопрос заключается в его длине. Рассмотрим простой кодовый замок. Его основной принцип состоит в том, что вы последовательно вводите десятичные цифры. Все это знают, но ключ хранится в секрете. Ключ длиной в две цифры образует 100 вариантов. Ключ длиной в три цифры означает 1000 вариантов, а при длине ключа в шесть цифр число комбинаций достигает миллиона. Чем длиннее ключ, тем выше показатель трудозатрат (work factor) взломщика шифра. При увеличении длины ключа показатель трудозатрат для взлома системы путем простого перебора значений ключа растет экспоненциально. Секретность передаваемого сообщения обеспечивается мощным (но все же открытым) алгоритмом и длинным ключом. Чтобы не дать прочитать свою электронную почту младшему брату, достаточно ключа длиной в 64 двоичных разряда. В коммерческих системах имеет смысл использовать ключи длиной 128 бит. Чтобы защитить ваши тексты от правительств развитых государств, потребуются ключи длиной, по меньшей мере, в 256 бит.