Description: 前言 本文全面的介紹了RSA算法的概念、原理、證明和實現。我在寫作本文之前在網上查閱過相關資料，可這些資料不是含糊其辭就是滿篇謬誤。所以我力求用通俗易懂的文字將算法深入剖析，用最嚴謹的步驟進行論相關的各項算法，以降低文章的閱讀難度。讀者只要學過初中代數就可以理解全文，我衷心希望更多讀者能認識到加密算法其實并不難。文中的算法均為偽代碼，由于偽代碼沒有辦法進行測試，再加上我個人數學功底比較薄弱，所以錯漏之處在所難免，還請各位老師給予指教。質疑或指正請發送電子郵件到fireseed1949@hotmail.com，我會認真閱讀并回復的！感謝北航數學系（畢業）李楨老師、西工大計算機系（畢業）張小寧老師在數學上對我的指點。另注：文中mod就是求余的符號，X mod Y表示X除以Y所得的余數。 ·概述 RSA算法是世界上第一個既能用于數據加密也能用于數字簽名的非對稱性加密算法。它易于理解和操作，所以流行甚廣。算法的名字以發明者的名字命名，他們是：Ron Rivest，Adi Shamir 和Leonard Adleman。雖然RSA的安全性一直未能得到理論上的證實，但它經歷了各種攻擊，至今未被完全攻破。為了讓讀者更容易的理解RSA加密，先大概講述一下信息加密技術的相關概念和原理。我們對于在數字媒體上進行交換的數據進行加密的方法稱為信息交換加密技術，它分為兩類，即對稱加密和非對稱加密。在對稱加密技術中，對信息的加密和解密都使用相同的鑰，也就是說一把鑰匙開一把鎖。這種加密方法可簡化加密處理過程，信息交換雙方都不必彼此研究和交換專用的加密算法。如果在交換階段私有密鑰未曾泄露，那么機密性和報文完整性就可以得以保證。對稱加密技術也存在一些不足，如果交換一方有N個交換對象，那么他就要維護N個私有密鑰，對稱加密存在的另一個問題是雙方共享一把私有密鑰，交換雙方的任何信息都是通過這把密鑰加密后傳送給對方的。如三重DES是DES（數據加密標準）的一種變形，這種方法使用兩個獨立的56為密鑰對信息進行3次加密，從而使有效密鑰長度達到112位。在非對稱加密（或稱公開密鑰加密）體系中，密鑰被分解為一對，即公開密鑰（公鑰）和私有密鑰（私鑰）。這對密鑰中任何一把都可以作為公開密鑰，通過非保密方式向他人公開，而另一把作為私有密鑰，加以妥善保存。公開密鑰用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開密鑰可廣泛公布，但它只對應于生成密鑰的交換方。非對稱加密方式可以使通信雙方無須事先交換密鑰就可以建立安全通信，廣泛應用于身份認證、數字簽名等信息交換領域。非對稱加密體系一般是建立在某些已知的數學難題之上，是計算機復雜性理論發展的必然結果。最具有代表性是RSA公鑰密碼體制。在RSA算法中，我們先要獲得兩個不同的質數P和Q做為算法因子，再找出一個正整數E，使得E與 ( P - 1 ) * ( Q - 1 ) 的值互質，這個E就是私鑰。找到一個整數D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立，D就是公鑰1。設N為P和Q的乘積，N則為公鑰2。加密時先將明文轉換為一個或一組小于N的整數I，并計算ID mod N的值M，M就密文。解密時將密文ME mod N，也就是M的E次方再除以N所得的余數就是明文。因為私鑰E與( P - 1 ) * ( Q - 1 )互質，而公鑰D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必須得出( P - 1 ) * ( Q - 1 )，因而必須先對N進行因數分解。如果N很大那么因數分解就會非常困難，所以要提高加密強度P和Q的數值大小起著決定性的因素。一般來講當P和Q都大于2128時，按照目前的機算機處理速度破解基本已經不大可能了。 ·證明下面將會開始討論RSA算法的原理及其算法證明。如果您只關心RSA算法的實現，則可以略過這一步。我把每一個有用的定理都用粗標標記了，對于數學不很在行的朋友可以只了解一下相關定理的說明而不需要驗證求證過程了。一、 費馬小定理[1]的轉化費馬小定理：有N為任意正整數，P為素數，且N不能被P整除，則有： NP mod P = N 費馬小定理可變形為： NP - N mod P = 0 ( N ( NP - 1 - 1 ) ) mod P = 0 因為 ( N ( NP - 1 - 1 ) ) mod N = 0 所以N和P的公倍數為： N ( NP - 1 - 1 ) （1）又因為N與P互質，而互質數的最小公倍數為它們的乘積，所以一定存在正整數M使得：N ( NP - 1 - 1 ) = MNP成立。并化簡為： NP - 1 - 1 = MP ( NP - 1 - 1 ) mod P = 0 可以變形為： NP - 1 mod P = 1 （2）（2）就是費馬小定理的轉化定理，為方便敘述，下文簡稱為定理一。小提示，可能很多人認為費馬小定理本來就是（2），實際上不是這樣，因為費馬小定理的轉化非常容易，而轉化定理又是一個無論在數學上還是計算機程序上都很常用的公式，所以人們就普遍認為（2）就是費馬小定理了。二、 積模分解公式有X、Y和Z三個正整數，且X * Y大于Z，則有： ( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z 證明如下當X和Y都比Z大時，可以將X和Y表示為： X = ZI + A （1） Y = ZJ + B （2）將（1）和（2）代入( X * Y ) mod Z得： ( ( ZI + A )( ZJ + B ) ) mod Z ( Z( ZIJ + IA + IB ) + AB ) mod Z （3）因為Z( ZIJ + IA + IB )是Z的整數倍，所以（3）式可化簡為： AB mod Z 因為A和B實際上是X和Y分別除以Z的余數，所以有： ( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。當X比Z大而Y比Z小時 X = ZI + A 代入( X * Y ) mod Z得： ( ZIY + AY ) mod Z AY mod Z 因為A = X mod Z， 又因為Y mod Z = Y，所以有： ( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。同理，當X比Z小而Y比Z大時，上式也成立。當X和Y都比Z小時，X = X mod Z，Y = Y mod Z所以有： ( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。積模分解公式成立。三、 定理二有P和Q兩個互質數，如果有X mod P = 0，X mod Q = 0，則有：X mod PQ = 0 證明：因為P和Q互質，所以它們的公倍數為KPQ（K為整數），最小公倍數為PQ。又因為X為P和Q的公倍數，所以X / PQ = K，所以X mod PQ = 0。四、 定理三有P和Q兩個互質數，設有整數X和Y滿足Y mod P = X，Y mod Q = X，則有：Y mod PQ = X 證明： X = Y mod P 可以表示為： Y = X + kP Y - X = kP 即Y - X可以被P整除，同理Y - X可以被Q整除。又因為P、Q互質，根據定理二可得： ( Y - X ) mod PQ = 0 即 Y mod PQ = X 五、 定理三的逆定理有P和Q兩個互質數，設有整數X和Y滿足Y mod PQ = X ，則有：Y mod P = X，Y mod Q = X 證明： Y mod PQ = X 可以表示為： ( Y – X ) mod PQ = 0 顯然 ( Y – X ) mod P = 0且 ( Y – X ) mod Q = 0 所以原命題成立。六、 RSA定理若P和Q是兩個相異質數，另有正整數R和M，其中M的值與( P - 1 )( Q - 1 )的值互質，并使得( RM ) mod ( P - 1 )( Q - 1 ) = 1。有正整數A，且A PQ，且A不是P的倍數也不是Q的倍數時，（2）可變形為： B = ( AAK ( P - 1 )( Q - 1 ) ) mod PQ 根據積模分解公式可變形為： B = ( ( A mod PQ )( AK ( P - 1 )( Q - 1 ) mod PQ ) ) mod PQ （3）根據定理三的逆定理： AK ( P - 1 )( Q - 1 ) mod PQ = ( AK ( P - 1 ) ) ( Q - 1 ) mod Q 根據費馬小定理可得： ( AK ( P - 1 ) ) ( Q - 1 ) mod Q = 1，則 AK ( P - 1 )( Q - 1 ) mod PQ = 1 故( 3 )可轉化為： B = ( A mod PQ ) mod PQ 因為A PQ，且A不是P的倍數而是Q的倍數時，A可表示為A = NQ，N為一小于A的整數。那么（2）式可變形為： B = ( NQ )K ( P - 1 )( Q - 1 ) + 1 mod PQ B = ( NK ( P - 1 )( Q - 1 ) + 1 )( QK ( P - 1 )( Q - 1 ) + 1 ) mod PQ 把Q作為公因子提出來，得： B = ( ( NNK ( P - 1 )( Q - 1 ) ) ( QK ( P - 1 )( Q - 1 ) mod P ) ) Q 用積模分解公式進行分解，得： B = ( ( NNK ( P - 1 )( Q - 1 ) mod P )( QK ( P - 1 )( Q - 1 ) mod P ) mod P ) Q 跟據定理四，NK ( P - 1 )( Q - 1 )和QK ( P - 1 )( Q - 1 )的值都為1，所以有： B = ( ( ( N mod P ) mod P ) mod P ) Q B = NQ mod PQ mod PQ mod PQ B = A mod PQ mod PQ mod PQ 因為A 1 E := E / 2，余數存入M IF M = 1 K := R * K END IF R := R * R NEXT R := R * K 再回到我們剛才討論的冪模運算。事實上在（1）式中，我們需要求出的就是( N mod D )R的值，那么只要令上面偽代碼中參量N的值為N mod D，并對結果R求R mod D就可以了，下面是基于上面求乘方算法的冪模運算的偽代碼。算法二：計算N的E次方再取D的模，令R為計算結果。 R := N mod D R := R ^ E ;調用算法一 R := R % D 如果再利用上文過程中提到積模分解公式對算法做進一步優化，直接把取余的運算代入到乘方中，就成為了著名的蒙格馬利快速冪模運算法，偽代碼如下。算法三：蒙格馬利法計算N的E次方再取D的模，令R為計算結果。 R := 1 A := N B := E WHILE B != 0 IF B & 1 ;判斷是否為奇數 B := B - 1 R := R * A X := X % D ELSE B := B / 2 A := A * A A := A % D END IF NEXT 蒙格馬利快速冪模運算，是目前世界上效率最高的冪模運算，很多硬件芯片在處理類似算法時都采用的這種方法。 ·尋找大素數為了有效防止破解，必要須找到兩個很大的素數作為算法因子。而尋找大素數，是數學家們一個永恒的話題。素數的定義是只能被自己和1整除的自然數，按照常規的理解，使用計算機對一個很大的數進行素數測試時，需要遍歷所有小于它且大于1的自然數，并逐個判斷是否能被該數整除。這個過程對于非常大的素數而言是非常緩慢的。但是根據費馬小定理，我們可以設計一種算法來快速測試素數。當A和Q互質時，有：AQ - 1 mod Q = 1，那么，我們可以通過判斷AQ - 1 mod Q的值是否等于1對Q進行素數測試。如果取了很多個A，Q仍未測試失敗，那么則認為Q是素數。當然，測試次數越多越準確，但一般來講50次就足夠了。另外，預先用常歸算法構造一個包括500個素數的數組，先對Q進行整除測試，將會大大提高通過率，方法如下：算法四：費馬定理測試可能素數P C := 500 ;素數表大小 S[ 0 TO C ] ;素數表 B := P - 1 T := 50 ;表示進行測試的次數 A := 0 FOR I := 0 TO C ;進行素數表初步測試 IF P mod S[I] = 0 RETURN FAILE END IF IF P 1 RETURN FAILE END IF NEXT I RETURN PASS 這個算法看起來很完美，但實際上從一開始它就犯了一個很大的錯，那就是對于任意與Q互質的A都有AQ - 1 mod Q = 1，這是素數的性質，是素數成立的一個必要條件，但不是充分條件！讓我們來看一下29341這個數，它等于13 * 37 * 61，但任何與它互質的A都有A29341 - 1 mod 29341 = 1成立。這種數字還有不少，數學上把它們稱為卡爾麥克數，現在數學家們已經找到所有1016以內的卡爾麥克數，最大的一個是9585921133193329。我們必須尋找更為有效的測試方法。數學家們通過對費馬小定理的研究，并加以擴展，總結出了多種快速有效的素數測試方法，目前最快的算法是拉賓米勒測試算法，其過程如下：首先確定N是否為奇數，不是奇數的判斷失敗。選擇T個隨機整數A，并且有 0 50那么測試失誤的機率就會小于10-30，這對于目前的計算機硬件來說已經足夠證明N就是素數了。下面是偽代碼。算法五：拉賓米勒測試法測試P是否為素數。 C := 500 ;素數表大小 S[ 0 TO C ] ;素數表 B := P - 1 T := 50 ;表示進行測試的次數 A := 0 ;用來測試通過的隨機整數 FOR I := 0 TO C ;進行素數表初步測試 IF P mod S[I] = 0 RETURN FAILE END IF IF P > 1 R := R + 1 ;計算R NEXT X := 0 Y := 0 FOR I := 0 TO T A := S[ RAND() mod C ] ;先進行費馬測試 IF A ^ ( P - 1 ) mod P <> 1 RETURN FAILE END IF X := A Y := A ^ ( M * R * 2 ) WHILE X <= Y IF X ^ M mod P = 1 BREAK END IF X := X ^ 2 NEXT IF X > Y RETURN FAILE END IF NEXT RETURN PASS ·二元一次不定方程在算法概述的章節里我們曾經討論過公鑰1的求法：找一個數D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。為了求D，我們先對這個方程變形。實際上這個方程可以看做AX mod B = 1，即： AX = BY + 1，Y為一整數。 AX - BY = 1 這就是一個二元一次不定方程，有已知數A、B，未知數X、Y。我們現在需要求的是X，那么就是求這個方程對于X的最小整數解。由于方程有兩個未知數，所以必須化簡方程，使得一個未知數的系數為0時才能得解。設B > A時有： AX - BY = 1 那么可以認為B = AN + M，則有： AX - ( AN + M )Y = 1 AX - ANY - MY = 1 A( X - NY ) - MY = 1 實際上M就是B mod A的值，設X’ = X - NY，B’ = B mod A則有AX’ - B’Y = 1，且A > M成立。接著可以用同樣的方法來化簡A，最終必能將一個系數化為0。此時求出另一個未知數的解，再按逆序代入上一步的方程，求出另一個未知數的解，再代入上一步的方程，一直遞推的第一個方程，最終即可獲得X和Y的最小整數解。因為每一步遞推的方程的余數相同，所以我們稱這些方程為“一次同余式”。這個算法被稱為歐幾里德擴展算法，而歐幾里德算法其實就是求公因式的輾轉相除法，大多數朋友在中學時就學過了，但是我們下面會用到，所以我這里簡單的用偽代碼來描述一下歐幾里德算法。算法六：求A和B兩相異自然數的最大公因數，另R為結果。 IF A P。并且有正整數D使ND mod P = 1成立，求D。 IF N和P的最大公因數 <> 1 ;調用算法六 RETURN FAILE END IF LT := 1 ;左上 RT := N mod P ;右上 LD := 0 ;左下 RD := P ;右下 X := 0 ;中間變量 WHILE RT <> 1 X := RD / RT RD := RD % RT IF RD = 0 RD := RT LD := ( X - 1 ) * LT + LD ELSE LD := X * LT + 1 END IF X := RT / RD RT := RT % RD IF RT = 0 RT := RD LT := ( X - 1 ) * LD + LT ELSE LT := X * LD + 1 END IF NEXT D := LT ·結語到現在，RSA算法中所涉及到的所有算法我們都已經討論過了。實際還有一個運算，就是私鑰的獲得辦法：計算得到與( P - 1 ) * ( Q - 1 )的值互質的整數E。我情愿不把它稱之為算法，因為只需要一個循環和一個判斷就可以完成，所以這里也就沒有必要對它多加論述了。 ·附錄費馬小定理的證明：引理1：設M，A的最大公約數( M，A ) = 1，且M整除AB，即M mod AB = 0，則M mod B = 0。引理2：設P是素數， 表示組合數，即從P個數中選出J個數的組合種數，且1 ≤ J ≤ P - 1，則P mod 。證明：已知組合數 = P! / ( J! * ( P - J )! )是整數，即J! * ( P - J )! mod P! = 0。由于P是素數，所以對任意1 ≤ I ≤ P-1有( P，I ) = 1。因此由引理1有( P，j! * ( P - J )! ) = 1，1 ≤ J ≤ P - 1。進而由引理1推出：當1 ≤ J ≤ P - 1時J! * ( P - J )! mod ( P - 1 )! = 0，得證。

posted on 2008-05-30 01:47 幽幽 閱讀(1417) 評論(0)  編輯 收藏 引用 所屬分類: 算法