Функционирование криптографических систем при конкретных параметрах, страница 3

Leg (y, p) - символ Лежандра, вычисляется как символ Якоби.

3. Теоретическая часть.

3.1. Криптосистема RSA.

3.1.1. Описание     системы.

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

Абонент A:

·  Генерирует два простых числа p и q примерно одинакового размера.

·  Вычисляет n=pq, j(n) =(p-1)(q-1).

·  Выбирает случайное число e, 1< e < j(n), такое, что НОД(e, j(n))=1.

·  Используя расширенный алгоритм Евклида, вычисляет d,

1<d< j(n), такое, что ed=1 (mod j(n)).

·  Открытым ключом объявляет пару чисел (n,e), в качестве секретного ключа хранит число d.

Числа n,e,d называют, соответственно, модулем, экспонентой зашифрования и расшифрования.

Шифрование:

Абонент B:

·  Получает копию открытого ключа (n,e) абонента А.

·  Представляет сообщение, как число m из интервала [0, n-1] (в необходимых случаях разбивает его на блоки, являющиеся числами в этом интервале).

·  Вычисляет c=m^e mod n.

·  Посылает шифртекст c абоненту А.

Расшифрование:

Абонент A:

·  Получает шифртекст c.

·  Используя секретный ключ d, вычисляет сообщение m=c^d mod n.

3.1.2. Пример.

·  Генерация ключей:

Пусть p = 73, q = 127, тогда n = 9271, j(n) = 9072, e = 17,d = 1601.

·  Шифрование:

m = 610

c = m^e mod n = 610¹⁷ mod 9271 = 8335

·  Расшифрование:

m = c ^d mod n = 8335¹⁶⁰¹ mod 9271 = 610

3.1.3. Задание.

·  Спроектировать систему по следующим параметрам.

Сгенерировать и сохранить p= p((₁[k(n)]₆)₁₀),

Сгенерировать и сохранить q= p((₁[k(n)]₆)₁₀+4),

Вычислить n=p×q,

Вычислить phi=j(n) = (p-1)(p-1).

Взять e взаимно простое с phi.

Вычислить d=e^-1 mod phi.

·  Взять сообщение m=k(n).

Вычислить шифробозначение (криптограмму) c=k(N)^emod n.