七讲RSA和Rabin算法上

1、第七讲 rsa和rabin算法(上) diffie和hellman提出了建立公钥密码系统的可能性。但是，他们并没有提出公钥密码算法。接下来的几年，一些公钥密码算法相继被提出。其中最为成功的依赖大整数分解困难性的公钥密码算法于1977年由rivest，shamir，和adleman提出。这也就是我们熟知的rsa算法。 虽然经过长期的密码分析并不能证明也不能否定rsa的安全，但是这也无疑给算法的安全性一定承诺。rabin提出了一个基于计算模合数平方根困难的公钥密码算法。rabin的工作在理论上具有重要价值，这是因为rabin算法的安全性等价于大整数分解困难问题。 攻击者攻击公钥密码系统的基本目标是

2、针对特定实体可以系统的从密文消息恢复出明文消息。如果能实现这一目标，就说公钥密码系统被破译。一个更具破坏性的目标是恢复出秘密密钥。 可以想到的攻击形式有选择密文攻击，也就是攻击者选择密文消息，之后以某种手段得到其所对应的明文消息。 (1) (冷漠)选择密文攻击。 (2) 适应性选择密文攻击。 注意这里讲到的公钥密码算法都是假定发送消息者已经得到接受者一份真实的公开密钥拷贝。现实中有许多技术保障真实公开密钥分配，包括：在可信信道上交换密钥，使用可信公开文件，使用在线可信服务器或使用离线服务器和证书。 这一讲的公钥密码方案假定明文消息都是以某个固定比特长度被加密。如果消息明文的长度超过规定长度，需

3、要将其按规定长度分组。为了提供对非法控制分组(例如，重新排序)的防护，可以使用密码分组链接(cbc)模式。本讲提要q rsa加密算法q rsa加密的执行q rsa加密的安全1 rsa加密算法1.1 加密。的秘密密钥为；，的公开密钥为。满足，算法计算唯一的整数使用扩展。，满足最大公约数，选择一个随机的整数。和计算基本相等。两个素数的长度，和的素数不同产生两个大随机做如下步骤：每个实体钥。的公开和对应的秘密密摘要：每一个实体产生公钥加密的密钥产生daenadeddeeeqpqpnqpa )( (5) (mod 1 1euclidean (4)1 = )( 1 (3)1) 1)( ( = = (2)

4、 )( (1) rsa rsa 1 1 算法算法1.1 加密 (续)。恢复明文消息使用秘密密钥应该做如下操作：，恢复明文消息为了从密文消息。给发送密文消息。计算之间的整数。，表示为在将明文消息。，的真实公开密钥得到做如下步骤：解密。实体，给实体加密一条明文消息摘要：实体公钥加密) mod( (1) (4) mod( (3)10 (2) ( (1) rsa ncm damcacnmcnmenabaambde解密.解密.加密.加密.算法2算法2 1.1 加密 (续)。有因此，在所有情况下。都同余这是因为两边模确，则上面的同余式依然正，另一方面，如果。得到并在两边乘上在同余式两边同时乘幂。小定理，则

5、依据，现在，如果。满足整数，因此存在一个由于) (mod 0 = )() (mod 1)( )1(mod fermat1 = ) ( +1 )(mod 11)1)(+11pmmpppmpmmmqkpmpmkd =ek dedeqpkp . . 证明解密过程正确证明解密过程正确1.1 加密 (续)。也就是，。我们有是不同的素数，因此，和最后，由于。有依据同样的理由，我们) (mod )() (mod ) (mod nmmcnmmqpqmmdeddede1.1 加密 (续)通常有相同的规模。和通常十分小，因此数值，约数为随机选择，则最大公和如果速度。然而，因而获得更快的解密小的解密指数可望得到一个

6、的一个因子。使用是们可以看出。我密钥产生中用来替代以在可从前面的证明可以看出常常被称为通用指数。表示最小公倍数，这里，数值qpqpdqpqp 1) 1( 1)1)( = rsa 11= 评论.评论.1.2 例子。计算，要解密。并将其发送给，计算使用模幂算法，实体要加密一条消息。的秘密密钥是，而，的公开密钥是对。满足算法找到扩展并且使用选择。和计算，并且和选择两个素数实体5234673 6012707) (mod 3650502 ) (mod 36505026012707) (mod5234673 ) (mod 5234673 = 422191 = 3674911) = 6012707 = (

7、) (mod 1 422191 = euclidean 3674911 = 6007800 = 1)1)( = 6012707 = = 2551 =2357 = 4221913674911ncmac anmcbmdae nadedeaqpqpnqpade解密.解密. 加密.加密.密钥产生.密钥产生.例子1例子12 rsa 加密的执行 2.1 素性测试 存在一个奇妙的事实，就是分解大整数虽然十分困难但测试整数的素性并不困难。也就是说证明一个数为合数要比分解它容易的多。我们知道很多大整数是合数但却并不能分解它们。 2.1 素性测试 (续)的一个伪素数。对基是，则我们说是合数并且如果。是素数。是合数

8、则，如果。计算。，随机选择一个整数是素数或合数的判断。输出：。和一个安全参数输入：一个奇整数素性测试annannnrnarnaatintnnn ) 1(mod #)return( (2)return( 1 (1.3) (mod (1.2)2 2 (1.1):following thedo to1 from for (1) 1 3 fermat 11算法3算法32.2 模幂。，则如果。输出：。以及一个正整数，输入：整数从左向右二进制算法)(return (3)(mod 1 (2.2)(mod (2.1):following thedo 0 down to from for (2)1= (1) (

9、mod)( = 2011angaa = bnaa atiangbbbbbngibtt算法4算法43 rsa加密的安全3.1 安全参数，d p，q 。，式可得因此，我们按照求根公。依据根与系数的关系有。和因此，我们知道。注意。和，就可以迅速找到和。如果我们知道是两个不同素数的乘积假定24) 1() 1( )( )( ) 1 ( 1) 1)(1(1 222nnnqpqxpxqpxqpxnxnxqpqpqpqpqpnqpnqpn 证明.证明.事实1事实13.1 安全参数，d p，q (续)的分解方法可以使用。通用指数因此，后面讲到的使用。有，以看到对任何，我们可的一个倍数，也就是是。由于率分解，我们

10、将以非常高的概，满足，对于所有一个通用指数果有讨论中，我们将看到如在接下来对分解方法的。高的概率分解则我们将可以以非常，和如果我们知道参数 ) (mod 1)( 1)(11 ) 1(mod1)(0 1naanakdede nnananedkde事实2事实23.2 关于整数分解尺寸差别。取上通常需要有些许的的两个素数选组成模在可以发现分解。因此，步，则需要计算会非常有效。如果情况下的两个素数非常接近的分解方法在直到发现平方为止。，也就是计算的分解。就能给出。这样写成两个平方之差：是将很慢。这种方法的思路情况下速度也分解方法，在大多数的法称做种方种方法显然太慢。另一但是在大多数情况下这，去除的办法

11、是用所有素数简单的分解整数nqpqpnnnnnyxyxnyxnnnnpnrsa /2| fermat 21 )(fermat22223.2.1 指数分解方法的一个非平凡因子。是，是合数。进一步，我们知道，但，由于平凡因子。的一个非就是因此，由于矛盾。这又与假设，则并且整除由于。假定设知这种情况不会发生。由假则，。如果，令的一个非平凡因子。给出，大公约数为合数。进一步最，则，但是满足和数为整数并且假定存在整令35 535)2(1235 5)3 (mod212 35) (mod212 1 ) (mod) (mod1)( 1) (mod ) ( ) () (mod) (mod 222222 例子2例

12、子2证明.证明. 基本原理1基本原理1ndndnyxnyxdyxyxyxndnyxndnyxdnnyxnnyxnyxyxn3.2.1 指数分解方法 (续)的一个非平凡因子。给出，则，但是，我们有。如果对于某个验另一个，则停止并实，我们有。如果对于某个个，则停止并实验另一。如果连续定义并且对于。令，的一个因子，因此假定，我们可以得到，如果。，机整数是个奇数。选择一个随，这里可以写。，有的整数，所有满足，对于数假定我们有一个通用指nnynynyuanyuanynyykunaynannanaammrrnaanaruuuuuumkr )1( ) (mod 1) (mod 1) (mod 1) (mod

13、 1) (mod 10 ) (mod 1)(1)(222 = ) (mod 11)( 0 10210 通用指数分解方法通用指数分解方法3.2.1 指数分解方法 (续)的一个非平凡因子。给出，则，但是，我们有如果对于某个，则分解失败。，我们有果对于某个，则分解失败。如。如果连续定义并且对于令是奇数。，这里。写满足数和一个整假定我们有一个指数nnynynyunyunynyykunaymmrnaaruuuuuumkr)1( ) (mod 1) (mod 1 ) (mod 1 ) (mod 1 ) (mod 10) (mod 2 =) (mod 1 0 10210 指数分解方法指数分解方法3.2.1

14、指数分解方法 (续)。分解整数方法有非常大的可能性，那么这一和足算法要求的以有意义的方法发现满果我们能，因此，方法失效。如但是这种情况下都是满足条件的。，则任何一个如果我们选定并不实用。因此，这一方法实际上的，况下，找到是十分困难用指数的问题。一般情决如何找到一个通。但是，我们并没有解分解整数以方法有非常高的概率可事实上，通用指数分解nrayran 11 (2) (1)0 评述.评述.3.2.2 pollard的p1算法种情况不太可能发生。因子时，这有至少两个不同大素数方法失败，但是如果，这时候。当然，也可能，则，如果。因此，小定理而有，因为，足满，并且对于任何平滑的，则是因子，满足的一个素数

15、是如果。有素数这里乘积实际包含了所，。这样，因此有，则的最小公倍数。如果幂是所有素数是一个平滑界。令令算法的基本思想如下。的 ) 1(= ) (mod 1fermat1 = )(1- 1 ln/lnlnln)()( 1 pollardlnlnnd=np|dnadpapaa|qpbpn pbq qq =qnlnqlnqnbqbpqqqnbql3.2.2 pollard的p1算法 (续)。，则失败终止算法。否则，或如果。，计算。计算。计算做如下操作。对于每个素数。则，如果。，并计算，随机选择一个整数。选择一个平滑界。的一个非平凡因子输出：。合数一个非单一素数乘幂的输入：算法分解整数的)(retur

16、n 1 (5)1( (4) (mod (3.2)lnln (3.1) (3)(return 2 )( 12 (2) (1) 1 pollard dd=nd=nad=naaqnl =bq ddnad=naabdnnplq算法5算法53.2.2 pollard的p1算法 (续)根据具体情况来确定。的实际值常常需要当慢。对，算法执行速度就会相大的择一个非常会非常低。如果我们选非常快但是成功的几率，则算法执行速度将会平滑界如果我们选择一个小的重新执行算法。的平滑界择一个更小。同时，我们还可以选使用指数分解方法分解这给了我们一个机会。满足我们得到了一个值，这种情况下，我们并不是一无所获事实上，如果bbb

17、bnnarndr (2) ) (mod1 (1)评述.评述.3.2.2 pollard的p1算法 (续)不平滑。对而平滑对。这里而注意。数这两个因子实际上是素和的两个非平凡因子是。，现在我们计算。，；，；，；，；，；，；，；，的值：和，的中间变量步的每一次循环过程中的第们列出在执行算法。接下来我，并计算，整数我们选择一个平滑界的一个非平凡因子。算法找到的使用19 1 19 1601 3 2 = 3606 =1115 3 2 = 5280 = 1)( 36075281 =5281 = )1(554506= 554506 51911406961517132711546 1396853556 11

18、152145868 7 1693722310 51355588915 3 229324424 2351 = ) 3( 3 19190485671 pollard 5qp qpq=n/p = pnndalqalqalqalqalqalqalqalqa lqna=b=n=p 例子3例子33.2.3 二次域筛法。我们得到矩阵。，二次域筛法思想00102200002001051000000100010026003000201011010210000500142623397807717078196419095 93983837523) (mod1375142623837523) (mod13523397

19、3837523) (mod19280773837523) (mod113217078 3837523) (mod13319643837523) (mod19131152190953837523) 19(mod5939822225222623222252本就是二次域筛法。上述方法的一个改进版所有小素数的乘积。系主要步骤是产生剩余关。，和，和，但是，因此，我们有，我们能进一步发现222222222222323223322662 #1093)3837523 177451147907(1774511479071093)383752325867052230387(25867052230387)38375

20、23 (mod2470003590523 2470003590523)31753()142629641 ()913111532()170789641909519398()913152(9131523397)80779398(x3.2.3 二次域筛法 (续)3.2.4 整数分解的进展的量。于趋进无穷大时其趋进表示一个当这里，需要的时间复杂度为模在分解围。且超出了课程的范具体的算法十分复杂并。法是数域筛法目前已知最快的分解算0 (1) rsanfs (nfs)3231)lnln()(ln)1(92291(no = enln/nn + o.3.3 小加密指数 e。，满足三个同余式，解余定理得到一个，

21、因此可以根据中国剩，到上得攻击者可以在公共信道这些模是两两互素，而。由于，这里，将发送，则是，而他们的加密指数都，他们的公开模为给三个实体希望发送同一条消息一个实体如果。同小加密指数。一组实体可能选择相例如，数们希望选择小的加密指为了改进加密效率，我) (mod) (mod) (mod 0321 ) (mod3 3 3322113213213321ncxncxncxnnnxxccc i=nmcae=nnnmaee=eii3.3 小加密指数 e (续)次方根得到。的计算就可以通过简单，则密文因为如果时同样存在问题，这是加密小消息的情形。小加密指数在用在同一消息加密群发使这样的小加密指数不能。因此

22、，消息恢复出明文的三次方，攻击者可以计算整数。因此，通过就必然有，由于ecnmcmnme = mxx=mnnnme/e) (mod 3 1332133.4 小解密指数d系统的方法。在有效攻击，就存示只要结论的进一步改进，显给出了对和年，。有效算法计算，就存在满足，。给定，假定是素数满足和，这里令发现：年，而，来改善解密的效率。然指数望选择小的解密的情况一样，我们也希和加密指数rsawienerdurfeeboneh 2000)(mod1 )( 3 2 wiener 1990 292. 025. 0ndddeen/ndqpqqpqpnde3.5 乘法特性。的适应性选择密文攻击加密如下的针对的同态

23、特性。这将导致这有时也被称做。密文消息就是的消息换句话说，对应于明文。密文消息。可以观察到分别是它们的加密和，并且令为两个不同的明文消息和令rsarsa ) (mod ) (mod ) (mod )( rsa 21212121212121ncccnmmmnccmmmmccmmeee3.5 乘法特性 (续)得到明文消息。攻击者可以计算，。由于将为攻击者计算后，。在接到并计算的整数，通过选择一个随机息攻击者可以隐藏密文消本身以外。了密文消息击者提供任意密文，除可以帮助解密攻。假定密文消息的望解密一条送给实体假定一个主动攻击者希)(mod ) (mod )()( ) (mod )( ) (mod ) (mod 1 nxmmnxmxccmnc macnxccxccanmcadedddee3.5 乘法特性 (续)。返回给将不会解密，因为性选择密文攻击将失败以上描述的适应不符合格式