打破 PRNG 計劃
假設 PRNG 在 [0,100) 中生成小數的方案如下
給定消息和密鑰，計算標籤：= HMAC512（消息，密鑰）。取標籤的前 5 個十六進製字元。如果結果小於十進制的 1,000,000，則將其除以 10,000 並返回，否則取標籤後面的 5 個十六進製字元並重複。如果 5 個十六進製字元組的所有 25 種情況產生的十進制整數 >=1,000,000，則剩餘的 3 個十六進制數字除以 100（十進制）並返回（十進制）。
為了計算數字流，消息中有一個計數器，它隨著每一代而遞增。
顯然，這不是一個好的方案（考慮到最後列出的條款）。但是，知道消息而不是密鑰的攻擊者能否預測後續數字或預測後續數字是否會在門檻值內（>=50 或 <50）？
問題中的生成器在內部轉換512 $ 512 $ -位串指定標記成一個輸出確定：
- 作為1/104 $ 1/10^4 $ 一個非負整數小於106 $ 10^6 $ ，只要“如果結果更小..”子句適用；
- 作為1/102 $ 1/10^2 $ 一個非負整數小於212 $ 2^{12} $ ， 除此以外。
確定過程 2 發生在d2=(220−106)25⋅212 $ d_2=(2^{20}-10^6)^{25}\cdot2^{12} $ 之間2512 $ 2^{512} $ 標記可以採用的位字元串（暫時忽略標記的生成方式），佔很小的比例d2/2512=2−110.8… $ d_2/2^{512}=2^{-110.8\dots} $ 這些位字元串。
在這個階段，應用的密碼學家：
- 得出的結論是，確定過程 2 更可能是由於某物的故障而不是任何其他原因（包括如果對手知道並可以操縱密鑰和消息），並忽略了確定過程 2（至少在級別其他可用資訊）；
- 看到剩下的唯一可信的確定過程會產生輸出數字X $ x $ 和0≤X<100 $ 0\le x<100 $ 並且可以用點後4位十進制數字精確表示，如果標記位串具有平坦分佈，則具有平坦分佈；
- 看到產生這樣的完美 TRNG 之間的任何區別X $ x $ （以下：明顯的目標）和輸出，也將是 HMAC512 假設未知密鑰的區別，他立即拒絕；
然後繼續前進，對問題中的 PRNG 對於任何實際目的都足夠接近其明顯目標感到滿意，包括如果密鑰未知則不可預測。
理論家繼續不為所動，仔細地將可能的輸出分為兩類：
- 中的一個212 $ 2^{12} $ 數字X $ x $ 和0≤X<40.96 $ 0\le x<40.96 $ 並且可以在點後用 2 個十進制數字精確表示；
- 其他號碼X $ x $ 和0≤X<100 $ 0\le x<100 $ 並且可以在點後用 4 個十進制數字精確表示。
每一個106−212 $ 10^6-2^{12} $ 類別 2 的輸出僅通過確定過程 1 達到，因此對於C2=(2512−d2)/106 $ c_2=(2^{512}-d_2)/10^6 $ 標籤位字元串。因此假設標籤位串的平坦分佈，達到類別 2 的機率^p2=C2⋅(106−212)/2512 $ \widehat{p_2}=c_2\cdot(10^6-2^{12})/2^{512} $ , 小於賠率p2=1−212/106 $ p_2=1-2^{12}/10^6 $ 在明顯目標中達到該類別：^p2=p2⋅(1−2−110.8…) $ \widehat{p_2}=p_2\cdot(1-2^{-110.8\dots}) $ .
那個發生器在理論家的眼裡是壞掉的，因為他有一個比他想像中的任何 HMAC512 都好得多的區分器。
也就是說，理論家可以設計一種策略，使他能夠以賠率獲勝p>1/2 $ p>1/2 $ 在玩遊戲時，目標是從一個給定的 RNG 輸出中猜測該 RNG 是否被選為問題中的 RNG（通過公平拋硬幣）（達到類別 2，賠率已知）^p2>1/2 $ \widehat{p_2}>1/2 $ ），或者作為一個具有明顯目標的TRNG（以已知的機率達到該類別p2>^p2 $ p_2>\widehat{p_2} $ ）。理論家對給他最大可能優勢的策略感興趣，定義為ε=|p−1/2| $ \epsilon=|p-1/2| $ （使用絕對值是因為將比基於拋硬幣的答案更糟糕的策略變成比這更好的策略是微不足道的）。
為了實現這個目標，當給定的 RNG 輸出屬於第 1 類時，理論家會假設在問題中押注 RNG，否則押注 TRNG （不是根據我之前給出的標準隨機押注，對那個錯誤感到抱歉，但我是應用類型）。計算賠率p $ p $ 對於獲勝，我們考慮該策略的兩個相互排斥的獲勝案例：
- 問題中的RNG被選中，其輸出屬於類別1，有賠率(1−^p2)/2 $ (1-\widehat{p_2})/2 $ ;
- TRNG 被選中，它的輸出屬於類別 2，有賠率p2/2 $ p_2/2 $ ;
給予p=(p2−^p2+1)/2 $ p=(p_2-\widehat{p_2}+1)/2 $ 因此優勢ε=(p2−^p2)/2=2−111.8… $ \epsilon=(p_2-\widehat{p_2})/2=2^{-111.8\dots} $ .
留給讀者作為練習，以表明如果n>1 $ n>1 $ 給出相同選擇的RNG的輸出，獲得的優勢小於n⋅ε $ n\cdot\epsilon $ ; 仍然非常邊緣化n≈1/ε≈2111.8 $ n\approx 1/\epsilon\approx2^{111.8} $ 輸出；變得相當大n≈ε−3/2≈2167.7 $ n\approx \epsilon^{-3/2}\approx2^{167.7} $ 輸出。