XXVII Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Создание онлайн-среды по криптографии и оценке криптостойкости

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Марков Я.А. 1

---

1Университетский лицей №1523 предуниверситария НИЯУ МИФИ

Троицкий И.И. 1

---

1МГТУ им. Н.Э.Баумана

Работа в формате PDF

464.9 KB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

Введение

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

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

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

Во-вторых, многие классические шифры активно используются в сфере ИТ. Например, многие устройства (в том числе устройства фирмы CISCO) используют для скрытия программного кода именно шифр Цезаря.

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

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

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

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

- основное внимание уделяется шифрованию и расшифрованию, то есть опускается вопрос проверки стойкости шифров (дешифрованию);

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

ОСНОВНАЯ ЧАСТЬ

Цели и задачи научно-исследовательской работы

В работе под криптографией понимаются методы по шифрованию, расшифрованию, а также по дешифрованию.

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

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

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

1. Написать и проверить программы на JavaScript по шифрованию, по расшифрованию и по дешифрованию;

2. Провести исследование методов дешифрования и разработать эффективный подход к дешифрованию;

3. Сделать веб-сайт и разместить там программы по криптографии.

При решении указанных задач применялись следующие методы исследования:

1. Изучение тематики криптографии путем практического освоения материалов (решения квестов) на стендах в музее криптографии¹, чтения учебной литературы, в первую очередь по классическим шифрам.

2. Конструирование путем:

- программирования программ на языках программирования JavaScript и Python;

- веб-программирования веб-сайта в среде WordPress;

- разработка оригинального алгоритма дешифрования.

3. Экспериментирование по шифрованию, расшифрованию и оценке эффективности различных способов дешифрования.

Используемые технологии и среды

В работе были использованы следующие технологии и среды.

Для написания программ использовался язык JavaScript (для онлайн-программ) и Python 3 (часть репозитория для обмена).

Для написания сайта была использована система создания и управления сайтом - WordPress 6.4.1.

Разработка велась на компьютере MSI в среде Windows 11.

Разработка программ по шифрованию и расшифрованию

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

Для начального исследования были выбраны популярные классические шифры, как перестановочные (обобщенный шифр Цезаря и диск Альберти), так и перестановочные (шифр Атбаш и шифр Вернама). Выбор шифров в каждом классе был определен требованием от «простого к сложному».

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

Рисунок 1. Демонстрация шифра Цезаря

Диск Альберти – это развитие шифра Цезаря, когда сдвиг очередного символа меняется в соответствии с ключом (ключ задает несколько сдвигов). Диск Альберти является аналогом современных дисковых устройств по шифрованию!

Шифр Атбаш – это популярный подстановочный шифр, в котором правило подстановки определяется заменой по правилу обратной индексации символов в алфавите.

Шифр Вернама – это шифр, в котором символы исходного текста складываются по правило XOR с символами ключа. Если ключ больше или равен длине открытого текста, то считается (согласно теореме Клода Шеннона), что шифр взломать нельзя!о

В рамках исследования разработаны указанные на языке JavaScript (рис. 2), а часть программ первоначально писались на Python и размещены на сайте в разделе репозитория.

Рисунок 2. QR-коды для шифрования и расшифрования

Исследование программ дешифрования

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

В литературе описаны несколько методов дешифрования. В работе исследовано три:

- прямой перебор;

- дешифрованием по известной фразе;

- частотный анализ.

Выбор обоснован следующим:

1. Прямой перебор (brute force attack) является самым простым, но самым длительным. Суть его состоит в переборе всевозможных ключей, в данном случае сдвигов. Считается, что эффективность любых других способов дешифрования (взлома) оценивается относительно эффективности прямого перебора. Можно привести пример, ключ из 8 символов имеет почти квинтиллион комбинаций². Взлом подбора ключей поэтому возможен только на специальных вычислителях.

2. Дешифрование по известной фразе упрощает ручной анализ прямого перебора, облегчая жизнь криптоаналитика. Такой способ имеет исторические корни, например, описаны способы взлома, если предполагали, что в зашифрованном тексте есть известная фраза, например, приветствие или обращение. Наиболее известна методика взлома немецких шифров времен II мировой войны - «Eins-алгоритм». Данный алгоритм предложил математик Алан Тьюринг, заметив, что в немецких шифровках наиболее часть используется немецкое слово один (eins)¹.

3. Что касается частотного анализа, то считается, что такой анализ, как считается, позволяет дешифровать любой классически шифр³. Суть частотного анализа состоит в том, что собирается статистика по использованию букв алфавита, а при дешифровании символы зашифрованного текста заменяются в соответствии с частотой их использования. К примеру, в интернет доступны словари частотности русских букв⁴ (Рисунок 3) и других символов⁵.

Рисунок 3. Статистика русских букв согласно исследованию

Разработка программ по дешифрованию

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

- программа дешифрования (взлома) шифра Цезаря прямым перебором,

- программа эвристического (умного) дешифрования шифра Цезаря, которая включала комбинацию прямого перебора и сравнения по часто используемой фразе (без генерации статистик эвристический частотный анализ совпадает к классическим);

Первоначально указанные программы были написаны автором на языке Python (их можно посмотреть на сайте в разделе «Репозиторий»⁶, затем (после исследования) их модификации были запрограммированы на языке JavaScript.

Рисунок 4. QR-код для дешифрования шифра Цезаря

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

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

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

Таблица 1.

Пример применения частотного анализа

Разработка экспертного алгоритма и оценка его эффективности

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

В исследовании была сформулирована гипотеза, что при подборе статистик можно угадать символы в зашифрованной фразе. Поэтому в рамках исследования был придуман эвристический частотный анализ. Суть его состоит в генерации множества статистик. При этом расшифровки с помощью данных статистик сравниваются с набором наиболее часто используемых слов (рис. 5). Эксперимент показал, что фрагмент текста в 200 символов начинается восприниматься аналитиком от 50 генераций и более.

В настоящее время в интернет не найдено аналога подобного алгоритма.

Рисунок 5. QR-код для дешифрования методом эвристического частотного анализа

Таблица 2.

Пример применения эвристического частотного анализа

Разработка веб-сайта

В рамках исследования автором был зарегистрирован домен cyberbugz.ru. А сам сайт был запрограммирован в среде WordPress (Рисунке 6). Выбор WordPress был определен не только популярностью, но и удобными функциями по управлению сайтом, разнообразием плагинов, возможностью разграничения функций администраторов, системными возможностями и пр.

Рисунок 6. Начальная страница веб-сайта

Обзор литературы, новизна, достоверность

В национальной электронной библиотеке elibrary.ru было найдено 23 научные статьи по анализу классических шифров⁷, однако доступный текст статей представлен лишь в [1-3, 5-9]. Во всех указанных статьях рассмотрены лишь вопросы шифрования и расшифрования. По сути, в интернет отсутствует предлагаемый автором вариант обеспечения шифра тремя средствами: шифрования, расшифрования и дешифрования. Следует отметить, что в интернет дано описание метода (на языке Python) частотного анализа на сайте www.habr.com [10], выполненное в сравнении с информацией, данной в Википедии⁸, однако и в нем есть недостатки (учтены лишь буквы русского языка, не рассмотрен способ использования частотного анализа при переборе - не был просчитан пробел). Доказано, что данный метод не работает для небольших сообщений [4].

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

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

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

ЗАКЛЮЧЕНИЕ

Таким образом в работе создан оригинальный веб-сайт с криптографическими программами, в том числе:

1. Разработаны программы для шифрования, расшифрования, дешифрования (программы прямого перебора и интеллектуального поиска).

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

3. Создан сайт, посвященный тематике безопасности информации.

В рамках исследования были сделаны следующие выводы:

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

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

Список литературы

1. Адаев, Р. Б. Программная реализация шифрования текстовых фраз / Р. Б. Адаев // Инженерный вестник Дона. 2021. № 11 (83). С. 172-180.

2. Ачекеев, К. С. Создание компьютерной программы для шифрования текстовой информации / К. С. Ачекеев, У. Т. Керимов, А. Б. Салижанов, У. Б. Салижанова // Известия ВУЗов Кыргызстана. - 2022. - № 2. - С. 45-47.

3. Гумерова, Л. З. Взлом шифра Цезаря методом «грубой силы» / Л. З. Гумерова, Г. Н. Аглямзянова, Е. С. Маисеева // В сборнике: Лучшие практики общего и дополнительного образования по естественно-научным и техническим дисциплинам. материалы II Всероссийской научно-практической конференции, посвященной памяти академика РАН К.А. РАН К.А. Валиева. - Казань, Казанский (Приволжский) федеральный университет, 2022. С. 157-163.

4. К вопросу о способах дешифрования классических шифров / Марков Я.А. // В сборнике: Безопасные информационные технологии. Сборник трудов Двенадцатой международной научно-технической конференции. Москва, 2023. С. 165-169.

5. Карпенкова, Н. В. Использование модулярной математики в криптографии / Н. В. Карпенкова // Электронный научно-практический журнал Культура и образование. - 2015. - № 1 (17). - С. 26.

6. Кузьминых, Е. С. Анализ симметричных методов шифрования, проблемы и пути возможного их решения / Е. С. Кузьминых, М. А. Маслова // Научный результат. Информационные технологии. - 2023. - Т. 8. - № 1. - С. 38-45. - DOI: 10.18413/2518-1092-2022-8-1-0-3.

7. Лепшокова, А. Р. Разработка интерактивного приложения для наглядного представления шифра Цезаря / А. Р. Лепшокова // В сборнике: Актуальные проблемы методики обучения информатике и математике в современной школе. Материалы Международной научно-практической интернет-конференции. – М.: МПГУ, 2020. - С. 493-498.

8. Михаэлис, В. В. Шифрование в среде MS Excel для безопасной передачи и хранения данных / В. В. Михаэлис, С. И. Михаэлис // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. - 2023. - №04/2. - С. 99-102. - DOI: 10.37882/2223-2966.2023.04-2.22.

9. Шарейко, В. В. Использование программы с реализацией алгоритмов симметричного шифрования для олимпиадных заданий / В. В. Шарейко // В сборнике: Информационные технологии в образовательном процессе вуза и школы. Материалы ХIV Всероссийской научно-практической конференции. – Воронеж: ВГПУ, 2020. - С. 384-388.

10. Wadik69, В. Дешифровка текста методом частотного анализа. / В. Wadik69 // Криптография. Шифрование и криптоанализ, 2020. - [Электронный ресурс]. – Режим доступа: https://habr.com/ru/articles/513926/