Страница:
В результате у американцев, которых совершенно не волновал отдаленный грохот войны в Европе, вдруг пробудилось сознание того, что война стояла у их границ. Удивленно вздрогнули техасцы: оказывается, немцы хотели отдать их штат мексиканцам! Жители Среднего Запада живо представили себе, как мексиканские войска, ведомые немецкими офицерами, переходят через границу и захватывают их прерии. При упоминании о возможной японской агрессии, подобно фугасной мине, взорвалось Западное побережье США. В течение месяца общественное мнение стало единым. Его выразил Вильсон, который всего три месяца назад говорил, что было бы «преступлением против цивилизации» ввергнуть страну в войну. 2 апреля он заявил, что «справедливость дороже мира», и обратился к конгрессу с призывом любыми средствами добиться торжества справедливости. В своем выступлении перед конгрессом Вильсон сослался на шифртелеграмму Циммермана:
Так прочтение дипломатической шифртелеграммы Германии помогло подтолкнуть Соединенные Штаты к вступлению в Первую мировую войну, что дало Англии и Франции возможность одержать победу над врагом и занять командные высоты в послевоенном мире. Никакая другая криптоаналитическая разработка не имела таких огромных последствий. Никогда, ни до этого, ни после, в результате дешифрования одного секретного сообщения не происходило так много важных событий, влиявших на ход мировой истории.
Секретность на продажу
«О том, что немецкое правительство намерено натравить на нас врагов у самого нашею порога, красноречиво свидетельствует перехваченная телеграмма, адресованная немецкому посланнику в Мехико. Мы принимаем этот враждебный вызов… Я рекомендую конгрессу объявить, что проводившийся за последнее время курс имперского правительства Германии в действительности является не чем иным, как настоящей войной против правительства и народа Соединенных Штагов, и официально провозгласить статус воюющей стороны, который был нам навязан таким образом».Конгресс удовлетворил просьбу президента Вильсона. Вскоре в Европу стали прибывать американские солдаты. Свежие силы молодой нации хлынули в окопы Западного фронта, чтобы спасти обессиленные войска Антанты.
Так прочтение дипломатической шифртелеграммы Германии помогло подтолкнуть Соединенные Штаты к вступлению в Первую мировую войну, что дало Англии и Франции возможность одержать победу над врагом и занять командные высоты в послевоенном мире. Никакая другая криптоаналитическая разработка не имела таких огромных последствий. Никогда, ни до этого, ни после, в результате дешифрования одного секретного сообщения не происходило так много важных событий, влиявших на ход мировой истории.
Секретность на продажу
Ранним декабрьским утром 1917 г. симпатичный молодой человек стремительно промчался между массивными колоннами вестибюля здания компании «Америкэн телефон энд телеграф» («AT&T»), расположенного в деловой части Нью-Йорка. Он вбежал в лифт и поднялся на нем на 17-й этаж, где находилось телеграфное отделение компании, входившее в состав ее научно-исследовательского отдела. Это отделение, в котором работали несколько самых талантливых инженеров, уже год занималось доведением до ума новейшего достижения в области телеграфии – буквопечатающего телеграфного аппарата, который в отделении нарекли телетайпом.
Молодого человека звали Гильберт Вернам, и он всегда немного опаздывал. Коллеги считали Вернама весьма толковым инженером и способным изобретателем. Среди них ходили слухи о том, что каждый вечер, растягиваясь на диване, он спрашивал сам себя вслух: «Что бы такое еще изобрести?» У Вернама был редкий склад ума, который позволял ему придумывать оригинальную электрическую цепь и затем переносить ее на чертежный холст, не воспроизводя все требуемые соединения с помощью проводов. Вернам очень хорошо зарекомендовал себя на работе, поэтому начальник телеграфного отделения компании «AT&T» Паркер без колебаний пригласил его принять участие в разработке особо секретного проекта. И хотя в это декабрьское утро Вернам опять опоздал, в его голове уже успела созреть прекрасная идея. Тихий и скромный по натуре, Вернам довольно несмело изложил свою идею коллегам, которые сразу же сочли ее заслуживающей особого внимания.
Работа над секретным проектом началась еще летом, несколько месяцев спустя после того, как Соединенные Штаты объявили войну Германии. Паркер поручил нескольким своим подчиненным исследовать вопрос о возможности сохранять в тайне сообщения, передаваемые по телетайпу. Оказалось, что колебания тока в линии связи могли быть записаны с помощью осциллографа и затем легко преобразованы в буквы передаваемого сообщения. Поэтому было решено внести изменения в соединения проводов печатающего механизма телетайпа. В результате текст сообщения шифровался методом одноалфавитной замены. В телеграфном отделении понимали, что такая защита являлась слишком слабой, однако ничего другого придумать не смогли и перестали заниматься этой проблемой до тех самых пор, пока Вернам не поведал им о своей идее.
Вернам предложил использовать особенности телетайпного кода, в котором кодируемый знак выражается в виде пяти элементов. Каждый из этих элементов символизирует наличие («плюс») или отсутствие («минус») электрического тока в линии связи. Таким образом, имеются 32 различных комбинации «плюсов» и «минусов». 26 из них ставятся в соответствие буквам, а оставшиеся 6 обозначают «служебные комбинации» (пробел между словами, переход с букв на цифры и знаки препинания, обратный переход с цифр и знаков препинания на буквы, возврат каретки печатающего устройства, переход на новую строку и холостой ход). Например, буква «А» выражается комбинацией «+ + – – -», букве «N» соответствует «– – + + -», а переход на цифры и знаки препинания задается через «+ + – + +». Закодированное сообщение набивается на перфоленте: «плюсы» представляются отверстиями, а «минусы» – их отсутствием. При считывании перфоленты металлические щупы проходят через отверстия, замыкают электрическую цепь и посылают импульсы тока по проводам. А там, где на перфоленте находится «минус», бумага не позволяет этим щупам замкнуть цепь, и в результате токовый импульс не передается.
Вернам предложил готовить перфоленту со случайными знаками (так называемую «гамму») заранее и затем электромеханически складывать ее импульсы с импульсами знаков открытого текста. Полученная сумма представляла собой шифртекст, предназначенный для передачи по линии связи. Вернам установил следующее правило суммирования: если сразу оба импульса являются «плюсами» или «минусами», то итоговый импульс будет «минусом», а если эти импульсы различны, то в результате получится «плюс».
Чтобы при шифровании суммировать импульсы электрически, Вернам сконструировал специальное устройство, состоящее из магнитов, реле и токосъемных пластин. А поскольку процедура расшифрования была совершенно аналогична процедуре зашифрования, это же самое устройство могло быть использовано и при расшифровании. Импульсы поступали в устройство суммирования с двух считывателей: один считывал «гамму», а другой – открытый текст. Получающиеся на выходе «плюсы» и «минусы» можно было передавать подобно обычному телетайпному сообщению. На приемном конце устройство, изобретенное Вернамом, прибавляло импульсы, которые считывались с идентичной ленты с «гаммой», и восстанавливало исходные импульсы открытого текста.
Вся прелесть изобретения Вернама заключалась в том, что больше не требовалось осуществлять зашифрование и расшифрование секретных сообщений в виде отдельных операций. Открытый текст входил в аппарат, находившийся у отправителя сообщения, и точно такой же открытый текст выходил из аппарата, принадлежавшего получателю этого сообщения. А если кто-либо перехватывал это сообщение по пути следования от отправителя к получателю, то в его распоряжении оказывалась ничего не значащая последовательность «плюсов» и «минусов». Теперь, чтобы зашифровать, передать, принять и расшифровать сообщение, требовалось приложить не намного больше усилий, чем при отправке сообщения открытым текстом. Основное преимущество изобретенного Вернамом метода засекречивания сообщений заключалось не в механическом шифровании открытого текста с последующей печатью результата на бумаге, что было осуществлено еще в начале 70-х годов XIX века французами Эмилем Винеем и Жозефом Госсеном. Вернам сумел слить воедино два процесса – шифрование и передачу сообщения. Он создал то, что впоследствии назвали линейным шифрованием, чтобы отличать его от ставшего традиционным предварительного шифрования. Вернам освободил процесс шифрования от оков времени и ошибок, исключив из этого процесса человека. Выдающийся вклад, внесенный Вернамом в практику шифрования, заключается именно в том, что он привнес в шифровальное дело автоматизацию, уже успевшую к тому времени сослужить людям огромную службу во многих областях их деятельности.
Вокруг идеи, высказанной Вернамом в кругу коллег, моментально развернулась кипучая деятельность. Сначала Вернама заставили изложить эту идею в краткой записке, датированной 17 декабря. Компания «AT&T» уведомила об изобретении Вернама американское военно-морское ведомство, с которым она поддерживала тесное сотрудничество. 18 февраля 1918 г. состоялось совещание, в котором приняли участие Паркер, Вернам и другие инженеры из телеграфного отделения компании «AT&T», с одной стороны, и военные моряки, с другой.
27 марта эти же инженеры встретились со своими коллегами из американской компании «Вестерн электрик», производственного филиала «AT&T», и договорились с ними об изготовлении первых двух линейных шифраторов с использованием как можно большего количества стандартных деталей. В лаборатории «Вестерн электрик» они подсоединили изготовленные шифраторы к телетайпам и осуществили первые испытания процесса, который назвали «автоматическим шифрованием». Все устройства, вовлеченные в него, работали превосходно. Компания «AT&T» проинформировала об этом факте майора Джозефа Моборна, который занимал тогда пост начальника отдела научно-исследовательских и конструкторских разработок войск связи США.
Нерешенным оставался всего один вопрос – откуда брать «гамму». В первые дни «гамма» для устройства Вернама представляла собой склеенные петлей короткие перфоленты, на которые были набиты знаки, извлеченные наугад из различных открытых текстов. Инженеры компании «AT&T» почти сразу обратили внимание на существенные изъяны такого процесса «автоматического шифрования», связанные с недостаточной длиной «гаммы». Поэтому, чтобы затруднить криптоанализ, они сделали перфоленты с «гаммой» более длинными. Но тогда с этими перфолентами стало слишком трудно обращаться.
Вернам предложил суммировать две короткие, имеющие различную длину «гаммы» таким образом, как будто бы одна «гамма» шифровала другую. Получающаяся в результате так называемая вторичная «гамма», имевшая значительно большую длину, чем две исходные, первичные «гаммы», которые были использованы для ее генерации, применялась для зашифрования открытого текста. Например, если одна закольцованная лента имела 1000 знаков, а другая 999, то данное различие в длинах всего в один знак давало 999000 комбинаций, прежде чем результирующая последовательность повторялась.
Однако Моборн понимал, что даже усовершенствованная система Вернама весьма уязвима для криптоанализа. В свои 36 лет будущий начальник войск связи США Моборн был незаурядным криптоаналитиком. Он основательно изучил криптоанализ в армейской школе связи и был хорошо знаком с последними достижениями в этой области. Более того, за несколько лет до описываемых событий Моборн сам принимал участие в одной научно-исследовательской работе, в ходе которой специалисты из армейской школы связи сделали вывод о том, что единственной стойкой «гаммой» является такая, которая сравнима по длине с самим шифруемым сообщением. Любое повторение в «гамме» подвергает огромному риску полученные с ее помощью криптограммы и, скорее всего, приведет к их вскрытию. Проведенный Моборном анализ системы «автоматического шифрования» еще более убедил его в этом. Он понял, что не имеет никакого значения, находятся ли повторения в пределах одной криптограммы или они распределены по нескольким, получаются ли они путем комбинирования двух первичных «гамм» или в результате простого повторения в единой длинной «гамме». Важно то, что в «гамме» повторений не должно быть ни при каких условиях. Необходимо, чтобы она была совершенно уникальна и предельно хаотична.
Осознав это, Моборн объединил свойство хаотичности «гаммы», на которое опирался Вернам в своей системе «автоматического шифрования», со свойством уникальности «гаммы», выработанным криптографами армейской школы связи, в системе шифрования, которую ныне принято называть «одноразовым шифрблокнотом». Одноразовый шифрблокнот содержит случайную «гамму», которая используется один, и только один раз. При этом для каждого знака открытого текста, принадлежащего всей совокупности сообщений, которые уже были посланы данной группой шифркорреспондентов или еще только будут посланы ею в обозримом будущем, предусматривается использование абсолютно нового и не поддающегося предсказанию знака «гаммы».
Это абсолютно стойкая шифрсистема. Подавляющее большинство систем шифрования являются абсолютно стойкими лишь на практике, поскольку криптоаналитик может найти пути их вскрытия при наличии у него определенного количества шифртекста и достаточного времени для его исследования. Одноразовый же шифрблокнот является абсолютно стойким как в теории, так и на практике. Каким бы длинным ни был перехваченный шифртекст, сколько бы много времени ни отводилось на его исследование, криптоаналитик никогда не сможет вскрыть одноразовый шифрблокнот, использованный для получения этого шифртекста. И вот почему.
Вскрытие многоалфавитного шифра означает объединение всех букв, зашифрованных при помощи одного шифралфавита, в единую группу, которую можно изучать на предмет выявления ее лингвистических особенностей. Методы такого объединения могут быть различны в зависимости от вида «гаммы». Так, метод Казиского заключается в выделении идентично гаммированных букв открытого текста при повторяющейся «гамме». Связная «гамма» может быть вскрыта путем взаимного восстановления открытого текста и «гаммы». А «гамма», использованная для зашифрования двух или более сообщений, поддается вскрытию путем одновременного восстановления открытых текстов этих сообщений, причем правильность прочтения одного текста контролируется читаемостью другого. Почти для всех разновидностей многоалфавитиых шифров разработан свой метод вскрытия, который основан на их отличительных особенностях.
Совершенно иначе обстоит дело с одноразовым шифрблокногом. В этом случае криптоаналитик не имеет отправной точки для своих исследований, так как в одноразовой шифрсистеме «гамма» не содержит повторений, не используется более одного раза, не является связным текстом и не имеет внутренних структурных закономерностей. Поэтому все методы дешифрования, в той или иной мере основанные на этих характеристиках, не дают никаких результатов. Криптоаналитик заходит в тупик.
А как обстоит дело с методом тотального опробования? Ведь прямой перебор всех возможных ключей в конечном счете обязательно приведет криптоаналитика к открытому тексту. Однако успех, приобретенный этим путем, иллюзорен. Тотальное опробование действительно позволяет получить исходный открытый текст. Но оно также даст и каждый другой возможный текст той же длины, и сказать, какой из них является истинным, будет невозможно.
Предположим, что криптоаналитик пытается дешифровать четырехбуквенное военное сообщение, применяя все «гаммы», начиная с «АААА». Используя «AABI» в качестве «гаммы», он получает открытый текст «kiss»56. Неподходящий вариант для данного контекста. Криптоаналитик не останавливается на достигнутом. С помощью «AAEL» получается открытый текст «kill»57. Уже лучше, но хочется удостовериться, нет ли чего более подходящего. Исследование продолжается, и при «гамме» «ААЕМ» выходит слово «kilt»58. «AAER» дает «kiln»59, «GZBM» – «fast»60, «KHIA» – «slow»61, «HRIW» – «stop»62, «PZVQ» – «hard»63 и «RZBU» – «easy»64. Когда криптоаналитик доберется, наконец, до «гаммы» «ZZZZ», он обнаружит, что просто составил перечень всевозможных английских слов из четырех букв.
У криптоаналитика остается последняя надежда. Предположим, что он получил н свое распоряжение открытый текст какой-то отдельной криптограммы (например, в результате ошибки связиста). В состоянии ли криптоаналитик использовать «гамму», которую он сможет теперь вычислить, имея на руках открытый и соответствующий ему шифрованный тексты, для определения алгоритма, с помощью которого была выработана эта «гамма», чтобы потом предугадать все будущие «гаммы»? Нет, не в состоянии. Ведь если «гамма» действительно случайна, это значит, что она не подчиняемся никаким видимым закономерностям.
Правильный ответ опять ускользает от криптоаналитика. Одноразовая случайная «гамма» полностью подавляет его, растворяя все усилия криптоаналитика в хаосе, с одной стороны, и в бесконечности, с другой. Здесь он сталкивается с пропастью, непреодолимой для человека.
Почему же горда этот самый совершенный шифр не нашел всеобщего применения? Ответ прост, из-за огромного количества «гаммы», которая требуется при его использовании. Проблемы, возникающие при изготовлении, рассылке и уничтожении «гаммы», человеку непосвященному во все тонкости организации шифрсвязи могут показаться пустячными, однако в военное время объемы переписки зачастую удивляют даже самых бывалых связистов. В течение суток может понадобиться зашифровать сотни тысяч слов, а для этого требуется изготовить миллионы знаков «гаммы». И поскольку «гамма» для каждого сообщения должна быть единственной и неповторимой, то ее общий объем будет эквивалентен объему всей переписки за время воины.
В общем, практические проблемы не позволяют применять одноразовые шифрблокноты в быстро меняющихся ситуациях, например в ходе проведения военных операций. Этих проблем не существует в более стабильных условиях: в высших военных штабах, дипломатических представительствах или в агентурной переписке одноразовые шифрблокноты достаточно практичны и находят повсеместное применение. Однако и здесь возникают непреодолимые трудности, если объем переписки слишком велик.
Это как раз и произошло, когда Моборн, устроив первое крупное испытание шифрсистемы Вернама, установил его машины сразу в трех городах. Даже при сравнительно небольшом объеме переписки (до 135 коротких сообщений в день) оказалось невозможным изготовить достаточное количество качественной «гаммы». Поэтому, не найдя другого выхода из затруднительного положения, Моборн стал комбинировать две относительно короткие «гаммы», чтобы получать из них более длинную «гамму», как это первоначально предлагал делать сам Вернам.
В сентябре 1918 г. Вернам отправился в Вашингтон и подал там заявку на патент. Первая мировая война успела закончиться прежде, чем шифрсистема Вернама сумела хоть как-то проявить свои достоинства на практике. Тем не менее 22 июля 1919 г. на нее был выдан патент № 1310719, являющийся, по-видимому, самым важным в истории криптографии. Эксперты из вашингтонского патентного бюро признали возможную полезность этого изобретения и в мирное время.
Однако, хотя устройство, придуманное Вернамом, несомненно являлось ценным плодом творческой инженерной мысли талантливого изобретателя, в коммерческом плане оно потерпело полный провал. Телеграфные компании и коммерческие фирмы, которые, по мнению «AT&T», должны были в массовых количествах покупать запатентованные шифрприставки Вернама к своим телетайпам, отдавали предпочтение старомодным кодам, которые существенно снижали длину сообщений, тем самым уменьшая телеграфные расходы и одновременно обеспечивая хоть какую-то, пусть небольшую, безопасность переписки. После окончания Первой мировой войны бюджеты вооруженных сил всех стран были сокращены до минимума. Недостаток средств и нехватка материальных ресурсов вынудили армейских связистов снова вернуться к комбинированию двух относительно коротких лент с «гаммой», а продемонстрированная военными криптоаналитиками слабая стойкость такой системы генерации «гаммы» привела к тому, что шифрсистема Вернама на некоторое время была предана забвению.
Что же касается самого Вернама, то он продолжал заниматься научно-исследовательской работой в компании «AT&T». Он немного усовершенствовал свою шифрсистему, а также изобрел устройство для автоматического зашифрования написанного от руки текста во время его передачи фототелеграфом. В 1929 г. Вернама со значительным повышением перевели в один из филиалов компании «AT&T». Однако через четыре месяца в США разразился финансовый кризис, и, так как Вернам еще не успел заработать достаточный трудовой стаж на новом месте, его вскоре уволили. Он перешел на работу в другую крупную компанию, но резкая перемена в его личной судьбе, видимо, подействовала на него угнетающе. С каждым годом о Вернаме было слышно все меньше и меньше, пока, наконец, 7 февраля 1960 г. человек, автоматизировавший процесс шифрования, умер в полной безвестности у себя дома.
История науки изобилует совпадениями. Например английский астроном Джон Адамс и его французский коллега Урбен Леверье почти одновременно сделали вывод о существовании планеты Нептун. Неудивительно, что подобные совпадения имели место и в криптографии. Случилось так, что в период между двумя мировыми войнами одно из таких совпадений затронуло сразу несколько человек. Как и Вернам, побуждаемые широким использованием секретной связи в военное время и вдохновляемые наступлением эпохи механизации, они независимо друг от друга изобрели машину, принцип действия которой на протяжении очень продолжительного времени находил наиболее широкое применение в криптографии. Этот принцип основывается на использовании колеса с перепайками – так называемого шифрдиска.
Шифрдиск представляет собой толстую круглую пластину, изготовленную из изоляционного материала (например, из твердой резины). С обеих сторон шифрдиска по окружности на равном расстоянии друг от друга закреплены по 26 электрических контактов (чаще всего они делались из латуни). Каждый контакт соединяется перепайкой с каким-либо другим контактом на противоположной поверхности шифрдиска. Таким образом, образуется электрическая цепь, которая начинается на одной стороне шифрдиска и заканчивается на другой.
Если условиться, что контакты на одной (входной) поверхности представляют буквы открытого текста, а контакты на другой (выходной) поверхности – буквы шифртекста, то проволочные перепайки между входной и выходной поверхностью обеспечивают преобразование открытого текста в криптограмму. Для зашифрования буквы открытого текста нужно только подать импульс тока на входной контакт, соответствующий этой букве. Ток пройдет по соединительному проводнику и появится на выходном контакте, представляющем букву шифртекста. Если записать все перепайки диска, зафиксировав соединения между входной и выходной поверхностью, то получится шифр одноалфавитной замены. Таким образом, шифрдиск воплощает процесс шифрования в форме, удобной для электромеханических манипуляций.
Для выполнения этих манипуляций шифрдиск устанавливается между двумя неподвижными круглыми пластинами, каждая из которых также изготовлена из изоляционного материала и снабжена 26 контактами, которые закреплены по кругу и соответствуют контактам, имеющимся на шифрдиске. Контакты входной пластины соединены с клавишами пишущей машинки, на которой набивается открытый текст. А каждый контакт выходной пластины связан с каким-либо устройством, предназначенным для вывода шифртекста (например, с сигнальной лампочкой). В результате, например, когда шифровальщик нажимает на клавишу «А» на пишущей машинке, он посылает токовый импульс от источника тока на контакт неподвижной входной пластины, закрепленный за буквой «А». Затем этот импульс попадает на входной контакт шифрдиска, соответствующий «А», и далее через перепайку проходит на выходной контакт, а с него – на лампочку, которая загорается над буквой шифртекста (пусть это будет буква «R»), которая ставится в соответствие букве «А».
Если бы все на этом и заканчивалось, то шифрдиск не был бы таким замечательным устройством. Тогда каждый раз при нажатии на клавишу «А» ток протекал бы по одной и той же электрической цепи и в итоге указывал бы на одну и ту же букву шифртекста.
Но все дело в том, что шифрдиск не остается неподвижным. Он вращается. Предположим, что он повернулся на одну позицию. Ток, который раньше, покидая контакт «А» входной пластины, попадал на контакт «R» выходной пластины, теперь преобразуется в совершенно другую букву, так как новый контакт шифрдиска с перепайкой, отличной от прежней, теперь встал против контакта «А» входной пластины. Подобным же образом всем другим буквам открытого текста ставятся в соответствие иные буквы шифртекста. Получается новый шифралфавит, причем каждый раз, когда шифрдиск поворачивается, используется другой шифралфавит. Можно выписать все эти шифралфавиты в виде таблицы из 26 строк и такого же количества столбцов. Если шифровальная машина сконструирована так, что шифрдиск поворачивается ровно на одну позицию каждый раз, когда зашифровывается какая-либо буква открытого текста, то итоговый результат будет таким же, как и при циклическом использовании этой таблицы строка за строкой сверху вниз. Получится не что иное, как шифр многоалфавитной замены с периодом 26.
Молодого человека звали Гильберт Вернам, и он всегда немного опаздывал. Коллеги считали Вернама весьма толковым инженером и способным изобретателем. Среди них ходили слухи о том, что каждый вечер, растягиваясь на диване, он спрашивал сам себя вслух: «Что бы такое еще изобрести?» У Вернама был редкий склад ума, который позволял ему придумывать оригинальную электрическую цепь и затем переносить ее на чертежный холст, не воспроизводя все требуемые соединения с помощью проводов. Вернам очень хорошо зарекомендовал себя на работе, поэтому начальник телеграфного отделения компании «AT&T» Паркер без колебаний пригласил его принять участие в разработке особо секретного проекта. И хотя в это декабрьское утро Вернам опять опоздал, в его голове уже успела созреть прекрасная идея. Тихий и скромный по натуре, Вернам довольно несмело изложил свою идею коллегам, которые сразу же сочли ее заслуживающей особого внимания.
Работа над секретным проектом началась еще летом, несколько месяцев спустя после того, как Соединенные Штаты объявили войну Германии. Паркер поручил нескольким своим подчиненным исследовать вопрос о возможности сохранять в тайне сообщения, передаваемые по телетайпу. Оказалось, что колебания тока в линии связи могли быть записаны с помощью осциллографа и затем легко преобразованы в буквы передаваемого сообщения. Поэтому было решено внести изменения в соединения проводов печатающего механизма телетайпа. В результате текст сообщения шифровался методом одноалфавитной замены. В телеграфном отделении понимали, что такая защита являлась слишком слабой, однако ничего другого придумать не смогли и перестали заниматься этой проблемой до тех самых пор, пока Вернам не поведал им о своей идее.
Вернам предложил использовать особенности телетайпного кода, в котором кодируемый знак выражается в виде пяти элементов. Каждый из этих элементов символизирует наличие («плюс») или отсутствие («минус») электрического тока в линии связи. Таким образом, имеются 32 различных комбинации «плюсов» и «минусов». 26 из них ставятся в соответствие буквам, а оставшиеся 6 обозначают «служебные комбинации» (пробел между словами, переход с букв на цифры и знаки препинания, обратный переход с цифр и знаков препинания на буквы, возврат каретки печатающего устройства, переход на новую строку и холостой ход). Например, буква «А» выражается комбинацией «+ + – – -», букве «N» соответствует «– – + + -», а переход на цифры и знаки препинания задается через «+ + – + +». Закодированное сообщение набивается на перфоленте: «плюсы» представляются отверстиями, а «минусы» – их отсутствием. При считывании перфоленты металлические щупы проходят через отверстия, замыкают электрическую цепь и посылают импульсы тока по проводам. А там, где на перфоленте находится «минус», бумага не позволяет этим щупам замкнуть цепь, и в результате токовый импульс не передается.
Вернам предложил готовить перфоленту со случайными знаками (так называемую «гамму») заранее и затем электромеханически складывать ее импульсы с импульсами знаков открытого текста. Полученная сумма представляла собой шифртекст, предназначенный для передачи по линии связи. Вернам установил следующее правило суммирования: если сразу оба импульса являются «плюсами» или «минусами», то итоговый импульс будет «минусом», а если эти импульсы различны, то в результате получится «плюс».
Чтобы при шифровании суммировать импульсы электрически, Вернам сконструировал специальное устройство, состоящее из магнитов, реле и токосъемных пластин. А поскольку процедура расшифрования была совершенно аналогична процедуре зашифрования, это же самое устройство могло быть использовано и при расшифровании. Импульсы поступали в устройство суммирования с двух считывателей: один считывал «гамму», а другой – открытый текст. Получающиеся на выходе «плюсы» и «минусы» можно было передавать подобно обычному телетайпному сообщению. На приемном конце устройство, изобретенное Вернамом, прибавляло импульсы, которые считывались с идентичной ленты с «гаммой», и восстанавливало исходные импульсы открытого текста.
Вся прелесть изобретения Вернама заключалась в том, что больше не требовалось осуществлять зашифрование и расшифрование секретных сообщений в виде отдельных операций. Открытый текст входил в аппарат, находившийся у отправителя сообщения, и точно такой же открытый текст выходил из аппарата, принадлежавшего получателю этого сообщения. А если кто-либо перехватывал это сообщение по пути следования от отправителя к получателю, то в его распоряжении оказывалась ничего не значащая последовательность «плюсов» и «минусов». Теперь, чтобы зашифровать, передать, принять и расшифровать сообщение, требовалось приложить не намного больше усилий, чем при отправке сообщения открытым текстом. Основное преимущество изобретенного Вернамом метода засекречивания сообщений заключалось не в механическом шифровании открытого текста с последующей печатью результата на бумаге, что было осуществлено еще в начале 70-х годов XIX века французами Эмилем Винеем и Жозефом Госсеном. Вернам сумел слить воедино два процесса – шифрование и передачу сообщения. Он создал то, что впоследствии назвали линейным шифрованием, чтобы отличать его от ставшего традиционным предварительного шифрования. Вернам освободил процесс шифрования от оков времени и ошибок, исключив из этого процесса человека. Выдающийся вклад, внесенный Вернамом в практику шифрования, заключается именно в том, что он привнес в шифровальное дело автоматизацию, уже успевшую к тому времени сослужить людям огромную службу во многих областях их деятельности.
Вокруг идеи, высказанной Вернамом в кругу коллег, моментально развернулась кипучая деятельность. Сначала Вернама заставили изложить эту идею в краткой записке, датированной 17 декабря. Компания «AT&T» уведомила об изобретении Вернама американское военно-морское ведомство, с которым она поддерживала тесное сотрудничество. 18 февраля 1918 г. состоялось совещание, в котором приняли участие Паркер, Вернам и другие инженеры из телеграфного отделения компании «AT&T», с одной стороны, и военные моряки, с другой.
27 марта эти же инженеры встретились со своими коллегами из американской компании «Вестерн электрик», производственного филиала «AT&T», и договорились с ними об изготовлении первых двух линейных шифраторов с использованием как можно большего количества стандартных деталей. В лаборатории «Вестерн электрик» они подсоединили изготовленные шифраторы к телетайпам и осуществили первые испытания процесса, который назвали «автоматическим шифрованием». Все устройства, вовлеченные в него, работали превосходно. Компания «AT&T» проинформировала об этом факте майора Джозефа Моборна, который занимал тогда пост начальника отдела научно-исследовательских и конструкторских разработок войск связи США.
Нерешенным оставался всего один вопрос – откуда брать «гамму». В первые дни «гамма» для устройства Вернама представляла собой склеенные петлей короткие перфоленты, на которые были набиты знаки, извлеченные наугад из различных открытых текстов. Инженеры компании «AT&T» почти сразу обратили внимание на существенные изъяны такого процесса «автоматического шифрования», связанные с недостаточной длиной «гаммы». Поэтому, чтобы затруднить криптоанализ, они сделали перфоленты с «гаммой» более длинными. Но тогда с этими перфолентами стало слишком трудно обращаться.
Вернам предложил суммировать две короткие, имеющие различную длину «гаммы» таким образом, как будто бы одна «гамма» шифровала другую. Получающаяся в результате так называемая вторичная «гамма», имевшая значительно большую длину, чем две исходные, первичные «гаммы», которые были использованы для ее генерации, применялась для зашифрования открытого текста. Например, если одна закольцованная лента имела 1000 знаков, а другая 999, то данное различие в длинах всего в один знак давало 999000 комбинаций, прежде чем результирующая последовательность повторялась.
Однако Моборн понимал, что даже усовершенствованная система Вернама весьма уязвима для криптоанализа. В свои 36 лет будущий начальник войск связи США Моборн был незаурядным криптоаналитиком. Он основательно изучил криптоанализ в армейской школе связи и был хорошо знаком с последними достижениями в этой области. Более того, за несколько лет до описываемых событий Моборн сам принимал участие в одной научно-исследовательской работе, в ходе которой специалисты из армейской школы связи сделали вывод о том, что единственной стойкой «гаммой» является такая, которая сравнима по длине с самим шифруемым сообщением. Любое повторение в «гамме» подвергает огромному риску полученные с ее помощью криптограммы и, скорее всего, приведет к их вскрытию. Проведенный Моборном анализ системы «автоматического шифрования» еще более убедил его в этом. Он понял, что не имеет никакого значения, находятся ли повторения в пределах одной криптограммы или они распределены по нескольким, получаются ли они путем комбинирования двух первичных «гамм» или в результате простого повторения в единой длинной «гамме». Важно то, что в «гамме» повторений не должно быть ни при каких условиях. Необходимо, чтобы она была совершенно уникальна и предельно хаотична.
Осознав это, Моборн объединил свойство хаотичности «гаммы», на которое опирался Вернам в своей системе «автоматического шифрования», со свойством уникальности «гаммы», выработанным криптографами армейской школы связи, в системе шифрования, которую ныне принято называть «одноразовым шифрблокнотом». Одноразовый шифрблокнот содержит случайную «гамму», которая используется один, и только один раз. При этом для каждого знака открытого текста, принадлежащего всей совокупности сообщений, которые уже были посланы данной группой шифркорреспондентов или еще только будут посланы ею в обозримом будущем, предусматривается использование абсолютно нового и не поддающегося предсказанию знака «гаммы».
Это абсолютно стойкая шифрсистема. Подавляющее большинство систем шифрования являются абсолютно стойкими лишь на практике, поскольку криптоаналитик может найти пути их вскрытия при наличии у него определенного количества шифртекста и достаточного времени для его исследования. Одноразовый же шифрблокнот является абсолютно стойким как в теории, так и на практике. Каким бы длинным ни был перехваченный шифртекст, сколько бы много времени ни отводилось на его исследование, криптоаналитик никогда не сможет вскрыть одноразовый шифрблокнот, использованный для получения этого шифртекста. И вот почему.
Вскрытие многоалфавитного шифра означает объединение всех букв, зашифрованных при помощи одного шифралфавита, в единую группу, которую можно изучать на предмет выявления ее лингвистических особенностей. Методы такого объединения могут быть различны в зависимости от вида «гаммы». Так, метод Казиского заключается в выделении идентично гаммированных букв открытого текста при повторяющейся «гамме». Связная «гамма» может быть вскрыта путем взаимного восстановления открытого текста и «гаммы». А «гамма», использованная для зашифрования двух или более сообщений, поддается вскрытию путем одновременного восстановления открытых текстов этих сообщений, причем правильность прочтения одного текста контролируется читаемостью другого. Почти для всех разновидностей многоалфавитиых шифров разработан свой метод вскрытия, который основан на их отличительных особенностях.
Совершенно иначе обстоит дело с одноразовым шифрблокногом. В этом случае криптоаналитик не имеет отправной точки для своих исследований, так как в одноразовой шифрсистеме «гамма» не содержит повторений, не используется более одного раза, не является связным текстом и не имеет внутренних структурных закономерностей. Поэтому все методы дешифрования, в той или иной мере основанные на этих характеристиках, не дают никаких результатов. Криптоаналитик заходит в тупик.
А как обстоит дело с методом тотального опробования? Ведь прямой перебор всех возможных ключей в конечном счете обязательно приведет криптоаналитика к открытому тексту. Однако успех, приобретенный этим путем, иллюзорен. Тотальное опробование действительно позволяет получить исходный открытый текст. Но оно также даст и каждый другой возможный текст той же длины, и сказать, какой из них является истинным, будет невозможно.
Предположим, что криптоаналитик пытается дешифровать четырехбуквенное военное сообщение, применяя все «гаммы», начиная с «АААА». Используя «AABI» в качестве «гаммы», он получает открытый текст «kiss»56. Неподходящий вариант для данного контекста. Криптоаналитик не останавливается на достигнутом. С помощью «AAEL» получается открытый текст «kill»57. Уже лучше, но хочется удостовериться, нет ли чего более подходящего. Исследование продолжается, и при «гамме» «ААЕМ» выходит слово «kilt»58. «AAER» дает «kiln»59, «GZBM» – «fast»60, «KHIA» – «slow»61, «HRIW» – «stop»62, «PZVQ» – «hard»63 и «RZBU» – «easy»64. Когда криптоаналитик доберется, наконец, до «гаммы» «ZZZZ», он обнаружит, что просто составил перечень всевозможных английских слов из четырех букв.
У криптоаналитика остается последняя надежда. Предположим, что он получил н свое распоряжение открытый текст какой-то отдельной криптограммы (например, в результате ошибки связиста). В состоянии ли криптоаналитик использовать «гамму», которую он сможет теперь вычислить, имея на руках открытый и соответствующий ему шифрованный тексты, для определения алгоритма, с помощью которого была выработана эта «гамма», чтобы потом предугадать все будущие «гаммы»? Нет, не в состоянии. Ведь если «гамма» действительно случайна, это значит, что она не подчиняемся никаким видимым закономерностям.
Правильный ответ опять ускользает от криптоаналитика. Одноразовая случайная «гамма» полностью подавляет его, растворяя все усилия криптоаналитика в хаосе, с одной стороны, и в бесконечности, с другой. Здесь он сталкивается с пропастью, непреодолимой для человека.
Почему же горда этот самый совершенный шифр не нашел всеобщего применения? Ответ прост, из-за огромного количества «гаммы», которая требуется при его использовании. Проблемы, возникающие при изготовлении, рассылке и уничтожении «гаммы», человеку непосвященному во все тонкости организации шифрсвязи могут показаться пустячными, однако в военное время объемы переписки зачастую удивляют даже самых бывалых связистов. В течение суток может понадобиться зашифровать сотни тысяч слов, а для этого требуется изготовить миллионы знаков «гаммы». И поскольку «гамма» для каждого сообщения должна быть единственной и неповторимой, то ее общий объем будет эквивалентен объему всей переписки за время воины.
В общем, практические проблемы не позволяют применять одноразовые шифрблокноты в быстро меняющихся ситуациях, например в ходе проведения военных операций. Этих проблем не существует в более стабильных условиях: в высших военных штабах, дипломатических представительствах или в агентурной переписке одноразовые шифрблокноты достаточно практичны и находят повсеместное применение. Однако и здесь возникают непреодолимые трудности, если объем переписки слишком велик.
Это как раз и произошло, когда Моборн, устроив первое крупное испытание шифрсистемы Вернама, установил его машины сразу в трех городах. Даже при сравнительно небольшом объеме переписки (до 135 коротких сообщений в день) оказалось невозможным изготовить достаточное количество качественной «гаммы». Поэтому, не найдя другого выхода из затруднительного положения, Моборн стал комбинировать две относительно короткие «гаммы», чтобы получать из них более длинную «гамму», как это первоначально предлагал делать сам Вернам.
В сентябре 1918 г. Вернам отправился в Вашингтон и подал там заявку на патент. Первая мировая война успела закончиться прежде, чем шифрсистема Вернама сумела хоть как-то проявить свои достоинства на практике. Тем не менее 22 июля 1919 г. на нее был выдан патент № 1310719, являющийся, по-видимому, самым важным в истории криптографии. Эксперты из вашингтонского патентного бюро признали возможную полезность этого изобретения и в мирное время.
Однако, хотя устройство, придуманное Вернамом, несомненно являлось ценным плодом творческой инженерной мысли талантливого изобретателя, в коммерческом плане оно потерпело полный провал. Телеграфные компании и коммерческие фирмы, которые, по мнению «AT&T», должны были в массовых количествах покупать запатентованные шифрприставки Вернама к своим телетайпам, отдавали предпочтение старомодным кодам, которые существенно снижали длину сообщений, тем самым уменьшая телеграфные расходы и одновременно обеспечивая хоть какую-то, пусть небольшую, безопасность переписки. После окончания Первой мировой войны бюджеты вооруженных сил всех стран были сокращены до минимума. Недостаток средств и нехватка материальных ресурсов вынудили армейских связистов снова вернуться к комбинированию двух относительно коротких лент с «гаммой», а продемонстрированная военными криптоаналитиками слабая стойкость такой системы генерации «гаммы» привела к тому, что шифрсистема Вернама на некоторое время была предана забвению.
Что же касается самого Вернама, то он продолжал заниматься научно-исследовательской работой в компании «AT&T». Он немного усовершенствовал свою шифрсистему, а также изобрел устройство для автоматического зашифрования написанного от руки текста во время его передачи фототелеграфом. В 1929 г. Вернама со значительным повышением перевели в один из филиалов компании «AT&T». Однако через четыре месяца в США разразился финансовый кризис, и, так как Вернам еще не успел заработать достаточный трудовой стаж на новом месте, его вскоре уволили. Он перешел на работу в другую крупную компанию, но резкая перемена в его личной судьбе, видимо, подействовала на него угнетающе. С каждым годом о Вернаме было слышно все меньше и меньше, пока, наконец, 7 февраля 1960 г. человек, автоматизировавший процесс шифрования, умер в полной безвестности у себя дома.
История науки изобилует совпадениями. Например английский астроном Джон Адамс и его французский коллега Урбен Леверье почти одновременно сделали вывод о существовании планеты Нептун. Неудивительно, что подобные совпадения имели место и в криптографии. Случилось так, что в период между двумя мировыми войнами одно из таких совпадений затронуло сразу несколько человек. Как и Вернам, побуждаемые широким использованием секретной связи в военное время и вдохновляемые наступлением эпохи механизации, они независимо друг от друга изобрели машину, принцип действия которой на протяжении очень продолжительного времени находил наиболее широкое применение в криптографии. Этот принцип основывается на использовании колеса с перепайками – так называемого шифрдиска.
Шифрдиск представляет собой толстую круглую пластину, изготовленную из изоляционного материала (например, из твердой резины). С обеих сторон шифрдиска по окружности на равном расстоянии друг от друга закреплены по 26 электрических контактов (чаще всего они делались из латуни). Каждый контакт соединяется перепайкой с каким-либо другим контактом на противоположной поверхности шифрдиска. Таким образом, образуется электрическая цепь, которая начинается на одной стороне шифрдиска и заканчивается на другой.
Если условиться, что контакты на одной (входной) поверхности представляют буквы открытого текста, а контакты на другой (выходной) поверхности – буквы шифртекста, то проволочные перепайки между входной и выходной поверхностью обеспечивают преобразование открытого текста в криптограмму. Для зашифрования буквы открытого текста нужно только подать импульс тока на входной контакт, соответствующий этой букве. Ток пройдет по соединительному проводнику и появится на выходном контакте, представляющем букву шифртекста. Если записать все перепайки диска, зафиксировав соединения между входной и выходной поверхностью, то получится шифр одноалфавитной замены. Таким образом, шифрдиск воплощает процесс шифрования в форме, удобной для электромеханических манипуляций.
Для выполнения этих манипуляций шифрдиск устанавливается между двумя неподвижными круглыми пластинами, каждая из которых также изготовлена из изоляционного материала и снабжена 26 контактами, которые закреплены по кругу и соответствуют контактам, имеющимся на шифрдиске. Контакты входной пластины соединены с клавишами пишущей машинки, на которой набивается открытый текст. А каждый контакт выходной пластины связан с каким-либо устройством, предназначенным для вывода шифртекста (например, с сигнальной лампочкой). В результате, например, когда шифровальщик нажимает на клавишу «А» на пишущей машинке, он посылает токовый импульс от источника тока на контакт неподвижной входной пластины, закрепленный за буквой «А». Затем этот импульс попадает на входной контакт шифрдиска, соответствующий «А», и далее через перепайку проходит на выходной контакт, а с него – на лампочку, которая загорается над буквой шифртекста (пусть это будет буква «R»), которая ставится в соответствие букве «А».
Если бы все на этом и заканчивалось, то шифрдиск не был бы таким замечательным устройством. Тогда каждый раз при нажатии на клавишу «А» ток протекал бы по одной и той же электрической цепи и в итоге указывал бы на одну и ту же букву шифртекста.
Но все дело в том, что шифрдиск не остается неподвижным. Он вращается. Предположим, что он повернулся на одну позицию. Ток, который раньше, покидая контакт «А» входной пластины, попадал на контакт «R» выходной пластины, теперь преобразуется в совершенно другую букву, так как новый контакт шифрдиска с перепайкой, отличной от прежней, теперь встал против контакта «А» входной пластины. Подобным же образом всем другим буквам открытого текста ставятся в соответствие иные буквы шифртекста. Получается новый шифралфавит, причем каждый раз, когда шифрдиск поворачивается, используется другой шифралфавит. Можно выписать все эти шифралфавиты в виде таблицы из 26 строк и такого же количества столбцов. Если шифровальная машина сконструирована так, что шифрдиск поворачивается ровно на одну позицию каждый раз, когда зашифровывается какая-либо буква открытого текста, то итоговый результат будет таким же, как и при циклическом использовании этой таблицы строка за строкой сверху вниз. Получится не что иное, как шифр многоалфавитной замены с периодом 26.