Алгоритм шифрування RSA, види атак на нього. Реалізація мовою Python

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Всім привіт! Мене звати Владислав Литвиненко, я студент Національного авіаційного університету, спеціальність «кібербезпека». У даній статті я максимально детально описав базові принципи роботи алгоритму RSA та деяких видів атаки на нього. А на прикладі мови Python створив елементарну реалізацію алгоритму RSA та атак на нього, пояснив, чому не варто використовувати власні реалізації криптографічних алгоритмів.

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

У статті описано принцип роботи трьох видів атаки на RSA: брут-форс, атака на спільний модуль та атака Хастада.

Теоретична основа

Що таке RSA

Почнемо з загальної інформації про RSA. Це асиметричний алгоритм шифрування, який названий на честь Рона Ріввеста, Аді Шаміра та Лена Адлемана, які його винайшли (Rivest, Shamir, Adleman). Перша публікація про алгоритм RSA датується 1977 роком.

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

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

Принцип роботи алгоритму

Алгоритм RSA складається з чотирьох етапів: 1) генерація ключа; 2) розподіл ключа; 3) шифрування; 4) дешифрування.

1. Генерація ключа. Даний етап, своєю чергою, ділиться ще на декілька підетапів:

• Вибір двох простих чисел. На даному етапі необхідно обрати два великі прості числа p та q (просте число — це таке, що може ділитись без залишку лише на 1 та на себе). Числа p і q повинні триматись в таємниці, оскільки саме на них базується процес створення приватного та публічного ключа. Для більшої надійності p та q повинні: бути обрані навмання; бути великими; мати велику різницю.
• Визначення модуля. На даному етапі необхідно визначити число n, що використовується як модуль для відкритого і закритого ключа: n = p * q. Довжина n, що виражена в бітах, і є довжиною ключа.
• Застосування функції Ейлера. Далі необхідно визначити значення функції Ейлера від числа n, що має наступний вигляд: φ(n) = (p — 1) * (q — 1).
• Вибір відкритої експоненти. Після визначення значення функції Ейлера необхідно випадково обрати ціле число e таке, що 2 < e < φ(n). Число e (яке також називають відкритою експонентою) повинно бути взаємно простим до значення φ(n). Занадто малі значення відкритої експоненти можуть послабити алгоритм RSA.
• Знаходження приватної експоненти (оберненого за модулем числа). В той час, коли відкрита експонента e є частиною публічного ключа, то приватна експонента d (або ж секретна) являється частиною приватного ключа. Приватна експонента d знаходиться як обернене за модулем φ(n) до числа e, тобто: d * e ≡ 1(mod(φ(n)). Значення оберненого за модулем числа можна визначити з допомогою розширеного алгоритму Евкліда.

2. Розподіл ключа. Тепер, коли визначено всі необхідні числа, можна сформувати приватний та публічний ключ. Приватний ключ складається з пари d та n, а публічний з пари e та n.

Число d повинно триматись у таємниці, оскільки воно використовується для дешифрування повідомлення. Числа p, q та φ(n) також повинні триматись у таємниці, адже з допомогою них можна визначити приватну експоненту d, але після її визначення ці числа можна одразу відкинути.

Публічний ключ пересилається з допомогою надійного, але не обов’язково зашифрованого каналу зв’язку.

3. Шифрування. Для того, щоб зашифрувати текст m, необхідно обчислити таку рівність: c = m^e (mod n), де c — зашифрований текст, m — простий текст.

4. Дешифрування. Для того, щоб розшифрувати текст c, необхідно обчислити таку рівність: m = c^d (mod n).

Приклад роботи алгоритму

Тепер розглянемо вищеописану роботу алгоритму RSA на конкретному прикладі. Для простоти обчислення я наведу малі значення параметрів ключів.

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

• Вибір двох простих чисел. Випадково оберемо прості числа p та q. Нехай, p = 11, q = 13.

• Визначення модуля. Визначимо модуль n, який становить добуток чисел p та q: n = 11 * 13 = 143.

• Застосування функції Ейлера. Застосуємо функцію Ейлера φ(143) = (11 — 1) * (13 — 1) = 120.

• Вибір відкритої експоненти. Тепер необхідно обрати значення відкритої експоненти. У нашому випадку її значення можна обрати з інтервалу від 2 до 120 (потрібно пам’ятати, що вона повинна бути взаємно простим числом до 120): 2 < e < 120. Нехай відкрита експонента e = 23.

  

  • Знаходження приватної експоненти (оберненого за модулем числа). Розширений алгоритм Евкліда. Значення приватної експоненти можна знайти за допомогою розширеного алгоритму Евкліда, у даному прикладі застосовується його табличне представлення.

  Алгоритм Евкліда передбачає ділення більшого числа на менше, доки ми не досягнемо залишку 0. На кожній ітерації ми записуємо залишки та частки від ділення в таблицю. Основні принципи роботи розширеного алгоритму Евкліда:

  • Q — частка; A — ділене; B — дільник; R — залишок;
  • на першій ітерації необхідно записати A і B так, щоб A > B;
  • на першій ітерації T₁ = 0, T₂ = 1;
  • на кожній ітерації необхідно обчислювати значення T з допомогою формули T = T₁ — (T₂ * Q);
  • при переході на кожну нову ітерацію значення B, R, T₂, T зміщуються ліворуч на одну клітинку;
  • обчислення завершується тоді, коли B = 0;
  • коли обчислення завершено, то T₁ на останній ітерації — обернене за модулем число.

  Необхідно знайти значення приватної експоненти: d * 23 ≡ 1(mod(120)). Запишемо у таблицю початкові параметри. Оскільки нам потрібно знайти обернене число до 23 за модулем 120, то обираємо більше з цих двох чисел і записуємо його у таблицю як A, менше число — як B. На першій ітерації T₁ = 0, T₂ = 1:

Ділимо 120 на 23, неповну частку записуємо як Q, залишок як R:

Визначаємо T з допомогою формули T = T₁ — (T₂ * Q) і записуємо у таблицю. T = 0 — 1 * 5 = −5.

Переходимо на нову ітерацію, для цього на новій ітерації значення B, R, T₂, T зміщуємо ліворуч на одну клітинку:

Ділимо 23 на 5, визначаємо і записуємо Q, R, T:

На новій ітерації повторно зміщуємо значення B, R, T₂, T ліворуч:

Ділимо 5 на 3, визначаємо і записуємо Q, R, T. Повторно виконуємо вищеописані дії допоки не досягнемо 0 у стовпці B:

Кінцеве значення у стовпці T₁ є оберненим за модулем. d = 47

2. Розподіл ключа. Тепер можна сформувати приватний та публічний ключ. Приватний ключ складається зі значень d та n, публічний ключ зі значень e та n.

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

3. Шифрування. У даному прикладі шифрується кожна окрема літера тексту і зашифроване повідомлення відправляється тому, хто має приватний ключ. Така реалізація шифрування може використовуватися лише в навчальних цілях, оскільки її легко зламати. У реальності реалізація процесу шифрування/дешифрування набагато складніша.

Зашифруємо слово «БЕЗПЕКА». Для цього переведемо кожну літеру слова у число відповідно до її порядкового номеру в українському алфавіті (нумерацію алфавіту починаємо з 0). Наприклад, номер букви Б в алфавіті — 1, букви Е — 6.

Відповідність літер у слові «БЕЗПЕКА» до їх порядкового номеру в алфавіті:

Б — 1; Е — 6; З — 9; П — 19; Е — 6; К — 14; А — 0;

Для шифрування повідомлення використовується рівність c= m^e (mod n). Зашифруємо кожне отримане число:

• 1²³ (mod 143) = 1
• 6²³ (mod 143) = 128
• 9²³ (mod 143) = 3
• 19²³ (mod 143) = 50
• 6²³ (mod 143) = 128
• 14²³ (mod 143) = 27
• 0²³ (mod 143) = 0

Тепер числа можна скласти докупи у список і відправити тому, хто повинен його розшифрувати.

4. Дешифрування. Для розшифрування тексту використовується рівність: m= c^d (mod n).

• 1⁴⁷ (mod 143) = 1
• 128⁴⁷ (mod 143) = 6
• 3⁴⁷ (mod 143) = 9
• 50⁴⁷ (mod 143) = 19
• 128⁴⁷ (mod 143) = 6
• 27⁴⁷ (mod 143) = 14
• 0⁴⁷ (mod 143) = 0

Отримані числа відображають порядкові номера літер алфавіту:

1 — Б; 6 — Е; 9 — З; 19 — П; 6 — Е; 14 — К; 0 — А;

Можливі види атак на криптосистему RSA

Існує ряд атак, які працюють або через те, що використовується ненадійна реалізація, або через те, що сам RSA використовується неправильно. Нижче наведено три можливі види атаки на RSA (хоча у реальності їх набагато більше). Малоймовірно, що ці атаки можна застосувати у реальному світі, але вони доволі гарно ілюструють чому необхідно використовувати надійні реалізації алгоритмів шифрування. У всіх прикладах вважається, що зловмисник знає публічний ключ.

Малі значення p та q (Brute-force)

Ми знаємо, що модуль n — це добуток чисел p та q, тому ми можемо послідовно перебирати і множити p та q доти, доки не отримаємо значення n. У цьому типі атаки перебираються такі значення p та q, що менше n. Коли p та q підібрані, то можна легко визначити всі інші параметри. Дана атака не являється дуже ефективною, оскільки це звичайний брут-форс. З допомогою такого підходу можливо (теоретично) зламати будь-яку реалізацію RSA, тому важливо використовувати лише великі значення ключів під час шифрування.

Використання спільного модуля у різних ключах

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

Цей вид атаки базується на теоремі Безу: якщо існують два цілі числа a і b, які не дорівнюють нулю, то існують цілі числа x і y такі, що xa + yb = НСД (a, b). Числа x та y можна знайти з допомогою розширеного алгоритму Евкліда. У нашому випадку a та b — це дві відкриті експоненти публічних ключів (надалі вони будуть записуватись як e₁ та e₂ відповідно).

Зламати зашифроване повідомлення можна визначивши, що:

де c₁ та c₂ — зашифровані різними ключами повідомлення, e₁ та e₂ — відкриті експоненти, m — розшифроване повідомлення.

Приклад: нехай, є сторони B та C, що отримали публічні ключі від сторони A. Також існує зловмисник, що перехопив публічні ключі. Тоді, якщо сторони B та C зашифрують однакове повідомлення з допомогою своїх ключів, то зловмисник зможе їх зламати.

Сторони B та C шифрують цифру 5 з допомогою своїх ключів і відправляють зашифроване повідомлення стороні A.

Зловмисник перехоплює повідомлення та розшифровує їх.

Тепер, маючи відкриті експоненти та зашифровані повідомлення, можливо отримати вихідний текст.

З допомогою розширеного алгоритму Евкліда потрібно визначити x та y. У A та B на першій ітерації необхідно поставити значення відкритих експонент (37 та 23).

T₁ на останній ітерації — необхідне значення x, а T₁ на передостанній ітерації — y. У такому випадку x = −8, y = 5.

Оскільки ми знаємо, що розшифроване повідомлення m= с^x₁*c^y₂, то

m=(125^-8*135⁵)mod143= ((125^-1)⁸*135⁵)mod143, де 125^-1 обернене за модулем до 143, яке необхідно визначити з допомогою розширеного алгоритму Евкліда:

За модульною арифметикою (-8)mod143 = 135mod143.

Тепер можливо отримати розшифроване повідомлення:

m=(125^-8*135⁵)mod143= ((125^-1)⁸*135⁵)mod143 = (135⁸*135⁵)mod143 = 5

Атака Хастада (атака на малу відкриту експоненту)

Нехай, сторони B, C та D відправляють стороні A однакове повідомлення m у зашифрованій формі як c_B, c_C, c_D. Повідомлення зашифровані публічними ключами з різними модулями, але однаковою малою відкритою експонентою e = 3; значення модулів — взаємно прості числа. Значення відкритої експоненти може бути більшим, але тоді кількість зашифрованих різними ключами повідомлень повинна бути ≥ e. Зловмисник, знаючи публічні ключі та зашифровані повідомлення c_B, c_C, c_D, може застосувати китайську теорему про залишки для отримання дешифрованого повідомлення:

x = (c₁ * M₁ * M₁^-1 + c₂ * M₂ * M₂^-1 +...+ c_k * M_k * M_k^-1)mod M, де

Приклад: публічні ключі сторін, що шифрують повідомлення — B — (3, 143), C — (3, 323), D — (3, 667). Повідомлення m = 15 шифрується з допомогою даних ключів як c_B = 86, c_C = 145, c_D = 40. Оскільки відкрита експонента у всіх ключах однакова і модулі ключів — взаємно прості числа, то можливо дешифрувати повідомлення з допомогою китайської теореми про залишки:

M=n_B * n_C * n_D=143 * 323 * 667= 30808063

M_B= 30808063 / 143 = 215441

M_C= 30808063 / 323 = 95381

M_D= 30808063 / 667 = 46189

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

M^-1_B*215441≡ 1(mod 143); M^-1_B=112

M^-1_C*95381≡ 1(mod 323); M^-1_C=286

M^-1_D*46189≡ 1(mod 667); M^-1_D=221

Тепер можливо знайти x:

x = (c₁ * M₁ * M₁^-1 + c₂ * M₂ * M₂^-1 + c₃ * M₃ * M₃^-1)mod M =

=(86 * 215441 * 112 + 145 * 95381 * 286 + 40 * 46189 * 221)mod 30808063 = 3375

Вихідне повідомлення

Реалізація криптосистеми RSA на прикладі Python

❗️ Безпека алгоритму RSA залежить від розміру ключа та якості генератора випадкових чисел, який використовується для генерації ключів. Модуль random у Python використовує генератор псевдовипадкових чисел, який не вважається криптографічно безпечним.

Крім того, дана реалізація не включає жодної схеми доповнення, яка є важливим компонентом безпечного шифрування RSA. Без належного доповнення — шифрування RSA вразливе до атак. Таким чином, подібну реалізацію не слід використовувати для будь-яких реальних програм, які потребують захищеності даних. Для забезпечення конфіденційності та цілісності зашифрованих даних важливо використовувати добре перевірену та безпечну реалізацію RSA з відповідними розмірами ключів і схемами доповнення.

Криптографам та інженерам знадобилися десятиліття, щоб розробити реалізацію RSA, яка є швидкою і достатньо безпечною. Навіть за наявності всієї документації, для виконання цього складного завдання знадобляться місяці. Як правило, під час впровадження RSA, використовуються бібліотеки або API, які надають необхідні функції для виконання операцій RSA.

Для роботи даної програми необхідно імпортувати модуль random:

import random

Далі йдуть допоміжні функції, що використовуються для шифрування та дешифрування тексту.

Функція, що перевіряє, чи число є простим:

def is_prime(n):
    """Check if a number is prime"""
    for i in range(2,n):
        if (n % i) == 0:
            return False
    return True

Функція Ейлера для знаходження φ від двох простих чисел:

def euler_func(p, q):
    """Count the positive integers (up to p*q) that are relatively prime to p*q"""
    return (p - 1) * (q - 1)

Розширений алгоритм Евкліда, що повертає НСД, x та y:

def extended_euclidean_algorithm(a, b):
    """Extended Euclidean algorithm for finding gcd, x, y"""
    if a == 0 :
        return b, 0, 1
    gcd,x1,y1 = extended_euclidean_algorithm(b % a, a)
    x = y1 - (b // a) * x1
    y = x1 
    return gcd, x, y

Функція, що повертає число, обернене до модуля:

def modular_inverse(num, mod):
    return extended_euclidean_algorithm(num, mod)[1] % mod

Тепер можливо описати функції, що безпосередньо реалізують алгоритм RSA.

Функція, що приймає значення довжини ключів і повертає відповідні публічні та приватні ключі:

def generate_keys(bit_length):
    """Generate public and private keys"""
    # Generation of p and q
    half_bit_length = bit_length // 2
    while True:
        p = random.randint(2**(half_bit_length-1), 2**half_bit_length-1)
        if is_prime(p):
            break
    while True:
        q = random.randint(2**(half_bit_length-1), 2**half_bit_length-1)
        if is_prime(q) and p != q:
            break
    # Calculation of the module
    n = p * q
    # Public key creation
    phi = euler_func(p, q)
    while True:
        e = random.randint(3, phi - 1)
        if extended_euclidean_algorithm(e, phi)[0] == 1:
            break
    pub_key = (e, n)
    # Private key creation
    d = modular_inverse(e, phi)
    priv_key = (d, n)
    return pub_key, priv_key 

Функція для шифрування тексту. Дана функція перетворює кожний окремий символ рядка у відповідний номер Юнікоду, шифрує символ і зберігає його у списку, який повертається функцією:

def rsa_encrypt(public_key, plain_text):
    """Encrypt text using input parameters"""
    e, n = public_key
    return [pow(ord(char), e, n) for char in plain_text]

Функція для дешифрування виконує все у зворотньому порядку:

def rsa_decrypt(private_key, encrypted_text):
    """Decrypt text using input parameters"""
    d, n = private_key
    decrypted_text = [chr(pow(char, d, n)) for char in encrypted_text]
    return ''.join(decrypted_text)

Тепер можливо перевірити роботу всіх створених функцій наступним чином:

keys = generate_keys(12)
initial_text = "HELLO WORLD"
encrypted_text = rsa_encrypt(keys[0], initial_text)
decrypted_text = rsa_decrypt(keys[1], encrypted_text)
print("Ключі - ", keys)
print("Початковий текст - ", initial_text)
print("Зашифрований текст - ", encrypted_text)
print("Розшифрований текст - ", decrypted_text)

Змінна keys приймає випадково згенеровані ключі, що мають довжину 12 біт. У initial_text зберігається текст, що необхідно зашифрувати, в encrypted_text зберігається список із зашифрованими символами з допомогою публічного ключа, а у decrypted_text зберігається розшифрований текст з допомогою приватного ключа.

Результат виконання:

Реалізація деяких видів атаки на криптосистему RSA

Далі реалізуються три методи атаки, принцип роботи яких описується вище.

Брут-форс атака

def rsa_bruteforce_attack(public_key, encrypted_text):
    """Brute-force attack. Iteration of p and q values."""
    e = public_key[0]
    n = public_key[1]
    # Finding p and q to determine phi
    for p in range(3, n):
        if is_prime(p) == False:
            continue
        for q in range(p + 1, n):
            if is_prime(q) == False:
                continue
            if p * q == n:
                phi = euler_func(p, q)
        else:
            continue
        break     
    # Private key definition
    d = modular_inverse(e, phi)
    priv_key = (d, n)
    # Decrypted message return
    return rsa_decrypt(priv_key, encrypted_text)

Приклад застосування:

keys = generate_keys(12)
initial_text = "HELLO WORLD"
encrypted_text = rsa_encrypt(keys[0], initial_text)
print("Ключі - ", keys)
print("Зашифрований текст - ", encrypted_text)
print("Брут-форс атака - ", rsa_bruteforce_attack(keys[0], encrypted_text))

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

Результат виконання:

Атака на спільний модуль

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

def rsa_common_modulus_attack(msg1, pub_key1, msg2, pub_key2):
    """Common modulus attack"""
    e1 = pub_key1[0]
    e2 = pub_key2[0]
    mod = pub_key1[1]
    # Finding x and y
    gcd, x, y = extended_euclidean_algorithm(e1, e2)
    # Message decryption
    decrypted_message = ""
    for i in range(len(msg1)):
        char1 = msg1[i]
        char2 = msg2[i]
        char1 = modular_inverse(msg1[i], mod) if x < 0 else char1 
        char2 = modular_inverse(msg2[i], mod) if y < 0 else char2
        decrypted_char = int(((char1**abs(x)) * (char2**abs(y))) % mod)
        decrypted_message += chr(decrypted_char)
    return decrypted_message

Приклад застосування: у даному прикладі значення ключів прописані самостійно, адже необхідно, щоб модуль ключів був однаковим.

pub_key1 = (23, 143)
pub_key2 = (37, 143)
initial_text = "HELLO WORLD"
encrypted_text1 = rsa_encrypt(pub_key1, initial_text)
encrypted_text2 = rsa_encrypt(pub_key2, initial_text)
print("Публічний ключ 1 - ", pub_key1)
print("Публічний ключ 2 - ", pub_key2)
print("Зашифрований текст 1 - ", encrypted_text1)
print("Зашифрований текст 2 - ", encrypted_text2)
print("Атака на спільний модуль - ", rsa_common_modulus_attack(encrypted_text1, pub_key1, encrypted_text2, pub_key2))

Результат виконання:

Атака Хастада

Функція приймає словник у вигляді {(публічний ключ) : [зашифроване повідомлення]} та повертає розшифроване повідомлення.

def rsa_hastads_attack(key_message_dict):
    """Hastad's attack"""
    messages = list(key_message_dict.values())
    modules = [i[1] for i in key_message_dict.keys()]
    M = 1
    for i in modules:
        M *= i
    M_k = [int(M / i) for i in modules]
    M_k_inversed = [modular_inverse(M_k[i], modules[i]) for i in range(len(modules))]
    decrypted_message = ""
    for i in range(len(messages[0])):
        decrypted_char = 0
        for j in range(len(modules)):
            decrypted_char += messages[j][i] * M_k[j] * M_k_inversed[j]
        decrypted_char %= M
        decrypted_char = round(decrypted_char**(1 / len(messages)))
        decrypted_message += chr(decrypted_char)   
    return decrypted_message

Приклад застосування: у даному прикладі значення ключів прописані самостійно, адже необхідно, щоб публічна експонента була однаковою у всіх ключах. Далі початковий текст шифрується з допомогою даних ключів, зашифровані тексти зберігаються у словнику як відповідність (публічний ключ) : [зашифроване повідомлення].

initial_text = "HELLO WORLD"
pub_key1 = (3, 143)
pub_key2 = (3, 323)
pub_key3 = (3, 667)
encrypted_text1 = rsa_encrypt(pub_key1, initial_text) 
encrypted_text2 = rsa_encrypt(pub_key2, initial_text) 
encrypted_text3 = rsa_encrypt(pub_key3, initial_text) 
keys_messages = {
    pub_key1: encrypted_text1,
    pub_key2: encrypted_text2,
    pub_key3: encrypted_text3
}
print("Відповідність публічних ключів та зашифрованих повідомлень: ")
for i in keys_messages.items():
    print(i)
print("Атака хастада - ", rsa_hastads_attack(keys_messages))

Результат виконання:

Висновок

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

При виборі алгоритму шифрування слід дотримуватися найкращих практик в галузі криптографії та користуватися перевіреними реалізаціями, які пройшли тестування на стійкість до атак. Також важливо пам’ятати, що необхідно використовувати достатню довжину ключів. Мінімальна рекомендована довжина ключа RSA на 2023 рік — 2048 біт.