Математические основы криптографии

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

Аракелян Г.С. 1

---

1МБОУ "Лицей №9 имени К. Э. Циолковского"

Рылова И.Г. 1

---

1МБОУ "Лицей №9 имени К. Э. Циолковского" города Калуги

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

162.2 KB

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

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

Введение.

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

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

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

Задачи исследования:в ходе исследования нужно решить следующие задачи:

Изучить литературу по криптографии, выяснить значение новых терминов

Узнать, где применяется криптография, и почему она так важна

Изучить известные шифры, привести примеры их использования

Получить навыки написания научно-исследовательской работы

Гипотеза: разные шифры обеспечивают разную степень защиты.

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

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

Криптография (от греч. κρυπτός - «скрытый» + γράφω - «пишу», буквально «тайнопись») – наука о способах шифрования информации с целью защиты ее от незаконного использования. Эта наука занимается созданием и исследованием методов шифрования. Это одна из старейших наук, история которой насчитывает около 4 тысяч лет. История этой науки будет рассмотрена ниже.

Внизу даны 2 фрагмента текста, один – просто набор символов, а второй – зашифрованное сообщение:

Определить, что есть что - невозможно. Первый фрагмент – зашифрованные при помощи алгоритма RC4 с ключом «123456» слова Натана Ротшильда: «Кто владеет информацией – тот владеет миром», а второй – случайные символы.

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

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

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

История криптографии. Периоды.

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

Одними из наиболее известными древними шифрами являются древнесемитский атбаш (приблизительно 600 г. до н. э.), шифр Цезаря (около 100 г. до н. э.), диск Энея (около 400 г. до н. э.)

Выделяют несколько периодов развития криптографии:

Первый период (~3-е тысячелетие до н. э.) ­ — моноалфавитные шифры.

Второй период (IX век на Ближнем Востоке и с XV века в Европе – начало XX века) — полиалфавитные шифры.

Третий период (начало XX века – середина XX века) — электромеханические устройства в работе шифровальщиков. Продолжается использование полиалфавитных шифров.

Четвёртый период (середина XX века – конец 1970-х годов) — переход к математической криптографии. В 1949 году математик Клод Шеннон пишет работу «Теория связи в секретных системах». В ней появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. При создании шифров изучают его уязвимости для различных атак — линейного и дифференциального криптоанализа. До 1975 года криптография остаётся криптографией с секретным ключом.

Современный период развития криптографии (конец 1970-х годов – настоящее время) — криптография с открытым ключом. Широкое распространение криптографии для использования частными лицами. Правовое регулирование использования криптографии частными лицами в разных странах сильно различается — от разрешения до полного запрета.

Коды и шифры. В чём разница?

Термины «кодирование» и «шифрование» имеет разное значение в криптографии. Кодирование – это процесс преобразования текста путём замены одних слов другими. Шифрование – замена букв либо отдельных символов.

Спустя время шифрование стало настолько распространённым, что превратилось в синоним «кодированного письма». Однако если следовать более научным определениям, правильнее будет говорить «шифрование сообщения» (или дешифрование в случае обратного процесса), а не «кодирование сообщения».

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

Если закодировать слово «ПРИВЕТ», мы можем получить «HELLO», переведя его на английский язык. Но если зашифровать, то же слово, сдвинув каждую букву на 3 позиции вправо мы получим «ТУЛЕЗХ». Такой шифр называется Шифр Цезаря.

Простейшие шифры.

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

Шифр Цезаря. Моноалфавитные шифры.

Рис. 1. Шифр Цезаря со сдвигом на 3. Здесь букве B соответствует буква E.

Шифр Цезаря — шифр, в котором каждый символ в открытом сообщении заменяется символом, находящимся на некотором числе позиций левее или правее него в алфавите. Это один из самых простых и наиболее широко известных методов шифрования. Формулы шифрования и дешифрования для шифра Цезаря представлены ниже:

где – символ исходного сообщения;

– ключ (сдвиг);

– мощность алфавита;

– символ зашифрованного сообщения.

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

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

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

Аффинный шифр.

Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами. Формулы шифрования и дешифрования для Аффинного шифра представлены ниже:

где – символ исходного сообщения;

– ключ (сдвиг);

– обратное к a число по модулю n

– мощность алфавита;

– символ зашифрованного сообщения.

При использовании данного шифра появляется вопрос: «Что такое обратное число и как его найти?»

Обратное число к числу по модулю – это такое число, которое удовлетворяет уравнению:

Рассмотрим 2 метода нахождения обратного элемента:

Перебор.

Метод с использованием Малой теоремы Ферма и Теоремы Эйлера:

Малая теорема Ферма - теорема, которая утверждает, что:

Если — простое число и — целое число, не делящееся на p, то делится на , то есть:

Эта теорема является частным случаем теоремы Эйлера.

Теорема Эйлера – теорема, которая утверждает, что:

Пусть , — взаимно простые натуральные числа. Тогда:

где — количество взаимно простых с n чисел от 1 до .

А из этого следует, что , где – обратный к x элемент.

Рассмотрим пример:

Пусть . Тогда:

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

Эпоха математической криптографии.

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

Шифр Хилла.

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

Дэвид Кан в книге «Взломщики кодов» описал шифр Хилла так:

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

Формулы для шифрования и дешифрования:

где – вектор-столбец высоты 3, представляющий открытый текст;

– вектор-столбец высоты 3, представляющий закрытый текст;

– матрица 3 × 3, представляющая ключ шифрования;

– обратная матрица 3 × 3 к матрице ;

– мощность алфавита.

Матрицы.

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

Свойства сложения

– коммутативность

– ассоциативность

– нулевой элемент, то есть

– обратный элемент

Свойства умножения типа (строчная буква – число, заглавная – матрица):

– при умножении на 0 получается нулевой элемент

Свойства умножения типа (две матрицы):

(в основном)

– единичная матрица, то есть

– обратная матрица

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

Шифрование при помощи шифра Хилла.

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

Сообщение :

И алфавит с мощностью .

Сначала нужно найти :

где – алгебраическое дополнение.

Алгебраическое дополнение находится по формуле:

где – минор.

Минор – определитель матрицы, полученный из матрицы   вычёркиванием i-й строки и j-го столбца 

Найдём алгебраические дополнения и :

И наконец зашифруем наше сообщение:

Дешифрование при помощи шифра Хилла.

Давайте расшифруем сообщение. Для этого нужно найти . Ниже представлена формула нахождения обратной матрицы:

где –союзная матрица.

Союзная матрица выглядит так:

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

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

Найдём :

Воспользуемся формулой:

Используем полученное значение в формуле расшифровки:

Заключение. Выводы.

Цели исследования достигнуты. Определены области использования криптографии. Широта областей применения криптографии подтверждает актуальность выбранной темы. Современный уровень развития криптографии подразумевает обязательное использование математических методов для повышения криптографической стойкости применяемых шифров. Гипотеза о том, что различные шифры обеспечивают различную степень защиты, подтверждается приведённым историческим анализом различных шифров. Так, например, шифр Хилла обеспечивает более высокую степень защиты, чем шифр Цезаря. Задачи, поставленные в данном исследовании, решены полностью. Исследование по данной теме открывает хорошие перспективы для дальнейшего изучения.

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

Алгебраические дополнения и миноры. Виды миноров и алгебраических дополнений — https://math1.ru/education/matrix/minor.html

Белоусов И. В. МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ: учебное пособие по линейной алгебре. / Кишинев: 2006/.

Видеокурс «Математические основы криптографии». CryptoFun [ IT ] — https://youtu.be/DmeyD2vSSwI

Дэвид Кан. Взломщики кодов. — Центрполиграф, 2000 год. — 480 с. — (Секретная папка). — 10 000 экз. — ISBN 5-227-00678-4.

Криптография: история шифровального дела —https://rostec.ru/news/kriptografiya-istoriya-shifrovalnogo-dela/

Мир математики: в 40 т. Т.2: Жуан Гомес. Математики, шпионы и хакеры. Кодирование и криптография. / Пер. с англ. – М.: Де Агостини, 2014. – 144 с.

Симметричное шифрование — https://encyclopedia.kaspersky.ru/glossary/symmetric-encryption/

Фильм «Игра в имитацию». Режиссёр - Мортен Тильдум

Формулы для вычисления определителей второго и третьего порядков. Примеры вычисления определителей второго и третьего порядков — https://math1.ru/education/matrix/det23.html

Эл Свейгарт Криптография и взлом шифров на Python.: Пер. с англ. – СПб.: ООО «Диалектика», 2020. – 512 с. – Парал. тит. англ.