Гилберт Сэндфорд Вернам (3 апреля 1890 — 7 февраля 1960) был выпускником Вустерского политехнического института в 1914 году и инженером AT&T Bell Labs , который в 1917 году изобрел аддитивный полиалфавитный поточный шифр , а затем стал соавтором автоматизированного одноразового блокнотного шифра . Вернам предложил шифр телетайпа, в котором заранее подготовленный ключ , хранящийся на бумажной ленте , посимвольно комбинируется с открытым текстовым сообщением для получения зашифрованного текста . Чтобы расшифровать зашифрованный текст, тот же ключ снова должен быть объединен посимвольно, образуя открытый текст . Позже Вернам работал в Postal Telegraph Company и стал сотрудником Western Union , когда эта компания приобрела Postal в 1943 году. Его более поздняя работа была в основном связана с системами автоматического переключения для телеграфных сетей.
Комбинирующая функция Вернама, указанная в патенте США 1310719 , выданном 22 июля 1919 года, представляет собой операцию XOR , применяемую к отдельным импульсам или битам , используемым для кодирования символов в коде Бодо . Вернам не использовал в патенте термин «исключающее ИЛИ», но реализовал эту операцию в релейной логике. В примере, который привел Вернам, открытый текст — это A , закодированный как « ++--- » в Бодо, а ключевой символ — это B , закодированный как « +--++ ». Результирующим зашифрованным текстом будет « -+-++ », который кодирует G. Объединение G с ключевым символом B на принимающей стороне дает « ++--- », который является исходным открытым текстом A. АНБ назвало этот патент «возможно , одним из самых важных в истории криптографии». [1]
Вскоре после этого Джозеф Моборн , в то время капитан Корпуса связи армии США , предложил, кроме того, чтобы ключ на бумажной ленте содержал случайную информацию. Эти две идеи, объединенные вместе, реализуют автоматическую форму одноразового блокнота , хотя ни один из изобретателей тогда не использовал это название.
Клод Шеннон , также работавший в Bell Labs, в своем исследовании времен Второй мировой войны , которое позже было опубликовано в октябре 1949 года , доказал, что правильно установленный одноразовый блокнот не может быть взломан. Он также доказал, что любая неразрушимая система должна иметь по существу те же характеристики, что и одноразовый блокнот: ключ должен быть действительно случайным, такого же размера, как и открытый текст, никогда не использоваться повторно полностью или частично и храниться в секрете. [2]
В современной терминологии шифр Вернама представляет собой симметричный поточный шифр, в котором открытый текст объединяется со случайным или псевдослучайным потоком данных («ключевой поток») той же длины для генерации зашифрованного текста с использованием логического «исключающего или» ( XOR) функция. Это обозначается ⊕ [3] и представлено следующей « таблицей истинности », где + представляет «истину», а – представляет «ложь».
Другие названия этой функции: «Не равно» (NEQ), сложение по модулю 2 (без «переноса») и вычитание по модулю 2 (без «заимствования»).
Шифр является взаимным, поскольку один и тот же ключевой поток используется как для шифрования открытого текста в зашифрованном тексте, так и для расшифровки зашифрованного текста с получением исходного открытого текста:
и:
Если поток ключей действительно случайный и используется только один раз, это фактически одноразовый блокнот . Замена псевдослучайных данных, сгенерированных криптографически безопасным генератором псевдослучайных чисел, является распространенной и эффективной конструкцией потокового шифра. RC4 — это пример шифра Вернама, который широко используется в Интернете.
Однако если один и тот же поток ключей используется для двух сообщений, известных криптоаналитикам как глубина , влияние потока ключей можно устранить, оставив два открытых текста объединенными XOR. Результат эквивалентен шифру с бегущим ключом, и два открытых текста могут быть разделены с помощью лингвистических криптоаналитических методов.
Ошибка оператора такого рода, как известно, позволила британцам провести криптоанализ шифра Лоренца в Блетчли-парке во время Второй мировой войны . Они диагностировали, как генерируется ключевой поток, придумали, как взломать шифр, и прочитали огромное количество сообщений высокого уровня, поступающих и исходящих от немецкого командования, даже не видя настоящей машины Лоренца. [4]