公钥密码学及RSA.ppt

公钥密码学与RSA公钥密码学n n是是密码学一次伟大的革命密码学一次伟大的革命n n使用两个密钥：公密钥、私密钥使用两个密钥：公密钥、私密钥n n加解密的非对称性加解密的非对称性n n利用数论的方法利用数论的方法n n是对对称密码的重要补充是对对称密码的重要补充公钥密码学解决的基本问题n n密钥交换密钥交换n n对称密码进行密钥交换的要求：对称密码进行密钥交换的要求：对称密码进行密钥交换的要求：对称密码进行密钥交换的要求：n n已经共享一个密钥已经共享一个密钥已经共享一个密钥已经共享一个密钥n n利用密钥分配中心利用密钥分配中心利用密钥分配中心利用密钥分配中心n n数字签名数字签名n n与传统手写的签名比较与传统手写的签名比较与传统手写的签名比较与传统手写的签名比较公钥密码体制n n重要特点重要特点n n仅根据密码算法和加密密钥来确定解密密钥仅根据密码算法和加密密钥来确定解密密钥仅根据密码算法和加密密钥来确定解密密钥仅根据密码算法和加密密钥来确定解密密钥在计算上不可行在计算上不可行在计算上不可行在计算上不可行n n两个密钥中的任何一个都可用来加密，另一两个密钥中的任何一个都可用来加密，另一两个密钥中的任何一个都可用来加密，另一两个密钥中的任何一个都可用来加密，另一个用来解密。个用来解密。个用来解密。个用来解密。n n六个组成部分：六个组成部分：n n明文、密文；公钥、私钥；明文、密文；公钥、私钥；明文、密文；公钥、私钥；明文、密文；公钥、私钥；n n加密、解密算法加密、解密算法加密、解密算法加密、解密算法公钥密码体制公钥密码体制的加密功能n nA向向B发消息发消息X，n nB的公钥为的公钥为KUb,私钥为私钥为KRbn n加密加密 Y=EKUb(X)n n解密解密 X=DKRb(Y)公钥密码体制的加密公钥密码体制的认证n nA向向B发送消息发送消息Xn nA的公钥为的公钥为KUa，私钥为私钥为KRan n“加密加密”：Y=EKRa(X)（数字签名）数字签名）n n“解密解密”：X=DKUa(Y)n n思考：能保证消息的保密性吗？思考：能保证消息的保密性吗？n n请问：利用公钥密码体制，请问：利用公钥密码体制，n个用户通信个用户通信需要多少个密钥？需要多少个密钥？公钥密码体制的认证具有保密与认证的公钥体制 对称密码 公钥密码一般要求：一般要求：1 1、加密解密用相同的密钥、加密解密用相同的密钥2 2、收发双方必须共享密钥、收发双方必须共享密钥安全性要求：安全性要求：1 1、密钥必须保密、密钥必须保密2 2、没有密钥，解密不可行、没有密钥，解密不可行3 3、知道算法和若干密文不足、知道算法和若干密文不足以确定密钥以确定密钥一般要求：一般要求：1 1、加密解密算法相同，但使、加密解密算法相同，但使用不同的密钥用不同的密钥2 2、发送方拥有加密或解密密、发送方拥有加密或解密密钥，而接收方拥有另一个密钥钥，而接收方拥有另一个密钥安全性要求：安全性要求：1 1、两个密钥之一必须保密、两个密钥之一必须保密2 2、无解密密钥，解密不可行、无解密密钥，解密不可行3 3、知道算法和其中一个密钥、知道算法和其中一个密钥以及若干密文不能确定另一个以及若干密文不能确定另一个密钥密钥关于公钥密码的几种误解n n公钥密码比传统密码安全？公钥密码比传统密码安全？事实上，任何加密方法的安全性依赖于事实上，任何加密方法的安全性依赖于密钥的长度和破译密文所需要的计算量。密钥的长度和破译密文所需要的计算量。从抗密码分析的角度看，原则上不能说从抗密码分析的角度看，原则上不能说传统密码优于公钥密码，也不能说公钥传统密码优于公钥密码，也不能说公钥密码优于传统密码密码优于传统密码n n公钥密码是通用方法，所以传统密码已公钥密码是通用方法，所以传统密码已经过时？经过时？由于现有的公钥密码方法所需的计算量由于现有的公钥密码方法所需的计算量大，所以取缔传统密码似乎不太可能大，所以取缔传统密码似乎不太可能n n公钥密码实现密钥分配非常简单？公钥密码实现密钥分配非常简单？事实上，使用公钥密码也需要某种形式事实上，使用公钥密码也需要某种形式的协议，该协议通常包含一个中心代理，的协议，该协议通常包含一个中心代理，并且它所包含的处理过程既不必传统密并且它所包含的处理过程既不必传统密码中的那些过程更简单，也不比之更有码中的那些过程更简单，也不比之更有效效n n为什么要提出公钥密码体制为什么要提出公钥密码体制是为了解决传统密码中最困难的两个问是为了解决传统密码中最困难的两个问题而提出的题而提出的密钥分配问题以及数字签密钥分配问题以及数字签名问题名问题RSA算法n n由由MIT的的 Rivest,Shamir&Adleman 在在 1977 提出提出n n最著名的且被广泛应用的公钥加密体制最著名的且被广泛应用的公钥加密体制 n n明文、密文是明文、密文是0到到n-1之间的整数，通常之间的整数，通常n的大小为的大小为1024位或位或309位十进制数位十进制数RSA算法描述n n加密：加密：C=Me mod N,where 0MNn n解密：解密：M=Cd mod N n n公钥为（公钥为（e，N），），私钥为（私钥为（d，N）n n必须满足以下条件：必须满足以下条件：n nM Meded=M mod N=M mod Nn n计算计算计算计算M Me e和和和和C Cd d是比较容易的是比较容易的是比较容易的是比较容易的n n由由由由e e和和和和n n确定确定确定确定d d是不可行的是不可行的是不可行的是不可行的RSA 密钥产生过程n n随机选择两个大素数随机选择两个大素数随机选择两个大素数随机选择两个大素数 p,q p,q n n计算计算计算计算 N=p.qN=p.qn n注意注意注意注意 (N)=(p-1)(q-1)(N)=(p-1)(q-1)n n选择选择选择选择 e e使得使得使得使得1e(N),1e(N),且且且且gcd(e,(Ngcd(e,(N)=1)=1 n n解下列方程求出解下列方程求出解下列方程求出解下列方程求出 d d n ne.d=1 mod(N)e.d=1 mod(N)且且且且 0 0dN dN n n公布公钥公布公钥公布公钥公布公钥:KU=e,N KU=e,N n n保存私钥保存私钥保存私钥保存私钥:KR=d,p,q KR=d,p,q RSA 的使用n n发送方要加密明文发送方要加密明文M:n n获得接收方的公钥获得接收方的公钥获得接收方的公钥获得接收方的公钥 KU=e,N KU=e,N n n计算计算计算计算:C=MC=Me e mod N,where 0MN mod N,where 0MNn n接收方解密密文接收方解密密文C:n n 使用自己的私钥使用自己的私钥使用自己的私钥使用自己的私钥 KR=d,N KR=d,N n n计算计算计算计算:M=M=C Cd d mod N mod N n n注意：注意：M必须比必须比N小小为什么RSA 可以加解密n n因为因为因为因为 Euler Euler 定理的一个推论定理的一个推论定理的一个推论定理的一个推论:n nMMk(n)k(n)1 1 =M mod N=M mod Nn nRSA RSA 中中中中:n nN=p.qN=p.qn n(N)=(p-1)(q-1)(N)=(p-1)(q-1)n n选择选择选择选择 e&d e&d 使得使得使得使得eded1 mod(N)1 mod(N)n n因此因此因此因此 存在存在存在存在k k使得使得使得使得e.d=1+k.(N)e.d=1+k.(N)n n因此因此因此因此C Cd d=(M=(Me e)d d=M=M1+k.(N)1+k.(N)=M mod N =M mod N RSA Example1.1.选择两个素数选择两个素数选择两个素数选择两个素数:p p=17&=17&q q=11=112.2.计算计算计算计算 n n=pqpq =17=17 11=18711=1873.3.计算计算计算计算 (n n)=()=(pp1)(1)(q-q-1)=161)=16 10=16010=1604.4.选择选择选择选择e e 使其使其使其使其gcd(e,160)=1gcd(e,160)=1，且，且，且，且160;160;这里选择这里选择这里选择这里选择 e e=7=75.5.确定确定确定确定 d d:使得使得使得使得de=de=1 mod 160 1 mod 160 且且且且d d 160 160 因为因为因为因为 2323 7=161=17=161=1 160+1 160+1 故取故取故取故取 d=23 d=23 6.6.所得的公钥所得的公钥所得的公钥所得的公钥 KU=7,187KU=7,1877.7.私钥私钥私钥私钥 KR=23,KR=23,187187给定给定 M=88n n加密加密:C=88C=887 7mod 187mod 187=(88=(884 4 mod187)(88mod187)(882 2 mod187mod187 )(88(881 1mod187)mod187)=11=11 n n解密解密:M=11M=112323 mod 187=88 mod 187=88 RSA 密钥生成n n必须做必须做n n确定两个大素数：确定两个大素数：确定两个大素数：确定两个大素数：p,q p,q n n选择选择选择选择e e或者或者或者或者d d，并计算并计算并计算并计算d d或者或者或者或者e en n素数测试是重要的算法素数测试是重要的算法n n由由e求求d要使用到扩展要使用到扩展Euclid算法算法RSA 的安全性n n三种攻击三种攻击 RSA的方法的方法:n n强力穷举密钥强力穷举密钥强力穷举密钥强力穷举密钥n n数学攻击数学攻击数学攻击数学攻击 ：实质上是对两个素数乘积的分解：实质上是对两个素数乘积的分解：实质上是对两个素数乘积的分解：实质上是对两个素数乘积的分解n n时间攻击：依赖解密算法的运行时间时间攻击：依赖解密算法的运行时间时间攻击：依赖解密算法的运行时间时间攻击：依赖解密算法的运行时间因子分解问题n n三种数学攻击方法三种数学攻击方法n n分解分解分解分解 N=p.q,N=p.q,因此可计算出因此可计算出因此可计算出因此可计算出(N)(N)，从而确定从而确定从而确定从而确定d dn n直接确定直接确定直接确定直接确定(N)(N)，然后找到然后找到然后找到然后找到d dn n直接确定直接确定直接确定直接确定d dn n由由N确定确定(N)等价于因子分解等价于因子分解使用RSA几个注意点n n计算能力的不断增强和因子分解算法的计算能力的不断增强和因子分解算法的不断改进，给大密钥的使用造成威胁。不断改进，给大密钥的使用造成威胁。n n因此我们在选择因此我们在选择RSA的密钥大小时应谨的密钥大小时应谨慎小心。在现阶段，密钥大小取在慎小心。在现阶段，密钥大小取在1024到到2048位是合适的位是合适的n n除了要指定除了要指定n的大小外，研究者还提出的大小外，研究者还提出了其他一些限制条件，为了防止可以很了其他一些限制条件，为了防止可以很容易地分解容易地分解n，RSA算法的发明者建议算法的发明者建议p和和q还应满足下列条件还应满足下列条件1.P和和q的长度应仅相差几位的长度应仅相差几位。这样对这样对1024位的密钥而言，位的密钥而言，p和和q都应约在都应约在1075到到10100之间之间2.(p-1)和和(q-1)都应有一个大的素因子。都应有一个大的素因子。3.gcd(p-1,q-1)应该比较小应该比较小 另外，已经证明，若另外，已经证明，若en,且且dn1/4,则则d很容易被确定很容易被确定 计时攻击n n由密码分析家由密码分析家P.C.Kocher于于1996年提出。年提出。被安全专家称为被安全专家称为“有创意的攻击有创意的攻击”n n通过观察系统处理特定函数所花费的时通过观察系统处理特定函数所花费的时间来寻找密文的信息。间来寻找密文的信息。n n定时攻击法的基本思想定时攻击法的基本思想 要计算要计算f=ab mod n,其中其中b用二进制表示为用二进制表示为 b=(bkb1b0)2 即为即为k比特长度。比特长度。计算程序如下计算程序如下(c为临时变量为临时变量):n n定时攻击法的基本思想定时攻击法的基本思想定时攻击法的基本思想定时攻击法的基本思想n n 计算程序计算程序计算程序计算程序n n 分析上述算法分析上述算法分析上述算法分析上述算法,如果指数的当前比特为如果指数的当前比特为如果指数的当前比特为如果指数的当前比特为1 1时时时时，就就就就要运算额外的模运算要运算额外的模运算要运算额外的模运算要运算额外的模运算(d d a a)mod)mod n n，当然此时，当然此时，当然此时，当然此时算法速度减慢算法速度减慢算法速度减慢算法速度减慢。对于某些对于某些对于某些对于某些a a和和和和d d，该模运算是非常该模运算是非常该模运算是非常该模运算是非常慢的慢的慢的慢的，而攻击者很容易掌握这些值而攻击者很容易掌握这些值而攻击者很容易掌握这些值而攻击者很容易掌握这些值。从而从而从而从而，攻击攻击攻击攻击者通过观察系统处理上述函数所花费的时间来者通过观察系统处理上述函数所花费的时间来者通过观察系统处理上述函数所花费的时间来者通过观察系统处理上述函数所花费的时间来判断判断判断判断，当很慢时指数比特就是当很慢时指数比特就是当很慢时指数比特就是当很慢时指数比特就是1 1，不然就是不然就是不然就是不然就是0 0，用用用用上述原理可以得到整个指数。上述原理可以得到整个指数。上述原理可以得到整个指数。上述原理可以得到整个指数。n n 由于上述攻击思想完全区别于以往的攻击方式，由于上述攻击思想完全区别于以往的攻击方式，由于上述攻击思想完全区别于以往的攻击方式，由于上述攻击思想完全区别于以往的攻击方式，所以称其为所以称其为所以称其为所以称其为“有创意的攻击有创意的攻击有创意的攻击有创意的攻击”。n n计时攻击不仅可以攻击计时攻击不仅可以攻击RSA而且可以攻而且可以攻击其他的公钥密码系统击其他的公钥密码系统n n计时攻击的完全不可预知性以及它仅依计时攻击的完全不可预知性以及它仅依赖于明文，所以它具有很大的威胁赖于明文，所以它具有很大的威胁n n其他方法其他方法其他方法其他方法n n迭代攻击、选择明文攻击、公共模攻击、低加迭代攻击、选择明文攻击、公共模攻击、低加迭代攻击、选择明文攻击、公共模攻击、低加迭代攻击、选择明文攻击、公共模攻击、低加密指数攻击等。密指数攻击等。密指数攻击等。密指数攻击等。n n消息隐匿问题消息隐匿问题消息隐匿问题消息隐匿问题1.1.对某些消息出现不动点问题。例如，对于明文对某些消息出现不动点问题。例如，对于明文对某些消息出现不动点问题。例如，对于明文对某些消息出现不动点问题。例如，对于明文x x，使用，使用，使用，使用RSARSA加密，可能出现加密，可能出现加密，可能出现加密，可能出现x xe e=x xmodmod n n，此时，此时，此时，此时消息也就泄露了，称该现象为明文在消息也就泄露了，称该现象为明文在消息也就泄露了，称该现象为明文在消息也就泄露了，称该现象为明文在RSARSA加密加密加密加密下的不动点。对下的不动点。对下的不动点。对下的不动点。对RSARSA算法总有一些不动点，如算法总有一些不动点，如算法总有一些不动点，如算法总有一些不动点，如x x=0,1,(=0,1,(n n-1)-1)。2.一般来说，对一般来说，对RSA加密算法有：加密算法有：1+gcd(e-1,p-1)gcd(e-1,q-1)个不动点个不动点；由于由于e-1,p-1,p-1都是偶数都是偶数，所以不所以不 动点至少有动点至少有339个个。由于由于n非常大非常大，所以所以 一般情况下不动点可以忽略不计一般情况下不动点可以忽略不计，一般系统一般系统 可以不考虑。可以不考虑。如何避免计时攻击n n尽管计时攻击会造成严重的威胁，但是尽管计时攻击会造成严重的威胁，但是有一些简单可行的解决办法，包括有一些简单可行的解决办法，包括1.不变的幂运算时间不变的幂运算时间 保证所有的幂运算在返回结果前执行的保证所有的幂运算在返回结果前执行的时间都相同，这种方法简单，但会降低时间都相同，这种方法简单，但会降低算法的性能算法的性能2.2.随机延时随机延时随机延时随机延时 通过在求幂算法中加入随机延时来迷惑计时攻击通过在求幂算法中加入随机延时来迷惑计时攻击通过在求幂算法中加入随机延时来迷惑计时攻击通过在求幂算法中加入随机延时来迷惑计时攻击者，可提高性能者，可提高性能者，可提高性能者，可提高性能3.3.隐蔽隐蔽隐蔽隐蔽 在执行幂运算之前先将密文乘上一个随机数在执行幂运算之前先将密文乘上一个随机数在执行幂运算之前先将密文乘上一个随机数在执行幂运算之前先将密文乘上一个随机数，这这这这一过程可使攻击者不知道计算机正在处理的是密一过程可使攻击者不知道计算机正在处理的是密一过程可使攻击者不知道计算机正在处理的是密一过程可使攻击者不知道计算机正在处理的是密文的哪些位，这样可防止攻击者一位一位的进行文的哪些位，这样可防止攻击者一位一位的进行文的哪些位，这样可防止攻击者一位一位的进行文的哪些位，这样可防止攻击者一位一位的进行分析，而这种分析正是计时攻击的本质所在。分析，而这种分析正是计时攻击的本质所在。分析，而这种分析正是计时攻击的本质所在。分析，而这种分析正是计时攻击的本质所在。nRSA数字签名应用较广，其在美国申请了数字签名应用较广，其在美国申请了 专利专利 但到但到2000年底保护期已经届满。年底保护期已经届满。n在标准化工作方面：在标准化工作方面：在法国、澳大利亚等都先后采用了在法国、澳大利亚等都先后采用了RSA并使并使 之标准化；之标准化；ISA9796也采用也采用RSA算法。由于算法。由于 其专利保护过期，其专利保护过期，RSA算法在信息安全领域算法在信息安全领域 的应用将愈加广泛。的应用将愈加广泛。