RSA加密算法初探

·前言

本文全面的介紹了RSA算法的概念、原理、證明和實現(xiàn)。我在寫作本文之前在網(wǎng)上查閱過相關(guān)資料，可這些資料不是含糊其辭就是滿篇謬誤。所以我力求用通俗易懂的文字將算法深入剖析，用最嚴(yán)謹(jǐn)?shù)牟襟E進行論相關(guān)的各項算法，以降低文章的閱讀難度。讀者只要學(xué)過初中代數(shù)就可以理解全文，我衷心希望更多讀者能認(rèn)識到加密算法其實并不難。

文中的算法均為偽代碼，由于偽代碼沒有辦法進行測試，再加上我個人數(shù)學(xué)功底比較薄弱，所以錯漏之處在所難免，還請各位老師給予指教。質(zhì)疑或指正請發(fā)送電子郵件到fireseed1949@hotmail.com，我會認(rèn)真閱讀并回復(fù)的！

感謝北航數(shù)學(xué)系（畢業(yè)）李楨老師、西工大計算機系（畢業(yè)）張小寧老師在數(shù)學(xué)上對我的指點。

另注：文中mod就是求余的符號，X mod Y表示X除以Y所得的余數(shù)。

·概述

RSA算法是世界上第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的非對稱性加密算法。它易于理解和操作，所以流行甚廣。算法的名字以發(fā)明者的名字命名，他們是：Ron Rivest，Adi Shamir 和Leonard Adleman。雖然RSA的安全性一直未能得到理論上的證實，但它經(jīng)歷了各種攻擊，至今未被完全攻破。為了讓讀者更容易的理解RSA加密，先大概講述一下信息加密技術(shù)的相關(guān)概念和原理。

我們對于在數(shù)字媒體上進行交換的數(shù)據(jù)進行加密的方法稱為信息交換加密技術(shù)，它分為兩類，即對稱加密和非對稱加密。

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

在非對稱加密（或稱公開密鑰加密）體系中，密鑰被分解為一對，即公開密鑰（公鑰）和私有密鑰（私鑰）。這對密鑰中任何一把都可以作為公開密鑰，通過非保密方式向他人公開，而另一把作為私有密鑰，加以妥善保存。公開密鑰用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開密鑰可廣泛公布，但它只對應(yīng)于生成密鑰的交換方。非對稱加密方式可以使通信雙方無須事先交換密鑰就可以建立安全通信，廣泛應(yīng)用于身份認(rèn)證、數(shù)字簽名等信息交換領(lǐng)域。非對稱加密體系一般是建立在某些已知的數(shù)學(xué)難題之上，是計算機復(fù)雜性理論發(fā)展的必然結(jié)果。最具有代表性是RSA公鑰密碼體制。

在RSA算法中，我們先要獲得兩個不同的質(zhì)數(shù)P和Q做為算法因子，再找出一個正整數(shù)E，使得E與 ( P - 1 ) * ( Q - 1 ) 的值互質(zhì)，這個E就是私鑰。找到一個整數(shù)D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立，D就是公鑰1。設(shè)N為P和Q的乘積，N則為公鑰2。加密時先將明文轉(zhuǎn)換為一個或一組小于N的整數(shù)I，并計算I^D mod N的值M，M就密文。解密時將密文M^E mod N，也就是M的E次方再除以N所得的余數(shù)就是明文。

因為私鑰E與( P - 1 ) * ( Q - 1 )互質(zhì)，而公鑰D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必須得出( P - 1 ) * ( Q - 1 )，因而必須先對N進行因數(shù)分解。如果N很大那么因數(shù)分解就會非常困難，所以要提高加密強度P和Q的數(shù)值大小起著決定性的因素。一般來講當(dāng)P和Q都大于2¹²⁸時，按照目前的機算機處理速度破解基本已經(jīng)不大可能了。

·證明

下面將會開始討論RSA算法的原理及其算法證明。如果您只關(guān)心RSA算法的實現(xiàn)，則可以略過這一步。我把每一個有用的定理都用粗標(biāo)標(biāo)記了，對于數(shù)學(xué)不很在行的朋友可以只了解一下相關(guān)定理的說明而不需要驗證求證過程了。

一、費馬小定理[1]的轉(zhuǎn)化

費馬小定理：有N為任意正整數(shù)，P為素數(shù)，且N不能被P整除，則有：

N^P mod P = N

費馬小定理可變形為：

N^{P - N} mod P = 0

( N ( N^{P - 1} - 1 ) ) mod P = 0

因為

( N ( N^{P - 1} - 1 ) ) mod N = 0

所以N和P的公倍數(shù)為：

N ( N^{P - 1} - 1 )                    （1）

又因為N與P互質(zhì)，而互質(zhì)數(shù)的最小公倍數(shù)為它們的乘積，所以一定存在正整數(shù)M使得：N ( N^{P - 1} - 1 ) = MNP成立。并化簡為：

N^{P - 1} - 1 = MP

( N^{P - 1} - 1 ) mod P = 0

可以變形為：

N^{P - 1} mod P = 1          （2）

（2）就是費馬小定理的轉(zhuǎn)化定理，為方便敘述，下文簡稱為定理一。小提示，可能很多人認(rèn)為費馬小定理本來就是（2），實際上不是這樣，因為費馬小定理的轉(zhuǎn)化非常容易，而轉(zhuǎn)化定理又是一個無論在數(shù)學(xué)上還是計算機程序上都很常用的公式，所以人們就普遍認(rèn)為（2）就是費馬小定理了。

二、積模分解公式

有X、Y和Z三個正整數(shù)，且X * Y大于Z，則有：

( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z

證明如下

當(dāng)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的整數(shù)倍，所以（3）式可化簡為：

AB mod Z

因為A和B實際上是X和Y分別除以Z的余數(shù)，所以有：

( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。

當(dāng)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成立。

同理，當(dāng)X比Z小而Y比Z大時，上式也成立。

當(dāng)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兩個互質(zhì)數(shù)，如果有X mod P = 0，X mod Q = 0，則有：X mod PQ = 0

證明：

因為P和Q互質(zhì)，所以它們的公倍數(shù)為KPQ（K為整數(shù)），最小公倍數(shù)為PQ。又因為X為P和Q的公倍數(shù)，所以X / PQ = K，所以X mod PQ = 0。

四、定理三

有P和Q兩個互質(zhì)數(shù)，設(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互質(zhì)，根據(jù)定理二可得：

( Y - X ) mod PQ = 0

即

Y mod PQ = X

五、定理三的逆定理

有P和Q兩個互質(zhì)數(shù)，設(shè)有整數(shù)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是兩個相異質(zhì)數(shù)，另有正整數(shù)R和M，其中M的值與( P - 1 )( Q - 1 )的值互質(zhì)，并使得( RM ) mod ( P - 1 )( Q - 1 ) = 1。有正整數(shù)A，且A < PQ，設(shè)C = A^R mod PQ，B = C^M mod PQ則有：A = B

證明：

將C = A^R mod PQ代入B = C^M mod PQ得：

B = ( ( A^R mod PQ )^M ) mod PQ

根據(jù)積模分解公式，可變形為：

B = ( A^R )^M mod PQ

B = A^RM mod PQ                      （1）

因為有( RM ) mod ( P - 1 )( Q - 1 ) = 1，所以有：

RM = K ( P - 1 )( Q - 1 ) + 1，K為正整數(shù)。

代入（1）得：

B = A^{K ( P - 1 )( Q - 1 ) + 1} mod PQ                 （2）

如果A^RM < PQ時，明顯有B = A。

如果A^RM > PQ，且A不是P的倍數(shù)也不是Q的倍數(shù)時，（2）可變形為：

B = ( AA^{K ( P - 1 )( Q - 1 )} ) mod PQ

根據(jù)積模分解公式可變形為：

B = ( ( A mod PQ )( A^{K ( P - 1 )( Q - 1 )} mod PQ ) ) mod PQ                   （3）

根據(jù)定理三的逆定理：

A^{K ( P - 1 )( Q - 1 )} mod PQ = ( A^{K ( P - 1 )} ) ^{( Q - 1 )} mod Q

根據(jù)費馬小定理可得：

( A^{K ( P - 1 )} ) ^{( Q - 1 )} mod Q = 1，則

A^{K ( P - 1 )( Q - 1 )} mod PQ = 1

故( 3 )可轉(zhuǎn)化為：

B = ( A mod PQ ) mod PQ

因為A < PQ，所以B = A成立。

在述證明過程中可以總結(jié)一點：

當(dāng)P為素數(shù)且A和P互質(zhì)時，那么當(dāng)N為任意自然數(shù)時都有A^{N( P - 1 )} mod P = 1成立，這個定理下面還要用到，我們稱之為定理四。

如果A^RM > PQ，且A不是P的倍數(shù)而是Q的倍數(shù)時，A可表示為A = NQ，N為一小于A的整數(shù)。

那么（2）式可變形為：

B = ( NQ )^{K ( P - 1 )( Q - 1 ) + 1} mod PQ

B = ( N^{K ( P - 1 )( Q - 1 ) + 1} )( Q^{K ( P - 1 )( Q - 1 ) + 1} ) mod PQ

把Q作為公因子提出來，得：

B = ( ( NN^{K ( P - 1 )( Q - 1 )} ) ( Q^{K ( P - 1 )( Q - 1 )} mod P ) ) Q

用積模分解公式進行分解，得：

B = ( ( NN^{K ( P - 1 )( Q - 1 )} mod P )( Q^{K ( P - 1 )( Q - 1 )} mod P ) mod P ) Q

跟據(jù)定理四，N^{K ( P - 1 )( Q - 1 )}和Q^{K ( 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成立

同理，當(dāng)A是P的倍數(shù)而不是Q的倍數(shù)時，B = A也成立。

又因為A小于PQ，而P和Q又都是質(zhì)數(shù)，所以A既是P的倍數(shù)又是Q的倍數(shù)的情況不存在。

RSA定理成立。

·大整數(shù)存儲運算

由于安全需要，目前主流的RSA加密算法都是基于2進制的512位或1024位的大整數(shù)，而目前的主流高級語言編譯器最多也只能支持到2進制64位整數(shù)，所以大整數(shù)的存儲和運算對于RSA算法的實現(xiàn)都是至關(guān)重要的。一個最容易理解的方法就是將大數(shù)用十進制表示，并將每一位（0 – 9）都做為一個單獨的數(shù)用數(shù)組進行管理。做加減乘除等運算時，人工的對其進行進、借位。然而計算機對于10進制數(shù)的處理并不在行，而且表示非2ⁿ進制的數(shù)會浪費很多空間，所以應(yīng)該采用8進制、16進制、32進制、64進制的表示法，使得每一位數(shù)字都能占據(jù)一個完整的內(nèi)存空間。目前絕大多數(shù)PC機都是基于32位運算的，所以采用2³²進制表示大數(shù)將會很大提高計算機的處理效率?，F(xiàn)實中，就使用32位的整數(shù)數(shù)組進行存儲每一位數(shù)，另設(shè)一個布爾值表示正負。進行計算時常會遇到進位借位的情況，而且常常會超過2³²次方，幸好目前的編譯器都支持64位整數(shù)，可以滿足( 2³² - 1 ) * ( 2³² - 1 )以內(nèi)的運算，所以使用64位整數(shù)作為運算中間量將會是很好的選擇。

大數(shù)除了加減乘除等基本運算以外，還有一些如賦值、比較、左右移位、或、與等，為了方便使用，我們可以利用面向?qū)ο蟮姆椒ò汛髷?shù)進行封裝，并利用C++的特性進行運算符重載，使它成為一個整體對象來進行操作。這樣我們就可像使用int一樣來使用它了。當(dāng)然，大數(shù)類的實現(xiàn)并不是一篇文章就可以敘述完的，而且目前有一些很成熟并且開源的大數(shù)類庫，如GTK、HugeCalc等，因此我在這里就不對具體的算法做進一步闡釋了。

·冪模運算

冪模運算是RSA算法中的關(guān)鍵，無論是素數(shù)測試，還是加密解密，都要用到冪模運算。簡單的講，冪模運算就是計算N^R mod D的值。但是對于計算機來講，計算R很大的N^R的值時將會非常浪費存儲空間，并使計算變的非常緩慢而難以實現(xiàn)。但是我們通過上文討論的積模分解公式，可以發(fā)現(xiàn)N^R mod D是可以進行轉(zhuǎn)換的。

N^R mod D = ( ( 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）式仍然可以進行分解以減少運算步驟。計算A¹³時，如果讓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 * A，一共五次運算?？偨Y(jié)這個規(guī)律可以發(fā)現(xiàn)，運算過程中如果某次的冪數(shù)為奇數(shù)時，在乘方過后還需要乘以上次保留的積。跟據(jù)這個規(guī)律，我們把運算分為兩部分的乘積，下面是偽代碼。

算法一：計算N的E次方，令R為計算結(jié)果。

R := N           ; R用來存儲2ⁿ

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的值，那么只要令上面?zhèn)未a中參量N的值為N mod D，并對結(jié)果R求R mod D就可以了，下面是基于上面求乘方算法的冪模運算的偽代碼。

算法二：計算N的E次方再取D的模，令R為計算結(jié)果。

R := N mod D

R := R ^ E            ;調(diào)用算法一

R := R % D

如果再利用上文過程中提到積模分解公式對算法做進一步優(yōu)化，直接把取余的運算代入到乘方中，就成為了著名的蒙格馬利快速冪模運算法，偽代碼如下。

算法三：蒙格馬利法計算N的E次方再取D的模，令R為計算結(jié)果。

R := 1

A := N

B := E

WHILE Z != 0

       IF B & 1              ;判斷是否為奇數(shù)

              B := B - 1

              R := R * A

              X := X % D

       ELSE

              B := B / 2

              A := A * A

              A := A % D

       END IF

NEXT

蒙格馬利快速冪模運算，是目前世界上效率最高的冪模運算，很多硬件芯片在處理類似算法時都采用的這種方法。

·尋找大素數(shù)

為了有效防止破解，必要須找到兩個很大的素數(shù)作為算法因子。而尋找大素數(shù)，是數(shù)學(xué)家們一個永恒的話題。素數(shù)的定義是只能被自己和1整除的自然數(shù)，按照常規(guī)的理解，使用計算機對一個很大的數(shù)進行素數(shù)測試時，需要遍歷所有小于它且大于1的自然數(shù)，并逐個判斷是否能被該數(shù)整除。這個過程對于非常大的素數(shù)而言是非常緩慢的。但是根據(jù)費馬小定理，我們可以設(shè)計一種算法來快速測試素數(shù)。當(dāng)A和Q互質(zhì)時，有：A^{Q - 1} mod Q = 1，那么，我們可以通過判斷A^{Q - 1} mod Q的值是否等于1對Q進行素數(shù)測試。如果取了很多個A，Q仍未測試失敗，那么則認(rèn)為Q是素數(shù)。當(dāng)然，測試次數(shù)越多越準(zhǔn)確，但一般來講50次就足夠了。另外，預(yù)先用常歸算法構(gòu)造一個包括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 mod S[I] = 0

              RETURN FAILE

       END IF

       IF P < S[I]

              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互質(zhì)的A都有A^{Q - 1} mod Q = 1，這是素數(shù)的性質(zhì)，是素數(shù)成立的一個必要條件，但不是充分條件！讓我們來看一下29341這個數(shù)，它等于13 * 37 * 61，但任何與它互質(zhì)的A都有A^{29341 - 1} mod 29341 = 1成立。這種數(shù)字還有不少，數(shù)學(xué)上把它們稱為卡爾麥克數(shù)，現(xiàn)在數(shù)學(xué)家們已經(jīng)找到所有10¹⁶以內(nèi)的卡爾麥克數(shù)，最大的一個是9585921133193329。我們必須尋找更為有效的測試方法。數(shù)學(xué)家們通過對費馬小定理的研究，并加以擴展，總結(jié)出了多種快速有效的素數(shù)測試方法，目前最快的算法是拉賓米勒測試算法，其過程如下：

首先確定N是否為奇數(shù)，不是奇數(shù)的判斷失敗。

選擇T個隨機整數(shù)A，并且有 0 < A < N成立。

進行費馬小定理測試，計算并判斷A^{N - 1} mod N的結(jié)果是否等于1，如果不是，則測試失敗。

找到R和M，使得N = 2^R * 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位的值。

如果A^M mod N = 1，則通過B對于N的測試，然后進行下一個A對N的測試，直到T個A對N的測試全部通過。

如果A^M mod N的值不是1，那么將A^M mod N式子中的A^M看做底數(shù)S，我們將S乘方后再計算S^M mod N的值，并判斷是否等于1，如果是則通過B對于N的測試，然后進行下一個A對N的測試，直到T個A對N的測試全部通過；如果不是則繼續(xù)將底數(shù)乘方。

如果一直到S = A ^ 2^MR時，并且S^M mod N = 1仍未通測試，那么測試失敗。

通過驗證得知，當(dāng)T為素數(shù)，并且A是平均分布的隨機數(shù)，那么測試有效率為1 / 4^K。如果T > 50那么測試失誤的機率就會小于10^-30，這對于目前的計算機硬件來說已經(jīng)足夠證明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 S[I] = 0

              RETURN FAILE

       END IF

       IF P < S[I]

              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

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

·二元一次不定方程

在算法概述的章節(jié)里我們曾經(jīng)討論過公鑰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，那么就是求這個方程對于X的最小整數(shù)解。由于方程有兩個未知數(shù)，所以必須化簡方程，使得一個未知數(shù)的系數(shù)為0時才能得解。設(shè)B > A時有：

AX - BY = 1

那么可以認(rèn)為B = AN + M，則有：

AX - ( AN + M )Y = 1

AX - ANY - MY = 1

A( X - NY ) - MY = 1

實際上M就是B mod A的值，設(shè)X’ = X - NY，B’ = B mod A則有AX’ - B’Y = 1，且A > M成立。接著可以用同樣的方法來化簡A，最終必能將一個系數(shù)化為0。此時求出另一個未知數(shù)的解，再按逆序代入上一步的方程，求出另一個未知數(shù)的解，再代入上一步的方程，一直遞推的第一個方程，最終即可獲得X和Y的最小整數(shù)解。因為每一步遞推的方程的余數(shù)相同，所以我們稱這些方程為“一次同余式”。這個算法被稱為歐幾里德擴展算法，而歐幾里德算法其實就是求公因式的輾轉(zhuǎn)相除法，大多數(shù)朋友在中學(xué)時就學(xué)過了，但是我們下面會用到，所以我這里簡單的用偽代碼來描述一下歐幾里德算法。

算法六：求A和B兩相異自然數(shù)的最大公因數(shù)，另R為結(jié)果。

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

歐幾里德擴展算法雖然容易理解，但當(dāng)A和B較大時會有很多步的遞歸，此時對于計算機而言就不是一個有效的算法了，那么如何才能設(shè)計一套真正對于計算機可行的大數(shù)二元一次方程的求解算法呢？

事實上我國古代數(shù)學(xué)家發(fā)明的大衍求一術(shù)，就可以非常好的解決這個問題。我國對于余數(shù)理論的研究是十分悠久的，而且有著卓越的成就。早在公元280到420年間問世的《孫子算經(jīng)》中就有著對一次同余式的問題有了初步的討論。到了南宋時代，數(shù)學(xué)家秦九韶對此加以整理總結(jié)，發(fā)展成為一個解聯(lián)立一次同余式的系統(tǒng)方法，稱為“大衍求一術(shù)”，記錄在他所著的《九章算術(shù)》中。大衍求一術(shù)的描述是這樣的：“置奇右上，定居右下，立天元一于左上，先以右上除右下，所得商數(shù)與左上一相生，入左下，然后乃以右行上下以少除多，于互除這，所得商數(shù)隨即于互累乘，于左行上下，須使右上末后奇一而止。乃驗左上所得以為乘率，或奇數(shù)已見單一者便為乘率”。這句話的意思我用偽代碼描述如下。

算法七：已知有自然數(shù)N和素數(shù)P，N > P。并且有正整數(shù)D使ND mod P = 1成立，求D。

IF N和P的最大公因數(shù) <> 1             ;調(diào)用算法六

       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

·結(jié)語

到現(xiàn)在，RSA算法中所涉及到的所有算法我們都已經(jīng)討論過了。實際還有一個運算，就是私鑰的獲得辦法：計算得到與( P - 1 ) * ( Q - 1 )的值互質(zhì)的整數(shù)E。我情愿不把它稱之為算法，因為只需要一個循環(huán)和一個判斷就可以完成，所以這里也就沒有必要對它多加論述了。

·附錄

費馬小定理的證明：

引理1：設(shè)M，A的最大公約數(shù)( M，A ) = 1，且M整除AB，即M mod AB = 0，則M mod B = 0。

引理2：設(shè)P是素數(shù)，<P，J>表示組合數(shù)，即從P個數(shù)中選出J個數(shù)的組合種數(shù)，且1 ≤ J ≤ P - 1，則P mod <P，J>。