公钥密码学与RSA课件.ppt

1、第9章 公钥密码学与RSA第1页，共26页。公钥密码学n是密码学一次伟大的革命n1976年，Diffie和Hellman 在“密码学新方向”一文中提出n使用两个密钥：公密钥、私密钥n加解密的非对称性n利用数论的方法n是对对称密码的重要补充第2页，共26页。公钥密码学解决的基本问题n密钥交换n对称密码进行密钥交换的要求：n已经共享一个密钥n利用密钥分配中心n数字签名n与传统的签名比较第3页，共26页。公钥密码体制n重要特点n仅根据密码算法和加密密钥来确定解密密钥在计算上不可行n两个密钥中的任何一个都可用来加密，另一个用来解密。n六个组成部分：n明文、密文；公钥、私钥；n加密、解密算法第4页，共2

2、6页。公钥密码体制第5页，共26页。公钥密码体制的加密功能nA向B发消息X，nB的公钥为KUb,私钥为KRbn加密 Y=EKUb(X)n解密 X=DKRb(Y)第6页，共26页。公钥密码体制的加密第7页，共26页。公钥密码体制的认证nA向B发送消息XnA的公钥为KUa，私钥为KRan“加密”：Y=EKRa(X)（数字签名）n“解密”：X=DKUa(Y)n注意：不能保证消息的保密性第8页，共26页。公钥密码体制的认证第9页，共26页。具有保密与认证的公钥体制第10页，共26页。对称密码 公钥密码一般要求：一般要求：1、加密解密用相同的密钥2、收发双方必须共享密钥安全性要求：安全性要求：1、密钥必

3、须保密2、没有密钥，解密不可行3、知道算法和若干密文不足以确定密钥一般要求：一般要求：1、加密解密算法相同，但使用不同的密钥2、发送方拥有加密或解密密钥，而接收方拥有另一个密钥安全性要求：安全性要求：1、两个密钥之一必须保密2、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若干密文不能确定另一个密钥第11页，共26页。关于公钥密码的几种误解n公钥密码比传统密码安全？n公钥密码是通用方法，所以传统密码已经过时？n公钥密码实现密钥分配非常简单？第12页，共26页。RSA算法n由MIT的 Rivest,Shamir&Adleman 在 1977 提出n最著名的且被广泛应用的公钥加密体制 n明文

4、、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数第13页，共26页。RSA算法描述n加密：C=Me mod N,where 0MNn解密：M=Cd mod N n公钥为（e，N），私钥为（d，N）n必须满足以下条件：nMed=M mod Nn计算Me和Cd是比较容易的n由e和n确定d是不可行的第14页，共26页。RSA 密钥产生过程n随机选择两个大素数 p,q n计算 N=p.qn注意(N)=(p-1)(q-1)n选择 e使得1e(N),且gcd(e,(N)=1 n解下列方程求出 d ne.d=1 mod(N)且 0dN n公布公钥:KU=e,N n保存私钥:KR=d,

5、p,q 第15页，共26页。RSA 的使用n发送方要加密明文M:n获得接收方的公钥 KU=e,N n计算:C=Me mod N,where 0MNn接收方解密密文C:n 使用自己的私钥 KR=d,N n计算:M=Cd mod N n注意：M必须比N小第16页，共26页。为什么RSA 可以加解密n因为 Euler 定理的一个推论:nMk(n)1 =M mod NnRSA 中:nN=p.qn(N)=(p-1)(q-1)n选择 e&d 使得ed1 mod(N)n因此 存在k使得e.d=1+k.(N)n因此Cd=(Me)d=M1+k.(N)=M mod N 第17页，共26页。RSA Examplen

6、Select primes:p=17&q=11nCompute n=pq=1711=187nCompute(n)=(p1)(q-1)=1610=160nSelect e:gcd(e,160)=1;choose e=7nDetermine d:de=1 mod 160 and d 160 Value is d=23 since 237=161=10160+1nPublish public key KU=7,187nKeep secret private key KR=23,17,11第18页，共26页。RSA Example contnsample RSA encryption/decrypti

7、on is:ngiven message M=88(nb.88187)nencryption:C=887 mod 187=11 ndecryption:M=1123 mod 187=88 第19页，共26页。模幂运算n模幂运算是RSA中的主要运算n(a mod n)(b mod n)mod n=(a b)mod nn利用中间结果对n取模，实现高效算法第20页，共26页。Exponentiation第21页，共26页。RSA 密钥生成n必须做n确定两个大素数：p,q n选择e或者d，并计算d或者en素数测试是重要的算法n由e求d要使用到扩展Euclid算法第22页，共26页。RSA 的安全性n三

8、种攻击 RSA的方法:n强力穷举密钥n数学攻击：实质上是对两个素数乘积的分解n时间攻击：依赖解密算法的运行时间第23页，共26页。因子分解问题n三种数学攻击方法n分解 N=p.q,因此可计算出(N)，从而确定dn直接确定(N)，然后找到dn直接确定dn大家相信：由N确定(N)等价于因子分解第24页，共26页。Timing Attacksndeveloped in mid-1990snexploit timing variations in operationsneg.multiplying by small vs large number nor IFs varying which instr

9、uctions executedninfer operand size based on time taken nRSA exploits time taken in exponentiationncountermeasuresnuse constant exponentiation timenadd random delaysnblind values used in calculations第25页，共26页。Summarynhave considered:nprinciples of public-key cryptographynRSA algorithm,implementation,security第26页，共26页。