Научный руководитель: Вильданов Алмаз Нафкатович
к.ф.-м.н., Уфимский университет науки и технологий, Нефтекамский филиал
Электронная подпись нужна в тех случаях, когда электронный документ должен иметь подтвержденного автора и не должен изменяться после подписания. В обычной жизни человек ставит подпись на бумаге, а в информационной системе вместо этого выполняется математическая операция. Результат такой операции можно проверить, но нельзя нормально подделать без закрытого ключа. Именно поэтому электронная подпись применяется в электронном документообороте, банковских сервисах, государственных порталах, корпоративных системах и при передаче программного обеспечения. В учебной работе важно не просто сказать, что подпись защищает документ, а показать, как она появляется из конкретных вычислений.
Одним из классических алгоритмов, на котором удобно объяснять электронную подпись, является RSA. Этот алгоритм был предложен Р. Ривестом, А. Шамиром и Л. Адлеманом и стал одним из самых известных примеров криптографии с открытым ключом [1]. Его популярность в учебных задачах объясняется тем, что основные шаги можно проследить без сложных программных библиотек. Достаточно знать, что такое простые числа, взаимная простота, функция Эйлера и вычисления по модулю. При этом за простыми на вид формулами стоит серьезная идея: некоторые действия легко выполнить в одну сторону, но трудно обратить без секретной информации.
В алгоритмах с открытым ключом у пользователя есть две связанные части ключа. Открытая часть может передаваться другим людям, а закрытая должна храниться только у владельца. При создании электронной подписи сообщение обрабатывается закрытым ключом. Проверка, наоборот, выполняется открытым ключом. Если результат проверки совпадает с исходным сообщением или его контрольным значением, подпись считается правильной. Для студента это важный момент, потому что RSA часто объясняют на примере шифрования, но для подписи направление использования ключей воспринимается иначе.
В реальных системах RSA не применяется в таком упрощенном виде, как в лабораторной работе. Обычно подписывается не сам документ, а его хеш, то есть короткое значение, полученное специальной хеш-функцией. Кроме того, используются большие ключи и специальные схемы заполнения. Такие требования описываются в технических документах и стандартах, например в спецификации RFC 8017 и стандарте FIPS 186-5 [2; 3]. Однако для первой практической работы полная промышленная схема была бы слишком тяжелой. Поэтому в учебной модели берется короткий текст, переводится в число, после чего над этим числом выполняются основные операции RSA.
Система Maple подходит для такой работы, потому что она позволяет удобно выполнять вычисления с целыми числами, простыми числами и степенями по модулю. В обычном калькуляторе студент быстро столкнулся бы с большими числами и потерял бы связь между этапами. В Maple каждый шаг можно записать отдельной командой, сразу увидеть результат и при необходимости изменить исходные данные. Поэтому программа получается не просто набором ответов, а понятной моделью алгоритма.
Первый этап работы связан с переводом текста в число. Криптографические алгоритмы не работают напрямую с буквами, потому что математические операции выполняются над числами. Поэтому текстовое сообщение необходимо закодировать. В лабораторном примере используется простой способ: английским заглавным буквам ставятся в соответствие номера от 1 до 26. Буква A получает номер 1, B получает номер 2, C получает номер 3, а Z получает номер 26. Чтобы потом можно было правильно восстановить текст, под каждую букву выделяются две позиции. Например, A записывается как 01, B как 02, K как 11, V как 22.
Для перевода строки в число используется функция str_to_num_eng. Она проходит по символам строки, получает код каждого символа через StringTools[Ord], вычитает 64 и таким образом получает номер буквы в английском алфавите. После этого номер записывается двумя цифрами и присоединяется к общему числу. Например, для сообщения VAN получается последовательность 22, 01, 14, а итоговое число равно 220114. Это число в дальнейшем обозначается как M и используется как исходное сообщение для подписи.
Рисунок 1. Пример работы функции str_to_num_eng в Maple
Обратная функция num_to_str_eng нужна для восстановления текста из числа. Она превращает число в строку, разбивает запись на пары цифр и каждую пару воспринимает как номер буквы. Если количество цифр получается нечетным, в начало добавляется ноль, чтобы разбиение на пары не нарушилось. Затем к номеру буквы прибавляется 64, и команда StringTools[Char] возвращает нужный символ. Такой способ легко проверить вручную: число 10202001 разбивается на 10, 20, 20, 01, что соответствует слову JTTA только при выбранной таблице. Поэтому важно внимательно следить за тем, какие именно пары цифр получаются после разбиения.
Использование только английских букв в этой модели связано не с ограничением RSA, а с выбранным способом кодирования. Заглавные английские буквы удобно расположены в таблице символов, и разность между их кодом и числом 64 дает понятный номер буквы. Если добавить русские буквы, пробелы, строчные символы или знаки препинания, функция уже не сможет работать по той же простой схеме. Для реального приложения нужно было бы использовать полноценную кодировку, например Unicode, но для учебной лабораторной работы такой вариант сделал бы пример менее наглядным.
После того как сообщение получено в числовом виде, начинается построение ключей RSA. В примере выбираются два простых числа p и q. С помощью команды nextprime(1000) можно получить p = 1009, а следующее простое число после него дает q = 1013. Эти числа специально небольшие, потому что задача состоит в объяснении алгоритма, а не в реальной криптографической защите. В настоящих системах применяются намного более длинные ключи, иначе их можно было бы подобрать перебором.
Далее вычисляется число n. Оно равно произведению p и q. В рассматриваемом примере n = 1009 · 1013 = 1022117. Число n входит и в открытый, и в закрытый ключ. Затем находится значение функции Эйлера для n. Поскольку n является произведением двух простых чисел, используется формула phi_n = (p − 1)(q − 1). Для выбранных значений получается phi_n = 1008 · 1012 = 1020096. Это значение нужно для выбора открытой экспоненты и вычисления закрытой экспоненты.
Функция Эйлера показывает, сколько натуральных чисел от 1 до n взаимно просты с n. Взаимно простыми называются числа, у которых наибольший общий делитель равен 1. Например, числа 8 и 15 взаимно просты, потому что у них нет общего делителя, кроме единицы. В RSA это условие важно, потому что выбранная открытая экспонента должна быть взаимно простой с phi_n. Без этого не получится корректно найти обратное число для закрытого ключа.
В качестве открытой экспоненты e в учебном примере берется число 1019. После этого командой igcd(e, phi_n) проверяется наибольший общий делитель чисел e и phi_n. Если результат равен 1, число e подходит. В данном случае проверка дает единицу, поэтому e можно использовать в открытом ключе. Сама команда igcd удобна тем, что сразу показывает, выполнено ли главное условие взаимной простоты.
Следующий этап – поиск закрытой экспоненты d. Она должна быть обратной к e по модулю phi_n. Это означает, что произведение e · d при делении на phi_n должно давать остаток 1. В Maple для этого используется команда igcdex, которая основана на расширенном алгоритме Евклида. После вычисления и приведения результата по модулю получается d = 397427. Это число является секретной частью ключа, и в настоящей системе его нельзя раскрывать.
Рисунок 2. Перевод сообщения VAN и расчет параметров RSA в Maple
После выполненных расчетов открытый ключ можно записать как пару (e, n), то есть (1019, 1022117). Закрытый ключ в учебной записи содержит d и n, то есть (397427, 1022117). Открытый ключ нужен для проверки подписи, а закрытый – для ее создания. Именно разделение ключей делает схему удобной: проверяющий может убедиться в правильности подписи, но при этом не получает закрытый ключ автора.
Создание подписи выполняется с помощью возведения числа M в степень d по модулю n. В Maple это можно записать как power(M, d) mod n. Для сообщения VAN числовое значение M равно 220114, а закрытая экспонента d равна 397427. В результате получается C = 877653. Это число и является электронной подписью в рамках учебной модели. Его нельзя воспринимать как зашифрованный текст в привычном смысле, потому что цель здесь не скрыть содержание сообщения, а подтвердить, что операция была выполнена закрытым ключом.
Проверка подписи выполняется открытым ключом. Для этого подпись C возводится в степень e по модулю n. Если вычисленное значение совпадает с исходным M, проверка проходит успешно. В примере команда power(C, e) mod n возвращает M1 = 220114. Поскольку M1 равно M, программа выводит сообщение о том, что проверка подписи выполнена успешно.
Такой результат показывает, что выбранные параметры согласованы правильно, а сама подпись соответствует исходному сообщению.
Рисунок 3. Создание и проверка электронной подписи в Maple
Назначение команд Maple в этой работе можно объяснить без сложных формулировок. Команда proc используется для создания собственной процедуры. В данном случае с ее помощью оформлены функции перевода строки в число и числа обратно в строку. Команда Ord возвращает код символа, а Char выполняет обратную операцию и возвращает символ по его коду. Команда parse превращает строковую запись числа в обычное число, с которым уже можно выполнять математические действия. Команда length определяет длину строки. Команда convert в Maple обычно используется для преобразования выражения или данных к другому виду, поэтому она тоже относится к базовым инструментам работы с типами и представлениями данных.
Для самой части RSA важны другие команды. Команда nextprime помогает получить простое число, что удобно при выборе p и q. Команда igcd вычисляет наибольший общий делитель и позволяет проверить взаимную простоту. Команда igcdex используется, когда нужно найти обратное число по модулю через расширенный алгоритм Евклида. Команда power нужна для возведения в степень. В RSA это особенно важно, потому что степени могут быть большими, а результат сразу берется по модулю n. Без модульного вычисления числа быстро стали бы слишком громоздкими даже для учебного примера.
Математическая основа RSA связана с теоремой Эйлера. В простом виде ее смысл можно передать так: если число a взаимно просто с n, то при возведении a в степень phi(n) получается остаток 1 по модулю n. Благодаря этому можно подобрать такие e и d, что последовательное применение закрытой и открытой экспоненты возвращает исходное сообщение. Малая теорема Ферма является частным случаем похожей идеи для простого модуля. Для студента эти теоремы могут казаться отвлеченными, но в лабораторной работе они сразу проявляются в конкретных числах.
Важно понимать, что данная программа не является готовым средством защиты документов. В ней используются маленькие простые числа, поэтому такой ключ не выдержал бы реальной атаки. Кроме того, сообщение подписывается напрямую, без хеширования. В настоящей электронной подписи сначала вычисляется хеш документа, потому что документ может быть большим, а хеш имеет фиксированную длину и меняется даже при небольшой правке исходного текста. Также реальные схемы RSA используют дополнительные правила обработки данных, чтобы избежать известных криптографических уязвимостей [4].
Ограничение с английскими буквами тоже является учебным. Функции str_to_num_eng и num_to_str_eng рассчитаны на заглавные символы английского алфавита, потому что так проще показать связь между буквой и числом. Под каждый символ выделяется две позиции, иначе возникла бы неоднозначность. Например, запись 111 может читаться как 1 и 11 или как 11 и 1. Если же использовать пары цифр, то K записывается как 11, A как 01, и восстановление становится понятным. Поэтому вопрос о двух позициях под символ здесь не техническая мелочь, а условие правильного обратного преобразования.
Новизна рассматриваемого кода заключается не в изменении самого алгоритма RSA. Алгоритм известен давно, и учебная работа не претендует на создание новой криптографической схемы. Новизна здесь скорее методическая. Код показывает полный путь от обычной текстовой записи до проверки подписи в одной среде Maple. Студент видит, как текст превращается в число, как выбираются простые числа, как появляются открытый и закрытый ключи, как создается подпись и почему проверка возвращает исходное сообщение. За счет этого тема перестает быть набором формул и становится понятным вычислительным процессом.
Такую модель удобно использовать на занятиях по информационной безопасности, дискретной математике или компьютерной алгебре. Преподаватель может предложить студентам изменить исходное сообщение, взять другие простые числа, проверить условие взаимной простоты для e, найти другое значение d и сравнить результаты. Если хотя бы один параметр выбран неправильно, проверка подписи не даст исходное сообщение. Это позволяет увидеть, что в RSA все этапы связаны между собой, а не выполняются отдельно друг от друга.
Для понимания RSA полезно отдельно сказать, почему в основе алгоритма лежит произведение двух простых чисел. Перемножить p и q легко даже вручную, если числа небольшие. Но если известно только большое число n, разложить его обратно на p и q намного сложнее. На этом и держится практическая стойкость RSA. В учебном примере n маленькое, поэтому его можно разложить достаточно быстро. В настоящих системах n имеет такую длину, что подбор множителей становится практически невозможным при правильном выборе параметров.
Есть еще одно важное условие: числовое сообщение M должно быть меньше n. В примере M = 220114, а n = 1022117, поэтому условие выполняется. Если бы сообщение оказалось больше n, его пришлось бы разбивать на части или применять другой способ подготовки данных. В реальных криптографических схемах эта проблема решается через стандартизированные форматы обработки сообщения. Для лабораторной работы достаточно выбрать короткую запись, например инициалы или транслитерацию фамилии, чтобы число не превышало модуль.
Контрольные примеры с функцией str_to_num_eng помогают проверить, понял ли студент сам способ кодирования. Если ввести AA, то сначала получается строка 0101, но после команды parse она превращается в число 101. Если ввести ABC, получается запись 010203, которая как число будет выглядеть как 10203. Если взять KB, то K дает 11, B дает 02, поэтому результатом будет 1102. Эти примеры показывают, почему при обратном переводе иногда нужно добавлять ноль в начало записи.
Функция num_to_str_eng выполняет обратную проверку. Если ей передать число 10, оно читается как одна пара 10, то есть буква J. Если передать 101, функция видит нечетную длину записи и добавляет впереди ноль. Получается 0101, то есть AA.
Если передать 526, сначала получится 0526, а затем пары 05 и 26 дадут буквы E и Z. Эти небольшие примеры полезны, потому что позволяют найти ошибку в функции еще до перехода к RSA.
Внутри функции str_to_num_eng переменная num играет роль накопителя результата. Сначала она пустая, а затем к ней постепенно присоединяются коды букв. Переменная code хранит текущий код символа, уже приведенный к двум позициям. Такой прием удобен, потому что сообщение может иметь разную длину. Цикл проходит по всем символам строки, и программа не зависит от того, ввел студент три буквы или пять. В конце строка с цифрами переводится в число, так как дальнейшие операции RSA требуют именно числовой тип данных.
В функции num_to_str_eng переменная result выполняет обратную роль: в ней постепенно собирается восстановленный текст. Переменная char_code хранит очередную пару цифр, которая затем переводится в символ. Проверка на нечетную длину нужна из-за того, что при переводе строки 0101 в число ведущий ноль исчезает. Без этой проверки число 101 разбилось бы неправильно. Поэтому даже такая небольшая деталь показывает, что при программировании криптографических алгоритмов важно аккуратно работать с форматом данных.
При выполнении лабораторной работы студент может допустить несколько типичных ошибок. Например, можно выбрать e, которое не является взаимно простым с phi_n. Тогда закрытая экспонента не будет найдена корректно. Еще одна ошибка – взять слишком длинное сообщение, числовое значение которого окажется больше n. Также можно случайно использовать строчные буквы или русские символы, и тогда функция перевода даст неправильный результат. Поэтому перед созданием подписи полезно отдельно проверить входные данные и все промежуточные значения.
С точки зрения оформления учебного кода можно добавить простые проверки. Например, программа может предупреждать, если сообщение содержит символы не из диапазона A-Z. Можно также проверять условие M < n и выводить понятное сообщение, если модуль слишком мал для выбранного текста. Еще одно улучшение – автоматически подбирать p и q так, чтобы n было больше сообщения. Такие дополнения не меняют саму идею RSA, но делают программу удобнее и ближе к реальному учебному приложению.
Возможным развитием работы является добавление хеширования. Тогда программа сначала вычисляла бы хеш сообщения, а уже потом подписывала бы его с помощью закрытого ключа. Это позволило бы объяснить студентам, почему в настоящих системах не подписывают весь документ напрямую. Также можно расширить кодировку символов, чтобы работать не только с английскими заглавными буквами, но и с пробелами, цифрами, знаками препинания и русским текстом. В этом случае пример стал бы сложнее, но зато ближе к реальным условиям.
Еще один вариант развития – сделать небольшую интерактивную форму для ввода сообщения и параметров RSA. Студент мог бы ввести текст, выбрать начальное число для поиска p, затем увидеть все промежуточные вычисления и итоговую подпись. Такой формат особенно полезен на практических занятиях, потому что позволяет быстро сравнивать разные варианты. Если результат проверки не совпал с исходным сообщением, программа могла бы показать, на каком этапе появилась ошибка.
Сравнение учебной модели с реальной электронной подписью помогает избежать неправильного вывода. Нельзя сказать, что приведенный код уже защищает документы. Правильнее говорить, что он объясняет принцип. В реальной системе важны длина ключей, качество генерации случайных чисел, защита закрытого ключа, корректная схема заполнения, хеш-функция и проверенные криптографические библиотеки. Но если сразу начать с этих деталей, студенту будет трудно понять основу. Поэтому учебный пример с Maple выполняет свою задачу: он показывает механизм без лишних технических слоев.
Содержательная ценность работы также в том, что она связывает несколько учебных тем. Из программирования здесь используются процедуры, строки, циклы и преобразование типов. Из математики – простые числа, наибольший общий делитель, функция Эйлера и вычисления по модулю. Из информационной безопасности – понятия открытого ключа, закрытого ключа, подписи, проверки подлинности и целостности данных. Благодаря этому одна лабораторная работа помогает повторить сразу несколько разделов, а не сводится к механическому запуску готового кода.
Программа также помогает объяснить, где применяется электронная подпись. Она нужна не только для электронных договоров или заявлений на государственных порталах. С ее помощью можно подтверждать авторство программных файлов, защищать банковские операции, проверять целостность сообщений и организовывать доверенный обмен документами между организациями. Главная идея везде одна: получатель должен иметь возможность убедиться, что данные пришли от нужного отправителя и не были изменены после подписания.
Если кратко описать работу кода, то сначала задается текстовое сообщение, например VAN. Затем функция str_to_num_eng переводит его в число 220114. После этого Maple подбирает простые числа p и q, вычисляет n и phi_n, выбирает e и находит d. Далее сообщение подписывается закрытым ключом, и получается C = 877653. Проверка открытым ключом возвращает M1 = 220114. Совпадение M1 и M означает, что подпись создана и проверена правильно.
Таким образом, моделирование электронной подписи RSA в Maple позволяет понятно показать один из базовых механизмов криптографии с открытым ключом. Работа объединяет программирование, арифметику по модулю и практическую задачу проверки подлинности электронного сообщения. Несмотря на упрощения, такой пример хорошо подходит для учебной статьи и лабораторной работы, потому что каждый этап можно объяснить, повторить и проверить. Главный результат состоит в том, что студент видит электронную подпись не как абстрактный термин из информационной безопасности, а как последовательность конкретных вычислений, где ошибка в одном шаге сразу влияет на итоговую проверку.
Дополнительно такую работу можно использовать как основу для небольшого самостоятельного проекта. Например, студент может оформить программу так, чтобы пользователь вводил текст, а Maple автоматически выводил все промежуточные значения: M, p, q, n, phi_n, e, d, C и результат проверки. Тогда лабораторная работа перестает быть только повторением команд и становится понятной мини-моделью электронного подписания.
Практическая ценность примера состоит еще и в том, что он показывает типичную логику проверки: получатель не обязан знать закрытый ключ автора, но может использовать открытый ключ и убедиться, что подпись подходит к сообщению.
Именно это свойство делает электронную подпись удобной для документооборота, где важно подтвердить авторство и целостность данных без передачи секретной информации.
Библиографический список
- Rivest R. L., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Communications of the ACM. – 1978. – Vol. 21, № 2. – P. 120–126.
- Moriarty K., Kaliski B., Jonsson J., Rusch A. PKCS #1: RSA Cryptography Specifications Version 2.2. RFC 8017. – Internet Engineering Task Force, 2016. – Режим доступа: https://www.rfc-editor.org/rfc/rfc8017, свободный. – Загл. с экрана.
- National Institute of Standards and Technology. Digital Signature Standard (DSS). FIPS PUB 186-5. – Gaithersburg: NIST, 2023. – Режим доступа: https://csrc.nist.gov/pubs/fips/186-5/final, свободный. – Загл. с экрана.
- Stallings W. Cryptography and Network Security: Principles and Practice. – 8th ed. – Pearson, 2020.
- Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. – Boca Raton: CRC Press, 1996.
- Maplesoft. Maple Help: StringTools Package [Электронный ресурс]. – Режим доступа: https://www.maplesoft.com/support/help/, свободный. – Загл. с экрана.
- Maplesoft. Maple Help: Number Theory Commands [Электронный ресурс]. – Режим доступа: https://www.maplesoft.com/support/help/, свободный. – Загл. с экрана.
- Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. – 20th Anniversary ed. – Indianapolis: Wiley, 2015.
- Paar C., Pelzl J. Understanding Cryptography: A Textbook for Students and Practitioners. – Berlin: Springer, 2010.
- Ferguson N., Schneier B., Kohno T. Cryptography Engineering: Design Principles and Practical Applications. – Indianapolis: Wiley, 2010.