信息安全技术chapter6公钥密码学和RAS算法

东南大学信息安全学科研究生学位课网络信息安全理论与技术黄杰信息安全研究中心第六讲公钥密码学与RSA本次课内容•数论入门–素数–Fermat定理和Euler定理–素性测试–离散对数•公钥密码学•RSA数论入门素数•任意正整数可由素数的乘积来表示。•整数12可用{a2=2,a3=1}来表示•整数18可用{a2=1,a3=2}来表示•两数相乘。对应指数相加。•整除的表示。对应指数比较大小。•最大公因子的计算。对应指数取最小值。–K=gcd(a,b)--对所有的p，kp=min(ap,bp),0pappPapaFermat定理•Fermat定理：若p是素数，a是正整数且不能被p整除，则•Fermat定理的另一种有用表示：若p是素数，a是任意正整数，则papmod11paapmodEuler函数•Euler函数Φ(n)，指小于n且与n互素的正整数的个数。•对于素数p有：Φ(p)=p-1•例如，P=7,小于7且与7互素的正整数有：1，2，3，4，5，6，所以Φ(7)=6•如果p=15，Φ(15)=??•Φ(15)=8•对于两个素数p和q，p≠q，那么对n=pq，有：Φ(n)=Φ(pq)=Φ(p)×Φ(q)=(p-1)×(q-1)Euler定理•Euler定理：对于任意互素的a和n，有：•Euler定理的另一种有用表示：•推论：给定两个素数p和q，整数n=pq，对于小于n的任意正整数m，有以下关系式成立：•推论的另一种表达形式：()1modnan()1modnaan()1(1)(1)1modnpqmmmn()1modknmmn素性测试•Miller-Rabin算法–目的：检验给定的大数n是否素数，如2150+1是否素数？–Miller和Rabin提出的算法较为常用。该算法不能确定一个大数是素数，但是可以确定一个大数是合数。–奇整数n=3的表示：n-1=2kq,k0,q为奇数–运算时间O(logn)Miller-Rabin算法•性质1：如果p是素数，a是小于p的正整数，当且仅当amodp=1或amodp=-1时，a2modp=1。•性质2：设p是大于2的素数，有p-1=2kq,k0,q为奇数。设a是整数，且1ap-1，则下面两个条件必有一个成立：–aq模p和1同余。–整数aq,a2q,…..,a2k-1q里存在一个数，模p时和-1同余。Miller-Rabin算法•atestbasedonFermat’sTheorem•algorithmis:TEST(n)is:1.Findintegersk,q,k0,qodd,sothat(n–1)=2kq2.Selectarandomintegera,1an–13.ifaqmodn=1thenreturn(“maybeprime);4.forj=0tok–1do5.if(a2jqmodn=n-1)thenreturn(maybeprime)6.return(composite)Miller-Rabin算法•如何利用Miller-Rabin算法确定某整数是或不是素数，并且要有很高的可信度？–对随机选取的a，重复调用TEST(n)，如果某时刻TEST返回“合数”，则n一定不是素数；若n为非素奇数，则TEST返回不确定的概率小于1/4。若TEST连续t次返回“不确定”，则n是素数的概率至少是1-4-t。•随机选取大素数的难度？也即需要进行多少次素性测试以找到一个素数？–素数定理：n附近的素数分布情况为，平均每ln(n)个整数中有一个素数。需测试的整数个数约为0.4ln(n)。另，素数的分布没有确定的规律。AKS算法•2002年，Agrawal，Kayal和Saxena设计•该算法是多项式时间的确定算法•运算时间O((logn)^12)•改善现代密码系统的安全性改进算法：•AKS－Berrizbeitia算法，复杂度O((logn)^6)•AKS－Bernstein算法，复杂度O((logn)^4)AKS算法离散对数•作用？•使得am≡1(modn)成立的最小正幂为m。此时，称m为：–a模n的阶–a所产生的周期长–a所属的模n的指数•本原根•若a是n的本原根，则a的1到Φ(n)次幂的模n各不相同的，且均与n互素。•当p为素数时，若a是n的本原根a的1到(p-1)次幂的模p各不相同的。a:primitiveroot模19的整数幂离散对数•离散对数的定义–对于某素数p，p的本原根为a；–对于任何整数b；–存在唯一的整数i,，使得–i称为以a为底b的指标也记为离散对数，记为dloga,p(b)•离散对数的性质•离散对数的计算y≡gxmodp已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的)1(0pipabimod,()apindb公钥密码学引言1双重加密方案•双重加密方案1.Alice把消息放到箱子里，用自己的锁锁上发送给Bob2.Bob收到箱子后加上自己的锁，在把箱子返回给Alice3.Alice除掉自己的锁，再把箱子寄给Bob4.Bob除掉自己的锁，读取消息•双重加密方案的数学描述：1.Alice发送EA(P)给Bob2.Bob发送EB(EA(P))给Alice3.Alice发送DA(EB(EA(P)))=DA(EA(EB(P)))=EB(P)给Bob4.Bob解密DB(EB(P)=P•双重加密方案的分析–要求构造一个函数，满足：•EB(EA(P))=EA(EB(P))–无法验证Alice或Bob的身份–Diffie的解决方法：–使用两个密钥而不是一个密钥传统密码中的两个难题•密钥分配问题。•数字签名问题。能否确保数字签名是出自某特定的人，并且各方对此均无异议？公钥密码学•公钥密码学和其之前的对称密码的区别•对称密码采用混淆和扩散；•公钥算法采用数学函数；•对称密码只使用一个密钥；•公钥算法使用两个独立的密钥。•关于公钥密码的误解•公钥密码比对称密码安全•公钥密码可以取代传统密码•公钥密码可以很容易的实现密钥分配公钥密码体制的组成部分•特点–仅根据密码算法和加密密钥不能确定解密密钥–两个密钥中任何一个用于加密，另一个解密•六个组成部分–明文–加密算法–公钥–私钥–密文–解密算法用公钥密码实现保密•用户拥有自己的密钥对(KU,KR)•公钥KU公开,私钥KR保密•A--B:Y=EKUb(X)•B:DKRb(Y)=DKRb(EKUb(X))=X公钥密码体制（加密过程）BobAlice用公钥密码实现认证•条件:两个密钥中任何一个都可以用作加密而另一个用作解密•认证:–AALL:Y=DKRa(X)–ALL:EKUa(Y)=EKUa(DKRa(X))=X对称密码和公钥密码对称密码一般要求1、加解密使用相同的密钥2、收发双方必须共享密钥安全性要求1、密钥必须秘密保存。2、无密钥，解密消息不可行。3、知道算法和密文不影响密钥的安全性。公钥密码一般要求1、算法相同，但不同加解密密钥。2、发送方和接受方拥有不同密钥。安全性要求1、有一个密钥必须保密2、无密钥，解密信息不可行。3、知道算法、其中的一个密钥和若干密文，不影响另一个密钥的安全性。PrinciplesofPKC公钥密码体制（认证过程）BobAlice关于认证的讨论•认证加密算法•加密整条消息•加密部分消息(消息摘要)•认证不能保证消息的保密性。•需要：–既能提供认证功能，又能保持保密性的方法公钥密码体制的应用•加密/解密•数字签名•密钥交换算法加密/解密数字签名密钥交换RSA算法是是是椭圆曲线是是是Diffie-Hellman否否是DSS否是否对公钥密码的要求•公钥和私钥的产生在计算上是容易的；•已知公钥和明文，产生密文在计算上是容易的；•已知私钥和密文，恢复出明文在计算上是容易的；•已知公钥，确定私钥在计算上是不可行的；•已知公钥和密文，恢复明文在计算上是不可行的；•加密和解密函数的顺序可以交换公钥密码分析•穷举攻击——使用长密钥–长密钥和短密钥矛盾–仅用于数字签名和密钥管理中•从给定的公钥计算私钥•穷举消息攻击–无论公钥体制的密钥有多长，这种攻击都可以转化为对56位密钥的穷举攻击。–抗攻击的方法：在发送的消息后附加一个随机数。RSA算法RSA算法•1977年Rivest,Shamir和Adleman共同提出，是最早提出的满足要求的公钥算法之一，是被广泛接受且被实现的通用公钥加密方法。•RSA是一种分组密码。明文和密文均为0到n-1的整数，通常n的大小为1024位二进制数或309位十进制数。S、R、ARSA算法描述•对于明文分组M，密文分组C，•加密过程：C=Memodn•解密过程：M=Cdmodn=(Me)dmodn=Medmodn•公钥用于加密KU={e,n}•私钥用于解密KR={d,n}•如何满足条件：M=Medmodn？RSA算法中的元素•两个素数，p,q(保密)•n=pq,（公开）•e,gcd(Φ(n),e)=1,（公开）•d,(保密)RSA加解密举例•例子–p=17–q=11–n=187–Φ(n)=？–e选为7–d=23–公钥为？私钥为？–输入明文M=88.密文为？如何计算abmodn•先计算幂，再取模——中间结果非常大•幂运算的有效性问题•解决方法：•利用模算术的性质(axb)modn=[(amodn)x(bmodn)]modn•重复计算中间结果的平方a2a4a8a16,只需四次乘法aaaaaaaaaaaaaaaaa16如何计算abmodn)2(0)2(0iiibiaaabm计算abmodn的算法：nnananaiiiibbmmod])mod[(mod)(mod)2(0)2(0密钥产生•如何找到足够大的素数p和q?•选择e或d计算另外一个素数选取•为了避免攻击者用穷举法求出p和q，应该从足够大的集合中选取p和q。即p和q必须是大素数。•没有产生任意的大素数的有用技术，通常的作法是随机选取一个需要的数量级的奇数并检验这个数是否是素数。若不是则挑选下一个随机数直至检测到素数为止。RSA的安全性•对RSA的攻击方法主要有以下三种：1.强力攻击（穷举法）：尝试所有可能的私有密钥2.数学分析攻击：有多种数学攻击方法，其本质等价于试图分解两个素数的乘积3.计时攻击：记录计算机解密消息所用的时间。4.选择密文攻击：利用RSA算法的性质。因子分解的计算量整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次）501.4x10103.9小时759.0x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0x1015年5001.3x10394.2x1025年因子分解问题的进展情况RSA的实现要求•若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效的时间内将n分解出来。建议选择p和q大约是100位的十进制素数。•模n的长度要求至少是512比特。在最近一段时间里，n取在1024到2048位是合适的。计时攻击•计时(Timing)攻击法由P.Kocher提出，利用测定RSA解密所进行的模指数运算的时间来估计解密指数d，而后再精确定出d的取值。•对策•使用恒定的幂运算时间•加一个随机延迟•隐蔽方法东南大学信息安全学科研究生学位课网络信息安全理论与技术谢谢！