Page 19 - 4395

буде знехтувана перед тим, як буде знайдено просте число. Результат
з теорії чисел, відомий як теорема простого числа, говорить, що
простих чисел, розташованих біля n в середньому одне на кожних
ln(n) чисел. Таким чином, в середньому потрібно перевірити

послідовність з ln(n) цілих, перш ніж буде знайдено просте число.
Оскільки всі парні числа можуть бути знехтувані без перевірки, то
потрібно виконати приблизно ln (n)/2 перевірок. Наприклад, якщо

просте число шукається в діапазоні величин 2200, то необхідно
виконати біля ln(2200)/ 2 = 70 перевірок.
Для виконання курсової роботи прості числа р і q вже задані.
Тому сказане вище носить ознайомчий характер.

Далі слід вибрати значення е так, щоб gcd(Ф(n), e) = 1 і
-1
обчислити значення d, d = e mod Ф(n). Існує єдиний алгоритм,
званий розширеним алгоритмом Евкліда, який за фіксований час

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

генерації серії випадкових чисел і перевірці кожного відносно Ф(n)
до того часу, поки не буде знайдено число, взаємно просте з Ф(n).
Виникає питання, як багато випадкових чисел доведеться перевірити

до тих пір, поки не знайдеться потрібне число, яке буде взаємно
простим з Ф(n). Результати показують, що вірогідність того, що два
випадкові числа є взаємно простимі, рівна 0.6.
Як було вказано вище, розміри р і q не перевищують двох

десяткових знаків (див. Завдання). Зокрема найбільші значення
складають p = 47, q= 71. При цьому Ф(n) = ( p - 1)*( q - 1) = 3220. Це
число ще не є великим, тому для розшуку взаємно простих с ним

можна використовувати звичайні оператори мов програмування.
Наприклад у MatLab 6 функція PRIMES(3220) дозволяє знайти 455
простих чисел, менше ніж число 3220, з яких можна вибрати e.
Тепер для обчислення d можна застосувати розширений алгоритм

Евкліда, який приводиться у додатку Б.

2.2.3 Криптоаналіз алгоритму RSA

Можна визначити чотири можливі підходи до криптоаналізу
алгоритму RSA:

 лобова (брутальна) атака – перебрати всі можливі закриті
ключі;

19