Этапы создания электронной подписи

Пролог

Высока вероятность, что вы сталкивались с «электронной подписью». Для меня определение того, кто редко пользуется такими документами, несколько абстрактно, хотя и отражает суть ЭП. Кроме того, ES можно использовать для определения повреждения отправленных сообщений. Вы можете проверить это позже.

Проблема с EP очевидна, но хотелось бы увидеть и почувствовать, что стоит за этими двумя словами. Дальнейшее копание в гугле показывает, что различные алгоритмы создания ЭЦП (ДСА, ГОСТ Р 34.10-2012, РСА-ПСС и др.) сложны.

Криптосистема RSA, разработанная Ривестом, Шамиром и Адлеманом в 1978 году, решает эту проблему и помогает нам понять, что такое ES. Многие алгоритмы не перегружены и основаны на относительно простой математике. В этом плане можно постепенно переходить от модульных операций к алгоритмам создания ЭЦП. Именно этому я хочу посвятить эту статью.

Теория

Открытый текст — данные, зашифрованные или полученные в результате расшифровки

Шифрованный текст — данные, полученные путем применения шифра к открытому тексту.

Шифрование представляет собой серию обратимых преобразований в зависимости от некоторых параметров (ключей).

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

Факторизация — это процесс разложения числа на простые множители.

НОД - наибольший общий делитель.

Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.

Функция Эйлера φ(n) — это функция, равная количеству взаимно простых натуральных чисел, меньших n.

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

Основная часть

Прежде чем мы погрузимся в огромный мир математики и более подробно рассмотрим, как работает RSA, давайте взглянем на то, как работает RSA.

симметричная криптосистема

Рассмотрим задачу сохранения содержимого посылки при передаче от отправителя к получателю. Это любимая многими фотография Алисы и Боба.

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

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

математика сейчас

Асимметричные криптосистемы основаны на так называемых односторонних функциях с секретом. Односторонняя функция — это функция i y=f(x) , легко вычислить существующий x , но сложно вычислить аргумент x для заданного значения функции. Точно так же секретной односторонней функцией является функция y=f(x, k). Это можно легко вычислить по данному x и секретному k, а аргумент x можно восстановить по заданному y. Это легко сделать, но трудно для неизвестного. К.

Подобными свойствами обладает операция возведения числа в степень по модулю.

c\equiv f(m)\equiv m^e\ mod\ n, \\ m \equiv f^{—1}(c) \equiv c^d\ mod\ n, \\ d \equiv