Необходимые сведения из элементарной теории чисел

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₁b + r₁. Далее вместо a и b, рассматриваем соответственно b и r₁: b = q₂r₁+ r₂. На следующем шаге роль b и r₁, играют r₁ и r₂: r₁ = q₃r₂ + r₃ и т.д. Процесс заканчивается на некотором шаге 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₂ = q₄r₃ + r₄ следует r₄ = r₂ +q₄r₃. В последнем равенстве r₃ можно заменить, исходя из соотношения r₁ = q₃r₂ + r₃, т.е. r₄ = r₂ – q₄(q₃r₂ – r₁). Поэтому r₄ = (1 – q₄q₃)r₂ + q₄r₁. Таким образом, мы выразили r₄ в виде целочисленной комбинации остатков с меньшими номерами, которые, в свою очередь, могут быть выражены аналогично. Продвигаясь “снизу вверх”, в конце концов, мы выразим r4 через исходные числа a и b. Если бы мы начали не с r₄, а с r_k, то получили бы r_k = xa + yb = d. Рассмотрим пример.

Решить 1547х + 560y = 7

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. Пусть функция j(n), где n — натуральное число, равна количеству натуральных чисел, меньших n, для которых (а,n)=1. Такая функция называется функцией Эйлера. Для чисел n видаn = (p_i — простое) функция Эйлера определяется как φ(n) =.

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, 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