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

Старт в науке

Разгадать загадку...

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

Новохатский Д.А. 1

---

1МБОУ СОШ № 7 с УИОП

Астахова Т.П. 1

---

1МБОУ СОШ № 7 с УИОП

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

194.7 KB

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

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

ВВЕДЕНИЕ

«…Классическая музыка по радио прервалась, и голос диктора стал зачитывать цифры, которые Штирлиц быстро записывал в аккуратные колонки… «Для него эти цифры всего лишь цифры», подумал Штирлиц. Когда сообщение закончилось, Штирлиц взял с полки томик Шиллера, открыл на нужной странице и начал превращать цифры в слова…»[7].

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

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

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

Цель – подтвердить значение математики в вопросах шифрования информации.

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

Объект исследования – шифровальная машина Энигма.

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

Для достижения поставленных целей в работе необходимо решить следующие задачи:

Раскрыть основное понятие науки «криптология» и ее двух составляющих – криптографии и криптоанализа.

Раскрыть взаимосвязь математики и криптологии.

Изучить принципы шифрования информации, используемой в шифровальной машине Энигма.

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

В процессе проведения исследования использовалась литература по криптологии, интернет-ресурсы, для подготовки презентации – программы Prezi и PowerPoint.

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

МАТЕМАТИКА И ШИФРЫ

«…едва ли разуму человека дано загадать такую загадку, которую разум другого его собрата, направленный должным образом, не смог бы раскрыть…»

Эдгар Алан По

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

Таблица 1

Рис. 1

Здесь сразу хотелось бы отметить одну особенность. Знакомые всем слова «код» и «шифр» не являются синонимами. Код – это замена каждого слова в сообщении кодовым словом или символом. А шифр – уже замена каждой буквы в сообщении буквой или символом шифра. Эти два понятия принято различать по целям применения: шифрование предназначено для скрытия информации, а кодирование – для удобства хранения и передачи различных данных. И в данной работе мы будем говорить именно о шифровании и шифрах.

На первый взгляд может показаться, что криптология используется только структурами, отвечающими за безопасность информации и связи, такими как военная или банковская служба. Но это не так. В повседневной жизни каждый из нас также сталкивается с элементами, присущими для криптологии. Так, можно с уверенностью утверждать, что 5 = 17, 1 = 13. Многие подумают, что такого просто не может быть. Но только не для, так называемой, часовой математики. В этом можно убедиться, сравнив цифровые и обычные часы со стрелками (таблица 2).

Таблица 2

Как видно, понятия 15-00 и 3 часа дня будут равнозначны. Конечно, это больше относится к бытовому уровню. Профессиональная же криптология, как наука, основывается в первую очередь уже на фундаментальных понятиях математики (теории чисел и вероятности, алгоритмика, матрицы…) и ее самых последних достижениях.

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

Таблица 3

Таким образом, используемый нами шифр Цезаря можно представить в виде функции:

Здесь

х – номер буквы открытого текста в алфавите;

с – номер буквы шифровки в алфавите

число 5 – указывает величину сдвига алфавита.

Величина сдвига может быть любой, поэтому нашу функцию можно представить в виде:

k – величина сдвига,

Дешифрование здесь производится сдвигом в противоположную сторону:

33 – количество букв в русском алфавите

Данный шифр относится к классу, так называемых моноалфавитных подстановок. Однако у него есть существенный недостаток. Использование таблицы частот встречаемости букв алфавита¹позволяет определить один или нескольких символов самого шифра, что бывает достаточным для его вскрытия. Именно частотный анализ является классическим приемом расшифрования – частота появления определенной буквы и даже слога в длинном слове одинаковы в любом языке. Об этом можно прочитать в уже ранее упоминаемых книгах «Пляшущие человечки» Артура Конан Дойля или «Золотой жук» Эдгара По. Нам же шифр Цезаря интересен тем, что именно его можно назвать прототипом машины Энигмы – главной загадки Второй мировой войны.

ШИФРОВАЛЬНАЯ МАШИНА ЭНИГМА

Энигма² – портативная шифровальная машина, которая использовалась для шифрования и расшифрования секретных сообщений. Изначально она создавалась для коммерческих и деловых целей - разработал и запатентовал Энигму в 1918 г. немецкий инженер Артур Шербиус. Но наибольшее распространение она получила в Германии во время Второй мировой войны. Применение Энигмы значительно ускорило процесс связи, исключив применение таблиц, шифр-блокнотов, журналов перекодирования и связанные с ними неизбежные ошибки.

Что же собой представляла Энигма? Это совсем небольшое устройство, сравнимое по размеру с печатной машинкой. Снаружи оно состояло из клавиатуры и панели. При нажатии на клавиатуре буквы А, на панели высвечивалась другая буква, например Q. Это означало, что в шифровке в этом месте вместе А появится Q. Внутри машины располагались рефлектор (отражатель) и три вращающихся диска – ротора (в последствии их количество возросло до 5), которые меняли свое положение после набора каждой буквы. Так при следующем нажатии А на панели высвечивалась уже не Q, а допустим G (Приложение 2).

Оператору, работавшему с Энигмой, не нужно было понимать весь процесс шифрования, он совершался полностью автоматически: необходимо было только установить нужный комплект роторов по заданным местам и задать величину шага, после чего записать три контрольные буквы, указывающие на установку роторов (забегая вперед, можно сказать, что это сыграло важную роль при взломе шифра). Зашифрованное сообщение, которое представляло собой полную абракадабру, передавалось по радио адресату. У немецкого офицера, получавшего его, была точно такая же машина и документ с установками Энигмы. Офицер соединял нужные пары букв, устанавливал диски (роторы) в соответствующее положение, набирал Q и на его панели высвечивалась А. Таким образом происходило расшифрование секретного сообщения.

Нельзя не отметить одно из главных преимуществ Энигмы. В ее набор входило 5 дисков (роторов), использовать можно было любые три и в любом порядке. У каждого диска было 26 начальных положений (по числу букв латинского алфавита). Все это, вместе с возможностью различных вариантов подключения электрических кабелей, давало такое количество комбинаций, которое просто невозможно было перебрать. Всего у Энигмы было 158 962 555 217 826 360 000 возможных изначальных установок (больше квинтиллиона). И каждые сутки, ровно в полночь они менялись.

С точки зрения математики шифр Энигмы – результат перестановок, который невозможно отследить, не зная стартовой установки. Ее функцию шифрования E можно выразить формулой:

Здесь

Р – коммуникационная панель;

U – рефлектор (отражатель);

L, M, R – действия левого, среднего и правого ротора соответственно.

РАЗГАДАТЬ ЗАГАДКУ

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

Именно тогда была обнаружена одна из слабостей Энигмы – для синхронизации установки передающей и принимающей шифровальной машины использовались первые три символа, которые передавались сначала незашифрованными, а потом уже зашифрованными. В выборе данной комбинации сыграла свою роль человеческая слабость – достаточно вспомнить как мы зачастую выбираем пароли для входа в современные информационные системы (123, abc и т.д.). Оператор Энигмы, как правило, использовал памятные для него сочетания. Этим воспользовались польские математики, придумавшие для автоматического перебора комбинаций электрическую машину Bomba³. Однако после того, как немцы увеличили число роторов до 5, польская машина перестала справляться с возложенными на нее задачами. И в 1939 году, так и не сумев преодолеть возникшие трудности, поляки передали все материалы англичанам.

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

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

Кроме того, одним из предположений А. Тьюринга и его команды, что утренние зашифрованные сообщения начинаются с чего-то однотипного, например, с прогноза погоды. Поэтому в зашифрованном сообщении, перехваченном в 6.05 утра, почти наверняка будет присутствовать слово «Wetter» — немецкое слово «погода». А учитывая, что военные сообщения жестко регламентированы, то первые шесть букв зашифрованного сообщения и будут соответствовать немецкому слову «wetter».

Одной из особенностей машины Энигма было то, что буква при шифровании не могла превратиться сама в себя. В связи с чем, перед
английскими математиками встала задача найти такую изначальную установку, чтобы шифр совпал с расшифровкой (словом «wetter»). Было важно определить, какие буквы объединены в пары. И здесь были сделаны два важнейших открытия:

Первое - если пара букв оказывается неправильной, то и все следовавшие из нее, тоже будут неправильные. А, следовательно, их не нужно проверять. Принцип Тьюринга заключался в том, чтобы исключить неправильные варианты и сделать это максимально быстро. Как сказал К. Дойль: «Когда вы исключили невозможное, все, что остается, каким бы невероятным оно ни было, должно быть правдой». Кстати, на уроках математики, некоторые задачи мы также решаем методом исключения.

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

ЗАКЛЮЧЕНИЕ

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

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

Математика – не просто наука, это целое искусство. Так знаменитый математик Пал Эрдёш говорил, что у Бога есть книга, в которой «Бог хранит лучшие доказательства математических теорем» и «если верить в Бога необязательно, то в Книгу верить стоит» [1]. Рассмотренный в работе пример с шифровальной машиной Энигмой, ярчайшим моментом в многовековой истории криптологии, является лишь подтверждением тому, какое огромное влияние оказывает математика на жизнь каждого человека.

Сейчас на уроках математики мы решаем задачи и доказываем теоремы. Возможно, в будущем кто-то из нас спроектирует новый суперкар, а кто-то, подобно А. Тьюрингу, решит сложнейшую математическую задачу или создаст сверхмощный компьютер. «…Нельзя заниматься химией, не зная физики, биологией, не зная химии, геологией, не зная биологии…Но есть одна наука, без которой не возможна никакая другая. Это – математика. Ее понятия, представления и символы служат тем языком, на котором говорят, пишут и думают другие науки…».

Вот такая невероятно полезная наука. Что и требовалось доказать.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

Айгнер М., Циглер Г. Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней. [https://howlingpixel.com]

Адаменко М.В. Основы классической криптологии. Секреты шифров и кодов.

Бабаш А.В., Баранова Е.К. Криптографические методы и средства информационной безопасности. Учебное пособие. Москва, 2010 г.

Жуан Г. Мир математики. № 2. «Математики, шпионы и хакеры. Кодирование и криптография [https://e-libra.ru/read/379010-mir-matematiki-t-2-matematiki-shpiony-i-hakery-kodirovanie-i-kriptografiya.html]

ЗубковА.М.. О применениях математики в криптографии [http://book.etudes.ru/toc/cryptography/]

Коробейников А.Г., Гатчин Ю.А. Математические основы криптологии. Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с.

Литва Н., Райгородский А. Кому нужна математика? Понятная книга о том, как устроен цифровой мир. – М.: Манн, Иванов и Фербер, 2017.

Ходжес Э. Вселенная Алана Тьюринга [https://biography.wikireading.ru/271445]

ПРИЛОЖЕНИЕ 1

Частотность букв русского языка⁵

ПРИЛОЖЕНИЕ 2

Принцип шифрования Энигмы

Р1 – левый ротор

Р2 – средний ротор

Р3 – правый ротор

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