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

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

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

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

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

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

ISBN 978-5-0060-2725-1

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Скитала

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

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

линейка Энея

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Также

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Антанта, уничтожив наиболее безопасные каналы передачи информации Германии, вынудила немцев использовать общедоступный телеграф. В то время на этом фронте немцы использовали шифр ADFGVX. Шифр этот является усложнением квадрата Полибия: ключом является таблица 6х6, чтобы зашифровать символ выписывается номер строки и столбца. В немецком шифре вместо цифр строки и столбцы нумеруются буквами A D F G V X (при передаче по телеграфу они наиболее не похожи друг на друга, что минимизирует вероятность ошибки передачи).

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

Пример первой половины ключа этого шифра

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

Однако, Жорж Пенвэн сумел за несколько напряжённых дней, доведя себя до изнеможения и потеряв 15 килограмм веса, вскрыть немецкий шифр ADFGVX.

Но не стоит списывать этот шифр со счётов – а что, если добавить побольше измерений, чем два? И алфавит тогда станет массивнее – хоть весь UTF-8, содержащий более 60 000 символов всех языков мира, смайликов, эмоджи, специальных математических знаков и много другого! И писать каждое сообщение на разных языках.

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

С 1928 года в криптоаналитики начинают набирать преимущественно математиков, а не лингвистов как раньше.

Позже мы разберём шифр Хилла.

В 1930-е в СССР была создана шифровальная машина В-4.

,в частности из-за строгой охраны шифровальных машин. Историк криптографии Леонид Бутырский поясняет:

Шифровальная машина М-101 Изумруд (в 2 раза уменьшен вес и в 6 раз габариты)

Группа из трёх польских математиков, несмотря на то, что британская и французская разведка не стали браться за эту задачу, сочтя её невыполнимой, вела работы по «борьбе» с «Энигмой» – немецкой роторной шифровальной машины, количество возможных ключей которой составляло более 10 000 000 000 000 000 – и даже умела читать многие сообщения, зашифрованные «Энигмой» до декабря 1938 года. Далее Англия собрала 12 000 специалистов, построила машину, помогавшую в дешифровке и читала все перехваченные и отправленные по телеграфу сообщения Германии, причём немцы так и не узнали об этом вплоть до конца войны (а европейцы ещё несколько лет после войны пользовались трофейными немецкими шифровальными машинами для передачи секретных дипломатических посланий, не зная, что англичане способны их расшифровывать), хотя СССР, состоявший в союзе с Британией имела доступ к переписке Германии и, в частности, благодаря этому смог подготовиться к Курской дуге. Подробнее об этом можно посмотреть в фильме «Игра в имитацию».

Bombe

Однако, взломать шифр – это лишь полдела, вторая половина – сделать так чтобы об этом не узнал враг. Чтобы не потерять это немаловажное преимущество и не вызывать лишних подозрений в шифре у немцев, Англии пришлось периодически давать Германии осуществлять её планы, даже уже зная их. Так, например, Черчилль в 1940 году принял решение не эвакуировать и не защищать город, о бомбардировке которого ему было известно заранее. Число повреждённых только зданий, не говоря уже о людях, составило 60 000. Такова цена секрета, о том, что другой секрет известен.

Для него использовалось новое устройство, называемое «машиной Лоренца».

Шифрование основывалось на шифре Вернама (о нём более подробно далее) и при правильном использовании гарантировало абсолютную криптостойкость.

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

,созданная Максом Ньюманом и Томми Флауэрсом при участии Алана Тьюринга в 1943 году. Машина позволила сократить время, требуемое на взлом сообщений, с шести недель до нескольких часов, что дало не только значительное военное преимущество, но и позволила сохранить силы и нервы самих дешифровщиков. Вот что пишет в своих мемуарах один из дешифровщиков из Блетчли-парк:

Также была подана идея итеративных блочных шифров.

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

В 1977 году он был опубликован, а в 1981 одобрен для использования в гражданском секторе. Однако шифр имел существенный недостаток – маленькую длину ключа (56 бит), что делало его уязвимым для простого перебора. Этот недостаток был специально внедрён АНБ (первоначально шифр мел длину ключа 112 бит), так как , поскольку гипотетически мощности вычислительной техники персональных компьютеров и публичная теоретическая база подобрались к тому, чтобы кто угодно мог шифровать любые послания так, что даже собственное правительство не в состоянии будет прочитать что там. Если раньше простая перлюстрация (вскрытие и прочтение) писем давала мощную фору государству, то теперь террористы, организованная преступность, бунтари или вражеская разведка этого не боятся. АНБ отказывало в государственных грантах математикам, кто вёл работы по криптографии, не сотрудничая с ними, накладывали гриф секретности на гражданские изобретения, связанные с шифрованием, запрещали публикацию материалов по шифрованию и криптоанализу. с этого времени начинается борьба государств с гражданской криптографией

Против автора бесплатного программного обеспечения с открытым кодом для шифрования и электронной подписи сообщений PGP (криптограф Брюс Шнайер охарактеризовал раннюю версию PGP как «ближайшую к криптосистемам военного уровня»), использующем известные несекретные шифры, Филиппа Циммермана было возбуждено уголовное дело за «экспорт вооружений», так как экспорт криптографических систем с длиной ключа более 40 бит был запрещён. Были многочисленные попытки внедрить в системы шифрования скрытые уязвимости с целью получения при необходимости спецслужбами расшифровки, однако по многим причинам это тогда не удалось. После отказа от технических средств доступа к ключам шифрования правительства обратились-таки к идее законодательного регулирования данного вопроса – когда человек обязан предоставить заранее или будет обязан предоставить по требованию ключ для чтения сообщений. Именно поэтому позже пытались закрыть тогда ещё только мессенджер «Telegram» – Павел Дуров отказался это делать для России, находясь за границей (c 2017 года проживает в Дубае, где и расположена штаб-квартира Telegram. Кроме российского и ОАЭ, имеет также паспорт государств «Сент-Китс и Невис» и Франции), Также он заявил, что во время поездки в США столкнулся с пристальным вниманием со стороны американских спецслужб.

В России тут же официально разблокировали «Telegram», однако, в Пакистане и Омане он также полностью заблокирован, видимо, нет нужды сотрудничать с ними.

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