Нужна помощь, чтобы понять атаку общего модуля RSA, чтобы получить закрытый ключ

Я узнаю об общей атаке по модулю и узнал, что атаки с открытым модулем могут узнать закрытый ключ. Предположим, что есть 2 пользователя с открытым и закрытым ключами. $(е_1, д_1)$ и $(е_2, д_2)$. Сценарий: у злоумышленника есть открытый и закрытый ключи. $(е_2, д_2)$ и открытый ключ жертвы $e_1$ Вот шаги, чтобы получить секретный ключ:

1. $t= e_2\cdot d_2-1$
2. Злоумышленник использует расширенный алгоритм Евклида, чтобы найти $f=\gcd(t,e_1)$ чьи пары чисел $(р,с)$ удовлетворяют уравнению $r\cdot t + s\cdot e_1 = f$
3. Если $f=1$ установлен $d_1' = с$ и вернуть закрытый ключ $d_1'$
4. Если $f\neq 1$ установлен $t=\frac t s$ и вернуться к шагу 2

у меня есть пример с $d_1=17, М = 25$ это два значения, которые мы должны найти. n = 253 (общий модуль) $e_1 = 13$ (открытый ключ жертвы) $e_2 = 23$ (открытый ключ злоумышленника) $d_2 = 67$ (закрытый ключ злоумышленника) $С = 27$ (Шифрованный текст). Злоумышленник найдет $d_1'$ в соответствии с шагами:

1. $t= e_2\cdot d_2-1 = 23\cdot 67 = 1540$
2. $\gcd(t,e_1) = 1 \имеется в виду r = -2, s = 237$
3. Так $d_1' = с = 237$
4. Проверять $M = C^{d_1} \bmod n = 27^{237} \bmod 253 = 25$

Проблема в том, что я не понимаю, почему с такими шагами мы найдем секретный ключ. Может кто-нибудь объяснить мне, пожалуйста?

Мы будем интенсивно использовать следующий факт: для фиксированного публичного модуля $n$ произведение различных простых чисел, пара целых чисел $(д,г)$ формирует совпадающую пару показателей RSA [то есть с $c\mapsto c^d\bmod n\,=\,m$ способный надежно расшифровать любой открытый текст $м$ в $[0,n)$ зашифровано в $m\mapsto m^e\bmod n\,=\,c$ ] если и только если$$e\cdot d\equiv1\pmod{\lambda(n)}$$куда $\лямбда$ это Функция Кармайкла. Можно показать, что это следует из определения $\лямбда(п)$ как наименьшее строго положительное целое число $у$ такой, что $m^y\экв 1\pmod n$ для всех $m\in\mathbb Z^*$. Это выполняется независимо от знака $д$.

Следует, что $t$ шага 1 алгоритма вопроса таков, что существует $k\in\mathbb Z$ с $t=k\cdot\лямбда(n)$.

Если алгоритм находит $f=1$ таким образом, при первом выполнении шага 2 выполняется $r\cdot k\cdot\лямбда(n)+s\cdot e_1=1$, следовательно $s\cdot e_1=1+(-r\cdot k)\cdot \lambda(n)$, следовательно, когда алгоритм устанавливает $d'_1=s$ на шаге 3 выполняется $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$. Применяя первый факт, $(e_1,d'_1)$ это совпадающая пара показателей RSA для общего модуля $n$. Если мы хотим $d'_1$ чтобы быть неотрицательным, мы можем сделать $d'_1=s\bмод т$, который по определению находится в диапазоне $[0,t)$ а также такое, что $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$.

Все идет не так, когда $f\ne1$ при первом выполнении шага 2. Часто $s$ не будет делиться $t$ на шаге 4, предотвращая применение алгоритма как есть. Пример: $р=13$, $q=19$, $n=247$, $\varphi(n)=216$, $\лямбда(п)=36$, $e_1=91$, $e_2=25$, $d_1=19$, $d_2=121$, $т=3024$, $г=-4$, $s=133$, $ф=7$, $t/s=432/19\не\в\mathbb Z$.

изменение $t:=\frac t s$ к $t:=\frac т f$ на шаге 4 гарантирует делимость и оставляет алгоритм в рабочем состоянии. Аргумент: $f$ делит $e_1$, и $\gcd(e_1,\лямбда(n))=1$, таким образом $f$ взаимно прост с $\лямбда(п)$, поэтому мы перезапускаем шаги 2 с $t$ по-прежнему кратно $\лямбда(п)$.

Альтернативно: дано $(n,e_2,d_2)$ противник может повлиять $n$ (видеть это) и из этого получить $\шляпа{d_1}=е^{-1}\bmod\лямбда(п)$ соответствие $(n,e_1)$, обычно с $\шляпа{d_1}$ меньше/быстрее, чем $d'_1$; или получить рабочий приватный ключ в виде позволяющем ЭЛТ-операция таким образом, еще более быстрое расшифрование или подпись.