Криптографічна система RSA (Rivest-Shamir-Adleman)

Авторами алгоритму RSA, запропонованого в 1977 р., є Р.Рівест (Rivest), А.Шамір (Shamir) і А.Адлеман (Adleman). Надійність алгоритму базується на складності факторизації (розкладення на множники) великих чисел і складності обчислення дискретних алгоритмів (знахождення x при відомих a, b і n із рівняння a^x = b (mod n)).

Алгоритм RSA складається з трьох частин: генерування ключів, шифрування і дешифрування.

 

1. Генерування ключів.

 

Оберемо два великих різних простих числа p і q (Натуральне число називається простим, якщо воно ділиться тільки на себе і на 1.) та знайдемо їх добуток

n = pq.

Обчислимо функцію Ейлера j(n) за формулою

j(n) = (p-1)(q-1).

Закритий ключ d обираємо з умов

d < j(n) і

d взаємно просте з j(n),

тобто d і j(n) не мають спільних дільників.

Відкритий ключ e обираємо з умов

e < j(n) і

de = 1 (mod j(n)).

Остання умова означає, що різниця de - 1 повинна ділитись на j(n) без залишку. Для визначення числа e слід підібрати таке число k, що

de - 1 = j(n)*k.

В алгоритмі RSA

(e, n) – відкритий ключ,

(d, n) – секретний ключ.

 

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

 

Вихідне повідомлення розбивається на блоки M_i однакової довжини. Кожен блок представляється у вигляді великого десяткового числа, менше n, і шифрується окремо. Шифрування блока M (M – десяткове число) здійснюється за наступною формулою

 

M^e = C (mod n),

 

де C – шифрблок, що відповідає блоку відкритого повідомлення M. Шифрблоки з`єднуються в шифрограму.

 

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

 

При дешифруванні шифрограма розбивається на блоки відомої довжини і кожен шифрблок дешифрується окремо за наступною формулою

 

C^d = M (mod n).

Додаток Д

 

Таблиця простих чисел

Додаток Е

Функція хешування

 

Функцією хешування (хеш-функцією або вкорочуючей функцією) називається перетворення даних, що переводить рядок бітів M довільної довжини в рядок бітів h(M) деякої фіксованої довжини (кілька десятків чи сотень біт).

Хеш-функція h(M) повинна задовольняти наступним умовам:

1. хеш-функція h(M) повинна бути чутливою до будь-яких змін вхідної послідовності M;

2. для даного значення h(M) повинно бути неможливо знайти значення M;

3. для даного значення h(M) повинно бути неможливо знайти значення M^’ ¹ M таке, що h(M^‘) = h(M).

 

Ситуація, за якої для різних вхідних послідовностей M, M^‘ співпадають значення їх хеш-образів: h(M) = h(M^‘), називається колізією.

При побудові хеш-образу, вхідна послідовність M розбивається на блоки M_i фіксованої довжини і оброблюється поблочно за формулою

 

H_i = f(H_i-1, M_i).

 

Хеш-значення, що обчислюється при введенні останнього блоку повідомлення, стає хеш-значенням всього повідомлення.

В якості прикладу розглянемо спрощений варіант хеш-функції із рекомендацій МККТТ Х.509:

H_i = (H_i-1 + M_i )² mod n,

 

де n = pq, p і q – великі прості числа, H₀ - довільний початковий вміст, M_i - i -тий блок повідомлення M = M₁ M₂ … M_k.

 

 

 

Додаток Ж

Електронний цифровий підпис

 

Цифровий підпис у цифрових документах грає ту ж роль, що і підпис, поставлений від руки в документах на папері: це дані, що приєднуються до повідомлення, котре передається, та підтверджують, що власник підпису склав чи завірив це повідомлення. Отримувач повідомлення за допомогою цифрового підпису може перевірити, що автором повідомлення є саме власник підпису і що в процесі передачі не було порушено цілісність отриманих даних.

При розробці механізму цифрового підпису виникають наступні задачі:

·створити підпис таким чином, щоб її неможливо було підробити;

·мати можливість перевірки того, що підпис дійсно належить вказаному власнику;

·мати можливість запобігти відмові від підпису.