用香蕉驅(qū)動(dòng)一個(gè)隨機(jī)數(shù)生成器，靠譜嗎？

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

比如前兩天，區(qū)塊鏈平臺(tái)Solana出現(xiàn)了長(zhǎng)達(dá)4個(gè)小時(shí)的宕機(jī)事件。

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

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

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

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

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

讓我們從問(wèn)題的根源開(kāi)始說(shuō)起。

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

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

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

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

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

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

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

TRNG有許多類型，不過(guò)他們?cè)矶际穷愃频?，即利用不同的物理隨機(jī)量并將其轉(zhuǎn)換為數(shù)字信息傳遞給計(jì)算機(jī)。最常見(jiàn)的是利用物理現(xiàn)象，如電阻的熱噪聲、二極管的雪崩效應(yīng)和其他混亂效應(yīng)。

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

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

但有一個(gè)問(wèn)題仍然存在：我們?cè)谟?jì)算機(jī)中對(duì)隨機(jī)數(shù)做什么？

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

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

要用什么來(lái)檢測(cè)“香蕉”

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

在這里我們當(dāng)然選擇ent。

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

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

做完這些，我們就可以第一次運(yùn)行ent測(cè)試了。

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

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

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

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

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

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

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

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

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

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

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

于是我們得到了實(shí)驗(yàn)的卡方值，3068。

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

但然而，對(duì)于我們來(lái)說(shuō)，這是一則壞消息，因?yàn)檫@意味著我們的數(shù)據(jù)不是均勻分布的。

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

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

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

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

經(jīng)過(guò)一些測(cè)試，我決定將偶數(shù)位置的字節(jié)與奇數(shù)位置的字節(jié)分開(kāi)。這是因?yàn)槊可梢粋€(gè)16位數(shù)字（2個(gè)字節(jié)），就會(huì)產(chǎn)生兩個(gè)字節(jié)，一個(gè)是偶數(shù)位置，一個(gè)是奇數(shù)位置。

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

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

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

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

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

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

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

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

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

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

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

相關(guān)報(bào)道：

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