RSA加密算法初探

1、RSA加密算法初探  ·前言 本文全面的介紹了RSA算法的概念、原理、證明和實現(xiàn)。我在寫作本文之前在網上查閱過相關資料，可這些資料不是含糊其辭就是滿篇謬誤。所以我力求用通俗易懂的文字將算法深入剖析，用最嚴謹?shù)牟襟E進行論相關的各項算法，以降低文章的閱讀難度。讀者只要學過初中代數(shù)就可以理解全文，我衷心希望更多讀者能認識到加密算法其實并不難。 文中的算法均為偽代碼，由于偽代碼沒有辦法進行測試，再加上我個人數(shù)學功底比較薄弱，所以錯漏之處在所難免，還請各位老師給予指教。質疑或指正請發(fā)送電子郵件到，我會認真閱讀并回復的！ 感謝北航數(shù)學系（畢業(yè)）李楨老師、西工大計算機系（畢業(yè)）張小寧老師

2、在數(shù)學上對我的指點。 另注：文中mod就是求余的符號，X mod Y表示X除以Y所得的余數(shù)。  ·概述 RSA算法是世界上第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的非對稱性加密算法。它易于理解和操作，所以流行甚廣。算法的名字以發(fā)明者的名字命名，他們是：Ron Rivest，Adi Shamir 和Leonard Adleman。雖然RSA的安全性一直未能得到理論上的證實，但它經歷了各種攻擊，至今未被完全攻破。為了讓讀者更容易的理解RSA加密，先大概講述一下信息加密技術的相關概念和原理。 我們對于在數(shù)字媒體上進行交換的數(shù)據(jù)進行加密的方法稱為信息交換加密技術，它分為兩類，即對稱加

3、密和非對稱加密。 在對稱加密技術中，對信息的加密和解密都使用相同的鑰，也就是說一把鑰匙開一把鎖。這種加密方法可簡化加密處理過程，信息交換雙方都不必彼此研究和交換專用的加密算法。如果在交換階段私有密鑰未曾泄露，那么機密性和報文完整性就可以得以保證。對稱加密技術也存在一些不足，如果交換一方有N個交換對象，那么他就要維護N個私有密鑰，對稱加密存在的另一個問題是雙方共享一把私有密鑰，交換雙方的任何信息都是通過這把密鑰加密后傳送給對方的。如三重DES是DES（數(shù)據(jù)加密標準）的一種變形，這種方法使用兩個獨立的56為密鑰對信息進行3次加密，從而使有效密鑰長度達到112位。 在非對稱加密（或稱公開密鑰加密）體

4、系中，密鑰被分解為一對，即公開密鑰（公鑰）和私有密鑰（私鑰）。這對密鑰中任何一把都可以作為公開密鑰，通過非保密方式向他人公開，而另一把作為私有密鑰，加以妥善保存。公開密鑰用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開密鑰可廣泛公布，但它只對應于生成密鑰的交換方。非對稱加密方式可以使通信雙方無須事先交換密鑰就可以建立安全通信，廣泛應用于身份認證、數(shù)字簽名等信息交換領域。非對稱加密體系一般是建立在某些已知的數(shù)學難題之上，是計算機復雜性理論發(fā)展的必然結果。最具有代表性是RSA公鑰密碼體制。 在RSA算法中，我們先要獲得兩個不同的質數(shù)P和Q做為算法因子，再找出一個正整數(shù)E，使得E

5、與 ( P - 1 ) * ( Q - 1 ) 的值互質，這個E就是私鑰。找到一個整數(shù)D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立1，D就是公鑰1。設N為P和Q的乘積，N則為公鑰2。加密時先將文轉換為一個或一組小于N的整數(shù)I，并計算ID mod N的值M，M就密文。解密時將密文ME mod N，也就是M的E次方再除以N所得的余數(shù)就是明文。 因為私鑰E與( P - 1 ) * ( Q - 1 )互質，而公鑰D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必須

6、得出( P - 1 ) * ( Q - 1 )，因而必須先對N進行因數(shù)分解。如果N很大那么因數(shù)分解就會非常困難，所以要提高加密強度P和Q的數(shù)值大小起著決定性的因素。一般來講當P和Q都大于2128時，按照目前的機算機處理速度破解基本已經不大可能了。 ·證明 下面將會開始討論RSA算法的原理及其算法證明。如果您只關心RSA算法的實現(xiàn)，則可以略過這一步。我把每一個有用的定理都用粗標標記了，對于數(shù)學不很在行的朋友可以只了解一下相關定理的說明而不需要驗證求證過程了。  一、 費馬小定理2的轉化 費馬小定理：有N為任意正整數(shù)，P為素數(shù)，且N不能被P整除，則有： NP mod P = N

7、 費馬小定理可變形為： NP - N mod P = 0 ( N ( NP - 1 - 1 ) ) mod P = 0 因為 ( N ( NP - 1 - 1 ) ) mod N = 0 所以N和P的公倍數(shù)為： N ( NP - 1 - 1 )（1） 又因為N與P互質，而互質數(shù)的最小公倍數(shù)為它們的乘積，所以一定存在正整數(shù)M使得：N ( NP - 1 - 1 ) = MNP成立。并化簡為： NP - 1 - 1 = MP ( NP - 1 - 1 ) mod P = 0 可以變形為： NP - 1 mod P = 1（2） （2）就是費馬小定理的轉化定理，為方便敘述，下文簡稱為定理一。小提示，可

8、能很多人認為費馬小定理本來就是（2），實際上不是這樣，因為費馬小定理的轉化非常容易，而轉化定理又是一個無論在數(shù)學上還是計算機程序上都很常用的公式，所以人們就普遍認為（2）就是費馬小定理了。  二、 積模分解公式 有X、Y和Z三個正整數(shù)，且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 ) ) mo

9、d Z ( Z( ZIJ + IA + IB ) + AB ) mod Z（3） 因為Z( ZIJ + IA + IB )是Z的整數(shù)倍，所以（3）式可化簡為： AB mod Z 因為A和B實際上是X和Y分別除以Z的余數(shù)，所以有： ( 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 = ( (

10、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兩個互質數(shù)，如果有X mod P = 0，X mod Q = 0，則有：X mod PQ = 0 證明： 因為P和Q互質，所以它們的公倍數(shù)為KPQ（K為整數(shù)），最小公倍數(shù)為PQ。又因為X為P和Q的公倍數(shù)，所以X / PQ = K，所以X mo

11、d PQ = 0。  四、 定理三 有P和Q兩個互質數(shù)，設有整數(shù)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互質，根據(jù)定理二可得： ( Y - X ) mod PQ = 0 即 Y mod PQ = X  五、 RSA定理 若P和Q是兩個相異質數(shù)，另有正整數(shù)R和M，其中M的值與( P - 1 )( Q - 1 )的值互質，并使得( RM ) mod ( P - 1 )( Q

12、- 1 ) = 1。有正整數(shù)A，且A < PQ，設C = AR mod PQ，B = CM mod PQ則有：A = B 證明： 將C = AR mod PQ代入B = CM mod PQ得： B = ( ( AR mod PQ )M ) mod PQ 根據(jù)積模分解公式，可變形為： B = ( AR )M mod PQ B = ARM mod PQ（1） 因為有( RM ) mod ( P - 1 )( Q - 1 ) = 1，所以有： RM = K ( P - 1 )( Q - 1 ) + 1，K為正整數(shù)。 代入（1）得： B = AK ( P - 1 )( Q - 1 ) + 1 m

13、od PQ（2） 如果ARM < PQ時，明顯有B = A。 如果ARM > PQ，且A不是P的倍數(shù)也不是Q的倍數(shù)時，（2）可變形為： B = ( AAK ( P - 1 )( Q - 1 ) ) mod PQ 根據(jù)積模分解公式可變形為： B = ( ( A mod PQ )( AK ( P - 1 )( Q - 1 ) mod PQ ) ) mod PQ（3） 因為P為素數(shù)，所以A和P互質。根據(jù)定理一，有AP - 1 mod P = 1成立 兩邊同乘K ( Q - 1 )次方 ( AP - 1 mod P )K ( Q - 1 ) = 1 1關于任何正整數(shù)取余的值都為1，兩邊同m

14、od P得： ( AP - 1 mod P )K ( Q - 1 ) mod P = 1 根據(jù)積模分解公式的逆公式 AK( P - 1 )( Q - 1 ) mod P = 1 同理可得： AK( P - 1 )( Q - 1 ) mod Q = 1 根據(jù)定理三可得： AK( P - 1 )( Q - 1 ) mod PQ = 1 代入（3）得： B = ( A mod PQ ) mod PQ 因為A < PQ，所以B = A成立 在述證明過程中可以總結一點： 當P為素數(shù)且A和P互質時，那么當N為任意自然數(shù)時都有AN( P - 1 ) mod P = 1成立，這個定理下面還要用到，我們稱

15、之為定理四。 如果ARM > PQ，且A不是P的倍數(shù)而是Q的倍數(shù)時，（一些證明過程如上，此項情況的證明過程就不再贅述了）A可表示為A = NQ，N為一小于A的整數(shù)。 那么（2）式可變形為： B = NQK ( 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 用積模分解公式進行分解

16、，得： B = ( ( NNK ( P - 1 )( Q - 1 ) mod P )( QK ( Personal - 1 )( Q - 1 ) mod P ) mod P ) Q 跟據(jù)定理四，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 < PQ，所以B = A成立 同理，當A是P的倍數(shù)而不是Q的倍數(shù)時，B = A也成立。 因為A小于

17、PQ，而P和Q又都是質數(shù)，所以A既是P的倍數(shù)又是Q的倍數(shù)的情況不存在。 RSA定理成立。  ·大整數(shù)存儲運算 由于安全需要，目前主流的RSA加密算法都是基于2進制的512位或1024位的大整數(shù)，而目前的主流高級語言編譯器最多也只能支持到2進制64位整數(shù)，所以大整數(shù)的存儲和運算對于RSA算法的實現(xiàn)都是至關重要的。一個最容易理解的方法就是將大數(shù)用十進制表示，并將每一位（0 9）都做為一個單獨的數(shù)用數(shù)組進行管理。做加減乘除等運算時，人工的對其進行進、借位。然而計算機對于10進制數(shù)的處理并不在行，而且表示非2n進制的數(shù)會浪費很多空間，所以應該采用8進制、16進制、32進制、64進制

18、的表示法，使得每一位數(shù)字都能占據(jù)一個完整的內存空間。目前絕大多數(shù)PC機都是基于32位運算的，所以采用232進制表示大數(shù)將會很大提高計算機的處理效率?，F(xiàn)實中，就使用32位的整數(shù)數(shù)組進行存儲每一位數(shù)，另設一個布爾值表示正負。進行計算時常會遇到進位借位的情況，而且常常會超過232次方，幸好目前的編譯器都支持64位整數(shù)，可以滿足( 232 - 1 ) * ( 232 - 1 )以內的運算，所以使用64位整數(shù)作為運算中間量將會是很好的選擇。 大數(shù)除了加減乘除等基本運算以外，還有一些如賦值、比較、左右移位、或、與等，為了方便使用，我們可以利用面向對象的方法把大數(shù)進行封裝，并利用C+的特性進行運算符重載，使

19、它成為一個整體對象來進行操作。這樣我們就可像使用int一樣來使用它了。當然，大數(shù)類的實現(xiàn)并不是一篇文章就可以敘述完的，而且目前有一些很成熟并且開源的大數(shù)類庫，如GTK、HugeCalc等，因此我在這里就不對具體的算法做進一步闡釋了。  ·冪模運算 冪模運算是RSA算法中的關鍵，無論是素數(shù)測試，還是加密解密，都要用到冪模運算。簡單的講，冪模運算就是計算NR mod D的值。但是對于計算機來講，計算R很大的NR的值時將會非常浪費存儲空間，并使計算變的非常緩慢而難以實現(xiàn)。但是我們通過上文討論的積模分解公式，可以發(fā)現(xiàn)NR mod D是可以進行轉換的。 NR mod D = ( (

20、N mod D )R ) mod D（1） 這樣，在運算( ( N mod D )R ) mod D的過程中，在最壞的情況下，可能出現(xiàn)的最大的值就是( D - 1 )R，而D <= N，從而較大的減少了數(shù)據(jù)量，提高了運算速度。通過觀查發(fā)現(xiàn)，（1）式仍然可以進行分解以減少運算步驟。計算A13時，如果讓A直接進行連乘，需要12次運算。但是如果把A * A的值保存起來，我們就只需要進行B = A * A和B * B * B * B * B * B * A，一共七次運算，如果我們再把B * B的值保存起來，那我們就只需要進行B = A * A、C = B * B、D = C * C、 D * C

21、 * A，一共五次運算?？偨Y這個規(guī)律可以發(fā)現(xiàn)，運算過程中如果某次的冪數(shù)為奇數(shù)時，在乘方過后還需要乘以上次保留的積。跟據(jù)這個規(guī)律，我們把運算分為兩部分的乘積，下面是偽代碼。 算法一：計算N的E次方，令R為計算結果。 R := N; R用來存儲2n K := 1; K用于存儲另一部分的乘積 M := 0; M表示冪數(shù)每次除2的余數(shù) WHILE E > 1 E := E / 2，余數(shù)存入M IF M = 1 K := R * K END IF R := R * R NEXT R := R * K 再回到我們剛才討論的冪模運算。事實上在（1）式中，我們需要求出的就是( N mod D )R的值，

22、那么只要令上面?zhèn)未a中參量N的值為N mod D，并對結果R求R mod D就可以了，下面是基于上面求乘方算法的冪模運算的偽代碼。 算法二：計算N的E次方再取D的模，令R為計算結果。 R := N mod D R := R E;調用算法一 R := R % D 如果再利用上文過程中提到積模分解公式對算法做進一步優(yōu)化，直接把取余的運算代入到乘方中，就成為了著名的蒙格馬利快速冪模運算法，偽代碼如下。 算法三：蒙格馬利法計算N的E次方再取D的模，令R為計算結果。 R := 1 A := N B := E WHILE Z != 0 IF B & 1;判斷是否為奇數(shù) B := B - 1 R :

23、= R * A X := X % D ELSE B := B / 2 A := A * A A := A % D END IF NEXT 蒙格馬利快速冪模運算，是目前世界上效率最高的冪模運算，很多硬件芯片在處理類似算法時都采用的這種方法。  ·尋找大素數(shù) 為了有效防止破解，必要須找到兩個很大的素數(shù)作為算法因子。而尋找大素數(shù)，是數(shù)學家們一個永恒的話題。素數(shù)的定義是只能被自己和1整除的自然數(shù)，按照常規(guī)的理解，使用計算機對一個很大的數(shù)進行素數(shù)測試時，需要遍歷所有小于它且大于1的自然數(shù)，并逐個判斷是否能被該數(shù)整除。這個過程對于非常大的素數(shù)而言是非常緩慢的。但是根據(jù)費馬小定理，我們可

24、以設計一種算法來快速測試素數(shù)。當A和Q互質時，有：AQ - 1 mod Q = 1，那么，我們可以通過判斷AQ - 1 mod Q的值是否等于1對Q進行素數(shù)測試。如果取了很多個A，Q仍未測試失敗，那么則認為Q是素數(shù)。當然，測試次數(shù)越多越準確，但一般來講50次就足夠了。另外，預先用常歸算法構造一個包括500個素數(shù)的數(shù)組，先對Q進行整除測試，將會大大提高通過率，方法如下： 算法四：費馬定理測試可能素數(shù)P C := 500;素數(shù)表大小 S 0 TO C ;素數(shù)表 B := P - 1 T := 50;表示進行測試的次數(shù) A := 0 FOR I := 0 TO C;進行素數(shù)表初步測試 IF P mo

25、d SI = 0 RETURN FAILE END IF IF P < SI BREAK END IF NEXT I FOR I := 0 TO T A := S RAND() mod C IF A ( P - 1 ) mod P <> 1 RETURN FAILE END IF NEXT I RETURN PASS 這個算法看起來很完美，但實際上從一開始它就犯了一個很大的錯，那就是對于任意與Q互質的A都有AQ - 1 mod Q = 1，這是素數(shù)的性質，是素數(shù)成立的一個必要條件，但不是充分條件！讓我們來看一下29341這個數(shù)，它等于13 * 37 * 61，但任何與它互質的

26、A都有A29341 - 1 mod 29341 = 1成立。這種數(shù)字還有不少，數(shù)學上把它們稱為卡爾麥克數(shù)，現(xiàn)在數(shù)學家們已經找到所有1016以內的卡爾麥克數(shù)，最大的一個是9585921133193329。我們必須尋找更為有效的測試方法。數(shù)學家們通過對費馬小定理的研究，并加以擴展，總結出了多種快速有效的素數(shù)測試方法，目前最快的算法是拉賓米勒測試算法，其過程如下： 首先確定N是否為奇數(shù)，不是奇數(shù)的判斷失敗。 選擇T個隨機整數(shù)A，并且有 0 < A < N成立。 進行費馬小定理測試，計算并判斷AN - 1 mod N的結果是否等于1，如果不是，則測試失敗。 找到R和M，使得N = 2R *

27、 M + 1成立。 找R和M的方式如下： N用二進制數(shù)B來表示，令C = B - 1。因為N為奇數(shù)，所以C的最低位為0，從C的最低位的0開始向高位統(tǒng)計，一直到遇到第一個1，0的個數(shù)即為R，M為B右移R位的值。 如果AM mod N = 1，則通過B對于N的測試，然后進行下一個A對N的測試，直到T個A對N的測試全部通過。 如果AM mod N的值不是1，那么將AM mod N式子中的AM看做底數(shù)S，我們將S乘方后再計算SM mod N的值，并判斷是否等于1，如果是則通過B對于N的測試，然后進行下一個A對N的測試，直到T個A對N的測試全部通過；如果不是則繼續(xù)將底數(shù)乘方。 如果一直到S = A 2M

28、R時，并且SM mod N = 1仍未通測試，那么測試失敗。 通過驗證得知，當T為素數(shù)，并且A是平均分布的隨機數(shù)，那么測試有效率為1 / 4K。如果T > 50那么測試失誤的機率就會小于10-30，這對于目前的計算機硬件來說已經足夠證明N就是素數(shù)了。下面是偽代碼。 算法五：拉賓米勒測試法測試P是否為素數(shù)。 C := 500;素數(shù)表大小 S 0 TO C ;素數(shù)表 B := P - 1 T := 50;表示進行測試的次數(shù) A := 0;用來測試通過的隨機整數(shù) FOR I := 0 TO C;進行素數(shù)表初步測試 IF P mod SI = 0 RETURN FAILE END IF IF P

29、 < SI BREAK END IF NEXT I M := P - 1;使二進制N的最后一位變?yōu)榕紨?shù) R := 0 WHILE M & 1 = 0;一直到有某一位為1為止 M := M >> 1 R := R + 1;計算R NEXT X := 0 Y := 0FOR 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 =

30、 1 BREAK END IF X := X 2 NEXT IF X > Y RETURN FAILE END IF NEXT RETURN PASS  ·二元一次不定方程 在算法概述的章節(jié)里我們曾經討論過公鑰1的求法：找一個數(shù)D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。為了求D，我們先對這個方程變形。實際上這個方程可以看做AX mod B = 1，即： AX = BY + 1，Y為一整數(shù)。 AX - BY = 1 這就是一個二元一次不定方程，有已知數(shù)A、B，未知數(shù)X、Y。我們現(xiàn)在需要求的是X，那么就是求這個方程

31、對于X的最小整數(shù)解。由于方程有兩個未知數(shù)，所以必須化簡方程，使得一個未知數(shù)的系數(shù)為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 - BY = 1，且A > M成立。接著可以用同樣的方法來化簡A，最終必能將一個系數(shù)化為0。此時求出另一個未知數(shù)的解，再按逆序代入上一步的方程，求出另一個未知數(shù)的解，再代入上一步的方程，一直遞推的第

32、一個方程，最終即可獲得X和Y的最小整數(shù)解。因為每一步遞推的方程的余數(shù)相同，所以我們稱這些方程為“一次同余式”。這個算法被稱為歐幾里德擴展算法，而歐幾里德算法其實就是求公因式的輾轉相除法，大多數(shù)朋友在中學時就學過了，但是我們下面會用到，所以我這里簡單的用偽代碼來描述一下歐幾里德算法。 算法六：求A和B兩相異自然數(shù)的最大公因數(shù)，另R為結果。 IF A < B SWAP A, B END IF WHILE A := A mod B IF A = 0 R := B BREAK END IF B := B mod A IF B = 0 R := A BREAK END IF NEXT 歐幾里德擴展算法雖然容易理解，但當A和B較大時會有很多步的遞歸，此時對于計算機而言就不是一個有效的算法了，那么如何才能設計一套真正對于計算機可行的大數(shù)二元一次方程的求解算法呢？ 事實上我國古代數(shù)學家發(fā)明的大衍求一術，就可以非常好的解決這個問題。 我國對于余數(shù)理論的研究是十分悠久的，而且有著卓越的成就。早在公元280到420年間問世的孫子算經中就有著對一次同余式的問題有了初步的討論。到了南宋時代，數(shù)學家秦九韶對此加以整理總結，發(fā)展成為一個解聯(lián)立一次同余式的系統(tǒng)方法，稱為“大衍求一術”，記錄在他所著的九章算術中。大衍求一術的描述是這