（计算机软件与理论专业论文）rsa算法研究及速度改进.pdf

沈阳工业大学硕士学位论文 摘要 随着网络技术在全球范围的迅速普及，锄c t 己逐渐渗透到人们的日常生活中， 成为信息交流的重要手段。所有这一切在给人们带来了极大便利同时，也向人们提出了 新的挑战，并对网络安全提出了更高的要求。因此有效保护网络信息传输的安全变得越 来越重要。 本文研究的对象是r s a 密码体制。r s a 是一种公开密钥算法，其加密密钥和算法 本身都可以公开，解密密钥则归用户私人拥有。从诞生那天起r s a 就因为安全强度高、 使用方便等卓越性能受到关注，并得到广泛应用。目前，许多密码系统中都嵌有r s a 密码算法但是，近年来由于分解大整数的能力日益增强，为保证r s a 密码体制的安 全性总是要增加模长，使得加密、解密操作要计算位数达十进制百位以上的模幂乘函数， 执行的时问长，这一直是制约其应用的瓶颈问题，因此本论文在速度方面对r s a 算法 做了相关改进。 本文首先对r s a 密码体制的原理进行了深入细致的研究，为改善算法打下良好的 理论基础；其次分析了r s a 密码体制的安全性，讨论了针对r s a 的各种攻击方法，以 及如何在相关算法中作相应处理以抵御这些攻击；再次，本文对影响算法速度的几个因 素做了详尽的分析，根据分析的结果，对递归余数和算法、基于乘同余对称性的快速算 法和素数的素性检测算法做了相应的改进。改进后的算法，通过一系列的测试数据表明， 其速度确实有所提高。 本文还提出了预处理表的思想，即当需要加密的信息均为英文时，可以预先生成一 个数据表，存放所有可能出现的明文所对应的密文，这样在后续的从明文到密文的转换 中，可以直接进行查表，极大的节省了计算时间。预处理表算法所节省的时间与要加密 的明文信息量的多少有关，要加密的明文越多，所节省的时间就越多。 关键词：船a 算法，递归余数和算法，乘同余对称性快速算法，预处理表 船a 算法研究及速度改进 r - e s e a r c h 锄da m e l i o r a t et h e 黜l t eo f r s aa l g o r i 协m a b s t r a c t 舢gw i n l 曲屺角s tp o p m a r i z a l i o fn 咖o r ki nm es e v e ns e 鹊，i n t 锄e t 弘i d l i a l l y p e m c t 翰：t e si n t 0p p l e sd a i l yl 疵，a n di tt l l m si n i 【ot h ei n l p d r t a n tm e t l l o do fi n f 0 埘怕商o n a 【c h 乏m g e a uo f t h e b i i n g st l 蟛豇i 讲m o 璐“m v c n i e i l t ot h ep e o p l e ，b u ti ta l s op m p o st h e n e w c h a l l g c ，a n ds c t sal l i g h 盯郴s tt ot l l e 晰o r 叠【c 吲吟t h e 豫f o 】哈e 蔬c t i v e l yp t c c t s t b e c l l r i 锣a b o l l t t h e i n f o m 俄i w h i c h 协i n 锄i t i n t h e 珊佃，o 出h 硒溉b c c 嘲e d l 黼觚d m o 旭i i i l p 叭协m 1 1 l i sa r t i c l es t u d i e st h eo b j e c to fr s a p a s s w o r ds y 咖i tb c d n g st ot t 圮a l g 鲥t h mo f p u b l i ck c y h lt l l i sa l g o r i t h m 的1 1 1 c 呻t i k e ya n da l g o r i t h mc 孤b ep u b l i s h e d ，姐dt l 把k e y o f d c c i p h e ri sp o s s e s s e db y 也ei n d i “d l l a lu 眦f r o l n 也ed a yt h a tb o 腓d 恤r s aa l g o 袖m b 嬲m i th a dt h e 础i l i t yo fl l i g l l l y c l l r i t y 觚db eo l ，e ：哺t c de a s i l yt h a tr e i v 蛆t h e 印p e r d l l i t ya t t e n t i o n 姐di tw 船u s e dw i d e s p 幅蒯a t 即m ，r s aa i g o m h mi si n v o l v e di n m 柚yc r y p t o g r a p l l i cs ) r s t 啪s b mi r h c e my e a 璐h 嬲m t l l ea b i l i t yo fa n a l y z e st h eg m a t i n t e g 盯t ob es 呦g t l l e n e dd a yb yd a y ，i no r d 盯t o 昏璃均m c c dt t i er s aa l 酬t h m s 叫r i t y a l w a y sh 鹪t oi n c r c a t h el e n g t ho fm o d i l l u s ，t h a tc a u st l l e 吼嘟叮p t i o na n dd e c i p h 盯 o p t 嬲t i o i lh a v et oc a l c l l l a t et l l cl a r g 胃n 岫b 盯a _ b o l l tt l l 时f h n c t i o no fm o d e la n dp o w t l l i s a l w a y s t l l eb o t n e c kq l l e s t i 他s 仃i c t si t s a p p l i c 砒i o nw h i c hp l o n g e s 也et i l n e o f e x e c m i o n ，姐1 e m f o t t l i s 弘i p 凹h 嬲m a d et h e r l 砒i o ni m p v 锄e n ti l it h e 锄p e c to fs p e e d a b o l i tt l l er s a a l g o f i m m a tf i r s to ft h i sa n i c l eh 鹊t h 邮吣g hc a 阳f h l l y s 坞h c dt l l ep r i n c i p l eo fr s a p a s s w o r d s y m 豇n ，t h a tb u i l d sm ef h v o m b l em t i o m l ef o fu l ei m p m w 髓e n to ft h ea l g o r i t h m ；n e x th 鹤 a n a l y z e dt h er s ap a s 副删s y s t e l n ss u r i t y ，d i s c u s d sm 锄ym e t h o d sa t 协c kt or s a ，鹤 w e u 勰h o wm a k e sc o r 陀s p o n d i n gp r o c e s s i n gi nt h ec o 柙e l a t i o na i g o r i t h mt 0 陀s i s tt 量】屺 抛c k s ；0 n c em o 把，t h i sa r t i c l et om a k cm ea 【l l a i l s t i v ea n a l y s i si ns e v e f a lf h c t o 塔w h i d h a 腩m e d 也es p e c do ft h ea i g o f 硫m 1 1 啪u g has e r i e st c s td 撒f o 岫dn l a ta f t 盯t h e i n l p 呦e n ti t ss l e c dh a sb 啪吼h a i l c e d 衄l y a c c o i 曲gt 0t h e 把s i l l to fa l l a l y ，i m p r o v e s n 把a l g o r i m mi l lt h 托e 蠲p c c t s ，t h a t i sr e c u r s i v es u 阳o fr e s i d u e s ，s y m m e 时o fm o d l l l o m i i l t i p l i c a t i 锄d 协et e s to f p l i i l 豫n 呦b e r i i 沈阳工业大学硕士学位论文 t h i sa n i c l ea l s op r o p o s e dt h et h o u g h to fp i 科把a 加舱mt a m e ，n 锄e l yt l l 砒w h 吼t i l e 龇缸i 傩w h i c h n e e d t o 锄唧a i lo f t h 舶眦e n g l i s h 蛳c 鼢p r 妣ea s h 瞅j l l 甜v 趾c c ，砌c hp l e s a l lt h e c r y p t o g 阻p h c s o ft l 圮p o s s i b l yl e t l 粥，t 1 1 i l if o l l o 丽唱 慨f o 胁a l i o nw h i c h 疳哪d e f i n i t eo r d e 培t oc r ) r p t o g r a p h ，y 帆c a nl o o k su pm ei i l | h m 蜥o n 丘d mt h et a b l et l l a ts a v en l ec a l c l l l a t et i m ee x 咖l e l y t h ep i 咀m 咖c n tt a b l ea l g o r i t l l ms a v e s t h et i n 把阳l 翻ew i 也h o wm 锄yd e 6 l l i t eo r d e r sn 地i n d e f i n i t ei n f 0 虹n a t i o nl l j w e ，m o d e f i l l i t e o r d e 培m o e rs a v e s l e 缸i n e k e y b r 凼：r s aa l g o r i t h m ，r e c u 瑙i v es u no fr 鹤i d u 瑚，s y m m 哪o fm o d u l o m u i t i p l i c a 缅，p i 峨嘲t m 蛐tt a b l e r i i 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：叁邋日期：鲨z ! ：z 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：j 啦导师签名：二、恤日期：j 竺z 二上l 沈阳工业大学硕士学位论文 1 绪论 1 1 密码学的产生与发展 自从人类有了战争，就有了密码，所以密码作为一种技术源远流长， 时代，而且还有过自己辉煌的经历，但成为一门学科则是近2 0 年的事， 科学蓬勃发展刺激的结果 可追朔到远古 这是受计算机 密码学是研究通信安全保密的科学，其目的是保护信息在信道上传输过程中不被他 人窃取、解读和利用，它主要包括密码编码学和密码分析学两个相互独立又相互促进的 分支【1 2 1 。前者研究将发送的信息( 明文) 变换成没有密钥不能解或很难解的密文的方 法；而后者则研究分析破译密码的方法，其发展经历了相当长的时期。 第一次世界大战之前，密码学的重要进展是不为人知的，很少有文献披露这方面的 信息嘲。直到1 9 1 8 年由w f 硒锄d 彻m 论述了重合指数及其在密码学中的应用以及转 轮机专利的发表，密码学才引起了人们的重视，但仅仅由军事和秘密部门所控制。 第一次世界大战之后到2 0 世纪4 0 年代末期，密码学家们将信息理论、密码学和数 学结合起来研究，使信息论成为研究密码编码学和密码分析学的重要理论基础1 4 j 。完全 处于秘密工作状态的研究机构开始在密码学方面取得根本性的进展，最具代表性的有 s h 锄( 香农) 的论文一保密系统的通信理论和通信的数学理论，他将安 全保密的研究引入了科学的轨道，从而创立了信息论的一个新学科【5 】。 从2 0 世纪5 0 年代初期到6 0 年代末期的2 0 年中，在密码学的研究方面公开发表的 论文极少，但d 删dk a b n 于1 9 6 7 年出版的著作破译者使密码学的研究涉及到 了相当广泛的领域，使不知道密码学的人了解了密码学，因此密码学的研究有了新的进 展嘲。 自2 0 世纪7 0 年代初期到现在，随着计算机科学与技术的发展，促进了密码学研究 的兴起和发展，人们使用密码技术来保护计算机系统中信息的安全。因此，在密码学的 研究和应用等方面取得了许多惊人的成果和理论。具有代表性的有： ( 1 ) 由d i 侬e 和h e l l 衄m 于1 9 7 6 年发表的“密码学的新方向”一文提出了公开密钥 密码学( 即公开密钥或双密钥体制) ，打破了长期沿用单密钥体制的束缚，提出了一种 i c s a 算法研究及速度改进 新的密码体制。公开密钥体制可使收、发信息的双方无须事先交换密钥就可秘密通信川。 ( 2 ) 由h o r s tf e s t a l 研究小组于2 0 世纪7 0 年代初着手研究美国数据加密标准( d g t a e n c r y p t i 帆s t a l l d a r d ，d e s ) ，并于1 9 7 3 年发表了“密码学与计算机保密”等有价值的论 文，该文论述了他们的研究成果并被美国标准局( n b s ) 采纳，于1 9 7 7 年正式公布实 施为美国数据加密标准并被简称为d e s 标准【8 】o 上述密码学的发展可粗略的划分为三个阶段：第一阶段( 1 9 4 9 年之前) 的密码学可 以说不是什么学科，仅为一门艺术；第二阶段( 1 9 4 9 年到1 9 7 5 年) 可以说是密码学研 究的“冬天”，成果和论文少且为单密钥体制，但在这一阶段有如s h 舭m 的理论和d 删d i l i n 的著作，为密码学奠定了坚实的理论基础；第三阶段( 1 9 7 6 年到现在) 可以说是 密码学研究的“春天”，密码学的各种理论和观点百花齐放，应用成果累累。 1 2 密码技术现状及发展方向 现在世界上的一些大国都非常重视密码学研究。在美国国家安全局( n s a ) 和国家 标准技术研究所( n i s t ) 的共同推动下，2 0 世纪7 0 年代以来陆续建立了国家数据加密 标准( d e s ) 和数字签名标准( d s s ) ，2 0 0 1 年又确定了高级加密标准算法( a e s ) 以 作为2 1 世纪的应用基础【9 】。美国政府为了适应信息社会发展的需要，加强政府司法机构 社会管理执法的高技术支撑能力和情报部门的对抗信息战的能力，正通过n i s t 提出并 推动着密钥托管、密钥恢复、证书授权认证、公开密钥基础设施、公开密钥管理基础设 施等一系列技术手段、技术标准和相关理论基础的研究。 国际上在分组密码和序列密码设计与分析方面的理论和技术已经比较成熟。除了算 法的设计之外，美国、欧洲、日本等发达国家在加密算法的标准化方面做了大量的工作。 我们国内的学者也设计了很多对称加密算法，但是目前的问题是，国内还没有一个统一 的加密标准。可喜的是，目前有关部门正在组织加密标准的讨论和征集。 目前比较流行的公钥密码体制主要有两类：一类是基于大整数因子分解问题的，其 中最典型的代表是r s a 体制：另一类是基于离散对数问题的，如e 1 g 锄a l 公钥密码体 制和影响比较大的椭圆曲线公钥密码体制【1 2 1 。由于分解大整数的能力日益增强，因此 为保证r s a 体制的安全性总是要增加模长。目前5 1 2 b i t 模长的r s a 体制已不安全，一 般建议使用1 0 2 4 b i t 模长，预计要保证2 0 年的安全性就要选择2 0 4 8 b i t 的模长，增大模 沈阳工业大学硕士学位论文 长带来了实现上的难度。而基于离散对数问题的公钥密码在目前技术下5 1 2 b i t 模长就能 够保证其安全性，特别是椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算 更困难，目前技术下只需要1 6 0 b “模长即可保证其安全性，适合于智能卡的实现， 因而受到国际上的广泛关注，并制定了椭圆曲线公钥密码标准瑾匝e p l 3 6 3 。 目前，公钥密码的重点研究方向为： ( 1 ) 用于设计公钥密码的新的数学模型和陷门单向函数的研究； ( 2 ) 针对实际应用环境的公钥密码的设计； ( 3 ) 公钥密码的快速实现研究，包括算法优化和程序优化、软件实现和硬件实现l ( 4 ) 公钥密码的安全性评估问题，特别是椭圆曲线公钥密码的安全性评估问题。 1 3 国内外研究动态 目前，国外在密码使用方面有以下几点：其一，美军的核心密仍是一次一密密码体 制，其它则以电子机内乱( 通过电子电路，以严格的程序进行逻辑运算，以少量的制乱 元素生产大量的加密乱数，因为其制乱是在加解密过程中完成的而不需预先制作，所以 称为电子机内乱密码) ，计算机密码( 计算机软件编程进行算法加密) 为主。从密码体 制上说，国外目前主要探讨：变态一次一密随机密码，一次一密伪随机密码，一次一密 近似伪随机密码以及公开密钥密码。其二，美俄等国以计算机为中心的对往返信息进行 快速保密处理的军队指挥自动化系统，亦即c 3 i 系统已实用化。西方电子支付系统也已 实用。国外目前正使用和研究各种类型的密钥管理体制，特别是密钥分配体制和签字， 鉴别方法其三，不少发达国家已逐步实现了办公室自动化，计算机网络化和通信网络 化，有关计算机网络和通信网络的保密安全性问题讨论较多。如：美国发明的一种基于 盘问与口令的计算机安全机制。盘问口令和应该回答的口令均为字母数字密码，存放在 二维或多维矩阵中，被访问的主机和请求访问的计算机或终端，存有相同的密码矩阵 在使用二维矩阵时，主机从矩阵中不同的行和列中，选出二个密码，发出盘问口令，请 求访问的计算机或终端，必须用由二个密码口令所确定矩形的另外两角上的密码口令回 答，访问才能成功。一组密码一旦已成功使用，即被去除，所以，非法用户仅通过重复 合法用户键入的密码是不可能进入系统的。如果要求更高的安全性，可使用高维的矩阵。 在规定的试探次数内，如没能回答出正确的口令，将自动地与系统切断，然后系统自动 3 一 l l s a 算法研究及速度改进 地从矩阵中选取一个新的密码组，盘问下一个请求者。其四，国外对不同的信息形态， 如文字、语音、图像、数据、真迹等进行了密码的编码和分析，就加密方式讲，除序列 加密外，在计算机密码和网络保密通信中还大量使用了分组加密方式，分组加密的优点 是不需要特殊同步措施，对组网非常方便。其五，从理论上讲，必须充分论证和解决各 种现代密码学问题的密度问题。所以，国外一直探讨和研究p 司心? 问题，就是说一种密 码是计算上保密的，或者理论上可破但实际上是保密的【1 3 】。 我国在密码学这一新兴领域的研究也逐渐开展起来，但是，无论是研究的规模，还 是研究的广度和深度，与国外相比都有很大的差距。随着我国国民经济和计算机技术的 发展，加强对这一领域的研究，已经是刻不容缓的事情了。 1 9 9 1 年，陶仁骥先生提出将( 4 4 ) 拉丁阵应用于基于有限自动机理论的序列 密码，并论证了其安全性【1 4 1 。 1 9 9 2 年，西安电子科技大学杨保宁等人提出一种新的模拟语音加密方案，根据s h 锄 姐保密通信理论，先去掉冗余信息，再加密，其保密度要高，伪信号的插入有效地掩盖 了原始语音中存在的间歇感和节奏感，成功地阻碍了窃听者对原始语音内容的听力理 解，由于解密时删除的非显著系数能量较小，对语音影响不大，恢复语音质量是完全可 以保证的i l ，j 。 1 9 9 3 年，郑州大学计算机科学系韩曙先生提出了一种基于任一逻辑基值的多值阵列 数据加密与解密系统。研究表明，这种加密系统具有较高的安全性【1 6 1 。 此之后的若干年，进入了中国密码学的春天，学术成果捷报频传。其中，2 0 0 4 年与 2 5 年是中国密码学界值得自豪的两年。一直在国际上广泛应用的两大密码算法凇5 、 s h a - l ，宣布被中国密码专家山东大学数学系王小云破解，一时间国际密码学领域风起 云涌。m d 5 与s 姒1 算法是目前国际电子签名及许多其他密码应用领域的关键技术，广 泛应用于金融、证券等电子商务领域。其中，s h a 1 算法早在1 9 9 4 年便为美国政府采纳， 目前广泛应用于美国政府的计算机密码系统。以往，专家们认为这两个算法固若金汤， 哪怕调用全球的计算机，花费上百年、上千年的时间，也难以破解这两个算法。但这一 切在2 0 0 4 年8 月之后改变了，中国人攻克了这两座堡垒( 埘 在当今科学技术飞速发展的时代，信息已成为推动社会向前发展的巨大资源。社会 4 沈阳工业大学硕士学位论文 机密和财富信息被高度集中存储在计算机的数据库中，并在与综合通信网相连的计算机 终端设备之间相互传送，因此，它们成了犯罪分子进行破坏活动的主要目标之一。如果 没有适当的安全保密措施，这些信息在传输过程中就易被截收，或在存储时被取出或复 制，造成信息泄露，产生隐患。另外，信息在存储和传输过程中还会遭受到非法删除、 篡改或增添的危险，从而导致对计算机资源及计算机服务的非法干预与使用。美国斯坦 福大学研究所的调查表明，计算机犯罪案的损失平均每起达4 5 万美元之多，是常规犯罪 案的几十倍到几百倍。全世界每年被人用计算机盗走的资金高达2 0 亿美元。因此，保护 计算机数据安全成为计算机科学技术领域的一个迫切问趔埔l 。 1 4 研究本课题的意义 r s a 算法是最为成功的非对称密码算法，其安全性高，易于理解和操作，因此受到 广泛的研究。算法的名字以发明者r o n 硒v e 吼，a d is h 扰l i r 和l f da d l 锄锄的名字 命名【埘。 r s a 体制是最具代表性的公开密钥编码体制，其基础是e u l 口定理，安全性依赖于 大数的因数分解的困难性【2 0 l 。r s a 体制的特点使得它成为公钥密码体制研究的- = 个标 准模板。同时，由于r s a 算法发展至今，在实现技术上已经相当成熟，因此本文算法 的实现在一些方面可以利用已有的技术，这对增强算法的实用性是非常有益的。 事物的本质是具有两面性的，尽管r s a 的算法的安全性得到了人们的认可，但是 算法计算复杂，实现的难度大，而且加密、解密操作要计算位数达十进制百位以上的模 幂乘函数，执行的时间长，这一直是制约其广泛应用的瓶颈问题，因此对r s a 算法速 度的改进将具有非常重要的现实意义 1 5 论文所做的工作 本课题具体研究内容如下： ( 1 ) 学习r s a 算法的基本原理。r s a 算法理论研究，包括r s a 算法的原理及组成， 对其主要函数模块一大素数的产生、密钥对的产生和r s a 消息处理分别做了详细地 研究，为算法的改善打下坚实的理论基础。 ( 2 ) 对r s a 算法安全性的分析。讨论了针对r s a 的各种攻击方法，以及如何在相 关算法中作相应处理以抵御这些攻击，分析了r s a 的安全性。 5 髂a 算法研究及速度改进 ( 3 ) 学习并研究递归余数和算法。研究表明算法的速度主要取决于被模数非零元素 的个数，非零元素越少，迭代步数越少，以此为据优化算法，以提高r s a 算法的速度。 ( 4 ) 学习并研究基于乘同余对称性快速算法。研究表明算法的速度主要取决于加密 指数的汉明重量，以此为据优化算法，以提高r s a 算法的速度。 ( 5 ) 深入研究大素数的产生及判定方法。将素数的陈氏生成法和m i l l 小r a b i l l 方法 有机的结合起来，以快速高质量的产生大素数。 ( 6 ) 提出一种全新的r s a 加解密方法一预处理表。当要加密的信息均为英文时， 产生预处理表，即把所有可能出现的明文所对应的密文预先计算出来，存放于处理表中， 这样在后续明文到密文的转化过程中，无需逐个计算，查表即可。 沈阳工业大学硕士学位论文 2r s a 密码体制 r s a 公钥密码体制是由麻省理工学院的r 册砌v e 鞋，a d is h 雒l i r 和l r da d l e 啪n 于1 9 7 6 年提出，1 9 7 8 年正式发表的一种可将加密密钥公开的密码体制。r s a 密码体制 从提出到现在经受住了多年深入的密码分析的考验，已逐步走向成熟，被越来越多的人 所接受，它是目前世界上唯一被广泛使用的公开密钥密码体制胆。公开密钥密码体制的 加解密过程如图2 1 所示。 信源a i 密钥对产生源i 信源b 加密密钥时l 解密密钥k s r li 明文x 一e 加密算法 - jl 一d 解密算法卜+ 明文x f l f j lf 加密密钥k p 密文 解密密钥k s v = e f x 、 图2 1 公开密钥体制的加密解密过程 f i g 2 1t l - cp 崩瑚so f 棚，p 村o rd i p l 耐n ga b o wp u b l 沁- k c yc r y i i o 目r a p h ya l g 硎岫 2 1r s a 算法描述 r s a 算法是基于单向函数的，所以首先介绍单向函数的概念。 如果对一个函数在定义域上的任意一个x 容易计算出舣) 的值，但对值域f 上的任 意一个y ，f 1 在计算上是不可行的，就称是单向函数嘲 单向函数是密码学中的一项重要的研究内容，在现实中，存在许多函数被认为是单 向的( 即具有单向函数的性质) 。这里给出一个可信程度很高的单向函数的例子：假设 n 是两个大素数p 和q 的乘积，分解n 被认为是一个非常困难的问题。并设b 是一个正 整数，定义函数f z n z n ，舣) ：= x 。m o dn ，则f 被认为是一个单向函数。当知道了n 的因 骼a 算法研究及速度改进 子是p 或q 时，计算逆是容易的，因而是陷门单向函数。 r s a 算法正是利用了陷门单向函数的一种可逆模指数运算，它的安全性是基于大整 数因子分解的困难性。下面给出r s a 的算法描述： s t e p l 密钥的产生： ( 1 ) 选择两个大素数p 和q ( 2 ) 计算n = 节x q 和西( n 产0 - 1 ) ( q 1 ) ； ( 3 ) 选择一个加密密钥e ，要满足( n ) ，且g c d ( e ，m ( n ) ) = l ： ( 4 ) 解密密钥d 要满足o 划锄( n ) ，且d e = l ( m o dm ( n ) ) ； ( 5 ) 得出所需要的公开密钥和秘密密钥： 公开密钥k p = e ，n 秘密密钥k s = d 脚 在上述步骤中，p 、q 和西( n ) 是不公开的【2 3 1 。 s 犍p 2 加解密算法 若用x 表示明文，用y 表示密文( x 和y 均小于n ) ，则加密和解密运算为： 加密：y = e 酝) = x 。( m d dn ) 解密：x - d 如) = 一( m o dn ) 踟 r s a 算法安全性的理论基础是大数的因子分解问题至今没有很好的算法，因而公开 e 和n 不易求出p 、q 及d 。为保证安全性，r s a 算法要求p 和q 是两个足够大的素数( 通 常是1 0 0 位以上的十进制数) 。 可以证明加密变换e k 为解密变换d k 的逆嘲 定理2 1 ( e u l e r 定理) 对任意a ，若g c d ( a n 户1 ，则有产) 兰l 瑚d n 。 定理2 2 设p 和q 是两个不同的素数，n = p 。q ，m ( n ) = 0 卜1 ) ( q 1 ) ，对任意的x z n 及任意的非负整数k ，有x k 帅卜1 ；xm o dn 。 由以上两个定理可推出对任意的x z i i ，d k ( e “x ) ) ：= x 。因为d 瞄lm o d 似n ) ，故可 设d e = t m ( n 卜l ，t 为整数且仑l 。对任意x z n ，有： 蹦e “x ) ) 兰d 心) 兰( 灼蝗x + 似咿1 三x 瑚dn( 2 1 ) 沈阳工业大学硕士学位论文 为了建立r s a 密码系统，用户a 需完成以下各步骤： ( 1 ) 用户a 产生两个大素数p 和q ； ( 2 ) a 计算n 印q 和帅户睁1 ) x ( q 1 ) ( 3 ) 选择一个随机数e ( o e 中( n ) ) ，使得g o d ( e ，m ( n ) 产l ； ( 4 ) a 使用扩展e u c l i d e 觚算法计算d = 一m o dm ( 1 1 ) ； ( 5 ) a 将n 和e 作为它的公钥直接公开。 2 2 素性检测 在r s a 算法中，需要产生两个大素数。素数在密码理论中占有极重要的地位，但 是关于一个整数是否为素数的判别却一直是个难点。判断一个整数是否为素数的最简 单、最直观的办法是用试除法，用小于n 的平方根以下的所有素数去除n ，若都除不尽， 则n 就是素数，否则为合数。这对于比较小的数来说还适用，若用计算机编成程序，对 于l o 位十进制数，几乎瞬间即可完成，对于一个2 0 位十进制数，则需要2 个小时，对 于一个5 0 位十进制数就需要一百亿年，令人吃惊的是，要检验一个一百位十进制数， 需要的时间就猛增到1 0 3 6 年嘲。 r s a 算法产生的素数通常是一百位左右的十进制数，用试除法判别素性显然是不现 实的，通常采用索性检测的方法来判别。 素性检测的方法可分为以下两类：确定性素数算法和概率性素数算法【2 刀。判定一个 数是素数比较难，而否定它是素数要容易得多。因此概率性素数算法研究得较多，是当 今判别大素数的主要算法，其算法较著名的主要有s o l o y - s n a s n 算法和m i l l 盱r a b i n 算法。 2 2 1s o i o v a r s t r a s s e n 素数测试算法 设n 是一个正奇数，则： s t 印l 选择一个随机整数a ，i s a 如1 ： s t e p 2 计算g c d ) ； s t 印3 若g c d ( a ，n 游l ，则n 非素数； s t c p4 计算( a n ) 及a ”“2m o dn ； 9 骶a 算法研究及速度改进 s t e l ) 5 若( 咖) 兰a “7 2 m o dn ，则n 可能是素数，否则n 是合数圆。 这个算法的正确性至少1 2 ，出错的概率小l ，2 ，若随机均匀地产生序列a i 加a k ， 都通过此判定法判定为是素数，那么n 为合数的概率小于( 1 ，2 ) k ，当k 充分大时，( 1 ，2 ) 。 是很小的数，则n 为素数的可信度很高。 2 2 2m i i e r 髓b i n 素数测试算法 定义2 1 令n - 1 = 2 。m ，其中l 是非负整数，m 是正奇数，若存在正整数a ，使得 水l ( m o dn ) 或对某个非负整数t ( o g 1 ) ，满足a 2 “；l ( m o dn ) ，则称n 关于a 通过m i l l e r 检测。 定理2 3 ( 费尔马定理) 若p 是素数，则对于任意的整数a ，应有矿1 z l ( m o dp ) 。 费尔马定理给出素数p 的必要条件，若不满足，则可断定它不是素数。 定理2 4 若n 是素数b 是整数，且n 能除尽b ，则n 必通过以b 为基的m i l l 盯r a b m 测试。 定理2 5 若n 是奇合数，则n 通过以b 为基的m i l l e r 蛐测试的数目最多为l 4 ， o 妇1 1 例。 由定理2 5 可知，随机选取a ，若n 关予a 通过m i l l e r 检测，则n 不是素数的可能 性为l ，4 ，若对于k 个随机选取的a ，n 关于它们都通过m m 盯检测，n 为合数的概率不 超过( 1 4 铲。 概率性素数算法的缺点在于它不能证明该数是素数，而只能证明该数很可能是素 数。也就是说，产生的数只是伪素数，为合数的可能性很小，但这种可能性依然存在。 它的优点在于使用概率性素数算法，产生伪素数速度较快，构造的伪素数无规律性。 2 3 随机数的产生 在加密用于各种网络安全应用的过程中随机数扮演着重要的角色。许多基于密码编 码学的网络安全算法都用到随机数，例如在相互鉴别方案中、会话密钥的产生中，在 r s a 算法中的密钥产生也要用到随机数。 真正的随机数序列必须满足以下几个要求：随机程度和不可预测程度以及不能重复 产生i 姗。所谓随机程度，是指通常在产生一系列声称是随机的数值时，人们关心的是这 1 0 沈阳工业大学硕士学位论文 一系列的数值在某种统计意义上是随机的。一系列数值是否是随机的通常用下面的两个 准则来验证： ( 1 ) 均匀分布：这一系列数值的分布应该是均匀的。也就是说，每个数出现的频率 相等。 c 2 ) 独立性：系列中的任意一个数都无法从其他数推测得到。虽然在确定一系列的 数值服从一种特定的分布( 比如均匀分布) 方面有着明确的测试方法，但是却没有测试 方法可以“证明”独立性。另一方面，有许多测试方法可以用来证明一个序列没有独立 性。通常的策略是进行一系列测试，一直到我们对于独立性成立的信任己足够强。 所谓不可预测程度，是要求序列各个后续的数是不可预测的。对于“真正的”随机 序列，每个数与其它数都是统计独立的，因此是不可预测的。然而，我们几乎很少使用 真正的随机数：相反地，看似随机的数值序列是由某种算法产生的。在这种情形下，必 须保证攻击者从序列前边的元素无法预测出将来的元素。 所谓不能重复产生是指如果你用完全同样的输入( 尽量排除外界干扰影响) 对序列 产生器操作两次，你将得到两个不相关的随机序列。 真正的随机数的来源难以得到。物理的噪声发生器是一个可能的来源，然而这些设 备在网络安全应用中不可能得到利用。另一种方法是找到已经发表的高质量的随机数； 然而这些随机数的数量不能满足一个有相当规模的网络安全应用的需要。另外，这样的 数虽然确实有者统计上的随机性，它们却是可以预测的，因此在不可预测性方面不能满 足要求。 因而密码编码应用通常使用算法技术来产生随机数。这些算法是确定性的，因此产 生的数值序列并不是统计随机的。然而，如果算法很好，所得的序列就可以通过许多随 机性的合理测试，这些数经常被称为伪随机数 到目前为止，使用得最广泛的伪随机数产生技术是由l c h m 盱首先提出的一个算法， 这个算法称为线性同余方法f 3 。该算法有四个参数，分别是： m a c 模数 乘数 增量 n 1 ) o 0 = g q n 0 = 董c k m r s a 算法研究及速度改进 x o初始值或种子畦 l 的最小的正整数u 。 如果 c 辜c ( m o dp )( 2 7 ) 那么，g c d ( c 7 - c ，n 声p 。类似地，如果 醛a 算法研究及速度改进 c ，兰c ( m o dq ) 那么，g c d ( c ，c ，n 户q 。无论上述哪种情况，n 可被分解，从而敌手可破译该系统