Схема Рабина: шифрование на квадратичных вычетах

Схема Рабина - асимметричная криптосистема, придуманная Михаэлем Рабином в 1979 году. Её особенность в том, что взлом доказуемо настолько же труден, насколько трудна факторизация большого числа: если бы кто-то умел дешифровать произвольное сообщение, он автоматически умел бы и раскладывать составной модуль на простые множители. Это редкое свойство - у популярной RSA такой строгой эквивалентности нет. Разберём, как устроены ключи, почему при дешифровании появляются сразу четыре варианта и как с этой неоднозначностью бороться. Если хотите сразу прогнать конкретные числа, соберите запрос в форме ниже.

Идея: возведение в квадрат вместо степени

В большинстве асимметричных систем шифрование - это возведение открытого текста в большую степень по модулю. Схема Рабина радикально упрощает эту операцию: показатель степени всегда равен двойке. Открытый ключ - это просто составной модуль $n = p \cdot q$, где $p$ и $q$ - два больших секретных простых числа. Шифрование сообщения $m$ выглядит так:

$$c = m^2 \bmod n$$

Никакой публичной экспоненты $e$, как в RSA, не нужно. Зато вся хитрость перемещается в дешифрование: чтобы восстановить $m$, нужно извлечь квадратный корень из $c$ по модулю $n$. А эта операция выполнима за разумное время только тому, кто знает разложение $n = p \cdot q$. Именно на этой асимметрии - легко возвести в квадрат, трудно извлечь корень без множителей - и держится вся схема Рабина.

Рассчитать для своей задачи

Квадратичные вычеты и почему корней четыре

Чтобы понять дешифрование, нужно вспомнить понятие квадратичного вычета. Число $c$ называется квадратичным вычетом по модулю $p$, если уравнение $x^2 \equiv c \pmod p$ имеет решение. Для простого модуля $p$ таких решений ровно два: $x$ и $-x$ (то есть $p - x$). Это прямое следствие того, что многочлен второй степени над полем имеет не более двух корней.

Теперь ключевой момент. Сама проверка, является ли $c$ вычетом, опирается на квадратичный закон взаимности и символ Лежандра. Модуль Рабина $n = p \cdot q$ составной, поэтому по китайской теореме об остатках извлечение корня по модулю $n$ распадается на два независимых извлечения - по модулю $p$ и по модулю $q$. У каждого из них по два корня, и комбинаций получается $2 \times 2 = 4$:

$$\begin{aligned} x &\equiv \pm m_p \pmod p, \\ x &\equiv \pm m_q \pmod q. \end{aligned}$$

Каждая из четырёх пар знаков, собранная обратно по модулю $n$, даёт свой корень. Один из них - исходное сообщение $m$, остальные три - посторонние корни. Эта четырёхзначность и есть главная плата за простоту шифрования: получатель должен как-то понять, который из четырёх корней был отправлен.

Генерация ключей: простые специального вида

Извлекать корни проще всего, когда оба простых дают остаток 3 при делении на 4, то есть $p \equiv q \equiv 3 \pmod 4$. Такие простые называют простыми Блюма, а их произведение - числом Блюма. При этом условии квадратный корень по модулю простого вычисляется одной формулой возведения в степень, без перебора:

$$m_p \equiv c^{(p+1)/4} \bmod p, \qquad m_q \equiv c^{(q+1)/4} \bmod q$$

Проверить, что это действительно корень, легко: возведя $m_p$ в квадрат, по малой теореме Ферма получаем обратно $c$. Поэтому генерация ключей сводится к выбору двух больших простых вида $4k+3$, их перемножению и публикации произведения. Секретный ключ - пара $(p, q)$, открытый ключ - одно число $n$. Сравните это с устройством алгоритма Диффи-Хеллмана: там секрет прячется за дискретным логарифмом, здесь - за факторизацией.

Дешифрование шаг за шагом

Полный алгоритм восстановления сообщения из шифртекста $c$ при известных $p$ и $q$ выглядит так:

1. Вычислить частичные корни $m_p \equiv c^{(p+1)/4} \bmod p$ и $m_q \equiv c^{(q+1)/4} \bmod q$.
2. Найти коэффициенты Безу $y_p$ и $y_q$ из расширенного алгоритма Евклида: $y_p \cdot p + y_q \cdot q = 1$.
3. Собрать четыре корня по китайской теореме об остатках:

$$\begin{aligned} r_1 &= (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \bmod n, \\ r_2 &= n - r_1, \\ r_3 &= (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \bmod n, \\ r_4 &= n - r_3. \end{aligned}$$

Все четыре числа $r_1, r_2, r_3, r_4$ при возведении в квадрат по модулю $n$ дают исходный $c$. Один из них и есть отправленное сообщение. Без знания $p$ и $q$ шаги 1 и 3 выполнить нельзя - именно поэтому открытому ключу разложение $n$ недоступно.

Рассчитать для своей задачи

Как снять неоднозначность четырёх корней

Проблема четырёх корней решается избыточностью в самом сообщении. Перед шифрованием в открытый текст добавляют заранее оговорённую метку - например, дублируют последние биты или приписывают фиксированный паттерн. После дешифрования получатель проверяет все четыре корня и оставляет тот единственный, в котором метка на месте. Вероятность, что посторонний корень случайно пройдёт проверку, ничтожно мала.

Альтернативный приём - символ Якоби. Сообщения ограничивают теми $m$, у которых символ Якоби $\left(\frac{m}{n}\right) = +1$ и которые меньше $n/2$; вместе эти два условия выделяют из четырёх корней ровно один. На практике в реальных реализациях (например, в стандарте IEEE P1363) почти всегда применяют именно встроенную в текст избыточность - она проще и устойчивее.

Связь стойкости с факторизацией

Главное теоретическое достоинство схемы Рабина - доказуемая редукция. Предположим, существует алгоритм, который по $c$ и $n$ возвращает какой-нибудь корень $m'$ из четырёх. Тогда с вероятностью $1/2$ корень $m'$ не равен $\pm m$, а значит $m' \not\equiv \pm m \pmod n$, при том что $m'^2 \equiv m^2 \pmod n$. Из этого следует, что $n$ делит $(m' - m)(m' + m)$, но не делит ни один из сомножителей по отдельности. Поэтому

$$\gcd(m' - m, n)$$

даёт нетривиальный делитель $n$ - то есть факторизацию. Вывод: если факторизация трудна, то трудна и дешифровка. Ни у RSA, ни у Диффи-Хеллмана такой строгой эквивалентности с конкретной классической задачей нет.

Где схема применяется

В чистом виде криптосистема Рабина в продакшене встречается редко: четыре корня и уязвимость к атаке с выбором шифртекста делают её неудобной без аккуратной обвязки. Зато её идея - основа целого семейства. На квадратичных вычетах построена вероятностная криптосистема Гольдвассер-Микали, схема подписи Рабина-Уильямса, а также ряд протоколов с доказуемой стойкостью. В учебных курсах схема Рабина незаменима: на ней удобно показать, как из элементарной операции (квадрат по модулю) вырастает система с формальной редукцией к факторизации. Это делает её любимым примером в разделах теории чисел и криптографии.

Частые ошибки

• Считать, что у корня всегда два значения. По простому модулю - да, два. По составному модулю $n = p \cdot q$ их четыре, и игнорирование этого ломает дешифрование.
• Путать открытый и секретный ключ. Открытый ключ - это только $n$, без $p$ и $q$. Никакой публичной экспоненты, как в RSA, здесь нет.
• Брать произвольные простые. Без условия $p \equiv q \equiv 3 \pmod 4$ простая формула корня через возведение в степень не работает - придётся применять Тонелли-Шенкса.
• Шифровать без избыточности. Без метки в тексте получатель не отличит настоящее сообщение от трёх посторонних корней и не сможет однозначно расшифровать.
• Считать схему стойкой к любым атакам. Базовая схема Рабина уязвима к атаке с выбором шифртекста - именно та редукция, что даёт стойкость, против активного атакующего работает во вред.

FAQ

Чем схема Рабина отличается от RSA? В RSA шифрование - это возведение в публичную экспоненту $e$, а дешифрование - в секретную $d$; стойкость связана с факторизацией лишь косвенно. В схеме Рабина показатель всегда равен 2, публичной экспоненты нет, а взлом доказуемо эквивалентен факторизации. Платой за это становится неоднозначность из четырёх корней при дешифровании.

Почему важно условие $p \equiv q \equiv 3 \pmod 4$? При нём квадратный корень по модулю простого вычисляется одной формулой $c^{(p+1)/4} \bmod p$. Без этого условия извлечение корня требует более сложного алгоритма Тонелли-Шенкса. Простые такого вида называют простыми Блюма, а их произведение - числом Блюма.

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

Коротко

Схема Рабина - асимметричная криптосистема, где шифрование сводится к возведению в квадрат по составному модулю $n = p \cdot q$, а дешифрование - к извлечению квадратного корня, доступному только владельцу простых множителей. Из-за составного модуля корней получается четыре, и нужный выбирают по встроенной в текст избыточности. Главное достоинство - доказуемая эквивалентность взлома и факторизации: умеющий дешифровать умеет и раскладывать $n$. Это же свойство делает базовую схему уязвимой к атаке с выбором шифртекста, поэтому на практике её применяют только с дополнением и проверкой.