Створення цифрового підпису за допомогою RSA

Важливою позитивною рисою алгоритму RSA є можливість його застосування як для шифрування, так і для створення цифрового підпису. Ці операції використовують подібні обчислення. Щоб підписати повідомлення m, володар закритого ключа обчислює s = m^d (mod n). Пара (m s) утворює підписане повідомлення. Щоб переконатися у дійсності підпису, кожний, хто знає відкритий ключ, може перевірити, чи виконується рівняння s^e = m (mod n).

Безпека цифрового підпису ґрунтується на складності обчислення дискретного логарифму (визначення d при відомих s та m: d =(log_m s) mod n). Зауважимо, що безпека шифрування забезпечується складністю визначення m за відомими m ^e та e, тобто обчислення кореня степеня e з числа m ^e за модулем n.

 

Відкриті показники степенів

Розглянутий алгоритм має один недолік. Якщо e має спільний дільник r > 1 з числом t = НСК(p - 1, q - 1), то потрібного d не існує (для будь-якого k, e^k mod t кратне r). Тому параметри p, q і e слід вибирати так, щоб не виникала подібна ситуація. Використання відкритого показника малої довжини підвищує ефективність RSA, оскільки для піднесення до степеню числа e потребує менше обчислень. Тому доцільно спочатку обрати e, а потім - p, q з урахуванням сформульованої вище умови. Необхідно ретельно стежити, щоб функції шифрування і цифрового підпису не взаємодіяли якимось небажаним способом. Неможна допускати, щоб зловмисник міг розшифрувати повідомлення c, переконавши володаря закритого ключа підписати це повідомлення. У кінцевому рахунку підписування повідомлення c – це те саме, що і розшифровування тексту c. Функції шифрування, які розглянемо пізніше, допомагають не допустити такої ситуації, однак використовувати одну і ту ж операцію RSA у якості обох функцій все ж таки не варто. Можна було б застосовувати для перевірки автентичності і шифрування різні ключі RSA, однак це підвищує складність обчислень і подвоює об’єм даних ключа. Поширеним способом розв’язання цієї задачі є застосування різних значень e для цифрових підписів і для шифрування при спільному значенні n. Часто при шифруванні покладають e = 5, а при підписуванні - e = 3. Це відокремлює системи, тому що кубічні корні і корні п’ятого степеню за модулем n не залежать один від одного. Крім того, встановлено, що знання одного з цих коренів не допомагає зловмиснику обчислити інший. Застосування чисел 3 і 5 дає змогу отримати достатню ефективність системи. Значення 3 використовується при підписуванні, оскільки шифрування кожного фрагменту повідомлення здійснюється один раз, а перевірка підпису може виконуватися багаторазово.

Закритий ключ

Зловмиснику дуже важко знайти параметри закритого ключа p, q, t або d, незважаючи на те, що n, e йому відомі. При достатньо великому n не існує відомого алгоритму визначення закритого ключа за прийнятний час. Найкращий відомий розв’язок полягає у розкладанні n, на множники p, q, і наступній спробі обчислення d. Ось чому розкладання на прості множники відіграє таку важливу роль у криптографії. Виявляється, що коли зловмисник знає хоча б один з параметрів закритого ключа, він може обчислити будь-який інший. Якщо відоме p, q = n / p, t = НСК(p - 1, q – 1), d = (1/ e)mod t. Якщо відоме t = (p – 1) (q – 1) / НСД(p - 1, q – 1), то оскільки добуток (p – 1) (q – 1) близький до n, НСД(p - 1, q – 1) – це найближче до n / t ціле число. (Тут враховується, що ймовірність того, що НСД(p - 1, q – 1) дуже велике число, мала. Це дозволяє зловмиснику обчислити (p – 1) (q – 1). Далі він може обчислити s = p + q = n - (p – 1) (q – 1) + 1, а це дає змогу отримати квадратне рівняння відносно p. p q = n, p + q = s.

Підставляючи у перше рівняння вираз для q, отриманий з другого, маємо p (s – p)= n, або p ²- s p + n = 0.

У випадку, коли зловмисник знає d, він може визначити t підбором. Дійсно, оскільки e мале, і d < t, величина ed – 1 лише у декілька разів може бути більше t. Зловмисник може підібрати відповідний множник, обчислити t, а потім спробувати знайти p і q. У разі невдачі він може перебрати інші варіанти. При підписуванні або шифруванні повідомлення володарю закритого ключа треба фрагменти повідомлення підносити до степеню d. Оскільки при цьому відоме розкладання на множники n = pq, то застосовують CRT–представлення для скорочення об’єму обчислень.

 

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

Для забезпечення потрібного рівня криптостійкості довжина ключа повинна бути достатньою. У сучасних система з відкритим ключем довжина закритого ключа складає декілька тисяч бітів. Для того, щоб отримати k -бітове число n, генерують два випадкових простих k /2-бітове числа p і q і перемножують їх. Іноді в результаті такого множення можна отримати (k -1)-бітове число, але це несуттєво.

Розглянемо дві функції, що генерують ключі RSA

Функція GenerateRSAPrime Вхід: k – довжина потрібного простого числа у бітах. Вихід: p – випадкове просте число з інтервалу 2^k-1, …, 2^k-1, що задовольняє умові p mod 3 ¹ 1 & p mod 5 ¹ 1. // Перевірка, чи правильний поданий інтервал

if 1024 £ k £ 4096 then // Максимальна кількість спроб

r 100 k

repeat

r r - 1

if r > 0

//Вибір у поданому інтервалі випадкового числа n.

n Î_R 2^k-1, …, 2^k-1

else return 0

fi

//Продовження спроб, доки не знайдене потрібне число

until n mod 3 ¹ 1 & n mod 5 ¹ 1 & IsPrime(n)

return n

fi

return 0

Наступна функція генерує усі параметри закритого ключа.

Функція GenerateRSAKey

Вхід: k – орієнтовна довжина модуля у бітах.

Вихід: p, q – множники модуля;

n – модуль довжиною приблизно k бітів;

d₃ – показник степеню для цифрового підписування;

d₅ – показник степеню для шифрування

// Перевірка, чи правильний поданий інтервал

if 2048 £ k £ 8192 then

// Генерація простих множників

p GenerateRSAPrime(ëk/2û)

q GenerateRSAPrime(ëk/2û)

// Перевірка роботи генератора випадкових чисел

if p ¹ q then

// Обчислення t як НСК(p-1, q-1)

t (p-1)(q-1)/НСД(p-1, q-1)

// Обчислення секретних показників степенів за допомогою розширеного алгоритму Евкліда

g, (u, v) ExtendedGCD (3, t)

// Перевірка НСД

if g ¹ 1 error

fi

d₃ u mod t

g, (u, v) ExtendedGCD (5, t)

// Перевірка НСД

if g ¹ 1 error

fi

d₅ u mod t

return p, q, pq, d₃, d₅

 

Шифрування в системі RSA

Алгоритм RSA передбачає, що довжина вхідного повідомлення менше n. Тому шифрування великих повідомлень вимагає завчасного розбиття повідомлення на блоки. Але, враховуючи трудомісткість алгоритму RSA, на практиці такий підхід не застосовується.У більшості випадків проблему розв’язують наступним чином: вибирають випадковий секретний ключ K і зашифровують його за допомогою RSA. Після цього повідомлення m, що треба відправити, шифрується за допомогою ключа K і деякого блочного алгоритму. Таким чином, замість того, щоб відправляти E_RSA(m), відправляють E_RSA(K) і E_K(m). Для виключення залежності між значеннями K, отриманими при різних виборах (у різних сеансах), визначення K здійснюється у два етапи. Спочатку вибирають випадкове r Î Z _n, а потім ключ блочного шифрування обчислюється як K = h(r), де h – деяка функція хешування. Шифрування числа r виконується шляхом піднесення r до п’ятого степеню за модулем n. Оскільки значення r вибирається випадковим чином, воно не підкоряється жодній структурі, що могла б бути використана для атаки на RSA. Функція хешування, у свою чергу, гарантує, що жодна залежність між різними значеннями r не перейде на значення K, за винятком умови: однаковим r відповідають однакові K.

Для спрощення реалізації r обирають у діапазоні 0. …, 2^k - 1, де k - найбільше число, для якого 2^k < n. Набагато легше згенерувати випадкове k -бітове число, ніж випадкове число з Z _n (отримане незначне відхилення від рівномірного розподілу у даному випадку несуттєве). Формальний опис алгоритму складається з опису двох функцій: кодування (для відправника) і декодування (для одержувача).

Функція EncryptRandomKeyWithRSA

Вхід: (n, e) – відкритий ключ RSA, e = 5.

Вихід: K – секретний блочний ключ

c – шифрований ключ: c = E_RSA(K).

// Обчислення k

k ëlog₂ nû

//Вибір випадкового числа r, такого, що 0 £ r £ 2^k - 1.

r Î_R {0, …, 2^k-1}

//Застосування функції хешування SHA_d – 256

K = SHA_d – 256(r)

c r^e mod n

return (K, c)

Одержувач, застосовуючи ту саму функцію хешування для закодованого повідомлення c, отримує ключ K.

Функція DecryptRandomKeyWithRSA

Вхід: (n, d) –закритий ключ RSA;

c – шифрований текст.

Вихід: K – секретний блочний ключ.

// Перевірка c

if 0 £ c £ n then

K SHA_d – 256(c^d mod n)

return K

Застосування функції хешування робить алгоритм RSA більш безпечним по відношенню до збоїв різних компонентів системи.

Підписи RSA

Реалізувати схему цифрових підписів дещо складніше. Повідомлення, що треба підписати, має чітку структуру. Допускати, щоб ця структура перейшла на числа, для яких підраховуються корені RSA, небажано. Тому структуру треба знищити. Перший крок до руйнування структури полягає у хешуванні повідомлення. Таким чином, замість повідомлення m довільної довжини обробляється значення h(m) фіксованої довжини, де h – функція хешування. Якщо застосувати функцію SHA_d – 256, то результатом буде 256-бітове число. Але це набагато менше n, що перешкоджає безпосередньому використанню h(m).

Розв’язання вказаної проблеми досягається використанням псевдовипадкового відображення h(m) на діапазон чисел 0, …, n – 1, і наступним шифруванням отриманого образу s. Підпис при цьому обчислюється як s^d mod n. Для спрощення реалізації h(m) відображається на діапазон 0, …, 2^k-1, де k - найбільше число, для якого 2^k < n.

Для реалізації схеми цифрового підпису застосовуються три функції: перша - для відображення m на s, друга – для підписування повідомлення, третя – для перевірки підпису.

Функція MsgToRSANumber

Вхід: n – відкритий ключ RSA;

m – повідомлення, що треба перетворити у число за модулем n.

Вихід: s – число за модулем n.

// Створення нового генератора псевдовипадкових чисел.

G InitializeGenerator()

//Поновлення початкового числа генератора за допомогою хеш-коду повідомлення.

ReSeed (G, SHA_d – 256(m))

// Обчислення k.

k ëlog₂ nû

x PseudoRandomData(G, ék/8ù)

//Розглядається рядок байтів x як ціле число, що представлене у форматі, в якому найменш значимий байт записується першим. Операція взяття за модулем виконується шляхом застосування операції AND до останнього байту x.

s x mod 2^k

return s

Функція SignWithRSA

Вхід: (n, d) –закритий ключ RSA, e = 3;

m – повідомлення, що треба підписати.

Вихід: s – підпис повідомлення m.

s MsgToRSANumber (n, m)

s s^d mod n

return s

Функція VerifyRSASignature

Вхід: (n, e) –відкритий ключ RSA, e = 3;

m – повідомлення, що підписане;

s – підпис повідомлення m.

Вихід: b – булева змінна, дорівнює true, якщо підпис правильний, і – false у іншому разі

s MsgToRSANumber (n, m)

if s = s ^e mod n then b = true

else b = false

return b