RSA – алгоритмів кодування з відкритим ключем

Перший алгоритм кодування з відкритим ключем (Public Key Encryption, далі PKE) було запропоновано Вітфілдом Діффі та Мартіном Хелманом у Стендфордському університеті. Вони, а також незалежно від них Ральф Меркл, розробили основні його поняття у 1976 році. Перевага PKE полягає у відсутності потреби секретної передачи ключа.

PKE базується на нерозв’язності проблеми розкладу натурального числа на прості множники.

RSA схему шифрування було запропоновано у 1978 році та названо іменами трьох його винахідників: Роном Рівестом (Ron Rivest), Аді Шаміром (Adi Shamir) та Леонардом Адлеманом (Leonard Adleman). RSA належить до класу алгоритмів кодування з відкритим ключем.

У 80-х роках криптосистема переважно використовувалася для забезпечення секретності та достовірності цифрових даних. У сучасному світі RSA використовується в web – серверах та браузерах для зберігання таємності даних що передаються по мережі, .

Схема RSA базується на обчисленні виразів зі степенями. Відкритий текст шифрується блоками, довжина кожного із яких менша за деяке число n.

Алгоритм генерації ключа

A повинен згенерувати відкритий та секретний ключі:

1. Згенерувати два великих простих числа p та q приблизно однакової довжини;

2. Обчислити n = p * q, fi = (p – 1) * (q – 1);

3. Вибрати натуральне e, 1 < e < fi, взаємно просте з fi;

4. Використовуючи розширений алгоритм Евкліда, розв’язати рівняння

d * e 1 (mod fi).

Відкритий ключ: (n, e). Секретний ключ: d.

Схема шифрування RSA

B шифрує повідомлення m та надсилає A.

1. Шифрування. В робить наступні дії:

а) отримати відкритий ключ (n, e) від А;

б) представити повідомлення у вигляді натурального числа m з проміжку [1..n];

в) обчислити c = me mod n;

г) надіслати шифротекст c до А.

2. Дешифрування. Для отримання повідомлення m із шифротксту c А робить наступні дії:

а) використовуючи секретний ключ d, обчислити m = cd mod n.

Теорема. Шифр c декодується правильно.