资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,华中农业大学信息学院,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,华中农业大学信息学院,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,华中农业大学信息学院华中农业大学信息学院,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,华中农业大学信息学院,*,Chapter 9,公钥密码学与RSA,Chapter 9 公钥密码学与RS,2024/11/14,华中农业大学信息学院,2,9.1,公钥密码体制的基本原理,传统密码体制只使用一个密钥,收发双方共享这个单一的密钥,密钥是对称的，双方是对等的；,因此，不能确保接收方伪造信息，并声称是该信息是发送方发送的,2023/10/4华中农业大学信息学院29.1 公钥密码体,2024/11/14,华中农业大学信息学院,3,对称密码体制的缺陷,2023/10/4华中农业大学信息学院3 对称密码体制的缺陷,2024/11/14,华中农业大学信息学院,4,公钥密码体制,密码学发展历史中最伟大的一次革命,采用两个密钥：一个公钥，一个私钥,参与方不对等，所以是非对称的；,基于数论中的结论,是私钥密码的补充而不是代替,2023/10/4华中农业大学信息学院4公钥密码体制密码学发,2024/11/14,华中农业大学信息学院,5,为什么需要公钥密码,?,两个考虑：,密钥分配 -KDC,数字签名,公认该发明属于Stanford Uni 的Whitfield Diffie 和 Martin Hellman，于1976年。,New Directions in Cryptography,IEEE Trans.Information Theory,IT-22,pp644-654,Nov 1976,James Ellis(UK CESG),在,1970,年曾提出此概念,2023/10/4华中农业大学信息学院5为什么需要公钥密码?,2024/11/14,华中农业大学信息学院,6,公钥密码体制,公钥,/,双钥,/,非对称 密码都是指使用两个密钥,:,公钥：,可以对任何人公开的密钥，用于加密消息或验证签名。,私钥：,只能由接收者私存，用于解密消息或签名。,非对称,用于加密消息或验证签名的人不能进行消息的解密或消息的签名。,2023/10/4华中农业大学信息学院6公钥密码体制公钥/双,2024/11/14,华中农业大学信息学院,7,公钥密码体制,2023/10/4华中农业大学信息学院7公钥密码体制,2024/11/14,华中农业大学信息学院,8,2023/10/4华中农业大学信息学院8,2024/11/14,华中农业大学信息学院,9,公钥密码体制特点,公钥密码算法依赖于,:,仅仅知道算法和加密密钥，推导解密密钥计算上是不可行的,已知加解密密钥时，进行加解密运算计算上是容易的,两个密钥中的任何一个都可以用来加密，而另一个用来解密。,2023/10/4华中农业大学信息学院9公钥密码体制特点公钥,2024/11/14,华中农业大学信息学院,10,公钥密码体制特点,公钥密码算法应该满足的条件,:,产生一对密钥（公、私钥对）在计算上是容易的；,已知公钥和要加密的消息，发送方产生相应的密文在计算上容易的；,接收方使用其私钥对接收的密文解密以恢复明文在计算上是容易的；,已知公钥时，攻击者要确定私钥在计算上不可行的；,已知公钥和密文，攻击者要恢复明文在计算上不可行的；,加密和解密函数的顺序可以交换（有用但非必要）。,2023/10/4华中农业大学信息学院10公钥密码体制特点公,2024/11/14,华中农业大学信息学院,11,单向陷门函数,单向陷门函数：,若k和X已知，则容易计算 Y=f,k,(X).,若k和Y已知，则容易计算X=f,k,-1,(Y).,若Y已知但k未知，则计算出X=f,k,-1,(Y)是不可行的.,寻找合适的单向陷门函数是公钥密码体制应用的关键,单向陷门函数举例：,离散对数,大整数分解,背包问题,2023/10/4华中农业大学信息学院11单向陷门函数单向陷,2024/11/14,华中农业大学信息学院,12,公钥密码体制：保密性和认证,2023/10/4华中农业大学信息学院12公钥密码体制：保密,2024/11/14,华中农业大学信息学院,13,公钥算法分类,Public-Key Distribution Schemes(PKDS),用于交换秘密信息(依赖于双方主体),常用于对称加密算法的密钥,Public Key Encryption(PKE),用于加密任何消息,任何人可以用公钥加密消息,私钥的拥有者可以解密消息,任何公钥加密方案能够用于密钥分配方案PKDS,许多公钥加密方案也是数字签名方案,Signature Schemes,用于生成对某消息的数字签名,私钥的拥有者生成数字签名,任何人可以用公钥验证签名,2023/10/4华中农业大学信息学院13公钥算法分类Pub,2024/11/14,华中农业大学信息学院,14,公钥密码体制的应用,分为三类:,加密/解密(提供保密性),数字签名(提供认证),密钥交换(会话密钥),一些算法可用于上述三类，而有些只适用用于其中一类或两类。,2023/10/4华中农业大学信息学院14公钥密码体制的应用,2024/11/14,华中农业大学信息学院,15,2023/10/4华中农业大学信息学院15,2024/11/14,华中农业大学信息学院,16,公钥密码体制安全性分析,一样存在穷举攻击,但所使用的密钥一般都非常大,(512bits),安全性基于,容易,（加解密）和,困难,（破译）之间巨大的差别,许多算法没有得到证明是安全的。（包括,RSA,）,需要采用一些特别大的数字,与私钥密码体制相比，速度慢。,2023/10/4华中农业大学信息学院16公钥密码体制安全性,2024/11/14,华中农业大学信息学院,17,RSA,1977,由,MIT,的,Rivest,Shamir,和,Adleman,发明,已知的且被广泛使用的公钥密码方案,有限域中的乘方运算,乘方运算需要,O(log n),3,),操作,(,容易的,),使用一些大的整数(例如.1024 bits),安全性基于大数的素因子分解的困难性,素因子分解需要,O(e,log n log log n,),操作,(,困难的,),2023/10/4华中农业大学信息学院17RSA1977由M,2024/11/14,华中农业大学信息学院,18,2023/10/4华中农业大学信息学院18,2024/11/14,华中农业大学信息学院,19,2023/10/4华中农业大学信息学院19,2024/11/14,华中农业大学信息学院,20,RSA,密钥的建立,每一个用户通过以下方法产生一个公钥,/,私钥对,:,随机地选择两个大的素数,p,q,计算方案中的模数,n=p.q,(n)=(p-1)(q-1),随机地选择一个加密密钥,e,满足,1 e (n),(e,(n)=1,求解下面的方程，以得到解密密钥,d,e.d 1 mod(n)and 0,d n,公开公钥,:PU=e,n,保密私钥,:PR=d,n,2023/10/4华中农业大学信息学院20RSA 密钥的建立,2024/11/14,华中农业大学信息学院,21,RSA 的使用,为了加密消息,M,，发送方,:,获得接收方的公钥,PU=e,n,计算,:C=M,e,mod n,其中,0,M n,为了解密密文,C,，接收者,:,使用自己的私钥,PR=d,n,计算,:M=C,d,mod n,消息M一定要比模数 n小(如果需要的话，可以进行分组),2023/10/4华中农业大学信息学院21RSA 的使用为了,2024/11/14,华中农业大学信息学院,22,RSA的工作原理,Euler,定理,:,a,(n),mod n 1,其中,(a,n)=1,RSA,中,:,n=p.q,(n)=(p-1)(q-1),仔细地选择,e,和,d,使得,mod(n),下，两者互逆,因此存在某个整数,k,，使得,e.d=1+k.(n),成立,所以,:C,d,=M,e.d,=M,1+k.(n),=M,1,.(M,(n),),k,M,1,.(1),k,=M,1,=M mod n,2023/10/4华中农业大学信息学院22RSA的工作原理E,2024/11/14,华中农业大学信息学院,23,RSA,举例,密钥的建立,选择素数,:,p,=17&,q,=11,计算,n,=,p q,=17,x,11=,187,计算,(,n,)=(,p,1)(,q-,1)=16,x,10=160,选择,e:,gcd(e,160)=1;,选择,e,=7,确定,d:,d e=,1 mod 160,且,d,160 d=23,因为,23,x,7=161=10,x,160+1,公钥,PU=7,187,私钥,PR=23,187,2023/10/4华中农业大学信息学院23RSA 举例,2024/11/14,华中农业大学信息学院,24,RSA,举例,加密,/,加密,明文消息,M=88(,注意,88 187),加密,:,C=88,7,mod 187 11,解密,:,M=11,23,mod 187 88,2023/10/4华中农业大学信息学院24RSA 举例,2024/11/14,华中农业大学信息学院,25,幂 运 算,可以用平方和乘法运算,N,次方，只需要,O(log,2,n),次乘法运算,如,.7,5,=7,4,.7,1,=3.7=10 mod 11,如,.3,129,=3,128,.3,1,=5.3=4 mod 11,2023/10/4华中农业大学信息学院25幂 运 算可以用平,2024/11/14,华中农业大学信息学院,26,幂 运 算,c=0;f=1,for i=k downto 0,do c=2 x c,f=(f x f)mod n,if b,i,=1 then,c=c+1,f=(f x a)mod n,return f,2023/10/4华中农业大学信息学院26幂 运 算c=,2024/11/14,华中农业大学信息学院,27,2023/10/4华中农业大学信息学院27,2024/11/14,华中农业大学信息学院,28,加密的效率,加密要计算 e 次方幂,若 e 较小,计算将很快,通常选择 e=65537(2,16,-1),或选择 e=3 或 e=17,但若 e太小(如 e=3)将易受到攻击,用中国剩余定理,必须确保,(e,(n)=1,2023/10/4华中农业大学信息学院28加密的效率加密要计,2024/11/14,华中农业大学信息学院,29,解密的效率,解密计算d次方幂,看起来很大，否则不安全,用中国剩余定理分别计算mod p和mod q，则可以得到所希望的答案,比直接快约4倍,只有知道p和q及私钥的接收者可以直接采用这个技术进行计算,2023/10/4华中农业大学信息学院29解密的效率解密计算,2024/11/14,华中农业大学信息学院,30,RSA 密钥的产生,RSA的用户必须:,随机确定两个素数,p,q,选择e或d，并求出另一个,素数,p,q,一定不能从,n=p.q,轻易得到,意味着数要足够大,典型地用猜测或可能性测试,指数e,d 是互逆的,2023/10/4华中农业大学信息学院30RSA 密钥的产生,2024/11/14,华中农业大学信息学院,31,RSA,安全性分析,攻击RSA可能的方法有:,穷举搜索(对于给定的数字规模是不可行的),数学攻击,(,基于计算,(n),的困难性,模,n,的因子分解的困难性,),计时攻击(基于解密的运行情况),选择密文攻击(RSA的已知特性),2023/10/4华中农业大学信息学院31RSA 安全性分析,2024/11/14,华中农业大学信息学院,32,RSA系统安全性与系统的参数,RSA系统安全性与系统的参数有很大关系
展开阅读全文