Опис алгоритму.

Алгоритм складається з трьох етапів :

• Генерація ключів.

• Шифрування.

• Дешифрування.

Процес створення пари ключів.

Вибирають два досить великі прості числа p і q . Для їх добутку n=p*q значення функції Ойлера дорівнює

(n)=(p-1)*(q-1)=n-p-q+1. (4.1)

Далі випадковим чином вибирають елемент e, що не перевищує значення (n) і взаємно простий з ним.

Іншими словами e є випадковим елементом із множини Z^*_(n). Для е за алгоритмом Евкліда знаходимо елемент d, обернений до е в Z^*_(n), тобто такий, що

d<(n) і ed1(mod(n)). (4.2)

Рис.1. Блок схема алгоритму генерації ключів.

Як результат покладають :

Відкритий ключ : e,n.

Таємний ключ : d,n.

Блок схему генерації ключів показано на рис. 3.

Як видно з рисунка в даному алгоритмі використовується наступні під алгоритми :

• знаходження простих чисел див. Рисунку 4.2.

• знаходження найменшого спільного дільника (NDS) дивися рисунок 4.3.

• знаходження числа D за алгоритмом Евкліда (MOD) дивися рисунок 4.4.

Шифрування

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

Скажімо, якщо блок записаний у вигляді війкового слова довжини m, то повинна виконуватись нерівність 2^m<n. Блок M розглядається як елемент кільця Z_n і як такий може підноситись до степеня за модулем n.

Алгоритм шифрування E у системі RSA полягає у піднесенні M до степеня e, дивися рисунок 4.5. Записуємо це так

E(M)=M^emod(n). (4.3)

В результаті отримується блок криптотексту C=E(M), який також є цифровим записом якогось елемента кільця Z_n.

D_X(E_X(M))= E_X(D_X(M))=M. (4.4)

Рис. 2. Блок схема алгоритму знаходження простих чисел.

Аутентифікація повідомлення.

В алгоритмі шифрування RSA кожен абонент X має пару ключів - загальновідомий відкритий (n_X,e_X) і таємний d_X, який знає лише X і ніхто інший. Таким чином, будь хто може скористатись алгоритмом шифрування E_X абонента X, але тільки він сам володіє алгоритмом дешифрування D_X. Важливим є виконання таких співвідношень для довільного повідомлення M. Ці співвідношення зводяться до рівностей :

(M^eX)^dX=(M^dX)^eX=M в Z_nX (4.5)

І виражають той факт, що шифруюче відображення E_X та дешифруюче D_X є взаємно оберненими.

Припустимо, що абонент А хоче переслати повідомлення M абонентові Б таким чином, щоб той був певен, що повідомлення справді послане абонентом А, а не опонентом. Для цього пропонується такий протокол, в якому (E_a,D_a) та (E_b,D_b) - алгоритми шифрування да дешифрування абонентів А та Б.

• Абонент А обчислює C=E_b(D_a(M)) і посилає C абоненту Б

• Абонент Б отримавши C, обчислює M=E_a(D_b(C)).

Коректність протоколу зводиться до рівності :

E_A(D_B(E_B(D_A(M))))=M, (4.6)

яка випливає із співвідношення (4.5).

Рис. 3. Блок схема алгоритму знаходження найменшого спільного дільника (NDS).

Рис. 4. Блок схема алгоритму знаходження числа D за алгоритмом Евкліда (MOD).

Ефективність. Абоненти А та Б використовують ефективні алгоритми шифрування та дешифрування криптосистеми RSA. Зауважимо, що абонент А використовує свій приватний алгоритм D_a та відомий всім алгоритм E_b. Те ж саме із абонентом Б - він використовує особистий алгоритм D_b і загальновідомий алгоритм E_a.

Рис. 5. Блок схема алгоритму шифрування та дешифрування.

Конфіденційність. Під конфіденційністю цього протоколу ми розуміємо його надійність як звичайної криптосистеми для пересилання повідомлень. В такому розумінні конфіденційність є досить інтуїтивним фактом, що грунтується на надійності алгоритму RSA.

Перед опонентом, який перехопив криптотекст C, виникає завдання визначити M із E_b(D_a(M)). Припустимо, що опонент знає навіть набагато більше, а саме приватний алгоритм D_a абонента А. Тоді визначення M для опонента рівносильне визначенню D_a(M). Але визначення D_a(M) із E_b(D_a(M)) є нічим іншим, як задачею зламу RSA.