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
º 1 (mod fi
).

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

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

RSA

B

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

.

1. Шифрування. В

робить наступні дії:

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

;

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

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

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

.

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

робить наступні дії:

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

Теорема.

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

Оскільки p
та q
– прості числа, то j (p
* q
) = j (n
) = (p
-1) * (q
-1), де j – функція Ейлера. З умови вибору ключа d
маємо: d
* e
modj(n
) = 1, або d
* e
= j (n
) * k
+ 1 для деякого натурального k.

cd
modn
= (m
e
)d
modn
= m
(
e
*
d
)
modn
= m
^ (
j
(
n
) *
k
+ 1)
modn
= (m
j
(
n
)
modn
) k
*
m
= 1 k
*
m
= m
, оскільки за теоремою Ейлера m
j
(n
)
mod n
= 1.

Означення.
RSA

системою

називають функцію RSAn
,
e
(x
) = xe
modn
та обернену їй RSA-1
n
,
e
(y
) = yd
modn
, де e
– кодуюча, а d
– декодуюча експонента, x
, y
Î Zn
*
.

Приклад

1. Оберемо два простих числа: p
= 17, q
= 19;

2. Обчислимо n
= 17 * 19 = 323, fi
= (p
- 1) * (q
- 1) = 16 * 18 = 288;

3. Оберемоe
= 7 (НСД(e
, fi
) = 1) та розв’яжемо рівняння 7 * d
º1 (mod 288), звідки d
= 247.

Побудовано RSAсистему: p
= 17, q
= 19, n
= 323, e
= 7, d
= 247.

Відкритий ключ: n
= 323, e
= 7, секретний ключ: d
= 247.

1. m
= 4. Кодування: 47
mod 323 = 234.Декодування: 234247
mod 323 = 4.

2. m
= 123. Кодування: 1237
mod 323 = 251.Декодування: 251247
mod 323 = 123.

За відомим шифром c
(c
= me
modn
) злодій, маючи відкритий ключ e
та n
, бажає знайти повідомлення m
.Він починає будувати послідовність чисел

c
, ce
, , , …

Оскільки обчислення відбуваються в групі Zn
*, то елемпнти послідовності знаходяться в межах від 0 до n
- 1. Отже існує таке натуральне k
, що с
= . Враховуючи що c
= me
modn
, маємо: me
= або m
= .

Таким чином для знаходження повідомлення m
за його шифром c
необхідно побудувати послідовність c
, ce
, , , …, , = c
, і взяти її передостаннє число.

Розв’язати рівняння: m
7
mod 323 = 251.

e
= 7, n
= 323, c
= 251.