XOR и одноразовый блокнот

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

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

Биты и операция XOR

Компьютер хранит всё в виде битов — значков, которые бывают только двух видов: 0 и 1. Буква, цифра, пиксель — это просто договорённость, какой цепочкой битов что обозначать. Восемь битов подряд называют байтом.

Для шифрования битов есть удобная операция, которую называют XOR (от англ. exclusive or — «исключающее или») и обозначают ⊕. Она берёт два бита и выдаёт один по правилу «одно из двух, но не оба»:

a	b	a ⊕ b
0	0	0
0	1	1
1	0	1
1	1	0

Есть способ запомнить таблицу без зубрёжки. Представьте, что второй бит — это выключатель. Если он 0, первый бит проходит как есть. Если 1 — первый бит переворачивается: 0 становится 1, а 1 становится 0. Вот и всё правило.

Отсюда главное свойство XOR. Если перевернуть бит дважды, он вернётся на место. Значит, (сообщение ⊕ ключ) ⊕ ключ = сообщение. Одна и та же операция с одним и тем же ключом и шифрует, и расшифровывает — как ROT13 из урока о Цезаре, только по битам.

Чтобы шифровать буквы, их сначала переводят в биты. Компьютеры используют для этого кодировку UTF-8 (о ней — в уроке о кодировках), но в этом уроке возьмём код попроще, «телеграфный»: пробел — 0, А — 1, Б — 2 и так до Я — 33. Каждая буква занимает шесть битов. Например, Д — пятая буква, 5 = 000101.

Попробуйте сделать ключ из одних нулей: шифр совпадёт с сообщением. Сделайте ключ равным самому сообщению: получатся одни нули, ведь x ⊕ x = 0. Эти два крайних случая пригодятся в конце урока.

Перехвачен один знак шифровки: 011010. Из других источников известно, что открытым текстом была буква Т (двадцатая буква, 20 = 010100). Какими шестью битами её зашифровали?

Шифр = текст ⊕ ключ. «Перебросьте» текст на другую сторону: ключ = шифр ⊕ текст. XOR сам себе обратный.

Идите по битам слева направо: где биты шифра и текста одинаковые, в ключе 0, где разные — 1.

Складываем по XOR: 011010 ⊕ 010100. Первые биты 0 и 0 — одинаковые, пишем 0. Дальше 1 и 1 → 0, 1 и 0 → 1, 0 и 1 → 1, 1 и 0 → 1, 0 и 0 → 0. Ключ — 001110, то есть число 14.

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

Вернам и бесконечная лента

В 1917 году инженер американской телефонной компании AT&T Гилберт Вернам работал с телетайпами — машинами, которые передавали текст по проводу. Телетайп кодировал каждую букву пятью отверстиями на бумажной ленте: пробито или нет, 1 или 0. Это и был пятибитный код, предок нашего «телеграфного».

Вернам придумал простую приставку. Рядом с лентой сообщения бежит вторая лента — с ключом. Машина сравнивает их отверстие за отверстием и пробивает новое там, где у лент разные значения. Это ровно XOR. На другом конце провода такая же ключевая лента снимала шифр. Человеку ничего не надо было делать руками: печатаешь текст, а в линию уходит тарабарщина. Патент Вернам получил в 1919 году.

У первой версии была слабость: ключевую ленту склеивали в кольцо, и ключ повторялся. А повторяющийся ключ — это почти шифр Виженера, который ломают, найдя длину ключа. Решение предложил офицер связи армии США Джозеф Моборн: ключ должен быть совершенно случайным, длиной во всё сообщение и никогда не использоваться повторно. Так появился одноразовый блокнот в его нынешнем виде.

Почему его нельзя взломать

Вспомните, как мы ломали Цезаря: перебрали все ключи и нашли тот, при котором текст читается. Попробуем то же с одноразовым блокнотом. Ключ длиной в сообщение, каждый бит случаен. Перебираем…

И тут ловушка. Среди всех ключей обязательно найдётся такой, который превращает шифровку в «АТАКУЕМ НА РАССВЕТЕ». И другой — который даёт «ОТСТУПАЕМ К РЕКЕ». И третий — для «КУПИ ХЛЕБА И МОЛОКА». Каждый осмысленный текст нужной длины получается каким-то ключом. Перебор выдаёт не один ответ, а все возможные ответы сразу, и выбрать между ними не по чему.

Это рассуждение превратил в строгую теорему Клод Шеннон, основатель теории информации. Он доказал её в секретном отчёте 1945 года и опубликовал в 1949-м в статье «Теория связи в секретных системах». Шеннон назвал такое свойство совершенной секретностью: шифровка не сообщает о тексте ничего, кроме длины. Если до перехвата противник считал, что атака с вероятностью 30 %, то и после перехвата он считает так же. Шифровка не сдвинула его знание ни на волос.

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

Если одноразовый блокнот нельзя взломать, почему им не шифруют всё подряд?

Ключа нужно столько же, сколько данных, и его надо заранее тайно доставить получателю Потому что XOR слишком медленно считается Потому что его давно научились взламывать

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

Ошибка двойного блокнота

Самое уязвимое условие — «ровно один раз». Посмотрим, что будет, если двумя разными сообщениями воспользоваться одной и той же страницей блокнота.

Пусть перехвачены две шифровки: ш₁ = т₁ ⊕ к и ш₂ = т₂ ⊕ к, где к — один и тот же ключ. Сложим их по XOR: ш₁ ⊕ ш₂ = т₁ ⊕ к ⊕ т₂ ⊕ к. Ключ встречается дважды, а x ⊕ x = 0, так что он сокращается. Остаётся т₁ ⊕ т₂ — смесь двух открытых текстов без всякого ключа.

Смесь ещё не текст, но дальше работает обычная смекалка. Предположим, в одной телеграмме есть слово «ПАРОЛЬ». Если приложить его к смеси в правильном месте, оно «вычтется» — и на этом месте проступит кусок второй телеграммы. В неправильном месте получится каша. Догадку называют шпаргалкой (по-английски crib), а метод — протаскиванием шпаргалки: её двигают вдоль ленты, пока снизу не появится что-то читаемое.

Найдя кусок одной телеграммы, получаем кусок другой. Новый кусок подсказывает продолжение — «…ВЕЗУТ» явно было «ПРИВЕЗУТ», — и вот уже есть ещё несколько букв первой телеграммы. Шаг за шагом обе раскручиваются целиком, а заодно восстанавливается и ключ: к = ш₁ ⊕ т₁.

Две телеграммы зашифрованы одной страницей блокнота. Разведка уверена, что в одной из них есть слово «ПОЛНОЧЬ». Протащите его вдоль ленты. Какое слово стоит в другой телеграмме на том же месте?

Буквы под догадкой появляются почти на каждой позиции — это нормально, кодов в алфавите много. Ищите позицию, где они складываются в настоящее слово.

Слово «ПОЛНОЧЬ» обычно стоит в конце фразы. Начните с последних позиций.

На последней позиции, 24-й, под «ПОЛНОЧЬ» проступает ЧЕТВЕРГ. Ни на какой другой позиции не выходит осмысленного слова: «ПОЛЁЕ Р», «ПОДЧЗУЖ» — это каша, хоть она и из букв.

Телеграммы целиком: «ЖДИТЕ НАШЕГО СИГНАЛА В ПОЛНОЧЬ» и «ГРУЗ ОТПРАВЯТ ТОЛЬКО В ЧЕТВЕРГ». Дальше их можно было бы раскрутить, подставляя «В » и «ГРУЗ». Шеннон гарантировал стойкость одной страницы, а не двух.

«Венона»: как сэкономили на бумаге

Именно эта ошибка случилась на самом деле. В начале 1942 года, в самый тяжёлый момент войны, советская служба, изготовлявшая шифроблокноты, не успевала выпускать их достаточно. Часть страниц была отпечатана в двух экземплярах и попала в разные блокноты. Каждый блокнот по отдельности использовался «правильно», один раз, но одинаковые страницы оказались у разных отправителей.

В феврале 1943 года армейская служба радиоразведки США в Арлингтон-Холле начала изучать перехваченные советские дипломатические телеграммы. Проект позже назвали «Венона». Дешифровщики заметили совпадения: какие-то шифровки были зашифрованы одним и тем же ключом. Дальше — годы кропотливой работы с кодовыми книгами и шпаргалками. Лингвист Мередит Гарднер с 1946 года восстанавливал словарь советского кода.

Прочитать удалось лишь часть телеграмм, и часто только кусками, но и этого хватило. Расшифровки помогли выйти на физика Клауса Фукса, передававшего сведения об атомной бомбе, и на сеть Юлиуса Розенберга. Проект закрыли в 1980 году, а рассекретили в 1995-м.

Агент дважды зашифровал одно и то же донесение двумя разными страницами блокнота и отправил обе шифровки. Что получит противник, сложив их по XOR?

Смесь двух страниц ключа: к₁ ⊕ к₂, а текст сократится Сам открытый текст Одни нули

(т ⊕ к₁) ⊕ (т ⊕ к₂) = к₁ ⊕ к₂: одинаковый текст сокращается, остаются две случайные страницы. Это бесполезно для противника, но и само повторное донесение разумно было бы не слать.

XOR сегодня

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

Выход — поточные шифры. Они берут короткий ключ, скажем 256 битов, и разворачивают его в сколь угодно длинную ленту псевдослучайных битов, а затем делают с ней XOR, как Вернам. Лента не по-настоящему случайна, поэтому совершенной секретности по Шеннону нет. Зато, чтобы отличить её от случайной, нужно перебрать столько ключей, что не хватит всех компьютеров мира. Такой шифр, ChaCha20, шифрует сегодня часть соединений HTTPS.

Главный современный шифр, AES, устроен иначе: он перемешивает данные блоками по 16 байт, раунд за раундом. Но и в каждом его раунде есть XOR с частью ключа, а в самом популярном режиме работы AES тоже вырабатывает ленту, которую складывают с данными по XOR. Попробуйте его в утилите «Шифрование AES по паролю». А в утилите XOR можно поиграть с повторяющимися ключами и атакой по известному началу текста — она пригодится в квесте.

Что взять с собой

• XOR — «одно из двух, но не оба». Единица в ключе переворачивает бит, ноль оставляет. Дважды применённый ключ возвращает текст.
• Одноразовый блокнот: случайный ключ длиной в сообщение, XOR (или сложение по модулю), один раз. Шеннон доказал, что такая шифровка не говорит о тексте ничего, кроме длины.
• Если одной страницей ключа зашифровать два текста, ключ сокращается: ш₁ ⊕ ш₂ = т₁ ⊕ т₂. Дальше их раскручивают догадками. Так работала «Венона».
• Если известен кусок открытого текста, XOR тут же выдаёт кусок ключа: к = ш ⊕ т.
• Современные поточные шифры и AES не дают совершенной секретности, зато обходятся коротким ключом — и внутри у них всё тот же XOR.

Шифр прячет сообщение так, чтобы его можно было вернуть. А что, если вернуть ничего не нужно, зато нужно уметь проверять — тот ли это файл, тот ли пароль? Для этого придумали «отпечатки» данных. Дальше: хеши →