Американский математик и криптограф Лоурен Смитлайн совершил то, что не смогли сделать до него целые поколения исследователей - он разгадал так называемый шифр Паттерсона. Проще говоря, он первым за двести лет прочитал страничку из письма математика Роберта Паттерсона президенту США Томасу Джефферсону.
"Искусство тайнописи или, как его обычно называют, шифрования, в течение многих веков привлекало внимание как государственных мужей, так и философов; все знакомые с нынешним состоянием этого искусства, как я считаю, признают, что оно по-прежнему далеко от совершенства". Так начинается злополучное письмо, отправленное Джефферсону из Филадельфии 19 декабря 1801 года.
Описывая свой шифр, Паттерсон в лице Томаса Джефферсона обращался не только к президенту США, но и к любителю криптографии и президенту Американского философского общества. Сам Паттерсон был вице-президентом этой уважаемой организации.
Работа Паттерсона удовлетворяла всем четырем им же придуманным критериям идеального шифра - она годилась для любого языка, не требовала подробных инструкций, текст легко записывался и считывался, и, что самое важное, был абсолютно непонятен.
Роберт Паттерсон был уверен, что создал загадку, перед которой бессильно даже объединенное хитроумие всего человечества. Совершенный шифр. Невзламываемый без знания ключа. Надежный настолько, что сам ключ не подобрать до конца времен.
У историков нет доказательств того, что Томас Джефферсон смог прочесть страничку с образцом сообщения, которую Паттерсон приложил к письму. Зато известно, что в 1803 году президент США отправил в Париж послу США во Франции Роберту Ливингстону описание разработанного Паттерсоном шифра. Джефферсон охарактеризовал шифр как "простейший" и "самый неподбираемый".
Действительно, Лоурену Смитлайну пришлось изрядно потрудиться над тем, чтобы взломать шифр при помощи технологий 21 века. Насколько можно судить, он разгадывал шифр не один месяц и прочел сообщение в 2007 году. Рассказав о своем решении несколько раз в университетских аудиториях, только недавно Смитлайн опубликовал статью в журнале American Scientist, который тут же сделал ее главным материалом номера. Вскоре об успешной дешифровке сообщил The Wall Street Journal, сделав очевидным вклад Смитлайна не только в историю математики, но и в историю США.
В конце 18 - начале 19 века были широко распространены два вида шифров. Первые, шифры подстановки, были известны с 15 века и потихоньку выходили из моды. В них каждой букве алфавита в соответствие ставилась другая. Текст становился абсолютно нечитаемым, но поддавался частотному анализу . Другими словами, узнав, какая буква встречается чаще всего, можно было заменить ее самой часто встречающейся и в обычном языке. Сейчас таким криптосхемам и их дешифровке учат в школе на уроках информатики.
Вторая схема заключалась в кодировании информации. Каждому слову ставился в соответствие некий номер. Используя специальные таблицы, можно было декодировать числа обратно в слова. Паттерсону эта схема очень не нравилась, ведь запомнить книгу с номерами слов - непростая задача.
Он решил пойти другим путем и перемешать буквы и строки. Дальше следует краткое описание шифра - тем, кто не собирается заниматься тайной перепиской с президентом США, можно пропустить пару абзацев.
В паттерсоновском шифре сообщение надо писать сверху вниз и слева направо. Затем следует разбить его на несколько секций размером не более девяти строк. Строки в каждой секции нумеруются и перемешиваются в произвольном порядке. Порядок строк в секции даст первую половину ключа, например: 5-1-3-2-4-7-6-8 для секции из восьми строк.
Затем в начало каждой строки можно вставить от 0 до 9 случайных букв. Получившаяся последовательность дает вторую половину ключа, например, 1-7-9-3-3-2-1-7 (в первую строку вставили 1 букву, во вторую 7 букв и так далее). У сообщения получится рваный правый край - в конец можно добавить еще немного бессмысленных букв, чтобы выровнять его.
Сам ключ записывается как двузначное число, где десятки - цифра из первой половины, а единицы - число добавленных в начало бессмысленных букв. Дешифровщику достаточно отнять от каждой строчки по указанному количеству букв и переставить их в нужном порядке (во времена Паттерсона надо было вооружиться ножницами и переклеить вырезанные строки на лист бумаги). Сообщение дешифровано, его снова можно прочесть сверху вниз, а бессмыслицу у правого края просто игнорировать.
У шифра Паттерсона есть несколько потенциальных слабостей (в частности, бессмысленные буквы должны удовлетворять частотной таблице выбранного языка), но в целом, несмотря на простоту, без ключа его не разгадаешь.
Смитлайн решил, что найти ключ ему поможет анализ частоты появления диграфов - двухсимвольных сочетаний знаков. Чем распространеннее получившиеся диграфы, тем большую оценку им давал составленный алгоритм. Выделив диграфы и угадав размеры секций, он принялся за перебор.
Затем он составил программу для перебора всех возможных "маршрутов" по тексту шифровки; сделав пару наблюдений, значительно сократил число вариантов; запустил программу. На все про все ушло 100 тысяч операций - Смитлайн утверждает, что в девятнадцатом веке при определенной усидчивости этот шифр можно было бы вскрыть.
Получив ключ, он прочитал: "In Congress, July Fourth, one thousand seven hundred and seventy six. A declaration by the Representatives of the United States of America in Congress assembled. When in the course of human events...".
Начало Декларации независимости США. Написанной самим Томасом Джефферсоном. Так Паттерсон подшутил над президентом. А Смитлайн мог бы и догадаться.