|
RSA密碼體制RSA cryptosystem
西安電子科技大學 曾華陽 2011/1/13
摘要： 隨著電子政務的快速應用，信息交換的安全越來越引起人們的關注。對網(wǎng)絡的新的威脅與攻擊不斷出現(xiàn)，尋找一個可靠安全的加密算法迫在眉睫。RSA就是目前主流的公鑰加密算法。本文著重分析RSA基本算法以及安全性問題，最后也提出了自己的一些想法與觀點。
Abstract：With the rapid application of e-government, exchange of information security has drawn increasing attention. The network’s new emerging threats and attacks, so look for a reliable and secure encryption algorithms imminent..RSA is the current mainstream public key encryption algorithm. This article focuses on the basic RSA algorithm and security issues, and finally also made some of their own thoughts and ideas.
關鍵詞: RSA算法 安全性 大整數(shù)分解 攻擊
引言：
眾所周知，在密碼系統(tǒng)中，分發(fā)密鑰是其中最弱的一個環(huán)節(jié)，如果入侵者能夠偷取到密鑰，則整個系統(tǒng)就毫無價值可言。在傳統(tǒng)的對稱密碼中，加密密鑰同解密密鑰是相同的，這就使得密鑰的保護變得比較復雜。而公鑰密碼的出現(xiàn)正好彌補了這個不足。在這個系統(tǒng)中，加密密鑰和解密密鑰并不相同。RSA算法可謂是經(jīng)典中的經(jīng)典，也是我比較推崇的一種算法。
1 RSA算法簡要分析
RSA公鑰密碼算法是基于大素數(shù)分解的困難性，下面簡要說明加密解密算法。
[1] 選擇兩個大的素數(shù)p和q（p、q之差要大，這點將在下文詳細說明）。
[2] 計算出n=p*q, z=(p-1)(q-1)。
[3] 選擇一個公鑰e，使e跟z互質。
[4] 選擇一個私鑰d，使得d*e=1 mod z 。
[5] 加密時從明文x計算密文y算法如下： 。
[6] 解密時，從密文y計算明文x的算法如下：
從算法中可以知道每一個RSA用戶有一個公鑰和一個私鑰公鑰（e,n）公布出來，私鑰自己保留。我們可以這樣假設每個用戶把自己的公鑰公布到一個統(tǒng)一的地方就像一個電話簿一樣。如果想找到某個用戶的公鑰給他發(fā)密文時，只需要到電話簿里找到就行。當然這就需要一個專門的密鑰分發(fā)中心，以防止不良者偽造。
2 安全性分析
從上面的介紹可以看出RSA算法本身很簡單，關鍵是選擇正確的密鑰。問題是公鑰e和n和私鑰d都是計算出來的，既然發(fā)布者可以計算出，那么攻擊者也可以�？墒遣挥脫模@才是RSA的強大之處，入侵者在得到公鑰e ，n的情況下想計算出d那是相當困難的。攻擊者只要知道公鑰e和n好像就可以用試錯法找到私鑰d。攻擊者要如何做呢？首先要用n分解出p和q。如果p和q很小，很容易就可以試解出來。但實際中沒人會那么傻把p和q設那么小。因此要從n分解出p和q是相當復雜和耗時的。數(shù)學分析表明，n為100位數(shù)時，要七十多年才能求出p和q。而現(xiàn)在512bit（154位）、664bit(200位)已有實用產(chǎn)品。也有人想用1024bit的模。若以每秒可進行100萬步的計算資源分解664bit大整數(shù)，這就需要將近1000年。我想等解出密碼的那一天，攻擊者所付出的代價肯定要比密碼消息本身大得多。而且這么多年過去了，密碼破譯出來之后又有什么價值呢，誰還在意呢！這正是RSA的強大之處�？墒请S著科技的發(fā)展以及人們不斷尋找更有效的攻擊方法，或許將來對于分解大素數(shù)也不會是個特別復雜和耗時的工作。下面給出一些常用的攻擊方法。
[1] 迭代攻擊法：Simmons和Norris【1977】曾提出迭代或者循環(huán)攻擊法。例如，給定一RSA的參數(shù)為（n,e,y）=(35,17,3)，可由： ，再由 。從而得到明文 。一般對明文x加密多次，直到再現(xiàn)x為止。Rivest【1978】證明當 和 中含有大素數(shù)因子，且n足夠大時，這種攻擊成功的概率為零。
[2] 選擇明文攻擊：一般攻擊者是將某一信息做一下偽裝，讓擁有私鑰的實體簽署，然后經(jīng)過計算就可以得到他想要的信息。從算法上無法解決這個問題。防護的措施有：一是可以采用更好的公鑰協(xié)議。另一條就是絕不對陌生人送來的隨機文檔簽名。
3 RSA（未完，下一頁）
|