【摘要】本文提出一种基于ADC芯片产生均匀分布真随机数方法,该方法以ADC芯片输出的数据最低位交错取原码反码结合成一个二进制序列,然后使之通过一个非线性反馈多项式算得最终的随机数结果。文章分析了该方法产生的随机数序列的随机特性,证明其实用有效,可以在火控雷达抗干扰、电子战与信息加密中得到应用。
【关键词】真随机数;ADC;非线性反馈多项式;均匀分布
1.引言
在民用和军用电子信息系统中,为了保证信息的存储、传送安全可靠,或者为了避免有源干扰机破坏系统的正常工作,需要对码元、载频、信道进行加密处理。例如,工作在复杂电磁环境下的雷达,为了对抗敌方电子干扰机,在产生低功率射频信号时可使用波形捷变技术,如随机跳频、随机相位调制等等,于是,得到均匀分布的随机调制次序就是首要问题。绝大多数情况下是采用伪随机数序列,伪随机数是根据某种算法得到的,在一定时间内可以保持随机性的数,如通信系统里面常研究的m序列,但是超过一定时间,伪随机数序列仍然难以避免周期性的重复,增加序列长度又带来存储空间拮据的问题。因此,如何得到服从均匀分布的真随机数序列就成为这个问题的一大难点。
所谓真随机数发生器(Truly Random Number Generator,TRNG)是指利用物理方法实现的随机数序列发生器。它是自然界随机物理过程的反映,即使算法及硬件的所有信息都被暴露,也还是无法预测序列元素,即高质量的真随机数发生器产生的随机数永远不具备周期性。TRNG所产生的随机数来源于真实的随机物理过程,如宇宙噪声、电路的热噪声和放射性衰变,很显然,在电子电路应用中使用电路噪声是最可能和直接的选择。
模数转换器(Analog Digital Conver-tor,ADC)广泛应用于通信和雷达系统中,利用ADC采样数据蕴含的电路噪声采样数据得到真随机数是很直接的想法,本文基于这一简单设想,分析其可行性和存在的缺陷,给出实用的改进方法,并给出性能分析。
2.原理与实现方法
2.1 原理
使用ADC芯片采集电路噪声获得随机数的方法案例频繁见诸报导,但大都需要一个专门的电路子系统,如对电路噪声加放大器、在噪声源输出端加大电阻、设计混沌电路扰乱噪声源等等,这些方法除了增加了额外的硬件开销外,所得到的真随机数随机特性并不一定是高质量的,特别的,不一定是均匀分布的:这是因为电路中的噪声源多种多样,有些不服从均匀分布,而且ADC器件本身的电路特性也会导致采样源数据偏离均匀分布[1]。本文首先分析了以上局限性,然后给出一种不增加硬件成本的软件方法,可以在单纯的ADC电路中获得服从均匀分布的真随机数。
一种直觉的想法是,ADC输出的最低几位都应该是噪声的采样值,简单举例来说,一个10位的ADC,参考电压范围±5V,板上噪声电平60mV,那么ADC输出的最低3位都应该是噪声才对,事实是否真的如此呢?表1给出了两款ADC的最低3位实际采样所得序列的比特分布特性(即采样序列中高低电平——‘1’和‘0’的个数对比)结果,BIT0表示最低位,单次采样数据量为65536个,共采样5次,结果是5次的平均值。
从表1可以看出,除了Bit0位的分布特性较好外,另外两位相当不好,其实Bit0位的比特分布特性也不是非常好,这跟直觉相去甚远。以下原因都可能是造成这一结果的原因:首先是板上占主导地位的噪声或干扰分布非均匀导致Bit1、Bit2的比特分布恶化,比如当ADC位数少同时参考电平较小时,又有诸如开关噪声或脉冲干扰存在就会出现类似问题;其次,ADC在从高位向低位转换同从低位到高位转换的不完全对称性也会导致Bit0出现高低电平的几率不是完全均等的。
如果将这种数据作为源数据产生的真随机数应用于加密或抗干扰系统中,就会导致短期内被破解的可能性大大增加。此外,如果想要获得比ADC采样频率高的随机数码率,比如采样时钟1M,想要得到4M的随机数码率,就会出现源数据不够的问题,此时应该对原始数据如何处理,都是下面要解决的问题。
针对以上情况,本文提出了在对源数据进行预处理后,增加一个非线性映射处理,可以保证连续高速地生成均匀分布的真随机数,下面对原理作详细说明。
2.2 实现方法
首先,由于Bit0位的比特分布特性也不是非常好,需要进行预处理,容易想到,可以采集两路或者两个时间段的Bit0序列,将其中一个取反,然后把两个序列通过交替“掺杂”的方式组合成一个新序列,通过这种方法的预处理,再来分析新序列的比特分布特性,可以得到“0”数目跟“1”的数目相差在0.1%以内,这样的序列均匀性很好,我们称之为原始码元序列,下面再做进一步的处理。
但是经过如上异或处理后,仍然不能解决随机数码率大于ADC采样率的要求,比如采样时钟1M,想要得到4M的随机数码率,最终想要得到1到16之间的随机数,以产生的连续出现一段“1”作为源数据,异或得到的新序列就是“01010101010101…”,4位译码后得到“5,5,5,…”,很显然,这样的序列的短期随机性很差。
针对这一问题,本文提出可以使用非线性映射将短期内不那么随机的序列变得不可预测,这种方法在通信调制中得到过应用,比如采用混沌映射得到的随机序列虽然本质上是确定性的,但是由于映射本身的高度非线性导致其不可预测[2]。
为理解上的方便,我们在讨论最终的随机数序列时采用十进制表示,如果需要的是1到16之间的自然数随机序列,那么很显然,选取4bit原始码元组成一个原始码片,变换成十进制后加1即得到一个1到16之间的自然数,将其称之为随机数种子序列,以xi表示第i次抽样组合得到的随机数种子,i≥0。最终的随机数yi由以下5个公式确定:
S0(x)=0 (1)
T-1(x)=x2+1 (2)
Ti(x)=Ti-1(x)+Si(x) (3)
yi=mod(Ti(xi),16) (4)
Si(x)=xyi-1 (5)
并且在计算Ti(x)时,当任何一项ajxb中aj=16时立即归零。很显然,上面的递归计算方法是一个非线性有反馈的迭代过程,这种计算方法因为高度的非线性导致结果短期内不可预测性,即使短期内输入的是同一个数也是如此,这就解决了如果ADC采样时钟低,但又想获得比采样时钟高的随机数输出码率的问题,可以用一次采样的随机数种子得到连续N个不同的随机数结果,由于非线性反馈公式的短期不可预测,所得随机数序列的随机性是可以得到保障的。当然,N不能太高,一般如果序列取值区间在1到M,那么N在(log2M)2到log2M之间取值可以满足需求。
3.性能分析
随机数序列的检验标准很多,在信息安全领域,针对随机序列检测的基本标准有美国商务部国家标准技术协会NIST发布的ITSEC、CC及FIPS系列标准。对于真随机数发生器而言,常用的评价标准有德国BSI发布的AIS31标准。结合上述标准并针对我们的实际应用目的,本文主要检测最终得到的随机数序列码元的分布均匀性、相关性等指标证明本方法的有效性[3]。
需要说明的是,虽然人们的一般目标是产生Mmin~Mmax之间的均匀分布的整数序列,但这最终结果同“0”、“1”随机序列的区别仅在于进制不同,所以以下分析皆基于最终的二进制随机序列。并且,以下结果除特殊说明的外,都是在同一器件和实验条件下5次结果算术平均后的结果。
3.1 跟随特性检测
序列的跟随特性指序列中相邻元素的出现情况的统计,主要是测试长为n比特的序列中00,01,10,11所占比例是否相等。表2给出了随机抽取的三个序列跟随特性检测结果。
由表2可以看出,各个测试单位出现的概率差别不大,特别是在不同的序列中,呈现出来互有多少的特点,所以在一个接近无限长序列中,可以判断出各个测试单位出现的概率是几乎相等的,这证明了被测试序列的跟随特性是满足要求的。
3.2 游程检测
游程是由连续0或者1组成的序列,并且其前后元素与游程的元素不同。游程数目为序列游程、非游程数目总和的一半时,产生的随机序列较好。表3给出了三个超长序列的游程检测结果。可以看出序列的游程检测结果是相当不错的。
3.3 扑克检测
扑克检测是一种均匀性检测,它是先将待测序列划分成若干个长为m(m为任意正整数)的二进制子序列,长为m的二进制子序列有2m种类型,然后检测这2m种子序列类型的个数所占比例是否都接近2-m,是的话序列均匀性好,容易知道当m=1时就是比特分布检测,当m=2时就是跟随特性检测。表4列出了3个被测序列在m分别等于3、5、4、6时子序列类型所占比例偏离2-m最大的一个概率,由表4可以看出,即使偏离最大的一个类型也很接近2-m,证明序列的均匀分布特性很好。
3.4 相关性检测
序列的相关性检测是独立性检测的重要内容,图1(a)和图1(b)分别给出了被测序列的自相关和互相关运算结果,幅值是对峰值进行归一化的结果。
并且,与伪随机码序列不同的是,所得到的真随机数序列自相关结果没有周期性,这也是真随机数序列区别于伪随机序列的一个重要特征。
4.总结及改进展望
本文提出一种基于ADC芯片产生均匀分布真随机数方法,该方法以ADC芯片输出的数据最低位交错取原码反码结合成一个二进制序列,然后使之通过一个非线性反馈多项式算得最终的随机数结果。文章分析了该方法产生的随机数序列的随机特性,证明其实用有效,可以在火控雷达抗干扰、电子战与信息加密中得到应用。
为了增强随机序列的随机特性,有时候还要对随机源进行处理,使其输出的随机序列能够更好的满足统计性检验。例如,采用两路或多路相互独立且相同的随机源各自产生随机数,然后经杂化网络(异或链网络等)扰乱输出位流,再通过一个伪随机数发生器后得到最终的随机数输出,这样一般可以得到更好的随机特性序列,但缺点是得需要额外的硬件、软件开销。
参考文献
[1]宋勇,陈贤富,姚海东.随机数发生器探讨及一种真随机数发生器实现[J].计算机科学,2007,7(2):23-25.
[2]邓洪敏.无线通信系统中混沌跳频和功放预失真技术研究[D].电子科技大学博士论文,2003,12.
[3]万艳,林晓伟,李炜,等.真随机数发生器芯片的设计[J].大众科技,2006,5(6):99-101.
作者简介:巩存根(1981—),男,山东枣庄人,硕士,工程师,研究方向:阵列信号处理。