現(xiàn)在人們普遍將互聯(lián)網(wǎng)作為信息傳送的平臺，但在互聯(lián)網(wǎng)上進行信息的傳送存在許多不安全因素.為了確保重要信息在網(wǎng)上安全傳輸，目前采用的措施主要有3種：安全信道、加密技術(shù)和信息隱藏，其中加密技術(shù)是應(yīng)用最廣的一種，雖然目前理論上沒有不能被破解的加密算法，但只要加密后的數(shù)據(jù)在要求的時間內(nèi)不被破解，數(shù)據(jù)就是安全的。目前的密碼體制分為對稱密碼體制和非對稱密碼體制2種，非對稱密碼體制的密鑰的管理和傳送很方便，在通過網(wǎng)絡(luò)傳輸信息時，公鑰密碼算法體現(xiàn)出了單密鑰加密算法不可替代的優(yōu)越性，其中公鑰密碼體制的算法中最著名的代表是RSA算法，RSA算法的安全性問題尚未得到理論上的證明，筆者就其安全性進行了一定的分析.

1 RSA加密算法的描述

RSA算法是一個基于初等數(shù)論定理的公鑰密碼體制加密算法，它的實現(xiàn)過程為：選取2個大素數(shù)p與q，然后算出n=pq，φ(n)=n－p－q＋1，再選取一個正整數(shù)e，使之滿足(e,φ(n))=1，1<E<Φ(N)；再求出正整數(shù)D，使之滿足1<D，而密鑰是.明文消息m滿足0≤m

例 取2個質(zhì)數(shù)p=11，q=13，p和q的乘積為n=p×q=143，算出φ(n)=n-p-q+1=120；再選取一個與φ(n)互質(zhì)的數(shù)，例如e=7，則公開密鑰=n，e=143，7.

對于這個e值，用歐幾里德擴展算法可以算出其逆：d=103.因為e×d=7×103=721，滿足e×d mod z =1；即721 mod 120=1成立.則秘密密鑰=n，d=143，103，

設(shè)發(fā)送方需要發(fā)送機密信息（明文）m=85，發(fā)送方已經(jīng)從公開媒體得到了接收方的公開密鑰n，e=143，7，于是發(fā)送方算出加密后的密文c= me mod n=857 mod 143=123并發(fā)送給接收方.

接收方在收到密文c=123后，利用只有他自己知道的秘密密鑰計算m= cd mod n =123103 mod 143=85，所以，接收方可以得到發(fā)送方發(fā)給他的真正信息m=85，實現(xiàn)了解密.

用RSA體制加密時，先將明文數(shù)字化再進行加密，在實際應(yīng)用中m值的長度一般要遠大于n的長度，因此實際加密消息m時，首先將它分成比n小的數(shù)據(jù)分組（采用二進制數(shù)，選取小于n的2的最大次冪），再每組單獨加密和解密.比如說，選用的p和q為100位的素數(shù)，那么n將有200位，每個數(shù)據(jù)分組應(yīng)小于200位長，但為保證安全性，每個數(shù)據(jù)的長度應(yīng)盡量接近n的長度.

2 RSA算法的加密強度與因子分解強度

目前密碼的破譯主要有2種方法.方法之一是密鑰的窮盡搜索，其破譯方法是嘗試所有可能的密鑰組合.雖然大多數(shù)的密鑰嘗試都是失敗的，但最終有一個密鑰讓破譯者得到原文，這個過程稱為密鑰的窮盡搜索.方法之二是密碼分析.由于RSA算法在加密和解密過程都是用指數(shù)計算，其計算工作量巨大，用窮盡搜索法進行破譯是根本不可能的.因此要對RSA算法加密后的信息進行破譯只能采用密碼分析法，用密碼分析法攻擊RSA密碼系統(tǒng)，途徑之一是直接計算“n的e次方根”，但目前還沒有解決這一問題的算法，這個問題是現(xiàn)實不可計算的問題；途徑之二[4]是想辦法計算出d，欲得到d，可考慮從以下3個方面入手.

(1) 將數(shù)n分解因子

密碼分析員一旦分解出n的因子p和q，就可以先后求出φ(n)和d，從而攻破RSA公開鑰密碼系統(tǒng)．由此得出如下結(jié)論：破譯RSA密碼不可能比分解因子的問題更困難.

(2) 不分解n的因子計算φ(n)

顯然，如果密碼分析員能夠求出φ(n)，由于e是公開的，就可以通過de≡1 (modφ(n))算出d，從而攻破RSA密碼系統(tǒng).但是，一旦密碼分析員知道了φ(n)，他就可以很容易地分解出n的因子.究其原因為

φ(n)＝n-（p+q）+l,

所以，由n及φ(n)可以計算出(p+q)．有了(p+q)，就可以通過p-q=(p+q)2-4n求出（p-q），因而最終解出p和q.計算φ(n)的方法并不比分解n的因子容易，換言之，通過計算φ(n)破譯RSA密碼的方法不會比通過分解n的因子破譯RSA密碼的方法更容易.

(3) 不分解n的因子或計算φ(n)確定d

如果能夠知道d，分解n的因子問題也同樣會變得容易起來.因為φ(n)＝(ed-1)×k，其中k為任意整數(shù)，已知d (e 是公開的)時,可求出φ(n),根據(jù)φ(n)＝n-（p+q）+l，由于n是已知的(公開的)，在求出φ(n)時可求出p+q，設(shè)求出的p+q=r，又由于n=p×q，從而可得p×p-p×r+n=0，這是一個一元二次方程，自然可非常簡單求出p,同理可求出q，分解n完成．

G. L. Miller在1975年指出，利用φ(n)的任何倍數(shù)都可以容易地分解出n的因子.因此，用Miller算法就可以由（ed-1）分解出n的因子，也就是說計算d并不比分解n的因子更容易.密碼分析員還可能希望找到某個與d等價的d′，從而攻破RSA密碼.但是，所有這樣的d′只相差（p-1）和（q-1）的最小公倍數(shù)的整數(shù)倍，因此，找到一個這樣的d′就可以使分解n的因子問題變得容易起來，也即找到這樣的d′并不比分解n的因子更容易.

綜上所述，破譯RSA密碼系統(tǒng)和分解因子問題同樣困難，盡管目前還不能完全證實它，即在目前狀況下，如果參數(shù)p,q和e選取恰當?shù)脑挘琑SA的加密強度，就取決于的抗因子分解強度.

3. 大數(shù)因子分解的難度

著名數(shù)學家費馬（1601—1665）和勒讓德（(1752—1833)都研究過分解因子的算法，現(xiàn)代某些更好的算法是勒讓德方法的擴展．其中，R. Schroeppel算法是好算法中的一類，用此法分解因子仍然需要大約eln nlnln n次運算，其中l(wèi)n表示自然對數(shù)，可見分解n 所需的運算次數(shù)與密鑰的長度有關(guān)，隨著密鑰長度的增加，分解所需的時間會成指數(shù)倍增加.對于不同長度的十進制數(shù)n，Schroeppel算法分解n的因子時所需的運算次數(shù)如表1所示.

若用1臺1 s能進行1億次因子分解的高速計算機來計算，分解十進制長度為200位的n，其所需時間為3 800 000年.由此可見，對于RSA系統(tǒng)，如果用一個長度為200位（十進制）的n，認為它是比較安全的，如果n的長度更長，因子分解越困難，一般來說，每增加10位二進制數(shù)，分解的時間就要加長1倍.密碼就越難以破譯，加密強度就越高.

不過隨著計算機運算速度的提高和并行計算的發(fā)展，破解的速度也會同步提高，這時可能要求使用更長的密鑰.

RSA的安全性依賴于大數(shù)的因子分解，這樣攻擊RSA系統(tǒng)的難度就是大整數(shù)因子分解的難度，一般認為這是一個NPC問題，盡管尚未在理論上證明分解因子的問題一定困難，但千百年來經(jīng)過眾多學者的研究，迄今沒有找到一種有效算法，絕大多數(shù)數(shù)論學家傾向于認為不存在大整數(shù)因子分解的多項式算法，因此目前這一破譯只能依賴于現(xiàn)代的計算機技術(shù)，用程序進行嘗試分解，從而對大數(shù)的因子分解.不過隨著計算機運算速度的提高和并行計算的發(fā)展，加上因子分解方法的改進，低位數(shù)的密鑰的破解已成為可能.因子分解需的時間隨密鑰長度的增加而成指數(shù)指增加，只要n的長度達到一定要求，并且參數(shù)p,q和e選取恰當?shù)脑?，RSA系統(tǒng)是相當安全的.

admin

收藏 海報分享