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

隨機(jī)性的定義

隨機(jī)性是指一系列事件或結(jié)果中不存在任何可預(yù)測(cè)模式或順序。真正的隨機(jī)性難以實(shí)現(xiàn),特別是在計(jì)算機(jī)這樣的確定性系統(tǒng)中,因?yàn)樗鼈冏裱囟ǖ闹噶钸\(yùn)行。在數(shù)學(xué)和計(jì)算領(lǐng)域,隨機(jī)性對(duì)于實(shí)現(xiàn)無(wú)偏采樣、密碼安全以及確保模擬和隨機(jī)化算法等過(guò)程的不可預(yù)測(cè)性至關(guān)重要。

隨機(jī)性可分為以下兩類(lèi):

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

熵的理解

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

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

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

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

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

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

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

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

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

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

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

PRNG的特點(diǎn):

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

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

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

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

常見(jiàn)的PRNG算法:

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

其中:

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

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

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

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

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

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

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

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

CSPRNG的主要特點(diǎn)包括:

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

為滿(mǎn)足上述要求,CSPRNG通?；诎踩拿艽a學(xué)原語(yǔ)構(gòu)建,如:

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

常見(jiàn)的CSPRNG算法包括:

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

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

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

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

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

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

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

TRNG中的真隨機(jī)性來(lái)源:

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

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

TRNG的特點(diǎn):

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

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

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

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

PRNG與TRNG的比較

確定性

• PRNG:具有確定性,即使用相同種子初始化時(shí),會(huì)產(chǎn)生相同的隨機(jī)序列。
• TRNG:非確定性,依賴(lài)于不可預(yù)測(cè)的物理過(guò)程。

速度性能

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

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

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

周期性

• PRNG:具有固定周期,最終會(huì)重復(fù),周期長(zhǎng)度取決于算法。
• TRNG:無(wú)周期性,每個(gè)隨機(jī)值都獨(dú)立生成。

熵的質(zhì)量

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

應(yīng)用場(chǎng)景

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

可預(yù)測(cè)性

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

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

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

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

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

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

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

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

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