一种基于FPGA的真随机数发生器设计与实现

只看该作者 · 2013-5-13 20:47

真随机数发生器(TRNG)在统计学、信息安全等领域有着广泛的应用。在这些领域中，不仅要求数据序列分布均匀、彼此独立，而且要求其具有不可预测性，能够抵御针对随机性的攻击。B．Sunar，W.J．Martin和D．R．Stinson提出，真随机数发生器的性能受3个因素的影响：熵源(Entropy Source)，采集方式(Harvesting Mechanism)和后续处理(Post-Processing)。在电路系统中最常见的三种真随机数产生方法为：
1)直接放**：放大电路中的电阻热噪声等物理噪声，通过比较器进行比较后获得随机数序列；
2)振荡采样法：用带有抖动的慢振荡器通过D触发器采样一个周期固定的快振荡器，输出随机序列；
3)离散时间混沌法：利用混沌电路不可预测以及对初始条件敏感的依赖性的特点产生随机序列。

基于模拟电路的结构，熵源的统计分布更加理想，且熵源噪声不随采样周期的变化而改变；基于数字电路的结构，集成度高，便于在FPGA等通用可编程平台上实现，但熵源的统计特性与模拟电路相比不够理想。

本文尝试了一种用纯数字电路实现的TRNG结构，且不使用诸如PLL等特殊资源，便于设计由FPGA验证移植到芯片设计。其核心思想是使用反相器和延时单元构成两个相互独立的振荡器，由于内部噪声的差异引起的相位偏移作为熵源，经过一段时间振荡后，随机的状态由数字双稳态电路锁存。多组振荡器的输出，经过异或和同步处理后得到随机序列。该TRNG在FPGA物理平台上实现并进行了测试验证。

1 TRNG的设计
1．1 相位漂移与抖动
由于受到电路中噪声的影响，数字电路中时钟信号的周期在每个不同的周期上可能缩短或者加长，这就是时钟抖动。抖动可以用许多方法来衡量和表征，它是一个均值为零的随机变量。振荡器起振时刻的差异和电路元件的工艺偏差，使得振荡器间存在相位漂移。因此抖动信号和相位漂移适合在数字电路中作为TRNG的随机源。

1．2 亚稳态
锁存器是有逻辑‘1’和‘0’两个稳定状态的双稳态器件，但是在特殊情况下其可能进入亚稳态，此时它的输出是介于‘1’和‘0’之间的中间电平。如图1所示锁存器用两个反相器和两个开关表征。当锁存器导通时，采样开关闭合，保持开关打开(图a)；当锁存器关闭时，采样开关打开，保持开关闭合(图b)。图c展示了两个反相器的直流传输特性。当锁存器关闭时A=B，稳态是A=B=0和A=B=VDD，亚稳态为A=B= Vm，其中Vm不是一个合理的逻辑值。因为电平在该点是相互稳定的并且可以无限期停留，所以称该点为亚稳态。但是，任何噪声或者其他干扰都会使得A和B最终稳定在两个稳态中的一个状态。图d非常形象地表征了亚稳态，它就好像处于山顶的小球任何干扰都会使小球滚落到山两端的稳定状态。

1．3 振荡器的设计
如图2所示，二选一复用器既作为延迟单元又作为选通单元使用。当选通信号为‘1’时，形成两个相互独立、自由振荡的环形振荡器。当选通信号为‘0’时，两组反相器交叉相连形成双稳态器件。自由振荡时，两个振荡器之间存在着抖动和相位偏移。在振荡的停止时刻，即振荡环路断开、两组反相器交叉连接时，反相器的瞬时输出电压以及内部噪声的绝对和相对值决定了电路最终稳定在哪个逻辑值上。有时即使反相器跨接在一起，电路也会振荡很长一段时间才能稳定下来，形成亚稳态。综上所述，随机序列的来源用到了抖动和亚稳态两种机制。

波形如图3所示，为了方便数据采集选通信号是由时钟经过分频得到的。在自由振荡阶段，输出信号快速变化不属于任何稳定状态，在图中用斜线表示。在解析阶段，电路是双稳态器件，此时应该保持解析时间足够长，从而使输出电平在大多数情况下稳定在逻辑‘1’或‘0’。

1．4 随机源模块的电路设计
各个振荡器的输出经过异或运算可以增加随机性，而亚稳态的传播会造成后续电路的错误动作，因此使用同步器将异或后的随机序列与后续电路隔离开来，同时也方便采集稳定的输出序列做性能分析。此处采用了三级寄存器的同步结构，由MTBF(Mean Time Between Failure)的定义可知，平均需要经过数百年时间才会发生一次亚稳态通过同步器向下传播的事件，因此是满足设计要求的。该模块电路图如图4所示。

1．5 后续处理模块的设计
理想情况下，D触发器所采集的信号具有随机的统计特性，可是FPGA内部电路不可避免地会受到温度漂移、电压抖动等不良因素影响，从而导致采样得到的随机信号中存在偏置，影响结果的统计特性。所以在采样得到随机序列后要对数据进行消偏处理，使0和1出现的概率相当。

本设计采用16位最大长度二进制伪随机序列(Pseudo Random Binary Sequence)的输出与采样得到的随机序列进行异或运算作为后续处理，PRBS产生电路消耗资源少并且使用线性反馈移位寄存器实现，非常适合于在FPGA上实现。它的生成多项式是：

多项式表示如图5所示。

2 TRNG的FPGA实现与测试
整个TRNG的实验环境由外部时钟源、FPGA开发板以及逻辑分析仪组成。TRNG采用Xilinx公司的Virtex-5系列中的XC5VLX110作为物理实现平台，外部时钟频率为64 MHz。由FPGA产生的随机数据，经逻辑分析仪采集后，使用DIEHARD battery of tests of randomness随机数测试程序进行测试，检验随机序列的性能。

DIEHARD测试是由16项测试组成的用来度量随机数发生器性能的一组统计学测试，它由George Marsaglia开发并于1995年首次发布。DIE HARD的测试结果叫做P-value，它由方程P-value=Fi(X)计算得到，其中Fi试图建立样本X在0和1间服从均匀分布的分布函数。因为Fi是渐进逼近的，它在尾部的近似效果变差，所以数值接近0或1的P-value在真随机序列中极少出现。当被测序列随机性能很差时，会有很多P-value的值是精确到小数点后数位的0或者1，例如1．000 000。需要强调的是，P-value等于1．000 000或0．000000是序列为真随机序列的充分不必要条件。

2．1 FPGA位置约束
为保证每个振荡器中的两个独立振荡环的理论振荡周期相同，以便更容易在锁定期间产生亚稳态，加大噪声对输出电平的影响，同时尽量让各个振荡器的输出在进行异或运算前延迟不出现太大偏差。所以对TRNG中的振荡环进行位置约束：将振荡环中的反相器约束在左右相邻的逻辑单元(Slice)中，让各个振荡环分别约束在上下相邻的逻辑单元中。

2．2 振荡器数目对统计特性的影响
在32 MHz的采样频率下，分别以15组、19组、27组和32组振荡器作为TRNG的随机源，随机序列经过同步器后不与PRBS运算直接输出。将采集到的随机序列送入测试程序进行测试以后，其结果如表1所示。

可以看出，振荡器的数目直接影响随机源模块产生序列的统计性能，振荡器数目越多，TRNG输出序列的随机性越好。但是如果振荡器的数目太多，会消耗过多的硬件资源，功耗也过大。因此，不宜通过单纯地增加振荡器数目的方法提高随机序列的性能。

定性分析如下：将序列的每位看作是一个随机的二进制变量X，定义b是序列的偏置。即

根据Piling-up引理，输出序列的偏置是：

其中n是输入序列的个数，bi是每个序列的偏置。容易看出b≤bi(1≤i≤n)，等式当且仅当在bi=0()或者bi=1／2()时成立。简而言之，异或运算显著地减小了独立输入序列的偏置。假设n=16且所有bi=1／3，那么b=0．000 761可以忽略不计。

2．3 后续处理模块对统计性能的改善
由上一节的分析可知，增加振荡器数量是改善序列统计特性的有效方法。但前提条件是各个振荡器相互独立。当振荡器数量过多时位置约束很可能与相互独立的要求相互矛盾。因为高速的振荡信号往往发生相互串扰的情况，并且消耗更多资源和功耗，所以有必要在保证TRNG包含一定数量的振荡器的前提下，引入后续处理模块。从而达到消耗资源较少，序列性能较好的目的。

本项测试以19组振荡器作为TRNG的随机源，输出序列与PRBS模块输出进行异或运算，然后分别使用32，16，8，2 MHz的采样时钟采集数据。将数据送入测试程序进行测试以后，结果如表2所示。

可以看出，TRNG生成的随机序列全部达到了预定的性能指标。同时不难发现，采样时钟频率对TRNG的输出统计特性是有影响的，当采样频率逐渐降低时，TRNG的随机性能逐步提高。出现这种现象是由于采样频率越高，就与振荡频率越接近，二者的相位偏移干扰了随机信号的获取影响了统计特性。

3 结束语
本文尝试了一种纯数字形式的真随机数发生器结构，规模较小、易于移植。电路包含两个振荡环，分为自由振荡和锁存至双稳态两个工作状态。利用振荡环之间的相位偏移和抖动以及双稳态器件的亚稳态作为随机源。本文探讨了振荡器数量对序列统计特性的影响，并在加入后续处理模块的情况下试验了多种采样频率，经测试随机序列完全符合预定指标。