《RSA的破解方法探讨.doc》由会员分享，可在线阅读，更多相关《RSA的破解方法探讨.doc（4页珍藏版）》请在三一办公上搜索。
1、RSA的破解方法探讨摘 要RSA加密体制广泛应用于信息安全领域中的信息加密和数字签名，其应用原理是产生一对密钥，一个为用户所保留，另一个则可以由任意用户获得，并且很难通过一个密钥去获取另一个密钥，从而保证公钥体制的安全性。本文通过欧拉函数以及其扩展的欧拉函数，试图由一个密钥去获取另一个密钥。关 键 词欧拉函数；逆元；RSA；密钥；破解一、问题的定义（一）RSA算法简介RSA算法是1978年由三个人提出的一种用数论构造的、迄今为止理论上最完善的公钥密码体制。它不仅可以用于加密信息，也可以用于数字签名。它的基本思想是产生一对密钥，其中一个用来加密信息，称之为公钥，任何人通过一定的方式都可以获取他人
2、的公钥；另一个用来解密信息，称之为私钥，私钥只有本人才拥有。按照如下的过程产生一对密钥：（1）任意选取两个保密的大素数和（2）计算出，其中是的欧拉函数值（3）任意选取一个整数，满足，且（4）计算，使其满足式子，也就是说，和互为乘法逆元（5）以为秘密密钥，以为公开密钥1由于和很大，而且一旦计算出的值以后，和即被销毁，也就无法根据和计算出，因此，无法通过或计算出另一个值。（二）问题的定义根据和的关系可知，这两个数是模的逆元，也就是说，利用和的乘积去模数，余数等于1，因此，只要能够计算出的值，就可以借助一定的工具与原理，通过或计算出另一个值，从而破解RSA加密算法。二、算法的破解分析（一）理论依据（
3、1）欧拉函数由密钥的生成过程可知，是的欧拉函数。欧拉函数的定义是：设是一正整数，小于且与互素的正整数的个数称为的欧拉函数。2（2）推广的欧拉函数假设有整数和，且，则，称是的逆元。2（二）破解的思路（1）计算的欧拉函数在公钥加密体制中，由于是公开的，因此，根据欧拉函数的定义，可以计算出的欧拉函数。再根据推广的欧拉函数，可以计算出一个数的逆元。计算欧拉函数的算法分为两个步骤：其中函数gcd（）是计算两个数是否互为素数，如果是，则返回1作为函数的值，否则返回0；函数count（）是用来统计1之间，与互为素数的元素的数量。函数的算法如下：int count(int q) for(i=1;iq;i+)
4、if(gcd(i,q)= =1) n+; /其中表示互为素数的元素的统计量 return n;int gcd(int a,int q) if(a= =0) return q; else return gcd(q%a,a); /通过辗转相除法计算这两个数的公约数，如果公约数为1，/则表示这两个数互为素数。（2）计算逆元令，又由于，将代入公式，得。根据推广的欧拉函数，可以求出的逆元，因为，如果两个数互为素数，一般来说，表达式有惟一的解，其中的即为的逆元。其算法如下： int inverse(int q)g=count(q); /表示的欧拉函数 for(i=1;ig;i+) mod*=e; d=(i
5、nt)(mod%q); return d; 算法中的即为的逆元。（三）举例说明假设用户A选取和。根据公钥的生成方法，可以求出，欧拉函数。若选取，满足，且，根据扩展的欧基里德算法可以求出的逆元。则公钥为，以为公开私钥。通过向CA机构，可以申请得到A的公钥，也就是说可以得到，。首先通过求解其欧拉函数的值。根据上面的算法，通过count（）和gcd（）可以计算出它的值为96。令，求模的逆元，再根据算法inverse（）可以求出逆元的大小为77，和用户的私钥相一致。在求解逆元的过程中，如果得到的值小于0，可以通过表达式将其转换为一个正整数。三、结论在公钥加密体制中，由于是两个保密的大素数和的乘积，而的欧拉函数是通过计算得到的。而通过欧拉函数本身的定义可得到计算欧拉函数的方法，可以借助计算机程序，利用扩展的欧拉函数来破解用户的私钥。参 考 文 献1杨波.现代密码学M，北京：清华大学出版社，2007：1052蔡乐才.应用密码学M，中国电力出版社，2005：353Niels Ferguson, Bruce Schneier编，张振峰，徐静,等译.密码学实践M，北京：电子工业出版社，2005：174杨义先，钮心忻.应用密码学M，北京：北京邮电大学出版社，2005 5谭浩强.C程序设计M，北京：清华大学出版社，1999
