是不是很難恢復ppp從kφ(p)ķφ(p)k phi(p)?
給定 $ k\phi(p) $ , 是不是很難恢復 $ p $ ? 這裡， $ p $ 是一個大素數， $ \phi(\cdot) $ 是歐拉的總函式和 $ k $ 是一個未知整數。
或者恢復的複雜性是什麼 $ p $ 從 $ k \phi(p) $ .
如果 $ p $ 是素數，那麼 $ \phi(p) = p-1 $ ; 所以問題是“給定 $ k(p-1) $ , 有人能很好地猜到什麼嗎 $ p $ 可能是？”攻擊者不太可能將其限制為一個特定的值 $ p $ （因為可能有多個值 $ p $ 這是合理的），但是攻擊者可能能夠建構一個簡短的可能性列表；如果攻擊者可以在某處創建具有正確值的列表，我們將認為它成功。
答案取決於有多大 $ k $ （和 $ p-1 $ ) 是（以及，產品有多大）。如果要麼很小（例如，不超過 100 或 200 位），要麼交替平滑（即，由很小的素因子組成），那麼ECM將能夠拉出 $ k $ （或者 $ p-1 $ )，給攻擊者一個很好的猜測。此外，如果兩者都有較大的因數，但乘積足夠小，則NFS將能夠分解乘積。但是，如果兩者都有大素數作為因數，那麼恢復的可能性不大 $ p $ .
但是，以上假設攻擊者沒有關於任何一個的進一步資訊 $ p $ 或者 $ k $ ; 如果他（例如）也知道值 $ pq $ （對於一個大素數 $ q $ )，那麼他很容易推導出來 $ p $ ; 他選擇一個隨機值 $ a $ , 併計算 $ gcd( pq, a^{k\phi(p)}-1 \bmod pq ) $ ; 很有可能，那是 $ p $ （假設 $ k $ 無關 $ q $ ; 如果值 $ k $ 是（比方說）的倍數 $ q-1 $ , 那麼還有其他方法可以恢復 $ p $ 和 $ q $ .
如果你知道多個 $ p $ 和 $ k $ 小於 $ \sqrt(p) $ 您可以使用與poncho不同的方法。
注意：知道的倍數 $ p $ 是 RSA 的典型案例，您知道模數 $ N $ 由製成 $ p\times q $ ，因此，如果您的問題涉及 RSA，那麼您只剩下對 $ k $ .
您可以使用的方法是對 Alexander May 在對 RSA 的新部分密鑰暴露攻擊中設計的Coppersmith 方法的改編，但在他的博士論文的 Theorem 10 中有更好的描述。
梅定理指出：
讓 $ N = pq $ 和 $ p > q $ . 此外，讓 $ k $ 是一個（未知）整數，它不是的倍數 $ q $ . 假設我們知道一個近似值 $ \widetilde{kp} $ 的 $ kp $ 和 $ |kp-\widetilde{kp}| \leq 2N^\frac14 $ . 然後我們可以找到因式分解 $ N $ 在時間多項式中 $ \log N $
請注意，您有 $ \widetilde{kp} = k(p-1) = kp -k $ 這是一個近似值 $ kp $ 誤差等於 $ k $ . 因此只要 $ k \leq 2N^\frac14 $ 你可以找到 $ p $ 在多項式時間內遵循梅定理。
一個實用的提示：雖然綁定在 $ k $ 翻譯成“的位大小 $ k $ 應該最大等於比特大小的一半 $ p $ “，在實踐中，比特大小為 $ k $ 小於 10 到 30 位（取決於模數大小）的範圍，以便能夠在合理的時間內（秒與天相比）計算 LLL 基減少。
如果未知 $ k $ 在您的問題中指的是 CRT-RSA 方程： $ ed_p = 1 \mod(p-1) = 1 +k(p-1) $ 超過你的上限 $ k $ 和 $ e $ 其大小是已知的。