Почему нельзя взломать шифр Вернама

Продолжается цикл статей о шифровании и криптографии. В предыдущих сериях:

Сегодня разберём невзламываемый симметричный шифр.

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

Как работают такие алгоритмы

Общие правила для абсолютно стойких шифров в симметричном шифровании такие:

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

Если в алгоритме соблюдаются все три правила, то такой шифр взломать нельзя даже теоретически.

Шифр Вернама — это просто

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

Шифр Вернама — это сложно

Теперь попробуем объяснить подробнее.

1. Сообщение хранится в виде битов данных. Допустим, мы шифруем текст. Компьютер не умеет работать с текстом как таковым, он этот текст хранит как набор числовых кодов (проще говоря, у компьютера все буквы пронумерованы и он помнит только эти номера).

Числа, в свою очередь, компьютер хранит в виде двоичного кода, то есть битов данных. Это пока что не относится к шифрованию, это просто то, как хранится любая текстовая информация в компьютере.

Двоичное счисление на пальцах

Буква	Код в ASCII	Биты данных
K	75	01001011
O	79	01001111
D	68	01000100

Если мы напишем KOD в кодировке ASCII, то для компьютера это будет последовательность из трёх чисел, а каждое число — это набор битов:

01001011 01001111 01000100

2. Берём случайные биты в качестве ключа шифрования. На входе у нас три числа по 8 бит. Чтобы их зашифровать, нам нужны 24 случайных бита. Возьмём их с потолка, они ничего не значат:

10101101 01111010 10101011

3. Накладываем коды друг на друга и применяем алгоритм шифрования. Шифр Вернама построен на принципе «исключающего ИЛИ», он же XOR. Он смотрит на каждую пару битов и пытается понять, они одинаковые или разные. Если биты одинаковые, результат проверки будет 0, если разные — 1.

Можно проверить себя так: XOR задаёт вопрос «Эти биты разные»? Если да — то 1, если нет — то 0.

Буква K	0	1	0	1	0	1	1
Ключ	1	0	1	1	1	0	1
XOR (Они разные?)	1	1	1	0	1	1	0

Если мы таким образом закодируем три буквы, мы получим три новых набора битов:

KOD (сообщение)	01001011	01001111	01000100
Ключ	10101101	01111010	10101011
Результат шифрования с помощью XOR	11100110	00110101	11101111

Получается, что на входе у нас было 24 бита данных и на выходе 24 бита данных. Но эти данные теперь совсем другие. Если перевести эти числа обратно в текст, мы получим:

KOD → æ5ï

Расшифровка шифра Вернама

Если у нас есть закодированное сообщение и ключ от него, то раскодировать его не составит труда. Мы просто пишем алгоритм, который применяет операцию XOR как бы в обратном порядке к каждому биту сообщения. Например:

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

Компьютер может совершать миллиарды таких операций в секунду. Главное — иметь на руках ключ для расшифровки.

Почему этот шифр невзламываемый

Для начала договоримся, что под взломом мы понимаем прочтение этого сообщения без ключа. Если бы у нас был ключ, мы бы прочитали это сообщение почти сразу, и это уже не взлом.

Теперь посмотрим, почему без ключа этот шифр невозможно взломать.

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

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

Пример работы

Если мы зашифруем так фразу «Привет, это журнал Код!», то можем получить что-то такое:

hi857ов9njg5jоlр6;p0ора

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

Срочно подпишись на код

Верни деньги, а то вилы

мама, я сдал зачёт, ура

Ваш зам предатель и вор

Ваш зам ни при чём, вот

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

Минусы шифра Вернама

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

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

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

Именно из-за таких требований к безопасности ключа этот шифр сейчас используется очень редко.