|
|  |
RSA – алгоритмів кодування з відкритим ключем, Детальна інформація
|
Реферат на тему:
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 \xF0BA\xF0201 (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 декодується правильно.
Оскільки p та q – прості числа, то \xF06A (p * q) = \xF06A (n) = (p - 1) * (q - 1), де \xF06A – функція Ейлера. З умови вибору ключа d маємо: d * e mod \xF06A(n) = 1, або d * e = \xF06A (n) * k + 1 для деякого натурального k.
cd mod n = (me)d mod n = m (e * d) mod n = m ^ (\xF06A (n) * k + 1) mod n = (m \xF06A (n) mod n) k * m = 1 k * m = m, оскільки за теоремою Ейлера m\xF06A (n) mod n = 1.
Означення. RSA системою називають функцію RSAn,e(x) = xe mod n та обернену їй RSA-1n,e(y) = yd mod n, де e – кодуюча, а d – декодуюча експонента, x, y \xF0CE\xF020Zn*.
Приклад
1. Оберемо два простих числа: p = 17, q = 19;
|
| Коментарі до даного документу |
|
|
|
|
|
|
Скачати "Реферат на тему RSA – алгоритмів кодування з відкритим ключем"
