1、5.1 公钥密码体制的基本原理 5.2 背包算法 5.3 RSA算法*5.4 Rabin算法 5.5 ElGamal算法 5.6 椭圆曲线算法 习题 5.1 公钥密码体制的基本原理公钥密码体制的基本原理5.1.1 公钥密码的基本思想公钥密码的基本思想运用诸如DES等经典密码系统进行保密通信时，通信双方必须拥有一个共享的秘密密钥来实现对消息的加密和解密，而密钥具有的机密性使得通信双方如何获得一个共同的密钥变得非常困难。通常采用人工传送的方式分配各方所需的共享密钥，或借助一个可靠的密钥分配中心来分配所需要的共享密钥。但在具体实现过程中，这两种方式都面临很多困难，尤其是在计算机网络化时代更为困难。1
2、976年两位美国密码学者W.Diffie和M.Hellman在该年度的美国国家计算机会议上提交了一篇名为“密码学的新方向（New Directions in Cryptography）”的论文，文中首次提出了公钥密码体制的新思想，它为解决传统经典密码学中面临的诸多难题提供了一个新的思路。其基本思想是把密钥分成两个部分：公开密钥和私有密钥（简称公钥和私钥），分别用于消息的加密和解密。公钥密码体制又被称为双钥密码体制（Asymmetric Cryptography System，非对称密码体制），与之对应，传统的经典密码体制被称为单钥密码体制（Symmetric Cryptography Syst
3、em，对称密码体制）。公钥密码体制中的公开密钥可被记录在一个公共数据库里或者以某种可信的方式公开发放，而私有密钥必须由持有者妥善地秘密保存。这样，任何人都可以通过某种公开的途径获得一个用户的公开密钥，然后进行保密通信，而解密者只能是知道相应私钥的密钥持有者。用户公钥的这种公开性使得公钥体制的密钥分配变得非常简单，目前常用公钥证书的形式发放和传递用户公钥(见7.3节)，而私钥的保密专用性决定了它不存在分配的问题(但需要用公钥来验证它的真实性，以防止欺骗)。公钥密码算法的最大特点是采用两个具有一一对应关系的密钥对k=(pk，sk)使加密和解密的过程相分离。当两个用户希望借助公钥体制进行保密通信时，
4、发信方Alice用收信方Bob的公开密钥pk加密消息并发送给接收方，而接收方Alice使用与公钥相对应的私钥sk进行解密。根据公、私钥之间严格的一一对应关系，只有与加密时所用公钥相对应的用户私钥才能够正确解密，从而恢复出正确的明文。由于这个私钥是通信中的收信方独有的，其他用户不可能知道，因此只有该收信方Bob才能正确地恢复出明文消息，其他有意或无意获得消息密文的用户都不能解密出正确的明文，达到了保密通信的目的。图5-1给出了公钥密码体制的基本流程。图5-1 公钥密码体制的基本流程5.1.2 公钥密码算法应满足的要求公钥密码算法应满足的要求基于图5-1 给出的公钥密码体制的基本流程，一个实际可用
5、的公钥密码体制(M，C，K，E，D)的基本要求如下：(1)对于K中的每一个公私钥对k=(pk，sk)，都存在E中的一个加密变换Epk:MC和D中的一个解密变换Dsk:CM，使得任意明文消息mM都能找到一个惟一的cC满足c=Epkm，且m=Dskc=DskEpkm；(2)对于任意的公私钥对k=(pk，sk)K，加密变换Epk和解密变换Dsk都是多项式时间可计算的函数，但由加密变换Epk推出解密变换Dsk在计算上是不可行的，或者说在知道公钥pk的情况下推知私钥sk是计算上不可行的。由上面的基本要求可以看出，公钥密码体制的核心在于加密变换与解密变换的设计。在密码算法中，加解密变换是互逆的，但条件(2
6、)说明在公钥密码体制中加解密变换不能简单地直接互推。上述条件表明公钥密码体制的加解密变换类似于陷门单向函数，因此可以利用陷门单向函数来构造公钥密码体制。所谓的陷门单向函数是一个可逆函数f(x)，满足对于定义域中的任何x，计算函数值y=f(x)都是容易的，但对几乎所有的x要由y=f(x)求x在计算上不可行(即使已经知道函数f(x)，除非知道某些辅助信息(称为陷门信息)。这里所说的“容易计算”是指函数值能在其输入长度的多项式时间内计算出来，比如若输入长度为n比特，求函数值的计算时间是na的某个倍数，则称此函数是容易计算的，否则就是不可行的，这里a是一个固定常数。针对公钥密码体制(M，C，K，E，D
7、)的基本要求，一个可行的公钥密码算法应该满足如下要求：(1)接收方Bob产生密钥对k=(pkB，skB)在计算上是容易的；(2)发送方Alice用收信方Bob的公钥pkB加密消息m产生密文在计算上是容易的；(3)接收方Bob用自己的私钥skB解密密文c，还原明文消息在计算上是容易的；mEcBpkcDmBsk(4)不仅攻击者由密文c和Bob的公钥pkB恢复明文m是计算上不可行的，而且攻击者由Bob的公钥pkB求解对应的私钥skB也是计算上不可行的；(5)一般情况下，加解密的次序可交换，即。mDEmEDBBBBskpkpksk公钥密码体制的思想完全不同于单钥密码体制，公钥密码算法的基本操作不再是单
8、钥密码体制中使用的代换和置换，公钥密码体制通常将其安全性建立在某个尚未解决(且尚未证实能否有效解决)的数学难题的基础上，并经过精心设计来保证其具有非常高的安全性。公钥密码算法以非对称的形式使用两个密钥，不仅能够在实现消息加/解密基本功能的同时简化了密钥分配任务，而且还对密钥协商与密钥管理、数字签名与身份认证等密码学问题产生了深刻的影响。可以说公钥密码思想为密码学的发展提供了新的理论和技术基础，是密码学发展史上的一次革命。下面分别给出常用公钥密码算法：背包算法、RSA公钥算法、Rabin算法、ElGamal算法、椭圆曲线密码的原理和算法分析。5.2 背包算法背包算法当W.Diffie和M.Hel
9、lman提出公钥密码体制的设想时，并没有给出一个具体的实例。直到两年后的1978年，由R.Merkle和M.Hellman给出了第一个公钥密码算法，这就是基于组合数学中背包问题(或者说是子集和问题)的背包公钥密码算法，也称为MH背包算法，简称背包算法。5.2.1 背包问题背包问题在组合数学中有一个背包问题：假设有一堆物品，体积各不相同，问能否从这堆物品中找出几个正好装满一个给定容量的背包？(假定物品之间不留空隙)记物品的体积分别为v1，v2，vn，背包的容量为C，则背包问题可表示为b1v1+b2v2+bnvn=C其中，bi(i=1，2，n)等于1或者0。bi=1表示第i个物品在背包中，bi=0
10、表示第i个物品不在背包中，称物品体积的序列(v1，v2，vn)为背包向量。理论上讲，通过检查背包向量V的所有子集，计算出每个子集的元素之和，总可找出一个子集作为背包问题的解，因此背包问题又称为子集和问题。然而长度为n的背包向量V的全体子集共有2n个，当n很大时，对全部2n个子集进行穷举式搜索是不可能的。事实上，背包问题是一类NP完全(NPC)问题，而目前还没有发现比穷举式搜索更好的NPC问题求解方法。幸运的是并非所有的背包问题都没有有效算法，有一类特殊的背包问题是容易求解的，这就是超递增背包问题。设V=(v1，v2，vn)是一个背包向量，若V满足即V中每一项都大于它前面所有项之和，则称V是一个
11、超递增向量，或者称序列v1，v2，vn是一个超递增序列，以V为背包向量的背包问题被称做超递增背包问题。比如，序列1，2，4，2n就是一个超递增序列。nivvijji,2,1,11超递增背包问题的解很容易通过以下过程找到：设背包容量为C，从右向左(从大到小)依次检查超递增背包向量V中的每个元素，以确定问题的解。若Cvn，则vn在解中，对应的bn应为1，并将C的值更新为C-vn；否则如果C32，得b6=1，更新C为43-32=11；C=118，得b4=1，更新C为11-8=3；C=32，得b2=1，更新C为3-2=1；C=1得b1=1，最后C减小到0。所以问题的解为110101。超递增背包问题是很
12、容易求解的。下面给出利用数论中的模乘运算将超递增序列变为非超递增序列的方法。选择满足如下条件的模数k和乘数t：即t与k互素，确保t在模k下的乘法逆元t-1存在。令 UtV mod kt(v1，v2，vn)mod k=(tv1 mod k，tv2 modk，tvn mod k)那么U是一个非超递增向量。1),gcd(,1ktvknii5.2.2 背包算法的描述背包算法的描述借助于背包问题中的超递增向量和相应的非超递增向量，可以构造一个公钥密码算法：背包算法。具体如下：私有密钥设置为将一个超递增向量V转换为非超递增向量U的参数t、t-1和k，公开密钥设置为非超递增向量U。具体的加/解密过程如下：(
13、1)加密变换：首先将二进制明文消息划分成长度与非超递增向量U长度相等的明文分组b1b2bn；然后计算明文分组向量B=(b1,b2,bn)与非超递增向量U=(u1,u2,un)的内积BU=b1u1+b2u2+bnun，所得结果为密文。(2)解密变换：先还原出超递增背包向量V=t-1U mod kt-1tV mod k，再将密文BU模k乘以t-1的结果作为超递增背包问题的背包容量，求解超递增背包问题，得到消息明文。例例5.2 设V=(1，3，7，13，26，65，119，267)是一个超递增背包向量，取模数k=523，乘数t=467，则t-1=28 mod 523。对V模k乘以t，计算出公钥：Ut
14、V mod k467(1,3,7,13,26,65,119,267)mod 523 (467,355,131,21,135,215)并对外公布U。假设发送方有一明文消息m=10101100，用公钥U对m加密得到密文：c=mU=(1,0,1,0,1,1,0,0)(467,355,131,318,113,21,135,215)=467+131+113+21 =732接收方利用公钥U与私钥t-1和k还原出超递增背包V，对密文c=732模k乘以t-1，得到ct-1mod k73228 mod 52320496 mod 523=99 以99作为背包的容量去解超递增背包问题：由99267得m8=0；由99
15、65得m6=1；由99-65=3426得m5=1；由34-26=87 得m3=1；由8-7=13得m2=0，m1=1。解密得到明文分组为10101100，即为原来的m。要解决类似例5.2这样的背包向量仅有8个分量的背包问题并不困难，甚至对非超递增的背包向量也是如此。但实用的背包向量至少应包含250个以上的分量，每个分量的大小一般要在200到400位，模数也应在100到200位之间。这些值可以使用随机序列发生器来生成。对于这样的背包算法，试图用穷举式搜索攻击来破译是无用的。5.2.3 背包算法的安全性背包算法的安全性背包算法利用难解的一般背包问题作为公开密钥，可以方便地对明文进行加密；而私有密钥
16、则利用易解的超递增背包问题给出一个解密的简单方法。那些不知道私钥的攻击者要想破译密文就不得不求解一个困难的背包问题，这在计算上看似是不可行的。背包算法提出两年后即被破解。破解的基本思想是不必找出真正的模数k和乘数t，也不用穷举式搜索背包向量的所有子集，而是找出一对任意的k和t，使得用公开的背包向量U模k乘t后能得到一个超递增向量。究其原因是Merkle-Hellman背包体制的公开密钥是由超递增向量变换而来的，虽然经过模乘置乱，但超递增向量内在的规律性并不能完全被隐藏，这就给攻击者留下了可乘之机。随后Merkle又提出了多次迭代背包体制，但最终也被破解。1984年Brickell最终证明了Me
17、rkle-Hellman背包体制的不安全性，并发现了一种算法可将难解的背包问题转化为易解的背包问题。背包算法是第一个使公钥密码体制成为现实的密码算法，它说明了如何将数学难题应用于公钥密码算法的设计。背包体制的优势是加解密速度很快，但它存在的不安全性使其不能用于商业目的。5.3 RSA算法算法数论里有一个大数分解问题：计算两个素数的乘积非常容易，但分解该乘积却异常困难，特别是在这两个素数都很大的情况下。基于这个事实，1978年美国MIT的三名数学家R.Rivest，A.Shamir和L.Adleman提出了著名的公钥密码体制：RSA算法。该算法以两个大素数的乘积作为算法的公钥来加密消息，而密文的
18、解密必须知道相应的两个大素数。迄今为止，RSA算法是思想最简单、分析最透彻、应用最广泛的公钥密码体制。RSA算法非常容易理解和实现，经受住了密码分析，密码分析者既不能证明也不能否定它的安全性，这恰恰说明了RSA具有一定的可信度。5.3.1 RSA算法的描述算法的描述基于大数分解问题，为了产生公、私钥，首先独立地选取两个大素数p和q(注：为了获得最大程度的安全性，选取的p和q的长度应该差不多，都应为长度在100位以上的十进制数字)。计算n=pq 和 (n)=(p)(q)=(p-1)(q-1)这里(n)表示n的欧拉函数，即(n)为比n小且与n互素的正整数的个数。随机选取一个满足1e(n)且gcd(
19、e，(n)=1的整数e，那么e存在模(n)下的乘法逆元d=e-1mod(n)，d可由扩展的欧几里得算法求得(附录A)。这样由p和q获得了三个参数：n、e、d。在RSA算法里，以n和e作为公钥，d作为私钥(注：p和q不再需要，可以销毁，但一定不能泄露)。具体的加/解密过程如下：(1)加密变换：先将消息划分成数值小于n的一系列数据分组，即以二进制表示的每个数据分组的比特长度应小于lbn。然后对每个明文分组m进行如下的加密变换来得到密文c：c=me mod n(2)解密变换：m=cd mod n。命题命题5.3.1 RSA算法中的解密变换m=cd mod n是正确的。证明：证明：数论中的欧拉定理指出
20、，如果两个整数a和b互素，那么a(b)1 mod b。在RSA算法中，明文m必与两个素数p和q中至少一个互素。不然的话，若m与p和q都不互素，那么m既是p的倍数也是q的倍数，于是m也是n的倍数，这与mn矛盾。由de1 mod(n)可知，存在整数k使得de=k(n)+1。下面分两种情形来讨论：情形一：m仅与p、q二者之一互素，不妨假设m与p互素且与q不互素，那么存在整数a使得m=aq，由欧拉定理可知mk(n)mod pmk(p)(q)mod p(m(p)k(q)mod p 1 mod p于是存在一个整数t使得mk(n)=tp+1。给mk(n)=tp+1两边同乘以m=aq得到mk(n)+1=tap
21、q+m=tan+m由此得cd=med=mk(n)+1=tan+mm mod n。情形二：如果m与p和q都互素，那么m也和n互素，有cd=med=mk(n)+1=mmk(n)m mod nRSA算法实质上是一种单表代换系统。给定模数n和合法的明文m，其相应的密文为c=me mod n且对于mm必有cc。RSA算法的关键在于当n极大时，在不知道陷门信息的情况下，很难确定明文和密文之间的这种对应关系。例例5.3 选取p=5，q=11，则n=55且(n)=40，明文分组应取为1到54的整数。如果选取加密指数e=7，则e满足1e(n)且与(n)互素，于是解密指数为d=23。假如有一个消息m=53197，
22、分组可得m1=53，m2=19，m3=7。分组加密得到711mod53 mod5537ecmn722mod19 mod5524ecmn733mod7 mod5528ecmn密文的解密为最后恢复出明文m=53197。2311mod37mod5553dcnm2322mod24mod5519dcnm2333mod28mod557dcnm5.3.2 RSA算法的安全性算法的安全性RSA算法的安全性完全依赖于对大数分解问题困难性的推测，但面临的问题是迄今为止还没有证明大数分解问题是一类NP问题。为了抵抗穷举攻击，RSA算法采用了大密钥空间，通常模数n取得很大，e和d也取为非常大的自然数，但这样做的一个明
23、显缺点是密钥产生和加/解密过程都非常复杂，系统运行速度比较慢。与其他的密码体制一样，尝试每一个可能的d来破解是不现实的。那么分解模数n就成为最直接的攻击方法。只要能够分解n就可以求出(n)，然后通过扩展的欧几里得算法可以求得加密指数e模(n)的逆d，从而达到破解的目的。目前还没有找到分解大整数的有效方法，但随着人们计算能力的不断提高和计算成本的不断降低，许多被认为是不可能分解的大整数已被成功分解。例如模数为129位十进制数字的RSA-129已于1994年4月在Internet上通过分布式计算被成功分解出一个64位和一个65位的因子。更困难的RSA-130也于1996年被分解出来，紧接着RSA-
24、154也被分解，据报导158位的十进制整数也已被分解，这意味着512比特模数的RSA已经不安全了。更危险的安全威胁来自于大数分解算法的改进和新算法的不断提出。当年破解RSA-129采用的是二次筛法，而破解RSA-130使用的算法称为推广的数域筛法，该算法使破解RSA-130的计算量仅比破解RSA-129多10%。尽管如此，密码专家们认为一定时期内1024到2048比特模数的RSA还是相对安全的。除了对RSA算法本身的攻击外，RSA算法还面临着攻击者对密码协议的攻击，即利用RSA算法的某些特性和实现过程对其进行攻击。下面介绍一些攻击方法。1.共用模数攻击共用模数攻击在RSA的实现中，如果多个用户
25、选用相同的模数n，但有不同的加解密指数e和d，这样做会使算法运行起来更简单一些，但却是不安全的。假设一个消息用两个不同的加密指数加密且共用同一个模数，如果这两个加密指数互素(一般情况下都这样)，则不需要知道解密指数，任何一个加密指数都可以恢复明文。理由如下：设e1和e2是两个互素的加密密钥，共用的模数为n。对同一个明文消息m加密得。攻击者知道n、e1、e2、c1和c2，他可以用如下方法恢复出明文m。nmcnmceemodmod2121和由于e1和e2互素，由扩展的欧几里德算法可找到满足re1+se2=1的r和s。由此可得明文消息m被恢复出来。(注意：r和s必有一个为负整数，上述计算需要用扩展的
26、欧几里德算法算出c1或者c2在模n下的逆)nmmmmmccsereseresrmod12121212.低加密指数攻击低加密指数攻击较小的加密指数e可以加快消息加密的速度，但太小的e会影响RSA系统的安全性。在多个用户采用相同的加密密钥e和不同的模数n的情况下，如果将同一个消息(或者一组线性相关的消息)分别用这些用户的公钥加密，那么利用中国剩余定理可以恢复出明文。举例来说，取e=3，三个用户的不同模数分别是n1、n2和n3，将消息x用这三组密钥分别加密为y1=x3 mod n1，y2=x3 mod n2，y3=x3 mod n3一般来讲，应选n1、n2和n3互素，以避免通过求出它们的公因子的方式
27、导致模数被分解。根据中国剩余定理，可由y1、y2和y3求出y=x3 mod n1n2n3由于xn1，xn2，xn3，因此x3e(e+1)/2，将k个线性相关的消息分别使用k个加密指数相同而模数不同的加密密钥加密，则低加密指数攻击能够奏效；如果消息完全相同，那么e个加密密钥就够了。因此，为了抵抗这种攻击，加密指数e必须足够大。对于较短的消息则要进行独立的随机数填充，破坏明文消息的相关性，以防止低加密指数攻击。3yx 3.中间相遇攻击中间相遇攻击指数运算具有可乘性，这种可乘性有可能招致其他方式的攻击。事实上，如果明文m可以被分解成两项之积m=m1m2，那么这意味着明文的分解可导致密文的分解，明文分
28、解容易使得密文分解也容易。密文分解容易将导致中间相遇攻击，攻击方法描述如下。假设c=me mod n，攻击者知道m是一个合数，且满足m2l，m=m1m2，m1和m2都小于2l/2。那么，由RSA的可乘性，有。121212()modeeeemmmmmccn12modeecmmn攻击者可以先创建一个有序的序列然后，攻击者搜索这个有序的序列，尝试从中找到两项ie和je满足攻击者能在步操作之内找到ie和je，由此获得明文m=ij。21,2,3,(2)modleeeen2,1,2,2li j,modnjicee22l攻击者的空间代价是需要能够提供比特的存储空间，时间代价的复杂度为，nllog22nOll
29、3212log22明显小于O(2l)，与平方根量级约化相当。在明文消息的长度为4060比特的情况时，明文可被分解成两个大小相当的整数的概率为18%50%。举例来说，假设用1024比特模数的RSA加密一个长度为56的比特串，如果能够提供2281024=238比特(约为32 GB)的存储空间，经过229次模指数运算，就可以有很大的把握找出明文比特串，它是两个28比特的整数之积。这种空间和时间的代价由一台普通的个人计算机就足够了。这说明用RSA直接加密一些比较短的比特串(如DES等单钥体制的密钥或者长度小于64比特的系统口令等)是非常危险的。5.3.3 RSA算法的参数选择算法的参数选择1.模数模数
30、n的确定的确定首先，多用户之间共用模数会招致共用模数攻击，因此不能在多个用户之间共用模数。其次，模数n是两个大素数p和q的乘积，因此n的确定问题可转化为如何恰当地选择p和q。p和q除了要足够大(至少100位以上的十进制整数)以外，还应满足如下要求:(1)p和q应为强素数；(2)p与q之差要合适；(3)p-1与q-1的最大公因子要小。若一个素数p称为强素数或一级素数，则p满足下列条件：a)存在两个大素数p1和p2，使得p1|(p-1)，p2|(p+1)；b)存在四个大素数r1，s1，r2和s2，使得r1|(p1-1)，s1|(p1+1)，r2|(p2-1)，s2|(p2+1)。称p1和p2为2级
31、素数；r1，s1，r2和s2为3级素数。为什么要采用强素数？这是因为p和q的取值会影响分解模数n的困难性。若p或q不是强素数，则可通过下面的方法分解模数n。其中pi为素数，ai为正整数(i=1，2，k)。如果pi都很小，不妨设piA(A为已知的小整数)，构造其中，amaxai，显然有(p-1)|R。假设p-1有k个素因子，由算术基本定理可得 ,kiaiipp11kiaipR1因为任意小于素数p的正整数t均与p互素，不妨设t=2，由欧拉定理可知t(p)=2(p)=2(p-1)1 mod p因而tR=2R1 mod p。计算X=tR mod n=2R mod n，若X=1，则令t=3重新计算X，直
32、到算出的X1。此时由gcd(X-1，n)=p，得到n的分解因子p和q。对于q也可以类似讨论。因此p-1和q-1必须有大素数因子，即p和q要为强素数。如果p与q之差很小，则由(p+q)2-(p-q)2=4pq=4n可得(p+q)2-4n=(p-q)2是一个小的平方数，所以(p+q)/2与 近似。令u=(p+q)/2，v=(p-q)/2，可以从大于 的整数依次尝试u且，从而解出p与q。尽管要求p与q之差不能太小，但二者之差也不能很大。如果很大，则其中一个必然较小，那么可以从一个小的素数开始依次尝试，最终分解n。因此，p与q之差要适当，一般是长度相差几个比特。nnnuv2要求p-1与q-1的最大公因
33、子要小是为了防止迭代攻击。假设攻击者截获了密文c=me mod n，可以进行如下的迭代攻击。记如果存在t使得et mod(n)=1，则有整数k使et=k(n)+1，那么由欧拉定理可知,2,1,modmodmod001iccncncncciieeeiicncnccnkettmodmod1)(与此同时还有所以因而如果t较小，则这种迭代攻击很容易成功。由欧拉定理可知t=(n)=(p-1)(q-1)，若p-1与q-1的最大公因子较小，则t较大，如果t大到(p-1)(q-1)的一半，则迭代攻击难以奏效。nccettmod1nmcnceetmodmod1ncncmettmodmod112.加密密钥加密密钥
34、e的选取的选取加密密钥e要满足以下几个要求：(1)e要与模数n的欧拉函数值(n)互素，即gcd(e，(n)1，否则无法计算解密密钥d。这一要求容易满足，现在已经证明两个随机数互素的概率约为3/5。(2)e不能太小，否则容易遭受低加密指数攻击。另外，如果e和m都很小且满足men，此时密文c=me mod n不需要经过模运算可直接得到，这样由c开e次方可得明文m。(3)e在模数(n)下的阶要足够大，即满足et mod(n)=1的最小正整数t要尽可能大，一般应达到(p-1)(q-1)/2。3.解密密钥解密密钥d的选取的选取加密密钥e选定之后，利用扩展的欧几里德算法可以求出解密密钥d。类似于对加密密钥
35、e的要求，解密密钥d也不能太小，否则容易遭受已知明文攻击。如果对明文m加密得到密文c，在解密密钥d很小的情况下，从某个正整数开始依次尝试，直接找出一个数t满足ct mod n=m，那么这个t就是解密密钥d。另外，Wiener于1990年利用连分数理论证明了当解密密钥d小于时很容易分解模数n，然后可求出解密密钥d。因此，一般要求d不能小于。3/4n4n5.4 Rabin算法算法5.4.1 求解数模下的平方根问题求解数模下的平方根问题定理定理5.4.1 假定n是大于1的奇数，且有如下分解其中，pi是互不相同的素数;ei是正整数。对于与n互素的整数a，如果a是模pi的平方剩余且对所有的i=1，2，l
36、都成立，那么同余方程x2a mod n存在2l个模n的解。1ileiinp证明：证明：根据已知条件，由同余理论可知同余方程x2a mod n等价于同余方程组因此，问题转化为求解上述的同余方程组。对所有的i=1，2，l，由a是模pi的平方剩余可知同余方程x2a mod 有两个模的解，分别记为 和。1ileiinp2modieixap1,2,ilieipieipieiipbxmod2,ieiipbxmod1,这样可以得到一系列的一次同余方程组其中，bi可取bi，1或者bi，2。由中国剩余定理可知每一个这样的一次同余方程组都有惟一的模n解。由于每个bi可取bi，1和bi，2之一，因此可以产生2l个不
37、同的(b1，bl)，即共有2l个不同的一次同余方程组。所以同余方程组(i=1，2，,l)共有2l个模n的解，即原同余方程x2a mod n存在2l个模n的解。ieipaxmod2lipbxieii,2,1,mod命题命题5.4.1 如果素数p3(mod 4)，a是模p的平方剩余，那么a模p的平方根是a(p+1)/4 mod p。证明：证明：根据a是模p的平方剩余，由Euler准则可知a(p-1)/2mod p=1。于是(a(p+1)/4)2 mod pa(p+1)/2 mod paa(p-1)/2 mod pa mod p5.4.2 Rabin算法描述算法描述对于RSA算法，如果能够成功分解模
38、数n，则可攻破RSA系统。因此，攻击RSA算法的难度不会超过大整数的分解，但它是否等价于大整数的分解，目前还不知道。本节讨论的Rabin算法既可看成是RSA算法的一个特例，也可以看成是对RSA算法的一个修正。Rabin算法是一个被证明其破解难度正好等价于大整数分解的公钥密码算法，它也是第一个可证明安全的公钥密码算法。Rabin算法的安全性基于求解合数模下的平方根的困难性。Rabin算法的基本框架类似于RSA，也是依赖于以两个大素数之积为模数的模指数运算，但Rabin算法对模数的选择和加解密模指数运算提出了特别的要求。Rabin算法的描述如下：首先选取两个相异的满足pq3 mod 4的大素数p和
39、q，以n=pq为模数。然后再随机选取一个整数bZn。算法以(n，b)为公开密钥，(p，q)为私有密钥。(1)加密变换：对于一个明文消息m，通过计算c=m(m+b)mod n得到密文c。(2)解密变换：为了解密出密文c，需要求解二次同余方程m2+bm-c0 mod n如果令，上面的方程可改写为如果再令，方程进一步可改写为x2C(mod n)因此解密问题归结为求C模n的平方根。2bmxcbC42)(mod422ncbx方程x2C(mod n)有四个解，由命题5.3.1可知，当pq3 mod 4时，方程x2C mod p的两个解是x=C(p+1)/4mod p，方程x2C mod q的两个解是x=C
40、(q+1)/4mod q因此，可以组合得到四个一次同余方程组qCxpCxqpmodmod4/)1(4/)1(qCxpCxqpmodmod4/)1(4/)1(qCxpCxqpmodmod4/)1(4/)1(qCxpCxqpmodmod4/)1(4/)1(利用中国剩余定理解这四个同余方程组得到四个解，它们是C模n的四个平方根。要寻找的明文就是四个解的其中之一。由上面的叙述可见，Rabin算法的加密函数不是单射，解密具有不确定性，合法用户不能确切地知道到底哪一个解是真正的明文。如果加密之前在明文消息中插入一些冗余信息，比如用户的身份数字、日期、时间或者事先约定的某个数值等，则可以帮助收信者准确地识别
41、解密后的明文。Rabin算法的解密过程是寻找C模n的平方根，这个问题的难度等价于n的因子分解。尽管计算模为素数的平方根是多项式时间可解的，但其过程仍然很复杂。要求p与q是模4同余3的限制条件是为了使解密的计算和分析变得容易。在实践中通常使用Rabin算法的一个变形或者说是特例，即取b=0。在这种情况下，加解密处理变成如下形式：(1)加密变换：c=m2 mod n(2)解密变换：mod n这种变形的Rabin算法可以看做是加密指数e=2的RSA算法。cm 例例5.4 假定模数n=1923=437，对明文m=183加密，则密文为c=m2 mod n=1832 mod 437=277如果要对密文c=
42、277进行解密，首先需要计算出277模19和模23的平方根。由于19和23都是模4同余3的，因此可得277模19的平方根：277(19+1)/427757 mod 19277模23的平方根：277(23+1)/427761 mod 23再解下面的同余方程组：23mod119mod7xx23mod119mod7xx23mod119mod7xx23mod119mod7xx利用中国剩余定理，可解出上面四个同余方程组的解，分别是x=254，45，392，183 mod 437由此可见，原始明文m=183是这四个解之一。5.4.3 Rabin算法的修正算法的修正Rabin算法具有解密不确定性的缺陷，为此
43、研究者们对其进行了多种改进，提出了一些更简单有效、可证明安全和解密惟一的修正方案。Williams方案比较具有代表性，简述如下。取两个不同的满足pq3 mod 4的大素数p和q，以n=pq为模数。再取一个小整数s，且s不是模n的平方剩余。以n和s为公钥对外公布，需要保密的私钥k满足1)1)(1(4121qpk(1)加密变换：对于消息m，先确定参数c1。如果m是模n的平方剩余，c1取0；否则，c1取1。然后计算以三元组(C，c1，c2)为所得密文。112121modmod2modcmsmncmCmn(2)解密变换：对于密文(C，c1，c2)，收信者根据m2=Ck mod n计算出m2，m2的符号
44、由c2确定：c20 mod 2时m2取负，c21 mod 2时m2取正。最后，由下式计算出明文消息m：212(1)modccmsmn 例例5.5 假设取p=3，q=7，则n=21，选s=2不是模21的平方剩余。对于消息m=19，不是模21的平方剩余，取c1=1。于是这样加密所得的密文为(16，1，1)。11121221mod219(mod21)17mod217mod21mod17 mod2116cmsmncmCmn如果要对密文解密恢复出明文，计算于是可见，解密是惟一的。22mod16 mod214kmCn21112(1)mod(1)24mod2119ccmsmn 21)17)(13(41211
45、)1)(1(4121qpkRabin算法对选择明文攻击是安全的，但已经证明它确实不能抵抗选择密文攻击。此外，针对RSA算法的一些攻击方法对Rabin算法也有效。因此，与RSA安全性有关的一些问题，比如如何选择系统参数等，对Rabin算法也同样适用。5.5 ElGamal算法算法ElGamal算法也是一种具有广泛应用的公钥密码体制，它的安全性基于有限域上计算离散对数问题的困难性，还有许多常用的密码算法与ElGamal算法具有类似的基本原理。相对来讲，ElGamal算法比较容易理解。5.5.1 离散对数问题离散对数问题假设a是群G中的任一元素，满足at=1的最小正整数t称为元素a的阶，如果不存在这
46、样的正整数t，则称a的阶为。假设群G为有限乘法群(p为素数)，将满足at=1 mod p 的最小正整数t称为元素a在模p下的阶。如果元素a模p的阶等于(p)，则称a是p的本原根或者本原元。如果模数取任意的正整数，上面模运算下元素的阶和本原根的概念仍然有意义。*pZ设a是素数p的本原根，那么a，a2，a(p)在模p下互不相同且正好产生1到(p)=p-1的所有值。因此，对于b1，2，p-1，一定存在惟一的x1，2，p-1 满足bax mod p。称x为模p下以a为底b的离散对数，并记为xlogab(mod p)。如果已知a、p和x，那么使用快速指数算法可以轻易地算出b；如果仅知a、p和b，特别是当
47、p的取值特别大时，要想求出x是非常困难的，目前还没有特别有效的多项式时间算法。因此，离散对数问题可以用于设计公钥密码算法。为了使基于离散对数问题的公钥密码算法具有足够的密码强度，一般要求模数p的长度在150位以上。5.5.2 ElGamal算法的描述算法的描述设p是一个素数，Zp是含有p个元素的有限域，是Zp的乘法群，p的大小足以使乘法群上的离散对数难以计算。选择的一个生成元g和一个秘密随机数a，要求它们都小于p，计算 y=ga mod p公开密钥取为(y，g，p)，且g和p可由一组用户共享；a作为私有密钥，需要保密。*pZ*pZ*pZ(1)加密变换：对于消息m，秘密选取一个随机数kZp-1，
48、然后计算c1=gk mod p 和 c2=myk mod pc1与c2并联构成密文，即密文c=(c1，c2)，因此密文的长度是明文的两倍。(2)解密变换：。由加密变换可知，。所以，解密结果是正确的。121()modamc cp1121()()modakakakakc cmygmggmp例例5.6 设p2579，取模p乘法群的生成元g=2，私钥x765。计算y=gx mod p=2765mod 2579949如果明文消息m1299，选择随机数k853，那么可计算出密文：c=(c1，c2)=(gk，myk)mod p =(2853mod 2579，1299949853mod 2579)=(435，
49、2396)对密文进行解密变换可计算出明文m：由于密文不仅取决于明文，还依赖于加密者每次选择的随机数k，因此ElGamal公钥体制是非确定性的，同一明文多次加密得到的密文可能不同，同一明文最多会有多达p-1个不同的密文。12992579mod)435(2396mod)(1765112pccmxElGamal算法建立在乘法群(p为素数)上，事实上可以基于任何离散对数问题难以求解的群来构造ElGamal算法。此时是将ElGamal算法建立在某个生成子群上，称这样得到的公钥密码体制为推广的ElGamal算法，简单描述如下。设G是运算符为*的有限群，元素gG，H是由g生成的子群，即H=gi|i0。G上的
50、离散对数问题是：对一个元素bH，能否找到惟一的整数a0，|H|-1，满足ga=bH，记。*pZbgalog如果上述的离散对数在有限群G的生成子群H上是难以求解的，那么可以在有限群G上构造如下的ElGamal公钥密码体制。任取a0，|H|-1，计算y=gaH，公开密钥取为(g，y)，私有密钥取为a。(1)加密变换：对于明文分组m，随机选取k0，|H|-1，计算密文c=(c1，c2)，其中c1=gk，c2=m*yk。(2)解密变换：。121()amc c5.5.3 ElGamal算法的安全性算法的安全性ElGamal算法的安全性基于有限群上离散对数问题的困难性。有学者曾提出模p生成的离散对数密码可
