Из истории криптографии США
Еще в конце XVIII века криптография обогатилась замечательным изобретением — шифратором Джефферсона, названным в честь государственного деятеля, первого государственного секретаря, а затем и президента Америки Томаса Джефферсона. Сам Джефферсон назвал свою систему «дисковым шифром». Реализовывало такое устройство известный шифр многоалфавитной замены.
Шифратор представлял собой деревянный цилиндр, который разрезался на 36 дисков (хотя количество дисков могло быть и другим), которые насаживались на одну ось так, чтобы независимо поворачиваться вокруг нее. На боковых поверхностях дисков в вольном порядке — все буквы английского алфавита.
Параллельно оси диска на поверхности цилиндра выделялась линия. Открытый текст разбивался на группы по 36 знаков, первая буква группы фиксировалась положением первого диска по выделенной линии, вторая — второго диска и т. д. Шифр-текст считывался с любой линии, параллельной выделенной. Для расшифровки, на аналогичном устройстве полученный шифрованный текст выписывался путем поворота дисков по выделенной линии, а открытый текст отыскивался среди параллельных ей линий путем осмысленного прочтения возможных вариантов.
Реплика дискового шифратора Джефферсона из пластика. Она имеет только 10 дисков, а не 36, но достаточно хорошо подходит для демонстрации работы данного шифратора:
Изобретение Джефферсона было предвестником появления дисковых шифраторов, которые использовались в развитых странах в ХХ веке. Как ни странно, при жизни самого создателя судьба данного устройства сложилась неудачно. Сам Джнфферсон с осторожностью относился к шифратору и продолжал использовать номенклаторы.
Для периода примерно с 16 по 19 вв. типичным был т. н. номенклатор – шифр, представлявший собой сочетание шифра замены и небольшого кода. Номенклатор обычно содержал кодовые эквиваленты букв алфавита и наиболее употребительных слогов, слов и словосочетаний, а также ряд специальных символов. Чаще всего в нем встречались специально созданные для этой цели символы, но нередко также использовалась астрологическая и оккультная символика.Номенклатор был разработан как система шифрования, наилучшим образом приспособленная к наиболее употребительным в то время методам криптоанализа, которые, как правило, включали подсчет частоты появления в тексте каждого шифрового символа и поиск в тексте слов и выражений, содержащих характерные для данного языка сочетания букв. Метод частотного анализа букв основан на том, что в любом языке одни буквы встречаются чаще, чем другие. В английском языке, например, чаще других встречается буква Е. Другие наиболее часто встречающиеся буквы – T, A, O, N, R и S. (Целиком эту группу букв легко запомнить в виде слова «SENORITA».) А буквы J, K, X и Z встречаются в английском редко. Поскольку в ходе операции замены частота буквы не меняется, ключ к разгадке истинного значения того или иного шифросимвола заключается иногда в подсчете частоты его появления в шифротексте. Равным образом операция простой замены не вносит изменений и в сочетания букв (буквенные модели). Например, слово ATTACK, будучи зашифрованным, может принять вид XJJXBU. Несмотря на то, что значения букв при этом изменились, буквенная модель слова (а именно две одинаковых буквы, обрамленные слева и справа одной и той же буквой, после чего следуют две другие различные буквы) осталась неизменной.
Номенклатором у древних римлян еще называли раба, в обязанности которого входило знать и называть своему господину имена граждан города и всех рабов в доме, а также провозглашать названия подаваемых кушаний. Но сейчас не об этом. «Номенклаторы» были стандартом для дипломатической корреспонденции, шпионских сообщений и являлись основным средством антиполитической конспирации с начала пятнадцатого столетия до конца восемнадцатого столетия.
Джефферсон очень осторожно относился к своему изобретению и по поводу него советовался с математиком Р. Паттерсоном. В результате такого обмена информации, Паттерсон предложил свой собственный шифр, по его словам более надежный, такой шифр представлял собой вертикальную перестановку с введением «пустышек», хотя по стойкости значительно уступал шифру Джефферсона.
В паттерсоновском шифре сообщение надо писать сверху вниз и слева направо. Затем следует разбить его на несколько секций размером не более девяти строк. Строки в каждой секции нумеруются и перемешиваются в произвольном порядке. Порядок строк в секции даст первую половину ключа, например: 5-1-3-2-4-7-6-8 для секции из восьми строк.
Затем в начало каждой строки можно вставить от 0 до 9 случайных букв. Получившаяся последовательность дает вторую половину ключа, например, 1-7-9-3-3-2-1-7 (в первую строку вставили 1 букву, во вторую 7 букв и так далее). У сообщения получится рваный правый край — в конец можно добавить еще немного бессмысленных букв, чтобы выровнять его.
Сам ключ записывается как двузначное число, где десятки — цифра из первой половины, а единицы — число добавленных в начало бессмысленных букв. Дешифровщику достаточно отнять от каждой строчки по указанному количеству букв и переставить их в нужном порядке (во времена Паттерсона надо было вооружиться ножницами и переклеить вырезанные строки на лист бумаги). Сообщение дешифровано, его снова можно прочесть сверху вниз, а бессмыслицу у правого края просто игнорировать.
Лишь в XX веке была признана высокая стойкость шифра Джефферсона, позднее использовался для зашифровки посланий американской армией во время Второй мировой войны, а самого изобретателя назвали отцом «американского шифровального дела».
За всю историю было несколько попыток заново «изобрести давно забытое колесо» Джефферсона. В начале XX века Паркер Хитт (опять таки США) облачил шифр Джефферсона в «полосковый шифр», значительно более простой в изготовлении. Полоски с удвоенным алфавитом, закреплялись в рамку, что было более технологично, чем деревянные диски с алфавитом. Смысл шифрования и расшифрования остался тем же, однако сложные диски были заменены на легко воспроизводимые «полоски» из твердого материала (например, картона, металла). Значимость этого изобретения — не в появлении новых криптографических идей, а в технологической простоте их воплощения. В конце 1937 года японцы осуществили секретную выемку в здании американского консульства в Кобе (Япония) и перефотографировали американский посольский
полосковый шифр. Однако эффективно воспользоваться этой добычей они не смогли, поскольку стойкость шифра определялась ключевой системой, в которую кроме «полосок» входили еще их выбор и расположение на планшете. Полоски были сменными, их было до сотни, а выбор тридцати действующих полосок задавался таблицей ключей.
Позднее, в 20 годах прошлого столетия, шифр Джефферсона был «изобретен» еще в очередной раз. После этого криптоаналитики пришли к выводу, что не смотря на свою простоту, этот шифр достаточно стойкий. Как следствие, армия США приняла его на вооружение и, как считается, применение данного шифра повлеко за собой появление первых сложных электромеханических устройств.
Метод длинной ленты
Ранним декабрьским утром 1917 г. симпатичный молодой человек стремительно промчался между массивными колоннами вестибюля здания компании «Америкэн телефон энд телеграф» («AT&T»), расположенного в деловой части Нью-Йорка. Он вбежал в лифт и поднялся на нем на 17-й этаж, где находилось телеграфное отделение компании, входившее в состав ее научно-исследовательского отдела. Это отделение, в котором работали несколько самых талантливых инженеров, уже год занималось доведением до ума новейшего достижения в области телеграфии – буквопечатающего телеграфного аппарата, который в отделении нарекли телетайпом.
Молодого человека звали Гильберт Вернам, и он всегда немного опаздывал. Коллеги считали Вернама весьма толковым инженером и способным изобретателем. Среди них ходили слухи о том, что каждый вечер, растягиваясь на диване, он спрашивал сам себя вслух: «Что бы такое еще изобрести?» У Вернама был редкий склад ума, который позволял ему придумывать оригинальную электрическую цепь и затем переносить ее на чертежный холст, не воспроизводя все требуемые соединения с помощью проводов.В его голове уже успела созреть прекрасная идея. Вернам довольно несмело изложил свою идею коллегам, которые сразу же сочли ее заслуживающей особого внимания.
Работа над секретным проектом началась еще летом, несколько месяцев спустя после того, как Соединенные Штаты объявили войну Германии. Паркер поручил нескольким своим подчиненным исследовать вопрос о возможности сохранять в тайне сообщения, передаваемые по телетайпу.
Оказалось, что колебания тока в линии связи могли быть записаны с помощью осциллографа и затем легко преобразованы в буквы передаваемого сообщения. Поэтому было решено внести изменения в соединения проводов печатающего механизма телетайпа. В результате текст сообщения шифровался методом одноалфавитной замены. В телеграфном отделении понимали, что такая защита являлась слишком слабой, однако ничего другого придумать не смогли и перестали заниматься этой проблемой до тех самых пор, пока Вернам не поведал им о своей идее.
Вернам работал в телеграфном ведомстве и назвал свой шифр «методом длинной ленты для телетайпов». Суть шифра Вернама проста: телеграфное сообщение, представленное в виде битового потока, складывалось по модулю с лентой, на которую был занесен случайный поток бит неограниченной длительности. То есть шифр гаммирования был перенесен на электрическую почву. К шифру было всего два требования, гамма должна была быть случайной и лента с гаммой могла быть использована всего лишь один раз ( от сюда название ОТР – One Time-Pad, OTK – One-Time-Key; OTT – One-Time-Tape). Для шифрования заранее готовилась гамма — перфолента со случайными знаками, после чего электромеханически складывались ее импульсы с импульсами знаков открытого текста. Полученная сумма представляла собой шифртекст. На приемном конце импульсы, полученные по каналу связи, складывались с импульсами той же самой двоичной гаммы, в результате чего восстанавливались исходные импульсы сообщения.
Вернам предложил использовать особенности телетайпного кода, в котором кодируемый знак выражался в виде пяти элементов. Каждый из этих элементов символизировал наличие («плюс») или отсутствие («минус») электрического тока в линии связи. Таким образом, имелось 32 различных комбинации «плюсов» и «минусов». 26 из них ставились в соответствие буквам, а оставшиеся 6 обозначали «служебные комбинации» (пробел между словами, переход с букв на цифры и знаки препинания, обратный переход с цифр и знаков препинания на буквы, возврат каретки печатающего устройства, переход на новую строку и холостой ход). Например, буква «А» выражалась комбинацией "+ + – – -", букве «N» соответствовало "– – + + -", а переход на цифры и знаки препинания задавался через "+ + – + +". Закодированное сообщение набивалось на перфоленте: «плюсы» представлялись отверстиями, а «минусы» – их отсутствием. При считывании перфоленты металлические щупы проходили через отверстия, замыкали электрическую цепь и посылали импульсы тока по проводам. А там, где на перфоленте находился «минус», бумага не позволяла этим щупам замкнуть цепь, и в результате токовый импульс не передавался.
Вернам сконструировал специальное устройство, состоящее из магнитов, реле и токосъемных пластин для того, чтобы при шифровании электрически суммировать импульсы. Поскольку процедура расшифрования была совершенно аналогична процедуре зашифрования, это же самое устройство использовалось и при расшифровке. Импульсы поступали в устройство суммирования с двух считывателей: один считывал «гамму», а другой – открытый текст. Получающиеся на выходе «плюсы» и «минусы» можно было передавать подобно обычному телетайпному сообщению. На приемном конце устройство, изобретенное Вернамом, прибавляло импульсы, которые считывались с идентичной ленты с «гаммой», и восстанавливало исходные импульсы открытого текста.
Одноленточная электромеханическая шифрмашина создана в США приблизительно в 1933 году Western Union Telegraph Company. Было выпущено ограниченное количество таких машин, в основе был шифр Вернама.
Даже если сообщение перехватывалось, без гаммы расшифровать его было невозможно, ведь противник видел только случайную последовательность, которая ничего для него не означала. Информация, которая была доступна противнику, лишь длина сообщения. В первоначальном виде система Вернама была уязвима, поскольку ключевая перфолента изготавливалась в форме кольца и использовалась снова после ее окончания. Вернам сумел слить воедино два процесса – шифрование и передачу сообщения. Он создал то, что впоследствии назвали линейным шифрованием.
Только после Первой мировой войны Вернам получил патент на свое изобретение, которое вскоре настигла, на некоторое время, участь дискового шифратора Джефферсона.
Однако, хотя устройство, придуманное Вернамом, несомненно являлось ценным плодом творческой инженерной мысли талантливого изобретателя, в коммерческом плане оно потерпело полный провал. Телеграфные компании и коммерческие фирмы, которые, по мнению «AT&T», должны были в массовых количествах покупать запатентованные шифрприставки Вернама к своим телетайпам, отдавали предпочтение старомодным кодам, которые существенно снижали длину сообщений, тем самым уменьшая телеграфные расходы и одновременно обеспечивая хоть какую-то, пусть небольшую, безопасность переписки. После окончания Первой мировой войны бюджеты вооруженных сил всех стран были сокращены до минимума. Недостаток средств и нехватка материальных ресурсов вынудили армейских связистов снова вернуться к комбинированию двух относительно коротких лент с «гаммой», а продемонстрированная военными криптоаналитиками слабая стойкость такой системы генерации «гаммы» привела к тому, что шифрсистема Вернама на некоторое время была предана забвению.
Что же касается самого Вернама, то он продолжал заниматься научно-исследовательской работой в компании «AT&T». Он немного усовершенствовал свою шифрсистему, а также изобрел устройство для автоматического зашифрования написанного от руки текста во время его передачи фототелеграфом. В 1929 г. Вернама со значительным повышением перевели в один из филиалов компании «AT&T». Однако через четыре месяца в США разразился финансовый кризис, и, так как Вернам еще не успел заработать достаточный трудовой стаж на новом месте, его вскоре уволили. Он перешел на работу в другую крупную компанию, но резкая перемена в его личной судьбе, видимо, подействовала на него угнетающе. С каждым годом о Вернаме было слышно все меньше и меньше, пока, наконец, 7 февраля 1960 г. человек, автоматизировавший процесс шифрования, умер в полной безвестности у себя дома.
Шифр Вернама (One-time pad) на PHP
Вот реализация на php:
<?php
/**
* Шифр Вернама
* реализован на php
*/
function shifrVernam($oStr,$key='')
{
$len = mb_strlen($oStr, 'utf-8'); //размер исходной строки
$shStr = ''; //зашифрованный текст
if($key == '')
for($i = 0; $i < $len; $i++)// определяем ключ случайным образом
$key .= mb_substr(md5(mt_rand(1,mt_getrandmax())),0,1,'utf-8');
for($i = 0; $i < $len; $i++) // шифруем
$shStr .= $oStr[$i]^$key[$i];
echo "<br>Открытый текст: '$oStr'", // смотрим что получилось
"<br>Ключ: '$key'", "<br>Зашифрованый текст: '$shStr'<br>";
return array($key => $shStr);
}
header('Content-type: text/html; charset=utf-8');
// Зашифруем строку для примера
$crypt = shifrVernam("Hello word!"); /*Вывод:
Открытый текст: 'Hello word!'
Ключ: 'c462031ba7e'
Зашифрованый текст: '+QZ^_F SD'
*/
// Результат расшифруем с полученным ключем
foreach($crypt as $key => $shr)
shifrVernam($shr,$key);/*Вывод:
Открытый текст: '+QZ^_F SD'
Ключ: 'c462031ba7e'
Зашифрованый текст: 'Hello word!'
*/Майор Джозеф Моборн был незаурядным криптоаналитиком. Он основательно изучил криптоанализ в армейской школе связи и был хорошо знаком с последними достижениями в этой области. Моборн занялся дальнейшим усовершенствованием метода Вермана. Он обьединил хаотичность гаммы с правилом одноразового шифрблокнота. Теперь было ввдено три ограничения: шифрблокнот реализовался как шифрующая гамма, по длине равная или превышающая шифруемое сообщение; знаки гаммы были полностью случайными или равновероятными; каждая гамма использовалась один и только один раз, после чего уничтожалась передающим или принимающим корреспондентом. Было еще и дополнительное правило: изготавливались только две копии шифрключа, одна копия для передающего, вторая копия для принимающего корреспондента.
Три листа из одноразового шифрблокнота, каждый из которых является возможным ключом для шифра. Сообщение зашифровано с помощью листа 1
Как следствие — абсолютно стойкая шифрсистема, одноразовый шифрблокнот является абсолютно стойким как в теории, так и на практике, каким бы длинным ни был перехваченный шифртекст, сколько бы много времени ни отводилось на его исследование, криптоаналитик никогда не сможет вскрыть одноразовый шифрблокнот, использованный для получения этого шифртекста, он по просту не имеет отправной точки для своих исследований, так как в одноразовой шифрсистеме гамма не содержит повторений, не используется более одного раза, не является связным текстом и не имеет внутренних структурных закономерностей. Поэтому все методы дешифрования, в той или иной мере основанные на этих характеристиках, не дают никаких результатов. И вот — криптоаналитик заходит в тупик.
Совершенный метод шифрования не «заслужил» всеобщего использования из-за огромного количества гаммы, которая требуется при его использовании. В военное время нужно было в течение суток зашифровать сотни тысяч слов, а для этого требовалось бы изготовить миллионы знаков гаммы. И поскольку гамма для каждого сообщения должна была быть единственной и неповторимой, то ее общий объем — эквивалентен объему всей переписки за время воины, что ну просто невозможно в быстро меняющихся военных условиях.
