1、第四章第四章 公钥密码公钥密码4.1 4.1 数论简介数论简介4.2 4.2 公钥密码体制的基本概念公钥密码体制的基本概念4.3 4.3 RSARSA算法算法4.4 4.4 背包密码体制背包密码体制4.5 4.5 RabinRabin密码体制密码体制4.6 4.6 NTRUNTRU公钥密码系统公钥密码系统4.7 4.7 椭圆曲线密码体制椭圆曲线密码体制4.8 4.8 基于身份的密码体制基于身份的密码体制2022-9-264.2 公钥密码体制的基本概念 Basic Concept of Public Key Cryptography2022-9-26公钥密码体制的原理公钥密码体制的原理公钥体制公
2、钥体制(Public key system)(Diffie(Public key system)(Diffie和和Hellman,1976)Hellman,1976)每个用户都有一对选定的密钥每个用户都有一对选定的密钥(公钥公钥k k1 1；私钥；私钥k k2 2)，公开的，公开的密钥密钥k k1 1可以像电话号码一样进行注册公布。可以像电话号码一样进行注册公布。主要特点：主要特点：n加密和解密能力分开加密和解密能力分开n多个用户加密的消息只能由一个用户解读，（用于公共多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）网络中实现保密通信）n只能由一个用户加密消息而使多个用户可
3、以解读（可用只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。于认证系统中对消息进行数字签字）。n无需事先分配密钥。无需事先分配密钥。解决了单钥密码体制中最难解决的解决了单钥密码体制中最难解决的两个问题：数字签字、密钥分配两个问题：数字签字、密钥分配2022-9-26公钥体制加密公钥体制加密 公钥体制加、解密公钥体制加、解密 mm=D D (c c)=)=D DSKBSKB(E EPKBPKB(mm)安全保障安全保障从公开钥从公开钥PKPKB B和密文和密文c c要推出明文要推出明文mm或解密钥或解密钥SKSKB B在计算上是在计算上是不可行的。不可行的。由于任
4、一用户都可用用户由于任一用户都可用用户B B的公开钥的公开钥PKPKB B 向他发送机密消息，向他发送机密消息，因而密文因而密文c c不具有认证性。不具有认证性。发送者A加密算法PKB密钥源SKB解密算法接收者B密码分析员mcmmSKB2022-9-26公钥密码认证体制公钥密码认证体制 用户用户A A以自己的秘密钥以自己的秘密钥S Sk kA A对消息对消息mm进行进行A A的专用变换的专用变换D DSKASKA，A A计算密文：计算密文：c c=D DSKSKA A(mm)送给用户送给用户B B，B B验证验证c c：mm=E EPKAPKA（c c）=E EPKAPKA(D DSKASKA
5、(mm)安全性：安全性：由于由于S Sk kA A 是保密的，其他人都不可能伪造密文是保密的，其他人都不可能伪造密文c c，可用，可用A A的的 公开钥解密时得到有意义的消息公开钥解密时得到有意义的消息mm。因此可以验证消息。因此可以验证消息mm来自来自A A而不是其他人，而实现了对而不是其他人，而实现了对A A所发消息的认证。所发消息的认证。发送者A加密算法SKA密钥源PKA解密算法接收者B密码分析员mcmSKA2022-9-26公钥保密和认证体制公钥保密和认证体制公开保密公开保密保密保密认证认证为了同时提供认证功能和保密性，可使用双重加、解密为了同时提供认证功能和保密性，可使用双重加、解密
6、加密加密c=Ec=EPKBPKBEESKASKAmm解密解密m=Dm=DPKAPKADDSKBSKBcc2022-9-26公钥密码应满足的要求公钥密码应满足的要求n接收方接收方B B产生密钥对在计算上是容易的产生密钥对在计算上是容易的n发送方发送方A A用收方的公开钥对消息用收方的公开钥对消息mm加密以产生密文加密以产生密文c c在在计算上是容易的。计算上是容易的。n收方收方B B用自己的秘密钥对密文用自己的秘密钥对密文c c解密在计算上是容易的。解密在计算上是容易的。n敌手由密文敌手由密文c c和和B B的公开密钥恢复明文在计算上是不可的公开密钥恢复明文在计算上是不可行的。行的。n敌手由密文
7、敌手由密文c c和和B B的公开密钥恢复秘密密钥在计算上是的公开密钥恢复秘密密钥在计算上是不可行的不可行的n加解密次序可换，即加解密次序可换，即E EPKBPKBDDSKBSKB(m)=D(m)=DSKBSKBEEPKBPKB(m),(m),不不是对任何算法都做此要求。是对任何算法都做此要求。以上要求本质就是找出合适的单向陷门函数以上要求本质就是找出合适的单向陷门函数2022-9-26单向函数单向函数一个可逆函数一个可逆函数f f：A AB B，若它满足：，若它满足：1 1o o 对所有对所有x x A A，易于计算，易于计算f f(x x)。2 2o o 对对“几乎所有几乎所有x x A A
8、”由由f f(x x)求求x x“极为困难极为困难”，以至于实际上不可能做到，则称以至于实际上不可能做到，则称f f为一单向为一单向(One-way)(One-way)函数。函数。n定义中的定义中的“易于计算易于计算”是指函数值能在其输入是指函数值能在其输入长度的多项式时间内求出，即若输入长度为长度的多项式时间内求出，即若输入长度为n n，计算函数的时间是计算函数的时间是n na a的倍数，的倍数，a a为一固定的常为一固定的常数。数。n若计算函数时间是若计算函数时间是a an n的倍数，则为不可能做到的倍数，则为不可能做到的。的。算法的复杂度算法的复杂度是以算法是以算法在在最坏最坏情况或情况
9、或平均平均情况情况时的复杂度来度量的时的复杂度来度量的2022-9-26陷门单向函数陷门单向函数n单向函数是求逆困难的函数，而单向陷门函单向函数是求逆困难的函数，而单向陷门函数数(Trapdoor one-way function)(Trapdoor one-way function)，是在不知，是在不知陷门信息下求逆困难的函数，当知道陷门信陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。息后，求逆是易于实现的。n陷门单向函数是一族可逆函数陷门单向函数是一族可逆函数f fk k，满足，满足1.1.Y=fY=fk k(X)(X)易于计算（当易于计算（当k k和和X X已知）已知）2
10、.2.X Xf f-1-1k k(Y)(Y)易于计算（当易于计算（当k k和和Y Y已知）已知）3.3.X Xf f-1-1k k(Y)(Y)计算上不可行（计算上不可行（Y Y已知但已知但k k未知）未知）2022-9-264.3 RSA4.3 RSA算法算法 RSA AlgorithmRSA Algorithm2022-9-26概况概况nMITMIT三位年青数学家三位年青数学家R.L.RivestR.L.Rivest，A.ShamirA.Shamir和和L.AdlemanL.Adleman等等1978,19791978,1979发发现了一种用数论构造双钥的方法，称作现了一种用数论构造双钥的方
11、法，称作MITMIT体制，后来被广泛称之为体制，后来被广泛称之为RSARSA体制。体制。n它既可用于加密、又可用于数字签字。它既可用于加密、又可用于数字签字。nRSARSA算法的安全性基于数论中大整数分解算法的安全性基于数论中大整数分解的困难性的困难性。2022-9-26算法描述密钥产生算法描述密钥产生独立地选取两大素数独立地选取两大素数p p和和q q(各各100100200200位十进制数字位十进制数字)计算计算 n n=p pq q，其欧拉函数值，其欧拉函数值(n n)=()=(p p1)(1)(q q1)1)随机选一整数随机选一整数e e，1 1 e e(n n)，gcd(gcd(n
12、n),),e e)=1)=1在模在模(n n)下，计算下，计算e e的有逆元的有逆元d=ed=e-1 -1 mod mod (n n)以以n n，e e为公钥。秘密钥为为公钥。秘密钥为d d。(p p,q q不再需要，可以销毁。不再需要，可以销毁。)加密加密将明文分组，各组对应的十进制数小于将明文分组，各组对应的十进制数小于n n c=me mod n解密解密 m=cd mod n2022-9-26解密正确性证明解密正确性证明ncd mod n med mod n m1 mod(n)mod n mk(n)+1 mod nngcd(m,n)=1 m(n)1 mod n欧拉定理欧拉定理 mk(n)
13、1 mod n mk(n)+1m mod nngcd(m,n)1m是是p的倍数或的倍数或q的倍数的倍数，设设m=cp，gcd(m,q)=1,m(q)1 mod q，mk(q)1 mod q，mk(q)(p)1 mod q mk(n)1 mod q，存在一整数存在一整数r，使mk(n)1rq两边同乘两边同乘m=cp,mk(n)+1m+rcpq=m+rcn,即即mk(n)+1m mod n2022-9-26 选选p=7p=7，q=17q=17。求求n=pn=pq=119q=119，(n)=(p-1)(q-1)=96(n)=(p-1)(q-1)=96。取取e=5e=5，满足满足11e(n)e(n)，
14、且且gcd(n),e)=1gcd(n),e)=1。确定满足确定满足de=1 mod 96de=1 mod 96且小于且小于9696的的d d，因为因为77775=385=45=385=496+196+1，所以，所以d d为为7777 公开钥为公开钥为55，119119，秘密钥为，秘密钥为7777。设明文设明文m=19m=19，则由加密过程得密文为则由加密过程得密文为 c19c195 5 mod 1192476099 mod 11966 mod 1192476099 mod 11966 解密为解密为66667777mod 11919mod 11919例题例题2022-9-26用用RSARSA算法
15、加密与解密的过程：算法加密与解密的过程：例：明文例：明文=“RSA ALGORITHM”=“RSA ALGORITHM”(1)(1)明文用数字表示明文用数字表示 空白空白=00=00，A=01,B=02,Z=26(A=01,B=02,Z=26(两两位十进制数表示位十进制数表示)1819 0100 0112 0715 1809 2008 13001819 0100 0112 0715 1809 2008 1300(2)(2)利用加密变换公式利用加密变换公式 C=mC=me e mod r,mod r,即即C=1819C=181912231223 mod mod 2867=27562867=275
16、62756 2001 0542 0669 2347 0408 1815p=47,q=61,(n)=2760时，时，d=167n=2867e=12232022-9-26RSA算法实现算法实现n如何判定一个给定的大整数是素数？如何判定一个给定的大整数是素数？n已知已知d d如何计算如何计算e e，使，使e e*d1 mod(n)d1 mod(n)？n如何计算如何计算C MC Me e mod n mod n或或MCMCd d mod n mod n？2022-9-26Miller-Rabin 素性检验算法素性检验算法2022-9-26求模逆元的扩展欧几里德算法求模逆元的扩展欧几里德算法2022-9
17、-26求模幂的模重复平方计算法求模幂的模重复平方计算法求求a amm，其中，其中a a，mm是正整数：是正整数：将将mm表示为二进制形式表示为二进制形式b bk k b bk-1k-1bb0 0，m=bm=bk k2 2k k+b+bk-1k-12 2k-1k-1+b+b1 12+b2+b0 0(12012222kkkbbbbbmaaaaaa 2022-9-26RSA的快速实现n加密很快，指数小加密很快，指数小n解密比较慢，指数较大解密比较慢，指数较大n利用中国剩余定理利用中国剩余定理CRTCRT，nCRT CRT 对对RSARSA解密算法生成两个解密方程解密算法生成两个解密方程（利用（利用M
18、=CM=Cd d mod pqmod pq）n即即:M:M1 1=M mod p=(C mod =M mod p=(C mod p)p)d mod(p-1)d mod(p-1)mod p mod p n M M2 2=M mod q=(C mod q)=M mod q=(C mod q)d mod(q-1)d mod(q-1)mod q mod q n解方程解方程 M=MM=M1 1 mod p mod p M=M M=M2 2 mod q mod q n具有唯一解（利用具有唯一解（利用CRT CRT）2022-9-26RSA的安全性的安全性nRSA的安全性是基于分解大整数的困难性假定的安全性
19、是基于分解大整数的困难性假定如果分解如果分解n=pq，则立即获得则立即获得(n)=()=(p1)(q1)，从而能够确定从而能够确定e的模的模(n)乘法逆乘法逆dn由由n n直接求直接求(n)等价于分解等价于分解n nnRSA-129历时历时8个月被于个月被于1996年年4月被成功分月被成功分解，解，RSA130于于1996年年4月被成功分解月被成功分解n密钥长度应该介于密钥长度应该介于1024bit1024bit到到2048bit2048bit之间之间2022-9-262022-9-26DES和RSA性能比较（同等强度）2022-9-26RSA的安全性的安全性n|p-qp-q|要大要大np p
20、-1,-1,q q-1-1都应有大的素因子。都应有大的素因子。nenen且且dndn1/41/4,则则d d能被容易的确定。能被容易的确定。2022-9-26(222444pqpqpqnpq(24pq2pq|p-q|p-q|要大要大?如果|p-q|小稍大于n稍大于n 顺序检查大于 的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。由x2-n=y2，得n=(x+y)(x-y)。n2022-9-26重复加密攻击重复加密攻击p-1p-1和和q-1q-1都应有大素因子都应有大素因子?(?(针对重复加密攻击针对重复加密攻击)设攻击者截获密文设攻击者截获密文c c，(2223111mod
21、modmodmodtttttteeeeeeeeeeeeeeeecmmncmmncmmncmmn(1modtemcn(1m o dtec m n使使t t足够大足够大2022-9-26当当t=t=（(n)(n)），），e et t1(mod(n)1(mod(n)（(n)(n)）足够大，）足够大，p-1p-1和和q-1q-1都应有都应有大的素因子大的素因子。(modtemmn(modtemmnEuler Euler 定理定理,1),(ma)(mod1)(mam2022-9-26共模攻击共模攻击n每一用户有相同的模数每一用户有相同的模数n nn设用户的公开密钥分别为设用户的公开密钥分别为e e1 1
22、,e,e2 2,且且e e1 1,e,e2 2互素，明互素，明文消息为文消息为m,m,密文为密文为n因为（因为（e e1 1,e,e2 2)=1,)=1,用欧几里德算法可求用欧几里德算法可求 r er e1 1+s es e2 2=1=1假定假定r r为负数，计算为负数，计算 (c c1 1-1-1)-r-r c c2 2s s=mm mod mod n nnmcnmceemodmod2121 2022-9-26低指数攻击低指数攻击 令网中三用户的加密钥令网中三用户的加密钥e e均选均选3 3，而有不同的模，而有不同的模n n1 1,n n2 2,n n3 3 若有一用户将消息若有一用户将消息
23、x x传给三个用户的密文分别为传给三个用户的密文分别为 y y1 1=x x 3 3 mod mod n n1 1 x nx n1 1y y2 2=x x 3 3 mod mod n n2 2 x n x n2 2y y3 3=x x 3 3 mod mod n n3 3 x nx n3 3一般选一般选n n1 1,n n2 2,n n3 3互素，互素，利用中国剩余定理，求出利用中国剩余定理，求出 y y=x x 3 3 mod(mod(n n1 1 n n2 2 n n3 3)。由由xnxn1 1,xnxn2 2,xnxn3 3，可得，可得x x3 3 n n1 1 n n2 2,n n3
24、3，故有，故有3yx 2022-9-26 RSA可用于数字签名n签名：对任意消息 mM,用户用自己的私钥签名如下：Smd(mod n),得到签了名的消息：（m,S）n验证签名：由该用户的公开密钥（e,n），验证 m Se(mod n)是否成立.2022-9-26选择密文攻击选择密文攻击 攻击者通过选取不同的待解密的密文，以得到对应的被加攻击者通过选取不同的待解密的密文，以得到对应的被加密的明文。原始的密的明文。原始的RSA不能抵抗这种攻击。不能抵抗这种攻击。例：如果例：如果E想窃听想窃听A发给发给B的加密消息的加密消息m，E可以收集到可以收集到m对对应的密文应的密文c，E想从想从c获取获取m，即，即 攻击过程如下：攻击过程如下：1.E首先选取一个小于首先选取一个小于n的随机数的随机数r。2.利用利用B的公钥的公钥e计算计算 3.E让让B用其私钥对用其私钥对y进行签名，注意进行签名，注意B以前没有见过以前没有见过y。4.B将将 发送给发送给 E.5.E计算：计算：解决方法：绝对不要对一个陌生人提交给你的随机文件签名。解决方法：绝对不要对一个陌生人提交给你的随机文件签名。)(modncmd)(modnrxe)(modnxcy)(mod1nrt)(modnyudmncncxrnyrntuddddmodmodmodmod112022-9-26
