?你以為的隨機數是不是都是那種很高級的？

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

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

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

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

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

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

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

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

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

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

數字的序列必須是事先無法預測的。

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

但是，這和香蕉有什么關系？

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

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

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

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

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

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

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

要用什么來檢測“香蕉”

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

在這里我們當然選擇ent。

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

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

#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給出了幾個參數：

• 熵：熵是一部分信息中包含的“隨機性”的數量。信息理論告訴我們，理論上可以通過壓縮而不損失信息的最小尺寸，由熵值表示。
• 卡方分布：這個測試是用來了解我們的數值分布對理論分布的遵守程度。從ent手冊來看，這個值應該盡可能地接近256，百分比值在10-90%之間。
• 算術平均值：比特的簡單算術平均值。由于數值在0到255之間，所以它應該大約等于127。
• 用蒙特卡洛方法計算π的值：在這里更多的是一個漂亮的數據，而不是一個有用的方法。
• 自相關：表示系列值之間的依賴性，在最佳情況下必須等于零。

香蕉與卡方的關系

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

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

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

這些是從實驗中得到的數據：

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

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

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

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

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

關于香蕉的猜測

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

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

?

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

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

?

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

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

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

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

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

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

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

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

但也有可能使用串行對延遲產生了影響，但還需要進一步調查?