Одноразовый блокнот в криптографии¶

Одноразовый блокнот (также шифр Вернама, одноразовая шифровальная лента, англ. one-time pad, OTP) — в криптографии совершенный шифр, при котором каждый символ открытого текста объединяется операцией сложения по модулю с символом ключа, представляющего собой последовательность случайных или псевдослучайных бит, длина которой равна длине открытого текста. Ключ используется строго один раз и никогда не применяется повторно, что обеспечивает абсолютную теоретическую стойкость шифра: перехваченная криптограмма не даёт криптоаналитику никакой информации об открытом тексте, кроме его максимально возможной длины.

¶История

Принцип, лежащий в основе одноразового блокнота, был впервые описан американским криптографом Фрэнком Миллером в 1882 году. Однако широкую известность метод получил благодаря сотруднику компании AT&T Гилберту Вернаму, который в 1917 году запатентовал устройство для автоматического шифрования телеграфных сообщений с использованием перфоленты. В первоначальной схеме Вернама ключ представлял собой замкнутую в кольцо перфоленту, которая повторялась, что делало шифр уязвимым. Позднее, в 1919 году, Джозеф Моборн предложил использовать ключ, длина которого равна длине сообщения и который не повторяется, фактически сформулировав концепцию современного одноразового блокнота.

Математическое доказательство абсолютной стойкости шифра Вернама было опубликовано Клодом Шенноном в 1949 году в работе «Теория связи в секретных системах». Шеннон показал, что если ключ является истинно случайным, используется один раз и держится в секрете, то шифр является совершенным: апостериорная вероятность любого открытого текста после перехвата шифротекста равна априорной вероятности.

¶Принцип работы

Алгоритм шифрования одноразовым блокнотом предельно прост. Открытый текст преобразуется в последовательность бит. Ключ также представляет собой последовательность бит той же длины, сгенерированную истинно случайным образом. Каждый бит открытого текста складывается с соответствующим битом ключа по модулю два (операция XOR). Полученная последовательность бит является шифротекстом. Для расшифрования получатель, обладающий копией ключа, выполняет ту же операцию XOR над шифротекстом и ключом, восстанавливая открытый текст.

Формально операция записывается как C = P ⊕ K, где C — шифротекст, P — открытый текст, K — ключ. Поскольку операция XOR является самодвойственной (P = C ⊕ K), процедуры шифрования и расшифрования идентичны.

¶Требования к ключу

Для обеспечения совершенной секретности ключ одноразового блокнота должен удовлетворять нескольким жёстким условиям. Во-первых, ключ должен быть по-настоящему случайным, то есть сгенерирован с использованием физических источников энтропии, а не детерминированных алгоритмов. Любая закономерность в ключе потенциально может быть использована криптоаналитиком. Во-вторых, длина ключа должна быть не меньше длины открытого текста. В-третьих, ключ никогда не должен использоваться повторно — даже частично. Повторное использование ключа для двух разных сообщений позволяет криптоаналитику сложить шифротексты по модулю два, получив XOR двух открытых текстов, что открывает возможности для частотного анализа. В-четвёртых, ключ должен храниться в строжайшей секретности и уничтожаться сразу после использования.

¶Практическое применение

Несмотря на абсолютную криптографическую стойкость, одноразовый блокнот имеет существенный недостаток — необходимость передачи ключа, длина которого равна длине сообщения. Эта проблема делает шифр экономически невыгодным для массового применения, однако в ряде областей он продолжает использоваться.

¶Дипломатическая и военная связь

Одноразовые блокноты исторически применялись для защиты особо важных каналов связи. Например, на «горячей линии» между Москвой и Вашингтоном, установленной в 1963 году после Карибского кризиса, использовались одноразовые шифровальные ленты. Ключи доставлялись дипломатической почтой, а сообщения передавались по телетайпу.

¶Разведывательная деятельность

Советские разведывательные сети использовали одноразовые блокноты на протяжении всей холодной войны. Известный случай — программа «Венона», в рамках которой американские криптоаналитики в 1940-х годах частично расшифровали советские сообщения именно потому, что советские шифровальщики повторно использовали страницы одноразовых блокнотов. Это наглядно демонстрирует критическую важность условия однократности использования ключа.

¶Современные системы

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

¶Критика и ограничения

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

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

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

¶Сравнение с другими шифрами

В отличие от блочных и поточных шифров, таких как AES или ChaCha20, одноразовый блокнот не может быть взломан перебором ключа, поскольку для любой криптограммы существует ключ, превращающий её в любой возможный открытый текст той же длины. Однако практическая стойкость современных алгоритмов основана на вычислительной сложности, в то время как одноразовый блокнот требует физической защиты ключа. Поточные шифры, такие как RC4, имитируют одноразовый блокнот, генерируя псевдослучайную гамму из короткого ключа, но не обладают совершенной секретностью.