Одноразовое заполнение (шифр Вернама)

В 1949 году американский криптограф Клод Шеннон опубликовал работу, в которой доказал абсолютную стойкость шифра Вернама, который также известен, как одноразовый блокнот (one-time pad).

Рис.3. Система одноразового шифрования

В системе одноразового заполнения каждое сообщение шифруется с ключом, который затем сбрасы­вается и никогда не используется снова. Поэтому ключ используется только один раз, давая шифру его название. Криптограмма зависит от сообщения и ключа, но так как ключ уникален для данной передачи и никогда повторно не используется, то подслушивающий не имеет никакой возможности узнать его и взломать шифр. Процесс кодирования может быть очень простым — нужно просто добавлять ключ к сообщению (рис.3).

Шифр Вернама был изобретен в 1917 году Мейджором Джозефом Моборном (Major Joseph Mauborn) и Гильбертом Вернамом (Gilbert Vernam) из AT&T (American Telephone & Telegraph). Суть шифрования одноразовым заполнением заключается в следующем: открытый текст представляется в виде пятизначных "импульсных комбинаций"(код Бодо). В этом коде, например, буква "А" имеет вид (+ + — — —). На бумажной ленте эта буква получала следующий вид:

Знак "+" означал отверстие, а знак "—" - его отсутствие. При считывании с ленты пятерка металлических щупов "опознавала" отверстия (при наличии отверстия щуп замыкал электрическую цепь). В линию связи посылались импульсы тока:

Вернам предложил электромеханически покоординатно складировать импульсы знаков секретного текста с импульсами гаммы (гамма - это секретный ключ, представляющий из себя хаотический набор букв того же самого алфавита). Сложение, по современной терминологии, осуществлялось "по модулю 2"(логика XOR или ИЛИ-НЕ):

(здесь "0" означает знак "—" "кода Бодо", а 1 - "+"). Пусть, например, знак гаммы имеет вид:

,

тогда буква "А" при шифровании переходит в двоичную комбинацию:

,

при расшифровывании ту же операцию необходимо повторить (покоординатно):

Для шифрования булевой строки длины N используется секретный ключ - полностью случайная булева строка длины N. Отправитель и Получатель имеют этот секретный ключ, и больше никто его не знает. Чтобы послать Получателю сообщение (булеву строку длины N), Отправитель побитно складывает текст сообщения с секретным ключом по модулю 2 и пересылает результат Получателю. Получатель, имея точно такой же ключ, сможет восстановить исходное сообщение, побитно сложив полученную от Отправителя строку с ключом. Шенноном было доказано, что такой шифр будет абсолютно стойким при условии полной случайности ключа и однократности его использования.

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