RSA大素数生成法.docVIP

RSA算法中安全大素数的生成 应用数学0801 白钦予 080705003 第一部分.序 RSA算法简介。 RSA是被研究得最广泛的公钥算法，也是第一个能同时用于加密和数字签名的算法RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。　　RSA的算法涉及三个参数，n、e1、e2。 　其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。 (n及e1),(n及e2)就是密钥对。 　RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n；:随机产生一个奇数p1进行素数测试,若是素数,则结束;否则,重新随机产生一个奇数P2进行素性测试,直至找到一个素数Pt。 由于素数分布的不确定性，尤其是在于高达2000以上位数的等级上素数的分布更加无序，可见这种方法实践起来是很耗时的。 随机递增有哪些信誉好的足球投注网站法比起之前的方法要好一点：随机产生一个奇数,对以该数为起点的奇数依次进行测试,直至找到一个素数。这种方法相对于随机有哪些信誉好的足球投注网站法，在速度上有一定的提高，但是并没有本质上的区别。 其实对于素数的生成，并不需要一定在一个算法中就要直接地生成一个素数，我们只需要生成一个接近于素数的数，比如非单位因子仅有很少的大奇数，或称其为伪素数，然后再对其进行素数检验就可以了。有时生成伪素数并进行检验，在时间上更要少过直接使用随机法寻找真正的素数。因为单一的生成不需要检验的确定为素数的大额数字，或是对随机递增法生成的奇数按次序检验素性，因为这些步骤在操作中都是很费时的工作，如果将两者组合进行，则将可以节省很多的时间，实现大素数的快速生成。 下面是一个寻找伪素数的方法，简称为素因子法： 对于任何一个合数，其本质上都是若干素数的乘积，比如：，其中x是一个大合数，a,b,c……是若干从小到大排列的素数，j,k,l……为幂数且为非负整数。即，任何一个大合数，都要含有素数作为因子，比如从4以上的偶数，都至少要含有2作为因子。于是我们可以适当归类，可以看出，一般的大合数的素数因子，比如2,3,5等等，这个素数因子的值越小，其幂数越有可能比较高。比如在从2到10000的所有数中，素数3的倍数明显要多于素数17的倍数。于是我们可以取某一个素数作为上限，将不大于它的所有素数作为生成工具，当一大数字并不含有它们任何一个作为因子，则我们就暂且认为这个大数字是素性的。其实这样生成的数字并能真的证明它确实是素性的，但是这样的方法可以过滤掉绝大多数非素性的大数字，留下的很有限的部分数字，我们暂且定义为“伪素数”。 于是在构造RSA体制中的大素数时，首先利用概率性素数测试产生伪素数，然后再利用确定性素数测试法进行检验。 【1】伪素数生成过程如下： 随机选取一个大奇数n 将从2开始的53个素数排列成数组，作为工具a[i] 令i=0，计算 判断，若x=0，说明n显然是合数，回到步骤1。若，说明暂且可以认为n是素性的，进行步骤5。 当i=52，则将n视为一个伪素数，然后作为素数生成部分的结果。 以上是生成过程，举例为前53个素数。其实在真正的实际应用之中，应当将所有2000以内的素数都纳入工具。对于 二．素数筛选。 在第一个阶段中生成的伪素数，并不能确定是完全素性的，所以需要筛选一下，去掉一些假的素数，常用的素数的筛选方法有Miller Rabin法,Lehmann法,Solovay Strassen法。 其中最常用的是,Miller Rabin测试法。这种方法有两种优点，第一，筛选的速度比较快。第二，筛选之后通过下一个素数检测阶段的概率很高。根据有关资料，通过r次测试后,错误概率不超过1/4的r次幂，可以说是很理想的。由于RSA密钥的生成时间大部分都在大素数的生成环节上，而大素数的生成的时间有相当一部分是素数的筛选环节，所以时间的节省是很重要的，这也是Miller Rabin筛选法的可行之处。 Miller Rabin法的原理其实来源于费马小定理，它的内容很简单，为：若P是一个素数，且0ap,则有：。于是我们可以通过计算来判定整数n的素性。当d不等于1时，n不是素数；当d等于1时，n可能是素数。费马小定理在叙述形式上其实已经接近于抽象化的伪代码了，我们只需要在实际的控制程序中，将之适当翻译就可以了。 但是使用费马小定理之上的理论，所筛选出的伪素数确实为素数的可能性，仅是“可能性相当大”，并不完全等同于素数。实际上，有些合数也满足费马小定理的条件，这些和数被称做Carmichael数。 【