TRNG隨機(jī)數(shù)學(xué)習(xí)和驗(yàn)證筆記

前言

計(jì)算機(jī)必須有一個(gè)科學(xué)穩(wěn)定的隨機(jī)數(shù)來源，才能得到隨機(jī)數(shù)。這個(gè)來源稱為隨機(jī)數(shù)生成器(Random number generators，RNG)。

第一個(gè)真隨機(jī)數(shù)生成器是在1955年由Rand公司創(chuàng)造，Rand公司在1955年出版了一本《A Million Random Digits with 100,000 Normal Deviates》，用作隨機(jī)數(shù)表。

1999年，Intel發(fā)布了Intel810芯片組時(shí)，就配備硬件隨機(jī)數(shù)生成器，原理是電阻和振蕩器產(chǎn)生的熱噪聲。目前，大部分芯片都集成了硬件隨機(jī)數(shù)生成器，使用非常方便。

常見的隨機(jī)數(shù)生成器有三種：

• 真隨機(jī)數(shù)生成器(True Random Number Generator，TRNG)，通過物理方法模擬自然界中的隨機(jī)過程，真隨機(jī)數(shù)無法預(yù)測且無周期性。

• 偽隨機(jī)數(shù)生成器(Pseudo Random Number Generator，PRNG)，通過數(shù)學(xué)方法生成和真隨機(jī)數(shù)具有相似以統(tǒng)計(jì)特征的偽隨機(jī)數(shù)。如果能夠通過統(tǒng)計(jì)檢驗(yàn)，就可以當(dāng)成真隨機(jī)數(shù)使用。

• 隨機(jī)數(shù)表法，即用真隨機(jī)數(shù)生成大量隨機(jī)數(shù)，存到數(shù)據(jù)庫中，使用時(shí)再從數(shù)據(jù)庫中調(diào)用。在20世紀(jì)早期，這種方法被大量使用，現(xiàn)在因?yàn)樾枰加么罅看鎯?chǔ)空間，已經(jīng)很少被使用。

1.真隨機(jī)數(shù)生成器（TRNG）

基于電路的TRNG：

• 振蕩器采樣：如Intel810RNG芯片，利用熱噪聲放大后，影響一個(gè)電壓控制的振蕩器，再通過一個(gè)高頻振蕩器來收集數(shù)據(jù)，得到隨機(jī)數(shù)。

• 直接放大電路噪聲：直接以熱噪聲等電路噪聲為隨機(jī)源，通過運(yùn)放放大，統(tǒng)計(jì)一定時(shí)間內(nèi)達(dá)到閾值的信號(hào)數(shù)以此得到隨機(jī)數(shù)。

• 電路亞穩(wěn)態(tài)：2010年德國研究團(tuán)隊(duì)利用計(jì)算機(jī)內(nèi)存雙態(tài)觸發(fā)器作為隨機(jī)的一個(gè)額外層，觸發(fā)器可以在0和1狀態(tài)切換。在切換之前，觸發(fā)器處于無法預(yù)測的亞穩(wěn)態(tài)，內(nèi)存中內(nèi)容為完全隨機(jī)值。

• 混沌電路：混沌電路的輸出結(jié)果對初始條件很敏感，不可預(yù)測，且在IC易于集成，可產(chǎn)生效果不錯(cuò)的真隨機(jī)數(shù)。

2.偽隨機(jī)數(shù)生成器（PRNG）

TRNG生成的隨機(jī)數(shù)是無周期性、不可預(yù)測、分布均勻，然而TRNG技術(shù)要求高，生成速度低，難以滿足計(jì)算機(jī)高速計(jì)算需要。

因此為了提高數(shù)據(jù)產(chǎn)生率，TRNG的結(jié)果往往作為PRNG種子值，并以此生成偽隨機(jī)的輸出序列。

偽隨機(jī)數(shù)算法：

• 線性同余法

N[i+1]=(A * N[i]+B) mod M

1. B、M互質(zhì)

2. M所有質(zhì)因數(shù)都能整除(A-1)

3. 若M是4的倍數(shù)，A-1也是

4. A、B、N[0]都比M小

5. A、B是正整數(shù)·

• 梅森旋轉(zhuǎn)法Mersenn Twister)

1. 基于二進(jìn)制字段上的矩陣線性遞歸，可以快速產(chǎn)生高質(zhì)量的偽隨機(jī)數(shù)。隨機(jī)數(shù)范圍[0，2*k)，k=19937，32，64。計(jì)算機(jī)各種語言常用的偽隨機(jī)數(shù)算法。

2. 參數(shù)選擇和梅森素?cái)?shù)有關(guān)。2**n-1是素?cái)?shù)（梅森素?cái)?shù)）。

3.隨機(jī)數(shù)檢測標(biāo)準(zhǔn)

3.1 檢測標(biāo)準(zhǔn)

• 中國：GB/T 32915-2016 信息安全技術(shù) 二元序列隨機(jī)性檢測方法

• 美國：NIST SP800-22r1a

• 德國：A1S31標(biāo)準(zhǔn)

3.2 檢測方法

• 比特分布檢測：n個(gè)比特內(nèi)0和1的個(gè)數(shù)

• 跟隨分布檢測：n個(gè)比特內(nèi)00、01、10、11的概率是否相等

• 游程檢測：游程由連續(xù)的0或者1組成，并且其前后元素與游程元素不同。游程數(shù)目為序列長度一半時(shí)，隨機(jī)性比較好。

• 碰撞檢測

• 撲克檢測：先將序列劃分成長度為m的二進(jìn)制子序列，長度為的二進(jìn)制子序列由2m中類型，然后檢測這2m中子序列類型數(shù)目是否相同。

此外，還有相關(guān)性檢測、線性復(fù)雜度檢測以及長游程檢測等。

4.Feature驗(yàn)證

墑源：四路獨(dú)立墑源。每一路獨(dú)立熵源有8路RO環(huán)，由一個(gè)獨(dú)立時(shí)鐘進(jìn)行采樣。

后處理：采用密碼AES算法。

健康度檢測：NIST SP800-90B標(biāo)準(zhǔn)中列出的重復(fù)計(jì)數(shù)測試(Repetition Counter Test)和自適應(yīng)比例測試(Adaptive Proportion Test)。

輸出：一次輸出4*32-bit。

墑源質(zhì)量驗(yàn)證：生成1000*1Mb數(shù)據(jù)，然后用NIST工具進(jìn)行墑源質(zhì)量分析。

1. 采集隨機(jī)數(shù)，用16進(jìn)制輸出32位隨機(jī)數(shù)

2. 用腳本轉(zhuǎn)換成二進(jìn)制文件，比特流

3. 用NIST軟件對比特流文件進(jìn)行分析，并且得到報(bào)告。如果某個(gè)項(xiàng)目測試結(jié)果有問題，該項(xiàng)目的P-VALUE和PROPORTION旁邊會(huì)出現(xiàn)*號(hào)。

5.應(yīng)用場景

密碼學(xué)：隨機(jī)數(shù)用于生成加密密鑰，并確保加密安全性。

數(shù)學(xué)模擬：隨機(jī)數(shù)可以用于模擬不確定性的系統(tǒng)，如隨機(jī)運(yùn)動(dòng)，隨機(jī)行為等。

游戲開發(fā)：隨機(jī)數(shù)可以用于生成游戲中的隨機(jī)事件，如游戲難度、隨機(jī)道具等。

計(jì)算機(jī)圖形學(xué)：隨機(jī)數(shù)可以用于生成隨機(jī)的圖形，如隨機(jī)分布的點(diǎn)、隨機(jī)生成的紋理。

統(tǒng)計(jì)學(xué)：隨機(jī)數(shù)可以用于統(tǒng)計(jì)學(xué)的模擬和分析，如隨機(jī)化試驗(yàn)、隨機(jī)抽樣等。

邀請函(報(bào)名倒計(jì)時(shí))