你以為的隨機數(shù)是不是都是那種很高級的？

比如前兩天，區(qū)塊鏈平臺Solana出現(xiàn)了長達4個小時的宕機事件。

根據(jù)聯(lián)合創(chuàng)始人Anatoly Yakovenko和其他開發(fā)人員表示，該問題是由于區(qū)塊鏈的持久隨機數(shù)功能存在錯誤導致的。Yakovenko表示，該問題“導致部分網(wǎng)絡認為該區(qū)塊無效”，因此“無法形成共識”。

再比如，在2015年與2017年，工行聯(lián)合中國科技大學實現(xiàn)基于量子通信技術(shù)的同城和異地數(shù)據(jù)加密傳輸，在電子檔案、網(wǎng)上銀行等領(lǐng)域落地試點。去年，工行在****業(yè)中率先完成了量子隨機數(shù)的場景試點。

工行金融科技部總經(jīng)理表示：“量子隨機數(shù)被認為是安全性最高的隨機數(shù)，我們利用其隨機性、不可推測和不可重復的特點，運用量子隨機數(shù)加密、標記、校驗重要金融交易信息，以更有效地防范用戶身份假冒、交易數(shù)據(jù)截獲重放等攻擊，更好地確保用戶意愿的真實性、交易要素的完整性和交易過程的安全性?！?/span>

但是你可能想都想不到，要生成隨機數(shù)，其實只要一根香蕉就夠了。這個別出心裁的腦洞得到一位即將電子學碩士畢業(yè)的博主Valerio Nappi實踐支持。

這個香蕉隨機數(shù)生成器原理是啥？真的靠譜嗎？快和文摘菌一起來看看~

讓我們從問題的根源開始說起。

計算機是確定性的系統(tǒng)。換句話說，如果我們總是給它們相同的輸入數(shù)據(jù)，它們也總是會返回相同的輸出值。這正是我們對計算機的期望。然而，確定性和隨機性并不是一種兼容的關(guān)系，而計算機本身無法做任何隨機的事情。

為了更好地理解隨機數(shù)，我們必須要理解一組數(shù)字成為隨機數(shù)的兩個必要不充分條件：

• 每個數(shù)字出現(xiàn)在列表中的概率必須與其他每個數(shù)字相同（取一個參考區(qū)間），也即均勻分布。

• 數(shù)字的序列必須是事先無法預測的。

顯然，確定型機器的困難在于回答第2點。在只滿足第1點的情況下，很有可能生成的是偽隨機數(shù)，并非真正的隨機。

但是，這和香蕉有什么關(guān)系？

當我們?yōu)橛嬎銠C提供隨機數(shù)時，硬件系統(tǒng)是必不可少的，這就是隨機數(shù)生成器（TRNG）。

TRNG有許多類型，不過他們原理都是類似的，即利用不同的物理隨機量并將其轉(zhuǎn)換為數(shù)字信息傳遞給計算機。最常見的是利用物理現(xiàn)象，如電阻的熱噪聲、二極管的雪崩效應和其他混亂效應。

使用香蕉的話，應該還是放射性衰變。我們知道，香蕉內(nèi)含有大量的鉀，而自然界中存在的鉀有一小部分是放射性的，但比例很高。具體來說，這里說的是40K同位素，它占自然界中鉀的0.01%。（以及很搭配與檸檬和糖一起吃）

這么來看的話，“以香蕉為動力的隨機數(shù)生成器”瞬間變得合理了不少。

但有一個問題仍然存在：我們在計算機中對隨機數(shù)做什么？

——加密。這也是研究隨機數(shù)及其與計算機關(guān)系的主要原因。隨機數(shù)被用來生成加密密鑰，這是決定加密系統(tǒng)有效性的唯一因素。正如Kerckhoffs原理所言，“一個密碼系統(tǒng)的安全性不應取決于保持密碼算法的隱蔽性，而只應取決于保持密鑰的隱蔽性”。

很明顯，如果攻擊者能夠以某種方式預測密鑰，我們便會處在一個脆弱的系統(tǒng)中。因此，“好的隨機數(shù)”是一個好的加密系統(tǒng)的基礎(chǔ)。

要用什么來檢測“香蕉”

為了分析隨機數(shù)生成器的質(zhì)量，我們還需要專門設計的軟件工具。目前最流行的兩個是ent和dieharder。ent是作為放射性衰變隨機數(shù)生成器的輕量級測試而設計的，它非常簡單和快速，需要的數(shù)據(jù)很少，但結(jié)果只是指示性的。Dieharder是一個被認為是隨機數(shù)生成器的黃金標準的測試套件，它進行非常徹底的測試，但需要數(shù)千兆字節(jié)的樣本來運行。

在這里我們當然選擇ent。

準備一下數(shù)據(jù)，我們用ent進行第一次測試。數(shù)據(jù)是由發(fā)生器寫入串口的，我們用cat /dev/ttyACM0 >> sampletext.txt從linux控制臺將它們保存在一個文件中，在append模式下利用bash流重定向命令，這樣我們就可以停止采集，以后再繼續(xù)采集，而不會覆蓋文件。

兩天內(nèi)收集的樣本包括90628個16位數(shù)字，每行一個。這些數(shù)字被保存為ascii文本文件，但ent分析的是二進制文件，可以用C語言寫一個很短的程序把它們轉(zhuǎn)換成二進制。

#include <stdio.h>#include <assert.h>#include <stdlib.h>#include <stdint.h> int main(int argc, char const *argv[]) {   FILE * lettura = fopen("textsample.txt", "r");  assert(lettura != NULL);   FILE * scrittura = fopen("sample.txt", "wb");  assert(scrittura != NULL);   uint16_t N = 0; //N is 16 bytes  char bytes[2];  char buffer[6]; // 5 char + terminator   do{    fscanf(lettura,"%s",buffer); // put one line in the buffer    N = atoi(buffer); // from char array to integer    bytes[0] = (N >> 8); // take the 8 msb    bytes[1] = (N & 0xFF); // take the 8 lsb    fwrite(bytes, 1, sizeof(bytes), scrittura); // output raw msb and lsb  }while (!feof(lettura));   fclose(lettura);  fclose(scrittura);  return 0;}

做完這些，我們就可以第一次運行ent測試了。

Ent給出了幾個參數(shù)：

• 熵：熵是一部分信息中包含的“隨機性”的數(shù)量。信息理論告訴我們，理論上可以通過壓縮而不損失信息的最小尺寸，由熵值表示。

• 卡方分布：這個測試是用來了解我們的數(shù)值分布對理論分布的遵守程度。從ent手冊來看，這個值應該盡可能地接近256，百分比值在10-90%之間。

• 算術(shù)平均值：比特的簡單算術(shù)平均值。由于數(shù)值在0到255之間，所以它應該大約等于127。

• 用蒙特卡洛方法計算π的值：在這里更多的是一個漂亮的數(shù)據(jù)，而不是一個有用的方法。

• 自相關(guān)：表示系列值之間的依賴性，在最佳情況下必須等于零。

香蕉與卡方的關(guān)系

卡方是統(tǒng)計學中的一個概念，主要用于測試一組數(shù)值與理論上預測的分布的擬合程度。

如果給定了一個數(shù)據(jù)集，頻率為一個給定的數(shù)據(jù)項出現(xiàn)的次數(shù)，自由度為可能值的數(shù)量減去1。為什么要減1？假設拋硬幣的情況，我們有兩種可能的結(jié)果：正面和反面。但出現(xiàn)正面的百分比直接由它出現(xiàn)反面的百分比決定。那如果我們考慮一個有三種可能結(jié)果的事件，第三種結(jié)果的百分比直接由其他兩種決定。

讓我們再搖骰子為例。擲骰子有6個可能的結(jié)果，這給了我們五個自由度。那投擲1000次骰子，我們要驗證統(tǒng)計學中所謂的零假設，或者驗證在一定的概率范圍內(nèi)，我們的結(jié)果是真正隨機的。

這些是從實驗中得到的數(shù)據(jù)：

于是我們得到了實驗的卡方值，3068。

現(xiàn)實情況下的數(shù)據(jù)完全反映理論分布是極不可能的，一個太接近于零的卡方值也是值得懷疑的。另一方面，我們離理論分布越遠，分子就越大，而分母不變。這導致了卡方值的增長。這對卡方值而言，意味著能夠拒絕無效假設，從而知道你所處理的數(shù)據(jù)不僅僅是偶然的結(jié)果，而是有一定的意義。

但然而，對于我們來說，這是一則壞消息，因為這意味著我們的數(shù)據(jù)不是均勻分布的。

表中的行代表系統(tǒng)的自由度，在模具案例中，有5個自由度。列代表計算值大于表格中的值的概率水平。也有一些表格表示計算值小于的概率，這些表格被稱為左尾表，上面顯示的表格是右尾表。這是因為在一種情況下考慮的是圖形的右邊，而在另一種情況下考慮的是左邊。案例中chi^2=3.068，這介于90%和25%的情況之間。這足以說明，從我們可以歸類為隨機的行為來看，沒有過度的變化。

讓我們回到香蕉上，把90%和10%作為參考百分比，對于255個自由度，從ent對生成器記錄的數(shù)值的測試中，能得到498.15的值，超出了可接受的范圍，ent返回的概率百分比為<0.01%。

關(guān)于香蕉的猜測

但可能有人馬上注意到，字節(jié)1的計數(shù)明顯少于其他的，字節(jié)2的計數(shù)則多得多。仔細一看，那些“缺少”的計數(shù)被分配給了2。

經(jīng)過一些測試，我決定將偶數(shù)位置的字節(jié)與奇數(shù)位置的字節(jié)分開。這是因為每生成一個16位數(shù)字（2個字節(jié)），就會產(chǎn)生兩個字節(jié)，一個是偶數(shù)位置，一個是奇數(shù)位置。

MSB沒有報告任何重大問題，但LSB組是問題所在。為了了解問題來源，我們必須首先了解數(shù)字是如何在內(nèi)部產(chǎn)生的。

蓋革管通過一個接口電路，當它被輻射擊中時，在單片機的引腳2（PB2/INT0）上發(fā)送一個信號，引腳2被配置為在收到上升沿時產(chǎn)生一個中斷：attachInterrupt(digitalPinToInterrupt(2), randomCore, RISING);。中斷將調(diào)用randomCore()函數(shù)，其定義如下：

該函數(shù)被調(diào)用時，反過來調(diào)用單片機的micros()函數(shù)。這個函數(shù)返回一個32位的數(shù)字，代表自系統(tǒng)開啟以來已經(jīng)過去的微秒數(shù)。作為一個32位無符號數(shù)，它將在4294.96秒后溢出，或每70分鐘左右溢出一次。由于微控制器的速度不足以獲得更準確的更新，micros()以4微秒為單位進行更新，始終保持兩個最小有效位為零。

出于這個原因，我們將micros()返回的值向右移動了兩個比特。這樣我們就得到了一個30比特的值。如果我們也使用最小有效位，我們將得到漸進的數(shù)字，直到下一次定時器溢出。在溢出發(fā)生的70分鐘內(nèi)，每個數(shù)字肯定會比前一個大，也肯定會比后一個小。這絕對不是隨機的。

因此，讓我們只保留micros()的前16字節(jié)。這個值每隔262144微秒就會有一次溢出，使得上述情況發(fā)生的可能性極小。

注意到，這個值每4*2^8=1024微秒出現(xiàn)一次，或者說大約1毫秒，是產(chǎn)生中斷溢出后的下一個值。然后我們把注意力放到單片機核心的millis()函數(shù)的代碼上來。

millis()函數(shù)通過將TIMER0的預分頻器設置為64來工作，對于一個時鐘為16MHz的8位定時器來說，這導致每1.024毫秒就有一次定時器溢出。定時器溢出會產(chǎn)生一個中斷，向量為TIMER0_OVF。如果蓋革管脈沖與TIMER0溢出同時到達，我們將有兩個相互競爭的中斷：TIMER0_OVF和INT0。這種情況由微控制器的中斷優(yōu)先級系統(tǒng)來處理，其優(yōu)先級順序在數(shù)據(jù)手冊中標明。

TIMER0溢出的優(yōu)先級比外部中斷低得多，所以就有了以下猜測：

情況1：INT0中斷與TIMER0_OVF中斷同時到達。由于它有更高的優(yōu)先級，外部中斷首先被執(zhí)行，犧牲了millis()，影響了函數(shù)的準確性，但對生成的數(shù)字沒有產(chǎn)生明顯的影響。

情況2：INT0中斷比TIMER0_OVF中斷在下一個時鐘周期到達。由于已經(jīng)過了一個時鐘周期，TIMER0_OVF中斷已經(jīng)在執(zhí)行了。當執(zhí)行結(jié)束時，micros()已經(jīng)是2的值了，所以生成的數(shù)字將被注冊為2的值。

但也有可能使用串行對延遲產(chǎn)生了影響，但還需要進一步調(diào)查，你怎么看呢，歡迎在評論區(qū)留言討論~

相關(guān)報道：

https://www.valerionappi.it/brng-en/