基于布尔网络的低功耗物理随机数发生器

杨 芮，侯二林，刘海芳，龚利爽，王云才, 3，张建国

1)太原理工大学物理与光电工程学院，山西太原 030024；2)太原理工大学新型传感器与智能控制教育部和山西省重点实验室，山西太原 030024；3)广东工业大学信息工程学院，广东广州 510006

随机数在蒙特卡洛仿真、深度学习、随机建模和密码学等领域具有广泛应用.密码学的安全算法和加密协议依托随机数生成不可预测的随机数密钥.因此，高质量的随机数对保证系统的信息安全尤为重要.随机数发生器分为伪随机数发生器和物理随机数发生器.前者主要通过特定算法产生，但其输出序列具有周期性，可被预测和还原，不适于安全保密性要求高的信息安全领域.物理随机数源于物理熵源，具有无周期、不可预测及不重复等特点，满足信息安全系统对随机数不确定性的要求.

激光器的相位噪声[1]、混沌激光[2-3]及光的量子效应[4]等都可以作为产生物理随机数的熵源，而基于电路的物理随机数发生器具有低功耗、可集成及易于在可编程平台上实现等优点，得以广泛应用.利用电路产生物理随机数的方法主要包括：基于模拟电路结构的直接放大噪声法和离散时间混沌法；基于数字电路结构的振荡采样法和亚稳态采样法.直接放大噪声法[5]通过放大电路中电阻的热噪声，与阈值比较产生随机序列.由于电阻噪声中的噪声幅值很小，需要高增益的运放器进行放大，而放大器有限的带宽和失调导致随机性变差.离散时间混沌法[6]利用混沌电路的不可预测及初值敏感性产生随机数，但由于电路设计复杂，很难同时满足高速和低功耗的要求.振荡器采样法[7]通过低频信号采样高频信号，利用时钟抖动作为随机源产生随机序列，但占空比失谐引起的统计偏差需进行后续处理.亚稳态是指电路无法在某个规定的时间内达到一个可确认的状态，当任何数字电路元件一旦进入亚稳状态，电路的输出将会取决于电路的噪声特性，而变得具有随机性，由此输出0或1的随机序列，即亚稳态采样法[8].由于电路中亚稳态持续时间较短，且对温度和电压的变化比较敏感，产生随机数的速率较慢.

布尔混沌是自治网络中的一种物理现象，其表现出随机性持续振荡，且可以产生带宽较高的信号，因此，成为随机数发生器的理想熵源.2013年，ROSIN等[9]提出一种基于自治布尔网络产生物理随机数的方法，但该方法采用自反馈结构作为物理熵源，从而引入相关性.2017年，DONG等[10]对此电路进行改进，提出每个节点均增添多个反向器的时延自反馈结构.然而这两种方法均是三输入结构，物理随机数发生器的功耗较高.

本研究提出一种基于二输入12节点相互耦合及1个反向器构成自治布尔网络作为物理随机数发生器(physical random number generator, physical-RNG)的熵源，节点数目的减少使该随机数发生器所占用的逻辑资源降低，从而降低功耗.在逻辑元器件的制造过程中，二输入逻辑门需要的晶体管数量约为三输入的一半，进一步降低功耗.该熵源产生带宽为700 MHz的混沌信号，通过D触发器采样及量化，随机序列的香农熵达到1 bit/sample.整个物理随机数发生器在可编程逻辑阵列(field programmable gate array, FPGA)平台上实现，逻辑资源消耗极少.美国国家标准与技术研究院(National Institute of Standards and Technology, NIST)随机数测试结果表明，所产生的随机数具有良好的随机统计特性.

1 熵源模拟

本研究提出的物理随机数发生器结构如图1，12个逻辑运算的节点相互耦合构成网络拓扑结构.其中，节点1执行三输入异或非(XNOR)运算；2个输入源于节点2和节点3，另一个输入来源于反相器；其余节点均执行二输入异或(XOR)运算.布尔延迟方程[11](Boolean delay equation)可对节点数为N的自治布尔网络进行动态分析，

xn(t)=fn[t,x1(t-τn1),x2(t-τn2),…,

xn(t-τnm)]

(1)

图1 物理随机数发生器结构

其中，τnm为节点n到节点m的延迟时间；xn(t)为节点n在t时刻的逻辑状态；fn为节点n执行的逻辑函数.

仿真结果表明，当τmn≠τnm时，XNOR节点输出的信号呈随机混乱状态,如图2；当τmn=τnm时，网络动态特性无法确定.由于逻辑器件本身的特性，无法响应转换速度过快的信号，即所谓的低通滤波效应[12-13].布尔网络的振荡频率f与节点数目N成反比，当节点数量较小时，振荡频率较高，网络无法响应频率过高的信号，使得该信号被衰减和抑制，导致振荡停止.随着节点数目的增加，f逐渐降低，当f低于截止频率时，网络出现持续性振荡.因此，需要通过增加节点数目来增加信号的延迟时间，使网络持续振荡.

图2 布尔网络动态仿真结果

2 熵源实验分析

2.1 混沌熵源电路特性

基于自治布尔网络作为熵源的物理随机数发生器由熵源和熵提取两部分构成.熵源由12个节点相互耦合及1个反向器构成自治布尔网络，每个节点均可以产生持续振荡信号.熵提取部分由1个三输入XOR逻辑门和3个D触发器组成.3个D触发器分别对节点1、5及9输出的混沌时序进行采样，对采样的序列经过XOR处理，进一步降低序列间的相关性和偏差.通过观测XNOR节点的电压输出，分析信号的物理特性.图3(a)为熵源输出信号的时序图，可见，该信号呈现复杂且无序的振荡；图3(b)为熵源输出信号的频谱图，输出熵源频谱带宽可达700 MHz(下降10 dB带宽)；图3(c)为熵源输出信号的自相关曲线，结果显示该信号的半高全宽(full width at half maximum, FWHM)约为1 ns.频谱的宽度及较短的自相关时间意味着可以从中提取速率较高的物理随机序列.

图3 熵源输出信号的时序、频谱及自相关曲线

李雅普诺夫指数是混沌动力学特性的一种重要表征方式.最大李雅普诺夫指数为正值即证明该系统为混沌系统[14].根据文献[15]的方法,计算熵源输出信号的最大李雅普诺夫指数λmax=0.36 ns-1，结果如图4,表明输出振荡信号具有混沌特性.其中，d为轨迹的分离距离.

图4 熵源信号的最大李雅普诺夫指数

2.2 熵值分析

熵值可描述信息的不可预测性.熵值越大，表示信息的不可预测性越高.对于长度为n的二进制序列X，其香农熵为

(2)

其中，p(xi)表示X的第i个元素为xi的概率.统计由不同数量节点 (N=3,4,…,16)构成自治布尔网络的香农熵.结果如图5.可见，随着N的增加，熵值呈现3种不同的状态：① 当N<4时，由于低通滤波效应无法产生振荡信号，此时熵值为0；② 当N逐渐增大时，网络中的周期抖动引起小的不确定性，导致产生低熵；③ 随着N的进一步增大，受逻辑门退化效应等非理想因素[9,13]的影响，熵值接近于最大值.需要说明的是，在经过对节点1、5及9进行XOR处理后，随机序列的熵值达到了1 bit/sample，图6为实时速率为100 Mbit/s的随机序列.考虑到随机数发生器的最优功耗，选择N=12的自治布尔网络作为physical RNG的熵源.

图5 随机序列熵值与节点数目的关系

图6 实时速率100 Mbit/s的物理随机序列

3 随机数发生器的硬件实现

该物理随机数发生器FPGA部分在可编程逻辑器件(Altera Cyclone IV，EP4CE10F17C8N)上实现，包括熵源及熵提取模块、时钟产生模块、双端口异步先进先出(first input first output, FIFO)指令及串口输出，整体构成如图7.在系统时钟的作用下，熵源模块产生混沌信号，熵提取模块将信号量化为随机序列.由于采样时钟和串口时钟是两个不同的时钟，随机序列需要经过双端口异步FIFO对数据进行缓存，经串口输出模块将数据输出.由FPGA产生的数据经USB传输，上位机接收后，在PC端进行随机性测试.本研究设计的随机数发生器单个熵源部分仅消耗13个逻辑单元(logic element, LE)，而整个工程所占用的LE数量小于整个FPGA资源的1%.因此，可根据需要在FPGA资源范围内任意添加该physical-RNG的路数，随机数发生器的实时速率可提高至Tbit/s级别.

4 随机性测试

对随机数质量的检测通常采用NIST发布的随机数测试程序[16].本研究测试了样本容量为1 Gbit的随机数.NIST有15个测试项，设置显著水平值α=0.01，测试结果包括p值及proportion，当p值≥0.01，proportion>0.980 6时，表示通过该项测试.测试结果如表1，可见，本研究设计的物理随机数发生器产生的1 Gbit随机数能够通过所有项的测试，具备良好的随机性.

图7 物理随机数发生器的硬件框图

表1 NIST测试结果

结 语

本研究通过对自治布尔网络行为的动态仿真模拟，验证其作为物理随机数发生器熵源的可行性.实验分析熵源输出信号的电路特性，结果表明，其时序呈现复杂无规律的持续振荡，频谱带宽可达700 MHz，半高全宽约为1 ns.李雅普诺夫指数的计算结果证明了信号的混沌特性，熵值分析结果表明，当选择以12个节点构成的自治布尔网络作为物理熵源时，随机数发生器的功耗及随机序列的质量得以最优化.将通过仿真模拟及实验验证的物理随机数发生器在可编程逻辑器件上实现，提取实时产生速率为100 Mbit/s的物理随机数进行NIST测试，结果表明，该随机数发生器产生的随机序列具有良好的随机统计特性.本设计仅用13个逻辑器件就产生了实时速率为100 Mbit/s的物理随机数产生，通过多路复用方式，随机数的产生速率可达Gbit/s.本设计具有高速、低功耗及易集成等特点，在高速加密系统中具有广泛应用前景.