Topic 43

3. Криптосистема шифрування даних RSA

Надійність алгоритму ґрунтується на труднощі факторизації великих чисел та труднощі обчислення дискретних логарифмів.

У криптосистемі RSA відкритий ключ A, секретний ключ B, повідомлення М і криптограма С належать безлічі цілих чисел

Тут Р і Q – випадкові великі прості числа. Для забезпечення максимальної безпеки вибирають Р і Q рівної довжини та зберігають у секреті.

Безліч Z N з операціями складання та множення за модулем N утворює арифметику за модулем N.

Відкритий ключ A вибирають випадковим чином так, щоб виконувались умови:

, (7)

, (8)

де – функція Ейлера.

Функція Ейлера вказує кількість позитивних цілих чисел в інтервалі від 1 до N, взаємно прості з N.

Друга із зазначених вище умов означає, що відкритий ключ A і функція Ейлера повинні бути взаємно простими.

Далі, використовуючи розширений алгоритм Евкліда, обчислюють секретний ключ k B такий, що

k B * До B = 1 (mod() (9)

Це можна здійснити, тому що одержувач знає пару простих чисел (P, Q) і може легко знайти . Зауважимо, що k B і N мають бути взаємно простими.

Відкритий ключ B використовують для шифрування даних, а секретний ключ k B - для розшифрування.

Перетворення шифрування визначає криптограму через пару (відкритий ключ К B , повідомлення М) відповідно до наступної формули:

(10)

В якості алгоритму швидкого обчислення значення використовують ряд послідовних зведень в квадрат цілого М і множень на М з приведенням по модулю N.

Звернення функції, тобто. визначення значення М за відомими значеннями, B і N, практично не здійсненно при N » 2 512 .

Проте обернену задачу, тобто. задачу розшифрування криптограми, можна вирішити, використовуючи пару (секретний ключ k B, криптограма С) за наступною формулою:

. (11)

Процес розшифрування можна записати так:

D B (Е B (М)) = М. (12)

Підставляючи (12) значення (10) і (11), отримуємо:

(13)

Величина відіграє у теоремі Ейлера, яка стверджує, що й НОД (х,N)=1, то

або у дещо більш загальній формі

(14)

Зіставляючи вирази (4.13) і (4.14), отримуємо

або, що те саме,

Саме тому обчислення секретного ключа k B використовують співвідношення (9).

Таким чином, якщо криптограму

звести в ступінь k B то в результаті відновлюється вихідний відкритий текст М, так як

Таким чином, одержувач, який створює криптосистему, захищає два параметри:

секретний ключ k B та
пару чисел (P, Q),

твір яких дає значення модуля N. З іншого боку, одержувач відкриває значення модуля N і відкритий ключ До B .

Противнику відомі лише значення До B і N. Якби він зміг розкласти число N на множники Р і Q, він дізнався б "потайний хід" - трійку чисел , обчислив значення функції Ейлера

та визначив значення секретного ключа k B .

Проте, як зазначалося, розкладання дуже великого N на множники обчислювально не здійсненно (за умови, що довжини обраних Р і Q становлять щонайменше 100 десяткових знаків).

Процедури шифрування та розшифрування

у криптосистемі RSA

Припустимо, що користувач А хоче передати користувачеві повідомлення в зашифрованому вигляді, використовуючи криптосистему RSA. У такому разі користувач А виступає у ролівідправника повідомлення, а користувач - у ролі одержувача. Як зазначалося вище, криптосистему RSA має сформувати одержувач повідомлення, тобто. Користувач В. Розглянемо послідовність дій користувача В та користувача А.

1. Користувач вибирає два довільних великих простих числа Р і Q.

2. Користувач обчислює значення модуля N = Р * Q.

3. Користувач В обчислює функцію Ейлера

і вибирає випадковим чином значення відкритого ключа B з урахуванням виконання умов:

4. Користувач В обчислює значення секретного ключа k B , використовуючи розширений алгоритм Евкліда під час вирішення порівняння

5. Користувач В пересилає користувачеві А пару чисел (N, К B ) незахищеним каналом.

Якщо користувач А хоче передати користувачеві У повідомлення М, він виконує такі кроки.

6. Користувач А розбиває вихідний відкритий текст М на блоки, кожен із яких може бути представлений у вигляді числа

7. Користувач А шифрує текст, поданий у вигляді послідовності чисел М, за формулою

та відправляє криптограму

C 1 , 2 , 3 . C i , .

8. Користувач розшифровує прийняту криптограму

C 1 , 2 , 3 . C i , .

використовуючи секретний ключ k B за формулою

В результаті буде отримана послідовність чисел M i , які є вихідним повідомленням М. Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, вміти оперативно обчислювати значення ключів B і k B .

приклад. Шифрування повідомлення CAB. Для простоти обчислень будуть використовуватись невеликі числа. Насправді застосовуються дуже великі числа.

Дії користувача Ст.

1. Вибирає Р=3 та Q=11.

2. Обчислює модуль N=P*Q=3*11=33.

3. Обчислює значення функції Ейлера N=33:

Вибирає як відкритий ключ До B довільне число з урахуванням виконання умов:

4. Обчислює значення секретного ключа k B , використовуючи розширений алгоритм Евкліда при вирішенні порівняння (див. додаток)

B є T 1 (mod20).

Рішення дає k B =3.

5. Пересилає користувачеві А пару чисел (N= 3, k B =7).

Дії користувача А.

6. Представляє повідомлення, що шифрується, як послідовність цілих чисел в діапазоні 0 . 32. Нехай буква А представляється як число 1, буква У - як число 2, буква С - як число 3. Тоді повідомлення CAB можна як послідовність чисел 312, тобто. M 1 = 3, M 2 = 1, M 3 = 2.

7. Шифрує текст, поданий у вигляді послідовності чисел M 1 , M 2 і M 3 , використовуючи ключ B = 7 і N = 33, за формулою

Надсилає користувачу У криптограму

C1, C2, C3 = 9, 1, 29.

Дії користувача Ст.

8. Розшифровує прийняту криптограму C 1 C 2 C 3 використовуючи секретний ключ k B =3, за формулою

Таким чином, відновлено вихідне повідомлення: CAB – 3 1 2.

Безпека та швидкодія криптосистеми RSA

p align="justify"> Безпека алгоритму RSA базується на труднощі вирішення завдання факторизації великих чисел, що є творами двох великих простих чисел. Дійсно, криптостійкість алгоритму RSA визначається тим, що після формування секретного ключа k B і відкритого ключа B "праються" значення простих чисел Р і Q, і тоді виключно важко визначити секретний ключ k B по відкритому ключу B, оскільки для цього необхідно вирішити задачу знаходження дільників Р та Q модуля N.

Розкладаннявеличини N на прості множники Р і Q дозволяє обчислити функцію і потім визначити секретне значення k B використовуючи рівняння

B * k B є 1 (mod (j (N)).

Іншим можливим способом криптоаналіз алгоритму RSA є безпосереднє обчислення або підбір значення функції j (N) = (Р -1) (Q -1). Якщо встановлено значення j (N), то помножувачі Р та Q обчислюються досить просто. Справді, нехай

у = (Р – Q) 2 = (Р + Q) 2 – 4*N.

Знаючи j(N), можна визначити х і потім у; знаючи х і у можна визначити числа Р і Q з наступних співвідношень:

Однак ця атака не простіше завдання факторизації модуля N [24].

Завдання факторизації є важкою задачею для великих значень модуля N.

Один з найбільш швидких алгоритмів, відомих в даний час, NFS (Number Field Sieve) може виконати факторизацію великого числа N (з числом десяткових розрядів більше 120) за число кроків, що оцінюються величиною

Було зроблено спробу розрахунку оцінок безпечних довжин ключів асиметричних криптосистем на найближчі 20 років виходячи з прогнозу розвитку комп'ютерів та їх обчислювальної потужності, а також можливого вдосконалення алгоритмів факторизації. Ці оцінки (табл.1.) дано для трьох груп користувачів (індивідуальних користувачів, корпорацій та державних організацій), відповідно до відмінності вимог до їх інформаційної безпеки. Звичайно, дані оцінки слід розглядати як суто приблизні як можливу тенденцію змін безпечних довжин ключів асиметричних криптосистем з часом.

Таблиця 1. Оцінка довжин ключів для асиметричних криптосистем, біт