Модульная арифметика

b – остаток

n – модуль числа

Например: 17 = 2mod15 17/15 = 1 + ост2 целая часть, равная 1 отбрасывается,

b = 2, n = 15

17 = 2mod5 17/5 = 3 + ост2 b = 2, n = 5 целая часть, равная 3 отбрасывается,

17 = 1mod4 17/4 = 4 + ост1 b =1, n = 4 целая часть, равная 4 отбрасывается.

используется в RSA.

Генерация ключей в RSA

1. Выбираем два взаимнопростых фактора p и q. Например: p = 3, q = 11 p ¹ q;

2. Вычисляем модуль RSA. n = pq (mod RSA = p*q = 33);

3. Вычисляем функцию Эйлера m = (p – 1)(q – 1). (m = (3 – 1)(11 – 1) = 20);

4. Выбираем фактор d < n – простое число (d = 7);

5. Из модульного уравнения d*e = 1modm вычисляем фактор e. Преобразуем:

6. Составляем секретный и открытый ключи RSA.

У нас:

7. Для сохранения (обеспечения) секретности ключей необходимо «убрать мусор», уничтожить p, q, m.

а) Шифрование: – по modn вычислить остаток;

б) Дешифрование: – вычислить остаток по modn.

При этом сообщение S и шифротекст С не должен превосходить модуль RSA n

(S,C) £ n

Сообщение S и шифротекст С сворачиваются в целое число.

Свёртка: S = АДА

Исходник записывается в форме полинома с основанием равным длине алфавита А = {А,Б,В,...,Я} – 32 символа.

, где n – длина сообщения.

Развёртка: 1185 32

96 37 32

225 32 1 = А

224 5 = Д

А

Шифрование: Исходник S = 1185

Так как сообщение S превышает модуль RSA n = 33, то сообщение S разбивают на блоки, и каждый блок шифруется самостоятельно S = 1185 > n = 33

Дешифрование:

Криптостойкость RSA:

1. Сверхвысокая криптостойкость, ключи не взламываются;
2. Ключи долговременные, постоянные;
3. Не нужен закрытый канал связи, т.к. секретный ключ не передается.

Недостаток: системы работают медленно, т.к. идет большая вычислительная работа (возведение больших целых чисел в большую целую степень).