Научный руководитель: Вильданов Алмаз Нафкатович
к.ф.-м.н., Уфимский университет науки и технологий, Нефтекамский филиал
Введение
В современных системах защиты информации электронная подпись является важнейшим инструментом обеспечения подлинности данных и подтверждения авторства цифрового документа. В основе большинства практических реализаций ЭП лежат асимметричные алгоритмы, среди которых RSA остается наиболее распространенным.
Для корректного моделирования работы RSA в среде Maple необходимо переводить текстовые данные в числовую форму, поскольку криптографические вычисления осуществляются над числами. На этом этапе используются процедуры преобразования строк и набор функций Maple.
1. Преобразование текста в числовой формат: функции Maple и их назначение
Поскольку криптографический алгоритм работает с целыми числами, текст необходимо предварительно перевести в кодированную последовательность. В Maple это реализуется с помощью специально написанных процедур str_to_num и num_to_str.
• proc – конструкция для объявления пользовательской процедуры;
• Ord – преобразует символ в его числовой ASCII-код;
• Char – выполняет обратное преобразование к символу;
• length – определяет количество символов в строке;
• parse – превращает строку цифр в целое число;
• convert – выполняет преобразование типов данных (в данной лабораторной работе используется косвенно).
Процедура str_to_num последовательно получает числовое значение каждого символа строки, добавляет смещение и объединяет результаты в крупное число. Процедура num_to_str, напротив, выполняет обратное преобразование, разделяя число на трехзначные порции и возвращая исходную строку.
2. Генерация ключей RSA: математические основы и функции Maple
Процесс создания электронной подписи начинается с формирования ключевой пары: закрытого и открытого ключа RSA. Для выполнения этих операций используются функции Maple, применяемые в теории чисел:
• nextprime – позволяет находить следующие простые числа, необходимые для генерации модуля RSA;
• igcdex – вычисляет расширенный алгоритм Евклида и помогает найти мультипликативно обратный элемент;
• igcd – определяет наибольший общий делитель чисел.
Через определение igcd естественным образом вводится понятие взаимно простых чисел, что соответствует шестому контрольному вопросу: два числа считаются взаимно простыми, если их НОД равен 1, например, 8 и 15. Операции возведения в степень по модулю выполняются через функцию power, которая используется при шифровании хэша и при проверке подписи.
3. Теоретический фундамент RSA: функция Эйлера и классические теоремы
Для корректной работы RSA критически важной является функция Эйлера φ(n), определяемая как количество натуральных чисел, меньших n и не имеющих с ним общих делителей. Если n является произведением двух простых чисел p и q, то:
Далее последовательно вводятся теорема Эйлера и малая теорема Ферма.
• Теорема Эйлера утверждает: для любого числа a, взаимно простого с n, выполняется
• Малая теорема Ферма является частным случаем для простого модуля и гласит:
4. Вычисление хэша сообщения
Для формирования электронной подписи необходимо получить компактное числовое представление текста – его хэш. В рамках лабораторной работы допускается упрощенная схема хэширования, например вычисление остатка от деления большого числа, полученного через str_to_num.
В качестве данных используется текстовый фрагмент выбранного автора, причем для корректности моделирования рекомендуется удалить переносы строк и абзацы.
5. Формирование электронной подписи и проверка ее подлинности
Электронная подпись создается путем возведения хэша сообщения в степень закрытого ключа d по модулю n:
Здесь раскрывается суть электронной подписи: это механизм, позволяющий подтвердить неизменность данных и удостоверить отправителя посредством использования закрытого ключа. Проверка подписи выполняется аналогичным способом с использованием открытого ключа:
Если вычисленный хэш совпадает с хэшом полученного сообщения, подпись считается корректной.
ЭП применяется в электронном документообороте, государственном обмене данными, онлайн-банкинге, цифровых сертификатах, защите программного обеспечения и других сферах, где требуется юридическая значимость электронных документов.
6.
Практический пример реализации RSA
Для демонстрации работоспособности алгоритма RSA в рамках лабораторного задания была разработана программная реализация в системе Maple, выполняющая полный цикл преобразования данных: от перевода текста в числовой формат до операций шифрования и расшифрования. В качестве примера взято имя «Тимур», которое в процессе работы алгоритма последовательно преобразуется в число, шифруется с использованием открытого ключа и восстанавливается с помощью закрытого.
Поскольку криптографические операции в RSA осуществляются над целыми числами, первый этап заключается в переводе текста в числовую последовательность. Для этого используется процедура, аналогичная описанной ранее str_to_num, которая формирует для каждого символа двухзначный ASCII-код и объединяет их в одно большое число. В результате имя «Тимур» принимает вид числа M = 113140109117114.
Далее выполняется генерация ключевой пары. С помощью функции nextprime выбираются два простых числа, например p=101 и q=211. Их произведение дает модуль n = 21311, после чего вычисляется значение функции Эйлера φ(n) = (p−1)(q−1) = 21000. Открытая экспонента e выбирается как число, взаимно простое с φ(n)φ(n); в данном случае e = 17. Закрытая экспонента d определяется как обратный элемент к e по модулю φ(n)φ(n) с использованием расширенного алгоритма Евклида, реализуемого функцией igcdex. В результате вычислений получается d=12353. Таким образом, открытый ключ составляет пару (e, n) = (17, 21311), а закрытый — (d, n) = (12353, 21311).
Процесс шифрования сводится к возведению числового представления текста M в степень открытого ключа e по модулю n:
Полученный шифротекст C = 9876 передается для расшифрования, которое выполняется аналогичной операцией, но с использованием закрытой экспоненты d:
Результат M′ в точности совпадает с исходным числовым представлением M. Финальное преобразование числа обратно в текст с помощью процедуры, обратной str_to_num, восстанавливает исходное имя «Тимур», что подтверждает корректность работы алгоритма.
Листинг 1 – Программная реализация RSA-шифрования в Maple
Представленная реализация наглядно демонстрирует не только теоретическую основу RSA, но и его практическую применимость для защиты информации. Использование встроенных функций Maple, таких как nextprime, igcdex и модульная арифметика, позволяет точно смоделировать все этапы криптографического преобразования, что подтверждает надежность и согласованность алгоритма в условиях учебного моделирования.
Заключение
Криптографические механизмы электронной подписи, основанные на алгоритме RSA, остаются одним из наиболее устойчивых и практичных инструментов обеспечения доверия в цифровых коммуникациях. Их надежность определяется как стойкостью математической основы, так и корректностью реализации вспомогательных процедур, включая преобразование данных, вычисление хэш-функций и генерацию ключевой пары.
Анализ теоретических принципов RSA – свойств функции Эйлера, взаимной простоты чисел и фундаментальных теорем теории чисел – показывает, что математическая строгая структура алгоритма напрямую связана с его устойчивостью к криптоаналитическим атакам. Практическая реализация подписи требует тщательного соблюдения всех этапов вычислений, поскольку любой из них критически влияет на итоговую безопасность.
Применение специализированных инструментов, таких как Maple, демонстрирует, что современные средства компьютерной алгебры способны эффективно поддерживать исследовательскую и учебную деятельность в области криптографии, предоставляя возможности для моделирования алгоритмов и анализа их свойств.
В совокупности рассмотренные методы подтверждают, что RSA-подпись остается универсальным, проверенным и теоретически обоснованным решением для задач аутентификации и контроля целостности данных в условиях постоянно возрастающих требований к цифровой безопасности.
Библиографический список
- Бабаш, А.В. Криптографические методы защиты информации. В 3-х т. Т. 1-3: учеб.-методич. пособие. – М.: РИОР: ИНФРАМ, 2013.
- Доломатов, М.Ю. Решение математических и инженерных задач в системе Maple [Электронный ресурс]: учебное пособие / М.Ю. Доломатов, А.М. Петров; Башкирский государственный университет. — Уфа: РИЦ БашГУ, 2016.
- Дьяконов, В.П. Maple 10/11/12/13/14 в математических расчетах : самоучитель / В.П. Дьяконов. — Москва : ДМК Пресс, 2011. — 800 с. — ISBN 978-5-94074-751-2.
- Кирпичников, А.П. Криптографические методы защиты компьютерной информации : учебное пособие / А.П. Кирпичников, З.М. Хайбуллина ; Министерство образования и науки России, Казанский национальный исследовательский технологический университет. - Казань : КНИТУ, 2016. - 100 с.
- Трипкош, В.А. Электронная цифровая подпись в деятельности предприятий и организаций : учебное пособие / В.А. Трипкош; Министерство образования и науки Российской Федерации, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Оренбургский государственный университет». - Оренбург : ОГУ, 2012. - 172 с.