14.2. Криптографічний система RSA
Самий загальний алгоритм відкритого ключа доступу - криптографічний система RSА. названа по імені його винахідників Ривеста, Шаміра, Еделман (Rivest, Shamir і Adelman).
RSА використовує два типи ключів - e і d. де e - відкритий, a d - секретний. Припустимо, що P - вихідний текст і C - зашифрований текст. Аліса використовує C = P e mod n. щоб створити зашифрований текст C з вихідного тексту P; Боб використовує P = C d mod n. щоб витягти вихідний текст (файл), переданий Алісою. Модулів n створюється дуже велика кількість за допомогою процесу генерації ключів, який ми обговоримо пізніше.
Для шифрування і дешифрування застосовують зведення в ступінь по модулю. Як ми вже обговорювали в лекціях 12-13, при використанні швидкого алгоритму спорудження до рівня по модулю здійснимо в поліноміальний час. Однак знаходження модульного логарифма так само складно, як і розкладання числа по модулю. Для нього немає алгоритму з поліноміальних часом. Це означає, що Аліса може зашифрувати повідомлення загальнодоступним ключем (e) в поліноміальний час. Боб також може розшифрувати його в поліноміальний час (бо він знає d). Але Єва не може розшифрувати це повідомлення, тому що вона повинна була б обчислити корінь e-тої міри з C з використанням модульної арифметики. Малюнок 14.5 показує ідею RSA.
Мал. 14.5. Складність операцій в RSA
Іншими словами, Аліса використовує однобічну функцію (піднесення до степеня за модулем) з лазівкою, відомої тільки Бобу. Єва не знає лазівку, тому не може розшифрувати повідомлення. Якщо коли-небудь знайдуть поліноміальний алгоритм для модуля обчислення кореня e-тої міри з n. то зведення в ступінь по модулю n більше не односторонньої функцією.
Малюнок 14.6 показує загальну ідею процедури, використовуваної в RSA.
RSA використовує зведення в ступінь по модулю для шифрування / дешифрування. Для того щоб атакувати закритий текст, Єва повинна обчислити
Мал. 14.6. Шифрування, дешифрування і генерація ключів в RSA
Дві алгебраїчні структури
RSA використовує дві алгебраїчних структури: кільце і групу.
Кільця шифрування / дешифрування. Шифрування і дешифрування зроблені з використанням комутативного кільця з двома арифметичними операціями: додавання і множення. В RSA це кільце загальнодоступним, бо модуль n загальнодоступний. Будь-хто може послати повідомлення Бобу, використовуючи це кільце для шифрування.
Групи генерування ключів. RSA використовує мультипликативную групу для генерації ключів. Група підтримує тільки множення і ділення (мультипликативную інверсію), які необхідні для того, щоб створити відкриті і секретні ключі. Цю групу треба приховати, тому що її модуль є секретним. Ми побачимо, що якщо Єва знайде цей модуль, вона зможе легко атакувати криптографічний систему.
RSA використовує дві алгебраїчних структури: відкрите кільце R =
генерація ключів
Боб використовує кроки, показані в алгоритмі 14.2. щоб створити свої відкритий і секретний ключі. Після генерації ключів Боб оголошує кортеж (e, n) як свій відкритий ключ доступу: Боб зберігає d як свій секретний ключ. Боб може відмовитися від p, q і; вони не можуть змінити його секретний ключ, не змінюючи модуль. Для безпеки рекомендується розмір для кожного простого p або q - 512 біт (майже 154 десяткові цифри). Це визначає розмір модуля, n 1024 біта (309 цифр).
14.2. RSA-генерація ключів
В RSA кортеж (e, n) - відкритий ключ доступу; ціле число d - секретний ключ.
шифрування
Передати повідомлення Бобу може будь-хто, використовуючи його відкритий ключ доступу. Шифрування в RSA може бути виконано з використанням алгоритму з поліноміальною складністю за часом, як показано в алгоритмі 14.3. Швидкий алгоритм піднесення до степеня було розглянуто в лекціях 12-13. Розмір початкового тексту повинен бути менше ніж n; якщо розмір початкового тексту більше, то він повинен бути розділений на блоки.
14.3. шифрування RSA
дешифрування
Щоб розшифрувати повідомлення зашифрованого тексту, яке Боб отримав в RSA. він може використовувати алгоритм 14.4. Це можна виконати, використовуючи алгоритм з поліноміальною складністю за часом, якщо розмір зашифрованого тексту менше, ніж n.
14.4. дешифрування RSA
В RSA p і q повинні бути принаймні 512 бітів; n повинні бути принаймні 1024 біт.
доказ RSА
Використовуючи другу версію теореми Ейлера, яка обговорювалася в лекціях 12-13, ми можемо довести, що шифрування і дешифрування інверсний один одному.
Припустимо, що вихідний текст, відновлений Бобом, є P1. Доведемо, що він еквівалентний P.
Вітаю! Хотілося б прояснити наступне питання: у МТІ припинена державна акредитація та коли буде восстановлена- невідомо, а в диплом про профперепідготовка видається на базі МТІ (як я зрозумів). Як закінчиться справа з отриманням диплома?
Питання важливе й актуальне, тому що необхідно терміново пройти навчання і отримати диплом і не хотілося б витрачати час і платити гроші даремно (якщо диплом виявиться недійсним і т.п.). Роз'ясніть, будь ласка, докладніше ситуацію.
Добрий день, Хотілося б прояснити ви в майбутньому плануєте узгоджувати цю програму, з регуляторами і чи пройде сам диплом зараз, коли вводяться проф стандарти?