Реферат: Тест числа на простоту

;

то есть , где k любое натуральное число (0, 1, 2…).

Пара G = (e,n) публикуется в качестве открытого ключа RSA (RSA public key).

Пара N = (d,n) играет роль секретного ключа RSA (RSA secret key) и держится в секрете.

Число n называется модулем, а числа e и d - открытой и секретной экспонентами, соответственно.

Допустим абонент В хочет послать сообщение абоненту В по коммутационному каналу.

Сообщением являются целые числа лежащие от 0 до n-1, .

Алгоритм шифрования:

Берется открытый ключ (e,n) стороны A, вставляется открытый текст L, передается шифрованное сообщение:

Алгоритм дешифрования:

Принимается зашифрованное сообщение С, для расшифровки сообщения применяется секретный ключ (d,n):

Цифровая подпись

Система RSA может использоваться не только для шифрования, но и для цифровой подписи.

Предположим, что абоненту Aнужно отправить абоненту Bответ L¹ , подтверждённый цифровой подписью.

Алгоритм подписи

Взять открытый текст L¹ , затем создаем цифровую подпись wc помощью секретного ключа (d,n).

Далее передаем (L¹ ,w), которая состоит из сообщения и подписи.

Алгоритм проверки подлинности подписи

Принять (L¹ ,w), берем открытый ключ (e,n) абонента А, проверяем подлинность подписи

подпись верна

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

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

Заметим, что подписанное сообщение L¹ не зашифровано. Оно пересылается в исходном виде и его содержимое не защищено. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем - зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.

RSA

Пример

Сначала нужно сгенерировать ключ

Выбираем два простых ключа p=13, q=41

Вычисляем модуль n=p*q = 13*41 =533