1、第4章 公钥密码第第4 4章章 公钥密码公钥密码4.1 引言引言4.2 背包公钥密码系统背包公钥密码系统4.3 RSA公钥密码公钥密码(基于大数分解基于大数分解)4.4 Rabin公钥体系公钥体系(基于二次剩余基于二次剩余)4.5 ElGamal公钥系统公钥系统(基于离散对数基于离散对数)4.6 McEliece公钥密码公钥密码(基于纠错码基于纠错码)4.7 椭圆曲线公钥体制椭圆曲线公钥体制习题习题 4实践练习实践练习 4第4章 公钥密码 计算机互联网的出现，极大地方便了人们对信息的交换和共享，电子商务和电子公务等越来越多的业务开始在网上进行，这就对信息交互提出了一系列新的需求。另一方面，网络
2、也给攻击者提供了更多的机会，病毒、黑客以及网络犯罪时有发生。如何更好地解决信息安全问题，已成为刻不容缓的任务。20世纪70年代出现的公开密钥体系，标志着现代密码学的诞生。新的理论与实践迅速发展起来了，随着一系列新观念和方法的出现，现代信息网络中的安全问题逐步得到解决，密码学进入了崭新的发展阶段。第4章 公钥密码4.1引言引言34.1.1对称密钥的困惑对称密钥的困惑 1.密钥交换问题密钥交换问题 为了使对称密钥(单钥制)体系实现信息的保密传输，通信双方必须事先约定相同的算法和步骤，称之为保密协议，并且设法在不让其他任何人知晓的条件下，双方获取统一的密钥，这一过程叫做密钥交换。密钥交换往往是比较困
3、难的任务，密钥是用秘密信道传递的，而秘密信道却昂贵且难得。因此，解决密钥交换问题便成了对称密钥体制的最大障碍。2.通信网络中的密钥管理问题通信网络中的密钥管理问题 网络中N个用户两两保密通信，需要分配和保管M=N(N+1)把密钥，当N很大时，比如N=1000时，则21第4章 公钥密码M5105，网管中心一定非常繁忙，甚至会成为通信的瓶颈。因此，密钥管理问题成了信息系统的又一难题。4.1.2公开密钥的产生和雏形公开密钥的产生和雏形 1Merkle难题难题 1974年，Merkle为解决对称单钥制保密系统的密钥交换问题提出了一个设想9。其密钥交换协议为：(1)甲向乙发送100万条消息，每条内容均为
4、：“这条信息是xi，它的密钥是yi”；xi是从0到999999之间任意选取但又各不相同的随机数，yi是xi的密钥，它也是从0到999999之间的任意被甲预先指定的一个各不相同的随机数。甲秘密保存所有yi与xi的密钥对照表后，就把这100万条消息分别用所宣布的这个yi加密，全部发给乙。第4章 公钥密码 (2)由于加密算法是公开的，乙收到100万条消息后，从中任选一条，然后遍历0999999之间的100万个密钥进行尝试，总有一个yj可将其解密，从而得知xj的值。(3)乙以明文形式将xj发给甲。(4)甲收到xj，即知乙所选的是哪个yj，从而甲、乙二人都有了同样的密钥yj。(5)非法窃听者丙即使收到了
5、全部往来的明文和密文，虽然知道了xj，但他不知道xj在哪条消息中，他需要对100万条消息一一进行解密，而每解译一条消息需要尝试100万个密钥。假若乙耗时半分钟能完成对100万个密钥的尝试，得到自己的密钥，丙则需要100万倍的时间，大约1年才能从100万条消息中确定乙所选的是哪一条。第4章 公钥密码 此设计方案显然是不太现实的，但其思想是很先进的。它用公开的算法通过不安全信道完成了密钥交换，其保密理念基于计算复杂性，安全性则是建立在机密与破译的时差之上的。该课题的出发点虽然是为了解决单钥交换问题，但客观上已走进了公开密钥的大门。2.双钥制的提出双钥制的提出 1976年11月，美国斯坦福大学电气工
6、程系研究生W.Diffie和副教授M.E.Hellman在IEEE上发表了题为“密码学新方向”的学术论文10，首次提出双密钥思想，用公开的算法解决了单钥制的密钥交换问题。设p为一个大素数，已知x和b，不难求出:y=bx mod p (4-1)第4章 公钥密码然而若已知y和b，求逆运算:x=logby mod p (4-2)却十分困难。利用离散对数复杂性，他们二人设计的密钥交换协议如下：(1)用户i选xi为私钥，求出 为公钥，公布之(连同b和p发给用户j)。(2)用户j选xj为私钥，求出 为公钥，公布之(发给用户i)。(3)约定 (4-3)pbyixi mod pbyjxj mod pbkjix
7、xij mod第4章 公钥密码为会话密钥(对称单钥)，用户i可由获得；用户j可由获得。(4)尽管公布了yi、yj和p，但基于离散对数的困难性，任何第三者都难以求出xi和xj，因此无法获得kij。Diffie和Hellman不仅用公开的算法，而且首次提出了公钥和私钥的概念，开创了现代密码学的先河。pypbkiijxjxxij mod)(mod)(pypbkjjixixxij mod)(mod)(第4章 公钥密码4.1.3公开密钥制的一般原理公开密钥制的一般原理 1.公开密钥体系的使用方式及功能公开密钥体系的使用方式及功能 W.Diffie和M.E.Hellman的论文发表后，立即引起了学术界的重
8、视，并且很快把双密钥的思想用到密码系统中，这不仅解决了单钥制的密钥交换问题，更重要的是以一种全新的方式很好地解决了保密、认证与网络管理等问题。假设在算法公开的双密钥密码体制下每个用户都分得了自己的公钥(可以公开的密钥)与私钥(必须秘密保存的密钥)，于是就能完成以下功能：(1)保密功能(包括会话密钥的交换)：发信人用收信人的公钥加密，形成密文，收信人用自己的私钥解密。其他人因为不掌握可配对的私钥，所以无法解读这个密文。第4章 公钥密码 (2)认证功能：发信人用自己的私钥加密形成密文，收信人用发信人的公钥解密。其实任何人都能查到发信人的公钥来解译密文，能正确解译即证明该密文是发信人所加密的。(3)
9、双重功能：发信人先用自己的私钥加密明文，再用收信人的公钥对密文再次加密；收信人收到密件后先用自己的私钥解密一次，再用发信人的公钥解密一次。这样的密文只有合法收信人才有能力阅读并验证。(4)网管功能：N个用户的系统，管理员只需保管(不必隐藏)N把公钥，私钥由用户个人保管。密钥分配与管理的问题立刻变得简单了。第4章 公钥密码 2.公开密钥体系的加、解密过程公开密钥体系的加、解密过程 公开密钥体系把算法公开，并且把一对密钥中的一把公开，才换来了功能上的增加与使用上的方便。而之所以将之公开，是因为解密所用算法并非加密的逆运算，解密所用密钥也不同于加密所用的密钥，而且二者不可互相推导。加密：明文M变换
10、(k1为加密密钥)密文C，即 (4-4)解密：密文C变换 (k2为解密密钥)明文M，即 (4-5)1kE2kD1MECk2CDMk第4章 公钥密码 3.单向陷门函数单向陷门函数(加密、解密的数学原理加密、解密的数学原理)作为一个保密系统，无论单钥制还是双钥制，解密和加密的效果一定应当是互逆的，通过解密应得到与原来的明文相同的译文。一般说来，解密应当用加密的逆运算实现，单钥制就是这么做的。然而，抛开逆运算的定式看问题，逻辑上并不排除存在其他算法也能解出正确译文的途径。如果有，为什么不可以用呢。至于密钥，它只是加、解密运算过程中的一些关键数据，更没有理由认为参与加密运算的密钥和参与解密运算的密钥必
11、须相同。(当然，加密密钥与解密密钥既然是配对的，那么总应当存在某种内在的联系，实际上也确实如此。不过只要这种内在联系涉及到复杂度很高的运算，就可以认为它们是无法相互推导的)。于是，问题又回到了数学上，能否找到这样的算法和密钥呢？第4章 公钥密码 数学上存在一种单向陷门函数，它有下列性质：(1)对于每个xX，计算y=f(x)是容易的。正是因为这一点，加密运算才是简单可行的。(2)明知y=f(x)在yY中有解，但由给定的y难以求出x，其逆运算x=f-1(y)十分复杂。正是因为这一点，它被叫做单向函数。即使公开了算法，也难以在有限机时内计算出逆运算结果，系统安全性才有了保障。(3)对于某些特殊的单向
12、函数(不是所有的单向函数)，若附加一点相应的“陷门信息k”，则存在另一个能算出x的方法：x=fk(y)。f k(y)不同于 f-1(y)，它可以容易地算出x；求解这个问题的关键数据k就是密钥。正是因为这一点，掌握密钥的合法用户才能容易地正确解译密文。第4章 公钥密码 数学中确实存在不少逆运算非常复杂的单向函数，如大数的分解因数、离散对数等等，这是构造公开密钥体系的必要条件。但是还必须设法引入“陷门”，就像魔术师做一个套，知道窍门的人，就能轻易地从别的路钻出来，而不必按进来的路线在迷宫里摸索。目前已找到多种单向陷门函数，设计出多种公开密钥系统，如RSA系统、背包系统、ElGamalJP系统、Ra
13、bin系统等，后面将陆续介绍。4.1.4现代密码学的理念现代密码学的理念 1.从基于算法的神秘性到基于算法的复杂性从基于算法的神秘性到基于算法的复杂性 传统密码体系的安全性依赖于对算法的保密，一旦算法失密，攻击者就可以用它的逆运算来破译密码系统。而现代密钥第4章 公钥密码学则利用逆运算复杂度非常高的单向算法来构建密码系统，就不必担心算法失密，因为攻击者即使应用现代最新计算技术，在有限时间内也是无法算出结果的。所谓复杂性，是指计算所必须的基本运算步骤的数量，它决定了计算所必须的机时和占用的计算机资源。计算复杂性理论告诉我们，计算量随着数据位数N的增长而变大，其增大的速度与算法的函数类型有关。按照
14、从小到大的次序是：常数，对数函数logN，线性函数aN，二次函数N2，三次函数N3，多项式函数Nd，亚指数函数2lgN，指数函数2N或10N。随着数据位数N的增长，计算量按照多项式以下的依赖关系变大的算法都可认为是有效算法，这样的增加速度对于现有第4章 公钥密码计算技术来说是可以接受的，有限时间内能够算出结果。否则，计算量将随着N的增长而迅速膨胀，就不可能在有限时间内算出结果。复杂性理论把依赖关系为多项式及其低于多项式的算法都称为可解问题(p类)，而将超过多项式的算法都称为难解问题(Np类，NpC类)。如果已经证明了某种密码的破译是Np类问题，那么只要数据位足够大，则任何现代的计算设备都不可能
15、在允许的时间内将其破译，因此它是安全的。由基于算法的神秘性到基于算法由基于算法的神秘性到基于算法的复杂性的复杂性是现代密码学设计理念上的一次重大转变，不靠神奇不靠神奇靠麻烦靠麻烦，算法不怕别人猜出，甚至可以公开。这样一来，密码分析者的注意力也就从研究由密文提取信息的可能性(老观点)改变为由密文提取信息的可行性(新观点)。第4章 公钥密码 2.算法的可公开性算法的可公开性 现代密码学认为藏着捂着的神秘算法，其安全性终究是侥幸的和脆弱的，只有根据算法的复杂性建立起来的密码体制，其安全性才是坚固可信的。这是因为算法的复杂性完全能够通过数学理论科学地预测，只要该算法复杂到不可行的程度，即使公开了算法，
16、也难以在有限机时内计算出逆运算结果。算法既然失去了保密的价值，公开算法就成了现代密码体制的一大特点。算法公开后，可以让它在攻击中不断完善和改进，并以此显示其安全的坚固性。第4章 公钥密码 3.安全的相对性安全的相对性 在科学技术高度发展的今天，应充分估计破译者的计算能力和计算技术未来的发展，从这个意义讲，不存在永远牢不可破的密码，只存在当前阶段与需求相适应的安全密码体系，破译只是时间和金钱的问题。但是如果破译工作所花的代价大于秘密本身的价值，或破译花费的时间大于秘密的有效期，则破译失去意义，则该保密系统就可以认为是安全的。这才是实事求是的科学的保密观和破译观。根据这个观点，破译的工作量取决于算
17、法的复杂度，而复杂性又取决于数据位数的长短，因此可以根据客观需求实事求是地设计不同层次、不同时效的密码体系。不求绝对不求绝对(安全安全)求相对求相对(安全安全)是密码设计理念上的又一个转变。第4章 公钥密码 4.密钥的机密性密钥的机密性 算法公开了，合法用户与非法用户的区别在哪里呢？合法用户拥有密钥，解译密文十分容易；非法用户没有密钥，破译密文则很不容易。这是因为如果攻击者用遍历法一个个去尝试密钥，设每尝试一个密钥需要1秒钟，则遍历160比特长的所有密钥需要2160秒钟，约1040年。只要密钥具有足够的长度与随机性，偶然猜中密钥的概率是极小的。不藏算法藏密钥不藏算法藏密钥是设计理念上一致的观点
18、。保守密钥的机密要比隐藏算法的机密容易得多，也安全得多。况且密钥是可以随时更换的，万一暴露了密钥，可以换一把，不致造成整个系统的破坏。第4章 公钥密码4.2背包公钥密码系统背包公钥密码系统 当初Diffie和Hellman提出公钥思想的时候，还没有一个实例。两年后，1978年,Merkle和Hellman利用古老的背包问题设计出一个公开的密钥系统11。4.2.1背包问题背包问题 1.问题问题 已知n个物体重量分别为A=(a1,a2,an)，任选其中若干件放入背包内，使其总重量恰好等于预先给定的b值。设所选物体用X=(x1,x2,xn)表示，这里xi(i=1,2,n)可为0或1，分别表示该物体被
19、取或不被取，则 bxainii1XA(4-6)第4章 公钥密码 2.解答解答 当n较小时，这是一个多解的不定方程问题。例如，A=1，2，5，8，11，17，21,b=47,则答案可以是2+5+8+11+21,也可以是1+8+17+21。当n较大时，它是一个Np类的难解问题。例如，n=100，2100=1.271030，以每秒107种方案的速度用计算机搜索，也得4.021015年才能完成穷举。3.超递增序列的背包问题超递增序列的背包问题 如果限制这些物体的重量，即每个物体的重量都满足比它的前面所有物体的重量之和大的条件，即11ijjiaa(4-7)第4章 公钥密码则这样的背包问题叫做超递增背包问
20、题。超递增背包问题是p类唯一解的可求解问题。例如：A=1，2，5，10，25，51，b=64，则由6451可知a6必存在；再由64-51=1310知a4必选；又由13-10=32知a2必选；最后由3-2=1=a1知a1也必选。故答案是X=1,0,1,0,1,1，即64=1+2+10+51。4.2.2 MH背包公钥系统背包公钥系统 设明文为M=m1,m2,mn,mi=。若用超递增序列B=b1,b2,bn将之加密，则 是p类可解问题；10iniibmC1第4章 公钥密码若用非超序列A=a1,a2,an将之加密，则 是Np类难解问题。iniiamC1 如果设计出一个方法，能把B变换成A，我们用A来加
21、密，使问题成为Np类完全难题，则合法用户由于掌握A变换成B所具有的信息(私钥)，就能由A求出B，使问题成为p类可求解问题。而非法用户只知道A(公钥)，不掌握私钥，因此就无法解答此题。Merkle和Hellman当初是利用模逆元进行这个变换的。例如，B=1，3，7，13，26，119，267，选大于全部元素之和501的一个数，p=523,再选一个与523互素的数w=28,并求出w-1=467 mod 523，于是可分别求出每个bi的模逆元：ai=w-1bi mod 523 (i=1,2，n)第4章 公钥密码结果是：A=4671,4673,4677,46713,mod 523 =467,355,1
22、31,318,113,21,135,215A和p=523为公钥，求出A后，将w-1销毁。要发送信息就用A来加密。例如，明文M=10101100，则密文为C=AM=a1+a3+a5+a6=467+131+113+21=732mod523=209w=28为合法用户的私钥。合法接收者不难求出：bi=wai mod p=ww-1bi mod p=bi mod p(i=1,2，n)第4章 公钥密码即求出 B=1,3,7,13,26,65,119,267 还能求出 C=wc mod p=28209 mod 523=99而这是一个超递增背包问题，容易解出：m1=m3=m5=m6=1其他mi=0，所以明文是M
23、=10101100。第4章 公钥密码4.2.3背包公钥体系的破解与发展现状背包公钥体系的破解与发展现状 Merkle和Hellman提出背包体系时，曾悬赏50美元征求人破译，两年后，Shamir将其破译了。尽管求大数的模逆元与分解大素数的复杂度相同，但该设计存在漏洞。后来Merkle和Hellman将漏洞补上，再次悬赏破译，两年后又被人破译，使背包体系受到致命打击。背包体系目前基本上已不大用了，但它作为公钥的先驱实践者，作为算法和思路很简单的公钥体制，仍有了解的必要。同时，以背包问题为原理的各种新密码体制目前仍有人在继续研究。第4章 公钥密码4.3 RSA公钥密码公钥密码(基于大数分解基于大数
24、分解)3，7，8 RSA公钥密码是第一个实用的，同时也是流行至今的最典型的公钥算法。1978年，美国麻省理工大学的Rivest、Shamir和Adelman利用数论相关知识，提出了这个公钥系统10。4.3.1RSA加解密原理加解密原理 设p和q为两个大素数，计算n=pq和欧拉数(n)=(p-1)(q-1),随机选择整数e,使满足(e,(n)=1,于是它的逆元存在，即d=e-1mod(n),即有：ed=1mod(n)或 ed=k(n)+1 (4-8)设m为明文，e为公钥，n也是公钥(公钥是两个数据),则加密过程为 C=me mod n (4-9)第4章 公钥密码因为逆运算 十分复杂，且存在多义性
25、(不定)，所以它是一个单向函数。然而，利用欧拉定理知，若m与n互素，则 m(n)=1mod n (4-10)对任意整数k，mk仍与n互素，则 (mk)(n)=1mod n于是：mk(n)+1=m mod n由此得到解密算法：Cd=med mod n=mk(n)+1 mod n=m mod n ecnm第4章 公钥密码即 m=Cd mod n (4-11)这里,d为私钥，只有合法用户掌握；p、q和(n)在完成设计后都可销毁；仅由公钥e和n是无法求出d的，除非能将n分解，求出p和q，而这是Np类难题，难以实现。4.3.2RSA的参数选择的参数选择 1.p和和q应为强素数应为强素数 强素数是这样一种
26、素数：对于素数p，若存在素数p1和p2，使p1|p-1，p2|p+1，则称p为一级素数，称p1和p2为二级素数；对于p1和p2，若存在素数r1r2和s1s2，使r1|p1-1,s1|p1+1,r2|p2-1,s2|p2+1,则称r1、r2、s1、s2为三级素数。存在二级和三级素数的一级素数才是强素数。这样才能保证在有效时间内不可能将其分解。反之，就有可能找到一些简便方法将其分解。第4章 公钥密码 2.p和和q的位数问题的位数问题 提出RSA的三人最初建议p和q为100位的十进制数(2332)，这样可使n达到200位以上，在亿次机上分解需55万年。同时，他们希望p和q的位数相差一般是几比特，这是
27、因为如果相差太小，就接近于，而 就很小，从而使费尔玛因式分解法容易进行：2qp 2qphnpqqpqph222241从小数的平方来测试，可以大大减少复杂性。(4-12)第4章 公钥密码 3.e和和d的选择的选择 e不能太小，太小了可以由 得到m。d小了虽然有利于解密的速度，然而d太小了也存在隐患，破解者可以对Cd穷举以获得m。因此，最好d 。4.n在使用上的限制在使用上的限制 不宜用同一个n去设计若干对(e,d),这样会引起不安全因素。假若对同一明文m：这里e1，e2互素，即满足te1+se2=1,于是有：这样一来，无需私钥，就得到了明文。eC41nnmCnmCee mod mod 2121，
28、nmmmmCCsetesetest mod 212121第4章 公钥密码4.3.3素数的检测素数的检测 1.素数是否够用素数是否够用 数论有定理指出，对正整数N，小于N的素数数目约为 。若p,q为十进制154位(512bit)的大素数，那么在此范围内约有10151个素数。宇宙中原子仅1077个，如果每个原子从宇宙诞生至今每秒钟需要一个素数，也才10109个。2.是否会两人偶然巧合选择了同一个素数是否会两人偶然巧合选择了同一个素数 小于n的素数的个数是 ，从中任选一个素数的概率是 ；当n是N位十进制大数时，这个概率小于 ，可见这种巧合的概率几乎为零。NNlnnnln nnNln nnln 第4章
29、 公钥密码 3.能否建立所有素数的数据库，用来破译能否建立所有素数的数据库，用来破译RSA(分解分解n)理论上可以这样做，但实际行不通。设每克半导体存储器可存储10亿字节，将512位的全部素数集中在有限尺寸的内存中，其存储器质量将超过引力场极限，使它变成黑洞，无法提取数据。4.怎么知道一个数是否为素数怎么知道一个数是否为素数 不能再分解的数才是素数，为此就得将其分解。而分解因数是Np问题，正因为它无法办到所以才有了RSA的安全性。那RSA所用的素数从何而得呢？似乎像是个先有鸡还是先有蛋的驳论。然而，检测素数毕竟与分解因数不同。现已找到多种素数测试方法和理论。第4章 公钥密码 威尔逊定理：n为素
30、数的充要条件是(n-1)!=-1modn(见前)。费尔马定理：若p为素数，则对任一整数a，有aP-11 mod p，但这只是必要条件。反过来，满足费尔马定理的并不一定都是素数，如n=561=31117就满足an-11 mod n，这样的n被称为卡密沙尔数(Carmichael)。欧拉定理：二次剩余理论中指出，p是素数的充要条件是 1modp，这里a是p的二次剩余。若a非二次剩余，则 -1mod p；若p是a的倍数，则 0 mod p。合起来就是勒让德函数：21pa21pa21pa第4章 公钥密码101 mod)(21papap,aLp(4-13)当不清楚n是不是素数时，上式为雅可比函数:nan
31、,aJp mod)(21(4-14)设 ，则 kkpppn2111101)(2121kkpapapanaJn,aJ(4-15)第4章 公钥密码由此得到素数判别程序的算法描述如下：S1:随机产生一整数a1，n-1。S2:计算gcda,n。S3:若gcda,n1，则n非素数，结束。S4：否则计算 及 modn。S5:若 mod n，则n可能是素数，转S1，进行第二轮，否则n是合数，结束。na21na21nana第4章 公钥密码 这个算法每进行一轮测试，正确性至少为 ；判断错误的概率小于 ；若两轮检测都通过，则判错概率小于 ；若n轮检测都通过，则判错概率小于=。进行n=1020轮判断，可使判错概率小
32、于万分之一。这种素数称为工业级素数。米勒-列宾(Miller Rabin)测试法：使用方法收敛很慢，而使用MR法k次通过的判错率仅为 ，且比减少一半的轮数。判别程序的算法描述如下：2121221nn2121kkk212141)(第4章 公钥密码 S1：先化n-1=2lm(m为去掉二进制最末位1后，再去掉l个连0)。S2：在1，2，,n-1中随机均匀地产生数b；j0，计算zbm mod n。若z=1或n-1，则n通过测试，结束。S3：若 j=l，则n非素数，结束，否则转S4。S4：j=j+1,zz2modn。若z=-1，则n通过测试，结束；否则转S3。当n通过第一轮测试后应回到S2，重新产生随机
33、数b，开始下轮测试。4.3.4RSA的安全性的安全性 RSA的安全性是基于大数进行因数分解的复杂性的。理论上已证明分解大数的渐进复杂度大约正比于elnnln(lnn)，可见n必须足够大，分解才能足够复杂。最初Rivest悬赏100美元破译129位(429比特)的RSA密码体系，估计百万次的计算机需连续工作4600年，结果43国600多第4章 公钥密码人动用1600台计算机通过因特网联合工作，耗时8个月，于1994年4月20日破译。后来130位的RSA也于1996年4月10日，用数域筛选法被攻破。人们又向154位发起攻击。200位(664比特)和1024比特的RSA已有实用产品。RSA的安全漏洞
34、：由于双钥制既能用于加密，又能用于认证，当A用自己的私钥对某文档“加密”后，y=md mod n，y就成为A对文档x的签名，任何人可以用A的公钥将其“解密”，即x=ye mod n，得到明文，同时证明该文是A所签发的。利用这一点，窃密者想解析某人发给A的密文C=me modn，他可以先自己随机产生一个文档r，用A的公钥加密s=re mod n，并求出r在模n下的逆r-1；之后，他把y=sC 发给A，请A签名，如果A同意签名，便计算u=yd mod n，发给窃密者；窃密者得到第4章 公钥密码u后，计算r-1u=r-1yd=r-1sdCd mod n，因为r=sd mod n，而r-1sd=r-1
35、r=1 mod n,所以r-1u=Cd mod n=m，明文m被窃得。这个攻击过程中，A被窃的疏漏在于他对陌生人的文档y进行了签名。为了骗取A的签名，有多种手法，比如A不愿对m3签名(或许因m3中有不利于A的文字)，骗子可以写m3=m1m2，而m1和m2的文字对A有利，它骗得 和 后，就可以计算 。又如,他还可以将m3改头换面为y=m3s(s=re mod n，是随机明文r的密文)，送y去让A签名，如果A签名了，则u=yd mod n，骗子便可以计算出：因此，绝不要对一个陌生人交给你的消息进行签名。即使要签，也应当只对消息的HASH值签名。dm1dm2dddmmm213nmrrmrsmrydd
36、ddd mod313131第4章 公钥密码4.4 Rabin公钥体系公钥体系(基于二次剩余基于二次剩余)Rabin公钥体制是RSA的e=2的特例。其加密算法是：C=m2 mod n(n为公钥)(4-16)它相当于同时满足：C=m2 mod p 和 C=m2 mod q表明C是两个素数共同的平方剩余：qCmpCmmodmod22(4-17)解密过程则是求同时满足模p和模q下密文C的平方根(p和q是私钥)。第4章 公钥密码4.4.1 GF(p)上平方根问题的讨论上平方根问题的讨论 在GF(p)域就是在整数1，p-1范围内求解。根据数学补充中关于二次剩余的知识，不难知道在1，p-1中的平方剩余方程：
37、x2=a mod p退化为 x2=a x1，p-1费尔马定理ap-1=1 mod p,则退化为 ap-1=1 x1，p-1于是 0110121211ppaaap第4章 公钥密码表明在1，p-1上，有 个根满足 =1 mod p，它们是平方剩余(QR)；而另外 个根满足 =-1 mod p=p-1mod p，它们是非平方剩余(NQR)。1.是奇数的情况是奇数的情况设是一个平方剩余，满足 =1，则 21p21pa21p21pa21p21p12121pp(4-18)因为 为奇数，所以 必为偶数，所以 必存在，21p21p41p第4章 公钥密码因此有 24121pp可见，是的一个平方根。另一个平方根是
38、p-，这是因为 (p-)2=p2-2p+2=2 mod p结论结论：对于p2的素数，它的平方剩余有两个根：(4-19)41ppp 和 41第4章 公钥密码 【例1】=2是否为二次剩余方程为x2=mod 23的平方剩余？如果是，求方程的根。解解：由 =211 mod 23=2048mod23=1知=2确为平方剩余，且 =11为奇数。于是模23运算下=2的两个根是:和 2=23-18=521p21p1823 mod226411p第4章 公钥密码 2.为偶数的情况为偶数的情况 令p-1=2hq，q为奇数(p-1被2连除h次才能得到奇数q)，可以证明以下几条：(1)若是NQR，则r=q满足 =1mod
39、p。(2)=-1mod p。(3)若QR，则存在偶数 j(0 j 2h)使q=rj。(4)r-jq+1=。(5)令j=2k(0k2k-1)，则 21phr212kr为奇数若为偶数若 1 1)(22kkkq第4章 公钥密码 证明证明：(1)因为假定为NQR，所以 (2)因为 ，而r=q，p1=2hq，所以(3)由于QR，因此又由于(2)的结论，因此若j为偶数，则 121pppqh mod 1)(12pp mod 121qqh 1221pr)(hhqp mod 1112221phqp mod 1)(1221prrhhjj mod 1)()(1122第4章 公钥密码比较可见:q=rj (0 j 2h
40、)(4)由q=rj就有r-jq=1，即 r-jq+1=或写为 (r-j/2(q+1)/2)2=表明(r-j/2)(q+1)/2是的一个平方根。再利用(1)的结果就有 2/221221jqjqhrr第4章 公钥密码 (5)令 j=2k，则q=rj=r2k,所以 奇数 1为偶数 11)()()()(1222222kkkkkqhhhrr 利用以上性质，得到计算平方根的算法如下：S1：通过测试(p-1)/2=p-1mod p=p-1modp，来选择1，p-1为NQR。S2：取值rq,q，I=h，J=1，K=0。S3：若 ，则转S5。S4：JJ 。S5：若I=2则作：rJ-1(q+1)/2，r即的平方根
41、，结束。S6：II-1，KK+1,转S3。Kr2)(1122IIJ第4章 公钥密码 3.n非素数，特别当非素数，特别当n=pq(p，q均为素数均为素数)x2=bmodn的讨论的讨论 x2=bmodn等价于两个联立方程：x2=bmodp和x2=b mod q。(1)当 和 均为奇数的情况。由于它们分别有 和 个QR，因此原方程有 个QR。两个方程分别有解为：和 ；和 。现在求x2=b mod n的解，必须是两个方程都满足的共同解。其次，应将解得区域1，p-1和1，q-1扩展到1，n，为此，第一个方程的解系可由 和 21p21q21p21q)1)(1(41qp41pb41pbp41qb41qbq4
42、1pb41pbp第4章 公钥密码加上p的整数倍得到，第二个方程的解系可由 和 加上q的整数倍得到。最后，从两个解系中找到共同的四个解。41qb41qbq 【例2】p=3，q=7，n=21,求解x2=1 mod 21。解解：因为 和 都是奇数，所以：显然b=1满足 和 ，故知b=1是平方剩余。故：和p-1=2是x2=1 mod p的两个解；和q-1=6是x2=1 mod q的两个解；21p21q121pb121qb1411bbxp12412bbxq第4章 公钥密码 第一个方程解系为1，2，1+3，2+3，1+6，2+6,；第二个方程解系为1，6，1+7，6+7，1+14，6+14,；共同解为1=
43、1和2=8，另外两个是21-1=20和21-2=13。还可验证b=4也是平方剩余。这是因为 =41mod p=1和 =43 mod q=64 mod 7=1。故：x1=b1=4 mod 3=1和 p-x1=3-1=2是方程x2=4 mod 3的两个解；x2=b2=16 mod 7=2和q-x2=7-2=5是方程x2=4 mod 7的两个解；21pb21qb41pb41qb第4章 公钥密码 扩展后的解系为1，2，4，5，7，8,和2，5，9，12,共同解为1=2和2=5，另两个是21-2=19和21-5=16。还可以验证b=16是平方剩余。这是因为 =16 mod p=1和 =163 mod q
44、=23 mod q=1。故:x1=16 mod p=1和p-x=2是方程x2=16mod3的两个解；x2=162 mod q=4 mod 7和q-4=3是方程x2=16 mod 7的两个解；2116p2116q41pb41qb第4章 公钥密码 扩展后的解系为1，2，4，5，7，8，10，11,和3，4，10，11,共同解为1=4，2=10,另外两个是21-4=17和21-10=11，共有 (p-1)(q-1)=3个QR。41 (2)或 为偶数的情况。这时，不能直接代公式写出它的解 或 ，然而如果用其他方法，比如穷举试解法(或用计算机程序搜索)得到了一个解，则求另一个解和共同解的做法同上。21p
45、21q41pb41qb第4章 公钥密码 【例3】p=13，q=5，n=65，求解x2=1 mod 65。解解:这时 =6,=2,均为偶数,因此它共有 (p-1)(q-1)=12个QR，不难验证b=1是p和q的平方剩余。对于b=1，有 =b1=1和 =b2=1，因此有:x2=1 mod p的解是x=1和x=p-1=12；x2=1 mod q的解是x=1和x=q-1=4。从而，解系为1，12，14，25，和1，4，6，9，11，14，；共同解为x=1，x=14，以及65-1=64和65-14=51。21p21q4121pb21qb第4章 公钥密码4.4.2Rabin密码的安全性密码的安全性 先来证
46、明，求解一个属于QR元素的平方根的计算，等价于分解n为因子的计算。如果能分解n=pq，则解x2=a mod n等价于解x2=a mod p和x2=a mod q。设它们的解分别是x1和x2，且|x1|x2|，则有：即 (x1+x2)(x1-x2)=0 mod n (4-21)它等价于p|(x1+x2)而q|(x1-x2)，或者p|(x1-x2)而q|(x1+x2)。其中，p和q不能同时整除(x1+x2)和(x1-x2)。nxx mod 2221(4-20)第4章 公钥密码 求出了x1和x2就等于求出了p和q。表明二次剩余的复杂度与分解大数相同，也就是说Rabin的复杂度不低于RSA，它除了求两
47、平方根问题外，还要求解中国剩余问题(二方程联立求平方剩余)。第4章 公钥密码4.5ElGamal公钥系统公钥系统(基于离散对数基于离散对数)ElGamal公钥系统是基于GF(p)域中离散对数的Np复杂性而设计的。4.5.1基本算法基本算法 设p是素数，g是 中的本原元素，选取0，p-1，计算：=gmod p (4-22)设私有密钥为k2=,公有密钥为k1=(g,p),则对于待加密消息m，选取随机数k0，p-1，加密算法为*pZ)()(211y,yk,mEk(4-23)第4章 公钥密码其中：y1=gk mod p,y2=mk mod p (4-23)解密算法为 pyyy,yDk mod)()(1
48、12212(4-24)这是因为 pmgmggmyykkkk mod)(112(4-24)算法中离散对数的复杂性决定了系统的安全，然而，算法的设计是基于 群是p为模的同余乘法群，对乘法满足封闭性，且存在乘法模逆元。如果p不是素数，则(模p)同余类群Zp只能是以加法为运算的整数群，只存在加法模逆元，只对加法满足封闭性，离散对数的关系就不存在了。*pZ第4章 公钥密码4.5.2有限群上的离散对数公钥体系有限群上的离散对数公钥体系 将 群推广到一般的有限群G，便得到推广的ElGamal公钥体制。设群G是运算符为*的有限群，G，H是由生成的G的子群，H=ii0，选取aH，计算=a,则私有密钥为a,公有密
49、钥为、。对于明文m，选择随机数k0，|H|-1,则加密算法为*pZ)()(211y,yk,mEk(4-25)其中：y1=k，y2=mk (4-26)解密算法为第4章 公钥密码myyakkakkmm)(112这是因为：112)()21(2yyy,yDk4.5.3离散对数计算法离散对数计算法 离散对数公钥体系的安全性是基于计算离散对数的复杂性的。无论从破译(分析)这种公钥体系的还是从改进(提高)这种公钥体系的安全性出发，都应了解计算离散对数的方法。离散对数是模幂运算的逆运算。计算模幂ax并不困难。将x表达为二进制形式：x=b0+b12+b222+bn-12n-1 (4-28)则第4章 公钥密码pa
50、aaaanbnbbbx mod)()()(112102222式中,bi=0的因子代之为1，bi=1的因子都化为a的各级二次幂。如求5375 mod 1823,则因为 375=(101110111)2=1+2+22+24+25+26+28所以 5375=552545165325645256求出5=5，52=25，54=625后，继续求得：58=6252 mod 1823=503，516=5032 mod 1823=1435 532=14352 mod 1823=1058，564=10582 mod 1823=42 5128=422 mod 1823=1764，5256=17642 mod 182
