Алгоритм створення відкритого і секретного ключів (RSA)
Наша мета - це формування 3-ох чисел (далі їх загальноприйняті назви):
- модуля $ \ Large n $
- відкритої експоненти $ \ Large e $
- і закритою експопнети $ \ Large d $
З трьох цих чисел відкритий з закритий ключ утворюються шляхом використання:
- пари $ \ Large \ left \
- пари $ \ left \
Друзі, зосередьтеся і уважно прочитайте наступні пункти:
- для початку ми беремо два випадкових простих числа ($ \ Large p $ і $ \ Large q $) стандартного розміру (наприклад 1024 біт - тобто - досить великі)
- потім обчислюємо функцію Ейлера від числа n, таким чином:
$ \ Large \ varphi (n) = (p-1) (q-1) $
(Права частина тут розраховується моментально а тому з даного рівняння ми можемо отримати саме значення $ \ Large n $) - Далі ви підбираємо $ \ Large e $ - відкриту експоненту. так щоб:
- її значення було взаємно простим із значенням функції $ \ Large \ varphi (n) $
- задовольняло нерівності: $ \ Large 1
- І тепер обчислюємо закриту експоненту d, значення якої повинно відповідати умові:
$ \ Large d \ cdot e \ equiv 1 \ mod $ - От і все )
Примітки
Як ви тільки що прочитали - ми шукали значення n (модуля) дуже так:
$ \ Large \ varphi (n) = (p-1) (q-1) $
де праву частину розрахувати швидко - в той час як зворотний пошук - $ \ Large p $ і $ \ Large q $ за заданим $ \ Large n $ заёмёт дуже багато часу - на цьому і заснована захист RSA, так як противник не знатиме вихідних $ \ Large p $ і $ \ Large q $ і йому доведеться їх підбирати