ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.06.2024
Просмотров: 21
Скачиваний: 0
, (4.7)
де – функція Ейлера.
Функція Ейлера вказує кількість додатних цілих чисел в інтервалі від 1 до, які взаємно прості з N
.
Умова (3.7) означає, що відкритий ключ і функція Ейлера повинні бути взаємно простими.
Далі, використовуючи розширений алгоритм Евкліда, обчислюють таємний ключ , такий, що
(4.8)
або
.
Це можна здійснити, тому що одержувач B знає пару простих чисел і може легко знайти . Помітимо, що й повинні бути взаємно простими.
Відкритий ключ використовують для шифрування даних, а таємний ключ – для розшифрування.
Процес зашифрування визначає криптограму через пару (, М) у відповідності до формули (4.9).
(4.9)
Обернення функції , тобто визначення значення M за відомим значенням практично не здійсненне при N2512.
Однак обернену задачу, тобто задачу розшифрування криптограми C, можна вирішити, використовуючи пару (, ) за формулою (4.10).
. (4.10)
Процес розшифрування можна записати так:
(4.11)
Підставляючи в (4.11) значення (4.9) і (4.10), одержуємо:
або
. (4.12)
Відповідно до теореми Ейлера, яка стверджує, що якщо , то
або
. (4.13)
Порівнюючи вираження (4.12) і (4.13), одержуємо
або, що те саме,
.
Саме тому для обчислення таємного ключа використовують співвідношення (4.8).
Таким чином, якщо криптограму
піднести до степеня , то в результаті відновлюється вихідний відкритий текст М, тому що
.
Отже, одержувач B, що створює криптосистему, захищає два параметри: таємний ключ і пару чисел , добуток яких дає значення модуля N. З іншого боку, одержувач B відкриває значення модуля N і відкритий ключ .
Зловмиснику відомі лише значення та N. Якби він зміг розкласти число N на множники P й Q, то він довідався б "потаємний хід" – трійку чисел , обчислив значення функції Ейлера та визначив значення таємного ключа .
Однак, як було відзначено раніше, розкладання дуже великого числа N на множники не здійсненно обчислювальними методами (за умови, що довжини обраних Р и Q становлять не менше 100 десяткових знаків).
Процедури шифрування та розшифрування в криптосистемі RSA
Припустимо, що користувач A хоче передати користувачеві B повідомлення в зашифрованому вигляді, використовуючи криптосистему RSA. У такому випадку користувач A є в ролі відправника повідомлення, а користувач B – у ролі одержувача. Як відзначалося вище, криптосистему RSA повинен сформувати одержувач повідомлення, тобто користувач В. Розглянемо послідовність дій користувача В і користувача A.
-
Користувач B вибирає два довільних великих простих числа P й Q.
-
Користувач B обчислює значення модуля N згідно з (4.5).
-
Користувач B обчислює функцію Ейлера й вибирає значення відкритого ключа з урахуванням виконання умов (4.6) і (4.7).
-
Користувач B обчислює значення таємного ключа за формулою (4.8), використовуючи розширений алгоритм Евкліда.
-
Користувач B пересилає незахищеним каналом користувачу A пару чисел (N, ).
Якщо користувач A має бажання передати користувачу B повідомлення М, він виконує такі кроки.
-
Користувач A розбиває вихідний відкритий текст М на блоки, кожний з яких може бути поданий у вигляді числа ,.
-
Користувач A шифрує текст, поданий у вигляді послідовності чисел М, за формулою
і відправляє користувачеві В криптограму
.
-
Користувач B розшифровує прийняту криптограму , використовуючи таємний ключ , за формулою
.
У результаті буде отримана послідовність чисел , які являють собою вихідне повідомлення М. Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, вміти оперативно обчислювати значення ключів та .
Наприклад, виконаємо шифрування повідомлення “Буду завтра”.
Нехай P=59, Q=61. Тоді , а . Виберемо як відкритий ключ довільне число з урахуванням виконання умов (4.6) і (4.7). Нехай . Згідно (4.8) таємний ключ .
Подамо повідомлення як послідовність цілих чисел у діапазоні від 1 до 32. Нехай A – 01, Б – 02, В – 03, ..., Я – 32.
Тоді повідомлення “Буду завтра” буде подано у вигляді
02 20 05 20 08 01 03 19 17 01.
Розбиваємо повідомлення на блоки по чотири цифри
0220 0520 0801 0319 1701
і кодуємо кожен блок:
У результаті одержимо шифр 0099 3273 2050 0719 1664.
Для відновлення вихідного тексту необхідно обчислити модульну експоненту, підвівши зашифроване значення в степінь за модулем N:
Таким чином, отримали відновлене вихідне повідомлення
0220 0520 0801 0319 1701.
Криптосистеми RSA реалізуються як апаратним, так і програмним шляхом.
Для апаратної реалізації операцій зашифрування та розшифрування RSA розроблені спеціальні процесори. Ці процесори, реалізовані на надвеликих інтегральних схемах, дозволяють виконувати операції RSA, пов’язані з піднесенням великих чисел у колосально великий ступінь за модулем N, за відносно короткий час.
Слід відзначити, що і апаратна, і програмна реалізації алгоритму RSA в декілька сот разів повільніші від реалізацій симетричних криптосистем. Мала швидкодія криптосистеми RSA обмежує сферу її застосування, але не перекреслює її цінність.
Безпека й швидкодія криптосистеми RSA
Безпека алгоритму RSA базується на труднощах розв’язання задачі факторизації великих чисел, що є добутками двох великих простих чисел. Дійсно, крипостійкість алгоритму RSA визначається тим, що після формування таємного ключа й відкритого ключа "стираються" значення простих чисел P й Q, і тоді винятково важко визначити таємний ключ за відкритим ключем , оскільки для цього необхідно розв’язати задачу знаходження дільників P та Q модуля N.
Розкладання величини N на прості множники Р і Q дозволяє обчислити функцію , а потім визначити таємне значення , використовуючи рівняння (4.8).
Іншим можливим способом криптоаналізу алгоритму RSA є безпосереднє обчислення або підбір значення функції . Якщо встановлено значення , то співмножники P й Q обчислюються досить просто. Справді, нехай
Знаючи (N), можна визначити х і потім y; знаючи х та y, можна визначити числа P і Q з таких співвідношень:
.
Однак ця атака не простіша задачі факторизації модуля N.
Задача факторизації є задачею, яка важко розв’язується для великих значень модуля N.
Спочатку автори алгоритму RSA пропонували для обчислення модуля N вибирати прості числа P й Q випадковим чином, по 50 десяткових розрядів кожне. Вважалося, що такі великі числа N дуже важко розкласти на прості множники. Один з авторів алгоритму RSA, Р.Райвест, вважав, що розкладання на прості множники числа з майже 130 десяткових цифр, наведеного в їхній публікації, зажадає більше 40 квадрильйонів років машинного часу. Однак цей прогноз не виправдався через порівняно швидкий прогрес обчислювальної потужності комп’ютерів, а також поліпшення алгоритмів факторизації.