與偽隨機數(shù)：密鑰生成中的隨機源與熵池管理)
1. 從一個看似矛盾的問題說起公鑰密碼學(xué)里有一個特別反直覺的事實你用來加密的密鑰是公開的任何人都能拿到但別人依然解不開你的密文。這件事第一次接觸會覺得像魔術(shù)但支撐它的數(shù)學(xué)基礎(chǔ)其實相當(dāng)樸素——單向函數(shù)。正向計算容易反向計算在算力上不可行。RSA依賴大整數(shù)分解橢圓曲線依賴離散對數(shù)它們都是這類函數(shù)的實例。但這里有個容易被忽略的環(huán)節(jié)密鑰是怎么來的。如果生成密鑰的那個隨機數(shù)本身不夠隨機整個公鑰體系的安全性就是紙糊的。我見過不少開發(fā)者算法選型很講究參數(shù)配置也到位結(jié)果栽在隨機數(shù)生成上。這篇文章就圍繞公鑰密碼學(xué)和偽隨機數(shù)之間的關(guān)系展開把密鑰生成、隨機源選擇、熵池管理這些環(huán)節(jié)拆開講清楚。適合有一定編程基礎(chǔ)、正在做安全相關(guān)功能、或者單純想搞明白“隨機數(shù)為什么能決定加密強度”的讀者。2. 公鑰密碼學(xué)的核心機制拆解2.1 對稱加密的困境與公鑰的破局思路對稱加密的邏輯很直接一把鑰匙開一把鎖加密解密用同一個密鑰。問題在于通信雙方怎么安全地把這把鑰匙交到對方手里。如果雙方能面對面交換那沒問題但如果隔著網(wǎng)絡(luò)你沒法保證傳輸通道本身是安全的。這就是經(jīng)典的密鑰分發(fā)難題。公鑰密碼學(xué)的破局思路是把密鑰拆成一對公鑰和私鑰。公鑰可以隨便公開私鑰只有自己持有。別人用你的公鑰加密你用私鑰解密。反過來你用私鑰簽名別人用公鑰驗證。整個過程中私鑰永遠不需要傳輸密鑰分發(fā)問題從根上被繞開了。這個設(shè)計的美妙之處在于它把“保密”這件事從傳輸環(huán)節(jié)轉(zhuǎn)移到了數(shù)學(xué)計算環(huán)節(jié)。你不需要保護公鑰的傳輸因為公鑰泄露不影響安全性。你只需要保護私鑰不被竊取。安全邊界從“通道”收縮到了“本地存儲”可控性大幅提升。2.2 單向函數(shù)公鑰密碼學(xué)的數(shù)學(xué)地基公鑰密碼學(xué)的安全性建立在單向函數(shù)之上。所謂單向函數(shù)就是正向計算很簡單反向求解在計算上不可行。注意這里的“不可行”不是理論上的不可能而是指以當(dāng)前已知的最佳算法和算力水平求解所需的時間超出了實際意義。以RSA為例。選兩個大質(zhì)數(shù)p和q計算n p × q這一步對計算機來說瞬間完成。但如果只知道n要反推出p和q當(dāng)n足夠大時比如2048位目前最好的分解算法也需要天文數(shù)字的時間。這就是RSA的安全基礎(chǔ)。橢圓曲線密碼學(xué)ECC用的是另一類單向函數(shù)橢圓曲線上的離散對數(shù)問題。在特定橢圓曲線上已知基點G和私鑰k計算公鑰K kG很容易但已知G和K求k在計算上不可行。ECC的優(yōu)勢在于達到同等安全強度所需的密鑰長度遠小于RSA。256位的ECC密鑰大約等價于3072位的RSA密鑰這對資源受限的環(huán)境非常友好。2.3 密鑰生成隨機數(shù)登場的時刻到這里隨機數(shù)還沒有正式出場。但密鑰生成這一步隨機數(shù)是絕對的主角。以RSA為例生成密鑰的第一步是選兩個大質(zhì)數(shù)p和q。這兩個質(zhì)數(shù)怎么來不是從質(zhì)數(shù)表里挑而是隨機生成一個大奇數(shù)然后做素性檢測不是質(zhì)數(shù)就換一個繼續(xù)試。這個“隨機生成”的過程用的就是隨機數(shù)生成器。ECC的密鑰生成更直接私鑰k就是一個隨機數(shù)在橢圓曲線的階的范圍內(nèi)隨機選取。公鑰K由k計算得出。如果k的隨機性不夠攻擊者可以通過窮舉或統(tǒng)計分析縮小搜索范圍私鑰就可能被推出來。所以隨機數(shù)的質(zhì)量直接決定了密鑰的質(zhì)量密鑰的質(zhì)量直接決定了整個公鑰體系的安全上限。算法再強隨機數(shù)不行一切白搭。3. 偽隨機數(shù)的真相不是真隨機但夠用3.1 真隨機與偽隨機的本質(zhì)區(qū)別嚴格來說計算機里沒有真正的隨機。計算機是確定性系統(tǒng)給定相同的輸入和狀態(tài)輸出必然相同。所謂“隨機數(shù)”要么來自物理世界的不可預(yù)測現(xiàn)象要么來自算法對種子的確定性變換。真隨機數(shù)生成器TRNG依賴物理熵源熱噪聲、光電效應(yīng)、放射性衰變的時間間隔等。這些現(xiàn)象在量子層面本質(zhì)上是不可預(yù)測的所以TRNG的輸出具有真正的隨機性。但TRNG的問題是速度慢、成本高而且不是所有環(huán)境都能提供高質(zhì)量的物理熵源。偽隨機數(shù)生成器PRNG則是純算法。給定一個種子它通過確定性算法生成一長串看起來隨機的數(shù)字序列。如果種子相同輸出序列完全相同。PRNG的優(yōu)點是速度快、可復(fù)現(xiàn)、實現(xiàn)簡單。缺點是如果種子被猜到或泄露整個序列都可被預(yù)測。3.2 密碼學(xué)安全偽隨機數(shù)生成器CSPRNG普通PRNG和CSPRNG的區(qū)別就像普通鎖和防盜鎖的區(qū)別。普通PRNG比如線性同余生成器的設(shè)計目標是統(tǒng)計特性好、速度快不關(guān)心抗攻擊能力。CSPRNG則必須滿足兩個額外條件一是給定部分輸出無法推算出后續(xù)輸出二是給定內(nèi)部狀態(tài)無法反推出之前的輸出。CSPRNG的典型構(gòu)造方式包括基于密碼學(xué)哈希函數(shù)如SHA-256的構(gòu)造、基于分組密碼如AES-CTR模式的構(gòu)造、以及專門設(shè)計的流密碼如ChaCha20。這些構(gòu)造的共同特點是即使攻擊者獲得了部分輸出也無法有效預(yù)測其余部分。在實際開發(fā)中選擇CSPRNG是密鑰生成的底線要求。Python的secrets模塊、Java的SecureRandom、Go的crypto/rand、OpenSSL的RAND_bytes這些都是CSPRNG的實現(xiàn)。而random模塊、Math.random()、C語言的rand()這些都不是密碼學(xué)安全的絕對不能用于密鑰生成。3.3 熵池隨機數(shù)的“水庫”操作系統(tǒng)層面隨機數(shù)的來源通常是一個熵池。Linux的/dev/random和/dev/urandom就是熵池的兩個接口。/dev/random在熵不足時會阻塞直到收集到足夠的熵/dev/urandom則不阻塞熵不足時用CSPRNG繼續(xù)生成。熵的來源包括鍵盤敲擊的時間間隔、鼠標移動軌跡、磁盤I/O的完成時間、網(wǎng)絡(luò)中斷的到達時間等。這些事件的時間戳具有足夠的不可預(yù)測性被內(nèi)核收集后混入熵池。這里有個常見的誤區(qū)很多人認為/dev/urandom不如/dev/random安全。實際上在現(xiàn)代Linux內(nèi)核中一旦熵池完成初始化/dev/urandom的輸出在密碼學(xué)上是安全的。/dev/random的阻塞行為在大多數(shù)場景下只會帶來不必要的性能問題。只有在系統(tǒng)剛啟動、熵池尚未初始化完成的極短窗口內(nèi)/dev/urandom的輸出才可能不夠安全。注意在嵌入式設(shè)備或虛擬機中熵源可能非常有限。系統(tǒng)啟動后熵池可能長時間處于低熵狀態(tài)。這種情況下建議使用haveged或rng-tools等工具補充熵或者在應(yīng)用層使用硬件隨機數(shù)生成器。4. 密鑰生成實操從隨機數(shù)到密鑰對4.1 RSA密鑰生成的完整流程RSA密鑰生成的核心步驟可以拆解為以下幾個環(huán)節(jié)隨機生成兩個大質(zhì)數(shù)p和q長度各為密鑰長度的一半計算n p × q計算歐拉函數(shù)φ(n) (p-1) × (q-1)選擇一個整數(shù)e滿足1 e φ(n)且gcd(e, φ(n)) 1計算d滿足d × e ≡ 1 (mod φ(n))公鑰為(n, e)私鑰為(n, d)其中第一步的“隨機生成大質(zhì)數(shù)”是最關(guān)鍵的環(huán)節(jié)。具體做法是用CSPRNG生成一個指定長度的隨機奇數(shù)然后做素性檢測。常用的素性檢測算法是Miller-Rabin它有一定的誤判概率但通過多輪檢測可以將誤判概率降到可忽略的程度。這里有一個實操中的細節(jié)生成隨機奇數(shù)時最高位必須置1保證質(zhì)數(shù)的位數(shù)正確最低位必須置1保證是奇數(shù)。中間位由CSPRNG填充。這個細節(jié)看似微小但如果最高位沒置1生成的質(zhì)數(shù)可能比預(yù)期短很多直接削弱密鑰強度。4.2 ECC密鑰生成的簡潔之美ECC的密鑰生成比RSA簡潔得多選定一條標準橢圓曲線確定基點G和階n用CSPRNG生成一個隨機整數(shù)d滿足1 ≤ d ≤ n-1計算公鑰Q d × G私鑰為d公鑰為Q整個過程只需要一次隨機數(shù)生成和一次橢圓曲線乘法。沒有素性檢測沒有模逆運算速度快、實現(xiàn)簡單。這也是ECC在移動端和物聯(lián)網(wǎng)設(shè)備上受歡迎的原因之一。但簡潔不意味著可以掉以輕心。私鑰d的隨機性要求極高。如果d的生成使用了弱隨機數(shù)攻擊者可以通過格攻擊lattice attack等方法從多個簽名中恢復(fù)私鑰。歷史上一些區(qū)塊鏈項目就因為ECDSA簽名時使用了弱隨機數(shù)導(dǎo)致私鑰被批量恢復(fù)。4.3 代碼示例用Python生成密鑰對下面用Python演示如何用CSPRNG生成RSA和ECC密鑰對。注意使用的是secrets模塊和cryptography庫而不是random模塊。import secrets from cryptography.hazmat.primitives.asymmetric import rsa, ec from cryptography.hazmat.primitives import serialization # 生成RSA密鑰對 def generate_rsa_keypair(key_size2048): private_key rsa.generate_private_key( public_exponent65537, key_sizekey_size, backendNone # 使用默認后端 ) public_key private_key.public_key() return private_key, public_key # 生成ECC密鑰對 def generate_ecc_keypair(curveec.SECP256R1()): private_key ec.generate_private_key(curve) public_key private_key.public_key() return private_key, public_key # 序列化私鑰 def serialize_private_key(private_key, passwordNone): if password: encryption serialization.BestAvailableEncryption(password.encode()) else: encryption serialization.NoEncryption() return private_key.private_bytes( encodingserialization.Encoding.PEM, formatserialization.PrivateFormat.PKCS8, encryption_algorithmencryption ) # 使用示例 rsa_priv, rsa_pub generate_rsa_keypair(2048) ecc_priv, ecc_pub generate_ecc_keypair() print(RSA私鑰長度:, len(serialize_private_key(rsa_priv))) print(ECC私鑰長度:, len(serialize_private_key(ecc_priv)))這段代碼里cryptography庫底層會調(diào)用操作系統(tǒng)的CSPRNG。在Linux上它讀取/dev/urandom在Windows上它調(diào)用BCryptGenRandom。這些都是密碼學(xué)安全的隨機源。提示public_exponent65537是RSA的標準選擇。這個值不能太小比如3否則可能受到小指數(shù)攻擊也不能太大否則加密速度會變慢。65537是一個兼顧安全和效率的平衡點。5. 隨機數(shù)質(zhì)量對安全性的實際影響5.1 弱隨機數(shù)導(dǎo)致的真實攻擊模式弱隨機數(shù)導(dǎo)致的密鑰泄露在現(xiàn)實中發(fā)生過多次。最典型的攻擊模式有兩種第一種是種子空間過小。如果PRNG的種子只有32位攻擊者最多嘗試2^32種可能就能窮舉出所有可能的密鑰。這在現(xiàn)代算力下是秒級的事情。歷史上某些嵌入式設(shè)備的密鑰生成就犯過這個錯誤種子來自設(shè)備啟動時間戳的低32位攻擊者可以輕松窮舉。第二種是種子可預(yù)測。如果種子來自可預(yù)測的事件比如進程ID、當(dāng)前時間戳、或者某個固定值攻擊者可以通過觀察系統(tǒng)狀態(tài)來縮小種子搜索范圍。Debian在2006年到2008年間發(fā)生過一次著名的OpenSSL漏洞就是因為注釋掉了一行代碼導(dǎo)致PRNG的熵源被大幅削弱生成的密鑰可被預(yù)測。第三種是隨機數(shù)復(fù)用。在ECDSA簽名中每次簽名都需要一個隨機數(shù)k。如果兩次簽名使用了相同的k攻擊者可以通過簡單的代數(shù)運算直接計算出私鑰。這個錯誤在區(qū)塊鏈領(lǐng)域出現(xiàn)過多次導(dǎo)致大量資產(chǎn)被盜。5.2 如何評估隨機數(shù)質(zhì)量評估隨機數(shù)質(zhì)量可以從以下幾個維度入手統(tǒng)計隨機性通過NIST SP 800-22測試套件檢查輸出序列的頻率、游程、自相關(guān)等統(tǒng)計特性不可預(yù)測性給定部分輸出檢查是否能預(yù)測后續(xù)輸出種子強度種子的熵有多少位是否來自不可預(yù)測的物理源前向安全性即使當(dāng)前狀態(tài)泄露是否能反推出之前的輸出后向安全性即使當(dāng)前狀態(tài)泄露是否能預(yù)測未來的輸出對于開發(fā)者來說最實用的評估方法是確認使用的API是否是CSPRNG。如果不是直接換掉。不需要自己去做統(tǒng)計測試那是庫開發(fā)者的事情。5.3 不同場景下的隨機數(shù)選擇建議場景推薦方案不推薦方案原因生成RSA/ECC密鑰secrets/SecureRandom/crypto/randrandom/Math.random()密鑰必須用CSPRNG生成會話令牌secrets.token_urlsafe()UUID4某些實現(xiàn)會話令牌需要不可預(yù)測生成初始化向量os.urandom()固定值或計數(shù)器IV需要隨機且唯一生成鹽值os.urandom()用戶名或時間戳鹽值需要隨機且唯一模擬測試數(shù)據(jù)random/Math.random()CSPRNG測試數(shù)據(jù)不需要密碼學(xué)安全游戲中的隨機事件普通PRNGCSPRNG性能優(yōu)先安全無關(guān)這張表的核心邏輯是只要隨機數(shù)的可預(yù)測性會影響安全性就必須用CSPRNG否則可以用普通PRNG。判斷標準很簡單如果攻擊者猜到了這個隨機數(shù)會不會造成安全問題會就用CSPRNG不會就隨意。6. 常見問題與排查技巧實錄6.1 密鑰生成速度慢怎么辦RSA密鑰生成尤其是4096位密鑰在低性能設(shè)備上可能需要幾秒甚至幾十秒。這不是bug是正?，F(xiàn)象。質(zhì)數(shù)生成本身就需要反復(fù)嘗試位數(shù)越大找到質(zhì)數(shù)的平均嘗試次數(shù)越多。如果速度成為瓶頸可以考慮以下方案降低密鑰長度。2048位RSA在當(dāng)前算力下仍然安全4096位是過度設(shè)計改用ECC。256位ECC密鑰的安全強度約等于3072位RSA但生成速度快幾個數(shù)量級預(yù)生成密鑰池。在系統(tǒng)空閑時預(yù)生成一批密鑰需要時直接取用使用硬件加速。某些CPU有專門的指令集加速大數(shù)運算注意不要為了速度而降低隨機數(shù)質(zhì)量。用弱隨機數(shù)生成的密鑰生成再快也沒有意義。6.2 熵不足的典型癥狀與解決熵不足的典型癥狀是密鑰生成阻塞、/dev/random讀取緩慢、系統(tǒng)啟動后一段時間內(nèi)隨機數(shù)質(zhì)量下降。在虛擬機、容器、嵌入式設(shè)備中尤其常見。排查方法# 查看當(dāng)前熵池大小 cat /proc/sys/kernel/random/entropy_avail # 查看熵池容量 cat /proc/sys/kernel/random/poolsize如果entropy_avail長期低于200說明熵池處于低熵狀態(tài)。解決方法包括安裝haveged用CPU時間抖動作為熵源安裝rng-tools如果有硬件隨機數(shù)生成器用它來補充熵池在虛擬機中確保宿主機啟用了熵傳遞功能在容器中確保/dev/urandom可訪問6.3 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案密鑰生成阻塞熵池不足查看entropy_avail補充熵源密鑰可被預(yù)測使用了弱PRNG檢查代碼中的隨機數(shù)API換用CSPRNGECDSA簽名私鑰泄露隨機數(shù)k復(fù)用檢查簽名實現(xiàn)使用RFC 6979確定性簽名不同設(shè)備密鑰相同種子相同檢查種子來源使用設(shè)備唯一熵源密鑰生成速度慢密鑰長度過大檢查密鑰長度配置降低到2048位或改用ECC隨機數(shù)序列重復(fù)PRNG狀態(tài)被重置檢查PRNG初始化邏輯確保種子只初始化一次6.4 一個容易被忽略的坑fork后的隨機數(shù)狀態(tài)在Unix-like系統(tǒng)中fork()創(chuàng)建子進程后子進程會繼承父進程的PRNG狀態(tài)。如果父子進程都繼續(xù)使用同一個PRNG生成隨機數(shù)它們會產(chǎn)生相同的序列。這在多進程服務(wù)器中是一個隱蔽的安全漏洞。解決方法是在fork()之后子進程重新初始化PRNG或者使用操作系統(tǒng)提供的CSPRNG它內(nèi)部會處理fork安全問題。OpenSSL的RAND_bytes在fork后會檢測PID變化并重新播種但自己實現(xiàn)的PRNG往往沒有這個保護。提示如果你在寫多進程程序并且自己實現(xiàn)了PRNG務(wù)必在fork()后的子進程中重新播種。最簡單的方法是混入子進程的PID和當(dāng)前時間戳。7. 公鑰密碼學(xué)與隨機數(shù)的未來走向后量子密碼學(xué)是當(dāng)前密碼學(xué)領(lǐng)域的熱點方向。量子計算機對RSA和ECC構(gòu)成實質(zhì)性威脅因為Shor算法可以在多項式時間內(nèi)解決大整數(shù)分解和離散對數(shù)問題。后量子密碼學(xué)的候選算法如基于格的密碼學(xué)、基于編碼的密碼學(xué)、多變量密碼學(xué)同樣依賴隨機數(shù)來生成密鑰。有意思的是后量子密碼學(xué)對隨機數(shù)的需求不僅沒有減少反而增加了。因為很多后量子算法的密鑰尺寸更大密鑰生成過程中需要更多的隨機數(shù)。同時一些后量子算法對隨機數(shù)的質(zhì)量更加敏感弱隨機數(shù)可能導(dǎo)致密鑰完全暴露。另一個趨勢是硬件隨機數(shù)生成器的普及。現(xiàn)代CPU如Intel的RdRand指令、AMD的RDRAND指令已經(jīng)集成了硬件隨機數(shù)生成器可以直接從CPU獲取高質(zhì)量的隨機數(shù)。操作系統(tǒng)和密碼學(xué)庫也在逐步適配這些硬件特性減少對熵池的依賴。對于開發(fā)者來說核心原則沒有變密鑰生成必須用CSPRNG不要自己造輪子不要用非密碼學(xué)安全的隨機數(shù)API。這個原則在過去二十年沒有變在未來二十年大概率也不會變。我在實際項目中遇到過幾次因為隨機數(shù)問題導(dǎo)致的密鑰安全事件每次追溯到最后都是某個環(huán)節(jié)用了不該用的隨機數(shù)API。最離譜的一次是有人用Math.random()生成AES密鑰還覺得“看起來挺隨機的”。隨機數(shù)這件事看起來簡單但真正理解其安全含義的人并不多。希望這篇內(nèi)容能幫你把這塊知識補上下次寫密鑰生成代碼的時候能多想一步我用的這個隨機數(shù)真的夠隨機嗎 公鑰密碼學(xué)與偽隨機數(shù)：密鑰生成中的隨機源與熵池管理
1. 從一個看似矛盾的問題說起公鑰密碼學(xué)里有一個特別反直覺的事實你用來加密的密鑰是公開的任何人都能拿到但別人依然解不開你的密文。這件事第一次接觸會覺得像魔術(shù)但支撐它的數(shù)學(xué)基礎(chǔ)其實相當(dāng)樸素——單向函數(shù)。正向計算容易反向計算在算力上不可行。RSA依賴大整數(shù)分解橢圓曲線依賴離散對數(shù)它們都是這類函數(shù)的實例。但這里有個容易被忽略的環(huán)節(jié)密鑰是怎么來的。如果生成密鑰的那個隨機數(shù)本身不夠隨機整個公鑰體系的安全性就是紙糊的。我見過不少開發(fā)者算法選型很講究參數(shù)配置也到位結(jié)果栽在隨機數(shù)生成上。這篇文章就圍繞公鑰密碼學(xué)和偽隨機數(shù)之間的關(guān)系展開把密鑰生成、隨機源選擇、熵池管理這些環(huán)節(jié)拆開講清楚。適合有一定編程基礎(chǔ)、正在做安全相關(guān)功能、或者單純想搞明白“隨機數(shù)為什么能決定加密強度”的讀者。2. 公鑰密碼學(xué)的核心機制拆解2.1 對稱加密的困境與公鑰的破局思路對稱加密的邏輯很直接一把鑰匙開一把鎖加密解密用同一個密鑰。問題在于通信雙方怎么安全地把這把鑰匙交到對方手里。如果雙方能面對面交換那沒問題但如果隔著網(wǎng)絡(luò)你沒法保證傳輸通道本身是安全的。這就是經(jīng)典的密鑰分發(fā)難題。公鑰密碼學(xué)的破局思路是把密鑰拆成一對公鑰和私鑰。公鑰可以隨便公開私鑰只有自己持有。別人用你的公鑰加密你用私鑰解密。反過來你用私鑰簽名別人用公鑰驗證。整個過程中私鑰永遠不需要傳輸密鑰分發(fā)問題從根上被繞開了。這個設(shè)計的美妙之處在于它把“保密”這件事從傳輸環(huán)節(jié)轉(zhuǎn)移到了數(shù)學(xué)計算環(huán)節(jié)。你不需要保護公鑰的傳輸因為公鑰泄露不影響安全性。你只需要保護私鑰不被竊取。安全邊界從“通道”收縮到了“本地存儲”可控性大幅提升。2.2 單向函數(shù)公鑰密碼學(xué)的數(shù)學(xué)地基公鑰密碼學(xué)的安全性建立在單向函數(shù)之上。所謂單向函數(shù)就是正向計算很簡單反向求解在計算上不可行。注意這里的“不可行”不是理論上的不可能而是指以當(dāng)前已知的最佳算法和算力水平求解所需的時間超出了實際意義。以RSA為例。選兩個大質(zhì)數(shù)p和q計算n p × q這一步對計算機來說瞬間完成。但如果只知道n要反推出p和q當(dāng)n足夠大時比如2048位目前最好的分解算法也需要天文數(shù)字的時間。這就是RSA的安全基礎(chǔ)。橢圓曲線密碼學(xué)ECC用的是另一類單向函數(shù)橢圓曲線上的離散對數(shù)問題。在特定橢圓曲線上已知基點G和私鑰k計算公鑰K kG很容易但已知G和K求k在計算上不可行。ECC的優(yōu)勢在于達到同等安全強度所需的密鑰長度遠小于RSA。256位的ECC密鑰大約等價于3072位的RSA密鑰這對資源受限的環(huán)境非常友好。2.3 密鑰生成隨機數(shù)登場的時刻到這里隨機數(shù)還沒有正式出場。但密鑰生成這一步隨機數(shù)是絕對的主角。以RSA為例生成密鑰的第一步是選兩個大質(zhì)數(shù)p和q。這兩個質(zhì)數(shù)怎么來不是從質(zhì)數(shù)表里挑而是隨機生成一個大奇數(shù)然后做素性檢測不是質(zhì)數(shù)就換一個繼續(xù)試。這個“隨機生成”的過程用的就是隨機數(shù)生成器。ECC的密鑰生成更直接私鑰k就是一個隨機數(shù)在橢圓曲線的階的范圍內(nèi)隨機選取。公鑰K由k計算得出。如果k的隨機性不夠攻擊者可以通過窮舉或統(tǒng)計分析縮小搜索范圍私鑰就可能被推出來。所以隨機數(shù)的質(zhì)量直接決定了密鑰的質(zhì)量密鑰的質(zhì)量直接決定了整個公鑰體系的安全上限。算法再強隨機數(shù)不行一切白搭。3. 偽隨機數(shù)的真相不是真隨機但夠用3.1 真隨機與偽隨機的本質(zhì)區(qū)別嚴格來說計算機里沒有真正的隨機。計算機是確定性系統(tǒng)給定相同的輸入和狀態(tài)輸出必然相同。所謂“隨機數(shù)”要么來自物理世界的不可預(yù)測現(xiàn)象要么來自算法對種子的確定性變換。真隨機數(shù)生成器TRNG依賴物理熵源熱噪聲、光電效應(yīng)、放射性衰變的時間間隔等。這些現(xiàn)象在量子層面本質(zhì)上是不可預(yù)測的所以TRNG的輸出具有真正的隨機性。但TRNG的問題是速度慢、成本高而且不是所有環(huán)境都能提供高質(zhì)量的物理熵源。偽隨機數(shù)生成器PRNG則是純算法。給定一個種子它通過確定性算法生成一長串看起來隨機的數(shù)字序列。如果種子相同輸出序列完全相同。PRNG的優(yōu)點是速度快、可復(fù)現(xiàn)、實現(xiàn)簡單。缺點是如果種子被猜到或泄露整個序列都可被預(yù)測。3.2 密碼學(xué)安全偽隨機數(shù)生成器CSPRNG普通PRNG和CSPRNG的區(qū)別就像普通鎖和防盜鎖的區(qū)別。普通PRNG比如線性同余生成器的設(shè)計目標是統(tǒng)計特性好、速度快不關(guān)心抗攻擊能力。CSPRNG則必須滿足兩個額外條件一是給定部分輸出無法推算出后續(xù)輸出二是給定內(nèi)部狀態(tài)無法反推出之前的輸出。CSPRNG的典型構(gòu)造方式包括基于密碼學(xué)哈希函數(shù)如SHA-256的構(gòu)造、基于分組密碼如AES-CTR模式的構(gòu)造、以及專門設(shè)計的流密碼如ChaCha20。這些構(gòu)造的共同特點是即使攻擊者獲得了部分輸出也無法有效預(yù)測其余部分。在實際開發(fā)中選擇CSPRNG是密鑰生成的底線要求。Python的secrets模塊、Java的SecureRandom、Go的crypto/rand、OpenSSL的RAND_bytes這些都是CSPRNG的實現(xiàn)。而random模塊、Math.random()、C語言的rand()這些都不是密碼學(xué)安全的絕對不能用于密鑰生成。3.3 熵池隨機數(shù)的“水庫”操作系統(tǒng)層面隨機數(shù)的來源通常是一個熵池。Linux的/dev/random和/dev/urandom就是熵池的兩個接口。/dev/random在熵不足時會阻塞直到收集到足夠的熵/dev/urandom則不阻塞熵不足時用CSPRNG繼續(xù)生成。熵的來源包括鍵盤敲擊的時間間隔、鼠標移動軌跡、磁盤I/O的完成時間、網(wǎng)絡(luò)中斷的到達時間等。這些事件的時間戳具有足夠的不可預(yù)測性被內(nèi)核收集后混入熵池。這里有個常見的誤區(qū)很多人認為/dev/urandom不如/dev/random安全。實際上在現(xiàn)代Linux內(nèi)核中一旦熵池完成初始化/dev/urandom的輸出在密碼學(xué)上是安全的。/dev/random的阻塞行為在大多數(shù)場景下只會帶來不必要的性能問題。只有在系統(tǒng)剛啟動、熵池尚未初始化完成的極短窗口內(nèi)/dev/urandom的輸出才可能不夠安全。注意在嵌入式設(shè)備或虛擬機中熵源可能非常有限。系統(tǒng)啟動后熵池可能長時間處于低熵狀態(tài)。這種情況下建議使用haveged或rng-tools等工具補充熵或者在應(yīng)用層使用硬件隨機數(shù)生成器。4. 密鑰生成實操從隨機數(shù)到密鑰對4.1 RSA密鑰生成的完整流程RSA密鑰生成的核心步驟可以拆解為以下幾個環(huán)節(jié)隨機生成兩個大質(zhì)數(shù)p和q長度各為密鑰長度的一半計算n p × q計算歐拉函數(shù)φ(n) (p-1) × (q-1)選擇一個整數(shù)e滿足1 e φ(n)且gcd(e, φ(n)) 1計算d滿足d × e ≡ 1 (mod φ(n))公鑰為(n, e)私鑰為(n, d)其中第一步的“隨機生成大質(zhì)數(shù)”是最關(guān)鍵的環(huán)節(jié)。具體做法是用CSPRNG生成一個指定長度的隨機奇數(shù)然后做素性檢測。常用的素性檢測算法是Miller-Rabin它有一定的誤判概率但通過多輪檢測可以將誤判概率降到可忽略的程度。這里有一個實操中的細節(jié)生成隨機奇數(shù)時最高位必須置1保證質(zhì)數(shù)的位數(shù)正確最低位必須置1保證是奇數(shù)。中間位由CSPRNG填充。這個細節(jié)看似微小但如果最高位沒置1生成的質(zhì)數(shù)可能比預(yù)期短很多直接削弱密鑰強度。4.2 ECC密鑰生成的簡潔之美ECC的密鑰生成比RSA簡潔得多選定一條標準橢圓曲線確定基點G和階n用CSPRNG生成一個隨機整數(shù)d滿足1 ≤ d ≤ n-1計算公鑰Q d × G私鑰為d公鑰為Q整個過程只需要一次隨機數(shù)生成和一次橢圓曲線乘法。沒有素性檢測沒有模逆運算速度快、實現(xiàn)簡單。這也是ECC在移動端和物聯(lián)網(wǎng)設(shè)備上受歡迎的原因之一。但簡潔不意味著可以掉以輕心。私鑰d的隨機性要求極高。如果d的生成使用了弱隨機數(shù)攻擊者可以通過格攻擊lattice attack等方法從多個簽名中恢復(fù)私鑰。歷史上一些區(qū)塊鏈項目就因為ECDSA簽名時使用了弱隨機數(shù)導(dǎo)致私鑰被批量恢復(fù)。4.3 代碼示例用Python生成密鑰對下面用Python演示如何用CSPRNG生成RSA和ECC密鑰對。注意使用的是secrets模塊和cryptography庫而不是random模塊。import secrets from cryptography.hazmat.primitives.asymmetric import rsa, ec from cryptography.hazmat.primitives import serialization # 生成RSA密鑰對 def generate_rsa_keypair(key_size2048): private_key rsa.generate_private_key( public_exponent65537, key_sizekey_size, backendNone # 使用默認后端 ) public_key private_key.public_key() return private_key, public_key # 生成ECC密鑰對 def generate_ecc_keypair(curveec.SECP256R1()): private_key ec.generate_private_key(curve) public_key private_key.public_key() return private_key, public_key # 序列化私鑰 def serialize_private_key(private_key, passwordNone): if password: encryption serialization.BestAvailableEncryption(password.encode()) else: encryption serialization.NoEncryption() return private_key.private_bytes( encodingserialization.Encoding.PEM, formatserialization.PrivateFormat.PKCS8, encryption_algorithmencryption ) # 使用示例 rsa_priv, rsa_pub generate_rsa_keypair(2048) ecc_priv, ecc_pub generate_ecc_keypair() print(RSA私鑰長度:, len(serialize_private_key(rsa_priv))) print(ECC私鑰長度:, len(serialize_private_key(ecc_priv)))這段代碼里cryptography庫底層會調(diào)用操作系統(tǒng)的CSPRNG。在Linux上它讀取/dev/urandom在Windows上它調(diào)用BCryptGenRandom。這些都是密碼學(xué)安全的隨機源。提示public_exponent65537是RSA的標準選擇。這個值不能太小比如3否則可能受到小指數(shù)攻擊也不能太大否則加密速度會變慢。65537是一個兼顧安全和效率的平衡點。5. 隨機數(shù)質(zhì)量對安全性的實際影響5.1 弱隨機數(shù)導(dǎo)致的真實攻擊模式弱隨機數(shù)導(dǎo)致的密鑰泄露在現(xiàn)實中發(fā)生過多次。最典型的攻擊模式有兩種第一種是種子空間過小。如果PRNG的種子只有32位攻擊者最多嘗試2^32種可能就能窮舉出所有可能的密鑰。這在現(xiàn)代算力下是秒級的事情。歷史上某些嵌入式設(shè)備的密鑰生成就犯過這個錯誤種子來自設(shè)備啟動時間戳的低32位攻擊者可以輕松窮舉。第二種是種子可預(yù)測。如果種子來自可預(yù)測的事件比如進程ID、當(dāng)前時間戳、或者某個固定值攻擊者可以通過觀察系統(tǒng)狀態(tài)來縮小種子搜索范圍。Debian在2006年到2008年間發(fā)生過一次著名的OpenSSL漏洞就是因為注釋掉了一行代碼導(dǎo)致PRNG的熵源被大幅削弱生成的密鑰可被預(yù)測。第三種是隨機數(shù)復(fù)用。在ECDSA簽名中每次簽名都需要一個隨機數(shù)k。如果兩次簽名使用了相同的k攻擊者可以通過簡單的代數(shù)運算直接計算出私鑰。這個錯誤在區(qū)塊鏈領(lǐng)域出現(xiàn)過多次導(dǎo)致大量資產(chǎn)被盜。5.2 如何評估隨機數(shù)質(zhì)量評估隨機數(shù)質(zhì)量可以從以下幾個維度入手統(tǒng)計隨機性通過NIST SP 800-22測試套件檢查輸出序列的頻率、游程、自相關(guān)等統(tǒng)計特性不可預(yù)測性給定部分輸出檢查是否能預(yù)測后續(xù)輸出種子強度種子的熵有多少位是否來自不可預(yù)測的物理源前向安全性即使當(dāng)前狀態(tài)泄露是否能反推出之前的輸出后向安全性即使當(dāng)前狀態(tài)泄露是否能預(yù)測未來的輸出對于開發(fā)者來說最實用的評估方法是確認使用的API是否是CSPRNG。如果不是直接換掉。不需要自己去做統(tǒng)計測試那是庫開發(fā)者的事情。5.3 不同場景下的隨機數(shù)選擇建議場景推薦方案不推薦方案原因生成RSA/ECC密鑰secrets/SecureRandom/crypto/randrandom/Math.random()密鑰必須用CSPRNG生成會話令牌secrets.token_urlsafe()UUID4某些實現(xiàn)會話令牌需要不可預(yù)測生成初始化向量os.urandom()固定值或計數(shù)器IV需要隨機且唯一生成鹽值os.urandom()用戶名或時間戳鹽值需要隨機且唯一模擬測試數(shù)據(jù)random/Math.random()CSPRNG測試數(shù)據(jù)不需要密碼學(xué)安全游戲中的隨機事件普通PRNGCSPRNG性能優(yōu)先安全無關(guān)這張表的核心邏輯是只要隨機數(shù)的可預(yù)測性會影響安全性就必須用CSPRNG否則可以用普通PRNG。判斷標準很簡單如果攻擊者猜到了這個隨機數(shù)會不會造成安全問題會就用CSPRNG不會就隨意。6. 常見問題與排查技巧實錄6.1 密鑰生成速度慢怎么辦RSA密鑰生成尤其是4096位密鑰在低性能設(shè)備上可能需要幾秒甚至幾十秒。這不是bug是正?，F(xiàn)象。質(zhì)數(shù)生成本身就需要反復(fù)嘗試位數(shù)越大找到質(zhì)數(shù)的平均嘗試次數(shù)越多。如果速度成為瓶頸可以考慮以下方案降低密鑰長度。2048位RSA在當(dāng)前算力下仍然安全4096位是過度設(shè)計改用ECC。256位ECC密鑰的安全強度約等于3072位RSA但生成速度快幾個數(shù)量級預(yù)生成密鑰池。在系統(tǒng)空閑時預(yù)生成一批密鑰需要時直接取用使用硬件加速。某些CPU有專門的指令集加速大數(shù)運算注意不要為了速度而降低隨機數(shù)質(zhì)量。用弱隨機數(shù)生成的密鑰生成再快也沒有意義。6.2 熵不足的典型癥狀與解決熵不足的典型癥狀是密鑰生成阻塞、/dev/random讀取緩慢、系統(tǒng)啟動后一段時間內(nèi)隨機數(shù)質(zhì)量下降。在虛擬機、容器、嵌入式設(shè)備中尤其常見。排查方法# 查看當(dāng)前熵池大小 cat /proc/sys/kernel/random/entropy_avail # 查看熵池容量 cat /proc/sys/kernel/random/poolsize如果entropy_avail長期低于200說明熵池處于低熵狀態(tài)。解決方法包括安裝haveged用CPU時間抖動作為熵源安裝rng-tools如果有硬件隨機數(shù)生成器用它來補充熵池在虛擬機中確保宿主機啟用了熵傳遞功能在容器中確保/dev/urandom可訪問6.3 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案密鑰生成阻塞熵池不足查看entropy_avail補充熵源密鑰可被預(yù)測使用了弱PRNG檢查代碼中的隨機數(shù)API換用CSPRNGECDSA簽名私鑰泄露隨機數(shù)k復(fù)用檢查簽名實現(xiàn)使用RFC 6979確定性簽名不同設(shè)備密鑰相同種子相同檢查種子來源使用設(shè)備唯一熵源密鑰生成速度慢密鑰長度過大檢查密鑰長度配置降低到2048位或改用ECC隨機數(shù)序列重復(fù)PRNG狀態(tài)被重置檢查PRNG初始化邏輯確保種子只初始化一次6.4 一個容易被忽略的坑fork后的隨機數(shù)狀態(tài)在Unix-like系統(tǒng)中fork()創(chuàng)建子進程后子進程會繼承父進程的PRNG狀態(tài)。如果父子進程都繼續(xù)使用同一個PRNG生成隨機數(shù)它們會產(chǎn)生相同的序列。這在多進程服務(wù)器中是一個隱蔽的安全漏洞。解決方法是在fork()之后子進程重新初始化PRNG或者使用操作系統(tǒng)提供的CSPRNG它內(nèi)部會處理fork安全問題。OpenSSL的RAND_bytes在fork后會檢測PID變化并重新播種但自己實現(xiàn)的PRNG往往沒有這個保護。提示如果你在寫多進程程序并且自己實現(xiàn)了PRNG務(wù)必在fork()后的子進程中重新播種。最簡單的方法是混入子進程的PID和當(dāng)前時間戳。7. 公鑰密碼學(xué)與隨機數(shù)的未來走向后量子密碼學(xué)是當(dāng)前密碼學(xué)領(lǐng)域的熱點方向。量子計算機對RSA和ECC構(gòu)成實質(zhì)性威脅因為Shor算法可以在多項式時間內(nèi)解決大整數(shù)分解和離散對數(shù)問題。后量子密碼學(xué)的候選算法如基于格的密碼學(xué)、基于編碼的密碼學(xué)、多變量密碼學(xué)同樣依賴隨機數(shù)來生成密鑰。有意思的是后量子密碼學(xué)對隨機數(shù)的需求不僅沒有減少反而增加了。因為很多后量子算法的密鑰尺寸更大密鑰生成過程中需要更多的隨機數(shù)。同時一些后量子算法對隨機數(shù)的質(zhì)量更加敏感弱隨機數(shù)可能導(dǎo)致密鑰完全暴露。另一個趨勢是硬件隨機數(shù)生成器的普及。現(xiàn)代CPU如Intel的RdRand指令、AMD的RDRAND指令已經(jīng)集成了硬件隨機數(shù)生成器可以直接從CPU獲取高質(zhì)量的隨機數(shù)。操作系統(tǒng)和密碼學(xué)庫也在逐步適配這些硬件特性減少對熵池的依賴。對于開發(fā)者來說核心原則沒有變密鑰生成必須用CSPRNG不要自己造輪子不要用非密碼學(xué)安全的隨機數(shù)API。這個原則在過去二十年沒有變在未來二十年大概率也不會變。我在實際項目中遇到過幾次因為隨機數(shù)問題導(dǎo)致的密鑰安全事件每次追溯到最后都是某個環(huán)節(jié)用了不該用的隨機數(shù)API。最離譜的一次是有人用Math.random()生成AES密鑰還覺得“看起來挺隨機的”。隨機數(shù)這件事看起來簡單但真正理解其安全含義的人并不多。希望這篇內(nèi)容能幫你把這塊知識補上下次寫密鑰生成代碼的時候能多想一步我用的這個隨機數(shù)真的夠隨機嗎