面向軟件的隨機數發生器設計和實現

彭金輝，張志鴻

(1.鄭州信大捷安信息技術股份有限公司 集成電路設計中心，河南 鄭州 450004；2.鄭州大學 計算機與人工智能學院，河南 鄭州 450001)

0 引 言

軟件密碼模塊主要為解決移動智能終端在開放環境下的信息安全問題而設計，隨機數發生器是其關鍵部件[1]。當前已有諸多軟件密碼模塊隨機數的產生方法，多依賴于操作系統，且形式多樣、安全程度不一。馬原等[1]從黑盒檢測等角度分析了通用操作系統內核所帶的軟件隨機數發生器，存在熵不足的問題。韓冬磊等[2]提出了一種基于可信執行環境的偽隨機數生成方案。劉攀等[3]從軟件隨機數發生器安全性的角度分析了通用操作系統平臺中軟件隨機數發生器的基本結構和工作原理。劉攀等[4]還針對通用操作系統自帶隨機數發生器存在熵源不足的問題，提出了一種帶有熵監控功能的軟件隨機數發生器。為解決上述問題，本文提出了一種基于多熵源的隨機數發生器[5]方案，該方案使用系統熵池、本地隨機數池和服務端真隨機數作為熵源的3個組成部分，以保證有足夠的熵。

本文首先描述了該方案的初始隨機數產生原理，然后給出初始隨機數的具體產生過程，并給出了實現方法，最后給出了安全通道分析和隨機數質量分析。

1 初始隨機數產生原理

軟件隨機數發生器產生的隨機數按用途分為3種：第一種是初始隨機性，通過客戶端和服務端建立初始安全通道時通過協商和計算得到，主要用作隨機數種子；第二種是建立安全通道后從服務端采集的真隨機數，主要用于更新本地隨機數池；第三種是基于隨機數種子和密碼算法產生的偽隨機性，主要用于滿足應用程序的高速率隨機數需求。下面說明本方案產生初始隨機數的3個熵源。

1.1 操作系統熵池

操作系統通常會提供一個內嵌的機制來產生隨機數，稱之為系統熵池，它表示當前操作系統運行的環境噪音和系統的混亂程度，由多個方面組成，比如鼠標和鍵盤及觸屏的活動、磁盤的I/O操作、內存的使用量、文件的使用量、不同類型的進程數量、特定的中斷等。產生的這些隨機比特位在緩沖池內組合得到原始隨機流，然后進行編碼處理以避免隨環境變化產生傾向性偏差，確保得到基本穩定的獨立均勻分布的數據流。當需要取隨機數時，從緩沖池讀取適量的比特傳給HASH函數。Linux系統熵池通過文件/dev/random獲取隨機比特流實現。Windows系統熵池通過微軟提供的CryptGenRandom實用工具生成隨機數來實現。

1.2 本地隨機數池

指在設備終端保存的一次性隨機數。在軟件密碼模塊客戶端初始化時生成，隨機數由服務端物理噪聲源產生，使用PIN口令派生密鑰加密保存在軟件密碼模塊所在客戶端設備中，加密算法使用SM4。每次產生初始隨機數時，選取若干字節使用。如使用超過閾值，需要通過安全通道更新。

1.3 服務端采集的隨機數

指由服務端物理噪聲源產生的真隨機數。在客戶端登錄建立安全通道過程中，客戶端先發送Client Hello消息，帶有PIN口令摘要值的密文等信息。服務端先驗證PIN口令是否正確，然后從物理噪聲源采集隨機數，并使用PIN口令派生密鑰加密，放在Server Hello消息中返回。

2 隨機數產生過程

2.1 初始化過程

軟件密碼模塊客戶端需要先初始化才能使用，初始化需要在安全環境下進行。主要完成以下工作：

客戶端發起初始化請求，并出示客戶端身份標識。

服務端使用物理噪聲源產生池子需求大小的真隨機數，并使用默認PIN口令派生密鑰key0加密。

客戶端把該文件保存在所在智能終端文件系統中，并把初始游標置為0。

初始化完成之后，管理員即可把智能終端交付給用戶在工作網絡環境下使用。

用戶首次使用軟件密碼模塊時，需要先產生初始隨機數并建立和服務端之間的安全通道，然后基于安全通道修改默認PIN口令。

2.2 初始隨機數產生過程

基于客戶端A和服務端B，初始隨機數的具體產生過程如下：

客戶端A進行如下操作：

A1：用戶輸入PIN口令登錄，計算PIN口令摘要值hash1，并使用hash1的前16字節作為PIN口令派生密鑰key1，然后使用key1對hash1進行SM4加密，得到PIN口令摘要值的密文HASH1。

A2：使用key1解密本地隨機數池，讀取16字節隨機數cr0，并后移游標。

A3：將客戶端身份標識(如IMEI號、硬盤序列號)、HASH1、隨機數cr0、客戶端時間戳NA通過Client Hello消息發給服務端。

服務端B進行如下操作：

B1：收到Client Hello消息后，先驗證用戶PIN口令，驗證方法是用hash1和數據庫中存儲的特定身份標識客戶端的PIN碼摘要值(記作SPH)比對，驗證失敗返回錯誤。

B2：從物理噪聲源采集16字節隨機數sr0，并用SPH的前16字節作為PIN口令派生密鑰key2，使用key2加密sr0加密得到SR0。

B3：將服務端證書、SR0、服務端時間戳NB通過Server Hello消息返回給客戶端。

客戶端A進行如下操作：

A4：使用CA證書鏈驗證服務端證書的合法性，若驗證失敗返回錯誤。

A5：使用PIN口令派生密鑰key1解密SR0得到sr0，sr0作為第一熵源。

A6：使用從本地隨機出池讀取的cr0作為第二熵源；判斷游標位置，如超過8 KB，第A9步完成后執行本地隨機數池更新流程。

A7：從系統熵池讀取16字節隨機數rd0，作為第三熵源。

A8：使用式(1)計算r0，并使用SM3算法其摘要值，記為h1(32字節)，即h1=SM3(r0)

r0=rd0⊕cr0⊕sr0

(1)

A9：對h1的前16字節和后16字節進行異或，得到r1作為初始隨機數。

r1的完整產生流程如圖1所示。

圖1 初始隨機數產生及安全通道建立過程

2.3 建立安全通道

使用初始隨機數可以建立客戶端A和服務端B之間的安全通道。

客戶端A進行如下操作：

A10：使用服務端公鑰PKB對r1進行SM2加密得到R1，發送到服務端

R1={r1}PKB

(2)

服務端B進行如下操作：

B4：使用私鑰SKB進行SM2解密R1，得到r′1

r′1={R1}SKB

(3)

B5：使用r′1做KDF運算的結果k1作為密鑰使用SM4算法加密握手消息msg，得到MSG。

客戶端A進行如下操作：

A11：收到握手消息密文MSG，使用r1做KDF運算的結果k′1作為密鑰使用SM4算法解密得到msg’，和msg比對，比對成功代表協商成功，后續通信使用此會話密鑰加密；否則返回失敗。

建立安全通道的流程如圖1所示。

KDF運算，指使用r1作為密鑰對客戶端隨機數cr0、服務端隨機數sr0、握手數據進行SM4加密運算

k1={cr0，sr0，msg}Kr1

(4)

2.4 更新本地隨機數池

更新方法是先建立軟件密碼模塊客戶端和服務端之間的安全通道，然后從服務端采集16字節真隨機數作為種子，并產生池子大小的隨機數序列，對本地隨機數池進行全量替換。產生偽隨機序列的方法是使用SM3算法對16字節真隨機數計算摘要，輸出32字節值作為隨機數，同時作為新的輸入，如此循環SM3運算，一直到產生池子大小的隨機序列。

具體流程如圖2所示。

圖2 本地隨機數池更新過程

2.5 加密傳輸業務數據

在軟件密碼模塊中，基于安全通道加密傳輸的業務數據包括修改用戶PIN口令、解鎖用戶PIN口令、遠程啟用/停用軟件密碼模塊、私鑰協同運算[6，7]等。

其中私鑰協同運算通過密鑰分割、分存分算的思想實現，即私鑰分割為兩份，客戶端和服務端各存儲一份，私鑰產生過程、簽名運算過程、解密運算過程需要客戶端、服務端協同完成，協同運算的中間數據要通過安全通道加密傳輸。

3 實現設計和性能評估

3.1 模型設計

按照NIST SP800-90B[12]隨機數發生器的分類，本方案設計的隨機數發生器是非確定隨機數發生器(NRBG)，也是真隨機數發生器(TRBG)。參照NIST SP800-90C[13]，本方案設計的隨機數發生器的模型如圖3所示。該模型中操作系統熵池作為硬件噪聲源輸出的是真隨機數[14]，本地隨機池預置的也是真隨機數，服務端通過安全通道提供的也是真隨機數，三者組合并經過處理產生初始隨機數。

圖3 NRBG模型

調整模塊為了滿足應用高速產生隨機數的需求，使用初始隨機數作為種子，使用SM3算法計算輸出偽隨機數。

A點和B點各帶一個隨機數測試模塊，A點對初始隨機數執行重復計數測試，B點對輸出的隨機數做隨機性測試(M=2的撲克測試)。

下面說明一下重復計數測試，對樣本最小熵為H位的噪聲源，有

Pr[在一列位中連續C位相同]≤(2-H)(C-1)

(5)

本方案采用的M=2的撲克測試，指長度為2的子序列有22種，即00、01、10、11，以長度2劃分待檢序列，檢測上述4種子序列的個數是否接近。

3.2 軟件架構設計

下面給出本方案的具體實現，客戶端以SDK的形式提供給軟件密碼模塊使用，支持Linux、Android、Windows等多種操作系統；服務端配備PCI-E密碼卡。

本方案通過C語言編碼實現，客戶端的軟件模塊架構包括軟件隨機數發生器、隨機數池管理模塊、本地隨機數池、網絡通信模塊、系統熵池管理模塊、SM4運算模塊、SM3運算模塊、PIN口令管理模塊、設備標識管理模塊。服務端軟件架構包括Server模塊、網絡通信模塊、數據庫模塊、PCI-E密碼卡。如圖4所示。

圖4 軟件模塊架構

客戶端部分，隨機數發生器對外提供產生隨機數接口，支持產生指定比特長度的隨機數。設備標識管理模塊提供獲取客戶端所在智能終端設備硬件唯一標識的接口。PIN口令管理模塊在密碼模塊登錄時提供用戶PIN口令輸入驗證，PIN口令派生密鑰用于保護本地隨機數池等敏感安全參數資源。網絡通信模塊負責安全通道的建立。系統熵池管理模塊提供從操作系統熵池獲取隨機數接口。隨機數池管理模塊提供智能終端本地隨機數池管理。運算模塊提供SM4加解密和SM3摘要運算等基礎運算功能。

服務端部分，數據庫模塊提供客戶端設備標識管理、PIN口令管理等功能，支持多個客戶端。PCI-E密碼卡提供硬件隨機數發生器和SM3/SM4基礎密碼運算。

3.3 性能評估

在華為Mate30智能終端上，實測了產生初始隨機數、建立安全通道的各個階段的平均耗時統計，見表1。

表1 實測平均性能

在該設備上SM2加密性能是724次/s，驗簽性能是805次/s，服務端SM2解密性能是6972次/s；對稱運算SM4和摘要運算SM3性能均超過80 MB/s，和SM2運算性能不在一個數量級，整體性能評估時可忽略[8]。產生初始隨機數種子階段，客戶端的主要操作是一次SM2驗簽；建立安全通道階段客戶端執行一次SM2加密，服務端執行一次SM2解密；網絡交互在穩定場景下耗時1 ms左右。可見表1中實測的各種性能數據是符合預期的。

3.4 應用場景

本方案適用于在開放環境下移動智能終端軟件密碼模塊產品，下面以鄭州信大捷安研制的軟件密碼模塊產品[4]為例說明。該產品的設備序列號采用智能終端IMEI號。客戶端部署在移動智能終端上，與業務APP集成，向應用提供密碼服務；服務端形態為硬件密碼模塊。私鑰產生和私鑰簽名采用協同運算的方法[6，7]，運算過程中的隨機數由本方案的隨機數發生器提供，如圖5所示。

圖5 軟件密碼模塊架構

該方案可解決業務應用身份認證、數字簽名、數據加密等安全需求，安全級別不低于智能密碼鑰匙，且無需增加額外硬件。

4 安全通道分析

本方案的安全通道是客戶端認證服務端的單向安全通道，下面參考有關文獻[10，11]的方法對該安全通道進行BAN邏輯分析。用符號A表示客戶端、B表示服務端，PKB表示B的公鑰，KAB表示協商的會話密鑰，給出以下基本假設：

安全通道理想化描述如下：

邏輯驗證過程如下：

在步驟2中，根據annotation規則可以得到

(6)

根據假設P1、P2和上述公式，可以得到

(7)

根據假設P3，得到

(8)

依據nonce-verification規則

(9)

截取上述公式，得到

(10)

根據假設P4和jurisdiction規則

(11)

在步驟3中，根據annotation規則

B?NB

(12)

根據假設P4，可得

(13)

綜上所述，獲得一階置信度的(11)和(13)以及二階置信度(10)。BAN邏輯驗證該協議是安全的。

該安全協議還可以防止重放攻擊，通過雙方交互數據中的隨機數和時間戳保證了每次交互消息的新鮮程度。

5 隨機數質量分析

5.1 隨機數熵估計

在NIST SP800-90B[12]中使用熵率的概念表示隨機數發生器輸出的偏差。熵率的定義為熵源提供熵的比率，它通過將熵的估計值除以位串的總數得到。這個值介于0(沒有不確定性)和1(完全不確定)之間，是一個位串隨機性和不可預測性的度量。如果一個位串是無偏的，即每一位和其它位相互獨立，熵率將等于1。

針對本方案最終輸出的隨機數比特序列，隨機采集255個數據樣本文件，每個文件采集215比特數據，通過統計樣本中比特0和比特1的頻次規律，進而近似為比特0和比特1概率，代入熵計算式(14)計算每個樣本文件的信源熵值[8]

h=-∑ipxilog2pxi

(14)

如表2所示，經過計算，熵率平均值為0.999 999 57，是滿足安全需求的。

表2 隨機采集的數據文件前20組信源熵值

5.2 隨機性檢測

由于無法從數學上驗證一個隨機數發生器產生的二元序列隨機性的好壞，因此常借助于統計檢驗來判斷。在檢驗時，如果二元序列沒有通過某一項檢驗，否則判斷該序列非隨機；如果能夠通過所有的檢驗，則判斷該序列隨機。即使能通過所有的統計檢驗也只能概率性的驗證該隨機數發生器產生的二元序列是具有隨機特性的序列。

下面采集N組長度為L的隨機數樣本(其中N=1000，L=128 KB，樣本文件命名為0001.bin～1000.bin)，進行SP800-22[15]和GM/T0015[9]規定的隨機性檢測。

測試標準為針對單個測試項，若通過的樣本個數不小于M(其中M=981表示通過率98.1%)，則判斷通過此項檢測。若有其中一項未通過檢測，允許重新采集N組隨機數重新測試。

測試參數中m表示子序列的比特長度，k表示二元推導檢測中對待檢序列中相鄰兩個比特做異或操作得到新序列的重復操作次數，d表示自相關檢測中的時延，有4種取值。

實測結果見表3，所有測試項目的測試結果均超過M/N，判定所采集隨機數質量是合格的。

表3 采集1000組隨機樣本的隨機性檢測

5.3 檢測結果分析

從上述熵估計和隨機性檢測來看，軟件密碼模塊通過本方案采集的隨機數質量是合格的，下面結合改進隨機數發生器機制及原理進行分析。

對于采用系統熵池作為單一熵源的軟件隨機數發生器，由于不同智能終端上隨機信號源都不是很完善，產生的隨機數種子的隨機性和精確性可能存在問題。其后處理過程不管采用對稱運算、摘要運算還是線性反饋移存器，由于算法是確定性的，輸出的二元序列本質上是偽隨機序列。

在華為智能終端做了一組實驗，采用單一系統熵源采集1000組樣本的隨機性檢測結果如表3第2列所示，可見統計上也取得了比較好的測試結果。

另一方面，如果本地隨機數池被攻擊，隨機數發生器的熵值將降低為0，產生的隨機數全部可預測、不再可靠；其次，隨機數池畢竟容量有限，循環使用完畢之后，如果不及時更新，輸出隨機數是可預測的。

5.4 聯合熵分析

由于初始隨機數的3個熵源是相互獨立的，在式(1)中，r0、rd0、cr0、sr0的長度均是16字節(128比特)，設集合

rd0={x1，x2，…，x128}，
cr0={y1，y2，…，y128}，
sr0={z1，z2，…，z128}，
r0={r1，r2，…，r128}，

其中，xi、yi、zi均為各自熵源提供的隨機變量，設p(xi)、p(yi)、p(zi) 分別是集合rd0、cr0、sr0上的概率分布，稱H(rd0)、 H(cr0)、 H(sr0) 分別為相應概率分布的熵。

式(1)展開，可得

{r1，r2，…，r128}={x1⊕y1⊕z1，x2⊕y2⊕z2，…，
x128⊕y128⊕z128}

(15)

設p(ri)=p(xi，yi，zi) 是集合rd0×cr0×sr0上的概率分布，稱H(r0)=H(rd0，cr0，sr0) 為該概率分布的熵。

由于在X、Y互相獨立時，H(X，Y)=H(X)+H(Y)， 進而根據熵的鏈式法則，可以進一步得到，如果隨機變量X、Y、Z互相獨立，聯合熵H(X，Y，Z) 可表示

H(X，Y，Z)=H(X)+H(Y)+H(Z)

(16)

根據式(16)

H(rd0，cr0，sr0)=H(rd0)+H(cr0)+H(sr0)

(17)

由于服務端熵源是硬件密碼模塊的真隨機數發生器提供，sr0是128比特的真隨機數，其熵值H(sr0) 為128比特；本地隨機數池種子來源也是硬件隨機數發生，在確保一次使用且及時更新的情況下，cr0是128比特的真隨機數，其熵值H(cr0) 也為128比特；系統熵池提供的隨機數雖然具有良好的統計特性，cr0也是128比特隨機數，但其熵值H(cr0) 可能不足128比特。這樣，本文提出的隨機數發生器由于熵池的3個來源互相獨立，根據式(17)，采集16字節初始隨機數的熵值可以接近384比特，即每猜測一個輸出比特值需要3個比特的信息量。而采集同樣字節長度隨機數使用單一熵源的最高熵值僅為128比特，遠低于384比特。

6 結束語

與單一熵源的軟件隨機數發生器相比，本文提出的隨機數發生器采用3個熵源，分別是系統熵池、本地隨機數池和服務端采集的隨機數，輸出的初始隨機數熵值足夠、質量合格。在初始隨機數的產生過程中，完成了對用戶的身份認證并建立了安全通道，安全通道可用于保護軟件密碼模塊和服務端之間的交互數據。對本方案輸出的隨機比特序列進行了分析，其信源熵值、隨機性、安全性均滿足需求。該隨機數發生器已經應用于軟件密碼模塊產品中，可廣泛應用于金融、物聯網、社區警務政務等領域。