公钥密码系统

第4章公钥密码体系1NetworkandInformationSecurity第4章公钥密码体系第4章公钥密码体系2NetworkandInformationSecurity主要内容4.1公钥密码概述4.2RSA密码系统4.3Diffie-Hellman密钥交换4.4数字签名4.5数字签名的算法4.6PGP第4章公钥密码体系3问题的提出：•传统的对称加密仅用一个密钥，由发送方和接收方共享•如果密钥公开，则通信是不安全的•存在的问题：无法保护发送方，如果接收方伪造一个消息并宣称是由发送发发送的密钥的分配：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，如何安全交换密钥？密钥管理问题若N个人相互保密通信，每人必须拥有（N-1)个密钥，N很大时，需要保存的密钥很多。如何解决？在有多个用户的网络中，任何两个用户之间都需要有共享的密钥。思考：需要的密钥量是多少？NetworkandInformationSecurity第4章公钥密码体系4挑战！NetworkandInformationSecurity第4章公钥密码体系5公钥加密算法NetworkandInformationSecurity第4章公钥密码体系6NetworkandInformationSecurity1公钥的起源公钥密码体系于1976年由美国斯坦福大学的W.Diffie和M.Hellman提出。公钥密码又叫非对称密码，这种密码体系的基本思想:将密钥K一分为二，一个专门加密，一个专门解密，即ke≠kd可以将ke公开，密钥量小，分配比较简单有ke不能计算出kd，所以kd便成为用户的指纹，实现数字签名。4.1公钥密码概述第4章公钥密码体系7NetworkandInformationSecurity2数学原理--陷门单向函数•公钥密码系统是基于陷门单向函数的概念。•陷门单向函数：单向函数是求逆困难的函数，而单向陷门函数，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。–单向陷门函数f(x)，必须满足以下三个条件。①给定x，计算y=f(x)是容易的；②给定y,计算x使y=f(x)是困难的（所谓计算x=f-1(y)困难是指计算上相当复杂已无实际意义）；③存在δ，已知δ时对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。注：仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ称为陷门信息。第4章公钥密码体系8NetworkandInformationSecurity（1）发送者用加密密钥PK（publickey）对明文X加密后，接收者用解密密钥SK（securekey）解密，即可恢复出明文，或写为：DSK(EPK(X))X此外，加密和解密的运算可以对调，即EPK(DSK(X))X。（2）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X))X（3）在计算机上可以容易地产生成对的PK和SK。（4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可行的”。（5）加密和解密算法都是公开的。3公开密钥算法的特点第4章公钥密码体系994.公钥密码系统可用于以下三个方面：(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。这时，通过公钥或密文分析出明文或私钥是不可行的。如图所示，Bob拥有多个人的公钥，当他需要向Alice发送机密消息时，他用Alice公布的公钥对明文消息加密，当Alice接收到后用她的私钥解密。由于私钥只有Alice本人知道，所以能实现通信保密。Alice的公钥Joy明文输入加密算法，如RSA传输密文解密算法明文输出Alice的私钥Bob的公钥环TedAliceMike第4章公钥密码体系1010(2)数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。如图所示，Bob用私钥对明文进行加密并发布，Alice收到密文后用Bob公布的公钥解密。由于Bob的私钥只有Bob本人知道，因此，Alice看到的明文肯定是Bob发出的，从而实现了数字签名。Bob的公钥Joy明文输入加密算法，如RSA传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMike第4章公钥密码体系11NetworkandInformationSecurity(3)密钥交换：通信双方交换会话密钥，这种应用也称为混合密码系统，即用常规密码体制加密需要保密传输的消息本身，然后用公钥密码体制加密常规密码体制中使用的会话密钥，将两者结合使用，充分利用对称密码体制在处理速度上的优势和非对称密码体制在密钥分发和管理方面的优势。第4章公钥密码体系12第4章公钥密码体系13第4章公钥密码体系14NetworkandInformationSecurity5对称密钥与非对称密钥的比较第4章公钥密码体系15NetworkandInformationSecurity4.2RSA密码系统4.2.1RSA算法1977年由Rivest、Shamir和Adleman在麻省理工学院发明，1978年公布第一个比较完善的同时也是应用最广泛的公钥密码算法。第4章公钥密码体系16RSA的基本原理:RSA是基于大整数难分解的公钥密码技术。大整数的分解问题可以被表述：已知整数n，n是两个素数的积，即n=p.q。求解p、q的值。大整数分解是计算上困难的问题，目前还不存在一般性的有效解决算法。NetworkandInformationSecurity第4章公钥密码体系17RSA的数学基础除数(因子)：设z为由全体整数而构成的集合，若b≠0且a，b，m∈z，使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).素数：对一个自然数P，如果P只能被1和自身除尽时，则称P为素数（或质数），否则为合数。例：100以内的素数共有25个：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97第4章公钥密码体系18最大公约数与互为素数：设且a，b，c∈z，如果c|a,c|b，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足：（1）d是a和b的公约数；（2）对a和b的任何一个公约数c，有c|d.a和b的最大公约数记为gcd(a,b)=d。如果gcd(a,b)=1，则称a与b是互素的，即a和b互为素数。例：8和15是互素的，即gcd（8，15）＝1。NetworkandInformationSecurity第4章公钥密码体系1919整数同余：设n是一个正整数，a,b∈Z，如果amodn=bmodn，则称a和b模n同余，记作a≡b(modn)，称整数n为同余模。模m求余运算称为模运算,下面是模运算的一些性质。(1)(a+b)modm=((amodm)+(bmodm))modm(2)(a-b)modm=((amodm)-(bmodm))modm(3)(a×b)modm=((amodm)×(bmodm))modm(4)(a×(b+c))modm=(((a×b)modm)+((a×c)modm))modm(5)a8modm=(a×a×a×a×a×a×a×a)modm化简为：((a2modm)2modm)2modm第4章公钥密码体系2011mod8=3；15mod8=7（11+15）mod8=26mod8=2[（11mod8）+（15mod8）]mod8=（3+7）mod8=2（11-15）mod8=-4mod8=4[（11mod8）-（15mod8）]mod8=（3-7）mod8=4（11*15）mod8=165mod8=5[（11mod8）*（15mod8）]mod8=（3*7）mod8=5计算117mod13112=121≡4mod13114=（112）2≡16mod13≡3mod13117=11*112*114≡11*4*3mod13≡132mod13≡2mod13第4章公钥密码体系21加法逆元：对于a∈Zn，存在b∈Zn，使得a＋b≡0（modn）,则b是a的加法逆元。记b=-a。例：11＋15≡0（mod26），则称11模26的加法逆元是15即-11（代表11模26的加法逆元）的结果为15乘法逆元：设a∈Zn，如果存在b∈Zn满足a×b≡1(modn)，则称b是a的模n乘法逆元，记为x=a-1(modn)7×15≡1(mod26)，则称7模26的乘法逆元是15加法一定存在逆元，乘法不一定存在逆元。第4章公钥密码体系2222欧几里德算法用途：(1)求两个正整数的最大公约数性质1：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)(a=b)可重复使用上式求出最大公约数。重复计算结束的条件是后一个整数等于0，此时前一个数即为二者的最大公约数。例：求gcd(18,12)=gcd(12,18mod12)=gcd(12,6)=gcd(6,12mod6)=gcd(6,0)=6第4章公钥密码体系23NetworkandInformationSecurity用途：(2)两个正整数互素，可以求一个数关于另一个数的乘法逆元性质2：若gcd(n,a)=1,则a在模n下有乘法逆元（设an）即存在xn,ax=1modn第4章公钥密码体系24求解乘法逆元的方法扩展的欧几里得算法:求d关于模f的乘法逆元d-1，即d×d-1modf=1①(X1,X2,X3)=(1,0,f)；(Y1,Y2,Y3)=(0,1,d)②if(Y3=0)thenreturnd-1=null//无逆元③if(Y3=1)thenreturnd-1=Y2//Y2为逆元④Q=X3divY3//整除，取商⑤(T1，T2，T3)=(X1-Q×Y1，X2-Q×Y2，X3-Q×Y3)⑥(X1，X2，X3)=(Y1，Y2，Y3)⑦(Y1，Y2，Y3)=(T1，T2，T3)⑧Goto②第4章公钥密码体系25例如：k=7,求解7-1（7关于模26的乘法逆元）循环次数QX1X2X3Y1Y2Y3初值无1026017130171-35211-35-14232-1423-111-11即为求得的结果，是11关于模26的加法逆元，即15。思考：k=550求解550-1（550关于模1769的乘法逆元）550-1mod1769=550第4章公钥密码体系26费马（Fermat）定理描述1：若p是素数，a是正整数且gcd（a,p）=1，则ap-1≡1（modp）描述2：对于素数p，若a是任一正整数，则ap≡a（modp）例：p=5,a=3,则35-1=81≡1mod535=243≡3mod5NetworkandInformationSecurity第4章公钥密码体系27欧拉函数欧拉函数φ(m)：当m1时，φ(m)表示比m小且与m互素的正整数的个数。例：m＝24，比24小且与24互素的正整数有：1、5、7、11、13、17、19、23，共8个。因此φ(24)＝81）m是素数，则φ(m)=m-12)m=pq,且p和q是互异的素数，则φ(m)=φ(p)φ(q)=(p-1)(q-1)例：φ(21)=φ(3)φ(7)=（3-1)(7-1)=12,这12个数是{1,2,4,5,8,10,11,13,16,17,19,20}欧拉定理：对于任何互素的两个整数a和m，有aφ(m)≡1(modm)例：设a=4，m=5则有φ(5)=4，44=256，256≡1(mod5)aφ(m)+1≡a(modm)第4章公钥密码体系28RSA密码算法•RSA密码体制(安全性基于大整数因子分解的困难性）–明文和密文均是0到n之间的整数，n通常为1024位二进制数或309位十进制数–明文空间P=密文空间C={x∈Z|0xn,Z为整数集合}。•RSA密码的密钥生成具体步骤如下：①选择互异的素数p和q，计算n=pq，(n)=(p-1)(q-1)；②选择整数e，使gcd((n),e)=1，且1e(n)；③计算d，de-1mod(n)，即d为模(