什麼時候破解RSAq=和−1模pq=和−1反對pq = e^{-1} bmod p?

這個問題是在最近結束的比賽中提出的。

• 我被賦予了 n 和 e 的值。e = 65537。n 是一個 2048 位的數字。
• p 是一個 1024 位的素數。
• q 是 e mod p 的模逆。這就是在這個問題中犯的錯誤。q 也是非素數。

我可以利用這些知識來簡化我對 totient 函式的計算嗎？

注意 $ q = e^{-1}\bmod p $ 表示存在整數 $ k $ 這樣 $ qe = 1 + kp $ . 因此 $$ ne = pqe = p\cdot(1+kp)/e\cdot e = p + kp^2 ,\text. \label{n-eq}\tag{$\ast$} $$

從 $ qe=1+kp $ ，我們進一步得到 $$ 1 \leq k = (qe-1)/p \leq pe/p = e = 65537 ,\text. $$

因此，要恢復 $ p $ ，我們可以遍歷所有可能的值 $ k $  - 之間 $ 1 $ 和 $ 65537 $  - 並嘗試求解二次方程 $ \eqref{n-eq} $ 每次超過整數。

引用自：https://crypto.stackexchange.com/questions/100766