第七讲 RSA和Rabin算法(上)

第七讲RSA和Rabin算法(上)Diffie和Hellman提出了建立公钥密码系统的可能性。但是，他们并没有提出公钥密码算法。接下来的几年，一些公钥密码算法相继被提出。其中最为成功的依赖大整数分解困难性的公钥密码算法于1977年由Rivest，Shamir，和Adleman提出。这也就是我们熟知的RSA算法。虽然经过长期的密码分析并不能证明也不能否定RSA的安全，但是这也无疑给算法的安全性一定承诺。Rabin提出了一个基于计算模合数平方根困难的公钥密码算法。Rabin的工作在理论上具有重要价值，这是因为Rabin算法的安全性等价于大整数分解困难问题。攻击者攻击公钥密码系统的基本目标是针对特定实体可以系统的从密文消息恢复出明文消息。如果能实现这一目标，就说公钥密码系统被破译。一个更具破坏性的目标是恢复出秘密密钥。可以想到的攻击是选择密文攻击，也就是攻击者选择密文消息，之后以某种手段得到其所对应的明文消息。(1)(冷漠)选择密文攻击。(2)适应性选择密文攻击。注意这里讲到的公钥密码算法都是假定发送消息者已经得到接受者一份真实的公开密钥拷贝。现实中有许多技术保障真实公开密钥分配，包括：在可信信道上交换密钥，使用可信公开文件，使用在线可信服务器或使用离线服务器和证书。这一讲的公钥密码方案假定明文消息都是以某个固定比特长度被加密。如果消息明文的长度超过规定长度，需要将其按规定长度分组。为了提供对非法控制分组(例如，重新排序)的防护，可以使用密码分组链接(CBC)模式。本讲提要RSA加密算法RSA加密的执行RSA加密的安全1RSA加密算法1.1加密。的秘密密钥为；，的公开密钥为。满足，，算法计算唯一的整数使用扩展。，满足最大公约数，，选择一个随机的整数。和计算基本相等。两个素数的长度，和的素数不同产生两个大随机做如下步骤：每个实体钥。的公开和对应的秘密密摘要：每一个实体产生公钥加密的密钥产生dAenAφdeφddφeφeeqpφqpnqpA)((5))(mod11Euclidean(4)1=)(1(3)1)1)((==(2))((1)RSARSA1算法1.1加密(续)。恢复明文消息使用秘密密钥应该做如下操作：，恢复明文消息为了从密文消息。给发送密文消息。计算之间的整数。，表示为在将明文消息。，的真实公开密钥得到做如下步骤：解密。实体，给实体加密一条明文消息摘要：实体公钥加密)mod((1)(4))mod((3)1][0(2))((1)RSAncmdAmcAcnmcnmenABAAmBde解密.加密.算法21.1加密(续)。有因此，在所有情况下。都同余这是因为两边模确，则上面的同余式依然正，，另一方面，如果。得到并在两边乘上在同余式两边同时乘幂。小定理，，则依据，现在，如果。满足整数，因此存在一个由于)(mod0=)()(mod1)()1(modFermat1=)(+1)(mod11)1)((+11pmmpppmpmmmqkpmpmφkd=ekφdedeqpkp.证明解密过程正确1.1加密(续)。也就是，。我们有是不同的素数，因此，和最后，由于。有依据同样的理由，我们)(mod)()(mod)(modnmmcnmmqpqmmdeddede1.1加密(续)通常有相同的规模。和通常十分小，因此数值，约数为随机选择，则最大公和如果速度。然而，，因而获得更快的解密小的解密指数可望得到一个的一个因子。使用是们可以看出。我密钥产生中用来替代以在可从前面的证明可以看出常常被称为通用指数。表示最小公倍数，，这里，数值λφqpqpdλφλqpφλqpλ1)1(1)1)((=RSA[]1]1[=评论.1.2例子。计算，要解密。并将其发送给，计算使用模幂算法，实体要加密一条消息。的秘密密钥是，而，的公开密钥是对。满足算法找到扩展并且使用选择。和计算，并且和选择两个素数实体52346736012707)(mod3650502)(mod36505026012707)(mod5234673)(mod5234673=422191=3674911)=6012707=()(mod1422191=Euclidean3674911=6007800=1)1)((=6012707==2551=2357=4221913674911ncmAcAnmcBmdAenAφdedeAqpφqpnqpAde解密.加密.密钥产生.例子12RSA加密的执行2.1素性测试存在一个奇妙的事实，就是分解大整数虽然十分困难但测试整数的素性并不困难。也就是说证明一个数为合数要比分解它容易的多。我们知道很多大整数是合数但却并不能分解它们。2.1素性测试(续)的一个伪素数。对基是，则我们说是合数并且如果。是素数。是合数则，如果。计算。，随机选择一个整数是素数或合数的判断。输出：。和一个安全参数输入：一个奇整数素性测试annannnrnarnaatintnnn)1(mod#)Return((2))return(1(1.3))(mod(1.2)22(1.1):followingthedoto1fromFor(1)13Fermat11算法32.2模幂。。，则如果。。。输出：。以及一个正整数，输入：整数从左向右二进制算法)(Return(3))(mod1(2.2))(mod(2.1):followingthedo0downtofromFor(2)1=(1))(mod)(=2011AngAA=bnAAAtiAngbbbbbngibtt算法43RSA加密的安全3.1安全参数，dp，q。，式可得因此，我们按照求根公。依据根与系数的关系有。和因此，我们知道。注意。和，就可以迅速找到和。如果我们知道是两个不同素数的乘积假定24)1()1())(()()1(1)1)(1(1222nnnqpqXpXqpXqpXnXnXqpqpqpqpqpnqpnqpn证明.事实13.1安全参数，dp，q(续)的分解方法可以使用。通用指数因此，后面讲到的使用。有，以看到对任何，我们可的一个倍数，也就是是。由于率分解，我们将以非常高的概，满足，，对于所有一个通用指数果有讨论中，我们将看到如在接下来对分解方法的。高的概率分解则我们将可以以非常，和如果我们知道参数)(mod1)(1)(11)1(mod1)(01naanakdedennananedkde事实23.2关于整数分解尺寸差别。取上通常需要有些许的的两个素数选组成模在可以发现分解。因此，步，则需要计算会非常有效。如果情况下的两个素数非常接近的分解方法在直到发现平方为止。，，，也就是计算的分解。就能给出。这样写成两个平方之差：是将很慢。这种方法的思路情况下速度也分解方法，在大多数的法称做种方种方法显然太慢。另一但是在大多数情况下这，去除的办法是用所有素数简单的分解整数nqpqpnnnnnyxyxnyxnnnnpnRSA/2||Fermat21))((Fermat22223.2.1指数分解方法的一个非平凡因子。是，是合数。进一步，我们知道，但，由于平凡因子。的一个非就是因此，，，由于矛盾。。这又与假设，则并且整除由于。。假定设知这种情况不会发生。由假则，。如果，令的一个非平凡因子。给出，大公约数为合数。进一步最，则，但是满足和数为整数并且假定存在整令35535)2(12355)3(mod21235)(mod2121)(mod)(mod1))((1)(mod)()()(mod)(mod222222例子2证明.基本原理1ndndnyxnyxdyxyxyxndnyxndnyxdnnyxnnyxnyxyxn3.2.1指数分解方法(续)的一个非平凡因子。给出，则，，但是，我们有。如果对于某个验另一个，则停止并实，我们有。如果对于某个个，则停止并实验另一。如果连续定义并且对于。令，的一个因子，因此假定，我们可以得到，如果。，机整数是个奇数。选择一个随，这里可以写。，有的整数，所有满足，对于数假定我们有一个通用指nnynynyuanyuanynyykunaynannanaammrrnaanaruuuuuumkr)1()(mod1)(mod1)(mod1)(mod1)(mod10)(mod1)(1)(222=)(mod11)(010210通用指数分解方法3.2.1指数分解方法(续)的一个非平凡因子。给出，，则，但是，我们有如果对于某个，则分解失败。，我们有果对于某个，则分解失败。如。如果连续定义并且对于令是奇数。，这里。写满足数和一个整假定我们有一个指数nnynynyunyunynyykunaymmrnaaruuuuuumkr)1()(mod1)(mod1)(mod1)(mod1)(mod10)(mod2=)(mod1010210指数分解方法3.2.1指数分解方法(续)。分解整数方法有非常大的可能性，那么这一和足算法要求的以有意义的方法发现满果我们能，因此，方法失效。如但是这种情况下都是满足条件的。，则任何一个如果我们选定并不实用。因此，这一方法实际上的，况下，找到是十分困难用指数的问题。一般情决如何找到一个通。但是，我们并没有解分解整数以方法有非常高的概率可事实上，通用指数分解nrayran11(2)(1)0评述.3.2.2Pollard的p1算法种情况不太可能发生。因子时，这有至少两个不同大素数方法失败，但是如果，这时候。当然，也可能，则，如果。因此，小定理而有，因为，足满，并且对于任何平滑的，则是因子，满足的一个素数是如果。有素数这里乘积实际包含了所，。这样，因此有，则的最小公倍数。如果幂是所有素数是一个平滑界。令令算法的基本思想如下。的)1(=)(mod1Fermat1=)(1-1ln/lnlnln)()(1Pollardlnlnnd=np|dnadpapaa|QpBpnpBqqQ=qnlnqlnqnBQBpQQqnBql3.2.2Pollard的p1算法(续)。，则失败终止算法。否则，或如果。，计算。计算。计算做如下操作。对于每个素数。则，如果。，并计算，，随机选择一个整数。选择一个平滑界。的一个非平凡因子输出：。合数一个非单一素数乘幂的输入：算法分解整数的)(return1(5))1((4))(mod(3.2)lnln(3.1)(3))(return2)(12(2)(1)1Pollarddd=nd=nad=naaqnl=Bqddnad=naaBdnnplq算法53.2.2Pollard的p1算法(续)根据具体情况来确定。的实际值常常需要当慢。对，算法执行速度就会相大的择一个非常会非常低。如果我们选非常快但是成功的几率，则算法执行速度将会平滑界如果我们选择一个小的重新执行算法。的平滑界择一个更小。同时，我们还可以选使用指数分解方法分解这给了我们一个机会。满足我们得到了一个值，这种情况下，，我们并不是一无所获事实上，如果BBBBnnarndr(2))(mod1(1)评述.3.2.2Pollard的p1算法(续)不平滑。对而平滑对。这里而注意。数这两个因子实际上是素和的两个非平凡因子是。，现在我们计算。，，；，，；，，；，，；，，；，，；，，；，，的值：和，，的中间变量步的每一次循环过程中的第们列出在执行算法。接下来我，，并计算，整数我们选择一个平滑界的一个非平凡因子。算法找到的使用19119160132=3606=111532=5280=1)(36075281=5281=)1(554506=55450651911406961517132711546139685355611152145868716