基于modelsim的rsa加密算法的研究.doc

理工大学毕业设计（论文）成绩评定学生姓名： 专业： 学号： 题目： 毕业设计（论文）答辩委员会（小组）评语：答辩评分: 答辩委员会主任（组长）（签字）： 年 月 日毕业设计（论文）成绩：指导教师评分( %)审阅评分( %)答辩评分( %)毕业设计（论文）成绩： （分）毕业设计（论文）总评成绩（等级）： 答辩委员会主任（签字）： 年 月 日毕业设计（论文）评语指导教师评语：指导教师评分： 指导教师（签字）： 年 月 日评阅人评语：评阅人评分： 评阅人（签字） ： 年 月 日学生毕业设计档案学 生 姓 名学 院信息科学与工程学院学 号指导教师姓名职 称讲师所在单位毕业设计题目基于modelsim的RSA加密算法的研究毕业设计（论文）完成情况毕业设计各阶段名称起止日期完成情况（存在问题及整改意见）阶段成绩*毕业设计（论文）开题，完成文献综述及外文文献翻译熟悉Verilog语言，研究公钥密码体制基本理论，掌握RSA密码算法原理及关键技术采用Verilog语言实现512位RSA加密算法，系统包括预处理模块、模幂计算模块、控制模块等使用modelsim软件进行仿真、测试验证并得出结论完善系统，撰写毕业论文13周46周710周1113周1416周指导教师意见（根据学生出勤及毕业设计（论文）完成情况，指导教师是否同意该学生参加答辩）指导教师（签名）： 年 月 日*注：阶段成绩分A、B、C三级：A为全面完成任务、B为完成任务、C为完成任务不好毕业设计（论文）任务书学 院信息科学与工程学院专 业通信工程学 生 姓 名学 号设计（论文）题目基于modelsim的RSA加密算法的研究内容及要求：RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。本设计主要功能及具体要求如下：1、研究RSA加密算法的基本理论，掌握RSA加密算法原理及关键技术。2、采用Verilog语言实现实现512位RSA加密算法，设计工作包括包括预处理模块、模幂计算模块、控制模块等。3、 使用modelsim软件进行仿真，并对结果进行分析。进度安排：13周：毕业设计（论文）开题，完成文献综述及外文文献翻译；46周：熟悉Verilog语言，研究公钥密码体制基本理论，掌握RSA密码算法原理及关键技术；710周：采用Verilog语言实现512位RSA加密算法，系统包括预处理模块、模幂计算模块、控制模块等；1113周：使用modelsim软件进行仿真、测试验证并得出结论；1416周：完善系统，撰写毕业论文；指导教师（签字）：年 月 日学院院长（签字）：年 月 日摘 要自20世纪90年代以来，计算机网络技术使得计算机应用得到进一步普及和发展，其应用几乎已深入到人类社会活动和生活的一切领域，但是如何保证信息的安全却是一个十分重要的问题。根据各种安全技术和应用的需求，人们提出了许多加密的算法。RSA算法被公认为是最优秀的密码体制之一，在广泛的应用过程中，它的安全性和性能不断得到人们的肯定，从而成为最流行的密码体制之一。可以用来进行数字签名和身份验证。 本文介绍了密码学的基本概念，包括数论的基础知识和模运算的概念。分析了RSA密码体制原理，剖析了RSA加解密过程中要用到的算法，重点介绍了改进的基为2的蒙哥马利模乘算法。对整个RSA系统的结构，采用verilog语言对其进行了设计和划分，并按照划分的子模，设计了数据通径模块和系统控制模块等子模块，而后使用modelsim软件实现。关键词:密码学，RSA加密算法，verilog语言，modelsimThe RSA encryption algorithm research based on modelsimAbstractComputer network technology, whose application has gone deep into almost every field of human life and social activity, has bee further popularized and developed since 1990s, but it is a very important question to guarantee information security. Various encryption algorithms have been presented to meet different security technology and application needs. RSA, whose security and property has been affirmed continually in its widespread application, is generally established as an excellent cryptosystem. RSA has become the most popular cryptosystem.it is often used in digital signature and identification system. In this thesis, the basic concepts of cryptogram including number theory and modular arithmetic are introduced. It is the base of knowing the RSA cryptosystem well. RSA system principle and some algorithm used in the encrypt and decrypt process are analyzed, especially radix-2 modified Montgomery modular multiplication algorithm. The full system' s design and partition is achieved. The modules of prepared implementation, exponentiation computation system and system controller etc. have been detailed based on system partition.Key Words: cryptology, RSA eryptographie algorithm, verilog language，modelsim 目 录第一章 绪 论11.1 课题背景和意义11.1.1课题背景11.1.2课题的研究意义11.2国内外研究现状21.3 论文的篇章结构3第二章 RSA公钥加密系统的基本原理52.1 RSA数学基础52.1.1 单向函数52.1.2 因子的概念52.1.3 公约数与最大公约数62.1.4 互质数62.1.5 欧拉定理62.2 素数的产生72.3 RSA加密算法82.3.1 RSA加密算法的公钥对（及私钥）对产生步骤82.3.2RSA加密算法加解密过程82.3.3证明加密算法的正确性92.4RSA加密算法在通信网络中的应用102.4.1 信息交换102.4.2数字签名112.5RSA加密算法的安全性11第三章 512位RSA加密算法的设计123.1 大数运算123.2 模乘运算143.3蒙哥马利模乘算法143.3.1原始蒙哥马利模乘算法143.3.2 一种改进的蒙哥马利模乘算法153.3.3 基于从左到右扫描法的蒙哥马利算法16第四章 基于VERILOG语言的512位RSA加密模块的设计184.1 RSA系统总体框架184.1.1 RSA系统外部管脚示意图184.1.2 RSA系统结构框图194.2 系统各模块设计204.2.1 数据通经模块204.2.2 控制模块设计23第五章 基于MODELSIM的RSA加密算法的仿真255.1 仿真工具软件介绍255.1.1Synopsys的VCS265.1.2modelsim软件介绍265.2CONTROL模块关键部分代码及其数据流图:275.3 DATAPATH模块源代码及其数据流图:325.4 RSA总体模块及其数据流图：345.4.1 RSA模块源代码:345.4.2 RSA_tb模块源代码:355.5 测试验证37结 论41参考文献42致 谢44附录A 英文原文45附录B 汉语翻译52第一章 绪 论1.1 课题背景和意义 1.1.1 课题背景 自20世纪90年代以来，计算机网络技术使得计算机应用得到进一步普及和发展，并在全球得以迅猛发展和延伸，成为当代发展最为迅猛的科学技术，其应用几乎已深入到人类社会活动和生活的一切领域。但在计算机给人们的生活和工作带来极大方便的同时也带来了许多待解决的问题，大量敏感信息如何保护成为一个主要的问题。一个安全、健壮的信息系统离不开各种信息安全技术的支持。计算机网络中所采用的核心安全技术都是由密码学派生出来的技术与应用，可以说现代密码学的研究和发展是计算机技术尤其是网络安全技术发展的重要保障。根据各种安全技术和应用的需求，人们提出了许多密码的算法，在广泛的应用中，一些优秀的密码体系的性能和安全性不断得到证实和加强。但是，随着计算机运算能力的提高以及分布式计算的发展，各种密码系统的安全性都受到了不同程度的威胁。有些密码系统已经被破解，例如DES(Data Encryption Standard)密码体制。另外许多著名的密码体制也岌岌可危，例如经典的RSA公钥密码体制。RSA算法曾被公认为是最优秀的密码体制之一，它由R. L. Rivest, A. Shamir和L. Adleman于1977年提出，在广泛的应用它的安全性和性能不断得到人们的肯定，从而成为最流行的密码体制。但在1999年8月，一个155位(512bit)的RSA模数被成功分解，以及还有更早被攻破的RSA-129(1994年)和RSA-130(1996年)。为此，人们提出了许多新的方案和算法以替代和加强现有的密码体系，量子密码以及混沌密码的提出更是给现代密码学注入了新的血液。但在现有的情况下，RSA密码体系仍被认为是不可破解的密码体系，但这是以增加秘钥的长度为代价，不可避免地增加了运算的时间，因此，找到一个快速的RSA的实现算法也是当前密码学的一个研究方向。1.1.2 课题的研究意义 近几年计算机和通信网络飞速发展，网络的作用越来越大，人们利用网络进行快捷、方便地交换信息，使人们足不出户就能了解世界，认识世界，使人与人之间的距离变得越来越短，使远在天边的人们变得近在咫尺，以至于人们把地球称为地球村。人们通过网络谈论个人私事、或传递商务信息、或下达军事和政府指令。它在方便人们生活的同时，也极大地提高工作效率。 不过地球村还没有处在理想社会，国家间仍然存在着政治、军事和经济斗争;企业间仍然存在着技术和商业利益竞争;人与人之间存在着个人隐私。如果通过网络以明文方式传送不希望第三方知道的敏感信息，无论是通过无线还是有线传输，所传送的敏感信息很容易被第三方窃听。若把在公共信道上传送的信息以密文的方式传输，使窃听者难以获得有用信息，则可达到安全通信的目的。对于保护由地面通信线路、通信卫星和微波设备组成的通信网络中所传的信息，密码技术是唯一己知的实用方法。众所周知，在现在以及将来，信息安全将在计算机和通信系统中起着重要作用。信息安全涉及法律、管理和技术等方面，本文仅讨论技术问题。从技术的角度讲，密码技术是使信息系统达到安全的核心手段。信息数据加密既可用硬件来实现，也可以通过软件来完成一一虽然软件加密己经变得比较流行，但是硬件加密仍是商业和军事用途的主要选择，采用硬件的好处:第一是速度，许多加密算法采用软件实现是无效率可言的，如DES, RSA等，需要用专门的硬件来加以实现;第二是安全性，对运行在没有物理保护的一般的计算机上的某个加密算法，敌对方可以用各种跟踪工具修改算法而不让其他人知道。硬件加密设备可以安全地封装起来，可以避免对关键信息的任何非法访问。 密码体制分公钥体制与私钥体制，公钥体制可用于密钥管理和数字签名，但速度较低;私钥体制既不利于密钥管理也不利于数字签名，但速度高，因此，目前的密码系统大多采用混合密码体系，即用公钥体制实现密钥管理和数字签名(都是短信息)，用私钥体制实现大量文本的加解密。由于RSA既可用于密钥传递又可用于数字签名，并且RSA的密码芯片在有线电话、便携式电脑设备、HTML、移动电话、传真、FFP服务器、传呼机、E-mail, WEB服务器等方面都有着广泛的用途。制成灵巧卡则可用于电话付费卡、信用卡、交通卡、保健卡等。因而研究RSA加密算法有着重要的现实意义。1.2 国内外研究现状RSA算法是非常有前途的公钥密码体制，但其运算复杂度高，在实现RSA密码算法时，可以通过软件和硬件方式实现。软件实现公钥密码体制因速度低或对处理器的运算能力要求过高而不能很好的对数据进行实时处理。硬件实现较软件实现方式有运算速度快、安全性高、兼容性好等优点。RSA密码算法的软件实现方法很多在此不做论述，下面主要就其硬件实现方法谈一下国内外研究现状。目前RSA密码算法硬件实现的主要问题在于速度和芯片资源(面积)，这也是研究RSA密码芯片要综合考虑的两个指标。模幂运算是RSA密码算法的核心运算，其耗时多是影响速度的主要因素，因此采用蒙哥马利构造模乘算法和L-R扫描模幂算法来实现RSA,经优化后速度可有一定的提升:采用矩形乘法器从硬件算法结构上降低大整数乘两次迭代之间的数据相关代价，从而可以成倍提高RSA专用乘法器时钟频率，引入中国剩余定理(CRT) ,提高模幂乘并行度:滑动窗口取幂法的思想通过预处理来提高运算速度:利用流水线并行设计技术，提高数据路径的吞吐率和系统的运行速度:在算法实现过程中，充分利用资源复用和分时共享技术，有效减少资源占用。信息安全是利用密码技术来保证信息的保密性、完整性、可用性和抗抵赖性。密码技术，特别是公钥密码技术RSA算法的芯片实现，代表着一个国家在信息安全领域的水平。为此，各个国家都投入了大量的人力、物力进行这方面的研究。目前，国际上美国、加拿大和欧洲一些国家的公钥密码算法芯片处十领先地位，世界上最先进的RSA密码算法芯片1024位RSA运算速度可以达到每秒几千次以上。根据信息产业部电子科技情报研究所提供信息，国内北京天一集成科技有限公司开发的“高速RSA密码算法芯片”基于0.25um芯片加工工艺进行设计，1024位RSA运算速度为2000次/秒:上海中芯国际集成电路有限公司研制的THURSA-1024高速安全芯片基于0. 18 u m CMOS工艺设计，可完成1024位RSA签名6900次/秒:美国Cavium NetworksCN1010芯片1024位运算速度为7000次/秒;IBM日本公司1024位RSA加密芯片运算速度为4761次/秒。 1.3 论文的篇章结构 论文内容分为六章。第一章绪论，该部分主要介绍了选题的意义和课题的国内外研究现状；第二章为RSA体制的基本原理和基本概念；第三章是本文的重点章节，介绍了RSA加密算法改进算法;第四章是基于verilog语言的基础上，完成对的512位RSA加密模块的设计；第五章是基于第四章完成对RSA加密算法的编译，使用modelsim软件进行仿真;最后一章是结论。第二章 RSA公钥加密系统的基本原理2.1 RSA数学基础 同大多数公钥密码体制一样，RSA的安全性主要取决于构造其加密算法的数学函数的求逆的困难性，我们称这样的函数为单向函数。单向函数在密码学中起一个中心作用。它对公钥密码体制的构造是非常重要的。单向函数的研究是公钥密码体制理论中的一个重要课题。但是，虽然很多函数(包括RSA算法的加密函数)被认为或被相信是单向的，但目前还没有一个函数能被证明是单向的。下面我们介绍一下单向函数的基础知识。2.1.1 单向函数 定义1:令函数是集合A到集合B的映射。若对任意x x，xA，有f(x)f(x)，则称f为1-1映射，或可逆函数。定义2:一个可逆函数f，若它满足: (1)对所有x，易于计算f(x) 。(2)对“几乎所有的”x，由f(x)求x“极为困难”，以至于实际上不可能做到，则称f为单向函数。 上面定义中的“极为困难”是相对于现有的计算机运算能力和算法而言的。单向函数是贯穿整个公钥密码体制的一个核心概念。2.1.2 因子的概念 一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号d|a，意味着对某个整数k，有a=k*d。 0可被每个整数整除。如果a>0且d>a则d<=|a|。如果d|a，则我们也可以说a是d的倍数。 如果d|a并且d>0，则我们说d是a的约数。一个整数的约数最小为1，最大为|a|。例如，24的约数有1, 2, 3, 4, 6, 8, 12和240 每个整数a都可以被其平凡约数1和a整除。a的非平凡约数也称为a的因子。例如:20的因子有2,4,5和l0。2.1.3 公约数与最大公约数 如果d是a的约数并且也是b的约数，则d是a与b的公约数。例如，24与30的公约数为1, 2, 3和6。1是任意两个整数的公约数。两个不同时为0的整数a与b的最大公约数表示成gcd(a,b)。例如，gcd(24,30)=6, gcd(5,7)=1, gcd(0,9)=9。如果a与b不同时为0，则gcd(a, b)是一个在1与min(|a|,|b|)之间的整数。我们定义gcd(0,0)=0。下列性质就是gcd函数的基本性质:1.对任意整数a与b，如果d|a并且d|b，则d|gcd(a, b)。2.对所有整数a和b以及任意非负整数n，gcd(a*n, b*n)=n*gcd(a,b)。3.对所有正整数n, a和b，如果n|a*b并且gcd(a,n)=1，则n|b。2.1.4 互质数 如果两个整数a与b仅有公因数1，即如果gcd(a, b)=1，则a与b称为互质数。例如，8和15是互质数，因为8的约数为1, 2, 4, 8，而15的约数为1, 3, 5, 15。 对任意整数a, b和p，如果gcd(a, p)=1且gcd(b, p)=1，则gcd(ab,p)=1。这说明如果两个整数中每一个数都与一个整数P互为质数，则它们的积与P互为质数。 如果两个正整数都分别表示为素数的乘积，则很容易确定它们的最大公约数。例如:300=2*3*5; 18=2*3;gcd(18, 300)=2*3*5= 6。 确定一个大数的素数因子是不容易的，实践中通常采用Euclidean和扩展的Euclidean算法来寻找最大公约数和各自的乘法逆元。 对于整数n,n,n，如果对任何不同的i,j都有gcd(n, n)=1，则说整数n,n,，n两两互质。2.1.5 欧拉定理 RSA的基础是数论的欧拉定理。欧拉定理:若整数a和n互素，则a 1 mod n (2.1)其中(n)是比n小但与n互素的正整数个数。推论(Fermat):若p是素数，(a, p) =1，则a 1 mod p (2.2)2.2 素数的产生素数是指这样一种正整数：除了1与本身之外，其它任何正整数都不能整除它。那么，对于RSA加密算法而言，素数到底有多少？是否足够我们用来使用RSA加密算法？为了证明这个问题，不妨设世界上仅有有限个素数p,p,p,p，对于正整数N = p* p* p* p.如果将左边的N分解成素数乘积的话，不可能包含任何素数p，因此它的分解式中必定含有这些p之外的新素数。这就和我们的假设矛盾了。所以素数是无限的。综上所述，可以断言：(1) 对人类使用RSA而言是取之不尽，用之不竭的;(2) 没有人能够建立所有素数的数据库来破译RSA算法。而它在所有正整数的地位中，就好比在无限的宇宙中，所存在的行星。比例十分小，若用F(x)表示素数，x表示正整数。当xà0时，F(x)/x值近乎为0.虽然素数在所有正整数占的比例很小。但它的构造并非无章可循。目前构造素数的方法很多。下面重点介绍两种素数的方法：梅森数列，欧拉素数构造法。梅森数列： M = 2-1, p = 2,3,5 (2.3)这里p依次取遍所有的素数。人们也曾猜想梅森数都是素数。比如前几项分别是3,7,31,127都是素数。但是M=23*89不是素数。一个有趣的结论断言：如果素数p被4除余数为3，并且2+1也是素数，那么M必定不是素数。欧拉素数构造法： n n + p (2.4)这里p是素数，使得当n从0开始直至某一个N为止逐一代入时，上述多项式取值始终为素数。RSA所使用的素数一般是经过测试得到的，这些数只有可控制的小概率不是素数。关于素数的测试方法，文献3有比较详细的介绍，下面介绍其中一种测试方法-莱曼测试法：1982年莱曼提出了一种测试算法。(1) 选择一个小于p的随机数a;(2) 计算j = a mod p; (2.5) (3) 如算j 1或-1 mod p,那么p肯定不是素数; (4) 如算j = 1或-1 mod p，那么p不是素数的可能性至多是50%。 数a被称为一个证据，如果P是合数，随机数a是P的证据的概率不小于50%。 对a选择t个不同的随机值，重复t次这种测试，如果计算结果等于1或-1，但不恒等于1，那么P可能是素数所冒的错误风险不超过1/2。2.3 RSA加密算法2.3.1 RSA加密算法的公钥对（及私钥）对产生步骤1.取两个素数p和q(保密)。2.计算n=pq(公开)，(n)=(p-1) (q-1)(保密)。 (2.6)3.随机选取整数e，满足gcd (e, (n) =1(公开)。 (2.7)4.计算d，满足de1 (mod (n)(保密)。 (2.8)那么，公钥对即：（e,n）。私钥对即：（d,n）。2.3.2 RSA加密算法加解密过程利用RSA加密第一步需将明文数字化，并取长度小于log(n)/ log(2)位的数字作明文块。加密算法: c=E(m)=m(mod n) (2.9)解密算法: m=D(c)=c(mod n) (2.10)式中，m是明文，c是密文，e是加密指数，(e, n)对是公钥，d是解密指数，(d, n)对是私钥。2.3.3 证明加密算法的正确性证明:设de=k(n) +1，对于任何k及任何m (<n) ,恒有 m (mod n)m mod n若(m, n)=1，则由欧拉定理可知m (mod n)1 mod n，若(m, n) > 1，由于n=p*q，故(m, n)必含p，q之一。设(m, n) =p，或m=bp, 1 b p,由欧拉定理 m 1 mod q因此，对任何k，总有 m 1 mod q m 1 mod q即m 1 mod q或1=m+hq其中h某个整数。由假定m=bp所以m mod n = m (mod n)+hbpq(mod n)这就证明了m = m mod n。例：取p=43，q=59。计算：n = pq=43*57=2539，(n)=(p-1)(q-1)=2436取e = 17，gcd(13,2436)=1,由de 1 mod (n),求出d。解： 2436=13*187+5 à 13=5*2+3 à 5=3+2 à 3=2+1 1=3-2 à 1=3-(5-3) à 1=3*2-5=(13-5*2)*2-5=13-5*5 à1=13*2-(2436-13*187)*5 à 1=13*937-2436*5 d=937 于是公开(e, n)=(13, 2537)，保密d=937和p=43, q=59,设明文m=50，加密是计算: c=E(m)=m mod n = 50 mod 2539 =437 m=D(m)=c mod n = 437 mod 2539 = 50若有明文：public key encryptions先分块：pu bl ic ke ye nc ry pt io ns利用英文字母表顺序：即a为00，b为01，将明文数字化得：1520 0111 0802 1004 2404 1302 1724 1519 0814 1418利用加密得密文：0095 1648 1410 1299 1365 1379 2333 2132 1751 1289其加解密流程图如图所示:发送人明文加密系统密文解密系统明文接收人 图2.1 加解密流程图2.4 RSA加密算法在通信网络中的应用RSA加密算法在通信网络中的应用是比较广泛的下面主要介绍在通信网络中两种重要应用：信息交换、数字签名。2.4.1 信息交换这里通过一个例子来说明用户之间用RSA来秘密通信，所采用的简单协议仅是为了说明问题，在实用系统中为了安全，所采用的协议要复杂的多。假定每一用户的公钥(e, n)都列在黄页上，用户A要给用户B发送信息，执行下列步骤，就可以实现从用户A到用户B的信息传输。1.像查电话号码那样，用户A从黄页上查到用户B的公钥(e,n) ;2.用户A计算c=m mod n;3.用户A通过通信网络把密文c发送给用户B;4.用户B接收密文c;5.用户B用自己的私钥计算m=c mod n;2.4.2 数字签名在传统世界里，人们用手写签名来证明一个文件出自某人，或是经过他同意的。在数字化世界里，则需要数字签名和验证来取代手写签名功能，RSA就提供了这种数字签名和验证机制，下面以用户A通过网络从银行的帐户上支取10000元钱来说明如何通过RSA来实现这一功能，具体做法是: 1.用户A对数字帐单m用自己的私钥(d,n)进行加密，即计算s= m mod n; 2.用户A把数字帐单m和数字签名s发送给银行。银行按下列步骤验证用户A的数字帐单m和数字签名s; 1.银行接收m和s，从黄页上查到用户A的公钥(e,n) ; 2.银行计算m=s mod n; 3.如果m=m则完成签名认证，给用户A 10000元钱。否则，不是数字帐单m就是数字鉴名s被修改，签名无效。 因为A的私钥(d,n)只有A才拥有，是唯一的，因此，A在以后不能否认他支取10000元钱，银行也不能诬赖A支取了20000元。2.5 RSA加密算法的安全性 借助着马克思主义哲学的可知论原理，我们可以了解到世界上没有一种加密算法是不可破译的。对于一种加密算法的安全性的衡量，一般是以这样一种标准来进行判断：如果所加密的信息的价值低于对于所需要破译加密算法的成本。那么就称这种加密算法是安全的。 而RSA加密算法是一种公钥加密、私钥解密（或私钥加密、公钥解密）的加密系统。一般情况下，公钥对是对外公开的。私钥是保密的。一旦私钥对中d的值被破解了。这对密钥就失去安全性了。而解出d值，在已知e的情况下，还需要求出(n)（这是根据 de1 (mod (n)这一公式）。而解出(n)的值，需要组成n的两个大素数因子p和q的值（(n)=(p-1)(q-1)）。因此，破解n的两个大素数组成因子p和q成为破解RSA加密算法的关键性步骤。 对于n位数低的秘钥对，被破译的可能性是非常高的。为了提高RSA加密算法的安全性，就必须得增加n的位数。 Rivest,Shamir和Adleman建议取P和q为100位十进制数(2，这样n为200位十进制数。要分解200位的十进制数，按每秒10的7次幂运算的超高速电子计算机，也要10年。因此，RSA加密算法的安全性是比较高的。第三章 512位RSA加密算法的设计在整套的RSA加密算法中，密钥的选取和加解密过程都非常简洁。而在算法上实现上主要要解决四个问题：1.如何处理大数运算2.如何快速进行模幂运算3.如何获取大素数4.如何进行同余运算实际上，在实现RSA 算法的过程中，后三个问题不是各自独立的，它们互有关联，环环相套。由于本文在第二章的2.1.2中介绍了大素数的产生、2.3.3中介绍了同余运算，那么，在本章中就不再给予介绍，将重点介绍大数运算和模幂运算。3.1 大数运算512位加密算法，指的是n的值转化为二进制时，n的位数是512位的加密算法。第二章中，为了验证加密算法的正确性，举了一个例子，计算出n的结果为2539。这时，n的位数才仅仅是12位的。计算难度已经比较大了。而对于512位RSA加密算法而言，可想而知，它的难度，复杂度是多么的大。 为了便于理解后面提到的蒙哥马利模乘算法，我引入了大数运算的概念。最简单的办法是将大数当作数组进行处理，数组的各元素也就是大数每一位上的数字，通常采用最容易理解的十进制数字09。然后对“数字数组”编写加减乘除函数。但是这样做效率很低，因为二进制为1024位的大数在十进制下也有三百多位，对于任何一种运算，都需要在两个有数百个元素的数组空间上多次重循环，还需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言，采用二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显然非常麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，当然这样效率就更低了。一个有效的改进方法是将大数表示为一个n 进制数组，对于目前的32位系统而言n 可以取值为2 的32次方，采用verilog语言描述，即 32b0，假如将一个二进制为512位的大数转化成32b0进制，就变成了32位，而每一位的取值范围不再是二进制的01或十进制的09，而是0-32bffffffff，我们正好可以用一个32位的DWORD （如：无符号长整数，unsigned long） 类型来表示该值。所以512位的大数就变成一个含有32个元素的 DWORD数组，而针对 DWORD数组进行各种运算所需的循环规模至多32次而已。而32b0进制与二进制，对于计算机来说，几乎是一回事，转换非常容易。例：C=A*B，首先我们需要观察日常做乘法所用的“竖式计算”过程如图3.1：A3 A2 A1 A0* B2 B1 B0-= A3B0 A2B0 A1B0 A0B0+ A3B1 A2B1 A1B1 A0B1+ A3B2 A2B2 A1B2 A0B2-= C5 C4 C3 C2 C1 C0图3.1 竖式计算可以归纳出：C = ，其中i-j必须>=0且<=p。当然这一结论没有考虑进位，虽然计算Ai-j*Bj和Sum的时候都可能发生进位，但显然这两种原因产生的进位可以累加成一个进位值。最终可用如下算法完成乘法：n=p+q-1carry=0For i FROM 0 TO nresult=carryFor j FROM 0 TO qIF 0<=i-j<=p result=result+Ai-j*BjC=result mod Rcarry=result / RIF carry! = 0n=n+1Cn=carry3.2 模乘运算模幂乘运算m mod n不能先计算m然后再求模，这样m的结果会占用巨量的存储空间而无法实现，必须对m的中间结果进行求模运算，使结果二进制位数始终保持在一定范围内。计算m mod n最简单的方法是重复进行c=c*m mod n模乘运算，直到求出m mod n为止，这种方法需要e-1次乘法运算。例如计算m mod n需要计算m à m à m à m à m à à m共需要14次乘法。而采用m à m à m à m à m à