Rsa
帶冪運算的離散對數 oracle
認為 $ (n, d) $ 是一個 RSA 私鑰對。我們只知道公鑰（wlog 假設它是 $ (n, 2^{16}+1) $ 我們得到了神諭 $ E $ , 解密 oracle 為 $ (n, d) $ . 有沒有有效的算法來恢復 $ d $ ? 這比直接攻擊已知的明文和密文對要容易一些，對於任何 $ m $ 我們可以建立這種關係：
$$ E(m) \equiv m^d \pmod n $$
不，沒有已知的恢復方法 $ d $ 使用甲骨文，給定 $ m $ , 返回 $ m^d \bmod n $ ; 也沒有證據表明這種方法不存在。
這種方法意味著 RSA 問題（即，給定 $ m^e \bmod n $ ， 恢復 $ m $ ) 等價於分解問題（其中的知識 $ d, e $ 可以讓你解決）；不知道這兩個問題是否等價。