公钥密码学与RSA

第9章公钥密码学与RSA公钥密码学是密码学一次伟大的革命1976年，Diffie和Hellman在“密码学新方向”一文中提出使用两个密钥：公密钥、私密钥加解密的非对称性利用数论的方法是对对称密码的重要补充公钥密码学解决的基本问题密钥交换对称密码进行密钥交换的要求：已经共享一个密钥利用密钥分配中心数字签名与传统的签名比较公钥密码体制重要特点仅根据密码算法和加密密钥来确定解密密钥在计算上不可行两个密钥中的任何一个都可用来加密，另一个用来解密。六个组成部分：明文、密文；公钥、私钥；加密、解密算法公钥密码体制公钥密码体制的加密功能A向B发消息X，B的公钥为KUb,私钥为KRb加密Y=EKUb(X)解密X=DKRb(Y)公钥密码体制的加密公钥密码体制的认证A向B发送消息XA的公钥为KUa，私钥为KRa“加密”：Y=EKRa(X)（数字签名）“解密”：X=DKUa(Y)注意：不能保证消息的保密性公钥密码体制的认证具有保密与认证的公钥体制对称密码公钥密码一般要求：1、加密解密用相同的密钥2、收发双方必须共享密钥安全性要求：1、密钥必须保密2、没有密钥，解密不可行3、知道算法和若干密文不足以确定密钥一般要求：1、加密解密算法相同，但使用不同的密钥2、发送方拥有加密或解密密钥，而接收方拥有另一个密钥安全性要求：1、两个密钥之一必须保密2、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若干密文不能确定另一个密钥关于公钥密码的几种误解公钥密码比传统密码安全？公钥密码是通用方法，所以传统密码已经过时？公钥密码实现密钥分配非常简单？RSA算法由MIT的Rivest,Shamir&Adleman在1977提出最著名的且被广泛应用的公钥加密体制明文、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数RSA算法描述加密：C=MemodN,where0≤MN解密：M=CdmodN公钥为（e，N），私钥为（d，N）必须满足以下条件：Med=MmodN计算Me和Cd是比较容易的由e和n确定d是不可行的RSA密钥产生过程随机选择两个大素数p,q计算N=p.q注意ø(N)=(p-1)(q-1)选择e使得1eø(N),且gcd(e,ø(N))=1解下列方程求出de.d=1modø(N)且0≤d≤N公布公钥:KU={e,N}保存私钥:KR={d,p,q}RSA的使用发送方要加密明文M:获得接收方的公钥KU={e,N}计算:C=MemodN,where0≤MN接收方解密密文C:使用自己的私钥KR={d,N}计算:M=CdmodN注意：M必须比N小为什么RSA可以加解密因为Euler定理的一个推论:Mkø(n)＋1=MmodNRSA中:N=p.qø(N)=(p-1)(q-1)选择e&d使得ed＝1modø(N)因此存在k使得e.d=1+k.ø(N)因此Cd=(Me)d=M1+k.ø(N)=MmodNRSAExample1.Selectprimes:p=17&q=112.Computen=pq=17×11=1873.Computeø(n)=(p–1)(q-1)=16×10=1604.Selecte:gcd(e,160)=1;choosee=75.Determined:de=1mod160andd160Valueisd=23since23×7=161=10×160+16.PublishpublickeyKU={7,187}7.KeepsecretprivatekeyKR={23,17,11}RSAExamplecontsampleRSAencryption/decryptionis:givenmessageM=88(nb.88187)encryption:C=887mod187=11decryption:M=1123mod187=88模幂运算模幂运算是RSA中的主要运算[(amodn)×(bmodn)]modn=(a×b)modn利用中间结果对n取模，实现高效算法ExponentiationRSA密钥生成必须做确定两个大素数：p,q选择e或者d，并计算d或者e素数测试是重要的算法由e求d要使用到扩展Euclid算法RSA的安全性三种攻击RSA的方法:强力穷举密钥数学攻击：实质上是对两个素数乘积的分解时间攻击：依赖解密算法的运行时间因子分解问题三种数学攻击方法分解N=p.q,因此可计算出ø(N)，从而确定d直接确定ø(N)，然后找到d直接确定d大家相信：由N确定ø(N)等价于因子分解TimingAttacksdevelopedinmid-1990’sexploittimingvariationsinoperationseg.multiplyingbysmallvslargenumberorIF'svaryingwhichinstructionsexecutedinferoperandsizebasedontimetakenRSAexploitstimetakeninexponentiationcountermeasuresuseconstantexponentiationtimeaddrandomdelaysblindvaluesusedincalculationsSummaryhaveconsidered:principlesofpublic-keycryptographyRSAalgorithm,implementation,security