第6章 公钥密码学

1、1/ 第六章第六章 公钥密码学公钥密码学 2公钥密码学提出的背景1密钥管理的困难性问题 传统密钥管理两两分别用一对密钥时则n个用户需要n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。2系统的开放性问题 对称密码体制的密钥分发方法要求密钥共享各方互相信任，因此它不能解决陌生人间的密钥传递问题 3数字签名问题 对称加密算法难以实现抗抵赖的安全需求。3密钥分发 DES提供了高效的密码系统，保障商家通讯不受到商务对手的攻击。用民用计算机来破解DES加密的密文几乎是不可能的，因为可能的密钥数目是十分大的。不幸的是，尽管DES强大，尽管DES提供了加密标准，商家们还要解决另一个密码通讯中存在的问题

2、，这个问题称作“密钥分发”。 很久以来“密钥分发”的问题一直困扰着密码专家。比如，二战时，德国高级指挥部每个月都需要分发每日密钥月刊给所有的“思格玛”机操作员。而且，即使u型潜艇大多数时间都远离基地，它也不得不想办法获得最新的密钥。 美国政府的密钥是COMSEC(通讯安全局的缩写)掌管和分发的1970年代，COMSEC每天分发的密钥数以吨计。当装载着COMSEC密钥的船靠港时，密码分发员会到甲板上收集各种卡片、纸带以及软盘和其他一切贮存密钥的介质。然后，把它们分发给客户。4公钥密码学的思想 公钥密码也称为非对称密码。使用公钥密码的每一个用户都分别拥有两个密钥：加密密钥与解密密钥，它们两者并不相

3、同，并且由加密密钥得到解密密钥在计算上是不可行的。每一个用户的加密密钥都是公开的。 不对称密码可以这样来理解：任何人只需按一下就可以把锁关上，但只有有钥匙的人才能把锁打开。关锁(加密)是容易的，人人都可以做到，但开锁(解密)只能由有钥匙的人来做了。知道关锁的知识毫无助于开锁。5公钥密码算法 公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥（简称公钥）用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥（简称私钥），用于解密。因此，公钥密码体制也称为双钥密码体制。 为了把不对称密码这个概念变成可实行的密码系统必须有人找到一个合适的数学函数。

4、这就是陷门单向函数。 单向陷门函数 单向陷门函数可以被定义为如下函数f： （1）给出f的定义域中的任意元素x, f(x)的计算是容易的； （2）给出y=f (x)中的y要计算x时，若知道设计函数f时结合进去的某种信息（该信息称为陷门），则容易计算；若不知道该信息，则难以计算。6公钥密码学的应用 （1） 机密性的实现 发送方用接收方的公钥加密消息，接收方用自己的私钥来解密。 （2） 数字签名 发送方用自己的私钥来签名消息，接收方通过发送方对应的公钥来鉴别消息，并且发送方不能对自己的签名进行否认。 （3） 密钥分发和协商 发送方和接收方基于公钥密码系统容易实现在公开信道上的大规模的密钥分发和协商。

5、7公钥密码体制认证框图 公钥密码体制认证框图公钥密码体制认证框图8公钥密码体制基于的困难问题 已经出现的并且仍然具有较高安全性的公开密钥密码体制所基于的困难问题有：1、大整数分解问题； RSA公钥密码体制 2、ZP上的离散对数问题； ElGamal公钥密码体制3、椭圆曲线上的离散对数问题；4、线性编码的解码问题；5、构造非线性弱可逆有限自动机的弱逆问题（基于有限自动机的公开密钥密码体制，它是我国学者陶仁骥等提出的一种公开密钥密码体制） 9数学背景 欧拉函数(m)：为小于或等于m且与m互素的正整数个数 定理 若p为素数，则(p)(p1)。如p和q为两个素数，则(pq)(p1)(q-1) 欧拉定理

6、(Euler定理): 设m2, 且(a,m)=1,则: a(m)1(mod m). 例1 求132001被15除所得的余数。解：因为(13,15)1，所以13(15)1(mod 15)。因为(15)(35)8，而200125081，所以1381(mod 15)，132001(138 )25013 13(mod 15)，即被15除所得的余数为13。10RSA密码算法 RSA公钥算法是由MIT的Rivest, Shamir和Adleman在I978年提出来的。RSA方案是被最广泛接受并实现的通用公开密钥密码算法，目前已成为公钥密码的国际标准。该算法的数学基础是初等数论中的欧拉定理，其安全性建立在大

7、整数因子分解的困难性之上。 Rivest和Shamir是计算机学家，Adleman是一位非常有能力的数学家，他负责挑出Rivest和Shamir的错误，以使他们在错误的道路上少浪费时间。 据英国政府声称，他们在切尔特汉姆的政府通讯总部很早就发明了公开密钥密码术。 1969年年初英国军方请求詹姆斯埃利斯，一位前英国政府的密码专家，找到一种能应付密钥分发问题的方法。埃利斯的个性有点古怪。他很骄傲地吹嘘他在出生前就绕着地球转了半圈他是在英国受孕的，却是在澳大利亚出生的。 11RSA密码算法 埃利斯的想法与Shamir、Rivest和Adleman的很相似，只是比他们提前了好几年。然而，没有人知道埃利

8、斯的工作因为他是英国政府的雇员，而且要发誓保密。到1969年末，埃利斯看来已经陷入了僵局，他已证明公开密钥是可能的，他也发明了公开密钥和私人密钥的概念。 接下来的三年中，政府通讯总部的最聪明的头脑努力寻找一个能满足埃利斯要求的单向函数，但毫无结果。 1973年9月，一个年轻的数学家加入了这个小组，克利福德科克斯。刚刚毕业于剑桥大学，是一个纯粹的数学家。 六个星期后，佩特森告诉科克斯，之所以告诉科克斯这个想法，是因为这是密码学中最让人兴奋的想法，而不是指望他能够解决这个问题。科克斯回忆到：“从开始到结束，我总共没花半个小时的时间，我对自己很满意，我想哦，这很好，别人给我提了一个问题，而我解决了。

9、”12RSA算法描述 （1）密钥的生成 1. 选择两个大素数 p，q，（p，q为互异素数，需要保密）， 2. 计算n = pq， (n) = (p1)(q1) 3. 选择整数 e 使 (n)，e) =1, 1e (n) 4. 计算d，使d = e1mod (n), 得到：公钥 为e,n； 私钥为d （2）加密(用e，n)：明文：Mn，密文 C= Me(mod n) （3）解密(用d，n)： 密文C， 明文 M = Cd(mod n)13举例例：设p=3, q=5, 则 n=p*q=3*5=15, (n)=(p-1)(q-1) =2*4=8取d=3, 则e=3, 因为ed 1mod (n) 1m

10、od8加密：1. 假设明文m=7, 则密文c=me=73 13(mod 15)解密：已知密文c=13, 则可如下恢复明文： m=cd=133 7(mod 15)2. 假设明文m=9(注意(9,15)不互素), 则密文c= me = 93 9(mod 15)解密：已知密文c=9, 则可如下恢复明文： m= cd= 93 9(mod 15)14RSA的证明证明：由加密过程知cme mod n，所以：cd mod nmed mod nm 1mod (n) mod n m k (n)+1 mod n下面分两种情况加以介绍。1）m与n互素，则由Euler定理得：m (n) 1modn, m k (n)

11、1 mod n, m k (n)+1 m mod n, 则cd mod nm。2) gcd(m,n)1，m是p的倍数或q的倍数，设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，与mn=pq矛盾。由gcd(m,q)=1及Euler定理得m (q) 1modq,，所以：m k (q) 1 mod q, (m k (q) (p) 1 mod q, m k (n) 1 mod q因此存在一整数r，使得： m k (n) 1 +rq两边同乘以m=cp得：m k (n)+1 m+rcpq=rcn+m即m k (n)+1 m mod n 。 所以，cd mod nm。15对素

12、数的认识 1、如果每个人都需要一个不同的素数，难道素数不会被用光吗？当然不会，事实上，小于n的素数的总数为n/(lnn)，这个结论称为素数个数定理。例：小于10100 的素数个数x=10100/ln10100 ln10100log210100=100*log210 10100/400 2、是否会有两个人偶然地选择了同样的素数的情况呢？这种情况不会发生。 从M个素数中选出q个素数，至少有两个素数相同的概率至少为1/2，此时q=1.17M1/2 3、如果有人建立了所有素数的数据库，难道他不能用这个数据库来破译公开密钥算法？ 4、产生素数困难吗？16素数的产生 现在还没有产生任意的大素数的有用技术，

13、因此解决这个问题需要其他方法。通常在使用过程中随机选取一个需要的数量级的奇数并检验这个数是否是素数。如果不是，则选取后继的随机数直到找到了通过检验的素数为止。 检验素数性方面已经出现了许多方法。几乎所有的检验方法都是概率性的，即这个检验只是确定一个给定的整数可能是素数。虽然缺乏完全的确定性，但是这些检验在运行时可以按照需要做到使得概率尽可能地接近1。 一般的，选取一个素数的过程如下：1）随机选一个奇数n(例如使用伪随机数产生器)；2）用某种概率性算法（如Miller-Rabin算法）对n进行一次素性检验，如果n没有通过检验，转到步骤1；3）重复步骤2足够多次，如果n都通过了检测，则认为n为素数

14、。 17RSA的实现 大数运算. 如何快速的计算am (mod n)求am可如下进行，其中a,m是正整数：将m表示为二进制形式bkbk-1b0，即：m=bk2k+bk-12k-1+b12+b0因此，例如：19=124+023+022+121+120，所以：a19=( a1)2 a0)2 a0)2 a1)2 a1注意一点，即所有的乘法或乘方运算之后都有一个模运算。1012222(.() .)kkbbbbmaaaaa18如：如：56mod 21=?6=(110)2d=1, i=2d=1*1=1; b2=1; d=1*5=5i=1d=5*5 4mod21; b1=1; d=4*5=20i=0d=40

15、01mod21;b0=0;结束结束算法：算法：d=1;for i=k downto 0 d (dd) mod n; if bi=1 then d (da) mod n return dRSA的实现19RSA的安全性 RSA的安全性-为什么要保密p,q,d d是私钥，当然要保密。为什么要保密p,q？也就是说为什么RSA是基于大数分解难题的？因为知道了p, q. 也就是说知道了n的因子分解，就可以算出Euler函数(n)=(p-1)(q-1)， 也就可以利用辗转相除法，根据ed1 mod (n), 由e求出d. 因为基于大整数分解的公开密钥体制的安全性依赖于大整数（大合数分解）问题，所以RSA的安

16、全性完全依赖于大数分解问题。但这只是一个推测，目前，还未能从数学上证明由c和e计算出m一定需要分解n。然而，如果新方法能使密码分析者推算出d，它也就成为大数分解的一个新方法。而且这种方法并不比分解n容易。 20RSA的安全性 形如p=2p1+1,p1也是素数的素数p，通常称为安全素数，也即: 在RSA中，(p-1)/2和(q-1)/2都应该是素数。也即: * p-1和q-1的最大公因子应该较小， * p-1和q-1都应有大的素因子。如23,47,83等是满足此特征的小素数。 安全素数是RSA算法中p, q选择必须满足的条件。安全素数的个数是否有限未能得到证明。21RSA安全性 |q p|要大设

17、q-p=k, 则：(q+p)2-(q-p)2=4pq=4n (q+p)2= (q-p)2 +4n=k2+4n如果k的值小，则可以容易找到这样的k,使得k2+4n是一个完全平方数，从得出q+p和q-p的值，联立求解可得到q、p。例：q=313,p=311,则n=97343, (q+p)2 =3893764n=389372, 则(q+p)2-4n4，很简单就得到了k的值。所以，q, p的差必须很大，最好差几个比特位。22RSA的安全性 不同用户不可共享模n（共模攻击） 假定用户B1与B2共享模数为n，它们的加密密钥分别是e1和e2，且（e1, e2）=1，某用户对同一消息m分别以e1和e2加密得到

18、密文c1与c2。 攻击者截获密文c1与c2后，由于(e1, e2)=1，攻击者能够（使用扩展欧几里德算法）计算得到r与s满足re1+se2=1，然后，攻击者将进行如下计算。12ee12c m mod n c m mod n1212eere +sersrs12c c mod n (m ) (m ) mod n mm23RSA的安全性 公开钥e：实际中加密指数e一般取3或者216+1=65537 ，这两个数的二进制表示中只有两个1。e=3时，加密只需要一次模乘法和一次模平方，e=65537时加密只需要16次模平方和一次模乘法，这使得加密运算非常快。 216+1优于3之处在于它能够抵抗对RSA公钥密

19、码的低指数攻击，因为同样的消息不可能发给(216+1)个接收者。 e和d也有些要求，如e不可太小，否则不安全。比如D欲向A、B、C三人送去信息m，A、B、C三人的eA=eBeC=3，nA,nB,nC无公因数 (因为若nA,nB有公因数，则求nA,nB的公因数便可将nA和nB因数分解)。则对密文： c1m3mod nA , c2m3mod nB, c3m3mod nC 利用中国剩余定理可求得解：m3mod(nA nB nC) 因为m3(nA*nB*nC),所以只要对m3开立方即可求得m。24RSA的安全性 不同用户选用的素数不能相同 若用户B1与B2选用了同一个素数p，设n1=pq1与n2=pq

20、2分别是他们的模数，那么任何人都可以用欧几里德算法求得(n1,n2)=p，从而得到n1与n2的分解式。当然，就是有用户选用了相同的素数，遭到攻击的可能性也是微乎其微，但我们应该尽量避免。 密钥泄漏 如果私钥d被泄露，则在模n的情况下重新计算一对密钥是不够的，而是必须选择一个新的公钥n. 从已知的算法可知，在私钥d泄露的情况下，可以成功分解n的成功概率至少为1/2. 说明：我们知道ed 1mod(n), 也即ed=k(n)+1.但是知道e,d并不能一下子就求得(n)，因为k的取值范围也很大，然而利用已知的算法是可以分解n的，请看例子。25密钥泄露例：设p=9103, q=9871,则n= pq=

21、89 855713取e=34 986 517,则d=82 330 933ed=2 880 472 587 030 361ed-1=2 880 472 587 030 360(n)=9870*9102=89 836 740(ed1)/(n)=32 063 414由此例可以看出，知道d的值并不是可以很快就能求出(n)的值，也就不能很快分解n,但有算法已经证明知道d是可以分解n的，成功的概率为1/2。所以，一旦d泄露，就要更换n.26RSA的安全性问题 按照攻击者占有资源的不同，攻击者分为 选择明文攻击者 CPA 选择密文攻击者 CCA1 适应性选择密文攻击者 CCA2 注意到RSA算法满足如下的性

22、质： (m1* m2)emod n= (m1e * m2e)mod n 现在设想一个适应性密文攻击者获得了消息m的密文c，其可以选择密文m，并询问密文(m)e *c所对应的明文，按照上边的关系，我们知道其明文是(m * m)，则c对应的明文易得。 最佳非对称填充（OAEP)27本原根 设n为正整数，对于am1 mod n,如果(a,n)=1,则至少有一个整数m满足这一方程，称满足方程的最小正整数m为模n下a的阶 如果a的阶m (n) ，则称a为n的本原根（本原元）, 例如模素数7的一个本原根是3 整数a是模n的一个本原根，如果对于每个与n互素的x都存在一个整数l，使得 al x mod n 并

23、非所有整数都有本原元，只有以下形式的整数才有本原元：2，4，pa, 2pa(a1,p为奇素数）28Elgamal公钥密码体制 ElGamal密码体制是T.ElGamal于1985年提出，是最有名的公钥密码体制之一，它的安全性是基于离散对数问题. 设p至少是150位的十进制素数，p-1有大素因子。Zp为有限域，若g为Zp中的本原元，有 Zp* 若取Zp*=Zp0，如何算得唯一得整数a， (要求，0 a p-2)，满足 ga=(mod p) 称为离散对数问题，将a记为a=logg 一般来说，求解a在计算上是难处理的。29算法描述 1密钥的生成 选取大素数p， gZp*是一个本原元（生成元）。p、g 作为系统参数所有用户共享。系统中每个用户U都随机挑选整数x，2 x p2，并计算： y= g x(mod p)， (p,g,y)作为用户U的公开密钥，而x作为用户U的秘密密钥 2. 加密：(1) 用户A先把明文M编码为一个在 0 到(p1)之间的整数m ；(2) 用户A挑选一个秘密随机数 r ( 2 r p2 )， 并计算： c1 g r (mod p)；c2 m yr (mod p)