如何區分偽隨機和真隨機？

01-20

本科期間做的一個關於保密通信編碼的項目，為了保證絕對的安全性，需要用到真隨機數序列。於是我用VHDL語言，在FPGA上實現過一個真隨機數發生器。

它的結構並不複雜，大概分為3部分。

1.振蕩電路

它大概是這樣的，將一組反相器（非門）頭尾相連。這個時候電路不再是普遍的邏輯電路，而是因為硬體電路的延遲，所以具有混沌性。

2.採樣處理

故而我採樣的時候，採樣結果具有隨機性。為了增加隨機性，我構建了8組振蕩電路，將8組採樣結構用異或門（XOR）處理。

如果有奇數組的採樣結果是1，則採樣輸出為1.

如果有偶數組的採樣結果是1，則採樣輸出為0.

因為這8組振蕩電路之間，彼此可以認為是獨立互不影響的，所以理論上組數越多，隨機性越好。

3.後處理

理想情況下，採樣結果具有統計上的隨機性。但由於FPGA硬體電路不可避免的揮手到溫度漂移，電壓抖動等不良因素影響，從而導致採樣得到的隨機信號中存在偏置，影響結果的統計特性。所以在採樣得到隨機序列後要對數據進行消偏處理，使0和1出現的概率相當。

所以採用16位最大長度二進位偽隨機序列的輸出與採樣得到的隨機序列進行異或運算作為後續處理。因為處理器是FPGA，所以可以使用線性反饋移位寄存器實現二進位偽隨機。

檢驗方式：整個TRNG的實驗環境由外部時鐘源、FPGA開發板以及邏輯分析儀組成。TRNG採用Xilinx公司的Virtex-5系列中的XC5VLX110作為物理實現平台，外部時鐘頻率為64 MHz。由FPGA產生的隨機數據，經邏輯分析儀採集後，使用DIEHARD battery of tests of randomness隨機數測試程序進行測試，檢驗隨機序列的性能。

DIEHARD測試是由16項測試組成的用來度量隨機數發生器性能的一組統計學測試，它由George Marsaglia開發並於1995年首次發布。DIE HARD的測試結果叫做P-value，它由方程P-value=Fi(X)計算得到，其中Fi試圖建立樣本X在0和1間服從均勻分布的分布函數。因為Fi是漸進逼近的，它在尾部的近似效果變差，所以數值接近0或1的P-value在真隨機序列中極少出現。當被測序列隨機性能很差時，會有很多P-value的值是精確到小數點後數位的0或者1，例如1．000 000。

需要強調的是，P-value等於1．000 000或0．000000是序列為真隨機序列的充分不必要條件。

計算機是怎麼理解隨機的? - 知乎用戶的回答

另外，很多回答都出現了一個常見的誤區：把周期性和隨機性混淆了。

事實上，周期性和隨機性是有區別的。

例如說我構造這麼一個序列：101001000100001...（就是相鄰的兩個1之間，0的個數依次遞增）。

這個序列顯然的周期性是正無窮（或者說沒有周期性），但是你能說它是隨機的？只要在序列中連續拿到三五個1，小學生都能把這規律給猜出來。。。

還有：

從純邏輯來說，給你一串有限長度的數字序列，無論它有多長或者多短，其實你都是不可能證明它是真隨機序列的一個子序列。

道理其實不難：假定你的數字序列為N位，那你是無法保證它是不是一個周期為大於等於N的周期重複序列的一個子序列。

所以，我個人認為：

如果給你一串數字序列，如果你能從中找到它的周期性，那麼它一定是偽隨機。但是，如果你找不到，那麼你只能說：「它可能是真隨機」。這個序列越長，它是真隨機的可能性就越高。我猜 @金山答案中提到的「隨機數測試包」，用的就是這個原理。

但是你永遠不可能有一個方法100%肯定它是一個真隨機序列。

當然，如果你能拿到那個隨機數發生器，你倒是可以看看它的原理是不是基於某些物理上的隨機過程來判斷。

物理上已知的隨機過程追根溯底都是各種量子效應。在宏觀上，例如說：熱運動（各種雜訊、布朗運動）、同位素衰變、勢壘穿透等。

看實現。

隨機數生成器是沒法黑盒測試的，你永遠沒法得知代碼里是不是寫著「在2020年1月30日零點生成1024」這種條件，即便其他情況下它都是真隨機。

可以檢出輸出是否有周期性。一般線性同餘生成器（Linear congruential generator）（一種偽隨機數生成器）的周期可能是2^32。但著名的梅森旋轉生成器（Mersenne Twister）的常用版本，其周期是 2^19937 - 1，就很難用黑盒方法檢測它的周期性。

如果亂數產生器中包含有一種(無周期性並攻擊者無法獲得)的信源或作為熵池，則可稱為真隨機。

1.比較常見的是光噪聲和熱噪聲的採集卡。

在os 層面中的熵池也可以採集wifi 信號，變壓器電壓等組成

2.真亂機產生器必然為堵塞。非堵塞的產生器如/dev/urandom 則不可避免有熵減少的情況出現

3.在偽亂數產生器可能受限於硬體系統的記憶體長度，在單次採集下，32bit 系統有2^32 位之一的必然重覆度。可以透過交換處理次序來提高但不是無限。

理想的隨機性必定等效於白雜訊（從信源、熵的角度理解）。

白雜訊有什麼特性？

1、自相關函數為 $delta (t)$

2、頻譜衡為常數

簡單的說，用譜分析之類的方法檢測偽隨機數，便能看出其不符合上述特徵。

--------------------------

然而，白雜訊物理上是不存在的，這就是個為了便於數學分析而構造出來的理想模型。因為白雜訊的能量是無窮大的（根據特性2和Parseval定理去理解）。真正的隨機性自然界是否存在？我很好奇。因為量子力學我不懂。

-----------------------

還是回歸日常吧。你能接觸到的序列全是偽隨機，不用驗證。至於要說事物發展因果循環是真隨機的話……還請去問大師。

但偽隨機很有用，人們想盡方法弄出了一些偽隨機數產生器。比如 @Milo Yip 提到的線性同餘生成器（LCG）、梅森旋轉生成器等。我再說一種佔用資源和隨機性效果介於上述二者之間的、大名鼎鼎的： 線性反饋移位寄存器（ linear feedback shift register ）。（學EE的同學有木有感覺很熟悉）

如果你知道了待測試系統的機理，那麼就可以針對其弱點加以攻破，例如對於LFSR，其不僅是周期的，而且對於相同的初始狀態，其後的輸出是確定的。（所以用matlab模擬的時候想要每次都跑出同樣的結果，就把隨機數種子固定一下下~）

信息安全領域大量用到隨機數，以上的方法安全性都挺弱的。所以針對安全性較高的系統，有更高級的偽隨機數產生器。有興趣可以看看 RFC 4086 - Randomness Requirements for Security 中的討論，有對LCG等偽隨機數產生器的破解方法（不僅能檢測出這是偽隨機數，而且能預測下一個數是什麼），也有一些安全性高但計算複雜的偽隨機數生成方法（比如Blum Blum Shub Sequence Generator？）。

謝邀

除了量子力學外，世界上沒有真隨機

如果你的偽隨機產生的質量很差，比如 10101010101010... 那當然很好區分。但如果使用偽隨機發生器就不一樣了。

按照定義，偽隨機發生器（Pseudorandom generator）生成的隨機序列和真正的隨機不可區分。偽隨機發生器是一個確定性的演算法，本身不含任何隨機性，需要提供一個種子，根據種子生成一段看起來很隨機的序列。如果種子等概率隨機選取，那生成的序列和真正的隨機序列無法區分。

前面的區分都是指在多項式時間內區分。如果運行指數時間當然能區分。

如果是指計算機隨機數生成，那麼有答主提到的通過引入某些物理雜訊的方法確實能夠實現無周期性的隨機，這是演算法無法做到的。最好的雜訊源就是CMB（宇宙微波背景輻射），當然，你追蹤某個顆粒的布朗運動效果也是極好的。

如果你是指隨機過程～尤其是物理學甚至是哲學意義上的，那麼很抱歉～沒人知道。

雖然世界上還有很多奧秘不為人所理解，然而，我們的科學，尤其是研究世界運行方式的物理學，是建立在這個世界遵守一套運行法則的假設的基礎上的，而且已經發現的這些物理法則，似乎都在加強這種信念～在這種假設成立的基礎上，真隨機是不存在的，我們看到的所有混亂無序的現象，要麼是出於我們對運行規律掌握的不完善，要麼僅僅是出於複雜程度超出了我們計算能力之外，但是，無論如何，仍然無法排除這樣一種可能～宇宙壓根就沒有運行法則，它是純粹的真隨機的，只不過由於大數原理，碰巧出現了一段看起來很有運行規律的時期，而我們就生活在這段時期中，當這段時期結束，宇宙會回到徹底混亂無序的狀態中，直到下一段看起來有規律的時期出現，如此循環。在這種圖景中，所有的科學實際上是沒有意義的，有的只是在規律時期的應用價值，超出這個時期後就沒有任何用處了～

民科腦洞勿輕信～只為博君一思～以上。

計算一個字元串的柯氏複雜度是不可計算的。所以也沒有演算法可以區分真隨機和偽隨機。

普通電子計算機用演算法生成的幾乎都是偽隨機，只能想辦法獲得看上去「更加隨機」的結果

真隨機不知道，但關於偽隨機：

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.
- John von Neumann

你坐在拉斯維加斯的賭場裡面，嘴角微微一笑覺得自己馬上就要變成百萬富翁，因為你有時光倒退1分鐘的能力。你先押了一點籌碼買小，半分鐘之後點數是大，然後你發動自己的時光倒退能力回到之前重新用所有籌碼買了大，你心跳加速，因為你知道自己即將大賺一筆。

結果重新出來了，你瞬間變成了窮人....因為結果變成了小

宏觀世界不存在真隨機

特別是圖靈機，圖靈機演算法特性之一是對於同一輸入只會產生同一輸出，大家能看到的隨機只是輸入跟使用程序時的時間等有關

真正的隨機存在於量子力學中

另外補充下密碼學中有對隨機性的講述，其中很重要的一點是統計上獨立

首先說明，這裡的偽隨機指的是，人為的去影響概率，而不是生成隨機的方式。

算概率的概率。

例如說，概率是0.5。

有1000個數據，不管真偽，基本都是在500左右為真。

但是如果我們每10個點算一次，

發生5次為真的概率應該只有0.246左右

而小於兩次為真的概率還有0.0547，

有隻有一次為真的概率為10/1024。

所以如果一個1000個數的數組，每連續10次計算一次，共計算991次。

其中少於等於一次為真的

沒有發生的概率為

（1013/1024）^991約為0.0000225

只發生一次的概率為

（1013/1024）^990*（11/1024）*991約為0.000242

根據 komolgrov 複雜性定理，判斷一個任意string是否是隨機的是不可計算的。

一切都是偽隨機。

不關心對隨機性要求，而只是在乎真偽隨機真的是意義不大。

又真有幾個應用真正需要用到真隨機？很多時候一個好的偽隨機加上一個真隨機的seee就ok了，畢竟真隨機往往成本太大，划不來。

計算機算出來的都是偽隨機，真隨機可以通過觀測物理過程得到，比如測放射源

我一直認為宇宙是純粹機械運行的，所以不存在真隨機