（模式识别与智能系统专业论文）rsa密码算法的模幂运算vlsi设计.pdf

华中科技大学项士学位论文 摘要 r s a 算法被公认为是目前理论和实际应用中最为成熟和完善的一种公钥密码体 制，可以用来进行数字签名和身份验证，其最基本最核心的算术操作是模乘运算 ( m o d u l a rm u l t i p l i c a t i o n ) ，再由一系列的模乘来完成模幂运算。f 采用与现代微电子技 术相结合的芯片设计技术来实现低复杂度、高速度的m o n t g o m e r y 运算电路对于r s a 密码算法的v l s i 实现具有重要的意义。 本课题基于此目的，完成了对一个5 1 2 位的r s a 密码系统的分析和系统设计， 、 结合现有条件，完成了模幂运算的口核设计：f 本文介绍了密码学的基本概念，包括 数论的基础知识和模运算的概念。分析了r s a 和m o n t g o m e r y 模乘算法，重点介绍了 基于脉动阵列的基为2 的改进的m o n t g o m e r y 模乘算法。对整个模幂运算系统的结构 进行了分析和划分，并按照划分的子模块，设计了串行乘法器、串行平方器、模乘器 等子模块。 本设计采用“t o p - d o w n ”的设计方法和“b o t t o m u p ”的测试方法，完成了前端 的设计流程。采用v e r i l o g h d l 语言进行了r t l 级的描述，并利用e d a 工具进行了 仿真和综合，得到了符合要求的电路和门级网表。 关键词：m o n t g o m 。e r y 姆+ 皇赁丞洼萤 串行平方器 堡垂曼 r s av l s im 核 一一一一 华中科技大学硕士学位论文 a b s t r a c t a m o n gt h ev a r i o u sp u b l i ck e yc r y p t o s y s t e m ，r s aa l g o d t h mi s t h eb e s tc h o i c ei n t h e o r ya n da p p l i c a t i o n , a n di t i so r e nu s e dt oc u g i t a ls i g n a t u r ea n di d e n t i f i c a t i o n m o d u l a r m u l t i p l i c a t i o ni st h eb a s i ck e y a r i t h m e t i co p e r a t i o no fr s a d e s i g nl o w e rc o m p l e x i t ya n d h i g h e rs p e e dm o n t g o m e r yd i g i t a lc i r c u i tu s i n gt h em o d e r nm i c r o e l e c t r o u i cc h i pd e s i g n t e c h n o l o g yb e c o m e s m o l ea t t r a c t i v e i nt h i st h e s i s ，a51 2b i t sr s a c r y p t o s y s t e m sa n a l y s i sa n ds y s t e md e s i g nh a sb e e n p r o p o s e d m o d u l a re x p o n e n t i a f i o ni pc o r o i s a c c o m p l i s h e du t i l i z i n g h u s ti cd e s i g n c e n t e r sc o n d i t i o n s t h eb a s i cc o n c e p t si n c l u d i n gn u m b e rt h e o r ya n dm o d u l a r a r i t h m e t i c a r ei n t r o d u c e d r s aa n dm o n t g o m e r ym o d u l a ra l g o r i t h ma r ea n a l y z e d ，e s p e c i a l l yr a d i x 2 m o d i f i e dm o n t g o m e r ym o d u l a rm 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 ns y s t o l i ca r r a y t h e m o d u l a re x p o n e n t i a t i o nc o m p u t a t i o ns y s t e m sa n a l y s i s a n d p a r t i t i o n i sa c h i e v e d h e s e r i a l - p a r a l l e lm u l t i p l i e ra n ds q u a r e r 、m o d u l a rm u l t i p l i e re t c ，h a s b e e nd e t a i l e db a s e do n s y s t e mp a r t i t i o n t h e t o p - d o w nd e s i g n m e t h o da n db o t t o m - u pt e s tm e , h o d i se m p l o y e d t h ec i r c u i ti s d e s c = r i b e di nv c r l i o g h d lo nr t ll e v e l t h es i m u l a t i o na n ds y n t h e s i sw i t he d a t o o l si s c o m p l e t e d , a n d t h ef a c t u a lc i r c u i ta n dn e tl i s t si sa c q u i r e d k e y w o r d s ：m o n t g o m e r y m o d u l a rm u l t i p l i c a t i o ns e r i a l - p a r a l l e lm u l t i p l i e r s e r i a l p a r a l l e ls q u a r e r m o d u l a r m u l t i p l i e r r s a i pc o r ev l s i 1 。1 澡题研究背景及意义 绪论 世界已进入信息时代，计算机网络和i n t e r n e t 的飞速增长，绘我们的生活带来了 蹙大的影响。现在，人们可以足苓出户，在计算机前面就完成购物、汇款、邮递辞活 动。燕是瞧予售息技术涉及到了社会生涵的各个方嚣，包括翁关国家安全的政治、经 济和军事情况戳及一些企泣秘私人戆提密与敏感接息，因此也裁成为敬对国家和些 电脑漂客威胁和玻击鹩主要醛标。这攫静藏胁和玻齑包攥嚣个方蘧。个是搔对姻络 和计算机物璎上的威胁和攻静，阮鲡自然灾菘、人为磙嚣等等，母戳遽过慰落惠系统 的冗余备份以及瞢棒性设计来避免；另个方面楚措对禽患静威胁和攻击，镪括信惠 泄漏和信息破坏。信息被侦晰、截获、窃取、删除等等都属于此类，这就提蹬了许多 信息安全的额课题，比如信息加密、数字签名、岿份验诞等等。随着电予商务等阏络 增殖灶务鹃迅速增长，铸息安全已经变得越来越重要。数据加密技术是网络中最基本 耱安全技零。它是逶过对露终孛传繁约傍息遴行力丑密来保障其安全性的。 匀日密技术按照密鹤嫠鬟方法苓霜霹鞋分必对椽密钥算法翔势对称密钥算法a 对称 密铜算法中，加密、解密都便蕉相弱靛鬻锯。 # 瓣称密锈算法又罄公钥密码算法，即 加密、解密使用两个不同的密铜。由于公锈密码算法在绦迁数据弱栋密性、完整蛙以 及签名和认可等方面的突出优点，它已经成为了当令嚼络安全串爱黧要滟解决方法。 在众多的公钥密码体制中，1 9 7 8 年由r i v e s t 、s h a m i r 和a d l e m a n 在美酗m i t 掇出静 r s a 算法被公认为是目前理论和实际应用中最为成熟和完善的种公铜密码体镧，w 班用来邀嚣数字签名窝赛份验落。该算法的安全性依赖于大整数的素数因予分解的融 难彀，其聂蒺本最核心静箕零掇作燕攘莱运算( m o d u l a rm u l t i p l i c a t i o n ) ，再由一系列 的攘乘来完硪模幂遂算秀7 游是砖密玛强度熬嚣求，摸幂运算的操作数的位数都比 较高( 5 1 2 使甚至更高) ，所良遂舞蠢极大，缀礁获褥缀舞豹数攥吞蛙率，成为提高系 统加解密运算速度的瓶颈。 _ h 一- 一h l 华中科技大学硕士学位论文 采用m o n t g o m e r y 模乘算法可以较好的解决这一问题。它是一种快速模乘运算方 法，采用了模加右移的方法来避免通常求模运算当中费时的除法步骤。基于 m o n t g o m e r y 算法，可以使用二进制方法处理幂运算，将幂运算用一系列的的乘法和 乘方运算来代替，但同时也带来了进行模乘次数过多的问题。 我们可以看到，利用r s a 密码算法对数据进行加解密操作是一种区别于加减乘 除的比较高级的运算形式一一求模运算。m o n t g o m e r y 算法将大数模幂运算分解之后， 又变成了一个运算非常密集的过程。如果采用软件来实现，按照现在的c p u 处理速 度和通常的通信带宽是无法进行实时处理的，而采用与现代微电子技术相结合的芯片 设计技术来实现低复杂度、高速度的m o n t g o m e r y 运算电路对于r s a 密码算法的v l s i 实现具有重要的意义。 目前的i c 设计已经进入了片上系统( s o c ) 时代，各种i p 核是进行s o c 设计的 物质基础。本课题结合华中科技大学集成电路设计中心的现有条件，对r s a 密码体 制中的模幂算法的m 核实现进行了重点研究，主要集中在提高其运算速度方面的性 能。 1 2 国内外研究现状 目前，基于m o n t g o m e r y 模乘算法，国内外的科研人员主要从两个方面展开了对 模幂运算的研究【“。 一个方面是采用冗余基数( r e d u n d a n tr a d i xn u m b e r ) 表达的方法，研究最多的就 是在m o n t g o m e r y 模乘算法中采用高基( 1 l i g h r a d i c e s ) 的结构。 e f b r i c k e l l 比较早的提出了这种思路伫l 【3 】； s e e l d r i d g c 等人通过简化电路结构中的组合逻辑，从而优化了关键路径，提高 了系统时钟的频率，获得了两倍于传统方法的加解密速度； h o r u p 通过改进算法，避免了高基方法中过于复杂的商的确定的问题【4 】： 位于巴黎的d i g i t a le q u i p m e n t 公司研究实验室的n s h a n d 等人采用了中国余数定 2 华中科技大学硕士学位论文 理、异步进位完成加法器以及窗口幂等方法，在一个由1 6 个x i l i n x3 0 9 0f p g a 组成 的阵列上实现了基于高基方法的模幂算法，它能以1 8 5 k b s 的速度完成9 7 0 b k 的r s a 加密运算； 为了减少一次操作的数的位数，台湾学者c h e h a r tw u 等人把乘法器的操作数划 分成了几个同样大小的部分，每一部分都作为一个累加和求模的基本单元进行运算。 这样，就每一部分的乘数和余数都可以采用流水线方式实现，同时，也采用了多比特 重叠扫描技术以减小逻辑深度，优化关键路径1 5 】。 n a o f u m i r a k a g i 等人在1 9 9 2 年提出了一种新的方法。它把所有的操作数都用冗余 数来表示，这样在进行模加的时候就不存在进位传播的问题，模乘器也可以以规则的 原胞阵列的结构来实现，从而更适合v l s i 实现【6 1 。类似的，j b a j a r d 等也在1 9 9 8 年 提出了类似的设想用。 除了采用高基的方法之外，另一种实现方法就是脉动阵列的方法实现，这种方法 一般都把操作数的基固定为2 ，利用脉动流水来实现高的数据吞吐率。 c o l i nd w a i t e r 利用右移被乘数来避免了商的确定，采用了一个m x m 的二维脉 动阵列来实现，使得模乘的速度达到了一个很高的水平8 1 1 9 ； 此外，这种采用二维脉动阵列的还有k 1 w a m u r a t l o l 、p a w a n ”，其特点都是硬 件开销巨大； p e t e rk o m e r u p 设计了一种一维结构，它由一行处理单元组成，平方和乘法平行 计算。对于一个i 1 比特的摸幂运算需要n 个脉动处理单元和2 n 2 个时钟周期1 1 2 1 ； psc h e n 等人改进了原始算法，把后调整的步骤从中去掉，对称地映射一个二维 信号流图到一个一维脉动阵列当中，得到了一种基于比特操作的结构，但是速度太慢 0 3 1 ； c h i n g - c h a oy a n g 等人也在对m o n t g o m e r y 改进的基础上，设计了一个一维脉动阵 列，通过减少关键路径的延时，提高了系统的性能； 相对于国外和台湾地区对于r s a 硬件实现研究的成熟，国内在这方面起步比较 晚，同时，受国内微电子工艺和i c 设计水平的限制，已经成功漉片的设计屈指可数。 1 9 9 8 年，清华大学的张武健等人采用了f i p s 等方法实现高基模乘算法； 3 华中科技大学硕士学位论文 = _ l = = = = = _ = = = = g _ _ - l j _ _ e ；= = l h = = _ 自e j 2 0 0 0 年，清华大学微电子学研究所的李树国等人在国家自然科学基金的支持下， 设计了一种适合于面积较小的智能卡应用的高基模乘器新结构【1 4 1 ： 2 0 0 1 年，清华大学的杨骞等人运用了适合硬件实现的c i o s 方法和窗口法减少 模幂运算过程中所需的模乘运算次数，提高了处理速度”6 1 ，也获得了嵌入式方面的应 用； 另外，采用高基方法的还有清华大学微电子研究所的周芬旧和方颖、- o - lj s l ，但是以 上的设计都没有见到投片的报道。 1 9 9 8 年和1 9 9 9 年，清华大学微电子学研究所的陈弘毅等人基于m o n t g o m e r y 模 乘变换，采用脉动阵列的方法，结合简单二进制幂运算算法，采用o 8 u c m o s 工艺， 设计并制造了2 5 6 比特模幂乘运算器t h m 2 5 6 ，共1 8 6 7 7 门，面积1 7 6 3 m m 2 ，工作于 9 0 m h z 以上，功耗低于1 5 w ，运算速度达到1 1 7 k b p s t l 9 1 ： 另外。深圳中兴集成电路设计有限公司已经成功的设计出了模幂乘密码算法协处 理器芯片一- - s s x 0 4 ，支持的最高时钟频率为i o o m h z ，模长和幂长都为1 0 2 4 位对的 模幂运算速度为6 6 次，秒。运算速度与模长度成反比，模的长度可以是从3 2 位到1 0 2 4 位的任意位数口0 1 ； 由此我们可以看出，国内在模幂算法的密码协处理器方面的设计相当落后，而且 集中在少数几所高校和企业。长期这样，会对我国的国家安全，经济稳定带来不可弥 补的损失。 1 3i c 设计的典型淹程 集成电路的发展经历了小规模( s s i ) 、中规模( 船i ) 、大规模( l s i ) 、超大 规模( v l s i ) 几个阶段。全球半导体工业将由模拟向数字，由超大规模集成电路( v l s i ) 向系统芯片( s 0 c ) 全面转型彤j 。 s o c 把多芯片集成系统的各个功能集成到一块芯片上，从而可以显著的提高 s o l u t i o n 的性能和可靠性。s o c 在单一芯片上可以集成数字和模拟电路，包括微处理 器，存储器，d s p ，a d 和d i a 转换器，p l l 甚至m e m s 等众多单元，一块s o c 就 4 华中科技大学硕士学位论文 = i i # 目= j ；= = = = j 自= = = j l _ - ；= i 目_ _ _ ；= 一目_ _ i = 是一个系统。个典型的s o c 如图1 1 所示。集成电路设计指的是从硬件的一种形式 到另一种形式的变换，设计的最终目标是得到集成电路的某种可制造的描述形式( 5 1 。 s o c 的设计采用t o p d o w n 和结构化设计的方法，以各种i p ( i n t e l l i g e n tp r o p e r t y ) 为 基础，以软硬件协同设计为主要方法来开发s o c 。i p 是具有知识产权的、已经设计好 并经过验证的并可重复利用的集成电路模块。比如存储器核，s p a r c 微处理器核等 等。这里的m 主要包括虚拟部件v c ，设计和重用，相关的接口标准。国外的i c 设 计厂家多年来积累了大量的i p 核，包括软核、固核和硬核，显然利用现有的p 进行 设计可以改善和提高系统性能，减少设计瓶颈。 图1 i 典型的s o c 结构 s o c 设计技术也可以称为基于平台的设计技术( p l a t f o r mb a s e dd e s i g n ) 。平台的 建立主要是口核的设计。平台的应用就是在m 核的基础上进行软件和硬件的独立或 者协同设计。图1 2 显示了一个典型的s o c 的设计流程。首先根据用户的要求提出整 个系统的设计规范以及系统的整体描述，其中包括了系统行为描述和系统结构描述。 行为描述就是对系统划分出具有不同功能的各个子模块；然后根据这个行为级的功能 划分进行结构描述，也就是把手中掌握的m 核( 包括已有的或者自己设计的) 对应 到各个功能模块。之后，通过系统仿真与系统行为描述的交互修正，确定系统结构描 述和软硬件的划分。s o c 中所使用的m 核来自不同的供应商，有些还可能是自己设 计的。所以l c 设计工程师必须对它们进行必要的修改和描述，以解决不同模块在s o c 设计中仿真致性的问题。 华中科技大学硕士学位论文 = = = t = 。- t = = = = = 。- ；t ；= = ；= = - - 圈一一： 图1 2 一个典型的$ o c 设计漉程 由此可以看出，现代s o c 设计的基础是各种m 核的设计。口核的设计应该遵循 一定的规范和标准，以获得良好的可重用性、可扩充性等品质。现在一个i c 设计公 司是否具有很强的实力，很大程度上看它拥有的具有自主知识产权的碑的多少a 目前，口核的设计基本上可以看作大家熟悉的传统v l s ! 设计中的前端设计。包 括： 6 华中科技大学硕士学位论文 = = = i t = l = = = ；= _ 。 ；目= _ e _ = i _ _ _ - _ # = # _ l - l # = = = _ j = = ； 1 、制定设计规范，抽象地描述所设计的电路的功能、接口和整体结构： 2 、进行功能级的描述和r t l 级的描述； 3 、利用e d a 工具进行功能级的仿真与验证： 4 、结合具体工艺进行逻辑综合，将r t l 的h d l 代码映射到具体的工艺上加以 实现； 5 、门级仿真：逻辑综合工具将r t l 描述转换成门级网表生成d b 文件。并将网 表中的延时信息存成s d f 文件( 标准延时文件) ，以用于门级仿真时将综合出 来的电路中的延时信息随测试代码一起送入仿真器中。门级仿真需要相应的 仿真库的支持。 其中，绝大部分的设计工作都集中在用硬件描述语言进行r t l 描述上。 1 4 论文的主要内容 本课题的任务就是采用脉动阵列结构设计一个r s a 密码体制中的模幂算法的礤 核。利用硬件描述语言v m - i l o g l - i d l 对其进行r t l 级描述，使用c a d e n c e 公司的v e f i l o g 一。仿真工具进行功能级和门级的仿真。使用s y n o p s y s 公司的d e s i g na n a l y z e r 进行 综合。论文结构如下： 第一章介绍了本论文的研究背景和意义，了解了目前国内外在基于m o n t g o m e r y 模乘方法的模幂运算的研究现状，简要介绍了s o c 设计的典型流程和口核的概念以 及本论文的体系架构。 第二章介绍密码学的一些基本概念，并着重介绍了r s a 公钥密码体制的基本原 理。 第三章介绍了m o n t g o m e r y 模乘的基本概念和算法 7 华中科技大学硕士学位论文 ；= = ；= = = = = 自_ 目= _ l i 自= = = = 自e = t t ： ； 第四章介绍了球核的需求分析和整体架构设计，之后分模块的介绍了设计过程。 第五章介绍了仿真、综合调试的试验结果。 第六章对全文工作进行了总结。 本设计采用的技术库是t s m c 0 2 5 u m s a g e 技术库，来自于美国a r t i s a n c o m p o n e n t s 公司。 d e s i g na n a l y z e r 的综合库设置为： l i n kl i b r a r y ( 联接库) ：t y p i c a l d b t a r g e tl i b r a r y ( 目标库) ：t y p i c a l d b s y m b o ll i b r a r y ( 符号库) ：t s m c 2 5 s d b 仿真库为t s m c 2 5 v 。 设计环境是s u n 公司的u l t r a l 0 工作站，采用s o l a r i s 2 i 6 版本的cs h e l l 环境下的 u n i x 操作系统。 8 华中科技大学硕士学位论文 5 。2 2 2 。目2 ；5 2 4 目。_ ； _ _ = t 口；= = ；= 目：l i _ 2 密码学的基本概念 为了内容的完整性，本章有必要对与后续章节有关的密码学的基本概念和r s a 密码体制做一些必要的介绍。 2 1 数论的基础知识 本节将简单地介绍有关整数集合z = ( ，一2 ，- 1 ，0 ，l ，2 ， 和自然数集合 n = 0 ，l ，2 ， 的最基本的数论概念吲。 2 1 i 因子的栩捻 一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号d a ( 读作 “d 除a ”) 意味着对某个整数k ，有a = k d 。0 可被每个整数整除。如果a o 且d a ， 则d i a l 。如果d l a ，则我们也可以说a 是d 的倍数。 如果d i a 并且d 0 ，则我们说d 是a 的约数。注意，d l a 当且仅当( - d ) ! a ，因此 定义约数为非负整数不会失去一般性，只要明白a 的任何约数的相应负数同样能整除 a 。一个整数a 的约数最小为l ，最大为l a 。例如，2 4 的约数有l ，2 ，3 ，4 ，6 ，8 ， 1 2 和2 4 。 每个整数a 都可以被其平凡约数1 和a 整除。a 的非平凡约数也称为a 的因子。 例如，2 0 的因子有2 ，4 ，5 和1 0 。 2 1 2 素数与合数 对于某个整数p l ，并且因子仅为l 和p ，则我们称p 为素数( 或质数) 。素数具 有许多特殊性质，在数论中举足轻重。按顺序，下列为一个小素数序列： 9 华中科技大学硕士学位论文 = # = ；= = = = 目自目目 ；= _ = = 不是素数的整数a l 称为合数。例如，因为有3 f 3 9 ，所以3 9 是合数。整数l 被 称为基数，它既不是质数也不是合数。类似地，整数0 和所有负整数既不是素数也不 是合数。 亚里士多德和欧拉已经用反证法非常漂亮的证明了“素数有无穷多个”。 若不计素数的排列次序，任何大于l 的整数a 都能被因式分解为如下的唯一形式 我们称为标准分解式： 口= 计店露 ( 式2 一1 ) 其中p 为自然数中的第i 个素数，p l p ： p r ，且e 为非负整数( 注意e 。可以为o ) 。 例如：1 1 0 1 1 = 7 1 1 2 1 3 另外，如果p 表示所有素数集合，则任一正整数均可唯一的表示为如下形式： a = 订p 叶其中a 。o ( 式2 - 2 ) p 上式右边是所有素数p 的乘积：对于任一特定的值a ，大多数分量a 口均为0 。 例如：3 6 0 0 - - 2 4 3 2 5 2 常用的素数表通常只有几千个素数，这显然无法满足密码学的要求，因为密码体 制往往建立在极大的素数基础上。所以我们要为特定的密码体制临时计算符合要求的 素数。这就牵涉到紊性检测的问题。 判断一个整数是不是素数的过程叫索性检测。目前还没有个简单有效的办法来 确定一个大数是否是素数。理论上常用的方法有： ( 1 ) w i l s o n 定理：若( n - i ) f 一l ( m o dn ) ，则n 为素数； ( 2 ) 穷举检测：若石不为整数，且n 不能被任何小于由的正整数整除，则n 为素数； i o 华中科技大学硕士学位论文 但是这些理论上的方法在n 很大时，计算量太大，不适合密码学中使用。现现在 常用的素性检测的方法是数学家s o l o v a y 和s t r a s s e n 提出的概率算法。即在某个区 间上能经受住某个概率检测的整数，就认为它是素数。因子分解问题是n p 困难问题。 如果n 为2 0 0 位十进制数，用那么对n 进行素数的因式完全分解大概要花费几十亿年。 所以，密码体制都是建立在大数的因式分解的基础上。 2 1 3 公约数与最大公约数 如果d 是a 的约数并且也是b 的约数，则d 是a 与b 的公约数。例如，2 4 与3 0 的公约数为l ，2 ，3 和6 。注意，1 是任意两个整数的公约数。 两个不同时为0 的整数a 与b 的最大公约数表示成g o d ( a ，b ) 。例如， g c d ( 2 4 ，3 0 ) = 6 ，g c d ( 5 ，7 ) = l ，g c d ( o ，9 ) = 9 。如果a 与b 不同时为0 ，则g c d ( a ，b ) 是一 个在1 与m i n ( ；aj ，ib | ) 之间的整数。我们定义g c d ( 0 ，0 ) = o 。下列性质就是g c d 函数 的基本性质： g c d ( 口，6 ) = g c d ( 6 ，a ) g c d ( a ，6 ) = g c d ( 4 ，6 ) g c d ( 口6 ) = g e d q 4 i 1 6 d g c d ( a ，0 ) = 4 a g o a l ( = ，勉) 爿a i 。j 6 ，e a c h 七e z 如果a 和b 是不都为0 的任意整数，则g e d ( a b ) 是a 与b 的线性组合集合( a x + b y ：x ，y z 中的最小正元素。 对任意整数a 与b ，如果d 8 并且d | b ，则d l g c d ( a ，b ) 。 华中科技大学硕士学位论文 = ；= = = = = = = = = 。= ；= = j - 目_ z = = = 目= ；= = = = = 一： ! 对所有整数a 和b 以及任意非负整数疗，g c d ( a n ，6 国= 仃g c d ( a , 功。 对所有正整数n ，a 和b ，如果n i a b 并且g c d ( a ，n ) = l ，则n ib 。 2 1 4 互质数 如果两个整数a 与b 仅有公因数l ，即如果g c d ( a ，b ) = 1 ，则a 与b 称为互质数。 例如，8 和1 5 是互质数，因为8 的约数为1 ，2 ，4 ，8 ，而1 5 的约数为l ，3 ，5 ，1 5 。 对任意整数a ，b 和p ，如果g c d ( a ，p ) = 1 且g c d ( b ，p ) = l ，则g c d ( a b ，p ) = 1 。这说 明如果两个整数中每一个数都与一个整数p 互为质数，则它们的积与p 与互为质数。 如果两个正整数都分别表示为素数的乘积，则很容易确定它们的最大公约数。例 如：3 0 0 = 2 2 3 5 2 ：1 8 = 2 x 3 2 ；g c d ( 1 8 ，3 0 0 ) = 2 3 5 。= 6 ： 确定个大数的素数因子是不容易的，实践中通常采用e u c l i d e a n 和扩展的 e u c i i d e a n 算法来寻找最大公约数和各自的乘法逆元。 对于整数n 。，n 矿”，n 。，如果对任何i c j 都有g c d ( n 。，n j ) = 1 ，则说整数r l ，n ：，n t 两 两互质。 2 2 模算术运算 2 2 1 模运算的基本概念 已知一个整数n ，所有整数帮可以分划为是n 的倍数的整数与不是n 的倍数的整 数。对于不是n 的倍数的那些整数，我们又可以根据它们除以n 所得的余数来进行分 类，数论的大部分理论都是基于上述分划的。 模算术运算也称为“时钟算术”。比如某人1 0 点到达，但他迟到1 3 个小时，则 ( 1 0 + 1 3 ) m o d 1 2 = 11 华中科技大学硕士学位论文 或者写成 l o + 1 3 = l l ( m o d1 2 、 对任意整数a 和任意正整数n ，存在唯一的整数q 和r ，满足0 r n ，并且a = q n + r ，值q - - - - k a n j 称为除法的商，其中lx j 表示小于等于x 的最大整数。值，= am o d 7 称为除法的余数，因此，对于任一整数，可表示为： 或者 口= 【口，一j 一+ 0r o o d n ) ( 式2 3 ) 口r o o d n = a - - k 月j 行 ( 式2 4 ) 例如：a = l l ：n 亍7 ；1 1 = 1 7 + 4 ：r - - 4 “m o d7 = 4 如果( a m o d n ) = ( b r o o d n ) ，则称整数a 和b 模n 同余，记为a - - bm o dn 。 例如：7 3 = 4m o d2 3 ：2 1 i - - 9m o d1 0 模运算符具有如下的性质： l 、若n l ( a - b ) ，则a = - - bm o dn ； 2 、( am o dn ) = ( bm o dr 1 ) 等价于a i bm o dn ； 3 、a = bm o d1 i 等价于b 2 am o dn ： 4 、若a bm o dn 且b cr o o dn ，则a cm o dn a 2 2 2 模运算操作与性质 从模运算的基本概念我们可以看出，模n 运算将所有整数映射到整数集合 o l ，( n 1 ) l ，那么，在这个集合内进行的算术运算就是所谓的模运算。 模算术类似于普通算术，它也满足交换律、结合律和分配律： 1 、 ( a m o dn ) + om o d n ) m o dn = ( a + b ) m o d n ； 华中科技大学硕士学位论文 = = = = = = = = ；。= = = = 目= | 2 = = = 自目 = ； 2 、【( am o dn ) - ( bm o dn ) m o dn = ( a - b ) r o o d 1 1 ； 3 、 ( a m o dn ) ( b r o o d n ) m o d a = ( a x b ) m o d n ； 指数运算可看作是多次重复的乘法运算。 例如：为了计算1 1 7 m o d l 3 ，可按如下方法进行： 1 1 2 = 1 2 1 9 4m o d1 3 u4 - - - - 4 2 ；3m o d1 3 1 17 i l l 4 x 3 - - - - 1 3 2 - - - - - 2m o d1 3 所以说，化简每一个模n 中间结果与整个运算求模再化简模n 结果是一样的。 模运算的主要性质如表2 1 所示。 性质表达式 交换律 ( w + x ) m o dn = ( x + w ) m o d 1 1 ( w x x ) m o dn 寻( x x w ) m o d n 结合律 【( 、+ x ) + y 】m o dn _ 【、+ x + y ) 1 m o d 1 1 ( w x x ) x y m o dn ：【w x ( x xy ) r o o d n 分配律 w x ( x + y ) m o d n = 【( w xx ) + ( w y ) m o d n 恒等式 ( o + w ) m o d n = wm o dn r 1 w ) m o d i - - - - wm o dn 2 2 3 费马定理和欧拉定理 表2 1 模运算的主要性质 费马定理和欧拉定理在公钥密码学中有重要的作用。 费马定理：如果p 式素数，a 是不能被p 整除的正整数，则： 矿i lm o dp( 式2 - 5 ) 费马定理还有另一种等价形式：如果p 是素数，a 是任意正整数，则： a - 2 am o dp( 式2 6 ) 欧拉定理：对于任何互质的整数a 和n ，有： 华中科技大学硕士学位论文 = = = = 口= = = = ；= = = = = = = - 口= 口l = = = i = = ；_ = 一； a “o - - - - - - im o dn ( 式2 7 ) 欧拉定理也有一种等价形式： a “”“2 am o dn ( 式2 8 ) 费马定理和欧拉定理及其推论在证明r s a 算法的有效性时是非常有用的。给定两 个素数p 和q ，以及整数n = p q 和m ，其中o m n ，则： m “：妒1 忡小三mm o dn ( 式2 - 9 ) 这将在后面介绍r s a 算法的时候涉及到。 2 3 密码学的基本概念 密码学是研究密码系统或通信安全的- r 学科，从广义上来讲，密码学属于数学 的一个分支。主要包括两个研究方向，即密码编码学和密码分析学。密码编码学的主 要目的是寻求保证信息保密性和可认证性的方法，密码分析学的主要目的是研究加密 信息的破译和信息的伪造。 密码技术的基本思想是伪装信息，使未授权者不能理解它的真实含义。所谓伪装 就是对信息进行一组可逆的数学变换。伪装前的原始信息称为明文( 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 ) 。 用于解密的一组数学变换称为解密算法。加密和解密算法的操作通常都是在一组密钥 控制下进行的，分别称为加密密钥和解密密钥。 华中科技大学硕士学位论文 = = = = = = ；= = = ；= = = ；j _ , ir i , 目= = i = = = = = 一 密钥j 【 图2 1 密码体制结构示意图 一个密码系统，通常简称为密码体制( c r y p t o s y s t e m ) ，如图2 1 所示，由5 个部 分组成： ( 1 ) 明文空间m ，它是全体明文的集合； ( 2 ) 密文空间c ，它是全体密文的集合； ( 3 ) 密钥空间k ，它是全体密钥的集合。其中每一个密钥k 均由加密密钥k 和解密密钥硒组成，即k = ； ( 4 ) 加密算法e ，它是一族由m 到c 的加密变换； ( 5 ) 解密算法d ，它是一族由c 到m 的解密变换； 对于每一确定的密钥k = ，加密算法将确定一个具体的加密变换，解密 算法将确定一个具体的解密变换，而且解密交换是加密变换的逆过程。对于明文空间 m 中的每一个明文m ，加密算法在加密密钥k 的控制下将m 加密成密文c c = e ( m ，砭)( 式2 1 0 ) 而解密算法在加密密钥的控制下从密文c 中解出同一个明文m m = d ( c ，硒) = d ( e ( m ，k ) ，l ( d ) ( 式2 1 1 ) 1 6 华中科技大学硕士学位论文 ；= = ；目；= ；= = = = # = = = ；t _ - ；自；2 = = ；= = = = 根据对明文地划分与密钥地使用方法不同可将密码体制分为分组密码( 块密码) 和序列密码( 流密码) 体制。 设m 为明文，分组密码将m 划分为一系列明文块m i ，m 2 ，m 。，通常每块 包含若干字符，并且对每一块m i 都用同一个密钥进行加密。即 c = c ( c l ，c 2 ，c 。) 其中 c i = e ( m i ，l ( c ) i 1 ，2 ，n ( 式2 - 1 2 ) 而序列密码将m 划分成一系列的字符或位c o i t ) m i ，m 2 ，r n n ，而且对于这每 一个m i 用密钥序列k = ( k l ，k e z ，k 。) 的第i 个分量k i 来加密，即 c = ( c t ，c 2 ，c n ) 其中 c i = e ( m i ，k ) i = 1 ，2 ，n 分组密码一次加密一个明文块，而序列密码一次加密一个字符或一个位( b i t ) 。两 种密码在计算机系统中都有广泛应用。 根据密钥的特点，s i m m o n s 将密码体制分为对称和非对称密码体制两种。即如果 式( 2 1 1 ) 中的k c - 硒，或由其中一个很容易推出另一个，则称为单密钥密码体制、私 钥密码体制，或者叫对称密码体制。否则，就称为非对称密码体制。进而，如果在计 算上不能由推出，这样，即使将公开也不会损害的安全，于是便可以将 k 公开。这种密码体制称为公开密钥密码体制，简称公钥密码体制。现有的大多数公 钥密码属于分组密码，概率加密体制属于序列密码。 如果能够根据密文确定出明文或密钥，或者能够根据明文一密文对确定出密钥， 则我们就说这个密码是可破译的否则，我们就说这个密码式不可破译的。 密码分析者攻击密码的方法主要有：穷举攻击、统计分析攻击和数学分析攻击三 种。根据密码分析者可利用的数据来分类，可将破译密码的类型也分为三种：仅知密 文攻击( c i p h e r t e x t - - o n l ya t t a c k ) 、已经明文攻击( k n o w n - - p l a i n t c x t a t t a c k ) 和选择明 文攻击( c h o s e - - p l a i n t e x ta t t a c k ) 。对于某一个密码，如果无论密码分析者截获了多少 密文和用什么方法进行攻击都不能被攻破，则称之为绝对不可破译的。这种密码在理 1 7 华中科技大学硕士学位论文 = = = = ；= ；= = = = = = = = ；= 。l l = = = t = = 2 论上是存在的，但是是不可能获得的。只要能够利用足够的人力物力和工具方法，则 任何实际的密码都是可破译的田1 。我们所要寻找的，是那些在有限的时间和有限的资 源内计算上不可破译的( c o m p u t a f i o n a u yu n b r e a k a b l e ) 密码体制。 2 4 公钥密码体制 上个世纪7 0 年代中期，美国斯坦福大学的研究生w h i t f i e l dd i f f i e 和m a r t i n h e u m a n 教授一般性地研究了密码学，特别研究了密钥分发问题。他们提出了一个方 案，由此能够通过交换公开信息建立一个共享的秘密。他们可以在公开的信道上通信， 以密码分析者可获得的形式来回传送信息；同时，生成一个不公开的密码数值。然后 通信双方能够使用这个秘密数值作为对称会话密钥。这个方案称为d i f f i e h e r m a n ， 或者d h 。由此在密码学这个领域出现了一种新的见解：密钥可以成对出现，即一个 加密密钥和一个解密密钥，并且两个密钥之间不能相互生成。d i r g e 和h e l l m a n 首次 在1 9 7 6 年的全美计算机会议上正式提出公钥密码学的概念，并在i e e e 上发表【2 4 1 。 从这个时候开始，人们提出了大量的公钥密码算法，其中许多是不安全的，认为 是安全的算法中又有许多是不实用的，不是密钥太大，就是密文比明文长的多。只有 一部分是既安全又实用的。在这些既安全又实用的公钥算法当中，有的只适合于密钥 分发，有的只适合于加密，有的只适合于数字签名。目前，只有r s a 和e i g a m a l 两 个算法既适合于加密也适合于数字签名。 2 4 1 公钥密码算法的安全性 对于公钥密码算法塞说，其“安全性”的含义有所改变，即假定密码分析者从加 密变换计算解密变换需要非常长的时间，则公开了加密变换对我们来说没有任何危 害，或者说是。安全的” 公钥算法是为了对抗选择明文攻击而设计的，其安全性并存于从公钥推断私钥的 难度和从密文推断明文的难度，但是，大多数公钥算法对选择密文攻击尤其敏感。密 码分析者在着手分析公钥算法时，他们可以选择任何明文来加密，就是说给定c = 1 3 华中科技大学硕士学位论文 = = = = ；。= = = = = = = = = ；# = 。t = j 口目；= = # ；= = = = = 一 e 。(