Ранее я писал о взломе первого и второго шифра, придуманных математиком Полом Оламом ради розыгрыша своего друга Ричарда Фейнмана. Если описать контекст в нескольких словах, то эти шифры были одной из математических шуток, которые были в широком ходу у коллектива учёных, работавших на «продуктовой» базе в Лос-Аламосе над созданием той самой «ядрёной» бомбы. Также я упоминал о трёх других шифрах, авторство которых до сих пор достоверно неизвестно и вряд ли выяснится. Их называют шифрами Фейнмана, и до середины прошлого года два из них оставались нераскрытыми, о чём я также писал ранее. Так вот, в мае прошлого года это всё-таки свершилось и они были вскрыты. В этой статье я расскажу как.
Само собой разумеется, что работал с этими шифрами не я, но и мне здорово пришлось поломать голову, как это всё рассказать. Пришлось пройти весь путь и кое-что допилить, чтобы результат стал доступен как можно большему количеству людей на той части земной поверхности, которую со времён господина Стрельбицкого было принято называть «одной шестой». Автор взлома — Дэйв Вьера (David Vierra).
Итак, впервые шифры Фейнмана стали достоянием широкой общественности в декабре 1987 года, когда Крис Коул разместил в конференции сообщение с ними. В нём он пояснил, что получил их от самого профессора Фейнмана, будучи его аспирантом в Калифорнийском технологическом институте. Первый шифр был вскрыт почти сразу, в отличие от остальных. Подробнее об этом я уже писал. Долгое время нераскрытые шифры вспоминались только некоторыми энтузиастами, но в марте 2019 года началась «новейшая» история шифров Фейнмана. После исторической экспозиции Калтеха на reddit всплыли два шифра Олама, а после — и их взлом. Этот факт и послужил причиной того, что любители подобного досуга вспомнили и о нераскрытых шифрах Фейнмана.
Шифры Олама были вскрыты Полом Релкиным. Первый содержал информацию о процедуре почтовой рассылки в Лос-Аламосе, зашифрованную простой заменой с добавлением незначащих символов. Второй поддался только спустя месяц, и его решение потребовало изобретения совершенно нового метода анализа транспозиционных шифров.
Ну что же, приступим.
Сразу скажу, что оба сообщения оказались зашифрованы одним и тем же методом. В некотором роде мне кажется, что этот факт свидетельствует о непричастности к ним Пола Олама, поскольку ранее при шифровании своих сообщений для товарища он использовал разные методы, хотя это всего лишь моё умозрительное заключение и совершенно не обязательно верное.
Оба шифра используют две одноалфавитные замены, которые не удалось полностью восстановить, однако я уже упоминал о том, что такие шифры обладают серьёзной уязвимостью, которую называют проблемой частично неверного ключа. То есть ключи, достаточно похожие на истинный, позволяют вскрыть большие куски разборчивого открытого текста, а при некотором везении и остальные части зашифрованного сообщения.
Вот полученные шифралфавиты:
Обычный алфавит | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
Шифралфавит 1 | M | A | N | Y | R | E | Q | U | S | — | H | V | B | C | I | D | — | O | L | W | G | Z | X | — | K | — |
Шифралфавит 2 | J | H | A | Z | T | E | N | Y | X | M | L | O | C | U | F | B | Q | V | K | P | S | G | W | — | D | — |
Сразу приведу решения шифров, поскольку в дальнейшем при описании метода шифрования они нам пригодятся:
Шифр №2
Шифрованный текст | Исходное сообщение (стихотворение 1896 года «Теренс, это глупости», Альфреда Хаусмана, одного из самых популярных английских поэтов своего времени) |
XUKEXWSLZJUAXUNKIGWFSOZRAWURORKXAOSLHROB XBTKCMUWDVPTFBLMKEFVWMUXTVTWUIDDJVZKBRMC WOIWYDXMLUFPVSHAGSVWUFWORCWUIDUJCNVTTBER TUNOJUZHVTWKORSVRZSVVFSQXOCMUWPYTRLGBMCY POJCLRIYTVFCCMUWUFPOXCNMCIWMSKPXEDLYIQKD JWIWCJUMVRCJUMVRKXWURKPSEEIWZVXULEIOETOO FWKBIUXPXUGOWLFPWUSCH | Why, if 'tis dancing you would be, There's brisker pipes than poetry. Say, for what were hop-yards meant, Or why was Burton built on Trent? Oh many a peer of England brews Livelier liquor than the Muse, And malt does more than Milton can To justify God's ways to man. Ale, man, ale's the stuff to drink For fellows whom it hurts to think |
Шифр №3
Шифрованный текст | Исходное сообщение (первые три предложения из работы Ричарда Фейнмана 1953 года о фазовом переходе в жидком гелии) |
WURVFXGJYTHEIZXSQXOBGSVRUDOOJXATBKTARVIX PYTMYABMVUFXPXKUJVPLSDVTGNGOSIGLWURPKFCV GELLRNNGLPYTFVTPXAJOSCWRODORWNWSICLFKEMO TGJYCRRAOJVNTODVMNSQIVICRBICRUDCSKXYPDMD ROJUZICRVFWXIFPXIVVIEPYTDOIAVRBOOXWRAKPS ZXTZKVROSWCRCFVEESOLWKTOBXAUXVB | The behavior of liquid helium, especially below the lambda transition, is very curious. The most successful theoretical interpretations so far have been largely phenomenological. In this paper and one or two to follow, the problem will be studied entirely from first principles. |
Давайте всё‑таки перейдём к описанию самого метода. В нём каждое слово шифруется одной из двух замен, чередующихся между собой после каждого слова, при этом первое слово каждого предложения или стихотворной строки всегда шифруется с использованием первого шифралфавита, что иногда приводит к случайным вариантам использования его для двух слов подряд. Также выяснилось, что слова с чётным количеством букв зеркально отражены.
Использованные сообщения придерживаются этой системы шифрования для каждого текста за одним исключением: последовательные слова «England brews» в пятой строке стихотворного отрывка зашифрованы вторым шифралфавитом, хотя для шифрования слова «brews» следовало бы использовать первый. Непонятно с чем это связано, может быть, автор шифров ошибся (что маловероятно), а, может, в этом был какой‑то сакральный смысл, который не достиг моего понимания.
Шифр №2
Исходный текст | why | if | tis | dancing | you | would | be | there | is | brisker | pipes | than | poetry |
Шифралфавит 1 | XUK | WSL | KIG | AR | WUROR | AOSLHRO | WUMC | ||||||
Шифралфавит 2 | XE | ZJUAXUN | WFSOZ | XK | BXBTK | BFTPVD | |||||||
Зеркальная замена | EX | RA | KX | CMUW | DVPTFB | ||||||||
Результат | XUK | EX | WSL | ZJUAXUN | KIG | WFSOZ | RA | WUROR | KX | AOSLHRO | BXBTK | CMUW | DVPTFB |
Шифр №3
Исходный текст | the | behavior | of | liquid | helium | especially | below |
Шифралфавит 1 | WUR | IE | URVSGB | ARVIX | |||
Шифралфавит 2 | HTYJGXFV | OXQSXZ | TKBTAXJOOD | ||||
Зеркальная замена | VFXGJYTH | EI | ZXSQXO | BGSVRU | DOOJXATBKT | ||
Результат | WUR | VFXGJYTH | EI | ZXSQXO | BGSVRU | DOOJXATBKT | ARVIX |
Очевидно, что первый алфавит произведён от какой‑то ключевой фразы, начинающейся со слов «MANY REQUESTS HAVE BEEN», а вот насчёт второго неизвестно, был ли он получен хоть каким‑то систематическим путём или нет. По крайней мере даже если это так, выяснить этот момент не удалось. Конечно, для полноты картины было бы интересно разузнать этот факт, но в конечном итоге для решения наших «подопечных» это не имеет абсолютно никакого значения.
Ход решения
Первичный анализ шифров выявил, что частотность букв для каждого из зашифрованных сообщений не была ни полиалфавитной, ни одноалфавитной. Применённый метод криптоанализа индекса совпадений, впервые описанный отцом американской криптологии Уильямом Фридманом в 1922 году, дал результаты 0,04 506 и 0,04 299 для второго и третьего шифра, соответственно. На сегодняшний день индексы совпадений для различных классических шифров уже давно рассчитаны. Для английского языка в полиалфавитном шифровании он составляет 0,03 846 (это же значение характерно для случайного набора букв), а для одноалфавитного — 0,0667. Кстати, на хабре имеется годная статья по криптоанализу классических шифров.
На графике периодического индекса совпадений не оказалось характерных всплесков, а повторов оказалось немного больше, чем ожидалось. В каждом из зашифрованных сообщений нашлись одинаковые буквенные сочетания. Графики частотности букв между двумя шифрсообщениями также оказались достаточно похожими для того, чтобы появилось подозрение в тождественности используемого метода шифрования. Тем не менее достаточно долго они никак не поддавались, несмотря на различные манипуляции и ухищрения.
Первичное отзеркаливание каждого шифра по отдельности дало совсем немного и никак не помогло. Однако объединение двух исходных зашифрованных сообщений и отзеркаливание получившегося текста немного подсобило. Полученный «франкенштейн» был скормлен сольверу AZDecrypt, который произвёл вот такое дешифрование (пробелы были вставлены автором взлома самостоятельно в произвольном порядке):
PRINCIPLES DS LESS ROT AT DELARS BE I BETS CAD ILL PARCE LIESTS ERRE I TOE ID ORATE BNAL AIO ITS I SET IN ATE PATE REVE A OR I LEAR ALCA AT SAME LOS SO STEE DAD A LILAD TEL A CITEROEST SMAAASSS MR TO STANDS ME EL MAMERIES TRANSITION RO PC SO ESTIE RACE SPECIALLINAR EMP LIVE I BE SHE SAM I OR AND HT END TO SD LMN IT IN EPS DOLLES LESS NIRB DES SETS AND I SAR ON A TAR ON AT DED A IS VESS IS ITS EODE TO AT IL TOND NOT TO RESEAST ALT STOP MS AEST D NOT LIVE OR RE BARE ALS DER HBN A LANE AS PEER A TAN I END TAL DON DREM CHER TON SO I IS DELD TO APS BRAI I ENDERE I NOD ROS SO SPOET RID NOT SEP I PLAH SELC IS AL AND CABLE OD MES AN ICN ABSE DISS NI
Сразу бросилось в глаза первое слово «PRINCIPLES». Как я уже писал выше, для некоторых видов шифров частично неверный ключ позволяет обнажить некоторые значимые куски осмысленного текста, которые могут помочь вскрыть и всё остальное сообщение. Также заметны «TRANSITION» в середине текста и комбинация букв «SPECIALL», которая следует сразу за «E», и подозрительная комбинация букв «CITEROEST».
Дальнейшие действия заключались в простой замене и вставке слов «PRINCIPLES», «TRANSITION» и «ESPECIALLY» в нужные места, чтобы посмотреть, что ещё получится. Эти манипуляции дали на первый взгляд ничего не значащий, но очень подозрительный фрагмент «LACITER». Воспоминание о том, что мы переворачивали текст, привело к фрагменту «RETICAL». Анализ английских слов, содержащих подобный фрагмент, в совокупности со знанием, для кого были созданы шифры, и куском шифра «CITEROEST», позволил сделать предположение о том, что изначальное слово с высокой вероятностью могло бы быть словом «THEORETICAL». Вот что получилось:
P | R | I | N | C | I | P | L | E | S |
B | V | X | U | A | X | B | O | T | S |
T | R | A | N | S | I | T | I | O | N |
P | V | J | U | K | X | P | X | F | U |
E | S | P | E | C | I | A | L | L | Y |
T | K | B | T | A | X | J | O | O | D |
T | H | E | O | R | E | T | I | C | A | L |
P | Y | T | F | V | T | P | X | A | J | O |
Как итог, сформировался вот такой недошифралфавит:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
J | A | T | Y | X | O | U | F | B | V | K | P | D |
Далее в обобщённом тексте с буквами «Т» и «Н» в глаза бросались короткие слова типа «THEY» и «HAVE» вперемешку с очевидной тарабарщиной, поэтому им, как и другим коротким фрагментам, пока ещё не стоило доверять, но иметь в виду всё равно было необходимо. Количество связанных друг с другом длинных слов оказалось достаточно велико, а одно из них вовсе оказалось перевёрнуто по отношению к остальным. В совокупности эти признаки дали некоторую надежду на то, что это всё‑таки правильный путь. Тем не менее до окончательного решения было ещё далеко.
Существенно много усилий ушло на проверку предположений об использовании омофонической замены в сочетании с транспозицией. В итоге они не оправдались. Не удалось получить больше нескольких коротких и совсем уж ненадёжных слов.
Итак, возвращаясь к методу Фридмана и усреднённому индексу совпадений каждого из шифров примерно равному 0,045, стоило задаться вопросом, а был ли мальчик мог ли шифр быть омофоническим? Может быть, он просто полиалфавитный? Если учитывать не самую высокую сложность предыдущих взломанных шифров, имеющих отношение к Фейнману, и вариант того, что они должны быть разгаданы вручную, вряд ли здесь должна быть омофоническая замена и транспозиция.
Повторяющиеся в словах буквы обратили на себя некоторое внимание «SCWRODORW». Поиск по шаблону «SCWRODORW» дал семь вариантов: «COGNISING», «COGNIZING», «GASEITIES», «HOSEPIPES», «INTERPRET», «MISREFERS», «UNDERBRED».
В ходе их перебора был выбран один, поскольку другие никак не укладывались в «прокрустово ложе» наших шифров. «INTERPRET» сложился в «INTERPRETATIONS», а после этого шифр развалился и приказал долго жить.
S | C | W | R | O | D | O | R | W |
I | N | T | E | R | P | R | E | T |
Вот так были вскрыты шифры, предназначавшиеся для Ричарда Фейнмана. Они оставались неразгаданными больше полувека. Разумеется в распоряжении профессора не было современных возможностей, но и тот, кто зашифровал эту информацию ими не обладал. Эти шифры были всего лишь интеллектуальной шуткой, которую не смог вскрыть даже великий Фейнман.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
- 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS
