RSA，指數是模的一個因子
這個週末我參加了一個 CTF，但遇到了一個我無法解決的任務。我找不到任何文章，所以我希望你能幫助我。
鑑於： $$ n = pq\ c_1\cong m_1^{\hspace{.3em}p} \mod n\ c_2\cong m_2^{\hspace{.3em}q} \mod n $$ 了解價值觀 $ c_1,c_2,n $ 然後 $ p $ 是 1024 位和 $ q $ 是 1000 位，與 $ p,q $ 是素數。有沒有有效的恢復方法 $ m_1,m_2 $ ?
我知道如果我能夠恢復 $ p,q $ 由於費馬定理，這是微不足道的，但是這個問題又是使 RSAP 變得困難的原因。
唯一給出的其他資訊是 $ m_1,m_2 $ 為 25 個字節（200 位）。沒有任何服務可以充當神諭。
這裡的關鍵思想是 $ m_1 $ （或者 $ m_2 $ ) 相對於模量非常小。這讓我們可以應用通常的 Coppersmith 技術。
我們知道 $ c_1 = m_1^p \bmod n $ ，這需要 $ c_1 \equiv m_1 \bmod p $ . 由此我們知道 $ c_1 - m_1 = t\cdot p $ ， 對於一些 $ t $ . 換句話說， $ \gcd(c_1 - x, n) = p \ge n^{1/2} $ 對於一些 $ x = m_1 \le n^{1/4} $ . 這裡是我們的預期 $ x = m_1 $ 遠小於 $ n^{1/4} $ ，事實上，這使得事情更容易計算。
這在 Sage 中很容易重現：
sage: p = random_prime(2^1024, lbound=2^1023+2^1022) sage: q = random_prime(2^1000, lbound=2^999+2^998) sage: n = p*q sage: sage: m1 = randint(0, 2^200) sage: m2 = randint(0, 2^200) sage: c1 = power_mod(m1, p, n) sage: c2 = power_mod(m2, q, n) sage: sage: P.<x> = Zmod(n)[] sage: f = (c1 - x).monic() sage: f.small_roots(beta=0.5) [1106883791702122199703869965196585780508362129433642126297878] sage: m1 1106883791702122199703869965196585780508362129433642126297878恢復 $ m_2 $ 可以以相同的方式完成，或者通過恢復因子一次 $ m_1 $ 被收回—— $ p = \gcd(c_1 - m_1, n) $ ——和解密 $ m_2 $ 一般。