Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
§ 8.3).
Асимметричные системы шифрования обеспечивают значительно меньшие скорости шифрования, нежели симметричные, в силу чего они обычно используются не столько для шифрования сообщений, сколько для шифрования пересылаемых между корреспондентами ключей, которые затем используются в симметричных системах.
Рассмотрим конкретные примеры систем шифрования с открытыми ключами.
§ 11.1. Шифрсистема RSA
Система RSA была предложена в 1978 г. [Riv78] и в настоящее время является наиболее распространенной системой шифрования с открытым ключом. Напомним ее определение, приведенное в гл. 2 (определение 4).
Пусть п = p-q — целое число, представимое в виде произведения двух больших простых чисел р, q . Выберем числа е и d из условия
e-d = l(mod (р(п))> (1)
где ф(п) = (р — 1) • (q -1) — значение функции Эйлера от числа п. Пусть k = (n,p,q,e,d) — выбранный ключ, состоящий из открытого ключа къ = (п9е) и секретного ключа
311
І лава 17
kp = (n,p,q,d) . Пусть M — блок открытого текста и С —
соответствующий блок шифрованного текста. Тогда правила зашифрования и расшифрования определяются формулами:
С = Ek(M) = Me(modп), Dk(C) = Cd(modn). (2)
Заметим, что в соответствии с (2) Dk (С) = M . Это выте-
кает из следующих рассуждений. Для любого целого числа M и любого простого р справедливо сравнение
Mp s М(mod р). (3)
В самом деле, (3) равносильно сравнению Mp -M = 0(mod р)
или сравнению
M(Mp-'-I) = 0(modр). (4)
Если НОД(М,р) = р, то р делит M, и поэтому M = 0(mod р), откуда следует (4). Если же НОД(М, р) = 1, то, согласно малой теореме Ферма (см. Приложение 3), Мр~х = l(modр), откуда также следует (4).
Согласно (1), существует целое число г, такое, что e-d = r • (р(п) + 1. Отсюда и из (3) получаем следующую цепочку равенств и сравнений:
Cd =(Me)d =Med =Mr ^(A7)+l = Mr{p~m~])+] =
= Mrpiq-l) -M-rq+r+l =(MPYiq-{) -M'rq+r+l = (5) = Mr(4~]) ¦ M-r4+r+' = M(mod p).
312
Системы с открытыми ключами
Аналогично можно показать, что
Cd = M mod q . (6)
Поскольку р и q — разные простые числа, то на основании известных свойств сравнений из (5), (6) получаем:
Cd =Mmodzj.
Отсюда и следует корректность определения (2).
Для того чтобы лучше представить себе технические детали, возникающие при зашифровании и расшифровании, приведем пример работы с RSA.
Пример
Зашифруем аббревиатуру RSA, используя р = 17, <7 = 31. Для этого вычислим п = pq = 527 и ср(п) = (р-\)(q -1) = 480 . Выберем, далее, в качестве е число, взаимно простое с (р{п), например е = 7. С помощью алгоритма Евклида найдем целые числа и и V, удовлетворяющие соотношению е • и + (pin) -v = l:
480 = 7-68 + 4,
7 = 4-1 + 3,
4 = 3-1 + 1,
1 = 4-3-1 = 4-(7-4-1)-1 =
= 4-2-7-1 = (480-7-68)-2-7-1 =
= 480-2-7-137,
V = 2, и = -137.
313
І лава 11
Поскольку -137 = 343(mod480),то d = 343. Проверка:
7 • 343 = 2401 s l(mod480).
Теперь представим данное сообщение в виде последовательности чисел, содержащихся в интервале 0,526 . Для этого буквы R9S и А закодируем пятимерными двоичными векторами, воспользовавшись двоичной записью их порядковых номеров в английском алфавите:
R = IS = (10010), S = 19 = (1001 IlA = I = (00001).
Тогда RSA = (100101001100001). Укладываясь в заданный интервал 0,526, получаем следующее представление:
RSA = (100101001),(100001) = (M1 = 297, M2 = 33).
Далее последовательно шифруем M1 и M2:
C1 = Ek (M1) = Мхе = 2977 (mod 527) = 474.
При этом мы воспользовались тем, что
2977 = ((2972 )3 297)(mod527) = = ((2003(mod527)297)(mod527), C2 = Ek(M1) = М2е = 337(mod527) = 407.
В итоге получаем шифртекст: ух = 474, у2 = 407.
При расшифровании нужно выполнить следующую последовательность действий. Во-первых, вычислить
314
Системы с открытыми ключами
Dk(Cl) = (C1)mI mod527).
Отметим, что при возведении в степень удобно воспользоваться тем, что 343 = 256 + 64 + 16 + 4 + 2 + 1. На основании этого представления получаем:
4742 ? 174(mod527), 4744(mod527) s 237, 4748 (mod 527) = 307,47416 (mod 527) = 443, 47432 (mod 527) = 205, 47464 (mod 527) s 392, 474128 (mod 527) = 307, 474256 (mod527) = 443,
в силу чего
47 4 343 (mod 527) = Э (443 • 392 • 443 • 237 • 174 • 474)(mod527) = 297.
Аналогично
407343 (mod 527) = 33.
Возвращаясь к буквенной записи, получаем после расшифрования RSA.
Проанализируем вопрос о стойкости системы RSA. Нетрудно показать, что сложность нахождения секретного ключа системы RSA определяется сложностью разложения числа п на простые множители. В связи с этим нужно выбирать числа р и q таким образом, чтобы задача разложения числа п была достаточно сложна в вычислительном плане. Для этого рекомендуются следующие требования:
315
І лава 11
1) числа р и q должны быть достаточно большими, не слишком сильно отличаться друг от друга и в то же время быть не слишком близкими друг другу;
2) числа р и q должны быть такими, чтобы наибольший
общий делитель чисел р — 1 и q — 1 был небольшим; желательно, чтобы НОД(/? -1, q -1) = 2 ;
