隨機性在諸多領(lǐng)域中扮演著至關(guān)重要的角色,涵蓋密碼學(xué)、仿真和機器學(xué)習(xí)等方面。因為隨機性為無偏決策、不可預(yù)測序列和安全加密提供了基礎(chǔ)。然而生成隨機數(shù)是一項復(fù)雜的任務(wù),理解偽隨機數(shù)生成(pseudo-random number generation, PRNG)與真隨機數(shù)生成(true random number generation, TRNG)之間的區(qū)別至關(guān)重要。本文將探討隨機性、熵的概念以及不同類型隨機數(shù)生成器(random number generator, RNG)的原理,重點介紹偽隨機數(shù)生成器(PRNG)和真隨機數(shù)生成器(TRNG)。

隨機性的定義

隨機性是指一系列事件或結(jié)果中不存在任何可預(yù)測模式或順序。真正的隨機性難以實現(xiàn),特別是在計算機這樣的確定性系統(tǒng)中,因為它們遵循特定的指令運行。在數(shù)學(xué)和計算領(lǐng)域,隨機性對于實現(xiàn)無偏采樣、密碼安全以及確保模擬和隨機化算法等過程的不可預(yù)測性至關(guān)重要。

隨機性可分為以下兩類:

• 確定性隨機性:由已知過程(如算法)生成,但呈現(xiàn)出隨機特征。
• 非確定性隨機性:由自然界中不可預(yù)測的過程(如放射性衰變或大氣噪聲)產(chǎn)生。

熵的理解

熵衡量了系統(tǒng)中的不可預(yù)測性或隨機性程度。在信息論中,熵量化了一個序列所包含的信息量,通常與無序程度相關(guān)。熵值越高,意味著不可預(yù)測性越強。

熵的關(guān)鍵概念:

香農(nóng)熵:度量隨機變量可能取值的平均不可預(yù)測性。其計算公式為:

其中p(x_i)表示每個可能結(jié)果x_i的概率。

熵源:物理過程(如放射性衰變、熱噪聲)和計算方法(如哈希函數(shù)、系統(tǒng)狀態(tài))可作為熵源,在生成密碼密鑰時尤其重要。

對于安全性和不可預(yù)測性要求極高的應(yīng)用,如密碼學(xué),高熵至關(guān)重要。低熵可能會暴露某些模式,使系統(tǒng)容易受到攻擊。

隨機數(shù)生成器(RNG)概述

隨機數(shù)生成器(RNG)是能夠生成無特定模式數(shù)字序列的算法或硬件系統(tǒng)。主要有兩類RNG:

• 偽隨機數(shù)生成器(PRNG):通過算法方法生成看似隨機但實際上具有確定性的數(shù)字序列。
• 真隨機數(shù)生成器(TRNG):利用物理現(xiàn)象,通過硬件方法產(chǎn)生真正不可預(yù)測的隨機數(shù)序列。

偽隨機數(shù)生成器(PRNG)

PRNG采用數(shù)學(xué)算法生成看似隨機但實為確定性的數(shù)字序列。PRNG由一個"種子"值初始化,如果給定相同的種子,它們總是產(chǎn)生相同的序列。

PRNG的特點:

• 確定性:對于相同的種子值,PRNG將始終生成相同的序列。
• 高效性:PRNG能夠快速生成大量隨機值。 
• 周期性:PRNG序列最終會在一定周期后重復(fù),不過現(xiàn)代PRNG算法的周期非常長。

除上述特點外,PRNG還具有以下優(yōu)點:

• 可重現(xiàn)性:由于PRNG的確定性,可以方便地重現(xiàn)特定的隨機數(shù)序列,這在某些應(yīng)用中非常有用,如調(diào)試、測試和科學(xué)模擬等。
• 可并行化:PRNG算法通常易于并行化,可以在多核處理器或分布式系統(tǒng)上高效運行,從而進一步提高生成速度。
• 靈活性:PRNG算法的參數(shù)(如種子值、算法系數(shù)等)可以根據(jù)需要進行調(diào)整,以滿足不同應(yīng)用對隨機性質(zhì)量的要求。 

盡管PRNG具有諸多優(yōu)點,但其確定性使其不適用于對不可預(yù)測性要求極高的場合,如密碼密鑰生成等。在這些領(lǐng)域,TRNG通常是更合適的選擇。

常見的PRNG算法:

1、線性同余生成器(LCG):作為最古老、最簡單的PRNG之一,LCG采用以下公式生成隨機數(shù)序列:

其中:

• X_n表示當(dāng)前隨機值,
• a,c和m為常數(shù)參數(shù),分別稱為乘數(shù)、增量和模數(shù)。

LCG的優(yōu)點在于實現(xiàn)簡單、計算速度快,但其統(tǒng)計性質(zhì)較差,不適合密碼應(yīng)用。

2、梅森旋轉(zhuǎn)算法(Mersenne Twister):以其超長周期(約為2^19937?1)著稱,MT算法被廣泛應(yīng)用于對隨機數(shù)質(zhì)量要求較高的領(lǐng)域。MT采用了一種基于矩陣線性遞歸的構(gòu)造方法,具有良好的統(tǒng)計特性和高維均勻分布。

梅森旋轉(zhuǎn)算法(Mersenne Twister)有一套復(fù)雜的數(shù)學(xué)公式。它基于矩陣線性遞歸,利用了有限二進制字段上的線性變換。但是在實現(xiàn)MT算法時,通常按照標(biāo)準(zhǔn)的描述來編程,無需從頭推導(dǎo)這些公式，所以我們這里就不詳細介紹了。

MT算法的突出優(yōu)點在于其超長周期和高維均勻分布,這得益于其巧妙的數(shù)學(xué)構(gòu)造。同時,MT也具有較高的生成速度和良好的統(tǒng)計學(xué)性質(zhì),因此被廣泛應(yīng)用于各種需要高質(zhì)量隨機數(shù)的領(lǐng)域。

3、Xorshift生成器:這類PRNG利用異或(XOR)和位移等位運算產(chǎn)生隨機數(shù)序列。其優(yōu)點是計算簡潔高效,速度遠超許多其他PRNG。Xorshift生成器的缺點是統(tǒng)計性質(zhì)略遜于MT,但仍可滿足一般應(yīng)用需求。以下是Xorshift算法的通用公式:

Xorshift算法的優(yōu)點在于其簡潔、高效,僅需要很少的狀態(tài)存儲和計算操作就能生成質(zhì)量尚可的偽隨機數(shù)序列。但它的統(tǒng)計性質(zhì)略遜于梅森旋轉(zhuǎn)等更復(fù)雜的算法。在對隨機性要求較高的場合,通常會選用Xorshift*或其他改進版本。

4、密碼學(xué)PRNG(CSPRNG):密碼學(xué)偽隨機數(shù)生成器(Cryptographically Secure Pseudo-Random Number Generator, CSPRNG)是一類特殊的偽隨機數(shù)生成器,旨在生成具有很高安全性和不可預(yù)測性的隨機數(shù)序列,使其能夠安全地用于密碼學(xué)應(yīng)用。與一般的PRNG相比,CSPRNG必須滿足更嚴(yán)格的安全性要求。

CSPRNG的主要特點包括:

1. 不可區(qū)分性:CSPRNG生成的隨機數(shù)序列應(yīng)當(dāng)與真隨機數(shù)序列在統(tǒng)計學(xué)上不可區(qū)分。即使攻擊者獲得了部分隨機輸出,也無法有效預(yù)測后續(xù)的隨機數(shù)。
2. 不可預(yù)測性:攻擊者即使知道CSPRNG的算法和部分狀態(tài)信息,也無法以優(yōu)于暴力搜索的效率預(yù)測后續(xù)輸出。這是通過引入足夠的熵(隨機性)來實現(xiàn)的。
3. 備用安全性:即使CSPRNG的部分狀態(tài)泄露或算法存在一定缺陷,仍能保證生成隨機數(shù)的安全性。這通常通過積累熵池、重新密鑰化等機制來實現(xiàn)。

為滿足上述要求,CSPRNG通常基于安全的密碼學(xué)原語構(gòu)建,如:

• 分組密碼:如AES、ChaCha20等,可用于構(gòu)建偽隨機函數(shù)(PRF)或偽隨機置換(PRP)。
• 哈希函數(shù):如SHA-2、SHA-3等,可用于熵萃取、密鑰派生等。
• 消息認證碼(MAC):如HMAC、CMAC等,可用于完整性驗證和密鑰生成。

常見的CSPRNG算法包括:

1. Fortuna:由Bruce Schneier等人設(shè)計,使用多個熵源來積累隨機種子,并周期性地對種子進行重新密鑰化。Fortuna廣泛應(yīng)用于開源操作系統(tǒng)和密碼庫中。
2. Yarrow:Fortuna的前身,也是一種積累熵的CSPRNG算法。Yarrow在MacOS、iOS等系統(tǒng)中使用。
3. CTR_DRBG:基于分組密碼(如AES)的確定性隨機比特生成器(Deterministic Random Bit Generator, DRBG),由NIST標(biāo)準(zhǔn)化。CTR_DRBG在Linux內(nèi)核、OpenSSL等中使用。
4. HASH_DRBG和HMAC_DRBG:分別基于哈希函數(shù)和消息認證碼的DRBG,也由NIST標(biāo)準(zhǔn)化。
5. ChaCha20:基于ChaCha20流密碼的CSPRNG,可用于快速生成隨機數(shù)。ChaCha20已被IETF標(biāo)準(zhǔn)化,并用于TLS協(xié)議等。

CSPRNG算法各自都有其獨特的結(jié)構(gòu)和流程,難以用一個通用公式來描述。CSPRNG與一般的PRNG相比,在種子管理、安全性分析等方面有更嚴(yán)格的要求,因此其算法結(jié)構(gòu)往往也更為復(fù)雜。在實際應(yīng)用中,應(yīng)當(dāng)選用經(jīng)過充分安全性評估的標(biāo)準(zhǔn)CSPRNG算法,而非自行設(shè)計。

PRNG的應(yīng)用場景:

• 模擬仿真:如蒙特卡羅方法、隨機采樣等。
• 游戲娛樂:游戲內(nèi)事件和元素的隨機生成。
• 統(tǒng)計抽樣:隨機選取數(shù)據(jù)樣本進行分析。

盡管PRNG在諸多領(lǐng)域有著廣泛應(yīng)用,但其確定性的特點限制了它在安全關(guān)鍵場合(如密鑰生成)中的使用。 

真隨機數(shù)生成器(TRNG)

TRNG,即硬件隨機數(shù)生成器,通過利用不可預(yù)測的物理過程產(chǎn)生真正隨機的數(shù)字序列。與PRNG不同,TRNG無需種子,其生成的隨機數(shù)完全獨立于之前的輸出值。

TRNG中的真隨機性來源:

1. 放射性衰變:放射性物質(zhì)以隨機方式發(fā)射粒子,是可靠的熵源。
2. 熱噪聲:電子元件中普遍存在的熱噪聲可作為隨機源。
3. 光子過程:光子在光學(xué)系統(tǒng)中的量子行為(如通過分束器)可用于提取隨機性。
4. 大氣噪聲:由無線電或傳感器采集的大氣噪聲變化是一種天然的不可預(yù)測隨機源。

除上述物理過程外,TRNG還可利用其他量子效應(yīng),如光子糾纏、電子自旋等,進一步提高隨機數(shù)的質(zhì)量。

TRNG的特點:

• 非確定性:即使在相同初始條件下,TRNG生成的隨機序列也不可重復(fù)。
• 生成速度限制:受物理過程的制約,TRNG的生成速率通常低于PRNG。
• 高熵輸出:TRNG提供接近完全隨機的高熵數(shù)據(jù),非常適合安全關(guān)鍵應(yīng)用。

TRNG的應(yīng)用領(lǐng)域:

• 密碼學(xué):生成加密密鑰、初始化向量、會話令牌等。 
• 科學(xué)實驗:在采樣或?qū)嶒炘O(shè)置中需要高度不可預(yù)測性的場合。
• 博彩業(yè):確保游戲結(jié)果的公平性和不可預(yù)知性。

盡管TRNG具有高安全性的優(yōu)點,但其生成速度和實現(xiàn)成本通常高于PRNG。因此,TRNG主要用于對隨機數(shù)絕對不可預(yù)測性有嚴(yán)格要求的應(yīng)用中。

PRNG與TRNG的比較

確定性

• PRNG:具有確定性,即使用相同種子初始化時,會產(chǎn)生相同的隨機序列。
• TRNG:非確定性,依賴于不可預(yù)測的物理過程。

速度性能

• PRNG:生成速度快,能夠快速產(chǎn)生大量隨機數(shù)。
• TRNG:受物理過程限制,生成速率通常低于PRNG。

實現(xiàn)復(fù)雜度

• PRNG:基于數(shù)學(xué)算法,通過軟件實現(xiàn)。
• TRNG:依賴專用硬件,從物理源中提取熵。

周期性

• PRNG:具有固定周期,最終會重復(fù),周期長度取決于算法。
• TRNG:無周期性,每個隨機值都獨立生成。

熵的質(zhì)量

• PRNG:熵的質(zhì)量取決于算法和種子,通常為中等水平。
• TRNG:能夠提供高質(zhì)量熵,生成全真隨機數(shù),適合安全關(guān)鍵應(yīng)用。

應(yīng)用場景

• PRNG:廣泛應(yīng)用于對效率要求較高的領(lǐng)域,如仿真、游戲和統(tǒng)計抽樣等。
• TRNG:主要用于密碼學(xué)和安全系統(tǒng)等對不可預(yù)測性要求極高的場合。

可預(yù)測性

• PRNG:當(dāng)種子已知時,輸出可被預(yù)測,因此不適合密碼應(yīng)用。
• TRNG:依賴自然熵源,輸出不可預(yù)測。

需要指出的是,在實際應(yīng)用中,PRNG和TRNG并非完全對立,它們常常協(xié)同使用以發(fā)揮各自的優(yōu)勢。例如,可用TRNG產(chǎn)生高熵種子,再用其初始化PRNG以提高生成速率。通過恰當(dāng)結(jié)合兩者,可在保證安全性的同時兼顧效率。

PRNG與TRNG的協(xié)同應(yīng)用

現(xiàn)代隨機數(shù)解決方案通常采用PRNG和TRNG相結(jié)合的混合架構(gòu),以期兼具速度和安全性。一種常見做法是利用TRNG產(chǎn)生高熵種子,再用其初始化密碼學(xué)安全的PRNG。這樣,既可從TRNG獲得高質(zhì)量熵,又能發(fā)揮PRNG的高速生成能力,是密碼通信等安全關(guān)鍵應(yīng)用的理想方案。

隨機數(shù)生成面臨的挑戰(zhàn)與思考

1. 熵估計困難:評估TRNG產(chǎn)生隨機數(shù)的質(zhì)量可能面臨挑戰(zhàn),需采用統(tǒng)計學(xué)檢測以確保熵足夠。
2. 潛在安全隱患:對于PRNG,不當(dāng)?shù)姆N子選取可能導(dǎo)致可預(yù)測性,從而危及密碼應(yīng)用安全。而TRNG硬件的缺陷則可能產(chǎn)生有偏差的隨機數(shù)。
3. 速度與質(zhì)量的權(quán)衡:TRNG提供優(yōu)質(zhì)隨機源,但生成速率較低;PRNG具有高速優(yōu)勢,但可能不及TRNG般不可預(yù)測。如何平衡二者是一大挑戰(zhàn)。
4. 嚴(yán)格測試與驗證:無論是PRNG還是TRNG,其隨機性都需經(jīng)過嚴(yán)格的統(tǒng)計學(xué)檢驗,如NIST SP800-22隨機性測試標(biāo)準(zhǔn)等,以保證隨機數(shù)序列的質(zhì)量。 

此外,隨機數(shù)生成技術(shù)的發(fā)展還面臨其他機遇與挑戰(zhàn):

• 后量子密碼學(xué):隨著量子計算的發(fā)展,傳統(tǒng)密碼體制面臨嚴(yán)峻挑戰(zhàn)。后量子密碼算法(如格基密碼、哈希簽名等)對隨機數(shù)質(zhì)量提出了更高要求,亟需發(fā)展更安全高效的隨機源。
• 機器學(xué)習(xí)中的隨機性:隨機性在機器學(xué)習(xí)中扮演重要角色,如隨機梯度下降、Dropout正則化等。開發(fā)適合機器學(xué)習(xí)場景的專用隨機數(shù)生成器,對提升模型性能意義重大。
• 隨機性的理論研究:隨機性的本質(zhì)一直是基礎(chǔ)科學(xué)的研究熱點。從算法復(fù)雜性到量子物理,從混沌動力學(xué)到生物學(xué),隨機性無處不在。深入探討隨機性的理論基礎(chǔ),有助于指導(dǎo)隨機技術(shù)的創(chuàng)新發(fā)展。

隨機性、熵和隨機數(shù)生成器是密碼學(xué)、安全系統(tǒng)等領(lǐng)域的核心概念。理解其內(nèi)涵對設(shè)計和實現(xiàn)安全可靠的應(yīng)用至關(guān)重要。PRNG憑借高效易用的特點,在仿真、游戲等領(lǐng)域得到廣泛應(yīng)用;而TRNG以其高熵、不可預(yù)測等優(yōu)勢,成為密碼學(xué)不可或缺的隨機源。在現(xiàn)實中,二者常常協(xié)同使用,以期在安全與效率間求得平衡。未來,隨著信息安全、人工智能等領(lǐng)域的快速發(fā)展,隨機技術(shù)必將迎來更多的機遇與挑戰(zhàn)。