RSA

ЩО ЦЕ ТАКЕ

Алгоритм RSA (Рівест-Шаміра-Адлемана) — це асиметричний або криптографічний алгоритм із відкритим ключем, що означає, що він працює з двома різними ключами: відкритим ключем і закритим ключем. Відкритий ключ використовується для шифрування та відомий усім, тоді як закритий ключ використовується для розшифровки та повинен зберігатися в секреті одержувачем. Алгоритм RSA названий на честь Рона Ріввеста, Аді Шаміра та Леонарда Адлемана, які опублікували алгоритм у 1977 році.

AЛГОРИТМ

МАТЕМАТИКА

Фішка RSA в тому що він вдало і влучно використовує модульну арифметику, властивості степенів, особливості факторизації великих простих чисел та їхню односторонню структуру, та апартатні особливості комп'ютерів, через що у нас є чотири ключових особливості цього алгоритму:

Криптостійкість

Уявіть нам дали задачу розкласти велике число на множники, як в молодній школі. Наприклад 258. Тут за допомогою ознак подільності на 2, 3, 5 тощо ми можемо обрахувати і спростити це число поділивши його на 2, тобто 2 х 129 далі можемо ще на 3. 2 х 3 х 41. Все, просто і легко.

А тепер згадуємо означення простого числа: це число, єдиними дільниками якого є 1 і воно само.

Тобто якщо в нас буде величезне число, яке є добутком двух величезних простих множників, то ознаки подільності нам не допоможуть, і єдиним рішенням буде перебір вручну. А перебрати добуток двох 1048 бітних чисел займе більше часу ніж атомів у Всесвіті. По ходу як ми будемо далі розбирати метод буде більше зрозуміла стійкість методу.

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

Зворотність і Асиметричність

Для розуміння цього етапу необхідно згадати степеневу математику та операцію остачі після ділення. Враховуючи що по факту наші ключі шифрування це уже великі степені, ми не можемо просто їх підносити до 65537 степеня і потім ще до величезного степеня, треба якийсь обмежувач. Ним буде остача з ділення, адже коли при піднесенні наше число стане більшим за n, з'являтиметься залишок, тобто остача.

Тепер інше питання, ми перебільшили наш ліміт n, в нас є остача від ділення. Скільки раз було перебільшено дане число? Показати краще на прикладі.

$26≡x^3(mod33)$

26 це остача, 3 степінь а 33 це ліміт. Нам треба дізнатись початкове число х, яким воно було до піднесення до степеня. Для цього додамо остачу до числе кратним тим на яке ми ділили, і треба знайти просто число яке є кубом. Формула така: Можливе початкове число (М) = 26 + (k * 33)

1. $26$

2. $26+33=59$

3. $26+66=92$

4. $26+99=125$ (ось наш реальний $5^3$, але ми цього не знаємо)

5. $26+132=158$

І так у нескінченність. Але в реальності в нас і степінь замість 3 це 65537 (чому так пізніше поясню), і n у нас не 33, а 2048 бітне число, щоб це все перебрати знову ж таки знадобиться нескінченний час і ресурси.

Тепер зрозуміло що перебір даних в даних операціях неможливий, і враховуючи класичну математику незворотну операцію $C≡M^e(modn)$ зашифрування. Але насправді вона є зворотньою, і тут помагає Ейлер.

Властивість Ейлерa, Функція Ейлера

П'єр де Ферма відкрив циклічність остач для простих чисел.

Леонарду Ейлеру вдалося розширити цю закономірність не лише для простих, а й для складених чисел. Він вивів функцію $ϕ(n)$, яка дозволяє точно обчислити кількість елементів у цьому математичному циклі для будь-якого модуля.

Що за цикл?

Беремо будь-яке число М. Наприклад М = 3. Починаємо послідовно підносити його до степеня 1, 2, 3... І що разу рахуємо остачу від ділення на n = 7:

1. $3^1$ = 3 (mod 7) = 3

2. $3^2$ = 9 (mod 7) = 2

3. $3^3$ = 27 (mod 7) = 6

4. $3^4$ = 81 (mod 7) = 4

5. $3^5$ = 243 (mod 7) = 5

6. $3^6$ = 729 (mod 7) = 1

7. $3^7$ = 2187 (mod 7) = 3

8. $3^8$ = 6561 (mod 7) = 2

Тепер зверніть увагу на закономірність, що після числа 1 остачі при збільшені степені почали повторюватись. Це і є циклом Ейлера, і число Ейлера це кількість елементів у циклі.

Формула для числа Ейлера для складених числе є: ф(n) = (p-1)(q-1), де n = q*p

Визначення Властивості Ейлера: Якщо ми знаємо число Ейлера ф(n), то для всіх кратних йому степенів k*ф(n) із додаванням одиниці (+1), операція остачі після ділення дає число, ідентичне початковому: $(M^e)^d=M^{1+k*ф(n)}$

Фактично ми множимо два абстрактні великі числа (e, d) так, щоб через одне можна було вивести інше. Тобто, знаючи один ключ, можна математично пов’язати його з іншим.

Унікальність ключів забезпечують параметри p і q. Вони критично важливі, тому що саме через них обчислюється функція Ейлера. Їх випадковість і унікальність створюють основу для формування числа, яке використовується в шифруванні. Якщо розширити число Ейлера і просто зробити рівняння зі степенями, то утворюється

$e*d=1+k*(p-1)(q-1)$

Якщо прикинути з точки зору злочинця, чи можемо ми якось зламати цей шифр, тобто дістати число d? Ні тому що в нас виходить рівняння з трьома невідомими: k, p, q. Доки не буде створено швидкий метод для факторизації двох простих множників, метод буде непробивний

Швидке обрахування ключів шифрування без втрат безпеки

Враховуючи що ключ дешифрування d ми вираховуємо з e, p i q. PQ оба мають бути взаємно простими, це розуміло щоб вся безпека алгоритму працювала. Для е ж є дві умови:

1. $1<e<ф(n)$

• Чому більше 1: Якщо e = 1, то рівняння виглядає як $M^1 = M$. Шифрування не відбувається взагалі, дані залишаються у відкритому вигляді. Це фатальна помилка архітектури.

• Чому менше ф(n): Тому що ф(n) — це довжина повного математичного циклу. Використовувати ключ, більший за ф(n), — це марнувати такти процесора на зайві оберти. Піднесення до степеня ф(n) + 5 дасть фізично ту саму остачу, що й піднесення до степеня . Тому е тримають у межах одного циклу для оптимізації обчислень.

2. е взаємно простий з ф(n)

• Чому? За законами модульної алгебри, зворотне число (наше d) існує виключно тоді, коли та взаємно прості (Найбільший спільний дільник дорівнює 1). Якщо в них є хоч один спільний дільник (наприклад, обидва парні і діляться на 2), рівняння ніколи не вийде на остачу 1 і вони просто поділяться один на одного. Генерація ключа фізично неможлива — алгоритм зависне або видасть помилку.

Чому майже завжди е це 65537

У двійковій системі числення $65537$ виглядає як 10000000000000001​ (це $2^{16}+1$). Піднесення повідомлення до степеня $e$ за допомогою алгоритму "Square-and-Multiply" вимагає виконання операцій множення лише для тих позицій, де стоять одиниці.

Якщо перевірити дві умови то це число їх задовільняє:

• 65537 менше числа Ейлера бо p i q в рази більше числа

• Це четверте число Ферма, тому воно є простим числом, просто треба передивитись щоб 65537 це було спільним множником з d, але для таких великих чисел це трапляється дуже рідко.

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

І враховуючи те що е це стале число, k ні на що не впливає, то якраз для створення пари ключів треба унікальнs велике 1024 бітні взаємно прості числа p та q, Програма створює за допомогою них d. Множить їх між собою і додає число n для обох приватних і публічних ключів. Бо після генерації n зберігає захист, унікальність і звязок e i d. Адже вже шифрування і дешифрування неможливо якщо ми не знаємо на що ділити

Розширенний Алгоритм Евкліда

ф

ДЖЕРЕЛА

RSA Algorithm in Cryptography - GeeksforGeeksGeeksforGeeks