Криптосистема Рабина

В январе 1979 года Майкл О. Рабин опубликовал описание своей системы. Было доказано, что восстановление исходного текста из зашифрованного столь же трудно, как факторизация больших чисел. Система Рабина стала первой асимметричной криптосистемой, для которой было выполнено такое доказательство. Сложность восстановления связана с трудностью извлечения квадратного корня по модулю составного числа N = р · q. Задача факторизации и задача по извлечению квадратного корня эквивалентны, то есть:

• зная простые делители числа N можно извлекать квадратные корни по модулю N;
• умея извлекать квадратные корни по модулю N, можно разложить N на простые множители.

Система Рабина, как и любая асимметричная криптосистема, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и может быть опубликован для всеобщего обозрения. Закрытый ключ необходим для расшифровки и должен быть известен только получателям зашифрованных сообщений.

Процесс генерации ключей следующий:

• выбираются два случайных числа p и q с учётом следующих требований:
  • числа должны быть большими (см. разрядность);
  • числа должны быть простыми;
  • должно выполняться условие: p ≡ q ≡ 3 mod 4.

Выполнение этих требований сильно ускоряет процедуру извлечения корней по модулю р и q;

• вычисляется число n = p · q;
• число n — открытый ключ; числа p и q — закрытый.

Пример. Пусть p = 7 и q = 11. Тогда n = p · q = 7 · 11 = 77. Число n = 77 — открытый ключ, а числа p = 7 и q = 11 — закрытый. Получатель сообщает отправителям число 77. Отправители шифруют сообщение, используя число 77, и отправляют получателю. Получатель расшифровывает сообщение с помощью чисел 7 и 11. Приведённые ключи плохи для практического использования, так как число 77 легко раскладывается на простые множители (7 и 11).

Исходное сообщение m (текст) шифруется с помощью открытого ключа — числа n по следующей формуле:

c = m² mod n.

Благодаря использованию умножения по модулю скорость шифрования системы Рабина больше, чем скорость шифрования по методу RSA, даже если в последнем случае выбрать небольшое значение экспоненты.

Пример (продолжение). Пусть исходным текстом является m = 20. Тогда зашифрованным текстом будет: c = m² mod n = 20² mod 77 = 400 mod 77 = 15.

Для расшифровки сообщения необходим закрытый ключ — числа p и q. Процесс расшифровки выглядит следующим образом:

• сначала, используя алгоритм Евклида, из уравнения ${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$ находят числа ${\displaystyle y_{p}}$ и ${\displaystyle y_{q}}$;
• далее, используя китайскую теорему об остатках, вычисляют четыре числа:

${\displaystyle {\begin{matrix}r&=&(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-r&=&n-r\\s&=&(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-s&=&n-s\end{matrix}}}$

Одно из этих чисел является истинным открытым текстом m.

Пример (окончание). В результате расшифровки получаем: ${\displaystyle m\in \{64,\mathbf {20} ,13,57\}}$. Видим, что один из корней является исходным текстом m.

• Ранцевая криптосистема Меркля-Хеллмана

• Мао В. Шифрование — асимметричные методы // Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.