【更新，参加7月期】基于Xilinx Spartan-3E的真随机数发生器的设计

huiyuanai3

文档   基于Xilinx Spartan-3E的真随机数发生器的设计.rar (643.33 KB, 下载次数: 295 )

2012-6-25 08:55 上传

点击文件名下载附件

       随机数检测标准.rar (1.97 MB, 下载次数: 292 )

2012-8-5 22:17 上传

点击文件名下载附件

      

源码   source.rar (2.59 KB, 下载次数: 200 )

2012-8-5 19:36 上传

点击文件名下载附件

视频  

     

          基于Xilinx Spartan-3E的真随机数发生器的设计

Song-Linyuan

Harbin Institute of technology at Weihai

--------------------------------------------------------------------------------------------

摘要 随机数发生器是信息安全领域不可或缺的重要组成部分，广泛应用于金融、军事等信息安全保密通信的电子设备中。目前，随着对随机数发生器体积、功耗接口方式以及随机数质量等方面要求的提高，设计集成化芯片或IP核形式的真随机数发生器成为一种必然。本文研究了真随机数的数字实现方案，在Xilinx的Spartan-3E FPGA中实现了随机数的生成，利用uart将生成的真随机数上传至PC，对生成的随机数进行FIPS140-1随机数质量检测，结果表明随机数质量优良，可以胜任个场合的需求。

关键词 真随机数发生器; FPGA; uart; 随机数质量检测

--------------------------------------------------------------------------------------------

0 引言

随着计算机技术、互联网以及其他数字技术的发展，开放式的信息共享系统得到了很大发展，人们在享受网络带来的方便、快捷的同时，却在信息安全方面遇到了黑客、木马等不安全因素的挑战。随即就产生了对信息的生成、传输、存储等各个方面进行保护的要求，而这种保护通常采用信息加密来实现。

真随机数发生器(TRNG)是信息加密设备中一个重要的组成部分，它产生的不可预知、不可再现的密钥数字串对信息加密有着重要的作用。在密码学领域，密钥管理、众多的密码学协议、数字签名和身份认证等都要用到随机数。随机数是作为密钥的补充信息，辅助信息和初始化向量来使用的，无论是在非对称算法中的私钥，还是对称算法中的密钥，为了保证其密码系统的安全性，原始钥匙都需要由独立的随机数算法来生成。从某种程度上讲，随机数的随机性决定了整个加密算法的性能。

近年来，FPGA在信息安全、计算机逻辑运算与接口电路、数字化仪表、图像系统、数字通信等领域中FPGA已成为最热门的产品之一。目前，FPGA加密产品中的随机数大都是利用线性反馈移位寄存器(LFSR)产生的伪随机数。由于伪随机数的可预测性，给信息安全构成了巨大的威胁。故利用编程的方法在FPGA上产生高质量的真随机数，对利用FPGA所开发产品安全性的提高具有深远的意义。

1 随机数的概念及应用

随机数就是取一个特定值的随机变量, 实用中是使用随机数所组成的序列。根据所产生的方式, 随机数序列再可以分为两类：

• 伪随机数序列。伪随机数序列由数学公式计算所产生。根据种子的不同，可以产生不同的随机序列。但这种方式产生的随即序列是重复的且是可以预测的，故具有伪随机性。线性反馈移位寄存器(LFSR)是产生伪随机序列的最常用方法。

• 真随机数序列。真随机数序列是不可预计、不可再现的，因而真随机数序列不可能出现周期性重复。它只能由随机的物理过程所产生, 如电路的热噪声、宇宙噪声、放射性衰变等。当前，真随机数发生器大都以模拟电路的形式通过放大电阻热噪声来产生。

真随机数发生器(TRNG)是信息加密设备中一个重要的组成部分，它产生的不可预知、不可再现的密钥数字串对信息加密有着重要的作用。在密码学领域，密钥管理、众多的密码学协议、数字签名和身份认证等都要用到随机数。随机数是作为密钥的补充信息，辅助信息和初始化向量来使用的，无论是在非对称算法中的私钥，还是对称算法中的密钥，为了保证其密码系统的安全性，原始钥匙都需要由独立的随机数算法来生成。从某种程度上讲，随机数的随机性决定了整个加密算法的性能。

随机数不仅应用于信息安全领域，而且在扩频通信、博采、赌博机、音乐和图形合成、模拟和测试等多个领域都有着广泛的应用。科学家、军事专家、加密专家、软件开发者等都在广泛地使用着随机数发生器。它们被用于科学研究，如蒙特卡洛模拟。它们还被用于超常规现象的研究，因为在该类研究中随机性是必要的前提条件。

2 Spartan 3E Starter Kit FPGA 开发板简介

Spartan®-3E FPGA 入门套件是一款全面的开发板解决方案，能够让设计者立即获得 Spartan-3E 系列的功能。该开发板采用XC3S500E作为主控FPGA芯片，做工精良、资源丰富，可以完成大部分设计需求。图1给出了此开发板的直观效果图。表1给出了该开发板的板上资源。

图1 Spartan 3E Starter Kit FPGA开发板

表1  Spartan 3E Starter Kit FPGA开发板资源一览

Xilinx芯片组	Spartan-3E（XC3S500E-4FGG320C）
	多达232个用户I/O
	320FBGA封装
	10,000逻辑单元，500,000门逻辑门
	Xilinx64宏单元 XC2C64A CoolRunner CPLD
	Xilinx 4 Mbit Platform Flash configuration PROM
时钟	50 MHz有源晶振
	8脚DIP插座晶振输入（可选）
	SMA接口时钟输入
存储器	64M(512M位) DDR SDRAM, 可做16位数据接口, 时钟100+ MHz
	16M (128M位) 并行 NOR Flash (英特尔标准存储器)
	可做FPGA配置存储器
	存储MicroBlaze代码的镜像文件
	16 Mbits of SPI 串行flash存储器(意法半导体)
	可做FPGA配置存储器
	存储MicroBlaze代码的镜像文件
接口	PS/2鼠标，键盘接口
	VGA显示接口
	10/100M 以太网接口
	2个RS232串行接口（一公、一母）
	USB下载与调试接口
	100个扩展接口
	一个旋转编码器加按钮
	四个滑动开关、8个LED、四个按键
	3个6脚扩展接口
显示	16 字符 - 2 行 LCD
目标应用	消费类电子，通讯，存储，图像处理，控制等

3 真随机数发生器的设计


3.1真随机数发生器的实现方案

由于真随机数发生器产生序列的随机性，恰当的选择熵源是保证随机数质量优良的前提条件。这里选用振荡采样法，利用时钟的相位抖动作为熵源获取随机数。

振荡采样法是指通过D触发器把两个独立的振荡信号进行数字混合，用低频信号采样高频信号，利用环形振荡器的频率抖动作为随机源，并进行后处理，从而得到随机数序列。其基本结构如图2所示，低频振荡器的上升沿通过D 触发器对高频振荡器的输出进行采样。振荡器的抖动引起每次采样时刻的不确定性，从而使输出序列具有随机性。大量实验数据表明，如果可以保证低频振荡器的周期间抖动的均方根值δ与高频振荡的周期T满足2δ /T >1.5，则可以认为每次采样之间是不相关的。                                          

图2 基于振荡器的真随机数发生器

3.2真随机数发生器的RTL设计3.2.1 TRNG模块的设计

TRNG模块完成随机数的生成，其基本结构如上图2所示。其中低频振荡器采用开发板上的50MHz有源晶振产生的时钟信号。高频振荡器采用如图3所示的由反相器链构成的环形振荡器产生的高频信号。每级环形振荡器采用7个反相器首尾相接，为了获得质量优良的随机数，共使用10级振荡器，输出异或后，经由触发器同步后作为输出，如图4所示。这样，只要有一级振荡器发生相位偏移，输出就会发生变化。

图3 由反相器链构成的高频振荡器

图4 trng模块结构图

3.2.2 uart模块的设计

在嵌入式开发和FPGA设计中，串口uart是使用非常频繁的一种调试手段，为了能够将生成的随机数上传至PC以便进行质量测试，特设计了uart模块。

串口一般在台式机上都会有，随着笔记本电脑的使用，一般会采用USB转串口的方案虚拟一个串口供笔记本使用。图5为uart串口的结构图，串口有9个引脚，但真正连接入FPGA开发板的一般只有两个引脚。这两个引脚是：发送引脚TxD和接受引脚RxD。

图5 串口的引脚功能图

串口发送数据的格式可由图6所示，在TxD或RxD这样的单线上，是从一个周期的低电平开始，以一个周期的高电平结束。他中间包含8个周期的数据位和一个周期针对8位数据的奇偶校验位。每次传送一个字节数据，他包含的8位是由地位开始传送的，最后一个传送的是第7位。

图6 串口发送串行数据的格式示意图

设计的uart模块的时序仿真图如图7所示，由图可以看出，模块完成了预定功能。

图7 uart模块时序仿真图

3.2.3 顶层模块的设计

顶层模块的设计如图8所示。

图8 顶层模块的设计

4 真随机数的评估

为了能够对随机数的质量进行评估，许多研究人员提出了不同的随机序列性能测试方法。这里采用NIST SP800-22标准评估随机数质量。该标准对随机数进行以下16种测试。

1	频率检验	Frequency Test
2	块内频数检验	Frequency Test within a Block
3	游程检验	Runs Test
4	块内最长游程检验	Test for the Longest Run of Ones in a Block
5	二元矩阵秩检验	Binary Matrix Rank Test
6	离散傅里叶变换检验	Discrete Fourier Transform Test
7	非重叠模块匹配检验	Non-overlapping Template Matching Test
8	重叠模块匹配检验	Overlapping Template Matching Test
9	Maurer 的通用统计检验	Maurer’s “Universal Statistical” Test
10	Lempel-Ziv压缩检验	Lempel-Ziv Compression Test
11	线性复杂度检验	Linear Complexity Test
12	序列检验	Serial Test
13	近似熵检验	Approximate Entropy Test
14	累加和检验	Cumulative Sums Test
15	随机游动检验	Random Excursions Test
16	随机游动状态频数检验	Random Excursions Variant Test

对每一种测试方法，相应于测试序列，会产生一个相应的P值。对于选定的显著性水平α（在这16种方法中，显著性水平α=0.01），若P≥α，则认为该序列通过该测试，否则视为未通过。

经过随机数发生器产生了近300MB的随机数，送入软件进行测试，以200组为单位进行计算，每组位数为1000000位，4-9为检测报告。图 9给出了随机数质量测试的结果，结果表明随机数质量优良，可以胜任各场合对随机数的要求。

图9 检测报告

经过整理主要结果数据见表2、表3。

表2 检测结果（一）

frequency	block-frequency	cumulative-sums	runs
0.9950	0.9900	0.9900	0.9950
longest-run	rank	fft	overlapping-templates
1.0000	0.9950	0.9850	0.9850

表3 检测结果（二）

universal	apen	random-excursions	linear-complexity
0.9900	0.9850	0.9916	0.9800
serial	lempel-ziv	random-excursions-variant
0.9950	0.9850	0.9832

经过大量的数据统计结果显示，随机游动状态频数检验最低的通过率为0.96263。随机数性能较好，所有参数均在0.98之上，绝大多数参数能在0.99之上，随机数发生器的制作令人满意。

5 结论

设计了基于FPGA的真随机数发生器，该方案克服了以往随机源所必须的模拟电路中的噪声的缺点，在数字电路中产生连续的亚稳态，可以以IP核的形式予以再利用。经NIST SP800-22随机数质量评估标准测试，随机数质量优良，可以胜任各种场合对随机数的需求。

参考文献

[1]李新兵. 兼容ARM9的软核处理器设计[M]. 北京: 机械工业出版社

[2]王春平, 张晓华, 赵翔. Xilinx 可编程逻辑器件设计与开发[M]. 北京: 人民邮电出版社.

[3]徐敏, 孙恺, 潘峰. 开源软核处理器OpenRisc的SOPC设计[M]. 北京: 北京航空航天大学出版社.

[4]吴燕雯, 戎蒙恬, 诸悦, 朱甫臣. 一种基于噪声的真随机数发生器的ASIC设计与实现[J]. 微电子学, 2005,35(2):213-216.

[5]Bock H, Bucci M, Luzzi R. An offset-compensated oscillator-based random bit source for security applications. Lecture Notes in Computer Science, pp. 268–281 (2004)

[6]Bucci M, Luzzi R. Design of testable random bit generators. In: Cryptographic Hardware and Embedded Systems-CHES 2005, Edinburgh, UK. Lecture Notes in Computer Science, vol. 3659, pp. 147–156. Springer, Berlin (2005)

[7]Bucci M, Germani L, Luzzi R. A high-speed oscillator-based truly random number source for cryptographic applications on a smart card IC. IEEE Trans. Comput., 403-409 (2003).

[8]Bock H, Bucci M, Luzzi R. An offset-compensated oscillator-based random bit source for security applications. Lecture Notes in Computer Science, pp. 268–281 (2004)

[9]Bucci M, Luzzi R. Design of testable random bit generators. In: Cryptographic Hardware and Embedded Systems-CHES 2005, Edinburgh, UK. Lecture Notes in Computer Science, vol. 3659, pp. 147–156. Springer, Berlin (2005)

[10]Bucci M, Germani L, Luzzi R. A high-speed oscillator-based truly random number source for cryptographic applications on a smart card IC. IEEE Trans. Comput., 403–409 (2003)

youlia

和我的开发板一样，关注下

steven_wgq

学习一下……

helo929

第一次來這邊留言，看這麼內容覺的這裡的大大好強啊~~~

1300961081

回复 1# huiyuanai3


    markmarkmarkmarkmarkmark

twotiger007

excellent, great

forevercyc

MARK一下，以后看

huiyuanai3

更改过了~

xiayngg

xie xie xie xie xie xie

xiaoyuzhong

支持下