Алгоритм RSA

Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = m^e(mod n).

При этом n = pq, где p и q — случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e выбирается как достаточно большое число из диапазона 1 < e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) — наименьшее общее кратное чисел p–1 и q–1. Далее, решая в целых числах x, y уравнение xe + yφ(n) = 1, полагается d = х, т.е. ed = 1(j(n)). При этом для всех m выполняется соотношение m^ed = m(n), поэтому знание d позволяет расшифровывать криптограммы.

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

1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.

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

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

Рассмотрим построение криптосистемы RSA на простом примере.

1. Выберем p = 3 и q = 11.

2. Определим n = 3 ∙ 11 = 33.

3. Найдем j(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⁷ = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1⁷ = 1(mod 33);
RSA(B) = RSA(1) = 2⁷ = 128 = 29(mod 33).

Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:

9³ = 729 = 3(mоd 33);
1³ = 1(mоd 33);
29³ = 24389 = 2(mоd 33).

Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):

· 512–768 бит — для частных лиц;

· 1024 бит — для коммерческой информации;

· 2048 бит — для секретной информации.

Пример реализации алгоритма RSA представлен в листингах 18.1 и 18.2 (компиляторы — Delphi, FreePascal).

Листинг 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