Эволюция шифров и их стойкость

Сферы применения

Криптография как наука возникла еще в 4000 году до нашей эры в Египте. Тогда не существовало эффективных средств передачи информации на дальние расстояния. Чтоб послать сообщение из одного места в другое требовалось снарядить гонца, накормить лошадь. Если расстояние достаточно большое необходимо было менять коней. Это было очень дорогое удовольствие, которое могли позволить лишь немногие.

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

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

Административно-коммуникативные функции

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

Государство, как общественный институт, имеет свои атрибуты на всех уровнях власти. Благодаря ним упрощается управленческая деятельность. Для послов — установлены специальные верительные грамоты, для жителей страны — документы на право собственности недвижимостью, для водителей транспортных средств — водительское удостоверение и так далее…

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

Империя Александра Македонского

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

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

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

Римская империя

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

Цезарь использовал цифру 3 в качестве ключа. С точки зрения безопасности, у него были проблемы с головой. Такого рода, «зашифрованные» сообщения разгадываются с использованием одной страницы блокнота. Существуют схожие и такие же ненадежные варианты: Атбаш, Rot-13, Rot-n и так далее.

Rot-13 — это шифр Цезаря со значением ключа n=13. В Атбаше буквы отражаются относительно средней буквы алфавита. Он изначально предназначен для алфавитов с парным значением символов. Для алфавитов с непарным количеством символов средняя буква не меняется. Указанный факт делает его ещё более незащищенным.

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

Кодировка Rot-13
Работа с кодировкой «ROT-13» в Python

Будьте внимательны, кодировщик Rot-13 в языке программирования Python работает только с ASCII строками. Как видите, со строкой содержащей один русский символ «Ш», он возвращает ошибку. Зная кодировку Unicode, нетрудно написать свой кодировщик поддерживающий символы других национальных алфавитов. Все стандарты Unicode описаны в RFC 5198.

Читайте также: Работа с кодировками в Python

Арабские криптографы

Первую серьезную попытку описать процесс расшифровки зашифрованных сообщений совершил арабский ученый криптограф Аль-Кинди в IX веке. В его книге «Трактат о дешифровке криптографических сообщений» впервые описано применение частотного анализа. Он создал таблицу относительной частоты появления букв в арабских словах. Благодаря его исследованиям арабские криптографы легко разгадывали все шифры однобуквенной замены. Для расшифровки сообщений подсчитывалась частота встречи букв в зашифрованых сообщениях. Частоты появления букв сравнивались с частотами появления букв в словаре. В результате, текст закрытого сообщения становился заметным.

Cube Mixer
Относительная частота букв в словах приложения Cube Mixer

На рисунке выше, изображена относительная частота появления букв в английских словах первой версии мобильного приложения Cube Mixer от CubbyDev.com. Как вы вы видите, чаще всего в английских словах встречаются гласные «A» и «E». Собственно, опыт арабов может быть полезен в отыскании фраз этой словесной головоломки.

Cube Mixer screenshot
Cube Mixer

Алгоритм эффективного решения данной головоломки с использованием метода Аль-Кинди:

  1. Отыщите куб и выберите грань содержащую букву из списка наиболее вероятных букв, подсветите его;
  2. Крутите кубы находящиеся рядом выбирая буквы в порядке спадания частоты и подсвечивайте их продолжая цепочку;
  3. Если выстроить слово не удалось вернитесь на первый шаг.

Средневековая Европа

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

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

Количество людей и городов увеличивалось и знания начали расходится. Людям стало проще обходить католические табу посредством использования шифров. Возникали тайные общества которые посвящали своих единомышленников во многие секреты и тайны доступные только для правителей.

Неправительственные организации

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

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

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

Философы просветители и становление первой республики

Франция во времена первой республики имела достаточное количество образованных людей. Среди них такие люди как: Пьер Гаспар Шомет, Жак-Рэне Эбер, Дантон, Максимильян Робеспьер и другие. Все они были очень образованные гуманитарии и стояли у истоков первой республики, использовали достижения криптографии. Но не один алгоритм не способен скрыть человеческую природу. Маниакальная жажда власти скрывалась за иллюзорными утопическими лозунгами: «Cвобода! Равенство! Братство!».

Они получили власть и одновременно стали её жертвами. Тем не менее, были и те кому удалось продолжить свой жизненный путь, несмотря на изменчивость того времени. Таким был знакомый Робеспьера, Лазар Карно (Lazare Carnot), входивший вместе с ним и Фуше в литературное общество поэтов «Розати». Кроме всего, Карно был ещё и прекрасным математиком. Холодный рассудок и страсть к науке позволили ему выжить и оставить после себя не менее знаменитого сына Сади Карно. В честь него назван термин в физике «цикл Карно».

Карта карно
Один из методов минимизации булевых функций

Французская фамилия «Carnot» (буква «т» не читается) видоизменилась в английскую созвучную ей Carnaugh. Через столетие она прославила себя ещё раз. Морис Карно создал карты Карно упрощающие булевы функции. Все люди закончившие ИТ специальности о них слышали и использовали. Но не все знают что он запатентовал импульсное кодирование (pulse code modulation). Его достижением является формат аудио записи PCM.

Декабристы и большевики

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

В тюремных камерах, они применяли тюремный шифр. В книжке Шахановой М.Е. «Современные технологии информационной безопасности. Учебно-методический комплекс» написано о князе Одоевском, который не смог установить связь с декабристами по той причине, что не помнил порядок букв в сокращенном алфавите. Дело в том, что сокращенный вариант алфавита 5х5 не имеет следующих букв «Ё», «Й», «Х», «Ч», «Щ», «Ь», «Ъ», «Э».

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

Советские диссиденты и тюремный шифр

Советские диссиденты перестукивались в камерах. Ниже приведена полная таблица для русского алфавита. Что бы передать букву «Я» медленно стучали 6 раз, и затем быстро 3 раза. Передать предложение которое содержит много букв «Я» и остаться незамеченным было достаточно сложно.

123456
1АБВГДЕ
2ЁЖЗИЙК
3ЛМНОПР
4СТУФХЦ
5ЧШЩЪЫЬ
6ЭЮЯ

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

Абсолютно стойкие шифры гаммирования и их недостатки

Абсолютная стойкость доказана только для симметричного шифрования Клодом-Шенноном в работе «Математическая теория криптографии», которая опубликована после Второй мировой войны. Согласно ней для сокрытия информации предложено использовать операцию «ИСКЛЮЧАЮЩЕЕ ИЛИ», или xor. Каждой букве отрытого сообщения соответствует буква последовательности гаммы. Основные требования для достижения абсолютной стойкости:

Веб приложение для xor-шифрования
XORcist
  1. Ключ должен использоваться всего один раз;
  2. Длинна ключа не должна быть короче количества букв в сообщении;
  3. Ключ должен быть случайной последовательностью букв, цифр, знаков;
  4. После расшифровки полученный ключ должен уничтожаться.

Основные недостатки:

  1. Для длинных сообщений нужно использовать длинную гамму (неинформативная гамма длинною в сообщение давала избыточность равную 100%);
  2. Пароли хранились на странице блокнота из-за чего он назван методом одноразовых блокнотов;
  3. Обмен паролей на расстояние требует наличие безопасного канала связи.

Основное преимущество простота реализации. Можете попробовать XORcist. XORcist реализует xor-шифрование онлайн: https://apps.cubbydev.com/web/XORcist.html

Асиметричное шифрование и государство нашего времени

gnupg app
Приложение для конфиденциальной переписки

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

Первую широкодоступную программу реализующую данную концепцию написал Филипп Циммерман. За что был подвергнут давлению со стороны властей. Ему и еще некоторым другим энтузиастам инкриминировали нарушение регуляторного акта по экспорту вооружений «The Arms Export Control Act and the International Traffic in Arms Regulations». На суде он отрицал свою причастность к передаче своей программы заграницу…

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

e-governance
Электронные государственные услуги

С её помощью можно однозначно идентифицировать гражданина, проголосовать на выборах (в некоторых странах), дистанционно отправить налоговую отчетность. Но самое главное преимущество, безусловно, безопасный Интернет. Протокол «https» не дает мошенникам возможность подмены информации «атакой человек по середине».

Механизм асимметричного шифрования и его надежность

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

Тем не менее, их существование принимается как гипотеза. Одно ясно наверняка, если найдется счастливчик который ускорит процесс расшифровки данного шифра, то это изменит мир ИТ. Поэтому специалисты рекомендуют устанавливать небольшой срок действия ЭЦП (не превышающий 10 лет). Именно поэтому, срок действия современных удостоверений личности не превышает 10 лет.

Выводы

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

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

Оставьте комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *