（微电子学与固体电子学专业论文）非对称算法空间可重组逻辑研究与soc设计.pdf

摘要 目前主要研究和应用的公开密钥( p k i ) 系统的密码算法有两种：r s a 算法 和e c c 算法，前者基于大整数因子分解难题，后者基于椭圆曲线上离散对数计算 难题绝大部分公开密钥系统中进行加解密和数字签名使用的是r s a 算法，随着 r s a 所要求的密钥比特长度的不断增长，效率成为个最大的瓶颈，尤其是对于越 来越要求进行大量的安全交易的应用场合如电子商务等场合更是如此眦应用 于公钥密码算法与r s a 相比的主要优点是：更快的加解密速度、更大的带宽节省、 更高的存储效率，1 6 0 位e c c 密码体制的加密强度已相当于1 0 2 4 位r s a 密码体制 加密强度而可以预见的是r s a 和e c c 必将在相当长一段时间内共存，因此研究一 种同时支持实现两者的加密算法的芯片的协处理器，这样应用于加密系统中，可 以实现两种算法互相配合，交替使用，无疑对提高信息安全有着很大的意义和应 用前景 ： t， ” 可重组理论思想是通过改变可重组电路内部可控节点的值从而的改变可重 组电路结构实现不同的电路功能的可重组运算，并且由可控节点设置指令可见的 指令流，组成算法配置文件，通过软硬件的协同工作，用有限的电路规模实现尽可 能的多种算法本文运用可重组理论，通过r s a 、e c c 算法在以m o n t m o n e y 模乘为核 心操作粒度上的可重组分析，依据r s a 和e c c 算法基本操作的连集、并集和共集等 关系，设置可控节点，设计了一种基于m o n t m o n e y 算法的双域密码可重组电路( 协 处理器) ，该重组电路核心部分双域模乘器电路由加法器构成，并且采用用8 级流 水实现模乘，用一种电路实现了r s a 和e c c 算法本文的设计是利用可重组理论进 行重组电路设计的一次初步的实践，对硬件的实现和软件指令的配置等做了描 述 本文中设计采用v e r i l o g 语言输入，并且在m o d e l s i m 环境下通过r t l 逻辑功能 j 仿真 ， 。 关键词：r s a ，e c c , 可重组逻辑，m o n t m o n e y 模乘，双域乘法器，协处理器 i n a b s t r a c t a tp r e s e n tt h em a i nr e s e a r c ha n dt h ea p p h c a f i o np u b h ck e y 口m r ) t h es y s t e m c r y p t o - a l g o r i t h mh a st w ok i n d s ：t h er s aa l g o r i t h ma n dt h ee c ca l g o r i t h m ，f o r m e r b a s e do nt h eg r e a td i v i s o ro fi n t c g e r sd e c o m p o s i t i o nd i f f i c u l tp r o b l e m ，l a t t e ri s s e p a r a t e dt h el o g a r i t h m i cc o m p u t a t i o nd i f f i c u l tp r o b l e m b a s e do nt h cc r y p t i cg u r v ei n i nt h em a j o rp a r tp u b l i ck e ys y s t e mc a i t i e so na d d st h ed e c i p h e ra n dt h ed i g i t a l s i g n a t u r eu s ei st h er s aa l g o r i t h m - t h ek e yl e n g t hu n c e a s i n gg r o w t hr e q u e s t sw h i c h a l o n gw i t hr s a , t h ee f f i c i e n c yb e c o m e sab i g g e s tb o t t l e n e c k , r e g a r d i n gm o r ea n d 。 m o f cr e q u e s t st oc a r r yo nm a s s i v es e c u r i t yt r a n s a c t i o ns i t u a t i o n sa n ds oo na p p l i c a t i o n s i t u a t i o nl i k ee l e c t r o n i cc , o m m e r c ei si np a r t i c u l a r e c ca p p l i e st h em a i nm e r i t w h i c hc o m p a r e s 妇t h ep u b h c k e ye r y p t o - a l g o r i t h ma n dr s a i s ：髓eq u i c k e rc a n a d i a n d e c i p h e rs p e e d , ag r e a t e rb a n dw i d t hs a v e s ，t h eh i g h e rm e m o r ye f f i c i e n c y , 1 6 0b i t s e c c p a s s w o r ds y s t e me n c r y p t i o ni n t e n s i t yh a sb e e ne q u a lt o1 0 2 4b i t sr s a p a s s w o r d s y s t e me n c r y p t i o ni n t e n s i t y b u tm a yf o r e s e ei sr s a a n de o cw i l lc e r t a i n l yt oc o e x i s t j nq u i t el o n gp e r i o do ft i m e , t h e r e f o r es t u d i e so n e 】( i n ds i m u l t a n e o u s l yt os u p p o r t r e a l i z e sb o t he n c r y p t i o na l g o r i t h mc h i pa s s o c i a t i o np r o c e s s o r , l i k et h i sa p p l i e si nt h e c r y p t o g r a p l f i cs y s t e m ，m a yr e a l i z et w oa l g o r i t h m sf oc o o r d i n a t em u t u a l l y , t l s e sj nt u r n ， w i t h o u td o u b tt oe n h a n c e st h ei n f o r m a t i o ns e c u r i t yr yh a v et h ev e r yb i gs i g n i f i c a n c e a n dt h ea p p l i c a t i o np r o s p e c t 耽er e c o n f i g u r a b l et h e o r yt h o u g h ti sm a yr e o r g a n i z et h ee l e c t r i cc i r c u i ti n t e r i o r c o n t r o l l a b l en o d et h r o u g ht h ec h a n g et h u sv a l u et h ec h a n g el ob ep o s s i b l et o r e o r g a n i z et h ee l e c t r i cc i r c u i ts t r u c t u r er e a l i z a t i o nd i f f e r e n te l e c t r i cc i r c u i tf u n c t i o nt o b ep o s s i b l et or e o r g a n i z et h eo p e r a t i o n , a n db yt h ec o n t r o l l a b l cn o d ee s t a b l i s h m e n t i n s t r u c t i o no b v i o u si n s t r u c t i o nc l a s s ，i sc o m p o s e dt h ea l g o r i t h mc o n f i g u r a t i o nf i l e s ， t h r o u g ht h es o f t w a r ea n dh a r d w a r ej o i n to p e r a t i o n , r e a l i z e sa sf a ra sp o s s i b l em a n y k i n d so fa l g o r i t h m sw i t ht h el i m i t e de l e c t r i cc i r c u i ts c a l e t h i sa r t i c l eu t i l i z e sm a y r e o r g a n i z et h et h e o r y , t h r o u g hr s a , t h ee c ca l g o r i t h mi nw h i l em a yr e o r g a n i z et h e ； a n a l y s i st a k et h em o u t m o n e ym o l da st h ec o r eo p e r a t i o ng r a n u l a r i t y 血r e s t so nr s a a n dt h ee c ca l g o r i t h me l e m e n t a r yo p e r a t i o ne oc o m p a n yc o l l e c t i o n , t h es u m a g g r e g a t ea n da l t o g e t h e rr e l a t i o n sa n ds oo nc o l l e c t i o n , t h ee s t a b l i s h m e n tc o n t r o l l a b l e n o d e ，d c s i g a c do n ek i n dt ob ep o s s i b l et or e o r g a n i z et h ee l e c t r i cc i r c u i tb a s e do nt h e m o n t m o n e ya l g o r i t h md o u b l et e r r i t o r yp a s s w o r d ( t oc o o p e r a t ep r o c e s s o r ) ，t h i s r e o r g a n i z a t i o ne l e c t r i cc i r c u i to n l yt h e nu s e d8l e v e lo fr u n n i n gw a t e rf o r m sb yt h e a c c u m u l a t o rt ob ec o m p o s e d ，h a sr e a l i z e dr s aa n dt h ee c c a l g o r i t h mw i t ho n ek i n d o fe l e c t r i cc i r c u i t 。t h i sp a p e rd e s i g ni st h er e c o n f i g u r a b l et h e o r yt o c a r r yo nt h e r e o r g a n i z a t i o nc i r c u i td e s i g nap r e l i m i n a r yp r a c t i c e ，a n ds oo nh a sm a d et h ec o n c r e t e d e s c r i p t i o no n t h eh a r d w a r ec o n c r e t er e a l i z a t i o na n dt h es o f t w a r e i n s t r u c t i o n d i s p o s i t i o n i nt h i sp a p e rd e s i g n si su s e dt h ev e r i l o gl a n g u a g ei n p u t ，a n dp a s s e dt h er t l l e v e rl o g i c a lf u n c t i o ns i m u l a t i o nu n d e rt h em o d e l s i me n v i r o n m e n t k e yw o r d s ：t h er e c o n f i g u r a b l el o g i ct e c h n o l o g y r s a e c c , m o n t g o m e r ym u i t i p l c a t i o n a l g o r i t h m , d u a l - f i e l dm u l t i p l i e r ，c o p r o s s o b v 第一章前言 1 1 研究背景 ， 公开密钥系统亦称非对称公钥密码系统，是现代密码学中最重要的研究内容 之一密码学通俗的理解就是一方面保护消息传递的机密性，更为重要的另一方 面就是对信息发送方的身份的认证以及信息的完整性的检验公开密钥系统很好 的解决了这两方面的问题，并正在产生更多的新的思想和方案公开密钥的观点 是由d i f f i e 和h e l i m a n 于1 9 7 5 年在其论文密码学的新的发展方向一文中首次 提出的，并进而引发了密码学一场深刻的变革密码算法主要分为基于算法保密 和基于密钥保密两种，前者的可靠性依取决于码算法的保密程度。一旦算法泄漏， 安全性也随之得不到有效保障，而且算法的种类也有限，因而只在要求不高的小 范围内应用而基于密钥的密码算法能完全的避免这一点，算法为公开的，只要密 钥不被泄漏，安全性也不会受到威胁，并且密钥的发放，管理策略十分完善和成熟 本文中以后所涉及的密码算法均指基于密钥的密码算法，主要分为对称算法 ( s y m m e t r i ca l g o r i t h m ) 和非对称算法( 也叫公开密钥算法，p u b l i c k e y a l g o r i t h m ) 本文中只讨论非对称密钥系统即公开密钥系统公开密钥系统中，加 密密钥不同于解密密钥，加密密钥在特定范围内是公开的，通信组内任一方都可 以使用解密密钥只有解密方才知道，分鄹称之为公开密钥( 公钥) 和秘密密钥( 私 钥) ，在至今为止的所有公开密钥系统中最著名的是由i tr i v e s t ，s h a m i r ， a d e l m a n 于1 9 7 7 年提出的r s a 公开密钥系统r s a 方法的优点主要在于原理简单， 使用方便它是少数几个能完成统的加密功能，同时具有如数字签名功能的加密 算法之一r s a 基于数论大数难分解原理：将两个大的素数合成一个大数容易，而相 反的过程则非常困难，因而决定t r s a 的安全性取决于作为公钥的大数n 的位数长 度但是随着计算机科学技术以及超大规模集成电路的发展，人们得以制造出计 算能力越来越强的计算机特别是分布式计算机网络出现提供前所未有的计算能 力而使分解大整数的能力日益增强在这种情况下，为了保证r s a 使用的安全性， 其密钥的位数需要被迫一直增加目前已经证明5 1 2 位的r s a 已经不安全，一般认 为r s a 至少需要1 0 2 4 位以上的字长才具有足够的安全保障，这样必然带来实现的 难度和硬件的开销并最终导致速度的下降，这无疑是r s a 面临的一个严峻的挑战 和考验这时人们把目光投向了基于离散对数问题的椭圆密码体铝r j e c c ( e l l i p t i c c u r v ec r y p t o g r a p h y ) e c c 体制上的离散对数的计算要比有限域上的离散对数的 计算更困难，同r s a 相比能设计出密钥更短的公钥密码，具有更高的安全性和更好 的算法实现性 目前实际应用的主流算法还是以使用r s a 算法为主，但是可以预见r s a g , 将被 e c c 替代考虑至u r s a 和e c c 的算法特点，两者的核心运算均可转化为模乘运算，因 而可以考虑设许一种处理器，可以同时可以支持两种算法，两种算法更替使用，显 然在安全强度上和安全策略上有着无与伦比的优势，而且这也是未来密码芯片设 计的的趋势本文运用可重组理论设计一种同时支持两种或更多种算法的密码芯 片的重组电路。( 协处理器) 所谓可重组芯片就是指用户可以通过编程改变芯片 内部的电路运算结构和顺序，使同一硬件能够实现不同的算法可重组密码芯片 算法编写成算法配置文件注入芯片，具有设计安全性，兼容性，可扩展性，灵活性 等优点 1 2 本文工作内容及论文结构 可重组密码芯片设计的思想：密码算法有一个显著的特点，即大部分的密码 算法都有相同或相似的操作和运算，如模加，模乘，模拟等，即在密码芯片逻辑电 路中存在着被不同算法重用的单元，那么这些基本操作成分所对应的硬件资源就 可以被多种不同的密码算法所共用，称之为重组单元通过提取重组单元并且在 重组单元之间和数据之间设置某些指令界面可见的可控节点，这样就可以通过相 应的指令集合即算法配置文件通过可控节点对重组单元和数据流等进行控制从 而以较少的电路规模构造一套逻辑电路利用软硬件协同工作来实现不同的密码 算法这也是本课题的设计依据 本文运用可重组逻辑技术进行实现多种非对称算法重组电路( 协处理器) 设 计，通过对非对称算法r s a ，e c c 全集成分的层次化分析，提炼并确定算法成分的连 集、并集和共集并优化，确定重组单元进而使资源最小化进而按照可重组理论进 行芯片的软硬件的划分并建立起体系结构，在资源优化前提下实践以软件算法配 置文件和硬件电路协同工作的方式下支持持两种以上非对称加密算法的设计 2 本文的章节及主要内容安排如下 第一章前言介绍了研究背景和研究内容以及论文工作安排 第二章介绍了可重组体系结构密码芯片设计思想以及方法 第三章介绍了非对称加密算法r s a 和e c c 算法和分析以及实现方法以 m o n t g o m e r y 模乘算法对r s a 和e c c 算法可重组分析，并给出了具体可重组方式的算 法实现，确定了硬件设计时可控节点选取的准则和对应算法的流程控错l - 第四章按照可重组体系结构，并对电路软硬件进行了划分，并分别做了设计 描述，着重描述了重组电路( 密码协处理器) 的设计和软件算法指令设计方案 第五章对本文所开展的工作进行了总结，对以后的进一步改进提出了一进。 一步的展望 3 第二章可重组体系结构密码芯片设计思想以及方法 2 1 可重组理论 可重组理论就是指一定的硬件电路通过不同的可控节点的控制或者数据的 分配，对应于不同的操作顺序或者对应于不同的数据选通关系等而实现不同的电 路功能，以满足不同的应用需求可重组理论可定义如下：在一定的体系结构下， 对应于一定的算法( 操作) 空间，如果该体系结构的逻辑电路存在可被重用的部件， 并且如果能在可重用逻辑部件之中可以设置指令界面可见的可控节点，通过不同 的指令对控制节点进行控制，改变重用部件内部运算顺序或者相互之间的互相连 接关系以及数据的分配等从而在同一电路实现不同的电路逻辑功能，可重组的粒 度即重用部件的租细等级的可小至基本门级电路，大到i p 级电路模块 + ， 2 2 可重组理论在芯片体系结构上的应用、 ， 所谓可重组理论体系结构是指硬件逻辑电路能够根据不同的应用需求，重新 组织，构成不同的电路结构，实现不同的功能，匹配不同的应用需求 可重组体系结构的定义：如果在某一体系结构的逻辑电路中存在某些可重用 的部件，势在可重用的部件之中设置了某些指令界面可见的控制结点，通过指令 或标识对这些可控结点进行控制，可以改变重用部件的内部结构或相互之闻的连 接关系，从而实现不同的电路结构，完成不同的逻辑功能，那么该体系结构就称为 可重组体系结构可被重用的部件是可重组体系结构的基础因此，可重用部件是 构成可重组体系结构的基本元素，称其为重组元素重组元素的粒度是不同的，可 以是基本门，也可以是具有一定功能的部件，也可能是几十功能部件构成的子系 统某些细粒度的重组元素可能构成中粒度的重组元素，某些中粒度的重组元素 也可能构成一个粗粒度的重组元素，粒度不同的重组元素也能相互组合，构成不 同的电路结构，实现不同的逻辑关系 可编程体系结构d s p 和专用集成电路a s i c 代表了两种极端的计算手段可编 程体系结构d s p 具有最大的灵活性和低性能，专用集成电路a s i c 具有最高的性能 和最差的灵活性而现在有许多应用需求既要求较高的性能，又需要定的灵活 4 性可重组是在软件的控制下，利用可重用资源，重构或重组成另一个计算平台， 以适应不同的应用需求，具有可重组特征的计算系统称为可重组计算系统可重 组体系结构提供了一种介于d s p 和a s i c 之间的计算手段，目前是学术界和工业界 的研究热点，已经有许多研究成果和工业产品面世，譬如f p g a 就是其中的一种代 表体系 一 可重组体系结构的主要技术特征在于： ( i ) 可快速设计实现多种不同算法的配置文件编码，采用可重组体系结构的 芯片中可代替多块针对特定算法设计的专用芯片；， ；( 2 ) 可以实时加载算法的配置文件，适应多种不同算法从而大大降低了专 用算法芯片的开发周期和生产成本，同时增加了产品裁不同应用领域中实时操作 的需求；。，；* 一”一 一”“。 ( 3 ) 配置文件不需要专用设备装载，不需要中断执行即可改变配置文件仅 利用计算机和网络即可快速变换适应不同地区使用的不同算法标准、要求，以及 快速变换以致销毁密码算法及密钥 ， * 如图2 1 所示为一典型的可重组理论的体系结构图，可重组体系结构包括通 用处理器，即，负责对整个系统的调度以及处理通用的计算和控制任务：可重组处 理单元，专门用于处理专用领域的计算任务；存储器，主要使数据和结果的储存： 输入输出接口，负责和外界交换数据或指令和可重组处理器根据具体应用情况 可以在同一芯片内或不同芯片内。 存储器主处理器输入输出 ， 8g 8 0 可重组单元 本地存储器 图2 1 典型的可重组理体系结构 5 2 3 可重组逻辑的设计思想 可重组密码芯片设计的思想：密码算法有一个显著的特点，即大部分的密码 算法都有相同或相似的操作和运算，如模加，模乘，模拟等，即在密码芯片逻辑电 路中存在着被不同算法重用的单元，这样通过提取重组单元并且在重组单元之间 和数据之间设置某些指令界面可见的可控节点，这样就可以通过相应的指令集合 即算法配置文件通过可控节点对重组单元和数据流等进行控制而实现不同的密 码算法 下面以两个例子简要的介绍一下可重组逻辑的基本思想，程序代码为 v e r i l o g - h d l 编写。本文中代码均为v e r i l o g - h d l 代码编写 实现不同逻辑功能的可重组电路： m o d u l er l o g i c ( a ，b ，c ，d ，c t r l i ，c r r l 2 ，f ) i n p u ta ，b ，c ，d ，c t r l l ，c t r l 2 ：。 o u t p u tf ： 4 a n d # tm l ( e ，a ，b ，c ) ： n o t # tm 2 ( g ，d ) ： ， a n d # tm 3 ( h ，c t r l l ，e ) ；c t r l l 为所示的可控节点 a n d # tm 4 ( l , g ，c t r l 2 ) ；c t r l 2 为所示的可控节点 o r # tm 5 ( f ，h ，l ) ： e n d m o d u l e 在上面代码中，m l ，l i l 3 ，融为与非门，m 2 为非门，m 5 为或门，其中a ，b 。c ，d ，为输 入变量，f 为输出变量，这里我们设置两个可控节点c t r l l ，c t r l 2 ，这样通过对 c t r l i 和c t r l 2 赋以不同的值，就对应的可以给出不同的f 的输出值，这样就在同一 表2 1 重组电路逻辑 c t r l lc t r l 2 f ( a ，b ，c ，d ) o 0 f - - o o l f - - d lo f = b c 。 ， l1f = a b c + d 逻辑电路上实现了不同的逻辑功能电路功能关系如上表2 - 1 所示： 6 通过改变数据选择关系的可重组电路： m o d u l er l o g i c ( a ，b ，m ，f ) i n p u ta ，b ，l i ； o u tf ：， a w a y s ( a ) c = a ： a w a y s ( b ) d = - b ； 7 a w a y s ( ao rbo rm ) m 为可控节点 c g s e ( m ) l ib o ：f = a ： 1 b l ：f - b ： d e f a u l t ：f = a ： e n d c a s e e n d m o d u l e 上两例中，可重组的思想所在就是在一定的逻辑电路的前提下，通过改变可 控节点值丽实现了不同的逻辑功能其可控节点的选取和重组方式有两种；一是 改变各功能模块的连接关系实现可重组；二是根据需要改变数据选通关系而实现 可重组由此可见，可重组电路的组成包含两个部分：可被重用的功能部件和相互 之间可以互联改变数据选通关系的数据传输路径等可重用部件，这是可重组的前 提和基础我们称这些可以重用的逻辑功能部件为可重组元素而且对应于不同 的应用需求。可重组元素要求实现的逻辑功能不尽相同，因为被不同的具体应用 环境所限定，因此，重组元素的内部关系必须是可以改变和扩展的，以便能实现不 同的逻辑功能而在密码学中，很多密码算法都使用了移位单元，模乘单元，模逆 单元，而这些操作重用率非常之高，不同的只是在不同的算法中只有操作数的不 同，或者要求操作的功能不同，如移位操作功能分循环左移，循环右移，逻辑左移， 逻辑右移，而且移位为数也不尽相同，这样移位单元如果要实现重组的话，必须能 够能有可控节点来改变电路内部的电路结构或者数据选通关系等又如模乘等， 在密码算法中可重用率也极高，但是在自然域，有限域中模乘的操作又有所不同， 同样，可以通过可控节点的选取来实现自然域和有限域中模乘的可重组设计，这 7 样显然减小了电路的规模，在可重组的前提下考虑流水，并行等处理，可以在较小 面积的前提下实现极高的主频 由此可见，通过在重组元素的内部是数据传输路径中设置一些可控节点，并 且这些可控节点要为指令界面可见，这样通过对这些节点按对应的应用环境或者 是要实现的电路功能对应加以控制，就可以改变重组元素之间的电路结构关系和 相互之间的连接关系，实现可重组设计 “ 一一 4 、结：可重组处理单元设许主要存以覃三点：重组元素的选取和设计，重组元 。， 素的粗细即重组元素的规模和层次的确定，对于使用频度高的基本运算成分，应 该在硬件逻辑电路中设置相应的基本单元，这些基本单元就作为可重组体系结构 的重组元素：重组元素之间互相连接关系的确定，确定不同的互连程度可以决定 电路内部互连线的连接复杂程度，可以影响到芯片面积：可控节点的合适选取，合 理的节点选取可以简化控制。简化编码难度，而使更为复杂的电路功能的实现变 ，为可能，使芯片各项性能达到较高的理想的指标 ， 8 第三章非对称算法空间r s a 和e c c 算法的可重组分析 3 1 密码学概述 人类应用密码学的历史可以追溯到几千年前，在很早以前人类就把密码技术 用到军事和政治等领域最早的密码学相关的技术文献的发展出现在3 0 0 0 多年前 的古埃及，千百年来随着密码学的不断应用和发展，密码学最终成为了- 1 7 为各 国所专注的特殊学科，特别香浓( s h a n n o n ，c l a u d ee l w o o d ) 的信息论的发表标志 着密码学进入了一个里程碑式的发展阶段在今天，密码学已经不限于政府部门 或者军事部门，而是应用到各个领域，而且在保障信息安全中越来越举足轻重 一密码学( c r y p t o l o g y ) 通俗的讲就是研究信息系统安全保密的科学，主要研究 领域分为密码编码学( c r y p t o g r a p h y ) ，密码分析学( c r y p t a n a l y s i s ) 两个方面， 密码编码学主要研究对信息进行编码，实现对信息的隐蔽密码分析学主要研究 加密消息的破译或消息的伪造密码编码学和密码分析学两个方面，前者是是信息 保密，而后者就是研究破译或者还原信息 在密码学中，需要加密和传递消息被称为明文( p l a i n t e x t ) 通常采用一定的 数学运算来伪装消息以隐藏它的内容的过程称为加密( e n c r t p t i o n ) ，被加密后的 消息称之为密文( c i p h e r t e x t ) ，相反的过程，把密文转变为明文的过程称为解密 ( d e c r y p t i o n ) ，通常也是要通过一定的数学运算来实现其中用于加密和解密的 数学函数称之为密码算法( c r y p t o g r a p h ya l g o r i t h m ) 加密和解密算法的操作通 常都是在一组密钥的控制下进行的，分别称为加密密钥( e n c r y p t i o n k e y ) 和解密 密钥( d e c r y p t i o nk e y ) 下图所示为通常的密码通信系统 ， 嗣圈 眇橱_ 瀚四毗 抽：密姒黜 。l j j 正 9 3 1 1 密码体制以及分类 3 1 1 1 密码体制 密码体制：它是一个五元组( p ，c ，k ，e ，d ) 满足条件： ( i ) p 是可能明文的有限集；( 明文空间) ( 2 ) c 是可能密文的有限集；( 密文空间) ( 3 ) k 是一切可能密钥构成的有限集：( 密钥空间)。 ( 4 ) 任意k e k , 有一个加密算法e k e 和相应的解密算法d k e d ，使得e k ：p - * c 和d k ：c - - - p 分别为加密解密函数，满足d k ( e k ( x ) ) = x ，这里x p 。 f 3 1 1 2 公开密钥系统 密码系统的分类可对应予不同的标准，通常将密码算法分为基于算法保密和 基于密钥保密两种，基于算法保密的加密算法的可靠性依赖加密算法的保密程度， 通常情况下算法是有限的，如果算法泄漏后必须更换新的算法，目前已经逐步为 基于密钥算法所取代基于密钥算法的保密性是基于对密钥的保护，而密钥的种 类，分发等策略已经相当成熟，因而，保密性大大增强 基于密钥的算法，按照密钥的特点分类可分为对称密码算法( s y m m e t r i c c i p h e r ) ，又称传统密码算法( c o n v e n t i o n a lc i p h e r ) ，就是加密密钥和解密密钥 相同，或实质上等同，即从一个易于推出另一个，又称秘密密钥算法或单密钥算法： 非对称密钥算法( a s y m e t r i cc i p h e r ) ：加密密钥和解密密钥不相同，从一个很难 推出另一个又称公开密钥算法( p u b l i c - k e yc i p h e r ) ，公开密钥算法用一个密 钥进行加密，而用另一个进行解密其中的加密密钥在一定范围内可以公开，又 称公开密钥( p u b l i c k e y ) ，简称公钥解密密钥必须保密，又称私人密钥( p r i v a t e k e y ) 私钥简称私钥应用非对称密码算法的密码系统称之公钥系统，也称p k i 系 统 ， 公钥密码体制使用的是在数学上相关的两个密钥，并通过用其中一个密钥加 密的明文只能用另一个密钥进行解密的方法来使用它们当使用用户专用密钥加 密，而用该用户公开密钥解密时，则可实现一个被加密的消息可被多个用户解 读；当使用用户公开密钥加密，而由该用户专用密钥解密时，则可实现传输的信息 1 0 只被一个用户解读前者常被用于数字签名，后者则常用于保密通信加密解密 过程可以双向进行，即我可以使用您的公钥加密某个信息以确保只有您可以使用 您的私钥来读取它另外，还可以使用我的私钥来加密某个信息，尽管从信息隐藏 的观点来看，这是没有意义的实践因为知道我公钥的任何人都可以解密该 消息但这是认证系统的基础，其确保了消息确实来自知道自己我私钥的人那里 自1 9 7 g 年以来，学者们提出了许多种公钥加密方法，它们的安全性都是基于 复杂的数学难题根据所基于的数学难题来分类，有以下三类系统；基于大整数因 子分解的公钥密码系统( 砖表性的有l i s a 基于离散对数的公钥系统( 代表性的有 d s a 椭圆曲线离散对数系统( e c c ) 与传统的对称密码体制相比较，非对称密码体制具有如下的优点： ( 1 ) 密钥分发简单由于加密和解密密钥不同，而且不能从加密密钥推导出 解密密钥，因此加密密钥表可以像电话号码本一样分发 ( 2 ) 需要保存的密钥量减少，存储的空间减少 ( 3 ) 可以实现数字签名，数字签名是指用户用自己的私钥对原始数据的h a s h 摘要进行加密所得的数据。信息接收者使用信息发送者的公钥对附在原始信息后 的数字签名进行解密后获得h a s h 摘要，并通过与自已收到的原始数据产生的h a s h 摘要对照，便可确信原始信息是否被篡改这样就保证了数据传输的不可否认性 实际上，由于使用公开密钥算法的加密和解密速度比对称密钥算法要慢的多， 通常用它对明文的摘要，或者对称密钥进行加密，而不直接对大量的明文做加密 1 3 2 密码学相关数学知识 3 2 i 数论 本文中需要了懈的数论知识包含：， ( 1 ) 模运算 给定一个整数n 如果用n 去除两个整数a ，b 所得到的余数相同，则称a 和b 关于 模n 的同余，记为a m b m o d n 从o n n 一1 的整数组成的集合构成了模n 的完全剩 余系，对每一个整数a ，它的模n 剩余是0 到n l 之间的某个整数，运算a m o d n 表 示a 被n 除的剩余，称为模n 运算 模运算同普通的算术一样是可以交换，结合，分配的，而且模n 运算的每一个 中间结果，与先进行全部运算，再对最后的结果模n ，其作用是一样的，模运算有下 述性质： ( a + b ) m o d n = ( ( a m o d n ) + ( b m o d n ) ) m o d n ( a - b ) m o d n = ( ( a m o d s ) 一( b m o d n ) ) m o d n a b m o d n = ( ( a m o d y ) ( b m o d n ) ) m o d n a ( b + c ) m o d n = ( ( a b m o d n ) + ( a c m o d n ) ) m o d n 若n i ( a - b ) ，则a ；bm o dn ： 、 ( am o dn ) = ( bm o dn ) 意味a i bm o dn a - - - - - - bm o dn 等价于b am o dn 若a e bm o dn 且b z cm o dn ，贝q a - - cm o dn。 密码学中用了很多的模运算，因为像计算离散对数和模n 平方根这样的问题 是团难的模运算也很容易在硬件上实现，因为它将所以中间值和最后值限定在 一个范围内对一个k 比特的模n ，任何加，减或乘的中间结果都不会超过2 k 比特长 因此我们可以用模算术做指数运算而又不会产生太大巨大的中间结果。 ( 2 ) 素数、大数概念 ， 素数指一个大于i 且因子只有1 和它本身的整数，没有其它整数可以整除它 如2 是尾各素数，其它素数如7 9 ，2 5 2 1 ，2 3 6 5 3 4 7 7 3 4 3 3 9 等，素数有无限多个，密码学 特别是公钥密码学使用大素数一般超过5 1 2 比特长甚至更大密码学中所使用的 数一般位长都在5 1 2 位以上，因此称之为大数 ( 3 ) 最大公因子 如果两个数它f f 】除l 之外没有其它共同的因子，则称这两个数是互素的，换言 之，如果正数a 和n 的最大公因子为l ，则记为 g c d ( a ，n ) = l 如1 5 和2 8 ，1 3 和5 0 0 ，一个素数与它倍数以外的任何其它数都是互素的计算 两个数的最大公因子是古老的e u c l i d e a n $ 莩法，k n u t h 描述了该算法及一些现代的 改进以下为计算最大公因子的e u c l i d e a n 算法： 输入：整数x y 输出：g c d ( x ，y ) ( 1 )如果x o ，则x 一一x ( 2 )如果y o ，则y 一一y ( 3 )g o ，执行： g 一x 。 x 一y m o d x g 一y ( 5 )返回g 上述方法可以推广到求m 个数的最大公因子 3 2 2 域表示 本节将对有限域做简要的介绍，在密码学中，大多数的运算多时在有限域内 进行的，而且满足有限域的一些运算法则由于有限域运算具有无进位、等比特和 无舍入误差的特点，使其在密码学领域中得到了广泛的应用 有限域( f i n i r ef i e l d ) ，又称伽罗瓦域( g a l o i sf i e l d ) ，是广泛应用于密 码学上的一种特殊的群基本定义如下：包含p 个元素的有限域元素存在并且唯一， 有限域就是指上述代数系统具有有限个元素，当且仅当p 是一个素数的幂在有限 域上。非零元素的加，减，乘，除均有定义，基本的加法单元为0 ，乘法单元为l ，任一 非零元素都有唯一的逆元，并且逆元必在该有限域中，有限域中，交换律，结合律， 一 分配律均适用 + ” 3 2 2 1 有限域f p “ n 有限域f p 是由整数集合 0 ，i ，p - l 组成，每个这样的整数可以用一个长度 恰为t = r l o g ，n 的= 进制整数表示，该表示由整数的二进制表示及在其左边添加 适当个数的0 组成，f ，中元素具有以下算术运算： 加法：如果a ，b g f ( p ) ，则a + b = r ，其中r 是a + b 被p 除所得的剩 余，o r r 1 、 ， 。 ， 乘法：如果a ，b c f ( p ) ，则a b = s ，其中s 是a b 被p 除所得的剩 余，o s p 一1 令f 表示g f ( p ) 中所有非零元素，可以证明在g f ( p ) 至少存在一个元素g ，使得 f p 中任意非零元素可以表示成为g 的方幂，这样的元素g 称为g f ( p ) 的生成元( 或本 原元) ，即有： f f g - ：o i p 2 ) a = g 。r 的乘法逆是a - = g - kg - i m o d ( p - 1 ) 大多数密码系统都基于素数域f p ，其中p 是一个非常大的素数，素数中所有的 运算都要模p 归约 3 2 2 2 有限域g f ( 2 m ) 7、 有限域对，q 为素数，有限域n 中的算术模n 次不可约多项式，且系数模p 归约 所谓不可约多项式，就是不能被表示成任何其它两个以上的多项式的乘积，如 x x o x ，而x 2 x 2 十x 就不是不可约多项式，因为它可以表示为x ( x + 1 ) ( x + 1 ) 通常令q = 2 ，则称之为g f ( 2 ) 有限域，也称为特征为2 有限域，特征为2 的有限 域在硬件上和软件上非常容易实现，因为计算机软件和硬件里都是采用的二进制 数表示方式，而且特征为2 的有限域上的运算同自然域的运算有所不同，由于只有 0 ，1 则当进行模加和模乘时分别可以用逻辑异或和逻辑与来完成 3 2 2 3 有限域g f c p ) 和有限域g f ( 2 ) 的统一 为了在硬件上更容易实现，本文中的讨论的e c c 是基于g f ( 2 i ) 的，而要与r s a 实现可重组设计，则必然要求能将两者基于的域统一起来通常r s a 算法运算要进 行取模运算，即最终运算结果要限定在模数n 内，因此r s a 算法实际上满足建立在 有限域g f ( p ) 上，对于g f ( p ) ，如果p 是一个大素数，令f 1 0 9 ：9 ，那么也可以将6 f ( p ) 中的元素用g f ( 2 ) 中的元素表示，这样r s a 算法基于g f ( p ) 讨论，其模数也可以表 示为类似子g f (