Алгоритм асимметричного шифрования RSA

 

Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и электронной цифровой подписи. В системах с открытым ключом исключают явную передачу по открытым каналам секретных постоянных данных - секретных ключей для шифрования.

Надежность алгоритма основывается на большой вычислительной сложности:

- факторизации (разложения на простые сомножители) больших чисел

 

- и вычисления дискретных логарифмов.

 

Сложность вычисления дискретных логарифмов заключается в том, что по известному числу Ко (открытому ключу) и зашифрованному тексту C математически сложно подобрать секретный ключ Kc и исходный текст M, для которых будет выполняться равенство М = CKc mod N, где C = MKо mod N.

Асимметричные алгоритмы применяются в основном в процедурах

 

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

В алгоритме выбираются случайные большие простые числа Р и Q, равной длины (с одинаковым количеством двоичных или десятичных разрядов, необходимых для хранения числа), которые являются секретом. Данные числа образуют модуль N, используемый для нормирования результатов: N = P? Q.

Открытый ключ Ко выбирается случайным образом так, чтобы одновременно выполнялись условия:

1< Kо ≤ j(N),

НОД(Kо, j(N)) = 1,

j(N)=(P-1)(Q-1),

где j(N) - функция Эйлера (раздел 1.6). Функция Эйлера j(N) указывает

 

количество положительных целых чисел в интервале

1, N -1 , которые

 

взаимно простые с числом N. Второе условие означает, что открытый ключ Kо и функция j(N) должны быть взаимно простыми (использование алгоритма Евклида, раздел 1.1).

Далее, используя расширенный алгоритм Евклида (раздел 2.2), вычисляется секретный ключ Kс как обратный элемент к Kо, такой, что

-1

Kc ? Ко ≡ 1 mod j(N) или Kc = Ко

mod((P-1)(Q-1)).

 

Для вычисления Kc числа j(N) и Ко должны быть взаимно простыми, то есть чтобы выполнялось условие НОД(j(N), Ко) = 1.

Открытый ключ Kо используют для шифрования данных, а секретный ключ Kc - для расшифровки.

Открытый текст M перед шифрованием разбивается на числовые блоки

 

Mi, не превосходящих N.

 

При шифровании выполняется преобразование открытого текста M с открытым ключом Ко по следующей формуле (возведение в степень с нормированием результата по модулю выполняется с помощью схемы

 

Горнера, раздел 1.7):

 

 

C = MKо mod N.

 

Задача расшифровки зашифрованного текста С решается с использованием пары чисел - секретного ключа Kc и зашифрованного текста

С - по формуле:

 

М = CKc mod N.

 

Процесс расшифровки можно записать как D(E(M)) = M (D - операция расшифровки, E - операция шифрования). Тогда M = (MKо)Kc mod N.

Рассмотрим вопрос: почему для целого числа M, удовлетворяющего неравенству 0 ≤ M ≤ N-1, выполняется тождество D(E(M)) = M.

Условие Kc ? Ко ≡ 1 mod j(N) можно записать в виде Kc ? Ко = 1 +

 

j(N)? t, где t - некоторое целое число. Тогда (MKо)Kc mod N = M1 + j(N)?t mod N =

 

= [M? Mj(N)?t] mod N = M? (Mj(N)) t mod N.

 

Если числа M и N взаимно простыми, то по теореме Эйлера (раздел 1.6)

 

Mj(N) ≡ 1 mod N. В результате, M? (Mj(N)) t mod N = [(M mod N)?

 

? (Mj(N)t mod N)] mod N = M? (1) t mod N = M? 1 mod N = M.

 

Доказательство тождества D(E(M)) = M для общего случая (когда

 

N и M не являются взаимно простыми). Покажем: почему работает RSA.

 

 

Чтобы однозначно поставить в соответствие С и М, требуется выполнение усдовия

e · d ≡ 1 mod φ(m), m=N

С = Me mod m; m = p·q; M<m.

 

Сd mod m = M = Me·dmod m = M(1+φ(m)k) mod m = M · Mφ(m)k mod m = M

 

mod m,

 

так как e·d ≡ 1 mod φ(m)

 

e·d = 1 + φ(m)·k,

 

aφ(m)k ≡ 1k mod m, (a,m) = 1

 

Необходимо доказать, что p·q | (Med – M) для любых М

 

Med mod p = M mod p

 

Med mod q = M mod q

 

p| (Med – M)

 

q| (Med – M)

 

(M · Mφ(m)k ) mod p = M · M(p-1)(q-1)k mod p = M mod p

 

(M · Mφ(m)k ) mod q = M · M(p-1)(q-1)k mod q = M mod q

 

M · M(p-1)(q-1)k mod p = 1

 

M · M(p-1)(q-1)k mod q = 1

 

Следовательно, p·q| (Med – M). По теории сравнимости: если одно и тоже число делится на p и на q, то оно делится и на их произведение.

 

В криптосистеме RSA открытый ключ Ко и секретный ключ Кс

 

принадлежат множеству целых чисел

2, j( N ) , а сообщение М и

 

криптограмма С - множеству целых чисел

 

Элементами системы являются:

0, N - 1, где N - модуль.

 

- открытые - открытый ключ Ko, модуль N и шифротекст C;

 

- закрытые - секретный ключ Kc, простые числа P и Q, и исходный текст M.

Особенности алгоритма RSA.

 

Чтобы алгоритм RSA имел практическую ценность, необходимо:

 

- генерировать большие простые числа без больших временных затрат;

 

- уметь оперативно вычислять значения ключей Кc и Кo.

 

Для нахождения чисел P и Q из N перед злоумышленником существует задача разложения числа N на множители. Для получения открытого текста M из закрытого текста C, без знания секретного ключа Kc, возникает проблема нахождения дискретного логарифма. Обе эти задачи имеют вычислительную экспоненциальную сложность.

Реализация RSA примерно в 100-1000 раз медленнее соответствующей реализации симметричного алгоритма.

Недостаток алгоритма RSA - существует малая вероятность того, что шифровка числа M возведением в степень Кo по модулю N может не изменить открытый текст M, то есть MKо ≡ M mod N.

 

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

Описание алгоритма RSA. Рассмотрим реализацию данного алгоритма для чисел размерностью в машинное слово (до 232), задавая в качестве исходного открытого текста буквы русского алфавита, и выбирая модуль, соизмеримый с размером алфавита (если модуль будет меньше, то результат расшифровки будет отличаться от исходного открытого текста).

 

 

Рис. 4.1. Оценки длин ключей для асимметричных систем

 

Пусть пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. Пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Элементы криптосистемы RSA должен формировать получатель сообщения - пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.

Действия пользователя B.

 

1. Выбираются 2 произвольных больших простых числа Р и Q.

 

2. Вычисляется значение модуля N = Р ? Q.

 

3. Вычисляется функция Эйлера: j(N) = (P-1)(Q-1) и выбирается случайным образом значение открытого ключа Ко, удовлетворяющего условиям:

 

1< Kо ≤ j(N),

НОД(Kо, j(N)) = 1 (алгоритм Евклида, раздел 1.1).

4. Вычисляется значение секретного ключа Kc (расширенный алгоритм

 

Евклида, раздел 2.2) решением сравнения

 

-1

Kc ≡ Ко

mod j(N).

 

5. Пользователю А пересылается пара чисел (N, Ко) по незащищенному каналу.

Действия пользователя A, передающего пользователю В сообщение М.

 

6. Исходный открытый текст М разбивается на n блоков чисел Mi < N,

 

i = 0, n - 1.

 

7. Текст, представленный в виде последовательности чисел Мi,

 

шифруется по формуле Сi = МiКo mod N,

 

i = 0, n - 1

 

(схема Горнера, раздел

 

1.7); отправляется криптограмма C0, С1, ..., Сn-1 пользователю В.

 

Действия пользователя B.

 

8. Расшифровывается полученная криптограмма C0, С1, ..., Сn-1 с помощью секретного ключа Kc по формуле Mi = СiКc mod N. В результате будет восстановлена последовательность чисел Мi, образующих исходное сообщение М.

Пример4.1. Проведем шифрование и расшифровку сообщения "ЭБФ". Будем использовать русские прописные буквы (перевод букв алфавита в

числа представлен в табл.4.1).

 

Таблица 4.1. Номера букв русского алфавита

 

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

 

 

Действия пользователя В.

 

1. Выбираются некоторые Р = 3 и Q = 11.

 

2. Вычисляется модуль N = P? Q = 3? 11 =33.

 

3. Вычисляется значение функции Эйлера для N = 33:

 

j(N) = j(33) = (Р-1)(Q-1) = 2? 10 = 20.

 

Выбирается в качестве открытого ключа Кo произвольное число, удовлетворяющее условиям: 1 < Кo ≤ 20, НОД(Кo, 20) = 1.

Пусть Кo = 7.

 

4. Вычисляется значение секретного ключа Кc (расширенный алгоритм

 

Евклида, раздел 2.2) решением сравнения

 

o

Кс ≡ К -1

 

mod j(N) = 7-1

 

mod 20 ≡ 3.

 

5. Пересылается пользователю А пара чисел (N = 33, Кo = 7).

 

Действия пользователя А.

 

6. Шифруемое сообщение представляется как последовательность

 

целых чисел в диапазоне

0, 32 . Пусть букве 'А' соответствует число 1, букве

 

'Б' - число 2, букве 'В' - число 3. Тогда сообщение "ЭБФ" можно представить как последовательность чисел 30 02 21, то есть М1 = 30, М2 = 2, М3 = 21.

7. Текст, представленный в виде последовательности чисел M1, М2 и

 

М3, шифруется с использованием ключа Ко = 7 и N = 33, по формуле

 

Ci = МКо mod N = M7 mod 33.

 

Получается

 

С1 = 307 (mod 33) = 24, C2 =2 7 (mod 33) = 29, C3 = 217 (mod 33) = 21.

Пользователю В отправляется криптограмма C1C2C3 = 24, 29, 21.

 

Действия пользователя В.

 

8. Расшифровывается принятая криптограмма С1С2С3 по формуле

 

Mi = СiKc mod N = Ci3 mod 33 на основе секретного ключа Kc = 3.

 

Получается

 

M1 = 243 mod 33 = 13824 mod 33 = 30, M2 = 293 mod 33 = 24389 mod 33 = 2, M3 = 213 mod 33 = 9261 mod 33 = 21.

Таким образом, было восстановлено исходное сообщение: "ЭБФ". Дополнительные примеры для решения.

Зашифруйте и расшифруйте первые буквы своих инициалов с

 

помощью алгоритма RSA, используя свои параметры алгоритма.

 

Вопросы для самопроверки.

 

1. Для чего предназначен алгоритм RSA?

 

2. На сложности разрешения каких математических задач базируется

 

RSA?

 

3. Какие параметры формирует шифрующая сторона? Какие условия

 

накладываются на них?

 

4. Как вычисляется секретный ключ в RSA?

 

5. Какие параметры RSA являются открытыми и секретными?

 

6. Как производится шифрование информации?

 

7. Как производится расшифровка информации?

 

8. Какими особенностями обладает алгоритм RSA?

 

9. Поясните упрощенный алгоритм вычисления обратных элементов?

 

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

11. Какие алгоритмы теории чисел и конечных полей используются в алгоритме RSA?

12. Какие математические операции используются в алгоритме RSA?