随机数在密码学中占有重要的地位

yingujun 2020-06-16 3542

电子说

1.3w人已加入

描述

设计一种超高速全数字真随机数发生器，使用嵌入亚稳态环节的环路振荡器作为随机源。对元胞自动机电路进行改良，向其中添加随机存储的特性，并将其作为后处理电路的一部分，提高了数据的熵值和伪随机性。后级电路采用异或链电路和 DES 加密算法，提高随机序列的每比特熵值，改善输出的统计特性。该方案具有良好的可移植性，极高的生成速率，偏低的资源使用和自定义扩展功能。通过 FPGA 版级验证，真随机数生成速率可达 1 Gb/s，具有一定的应用价值。

DOI：10.19339/j.issn.1674-2583.2020.04.006

一种基于随机储存元胞自动机真随机发生器［J］。集成电路应用， 2020， 37（04）： 18-21.

True Random Generator Based on Random Storage Cell Automaton

JI Lei， PAN Weiqing， ZHI Yanan

Abstract — In this paper， a ultra-high-speed all-digital true random number generator is designed.The designer uses ring oscillators embedded in a metastable state as a random source. The cellular automaton circuit is improved， and the random storage feature is added to it as a part of the post-processing circuit， which improves the entropy value and pseudo-randomness of the data. The post-stage circuit uses XOR circuit and DES encryption algorithm to increase the entropy value of each bit of the random sequence and improve the statistical characteristics of the output. This solution has good portability， extremely high generation rate， low resource usage， and custom extension functions. Through FPGA-level verification， the true random number generation rate can reach 1 Gb/s， which has certain application value.

Index Terms — TRNG， ring oscillator， metastable state， cellular automata， DES， FPGA.

随机数在密码学中占有重要的地位，几乎所有的密码算法都要用到一些对攻击者来说必须是秘密的数据，而其中密钥必须是随机数。随着加解密技术的快速发展，基于软件实现的伪随机数发生器可能无法满足安全性的要求，虽然基于物理随机源的 TRNG 能保证安全性，但其产生的真随机数的质量不高，生成速率偏慢。考虑到 5G 时代的到来，基于区块链、物联网、车联网、智慧城市技术的快速发展，海量的数据需要在信息交互节点进行加密传输，这对真随机数生成的速率有了更高的要求。

本文设计了一种超高速真随机数发生器，其具有可移植性好，生成速率高，实现成本低廉的特点并具有自我扩展特性。实际测试中，真随机数生成速率高达 1 Gb/s，吞吐量/资源高于 1 Mb/LUT，远远高于常规真随机数发生器吞吐量百兆级别，0.3 Mb/LUT 左右的性能。

1 真随机整体设计

本文整体架构如所示，框架包括 5 部分：基于亚稳态的环振器真随机源，基于随机储存的元胞自动机电路，异或链电路，DES 电路和千兆光口输出单元。

J.D. Golic 最早提出 Fibonacci 和 Galois 环形振荡器电路，但随机数生成速率偏低。2008 年，I.Vasyltsov 等人在 Fibonacci 和 Galois 环形振荡器的基础上引入了亚稳态结构，减少所需熵的积累时间。文献中，朱亮亮等人向其中引入控制环节，降低发生器功耗。本文随机熵源采用方案。

控制信号为低电平时，大环路断开，各反相器自成环路，受到半导体噪声的影响，他们的输出会在亚稳态区域波动。当控制信号为高电平的时候，各反相器接入大环路，迅速离开亚稳态区域，并进入稳态区域，此时其输出具有随机性。

二进制系数 fi 决定环振器的反馈连接。当 fi＝1 时，反馈连接；当 fi＝0 时，反馈断开；反馈多项式可以表示为式。

（1）式中，n 为反相器个数。为了确保输出不会恒定不变，多项式须满足式。

必须保证 n 为奇数，h（x）不能被 1+x 整除，且 f（x）可以被 1+x 整除。如果反馈多项式为本原多项式则以上都可以满足。

本文采用 36 个 7 阶 Fibonacci 震荡环，28 个 7 阶 Galois 震荡环作为真随机源。7 阶本原多项式共 18 个，重复 3.5 次使用，其输出作为随机储存元胞自动机电路的选择输入端。7 阶本原多项式如所示。

以上输出的序列具有真随机和伪随机性，但数字熵源的统计特性往往不够理想，在物理随机过程采样中，会引入偏差和相关性，所以需要添加后处理电路提减小偏差和相关性。

元胞自动机的概念最初被 John von Neumann 和 Ulam 提出，并常用于物理、生物和化学的建模，也用于生成伪随机序列，是常用的后处理算法之一。元胞自动机是元胞的有限阵列，由相同的元胞组成，根据局部过度功能同步并行发展，且只能与他们最近的邻居通信。其可以由四元组（Z，Q，V，f）所定义，其中 Z 代表 d 维的细胞空间，Q 代表可能元胞可能状态组成的集合，V 表示局部规则使用的邻域，f 代表本地规则。初始时，每个元胞都有一个初始状态，根据本地规则和邻域联系，细胞状态发生变化。

初级元胞自动机是一个基本元胞自动机，一维细胞空间 Z，元胞状态 Q＝{0，1}，邻域 V＝（-1，0，1），本地规则 f：Q3→Q，Wolfram 在数学上证明了它作为高性能随机数发生器的适用性，可以并行的有效实现，如式。

最上方三个方块表示所有当前时刻 n 可能的邻域状态，下一单元格代表下一时刻元胞输出的状态。本地规则被下一时刻序列的二进制值所命名。

2014 年，一种基于储存的元胞自动机被提出，其中 x，y，z 为包括 0 的正整数［9］。元胞的下一状态的输出与相邻元胞和本身的过去状态有关，如式。

最近，一种基于随机储存的元胞自动机被提出，Q＝{0，1}，邻域 V＝（-1，0，1）。其中，τi是随机值，其小于等于元胞储存的状态数 M，元胞的下一状态可以随机地由当前状态，以及过去状态确定，如式。

本文设计一个基于随机储存的元胞自动机，其元胞储存状态数 M 为 1，本地规则为 R150，其τi的值由上级的亚稳态震荡环的输出决定。0 代表τi＝0，输出当前状态；1 代表τi＝1，输出上一状态。其元胞单元电路如图 5 所示。bit_out 为该元胞自动随机数的输出端，连接到异或链电路。bit_i_m 为随机储存输出端，连接与其相邻的左右两个元胞单元。

随机储存的元胞自动机包含 64 个元胞环形连接，其相互连接图如图 6 所示，其中只有一个 bit_i_m 初始值为 1。系统开始工作后，每个时钟周期生成 64 个 bit_out，每相邻 8 位进行异或压缩操作，送入下级异或链电路中。

为了减小偏差，使得“0，1”分布均匀，采用异或链进行处理，对数据进行校正，结构如图 7 所示。本文采用 8 路异或链电路，每路由 8 个触发器进行异或链纠偏，每个时钟周期输出 8 bit 数据，输出偏执非常小。

1940 年代末，香农提出了设计密码系统的两个基本方法-混淆和扩散。扩散和混淆可以极大改善输出序列的统计特性，提高熵值，弥补统计缺陷。

设计中最后采用 DES 加密算法对数据进一步后处理，为 DES 加密算法处理过程。首先对上级输入的 8 bit 序列进行数据重排，扩展到 128 bit，高 64 bit 和低 64 bit 分别作为明文和密钥输入，进行 IP 初始置换，然后 16 轮迭代变换，最后左右交换后进行逆初始置换（IP-1）得到 64 bit密文，作为真随机数输出序列，16 轮迭代采用 Feistel 密码结构对明文和密钥进行混淆和扩散。其中置换移位操作可获得扩散，非线性函数 f 操作可获得混淆。

2 实验验证

本文设计真随机发生器在 FPGA 上进行实验实现，型号为 xc7z035ffg676-2。外接输入时钟为 100 MHz，经过 PLL 倍频到 500 MHz 后，最后输出真随机输出速率高达 1 Gb/s。实现过程中没有使用任何布局布线约束，完全由设计软件自动处理。PC 端通过光口接受 126 组数据，每组 1 Mbit，使用NIST SP-800-22 随机数测试套件进行随机性评估测试。测试规定当测试通过率都大于 96 %时，则认为通过该项测试；如果数据通过全部 15 项测试，则认为序列是真随机的。

为测试结果，数据完全通过试。

为体现本文所设计的真随机数发生器的性能，本设计与国内外已经公开发表的真随机数发生器进行比较，其中单个 LUT 资源相当于一个 LE 资源；可移植性的判断是基于实现时是否使用特殊器件或手动布局布线，如使用则移植性较差，对比结果如表 3 所示。在吞吐量方面，本文设计的真随机数发生器远超常规数字发生器的百兆级别。吞吐量/逻辑资源比为 1.107 Mb/LUT，远大于常规 0.3 Mb/LUT，更加节省资源。移植性方面由于没有使用特殊器件和物理约束实现，因此可以快速集成到芯片或 FPGA 当中。

由于元胞自动机结构简单，易扩展的特性，本文对该设计的自我扩展性能进行了实验验证，本文将 64 个元胞自动机裁剪为 32 个、16 个，减少硬件资源分别为 143LUT、200LUT，并依次重新实现设计，生成速率分别为 500 Mb/s、250 Mb/s，结果均能通过 NIST SP800-22 测试。实验表明该随机数发生器具有扩展性能，使用者可以根据自己实际需求自我进行裁剪或扩展。

3 结语

本文介绍了一种新的数字真随机数发生器，解决现有真随机数发生器生成速率，资源消耗，可移植性和扩展性无法全面的兼顾的问题。实际测试真随机数生成速率可达 1 Gb/s，吞吐量/资源比为 1.1 Mb/LUT，远远高于常规真随机发生器吞吐量的百兆级别和 0.3 Mb/LUT 的吞吐量/资源比。该方案纯具有资源消耗低，吞吐量极高，可移植性好和可扩展的特点。便于集成到芯片和 FPGA 中，缩短开发周期，具有很好的实际应用价值，可满足了未来区块链、物联网、车辆网、智慧城市中需要大量真随机数进行信息加密的场合。
责任编辑:pj

打开APP阅读更多精彩内容