0博士论文0由...提交的论文0Mohammed Bakiri0为了获得勃艮第弗朗什-孔泰大区大学计算机科学复杂系统系（DISC）博士学位0工程师和微技术科学博士教育委员会第37号0专业：计算机科学0基于混沌迭代的伪随机数生成器的硬件实现02018年1月8日在贝尔福公开支持，评审委员会成员如下：0Enrico Formenti教授，尼斯索菲亚安蒂波利斯大学主席0西尔万∙康塔索-维维尔教授，洛林大学评审人0Frédéric Magoulès教授，巴黎-萨克莱大学评审人0Christophe Guyeux教授，勃艮第弗朗什-孔泰大区大学考官0Jean-François Couchot博士，副教授和高级研究员，大学主管0勃艮第弗朗什-孔泰大区0Abdelkrim Kamel Oudjida博士，研究硕士和高级研究员，开发中心共同指导0阿尔及尔高级技术中心0N ◦ 2 0 1 8 U B F C D 0 1 40博士论文0由...提交的论文0Mohammed Bakiri0为了获得勃艮第弗朗什-孔泰大区大学博士学位，复杂系统计算机科学系（DISC）0工程师和微技术科学博士教育委员会第37号0专业：计算机科学0基于混沌迭代的伪随机数生成器的硬件实现02018年1月8日在贝尔福公开支持，评审委员会成员如下：0Enrico Formenti教授，尼斯索菲亚安蒂波利斯大学主席0西尔万∙康塔索-维维尔教授，洛林大学评阅人0Frédéric Magoulès教授，巴黎-萨克莱大学评审人0克里斯托夫∙吉耶教授，勃艮第弗朗什-孔泰大区大学考官0Jean-François Couchot博士，讲师和高级研究员，大学指导0勃艮第弗朗什-孔泰大区0Abdelkrim Kamel Oudjida博士，研究员和高级研究员，开发中心共同指导0阿尔及尔高级技术中心0N ◦ 2 0 1 8 U B F C D 0 1 4Je tiens également à remercier les membres de mon jury de thèse particulièrement, Prof.Sylvain Contassot-Vivier et Prof. Frédéric Magoules qui m’ont fait l’honneur d’être lesrapporteurs de cette thèse. Que Prof. Enrico Formenti soit aussi remercié pour avoiraccepté d’être examinateur. Merci pour leurs suggestions et leurs précieux conseils, quiont permis de clarifier et donc d’améliorer ce mémoire.Je tiens aussi à remercier tous les membres de l’équipe AND à Belfort pour leur amitiéet la bonne ambiance qu’ils contribuent à créer, spécialement Amor Lalama, NeserineKhernane et Prof. Raphaël Couturier.Je ne remercierai jamais assez mes parents et mon épouse Radhia qui ont toujours été àmes cotés, mes frère et soeurs (Soumia, Foued, Karima et Walid), pour avoir toujours étéprésents, m’avoir toujours aidé et soutenu, et pas seulement durant mes études. Sanseux, sans leur gentillesse, leurs encouragements et leur dévouement, je n’en serais paslà.0致谢0首先，我要感谢两位导师对我的指导、支持和友谊：ChristopheGuyeux教授是我的第一位导师，Jean-FrançoisCouchot博士从一开始就作为共同导师，最后成为独立导师。尽管他们的日程安排很忙，但他们始终在我身边，分享他们的经验、智慧和对我的研究对象的知识。我的工作和这篇论文没有他们的动力、鼓励、耐心、远见、批判性思维和建议的准确性。与他们一起工作是一种巨大的快乐，我希望能够继续与他们合作很长时间。0我还要感谢AbdelkrimOudjida博士以及IPLS团队的成员们，感谢他们在数字领域的专业知识、鼓励和建议。我非常感激Nouma Izeboudjen、Sabrina Titri、Samir Tagzout、Ibrahim Bouzouia和Mohand TaharBelaroussi对我的支持、鼓励、可用性和信任。这些感谢之词无法表达我对他们的感激之情。CONTENTSList of Abbreviations7IGeneral Introduction9IIScientific Background171Random Number Generators on FPGA191.1General presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191.2Linear Pseudorandom Number Generators. . . . . . . . . . . . . . . . . .221.2.1Linear Congruential Generators . . . . . . . . . . . . . . . . . . . . .231.2.2Linear Feedback Shift Register generators. . . . . . . . . . . . . .241.2.3Look-up Table Optimized Generators . . . . . . . . . . . . . . . . . .261.2.4Twisted Generalized Feedback Shift Register PRNG . . . . . . . . .271.2.5Cellular Automata based PRNGs . . . . . . . . . . . . . . . . . . . .301.3Non-Linear Pseudorandom Number Generators. . . . . . . . . . . . . . .331.4True Random Number Generators . . . . . . . . . . . . . . . . . . . . . . .371.4.1Phase-Locked Loop TRNGs. . . . . . . . . . . . . . . . . . . . . .371.4.2Ring Oscillator TRNGs . . . . . . . . . . . . . . . . . . . . . . . . . .381.4.3Self-Timed Ring TRNG. . . . . . . . . . . . . . . . . . . . . . . . .391.4.4Metastability TRNG. . . . . . . . . . . . . . . . . . . . . . . . . . .391.5.1Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .411.6Statistical Test Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . .431.7Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .482.1Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4901.5 实验结果和硬件分析 . . . . . . . . . . . . . . . . . . . . . . . . . 4101.5.2 硬件比较 . . . . . . . . . . . . . . . . . . . . . . . . . . 4201.6.1 基于FPGA的RNG的统计结果 . . . . . . . . . . . . . . . . . 4702 基于混沌迭代的PRNG 492.1.1Boolean domain. . . . . . . . . . . . . . . . . . . . . . . . . . . . .502.2Unary and Parallel chaotic scheme . . . . . . . . . . . . . . . . . . . . . . .512.4Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .553Quantifying Hardware Performance of Linear PRNGs593.1Methodology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .593.2Linear Complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .593.3Jump Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .603.4Arithmetic Operators and Dynamic Range . . . . . . . . . . . . . . . . . . .623.5Throughput and Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . .633.6Experimental Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .653.7Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .664Hardware Test Platform and Comparison674.1FPGA Platform based on Zynq-EPP for PRNG. . . . . . . . . . . . . . . .674.1.1General Presentation. . . . . . . . . . . . . . . . . . . . . . . . . .674.1.2Hardware Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . .684.1.3SDK Firmware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .694.2New Reconfigurable FPGA Platform for CIPRNG . . . . . . . . . . . . . . .694.2.1General Presentation. . . . . . . . . . . . . . . . . . . . . . . . . .704.2.2Hardware Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . .704.2.3Firmware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .714.3FPGA Global Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . .724.4ASIC Platform for PRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724.4.1General Presentation. . . . . . . . . . . . . . . . . . . . . . . . . .724.4.2ASIC Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724.5Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74IVFrom Unary to Parallel Chaotic Iteration PRNG755Unary Chaotic Iteration PRNG: CIPRNG Multi-Cycle and XOR7704 目录02.1.2 迭代图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5102.3 广义方案 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540III 在FPGA平台上量化PRNG的硬件性能 57CONTENTS55.1CIPRNG Multi-Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .775.2CIPRNG-XOR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .795.3FPGA Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .805.3.1Global Comparison. . . . . . . . . . . . . . . . . . . . . . . . . . .805.3.2Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .815.4ASIC Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .825.5Statistical tests results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84VGeneralized Chaotic Iteration PRNG876.1General idea. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .896.2Mixing Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .916.4FPGA Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .936.5Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95VIGeneral Conclusion977General Conclusion997.1Contribution Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .997.2Perspectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100VIIAnnexes103A Mathematical Proofs105A.1 Further investigations of the chaotic behavior of “chaotic iterations” . . . . . 105A.2 Mathematical chaos of the proposed design of GCIPRNG . . . . . . . . . . 109A.2.1First considerations. . . . . . . . . . . . . . . . . . . . . . . . . . . 109A.2.2Proof of chaos: the internal process . . . . . . . . . . . . . . . . . . 109B PRNG implented on FPGA11505.4.1 ASIC比较 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8205.6 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8406 广义混沌迭代 8906.1.1 迭代函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9106.3 混沌行为 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9206.4.1 统计检验结果 . . . . . . . . . . . . . . . . . . . . . . . . . . 956CONTENTSB.1Linear PRNG on FPGA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115B.2Software part of SoC based Zynq. . . . . . . . . . . . . . . . . . . . . . . 117B.3Software part of AXI-Platform . . . . . . . . . . . . . . . . . . . . . . . . . . 118Bibliography121List of Figures134List of Tables135ABBREVIATIONSRNG . . . . . . . . . . . . Random Number GeneratorPRNG . . . . . . . . . . Pseudo Random Number GeneratorTRNG . . . . . . . . . . True Random Number GeneratorCPRNG . . . . . . . . Chaotic Pseudo Random Number GeneratorLPRNG . . . . . . . . . Linear Pseudo Random Number GeneratorCI . . . . . . . . . . . . . . Chaotic IterationCIG . . . . . . . . . . . . . Chaotic Iteration GeneralizedNIST . . . . . . . . . . . National Institute of Standard and TechnologiesFIPS . . . . . . . . . . . . Federal Information Processing StandardASIC . . . . . . . . . . . Application-Specific Integrated CircuitRTL . . . . . . . . . . . . Register Transfert LevelSDK . . . . . . . . . . . . Software Development KitIP . . . . . . . . . . . . . . Intellectual Property (semiconductor)IOB . . . . . . . . . . . . . Input Output BlockFF . . . . . . . . . . . . . . Flip-FlopDSP . . . . . . . . . . . . Digital Signal ProcessingBRAM . . . . . . . . . . Block of RAM0FPGA . . . . . . . . . . 可编程门阵列0HDL . . . . . . . . . . . . 高级描述语言0HLS . . . . . . . . . . . . 高级综合0SoC . . . . . . . . . . . . 片上系统0CLB . . . . . . . . . . . . 可配置逻辑块0LUT . . . . . . . . . . . . 查找表0SR . . . . . . . . . . . . . 移位寄存器0RAM . . . . . . . . . . . 随机存取存储器0FIFO . . . . . . . . . . . 先进先出8abbreviationsLCG . . . . . . . . . . . . Linear Congruential GeneratorMT . . . . . . . . . . . . . Mersenne TwisterTGFSR . . . . . . . . . Twisted Generalized Feedback Shift RegisterBBS . . . . . . . . . . . . Blum Blum Shub generator0LFSR . . . . . . . . . . . 线性反馈移位寄存器生成器0CA . . . . . . . . . . . . . 元胞自动机0PLL . . . . . . . . . . . . 相锁环0RO . . . . . . . . . . . . . 环形振荡器发生器0VCO . . . . . . . . . . . . 电压控制振荡器0PS . . . . . . . . . . . . . . 外围系统0PL . . . . . . . . . . . . . . 可编程逻辑0AXI . . . . . . . . . . . . . 高级可扩展接口0UART . . . . . . . . . . 通用异步收发器0DMA . . . . . . . . . . . 直接内存访问0S2MM . . . . . . . . . . 从从属到内存映射0MM2S . . . . . . . . . . 内存映射到从属0GE . . . . . . . . . . . . . 等效门0P&R . . . . . . . . . . . . 放置和布线0Gbps . . . . . . . . . . . 每秒十亿比特0我0总体介绍0介绍0动机和问题陈述0尽管随机生成有着悠久的历史，但随着所谓的随机或熵作为服务的出现[1]需求，它仍然是一个热门话题。它也成为物联网设备轻量级安全核心的关键要素。尽管这些生成器在许多应用中被广泛使用，如上述所述，但将它们集成到芯片系统中变得非常有必要，特别是对于物联网和智能卡。因此，当前研究在这个领域的实际目的是为硬件应用提供紧凑、高吞吐量、安全和可重构的伪随机生成器。0让我们回顾一下，随机数生成器算法可以通过生成器的状态空间S，转换映射函数f，从给定状态提取输出的提取器函数g和种子x0来定义。随机输出序列是y1，y2，...，其中每个yt0由之后描述的两个主要步骤生成。第一步根据递推公式xt+1=f(xt)应用转换函数，其中xt和xt+1都属于S。映射函数f可以是在离散和有限状态空间中确定性地产生类似随机数的算法。这样的生成器被称为伪随机数生成器（PRNGs）。相反，f可以基于物理熵源产生随机性，从而使S成为连续空间。整个方法因此被称为“真”随机数生成器（TRNG）。第二步是将函数生成器应用于新的内部状态，得到输出yt，即yt=g(xt)。有各种各样的这种递归生成器，可以是线性的或非线性的，混沌的等等。0伪随机数生成在数学和软件方面更受关注，而硬件和半导体解决方案则深入研究真随机数生成。一方面，线性伪随机数生成器（LPRNG）是线性递归模2（即S是F2）的特例。许多研究工作和解决方案定期提出以提高它们的性能和统计特性，并相应地研究它们的线性性和安全性。不幸的是，只有很少的这些线性伪随机数生成器在硬件层面上进行了详细分析，如FPGA和ASIC。另一方面，混沌伪随机数生成器（CPRNGs）是形式为x0∈R和xt+1=f(xt)的非线性生成器，其中f是一个混沌映射。它们是混沌数学理论的一个有吸引力的应用。解释这种兴趣的原因包括它们对初始条件的敏感性和不可预测性。真正的混沌生成器是这些特性的很好证明：它们的周期是无限的，硬件资源紧凑，统计测试通常相当合理地成功[2,3]。0一个自然的问题是：在尊重Devaney对这种有限状态机提供的混沌数学定义的同时，我们如何在确定性数字系统中注入无序性？在数字嵌入式系统中，一个常见的答案是考虑伪混沌生成器而不是真正的混沌生成器[5,6]。尽管基于混沌现象的TRNG输出质量很高，但是大多数这些技术的制作方式要么很慢（即从给定组件中提取噪声或抖动的速度在几Kbps到Mbps之间[7]），要么很昂贵（例如，使用示波器或激光器提取或测量某些噪声[3]）。此外，将这些TRNG嵌入到纯数字平台中是一个极大的挑战，主要问题是校准来自模拟输入的偏置现象。与理论相比，数字TRNG导致输出的一致性和性能无法控制。相反，混沌伪随机数生成器（CPRNG）似乎是Zynq基于FPGA等SoC平台的一个方便的解决方案[8]。然而，由于浮点数的有限精度和量化，后者可能表现出周期缩短和非均匀分布的输出。此外，这些伪随机数生成器有各种缺点，特别是它们无法通过一些统计测试，并且从密码学家的角度来看，混沌与安全性无关[9]。因此，避免浮点近似及其后果是一个重要的研究目标，已经在各种最新技术提案中进行了研究。TRNG output based on a chaotic phenomenon, most of these techniques are howeverproduced in a manner that is either slow (i.e, in a range of some Kbps to Mbps, to extractnoise or jitter from a given component [7]) or costly (e.g., extracting or measuring somenoise using oscilloscope or laser [3]). Additionally, to embed these TRNGs in a pure dig-ital platform is an extreme challenge, where the main concern is calibration of the biasphenomenon coming from analog inputs. Digital TRNGs lead thus to an uncontrollableuniformity and performance of the outputs compared to the theory. Conversely, chaoticPRNG (CPRNG) appears as a convenient solution in SoC platforms such as Zynq basedFPGA [8]. However, due to the finite precision and quantization of floating point numbers,this latter may exhibit both deflated periods and non uniformly distributed outputs. Addi-tionally, these PRNGs have various drawbacks, particularly they fail some statistical tests,and from a cryptographer point of view, chaos is not related to security [9]. Thus, avoid-ing floating approximation and its consequences is a major research objective, which hasbeen investigated in various state-of-the-art proposals.012 引言0最近，在FEMTO-ST研究所的DISC部门开发了一种软件方法。从形式上讲，这是一个特定二进制函数迭代图中的随机游走。要采取的方向和路径长度由嵌入的生成器定义。实际上，它可以被看作是一种后处理处理，它向嵌入的伪随机数生成器添加了混沌（由Devaney定义）。这种方法的第一个应用是在伪随机数生成器框架中提出的，导致了所谓的基于混沌迭代的伪随机数生成器（CIPRNG，[10, 11]）。从那时起，已经提出了各种改进版本，其中之一是专门为FPGA设计的。0本论文的目标是研究使用混沌迭代生成伪随机数的方法，以便在硬件实现方面提供尽可能广泛的应用覆盖。我们的兴趣集中在使用我们在CDTA研究中心的微电子部门的FPGA和ASIC设备上的硬件/软件设计技能，将新的混沌迭代过程作为随机数生成器集成和实现在SoC/FPGA/ASIC上。换句话说，目标是提出一系列混沌后处理伪随机生成器，以增加它们的统计特性，增加混沌性，同时保持较大的吞吐量，在硬件和软件支持上具有密码学安全性，并且最终独立于技术。0需求和规范0我们在硬件随机数生成器领域的研究中考虑了一些规范，总结如下：0•先前的研究中提出了CIPRNG的初始FPGA实现[11]，其中生成器基于已经被证明具有密码安全性和良好行为（BBS，ISAAC）的伪随机数生成器。0• 提出的CIPRNG的大多数统计测试分析仅在软件级别上执行，使用基本的FPGA实现。0•如前所述，基于混沌迭代的伪随机数生成器（CIPRNGs）使用伪随机数生成器作为选择要迭代的位的策略。这些伪随机数生成器较弱。0引言 130在硬件级别上进行了调查和分析。此外，其中大多数无法通过统计测试。0•大多数随机数生成器的ASIC实现都基于真随机数生成器（TRNG），其使用物理源（激光、晶体管、噪声等）。相反，伪随机生成器也被弱化实现，并且难以通过统计测试。0•最后，除了我们的CIPRNGs之外，FPGA上的混沌硬件伪随机数生成器都无法通过著名的TestU01的BigCrush统计测试（319个测试）。0因此，新的硬件混沌伪随机数生成器需要满足以下要求：0• 在数字系统上注入大部分混沌迭代理论，其中仅考虑定点表示和正数。0•硬件实现与技术无关（无需DSP或块存储器），易于集成到FPGA和ASIC应用的片上系统中。0• 需要高吞吐量、小面积和低功耗。0• 数据宽度范围广泛（8、16、32和64位）、周期长度和k维混沌伪随机数生成器。0• 最终，具有高成功率的统计测试，包括最困难的测试（例如TestU01的BigCrush）。0论文的贡献0本文报告了基于（广义）混沌迭代的硬件伪随机数生成器的设计和评估，作为硬件伪随机数生成器的可能后处理方法，证明了与其他线性和混沌伪随机数生成器相比的优势。该提议侧重于在线性伪随机数生成器上添加混沌作为后处理，在每次迭代中，只更新迭代向量的一部分分量。0本论文的贡献总结如下：0•对FPGA上的大量选定的硬件随机数生成器实现进行了调查。研究了伪随机数生成器和真随机数生成器，同时讨论了线性和非线性生成器的情况。每种方法都有详细的解释，并系统地讨论了实现和统计测试的结果。如果有的话，还介绍了频率、面积大小、弱点和统计评估方面的性能。0•为了研究策略属性，对属于4个家族（xorshift、LFSR、TGFSR和LCG）的18个线性伪随机数生成器进行了物理实现，并在FPGA上进行了面积、吞吐量和统计测试的比较。因此，使用寄存器传输级（RTL）和高级综合（HLS）两种设计流程。基于这项研究，线性复杂性、种子和算术运算与FPGA中部署的资源之间的关系得到了深入研究。据我们所知，没有发表的工作真正深入研究过这种线性伪随机数生成器的硬件实现。• Implementation and tests of these new families of post-processing PRNGs are pro-posed based on chaotic iterations for FPGA and ASIC. The first one is an up-date of CIPRNG [10], in which three CIPRNG variants for FPGA have been de-signed, namely the XOR-CIPRNG, the CIPRNG-MultiCycle, and Multi-Cycle Multi-Dimension (CIPRNG-MCMD) (see [12]). These hardware pseudorandom numbergenerations can reach a very large throughput/latency ratio.014 引言0• 基于混沌迭代的新型后处理伪随机数生成器的实现和测试提出了FPGA和ASIC的方案。第一个方案是CIPRNG[10]的更新，其中设计了三种FPGA的CIPRNG变体，分别是XO
我的内容管理
展开
