Read the book: «Шифрованный мир. Азы криптографии и задачи по криптоанализу»
Автор-составитель Артём Музагафаров
ISBN 978-5-0060-2725-1
Создано в интеллектуальной издательской системе Ridero
Введение
Информация может очень дорого стоить (ведь знание – это сила, а ещё инструмент шантажа и конкурентного преимущества, а порой она может даже решить, чьи люди выиграют войну, а чьи погибнут). Однако её проблематично просто хранить в сейфе – ей необходимо делиться с союзниками или постоянно использовать в производственных процессах. Поэтому делают так, чтобы свои могли её прочесть, а чужие – нет. Это и называется шифрование. В современном мире криптография имеет множество различных применений, как в частном, так и государственном секторе. Кроме очевидных, она используется в сотовой связи, платном цифровом телевидении, при подключении к Wi-Fi и для защиты транспортных билетов от подделок, в банковских операциях, и даже для защиты электронной почты от спама.
В этой книге я попытался простым языком и с иллюстрациями увлекательно рассказать о наиболее популярных, интересных и понятных шифрах. Ну что же, приступим! Начнём с небольшого экскурса в науку, которая занимается шифрованием, продолжим историей развития методов шифрования и дешифровки, ну и закончим ознакомлением с видами шифров.
Что такое криптография?
(от древнегреческих «криптос» – скрытый, тайна и «графо» – пишу) – это наука о методах и инструментах обеспечения конфиденциальности и аутентичности информации, но что же это такое?
Конфиденциальность обеспечивает невозможность прочтения информации несанкционированными пользователями (т.е. всеми, кому эта информация не предназначается). В криптографии конфиденциальность заключается в шифровании информации на основе условленного (заранее обеими сторонами – отправителем и получателем) метода шифрования (вида шифра) с секретной передачей ключей для шифровок.
Аутентичность же подразумевает целостность и подлинность авторства, а, следовательно, и невозможность отказа от авторства информации. То есть гарантию того, что сообщение не было кем-либо изменено в процессе доставки и того, что оно было отправлено именно тем, кем было заявлено. В криптографии аутентичность достигается применением ассиметричного шифрования, электронной подписи, хеш-функций и много другого. Однако следует помнить о границе применимости этой прикладной науки. Так криптография не занимается защитой от иррационального поведения и неадекватных действий санкционированных абонентов (человеческий фактор). Не в её компетенции и кража, копирование физических носителей секретных ключей, распространение уже расшифрованных секретных (составляющих государственную тайну) и конфиденциальных (не защищаемых государственными службами) сообщений (вспомним Эдварда Сноудена как широко известный пример добровольного рассекречивания большого объёма информации), а также многих других угроз информации, возникающих в защищенных системах передачи данных. Этим вместо криптографии занимается теория и методология защиты информации, комплексная система защиты информации (включающая в себя при необходимости и криптографическую составляющую) и в немалой степени сами организаторы и технологи защиты информации (например, службы безопасности, имеющиеся во многих даже частных организациях).
Однако, у криптографии есть, так сказать, злой брат-близнец – криптоанализ, который наоборот хочет всячески ей помешать. И, таким образом, им приходится постоянно соперничать, Совершенствуя каждый свои методы, и получается сложная и не стоящая на месте наука криптология, в которую входит, как сама криптография, так и криптоанализ.
История криптологии
насчитывает около 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.
Оно широко применяется в криптографии и сейчас известно как принцип Керкгоффса. То есть секретными должны быть только ключи шифрования, но не сам алгоритм. Так до этого, например, на Руси
The free excerpt has ended.
