題 偽隨機數和真正的隨機數如何不同,為什麼重要?


我從來沒有這麼做過。只是說你用任何語言寫一個小程序就可以擲骰子(只是用骰子作為例子)。在600,000卷後,每個數字將被滾動大約100,000次,這是我所期望的。

為什麼有網站致力於“真正的隨機性”?當然,根據上面的觀察,獲得任何數字的機率幾乎都是1,而不管它有多少數字可供選擇。

我試過了 蟒蛇:這是6000萬卷的結果。最高的變化是0.15。這不是隨機的嗎?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

653


起源


看看維基百科上的文章 硬件生成隨機數 另見 - stats.stackexchange.com/questions/32794/... - steadyfish
你是什​​麼意思“卷一些骰子”?它是否附有機器人手臂和相機? - starblue
雖然我同意你語氣的一般要點,但我們經常擔心這個問題,但它在現實生活中被利用了: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
看到 這個 關於在線撲克遊戲的文章缺少真正的隨機性以解釋它的重要性。 - Varaquilex
如果你只是保持一個0-5計數器並相應地滾動一個骰子,666千萬次,你也會獲得相同的分佈。 - jcora


答案:


讓我們玩一些電腦撲克,只有你,我和我們都信任的服務器。服務器使用偽隨機數生成器,在我們播放之前使用32位種子初始化。所以大約有40億個可能的套牌。

我手裡拿著五張牌 - 顯然我們不是在玩德州撲克。假設這些卡片發給我一個,一個給你,一個給我,一個給你,依此類推。所以我在牌組中有第一張,第三張,第五張,第七張和第九張牌。

之前我運行了40億次偽隨機數生成器,每個種子運行一次,並將為每個生成的第一張卡寫入數據庫。假設我的第一張卡片是黑桃皇后。這只能在每52個可能的甲板中顯示一個作為第一張卡,因此我們將可能的甲板從40億減少到大約8000萬左右。

假設我的第二張牌是三顆心。現在,我使用產生黑桃皇后的8000萬種子作為第一個數字,再運行我的RNG 8000萬次。這花了我幾秒鐘。我寫下了產生三顆心的所有甲板作為第三張牌 - 我手中的第二張牌。這只是甲板的2%左右,所以現在我們已經減少到200萬套。

假設我手中的第三張牌是7個球桿。我有一個200萬種子的數據庫,可以處理我的兩張卡片;我再次運行我的RNG 200萬次,找到產生7個俱樂部的甲板中的2%作為第三張牌,而我們只有4萬個套牌。

你看這是怎麼回事。我運行我的RNG 40000多次找到生產我的第四張牌的所有種子,然後讓我們降到800副牌,再運行800次以獲得生產我的第五張牌的~20粒種子,現在我只是生成那些二十副牌,我知道你有二十個可能的牌之一。而且,我非常了解接下來要繪製的內容。

現在你明白為什麼真正的隨機性很重要嗎?您對此的描述方式,您認為如此 分配 很重要,但分配不是使過程隨機的原因。 不可預測性 是一個使進程隨機的原因。

UPDATE

基於(現在由於其非建設性質而刪除)評論,至少有0.3%讀過這篇文章的人對我的觀點感到困惑。當人們反對我沒有做過的觀點,或者更糟糕的是,爭論 對於 指出我 沒有 做上 假設我沒有製作它們,那麼我知道我需要更清楚,更仔細地解釋。

這個詞似乎特別混亂 分配 所以我想小心地打電話給我們。

手頭的問題是:

  • 偽隨機數和真正的隨機數如何不同?
  • 為什麼差異很重要?
  • 這些差異是否與PRNG的輸出分佈有關?

讓我們先考慮一下 完善 生成隨機撲克牌的方法。然後我們將看到生成套牌的其他技術是如何不同的,以及是否可以利用這種差異。

讓我們首先假設我們有一個標記的魔術盒 TRNG。作為它的輸入,我們給它一個大於或等於1的整數n,並且作為它的輸出它給出了一個在n和n之間的真正隨機數。盒子的輸出是 完全不可預測 (當給出一個不是一個的數字時)和一個和n之間的任何數字都可能與另一個相同;也就是說 分配 是 制服。 (我們可以執行其他更高級的隨機性統計檢查;我忽略了這一點,因為它與我的論證沒有密切關係。通過假設,TRNG在統計上是完全隨機的。)

我們從一張未洗過的牌組開始。我們在方框中詢問1到52之間的數字 - 也就是說, TRNG(52)。無論它返回什麼數字,我們都會從我們排序的牌組中扣掉許多牌並取出該牌。它成為洗牌的第一張牌。然後我們要求 TRNG(51) 並執行相同操作以選擇第二張卡,依此類推。

另一種看待它的方式是:有52個! = 52 x 51 x 50 ... x 2 x 1個可能的甲板,大約2個226。我們真正隨機選擇了其中一個。

現在我們處理這些卡片。當我看到我的卡片時 什麼都不知道 你有什麼牌。 (除了明顯的事實,你沒有我的任何卡。)他們可能是任何卡,概率相等。

所以,讓我確保我清楚地解釋這一點。我們有 均勻分佈 每個單獨的輸出 TRNG(n);每個人以1 / n的概率選擇1和n之間的數字。此外,這個過程的結果是我們選擇了52個中的一個!可能的甲板概率為1/52!,因此分佈 在可能的甲板上 是  制服。

行。

現在讓我們假設我們有一個不太神奇的盒子,貼上標籤 PRNG。在你可以使用它之前,它必須是 播種 使用32位無符號數。

在旁邊: 為什麼32?它不能用64或256或10000位數種子播種?當然。但是(1)在實踐中,大多數現成的PRNG都是32位數種子,(2)如果你有10000位的隨機性來製作種子那你為什麼要使用PRNG呢?你已經擁有了10000比特的隨機性!

無論如何,回到PRNG的工作方式:播種後,你可以像使用它一樣使用它 TRNG。也就是說,你傳遞一個數字n,它會返回一個介於1和n之間的數字。此外, 該輸出的分佈或多或少是均勻的。也就是說,當我們問 PRNG 對於1到6之間的數字,無論種子是什麼,我們大約有六分之一的時間得到1,2,3,4,5或6。

我想多次強調這一點,因為它似乎是讓某些評論者感到困惑的一個。 PRNG的分佈至少在兩個方面是均勻的。首先,假設我們選擇任何特定的種子。我們期待這個序列 PRNG(6), PRNG(6), PRNG(6)... 一百萬次將在1到6之間產生均勻的數字分佈。第二,如果我們選擇了一百萬種不同的種子並且被稱為 PRNG(6)  一旦 對於每個種子,我們再次期望從1到6的數字均勻分佈。 跨越這些操作的PRNG的一致性與我所描述的攻擊無關

這個過程據說是 偽隨機 因為盒子的行為實際上是完全確定的;它從2中選擇一個32 基於種子的可能行為。也就是說,一旦播種, PRNG(6), PRNG(6), PRNG(6), ...  產生一個 序列 具有均勻分佈的數字,但該序列是 完全 由種子決定。對於給定的呼叫序列,比如PRNG(52),PRNG(51)......等等,只有2個32 可能的順序。種子基本上選擇我們得到的。

為了生成套牌,服務器現在生成種子。 (怎麼樣?我們會回到那一點。)然後他們打電話 PRNG(52)PRNG(51) 等等產生甲板,類似於之前。

該系統易受我所描述的攻擊。為了攻擊服務器,我們首先提前將我們自己的盒子副本與0一起播種並要求 PRNG(52) 寫下來。然後我們用1重新播種,請求 PRNG(52)並寫下來,一直到232-1。

現在,使用PRNG生成套牌的撲克服務器必須以某種方式生成種子。 他們是怎麼做的並不重要。 他們可以打電話 TRNG(2^32) 得到一個真正隨機的種子。或者他們可以將當前時間作為種子,這根本不是隨機的;我知道你的時間和你一樣多。我的攻擊點是無所謂, 因為我有我的數據庫。當我看到我的第一張卡片時,我可以消除98%的可能種子。當我看到我的第二張牌時,我可以消除98%以上,等等,直到最終我可以得到一些可能的種子,並且極有可能知道你手中的東西。

現在,我再次強調,這裡的假設就是這樣 如果我們打電話 PRNG(6) 一百萬次我們會得到大約六分之一的時間。那個分佈是(或多或少) 制服,和 如果你所關心的那種分佈的一致性, 沒關係。問題的關鍵是 是否存在其他分佈的東西 PRNG(6) 我們在乎什麼? 答案是 。我們關心 不可預測性 同樣。

另一種看待問題的方法是即使分配了一百萬次調用 PRNG(6) 可能沒事, 因為PRNG只選擇232 可能的行為,它不能產生每一個可能的套牌。  它只能生成232 2226 可能的甲板;一小部分。所以分配 在所有甲板上 很糟糕。但同樣,這裡的根本攻擊是基於我們能夠成功 預測 過去和未來的行為 PRNG 從其輸出的一小部分樣本。

讓我說這是第三次或第四次,以確保它沉入。這裡有三個分佈。首先,產生隨機32位種子的過程的分佈。這可以是完全隨機的,不可預測的和統一的 攻擊仍然有效。第二,撥打一百萬電話 PRNG(6)。這可以完全統一,攻擊仍然有效。第三,我所描述的偽隨機過程選擇的甲板的分佈。這種分佈非常差;只有極少數IRL可能的甲板可以選擇。攻擊取決於 預測 PRNG的行為 基於對其輸出的部分了解

ASIDE:此攻擊要求攻擊者知道或能夠猜出PRNG使用的確切算法是什麼。這是否現實是一個懸而未決的問題。然而, 在設計安全系統時,即使攻擊者知道程序中的所有算法,您也必須將其設計為安全抵禦攻擊。換句話說:為了系統安全而必須保密的安全系統部分稱為“密鑰”。如果您的系統依賴於算法的安全性,那麼您使用的算法就是秘密 你的密鑰包含那些算法。那是一個 非常 弱勢地位!

繼續。

現在我們假設我們標有第三個魔術盒 CPRNG。它是一個加密版本的 PRNG。它需要256位種子而不是32位種子。它與...分享 PRNG 種子從2中選擇的屬性256 可能的行為。和我們的其他機器一樣,它具有大量調用的屬性 CPRNG(n) 在1和n之間產生均勻的結果分佈:每個發生在1 / n的時間。我們可以對它進行攻擊嗎?

我們最初的攻擊要求我們存儲232 種子映射到 PRNG(52)。但是2256 是一個更大的數字;跑步是完全不可行的 CPRNG(52)很多時間並存儲結果。

但是假設有一些 其他 採取價值的方式 CPRNG(52) 從中推斷出關於種子的事實?到目前為止,我們一直非常愚蠢,只是強迫所有可能的組合。我們可以查看魔術盒內部,弄清楚它是如何工作的,並根據輸出推斷種子的事實嗎?

沒有。細節太複雜,無法解釋,但CPRNG的設計巧妙,因此推斷它是不可行的 任何 關於第一次輸出的種子的有用事實 CPRNG(52) 或來自 任何 輸出的子集, 無論多大

好的,現在讓我們假設服務器正在使用 CPRNG 生成套牌。它需要256位種子。它是如何選擇種子的?如果它選擇攻擊者可以預測的任何值 然後突然襲擊再次變得可行。如果我們可以確定2256 可能的種子,服務器可能只選擇了40億個種子 我們又回來了。我們可以再次發起這次攻擊,只關注可能產生的少量種子。

因此,服務器應該工作以確保256位數 均勻分佈  - 也就是說,每個可能的種子的概率為1/2256。基本上服務器應該調用 TRNG(2^256)-1 生成種子 CPRNG

如果我可以破解服務器並查看它以查看選擇了什麼種子怎麼辦? 在這種情況下,攻擊者知道CPRNG的完整過去和未來。服務器的作者需要防範這種攻擊! (當然,如果我能成功安裝這種攻擊,那麼我也可以直接將錢轉移到我的銀行賬戶,所以也許那不是那麼有趣。重點是:種子必須是一個難以猜測的秘密,而且真正隨機的256位數很難猜到。)

回到我之前關於縱深防禦的觀點:256位種子是  到這個安全系統。 CPRNG的想法是系統是安全的 只要鑰匙是安全的;即使關於算法的所有其他事實都是已知的,只要你能保守密鑰,對手的牌就是不可預測的。

好的,所以種子應該是秘密的和均勻分佈的,因為如果不是,我們就可以發動攻擊。我們假設輸出的分佈 CPRNG(n) 是統一的。 所有可能的甲板上的分佈怎麼樣?

你可能會說:有2個256 CPRNG輸出的可能序列,但只有2226 可能的甲板。因此,有更多可能的序列而不是甲板,所以我們很好;在這個系統中,現在(很有可能)每個可能的IRL套牌都是可能的。這是一個很好的論據,除了......

2226 只是一個 近似52!把它分開。 2256/ 52!不可能是一個整數,因為一件事,52!可以被3整除,但沒有兩個的力量!由於這不是一個整數,現在我們有所有甲板的情況 可能但是 有些套牌比其他套牌更有可能

如果不清楚,請考慮數字較小的情況。假設我們有三張卡,A,B和C.假設我們使用帶有8位種子的PRNG,因此有256種可能的種子。有256種可能的輸出 PRNG(3) 取決於種子;沒有辦法讓三分之一的人成為A,其中三分之一是B,其中三分之一是C,因為256不能被3整除。必須對其中一個人有一點偏見。

同樣,52不會均分為2256因此,選擇第一張牌並偏離其他牌時,必須對某些牌有偏見。

在我們原有的32位種子系統中存在巨大的偏差,絕大多數可能的平台從未生產過。在這個系統中,所有的甲板都可以生產,但是 甲板的分佈仍然存在缺陷。有些套牌是 很輕微 比其他人更可能。

現在的問題是: 我們是否有基於這個漏洞的攻擊? 答案是 在實踐中,可能不是。 CPRNG的設計是為了這樣 如果種子真的是隨機的 然後 區分它們在計算上是不可行的 CPRNG 和 TRNG

好的,讓我們總結一下。

偽隨機數和真正的隨機數如何不同?

它們表現出的可預測性水平不同。

  • 真正的隨機數是不可預測的。
  • 如果可以確定或猜測種子,則所有偽隨機數都是可預測的。

為什麼差異很重要?

因為存在系統安全性依賴的應用程序 不可預測性

  • 如果使用TRNG來選擇每張卡,那麼系統是無懈可擊的。
  • 如果使用CPRNG來選擇每張卡,那麼如果種子既不可預測又未知,則係統是安全的。
  • 如果使用具有小種子空間的普通PRNG,則無論種子是不可預測的還是未知的,系統都是不安全的;足夠小的種子空間容易受到我所描述的那種暴力攻擊。

差異是否與PRNG的輸出分佈有關?

分佈均勻或缺乏分佈 個人電話 至 RNG(n) 與我所描述的攻擊無關。

正如我們所見,兩者都是 PRNG 和 CPRNG 在選擇所有可能的甲板上的任何單個甲板的可能性方面產生差的分佈。該 PRNG 更糟糕,但兩者都有問題。

還有一個問題:

如果TRNG比CPRNG好得多,後者反過來比PRNG好得多,為什麼有人使用CPRNG或PRNG?

有兩個原因。

第一:費用。 TRNG是 昂貴。生成真正隨機的數字很困難。 CPRNG僅為任意多次呼叫提供良好的結果  致電TRNG尋找種子。不利的是當然 你必須把這粒種子保密

第二:有時我們  可預測性和我們關心的是良好的分配。如果您正在生成“隨機”數據作為測試套件的程序輸入,並且它顯示了一個錯誤,那麼再次運行測試套件會再次產生錯誤會很好!

我希望現在更清楚了。

最後,如果你喜歡這個,那麼你可能會對隨機性和排列的主題有進一步的了解:


1374



好的,男孩和女孩。現在這已經足夠評論了。如果你想進一步討論這個問題,那就自己去聊聊吧吧,kthnxbye! - Ivo Flipse♦
@Eric但是在每次新牌組抽籤之前種子沒有重置,是嗎?所以,雖然你是對的,但只有相對較少的 軌跡 我們正在採樣,你不知道你現在的軌跡在哪里和軌跡相交。 - A.S.
實際上有人做過這樣的事情 - EJoshuaS
對Knuth的TAOCP第2卷,第3.5節“什麼是隨機序列?”(第149頁)中的相關問題的良好(但密集)處理,從闡明等分佈,k分佈和∞分佈序列的定義開始。偽隨機序列在3.5.F(p.170)中討論。另見偽隨機性標準 複雜性理論 和 德國BSI。 - ShreevatsaR


正如Eric Lippert所說,這不僅僅是分銷。還有其他方法可以衡量隨機性。

其中一個早期的隨機數發生器在最低有效位中有一個序列 - 它交替為0和1。因此LSB是100%可預測的。但你需要擔心的不僅僅是這個。每一位都必須是不可預測的。

這是思考問題的好方法。假設您正在生成64位隨機性。對於每個結果,取前32位(A)和後32位(B),並將索引轉換為數組x [A,B]。 現在執行一百萬次測試,對於每個結果,在該數字處遞增數組,即X [A,B] ++;

現在繪製一個二維圖,數字越大,該位置的像素越亮。

如果它是真正隨機的,顏色應該是均勻的灰色。但你可能會得到模式。以Windows NT系統的TCP序列號中的“隨機性”為例:

Windows NT 

甚至是Windows 98中的這個:

Windows 98 

這是Cisco路由器(IOS)實現的隨機性。 Cisco ISO

這些圖表是禮貌的 MichałZalewski的論文。在這種特殊情況下,如果可以預測系統的TCP序列號是什麼,則可以在與另一個系統建立連接時冒充該系統 - 這將允許劫持連接,攔截通信等。 即使我們無法100%預測下一個數字,如果我們可以創建一個新的連接 在我們的控制下,我們可以增加成功的機會。當計算機可以在幾秒鐘內產生100,000個連接時,攻擊成功的機率從天文到可能甚至可能。


156



這太棒了,它給我的眼睛帶來了淚水。應該有一個應用程序為每個操作系統(移動/桌面/服務器)和平台(JVM / Javascript /等)創建這些。 - HDave
Windows rand()函數非常好!它產生的雲沒有任何明顯的模式。看看我的實現嘗試它(和其他算法): github.com/Zalastax/visualize_random - Zalastax


雖然計算機生成的偽隨機數對於計算機用戶遇到的大多數用例是可接受的,但有些情況需要 全然 不可預測的隨機數。

在諸如加密的安全敏感應用中,偽隨機數發生器(PRNG)可以產生儘管在外觀上是隨機的,但實際上可由攻擊者預測的值。如果使用PRNG並且攻擊者俱有關於PRNG狀態的信息,則試圖破解加密系統的人可能能夠猜測加密密鑰。因此,對於這樣的應用,需要產生真正不可知的值的隨機數發生器。注意 一些PRNG旨在加密安全 並且可用於此類安全敏感應用程序。

有關RNG攻擊的更多信息,請參閱 這篇維基百科文章


92



密碼PRNG存在並被廣泛使用。它們可以從適度大小的種子生成實際上無限的隨機數流。將這樣的流與真隨機數區分開在計算上是不可行的,因此不能從這種流的任何部分獲得附加信息,並且對於任何實際目的,數字與真隨機數一樣好。 - aaaaaaaaaaaa
我認為最簡單的解釋方法是必須編程隨機數生成器算法。這意味著正在遵循一系列指令。如果有一組指令,則它不能隨機。 - Keltari
@Keltari你錯過了熵的元素......大多數RNG(至少是加密的)從外部來源收集輸入(例如鼠標移動)並將其用作起始條件的一部分 - 因此,從 A 至 B 是編程但初始狀態 A (應該)是不可饒恕的。 linux的 /dev/random 將保留熵可用量的近似值,並在數量過低時停止給出數字。 - Basic
出於好奇 - 為什麼熔岩燈被認為是“真正的隨機”?我知道它表現出相當不可預測的行為,但是對流體動力學有足夠的把握以及這些流體如何在地球引力環境中相互作用的人肯定會產生“可預測的”結果,不是嗎?當然,熔岩燈是不可預測的,但對我來說,它們根本不是隨機的,而是高度可預測的。 - theGreenCabbage
@theGreenCabbage:我懷疑熔岩燈是混亂的。如果計算機模型足夠好,並且準確度足夠高,您可以(原則上)預測行為一段時間。但是,由於系統混亂,兩個初始條件變化最小的熔岩燈的行為會迅速發生變化。 (這個評論忽略了混亂的吸引子。) - dmm


我在Python中嘗試過:這是6000萬卷的結果。最高的變化是0.15。這不是隨機的嗎?

實際上,它是 所以“好”這很糟糕...所有現有的答案都集中在 預測 給出一小部分初始值。我想提出另一個問題:

您的 分配 標準差比隨機輥小得多

真正的隨機性並不完全  接近平均“幾乎完全可以選擇多少數字”,你用它作為質量的指標。

如果你看看 這個Stack Exchange問題關於多個骰子卷的概率分佈,你會看到一個N骰子標準差的公式(假設真正隨機的結果):

 sqrt(N * 35.0 / 12.0).

使用那個公式, 標準差 對於:

  • 100萬卷是 1708
  • 6000萬卷是 13229

如果我們看看你的結果:

  • 100萬卷:stddev(1000066,999666,1001523,999452,999294,999999)是 804
  • 6000萬卷:stddev(9997653,9997789,9996853,10006533,10002774,9998398)是 3827

您不能指望有限樣本的標準偏差與公式完全匹配,但它應該非常接近。然而,在100萬卷上你不到一半適當的stddev,而在6000萬你不到三分之一 - 它變得更糟,這並非巧合......

偽RNG傾向於通過一系列不同的數字移動,從種子開始而不是在特定時期內重新訪問原始數字。例如,舊C庫的實現 rand() 函數通常具有2 ^ 32的周期,並且在重複種子之前它們將恰好訪問0到2 ^ 32-1之間的每個數字。所以,如果你模擬2 ^ 32骰子卷的預模(%)結果將包括從0到2 ^ 32的每個數字,每1-6個結果的計數將是715827883或715827882(2 ^ 32不是6的倍數),因此標準偏差僅小於0。上面的公式,2 ^ 32卷的正確標準偏差是111924.無論如何,隨著偽隨機捲數的增加,你收斂到0標準差。當卷數是這一時期的重要部分時,這個問題可能會很明顯,但是一些偽RNG可能會出現更嚴重的問題 - 即使樣本數量更少也會出現問題 - 比其他問題更嚴重。

因此,即使您不關心加密漏洞,在某些應用程序中,您可能會關心那些沒有過多,人為甚至結果的發行版。某些類型的模擬非常具體地試圖弄清楚結果 不均勻的 結果很自然地出現在單個隨機結果的大樣本中,但它們在一些pRNG的結果中代表性不足。如果你試圖模擬一個龐大的人口如何對某個事件作出反應,那麼這個問題就可以了 根本 改變你的結果導致非常不准確的結論。


舉一個具體的例子:假設一位數學家告訴撲克機程序員,經過6000萬次模擬滾動 - 用於在屏幕周圍閃爍數百個小“燈”,如果有10,013,229或更多六,數學家希望是1 stddev遠離平均值,應該有一個小的支付。按照 68-95-99.7規則(維基百科) 這應該發生 16% 時間(約68%落在標準差內/只有一半在外面)。使用隨機數生成器,這比平均值高出約3.5個標準偏差:Under 0.025% 機會 - 幾乎沒有客戶獲得這種好處。請參閱剛剛提到的頁面上的“更高偏差”表,具體如下:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

76



你在這裡比較蘋果和橘子。這兩個標準偏差完全沒有任何關係。 - Jbeuh


我剛寫了這個隨機數生成器來生成骰子卷

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

你這樣使用它

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

你是否樂意使用這個發生器來運行骰子遊戲的程序?請記住,它的分佈正是您對“真正隨機”發生器的期望!

偽隨機數生成器基本上做同樣的事情 - 它們生成具有正確分佈的可預測數字。它們之所以糟糕是因為上面簡單的隨機數生成器是壞的 - 它們不適合你需要真正不可預測性的情況,而不僅僅是正確的分佈。


50



“偽隨機數生成器......生成具有正確分佈的可預測數字” - 僅僅因為它是PRNG並不能保證它具有完美的分佈(事實上,商業上的那些基本上沒有,完全是這些答案中概述的原因)。雖然給定足夠的信息(使用算法,開始種子,輸出值,w / e)它們可能是可預測的,但它們仍然存在差異。 - Brian S
除了這一點,我知道,但是 get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on 太優雅了,別說:) - Janus Troelsen
@BrianS實際上,隨著時間的推移,分佈測試失敗的PRNG可以根據定義進行預測。因此,對於一些大N來說,如果你從N / 2頭的N幣翻轉得到一點點,你可以開始投注頭,你可以贏得比你輸的更多。同樣地,如果你有一個完美的頭部和尾部分佈,但是頭部總是成對出現,那麼你將再次獲得勝利的秘訣。分佈測試是你如何知道PRNG是有益的。 - Jon Kiparsky
你忘了 nonlocal next :-)。 - Kos
更好的例子:Pi被認為是 正常,意味著任何基數中任何給定長度的任何數字序列的出現頻率不會超過該基數中該長度的任何其他序列。一種算法,當被要求時 ñ 隨機位,接下來 ñ pi的位並返回它們(“種子”是你開始的位),從長遠來看應該產生完美均勻的分佈。但是你仍然不希望它用於你的生成器 - 知道你生成的最後一串比特的人可以在第一次發現序列時發現,假設你的種子在那裡,並且可能是正確的。 - cpast


計算機可以執行的隨機數生成適合大多數需求,並且您不太可能遇到需要真正隨機數的時間。

真正的隨機數生成有其目的。在計算機安全,賭博,大型統計抽樣等

如果您對隨機數的應用感興趣,請查看 維基百科文章


26



最大的問題是,當您需要攻擊者出於安全原因無法預測的隨機數時。 - David Schwartz
你肯定可能會遇到一個需要真正隨機數的時間。它足以打開一個以...開頭的網頁 https://... - Jan Hudec
@JanHudec:嗯,在日常使用中,在打開任何程序之前,在輸入地址欄之前,你需要安全的隨機數: 地址空間佈局隨機化。這就是為什麼 像這樣的東西 發生。 - Reid
@JanHudec我特意說你需要使用在線隨機數生成器。真正的隨機數經常被使用,但實際上很少有人需要自己生成它們。 - Alex McKenzie
老虎機也使用PRNG,而不是TRNG。生成器一直運行,並且在按下旋轉按鈕的確切時間選擇一個數字。 PRNG和真正隨機按鈕按下時間的總和相當於TRNG。 - Roger Dahl


大多數編程語言中典型函數生成的隨機數不是純隨機數。它們是偽隨機數。由於它們不是純粹的隨機數,因此可以猜測有關先前生成的數字的足夠信息。所以這將是一個 密碼學中的安全性災難

例如,下面使用的隨機數生成器函數 glibc 不產生純粹的隨機數。由此產生的偽隨機數可以猜到。這是一個安全問題的錯誤。這是一個災難性的歷史。這不應該用於加密。

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

永遠不應該在安全敏感的地方使用這種類型的偽隨機數生成器,即使在統計上非常重要。

偽隨機密鑰的一個著名攻擊是攻擊 802.11b WEP。 WEP具有104位長期密鑰,與24位IV(計數器)連接以生成128位密鑰,然後將其應用於 RC4算法 生成偽隨機密鑰。

( RC4( IV + Key ) ) XOR (message)

鑰匙彼此密切相關。在這裡,每一步只有IV增加1而其他所有步驟保持不變。由於這不是純粹隨機的,因此它是災難性的並且容易被分解。通過分析大約40000幀可以恢復密鑰,這是幾分鐘的問題。如果WEP使用純隨機的24位IV,那麼它可以是安全的,直到大約2 ^ 24(接近1680萬)幀。

因此,在可能的情況下,應該在安全敏感問題中使用純隨機數生成器。


26



我會使用弱密碼將WEP的東西歸咎於設計糟糕的協議。使用現代流密碼,您可以使用計數器作為IV。 - CodesInChaos
WEP的主要問題是在2 ^ 24(近1600萬)幀中重複密鑰。更糟糕的是,使用相關鍵可以在大約40000幀中破解代碼。這裡的要點是密鑰不是隨機的。它密切相關,因此容易破解。 - Prabhu
密碼學中的偽隨機性很差 僅在生成加密密鑰時。除此之外完全沒問題。實際上,RC4只不過是一個偽隨機數發生器,其接種的是將密鑰的128位擴展XOR到消息的明文上。 - Matt