Re: [請益] 亂數表有沒有規律??

看板ask-why (知識奧秘)作者StaticVortex時間17年前 (2009/05/20 23:52)推噓2(2推 0噓 7→)

留言9則, 2人參與討論串18/19 (看更多)

感謝回應, 提供幾點迴響, 也許有誤或不足, 希望不吝指教. 關於以使用者擊鍵時間間隔為亂數種子, 可能會由於作業系統對鍵盤緩存的設計, 使得當程式要求讀值時, 在緩存中的幾筆資料在很短的時間內送往程式, 也就失去了原來自然亂數的性質. https://www.random.org/randomness/ For example, it can be tricky to use keystrokes in this fashion, because keystrokes are often buffered by the computer's operating system, meaning that several keystrokes are collected before they are sent to the program waiting for them. To a program waiting for the keystrokes, it will seem as though the keys were pressed almost simultaneously, and there may not be a lot of randomness there after all. http://msdn.microsoft.com/en-us/library/aa459265.aspx Keystrokes occur asynchronously with user action while the I/O Manager sends the driver an IRP for the read request. The driver gives the appearance of simultaneously receiving input from the device and passing the keystroke data to I/O Manager by maintaining a buffer of keystrokes. 在應用自然亂數於資訊安全時, 如果重複使用虛擬亂數產生器作為新種子, 通常會使產生的亂數品質變差, http://www.lavarnd.org/faq/prng.html To achieve output unpredictability of high quality PRNG, one must start with an unpredictable seed. Using second PRNG to create the seed does not help because that simply transfers the problem of seeding onto the second PRNG. Worse yet, using a PRNG to repeatedly seed another (or even worse the same) PRNG usually degrades the quality of the output. 但在這篇專利 http://www.google.com/patents?id=ou0gAAAAEBAJ ( www.lavarnd.org 前身 lavarand 使用的技術參見 http://www.wired.com/wired/archive/11.08/random.html Lavarand, a patented system that used Lava Lites to help generate random numbers. (Patent 5,732,138: "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system.") ) 它將經由渾沌系統產生的自然亂數先雜湊過後再作為種子, " the present invention pertains to an apparatus and method for producing a seed for a pseudo-random number generator from hashing the digitization of a chaotic source. 其理由這麼說 " The cryptographic hashing function serves several purposes. The cryptographic hash make it difficult to predict the chaotic system. Furthermore, small variations in the digitized chaotic system will produce extremely different binary strings. In addition, knowledge about the cryptographic hash yields no information regarding the chaotic system. 其舉了 state of clouds 作為例子說明 locality inherent 使渾沌系統在某些程度上可以被預測, 而使用 hash function 轉換後可以消抹 locality inherent 性質. ( given hash(x) , it is hard to find hash(x+1) ) 不過經過一次雜湊, 為什麼不會像前面引文所指,反而使亂數品質變差呢? 如果跳過雜湊, 直接將自然亂數作為亂數種子丟到虛擬亂數產生器所產生的金鑰, 沒辦法有效消抹 locality inherent 性質嗎? ※ 引述《H45 (!H45)》之銘言： : 此問題應回歸於：為何需要亂數？ : 因實際需求，有些亂數要求無法預測以提升系統安全 : 有些亂數要求分佈足夠均勻以提升搜尋效果 : 而有些亂數要求模擬真實環境以測試系統容錯能力 : 基於以上需求，有些情況並非虛擬亂數可以滿足 : 無法預測的特性乃自然亂數優於虛擬亂數的原因之一 : 在一般的情況下 : 虛擬亂數 (如 Java 內建 Random 類別所含演算法) 已經足以應付大部分的需求 : 好比說：隨機從題庫抓練習題、隨機閱讀網路的一篇文章 : 並不需要多麼難以預測的亂數源，只要虛擬亂數即可。 : 然而，需要絕對無法被猜到的情況下，自然亂數比虛擬亂數更加可靠 : 好比說：隨機產生加密金鑰、隨機產生雜訊 : 自然亂數保證任何人都無法準確地猜到未來的亂數是多少 : 畢竟人類還沒有能力預言這個世界的所有細節。 : 回到原發問者的問題：以使用者的 input 時間間隔來取種子的方式會遇到什麼限制？ : 假設使用者 input 時間間隔足夠稱為自然亂數 (不是由機器精準地以固定時間輸入) : 那麼，此種子即為自然亂數，後面的種種運算都是基於自然亂數的結果 : 此時間間隔不能說是偽亂數。 : 然而，如果將自然亂數再做一次虛擬亂數演算法所得到的數值，並不能稱之為自然亂數 : 因為每一次運算所得到數值都與自然亂數相關 : 連續做多次虛擬亂數演算法所得到一連串數字彼此之間有關聯 : 這些數字只能代表同一個自然亂數的衍生物 : 只要知道第一個數字是多少，後面的數字全部都可以推算出來 : 相對地，一連串真正的自然亂數是知道第一個數字，仍然無法推算出其他亂數是多少。 : 舉例而言，你有辦法知道另一個使用者 (人) input 的時間間隔嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.42.20.13