Материал: MSZI_2003
Криптографическая
система
RSA
371
Широко
известным
примером
криптосистемы
с
открытым
ключом
является
крипто
-
система
RSA
,
разработанная
в
1977
году
и
получившая
название
в
честь
ее
создателей
:
Ривеста
,
Шамира
и
Эйдельмана
.
Стойкость
этой
системы
основывается
на
сложности
обратимости
степенной
функции
в
кольце
вычетов
целых
чисел
по
составному
модулю
n
(
при
надлежащем
выборе
модуля
).
Необходимые
сведения
из
элементарной
теории
чисел
1.
Простым
числом
называется
натуральное
число
,
имеющее
только
два
неравных
на
-
туральных
делителя
.
2.
Каждое
натуральное
число
единственным
образом
,
с
точностью
до
порядка
записи
сомножителей
,
представляется
в
виде
произведения
степеней
простых
чисел
.
3.
Наибольшим
общим
делителем
двух
целых
чисел
НОД
(a,b)
(
или
(a,b)
)
называется
наибольшее
целое
,
на
которое
без
остатка
делится
как
a
,
так
и
b
.
4.
Пусть
a > b
и
d = (a,b)
.
Тогда
существуют
целые
x
и
у
,
являющиеся
решением
уравнения
xa + yb = d
.
Если
d = 1
,
то
a
и
b
называются
взаимно
простыми
.
5.
Наибольший
общий
делитель
двух
чисел
можно
найти
с
помощью
алгоритма
Эвкли
-
да
.
Для
этого
a
делится
с
остатком
на
b
,
т
.
е
.
а
= q
1
b + r
1
.
Далее
вместо
a
и
b
,
рас
-
сматриваем
соответственно
b
и
r
1
:
b = q
2
r
1
+ r
2
.
На
следующем
шаге
роль
b
и
r
1
,
играют
r
1
и
r
2
:
r
1
= q
3
r
2
+ r
3
и
т
.
д
.
Процесс
заканчивается
на
некотором
шаге
k+1
,
для
которого
r
k+1
= 0
.
Тогда
НОД
(a,b) = r
k
.
Рассмотрим
пример
.
Найти
НОД
(1547, 560)
1547 = 2
х
560 + 427
560 = 1
х
427 + 133
427 = 3
х
133 + 28
133 = 4
х
28 + 21
28 = 1
х
21 + 7
21 = 3
х
7 + 0
НОД
(1547,560)=7
6.
Для
решения
уравнения
xa + yb = d
можно
использовать
данные
,
полученные
в
ка
-
ждом
шаге
алгоритма
Эвклида
,
двигаясь
снизу
вверх
,
с
помощью
выражения
остатка
через
другие
элементы
,
используемые
в
соответствующем
шаге
.
Например
,
из
r
2
=
q
4
r
3
+ r
4
следует
r
4
= r
2
+q
4
r
3
.
В
последнем
равенстве
r
3
можно
заменить
,
исходя
из
соотношения
r
1
= q
3
r
2
+ r
3
,
т
.
е
.
r
4
= r
2
– q
4
(q
3
r
2
– r
1
)
.
Поэтому
r
4
= (1 – q
4
q
3
)r
2
+ q
4
r
1
.
Таким
образом
,
мы
выразили
r
4
в
виде
целочисленной
комбинации
остатков
с
меньшими
номерами
,
которые
,
в
свою
очередь
,
могут
быть
выражены
аналогич
-
но
.
Продвигаясь
“
снизу
вверх
”,
в
конце
концов
,
мы
выразим
r
4
через
исходные
числа
a
и
b
.
Если
бы
мы
начали
не
с
r
4
,
а
с
r
k
,
то
получили
бы
r
k
= xa + yb = d
.
Рассмотрим
пример
.
Решить
1547
х
+ 560y = 7
372
Глава
18.
Криптографическая
защита
7 = 28 – 1
х
21 = 28 – 1
х
(133 — 4
х
28) = 5
х
28 - 1
х
1
ЗЗ
=
= 5
х
(427 - 3
х
133) — 1
х
13
З
= 5
х
427 – 16
х
(560 - 1
х
427)=
= 21
х
427 - 16
х
560 = 21
х
(1547 - 2
х
560) - 16
х
560 =
= 21
х
547 - 58
х
560
Решение
: x = 21, y = -58
7.
Число
a
сравнимо
с
числом
b
по
модулю
n
,
если
a – b
делится
на
n
.
Запись
дан
-
ного
утверждения
имеет
следующий
вид
:
а
= b(mod n)
.
Наименьшее
неотрица
-
тельное
число
а
,
такое
,
что
а
= A(mod n)
называется
вычетом
числа
A
по
моду
-
лю
n
.
Если
(a,n) = 1
,
то
существует
x
,
такое
,
что
x = a
-1
(mod n)
.
Действительно
,
(a,n) = 1 = d = ax + ny
,
поэтому
ax = 1(mod n)
.
Такое
число
x
назы
-
вается
обратным
к
а
по
модулю
n
и
записывается
в
виде
a
-1
(mod n)
.
8.
Пусть
функция
ϕ
(n)
,
где
n
—
натуральное
число
,
равна
количеству
натуральных
чи
-
сел
,
меньших
n
,
для
которых
(
а
,n)=1
.
Такая
функция
называется
функцией
Эйлера
.
Для
чисел
n
вида
n =
i
П
p
i
(
p
i
—
простое
)
функция
Эйлера
определяется
как
φ
(n) =
i
П
(p
i – 1)
.
9.
Теорема
Эйлера
.
Пусть
(
а
,n) = 1
.
Тогда
a
φ
(n)
= 1(mod n)
.
Следствие
.
Если
ed = 1(mod
φ
(n))
и
(a, n) = 1
,
то
(
а
e
)
d
=
а
(mod n)
.
10.
Для
большинства
вычетов
по
модулю
n = pq
показатель
степени
в
соотношении
a
φ
(n)
= 1(mod n)
может
быть
уменьшен
,
но
в
этом
случае
он
зависит
от
a
.
Наименьший
показатель
k(a)
,
для
которого
a
k(a)
= 1(mod n)
,
называется
порядком
числа
a
по
мо
-
дулю
n
и
обозначается
как
о
rd
n
(a)
.
Для
любого
a
значение
о
rd
n
(a)
является
делите
-
лем
значения
функции
Эйлера
φ
(n)
.
Алгоритм
RSA
Криптосистема
RSA
на
каждом
такте
шифрования
преобразует
двоичный
блок
от
-
крытого
текста
m
длины
size(n)
,
рассматриваемый
как
целое
число
,
в
соответствии
с
формулой
:
c = m
e
(mod n)
.
При
этом
n = pq
,
где
p
и
q
—
случайные
простые
числа
большой
разрядности
,
кото
-
рые
уничтожаются
после
формирования
модуля
и
ключей
.
Открытый
ключ
состоит
из
пары
чисел
e
и
n
.
Подключ
e
выбирается
как
достаточно
большое
число
из
диапазона
1
< e <
φ
(n)
,
с
условием
:
НОД
(e,
ϕ
(n)) = 1
,
где
ϕ
(n)
—
наименьшее
общее
кратное
чи
-
сел
p–1
и
q–1
.
Далее
,
решая
в
целых
числах
x
,
y
уравнение
xe + y
φ
(n) = 1
,
полагается
d =
х
,
т
.
е
.
ed = 1(
ϕ
(n))
.
При
этом
для
всех
m
выполняется
соотношение
m
ed
= m(n)
,
поэтому
знание
d
позволяет
расшифровывать
криптограммы
.
Чтобы
гарантировать
надежную
защиту
информации
,
к
системам
с
открытым
клю
-
чом
предъявляются
два
следующих
требования
.
1.
Преобразование
исходного
текста
должно
исключать
его
восстановление
на
основе
открытого
ключа
.
Криптографическая
система
RSA
373
2.
Определение
закрытого
ключа
на
основе
открытого
также
должно
быть
вычисли
-
тельно
нереализуемым
.
При
этом
желательна
точная
нижняя
оценка
сложности
(
ко
-
личества
операций
)
раскрытия
шифра
.
Алгоритмы
шифрования
с
открытым
ключом
получили
широкое
распространение
в
современных
информационных
системах
.
Рассмотрим
построение
криптосистемы
RSA
на
простом
примере
.
1.
Выберем
p = 3
и
q = 11
.
2.
Определим
n = 3 · 11 = 33
.
3.
Найдем
ϕ
(n) = (p – 1)(q – 1) = 20
.
4.
Выберем
e
,
взаимно
простое
с
20
,
например
,
e = 7
.
5.
Выберем
число
d
,
удовлетворяющее
7d = 1(m
о
d 20)
.
Легко
увидеть
,
что
d = 3(m
о
d 20)
.
Представим
шифруемое
сообщение
как
последовательность
целых
чисел
с
помощью
соответствия
:
А
= 1
,
B = 2
,
С
= 3
, ...,
Z = 26
.
Поскольку
size(n) = 6
,
то
наша
криптоси
-
стема
в
состоянии
зашифровывать
буквы
латинского
алфавита
,
рассматриваемые
как
блоки
,
Опубликуем
открытый
ключ
(e, n) = (7, 33)
и
предложим
прочим
участникам
системы
секретной
связи
зашифровывать
с
его
помощью
сообщения
,
направляемые
в
наш
адрес
.
Пусть
таким
сообщением
будет
CAB
,
которое
в
выбранном
нами
кодировке
принимает
вид
(3, 1, 2)
.
Отправитель
должен
зашифровать
каждый
блок
и
отправить
зашифрованное
сообщение
в
наш
адрес
:
RSA(C) = RSA(3) = 3
7
= 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1
7
= 1(mod 33);
RSA(B) = RSA(1) = 2
7
= 128 = 29(mod 33).
Получив
зашифрованное
сообщение
(9, 1, 29)
,
мы
сможем
его
расшифровать
на
ос
-
нове
секретного
ключа
(d, n) = (3, 33)
,
возводя
каждый
блок
в
степень
d = 3
:
9
3
= 729 = 3(m
о
d 33);
1
3
= 1(m
о
d 33);
29
3
= 24389 = 2(m
о
d 33).
Для
нашего
примера
легко
найти
секретный
ключ
перебором
.
На
практике
это
невоз
-
можно
,
т
.
к
.
для
использования
на
практике
рекомендуются
в
настоящее
время
следую
-
щие
значения
size(n)
:
•
512–768
бит
—
для
частных
лиц
;
•
1024
бит
—
для
коммерческой
информации
;
•
2048
бит
—
для
секретной
информации
.
Пример
реализации
алгоритма
RSA
представлен
в
листингах
18.1
и
18.2 (
компилято
-
ры
— Delphi, FreePascal).
374
Глава
18.
Криптографическая
защита
Листинг
18.1.
Пример
реализации
алгоритма
RSA
на
языке
Pascal
program Rsa;
{$APPTYPE CONSOLE}
{$IFDEF FPC}
{$MODE DELPHI}
{$ENDIF}
uses SysUtils, uBigNumber;
//
Генератор
случайных
чисел
var t: array[0..255] of Byte;
var pos: Integer;
var cbox: array[0..255] of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173,
47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200,
131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155,
198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41,
94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207,
163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221,
168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165,
122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92,
78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45,
73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50,
132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160,
170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171,
40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174,
140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227,
18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21,
137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107,
210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61,
249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84,
128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);
procedure InicMyRandom;
var i: Integer;
var s: string;
begin
WriteLn('
Введите
какой
-
либо
текст
для
инициализации
генератора
случайных
чисел
(
до
256
символов
):');
ReadLn(s);
i := 1;
while (i<=255) and (i<=Length(s)) do
Криптографическая
система
RSA
375
Продолжение
листинга
18.1
begin
t[i] := Ord(s[i]);
Inc(i);
end;
pos := 0;
WriteLn('OK');
WriteLn;
end;
function MyRandom: Cardinal;
var i: Integer;
var l: Cardinal;
begin
if (pos = 0) then
begin
for i := 1 to 255 do t[i] := cbox[(t[i-1]+t[i]) and 255];
for i := 254 downto 0 do t[i] := cbox[(t[i]+t[i+1]) and 255];
end;
l := 0;
for i := 0 to 3 do l := l shl 8 + Cardinal(t[pos+i]);
Result := l;
pos := (pos+4) and 255;
end;
//-------------------------------------------------------------
//
Главная
программа
var i,j: Integer;
var maxbit: Integer;
var none,ntwo: TBigNum;
var n1,n2: TBigNum;
var p,q,z: TBigNum;
var n,e,d: TBigNum;
var s1,s2: string;
begin
WriteLn;
InicMyRandom();
repeat
Write('
Введите
максимальный
размер
простых
чисел
(p
и
q)
в
битах
(8-257): ');
ReadLn(maxbit);