Random-Number-Generator

擲骰子作為熵源?

  • December 16, 2016

我想用骰子生成一個 128 位隨機數,但我聽說骰子非常有偏見,尤其是低質量(非賭場骰子)。

  1. 生成更高的位數是否有意義,例如 1000 位數?這會“吸收”骰子中表現出的缺陷和偏見嗎?在整體偏差減少的意義上,你添加的比特數越多?
  2. 消除偏見的最佳方法是什麼?
  • 將單個數字連接成 128 位字元串
  • 將拋出的單個數字相乘
  • 兩者的組合,例如 2 個骰子:(R1+R2)x(R3+R4)x(R5+R6)…

……

消除偏見的最佳方法是什麼?

無論我們談論的是來自製造缺陷的偏差,還是我們從賭場質量骰子中知道的偏差,您都可以使用馮諾依曼偏斜校正算法從偏斜的輸入中生成均勻隨機的數據。

馮諾依曼偏斜校正算法發表在“與隨機數字相關的各種技術”中。(NIST 期刊,應用數學系列,12:36-38,1951)。由於該論文的年代和出版日期難以在網上找到,我已將副本放入我的 Google Drive 帳戶(PDF) 以供參考。

Von Neumann 的偏斜校正背後的總體思想是考慮擲骰/擲硬幣/其他任何序列,而不是孤立序列,同時選擇一個足夠長的序列長度,以使偶數個可能的結果具有相等的機率。

解釋馮諾依曼偏斜校正算法:

對於骰子,選擇一個序列長度,其中 $ n>2 $ . 選擇序列長度的原因 $ n>2 $ 是沒有相同機率的可能結果的子集 $ n=1 $ 或者 $ n=2 $ 有一個基數可以被 $ 6 $ .

所以,對於這個例子,讓我們簡單地採取 $ n=3 $ . 這樣做,任何骰子的結果都可以根據擲出的連續數字的相對順序劃分為 6 個等機率類別——前提是這些數字都是不同的。

我們需要這個,以便可以根據第二個數字是否大於1或小於0第一個,以及第三個數字是大於111,011還是小於100,000第一個和第二個,或者介於兩者之間,對序列進行分組110,001

所有 6 種可能的排序將以相等的機率發生,因為屬於這些排序中的任何一個的序列中的每一個都與每隔一個排序中的一個等機率序列完全匹配。含義:1,2,4,1,2,4匹配 ordering 111,而2,1,4,2,1,4(同樣可能被滾動)匹配011

編輯

@fgrieu在下面的評論中描述了一個不同但同樣實用的實現。

是的,die 可能會有明顯的偏差,但如果來自不同製造商的 die 的輸出差到足以導致任何實際攻擊,即使是要求與一次性焊盤一樣嚴格的東西(除非骰子被故意破壞)。

就個人而言,如果您不允許使用電腦,我會執行以下操作:從不同製造商處獲取 d6 骰子(至少 2 個骰子,尋找沒有圓邊的骰子),建構一個 6x6 表(範例如下,但可能有很多變體)並從 2 個骰子的交集中選擇您的角色。如果你想確定一個字母是大寫還是小寫,你可以做拋硬幣之類的事情。

繼續通過此方法建構您的密鑰,直到您獲得所需的輸出量。

\|1|2|3|4|5|6|
1|a|b|c|d|e|f|
2|g|h|i|j|k|l|
3|m|n|o|p|q|r|
4|s|t|u|v|w|x|
5 | y | z | 0 | 1 | 2 | 3 |
6|4|5|6|7|8|9|

更新:我剛剛注意到你說你只需要生成數字。這是一張不同的表(但 16.67% 的捲將無效):

\|1|2|3|4|5|6
1|0|1|2|3|4|5
2|6|7|8|9|0|1
3|2|3|4|5|6|7
4|8|9|0|1|2|3
5|4|5|6|7|8|9
6|R|E|R|O|L|L

6x6 桌,只有 2 次擲骰子的機率為 86.11%(無效擲骰的機率為 2.77%)和 2 次擲骰子 + 1 次擲硬幣的機率為 13.89%:

\|1 |2 |3 |4 |5 |6
1|0 |1 |2 |3 |4 |5
2|6 |7 |8 |9 |0 |1
3|2 |3 |4 |5 |6 |7
4|8 |9 |0 |1 |2 |3
5|4 |5 |6 |7 |8 |9
6|0/1|2/3|4/5|6/7|8/9 |重新滾動

引用自:https://crypto.stackexchange.com/questions/42147