在保障互联网安全的各种加密算法中,随机数产生至关重要。产生随机数的方法有多种,其中振荡器采样法最适于构建SoC设计所需的随机数发生器。本文介绍振荡器采样法的工作原理,并概述在具体使用这种振荡器时应注意的事项。
随着许多企业的网络应用从内部网扩展到公众互联网,对虚拟专用网络(VPN)设备的需求也开始逐渐上升。为了服务于这个市场,半导体厂商推出了一些专用产品,把所有必需安全功能都集成在一个器件里面。
专用于互联网协议安全(IPsec)的AES和3DES类加密/解密算法以及SHA1和MD5等散列算法已广为人知并得到普遍重视,然而,保证VPN系统安全的关键在于生成随机数的能力,但这点却常常被忽视。
随机数是许多加密应用的基础,其作用是生成Diffie-Hellman、Rivest-Shamir-Adelman和数字签名等算法所需的公共/专用密钥对,并为大批量加密算法和IPsec分别生成初始向量和即时随机数,此外,大量其它类型的安全协议也靠随机数发生器的不可预测性来防止系统被破解。常用一些复杂数学函数生成高质量伪随机数发生器(PRNG)位流,但事实证明有很多途径可以攻击用PRNG加密的系统,因此加密安全系统需要使用更高质量的随机数发生器。
在明确了这些需求之后,到底有没有一种真正的随机数发生器可以根据非确定噪声源产生随机数,并特别适用于系统级芯片(SoC)设计呢？大多数随机数发生器方案通常可以归为三大类,即直接放大、离散时间混沌和振荡器采样。前两种方法更适用于客户定制的单元设计,因为在这些场合设计人员可以控制实际电路的布局；而振荡器采样技术可以作为标准单元设计流程的一部分,因此在SoC设计中很流行。不过设计人员即使选用了振荡器技术,仍然有许多实施问题需要仔细考虑。
随机数生成技术
直接放大技术使用高增益高带宽放大器来处理由热噪声或散射噪声引起的电压变化。例如可采用N阱电阻对将其热噪声转换成一个电压变化信号,然后以抖动的形式输入随机数发生器模块微系统中(图1)。采用这种方法时设计人员必须要考虑其它一些因素,如系统热噪声通常与基底噪声及电源电压波动等局部特征耦合在一起,如果电路没有正确屏蔽,这些因素便会使热噪声源的随机性受到影响。克服这种现象的方法是对一对邻近的电阻进行采样,再对结果求差以减少其它噪声源的影响。
离散时间混沌法使用模拟信号处理技术产生随机位流。这种方式下,随机性不是从热噪声源获得,而是从非常稳定的动态变化中得到,其系统设计与模/数转换器性质类似。在传统的A/D转换器中,残余信号经过采样和保持,再馈送到A/D转换器的输入端(图2)。一般来说,单是这种技术本身尚不足以产生随机序列,因为电路的不准确性限制了A/D转换分辨率,也降低了系统产生随机序列的能力。因此,为获得非确定随机性,这种技术常常要与其它技术配合使用。
目前,随机数发生器(RNG)设计中最流行的方法是振荡器采样法(图3),其基本设计思想是利用两个独立工作的高、低频振荡器之间的相对关系来得到非确定噪声源,用高抖动低频振荡器采样高频振荡器,从而产生随机数序列。在数字电路中,低频方波源可作为一个正沿触发D触发器的时钟,高频方波源则作为触发器的数据输入,并在时钟脉冲的上升沿对其进行采样。
在该系统中,产生随机数的关键元件是低频振荡器,因为它的设计具有频率不稳定性,即抖动,而且低频与高频之比经过仔细选择可以符合一定条件。设计中最重要的是低频振荡器的抖动量,这个抖动就是随机源。频率不稳定性可以是此类振荡器的一个功能,也可由另一个非确定噪声源直接“植入”,因此可以说,正是采样时钟相对于高频数据输入的相位变化保证了可以获得随机位流。
如果两个振荡器在工作过程中都不发生漂移,那么采样得到的位流便具有周期性而且可以预测,这种周期性和通常称为节拍频率的频率比有关。此外,两个振荡器的频率比对所产生的位流有着非常重要的影响。多项研究表明,为了保证高度随机性,低频振荡器周期变化标准差的两倍与高频振荡器周期之比应该大于3:2,否则位码之间便会存在明显的相关性,以致于后面的位将比其前面的位更容易预测。
使用振荡器采样法
选用振荡器采样法来设计随机数发生器的设计人员还必须考虑其它一些实施问题,所选振荡器的类型也会影响整个系统设计的固有随机性。此外,为了保证相关噪声源不会降低系统随机性,必须仔细选择振荡器,这必然又会增加器件电路布局的复杂性。作为一种补偿,可采用数字后处理技术来降低设计风险并保留系统的随机性。
在考虑实施振荡器采样法时,设计人员可从几种不同类型的振荡器中进行选择,包括差分振荡器、单端振荡器及混合振荡器,不同类型振荡器对不同噪声源的敏感度也不一样。显而易见,不同振荡器的特性比较需要丰富的知识,本文在此只作简单讨论。
通常,差分振荡器对电源及基底噪声的敏感度不如单端振荡器。这是因为差分放大器对的电源和接地点会同时出现电压摆动,所以两个输入之间的差值保持一致,输出也一致,呈现出较高的共模抑制比(CMRR)。差分逻辑常用于模拟逻辑压控振荡器设计中,例如锁相环中的振荡器,因为锁相环需要较高的CMRR,所以差分振荡器方案并不特别适用于那些需要非确定噪声源的设计。另一方面,单端反相振荡器极易受电压摆动或输入信号中直流分量的影响,如果噪声对电平带来任何波动,都会影响振荡器的抖动。此外,差分、感容及张弛振荡器设计需要客户定制的电路布局,所以无法集成到标准单元的SoC设计中。因此,在SoC设计中最简单直接的解决方案通常是单端环形振荡器(图4)。
尽管单端环形振荡器有这样的优势,在选用时还是有一些复杂因素必须考虑。由于高速数字系统存在切换动作,因此热噪声与电源/基底噪声相比一般可以忽略不计。电源和基底噪声是引起噪声耦合的主要原因,噪声耦合的振荡器在反相电路中会产生δ延迟。电源电压变化或来自基底耦合的噪声会改变每级电路输出节点的电容,从而使振荡器的总频率不断改变。此外,除热噪声外,所有环形振荡器延迟电路级中的电源和基底噪声都是相关的,所以如果没有牢靠的接地环保护电路,设计人员都不希望让两个振荡器电路靠得太近。如果屏蔽不是很好,会造成两个位流源之间的随机性相互关联。在最终的振荡器设计中,所有这些因素都必须要考虑到。
此外,就算设计人员有良好的意愿,实施方案也可能无法产生真正的随机位流。设计人员或许要借助一些成本高昂的额外测试来保证随机数发生器系统能产生期望的结果。如前所述,随机性主要来自电源和基底噪声与振荡器电路的耦合,由于这些振荡器会耦合同一个噪声源,因此设计人员不希望将它们靠得太近。进一步来说,如果两个振荡器锁定在同一个噪声源上并相互耦合,那么它们之间的相关性也会增加,从而使两个源的随机输出相互关联。如果在最终布局上将两个振荡器分开,电源和基底噪声的相关效应便可减轻。
采用振荡器采样法的一种常见做法是多设计一对振荡器,万一主随机源失效了,它还可以降低RNG系统没有非确定性噪声源的风险,随后通过一个强大的混合函数将采样位流进行混合,以便保留各个源固有的随机性,这一点将在后面详述。为了从混合位流中获得更好的随机性,必须给各振荡器选择一个独特的主标称频率,或者使其频率能够调节,这可尽量减少多个源之间的互相关性。当然,设计者必须权衡考虑,要么接受额外成本,要么承担不能生成真正随机数的风险。
偏差纠正器
振荡器采样法的工作基于这样一个事实,即高频振荡器一直保持50%的占空比,而低频振荡器每个周期都有明显变化。如果情况不是这样(尽管绝大部分情况下是这样),所获得的位码便会出现偏差,既可能是“1”,也可能是“0”,这称为偏移。幸运的是我们可以采取有效的后处理方法来纠正偏差,以一种确定的方式产生分布更均匀的位流。其中两种最简单的技术分别称为奇偶生成和转换映射,此外还有一些较复杂的偏差纠正方法,包括使用快速傅利叶变换函数和更复杂的位混排技术,它们通常采用延迟元件和反馈通路组合来去除位与位之间的相关性。
偏差纠正的目标是对位流进行均衡分配,以便以相同的概率产生“1”和“0”,其做法基本上是从有偏差的位序列中提取出更随机的数值。这种后处理功能并非振荡器采样技术所独有,其应用对原始噪声源没有要求,要实现这种功能也并不复杂。一种简单方法是奇偶生成,它具有鲁棒性强的优点,可用于更大范围的偏差分布。用硬件来实现固定长度位采样序列一般非常简单,例如简单的级联XOR链便可有效用作一个奇偶生成器并完成适当的偏差纠正(图5)。
转换映射也叫做冯·诺依曼纠正器,它将一对采样输入位转换成一个输出位,例如把输入对[0,1]转换成1,把[1,0]转换成0,而在输入为[0,0]或[1,1]时什么也不输出。这种技术可以完全消除偏差,但其代价是必须在输入位之间创建一个不定量的延迟,并产生一个输出位长的任意数。
混合函数
即使采用了所有上述技术,仍然存在这样一些担忧,即由于存在多种非随机数据源(如前面提及的多个振荡器源组合),系统固有的随机性可能受到影响。采用功能强大的混合函数可以确保随机源的随机性,这些函数将两个或更多采样位进行组合,然后产生一个输出位,该输出位是先前各输入位的复杂非线性函数。当然,这样获得的输出随机位数不可能多于输入位数。对这个函数期望的功能是任何输入位的改变都会引起大约一半输出位的改变,这些混合函数也可作为更复杂的纠偏方法去除位流偏差,如同前面讨论的那样。
一般情况下,混合函数功能越强,它所占用的芯片面积也越大,前面提到的级联XOR便是很简单的一例。DES加密/解密算法则是更为复杂的例子,因为它需要120个输入位,产生64个输出位,每一个输出位都依赖一个涉及所有输入位的复杂非线性函数,其它加密/解密算法的工作方式也类似。混排函数也可用作强大的混合函数,它们使用任意长度的输入位,并产生一定长度的信息摘要。同样,设计工程师需要进行权衡,要在额外开销与所生成的位流无法达到期望随机度之间做选择。
统计评估
美国商业部创建了多种用来评估加密应用中随机数发生器随机程度的标准,美国国家标准技术研究所(NIST)出版的“800-22特刊”推荐了一种全面的随机数发生器统计测试方法,并严格规定了满足各种程度随机性的衡量标准。测试工程师可在验证过程中使用这种测试方法或其它类似测试,检验设计是否具有非随机特征,从而判断是否达到了某种程度的随机性。NIST统计测试套件中规定了16种不同类型的测试,以便能发现被测随机数发生器的缺陷。
NIST FIPS 140-2是美国商业部颁发的另一份文件,它定义了设计者在安全应用中采用加密设备时必须遵守的一系列要求。其中一个最重要的要求是任何使用随机数发生器的实时加密模块必须提供加电能力并可对RNG功能进行持续的实时测试,确保它在工作过程中不出现故障,如果在规定的统计测试中出现任何失败,RNG模块都必须进入一种错误状态。对于SoC设计来说,这意味着如果最终产品希望获得美国政府安全标准许可的话,那么进行测试的测试器模块必须集成在设备本身之中并满足规定的要求。
某些产生非确定性噪声源的技术也许并不适用,这取决于是使用标准单元设计还是使用客户定制布局设计。的确可以保证一项设计达到期望的随机度,但这种保证的代价是增加芯片尺寸以便实现冗余结构或更为复杂的后处理功能。即便是精心规划的设计,最后阶段也必须通过统计测试套件的验证,只有这样才能说设计达到了期望的随机度。
参考文献
1. Jun and Kocher, "Intel Random Number Generator," Cryptography Research Inc. white paper, April 1999
2. Craig Petrie and J. Alvin Connelly, "A Noise-Based IC Random Number Generator for Applications in Cryptography," IEEE TCAS I, Vol. 47, No. 5, May 2000, p615-621
3. Fairfield, Mortenson, Coulthart, "An LSI Random Number Generator," Advances in Cryptology, Proceedings of Crypto 84, p203-230
4. Frank Herzel and Behzad Razavi, "A Study of Oscillator Jitter Due to Supply and Substrate Noise," IEEE TCAS II, Vol. 46, No. 1, January 1999, p56-62
5. Eastlake, Crocker and Schiller, "Randomness Recommendations for Security," RFC-1750
6. NIST Special Publication 800-22, "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications," Information Technology Laboratory of the National Institute of Standards and Technology, Gaithersburg, Md., September 2000
7. Federal Information Processing Standards Publication 140-2, "Security Requirements for Cryptographic Modules," Information Technology Laboratory of the National Institute of Standards and Technology, Gaithersburg, Md., May 2001
作者: Alex Soohoo
系统应用经理
互联产品事业部
IDT公司
Email: @
京公网安备 11011202001138号
