加密技术(2)研公钥密码体系(自学)

1、2006计算机网络安全概论计算机网络安全概论1附2 数据加密技术2006计算机网络安全概论计算机网络安全概论2信源编码器信道解码器接收者秘密信道密 码 分 析者密钥源密钥源2006计算机网络安全概论计算机网络安全概论3u传递信息是否安全？传递信息是否安全？uA P B2006计算机网络安全概论计算机网络安全概论4u使用钥匙是否可保证安全？使用钥匙是否可保证安全？uA Bu密钥发布（密钥发布（Distribution）或交换（）或交换（exchange）2006计算机网络安全概论计算机网络安全概论5u76年Diffie和Hellman发表了“密码学的新方向”，奠定了公钥密码学的基础uDiffie

2、-Hellman密钥交换协议算法u使用此方法确定对称密钥交换Ralph Merkle,and independently Marty Hellman Whit Diffie,invented the notion of public-key cryptography.In November 1976,Diffie and Hellman published Directions in Cryptography, proclaiming “We are at the brink of a revolution in cryptography.”2006计算机网络安全概论计算机网络安全概论6u78

3、年，RSA算法u公钥技术是二十世纪最伟大的思想之一 v改变了密钥分发的方式v可以广泛用于数字签名和身份认证服务RSA(Ron Rivest,Adi Shamir,Len Adleman,1977)2006计算机网络安全概论计算机网络安全概论7uAlice与ob确定两个大素数n和g，这两个整数不保密， Alice与ob 可以使用不安全信道确定这两个数uAlice选择另一个大随机数x，并计算A如下： A=gx mod nuAlice将发给obuob选择另一个大随机数y，并计算B如下： B=gy mod nuob将发给Aliceu计算秘密密钥K1如下： K1=Bx mod nu计算秘密密钥K2如下：

4、 K2=Ay mod n2006计算机网络安全概论计算机网络安全概论8uAlice与ob确定两个大素数n和g，这两个整数不保密， Alice与ob 可以使用不安全信道确定这两个数设设 n=11,g=7n=11,g=7uAlice选择另一个大随机数x，并计算A如下： A=gx mod n设设 x=3,x=3,则则 A = 7A = 73 3 mod 11 = 343 mod 11 = 2mod 11 = 343 mod 11 = 2uAlice将发给ob AliceAlice将发给将发给obobuob选择另一个大随机数y，并计算B如下： B=gy mod n设设 y=6,y=6,则则 B = 7

5、B = 76 6 mod 11 = 117649 mod 11 = 4mod 11 = 117649 mod 11 = 4uob将发给Aliceobob将将4 4发给发给AliceAlice2006计算机网络安全概论计算机网络安全概论9u计算秘密密钥K1如下： K1=Bx mod n有有 K1 = 4 K1 = 43 3 mod 11 = 64 mod 11 = 9mod 11 = 64 mod 11 = 9u计算秘密密钥K2如下： K2=Ay mod n 有有 K2 = 2 K2 = 26 6 mod 11 = 64 mod 11 = 9 mod 11 = 64 mod 11 = 92006

6、计算机网络安全概论计算机网络安全概论10u安全性在于有限域中的离散对数计算难度比同一个域中的指数计算难得多vAlice在第步的计算：K1=Bx mod nB=gy mod nK1=（gy）x mod n=gyx mod nvBob在第步的计算：K2=Ay mod nA=gx mod n K2=（gx）y mod n=gxy mod nvK1=K2=K uAlice与Bob交换n、g 、A 、B。根据这些值并不容易求出x（Alice知道）和 y（ Bob知道）,数学上对于足够大的数，求x与y是相当复杂的ua b(mod n) a0而0bn, b是a/n的余数，a为同余例：2311(mod 12)

7、u求模指数y=ax mod nu求一个数的离散对数求x，使ax b(mod n) 2006计算机网络安全概论计算机网络安全概论11u A、B(A-B) 1u A、B、C (A-B 、 A-C 、 B-C ) 3u A、B、C 、D (A-B 、 A-C 、 A-D 、 B-C 、 B-D 、 C-D ) 6u n n*(n-1)/2u N=1000 499500u 钥匙的管理非常复杂（引入管钥匙的T）2006计算机网络安全概论计算机网络安全概论12u 中间人攻击Alicen=11,g=7Tomn=11,g=7Bobn=11,g=71Alicex=3Tomx=8,y=6Boby=92AliceA

8、=gx mod n =73 mod 11 =2TomA=gx mod n =78 mod 11 =9BobB=gy mod n =79 mod 11 =83B=gy mod n =76 mod 11 =42006计算机网络安全概论计算机网络安全概论13A=2A=2截获A=A=B=8B=8A=4A=442006计算机网络安全概论计算机网络安全概论14AliceA=2, B=4TomA=2, B=8BobA=9, B=85AliceK1=Bx mod n =43 mod 11 =9TomK1=Bx mod n =88 mod 11 =5BobK2=Ay mod n =99 mod 11 =56K2

9、=Ay mod n =26 mod 11 =92006计算机网络安全概论计算机网络安全概论15uA、B不必同时访问T以获得密钥对uB访问T取得一个锁和密钥（K1）,将锁和密钥（K1）发给AuB告诉A可以使用这个锁和密钥（K1）封箱uB拥有不同组相关的密钥（K2）， B从T取得（K2） ，是根据锁和密钥（K1）求出的，只有（K2）可用于开（K1）加的锁u一个密钥（K1）用于封箱，一个密钥（K2）用于开锁u这里引入T为可信任的第三方， T经过认证，是高度可靠和高效的机构 B拥有密钥对K1和K2，K1用于封箱，K2用于开锁，B可以将锁与钥匙K1 发给任何人（如A），使其可以安全的向B发消息。B请求发

10、送方（如A）用锁与钥匙K1 封住内容，然后B 可以用密钥K2开锁这里密钥K1是公开的，称为公钥（Public key）,另一个密钥K是私有的的，称为私钥（Private key）2006计算机网络安全概论计算机网络安全概论16u A、B(A-B) u A、B、C (A-B 、 A-C 、 B-C ) u A、B、C 、D (A-B 、 A-C 、 A-D 、 B-C 、 B-D 、 C-D ) u n nu N=1000 1000 u 1000个锁，1000个公钥，1000个私钥2006计算机网络安全概论计算机网络安全概论172006计算机网络安全概论计算机网络安全概论182006计算机网络安

11、全概论计算机网络安全概论19u涉及到各方：发送方、接收方、攻击者u涉及到数据：公钥、私钥、明文、密文u公钥算法的条件：v产生一对密钥是计算可行的v已知公钥和明文，产生密文是计算可行的v接收方利用私钥来解密密文是计算可行的v对于攻击者，利用公钥来推断私钥是计算不可行的v已知公钥和密文，恢复明文是计算不可行的v(可选)加密和解密的顺序可交换2006计算机网络安全概论计算机网络安全概论20u公钥和私钥必须相关，而且从公钥到私钥不可推断v必须要找到一个难题，从一个方向走是容易的，从另一个方向走是困难的v如何把这个难题跟加解密结合起来u数学上是用一个单向陷门函数描述,满足下列条件的函数f:v给定定义域内

12、的任意x，计算y=f(x)是容易的v给定y,计算x使y=f(x)是困难的，即要求出x=f-1(y)在计算上是不可行的v存在某个，当它已知时，对任何给定的y，若相应的x存在，则计算x使y=f(x)是容易的单向函数陷门性公钥私钥2006计算机网络安全概论计算机网络安全概论21u与计算复杂性计算复杂性理论密切相关v基于大整数因式分解问题（RSA体制）v以大素数为模，计算离散对数问题(Elgamal体制,椭圆曲线密码体制)u计算复杂性理论可以提供指导v但是需求不尽相同计算复杂性通常针对一个孤立的问题进行研究而公钥密码学往往需要考虑一些相关的问题比如，密码分析还需要考虑已知明文、选择明文等相关的情形v讨

13、论的情形不同计算复杂性考虑最坏的情形而对于公钥密码学则是不够的u一个np问题必然会导致一个保密性很好的密码系统吗？v不一定，还需要有好的构造2006计算机网络安全概论计算机网络安全概论22uEL Gamal算法v取P为质数，随机数gP,xP,计算y=gx mod P,(y,g,p)为公开密钥，x为隐蔽密钥。v选取随机数k,使K与p-1互质；v计算a=gk mod p ; b=ykM mod pv a和b构成密文，它比明文M长一倍；v解密时计算M=b/ax mod p2006u大整数因数分解问题v两个素数pq，计算积容易n=pXqv给定n,求两个素因子pq,使n=pXq难v这是RSA算法未被破译

14、的前提假设条件2006u离散对数问题v已知有限循环群G=gk|k=0,1,2,及其生成元g和阶n=|G|.v给定整数a ,计算ga=h容易；v给定元素h,计算整数x,0=x=n,使得gx=h非常困难vDH、RSA算法的假设前提2006u椭圆曲线离散对数问题v已知有限域Fp上的椭圆曲线点群E(Fp)=(x,y) 属于Fp X Fpy2=x3+ax+b,a,b属于Fp UO点P=（x,y）的阶为一个大素数则：给定a,计算点aP很容易给定Q,计算整数x,使xP=Q非常困难。这是椭圆加密算法的前提假设2006计算机网络安全概论计算机网络安全概论26u1977年由Ron Rivest、Adi Shami

15、r和Len Adleman发明，1978年公布u是一种块加密算法。u应用最广泛的公钥密码算法u只在美国申请专利，且已于2000年9月到期2006计算机网络安全概论计算机网络安全概论27u素数只能被和本身整除的数（、）uRSA算法思想：v两个大素数很容易相乘v而对得到的积求因子则很难vRSA中的私钥和公钥基于大素数（100位以上）v难度在于RSA选择和生成私钥和公钥2006计算机网络安全概论计算机网络安全概论28u产生密钥对v选择两个大素数p,q, pqv计算n=pq,(n)=(p-1)(q-1)v选择整数e（公钥，即加密密钥）,使gcd(e,(n)=1v选择整数d（私钥，即解密密钥）,使d*e

16、 mod (n) =1 u公钥: KU=e,n, 私钥: KR=d,nu使用v加密: C = Me mod nv解密: M = Cd mod n明文明文密文密文2006计算机网络安全概论计算机网络安全概论29u计算d=am, m=bkbk-1b0(二进制表示)d1for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod nreturn du原理：M = (bk2+bk-1)2+bk-2)2+bk-3)2+)2+b02006计算机网络安全概论计算机网络安全概论30u产生密钥对v选择两个大素数p=7,q=17, pqv计算n=pq=7*17=1

17、19,(n)=(p-1)(q-1)=6*16=96,96的因子有2,2,2,2,2和，因此e不能有2和3的因子v选择整数e=5（公钥，即加密密钥）,使gcd(e,(n)=1v选择整数d=77（私钥，即解密密钥）,使d*e mod (n) =1 (5*77) mod 96 = 385 mod 96 =1u公钥: KU=e,n=5,119, 私钥: KR=d,n=77,119u使用v加密: C = Me mod nv解密: M = Cd mod n2006计算机网络安全概论计算机网络安全概论31用用A=1、B=2等编码原字符等编码原字符求出明文求出明文e的幂（这里是的幂（这里是5）将结果除以将结果

18、除以119，得到余数，得到余数，即为密文即为密文求出密文求出密文d的幂（这里是的幂（这里是77）将结果除以将结果除以119，得到余数，即，得到余数，即为明文为明文用用A=1、B=2等译码原字符等译码原字符使用公钥的加密算法使用公钥的加密算法使用私钥的解密算法使用私钥的解密算法FF=66565 Mod 119=4141774177 Mod 119=66=F41F2006计算机网络安全概论计算机网络安全概论32u块大小为k, 2k n 2k+1v明文信息M n u加密: C = Me mod nu解密: M = Cd mod n = Med mod nu公钥: KU=e,n, 私钥: KR=d,n

19、u上述算法需要满足以下条件:v能够找到e,d,n,使得Med mod n = M, 对所有Mnv计算Me和Cd相对容易v从e和n得到d是在计算上不可行的公开公开2006计算机网络安全概论计算机网络安全概论33u令n=pq, pq都是素数,(n)=(p-1)(q-1)是n的Euler函数uEuler定理推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mnmk(n)+1 m mod n, 对任意0mnu只要选择e,d, 满足ed=k(n)+1,即 ed mod (n) 1 ed 1 mod (n) d e-1 mod (n)u公钥:

20、KU=e,n, 私钥: KR=d,n即选择e或d,使e与(n) 互质2006计算机网络安全概论计算机网络安全概论34u素数的产生取大数n（100位以上的整数）和整数an, 计算an-1modn 若结果不为1，则n必不为质数 否则n不为质数的概率大约10-13u大整数模运算v许多实际应用的RSA系统中，模数至少取512位，更多的建议使用1024位2006计算机网络安全概论计算机网络安全概论35u产生两个素数v由于n = pq是公开的，所以，为了防止攻击者利用n获得p和q，必须选择足够大的素数p和qv大素数产生算法u选择e或者d，然后求出另一个2006计算机网络安全概论计算机网络安全概论36u素数

21、生成过程: 随机选择一个奇数n 随机选择a, 使an 进行素性测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到 如果通过了足够次数的测试,认为n是素数,否则转到.u素数理论: 在N附近，每ln(N)个整数中有一个素数2006计算机网络安全概论计算机网络安全概论37u基于数学的攻击（30年研究）公钥: KU=e,n, 私钥: KR=d,n, n=pqv分解n=pq (n)=(p-1)(q-1) d=e-1 mod (n)v不求出p,q,直接求(n) d=e-1 mod (n)v不求出(n),直接计算dv500位10进制数需要1025年u结论v已知的方法至少跟因子分解一样

22、难度v尚未发现多项式时间的因子分解算法v因子分解的算法已经取得了长足进步u措施: 选择足够大的n(1024位以上),并且使得e,d之间相差不太大,也不太小2006计算机网络安全概论计算机网络安全概论38 19851985年，年，N.KoblitzN.Koblitz及及V.S.MillerV.S.Miller分别提分别提出了椭圆曲线密码体制（出了椭圆曲线密码体制（ECCECC），只是为公钥），只是为公钥密码需要的复杂数学运算提供了另一种方案。密码需要的复杂数学运算提供了另一种方案。与其他公钥密码体制相比，椭圆曲线密码体制与其他公钥密码体制相比，椭圆曲线密码体制的优点主要表现在以下的优点主要表现在

23、以下4 4个方面：个方面：(1) (1) 密钥尺度较小；密钥尺度较小；(2) (2) 参数选择比较灵活；参数选择比较灵活；(3) (3) 具有由数学难题保证的安全性；具有由数学难题保证的安全性；(4) (4) 实现速度较快。实现速度较快。2006计算机网络安全概论计算机网络安全概论39u椭园曲线曲线E是具有如下形式的函数图：是具有如下形式的函数图：vE：y2 = x3 + ax +b, 其中还包括一个无穷远点其中还包括一个无穷远点O。u椭园曲线（曲线（E）上两点的和运算，就是连接两点）上两点的和运算，就是连接两点做直线，并与做直线，并与椭园曲线相交于另外一点，该交点曲线相交于另外一点，该交点关

24、于关于x轴的对称点就是和。则轴的对称点就是和。则是一阿贝尔是一阿贝尔群。群。v POOPPv P1=（x1,y1), P2=(x2,y2)v if P1 P2 x3= m2 - x1 - x2, y3= m(x1-x3)-y1, m=(y2-y1)/（x2-x1)v If P1 = P2x3= m2 - x1 - x2, y3= m(x1-x3)-y1 mod p， m =(3 x12 + a)/(2y1) mod p2006计算机网络安全概论计算机网络安全概论40u信息m与点 的对应关系u假设有一正整数k满足pMk.使得对任意的消息m, 0mM-1,1jk,满足 使其有解，取其中的一个解为m

25、对应E上的点。反过来对于点Pm=(xm,ym),令 m=(xm-j)/k, 则得到点Pm与m的对应关系。 显然k是存在的，具体取值，要视所选取的曲线而定。P(,)mmmxy23()()(mod)ymkja mkjbp,P(,)mmmmyxy则2006u算法v准备工作 选择有限域Fq、椭圆曲线E、G（x,y),把明文编码到曲线上的点（xm,ym).选择私钥n,计算公钥P=nG对于A：私钥为na,公钥为Pa=naG; 对于B：私钥为nb,公钥为Pb=nbG; v加密：对于任何想发送消息给A的人 选择一个随机整数k,生成密文 Cm=k(x,y),(xm,ym)+kPav解密：A用私钥恢复明文 计算n

26、a(k(x,y)），再计算 （xm,ym)+kPa-na(k(x,y)=（xm,ym)2006例：y2= x3 +11 x + 19 (mod 167) 及 点（2，7）uAlice选择A=15， B选择 B=22，则vAlice计算 A（2，7）=15（2，7）=（102，88）发给bobvBob计算B（2，7）=22（2，7）=（9，43）发给AlicevAlice 对 Bob发来的结果使用她的密码A进行X运算A（9，43）= 15（9，43）=（131，140）vBob 对Alice发来的结果使用他的密码B进行X运算B（102，88）=22（102，88）=（131，140）计算机网络安

27、全概论计算机网络安全概论422006计算机网络安全概论计算机网络安全概论43 CerticomCerticom公司对公司对ECCECC和和RSARSA进行对比后发现，进行对比后发现，在实现相同安全性的情况下，在实现相同安全性的情况下，ECCECC所需要的密所需要的密钥量要比钥量要比RSARSA少的多少的多ECC的密钥长度RSA的密钥长度Mips年16010241012320512010366002100010781200120000101682006计算机网络安全概论计算机网络安全概论44ECCECC特别适用于以下情况：特别适用于以下情况：(1) (1) 无线无线ModemModem的实现。为

28、分组交换数据网提供加密。在移动通信器的实现。为分组交换数据网提供加密。在移动通信器件上运行件上运行4MHz4MHz的的68330CPU68330CPU，则可实现快速的，则可实现快速的Diffie-Hellman Diffie-Hellman 密钥交密钥交换，并极小化密钥交换所占用的宽带，并将计算时间从换，并极小化密钥交换所占用的宽带，并将计算时间从6060秒降到秒降到2 2秒秒以内。以内。(2) Web(2) Web服务器实现服务器实现在在web web 服务器上集中进行密码计算就会形成瓶颈，服务器上集中进行密码计算就会形成瓶颈，WebWeb服务器上的宽服务器上的宽带有限使宽带费用增高，而采用

29、带有限使宽带费用增高，而采用ECCECC后就可节省时间和宽带，且通过后就可节省时间和宽带，且通过算法的协商也比较容易处理兼容性方面的问题。算法的协商也比较容易处理兼容性方面的问题。(3) (3) 集成电路卡的实现集成电路卡的实现ECCECC无需协处理器就可以在标准卡上实现快速、安全的数字签名，而无需协处理器就可以在标准卡上实现快速、安全的数字签名，而RSARSA体制难以做到。而且体制难以做到。而且ECCECC可使程序代码、密钥、证书的存储空间极可使程序代码、密钥、证书的存储空间极小化，数据帧最短，便于实现，从而大大降低了小化，数据帧最短，便于实现，从而大大降低了ICIC卡的成本。卡的成本。20

30、06特征对称密钥加密非对称密钥加密加密/解密使用的密钥相同不相同加密/解密的速度快慢得到的密文长度等于或小于明文长度大于明文长度密钥协定与密钥交换大问题没问题所需密钥数量和消息交换参与者个数的关系大约为参与者个数的平方,伸缩性不好等于参与者个数,伸缩性好用法主要用于加密/解密(保密性),不能用于数字签名(完整性和不可抵赖检查)可以用于加密/解密(保密性)和数字签名(完整性和不可抵赖检查)网络与信息安全网络与信息安全452006加密对称密钥用户A 明文明文 密文密文用户B的公钥数字信封解密用户B 明文明文hash摘要摘要签名签名签名签名A证书证书B证书证书用户A的私钥用户B的私钥对称密钥 密文密文解密 明文明文签名签名A证书证书签