Коды и шифры

Ключи зашифрования и расшифрования в системе rsa

Чтобы зашифровать текст с помощью метода RSA, нам потребуется:

большое число n(=pq), являющееся произведением только двух различных простых чисел p и q. Вопрос, как именно отыскивать очень большие простые числа, весьма уместен. Мы уже сталкивались с этой проблемой раньше, в связи с системой рассылки ключей Диффи-Хеллмана. В общем случае потребуется значительный объем вычислений. Поскольку используемые простые числа в данном случае не могут иметь специального вида, такого как 2^p-1, то никаких действительно быстрых методов не найдено. Правда, существует метод нахождения предположительно простых чисел, в котором вероятность простоты числа может быть сделана сколь угодно близкой к единице, т.е. число будет простым почти наверное. (Детали можно найти в М24);
целое число e, называемое ключом зашифрования, не имеющее общих делителей с (p-1)(q-1) и с самим числом n;

Для расшифрования текста, зашифрованного по методу RSA, далее нам понадобится

целое число d, называемое ключом расшифрования, которое удовлетворяет условию

ed1(mod (p-1)(q-1)).

Теперь стоит отметить, что числа e и d симметричны друг относительно друга. Это говорит о том, что если d - ключ расшифрования для e, то e - ключ расшифрования для d. Значение этого факта станет ясно, когда мы будем рассматривать то, каким образом "хозяин" ключа расшифрования d может отвечать своим корреспондентам.

После того, как выбраны n и e, необходимо вычислить число d. Если p и q известны, существует метод нахождения d; но если p и q неизвестны, найти d невозможно. Именно этот факт обеспечивает стойкость системы RSA. Если p и q очень велики (например, более 10²⁰⁰), то найти их за приемлемое время (то есть факторизовать число n) не под силу даже наибыстрейшим компьютерам.

Прежде чем перейти к описанию самого процесса зашифрования, рассмотрим два примера, которые показывают, как найти d по известным значениям p, q и e. В первом примере все величины маленькие; второй пример оперирует несколько большими величинами, хотя они все равно гораздо меньше тех, что подходят для использования в алгоритме шифрования RSA.

Пример 13.1

Найти ключ расшифрования d, если n=91, а ключ зашифрования e=29.

Решение

В качестве первого шага отметим, что 91=713, поэтому, положив p=7 и q=13, получим

(p-1)(q-1)=612=72,

и поскольку число 29 на имеет общих делителей ни с 91, ни с 72, то оно годится в качестве ключа зашифрования по методу RSA. Чтобы найти соответствующий ключ расшифрования d, применяем алгоритм Евклида (он разъяснён в М25). Метод нахождения можно проиллюстрировать следующими шагами:

72=229+14,

29=214+1,

поэтому

1=29-214,

но, как мы видим из первого равенства, 14=72-229, и поэтому

1=29-2(72-229)=529-272, то есть

529=272+1,

откуда

5291(mod 72)

(т.е. 145=144+1), и следовательно, ключ расшифрования d=5.

Это может показаться странным, но метод состоит в том, чтобы с помощью алгоритма Евклида найти наибольший общий делитель ключа зашифрования e и числа (p-1)(q-1). Поскольку e и (p-1)(q-1) не имеют общих делителей, то их наибольший общий делитель равен единице. Если теперь мы "вернемся назад" по шагам алгоритма Евклида от последней строчки к первой, заменяя каждый раз последнее число справа его выражением через оставшиеся числа, то в конце концов получим ключ расшифрования d, определяемый приведенным выше сравнением из пункта (3). Формальное описание метода и альтернативный подход даны в М25.

Пример 13.2 (Немного более реалистичный случай, который мы будем использовать ниже)

Найти ключ расшифрования d, если n=3127, а ключ зашифрования e равен 17.

Решение

Заметим, что n=3127=5359, причем и 53, и 59 - простые числа. Следовательно, значение n годится в качестве модуля для системы RSA, а (p-1)(q-1)= 5258=3016. Далее, поскольку число 17 не имеет общих делителей ни с 3127, ни с 3016, то оно годится в качестве ключа зашифрования. Действуя, как и ранее, то есть по алгоритму Евклида, получаем:

3016=17717+7,

17=27+3,

7=23+1,

откуда

1=7-23,

но из второго равенства сверху следует, что 3=17-27, поэтому

1=7-2(17-27)=57-217,

а из первого равенства следует, что 7=3016-17717, поэтому

1=5(3016-17717)-217=53016-88717,

или

88717-1(mod 3016).

Нам требуется значение d, которое, будучи умножено на 17, даст при делении на 3016 остаток +1. Следовательно, оно равно -887, а не +887. Так как -8872129(mod 3016), то окончательно получаем, что ключ расшифрования d=2129.

(Проверка: 212917=36193=123016+1.)

Содержание