基于RSA加密算法.doc

1、摘 要数据通信是依照一定的通信协议，利用数据传输技术在两个终端之间传递数据信息的一种通信方式和通信业务。随着数据通信的迅速发展而带来了数据失密问题。信息被非法截取和数据库资料被窃的事例经常发生，在日常生活中信用卡密码被盗是常见的例子。所以数据加密成为十分重要的问题，它能保证数据的安全性和不可篡改性。 RSA加密算法以它难以破译的优点，被广泛的使用在电子商务和VPN中。 本文针对非对称性加密RSA算法，采用软件Visual C+6.0进行程序编写。根据模乘法运算和模指数运算的数学原理所编写的程序在进行测试后，能够通过输入两个素数进行运算从而实现明文与密文之间的转换，然后通过对公钥和私钥的管理，对

2、所传输的数据进行保护，让数据只能由发送者和接收者阅读，以达到数据通信中数据无法被他人破译的目的。关键词:RSA算法，数据通信，加密, 解密。and ImplementationTeacher:Chen Fei student:Lu HuiAbstractData communications in accordance with certain communication protocols, the use of data transmission technology in the transmission of data between two terminals as a means

3、of communication of information and communication business. With the rapid development of data communications and has brought the issue of data compromise. Unlawful interception of information and database information on frequent instances of theft, credit card in their daily lives stolen passwords

4、is a common example. Therefore, data encryption has become a very important issue, it can ensure data security and can not be tamper with nature. RSA encryption algorithm to the merits of it difficult to decipher, was widely used in the e-commerce and VPN. In this paper, asymmetric RSA encryption al

5、gorithm, the use of software for Visual C + +6.0 programming. According to Die multiplication and modular exponentiation by the mathematical principles in the preparation of test procedures can be adopted for the importation of two prime numbers and computing in order to achieve explicit conversion

6、between the ciphertext, and then through a public key and private key management, for the transmission of data protection, so that data can only be made by the sender and the recipient to read, in order to achieve data communications data can not be the purpose of deciphering the others.Keywords: RS

7、A algorithms, data communication, encryption, decryption.目录摘 要IAbstractII第1章 引言11.1题目背景11.2国内外现状11.3本课题的主要工作2第2章 数据通信中的加密技术32.1数据加密技术的起源和发展32.2数据加密的方法32.3密钥的管理52.4数据加密的标准52.5数据加密的应用62.6本章小结6第3章 数据加密中的RSA算法83.1 RSA公钥密码体制概述83.2 RSA公钥密码体制安全性分析93.3 RSA算法的缺点103.4 本章小结10第4章 RSA数据加密中的实现114.1随机大素数的产生114.1.1

8、素数的分布114.1.2大素数生成的方法124.1.3 Miller Rabin素性测试法124.1.4基于Miller Rabin素性测试法的新的素数生成方法134.2密钥的生成及加密和解密144.2.1最大公因子gcd运算144.2.2模n求逆元运算164.2.3模n的大数幂乘运算174.2.4模n的大数幂乘运算174.3 RSA算法分析184.3.1 RSA安全性分析184.3.2 RSA时间复杂度分析194.4本章小结19第5章 RSA算法的实现215.1选定组合算法的准则215.2模幂组合算法的实现215.3试验与运行结果22总结24参考文献25致谢26附录2725第1章 引言1.1

9、题目背景 在当今的信息社会中，每天都有大量的信息在传输、交换、存储和处理，而这些处理过程几乎都要依赖强大的计算机系统来完成。一旦计算机系统发生安全问题，就可能造成信息的丢失、篡改、伪造、假冒，以及系统遭受破坏等严重后果。因此，如何保证计算机系统的安全，是当前一个需要立即解决的十分严峻的问题。 通常保障网络信息安全的方法有两大类:一是以防火墙技术为代表的被动防卫型，二是建立在数据加密，用户授权确认机制上的开放型网络安全保障技术。 防火墙技术，就是在局域网与外部网络之间设立一个服务器，将它们之间隔离开来，建立起一个安全网关，从而保护内部网免受非法用户的侵入。 数据加密技术是可以与防火墙配合使用的一

10、种安全技术，这种技术可以提高信息系统及数据的安全性和保密性、防止秘密数据被外部破解所采用的主要技术手段之一。按其不同的作用，数据加密技术主要分为数据传输、数据存储、数据完整性的鉴别以及密钥管理技术四种。加密技术是通过计算机网络中的加密机构，把网络中的各种原始数字信息(明文)按照某种特定的加密算法变换成与明文完全不同的数字信息，即转换成密文。计算机网络中的加密技术主要采用链路加密和端对端加密等两种方式。通常情况是将这两种加密模式结合起来共同使用，即可保证网内用户的数据安全，又可提供用户之间的身份鉴别与认证。1.2国内外现状RSA被广泛应用于各种安全或认证领域，如web服务器和浏览器信息安全、Em

11、ail的安全和认证、对远程登录的安全保证和各种电子信用卡系统的核心。硬件上，如安全电话、以太网卡和智能卡也多采用RSA技术。而几乎所Internet安全协议如S/MIME,SSL和S/WAN都引入了RSA加密方法。IS09796标准把RSA列为一种兼容的加密算法，使得RSA的应用目前非常广泛。RSA模数n=pq是RSA算法的安全性的核心。如果模数n被分解，则RSA体制立刻被攻破。如果RSA算法是安全的，那么n=pq必须足够大，使得因式分解模数n在计算上不可行的。基于安全性考虑，实际应用中所选择的素数p和q至少应该为100位以上的十进制数，相应的模数n=pq将是200位的十进制数。C E Sha

12、nnon建议使用至少100位长度的大素数，从而得到长度为200位以上的大整数模数n。RSA算法的缺点是加密速度慢，模数n的长度越大，加/解密运算所需要的时间就越长，算法实现的速度也就越慢。为了尽可能使用大的模数而又不影响系统实现的速度，实际应用中通常使用专门的硬件实现RSA算法。最重要的影响速度的实现细节是加/解密中的大数运算。大数模幂乘运算是RSA算法的核心运算，也是运算速度提高的关键。高效的大数模幂乘算法可以有效提高系统速度。需要每做一次平方或乘法运算后，就要作一次模运算，当n的值很大时，做一次模运算所需的时间比做一次平方或一次乘法所需的时间更多，是影响算法实现速度的关键。但在实际加密解密

13、过程中，n可能是几个数的乘积，如RSA算法中，n是两个大素数的乘积。这时可通过中国剩余定理进行变换，降低指数的数量级.1.3本课题的主要工作 本文选择RSA数字加密体制为研究对象，讨论了RSA实现过程中，每一步的具体实现算法。RSA加密算法是第一个成熟的、迄今为止理论上最成功的公开钥密系统。它的安全性基础是数论和计算复杂性理论中的下述论断:求两个大素数的乘积在计算上是容易的，但若要分解两个大素数的积而求出它的素因子则在计算上是困难的。但是，在进行加密和解密运算时的整数求幂运算耗时很大，影响了运算速度，因此，人们提出了多种实现算法，以加快运算速度，例如本文提到的SMM算法和指数2K进制化法等。这

14、些算法都是从某一方面入手，在一定程度上加快了运算速度。本文通过分析这些算法的特点，提出了一种综合性的组合方法，在原有算法的基础上更进一步地加快了运算速度。 本文首先介绍了加密算法的数学基础，从数学理论上分析了RSA算法的原理;然后通过C+程序进行实现。 第2章 数据通信中的加密技术随着信息化的应用水平不断提高，尤其是电子政务和电子商务的蓬勃发展，互联网络的信息安全问题越来越引起全社会的重视。数字化办公和生活面临一系列的严重“威胁”。由于互联网的开放性，我们面临各种各样的安全威胁。网上传输的邮件可能被截取，信息的内容可能被篡改;电子商务过程中，信用卡帐号和密码可能暴露在第二者面前;一些人可能会假

15、冒合法用户身份或者假冒网站来用于一些非法目的，而事后又对自己的行为进行抵赖:系统可能由于黑客的攻击而无法提供有效的服务。这些问题给计算机从业人员揭示信息安全问题的严重性。 因此如何保证信息的机密性、完整性、不可抵赖性、有效性，成为网络安全关注的核心问题。人们由此采用防火墙和数据加密等技术来保障网络本身的安全。2.1数据加密技术的起源和发展 早在互联网出现之前，密码技术已经广泛应用于军事和民用方面。有记载的最早的密码系统可能是希一腊历史学家Polybios发明的Polvbios格板，它是一种替换密码系统。人们很早以前将密码系统分为代替和换位密码两种。 从密码史的发展来看，1949年，信息论的创始

16、人仙农(C. E.Shannon)发表了一篇著名的文章，论证了一般经典加密方法都是可以破解的。到了60年代，随着电子技术、信息技术的发展及结构代数、可计算性理论和复杂度理论的研究，密码学又进入了一个新的时期。我们当前所应用的密码体制，都是属于近代非经典的密码体制。70年代后期出现的数据加密标准DES(DataFncryptionStandard)和公开密钥密码(非对称密码)体制(Publickeycrypto一system)是近代密码学发展史上的两个重要里程碑。目前，最著名公开密钥密码体制是RSA体制，它是由美国MIT的二位科学家Rivest, Shamir不II Adleman于1976年提

17、出的，是一种基于数论中大数分解的理论。由于RSA的安全性和实用性，它是当前使用最广泛的公钥密码系统，即可以进行加密，也可以进行数字签名。保障了数据的完整性、机密性，解决了身份认证问题和不可抵赖性问题.2.2数据加密的方法 数据加密的方法通常分为两大类:对称式加密体制 (常规密钥密码体制)和非对称式加密体制(公开密钥密码体制)。对称式加密就是加密和解密使用同一个密钥，通常称之为Session Key”这种加密技术曾经被广泛采用，其原理如图2-1所示。如美国政府所采用的DES加密标准就是一种典型的“对称式”加密法，它的Session Key长度为56位。发送者加 密相同的密钥加密的信息接受者解 密

18、明文明 文2-1 对称密码算法示意图非对称式加密就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为“公钥”和“私钥夕，它们两个必需配对使用，否则不能打开加密文件。这里的“公钥”是指可以对外公布的，“私钥”则不能，只能由持有人一个人知道。它的优越性就在这里，因为对称式的加密方法如果是在网络上传输加密文件就很难把密钥告诉对方，不管用什么方法都有可能被他人窃听到。而非对称式的加密方法有两个密钥，目_其中的“公钥”是可以公开的，也就不怕别人知道，收件人解密时只要用自己的私钥即可以，这样就很好地避免了密钥的传输安全性问题。非对称加密工作原理如图2-2所示。加密密钥EB明 文明文解 密接受者加密的

19、信息加密密钥EB（公开）加 密发送者解密密钥DB（保密）EBDBDB2-2 非对称性密码算法示意图2.3密钥的管理密钥既然要求保密，这就涉及到密钥的管理问题，密钥的管理涉及到以下几个方面:(1)密钥使用的时效和次数如果用户使用同样密钥多次与其他用户交换信息，那么密钥也同其它任何密码一样存在着一定的安全性。虽然用户的私钥是不对外公开的，但是也很难保证私钥长期的保密性，很难保证长期以来不被泄漏。如果入侵者偶然地知道了用户的密钥，那么用户曾经和其他用户交换的每一条消息都不再是保密的。另外使用一个特定密钥加密的信息越多，提供给窃听者的材料也就越多，从某种意义上来讲也就越不安全了。因此，一般强调仅将一个

20、对话密钥用于一条信息中或一次对话中，或者建立一种按时更换密钥的机制以减小密钥暴露的可能性。(2)多密钥的管理假设在某机构中有100用户，如果任意两个用户之间可以进行秘密对话，那么总共需要多少密钥呢?每个人需要知道多少密钥呢? 如果任何两个用户之间通信需要不同的密钥，则总共需要4950个密钥，而且每个人应记住99个密钥。如果机构的用户更多，这种办法就显然过于平庸。Kerberos提供了一种解决这个较好方案，它是由MIT发明的，使保密密钥的管理和分发变得十分容易，但这种方法本身还存在一定的缺点。为能在互联网上提供一个实用的解决方案，Kerberos建立了一个安全的、可信任的密钥分发中心(Key D

21、istribution Center,KDC)，每个用户只要知道一个和KDC进行会话的密钥就可以了，而不需要知道成百上千个不同的密钥。2.4数据加密的标准对称密钥加密算法DES (Data Encryption Standard)是由工BM公司在70年代发展起来的，并经政府的加密标准筛选后，于1977年被正式批准并作为美国联邦信息处理标准。DES使用64位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。64位密钥中，有8位奇偶校验位，实际密钥长度只有56位。每轮编码时，一个48位的“每轮”密钥值由_5 6位的完整密钥得出来。DES用软件进行解码需用很长时间，而用硬件解码速度非常

22、快。对于DES的最后一次评估是在1994年，美国己决定1998开始，不在使用DES。目前，新的加密标准AES正在征集、评估和制定中。尽管如此，DES对于推动密码理论的发展和应用起了重大作用。RSA是另外一种非常著名的公钥加密体制，由Ron Rivest, AdiShami:以及Leonard Adleman于1978年提出，一该体制至今仍被公认为是一个安全性能良好的密码体制。该算法是基于大数不可能被质因数分解假设的公钥体系。简单地说就是找两个很大的质数。一个对外公开的为“公钥”(Public key)，另一个不告诉任何人，称为“私钥”(Private key)。这两个密钥是互补的，也就是说用公

23、钥加密的密文可以用私钥解密，反过来也一样。DES被公认为世界上第一个实用的密码算法标准。它的出现适应了电子化和信息化的要求，是一种加/解密标准，适合于硬件实现，因此它的算法被制成专门的芯片，应用于加密机中。DES现在仍被广泛应用于金融和商业领域。RSA则是非对称密钥的实际标准。在实际应用中，通常是DES和RSA加密算法同时使用。由于DES加确牟密速度上的优势，因此数据的加/解密通常是用DES完成的，而 DES使用的密钥是通过应用RSA算法生成的数字信封来传递的，保障了密钥传递的安全性。2.5数据加密的应用 数据加密技术的应用是多方面的，但最为广泛的还是在电子商务和VPN上的应用。 (1)在电子

24、商务方面的应用 电子商务(E-business)允许顾客和商家可以在网上进行各种商务活动，同时不必担心相应的商务信息被盗用，比如信用卡号码、商品报价等。RSA的出现，提高网上交易的安全性，从而使电子商务走向实用成为可能。 NETSCAPE公司提供了一种基于RSA的安全套接层协议SSL(Secure Sockets Layer)即为数据加密技术在电子商务方面应用的一个典型案例。 SSL2. 0用电子证书(Electric certificate)来实行身份进行验证后，双方就可以用保密密钥进行安全的会话了。它同时使用“对称”和“非对称”加密方法，在客户与电子商务的服务器进行沟通的过程中，客户会产生

25、一个Session Key，然后客户用服务器端的公钥将Session Key进行加密，再传给服务器端，在双方都知道Session Key后，传输的数据都是以Session Key进行加密与解密的，但服务器端发给用户的公钥必需先向有关发证机关中请，以得到公证。 SSL协议是一个比较优秀而久经考验的网络安全协议，一般情况下能够抵抗窃听、篡改、会话劫持、中间人等多种攻击手段。协议的设计模式为“契入式”，与高层应用协议和低层网络协议无关，可以方便地集成到多种网络环境中去，可根据不同的安全需求，选择协议提供得多种密码算法和密钥交换协议。SSL目前在Web和电子商务中的应用相当广泛。(2)加密技术在VPN

26、中的应用 目前，跨地域国际化的机构越来越多。一个机构在多个城市、国家设有分支机构。每一个机构都有自己的局域网LAN (Local AreaNetwork)。事实上，很多机构一般租用专用线路来连结这些虚拟的局域网。这种情况下，机构内部的重要文件、数据是通过广域网进行传输，因此网络的安全问题最为重要。具有加密/解密功能的路由器等设备的出现，使通过广域网组成局域网成为可能，即所谓的的虚拟专用网(Virtual Private Network, VPN)。当数据离开发送者所在的局域网时，该数据首先被用户湍连接到互联网上的路由器进行硬件加密，数据在互联网上是以加密的形式传送的，当达到目的LAN的路由器时

27、，该路由器就会对数据进行解密，这样目的LAN中的用户就可以看到真正的信息了。而加密解密过程对于普通的非网络管理用户来说，是透明的，既普通用户无需考虑VPN及加密解密的相关问题。因此，对普通用户来说， VPN在使用过程中和一般LAN没有任何区别。2.6本章小结本章对数据加密技术作了简要的介绍，其中包括数据加密技术的起源、发展，数据加密技术的概念，密钥管理等密码技术各方面的内容。此外还对数字签名技术作了介绍。数字签名技术实际上是数据加密技术在应用上的延伸，是目前网上交易活动中，身份验证技术的重要组成部分。而基于公开密钥机制的数字签名技术在应用中，占有统治地位，尤其是基于RSA公钥的数字签名体制在应

28、用中更为广泛。在接下来的一章，就将详细介绍基于RSA的数字签名体制。第3章 数据加密中的RSA算法目前企业面临的计算环境和过去有很大的变化，许多数据资源能够依靠网络来远程存取，而且越来越多的通讯依赖于公共网络公共网络（如 Internet），而这些环境并不保证实体间的安全通信，数据在传输过程可能被其它人读取或篡改。加密将防止数据被查看或修改，并在原本不安全的信道上提供安全的通信信道，它达到以下目的：保密性：防止用户的标识或数据被读取。 数据完整性：防止数据被更改。 身份验证：确保数据发自特定的一方。3.1 RSA公钥密码体制概述 RSA公钥密码体制于1978年，由美国麻省理工学院Rivest,

29、Shami:和Adleman二人提出的，至今为止仍被公认为是公钥密码体制中最优秀的加密算法，被认为是密码学发展史上的第二个里程碑.它是一种特殊的可逆摸指数运算的加密体制，其理论基础是数论中的一条重要论断:求两个大素数之积是容易的，而将一个具有大素数因子的合数进行分解却是非常困难的。除了用于加密之外，它还能用于数字签名和身份认证。RSA公钥密码体制过程描述如下:(1)选取两个大素数和.(2)计算（公开)，欧拉函数)。(3)随机选取正整数e, ，满足, e是公开的加密密钥。(4)计算d，满足. d是保密的解密密钥。(5)加密变换:对明文,明文为(Zn为明文空间)(6)解密变换:对密文,明文为可以证

30、明，解密变换是加密变换的逆变换。例:(1)生成密钥:选择两个互质的质数; 取 ;由，得d=147;所以，保密的解密密钥为d=147，公开的加密密钥公钥为e=3,n=253;明文空间为(2)加密原文:假设原文m的数字为16_5，用公钥加密原文。(3)解码密文: A=C，由此可以看出RSA算法的一般过程。3.2 RSA公钥密码体制安全性分析RSA体制中，加密密钥e与大整数n是公开的，而解密密钥d与大素数p和q是保密的。虽然在RSA的加密与解密密钥建立后，p和q不再需要，但p和q也绝不能泄露。若n被分解，则也就不保密，e公开，d就可以计算出来，RSA便被破译。己知n，求得，则P和q可以求得。因为根据

31、欧拉定理，又有据此列出方程:由以上方程组，可以求得p和q。因为p和q都是大素数，根据现在已知的结果，因子分解n是最好的算法，此时复杂性为:若n为200位于进制数，则用每秒107次运算的高速计算机，也要108年才能得到计算结果。可见，RSA的素数分解确实存在一定的难度。为安全起见，对p和q要求:p和q的相差不大;(p-1)和(q-1)有大素数因子;很小，满足这样条件的素数称做安全素数。RSA的出现使得大整数分解因式这一古老的问题再次被重视，近些年来出现的不少比较高级的因数分解方法使“安全素数”的概念也在不停的演化。所以，选择传统上认为是“安全素数”并不一定有效的增加安全性，比较保险的方法就是选择

32、足够大的素数。因为数越大，对其分解因式的难度也就越大!对n和密钥长度的选择取决于用户保密的需要。密钥长度越大，安全性也就越高，但是相应的计算速度也就越慢。由于高速计算机的出现，以前认为己经很具安全性的512位密钥长度己经不再满足人们的需要。1997年，RSA组织公布当时密钥长度的标准:个人使用768位密钥，公司使用1024位密钥，而一些非常重要的机构使用2048位密钥。3.3 RSA算法的缺点RSA的缺点主要有： A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法

33、慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。3.4 本章小结RSA算法在理论上的重大缺陷就是并不能证明分解因数绝对是困难的。RSA方法既可用于保密、也能用于签名和认证，许多流行的操作系统如微软、Apple, Sun和Novell都在其产品上融入了RSA。同时，RSA也被广泛应用于各种安全或认证领域，如web服务器和浏览器信息安全、Email的安全和认证、对远程登录的安全保证和各种电子信用卡系统的核心。硬件上，如安全电话、以太网卡和I智能卡也多采用RSA技术。而且几乎所有Internet安全协议如SMME, SSL不II SWAN都引入了RSA加密方法。IS

34、09796标准把RSA列为一种兼容的加密算法，使得RSA的应用目前非常广泛。任何一种事物有出现、繁荣，也不可避免的会走向灭亡。在没有找到快速进行大整数分解因式方法的时候，RSA显示了不可比拟的优点。而当分解因式不再是难题的时候，RSA算法也就将失去存在的价值。第4章 RSA数据加密中的实现RSA算法,它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字就是发明者的名字：Ron Rivest, AdiShamir 和Leonard Adleman, 但RSA的安全性一直未能得到理论上的证明， RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的

35、难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题， RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA算法实现数据加密的主要步骤分为：1、获取密钥，这里是产生密钥，实际应用中可以从各种存储介质上读取密钥。2、加密。3、解密。4.1随机大素数的产生 公钥密码学需要大素数，因此，大素数的快速有效随机生成方法是公钥密码学中的一个重要问题，具有非常显著的实用价值。显然，通

36、过对一个随机数进行因子分解，我们可以判断这个随机数是否为素数。如果这个随机数能被因子分解，则它不是素数，否则它一定是素数。但是，大素数的因子分解是一个复杂的问题，到现在还没有找到一个快速有效的算法来对大整数进行因子分解。因此，不能试图通过对随机数进行因子分解来生成大素数。正确的生成大素数的方法是对生成的随机数先测试它是否为素数，而不是对它进行因子分解。这种素性测试比因子分解要容易得多，己经有许多素性测试方法能够确定一个随机数是否为素数。如果合数通过一个素性测试的概率足够小，则这个素性测试就是很可靠的。实际上，对于许多素性测试方法，合数通过测试的概率可以受到人为的控制，即是可以把合数通过测试的概

37、率设定的足够小。4.1.1素数的分布 要讨论素数的生成问题，首先要讨论素数的分布。素数的分布是极不均匀的，素数越大，分布也就越稀疏。 首先，存在无穷多个素数。对此，我们可以证明。假设正整数中只有k个素数，设为。令,则n1。如果n是素数，则显然n与都不相同，这与只有k个素数的假设相矛后。如果n不是素数，则n一定有一个素数因子, ，否则由于以及,所以,这与p是素数相矛盾。故p与都不相同，这与只有k个素数的假设想矛盾。因此素数有无穷多个。其次，我们可以根据素数定理，发现素数的分布情况。素数定理的描述为:设, 为不大于x的整数的个数，则根据素数定理，可以估计出长度为t位的素数大约有个。例如，一个长度为

38、256位的随机数的素数的概率为而一个长度为64位的随机数的素数的概率为由此可见，位数越多，素数的分布越为稀疏。4.1.2大素数生成的方法产生素数的一般方法可以分为两类，即确定性素数产生方法和概率性素数产生方法。（1）确定性素数产生方法确定性素数产生方法产生的数必然是素数。然而其产生的素数却带有一定的限制。假若算法设计不佳，便容易构造出带有规律性的素数，使密码分析者能够分析出素数的变化，进而可以猜到该系统中使用的素数。此类方法主要有两类，即基于Lucas定理和基于Pocklington定理的确定性素数产生方法。这里简单介绍基于Lucas定理的确定性素数产生方法。此方法需要求得素数n-1的全部素因

39、子。Lucas定理：设，存在一个正整数且，且对于n-1的每一个素q，均满足a，则n为素数。(2)概率性素数产生方法概率性素数产生方法产生的数仅仅是伪素数。其缺点在于，尽管其产生合数的可能性很小，但是这种可能性仍然存在:其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是生成大素数的主要方法，其中著名有:Miller Rabin与Solovay Strassen算法等。本文讨论Mill Rabin算法。4.1.3 Miller Rabin素性测试法Miller Rabin素性测试法是在实际中应用非常广的一种素性测试方案，可以用来判定某随机数是否为素数。其定义如下:设是一个奇数，设，

40、其中s是非负整数，是奇数，设，如果，或者存在一个r,，使得则称n通过以b为基的Miller-Rabin测试。下面是Miller-Rabin素性测试的依据，包括两个定理:定理一：设p是一个素数，对任意整数b，如果 ，则p一定可以通过以b为基的Miller-Rabin测试。定理二：如果n2是一个奇合数，则至多有个b，0b30)次Miller Rabin检测，则可以人为P是一个素数。大素数的选取对RSA系统的安全而言至关重要。一个直接方法是分解n，求出因子p与q，进而求得解前的分解能力大约为130位十进制数，但512比特(154位于进制数)模长的RSA体制的安全性已经受到一定的威胁。专家建比特(30

41、8位十进制数)模长。由于密码长度直接影响系统运行的速度，所以对要不是特别高的系统，可以适当的减少密码的长度。4.2密钥的生成及加密和解密为了建立密码系统，用户A需要完成以下各步骤（1）A产生两个大素数p和q； （2）A计算n=pq和；（3）A选择一个随机数，使得；（4）A计算；（5）A将n和a作为他的公钥直接公开;（6）加密变换和解密变换。由上述过程，我们可以看出RSA加密系统的主要工作为大素数的生成、最大公因子gcd、模n求逆和模n的大数幂乘的算法。上一节，已经讨论了大素数的生成算法，这里主要讨论最大公因子gcd、模n求逆和模n的大数幂乘的算法。4.2.1最大公因子gcd运算这里采用经典的E

42、uclid算法为基础进行运算C。这个算法就是公元前300年，欧几里德在其著作几何原本)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。设定n和u两个正整数，则一定存在整数q和r使得n=qu+r,其中，不难看出，由此，我们得到求两个正整数的最大公因子的Euclid算法如下:(1);(2)(3)如r=0，则;(4)如果r0，则，转第(2)步。以下对这一算法稍作改进:令为Euclid算法中第i次对赋值后的值，为Euclid算法中第i次对赋值后的值，,规定。利用数学归纳法容易证明:对任意，存在整数使得 事实上，当时，取则显然有假设i=j时，式(4-15)和(4-16)成立，则当i=j+l时， 其

43、中q(j)为Euclid算法中第i次对q赋值后q的值，规定，因此从上面的讨论可知，存在整数a和b使得.可以对Euclid算法做一点修改，使之可以同时求出gcd(n,u)和满足上式的整数a和b，称之扩展Euclid算法，此算法描述如下:(1)(2) (3)如果r=0，则;(4)如果r0，则，则转(2)步。以上即为扩展的Euclid算法，该算法在计算模n求逆时，颇有用处。4.2.2模n求逆元运算这里来讨论模n求逆元的算法。设n和u都是正整数，模n的逆就是满足的整数v,。可以证明，对于正整数，对于，存在。使得的充分必要条件是。证明必要性:对于任意，存在整数q使得,假设。因为，所以，即对任意，都有，因

44、此，如果存在，使得，则必然有。证明充分性：假设，则存在整数a和b使于是令，则。由上述定理的充要性证明可以得知，利用扩展的Euclid算法可以求得u模n的逆，以扩展的Euclid算法为基础，可以得到模n求逆的算法如下：(1);(2);(3)如果r0，则；(4)如果1，则u模n不存在逆元；(5)如果=1，则u模n逆元为。举例说明上述算法，求13模35的逆元:35=213+9,9=135-213,13=19+4,4=113-19=-135+39=24+1,1=19-24=335-813,所以13模35的逆元为4.2.3模n的大数幂乘运算RSA公钥密码体制中，加密和解密时都要进行运算，下面给出一个计算的快速算法。(1)ax,br,c1;(2)如果b=0，则输出结果c，结束;(3)如果b mod 20，则转到第(5)步;(4)转第(3)步:，(5)，转第(2)步。举例说明上述算法，求13模35的逆元:35=213+9,9=135-213,13=19+4,4=113-19=-135+313,9=24+1,1=19-24=335-813,所以1