Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 30
×

Алгоритм шифрування 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 = me (mod n), де c — зашифрований текст, m — простий текст.

4. Дешифрування. Для того, щоб розшифрувати текст c, необхідно обчислити таку рівність: m = cd (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;
    • на першій ітерації T1 = 0, T2 = 1;
    • на кожній ітерації необхідно обчислювати значення T з допомогою формули T = T— (T2 * Q);
    • при переході на кожну нову ітерацію значення B, R, T2, T зміщуються ліворуч на одну клітинку;
    • обчислення завершується тоді, коли B = 0;
    • коли обчислення завершено, то Tна останній ітерації — обернене за модулем число.

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

Ітерація

Q

A

B

R

T1

T2

T

1

120

23

0

1

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

Ітерація

Q

A

B

R

T1

T2

T

1

5

120

23

5

0

1

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

Ітерація

Q

A

B

R

T1

T2

T

1

5

120

23

5

0

1

-5

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

Ітерація

Q

A

B

R

T1

T2

T

1

5

120

23

5

0

1

-5

2

23

5

1

-5

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

Ітерація

Q

A

B

R

T1

T2

T

1

5

120

23

5

0

1

-5

2

4

23

5

3

1

-5

21

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

Ітерація

Q

A

B

R

T1

T2

T

1

5

120

23

5

0

1

-5

2

4

23

5

3

1

-5

21

3

5

3

-5

21

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

Ітерація

Q

A

B

R

T1

T2

T

1

5

120

23

5

0

1

-5

2

4

23

5

3

1

-5

21

3

1

5

3

2

-5

21

-26

4

1

3

2

1

21

-26

47

5

2

2

1

0

-26

47

-120

6

1

0

47

-120

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

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

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

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

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

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

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

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

  • 123 (mod 143) = 1
  • 623 (mod 143) = 128
  • 923 (mod 143) = 3
  • 1923 (mod 143) = 50
  • 623 (mod 143) = 128
  • 1423 (mod 143) = 27
  • 023 (mod 143) = 0

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

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

  • 147 (mod 143) = 1
  • 12847 (mod 143) = 6
  • 347 (mod 143) = 9
  • 5047 (mod 143) = 19
  • 12847 (mod 143) = 6
  • 2747 (mod 143) = 14
  • 047 (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та e2 відповідно).

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

де c1 та c2 — зашифровані різними ключами повідомлення, e1 та e2 — відкриті експоненти, m — розшифроване повідомлення.

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

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

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

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

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

Ітерація

Q

A

B

R

T1

T2

T

1

1

37

23

14

0

1

-1

2

1

23

14

9

1

-1

2

3

1

14

9

5

-1

2

-3

4

1

9

5

4

2

-3

5

5

1

5

4

1

-3

5

-8

6

4

4

1

0

5

-8

37

7

1

0

-8

37

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

Оскільки ми знаємо, що розшифроване повідомлення m= сx1*cy2, то

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

Ітерація

Q

A

B

R

T1

T2

T

1

1

143

125

18

0

1

-1

2

6

125

18

17

1

-1

7

3

1

18

17

1

-1

7

-8

4

17

17

1

0

7

-8

143

5

1

0

-8

143

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

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

m=(125-8*1355)mod143= ((125-1)8*1355)mod143 = (1358*1355)mod143 = 5

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

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

, де k — кількість зашифрованих різними ключами повідомлень, x — розв’язок системи лінійних конгруенцій, що можна знайти наступним чином:

x = (c1 * M1 * M1-1 + c2 * M2 * M2-1 +...+ ck * Mk * Mk-1)mod M, де

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

M=nB * nC * nD=143 * 323 * 667= 30808063

MB= 30808063 / 143 = 215441

MC= 30808063 / 323 = 95381

MD= 30808063 / 667 = 46189

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

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

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

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

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

x = (c1 * M1 * M1-1 + c2 * M2 * M2-1 + c3 * M3 * M3-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 біт.

👍ПодобаєтьсяСподобалось25
До обраногоВ обраному13
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

треба співробітників ДССЗЗІ в тред закликати, що їм треба щоб цю лібу сертифікувати

Велике дякую! Чудова стаття вийшла. Гарно оформлена, подробна, просто в розумінні, корисна і цікава. Ще й українською! Прям 10 із 10.

Спасибо, отличная статья!

e може бути не випадковим, на відміну від p та q(при низький ентропії генератора можливо дізнатися приватний ключ eprint.iacr.org/2012/064.pdf, як можна побачити у статті — атака є цілком практичною). Дуже часто e обирать сталим(65537) і тоді як публічний ключ можна використовувати просто N. Також, наскільки я роузмію, якщо ви використовуєте безпечний падінг, такий як, наприклад, RSA-OAEP, e=3 нічим не гірше великої експоненти. Швидкість шифрування при e=3 і e=65537 не сильно відрізняєтсья, бо у 1 випадку вам треба 3 множення, а у 2 — 17, тому e=3 і не використовують часто, але ви все ж таки праві, що для textbook RSA без падінгу малий модуль не є безпечним . Ви могли зупинитися на розгляді RSA як trapdoor function, на основі якої вже можна будувати алгорими шифрування з публічним ключем, бо для алгоритму публічного шифрування вам не вистачає не тільки безпечного алгоритму падіну, а й безпечного алгориму хешування і безпечного алгоритму автентифікованого шифрування з симетричним ключем

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

В RSA була ще одна атака, можна впливати на зашифрований текст за допомогою множення або ділення шифра. Щось накшталт (2*text)^e mod N = (2^e mod N * text^e mod N) mod N

Це не атака, а притаманна RSA властивість, що називається «деформованість» (malleability). Зазвичай ця властивість вважається негативною, бо унеможливлює стійкість проти адаптивних атак з вибраним шифротекстом (CCA2). Проте водночас стає корисною в алгоритмах гомоморфного шифрування.

В общем случае (a*b)^e mod n = a^e mod n * b^e mod n.
И против этого в PKCS#1 явно записана мера: добавлять рандом в каждое зашифрованное значение.
Вообще в PKCS#1 прописаны все атаки и проблемы, без его чтения лучше дальше не идти.

Это всё прикольно конечно, только все уже давно пользуются криптографией на эллиптических кривых.

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

Алгоритмы в промышленном применении появились ещё до того, как Go вышел, так их сразу же включили в стандартную библиотеку, вот пруф для подписи pkg.go.dev/crypto/ecdsa
Ну и кроме того, RSA и тем более с ключом в 2048 бит использовать непрактично на сегодняшний день. Там только один JWT-токен на такой подписи будет больше, чем полезная нагрузка в ajax-запросах.

RSA існує трохи довше, ніж ECC, і сьогодні все ще широко використовується у сертифікатах SSL/TLS, ключах SSH і цифрових підписах. Як приклад можу навести процес створення центру сертифікації у AWS, при виборі алгоритму там вказується наступне: «The 2048-bit RSA key algorithm is widely supported by browsers and other clients. The 2048-bit size provides a good balance between security and efficiency.» та «The ECDSA P256 algorithm is an elliptic curve cryptography (ECC) algorithm. ECC is more efficient than RSA, but not all applications support ECC. ECDSA 256 bit keys are equivalent in cryptographic strength to RSA 3072 bit keys». До того ж всі англомовні ресурси називають RSA найбільш поширеним асиметричним криптографічним алгоритмом. Хоча прогнозується, що до ~2030 року RSA-2048 більше не буде вважатись безпечним, тому все більше систем буде використовувати алгоритм ECC через його ефективність.

Дякую за гарну статтю

А де про головні атаки сьогодення та майбутнього — квантові компьютери?

Ви хотіли пошуткувать, але у вас не вийшло. ©

Які ж тут жарти, це реальність

Думав написати про це, але не маю квантового комп’ютера, щоб з його допомогою реалізувати атаку :)

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

learn.microsoft.com/...​ines/full-state-simulator

quantum-computing.ibm.com/...​docs/iql/manage/simulator

Треба більше таких статей — та набагато менше срачів на вічні теми.
Дякую автору за прекрасну статтю!

Перевіряти простоту числа можна до sqrt(n) в вашому випадку

От такого не вистачає DOU Дяка за круту статтю

Підписатись на коментарі