密码学基础课件：第十四讲 RSA实现

1、第十四讲 RSA实现RSA实现RSA分析回顾大整数的加，减，乘，除，欧几里得求逆已知a,b互素，必然有ax+by=1.(gcd(a,b)那么ax+by (mod b) = 1 (mod b)ax=1 mod bx就是a的逆在模运算下，a/b mod n本质上是计算ab-1 mod n，模运算下的除法不是普通除法运算得到商后再取模整数的素性判断如果一个整数的因数只有1和其自身，称该整数位素数1。朴素的判断方法：对于n，判断2,.n(1/2)中的素数是否能够整除n2。费马定理：如果n是素数，那么对于a in Z_n*，a(n-1) =1 mod n当然，如果a(n-1) =1 mod n, n不一

2、定就是素数，因为可能存在b(n-1) !=1 mod n, b in Z_n*基于费马定理的素性测试指定随机测试的次数T随机选择a in Z_n*，测试a(n-1) =1 mod n是否成立，不成立返回不是素数，成立则继续测试，直到达到要求的次数T。如果T次测试都满足，返回是素数。但是。存在Carmichael数，满足所有的a in Z_n*， a(n-1) =1 mod n，但是是合数。即便如此。如何计算a(n-1) =1 mod n？例如n-1=14,展开为2进制是1110，即23+22+2所以a14=a(23)*a(22)*a(2)即：a2*(a2)2*(a2)2)2所以可以这么算(从低

3、位向高位)：pow=1; for(;i 0) if (n & 1) / n & 1 等价于 (n % 2) = 1 pw *= x; x *= x; n = 1; / n = 1 等价于 n /= 2 MillerRabin素性测试事实1：如果n是素数，那么 x2=1 mod n仅有两个解。n|(x+1)(x-1)，如果n是素数，n|x+1或n|x-1，所以x同余于1或-1。例如：x2 =1 mod 15，15|(4+1)(4-1)，但15不是5或者3的因子MillerRabin素性测试-2事实2：费马小定理，n素，则a(n-1) =1 mod n事实3：如果n素，那么对a(n-1)连续开方，

4、计算A_(s-1)=a(n-1/2),A_(1)=a(2d),A_0=ad，其中d为奇数；n-1=2s*d该序列或者得到A_i=-1终止，或者得到ad=1终止（ad=-1的情况包含在i=s的情况中）MillerRabin素性测试-2事实3的逆反命题构成MR素性测试的基础If we can find an a such thatad notequiv 1 mod nanda2rd notequiv -1 mod nfor all 0 r s 1, then n is not prime.WiKi伪代码示例Input: n 3, an odd integer to be tested for pr

5、imality;Input: k, a parameter that determines the accuracy of the testOutput: composite if n is composite, otherwise probably primewrite n 1 as 2rd with d odd by factoring powers of 2 from n 1WitnessLoop: repeat k times: pick a random integer a in the range 2, n 2 x ad mod n if x = 1 or x = n 1 then

6、 do next WitnessLoop repeat r 1 times: x x2 mod n if x = n 1 then do next WitnessLoop return composite/这里的执行条件是在任意一次测试中，如果r-1次都没有等n-1，满足逆反命题，返回合数。return probably prime/k次测试完成，每一次都没有返回合数，执行到这一步就返回素数，正确率1-(1/4)k代码的简单分析x ad mod n if x = 1 or x = n 1 then do next WitnessLoop计算最低幂次,然后可以用乘法根据事实3,可以判断为素数,所

7、以换新的测试数 repeat r 1 times: x x2 mod n if x = n 1 then do next WitnessLoop在其余的s-1次计算中，如果任何一次是n-1，那么根据事实3，可以判断为素数，更换新的测试数RSA分析分解模数n在理论上，RSA的安全性取决于模n分解的困难性，但数学上至今还未证明分解模就是攻击RSA的最佳方法。常用分解算法：Pollard p-1算法Pollard 算法Dixon的随机平方算法二次筛法椭圆曲线分解算法(ECM)数域筛法ECM是将pollard“p-1”法推广到椭圆曲线群上 分解现状RSA-129： Rivest等最初悬赏$100的RS

8、A-129，已由包括五大洲43个国家600多人参加，用1600台机子同时产生820条指令数据，通过Internet网，耗时8个月，于1994年4月2日利用二次筛法分解出为64位和65位的两个因子，原来估计要用4亿亿年。所给密文的译文为“这些魔文是容易受惊的鱼鹰”。 RSA-130于1996年4月10日利用数域筛法分解出来。RSA-140 (465-bit）于1999年2月分解出来（ 185 networked computers ）。RSA-154(512bit)于1999年8月分解出来。RSA-160, 2003.01 (http:/www.loria.fr/zimmerma/records

9、/rsa160)RSA-174(576bit), 2003. 12 RSA-194(640-Bit), 2005. 11RSA-768：RSA-768 has 768 bits (232 decimal digits), and was factored on December 12, 2009 by Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thom, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos,

10、Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul ZimmermannRSA-768 = 12301866845301177551304949583849627207728535695953347921973224521517264005 07263657518745202199786469389956474942774063845925192557326303453731548268 50791702612214291346167042921431160222124047927473779408066535141959745

11、985 6902143413RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793 878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666 511279233373417143396810270092798736308917/2010/006从n若能求出(n)，则可求得p1, p2，因为n(n)1=p1p

12、2(p11)(p21)1=p1p2 而 ，已证明，求(n)等价于分解n的困难。 计算欧拉函数(n)Boneh and Durfee have improved the bound to d n0.292. 迭代攻击法： Simmons和Norris曾提出迭代或循环攻击法。例如，给定一RSA的参数为(n, e, y)=(35, 17, 3)，可由y0=y=3计算y1=317=33 mod 35。再由y1计算y2=y117=3 mod 35，从而得到明文x=y1=33 mod 35。一般对明文x加密多次，直到再现x为止。Rivest证明，当p11和p21中含有大素数因子，且n足够大时，这种攻击法成

13、功的概率趋于0。对 RSA的其他攻击若很多人共用同一模数n，各自选择不同的e和d，这样实现当然简单，但是不安全。若消息以两个不同的密钥加密，在共用同一个模下，若两个密钥互素(一般如此)，则可用任一密钥恢复明文。 设e1和e2是两个互素的不同密钥，共用模为n，对同一消息x加密得 y1=xe1 mod n, y2=xe2 mod n。分析者知道n, e1, e2, y1和y2。因为(e1, e2,)=1，所以有r e1,+s e2=1。由Euclidean算法可计算 (y1)r y2s=x mod n 还有两种攻击共用模RSA的方法，用概率方法可分解n和用确定性算法可计算某一用户密钥而不需要分解n

14、。 公用模攻击采用小的e可以加快加密和验证签字的速度，且所需的存储密钥空间小，但若加密钥e选择得太小，则容易受到攻击。令网中三用户的加密钥e均选3，而有不同的模n1, n2, n3，若有一用户将消息x传给三个用户的密文分别为 y1=x3 mod n1 x n1y2=x3 mod n2 x n2y3=x3 mod n3 x n3 一般选n1, n2, n3互素(否则，可求出公因子，而降低安全性)，利用中国余定理，可从y1, y2, y3求出 y=x3 mod (n1 n2 n3)。 由xn1, xn2, xn3，可得x3 n1 n2, n3，故有 低加密指数攻击 若x后加时戳 y1=(2t x+

15、t1)3 mod n1y2=(2t x+t2)3 mod n2y3=(2t x+t3)3 mod n3 t是t1, t2, t3的二元表示位数，可防止这类攻击。上述攻击扩展为k个用户，即将相同的消息x传给k个人，只要，采用低指数亦可有效攻击。因此，为抗击这种攻击e必须选得足够大。一般，e选为16位素数。 对短的消息，可用随机数字填充，以防止低加密指数攻击。定时攻击法：定时(Timing)攻击法由P. Kocher提出，利用测定RSA解密所进行的模指数运算的时间来估计解密指数d，而后再精确定出d的取值。R. Rivest曾指出，这一攻击法可以通过将解密运算量与参数d无关挫败。另外还可采用盲化技术

16、，即先将数据进行盲化，再进行加密运算，而后做去盲运算。这样做虽然不能使解密运算时间保持不变，但计算时间被随机化而难于推测解密所进行的指数运算的时间。 侧信道攻击为了保证安全，必须仔细选择各参数。 （1）n的确定 n=p1p2，p1与p2必须为强素数。 强素数p的条件：（a）存在两个大素数p1和p2，p1|(p1)，p2|(p1)。（b）存在4个大素数r1, s1, r2及s2，使r1|(p11), s1|(p11), r2|(p21), s2|(p21)。称r1, r2, s1和s2；p1和p2为二级素数。 RSA的参数选择 p1与p2之差要大。若p1与p2之差很小，则可由n=p1p2估计(p

17、1p2)/2=n1/2，则由(p1p2)/2)2n=(p1p2)/2)2。上式右边为小的平方数，可以试验给出p1, p2的值。 p11与p21的最大公因子要小。在惟密文攻击下，设破译者截获密文y=x e mod n。破译者做下述递推计算： xi=xi-1e mod n=(xe)i mod n若ei=1 mod (n)，则有xi=x mod n，且ei+1=e mod (n)，即xi+1=x。若i小，则由此攻击法易得明文x。由Euler定理知，i=(p11)(p21)，若p11和p21的最大公因子小，则i值大，如i=(p11)(p21)/2，此攻击法难于奏效。 p，q要足够大，以使n分解在计算上不可行。（2）e的选取原则: (e, (n)=1 e不可过小：若e小，x小，易遭低指数攻击 选e在mod (n)中的阶数，