基於RSA的方程組求解
我有 4 個變數 $ n $ , $ x $ , $ y $ ， 和 $ z $ ：
這裡， $ n = p\cdot q $ 和 $ p $ 和 $ q $ 是不同的素數
$$ \begin{align} x &= m^p \bmod n\ y &= m^q \bmod n\ z &= m^n \bmod n\ \end{align} $$ 我怎樣才能找到 $ m $ ?
由於這是過去的 CTF，我們可以提供解決它的指南。
歐拉定理指出，如果 $ \gcd(m,n) =1 $ 和 $ m,n \in \mathbb{Z}^+ $ 然後
$$ m^{\varphi (n)} \equiv 1 \pmod{n} \label{5}\tag{1} $$
和 $ \varphi $ 是 歐拉的總函式。如果是 $ n= pq $ 在哪裡 $ p $ 和 $ q $ 是不同的素數$$ \varphi (n) = (p-1)(q-1) $$
現在，一點算術；
$$ \begin{align} \varphi (n) &= (p-1)(q-1)\ \varphi (n) &= pq-p- q +1\ \varphi (n) &= n - p - q +1\ \end{align} $$
現在在方程上使用它 $ \ref{5} $
$$ m^{n - p - q +1} \equiv 1 \pmod{n} $$
其餘的應該是顯而易見的。$$ \frac{m^{n}\cdot m}{m^p\cdot m^q} \equiv 1 \pmod{n} $$
其餘的應該更明顯。
$$ m \equiv \frac{m^p\cdot m^q}{m^{n}} \pmod{n} \label{lab1}\tag{2} $$從事 CTF 工作的人可以直接使用方程 $ \ref{lab1} $ .
然而，要達到這一點，我們需要確保 $ m^n $ 與模有逆 $ n $ .
唯一不可逆的元素是 $ kp+n\mathbb Z $ （為了 $ 0<k<q $ ） 和 $ kq+n\mathbb Z $ （為了 $ 0<k<p $ ) 因為要有逆必須有 $ \gcd(a,n) =1 $ 這不是倍數的情況 $ p $ 和 $ q $ （實際上，確實有 $ \varphi(n) $ 可逆元素 $ \mathbb Z $ .
所以 $ m^n $ 是可逆的 $ p \nmid m $ 或者 $ q \nmid m $ . 為此，SageMath 的打擊程式碼是對某些人的驗證 $ m $ , 沒有倒數 $ m^n $ .
剩下的就是一個大劇透，因為它包含 SageMath 程式碼！要查看它，您需要編輯此答案。
由於這是一個 CTF，因此可以確保 CTF 組織者選擇了 $ m $ 可逆讓CTF玩家有解決方案！