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

Данная система не получила широкого применения, но приведена здесь для иллюстрации возможности использовать при асимметричном шифровании операции модульного возведения в квадрат. Система основана на трудности извлечения квадратного корня по модулю составного числа без знания разложения модуля на множители.

Каждый абонент выбирает собственную пару простых чисел p и q, с соблюдением следующего требования: , что позволит извлекать квадратный корень не прибегая к алгоритму Шенкса.

Затем вычисляют: и выбирают

Открытым ключом является пара

Закрытым ключом является пара

Особенностью системы является очень простая и быстрая операция зашифрования :

Для расшифрования необходимо вычислить:

Ниже приведено краткое доказательство работоспособности, в котором для удобства опущены операции приведения по модулю:

Для удобства вычислений принимаем:

и соответственно:

Извлечение корней производится по модулю простых чисел p и q:

Каждое из сравнений дает по два корня и, соответственно вариантов значения s_i получается всего четыре (что является основным недостатком системы). Найдем их попарно, при помощи КТО и свойства корней:

Четыре варианта расшифрования получим, выполнив вычисления:

Для распознавания правильного варианта расшифрования, как правило вводят некоторую обратимую функцию избыточности F(m), позволяющую с высокой вероятностью выбрать правильный вариант. В приведенном ниже примере F(m) = 44||m.

Задача 3.5. Для заданной пары простых чисел p и q и открытого текста m, определить самостоятельно остальные параметры шифрсистемы Рабина и осуществить зашифрование и расшифрование. Проверить совпадение исходного m и одного из четырех полученных m_j’ значений открытого текста.

Пример решения