Безпека RSA: деякі алгоритми факторизації

RSA как схема шифрования и подписи

RSA как схема подписи

RSA как схема шифрования

Шифрування та підпис за схемою RSA

Если пользователь, скажем, Алиса, хочет послать секретное сообщение Бобу, то она находит публичный ключ Боба ‑ пару и представляет свое сообщение в произвольной стандартизованной форме как число. Затем Алиса посылает шифртекст, вычисленный следующим образом:

Боб может восстановить из, возводя в степень, которая известна только ему. В самом деле, для некоторого целого мы имеем

(9.5)

когда.

САМОСТОЯТЕЛЬНО. В задаче 9.2 проверить, что система работает и тогда, когда.

Резюмируем систему шифрования RSA в следующей таблице.

Таблица 9.1. RSA как схема шифрования.

публичные	и всех пользователей
секретное	пользователя
свойство
сообщение для
шифрование для
дешифрование

Публичный и секретный показатели в системе RSA традиционно обозначаются через и, чтобы указать на функции шифрования (encryption) и дешифрования (decryption) соответственно.

Пример 9.1 (часть 3)

Продолжаем пример 9.1 с теми же параметрами, так что,. Шифрование сообщения выполняется в пакете "Mathematica" с помощью функции PowerMod:

nB = 99052741; eB = 81119923; dB = 17089915;

m = 12345678;

c = PowerMod[m, eB, nB]

|| 38447790

Боб дешифрует это, вычисляя, что дает.

PowerMod [c, dB, nB]

|| 12345678

Можно уменьшить объем работы в процессе дешифрования, применив китайскую теорему об остатках.

Китайская теорема об остатках

Пусть:

, — попарно взаимно простые натуральные числа,

, — целые числа с.

Тогда система сравнений

или кратко

(A.12)

имеет единственное решение по модулю для всех возможных целых чисел.

Боб, зная разложение, может поступить следующим образом.

Он предварительно вычисляет целые числа и, меньшие, удовлетворяющие системам сравнений

В соответствии с китайской теоремой об остатках значения и будут по модулю.

Получив шифртекст, Боб приводит его по модулю и, соответственно получая:

·,

·,

а затем вычисляет

·,

·,

Заметим, что все эти вычисления выполняются по модулю и, типичная длина которых составляет половину длины. По китайской теореме об остатках равно
.

Вычисления и можно дополнительно упростить, приведя показатель по модулю и соответственно:

·, где,

·, где.

Справедливость такого упрощения можно пояснить так.

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

Пример 9.1 (часть 4)

Продолжаем с параметрами примера 9.1, так что,,, и. Чтобы найти решения систем

и найдем числа и с помощью функции ChineseRemainderTheorem:

a = ChineseRemainder[{1, 0}, {9733, 10177}]

b = ChineseRemainder[{0, 1}, {9733, 10177}]

|| 45287650

|| 53765092

Далее, вычисляем и, получая

p = 9733; q=10177; d = 17089915;

c = 38447790;

c1 =Mod[c, p]

c2 =Mod[c, q]

d1 = Mod[d, p-1]

d2 = Mod[d, q-1]

m1 = Mod[c1^d1, p]

m2 = Mod[c2^d2, q]

|| 2440

|| 9261

|| 523

|| 4411

|| 4234

|| 977

Результат дешифрования дается выражением и совпадает указанным, ранее

n = 99052741;

Mod[m1*a+m2*b,n]

|| 12345678

Также систему RSA можно использовать для подписывания сообщений. Чтобы подписать сообщение, Боб вычисляет.

Получатель сообщения, скажем, Алиса, может легко восстановить исходное, вычисляя, так как параметры и Боба публичны. Чтобы проверить это, повторим вычисления (9.5) (с небольшой вариацией):

(9.6)

для всех с. Сравнение выполняется и тогда, когда

САМОСТОЯТЕЛЬНО. В задаче 9.2 доказать, что сравнение выполняется и тогда, когда.

Алиса должна рассматривать как подпись Боба к. Только Боб может вычислить, исходя из, потому что ему одному известно.

Таблица 9.2. Система RSA для подписывания

публичные	и всех пользователей
секретное	пользователя
свойство
сообщение Боба
B подписывает
проверяет

Пример 9.1 (часть 5)

Боб подписывает сообщение, вычисляя

m = 11111111;

c = PowerMod[m,dB,nB]

|| 74138899

Алиса проверяет подпись, вычисляя и получая.

Предположим, что Алиса хочет подписать и зашифровать сообщение Бобу. Общее решение, описанное ранее, а именно, Алиса сначала подписывает с помощью своего секретного ключа, а затем шифрует результат с помощью публичного ключа Боба, не всегда непосредственно применимо в системе RSA.

Чтобы увидеть это, заметим, что Алиса должна была бы послать

(9.7)

Однако это отображение не будет инъективным (инъективный ‑ однозначный, т.е. для двух разных аргументов невозможно получить одинаковое значение функции), если. Например,

т.е. оба сообщения и отобразятся в.

Так как Алиса и Боб не хотят делиться своими простыми числами, необходимо, чтобы было. В этом случае Боб может восстановить следующим образом:

Чтобы проверить это, можно воспользоваться соотношениями (9.5) и (9.6).

Конечно, теперь возникает новая проблема — что делать, когда Боб захочет подписать и зашифровать сообщение Алисе?

Простое решение состоит в том, чтобы каждый пользователь создавал два набора параметров (две пары ключей) — один с модулем, меньшим некоторого порога, и другой с модулем, большим. В этих условиях отправитель использует свой собственный меньший модуль для подписи и больший модуль получателя — для шифрования.

Таблица 9.3. RSA как схема шифрования и подписи

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

Если между Алисой и Бобом возникает спор, то они идут к арбитру. Этот арбитр получает от Боба числа и. Последнее равно, так как

Точно также арбитр проверяет, будет ли. Если это условие выполняется, то сообщение действительно пришло от Алисы; если же нет, не будет рассматриваться как подпись Алисы к.

Заметим, что арбитр не нуждается в знании секретных показателей Алисы или Боба. Поэтому Алиса и Боб могут продолжать использовать свои исходные наборы параметров.

Дата добавления: 2013-12-12