Понятие криптосистемы Рабина

Криптосистема Рабина - это асимметричный криптографический метод, безопасность которого, связана со сложностью целочисленной факторизации. Криптосистема Рабина математически доказана как вычислительно безопасная против атаки с выбранным открытым текстом до тех пор, пока злоумышленник не может эффективно факторизовать целые числа
История
Алгоритм был опубликован в январе 1979 года Майклом О. Рабином Криптосистема Рабина была первой асимметричной криптосистемой, где восстановление открытого текста из зашифрованного могло быть доказано так же трудно, как факторинг.
Алгоритм шифрования
Как и все асимметричные криптосистемы, система Рабина использует пару ключей: открытый ключ для шифрования и закрытый ключ для дешифрования. Открытый ключ публикуется для любого пользователя, в то время как закрытый ключ остается известным только получателю сообщения.
Генерация ключей
Ключи для криптосистемы Рабина генерируются следующим образом:
Выберите два больших различных простых числа и такие, что
Вычислить
Затем n идет открытый ключ, а пара (pq) -закрытый ключ.
Шифрование
Сообщение M можно зашифровать, сначала преобразовав его в число с помощью обратимого отображения, а затем вычислить . Зашифрованный текст есть c.
Расшифровка
Сообщение m может быть восстановлено из зашифрованного текста, если взять его квадратный корень по модулю n следующим образом.
Вычислите квадратный корень из модуля и с помощью этих формул:
Используйте расширенный евклидов алгоритм, чтобы найти и такое, что .
Используйте китайскую теорему остатка, чтобы найти четыре квадратных корня по c модулю n:
Одно из этих четырех значений является исходным открытым текстом m, хотя какое из них является правильным, невозможно определить без дополнительной информации.
Вычисление квадратных корней
Формулы, приведенные на шаге 1 выше, на самом деле производят квадратные корни из следующего. Для первой формулы это можно доказать следующим образом:
.
Так как показатель степени является целым числом. Доказательство тривиально, если , таким образом p не делится на c. Заметим, что из этого следует, что , таким образом, c является квадратичным вычетом по модулю p. Затем
Последний шаг обосновывается критерием Эйлера.
Пример
В качестве примера рассмотрим p=7 и q=11, далее n=77 и m = 20 в качестве открытого текста. Шифротекст таков с=m2mod n=400 mod 77==15.
Расшифровка происходит следующим образом:
Вычисление
Вычисление yp=-3 и yg=2 при помощи расширенного алгоритма Евклида алгоритм.
.
Вычисление четырех кандидатов открытого текста:
Таким образом, r3 - это искомый открытый текст. Обратим внимание, что все четыре кандидата являются квадратными корнями из 15 mod 77. То есть для каждого кандидата ri2 mod 77=15, таким образом, каждый ri шифрует одно и то же значение, 15.
Алгоритм цифровой Подписи
Криптосистема Рабина может использоваться для создания и проверки цифровых подписей

. Для создания подписи требуется закрытый ключ (p,q). Для проверки подписи требуется открытый ключ n.
Подписание
Сообщение может быть подписано закрытым ключом следующим образом:
Генерация случайного значения u.
Применение криптографической хэш-функцию H для вычисления
c =H(m|u), где полоса обозначает конкатенацию. c должно быть целое число меньше n.
Рассматривая c, как зашифрованное Рабином значение для его расшифровки, используется закрытый ключ (p,q). Это даёт обычные четыре результата .
Можно было бы ожидать, что шифрование каждого из них даст результат c. Однако это будет верно только в том случае, если c окажется квадратичным вычетом p по модулю q. Чтобы определить, так ли это, зашифруйте первый результат расшифровки . Если он не шифруется c, необходимо повторить этот алгоритм с новым случайным количеством раз, которое этот алгоритм должен быть повторен, прежде чем найти подходящий u, равный 4.
Найдя то , что шифруется c, подпись есть (,u).
Проверка подписи
Подпись (r,u) сообщения m может быть проверена с помощью открытого ключа n следующим образом:
Вычислить c =H(m|u);
Шифрование r с помощью открытого ключа n.
Подпись действительна тогда и только тогда, когда шифрование r равно c.
Эффективность
Расшифровка дает три ложных результата в дополнение к правильному, так что правильный результат должен быть угадан. Это главный недостаток криптосистемы Рабина и один из факторов, не позволивших ей найти широкое практическое применение.
Если открытый текст предназначен для представления текстового сообщения, догадаться нетрудно; однако, если открытый текст предназначен для представления числового значения, эта проблема становится проблемой, которая должна быть решена с помощью какой-то схемы устранения неоднозначности. Можно выбрать простые тексты со специальными структурами или добавить заполнение, чтобы устранить эту проблему. Способ устранения двусмысленности инверсии был предложен Блюмом и Уильямсом: два используемых простых числа ограничены простыми числами, конгруэнтными 3 по модулю 4, а область возведения в квадрат ограничена множеством квадратичных вычетов. Эти ограничения превращают функцию возведения в квадрат в перестановку люка, устраняя двусмысленность.
Для шифрования необходимо вычислить квадрат по модулю n. Это более эффективно, чем RSA, который требует вычисления по крайней мере куба.
Для расшифровки используется китайская теорема об остатках, а также два модулярных возведения в степень . Здесь эффективность сравнима с RSA.
Устранение неоднозначности приводит к дополнительным вычислительным затратам, и именно это помешало криптосистеме Рабина найти широкое практическое применение.
Безопасность
Было доказано, что любой алгоритм, который расшифровывает значение, зашифрованное Рабином, может быть использован для факторизации модуля n