Применение простых чисел в криптографии и защите информации

 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ЛУГАНСКОЙ НАРОДНОЙ РЕСПУБЛИКИ

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ

ДОПОЛНИТЕЛЬНОГО ОБРАЗОВАНИЯ 

ЛУГАНСКОЙ НАРОДНОЙ РЕСПУБЛИКИ

«СВЕРДЛОВСКИЙ ЦЕНТР ДЕТСКОГО И ЮНОШЕСКОГО ТВОРЧЕСТВА

«МЕЧТА»

Отделение: физико-математическое, 

экономики и астрономии

                                                               Секция: прикладная математика

Применение простых чисел в криптографии и защите информации

 Работу выполнила:

Григоренко Варвара Сергеевна, 

ученица  9 класса

Государственного бюджетного общеобразовательного учреждения Луганской Народной Республики «Червонопартизанская средняя школа №2 имени Сергея Чепижко»

Научный руководитель: 

Лебединская Наталия Ивановна, 

учитель математики

Государственного бюджетного общеобразовательного учреждения Луганской Народной Республики «Червонопартизанская средняя школа №2 имени Сергея Чепижко»

Свердловск, 2025

Содержание

Введение……………………………………………………………………..                                                                                                   Раздел 1. Теоретические основы…………………………………………. 1.1 Шифрование и дешифрование..……………………………………………..                                  1.2 Значение ключей в криптографии…………………………………  1.3 Примеры применения криптографии в повседневной жизни …..                                                                                                                  Раздел 2. Простые числа и их роль в защите информации ……………..  Что такое простые числа ………………………………………….  Почему они служат основой для безопасности данных …………  Примеры использования простых чисел в криптографии ……… Раздел 3. RSA: метод шифрования на основе простых чисел…………….. 3.1 Как работает метод RSA ………………………………………….. 3.2 Почему RSA считается надежным методом шифрования ……… 3.3 Примеры применения RSA для защиты информации ………….. Раздел 4. Практические задания и эксперименты ………………………  Шифрование и дешифрование сообщений с использованием простых чисел……………………………………………………….  Создание своего шифровального алгоритма на основе простых чисел ………………………………………………………………… Заключение…………………………………………………………………                                                                                                 Список используемой литературы………………………………………..

3 4 4 4 5 6 6 6 7 8 8 8 9 10 10 11 13 14

 

ВВЕДЕНИЕ

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

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

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

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

Цель моей работы шифрование и дешифрование сообщений с использованием простых чисел, и создание своего шифровального алгоритма на основе простых чисел.

    Задачи работы:

1. Познакомиться с основами криптографии.
2. Изучить роль простых чисел в защите информации.
3. Рассмотреть RSA: метод шифрования на основе простых чисел.
4. Сделать выводы о важности понимания криптографии и простых чисел для безопасности информации.

РАЗДЕЛ 1. ТЕРЕОТИЧЕСКИЕ ОСНОВЫ

1.1 Шифрование и дешифрование

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

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

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

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

•  Значение ключей в криптографии

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

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

Ключи в криптографии обладают следующими свойствами:

1. Конфиденциальность: ключи обеспечивают конфиденциальность данных, так как без знания правильного ключа невозможно дешифровать зашифрованное сообщение.
2. Аутентификация: ключи могут использоваться для проверки подлинности отправителя или получателя сообщения.
3. Целостность: ключи помогают защитить данные от изменений или подделок в процессе передачи.
4. Надежность: использование сложных и надежных ключей повышает уровень безопасности криптографических систем.

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

 

1.3 Примеры применения криптографии в повседневной жизни

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

1. Шифрование сообщений: Одним из наиболее распространенных примеров применения криптографии является шифрование сообщений в мессенджерах, электронной почте и других онлайн-сервисах. Например, когда вы отправляете конфиденциальное сообщение через WhatsApp или Signal, оно автоматически шифруется с использованием сильных криптографических алгоритмов, чтобы обеспечить конфиденциальность содержимого.
2. Онлайн-банкинг и электронные платежи: При совершении онлайн-транзакций, таких как платежи через интернет-банкинг или использование электронных кошельков, криптография играет ключевую роль в обеспечении безопасности финансовых данных. SSL-шифрование (Secure Sockets Layer) используется для защиты передачи данных между вашим устройством и сервером банка.
3. Пароли и аутентификация: Криптография также используется для хранения и защиты паролей пользователей. При входе в аккаунт или при совершении онлайн-транзакций, ваш пароль шифруется и хранится в зашифрованном виде, чтобы предотвратить несанкционированный доступ к вашей учетной записи.
4. Безопасность сетей Wi-Fi: Когда вы подключаетесь к защищенной Wi-Fi-сети, данные, передаваемые между вашим устройством и маршрутизатором, шифруются с использованием протокола WPA (Wi-Fi Protected Access) или WPA2 для предотвращения перехвата информации злоумышленниками.
5. Цифровые подписи: Криптография также используется для создания цифровых подписей, которые подтверждают подлинность документов, электронных сообщений и транзакций. Цифровая подпись гарантирует, что информация не была изменена после подписания и что она была создана конкретным отправителем.

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

РАЗДЕЛ 2. ПРОСТЫЕ ЧИСЛА И ИХ РОЛЬ В ЗАЩИТЕ ИНФОРМАЦИИ

2.1 Что такое простые числа

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

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

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

Простые числа можно найти путем проверки всех чисел до квадратного корня данного числа на делимость. Если число не делится нацело ни на одно из этих чисел, то оно является простым. Например, число 7 является простым, так как оно не делится нацело ни на 2, ни на 3 (квадратный корень из 7 округленный вниз равен 2).

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

2.2 Почему они служат основой для безопасности данных

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

1. Уникальность: Простые числа имеют только два делителя — 1 и само число. Это делает их более сложными для факторизации и анализа, что делает их хорошим выбором для создания безопасных шифров.
2. Сложность разложения на множители: Чем больше простое число, тем сложнее его разложить на множители. Это свойство делает простые числа идеальным выбором для создания криптографических ключей, которые сложно взломать.
3. Безопасность: Использование простых чисел в криптографии обеспечивает высокий уровень безопасности и защиты данных. Алгоритмы, основанные на простых числах, обладают стойкостью к различным методам взлома.
4. Математическая основа: Простые числа широко изучены в математике, их свойства и характеристики хорошо известны. Это позволяет разработать эффективные криптографические алгоритмы на основе простых чисел.

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

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

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

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

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

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

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

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

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

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

РАЗДЕЛ 3. RSA: МЕТОД ШИФРОВАНИЯ НА ОСНОВЕ ПРОСТЫХ ЧИСЕЛ

3.1 Как работает метод RSA

           Метод RSA (Rivest–Shamir–Adleman) является одним из наиболее распространенных алгоритмов шифрования в современной криптографии. Он основан на математических принципах теории чисел и использует понятие простых чисел для обеспечения безопасности передачи информации.

          Для работы метода RSA необходимо сгенерировать два простых числа, которые будут служить в качестве закрытого и открытого ключей. Первым шагом является выбор двух больших простых чисел p и q. Затем вычисляется их произведение n = p * q, которое будет использоваться в качестве модуля для шифрования и дешифрования данных.

          Далее необходимо найти значение функции Эйлера от числа n, которое равно (p-1)*(q-1). Затем выбирается целое число e, взаимно простое с функцией Эйлера и меньшее ее значения. Число e становится открытым ключом для шифрования данных.

         Для шифрования сообщения M в число C используется следующая формула: C = Me mod n. Полученное зашифрованное сообщение C передается получателю.

         Для дешифрования зашифрованного сообщения C получатель использует закрытый ключ d, который является обратным по модулю к числу e по модулю функции Эйлера. Для дешифрования используется формула: M = Cd mod n.

• Почему RSA считается надежным методом шифрования

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

          RSA использует понятие простых чисел, которые не имеют делителей, кроме единицы и самих себя. При генерации ключей для RSA выбираются два больших простых числа p и q. Умножение этих чисел даёт модуль n, который используется для шифрования и дешифрования данных. Затем находится значение функции Эйлера от числа n, которое играет важную роль в определении открытого и закрытого ключей.

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

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

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

•  Примеры применения RSA для защиты информации

RSA (Rivest-Shamir-Adleman) является одним из самых распространенных алгоритмов шифрования, который используется для защиты конфиденциальности информации в сети Интернет, электронной почте, банковских транзакциях и других областях. Ниже приведены примеры применения RSA для защиты информации:

1. Шифрование данных: RSA позволяет отправителю зашифровать данные с использованием открытого ключа получателя. Только обладатель соответствующего закрытого ключа может расшифровать сообщение. Это обеспечивает конфиденциальность информации при передаче по открытым каналам связи.
2. Цифровые подписи: RSA также используется для создания цифровых подписей, которые позволяют проверить подлинность отправителя и целостность сообщения. Отправитель создает подпись с использованием своего закрытого ключа, а получатель проверяет подпись с помощью открытого ключа отправителя. Это гарантирует, что сообщение не было изменено и было отправлено именно указанным отправителем.
3. Аутентификация: RSA может быть использован для аутентификации пользователей в системах безопасности. Пользователь может предоставить свой цифровой сертификат, содержащий открытый ключ RSA, чтобы доказать свою личность. Система может проверить подлинность сертификата, используя общедоступный ключ сертификационного центра.
4. Шифрование файлов: RSA может быть применен для шифрования файлов на компьютере или в облачном хранилище. Пользователь может создать пару ключей RSA, чтобы зашифровать свои файлы перед сохранением их на диске. Только обладатель закрытого ключа сможет расшифровать файлы для доступа к их содержимому.

РАЗДЕЛ 4. ПРАКТИЧЕСКИЕ ЗАДАНИЯ И ЭКСПЕРИМЕНТЫ

4.1 Шифрование и дешифрование сообщений с использованием простых чисел

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

Допустим, у нас есть сообщение «ЗАЩИТА», которое мы хотим зашифровать с использованием простых чисел. Для этого мы можем присвоить каждой букве числовое значение (например, A=1, Б=2, В=3 и т.д.):

— З = 9

— А = 1

— Щ = 27

— И = 10

— Т = 20

— А = 1

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

— З: 9 * 2 = 18

— А: 1 * 3 = 3

— Щ: 27 * 2 = 54

— И: 10 * 3 = 30

— Т: 20 * 2 = 40

— А: 1 * 3 = 3

Таким образом, зашифрованное сообщение будет выглядеть как » 18 3 54 30 40 3″.

Для дешифрования сообщения получатель должен знать используемые простые числа (2 и 3) и обратно преобразовать числа в буквы, разделив их на соответствующие простые числа:

— 18 / 2 = 9 (З)

— 3 / 3 = 1 (А)

— 54 / 2 = 27 (Щ)

— 30 / 3 = 10 (И)

— 40 / 2 = 20 (Т)

— 3 / 3 = 1 (А)

Таким образом, полученное дешифрованное сообщение будет «ЗАЩИТА».

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

4.2 Создание своего шифровального алгоритма на основе простых чисел

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

1. Выбор простых чисел p и q: Начните с выбора двух больших простых чисел p и q. Эти числа будут использоваться для генерации открытого и закрытого ключей.
2. Вычисление произведения n: Вычислите произведение n = p * q. Это будет ваш модуль шифрования и дешифрования.
3. Вычисление функции Эйлера φ(n): Вычислите функцию Эйлера φ(n) для числа n. Функция Эйлера определяется как количество целых чисел от 1 до n-1, взаимно простых с n.
4. Выбор открытого ключа e: Выберите целое число e, которое является взаимно простым с φ(n) и меньше φ(n). Обычно выбирают значение e = 65537, которое является распространенным выбором.
5. Вычисление закрытого ключа d: Найдите число d, которое удовлетворяет условию (d * e) mod φ(n) = 1. Это число будет вашим закрытым ключом.
6. Шифрование сообщения: Для шифрования сообщения m используйте открытый ключ (e, n) и вычислите c = me mod n.
7. Дешифрование сообщения: Для дешифрования зашифрованного сообщения c используйте закрытый ключ (d, n) и вычислите m = cdmod n.
8. Тестирование алгоритма: Протестируйте свой алгоритм на различных сообщениях, чтобы убедиться, что он работает правильно.

Создадим простой шифровальный алгоритм на основе простых чисел,  назовем наш алгоритм «Простой Шифр 14». Мы будем использовать два простых числа p = 17 и q = 19.

1. Выбор простых чисел p и q:

   — p = 17

   — q = 19

2. Вычисление произведения n:

   — n = p * q = 17 * 19 = 323

3. Вычисление функции Эйлера φ(n):

   — φ(n) = (p-1) * (q-1) = 16 * 18 = 288

4. Выбор открытого ключа e:

   — Выберем e = 5 (взаимно простое с φ(n) и меньше φ(n))

5. Вычисление закрытого ключа d:

   — Найдем d такое, что (d * e) mod φ(n) = 1

   — d = 173 (поскольку (173 * 5) mod 288 = 1)

6. Шифрование сообщения:

   — Предположим, что мы хотим зашифровать сообщение m = 10

   — Зашифруем сообщение: c = me mod n = 105 mod 323 = 100000 % 323 = 267

7. Дешифрование сообщения:

   — Для дешифрования используем закрытый ключ (d, n)

   — Дешифруем сообщение: m = cd mod n = 267173 mod 323 = 10

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

 

Заключение

Понимание криптографии и простых чисел имеет огромное значение для обеспечения безопасности информации в современном мире. Вот несколько ключевых выводов:

1. Шифрование информации: Криптография позволяет защищать данные, делая их недоступными для несанкционированного доступа. Шифрование основано на математических принципах, включая использование простых чисел, что делает алгоритмы шифрования надежными.
2. Безопасность коммуникаций: При передаче конфиденциальной информации через сети Интернет или другие каналы связи, криптография помогает защитить данные от перехвата и подмены. Простые числа используются в алгоритмах шифрования для создания ключей и обеспечения безопасности передачи данных.
3. Цифровые подписи: Криптография также позволяет создавать цифровые подписи, которые подтверждают подлинность отправителя и целостность данных. Простые числа используются при генерации ключей для цифровых подписей.
4. Защита от атак: Понимание простых чисел и их роли в криптографии поможет лучше понять уязвимости и методы атак на шифровальные системы. Это поможет разработчикам и специалистам по безопасности создавать более надежные системы защиты.
5. Обучение и осведомленность: Обучение основам криптографии и простым числам поможет людям лучше понимать важность безопасности информации и принимать соответствующие меры для защиты своих данных.

 

Список используемой литературы

 

1. Бабаш, А. В. История криптографии. Часть I / А.В. Бабаш, Г.П. Шанкин. — М.: Гелиос АРВ, 2002. — 240 c. 
2. Баричев, С. Г. Основы современной криптографии / С.Г. Баричев, В.В. Гончаров, Р.Е. Серов. — Москва: СИНТЕГ, 2011. — 176 c. 
3. Жданов, О. Н. Методика выбора ключевой информации для алгоритма блочного шифрования / О.Н. Жданов. — М.: ИНФРА-М, 2015. — 607 c.
4. Криптография: скоростные шифры / А. Молдовян и др. — М.: БХВ-Петербург, 2002. — 496 c. 
5. Молдовян, Н. Криптография: от примитивов к синтезу алгоритмов / Н. Молдовян, А. Молдовян, М. Еремеев. — М.: БХВ-Петербург, 2004. — 448 c.