面向软件的随机数发生器设计和实现

彭金辉，张志鸿

(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个熵源，分别是系统熵池、本地随机数池和服务端采集的随机数，输出的初始随机数熵值足够、质量合格。在初始随机数的产生过程中，完成了对用户的身份认证并建立了安全通道，安全通道可用于保护软件密码模块和服务端之间的交互数据。对本方案输出的随机比特序列进行了分析，其信源熵值、随机性、安全性均满足需求。该随机数发生器已经应用于软件密码模块产品中，可广泛应用于金融、物联网、社区警务政务等领域。