Алгоритмы ЭЦП. Алгоритм цифровой подписи RSA

Электронная цифровая подпись (ЭЦП)— реквизит электронного документа, предназначенный для удостоверения источника данных и защиты данного электронного документа от подделки.

Схема электронной подписи обычно включает в себя:

• алгоритм генерации ключевых пар пользователя;

• функцию вычисления подписи;

• функцию проверки подписи.

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

Генерация ключей

Для того, чтобы сгенерировать пару ключей выполняются следующие действия:

1. Выбираются два больших простых числа и

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

3. Вычисляется

4. Выбирается целое такое, и взаимно простое с

5. С помощью расширенного алгоритма Евклида находится число такое, что

Число называется модулем, а числа и — открытой и секретной экспонентами, соответственно. Пара чисел является открытой частью ключа, а ­- секретной. Числа и после генерации пары ключей могут быть уничтожены, но ни в коем случае не должны быть раскрыты.

Зашифрование и расшифрование

Для того, чтобы зашифровать сообщение вычисляется

Число используется в качестве шифртекста. Для расшифрования нужно вычислить

Нетрудно убедиться, что при расшифровании мы восстановим исходное сообщение:

Из условия следует, что для некоторого целого , следовательно Согласно теореме Эйлера:

поэтому