RSA 和強 RSA 假設
RSA 假設：
給定一個隨機生成的 RSA 模數 $ n $ , 指數 $ r $ 和一個隨機 $ z \in \mathbb{Z}_n^{*} $ ， 尋找 $ y $ 這樣 $ y^r=z $ .
強 RSA 假設：
給定一個隨機選擇的 RSA 模數 $ n $ , 和一個隨機 $ z \in \mathbb{Z}_n^{} $ ， 尋找 $ r>1 $ 和 $ y \in \mathbb{Z}_n^{} $ 這樣 $ y^r=z $ .
在強 RSA 假設中，他們通常會說“ $ r $ 可以選擇依賴於的方式 $ z $ , 而在通常的 RSA 假設中 $ r $ 可以以獨立的方式選擇 $ z $ ”。
在某種程度上取決於 $ z $ ? 如何實現這種依賴？如果有人可以解釋這一點，我將不勝感激。
即使將一些值替換為 $ n $ , $ z $ 等等會很棒，會幫助我理解更多。
提前非常感謝。
“是什麼意思 $ r $ 可以選擇依賴於的方式 $ z $ “？
一個假設的算法 $ \mathcal A_2 $ 打破強大的 RSA 假設有輸入¹ $ (n,z) $ 和 $ n $ 由 RSA 密鑰生成過程生成，並輸出² $ (r,y) $ 這樣 $ y^r\equiv z\pmod n $ , 唯一的其他約束是 $ r $ 那 $ r>1 $ . 與假設算法對比 $ \mathcal A_1 $ 打破具有輸入的 RSA 假設¹ $ (n,r,z) $ 和 $ (n,r) $ 由 RSA 密鑰生成過程生成，並輸出² $ y $ 這樣 $ y^r\equiv z\pmod n $ .
區別使問題不同：一種假設的算法 $ \mathcal A_2 $ 建立 $ r $ 作為 $ r\gets n $ 對破壞 RSA 沒有明顯用處，因為選擇 $ r $ 標準 RSA 密鑰生成過程從未使用過。相同如果 $ \mathcal A_2 $ 正在生成 $ r $ 作為一個函式 $ z $ ，例如 $ r\gets2,\lfloor z/7\rfloor+3 $ ， 因為那個 $ r $ 匹配的機率極低 $ r $ 由 RSA 密鑰生成過程生成。
在另一個方向，我們可以把一個假設的算法 $ \mathcal A_1 $ 種入其中之一 $ \mathcal A_2 $ kind，例如通過反复嘗試增量奇數 $ r\ge3 $ , 送出 $ (n,r,z) $ 至 $ \mathcal A_1 $ 用作子程序，如果在某個時間限制內輸出 $ y $ , 給 $ (r,y) $ 作為我們的輸出 $ \mathcal A_2 $ .
強 RSA 假設（即不存在算法² $ \mathcal A_2 $ ) 因此是不比 RSA 假設弱的假設（即不存在算法² $ \mathcal A_1 $ ）。這些不同的概念是正確命名的！
¹ 隱含安全參數，可以作為比特大小 $ n $ ，以及隨機算法的隨機輸入。
² 安全參數在時間多項式內成功機率不為零。
³ 它由早於 RSA 的CC Cocks 密碼系統使用，並且被認為同樣安全。