Асиметричне криптографічне RSA перетворення направленого шифрування класу RSA

Лекція № 11 а

З дисципліни  „ ОТЗІ”

Тема лекції

АСИМЕТРИЧНЕ КРИПТОГРАФІЧНЕ RSA ПЕРЕТВОРЕННЯ НАПРАВЛЕНОГО  ШИФРУВАННЯ КЛАСУ RSA

Навчальні питання

11.1 Імовірно стійка RSA криптосистема з відкритими ключами

11.2 Алгоритм формування RSA ключових пар

11.3 Методи оцінки стійкості RSA криптоперетворень

11.4 Приклади розв’язку задач RSA криптоперетворень

11.5 Основні визначення і вимоги безпеки до функцій гешування

ОСНОВНА ЛІТЕРАТУРА

1.  Горбенко І.Д. Основи теорії захисту інформації. Електронний конспект лекцій. Харків, ХНУРЕ, 2005 р.

2.  Горбенко І.Д. „Криптографічний захист інформації”. Навч. посібник Харків, ХНУРЕ, 2004 р.

В. Задірака . Компьютерная криптологія. Підручник. К, 2002 ,504с.

 Додаткова література

1.  А. Менезис, П. Ван Аршот, С. Ватсон. Руководство по прикладной криптографии CRC Press, 1997, электронная копия, 662 с

2.Брюс Шнайер. Прикладная криптография. М., изд. Триумф. 2002 г., 797 с

11.1 Імовірно стійка RSA  криптосистема з відкритими ключами

У 80-і роки ХХ століття широке розповсюдження отримала криптосистема з відкритими ключами відома на сьогодні, як RSA [12-15] система. Основною особливістю цієї системи є те, що в ній ключ зашифрування К^з не співпадає з ключем розшифрування К^р, тобто

,                                                         (1.48)

а знайти один ключ при відомому другому для відповідних значень загаль-носистемних параметрів можна не нижче ніж з субекспоненційною складністю. Хоч на сьогодні RSA криптосистема піддається нападкам і відносно неї даються різні прогнози, але вона проіснувала більше 25 років і дозволяє реалізувати направ-
лене шифрування, ЕЦП та слушні протоколи. Крім того, на наш погляд, RSA система дозволяє якісно реалізувати криптографічними методами таку основну функцію, як спостережливість, в змісті причетності відправника та отримувача. Так причетність відправника може бути забезпечена за рахунок здійснення цифрового підпису з використанням особистого (таємного) ключа, а перевірка цілісності та справжності підписаної інформації здійснюються з використанням особистого (публічного) ключа. Далі направлене шифрування може бути здійснене з використанням другої ключової пари, відкритий ключ отримувача якої застосовують для направленого шифрування, а особистий ключ застосовується для розшифрування повідомлення. Тому розглянемо цю класичну систему докладно.

RSA криптоалгоритм є блоковим, у ньому повідомлення М розбивається на блоки М_i, з довжиною блоку  (на сьогодні 768 біт мінімум), реально 1024, 2048 і більше бітів. Блок криптограма С_і обчислюється за правилом

,                                              (1.49)

де  – є відкритий ключ прямого перетворення, N – модуль перетворення є добутком виду

,                                                 (1.50)

де в свою чергу P, Q – великі прості числа.

Якщо  l_p є довжина простого числа Р, наприклад в бітах, а l_q – довжина простого числа Q, то довжина модуля N

.                                               (1.51)

Розшифрування блока криптограми здійснюється за правилом:

,                                     (1.52)

де D_к – є ключ зворотного перетворення, тобто розшифрування .

Однозначність розшифрування можна підтвердити, підставивши (1.52) в (1.49). В результаті отримаємо:

.                                         (1.53)

Оскільки ключова пара  пов’язана між собою порівнянням:

,                                          (1.54)

де  є функцією Ойлера від модуля N

= .

Якщо (1.54) має єдине розв’язання, тобто існує єдина пара , то такий шифр є однозначним і при таких умовах RSA криптосистема забезпечує однозначне направлене шифрування.

Зазначимо, що з точки зору забезпечення максимально можливої крипто-стійкості прості числа P i Q мають бути сильними в широкому або вузькому значенні [7]. Так просте число Р вважатимемо сильним в широкому значенні, якщо

,                                                              (1.55)

де R – також велике просте число.

Аналогічно визначається і сильне в широкому значенні просте число Q.

Просте число Р вважається сильним у вузькому значенні, якщо  містить в своєму канонічному розкладі велике просте число R, Р+1 містить в своєму розкладі велике просте число S, а крім того R-1 містить в своєму розкладі велике число T.

Хоч розробниками RSA системи вважають Рона Рівеста, Аді Шаміра і Леонарда Адлемана, в підручнику „Фізика квантової інформації”, авторів Д. Бауместер, А. Екерт, А. Цайлингер на стор. 37-38 стверджується, що в Англії RSA подібний алгоритм було винайдено на декілька років раніше.

11.2 Алгоритм формування RSA ключових пар

Генерація ключів (задачі)