Шифрованный мир. Азы криптографии и задачи по криптоанализу

Артём Музагафаров

В этой книге просто и увлекательно рассказано про азы шифрования и криптоанализа с примерами и историей разных шифров, с примерами и задачами. А также в этой книге вы можете найти приложение для дешифрования простых шифров.

История криптологии

насчитывает около 4000 лет, что делает её одной из старейших наук наряду с математикой, логикой, геометрией, астрономией и медициной.

Первые шифры появились практически сразу вместе с появлением самой письменности — не позднее, чем в третьем веке до нашей эры — и были очень просты. Это был алгоритм вроде «заменить все буквы А на букву В, Б на Д, а В на Я…». Такие способы тайной письменности были известны уже древним цивилизациям Индии (и считались там одним из искусств), Египта и Месопотамии. Большую область применения криптография имела тогда, конечно же, в военном деле, однако археологи находили и зашифрованные рецепты Месопотамии, относящиеся к обычным ремеслам, вроде изготовления гончарных изделий.

В Древнем Египте полностью зашифрованные тексты встречаются с 16 века до нашей эры. Здесь в это время криптография была представлена в виде загадок и ребусов. Однако это делалось не столько для того, чтобы затруднить чтение, а чтобы превзойти друг друга в остроумии, а также, привлечь внимание к своим текстам. Использовались необычные иероглифы, которые не могли прочесть лаже многие грамотные египтяне.

В книге пророка Иеремии (6 век до н.э.) использовался метод Атбаш — когда заменяют первую букву алфавита на последнюю, вторую на предпоследнюю и т. д.

В это же время между Афинами и Спартой шла война. Как говорят «в любви, как и на войне, все средства хороши» и шифрование в данном случае — отличное средство. У Древней Спарты был козырь — скитала — одно из древнейших криптографических устройств.

Скитала представляла собой обычный длинный цилиндр определённого диаметра или в более удобном варианте — его ещё обтёсывали до определённого числа граней.

Скитала

Сам же процесс шифровки происходил следующим образом — на скиталу наматывали тонкую полоску пергамента (бумагу сейчас использовать в этих целях не рекомендуется — по её сгибам достаточно легко восстановить характеристики самой скитале) и писали сначала послание, а на оставшихся пустых гранях — случайные буквы. После размотки на ленте образовывалась шифровка, расшифровать которую можно было, только намотав эту ленту на такую же скиталу с таким же диаметром и количеством граней. Таким образом, получалось, что большинство символов в шифровке просто лишние и маскируют открытый текст. Например, ОБВКЫРКРЛОУИМИНПРСТТОЛДОШГУГМИРРЫЧААРСЧФУЕПИПАСЯГРС — это что-то нечитаемое и непонятно о чём вообще, однако достаточно просто прочитать только каждую четвёртую букву из этого сообщения, чтобы получить вполне внятное слово. Для этого в скитале было четыре грани размером в высоту одной буквы или один оборот по цилиндру был по длине как высота четырёх букв.

Через век Аристотель нашёл способ взламывать такой шифр — наматывать ленту с шифровкой на острый конус до тех пор, пока не появлялись читаемые куски текста. Шифр перестал считаться надёжным и греческий полководец Эней Тактик придумал новый шифр со своим криптографическим инструментом — линейкой Энея.

линейка Энея

Суть этой тайной передачи посланий заключался в следующем. Бралась нить и завязывалась на начальных прорезях в линейке. Далее она протягивалась до первой буквы в послании, после чего на ней завязывался узел. Потом также узел делался на второй букве и так до конца сообщения. После всех этих действий нить отделялась от линейки и с полученными на ней узлами передавалась гонцам. Только получатель, имеющий в точности такую же линейку с порядком букв и расстояниями между ними, мог по расстояниям между узлами на нити расшифровать послание.

Далее несколько веков значимых нововведений в чистой криптографии (не считая косвенно касающихся областей, таких как кодирование, особые приёмы письма, затрудняющих чтение и т.п.) не было. До сих пор наиболее популярными были шифры с простой заменой — так например, Гай Юлий Цезарь в 1 веке до нашей эры просто прибавлял к алфавитному номеру буквы, которую надо было зашифровать, определённое число (это число и было ключом расшифрования) и писал вместо неё букву с получившимся номером. Однако (возможно, что и за счёт этой стагнации) практическое использование криптографии многократно увеличивается. Шифрованием начинают широко пользоваться дипломаты, купцы и даже простые граждане.

Вот тогда и зарождается криптоанализ — наука о методах взлома шифров и оценки их надёжности. Произошло это в 8 веке (уже нашей эры) в арабских странах. Кстати именно арабы придумали такие понятия, как алгоритм (спасибо Аль-Хорезми) и шифр (от араб. «sifr» — ноль). Итак, Халиль аль-Фарахиди первым обратил внимание на возможность использования стандартных фраз открытого текста для дешифрования: он предположил, что первыми словами в письме на греческом языке византийскому императору будут «Во имя Аллаха», что позволило ему, уже зная значения этих букв, прочитать оставшуюся часть сообщения. Абу Бакр Ахмед ибн Али Ибн Вахшия ан-Набати (интересно что зашифровано в его имени? шутка) написал «Книгу о большом стремлении человека разгадать загадки древней письменности». Это

одна из первых книг о криптографии с описаниями нескольких шифров, в том числе с применением нескольких алфавитов.

История криптографии — Википедия

А в книге Абу Юсуфа Аль-Кинди, встречается первое упоминание о частотном криптоанализе. В ней был описан эффективный метод расшифровки сообщений, зашифрованных простой заменой (о нём в следующих главах), тем самым подтолкнув развитие полиалфавитных шифров в арабских странах. Благодаря этому они опередили Европу в вопросах криптографии на 600 лет. Так или иначе, книга чётко обозначила проблему одноалфавитных шифров, и ровно с этого момента — 9 век — пошёл второй этап в криптографии.

Второй этап криптологии начался введением в широкое использование полиалфавитных шифров.

Ниже я подробно разберу все виды шифров, а в этой главе могу сказать, что, например, в 1401 году (в Европе только лишь тогда начался второй этап) Симеоне де Крема (Центром прогресса становится Италия, больше других контактировавшая с Востоком, пережившим свой Золотой век в 10—13 веках, торговый и культурный центр эпохи Возрождения), так вот, он заменяет согласные одной конкретной другой буквой, а гласную (поскольку гласные являются самыми частыми буквами) может заменить любой из нескольких, и не только буквами, но даже цифрами и специальными символами:

Всё больше увеличивается объём шифрованной переписки, и в связи с этим появляется первая организация, посвятившая себя целиком криптографии (Италия, Венеция, 1452 г.) и занимавшаяся взломом и созданием шифров по заданиям правительства.

Леон Баттист Альберти, знаменитый архитектор и философ,

изучив методы вскрытия использовавшихся в Европе моноалфавитных шифров, попытался создать шифр, который был бы устойчив к частотному криптоанализу.

История криптографии — Википедия

Альберти предложил папской канцелярии в 1466 году

вместо единственного секретного алфавита, как в моноалфавитных шифрах, использовать два или более, переключаясь между ними по какому-либо правилу.

История криптографии — Википедия

Также Альберти предложил устройство из двух скреплённых в центре медных дисков, один шире другого, каждый из которых имел алфавит, написанный по краю, и мог поворачиваться относительного другого диска.

Пока диски не двигаются, они позволяют шифровать с использованием шифра Цезаря, однако через несколько слов диски поворачиваются, и меняется ключ сдвига.

Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7

Диск Альберти

Позже это устройство переизобреталось и использовалось не один раз в разных странах вплоть до 19 века. (В России это был «Криптограф» Деревянкина — главного механика, помощника начальника Петербургского почтово-телеграфного округа в 1879 году.)

А через 3 года после изобретения Альберти появляется первый шифр пропорциональной замены «Миланский ключ» — чем чаще буква встречается в обычном тексте — тем большим количеством символов она может быть заменена, таким образом частотный криптоанализ наконец-то оказался побеждён.

Габриэль де Лавинда вносит свою лепту, вводя номенклаторы — специальные значки или буквенно-цифровых коды для отдельных слов и фраз, таких как географические названия, титулы и должности. Это устраняет уязвимость, найденную ранее Халиль аль-Фарахиди и теперь предугать с чего начинается письмо, например, Папе Римскому становится проблематично. До этого же оно всегда начиналось «Ваше Святейшество».

В 1518 году германский аббат Иоганн Тритемий в своей книге предложил каждую следующую букву шифровать с уникальным ключом для сдвига Цезаря, используя определённый заранее цикл, который и является итоговым ключом для «шифра Виженера», как он известен сейчас.

Кроме этого, Тритемий первым заметил, что шифровать можно и по две буквы за раз — биграммами.

Жельников В. Становление науки криптологии // Криптография от папируса до компьютера. — М.: ABF, 1996. — 335 с. — ISBN 5-87484-054-0.

В 1549 году в России учреждена первая государственная шифровальная служба — «посольский приказ» с «циферным отделением».

В 1550 году итальянский математик Джероламо Кардано, состоящий на службе у самого Папы Римского

Жельников В. Становление науки криптологии // Криптография от папируса до компьютера. — М.: ABF, 1996. — 335 с. — ISBN 5-87484-054-0.

изобрёл новый шифр — решётку Кардано.

Этот метод похож на спартанскую скиталу — сами буквы текста не изменяются, однако добавляются много лишних. В отличие от скиталы вместо алгоритма определения шифрованного текста, который можно просто подобрать здесь используется специальный шаблон — решётка из листа картона, пергамента, или тонкого металла. Также если шифровка скиталой была перехвачена, сразу было понятно, что тут что-то зашифровано, а шифровку решёткой Кардано можно замаскировать под обычное письмо, вставив в пустые места не случайные символы, а подходящие под синтаксис естественного языка, хотя мысли об этом высказывались ещё век назад Леоном Альберти.

Пример письма, скрытого решёткой Кардано

В 1585 году Блез де Вижинер наконец-то рассказал о шифре Тритемия широкому читателю в своей книге.

В этом труде он также замечает:

«Все вещи в мире представляют собой шифр. Вся природа является просто шифром и секретным письмом».

«Трактат о шифрах» — Посол Франции в Риме Блез де Виженер

В 1605 году выходит книга «О преумножении наук» Фрэнсиса Бэкона, в которой он представил свой шифр: каждая буква алфавита кодируется в двоичной системе (для этого достаточно 5 бит на букву) — например буква А — это 00000, Б = 00001, Е = 00101 и т.п., далее берётся любой открытый достаточно длинный текст и в соответствии с полученной кодировкой шифруемого сообщения, буквы открытого текста соответствующие единице немного изменяются (например, пишутся курсивом или другим шрифтом). Таким образом, с виду не сразу может быть понятно, что тут вообще что-то зашифровано. Например, попробуйте разгадать, что я тут зашифровал: Тётя Марта заболела и желает видеть тебя. Будь добр, ну приезжай к нам хотя бы на неделю!

(подсказка: пробел и знаки препинания не учитываются, Й не включён в алфавит, а стандартную таблицу кодировки для шифра Бэкона Вы можете найти в конце книги).

А теперь представьте, что у Вас и Вашего друга есть своя такая таблица кодировок, взломать шифр становится уже труднее, однако, зная основной принцип, такой шифр сводится к шифру простой замены.

В 1630-е во Франции первый профессиональный криптоаналитик Антуан Россиньоль при поддержке Людовика XIII разработал «Великий Шифр». Он

получил такое название из-за своей стойкости и репутации невзламываемого

Великий Шифр — Википедия

(более двух столетий никто не мог взломать его). Шифр представлял собой набор из огромного количества чисел (уникальными же были лишь 587), большая часть которых обозначает слоги. Однако, некоторые числа обозначали буквы или же целые слова, для часто употребляемых букв и слогов существовало несколько чисел, а одно число служило ловушкой для криптоаналитиков — оно ничего не обозначало, а отменяло предыдущее число.

Также

Антуану Россиньолю принадлежит доктрина, согласно которой стойкость шифра должна определяться видом зашифрованной информации. Для военного времени достаточной будет являться стойкость, если сообщение с приказом армейскому подразделению не будет расшифровано противником хотя бы до момента исполнения получателем, а для дипломатической почты шифр должен обеспечивать сохранность на десятки лет.

В 1750-х годах в России от шифров стали требовать алфавиты мощностью более чем в тысячу символов.

Соболева Т. А. Введение // История шифровального дела в России. — М.: ОЛМА-ПРЕСС Образование, 2002. — 512 с. — (Досье). — 5000 экз. — ISBN 5-224-03634-8.

Таким образом, осуществлялась защита от частотного криптоанализа, и можно было зашифровать сообщение, части которого написаны на нескольких языках.

В 18 веке Бенедикт Арнольд, генерал армии США, использовал «кодовую книгу», копия которой должна быть у каждого отправителя и получателя сообщений. Шифр состоял в указании позиции слова в книге, в том числе страницы, строки и номера в строке. Данный метод получил название книжного шифра.

Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7

В 1790-х годах будущий президент США Томас Джефферсон построил одну из первых механических роторных машин, упрощавшей использование полиалфавитных шифров.

Криптография от Средних веков до Нового времени

Однако распространение роторные машины получили лишь в начале XX века.

Баричев С. Г., Гончаров В. В., Серов Р. Е. История криптографии // Основы современной криптографии — М.: Горячая линия — Телеком, 2002. — 175 с. — (Специальность. Для высших учебных заведений) — ISBN 978-5-93517-075-2

Шифровальное устройство М-94

Значительный толчок криптографии дало изобретение телеграфа. Сама передача данных перестала быть секретной, и сообщение, в теории, мог перехватить кто угодно. Интерес к криптографии возрос, в том числе и среди простого населения, в результате чего многие попытались создать индивидуальные системы шифрования. Преимущество телеграфа было явным и на поле боя, где командующий должен был отдавать немедленные приказания по всей линии фронта или хотя бы на всём поле сражения, а также получать информацию с мест событий. Это послужило толчком к развитию полевых шифров. Армия США использовала шифр Виженера с коротким ключевым словом до 1863 года.

Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7

В 1854 году Чарлз Уитстон описал, а Лион Плейфер добился применения британскими вооружёнными силами нового шифра, как его позже назовут — шифра Плейфера. Его особенностью была относительная простота использования, хотя этот шифр являлся одним из первых, в котором применялась замена биграмм вместо отдельных букв. Поэтому его использовали для шифрования важной, но не очень секретной информации во время боя — через то время, которое противник потратит на взлом шифра, информация станет уже неактуальной.

Бабаш А. В., Шанкин Г. П. История криптографии. Часть I. — М.: Гелиос АРВ, 2002. — 240 с. — 3000 экз. — ISBN 5-85438-043-9.

Шифр использовался вплоть до Второй мировой войны.

Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7

Суть шифра разберём позже.

В 1863 году Фридрих Касиски опубликовал метод, впоследствии названный его именем, позволявший быстро и эффективно вскрывать практически любые шифры того времени. Метод состоял из двух частей — определение периода шифра

Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7

(через сколько символов повторяются одинаковые символы в шифровке, путём вычисления наименьшего общего делителя можно установить длину ключа шифра)

и дешифровка текста с использованием частотного криптоанализа.

Fred Cohen. A Short History of Cryptography // Introductory Information Protection. — 1987. — ISBN 1-878109-05-7

В 1883 году Огюст Керкгоффс описал требования, которым должна удовлетворять защищённая система. Одно из них звучит так:

«Нужно, чтобы не требовалось сохранение всей системы шифрования в тайне; попадание системы в руки врага не должно причинять неудобств»

Auguste Kerckhoffs. La cryptographie militaire. — Journal des sciences militaires, 1883.

Оно широко применяется в криптографии и сейчас известно как принцип Керкгоффса. То есть секретными должны быть только ключи шифрования, но не сам алгоритм. Так до этого, например, на Руси

слова «шифр» и «ключ» до 20 века были синонимами: ключом называли принцип шифрования, а его раскрытие означало гибель шифра.

Токарева Н Н. Об истории криптографии в России // ПДМ. — 2012. — Декабрь. — С. 82—107.

Принцип Керкгоффса направлен на то, чтобы сделать безопасность алгоритмов и протоколов независимой от их секретности; открытость не должна влиять на безопасность.

Mann, Charles C. (September 2002), Homeland Insecurity, The Atlantic Monthly

Использование безопасной криптографии заменяет сложную проблему обеспечения безопасности сообщений гораздо более управляемой: хранением относительно небольших ключей в безопасности. Хранить используемые методы в секрете сложнее, особенно в долгосрочной перспективе, как и изменять их после развертывания системы.

Savard, John J. G. A Cryptographic Compendium. The Ideal Cipher. — 1998, 1999.

Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей

Принцип Керкгоффса — Википедия

и нужно проектировать системы, исходя из предположения, что противник с ними полностью ознакомится.

МАКСИМА ШЕННОНА

Friedrich L. Bauer. Decrypted Secrets: Methods and Maxims of Cryptology (англ.). — 4th, Revised & Extended Edition. — Springer, 2007. — 504 p. — ISBN 9783662047378.

Сокрытие алгоритма снижает вероятность нахождения и исправления уязвимостей и увеличивает вероятность того, что они могут, и будут использоваться злоумышленниками.

Открытое обсуждение и анализ алгоритмов выявляют слабые стороны, о которых не думали первоначальные авторы, и тем самым приводят к созданию более совершенных и более безопасных алгоритмов.

Принцип Керкгоффса — Википедия

Однако, не все согласны с этим принципом — так АНБ США хранит свои алгоритмы в секрете, а в некоторых компаниях принято хранить в тайне внутреннюю работу системы.

Они утверждают, что безопасность через неясность делает продукт более безопасным и менее уязвимым для атак. Противоположным аргументом является то, что безопасность через неясность может привести ко многим реальным атакам. Разработчики не должны недооценивать хитрость злоумышленников и никогда не должны пренебрегать данным принципом.

Принцип Керкгоффса — Википедия

При работе с шифрами не стоит забывать о самом главном слабом месте любого шифра — человеческий фактор. Поэтому организационные меры порой важнее самого шифра. Так, например, Россия похитила кодовую книгу посла США в Бухаресте, а из-за того, что посол не доложил начальству о пропаже (видимо, боясь наказания), а просто пользовался аналогичной кодовой книгой другого посла, российская сторона смогла читать переписку США со своими послами вплоть до Первой мировой.

Благодаря помощи русских, захвативших кодовую книгу с затонувшего германского крейсера «Магдебург», а также собственным подобным операциям, англичане сумели разгадать принцип выбора шифров Германией. Чтение их переписки дало значительный вклад в уничтожение германских подводных лодок.

Анин, Б. Ю.. Англичане. Истоки. Со дна морского. // Радиоэлектронный шпионаж. — М.: Центрполиграф, 2000. — С. 307—310. — (Секретная папка). — 10 000 экз. — ISBN 5-227-00659-8.

Также есть риск «человека посередине»:

С помощью ложного приказа, отправленного английским агентом немецким шифром, недалеко от Южной Америки была уничтожена целая эскадра. А с помощью подложного английского кода, попавшего в руки Антанте в мае 1915 года, англичане не раз вводили Германию в заблуждение, заставив, например, в сентябре 1916 года оттянуть значительные силы для отражения мифической десантной атаки.

Анин, Б. Ю.. Англичане. Истоки. Игра в поддавки. // Радиоэлектронный шпионаж. — М.: Центрполиграф, 2000. — С. 310—313. — (Секретная папка). — 10 000 экз. — ISBN 5-227-00659-8.

Именно поэтому важным свойством современных шифров является не только конфиденциальность, но и аутентичность (возможность проверить кто отправил сообщение).

В СССР криптография была полностью закрытой дисциплиной, которая использовалась исключительно для нужд обороны и государственной безопасности, а потому не было необходимости в публичном освещении достижений в этой области.

Сокровищница отечественной криптографии

Наиболее известным результатом работы криптоаналитиков времени Первой мировой войны (1917г.) является расшифровка телеграммы министра иностранных дел Германии Циммермана немецкому послу в США, подтолкнувшая США к вступлению в войну на стороне Антанты.

М. А. Партала. Радиоразведка балтийского флота в Первую мировую войну

До этого американская пресса симпатизировала Британии не больше, чем Германии, а подавляющее большинство американцев хотели бы избежать участия США в войне в Европе. Телеграмма была перехвачена сразу после отправки. Криптоаналитики «Комнаты 40» Британского Адмиралтейства получили копию для дешифровки. В Телеграмме был использован шифр 0075, который был уже частично взломан в Комнате 40. Для Британского правительства телеграмма была блестящей возможностью заставить Соединённые Штаты вступить в Первую мировую войну на стороне союзников.

Телеграмма Циммермана — Википедия

Необходимо было

принять определённые меры предосторожности дипломатического характера

«Why was the Zimmerman Telegram so important?», BBC News, 17.01.2017

— нужно было не показывать, что Британия прослушивает США (Для этого уже после взлома достали копию телеграммы из Мексики — немецкий посол переотправил её в Мексику.

Эта копия беспрепятственно могла быть передана американцам. Она была зашифрована кодом 13040, образец которого Британия заполучила в Месопотамии, и таким образом к середине февраля у Британии появился полный текст).

Телеграмма Циммермана — Википедия

Та самая телеграмма, и использовавшиеся номенклаторы.

Также нужно было не выдавать, что коды Германии взломаны (Заявили, что в Мексике была уже расшифрованная версия телеграммы. Немецкое правительство отказалось рассматривать возможность взлома кода, вместо этого оно поручило фон Экхарду найти шпиона в посольстве в Мексике). После этого мексиканская телеграмма была передана в США и была опубликована в печати как достижение американской разведки.

Содержание телеграммы Циммермана (привлечение Мексики в войну на стороне Германии против США) привело к резкому росту антигерманских настроений в Америке и Конгресс США официально утратил нейтралитет, объявив войну Германии.

Телеграмма Циммермана — Википедия

В 1918 году Франции

Конец ознакомительного фрагмента.