使用預言機反轉 RSA

假設你得到了一個有效的確定性算法“I”，它可以在 1% 的點上反轉 RSA 函式 $ Z^_{N} $ . 也就是說，如果 y $ \in $ $ Z^{N} $ 是“我”的“好”點，那麼 $ (I(N, e, y))^e $ = y。（但是，您不知道“I”的這些“好”點是什麼。）表明您可以使用“I”來建構算法“A”，該算法可以在任何輸入上反轉 RSA 函式，而且速度很快平均。也就是說，如果 x $ \xleftarrow{$} Z^*{N} $ 和 $ \xleftarrow{$} x^e $ mod N，然後 A(N, e, y) 返回 x。描述你的“A”，並解釋為什麼它總是正確且平均速度快。作為提示，請考慮使用隨機化並利用 RSA 函式的乘法特性。

我的想法是想出一個算法來挑選 $ y_1 $ 和 $ y_2 $ ，當它們相乘時得到 y，然後繼續反轉這兩個點。

1. $ y_1 \xleftarrow{$} Z^*_{N}-\lbrace{1,y\rbrace} $
2. $ y_2 \xleftarrow{$} y.y^{-1} mod N $
3. $ x_1 \leftarrow I(n, e, y_1) $
4. $ x_2 \leftarrow I(n, e, y_2) $
5. $ x \leftarrow x_1.x_2 $ 模數
6. 回复 y, x

現在，x 必須是 y 的倒數，因為 $ x^e \equiv (x_1.x_2)^e \equiv x_1^e.x_2^e \equiv y_1.y_2 \equiv y $

但是，問題是我可以成功反轉的機率 $ y_1 $ 或者 $ y_2 $ 算法 I(?) 小於 1%。因此，該算法可能在 100 個案例中有 99 個失敗。即使我重複它直到我得到“好的”點，它也會非常慢。我該如何解決這個問題並使新算法更快？而且，我如何證明它的快？

這是作業，所以我不會直接給你答案；我會給出提示：

提示 1：如何有效地生成隨機對 $ x_1, y_1 $ 和 $ x_1^e = y_1 $ ，而不訴諸甲骨文？

提示 2：你如何使用上述觀察來加速你的算法？

引用自：https://crypto.stackexchange.com/questions/34522