1、第4章公钥密码体制传统密码体制在应用中的缺陷 v密钥管理的麻烦密钥管理的麻烦v密钥难以传输密钥难以传输v不能提供法律证据不能提供法律证据v缺乏自动检测密钥泄密的能力缺乏自动检测密钥泄密的能力整 除v定理：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|bv例：3|15，-15|60v性质：对所有整数a0，a|0、a|a成立 对任意整数b，1|b成立素数(prime numberprime number)v定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。v素数定理：v在各种应用中，我们需要大的素数,如100位的素数v素数是构成整
2、数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。(),()(),1lnlnxxxxxxxxx设是小于的素数的个数则且当最大公约数va和b的最大公约数是能够同时整除a和b的最大正整数，记为gcd(a,b)。v如果gcd(a,b)=1，则说a和b是互素的。v定理：设a和b是两个整数(至少一个非0)，d=gcd(a,b)，则存在整数x和y，使得ax+by=d特殊地，如果a和b互素，则有整数x和y，使得ax+by=1同余v设整数a，b，n(n 0)，如果a-b是n的整数倍，则ab(mod n)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。v(mod n)运算将所有的整数(无
3、论小于n还是大于n)，都映射到0,1,n-1组成的集合。v模算术的性质：(a mod n)+(b mod n)=(a+b)mod n(a mod n)-(b mod n)=(a-b)mod n(a mod n)*(b mod n)=(a*b)mod n性质v有整数a，b，c，n(n 0)：如果ab(mod n)，bc(mod n)那么ac(mod n)如果ab(mod n)，cd(mod n)那么a+cb+d，a-cb-d，acbd(mod n)v计算117 mod 13 v计算21234 mod 789 指数运算的优化启示：如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做
4、平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此12012222kkkbbbbbmaaaaaa 例如：23=124+023+122+121+120a23 =?快速指数算法：(给定a,m)d=1；For i=k Downto 0 DO d=(dd)mod n;if bi=1 then d=(da)mod nreturn d.算法验证：例如 求7560 mod 561。将560表示为1 0 0 0 1 1 0 0 0 0迭代指数中间值(1 2 4 8 17 35
5、70 140 280 560）算法的中间结果(7 49 157 526 67 1)所以7560 mod 561=1。除法v设整数a，b，c，n(n 0)，且gcd(a,n)=1。如果abac(mod n)，那么bc(mod n)证明：gcd(a,n)=1，有x和y，使ax+ny=1两边同乘以(b-c):(b-c)(ax+ny)=b-c即:(ab-ac)x+n(b-c)y=b-c abac(mod n),即ab=ac+k1n,ab-ac 是n的倍数同时，n(b-c)y显然也是n的倍数所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍则式变为：b-c=k2n即bc(mod n)欧几
6、里德算法(Euclid)v用欧几里德算法求最大公约数。v求：gcd(482,1180)1180=2*482+216482=2*216+50216=4*50+1650=3*16+216=8*2+0所以gcd(482,1180)=2乘法逆元v如果gcd(a,b)=1，那么：存在a-1，使a*a-1 1 mod b存在b-1，使b*b-1 1 mod av这里，把a-1称为a模b的乘法逆元，b-1称为b模a的乘法逆元用扩展的欧几里德算法求乘法逆元vgcd(11111,12345)12345=1*11111+123411111=9*1234+51234=246*5+45=1*4+14=4*1+0v1=
7、5-1*4=5-1*(1234-246*5)=247*5-1*1234 =247*(11111-9*1234)-1*1234 =247*11111-2224*1234 =247*11111-2224*(12345-1*11111)=2471*11111-2224*12345费尔马小定理(FermatFermat)v如果p是一个素数,a不是p的倍数，则：ap-11(mod p)证明：设有一整数空间S=1,2,p-1再设有一函数(x)=ax(mod p)xS(1)对于任何xS，有(x)S(2)对于x和y(xy),有(x)(y)(3)根据乘法定理和除法定理 (p-1)!ap-1(p-1)!mod p
8、欧拉函数v(n)：小于n且与n互素的正整数的个数v显然，对于素数p，有(p)=p-1v设有两个素数p和q，p q，那么对于n=pq，有：(n)=(pq)=(p)*(q)=(p-1)*(q-1)欧拉定理(EulerEuler)v对于任意互素的a和n，有a(n)1 mod n证明：对于整数n，与n互素的数有(n)个：令这些数为：R=x1,x2,x(n)用a与R中的每个元素相乘模n，得到集合S：S=ax1 mod n,x2 mod n,x(n)mod n 其实S就是R：(ax1 mod n)RS中的元素是唯一的那么：R中各元素相乘就等于S中各元素相乘：()()11modnniiiixaxn离散对数v
9、由Euler定理可知，互素的a和n，有a(n)1 mod n也就是说，至少存在一个整数m，使am 1 mod n成立v使得成立am 1 mod n的最小正幂m，称为a的阶、a所属的模n的指数，或a所产生的周期长。v本原根：如果使得am 1 mod n成立的最小正幂m：m=(n)，则称a是n的本原根。指标v某素数p，有本原根a，且：X1=a1 mod p，X2=a2 mod p，Xp-1=ap-1 mod p，则：x1x2 xp-1令：S=x1,x2,xp-1，T=1,2,p-1则：S=P对于任意整数b，有br mod p (0rp-1)所以，对于b和素数p的本原根a，有唯一的幂i，使得：bai
10、 mod p，0ip-1指数i称为a模p的b的指标，记为inda,p(b)指标的性质vinda,p(1)=?vinda,p(a)=?v乘法性质v幂性质离散对数的计算v对于方程y=gx mod p给定g,x,p,计算y比较容易。但给定y,g,p,求x非常困难。X=indg,p(y)其难度与RSA中因子分解素数之积的难度有相同的数量级。公钥密码体制(Public key system)(Public key system)v公钥密码学与其他密码学完全不同：公钥算法基于数学函数而不是基于替换和置换使用两个独立的密钥v公钥密码学的提出是为了解决两个问题：密钥的分配数字签名v1976年Diffie和He
11、llman首次公开提出了公钥密码学的概念，被认为是一个惊人的成就。公钥密码体制的原理公钥体制公钥体制(Public key system)(Diffie(Public key system)(Diffie和和Hellman,1976)Hellman,1976)每个用户都有一对选定的密钥每个用户都有一对选定的密钥(公钥公钥k k1 1；私钥；私钥k k2 2)，公开的，公开的密钥密钥k k1 1可以像电话号码一样进行注册公布。可以像电话号码一样进行注册公布。主要特点：主要特点：v加密和解密能力分开加密和解密能力分开v多个用户加密的消息只能由一个用户解读，（用于公共多个用户加密的消息只能由一个用户
12、解读，（用于公共网络中实现保密通信）网络中实现保密通信）v只能由一个用户加密消息而使多个用户可以解读（可用只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。于认证系统中对消息进行数字签字）。v无需事先分配密钥。无需事先分配密钥。公钥密码体制有4个组成部分v明文：算法的输入，它们是可读信息或数据，用M表示；v密文：算法的输出。依赖于明文和密钥，对给定的消息，不同的密钥产生密文不同。用E表示；v公钥和私钥：算法的输入。这对密钥中一个用于加密，为Ke，此密钥公开；一个用于解密，为Kd，此密钥保密。加密算法执行的变换依赖于密钥；v加密、解密算法 公钥密码体制下的秘密通信
13、 公钥加密体制的特点v加密和解密能力分开v多个用户加密的消息只能由一个用户解读，可用于公共网络中实现保密通信v用私钥加密的消息可以用对应的公钥解密，所以由一个用户加密消息而使多个用户可以解读，可用于认证系统中对消息进行数字签字v无需事先分配密钥v密钥持有量大大减少v提供了对称密码技术无法或很难提供的服务：如与哈希函数联合运用可生成数字签名，可证明的安全伪随机数发生器的构造，零知识证明等 保证机密性保证机密性 MEKbeE(M,Kbe)DKbdMKbe：Bob的公钥Kbd：Bob的私钥保证真实性保证真实性 Kad：Alice的私钥Kae：Alice的公钥MEKadE(M,Kad)DKaeM既保证
14、机密性又保证真实性既保证机密性又保证真实性 Kad：Alice的私钥Kae：Alice的公钥MEKbeE(C1,Kbe)DKbdMEKadC1=E(M,Kad)C1DKaeKbe：Bob的公钥Kbd：Bob的私钥公钥密码应满足的要求公钥密码应满足的要求v接收方接收方B B产生密钥对在计算上是容易的产生密钥对在计算上是容易的v发送方发送方A A用收方的公开钥对消息用收方的公开钥对消息mm加密以产生密文加密以产生密文c c在计算在计算上是容易的。上是容易的。v收方收方B B用自己的秘密钥对密文用自己的秘密钥对密文c c解密在计算上是容易的。解密在计算上是容易的。v敌手由密文敌手由密文c c和和B
15、B的公开密钥恢复明文在计算上是不可行的。的公开密钥恢复明文在计算上是不可行的。v敌手由密文敌手由密文c c和和B B的公开密钥恢复秘密密钥在计算上是不可的公开密钥恢复秘密密钥在计算上是不可行的行的v加解密次序可换，即加解密次序可换，即E EPKBPKBDDSKBSKB(m)=D(m)=DSKBSKBEEPKBPKB(m),(m),不是对不是对任何算法都做此要求。任何算法都做此要求。对公钥密码体制的攻击v和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得
16、更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。v对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。RSARSA算法算法RSA AlgorithmRSA Algorithm概况概况vMIT三位年青数学家R.L.Rivest，A.Shamir和L.AdlemanRivest等1978,1979发现了一种用数论构造双钥的方法，称作MITMIT体制体制，后来被广泛称之为RSARSA体制体制。v它既可用于加密、又可用于数字签字。vRSA算法的安全性基于数论中大整数分解的困难性。v迄
17、今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。算法原理vRSA算法使用了乘方运算。v要求：明文M经过加密得到密文C：C=Me mod n 密文C经过解密得到明文M：Cd mod n=(Me mod n)d mod n=Med mod n=M即：必须存在e，d，n，使Med mod n=M成立如何确定e,d,nv确定n：独立地选取两大素数独立地选取两大素数p p和和q q(各各100100200200位十进制位十进制数字数字)计算计算 n n=p pq q，其欧拉函数值，其欧拉函数值(n n)=()=(p p1)(1)(q q1)1)v确定e：随机选一整数随机选一整数e e，1
18、 1 e e(n n)，gcd(gcd(n n),),e e)=1)=1v确定d：根据根据ed=1ed=1 mod mod (n n)在模在模(n n)下，计算下，计算d d这样确定的e,d,n是否能使Med mod n=M成立呢？v因为因为ed=1ed=1 mod mod (n n)即即ed=ked=k(n n)+1)+1 所以：所以：MMeded=M=Mk k(n n)+1)+1v如果如果MM和和n n互素，即互素，即gcd(M,n)=1 gcd(M,n)=1 那么，那么，根据欧拉定理根据欧拉定理(如果如果gcd(a,n)=1gcd(a,n)=1，则，则 a(n)1 mod n)：有：有：
19、MM(n n)11 mod n mod n所以：所以：MMed ed M Mk k(n n)+1)+1 MMMM(n n)k kmod nmod n M M11k kmod nmod n M M mod n mod nv如果如果MM和和n n不互素，即不互素，即gcd(M,n)1gcd(M,n)1，即，即MM和和n n有大于有大于1 1的公约数。的公约数。因为因为n=pqn=pq，而，而p p、q q都是素数，不可再分解，都是素数，不可再分解，所以所以MM一定包含了一定包含了p p或或q q为因子。为因子。又因为又因为MnMn，所以，所以MM不可能既是不可能既是p p的倍数又是的倍数又是q q
20、的倍数。的倍数。v不妨设不妨设MM是是p p的倍数，的倍数，M=cpM=cp。由于由于MM不是不是q q的倍数，所以的倍数，所以gcd(M,q)=1gcd(M,q)=1，则，则MM(q q)11 mod q mod q，所以：，所以：MM(q q)(p p)11 mod q mod q 即即MM(n n)11 mod mod q q，即，即MM(n n)=1+kq=1+kqvMM(n n)=1+kq=1+kq两边同乘以两边同乘以M=cpM=cp，则：，则：MM(n n)+1)+1=M+kqcp=M+kcn=M+kqcp=M+kcn把把kckc看作一个常数，则：看作一个常数，则：MM(n n)+
21、1)+1=M+tn=M+tn即：即：MM(n n)+1)+1 MM mod n mod n，即，即MM(n n)11 mod n mod n因为因为ed=1 mod ed=1 mod (n n)，所以：所以：M Med ed M Mk k(n n)+1)+1 MMMM(n n)k kmod nmod n M M11k kmod nmod n M M mod n mod n综上综上,这样的这样的e e，d d，n n可以实现加密可以实现加密C=Me mod n和解密和解密M=Cd mod n密钥v以以n n，e e为公钥。秘密钥为为公钥。秘密钥为d d。(p p,q q不再需要，不再需要，可以销
22、毁。可以销毁。)RSA算法在计算上的可行性v加密和解密无论是加密还是解密都需要计算某个整数的模n整数次幂，即C=Me mod n、M=Cd mod n。但不需要先求出整数的幂再对n取模，而可利用模运算的性质：(a mod n)*(b mod n)=(a*b)mod n对于Me mod n，可先求出M1 mod n，M2 mod n，M4 mod n，再求Me mod nRSA算法在计算上的可行性v产生密钥由于n是公开的，为了避免攻击者用穷举法求出p和q（根据n=pq），应该从足够大的集合中选取p和q，即p和q必须是大素数。目前还没有有效的方法可以产生任意大素数，通常使用的方法是：随机挑选一个期
23、望大小的奇数，然后测试它是否是素数，若不是，则挑选下一个随机数直至检测到素数为止。素性检验素性检验v引理：如果引理：如果p p为大于为大于2 2的素数，则方程的素数，则方程x x2 21 mod p1 mod p的解只有和的解只有和x1x1和和x-1x-1v证明证明:x x2 21 mod p 1 mod p x x2 2-1 -1 0 mod p0 mod p (x+1)(x-1)0 mod p (x+1)(x-1)0 mod p 所以所以,p|(x+1),p|(x+1)或或p|(x-1)p|(x-1)或或p|(x+1)p|(x+1)且且p|(x-1)p|(x-1)存在存在k,jk,j，x+
24、1=kp,x-1=jpx+1=kp,x-1=jp2=(k-j)p,2=(k-j)p,这是不可能的。这是不可能的。v引理的逆命题：若方程引理的逆命题：若方程x x2 21 mod p1 mod p有唯一解有唯一解x x不为不为+1+1或或-1-1，p p不是素数不是素数素性检验素性检验vMiller-RabinMiller-Rabin素性概率检测法素性概率检测法n n为待检测数，为待检测数，a a为小于为小于n n的整数，将的整数，将n-1n-1表示为二进制形式表示为二进制形式b bk kb bk-1k-1b b0 0,d,d赋初值为赋初值为1 1，算法核心如下，算法核心如下 for i=k d
25、ownto 0 do xd;d(dd)mod n;if d=1 and(x1)and(xn-1)then return False if bi=1 the d(da)mod n if d 1 then return False;return True若返回若返回False,nFalse,n不是素数不是素数,若返回若返回True,True,有可能是素数有可能是素数。素性检测素性检测ForFor循环结束循环结束,有有dadan-1 n-1 mod n.mod n.由费尔玛定理由费尔玛定理,若若n n为素数为素数,d,d为为1.1.所以所以d1d1，则，则d d不是素数不是素数n-1-1 mod n
26、,n-1-1 mod n,所以所以x 1x 1和和x n-1x n-1指指x x2 21 mod n 1 mod n 有有非非1 1的根的根,n,n不是素数不是素数v该算法对该算法对s s个不同的个不同的a a，重复调用，如果每次，重复调用，如果每次都返回都返回truetrue，则，则n n是素数的概率大于等于是素数的概率大于等于1-21-2-s-svMiller-RabinMiller-Rabin算法可以确定一个整数是合算法可以确定一个整数是合数，但不能确定其一定是素数。数，但不能确定其一定是素数。v要找到一个要找到一个2 2200200左右的素数，在找到素左右的素数，在找到素数之前大约要进
27、行数之前大约要进行ln(2ln(2200200)/2=70)/2=70次尝试次尝试v在在NN附近平均每隔附近平均每隔lnNlnN个整数就会有一个个整数就会有一个素数。素数。RSA算法在计算上的可行性v确定d和e有了p和q，可计算出(n n)=()=(p p1)(1)(q q1)1)根据根据gcd(gcd(n n),e)=1),e)=1来选择来选择e e，这一步计算量也不，这一步计算量也不大，因为两个随机数互素的概率约为大，因为两个随机数互素的概率约为0.60.6有了有了e e，再计算，再计算d=ed=e-1-1 mod mod (n n)，这里用的是扩展，这里用的是扩展的的EuclidEucl
28、id算法。算法。选两个保密的大素数p和q。计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。选一整数e，满足1e(n)，且gcd(n),e)=1。计算d，满足de1 mod(n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。以e,n为公开钥,d,n为秘密钥。算法描述选p=7，q=17。求n=pq=119，(n)=(p-1)(q-1)=96。取e=5，满足1e(n)，且gcd(n),e)=1。确定满足de=1 mod 96且小于96的d，因为775=385=496+1，所以d为77。因此公开钥为5，119，秘密钥为77，119。设明
29、文m=19，则由加密过程得密文为C=195 mod 1192476099 mod 119=66解密为6677mod 119=19RSA的安全性vRSA的安全性是基于分解大整数的困难性假定v如果分解n=pq，则立即获得(n)=(p1)(q1)，从而能够确定e的模(n)乘法逆dvRSA-129历时8个月(曾经预言需要4*1016年)被于1996年4月被成功分解，RSA130于1996年4月被成功分解v密钥长度应该介于1024bit到2048bit之间v由n直接求(n)等价于分解nRSA-129的故事的故事 v鹗鸟（ossifrage），又名髭兀鹰（lammergeier），是阿尔卑斯山上一种稀有的
30、肉食秃鹰。它的翅膀展开将近十米宽。鸟名的字面含义是“碎骨”。顾名思义，其习性令人毛骨悚然。vMirtin Gardner在1977年“Scientific American”的专栏文章中介绍了RSA码。为了显示这一技术的威力，RSA公司的研究人员用一个129位的数N和一个4位数e 对这个关于秃鹰的消息作了编码。Gardner刊登了那个密文，同时给出了N和e。RSA公司还悬赏100美元，奖给第一个破译这密码的人。v96869 61375 46220 61477 14092 22543 55882 90575 99911 24574 31987 46951 20930 81629 82251 45
31、708 35693 14766 22883 98962 80133 91990 55182 99451 57815 154 v一批松散组成的因子分解迷，大约有六百多人，分布在二十几个国家。他们经过八个月的努力最后于1994年4月为RSA-129找到了64位数和65位数两个素数因子。v11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561 84293 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 3541=349
32、05 29510 84765 09491 47849 61990 38981 33417 76463 84933 87843 99082 0577*32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 88533 v“The magic words are squeamish ossifrage”来自两个方面的威胁v人类计算能力的不断提高v分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。几个建议v为了防止可以很容易地分解n，RSA算法的发明者建议p和q还应满足下列限制条件：P和q的长度应仅相差几位。对于1024位的密钥而言，p和q都应在1075到10100之间。(p-1)和(q-1)都应有一个大的素因子。Gcd(p-1,q-1)应该较小。精品课件精品课件！精品课件精品课件！
