打破線性同餘生成器的變化
所以我最近一直在嘗試學習一些密碼分析和破解偽隨機生成器，但我在學習中遇到了障礙，因為我無法破解這個問題。基本上它是一個 LCG 的變體，但我不知道如何解決它，即使我很確定它很弱，我只是缺乏對嘗試什麼技術的理解。
生成器來自 TI 計算器使用的隨機數生成器，此處可以找到。
基本上它是這樣的：
$$ \begin{align} s_1&\gets s_1\cdot a_1\bmod m_1\ s_2&\gets s_2\cdot a_2\bmod m_2\ r&\gets (s_1-s_2)/m_1\ \text{if }&r<0\text{ then }r\gets r+1 \end{align} $$ [編者註：該生成器相當於Pierre l’Écuyer 的“組合多重遞歸隨機數生成器”中的圖 3之一，CACM 第 31 卷第 6 期，1988 年 6 月，p。742-751。模數 $ m_i $ 是略低於素數 $ 2^{31} $ 和 $ \gcd(m_1-1,m_2-1)=2 $ 和 $ m_1 $ 略大於 $ m_2 $ . 這 $ a_i $ 甚至是稍低於常數的常數 $ \sqrt{m_i} $ , 給出最大周期，據說可以為乘法 LCG 的頻譜測試提供良好的結果。多變的 $ r $ 是浮點數。在 l’Écuyer 的論文中，我們有 $ r=((s_1-s_2)\bmod m_1)\cdot(\widetilde{1/m_1}) $ 在哪裡 $ \widetilde{1/m_1} $ 預設情況下是一個接近的浮點近似值 $ 1/m_1 $ ， 和 $ v=u\bmod m $ 意思是 $ 0\le v<m $ 和 $ m $ 劃分 $ u-v $ . ] 這種微小的變化扼殺了我的嘗試（已經斷斷續續幾個月了）。如果有人解釋如何僅從我想知道的結果中獲得下一個數字，或者即使您能指出我正確的方向，我將不勝感激。
謝謝！！！
PS：我希望這是正確的類別，我是這個網站的新手，也搜尋過類似的問題，但找不到任何可以幫助我的問題。
該生成器的狀態定義為 $ s_1 $ 和 $ s_2 $ , 並且可以在下面 $ 2^{62} $ 狀態。按照今天的標準，這在密碼學上是不安全的，這需要超過 80 位的安全性，但對於使用單個 CPU 的純蠻力進行快速密碼分析來說仍然太多了。我們至少需要一次嚴重的加速。
最明顯的是：列舉（小於 $ 2^{31} $ ） 狀態 $ s_1 $ ，並且對於每個推導 $ s_2 $ 從一個輸出（給我們 $ (s_1-s_2)\bmod m_1 $ ） 和 $ s_1 $ （或者，在極少數情況下， $ s_1 $ 不能有那個值）；然後檢查這些 $ s_1 $ 和 $ s_2 $ 還有更多的輸出。
魔鬼在細節中，尤其是我們所犯的錯誤 $ (s_1-s_2)\bmod m_1 $ 從實際輸出反向計算。如果 $ r $ 給出了小數點右邊的 6 個小數，我們只能得到 31 位中的大約 20 個（但如果 $ r $ 給出了 6 個有效數字，我們會得到更多的小 $ r $ ）。然而，這足以重建 $ s_2 $ 從兩個連續的輸出和值 $ s_1 $ 沒有列舉所有可能的值 $ (s_1-s_2)\bmod m_1 $ （那隻是最後的手段）。
以上是粗略的，但是通過在現代 CPU 上的仔細實施，可以在幾秒鐘內完成工作。並且（引用布魯斯·施奈爾（Bruce Schneier）將這句話歸因於 NSA）：
攻擊總是變得更好；他們永遠不會變得更糟。
注意：由於 Pierre l’Écuyer 的生成器已經存在了近 3 年，它非常適用於非加密目的，例如模擬、便攜、考慮到該約束相對高效，並且顯然經常使用，如果它被研究過，我不會感到驚訝深入，並發現了更好的攻擊。
假設我們有一個 $ r $ （如 4.833936e-5）讓我們走回 $ (s_1-s_2)\bmod m_1\ =d $ 確切地說，未優化的算法是：
- 為了 $ s_1 $ 從 $ 1 $ 至 $ m_1-1 $
- $ s_2\gets(s_1-d)\bmod m_1 $
- 如果 $ 0<s_2<m_2 $
$ s_{1.1}\gets s_1\cdot a_1\bmod m_1 $
$ s_{2.1}\gets s_2\cdot a_2\bmod m_2 $
如果 $ (s_{1.1}-s_{2.1})\bmod m_1 $ 匹配輸出足夠好
$ s_{1.2}\gets s_{1.1}\cdot a_1\bmod m_1 $
$ s_{2.2}\gets s_{2.1}\cdot a_2\bmod m_2 $
如果 $ (s_{1.2}-s_{2.2})\bmod m_1 $ 匹配輸出足夠好
- 成功，輸出 $ (s_1,s_2) $ 並停下來。
- 失敗，精益求精。
一個可能的改進是大多數時候 $ s_{1.1}−s_{2.1} $ 因人而異 $ a_1-a_2 $ 從外循環的一個步驟到另一個步驟，這很小，可以快進 $ s_1 $ 相當。我相信僅此一項就可以將攻擊減少到幾分之一秒（cf說）。