Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Предположим, что наиболее вероятный кандидат — число 5, потому что это общий делитель, который встречается чаще всего. Теперь мы попытаемся догадаться, каким буквам соответствует каждая из пяти букв ключевого слова. Как мы помним, каждая буква ключевого слова в квадрате Виженера определяет моноалфавитный шифр для соответствующей буквы в исходном сообщении. В случае нашего гипотетического ключевого слова из пяти букв (C1, С2, СЗ, С4, С5) шестая буква (С6) шифруется тем же алфавитом, что и первая буква (С1), седьмая (С7) — тем же, что и вторая (С2), и так далее. Поэтому на самом деле криптоаналитик имеет дело с пятью отдельными моноалфавитными шифрами, каждый из которых уязвим для традиционного криптоанализа.
Процесс завершается составлением таблицы частот для всех букв в зашифрованном тексте, соответствующих буквам
Если таблицы не совпадают, процесс повторяется с другой вероятной длиной ключевого слова. Как только мы определим ключевое слово, останется только расшифровать исходное сообщение. С помощью этого метода и был взломан полиалфавитный шифр.
Поразительные работы Бэббиджа, завершенные около 1854 г., так бы и остались в безвестности. Эксцентричный британский интеллектуал не опубликовал свое открытие, и только недавние исследования его записок показали, что именно он был пионером в расшифровке полиалфавитных ключевых слов. К счастью для криптоаналитиков всего мира, несколько лет спустя, в 1863 г., прусский офицер Фридрих Касиски опубликовал аналогичный метод.
Независимо оттого, кто первый взломал его, полиалфавитный шифр перестал быть неприступным. С этого момента сила шифра стала зависеть не столько от алгоритмических нововведений шифрования, сколько от количества используемых шифроалфавитов, которое должно быть достаточно большим, чтобы сделать частотный анализ и его варианты совершенно бесполезными. Параллельной целью был поиск способов ускорения криптоанализа. Обе цели пересеклись в одной точке и породили один и тот же процесс: компьютеризацию.
Рабочая часть разностной машины Бэббиджа, построенной в 1991 г. в соответствии с чертежами, оставленными ее изобретателем. Устройство позволяет находить приближенные значения логарифмических и тригонометрических функций и, следовательно, делать расчеты астрономических таблиц. Бэббидж не успел при жизни увидеть свою машину.
Глава 3. Шифровальные машины
В XIX в. шифрование оказалось полезным не только для пересылки секретных сообщений. Появление телеграфа в первой трети века и затем, спустя 30 лет, развитие двусторонней телеграфной связи Томасом Альвой Эдисоном произвело революцию в коммуникации и, следовательно, изменило мир. Так как телеграф использовал электрические импульсы, нужен был метод для перевода текста сообщения на язык, который машина может воспроизвести и передать. Другими словами, необходимо было кодирование. Среди различных предложенных методов верх взяла система передачи букв точками и тире, придуманная американским художником и изобретателем Сэмюэлом Морзе. Азбуку Морзе можно считать предшественником кодов, которые многие десятилетия спустя неявно используются всеми нами для ввода данных в компьютеры и получения информации от них.
Азбука Морзе использует комбинацию точек, тире и пробелов для представления букв алфавита, цифр и других символов. Таким образом, она переводит алфавит в набор знаков, которые могут быть выражены с помощью простых сигналов света, звука или электричества. Каждая точка соответствует единице времени продолжительностью около 1/25 доли секунды; каждое тире — три единицы времени (эквивалентно трем точкам). Длина пробелов между буквами — также три единицы времени, а пять единиц соответствуют пробелам между словами.
Сначала Морзе было отказано в патенте на этот код и в Соединенных Штатах, и в Европе. Лишь в 1843 г. он получил государственную субсидию для строительства телеграфной линии между Вашингтоном и Балтимором. В 1844 г. была произведена первая передача закодированного сообщения, и почти сразу была создана компания с целью охвата всей Северной Америки телеграфными
линиями. К 1860 г., когда Наполеон III наградил Морзе орденом Почетного легиона, Соединенные Штаты и Европа уже были опутаны телеграфными проводами. К моменту смерти Морзе в 1872 г. в Америке было проложено более 300000 километров кабеля.Сначала простое устройство, изобретенное в 1844 г. самим Морзе, использовалось для передачи и приема телеграфных сообщений. Оно состояло из телеграфного ключа, который служил для включения и отключения электрического тока, а также электромагнита, который получал поступающие сигналы. Каждый раз, когда нажимался ключ, — как правило, указательным или средним пальцем — возникал электрический контакт. Периодические импульсы, производимые нажатием телеграфного ключа, передавались по кабелю, состоящему из двух медных проводов.
Эти провода, поддерживаемые высокими деревянными «телеграфными» столбами, связывали различные телеграфные станции страны и часто тянулись на сотни километров.
* * *
НЕВЕРБАЛЬНАЯ КОММУНИКАЦИЯ
Так как Томас Альва Эдисон (1847–1931) плохо слышал, он общался со своей женой, Мэри Стиуэлл, с помощью азбуки Морзе. Во время ухаживания Эдисон сделал предложение, отстучав слова рукой, и она ответила тем же способом. Телеграфный код стал обычным средством общения для супругов. Даже когда они ходили в театр, Эдисон клал руку Мэри себе на колено, чтобы она могла «телеграфировать» ему диалоги актеров.
Первый телеграфный аппарат, изобретенный Сэмюэлом Морзе в 1844 г.
* * *
СИМФОНИЯ V-МАЖОР
Бетховен — еще один плохослышащий знаменитый человек, имя которого связано с телеграфом, хотя в данном случае лишь косвенно: первые четыре ноты Пятой Симфонии гениального композитора по ритму напоминают сообщение в азбуке Морзе: «точка точка точка тире».
В азбуке Морзе «точка точка точка тире» соответствуют букве V, первой букве английского слова «victory» («победа»). Поэтому на «Би-би-си» Пятая симфония Бетховена использовалась как позывные радиостанции перед началом всех трансляций для оккупированной Европы во время Второй мировой войны.
* * *
В приемном устройстве имелся электромагнит, представлявший собой катушку из медной проволоки, обмотанной вокруг железного сердечника. Когда катушка получала импульсы электрического тока, соответствующие точкам и тире, железный сердечник намагничивался и притягивал подвижную часть, также сделанную из железа. Она издавала характерный звук при ударе о магнит. Этот звук слышен как короткий «щелчок», если получена точка, и как более длительная нота — при получении тире. Первое время для отправки телеграммы с помощью такого устройства требовался человек-оператор, который настукивал кодированную версию сообщения на одном конце, и еще один человек получал и расшифровывал текст на другом конце.
Кодирование символов по азбуке Морзе производилось в соответствии со следующей таблицей:
Так, сообщение: «I love you» («Я тебя люблю») будет закодировано следующим образом:
Как уже говорилось ранее, азбука Морзе была в некотором смысле первым вариантом будущих цифровых систем связи. Чтобы продемонстрировать эту идею, мы легко можем преобразовать код Морзе в числа, заменяя каждую точку единицей, а каждое тире — нулем. Строки из нулей и единиц часто будут встречаться нам в следующих главах.