唐俊龙，涂士琦，肖仕勋，袁攀，汤孟媛，孟帧，邹望辉*
(长沙理工大学，物理与电子科学学院 湖南 长沙 410114)
摘要：采用Montgomery模乘实现RSA算法解决在硬件实现时普遍存在计算速度慢、硬件面积大的缺点。基于TSMC90nm工艺，利用Synopsys系列EDA软件完成了RSA算法verilog代码的逻辑仿真和逻辑综合，形式验证、静态时序分析、布局布线、时钟树综合，实现了RSA公钥加密算法的IP硬核的物理版图，时钟频率达167MHz、面积为109646.08、功耗26.3026 mW，具有一定的应用价值。
关键词：RSA算法，Montgomery模乘，verilog，IP硬核
中图分类号：510.3040；510.1010文献标识码：A
0引言
目前大量超级计算机的不断出现以及量子计算机的不断发展，信息安全越来越成为日常生活中极其重要的部分。RSA算法是公钥密码体制中最早的成员，从1987年公布至今，RSA算法已经成为世界上应用最为广泛的加密算法之一，具有极好的安全性和保密性，在银行系统、电子商务、电子政务、保险系统、军事以及其他领域中得到了巨大推广[1]。本文基于蓝牙加密算法的应用改进，采用DES和RSA混合加密算法替代当前蓝牙技术中通用的AES加密算法。作为混合加密算法的重要环节，RSA算法用于对DES加密算法的加密密钥进行加密。随着市场需求地不断变化以及当前国家对于集成电路产业的大力支持，部分RSA算法的硬件化设备已经进入市场。与传统的软件实现相比，硬件实现具有速度更快、更安全、更稳定、成本更低、产品体积更小等诸多优点。而随着各类改进算法的出现以及微电子技术的不断成熟，RSA 加密算法被更加广泛的使用在类似像银行U 盾和身份 IC 卡等产品上，越来越多的小型硬件设备出现在银行系统、便携式电子产品以及电子商务等领域中[2-3]。
1 RSA算法的基本原理
RSA算法的加解密公式(1)：
加密：
解密： (1)
其中，e、n为加密公钥，d、n为解密私钥，C、M分别为加密密文和解密明文。
，p和q为两个大素数； e为随机选取的素数，满足e和（φ(n)为n的欧拉函数）互质，即。 e取不同的素数时，d通过Extended-Euclidean算法得到，对应特定e可以取一个或多个不同的值，满足e和d的乘积与互质，即 [4-5]。
RSA算法主要包括加解密密钥算法、素性检测和模幂运算等。RSA算法中p、q和e的选取，d和加解密的计算，都涉及到大数运算，素数的产生决定了算法的效率，p和q为至少512bit的大素数，生成主要通过素数定理使用计算机对第n个素数进行估算，素性检测主要有费马定理、Rabin-miller素性检测算法、Solovay-strassen素数测试、Lehmann算法及AKS素数测试算法等。大整数分解的难度大，保证了RSA算法较高的安全性[5]。加解密过程涉及大量模幂运算，模幂运算复杂度高，涉及除法，一次除法运算由多次减法和乘法组成，计算速度较慢，效率低，同时在硬件上实现算法时开销较大。实现快速模幂的关键就是加速取模运算。模幂优化算法主要有Blakley算法，Brickell算法，Barrett算法和Montgomery模乘算法等[6-9]。模幂运算的速度快慢决定了RSA算法的整体效率。
2 RSA算法IP硬核实现路
2.1 IP硬核实现的RSA算法原理与流程
本文实现IP硬核的RSA公钥加密算法主要采用Extended-Euclidean计算解密密钥，费马定理对大素数进行检测，Montgomery模乘算法进行加解密运算。Montgomery算法是目前在计算机软硬件中通用的模乘算法，已经发展出了许多种基于Montgomery算法的实用型软硬件用以实现模乘算法[10]。相比于原始的RSA加密，使用Montgomery模乘的RSA加密，减小了取模的次数，降低了除法的复杂度。Montgomery模乘算法公式如(2)，其中，a和b是与N同位长的大数，ρ= r^len(len指N的位长)，ρ^(-1)是指ρ相对于M的模逆，即ρ^(-1)是满足如下条件的数：ρ*ρ^(-1) mod M = 1；这个条件成立的充要条件是：gcd(N,r)=1[11-12]。基于Montgomery模乘的RSA算法原理框图如图1。
(2)
图1 RSA算法原理框图
IP硬核的实现采用Verilog语言进行RTL级描述，基于Synopsys平台的Verilog Compiler Simulator （VCS）、Design compiler（DC）工具进行逻辑仿真、逻辑综合，Formality和Primetime工具进行形式验证、静态时序分析和物理验证，IC Compiler（ICC）进行布局布线和时钟树综合，RSA算法IP硬核的实现流程图如图2。
图2 RSA算法IP硬核实现流程图
2.2 IP硬核的RSA算法电路实现
IP硬核的RSA算法中Extended-Euclidean、费马定理和Montgomery模乘等功能采用RTL级Verilog语言描述，得到RSA算法顶层模块（rsa_top.v）和子模块Montgomery模乘（rsa_mmm.v）。添加大素数p、q和明文等测试激励，利用逻辑仿真工具VCS对RSA算法的rsa_top.v和rsa_mmm.v的加解密功能进行验证，通过VCS模拟器中的可视化图形调试软件（Discovery Visual Environment，DVE）查看RSA算法模块的仿真波形，加密密文解密后的明文与原始明文一致，同时生成基于Montgomery模乘的RSA算法模块电路原理图如图3。
图3 RSA算法模块电路原理图
2.3RSA算法IP硬核版图的生成
RSA算法的rsa_top.v和rsa_mmm.v模块的逻辑综合利用DC工具，基于TSMC090nm工艺库，加入时钟周期、最大延迟、扇出、驱动、输入/输出延迟、线负载模型、工作条件等设计约束进行translate、optimize和mapping，生成门级网表（Netlist）、Setup Verification File（SVF）、Synopsys Design Constraints File（SDC）和Standard Delay Format（SDF）等文件。其中Netlist由顶层模块（rsa_top）和子模块（rsa_mmm_1~8）组成，Netlist顶层图如图4。DC综合后主要参数如表(1)。
图5RSA算法IP核物理版图
RSA算法IP硬核版物理实现使用ICC工具，导入Netlist和SDC文件，设定芯片尺寸，I/O管脚的排列，pad、宏单元以及电源环位置等实现布图规划（Floorplan）。在布图规划的基础上检查金属布线层和扫描链信息等，进行标准单元放置和优化即为布局（Placement）。插入缓冲（buffer）和时钟网络分层的时钟树综合由于上文完成了静态时序分析过程相对简单，然后进行全局布线（Routing），最终生成可以交付给芯片生产厂商的版图设计结果Generic Data Structures Library（GDSII）， RSA算法IP核6层金属物理版图如图5，面积109646.08，平均功耗为26.3026 mW。
3 结论
本文面向蓝牙技术基于DES和RSA混合加密算法的应用，RSA算法用于对DES加密算法的加密密钥进行加密，采用Montgomery模乘实现RSA算法。基于TSMC90nm工艺，利用Synopsys平台的VCS、DC、Formality、Primetime、ICC等工具，完成逻辑仿真、逻辑综合、形式验证、静态时序分析、布局布线和时钟树综合，最后实现RSA公钥加密算法的IP硬核的物理版图，相比于未采用Montgomery模乘实现的RSA算法软核，在速度、面积、功耗等性能方面更具优势，时钟频率达167MHz、面积为109646.08、功耗26.3026 mW。RSA算法作为目前主流的公钥加密算法，将来的市场需求非常可观，具有一定的应用价值。
参考文献：
陈侨川，一种基于DES和RSA算法的混合加密算法 [D] ，云南大学硕士学位论文，2015.4
[1] 龚文杰，RSA算法的FPGA快速实现[D]，2016.3.28
[2] 张鹏，RSA算法研究及其ASIC设计[D]，2013.3.12
[3] 陈鲁生，沈世镒，现代密码学[M]，科学出版社，2002.7
[4] 任伟，现代密码学[M]，北京邮电出版社，2011.4
[5] 廖彬宇，改进的RSA负载均衡RSA算法[J]，电脑知识与技术，2018.9，14(25):25-26
[6] 陈春玲，齐年强，余瀚，RSA算法的研究与改进[J]，计算机技术与发展，2016.8第26卷第8期
[7] 李云飞，刘菊琨，柳青，改进RSA算法的安全性分析[J]，计算机应用与软件，2018.6第35卷第6期
[8] 徐江涛，傅妍芳，蒙哥马利算法在RSA公钥算法中的应用[J]，电子设计工程，2013.5第21卷第9期
[9] 孙伟，公钥RSA加密算法的改进与实现[D]，安徽大学硕士学位论文，2014.4
[10] 石井等，RSA数据加密算法的分析与改进[J]，济南大学学报（自然科学版），2013.7，27(3).283-286
[11] 孙建林，基于FPGA的RSA快速加密算法的改进[D]，河北大学硕士学位论文，2016.6
[12]
基金项目：国家科技支撑计划项目(2014BAH28F04)；湖南省教育厅创新平台开放基金项目（17K004）；柔性电子材料基因工程湖南省重点实验室
作者简介：唐俊龙(1973—)男(汉族)，博士，副教授，主要研究方向为CMOS数字模拟集成电路设计；
涂士琦(1992—)男(汉族)，硕士研究生，主要研究方向为数字集成电路设计；
邹望辉*(1978—)男(汉族)，博士，讲师，主要研究方向为CMOS数字模拟集成电路设计，
论文作者:唐俊龙，涂士琦，肖仕勋，袁攀，汤孟媛，孟帧，邹望辉*
论文发表刊物:《科技新时代》2019年2期
论文发表时间:2019/4/11
标签：算法论文; 素数论文; 加密算法论文; 时钟论文; 版图论文; 公钥论文; 模块论文; 《科技新时代》2019年2期论文;