《次课公钥密码》PPT课件.ppt

公钥密码 Public Key Cryptography,公钥密码学思想,公钥密码算法的基本工具不再是代换和置换，而是数学函数。 公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对 保密性、密钥分配、认证 等都有着深刻的意义。 公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。,公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的,W.Diffie and M.E.Hellman, New Directrions in Cryptography,公钥密码体制的原理,采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥 ，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥 ，用于解密。 因此公钥密码体制也称为双钥密码体制 。 算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的。,公钥密码体制的原理,公钥体制(Public key system) (Diffie和Hellman,1976) 每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。 主要特点： 加密和解密能力分开。 多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）。 只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。 无需事先分配密钥。,公钥密码体制的意义,密钥分配 数字签字,公钥密码体制的概念在密钥分配 上的贡献； 公钥密码体制的概念在密钥创建 上的贡献。,考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。,公钥体制加密 的框图,B产生公钥和私钥： PKB、SKB,A向B发送消息m，利用PKB加密，得密文c 。,B收到密文c ，利用私钥SKB解密，得明文m 。,多个用户加密的消息只能由一个用户解读。,由于任一用户都可用用户B的公开钥PKB 向他发送机密消息，因而密文c不具有认证性。,公钥密码体制认证 框图,只能由一个用户加密消息而使多个用户可以解读。,A向B发送消息m，利用SKA加密，得密文c 。,A产生公钥和私钥： PKA、SKA,B收到密文c ，利用A的公钥PKA解密，得明文m 。,安全性： 由于SkA 是保密的，其他人都不可能伪造密文c，可用A的 公开钥解密时得到有意义的消息m。因此可以验证消息m来自A而不是其他人，而实现了对A所发消息的认证。,不具有保密性！,公钥密码体制的认证、保密框图,以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。,公钥密码应满足的要求,接收方B产生密钥对在计算上是容易的。 发送方A用收方的公开钥对消息m 加密以产生密文c 在计算上是容易的。 收方B用自己的秘密钥对密文c 解密在计算上是容易的。 敌手由密文c 和B的公开密钥恢复明文在计算上是不可行的。 敌手由密文c 和B的公开密钥恢复秘密密钥在计算上是不可行的。 加解密次序可换，即EPKBDSKB(m)=DSKBEPKB(m) ,不是对任何算法都做此要求。,以上要求的本质之处在于要求一个陷门单向函数。,单向函数,一个可逆函数f：AB，若它满足： 1o 对所有xA，易于计算f (x)。 2o 对“几乎所有xA ”由f (x)求x “极为困难”，以至于实际上不可能做到，则称f 为一单向(One-way)函数。 定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为n，计算函数的时间是na的倍数，a为一固定的常数。 若计算函数时间是an的倍数，则为不可能做到的。,陷门单向函数,单向函数是求逆困难的函数，而单向陷门函数(Trapdoor one-way function)，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。 陷门单向函数是一族可逆函数fk，满足 Y=fk(X)易于计算（当k和X已知） Xf-1k(Y)易于计算（当k和Y已知） Xf-1k(Y)计算上不可行（Y已知但k未知） 研究公钥密码算法就是找出合适的单向限门函数。,对公钥密码体制的攻击,穷搜索攻击。 寻找从公开钥计算秘密钥的方法。 可能字攻击。,对称密码 公钥密码,关于公钥密码的几种误解,公钥密码比传统密码安全？ 公钥密码是通用方法，所以传统密码已经过时？ 公钥密码实现密钥分配非常简单？,公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（IFP）的算法体制 基于离散对数难题（DLP）算法体制 基于椭圆曲线离散对数难题（ECDLP）的算法体制,RSA算法 RSA Algorithm,RSA算法概况,MIT三位年青数学家R.L.Rivest，A.Shamir和L.AdlemanRivest等1978, 1979发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。 它既可用于加密、又可用于数字签字。 RSA算法的安全性基于数论中大整数分解的困难性。,Euler 函数,(n): 设n是一个正整数，小于n且与n互素的正整数的个数称为n的欧拉函数。 当n是素数时，小于n的所有整数均与n互素，因此(n)=n-1 . 对n=pq, p和q 是素数，(n)=(p)(q)=(p-1)(q-1),Euler定理、Fermat定理,Euler定理：设 x 和 n 都是正整数，如果gcd(x，n)1，则 x (n)1 (mod n). Fermat定理:设 x 和 p 都是正整数，如果gcd(x，p)1，则 x p-11 (mod p).,算法描述,1. 密钥产生 独立地选取两大素数 p 和 q (各100200位十进制数字) 计算 n=pq，其欧拉函数值(n)=(p1)(q1) 随机选一整数e，1 e(n)，gcd(n), e)=1 在模(n)下，计算e 的乘法逆元d=e -1 mod (n) 以n，e 为公钥。秘密钥为d 。(p, q不再需要，可以销毁。) 2. 加密 （将明文分组，各组对应的十进制数小于n，即分组长度小于log2n） c=me mod n 3. 解密 m=cd mod n,解密正确性证明,cd mod n med mod n m1 modj(n) mod n mkj(n)+1 mod n m m与n互素 gcd(m,n) 1,c=me mod n,d=e -1 mod (n),m(n) 1 modn,mk(n) 1 modn,mk(n)+1 m modn,？,所以，m是p的倍数，或者，m是q的倍数。不可能既是p，也是q的倍数。,设：m=tp，t是一个正整数，得 gcd(m,q) =1,m(q) 1 modq,mk(q) 1 modq,mk(q) (p) 1 modq,mk(n) 1 modq,mk(n) 1+rq,两边同乘m=tp，得：,mk(n)+1 (1+rq)tp = m+rtn,mk(n)+1 m modn,RSA算法举例,设 p=11, q=23, n=11*23=253; 参数T=n=253; (n)=(11-1)(23-1)=220; 选择e=139, gcd(139,220)=1; 公钥pk=139; 计算d, ( d*e) mod 220=1; d=19; 私钥sk=19;,Alice发送“Hi”给Bob。,“Hi” 01001000 01101001 72 105,加密：72139 (mod253) = 2 105139 (mod253) = 101,Bob收到消息(2 101) ，用自己的私钥解密。,解密：219 (mod253) = 72 10119 (mod253) = 105,Bob查表得 “Hi”,实际中不可能用这么小的数字(eg. 11、23)，这样能很容易从公钥发现私钥。,例如：已知Pk=(139,253)，可尝试分解253求出p和q。,最简单的方法：用小于16的每个素数去除253。,162253,很快发现：11*23=253，则得(n) =220,根据 139d(mod220)=1 d=19,实际中使用RSA，必选两个很大的素数，从而使n几乎不可分解因子。,小结 RSA使用的运算,d=e -1 mod (n) d是e的反模运算，利用欧几里德算法。 大素数的选择 素性检验 大整数的幂的计算 用于加（解）密时，手工完成不可能，计算机直接算也比较慢。,反模运算e d=1 mod (p-1)(q-1),欧几里德(Euclid)算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。 推广Euclid算法，不仅可求两个正整数的最大公因子；而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。,Euclid算法 -求最大公因子,基于结论：任意非负整数a和正整数b， 有gcd(a,b)=gcd（b,a(modb) 证明： 是正整数,可表示为a=k+r,即a(modb)=r,k是一整数,a(modb)=a-kb,又设是，的公因子，即d|a , d|b,d|kb,d|(a-kb) ,即 d|(amodb),整除的性质,是和amodb的公因子,a，b的公因子集合与b，amodb的公因子集合相等，两个集合的最大值也相等。 证毕,Euclid算法 -求最大公因子（示例）,gcd(55,22)=gcd(22,55mod22) =gcd(22,11) =gcd(11,22mod11) =gcd(11,0)=11 gcd(18,12)=gcd(12,6)=gcd(6,0)=6 gcd(11,10)=gcd(10,1)=1,Euclid算法 -求最大公因子（伪代码）,设输入两个正整数d，f，且fd X f ; Y d ; If(Y=0) then return X=gcd(f,d) If(Y=1) then return Y=gcd(f,d) R=XmodY X=Y Y=R goto 2,gcd(18,12)=gcd(12,6)=gcd(6,0)=6,f,d,X,Y,思考：gcd(1970,1066)=?,扩展Euclid算法 -求乘法逆元,整除中一个论断： 如果gcd(a,b)=d，则存在m,n，使得d=ma+nb，称这种关系为a,b组合整数d，m,n称为组合系数。 当d=1，有ma+nb=1，此时可看出m是a模b的逆元， n是b模a的逆元。 推广Euclid算法先求出gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。,扩展Euclid算法 -求乘法逆元（伪代码）,设ed(modm)=1，求e的值 (X1, X2, X3)(1,0,m); (Y1, Y2, Y3)(0,1,d); If Y3=0 then return X3=gcd(m,d) , stop; If Y3=1 then return e=d-1(modm)=Y2 , stop; Q=X3/Y3 （整数除） (T1, T2, T3)(X1-QY1 , X2-QY2 , X3-QY3) ; (X1, X2, X3) (Y1, Y2, Y3) ; (Y1, Y2, Y3) (T1, T2, T3) goto 2,扩展Euclid算法 -求乘法逆元（示例）,求解11e(mod51)=1 循环次数 Q X1 X2 X3 Y1 Y2 Y3 初值 1 0 51 0 1 11,1 4,0 1 11,1 -4 7,(X1, X2, X3)(1,0,m); (Y1, Y2, Y3)(0,1,d);,Q=X3/Y3 （整数除）,(X1, X2, X3) (Y1, Y2, Y3),(T1, T2, T3)(X1-QY1 , X2-QY2 , X3-QY3),(Y1, Y2, Y3) (T1, T2, T3),2 1,1 -4 7,-1 5 4,3 1,-1 5 4,2 -9 3,4 1,-3 14 1,2 -9 3,算法中隐含：mX1+dX2=X3 mY1+dY2=Y3,当Y3=1，Y1=d-1modm,X3 和Y3相当于Euclid中的X和Y,X3=前一轮的Y3 Y3=前一轮X3-QY3，即X3modY3,思考： gcd(1769,550)=1 550-1mod1769=?,小结 RSA使用的运算,d=e -1 mod (n) d是e的反模运算，利用欧几里德算法。 大素数的选择 素性检验 大整数的幂的计算 用于加（解）密时，手工完成不可能，计算机直接算也比较慢。,素性检验（1）,方法1：用2- 之间的每个素数去除n，均除不尽，则n为素数。 方法2：Fermat测试 定理：底数a和素数p，其中a不能被p整除，那么有ap-1modp=1 例如：6为底数，7为素数，67-1mod7=66mod7=46656mod7=1 方法：若c可能是素数，则选一底数（eg，2），验算是否2c-1modc=1 正确理解：所有素数满足该等式，但使该等式成立的不一定是素数。 例如：2341-1mod341=1, 但11*13=341 问题：伪素数，eg 341， 91等。 解决方案：使用不同的底数进行两次测试，可避免伪素数。 问题：卡米克尔数（Carmichael),对所有底数都是伪素数。eg 561,1105,1729等。 解决方法：多个底数进行Fermat测试，若通过，再与Carmichael数表比较，若不在其中，则为素数。（小于25*109的数中，有2163个Carmichael数）,素性检验（2）,方法：米勒罗宾（Miller-Rabin）测试法 引理：若p(2)为素数，则方程x2=1(modp)的解只有x=1和x=-1 推论：若方程x2=1(modp)有一解x0 -1,1 ,那么p不是素数。 算法Witness(a,n): 先将n-1表示为二进制bk bk-1 b0 , d赋初值1 。 For i=k downto 0 do xd; d(d*d)modn; if (d=1) and (x1) and (xn-1) then return False; if (bi=1) then d (d*a)modn If d 1 then return False; return True;,n是待测数，a(n)是整数。,for循环结束后，有d=an-1modn (由Fermat定理，若n为素数，d=1),米勒罗宾（Miller-Rabin）测试法 对s个不同的a，重复调用这一算法，只要有一次算法返回为False，就可肯定n不是素数； 如果算法每次都返回True，则n为素数的概率至少为1-2-s 对于足够大的s，就可很肯定n为素数。,小结 RSA使用的运算,d=e -1 mod (n) d是e的反模运算，利用欧几里德算法。 大素数的选择 素性检验 大整数的幂的计算 用于加（解）密时，手工完成不可能，计算机直接算也比较慢。,大整数的幂的计算（1）,问题1：中间结果很大，有可能超出计算机所允许的整数取值范围。 问题：乘法次数很多。 解决：每次乘法运算后取模。因为abmodn=(amodn)(bmodn)modn 解决：利用重复平方的方法来减少乘法的次数。 例如2116，16次乘法 因为16=2*2*2*2 所以2116=212*2*2*2=(212)2)2)2 4次乘法,大整数的幂的计算（2）,此方法对所有指数是2的乘幂都是可以的 如果指数不是2的乘幂，可通过指数的二进制表示改为2的乘幂。 例如2141 ，41=(101001)2 25+23+20 所以 2141=2132218211 例如7951mod90=79327916792791mod90=19 51: 11011,大整数的幂的计算（3）,快速指数算法：将m表示为二进制bkbk-1b0，求ammodn c=0; d=1; for i=k downto 0 do c=2*c; d=(d*d)modn; if bi=1 then c=c+1; d=(d*a)modn Return d; d的终值是所求，c的终值为指数m。,m=bk2k+bk-12k-1+b12+b0,在i=k时，完成 abk 在i=k-1时，完成 (abk)2 当i=0时，即使 b0=1也不需要平方了,RSA的安全性,RSA的安全性是基于分解大整数的困难性假定（尚未证明分解大整数是NP问题）。 如果分解n=pq，则立即获得(n)=(p1)(q1)，从而能够确定e的模(n)乘法逆d。 RSA-129历时8个月被于1996年4月被成功分解，RSA130于1996年4月被成功分解。 密钥长度应该介于1024bit到2048bit之间。 由n直接求(n)等价于分解n。,对p、q要求： |p-q|要大 p-1和q-1都应有大素因子 如果en且dn1/4，则d能被容易地确定。,RSA的攻击,有些攻击是专门针对RSA的实现。 不攻击基本的算法，而是攻击协议。,RSA的攻击（1）,情况1：攻击者在发方A的通信中窃听，获得一个A的公开秘钥加密的密文c，攻击者计算m 方法：选一随机数rn，已知A的Pk=e，计算x=remodn , y=xcmodn, t=r-1modn 现攻击者让A用其SK对y签名，以便解密y（A对消息y签名，而非对消息的Hash值签名），A计算u=ydmodn 现攻击者计算 tu=r-1yd=r-1(xc)d=cd=mmodn,若 x=remodn 则，r=xdmodn,RSA的攻击（2）,情况：T是公开的计算机公证人，若M想让T对一个其不愿签名的消息m签名。 方法：M选一x，计算y=xemodn, 即x=ydmodn,然后计算 m=ymmodn,将m发送给T签名。 T回送mdmodn M计算 (mdmodn)x-1modn=(ym)dx-1 = mdydx-1=(m)dmodn,RSA的攻击（3）,情况3：E想让A对m3签名 方法：E产生两份消息m1，m2，满足m3=m1*m2(modn) 若E能让A对m1，m2签名，他就能计算m3的签名 m3d=(m1dmodn)(m2dmodn)(modn) 总结：不要对陌生人的随机消息进行签名，若要签名，应对消息的Hash值签名。,RSA的攻击（4）,另外，对RSA还存在公共模数攻击，低加密指数攻击，低解密指数攻击。,选择大d,加密前用随机位填充消息，确保m和n的大小一样,不要在一组用户间共享n,单向陷门函数,单向陷门函数(One-way Trapdoor Function)定义： 一“可逆”函数F若满足下列二条件，则F称为单向陷门函数： 1.对于所有属于F定义域的任一x，可以很容易算出F(x) = y; 2.对于几乎所有属于F值域的任一y，则在计算上除非获得陷门，否则不可能求出x，使得x = F(-1)(y)，F（-1）为F的反函数。但若有一额外数据z（称为陷门），则可以很容易的求出 x = F(-1)(y)。,单向函数与单向陷门函数的差异在于可逆与不可逆。若单向陷门函数存在，则任何单向陷门函数均可用来设计公开密钥密码系统。同时，若单向函数满足交换性，则单向函数也可能用来设计公开密钥密码系统。,