RSA报告

1公钥密码体制1976年，美国学者Diffie和Hellman为解决密钥的分发与管理问题发表了著名论文《密码学的新方向》NewDirectioninCryptography[krɪpˈtɑɡrəfi]，提出一种密钥交换协议，允许在不安全的媒体上通过通讯双方交换信息，安全地传送秘密密钥，并提出了建立“公开密钥密码体制”(PublicKey)的新概念。提出了“单向陷门函数”的概念。单向陷门函数One-wayTrapdoor[træpdɔːr]Function是有一个陷门的一类特殊单向函数。它首先是一个单向函数，在一个方向上易于计算而反方向却难于计算。但是，如果知道那个秘密陷门，则也能很容易在另一个方向计算这个函数。即已知x，易于计算f（x），而已知f（x），却难于计算x。然而，一旦给出f（x）和一些秘密信息y，就很容易计算x。在公开密钥密码中，计算f（x）相当于加密，陷门y相当于私有密钥，而利用陷门y求f（x）中的x则相当于解密。RSA算法1978年，Rivest、Shamir和Adleman[admen]提出首个候选陷门函数。直至今日，仍被认为是安全的。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。下面解释RSA算法的原理。先介绍要用到的几个数学概念。可以看到，RSA算法并不难，只需要一点数论知识就可以理解。1互质关系如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。需要注意的是，不是质数也可以构成互质关系。关于互质关系，不难得到以下结论：p是大于1的整数，则p和p-1构成互质关系。2欧拉函数请思考以下问题：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以)(n表示。)(n的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。①如果n=1，则φ(1)=1。因为1与任何数（包括自身）都构成互质关系。②如果n是质数，则φ(n)=n-1。因为质数与小于它的每一个数，都构成互质关系。③如果n是质数的某一个次方，即n=p^k(p为质数，k为大于等于1的整数)，则比如φ(8)=φ(2^3)=2^3-2^2=8-4=4。在1到8之中，与8形成互质关系的是1、3、5、7，所以)(n=4。这是因为只有当一个数不包含质数p，才可2能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。④如果n可以分解成两个互质的整数之积，n=p×q则)1)(1()(qpn即积的欧拉函数等于各个因子的欧拉函数之积。这一条的证明要用到中国剩余定理，这里就不展开了，只简单说一下思路：如果a与p互质(ap)，b与q互质(bq)，c与pq互质(cpq)，则c与数对(a,b)是一一对应关系。由于a的值有φ(p)种可能，b的值有φ(q)种可能，则数对(a,b)有φ(p)φ(q)种可能，而c的值有φ(pq)种可能，所以φ(pq)就等于φ(p)φ(q)。3在数论中，欧拉定理，是一个关于同余的性质。欧拉定理表明，若n，a为正整数且互质，则)(mod1)(nan4如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数是1。)(mod1nab这时，b就叫做a的模反元素。计算e对于)(n的模反元素d，使得1)(nked这个公式也可以表达为))((mod1ned于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。ex+φ(n)y=1这个方程可以用扩展欧几里得算法gcd（a，b）=ax+by求解，根据数论的相关知识，肯定是有解的。密钥生成的步骤（1）选择一对不同的、足够大的素数p，q。（2）计算qpn。（3）计算)1)(1()(qpn，同时对p，q严加保密，不让任何人知道。（4）找一个与)(n互质的数e，且)(1ne。（5）计算e对于)(n的模反元素d，使得1)(nked。这个公式也可以表达为))((mod1ned（6）公钥KU=(e,n)，私钥KR=(d,n)。RSA加密与解密加密要用公钥(n,e)，假设A要向B发送加密信息m，他就要用B的公钥(n,e)对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode3值），且m必须小于n。所谓加密，就是算出下式的c：)(modnmce解密就是算出下式的d：)(modnmcd我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。值得注意的是，公钥(n,e)只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种对称性加密算法（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。私钥解密的证明为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子：)(modnmcd因为，根据加密规则)(modnmce于是，c可以写成下面的形式：knmce将c代入要我们要证明的那个解密规则：)(mod)(nmknmde它等同于求证)(modnmmed由于))((mod1ned所以1)(nhed将ed代入)(mod1)(nmmnh接下来，分成两种情况证明上面这个式子。（1）m与n互质。根据欧拉定理，此时)(mod1)(nmn得到)(mod)()(nmmmhn原式得到证明。（2）m与n不是互质关系。此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。以m=kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：)(mod1)(1qkpq进一步得到)(mod))(()1(1qkpkpkpphq即)(mod)(qkpkped将它改写成下面的等式kptqkped)(这时t必然能被p整除，即pttkppqtkped)(因为m=kp，n=pq，所以)(modnmmed原式得到证明。4RSA的安全性RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。RSA的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的选择密文攻击RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法构：(XM)^d=X^d*M^dmodn前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-WayHashFunction对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。RSA的公共模数攻击。若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n。密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，故用Euclidean算法能找到r和s，足：r*e1+s*e2=1。假设r为负数，需再用Euclidean算法计算C1^(-1)，则(C1^(-1))^(-r)*C2^s=Pmodn另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。RSA的小指数攻击。有一种提高RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长5度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。