軟問題：密碼學中漂亮證明的例子有哪些？
這些可能包括任何證明、簡化、構造等。例如，對乍一看似乎很難的問題的簡單解決方案。優雅的結構隱藏了深刻的數學概念，但一旦呈現就易於使用。
任何你認為優雅和聰明的東西。
特別歡迎帶有漂亮圖形的證明。
（最好是可以合理地融入 StackExchange 答案的那些）。
定理。 分組密碼的 ECB 模式在選擇明文攻擊下是可區分的，具有可笑的高優勢。
證明。
假設你有一個隨機算法 $ S(y, n) $ 可以，有成本 $ C $ 和成功機率 $ \varepsilon $ ，計算隨機二次殘差的平方根 $ y $ 以產品為模 $ n = pq $ 的隨機素數。（例如，這個算法可以從隨機預言模型中的 Rabin 簽名偽造者推導出來。）你能用 $ S $ 作為隨機算法中的子程序 $ F(n) $ 考慮因素 $ n $ ? 是的！
定義算法 $ F(n) $ 如下：
- 挑選 $ 0 \leq x < n $ 均勻隨機。
- 計算 $ y = x^2 \bmod n $ .
- 計算 $ \xi = S(y, n) $ .
- 如果 $ x \pm \xi \equiv 0 \pmod n $ ， 失敗; 否則返回 $ \gcd(x \pm \xi, n) $ .
該算法的代價是一個隨機選擇 $ n $ 可能性，一個平方模 $ n $ , $ C $ （的代價 $ S $ )，以及一個 gcd 與 $ n $ ——所以這個算法比任何計算平方根的算法成本都高。成功機率是多少？
第 1 步總是成功。第 2 步總是成功。步驟 3 成功的機率 $ \varepsilon $ . 第 4 步是有趣的一步。
- 每個二次餘數，如 $ y $ , 最多有四個不同的平方根模 $ n $ : 兩個平方根模 $ p $ , 和兩個平方根模 $ q $ . 如果我們能找到兩個不同的根 $ x $ 和 $ \xi $ 的 $ y $ ——不僅僅是符號——那麼因為 $ x^2 \equiv y \pmod n $ 和 $ \xi^2 \equiv y \pmod n $ ， 我們有 $ x^2 \equiv \xi^2 \pmod n $ 用非平凡整數方程$$ k n = x^2 - \xi^2 = (x + \xi) (x - \xi) $$對於一些 $ k $ . 此外，我們知道 $ n $ 不能分割 $ x \pm \xi $ 自從 $ x \pm \xi \not\equiv 0 \pmod n $ . 因此$$ n \mid (x + \xi) (x - \xi), \quad \text{but} \quad n \nmid x \pm \xi. $$ 因此，由於整數具有唯一的因式分解， $ n = pq $ 必須與*_* $ x \pm \xi $ ， 所以 $ \gcd(x \pm \xi, n) $ 在以下情況下返回一個非平凡因素 $ x \pm \xi \not\equiv 0 \pmod n $ .
大約有1/2的機會 $ S $ 返回 $ \pm x $ 以便 $ x \pm \xi \equiv 0 \pmod n $ : $ S $ 不知道四個平方根中的哪一個 $ x $ 的 $ y $ 即使它想阻撓我們，我們也開始了。所以步驟 4 以大約 1/2 的機率成功，算法以大約 1/2 的機率成功 $ \varepsilon/2 $ . 如果我們重試直到成功，則預期的試驗次數要考慮 $ n $ 大約是2。
該證明由邁克爾·拉賓（Michael Rabin）於 1979 年在一份關於公鑰簽名方案提案的技術報告中發表，以證明其與保理相關的安全性。與之前的容易破解的RSA 提案（免付費牆）不同，Rabin 的簽名方案是歷史上第一個仍然受到現代審查的簽名方案，只要選擇合適的參數大小，通過使用散列而不是僅僅作為一種方法壓縮大消息，但作為破壞消息結構的安全性的組成部分。今天，教科書和維基百科一直將拉賓的密碼系統歪曲為一個損壞的加密方案或一個損壞的無雜湊簽名方案，好像幾乎沒有人願意閱讀這篇論文。
拉賓是否是第一個發表平方根可以進行因式分解的證明的人，我不知道——大約在 1643 年，費馬給梅森寫了一封信，觀察到找到了一種寫作方法 $ n $ 由於平變異數會導致因式分解，因此拉賓之前的數論家似乎可能會遇到與模組化平方根算法導致因式分解算法相同的增量改進。但是，話又說回來，直到 1970 年代公鑰密碼學的發展，如果一開始沒有平方根算法，也許人們對這種觀察幾乎沒有興趣，顯然我們當時沒有，現在仍然沒有現在有！
唉，同樣的技術不能證明 RSA 問題——反相 $ x \mapsto x^e \bmod n $ 什麼時候 $ \gcd(e, \phi(n)) = 1 $ ——再簡單不過了，因為至多只有一個 $ e^{\mathit{th}} $ 根：根據貝祖的身份，存在一些 $ d $ 和 $ k $ 這樣 $ d e - k \phi(n) = \gcd(e, \phi(n)) = 1 $ ， 或者 $ e d = 1 + k \phi(n) $ ，所以如果 $ y \equiv x^e \pmod n $ ， 然後$$ y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k\phi(n)} \equiv x \cdot (x^{\phi(n)})^k \equiv x \pmod n, $$由歐拉定理；所以 $ x \mapsto x^e \bmod n $ 是雙射。