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

Криптосистема Рабина — криптографическая система с открытым ключом, безопасность которой обеспечивается сложностью поиска квадратных корней в кольце остатков по модулю составного числа. Безопасность системы, как и безопасность метода RSA, обусловлена сложностью разложения на множители больших чисел. Зашифрованное сообщение можно расшифровать 4 способами. Недостатком системы является необходимость выбора истинного сообщения из 4-х возможных.

История

В январе 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. Процесс расшифровки выглядит следующим образом:

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

[math]\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} }[/math]

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

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

Оценка алгоритма

Эффективность

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

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

Скорость вычислений

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

Для декодирования китайская теорема об остатках применена вместе с двумя возведениями в степень по модулю. Здесь эффективность сопоставима RSA.

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

Безопасность

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

Криптосистема Рабина является доказуемо стойкой к атаке на основе подобранного открытого зашифрованного текста в рамках подхода «все или ничего», тогда и только тогда, когда задача о разложении целого числа на простые множители является трудноразрешимой.

Стойкость по принципу «все или ничего» заключается в том, что, имея текст, зашифрованный определенным алгоритмом, атакующий должен восстановить блок исходного текста, размер которого, как правило, определяется параметром безопасности криптосистемы. Имея исходный и зашифрованный текст, атакующий должен восстановить целый блок секретного ключа. При этом атакующий либо добивается полного успеха, либо не получает ничего. Под словом «ничего» подразумевается, что атакующий не имеет никакой секретной информации ни до, ни после безуспешной атаки.

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

К примеру, при добавлении избыточности, например, повторение последних 64 бита, можно сделать корень единственным. Алгоритм расшифрования в этом случае выдает единственный корень, который уже известен атакующему.

Процесс дополнительно уязвим, так как при кодировании используются только квадратные остатки. В примере при n = 77 используется только 23 из 76 возможных состояний.

См. также

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

Литература

• Шаблон:Source
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.