1、1第五章 公钥密码技术2n一、公钥密码体制的提出n对称密钥密码体制存在的问题n密钥分配与管理问题密钥分配与管理问题n密钥空间大：传统密钥管理两个用户之间分别用一密钥空间大：传统密钥管理两个用户之间分别用一对密钥时，则对密钥时，则n个用户需要个用户需要C(n,2)=n(n-1)/2个密钥，个密钥，当用户量很大时，密钥空间急剧增大，如当用户量很大时，密钥空间急剧增大，如 n=100时，时，c(100,2)=4,950 n=1000时，时，c(1000,2)=499,500n密钥通过网络进行密钥分配时容易被截获或冒领。密钥通过网络进行密钥分配时容易被截获或冒领。n签名验证问题签名验证问题n传统加密算
2、法无法实现抗抵赖的需求传统加密算法无法实现抗抵赖的需求5.1概述34n一、公钥密码体制的提出n19761976年年,斯坦福大学的博士生斯坦福大学的博士生DiffieDiffie和其导和其导师师HellmanHellman在在密码学的新方向中首次提出了公钥密码的观点，标志密码学的新方向中首次提出了公钥密码的观点，标志着公钥密码学研究的开始着公钥密码学研究的开始。W.Diffie and M.E.Hellman,New direction in W.Diffie and M.E.Hellman,New direction in cryptography,IEEE Trans.on Informat
3、ion Theory,1976,cryptography,IEEE Trans.on Information Theory,1976,IT-22.(6),pp.644-654.IT-22.(6),pp.644-654.n19771977年由罗纳德年由罗纳德李维斯特李维斯特(Ron Rivest)(Ron Rivest)、阿迪、阿迪萨莫尔萨莫尔(Adi Shamir)(Adi Shamir)和伦纳德和伦纳德阿德曼阿德曼(Leonard Adleman)(Leonard Adleman)一起提一起提出了第一个比较完善的公钥密码算法，即出了第一个比较完善的公钥密码算法，即RSARSA算法，并且算法，
4、并且在在19781978年首次公布。年首次公布。n公钥密码体制的出现在密码学历史上是迄今为止最大的、公钥密码体制的出现在密码学历史上是迄今为止最大的、而且是惟一真正的革命。而且是惟一真正的革命。5.1概述5n二、公钥密码体制的原理n公钥密码体制也称非对称密码体制；公钥密码体制也称非对称密码体制；n公钥密码算法是基于数学函数（如单向陷门函数）而不是公钥密码算法是基于数学函数（如单向陷门函数）而不是基于代替和置换基于代替和置换n公钥密码算法要求每个参与方拥有一对相关的密钥公钥密码算法要求每个参与方拥有一对相关的密钥K K=(=(P PK K,S SK K)：n一个公开，称为公开密钥一个公开，称为公
5、开密钥P PK K ，用于加密，用于加密 n另一个保密，称为私有密钥另一个保密，称为私有密钥S SK K ，用于解密，用于解密n在计算上由在计算上由P PK K推出推出S SK K是困难的是困难的.n加密和解密会使用两把不同的密钥，因此称为非对称加密和解密会使用两把不同的密钥，因此称为非对称5.1概述6n二、公钥密码体制的原理n公钥密码算法具有以下重要特性：公钥密码算法具有以下重要特性：n仅仅知道密码算法和加密密钥而要确定解密密钥，仅仅知道密码算法和加密密钥而要确定解密密钥，在计算上是不可能的；在计算上是不可能的；n两个相关密钥中任何一个都可以用作加密而让另两个相关密钥中任何一个都可以用作加密
6、而让另外一个用作解密。外一个用作解密。n公钥可以被任何人知道，用于加密消息以及验证公钥可以被任何人知道，用于加密消息以及验证签名；签名；n私钥仅仅自己知道的，用于解密消息和签名私钥仅仅自己知道的，用于解密消息和签名n例如，例如，RSARSA算法。算法。5.1概述7n二、公钥密码体制的原理5.1概述消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源SKBPKB图5-1 公钥密码体制的加解密原理图8n二、公钥密码体制的原理5.1概述消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PKASKA图 公钥认证模型95.1概述消息加密算法解密算法消息MXC接收方B发送方A密钥源PKASK
7、A图图 公钥密码体制的保密和认证公钥密码体制的保密和认证加密算法X解密算法M密钥源SKBPKB接收方：接收方：C=EPKBESKAM发送方：发送方：C=EPKBESKAM1011n公开密钥加密既可以使用本方的私有密钥，也可以使用对方的公开密钥。n加密加密n使用对方使用对方B的公开密钥的公开密钥KUB进行加密可以实进行加密可以实现数据的加密。现数据的加密。n鉴别鉴别n而使用本方而使用本方A的私有密钥的私有密钥KRA进行加密实现进行加密实现鉴别。鉴别。n加密与鉴别加密与鉴别5.1概述12n公钥密码体制的特点n新用户的增加只需要产生一对公共新用户的增加只需要产生一对公共/私有密钥，私有密钥，密钥分配
8、过程简单。密钥分配过程简单。n只有在用户的私有密钥被破坏时，才需要进行只有在用户的私有密钥被破坏时，才需要进行密钥重建；密钥重建；n非对称密钥加密提供了认证功能。非对称密钥加密提供了认证功能。n加密和解密较常规密钥密码体制慢。加密和解密较常规密钥密码体制慢。5.1概述13常规加密与公钥密码的比较需要澄清的问题：需要澄清的问题：公开密钥加密方法要比传统的加密方法公开密钥加密方法要比传统的加密方法更加安全？更加安全？事实上，任何加密方案的安全程度都依赖于密钥的长度和事实上，任何加密方案的安全程度都依赖于密钥的长度和破译密码所需要的工作量。破译密码所需要的工作量。145.1概述n三、三、Diffie
9、-Hellman密钥交换算法密钥交换算法nDiffie-Hellman密钥交换是密钥交换是W.Diffie和和M.Hellman于于1976年提出的第一个公开密钥算法。年提出的第一个公开密钥算法。n该算法的安全性基于求离散对数的困难性。该算法的安全性基于求离散对数的困难性。n算法的惟一目的是使得两个用户能够安全地交换算法的惟一目的是使得两个用户能够安全地交换密钥，得到一个共享的会话密钥。密钥，得到一个共享的会话密钥。n算法本身不能用于加、解密。算法本身不能用于加、解密。155.1概述n三、Diffie-Hellman密钥交换算法16本原元并不唯一（本原元并不唯一（1919本原元还有本原元还有2
10、 2，3 3，1010，1313，1414，1515），不是所有的整数都有本原元。，不是所有的整数都有本原元。175.1概述n三、Diffie-Hellman密钥交换算法离散对数的离散对数的难解性：难解性：离散对数的离散对数的概念：概念：18三、Diffie-Hellman密钥交换算法19三、Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换20三、Diffie-Hellman密钥交换算法21三、Diffie-Hellman密钥交换算法22三、Diffie-Hellman密钥交换算法23nRSA算法是罗纳德罗纳德李维斯特李维斯特(Ron Rivest)(Ron Riv
11、est)、阿、阿迪迪萨莫尔萨莫尔(Adi Shamir)(Adi Shamir)和伦纳德和伦纳德阿德曼阿德曼(Leonard Adleman)(Leonard Adleman)于1977年研制并于1978年首次发表的一种算法。n它是第一个既能用于数据加密，也能用于数字签名的公开密钥密码算法。5.2 RSA公钥密码24n依据的依据的原理是原理是：寻求两个大素数的乘积比寻求两个大素数的乘积比较简单，而将它们的乘积分解开较简单，而将它们的乘积分解开(因式分解因式分解)则极其困难。则极其困难。5.2 RSA公钥密码7310713911391可以分解成哪两个素数的积？25nRSA算法包括三个部分：n密钥
12、的产生密钥的产生n加密加密n解密解密算法描述26n密钥的产生n选择两个大素数选择两个大素数p,q（p,q保密）；保密）；n计算计算n=pq（n公开）；公开）；n计算计算(n)=(p-1)(q-1)，(n)是是n的欧拉函数；的欧拉函数；n选择整数选择整数e，使得，使得gcd(n),e)=1,1 e(n)（e公开）；公开）；n计算计算d，使得，使得ed=1 mod(n)，即，即d是是e在模在模(n)下的乘法逆元；下的乘法逆元；n公钥公钥KU=e,n，私钥，私钥KR=d,n或或d,p,q算法描述27n加密/解密n明文以分组为单位加密，每个分组是小于明文以分组为单位加密，每个分组是小于n的的二进制值二
13、进制值nM表示明文，表示明文，C表示密文表示密文n加密形式如下：加密形式如下：nC=Me mod n 用公钥用公钥e,nn解密形式如下：解密形式如下：nM=Cd mod n 用私钥用私钥d,n 算法描述28n例子：例子：n选择两个素数选择两个素数p=3，q=17；n计算计算n=pq=317=51；n计算计算(n)=(p-1)(q-1)=32；n选择选择e，使，使1 e (n)且与且与(n)互素，取互素，取e=13；n计算计算d，使得，使得ed=1 mod(n)，即，即ed=k(n)+1，取，取k=2，则，则d=5。n最终，加密密钥为最终，加密密钥为13,51，解密密钥为，解密密钥为5,51。n
14、加密：令明文加密：令明文M=2，密文，密文C=Me mod n=213 mod 51=8192 mod 51=32n解密：解密：M=Cd mod n=325 mod 51=512 mod 51=2算法描述29算法描述n例子：设p=7，q=11，e=13，求n、(n)和d。n例子：设p=7，q=17，e=5，明文m=19求(n)，d和密文C。30n使用RSA时的计算问题n加密与解密过程加密与解密过程nRSA密钥的产生密钥的产生 RSA算法中的计算问题31n加密与解密过程n加密与解密过程均涉及计算一个大整数的整数加密与解密过程均涉及计算一个大整数的整数次幂，然后取模。如果先对整数进行指数运算，次幂
15、，然后取模。如果先对整数进行指数运算，然后进行模然后进行模n运算，则中间结果非常大。运算，则中间结果非常大。n需要用到快速指数计算法需要用到快速指数计算法RSA算法中的计算问题32快速指数算法快速指数算法1 am mod nn将将m表示为二进制形式表示为二进制形式bkbk-1b0，c=0;d=1;for i=k downto 0 do c=2c;d=(dd)mod n;if bi=1 then c=c+1;d=(da)mod n;return d;RSA算法中的计算问题33RSA算法中的计算问题快速指数算法快速指数算法2 am mod nn将将m表示为二进制形式表示为二进制形式bkbk-1b0
16、，n1.b=m,c=a,d=1;n2.如果如果b=0,输出结果输出结果d；n3.如果如果b是奇数，转到是奇数，转到5；n4.b=b/2;c=c2 mod n,转到转到3；n5.b=b-1;d=(cd)mod n,转到转到2.34RSA算法中的计算问题n例例P82页：页：30 37 mod 77 35nRSA密钥的产生n在使用公开密钥密码系统之前，每个参与者都在使用公开密钥密码系统之前，每个参与者都必须产生一对密钥。必须产生一对密钥。n产生密钥时，需要考虑以下问题：产生密钥时，需要考虑以下问题：n确定两个大素数确定两个大素数p和和q；n选择选择e，并且计算，并且计算d。RSA算法中的计算问题36
17、n确定两个大素数确定两个大素数p和和qn因为因为n=pq在公钥体制中是公开的，因此为了防止在公钥体制中是公开的，因此为了防止敌手通过穷举攻击发现敌手通过穷举攻击发现p和和q，这两个素数应该是从，这两个素数应该是从足够大的集合中选取的大素数。足够大的集合中选取的大素数。n寻找大素数的过程如下：寻找大素数的过程如下：随机选取一个大的奇数；随机选取一个大的奇数；使用素性检验算法检验该奇数是否为素数；使用素性检验算法检验该奇数是否为素数；若不是素数则选取另一个大的奇数，重复这一过若不是素数则选取另一个大的奇数，重复这一过程，直至找到大素数为止。程，直至找到大素数为止。RSA算法中的计算问题37nRSA
18、算法的安全性是基于对大整数进行因子分解的困难性。n可能的对RSA的攻击方法包括：n选择密文攻击、公共模数攻击、低指数选择密文攻击、公共模数攻击、低指数攻击、定时攻击等。攻击、定时攻击等。5.2.6 RSA的安全性38n选择密文攻击 一般攻击者是将希望解密的信息C作一下伪装reC，让拥有私钥的实体解密。然后，经过解密计算就可得到它所想要的信息。(reC)d=red*Cd mod n=r*M mod n，所以 M=(reC)d*r-15.2.6 RSA的安全性395.2.6 RSA的安全性n公共模数攻击公共模数攻击若系统中用户共有一个模数若系统中用户共有一个模数n n，而拥有不同的，而拥有不同的e
19、 e和和d d。若存在同一信息（设为。若存在同一信息（设为P P）分别用不同）分别用不同的公钥（的公钥（e1e1和和e2e2）加密，）加密，C1=PC1=Pe1e1 mod n mod n；C2=pC2=pe2e2 mod n mod n 设密码分析者截获设密码分析者截获n n、e1e1、e2e2、C1C1和和C2C2，若恰若恰好好e1e1和和e2e2互质，则他可以得到互质，则他可以得到P P。405.2.6 RSA的安全性n公共模数攻击公共模数攻击 证明：因为证明：因为e1和和e2互质，故用扩展的欧几里得互质，故用扩展的欧几里得算法能找到算法能找到r和和s，满足：，满足：r*e1+s*e2=
20、1 则则 (C1)r*(C2)s=(Pe1)r*(pe2)s mod n =P r*e1+s*e2 mod n=P mod n415.2.6 RSA的安全性n低指数攻击低指数攻击为了缩短加密时间，使用小的加密指数为了缩短加密时间，使用小的加密指数e e是非是非常诱人的。普通的常诱人的。普通的e e值是值是e=3e=3。不过有几种针。不过有几种针对低加密指数的潜在攻击。为了阻止这些类型对低加密指数的潜在攻击。为了阻止这些类型的攻击，我们推荐使用的攻击，我们推荐使用e=2e=21616-1=65535.(-1=65535.(或者或者一个接近这个值的素数一个接近这个值的素数)。当解密指数过小的时候，
21、攻击者可以计算出解当解密指数过小的时候，攻击者可以计算出解密指数密指数d d425.2.6 RSA的安全性n定时攻击定时攻击RSA核心运算是非常耗时的模乘，如果能够精确的监核心运算是非常耗时的模乘，如果能够精确的监视视RSA的解密过程，获得解密时间，就可以估算出私的解密过程，获得解密时间，就可以估算出私有密钥有密钥D。如果私密指数如果私密指数d中的相关比特是中的相关比特是0的话，这种算法只应的话，这种算法只应用平方；如果相关的位是用平方；如果相关的位是1，这种算法就既应用平方也，这种算法就既应用平方也应用乘法，完成每一个迭代需要的时序会更长。应用乘法，完成每一个迭代需要的时序会更长。根据执行时
22、间来判断当前位是根据执行时间来判断当前位是0还是还是1，这种方法实际，这种方法实际操作很困难。操作很困难。435.2.6 RSA的安全性nRSA存在很多种攻击，并不是因为算法本存在很多种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成身存在缺陷，而是由于参数选择不当造成的，为保证算法足够安全，需要仔细选择的，为保证算法足够安全，需要仔细选择参数。参数。445.4 ElGamal密码系统nElGamal是是1985年由年由T.EIGamal提出的一提出的一个著名的公钥密码算法个著名的公钥密码算法n该算法既能用于数据加密也能用于数字签该算法既能用于数据加密也能用于数字签名名n其安全性是依
23、赖于计算有限域上离散对数其安全性是依赖于计算有限域上离散对数这一难题这一难题 455.4 ElGamal密码系统n密钥产生密钥产生任选一个大素数任选一个大素数p，使得，使得p-1有大素因子，有大素因子，g是是模模p的一个本原根，公开的一个本原根，公开p与与g。使用者任选一私钥使用者任选一私钥x，x0,p-1计算公钥：计算公钥：y=gx mod p公开公钥：公开公钥：y,p,g保密私钥：保密私钥：x465.4 ElGamal密码系统n加密过程加密过程：设欲加密明文消息为M.随机选一与p-1互素的整数k，0=k=p-1；计算密文对:C=C1,C2,发送给接收者nc1=gk mod pnc2=ykm
24、 mod p475.4 ElGamal密码系统n解密算法解密算法:设密文为设密文为c=(c1,c2),则明文为则明文为pcwxmod)(11pwcmmod2先计算：先计算：再计算明文：再计算明文：485.4 ElGamal密码系统1)密钥生成密钥生成.选择公开参数：p=97 及本原根 a=5；Bob 选择 秘密钥xB=58，计算并发布公钥y yB B=5=55858=44 mod 97.=44 mod 97.2)Alice 要加密要加密 M=3M=3 给给 Bob.首先得到 Bob的公开密钥 yB=44，选择随机 k=36 计算:yBK=4436=75 mod 97.计算密文对:C1=536=
25、50 mod 97；C2=75*3 mod 97=31 mod 97.发送 50,31 给Bob.3)Bob 解密消息解密消息.恢复消息密钥 K=5058=75 mod 97.Bob 计算 K-1=22 mod 97.Bob 恢复明文 M=31*22=3 mod 97.49本章结束5051练习1np=7,q=11,e=17,m=8n求d和密文。n解 n=pq=77n(n)=60n(17,60)=1n60=173+9 (1)9=60-173 (1)n17=91+8 (2)8=17-91 (2)n9=81+1 (3)1=9-81 (3)n1=602-177nd=17-1mod 60=-7 mod
26、60=53ned=1753=901=900+1=6015+1n1753=6015+1nC=memodn817mod7752练习2n2、设p=47，q=59，则n=2773n令d=157，n求（1）en （2）明文M=7，密文是多少n （3）用程序实现53n3、设p=7，q=11。n求（1）n=？(n)=?n （2）e=7,d=？n （3）明文M=88，密文是多少n （4）用程序实现n解 d=4354设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是C=10，求明文M.2.在ElGamal加密体制中，设素数p=71，本原根g=7.1)如果接收方B的公开钥是yB
27、=3，发送方A选择的随机整数k=2，求明文M=30所对应的密文.2)如果A选择另一个随机整数k，使得明文M=30加密后的密文是C=(59,C2)，求C2.555.2.6 RSA的安全性|p-q|要大.如果如果|p-q|较小较小,则则(p+q)/2 n1/2,(p-q)/2)2=(p+q)/2)2-n.可求出可求出p和和q.例例:对于对于n=164009,有有n1/2 405.令令 (p+q)/2=405,(p-q)/2)2=4052-n=16 p+q=810,p-q=8 p=409,q=401 164009=409 401.p和q要足够大:n=pq 为1024位,或2048位565.2.6 R
28、SA的安全性p-1和q-1的最大公因子要小 设攻击者截获到密文设攻击者截获到密文 y1=xe mod n 迭代加密迭代加密:yi=yi-1e=xe e e mod n(i=2,3,4,)如果有如果有i使得使得:di=1 mod (n),则有则有:yi=x mod n 因此因此,如果如果i很小很小,则容易求得明文则容易求得明文x.由由Euler定理和定理和di=1 mod (n),可得可得 i=(n)=(p-1)(q-1)=D (p-1)(q-1)/(D),其中其中D=gcd(p-1,q-1).当当D小时小时,(D)就小就小,从而从而i大大.575.2.6 RSA的安全性p-1和q-1的最大公因
29、子要小 设设p和和q是理想的强素数是理想的强素数,即即 p=2a+1,q=2b+1 (a,b为奇素数为奇素数)D=2,(D)=1,i=2(a-1)(b-1).例例:设设p=17,q=11,n=187,d=7,D=gcd(p-1,q-1)=gcd(16,10)=2.对对x=123,有有 y1=1237=183 mod 187 y2=y17=1837=72 mod 187 y3=y27=727=30 mod 187 y4=y37=307=123 (=x)mod 187.585.2.6 RSA的安全性加密指数e 的选择 为使加密速度快为使加密速度快,应使应使e的二进制表示中的二进制表示中,1的个的个数尽量小数尽量小,但不能太小但不能太小.可取可取:e=3,216+1=65537(在二进制表示中只有在二进制表示中只有2个个1).解密指数d的选择 在在d的二进制表示中的二进制表示中,1的个数尽量小的个数尽量小,但不能太但不能太小小.3d n1/4.人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。
