已阅读5页,还剩87页未读, 继续免费阅读
(微电子学与固体电子学专业论文)1024位rsa算法的vlsi实现.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2 0 0 6 矩 中国科学技术大学硕士学位论文 摘要 求解两个大素数的乘积在计算上非常容易,而要分解两个大素数的积求出它 的因子则是世界上公认的数学难题。r s a 算法正是一种基于大数因子分解的算 法。r s a 算法在数据加密和数字签名技术作为保证信息安全的重要手段己得到 了广泛的应用。从1 9 7 8 年开始,r s a 算法的研究十分繁多,已取得的成果主要 集中在m o n t g o m e r y 模乘算法的改进方面。但随着s o c 设计方法的兴起,将r s a 算法融入s o c 中将是一个非常有益的尝试。本文给出了r s a 算法从系统级建模、 r t l 级实现、f p g a 验证到易于转换成a s i c 的设计综合的完整流程,为相关的 设计提供了宝贵经验。 现代芯片设计的关键有两个方面,一是设计周期,二是芯片性能。而r s a 算法实现的多样性和复杂性,大大限制了r s a 算法的设计周期和运算速度。 在缩短设计周期方面,本文介绍了一种基于系统级算法的快速成型实现流 程。从一个好的构思到芯片的诞生,其研发过程刻不容缓。在系统级设计阶段确 定r s a 的实现算法并对其有效评估及优化,为以后的r t l 级设计节约大量时间, 也为最终能否流片提供了指导,有关方法己撰写成论文“一种基于系统级算法的 芯片快速成型设计流程”。 在提高芯片性能方面,本文提出了基于流水线、查找表技术,并带有c s a 、 c l a 结构的m o n t g o m e r y 模乘改进算法,较大地提高了r s a 核心运算速度及整 体运算速度。利用s y n o p s y s 的综合工具,采用s m i c 的0 1 8 “m 的工艺库对设计 进行了综合。在自行设计的f p g a 测试系统中,时钟频率为1 0 0 m h z 时,测得 1 0 2 4 位r s a 算法运算速度为每秒1 2 0 次左右。 该运算速度在不使用片内微处理器来实现r s a 算法中是比较快的,特别在 r s a 算法基于s o c 的快速成型设计流程时,其能更好地与性能不断提高的微处 理器核融合为新的基于s o c 的设计,很有实用价值。 关键词:r s a 算法,m o n t g o m e r y 改进算法,设计流程,f p g a ,v l s i 2 0 0 6 链 中国科学技术大学硕:l 二学位论文 a b s tr a c t i t i sv e r ye a s yt oc o m p u t et h ep r o d u c to ft w ob i gp r i m en u m b e r sb u td i m c u l tt o g e tt h e s et w ob i gp r i m en u m b e r sd e c o m p o s e df r o mt h e i rp r o d u c t t h i sp r o b l e mi st h e o n eo ft h em o s td i m c u l to n e si nm a t h sd o m a i n r s aa l g o r i t h mi sj u s tb a s e do nt h i s d i f f i c u l tp r o b l e m ,w h i c hi sw i d e l yu s e di nd a t a e n c r i p t i o na n dd i g i t a ls i g n a t u r ea sa v a l i dm e t h o di ni n f o r m a t i o ns e c u r i t y s i n c e19 7 8 ,m a n yp e o p l eh a v eb e e nd o i n gm a n y r e s e a r c h e so ni t ,h o w e v e r ,t h e s er e s e a r c h e sa r ep a i dm u c ha t t e n t i o nt ot h er e d u c t i o no f m o d u l a r m u l t i p l i c a t i o na l g o r i t h m w i t ht h ed e v e l o p m e n to fs o c ( s o c :s y s t e mo na c h i p ) d e s i g nm e t h o d ,i ti sav a l u a b l ea t t e m p tt or e a l i z er s aa l g o r i t h mi ns o c d e s i g n t h ec o m p l e t ed e s i g nf l o wf r o my s t e ml e v e l m o d e l i n gt or t lf r t l :r e g i s t e r t r a n s i s t e rl e v e l ) d e s i g nt h e nt ov e r i f i c a t i o no nf p g af f p g a :f i e l dp r o g r a m m a b l e g a t ea r r a y ) a n dl a s tt o d e s i g ns y n t h e s i s t h a ti s e a s i l yr e l i a e d i na s i c ( a s i c : a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) w a sg i v e ni nt h i st h e s i s ,w h i c hc a np r o v i d e s o m eg o o di n s t r u c t i o n st ot h i sk i n do f d e s i g n t h e r ea r et w ok e ya s p e c t si ni cd e s i g n ,o n ei sd e s i g nc y c l ea n dt h eo t h e ri sc h i p p e r f o r m a n c e t h ed i v e r s i t ya n dc o m p l e x i t yo fr s aa l g o r i t h ml i m i tt h ed e s i g nc y c l e a n dc h i pp e r f o r m a n c e o nt h ea s p e c to fd e s i g nc y c l e ,ad e s i g nf l o wf o r ms y s t e ml e v e la l g o r i t h mt oc h i p r a p i dp r o t o t y p i n gw a si n t r o d u c e di nt h i st h e s i s f r o mag o o di d e at oac h i p ,t h e r e s e a r c ha n dd e v e l o p m e n tc a n tw a s t ea n yt i m e d u r i n gs y s t e ml e v e ld e s i g n ,i no r d e r t os a v et h et i m eo fr t ld e s i g na n dt e l lu sw h e t h e ro u rd e s i g nc a nb er e a l i z e di nc h i p , t h ee v a l u a t i o na n do p t i m i a z a t i o no fr s aa l g o r i t h mm u s tb ed o n ei ns y s t e ml e v e l d e s i g n t h i sd e s i g nm o t h o dh a sb e e nd e s c r i b e di nm yp u b l i s h e dp a p e rn a m e d ”a d e s i g nf l o wf o r ms y s t e ml e v e la l g o r i t h mt oc h i pr a p i dp r o t o t y p i n g ” o nt h e a s p e c t o f c h i pp e r f o r m a n c e , ar e d u c t i o no f m o n t g o m e r y m o d u l a 卜m u l t i p l i c a t i o na l g o r i t h mb a s e do np i p e p l i n e ,l o o k u pt a b l e ,c s a ( c s a :c a r r y s a v ea d d e r ) ,c l a ( c l a :c a r r yl o o k a h e a da d d e r ) a n do t h e rd e s i g ns k i l l sw a s i n t r o d u c e di nt h i st h e s i s t h i sh a r d w a r es t r u c t u r ec a ns p e e du pm o d u l a r m u l t i p l i c a t i o n c o m p u t a t i o na n dr s ac o m p u t a t i o n iu s e ds y n t h e s i st o o io fs y n o p s y sc o r p a n d 0 18 9 mt e c h n o l o g y l i b r a r yo fs m i cc o r p t os y n t h e s i z em yd e s i g n it e s tr s a a l g o r i t h mi nx i l i n xf p g ab o a r dw h i c hw a sd e s i g n e db ym ys e l f w h e nt h eg r o u p c l o c ki s10 0 m h z ,t h es p e e do fm yr s aa l g o r i t h mc o m p u t a t i o nw a sa b o u t12 0p e r s e c o n d t h i st e s tr e s u l ti sb e t t e ra m o n gt h i sk i n do fr s a a l g o r i t h md e s i g nt h a td o n th a v e m p u ( m p u :m i c r o p r o c e s su n i t ) i nc h i p e e s p e c i a l l y ,w h e nr s aa l g o r i t h md e s i g ni s b a s e do ns o cr a p i dp r o t o t y p i n g ,i tc a nb ec o m b i n e dw i t hm o r ea n dm o r ef a s t e rm p u i ns o c t h a ti sv e r yv a l u a b l ei nf e a t u r er s a a l g o r i y h md e s i g n k e yw o r d s : r s aa l g o r i t h m ,m o n t g o m e r yr e d u c t i o na l g o r i t h m ,d e s i g nf l o w , f p g a ,v l s i 中国科学技术大学硕士学位论文 第一章绪论 本章介绍了密码体制,r s a 算法相关知识及国内外相关的研究现状,讨论 了r s a 算法的研究方法、意义等。 1 1 密码体制及其分类 密码体制的基本思想就是将要保护的信息变成伪装信息,只有合法的接收 者才能从中得到真实的信息。 表1 1 介绍了密码体制中的基本概念。 表1 1 密码体制的基本概念 基本概念英文解释 明文p l a i n t e x t 待加密的消息 密文 c i p h e r t e x t 被加密过的消息 加密 e n c r y p t i o n 用某种方法伪装消息以隐藏它的内容的过程 解密 d e c r y p t i o n 把密文转变为明文的过程 加密和解密算法的操作通常都是在一组数据的控 密钥 k e y制下进行的,分别称为加密密钥( e n c r y p t i o nk e y ) 和解密密钥( d e c r y p t i o nk e y ) 密码体制 c r y p t o s y s t e m 由算法以及所有可能的明文,密文和密钥组成 用于加密和解密的数学函数,通常情况下有两个, 密码算法 a l g o r i t h m 一个用于解密,一个用于加密 密码体制的示意图如图1 1 所示。 2 0 0 6 正 中国科学技术大学硕士学位论文 图1 1密码体制示意图 根据密钥的特点,密码体制分为对称和非对称密码体制两种。对称密码体制 又称私钥密码体制,非对称密码体制又称公钥密码体制。私钥密码体制中加密密 钥和解密密钥是一样的或彼此之间容易相互确定。私钥密码体制的一个严重缺陷 是在任何密文传输之前,发送者和接受者必须使用一个安全信道预先传递密钥。 在公钥密码体制中,解密密钥和加密密钥不同,从一个难于推出另一个来,解密 和加密是可以分离的,通信双方无需事先交换密钥就可以建立起保密通信。 1 2r s a 密码体制 19 7 8 年,r o n a l d l r i v e s t ,a d is h a m i r 和l e o n a r dm a d l e m a n 发表了著名的 论文“am e t h o df o ro b t a i n i n gd i g i t a ls i g n a t u r e sa n dp u b l i c - k e yc r y p t o s y s t e m s ”( 获 得数字签名和公开密钥密码系统的一种方法) ,提出了第一个有效的公钥密码体 制,称为r s a 公钥密码体制,它是第一个既能用于数据加密也能用于数字签名 的算法,但r s a 的安全性一真未能得到理论上的证明。 r s a 算法的理论是一种特殊的可逆模指数运算,具体描述如下: ( 1 ) 取两个不同奇素数p 和q ; ( 2 ) 计算模数n 和伊0 ) : 玎= p q ,妒0 ) = 0 1 一1 ) 中国科学技术大学硕士学位论文 ( 3 ) 设e 是加密密钥,d 是解密密钥,定义密钥空间: k = 骱,p ,q ,p ,d i n = p q ,p ,q p r i m e n u m b e ,e d 三1 m o dc p ( n ) ( 4 ) 对每一个k = ( g ,p ,q ,e ,d ) ,定义: 加密变换:e 似) = 脚8m o d n ,朋z 。 解密变换:d 如) = c 4m o d n ,c z 。 其中,n 和e 公开,p 、q 和d 保密。 由n = p q 和缈0 ) = 0 1 x q 一1 ) ,可得 l 乳剐 lp + q = 一缈0 ) + 1 p 、q 是二次方程x 2 + 0 ) 一胛一1 h + 门= 0 的根。 因为n 和e 是公开的,如果能求解出上述方程的根,即得到p 和q ,那么r s a 密码体制所有参数都将得到,从而破解r s a 。 但是r s a 的安全性恰恰是基于分解大数的困难性上的,大数因子分解问题 的安全性是基于大数因子分解的困难性,而大数因子分解问题是数学上的著名难 题,因而可以确保这类算法的安全性。对于1 0 2 4 位的r s a 密码体制以目前人类 最好计算机并行计算,其破解b , - j f 司也是天文数字。不过,目前还没有证明,n 是 分解困难的可保证r s a 一定是安全的。 1 3国内外研究状况 目前1 0 2 4 位r s a 芯片运算速度在每秒2 0 0 0 次以上的大多集中在美国和日 本,国内只有天芯一号s s x l 6 密码算法芯片可以达到每秒2 0 0 0 次,不过它的芯 片内部使用了3 2 位d s p 微处理器,其余的国内产品运算速度均不理想。 表1 2 是国内外几款r s a 加密芯片的具体参数。 2 0 0 6 在中国科学技术大学硕:l = 学位论文 表1 2国内外几款r s a 加密芯片具体参数 芯片 位宽速度频率工艺 备注 天芯一号s s x l 63 2 位d s p 片内微处 1 0 2 4 2 0 0 0 次秒 2 0 0 m 0 2 5 p m 密码算法芯片 理器 s s x 0 4 模幂乘密 该速度为模长和幂 码算法协处理器 1 0 2 4 6 6 次秒 1 0 0 m 0 2 5 9 m 长都为1 0 2 4 位时的 芯片模幂运算速度 t h m 2 5 6 模幂 基于m o n t g o m e r y 算 乘处理器2 5 611 7k b p s9 0 m o 8 9 m 法,线性脉动阵列流 水线结构 n i t r o x s e c u r i t ym i p s 6 4 片内微处理 m a c r op r o c e s s o r s1 0 2 4 4 2 0 0 0 次秒 2 0 0 m 未知器,采用了中国剩余 c n l 3 4 0 定理( c r t ) h i f n8 1 7 0 s e c u r ev o i p1 0 2 4 2 0 0 次秒1 0 4 m 0 1 3 9 m 无 p r o c e s s o r 1 4 选题意义与研究内容 随着基于各种开放式协议基础上的i n t e r n e t 的迅速发展,网络安全受到越来 越广泛的重视,因此,人们对在网络中进行数据传递的安全性的要求也越来越高, 加之破解技术的进步,在数据传递安全上需要一个安全可靠的密码体制。 r s a 密码体制的优点前文已经提到,它是一个非常优秀和安全的公钥密码 体制,但是在硬件实现的问题上,它有着明显的劣势,因为r s a 算法涉及到大 数的模幂运算,运算量相当大,因此在硬件实现时速度、面积和功耗都要比一般 密码体制( 如d e s ) 逊色一些。但由于它的安全性高,人们一直没有放弃对这 种算法高效实现的追求。 由于r s a 算法的安全性很高,i n t e l 和a m d 公司都已经和r s a d a t as e c u r i t y 公司共同开发具有内部加密能力的芯片和软件。 本人独立完成r s a 算法的系统级设计到p c b 电路板的f p g a 实现,以及最 中国科学技术大学硕士学位i = 仑文 后的设计综合。 研究内容具体包括:r s a 算法的研究,1 0 2 4 位大整数的加法、模乘及模幂 算法的研究,r s a 算法的系统级设计、r t l 级设计、p c b 板设计及算法的板级 验证以及最后的v l s i 实现。 研究重点是适合于r s a 硬件实现的模乘算法的选择,r s a 硬件实现时结构 框架的优化,r s a 算法的仿真、验汪及v l s i 实现。 1 5创新之处 这里将设计中的一些创新点归结为以下几点: 1 设计中采用了基于系统级算法的芯片快速成型设计流程,即设计从系统 级到r t l 级,然后到f p g a 实现,最后a s i c 实现。该设计流程在可以 使设计者将自己的想法事先通过s y s t e m c 语言进行建模,尽快得到验证, 然后再向更低级的设计层次迈进。 2 设计中,先后考虑了三种r s a 实现算法,即c r t 算法( 中国剩余定理) 、 s q u a r e - m u l t ( 平方乘) 算法和m o n y g o m e r y 算法。最终,我们选择了 m o n t g o m e r y 算法,通过对m o n t g o m e r y 基本算法和改进算法i 的分析, 提出了自己的想法,即m o n t g o m e r y 改进算法i i ,采用流水线和查找表 结构实现r s a 算法中运算量最大的模乘运算,大大减少了面积,提高了 运算速度。 3 为了提高运算速度,设计中广泛采用了流水结构,d , 至o d n 法器的实现, 大到模乘运算单元和r s a 顶层单元的设计,流水线的瓶颈很低,这样时 钟可以提高很多,而不会影响运算结果,这样也提高运算速度。 4 采用预先用软件计算m o n t g o m e r y 与模有关的常数n u m ,因为n u m = 2 2 m o d n ,n = 1 0 2 4 ,n 为1 0 2 4 位宽的二进制数,如果在片内计算,那 是相当费时、占资源的,采用软件事先计算后,将其和r s a 密钥对一起 作为设计的输入,会大大提高运算速度。 5 f p g a 实现后,在5 0 m h z 时钟频率下,分别测试了1 0 2 4 位、5 1 2 位和 2 0 0 6 :钷 中国科学技术大学硕士学位论文 2 5 6 位的r s a 运算,1 0 2 4 位的计算速度可以达到每秒6 0 多次,由于测 试中改变了r s a 设计的输入输出结构,因此,在输入输出节省了近7 0 个周期,但即便如此,运算速度保守估计能达到每秒6 0 次,而且时钟频 率在l o o m h z 时,1 0 2 4 位r s a 运算速度可以到每秒1 2 0 次以上。 6 运算位宽可调整,最大位宽是1 0 2 4 位,但支持满足r s a 密钥对条件的 低于1 0 2 4 位的所有位宽的r s a 运算,如常见的的7 6 8 位、5 1 2 位、2 5 6 位等等。 7 可以在加密过程中随时更改密钥对,因为设计输入是d a t ai n 、k e y 、1 1 和f l t l m ,即明文密文、密钥、模和跟模和位宽有关的数r l u m 。加密过程 中改变k e y 、n 和n u m 可以增加信息的保密程度,解密时根据数据达到 时间使用相应的解密密钥对,即可解密。 1 6 设计流程 本设计采用的设计流程是基于系统级算法的芯片快速成型实现流程,所谓快 速成型( r a p i dp r o t o t y p i n g ) 臣p 要求从一个好的构想到芯片的诞生,其中的研发过程 刻不容缓,否则相同概念的产品很可能如雨后春笋般接踵而至。利用这种设计流 程可以大大节省设计周期,使设计者的想法很快的得到验证和实现。具体内容为, 由系统级建模、仿真和优化,到行为级、r t l 级的转化和验证,然后进行综合并 在自行设计的f p g a 开发板上验证,最后是a s i c 实现。 流程如图1 2 所示: 6 2 0 0 6 芷中国科学技术大学硕士学位论文 图1 2 基于系统级算法的快速实现流程 r s a 算法v l s i 具体的实现流程为: 图1 3r s a 算法v l s i 实现具体流程 设计前期主要在w i n d o w s 操作系统下工作,后期工作转移到l i n u x 操作系 统中,具体硬件环境和软件环境如表1 3 所示。 2 0 0 6 矩 中国科学技术大学硕士学位沦文 表1 3 设计环境 笔记本电脑1 9 gc p u 、5 1 2 m 内存 硬件环境 x i l i n xv e r t e xp c b 开发板 8 0 万门,4 层板设计 i ? :。、。i i i:o - 。ij 、 “! :饿? ,: + ,屯 :、:”:x :。 。:。 ;:量 。,、;:ij :,。 。| 。 函器i :,| ,如i 一? j j 。“一粤* ,_ :、一4 誓0 。置r - 、4 o i j j - : 。 - + : r w i n d o w sx pp r o f e s s i o n a ls pl l i n u xr e d h a ta s 3u 4 v i s u a lc + + 6 0 版本( w i n d o w s ) m o d e i s i m 6 0 版本( w i n d o w s & l i n u x ) 软件环境 i s e 7 1 版本( w i n d o w s ) s y n p l i f y 8 1 版本( w i n d o w s ) d e b u s s y 6 0 版本( l i n u x ) d e s i g n v i s i o n 2 0 0 4 0 6 s pi 版本( l i n u x ) 8 2 0 0 6 证 中国科学技术大学硕士学位论文 第二章r s a 算法 弟一早 畀法 本章主要介绍r s a 算法的理论,以及r s a 算法中各种运算的算法流程。 2 1r s a 算法一例 在绪论中已对r s a 原理做了简单介绍,在详细介绍r s a 算法理论之前,先 通过一个例子来认识r s a 算法。 取p = 4 7 、q = 7 1 ,则1 1 = p * q = 3 3 3 7 ,( p 1 ) 卡( q 1 ) = 3 2 2 0 ,随机选取加密密 钥e ,e 与( p 1 ) 木( q - 1 ) 互质,若取e = 7 9 ,则d = 7 9 _ r o o d3 2 2 0 = 1 0 1 9 。 设要加密的信息是m = 6 8 8 2 3 2 6 8 7 9 6 6 6 6 8 3 ,首先,根据n 的大小将m 分块, 这里把m 分成六块,即: m 1 = 6 8 8m 2 = 2 3 2m 3 = 6 8 7m 4 = 9 6 6m 5 = 6 6 8 m 6 = 0 0 3 接着,分别对各个块进行加密,第一块加密为: 6 8 8 丹r o o d3 3 3 7 = 1 5 7 0 = c 1 类似的,对其余各块进行加密,得到如下密文: c = 1 5 7 02 7 5 62 0 9 12 2 7 62 4 2 31 5 8 解密时需要用到解密密钥l o l 9 进行同样的指数运算,即: 1 5 7 0 0 1 9m o d3 3 3 7 = 6 8 8 = m 1 其余的密文用同样的办法恢复出来。 2 2r s a 算法实现过程 图2 1 是r s a 算法实现过程。 9 2 0 0 6 链中国科学技术大学硕士学位论文 图2 1r s a 算法实现过程 2 2 1判别p ,q 为素数 这里介绍一下比较广泛使用的m i l l e r r a b i n 素数检测算法m i l l e r r a b i n ( n , t ) ,其中n 是输入的奇数,t 是安全参数,因为判素性检测可能检测出来的“素 数”是伪素数,这种发生错误的概率小于( 丢) ,因此,t 大一些保障就高一些, 图2 2 是m i l l e r - r a b i n 算法流程图。 1 0 2 0 0 6 壬e中国科学技术大学硕士学位论文 随机产生奇数n 记肝一1 = 2 5 ,r 为奇数 厂、 取随机整数a 1 a n l 、, 厂 、 计算j ,= a m o d 门 图2 2 判素性算法流程图 n 2 0 0 6 :宅中国科学技术大学硕二e 学位沦文 2 2 2 判别加密密钥e 与妒( 门) 互素 判别加密密钥e 与妒( ”) 互素是采用e u c l i d e a n 定理来实现的,欧几里得定理 可用来求两个非负整数的最大公约数,如果得到的最大公约数是1 ,那么加密密 钥e 与妒( 聆) 互素,图2 3 是算法的流程图: 图2 3判别加密密钥e 与缈( 门) 互素算法流程图 2 2 3 解密密钥d 的选择 解密密钥d 的定义是d = p 一= e m o d o ( n ) ,可以用扩展e u c l i d e a n 定理求解, 具体描述如下: 输入:两个非负箍数a 和b ,a b 输出:m = g c d ( a b ) 和满足等式a x + b y = m 的整数x 和y ( 1 ) 如果b = 0 ,则置m = a ,x = 1 ,y = 0 ,并返回( m ,x ,y ) ( 2 ) 置x 2 = 1 ,x 1 = 0 ,y 2 = 0 ,y l = l 中国科学技术大学硕士学位论文 当b 0 时,执行下列步骤: q = a b ,r 2 a q b ,x2x 2 一q x l ,y2y 2 一q y l , a = b ,b 。r ,x 22x i ,y 2 = y l ,x i2x ,y l 2 y 置m = a ,x = x 2 ,y = y z ,并返回( m ,x ,y ) 对r s a 密码体制而言,a = 妒( 门) ,b = e ,m = g c d ( o ( n ) ,e ) = l ,x 和y 中y 即为所求的解密密钥d 。 2 2 4 模乘与模幂算法 由于r s a 算法的硬件设计主要着手于模乘、模幂算法的实现,而上述的 些算法是需要在软件上实现的,在硬件实现日寸只需直接利用软件得到的上述算法 的结果即司。 此外,r s a 算法硬件实现的核心也正是模乘、模幂算法的设计和优化,这 些算法主要有s q u a r e m u l t 算法、m o n t g o m e r y 算法和c r t ( 中国剩余定理) ,由 于在设计过程中只涉及到前面两种算法,这里主要介绍一下用c r t ( 中国剩余 定理) 实现模幂算法的思想。至于前面两种算法将在r s a 硬件实现那部分详细 介绍。 中国剩余定理,也叫孙子定理,其定义如下: 设刀,z , 1 ,七,g c d ( n ,门,) = 1 ,口,z ,l i k ,则r 个同余方程组: x 三口 x 三日 m o d 门l m o d ” r o o d 以 模= 胛。门: 。有唯解,该解由下式给出: 七 x = 口,n ,y ir o o dn i = l 其中,n j = n n ,y 。= n i m o dn ,1 isk 。 中国科学技术大学硕士学位论文 设取得两个大素数p 和q ,n = p q ,明文m n ,加密密钥为e ,密文为c , 计算c = m e m o d n ,取: 骺e p = e m 删o d ( p - 1 ; r p = q p 叫- i 删r o o d : 第一步:计算m ,和m 。 篇m p = m 删r o o d ; 第二步:计算c ,和c , 仁c p = m 知; m 。o d d ; 第三步:计算s ,和s 。 雠s p = ( c p 以r p 舢) m o l d c = ,+ s 。) r o o dn c r t 算法的优点是将模幂运算的幂降低了,这样在速度j 二能得到很大提高。 不过,它的缺点是比较明显的,设计过程中需要把p 和q 这两个关键数据放 入设计t 模块中,因为p 和q 参与了c r t 算法,这样一来,j ! := 片自身又要对p 和 q 的保密性多加考虑才彳亍,因为一旦p 和q 被破泽了出来,r s a 的切信启、全部 2 0 0 6 年 中国科学技术大学硕士学位论文 第三章r s a 算法的系统级设计 本章介绍了基于s y s t e m c 的系统级设计流程,并用s y s t e m c 描述语言对r s a 算法进行系统级设计,并在m o d e l s i m 上进行仿真。 31 基于s y s t e m c 的设计方法学 随着高性能、低功耗、多功能i c 芯片需求的增加,现有的设计水平与工艺 发展的不平衡,传统i c 设计流程成为满足市场需求的瓶颈。为了避免这个问题, 仔细而又精确地进行系统级设计显得尤为重要。在我们从事系统级设计的过程 中,经常遇到一些很好的设计构想和算法,在计算机上可以较为顺利的实现,在 将其转化为芯片时却遇到了许许多多的问题,这往往使得一些设计被迫进行修 改,从而开发周期较长,大大影响了芯片的快速成型。所谓快速成型( r a p i d p r o t o t y p i n g ) 即要求从一个好的构想到芯片的诞生,其中的研发过程刻不容缓, 否则相同概念的产品很可能如雨后春笋般接踵而至。 目前,在复杂数字电路自顶而下设计领域中,v e r i l o g 语言是一种广泛使用 的硬件设计描述语言,在r t l 级层次描述有优势,但是该语言不能很好建立系 统级结构的模型,在涉及到算法的领域,它往往会束手无策。 c c + + 语言对于一些算法的表述较为方便,它与v e r i l o g 语言在结构和关键 词上有相似之处,对一些涉及到算法和体系且规模较大的i p c o r e 设计,我们可 以先用c c + + 语言进行建模,再将其转换成v e r i l o g 语言。 s y s t e m c 语言实质上是在c + + 基础上添加的硬件扩展库和仿真核,可以进 行设计规范、系统体系结构分析和验证平台,还可以利用s y s t e m c 和c + + 开发 工具建立系统级模型,并且进行仿真、验证和优化以及各种算法的探究。 利用s y s t e m c 进行硬件设计的理想流程如图3 1 所示。 2 0 0 6 笠中国科学技术大学硕士学位论文 图3 1 s y s t e m c 进行硬件设计的理想流程 目前还没有一个大家一致认可的主流的厂商支持将s y s t e m c 直接综合到网 表,虽然也有一些e d a 工具可以实现转换,但转换并不尽如人意,最后还是免 不了手工修改。用s y s t e m c 写的硬件要成为产品一般都需要向更低的描述层优 化,我们可先用s y s t e m c 建立系统级模型或算法,然后再进行仿真、验证和优 化,再将其转化成更低的v e r i l o g 描述层次,得到网表并硬件实现,因此,实际 的设计流程如图3 2 所示。 ,劈携 图3 2 s y s t e m c 进行硬件设计实际的设计流程 1 6 中国科学技术大学硕士学位论文 3 2 r s a 算法的s y s t e m c 实现 在s y s t e m c 设计阶段我们着眼点是r s a 算法的实现,对r s a 算法的硬件实 现的结构做初步的划分,为后续设计打好基础。本节主要以模乘为例加以介绍。 r s a 算法的s y s t e m c 实现,使用的工具的m i c r o s o f t 公司的v i s u a lc + + 6 0 。 在w w w s y s t e m c o r g 上下载s y s t e m c 最新版本,即s y s t e m c 一2 1 v 1 ,然后在v i s u a l c + + 6 0 编译,得到s y s t e m c 1 i b 库文件。这样,在以后的设计中,只要在:亡程设 茕中指定好s y s t e m c 1 1 头文4 - t :和s y s t e m c 1 i b 库文件的位置即可。 设计t 过程中,系统级设计与最终的r t l 级设计在结构上有些区别,这是主 要还是因为我在s y s t e m c 设计阶段更多是考虑算法的实现,在r t l 级发计阶段, 借鉴系统级设计的结果,采用更好的优化算法( 如m o n t g o m e r y 算法) 和体系结 构( 如流水线、c s a 等) 。 r s a 算法中,最核心的运算是模幂运算,即: e 膏( 聊) = 研。r o o d n 和d k ( m ) = c 。m o d n 很明显,加密和解密所用到的函数原型是同一个函数,即x ym o d z ,进一步 分析可知,x ym o d z 的实现又在于a b m o d m 模乘的实现,因为 工,m 。d z = ( x ;m 。d z ( x jm 。d z m 。d z 即,可以把模幂运算转化成若干模乘运算,降低算法的复杂度。 在本设计的s y s t e m c 实现过程中,采用的是用s q u a r e m u l t 算法来实现r s a 算法的,有关s q u a r e m u l t 算法的具体描述,将在r s a 算法的r t l 实现中给出。 3 2 1 模乘运算的s y s t e m c 实现 模乘运算模块的接口信号 2 0 0 6 笼 中国科学技术大学硕士学位论文 表3 1 模乘运算模块接口信号 信号 类型位宽 描述 c l k i n p u t lb i t时钟信号 r e s e t m p u t lb i t 复位信号 i d i n p u t lb i t 数据l o a d 信号 a m p u t 10 2 4b i t乘数 b i n p u t l0 2 4b i t 被乘数 n i n p u t 1 0 2 4b i t 模数 o u t o u t p u t 1 0 2 4b i t 模乘结果 d o n e o u t p u t lb i t运算完毕信号 2 接口信号的时序关系 r e s e t 信号置1 时不动作;r e s e t 置0 ,若l d 为l ,即l o a d 信号有效,加载数 据,在下一个c l k 上升沿到来时进行模乘运算,此时d o n e 信号为0 ;当完成运算 时,在c l k 上升沿将结果送出,并置d o n e 为】。 3 模乘运算的部分s y s t e m c 代码 2 0 0 6 :白三 中国科学技术大学硕士学位论文 4 模乘运算模块的编译和仿真结果 编译很简单,在v i s u a lc + + 6 0 里操作跟一般的c 程序一样,直接b u i l d 即 可,不过要在程序的t e s t b e n c h 中加入t r a c e 相关语句,才能生成波形文件。 由于s y s t e m c 代码自身只能生成v c d 格式的波形文件,所以要看到波形需 采用其他工具软件。w a v e 是个专门查看v c d 格式波形的工具,但由于对波形表 现方面欠佳,设计中使用的是m e n t o r 公司的m o d e l s i m 工具来查看波形。因为 m o d e l s i m 只能查看w l f 格式的波形文件,所以,实现要对v c d 格式的文件进行 转化。 转化很方便,打开m o d e l s i m ,在其控制台处执行以下命令: v c d 2 w l f p a t h t o s o u r c e v c d p a t h t o t a r g e t w l f 然后,用m o d e l s i m 打开w l f 文件,即可看到波形了。 为观察方便,取a ,b ,h 为较小的1 0 2 4 位数,取a = 2 3 51 ,b = 3 7 6 8 ,n = 4 2 5 7 , 中国科学技术大学硕士学位 仑文 则理论运算结果应为2 3 5 l 3 7 6 8m o d4 15 7 = 4 0 0 8 。 模乘运算模块的仿真波形如图3 3 所示。 图3 3系统级模乘运算模块仿真波形 3 2 2 r s a 运算的s y s t e m c 实现 1 r s a 运算模块的接口信号 r s a 加解密模块是可以进行加密和解密操作的,因此,当输入端是明文和 加密密钥时,输出的就是密文;当输入端是密文和解密密钥时,输出就是明文。 表3 2r s a 运算模块接口信号 信号类型位宽 描述 c l k i n p u t 1b i t 时钟信号 r e s e t i n p u t lb i t 复位信1 勺1 7 7 1 + l d i n p u t lb i t数据l o a d 信号 d a t ai n m p u t 10 2 4b i t 明文或密文 k e yi n p u t 10 2 4b i t 加密密钥或解密密钥 n i n p u t 10 2 4b i t 模数 d a t ao u t o u t p u t 10 2 4b i t 密文或明文 d o n e o u t p u t 1b i t运算完毕信号 2 接口信号的时序关系 r e s e t 信号置l 时不动作:r e s e t 置0 ,若l d 为1 ,即l o a d 信号有效,加载数 据,在下一个c l k 上升沿到来时进行模乘运算,此时d o n e 信号为0 :当完成运算 2 0 2 0 0 6 年中国科学技术大学硕士学位沦文 时,在c l k 上升沿将结果送出,并置d o n e 为1 。 3 r s a 运算的部分s y s t e m c 代码 2 l 中国科学技术大学硕士学位沦文 4 r s a 运算模块的编译和仿真结果 r s a 运算模块的编译的操作同模乘模块,操作很简单。由于r s a 的软件实 现比较成熟,而且,前面已经提到,软件实现r s a 算法( 大多用c 代码或c + + 实现) 时,是将随机大素数的生成以及判素性等一并实现的,这样一来,在发计 过程中就可以利用软件实现过程中产生的密钥对作为测试程序的密钥对,并且根 据软件实现的结果来判断s y s t e m c 仿真结果是否正确。 我采用了一个网上流传的比较优秀的用c + + 编写的r s a 计算程序作为密钥 对生成工具和结果的判定依据,并用m a p l e 软件中的相关函数对结果进行了验 征。 表3 31 0 2 4 位r s a 加密解密密钥列 1 0 9 c
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年黔南民族医学高等专科学校高职单招笔试物理历年参考题库含答案解析
- 2026年鹤壁职业技术学院高职单招笔试数学历年参考题库含答案解析
- 砖瓦生产工岗前绩效目标考核试卷含答案
- 2026年陕西能源职业技术学院高职单招笔试化学历年参考题库含答案解析
- 2026年长沙职业技术学院高职单招笔试化学历年参考题库含答案解析
- 2026年铁岭卫生职业学院高职单招笔试语文历年参考题库含答案解析
- 全麻术后舒适化护理
- 肾囊肿护理查房模板
- 小儿脑性瘫痪护理业务查房
- 病情观察及危重病人抢救和护理
- 高中物理选择性必修2-基础知识自测小纸条(含答案)
- 气管切开患者气管造口周围皮肤护理
- 2025年中国铁路南宁局校招真题及答案
- 子宫肌瘤的课件
- 2026年美丽中国全国国家版图知识竞赛测试题库
- 2026海南农垦投资控股集团秋招试题及答案
- 智慧育种课件
- 国企招聘面试流程与技巧分享
- 高考英语词汇 40篇短文搞定高考英语3500单词
- 老年急性胆道感染诊治专家共识(2025版)解读 3
- 《如何做好调查研究》课件
评论
0/150
提交评论