公钥密码体制与数论(终稿).doc

公钥密码RSA加解密体制中的数论和快速算法（武汉工业学院 数理科学系 陈欣 ）关键字：单向函数与严格单向函数 公钥与私钥 欧拉定理 素性判别 大数分解 模算术内容摘要：传统的密码体制，收发双方有相同的加密密钥和解秘密钥，如DES,3-DES,AES等。而且加密密钥和解密密钥都是相同的。这就给密钥的分配和管理带来了很大的难度。公钥密码体制的好处有两点。第一，加密密钥和解密密钥分开，加密密钥可以公开，而解密密钥是严格保密。第二，这一密码体制可以用来进行数字签名认证。本文重点介绍RSA公钥密码体制的理论基础、算法流程以及相关算法的软件实现。正文：一、公钥密码算法体制RSA基本数论知识定义1：一个数论函数称作严格单向函数，如果它满足以下条件：存在一个有效的方法，对所有,是容易计算的方程在中有解，但是由计算是困难的。定理1：任意一个正整数，总可以分解为，其中是的所有的素因子，是正整数。1有几个单向函数，人们长期以来无法证明其不是严格的单向函数。但是从另一方面讲，也增加了他们是的可能性2。目前人们就把他们当作是严格单向函数使用，大素数相乘就是其中之一。求大素数的乘积是一件很容易的事，可是将一个合数分解成大素数的乘积就不是一件容易的事情了。特别是当素数的规模在1024位及以上时（2进制）。这样可以认为它是一个严格单向函数，这是数学上一个著名的难题-大整数分解难题（IFP）。关于大整数分解问题的困难性，可以参见2。著名的RSA密码算法体制的安全性就基于此。定义2：，在中与互素的元素个数记作。称为欧拉函数。定理2：，其中是的所有的素因子，是正整数。则=。1定理3：若整数互素。则。特别的。当是素数，则当时，有，此特殊形式称之为费马小定理。1定理4：若，则同余方程有唯一的解。1RSA密码体制简介RSA密码体制采用下述加解密变换：为方便起见，我们约定Alice为明文消息发送方，Bob为密文接受者。步骤1：Bob选取两个大素数（严格保密）。步骤2：Bob计算（公开），由定理2可知（保密）步骤3：Bob选取随机整数，满足（公开）步骤4：Bob计算，满足，由定理4可知存在且唯一（保密）步骤5：将加密信息及明文数字化记为,记为加密后的密文。加密： Bob将公开。Alice用Bob的公钥加密明文,得到密文。并且将密文发给Bob 解密: Bob 接到Alice发过来的密文，用自己的私钥解密。得到明文下面证明解密过程是正确的：由于。设。这样对任何，一定有。接下来分两种情况进行处理：如果:则由定理3，故。如果:由于，故，则不妨设，则。由定理3，这样对任何，总有，则由欧拉函数的性质得到，由此。这样一定存在整数，使，从而。二、RSA算法中的快速的模运算算法 在本文第一部分中，我们通过详细介绍RSA公钥密码体制，发现数论是其主要理论基础。当然学过数论的读者，当然不会对本文中的一些数论相关的理论感到陌生。事实上，我们考虑的是，其中相关的算法如何实现。我们都知道，现在的电脑处理大整数的能力是远远不能满足RSA的需要的。因为从现在的安全角度来讲，RSA算法中初始的大素数起码要是1024位（2进制）的，而现在电脑处理的整数最多不超过64位（换算成十进制数仅仅只有）。我们在这里假定读者已经实现了大整数的基本四则运算。事实上，关于这一点，读者有多种选择：既可以使用国际上现行流行的免费大整数库例如GNU MP(/gmp/)、OpenSSL（）等等，也可以自行开发快速的大整数库.笔者建议，从安全的角度出发，最好采用自行开发的大整数库。而这一点，对于一些有初等计算机编程能力的密码工作者来说是很容易的。但是即使如此，我们注意到，仅仅只掌握了大整数的四则运算，对实现RSA是远远不够的。因为RSA基本加解密的流程主要是模算术。在RSA加解密变换的5个步骤中。仍然有以下一些算法（重点是模算术）上的问题我们要单独拿出来分析。素数的判别与生成 在RSA密码体制采用加解密变换的步骤1中，如何选择合适的大素数一直是RSA的焦点所在。我们接下来介绍几种常见的素数判定方法。 俄拉多塞筛法（试除法）定理5：如果是合数，则必能被一个不大于的素数所整除。3这样对于，要判别是不是素数，只要用不大于的所有素数去试除，只要有一个能整除，则是合数。否则是素数。用传统的素数筛选方法检测一个随机数是否为素数首先需要获得所有小于的素数，当很大时，要获得所有小于的素数就是一件困难的事。并且以下的定理告诉我们，用这样的方法去计算的时候计算量是很大的，特别是在很大的情况下。定理6：用试除法判定给定的整数是否素数其计算量是3目前对于大数的素性测试，通常都采用MillerRabin测试法。这是美国国家标准和技术研究所（NIST）在数字签名标准(DSS)建议中推荐使用的算法。MillerRabin（测试法）首先选择一个待测的正奇数，计算，是2整除的最大次数，然后计算，使得，显然此时是奇数。此算法的基本思想如下：步骤1：选择一个小于的随机数；步骤2：设 步骤3：如果，那么通过了测试，可能是素数；步骤4：否则继续：对，计算，如果，停止。那么通过了测试，可能是素数；如果，则停止。返回是合数步骤5：如果都不是，则返回是合数步骤6：通过了测试，可能是素数； 可以证明，进行一次MillerRabin测试，将合数误判为素数的概率仅是。2我们可以选取不同的随机数重复进行此判别比如10次，这样一来如果在10次判别后仍然没有返回“合数”，则可以将当成概率素数，并且误判率不会高于。 大整数的分解 破解RSA实际上就等同于对大整数进行分解。事实上我们有下面的定理。定理7：设，则计算与分解是等价的。3对大数分解的困难就保证了RSA加密体制的安全性。为了实际上的安全考虑，我们选取的大素数应该至少是155位到200位的素数，以抵御现行的分解大整数的能力。1977年，当里凡斯特等人提出RSA加密体制的时候，他们给出了一个例子。是64位的素数，是65位的素数，是130位的素数。在当时分解这样的素数简直就是一项不可能的事。但是随着计算机的运算能力的不断加强，在1996年4月。人们已经可以成功分解出一个130位的RSA数。并且在现在为止，随着连分数法、二次筛法、数域筛法的相继出现，人们掌握的整数分解办法已经可以成功地分解出155位的十进制数。所以现在RSA数的选择必须要更大一些。相关模运算a. 求最大公约数(Gcd)在RSA加密流程的步骤3中，要求两个数的最大公约数(Gcd)。我们采用stein算法，其理论基础由如下定理给出：定理8：对于正整数，则对任意整数， 4定理9：对于正整数，则 4流程如下：输入：正整数输出：步骤1：令正整数步骤2：若都是偶数。则步骤3：若仍是偶数。转到步骤2步骤4：若是偶数，是奇数。则步骤5：若仍是偶数，则转到步骤4步骤6：若是偶数，是奇数。则步骤7：若仍是偶数，则转到步骤6步骤8：若都不是偶数。则步骤9：若，转到步骤2步骤10：步骤11：输出比起传统的Eculid5求Gcd，Stein算法没有用除法，始终都在作加减和移位运算。因为在计算机中，乘以2或者处以2都是用左移和右移来实现的，这就极大加快了运算的速度。b扩展Eculid算法求模逆元在RSA加密流程的步骤4中，要用到计算，满足。这就是我们所说的求模逆的运算。我们采用扩展Eculid算法求的解。算法流程如下：输入：正整数输出：或者不存在的信息步骤1：如果，返回不存在步骤2：步骤3：计算步骤4：步骤5：回到步骤2，直到，返回算法分析：其理论基础是Eculid辗转相除法。1我们用数学归纳法来证明算法的正确性：首先，我们证明在以上算法流程中，每一次循环体内均有下面等式成立：第一轮的初值可以验证成立。假设轮候等式仍成立，则考虑第轮的赋值（打好表示新一轮的值）。利用归纳假设可以知道：故论是仍然成立，上述中的三个等式得证。其次，每新一轮的被赋值，这样辗转下去，必然下降到初始值的最大公约数。所以当循环结束时，根据等式，此时的即为所求。C模幂算法在RSA加密流程的步骤5中，无论是加密还是解密，都用到了计算这样的同余式。我们介绍一种快速的算法：输入：，这里采用的是2进制的表示输出：算法流程：步骤1：如果则，否则步骤2: 从，重复执行 2.1 2.2 如果，则步骤3: 返回算法流程中2.1 这一步，可采用特殊的平方乘算法。读者可参阅5d.模乘算法 在这里我们介绍一种快速的模乘即是著名的Montgomery模乘。1985年，Peter L.Montgomery提出Montgomery算法，后进过多次改进。算法思想如下： 给定一个比特正整数（模）和两个比特级操作数，其中，模乘就是计算。我们记 其中，是字长通常取32或者64。对于RSA，一般取1024或者2048。算法流程：输入：。其中为模，输出：步骤1：步骤2：步骤3：步骤4：若，则返回，否则返回最后。其中对事先做一个预处理即可。上述算法可知，Montgomery模乘不需要用到除法或者求逆，因为，模实际上就是取其最低位，而除就是将其右移位，这无论是在硬件还是软件都是很容易实现的。参考文献：1 华罗庚 数论导引科学出版社1957 2 Bruce Schneier应用密码学、协议与源程序机械工业出版社3 柯召 孙琦 数论讲义高等教育出版社 第二版 2001年4 潘承洞 潘承彪初等数论北京大学出版社 19985 Paul Garrett 著密码学导引机械工业出版社 20036 Peter L.Montgomery. Modular Multiplication Without Trial Division. MatheMatica of Computation,1985,44(170):519-521 Abstract: In the traditional cryptography , the management and allocation of key became very inconvenient. Cryptography which develop s gradually in the struggle between coding and decoding ,has became an all-around and outlying technology, with the progress of appli