隨機(jī)性、熵與隨機(jī)數(shù)生成器:解析偽隨機(jī)數(shù)生成器（PRNG）和真隨機(jī)數(shù)生成器（TRNG）
隨機(jī)性在諸多領(lǐng)域中扮演著至關(guān)重要的角色,涵蓋密碼學(xué)、仿真和機(jī)器學(xué)習(xí)等方面。因?yàn)殡S機(jī)性為無偏決策、不可預(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ī)性、熵的概念以及不同類型隨機(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)無偏采樣、密碼安全以及確保模擬和隨機(jī)化算法等過程的不可預(yù)測(cè)性至關(guān)重要。
隨機(jī)性可分為以下兩類:
- 確定性隨機(jī)性:由已知過程(如算法)生成,但呈現(xiàn)出隨機(jī)特征。
- 非確定性隨機(jī)性:由自然界中不可預(yù)測(cè)的過程(如放射性衰變或大氣噪聲)產(chǎn)生。
熵的理解
熵衡量了系統(tǒng)中的不可預(yù)測(cè)性或隨機(jī)性程度。在信息論中,熵量化了一個(gè)序列所包含的信息量,通常與無序程度相關(guān)。熵值越高,意味著不可預(yù)測(cè)性越強(qiáng)。
熵的關(guān)鍵概念:
香農(nóng)熵:度量隨機(jī)變量可能取值的平均不可預(yù)測(cè)性。其計(jì)算公式為:
其中p(x_i)表示每個(gè)可能結(jié)果x_i的概率。
熵源:物理過程(如放射性衰變、熱噪聲)和計(jì)算方法(如哈希函數(shù)、系統(tǒng)狀態(tài))可作為熵源,在生成密碼密鑰時(shí)尤其重要。
對(duì)于安全性和不可預(yù)測(cè)性要求極高的應(yīng)用,如密碼學(xué),高熵至關(guān)重要。低熵可能會(huì)暴露某些模式,使系統(tǒng)容易受到攻擊。
隨機(jī)數(shù)生成器(RNG)概述
隨機(jī)數(shù)生成器(RNG)是能夠生成無特定模式數(shù)字序列的算法或硬件系統(tǒng)。主要有兩類RNG:
- 偽隨機(jī)數(shù)生成器(PRNG):通過算法方法生成看似隨機(jī)但實(shí)際上具有確定性的數(shù)字序列。
- 真隨機(jī)數(shù)生成器(TRNG):利用物理現(xiàn)象,通過硬件方法產(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ù),不過現(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)整,以滿足不同應(yīng)用對(duì)隨機(jī)性質(zhì)量的要求。
盡管PRNG具有諸多優(yōu)點(diǎn),但其確定性使其不適用于對(duì)不可預(yù)測(cè)性要求極高的場(chǎng)合,如密碼密鑰生成等。在這些領(lǐng)域,TRNG通常是更合適的選擇。
常見的PRNG算法:
1、線性同余生成器(LCG):作為最古老、最簡(jiǎn)單的PRNG之一,LCG采用以下公式生成隨機(jī)數(shù)序列:
其中:
- X_n表示當(dāng)前隨機(jī)值,
- a,c和m為常數(shù)參數(shù),分別稱為乘數(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)著稱,MT算法被廣泛應(yīng)用于對(duì)隨機(jī)數(shù)質(zhì)量要求較高的領(lǐng)域。MT采用了一種基于矩陣線性遞歸的構(gòu)造方法,具有良好的統(tǒng)計(jì)特性和高維均勻分布。
梅森旋轉(zhuǎn)算法(Mersenne Twister)有一套復(fù)雜的數(shù)學(xué)公式。它基于矩陣線性遞歸,利用了有限二進(jìn)制字段上的線性變換。但是在實(shí)現(xiàn)MT算法時(shí),通常按照標(biāo)準(zhǔn)的描述來編程,無需從頭推導(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生成器:這類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,但仍可滿足一般應(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)是一類特殊的偽隨機(jī)數(shù)生成器,旨在生成具有很高安全性和不可預(yù)測(cè)性的隨機(jī)數(shù)序列,使其能夠安全地用于密碼學(xué)應(yīng)用。與一般的PRNG相比,CSPRNG必須滿足更嚴(yán)格的安全性要求。
CSPRNG的主要特點(diǎn)包括:
- 不可區(qū)分性:CSPRNG生成的隨機(jī)數(shù)序列應(yīng)當(dāng)與真隨機(jī)數(shù)序列在統(tǒng)計(jì)學(xué)上不可區(qū)分。即使攻擊者獲得了部分隨機(jī)輸出,也無法有效預(yù)測(cè)后續(xù)的隨機(jī)數(shù)。
- 不可預(yù)測(cè)性:攻擊者即使知道CSPRNG的算法和部分狀態(tài)信息,也無法以優(yōu)于暴力搜索的效率預(yù)測(cè)后續(xù)輸出。這是通過引入足夠的熵(隨機(jī)性)來實(shí)現(xiàn)的。
- 備用安全性:即使CSPRNG的部分狀態(tài)泄露或算法存在一定缺陷,仍能保證生成隨機(jī)數(shù)的安全性。這通常通過積累熵池、重新密鑰化等機(jī)制來實(shí)現(xiàn)。
為滿足上述要求,CSPRNG通常基于安全的密碼學(xué)原語構(gòu)建,如:
- 分組密碼:如AES、ChaCha20等,可用于構(gòu)建偽隨機(jī)函數(shù)(PRF)或偽隨機(jī)置換(PRP)。
- 哈希函數(shù):如SHA-2、SHA-3等,可用于熵萃取、密鑰派生等。
- 消息認(rèn)證碼(MAC):如HMAC、CMAC等,可用于完整性驗(yàn)證和密鑰生成。
常見的CSPRNG算法包括:
- Fortuna:由Bruce Schneier等人設(shè)計(jì),使用多個(gè)熵源來積累隨機(jī)種子,并周期性地對(duì)種子進(jìn)行重新密鑰化。Fortuna廣泛應(yīng)用于開源操作系統(tǒng)和密碼庫中。
- Yarrow:Fortuna的前身,也是一種積累熵的CSPRNG算法。Yarrow在MacOS、iOS等系統(tǒng)中使用。
- CTR_DRBG:基于分組密碼(如AES)的確定性隨機(jī)比特生成器(Deterministic Random Bit Generator, DRBG),由NIST標(biāo)準(zhǔn)化。CTR_DRBG在Linux內(nèi)核、OpenSSL等中使用。
- HASH_DRBG和HMAC_DRBG:分別基于哈希函數(shù)和消息認(rèn)證碼的DRBG,也由NIST標(biāo)準(zhǔn)化。
- ChaCha20:基于ChaCha20流密碼的CSPRNG,可用于快速生成隨機(jī)數(shù)。ChaCha20已被IETF標(biāo)準(zhǔn)化,并用于TLS協(xié)議等。
CSPRNG算法各自都有其獨(dú)特的結(jié)構(gòu)和流程,難以用一個(gè)通用公式來描述。CSPRNG與一般的PRNG相比,在種子管理、安全性分析等方面有更嚴(yán)格的要求,因此其算法結(jié)構(gòu)往往也更為復(fù)雜。在實(shí)際應(yīng)用中,應(yīng)當(dāng)選用經(jīng)過充分安全性評(píng)估的標(biāo)準(zhǔn)CSPRNG算法,而非自行設(shè)計(jì)。
PRNG的應(yīng)用場(chǎng)景:
- 模擬仿真:如蒙特卡羅方法、隨機(jī)采樣等。
- 游戲娛樂:游戲內(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ù)生成器,通過利用不可預(yù)測(cè)的物理過程產(chǎn)生真正隨機(jī)的數(shù)字序列。與PRNG不同,TRNG無需種子,其生成的隨機(jī)數(shù)完全獨(dú)立于之前的輸出值。
TRNG中的真隨機(jī)性來源:
- 放射性衰變:放射性物質(zhì)以隨機(jī)方式發(fā)射粒子,是可靠的熵源。
- 熱噪聲:電子元件中普遍存在的熱噪聲可作為隨機(jī)源。
- 光子過程:光子在光學(xué)系統(tǒng)中的量子行為(如通過分束器)可用于提取隨機(jī)性。
- 大氣噪聲:由無線電或傳感器采集的大氣噪聲變化是一種天然的不可預(yù)測(cè)隨機(jī)源。
除上述物理過程外,TRNG還可利用其他量子效應(yīng),如光子糾纏、電子自旋等,進(jìn)一步提高隨機(jī)數(shù)的質(zhì)量。
TRNG的特點(diǎn):
- 非確定性:即使在相同初始條件下,TRNG生成的隨機(jī)序列也不可重復(fù)。
- 生成速度限制:受物理過程的制約,TRNG的生成速率通常低于PRNG。
- 高熵輸出:TRNG提供接近完全隨機(jī)的高熵?cái)?shù)據(jù),非常適合安全關(guān)鍵應(yīng)用。
TRNG的應(yīng)用領(lǐng)域:
- 密碼學(xué):生成加密密鑰、初始化向量、會(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:非確定性,依賴于不可預(yù)測(cè)的物理過程。
速度性能
- PRNG:生成速度快,能夠快速產(chǎn)生大量隨機(jī)數(shù)。
- TRNG:受物理過程限制,生成速率通常低于PRNG。
實(shí)現(xiàn)復(fù)雜度
- PRNG:基于數(shù)學(xué)算法,通過軟件實(shí)現(xiàn)。
- TRNG:依賴專用硬件,從物理源中提取熵。
周期性
- PRNG:具有固定周期,最終會(huì)重復(fù),周期長(zhǎng)度取決于算法。
- TRNG:無周期性,每個(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:依賴自然熵源,輸出不可預(yù)測(cè)。
需要指出的是,在實(shí)際應(yīng)用中,PRNG和TRNG并非完全對(duì)立,它們常常協(xié)同使用以發(fā)揮各自的優(yōu)勢(shì)。例如,可用TRNG產(chǎn)生高熵種子,再用其初始化PRNG以提高生成速率。通過恰當(dāng)結(jié)合兩者,可在保證安全性的同時(shí)兼顧效率。
PRNG與TRNG的協(xié)同應(yīng)用
現(xiàn)代隨機(jī)數(shù)解決方案通常采用PRNG和TRNG相結(jié)合的混合架構(gòu),以期兼具速度和安全性。一種常見做法是利用TRNG產(chǎn)生高熵種子,再用其初始化密碼學(xué)安全的PRNG。這樣,既可從TRNG獲得高質(zhì)量熵,又能發(fā)揮PRNG的高速生成能力,是密碼通信等安全關(guān)鍵應(yīng)用的理想方案。
隨機(jī)數(shù)生成面臨的挑戰(zhàn)與思考
- 熵估計(jì)困難:評(píng)估TRNG產(chǎn)生隨機(jī)數(shù)的質(zhì)量可能面臨挑戰(zhàn),需采用統(tǒng)計(jì)學(xué)檢測(cè)以確保熵足夠。
- 潛在安全隱患:對(duì)于PRNG,不當(dāng)?shù)姆N子選取可能導(dǎo)致可預(yù)測(cè)性,從而危及密碼應(yīng)用安全。而TRNG硬件的缺陷則可能產(chǎn)生有偏差的隨機(jī)數(shù)。
- 速度與質(zhì)量的權(quán)衡:TRNG提供優(yōu)質(zhì)隨機(jī)源,但生成速率較低;PRNG具有高速優(yōu)勢(shì),但可能不及TRNG般不可預(yù)測(cè)。如何平衡二者是一大挑戰(zhàn)。
- 嚴(yán)格測(cè)試與驗(yàn)證:無論是PRNG還是TRNG,其隨機(jī)性都需經(jīng)過嚴(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正則化等。開發(fā)適合機(jī)器學(xué)習(xí)場(chǎng)景的專用隨機(jī)數(shù)生成器,對(duì)提升模型性能意義重大。
- 隨機(jī)性的理論研究:隨機(jī)性的本質(zhì)一直是基礎(chǔ)科學(xué)的研究熱點(diǎn)。從算法復(fù)雜性到量子物理,從混沌動(dòng)力學(xué)到生物學(xué),隨機(jī)性無處不在。深入探討隨機(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ǐng)域的快速發(fā)展,隨機(jī)技術(shù)必將迎來更多的機(jī)遇與挑戰(zhàn)。
