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

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

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

Шифрованный мир

Азы криптографии и задачи по криптоанализу

Автор-составитель Артём Музагафаров

ISBN 978-5-0060-2725-1

Создано в интеллектуальной издательской системе Ridero

Введение

Информация может очень дорого стоить (ведь знание – это сила, а ещё инструмент шантажа и конкурентного преимущества, а порой она может даже решить, чьи люди выиграют войну, а чьи погибнут). Однако её проблематично просто хранить в сейфе – ей необходимо делиться с союзниками или постоянно использовать в производственных процессах. Поэтому делают так, чтобы свои могли её прочесть, а чужие – нет. Это и называется шифрование. В современном мире криптография имеет множество различных применений, как в частном, так и государственном секторе. Кроме очевидных, она используется в сотовой связи, платном цифровом телевидении, при подключении к Wi-Fi и для защиты транспортных билетов от подделок, в банковских операциях, и даже для защиты электронной почты от спама.

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

Что такое криптография?

(от древнегреческих «криптос» – скрытый, тайна и «графо» – пишу) – это наука о методах и инструментах обеспечения конфиденциальности и аутентичности информации, но что же это такое?

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

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

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

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

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

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

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

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

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

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

Скитала

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

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

линейка Энея

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

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

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

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

История криптографии – Википедия (https://ridero.ru/link/PYEsLYVdiqmAXX0iIdvxS)

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

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

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

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

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

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

История криптографии – Википедия (https://ridero.ru/link/0X5LVJG16aN2Ufsf8Qehq)

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

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

История криптографии – Википедия (https://ridero.ru/link/0X5LVJG16aN2Ufsf8Qehq)

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

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

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.