Метод Райвеста-Шамира-Адлемана (RSА).

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

Для генерації пари ключів беруться два великих випадкових простих числа p та q. З метою максимальної крипостійкості p і q вибираються рівної довжини. Потім обчислюється їх добуток n = p*q (n називається модулем). Далі випадковим чином вибирається число e (ключ шифрування), що задовольняє умові: 1 <e <(p - 1) * (q - 1) і не має спільних дільників окрім 1 (взаємно просте) з числом f(n)=(p-1)*(q-1).

Нарешті розширений алгоритм Евкліда використовується для обчислення ключа дешифрування d, такого, що ed = 1 mod f(n). Число d таке, що (ed - 1) ділиться на (p - 1) (q-1).

Відкритий ключ (Public) :

 n- добуток двух простих чисел p і q (повинні зберігатися в секреті);

e - число, взаємно просте з f(n)

Секретний ключ (Private) : d = e-1mod f(n)

Шифрування: c = m^e mod n

Дешифрування: m = c^d mod n

Числа d і n - також взаємно прості числа. Числа e і n - відкритий ключ, а d - секретний. Два простих числа p і q зберігаються в секреті.

Для шифрування повідомлення m необхідно виконати його розбивку на блоки, кожний з яких менше n (для двійкових даних вибирається найбільша ступінь числа 2, менша n). Тобто якщо p і q - 100 розрядні прості числа, то n буде містити близько 20 розрядів і кожен блок повідомлення m_i повинен мати таке ж число розрядів. Якщо ж потрібно зашифрувати фіксоване число блоків, їх можна доповнити декількома нулями зліва, щоб гарантувати, що блоки завжди будуть менше n. Зашифроване повідомлення c складатиметься з блоків c_i тієї ж самої довжини.

Шифрування зводитися до обчислення : c_i=m_i^emodn.

При дешифруванні для кожного зашифрованого блоку c_i обчислюється

m_i = c_i^dmodn

Останнє справедливо, так як

c_i^d = (m_i^e)^d = m_i^ed = m_i^kf(n)+1 = m_i·1 = m_i

Всі обчислення виконуються за mod n. Повідомлення може бути зашифроване за допомогою d, а дешифровано за допомогою e, можливий будь-який вибір.

Передбачається, що крипостійкість RSA залежить від проблеми розкладання на множники великих чисел. Проте ніколи не було доведено математично, що потрібно n розкласти на множники. Щоб відновити m по с та e. Не виключено, що може бути відкритий зовсім інший спосіб криптоаналізу RSA. Однак, якщо цей новий спосіб дозволить криптоаналітику отримати d, він також може бути використаний для розкладання на множники великих чисел. Також можна атакувати RSA, вгадавши значення (p-1) (q-1). Однак цей метод не простіше розкладання n на множники. При використанні RSA розкриття навіть кількох бітів інформації з шифротексту не легше, ніж дешифрування всього повідомлення. Самою очевидною атакою на RSA є розкладання n на множники. Будь-який супротивник зможе отримати відкритий ключ e та модуль n. Щоб знайти ключ дешифрування d, супротивник повинен розкласти n на множники. Криптоаналітик може перебирати всі можливі d, поки не підбере правильне значення. Але подібна силова атака навіть менш ефективна, ніж спроба розкладання n на множники. У 1993 р. був запропонований метод криптоаналізу, заснований на малій теоремі Ферма. На жаль, цей метод виявився повільнішим за розкладання на множники. Існує ще одна проблема. Більшість загальноприйнятих тестів встановлює простоту числа з певною ймовірністю. Що станеться якщо p або q виявиться складовим? Тоді у модуля n буде три або більше дільників. Відповідно деякі дільники будуть менше рекомендованої величини, що, у свою чергу відкриває можливості для атаки шляхом факторизації модуля. Інша небезпека полягає в генерації псевдопростих чисел (чисел Кармайкла), що задовольняють тестам на простоту, але при цьому не є простими. Однак імовірність генерації таких чисел пренебрежимо мала. На практиці, послідовно застосовуючи набір різних тестів на простоту, можна звести ймовірність генерації складеного числа до необхідного мінімуму.