19. Зламування криптограм rsа.

RSA - криптографічна система відкритого ключа, що забезпечує такі механізми захисту як шифрування і цифровий підпис (автентифікація - встановлення автентичності). Криптосистема RSA розроблена в 1977 році і названа на честь її розробників Ronald Rivest, Adi Shamir і Leonard Adleman.

Алгоритм RSA працює наступним чином: беруться два досить великих простих числа p і q та обчислюється їх добуток n = p * q; n називається модулем.

Потім вибирається число e, що задовольняє умові 1 <e <(p - 1) * (q - 1) і не має спільних дільників окрім 1 (взаємно просте) з числом (p - 1) * (q - 1).

Потім обчислюється число d таким чином, що (e * d - 1) ділиться на (p - 1) * (q - 1).

• e - відкритий (public) показник

• d - приватний (private) показник.

• (n; e) - відкритий (public) ключ

• (n; d). - Приватний (private) ключ.

Дільники (фактори) p і q можна або знищити або зберегти разом з приватним (private) ключем.

Якби існували ефективні методи розкладання на співмножники (факторингу), то, розклавши n на співмножники (фактори) p і q, можна було б отримати приватний (private) ключ d. Таким чином надійність криптосистеми RSA заснована на важко вирішуваній - практично не вирішуваній - завдання розкладання n на співмножники (тобто на неможливості факторингу n) так як в даний час ефективного способу пошуку співмножників не існує.

Припустимо, Аліса хоче послати Бобу повідомлення M. Аліса створює зашифрований текст З, зводячи повідомлення M в ступінь e і множачи на модуль n: C = M^**e* (mod n), де e та n - відкритий (public) ключ Боба. Потім Аліса посилає С (зашифрований текст) Бобу. Щоб розшифрувати отриманий текст, Боб зводить отриманий зашифрований текст C в ступінь d і примножує на модуль n: M = c**^d*(mod n); залежність між e і d гарантує, що Боб вирахує M вірно. Так як тільки Боб знає d, то лише він має можливість розшифрувати отримане повідомлення.

Існує кілька способів злому RSA. Найбільш ефективна атака - знайти секретний ключ, відповідний необхідного відкритому ключу. Це дозволить нападаючому читати всі повідомлення, зашифровані відкритим ключем, і підробляти підпис. Таку атаку можна провести, знайшовши головні співмножники (фактори) загального модуля n - p і q. На підставі p, q і e (загальний показник) нападаючий може легко обчислити приватний показник d. Основна складність в пошуку головних співмножників (факторинг) n. Безпека RSA залежить від розкладання на співмножники (факторингу), що є важким завданням, що не має ефективних способів вирішення.

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

Інший спосіб зламати RSA полягає в тому, щоб знайти метод обчислення кореня ступеня e з mod n. Оскільки С = M^e mod n, то коренем ступеня e з mod n є повідомлення M. Обчисливши корінь, можна розкрити зашифровані повідомлення й підробляти підписи, навіть не знаючи приватний ключ. Така атака не еквівалентна факторингу, але в даний час невідомі методи, які дозволяють зламати RSA таким чином. Однак в особливих випадках, коли на основі одного і того ж показника відносно невеликий величини шифрується досить багато пов'язаних повідомлень, є можливість розкрити повідомлення. Згадані атаки - єдині способи розшифрувати всі повідомлення, зашифровані даними ключем RSA.

Існують і інші типи атак, що дозволяють, однак, розшифрувати лише одне повідомлення і не дозволяють нападнику розкрити інші повідомлення, зашифровані тим же ключем. Також вивчалася можливість розшифрування частини зашифрованого повідомлення.

Найпростіше напад на окреме повідомлення - атака по передбачуваному відкритому тексту. Нападник, маючи зашифрований текст, передбачає, що повідомлення містить якийсь певний текст, потім шифрує передбачуваний текст відкритим ключем одержувача і порівнює отриманий текст з наявним зашифрованим текстом. Таку атаку можна запобігти, додавши в кінець повідомлення кілька випадкових бітів. Інша атака на єдине повідомлення застосовується в тому випадку, якщо відправник посилає одне і те ж повідомлення M трьом кореспондентам, кожен з яких використовує загальний показник e = 3. Знаючи це, нападаючий може перехопити ці повідомлення і розшифрувати повідомлення M.

Таку атаку можна запобігти, вводячи перед кожним шифруванням у повідомлення кілька випадкових бітів. Також існують кілька атак по зашифрованому тексту (або атаки окремих повідомлень з метою підробки підпису), при яких нападаючий створює деякий зашифрований текст і отримує відповідний відкритий текст, наприклад, змушуючи обманним шляхом зареєстрованого користувача розшифрувати підроблене повідомлення. Зрозуміло, існують і атаки, націлені не на криптосистему безпосередньо, а на вразливі місця всієї системи комунікацій в цілому. Такі атаки не можуть розглядатися як злом RSA, так як говорять не про слабкість алгоритму RSA, а скоріше про уразливість конкретної реалізації. Наприклад, нападаючий може заволодіти секретним ключем, якщо той зберігається без належної обережності. Необхідно підкреслити, що для повного захисту недостатньо захистити виконання алгоритму RSA і прийняти заходи математичної безпеки, тобто використовувати ключ достатньої довжини, так як на практиці найбільший успіх мають атаки на незахищені етапи управління ключами системи RSA.