资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 公钥密码,4.1,数论简介,4.2 公钥密码体制的基本概念,4.3,RSA,算法,4.4 背包密码体制,4.5,Rabin,密码体制,4.6,NTRU,公钥密码系统,4.7,椭圆曲线密码体制,4.8,基于身份的密码体制,2024/10/3,1,第四章 公钥密码4.1 数论简介2022/9/281,4.2,公钥密码体制的基本概念,Basic Concept of Public Key Cryptography,2024/10/3,2,4.2 公钥密码体制的基本概念Basic Concept o,公钥密码体制的原理,公钥体制,(Public key system)(Diffie,和,Hellman,1976),每个用户都有一对选定的密钥,(,公钥,k,1,；私钥,k,2,),，公开的密钥,k,1,可以像电话号码一样进行注册公布。,主要特点：,加密和解密能力分开,多个用户加密的消息只能由一个用户解读，（用于公共网络中实现保密通信）,只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。,无需事先分配密钥。,解决了单钥密码体制中最难解决的两个问题：数字签字、密钥分配,2024/10/3,3,公钥密码体制的原理公钥体制(Public key syste,公钥体制加密,公钥体制加、解密,m,=,D,(,c,)=,D,SKB,(,E,PKB,(,m,),安全保障,从公开钥,PK,B,和密文,c,要推出明文,m,或解密钥,SK,B,在计算上是不可行的。,由于任一用户都可用用户,B,的公开钥,PK,B,向他发送机密消息，因而密文,c,不具有认证性。,发送者,A,加密算法,PK,B,密钥源,SK,B,解密算法,接收者,B,密码分析员,m,c,m,m,SK,B,2024/10/3,4,公钥体制加密 公钥体制加、解密 m=D(c),公钥密码认证体制,用户,A,以自己的秘密钥,S,k,A,对消息,m,进行,A,的专用变换,D,SKA,，,A,计算密文：,c,=,D,SK,A,(,m,),送给用户,B,，,B,验证,c,：,m,=,E,PKA,（,c,）,=,E,PKA,(,D,SKA,(,m,),安全性：,由于,S,k,A,是保密的，其他人都不可能伪造密文,c,，可用,A,的 公开钥解密时得到有意义的消息,m,。因此可以验证消息,m,来自,A,而不是其他人，而实现了对,A,所发消息的认证。,发送者,A,加密算法,SK,A,密钥源,PK,A,解密算法,接收者,B,密码分析员,m,c,m,SK,A,2024/10/3,5,公钥密码认证体制 用户A以自己的秘密钥SkA对消息m,公钥保密和认证体制,公开,保密,公开,保密,保密,认证,为了同时提供认证功能和保密性，可使用双重加、解密,加密,c=E,PKB,E,SKA,m,解密,m=D,PKA,D,SKB,c,2024/10/3,6,公钥保密和认证体制公开保密公开保密保密认证为了同时提供认证功,公钥密码应满足的要求,接收方,B,产生密钥对在计算上是容易的,发送方,A,用收方的公开钥对消息,m,加密以产生密文,c,在计算上是容易的。,收方,B,用自己的秘密钥对密文,c,解密在计算上是容易的。,敌手由密文,c,和,B,的公开密钥恢复明文在计算上是不可行的。,敌手由密文,c,和,B,的公开密钥恢复秘密密钥在计算上是不可行的,加解密次序可换，即,E,PKB,D,SKB,(m)=D,SKB,E,PKB,(m),不是对任何算法都做此要求。,以上要求本质就是找出合适的单向陷门函数,2024/10/3,7,公钥密码应满足的要求接收方B产生密钥对在计算上是容易的以上要,单向函数,一个可逆函数,f,：,A,B,，若它满足：,1,o,对所有,x,A,，易于计算,f,(,x,),。,2,o,对“,几乎所有,x,A,”,由,f,(,x,),求,x,“,极为困难”，以至于实际上不可能做到，则称,f,为一单向,(One-way),函数。,定义中的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即若输入长度为,n,，计算函数的时间是,n,a,的倍数，,a,为一固定的常数。,若计算函数时间是,a,n,的倍数，则为不可能做到的。,算法的复杂度,是以算法在,最坏,情况或,平均,情况时的复杂度来度量的,2024/10/3,8,单向函数一个可逆函数f：AB，若它满足：算法的复杂度是以算,陷门单向函数,单向函数是求逆困难的函数，而单向陷门函数,(Trapdoor one-way function),，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。,陷门单向函数是一族可逆函数,f,k,，满足,Y=f,k,(X),易于计算（当,k,和,X,已知）,X,f,-1,k,(Y),易于计算（当,k,和,Y,已知）,X,f,-1,k,(Y),计算上不可行（,Y,已知但,k,未知）,2024/10/3,9,陷门单向函数单向函数是求逆困难的函数，而单向陷门函数(Tra,4.3 RSA,算法,RSA Algorithm,2024/10/3,10,4.3 RSA算法RSA Algorithm2022/9/,概况,MIT,三位年青数学家,R.L.Rivest,，,A.Shamir,和,L.Adleman,等,1978,1979,发现了一种用数论构造双钥的方法，称作,MIT,体制，后来被广泛称之为,RSA,体制。,它既可用于加密、又可用于数字签字。,RSA,算法的安全性基于数论中大整数分解的困难性,。,2024/10/3,11,概况MIT三位年青数学家R.L.Rivest，A.Shami,算法描述密钥产生,独立地选取两大素数,p,和,q,(,各,100,200,位十进制数字,),计算,n,=,p,q,，其欧拉函数值,(,n,)=(,p,1)(,q,1),随机选一整数,e,，,1,e,(,n,),，,gcd(,(,n,),e,)=1,在模,(,n,),下，计算,e,的有逆元,d=e,-1,mod,(,n,),以,n,，,e,为公钥。秘密钥为,d,。,(,p,q,不再需要，可以销毁。,),加密,将明文分组，各组对应的十进制数小于,n,c=m,e,mod,n,解密,m=c,d,mod,n,2024/10/3,12,算法描述密钥产生独立地选取两大素数p和q(各100200,解密正确性证明,c,d,mod,n,m,ed,mod,n,m,1,mod,j,(,n,),mod,n,m,k,j,(,n,)+1,mod,n,gcd(,m,n,),=1,m,j,(,n,),1 mod,n,欧拉定理,m,k,j,(,n,),1 mod,n,m,k,j,(,n,)+1,m,mod,n,gcd(,m,n,),1,m,是,p,的倍数或,q,的倍数,，,设,m=cp,，,gcd(,m,q,)=1,m,j,(,q,),1 mod,q,，,m,k,j,(,q,),1 mod,q,，,m,k,j,(,q,),j,(,p,),1 mod,q,m,k,j,(,n,),1 mod,q,，,存在一整数,r,，使,m,k,j,(,n,),1,rq,两边同乘,m=cp,m,k,j,(,n,)+1,m,+,rcpq=m+rcn,即,m,k,j,(,n,)+1,m,mod,n,2024/10/3,13,解密正确性证明cd mod n med mod n gcd,选,p=7，q=17。,求,n=pq=119，(n)=(p-1)(q-1)=96。,取,e=5，,满足1,e(n)，,且,gcd(n),e)=1。,确定满足,de=1 mod 96,且小于96的,d，,因为775=385=496+1，所以,d,为77,公开钥为5，119，秘密钥为77。,设明文,m=19，,则由加密过程得密文为,c19,5,mod 1192476099 mod 11966,解密为66,77,mod 11919,例题,2024/10/3,14,选p=7，q=17。例题2022/9/2814,用,RSA,算法加密与解密的过程：,例：明文,=“RSA ALGORITHM”,(1),明文用数字表示 空白,=00,，,A=01,B=02,Z=26(,两位十进制数表示,),1819 0100 0112 0715 1809 2008 1300,(2),利用加密变换公式,C=m,e,mod r,即,C=1819,1223,mod 2867=2756,2756 2001 0542 0669 2347 0408 1815,p=47,q=61,(n)=2760,时，,d=167,n=2867,e=1223,2024/10/3,15,用RSA算法加密与解密的过程：2756 2001 054,RSA,算法实现,如何判定一个给定的大整数是素数？,已知,d,如何计算,e,，使,e*d1 mod(n),？,如何计算,C M,e,mod n,或,MC,d,mod n,？,2024/10/3,16,RSA算法实现如何判定一个给定的大整数是素数？2022/9/,Miller-Rabin,素性检验算法,2024/10/3,17,Miller-Rabin 素性检验算法2022/9/281,求模逆元的扩展欧几里德算法,2024/10/3,18,求模逆元的扩展欧几里德算法2022/9/2818,求模幂的模重复平方计算法,求,a,m,，其中,a，m,是正整数：,将,m,表示为二进制形式,b,k,b,k-1,b,0,，,m=b,k,2,k,+b,k-1,2,k-1,+b,1,2+b,0,2024/10/3,19,求模幂的模重复平方计算法求am，其中a，m是正整数：202,RSA,的快速实现,加密很快，指数小,解密比较慢，指数较大,利用中国剩余定理,CRT,，,CRT,对,RSA,解密算法生成两个解密方程,（利用,M=C,d,mod pq,）,即,:M,1,=M mod p=(C mod,p),d mod(p-1),mod p,M,2,=M mod q=(C mod q),d mod(q-1),mod q,解方程,M=M,1,mod p,M=M,2,mod q,具有唯一解（利用,CRT,）,2024/10/3,20,RSA的快速实现加密很快，指数小2022/9/2820,RSA,的安全性,RSA,的安全性是基于分解大整数的困难性假定如果分解,n=p,q,，,则立即获得,(,n,)=(,p,1)(,q,1),，,从而能够确定,e,的模,(,n,),乘法逆,d,由,n,直接求,(,n,),等价于分解,n,RSA-129,历时,8,个月被于,1996,年,4,月被成功分解，,RSA,130,于,1996,年,4,月被成功分解,密钥长度应该介于,1024bit,到,2048bit,之间,2024/10/3,21,RSA的安全性RSA的安全性是基于分解大整数的困难性假定如果,2024/10/3,22,2022/9/2822,DES,和,RSA,性能比较（同等强度）,2024/10/3,23,DES和RSA性能比较（同等强度）2022/9/2823,RSA,的安全性,|,p-q,|,要大,p,-1,q,-1,都应有大的素因子。,en,且,dn,1/4,则,d,能被容易的确定。,2024/10/3,24,RSA的安全性|p-q|要大2022/9/2824,|p-q|,要大,?,如果,|p-q|,小,稍大于,n,稍大于,顺序检查大于 的每一整数,x,，直到找到一个,x,使得,x,2,-n,是某一整数（记为,y,）的平方。,由,x,2,-n=y,2,，得,n=(x+y)(x-y),。,2024/10/3,25
展开阅读全文