RSA的破解方法探討

1、rsa的破解方法探討摘 要rsa加密體制廣泛應(yīng)用于信息安全領(lǐng)域中的信息加密和數(shù)字簽名，其應(yīng)用原理是產(chǎn)生一對(duì)密鑰，一個(gè)為用戶所保留，另一個(gè)則可以由任意用戶獲得，并且很難通過(guò)一個(gè)密鑰去獲取另一個(gè)密鑰，從而保證公鑰體制的安全性。本文通過(guò)歐拉函數(shù)以及其擴(kuò)展的歐拉函數(shù)，試圖由一個(gè)密鑰去獲取另一個(gè)密鑰。關(guān) 鍵 詞歐拉函數(shù)；逆元；rsa；密鑰；破解一、問(wèn)題的定義（一）rsa算法簡(jiǎn)介rsa算法是1978年由三個(gè)人提出的一種用數(shù)論構(gòu)造的、迄今為止理論上最完善的公鑰密碼體制。它不僅可以用于加密信息，也可以用于數(shù)字簽名。它的基本思想是產(chǎn)生一對(duì)密鑰，其中一個(gè)用來(lái)加密信息，稱之為公鑰，任何人通過(guò)一定的方式都可以獲取他人

2、的公鑰；另一個(gè)用來(lái)解密信息，稱之為私鑰，私鑰只有本人才擁有。按照如下的過(guò)程產(chǎn)生一對(duì)密鑰：（1）任意選取兩個(gè)保密的大素?cái)?shù)和（2）計(jì)算出，其中是的歐拉函數(shù)值（3）任意選取一個(gè)整數(shù)，滿足，且（4）計(jì)算，使其滿足式子，也就是說(shuō)，和互為乘法逆元（5）以為秘密密鑰，以為公開(kāi)密鑰1由于和很大，而且一旦計(jì)算出的值以后，和即被銷毀，也就無(wú)法根據(jù)和計(jì)算出，因此，無(wú)法通過(guò)或計(jì)算出另一個(gè)值。（二）問(wèn)題的定義根據(jù)和的關(guān)系可知，這兩個(gè)數(shù)是模的逆元，也就是說(shuō)，利用和的乘積去模數(shù)，余數(shù)等于1，因此，只要能夠計(jì)算出的值，就可以借助一定的工具與原理，通過(guò)或計(jì)算出另一個(gè)值，從而破解rsa加密算法。二、算法的破解分析（一）理論依據(jù)（

3、1）歐拉函數(shù)由密鑰的生成過(guò)程可知，是的歐拉函數(shù)。歐拉函數(shù)的定義是：設(shè)是一正整數(shù)，小于且與互素的正整數(shù)的個(gè)數(shù)稱為的歐拉函數(shù)。2（2）推廣的歐拉函數(shù)假設(shè)有整數(shù)和，且，則，稱是的逆元。2（二）破解的思路（1）計(jì)算的歐拉函數(shù)在公鑰加密體制中，由于是公開(kāi)的，因此，根據(jù)歐拉函數(shù)的定義，可以計(jì)算出的歐拉函數(shù)。再根據(jù)推廣的歐拉函數(shù)，可以計(jì)算出一個(gè)數(shù)的逆元。計(jì)算歐拉函數(shù)的算法分為兩個(gè)步驟：其中函數(shù)gcd（）是計(jì)算兩個(gè)數(shù)是否互為素?cái)?shù)，如果是，則返回1作為函數(shù)的值，否則返回0；函數(shù)count（）是用來(lái)統(tǒng)計(jì)1之間，與互為素?cái)?shù)的元素的數(shù)量。函數(shù)的算法如下：int count(int q) for(i=1;iq;i+)

4、if(gcd(i,q)= =1) n+; /其中表示互為素?cái)?shù)的元素的統(tǒng)計(jì)量 return n;int gcd(int a,int q) if(a= =0) return q; else return gcd(q%a,a); /通過(guò)輾轉(zhuǎn)相除法計(jì)算這兩個(gè)數(shù)的公約數(shù)，如果公約數(shù)為1，/則表示這兩個(gè)數(shù)互為素?cái)?shù)。（2）計(jì)算逆元令，又由于，將代入公式，得。根據(jù)推廣的歐拉函數(shù)，可以求出的逆元，因?yàn)?，如果兩個(gè)數(shù)互為素?cái)?shù)，一般來(lái)說(shuō)，表達(dá)式有惟一的解，其中的即為的逆元。其算法如下： int inverse(int q)g=count(q); /表示的歐拉函數(shù) for(i=1;ig;i+) mod*=e; d=(i

5、nt)(mod%q); return d; 算法中的即為的逆元。（三）舉例說(shuō)明假設(shè)用戶a選取和。根據(jù)公鑰的生成方法，可以求出，歐拉函數(shù)。若選取，滿足，且，根據(jù)擴(kuò)展的歐基里德算法可以求出的逆元。則公鑰為，以為公開(kāi)私鑰。通過(guò)向ca機(jī)構(gòu)，可以申請(qǐng)得到a的公鑰，也就是說(shuō)可以得到，。首先通過(guò)求解其歐拉函數(shù)的值。根據(jù)上面的算法，通過(guò)count（）和gcd（）可以計(jì)算出它的值為96。令，求模的逆元，再根據(jù)算法inverse（）可以求出逆元的大小為77，和用戶的私鑰相一致。在求解逆元的過(guò)程中，如果得到的值小于0，可以通過(guò)表達(dá)式將其轉(zhuǎn)換為一個(gè)正整數(shù)。三、結(jié)論在公鑰加密體制中，由于是兩個(gè)保密的大素?cái)?shù)和的乘積，而的歐拉函數(shù)是通過(guò)計(jì)算得到的。而通過(guò)歐拉函數(shù)本身的定義可得到計(jì)算歐拉函數(shù)的方法，可以借助計(jì)算機(jī)程序，利用擴(kuò)展的歐拉函數(shù)來(lái)破解用戶的私鑰。參 考 文 獻(xiàn)1楊波.現(xiàn)代密碼學(xué)m，北京：清華大學(xué)出版社，2007：1052蔡樂(lè)才.應(yīng)用密碼學(xué)m，中國(guó)電力出版社，2005：353niels ferguson, bruce schneier編，張振峰，徐靜,等譯