Криптосистема Рабина: атака с выбранным зашифрованным текстом

Я читал в литературе, что криптосистему Рабина можно взломать с помощью атаки с выбранным зашифрованным текстом. Описано, что после расшифровки выбранного шифротекста злоумышленник может факторизовать открытый ключ. $n$ используя квадратный корень с вероятностью $1/2$. Но в статье не описано, как делается эта факторизация.

Если кто-то может привести пример, буду признателен.

Я предполагаю, что это не домашнее задание.

Это на самом деле довольно просто:

• Выберите случайное значение $г$

• Вычислить $s = r^2 \bmod n$, и отправить $s$ к дешифратору Рабина

• С $s$ является квадратичным остатком, дешифратор Рабина вернет некоторое значение $t = \sqrt{s} \bmod n$.

• В настоящее время, $s$ имеет четыре квадратных корня (при условии, что $n$ имеет два простых множителя, и вы случайно не выбрали $г$ это не относительно просто $n$); если у вас есть $ т = г $ или же $t = n-r$, это не сработало. Если это одно из двух других возможных значений, то мы имеем $r^2 = t^2 \bmod n$, это, $(r+t)(r-t) = kn$, для некоторого целого числа $к$; однако ни $г+т$ ни $р-т$ кратны $n$, следовательно $\gcd(r+t, n)$ является нетривиальным фактором $n$ (и $\gcd(r-t, n)$ еще один нетривиальный фактор).

Потому что мы выбрали $г$ случайным образом Рабин не может узнать, какую из четырех возможностей мы выбрали; он возвращает один из них, поэтому вероятность того, что он вернет тот, который дает нам факторизацию, равна $2/4 = 0.5$