搜索
第4章数据加密技术信息学院刘丽4.1密码学基础124.2对称密码体制34.4消息认证44.3公钥密码体制4.5数字签名124.6身份认证3424.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.dmodø(N)=1且0≤d≤N•公布公钥:KU={e,N}•保存私钥:KR={d,N}RSA的使用•发送方要加密明文M:–获得接收方的公钥KU={e,N}–计算:C=MemodN,where0≤MN•接收方解密密文C:–使用自己的私钥KR={d,N}–计算:M=CdmodN•注意：M必须比N小RSAExample1.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×16+16.PublishpublickeyKU={7,187}7.KeepsecretprivatekeyKR={23,187}RSAExample•sampleRSAencryption/decryptionis:•givenmessageM=88(nb.88187)•encryption:C=887mod187=11•decryption:M=1123mod187=88模幂运算•模幂运算是RSA中的主要运算•[(amodn)×(bmodn)]modn=(a×b)modn•利用中间结果对n取模，实现高效算法RSA密钥生成•必须做–确定两个大素数：p,q–选择e，并计算d•素数测试是重要的算法课堂演练：RSA-Tool的使用RSA的安全性•三种攻击RSA的方法:–强力穷举密钥–数学攻击：实质上是对两个素数乘积的分解–时间攻击：依赖解密算法的运行时间Diffie-Hellman密钥交换算法•Diffie-Hellman密钥交换算法的目的：•使得两个用户能够安全的交换密钥，供以后加密消息时使用。该算法本什么仅局限与密钥交换。Diffie-Hellman密钥交换算法•有效性依赖于计算离散对数的难度•离散对数定义：首先定义一个素数p的原根，为其各次幂产生从1到p-1的所有整数根，也就是说，如果a是素数p的一个原根，那么数值•amodp,a2modp,...,ap-1modp•是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数Diffie-Hellman密钥交换算法•对于一个整数b和素数p的一个原根a，可以找到惟一的指数i，使得•b=aimodp其中0≤i≤(p-1)•指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda,p(b)。算法描述•1、有两个全局公开的参数，一个素数q和一个整数α，α是q的一个原根。•2、假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XAq，并计算公开密钥YA=αXAmodq。A对XA的值保密存放而使YA能被B公开获得。•用户B选择一个私有的随机数XBq，并计算公开密钥YB=αXBmodq。B对XB的值保密存放而使YB能被A公开获得。•3、用户A产生共享秘密密钥的计算方式是K=(YB)XAmodq。同样，用户B产生共享秘密密钥的计算是K=(YA)XBmodq。•4、因为XA和XB是保密的，一个敌对方可以利用的参数只有q、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户B的秘密密钥，敌对方必须先计算•XB=inda,q(YB)•然后再使用用户B采用的同样方法计算其秘密密钥K。•注意：虽然计算模幂运算相对容易，但是计算离散对数却非常困难。对于大素数，计算离散对数认为是不可行的。Diffie-Hellman的简单协议Diffie-Hellman算法优点•仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。•除对全局参数的约定外，密钥交换不需要事先存在的基础结构。不足•没有提供双方身份的任何信息。•它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥。受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作。•没办法防止重演攻击。•容易遭受中间人的攻击•思考：•1考虑公共素数q=11和本原根α=2的Diffie-Hellman方案•a。如果用户A有公钥YA=9,请问A的私钥是什么?•b.如果用户B有公钥YB=3,请问共享的密钥是什么？•2.在使用RSA的公钥系统中，你可截获发送给用户的密文是C=10，并且已知他的公钥是e=5，n=35.明文M是什么？