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

比如前兩天，區塊鏈平臺Solana出現了長達4個小時的宕機事件。

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

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

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

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

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

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

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

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

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

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

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

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

當我們為計算機提供隨機數時，硬件系統是必不可少的，這就是隨機數生成器（TRNG）。

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

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

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

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

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

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

要用什么來檢測“香蕉”

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

在這里我們當然選擇ent。

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

兩天內收集的樣本包括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。
• 用蒙特卡洛方法計算π的值：在這里更多的是一個漂亮的數據，而不是一個有用的方法。
• 自相關：表示系列值之間的依賴性，在最佳情況下必須等于零。

香蕉與卡方的關系

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

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

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

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

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

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

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

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

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

關于香蕉的猜測

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

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

?

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

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

?

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

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

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

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

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

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

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

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

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