RSA加密算法初探
·前言
本文全面的介紹了RSA算法的概念、原理、證明和實(shí)現。我在寫(xiě)作本文之前在網(wǎng)上查閱過(guò)相關(guān)資料，可這些資料不是含糊其辭就是滿(mǎn)篇謬誤。所以我力求用通俗易懂的文字將算法深入剖析，用最嚴謹的步驟進(jìn)行論相關(guān)的各項算法，以降低文章的閱讀難度。讀者只要學(xué)過(guò)初中代數就可以理解全文，我衷心希望更多讀者能認識到加密算法其實(shí)并不難。
文中的算法均為偽代碼，由于偽代碼沒(méi)有辦法進(jìn)行測試，再加上我個(gè)人數學(xué)功底比較薄弱，所以錯漏之處在所難免，還請各位老師給予指教。質(zhì)疑或指正請發(fā)送電子郵件到fireseed1949@hotmail.com，我會(huì )認真閱讀并回復的！
感謝北航數學(xué)系（畢業(yè)）李楨老師、西工大計算機系（畢業(yè)）張小寧老師在數學(xué)上對我的指點(diǎn)。
另注：文中mod就是求余的符號，X mod Y表示X除以Y所得的余數。
·概述
RSA算法是世界上第一個(gè)既能用于數據加密也能用于數字簽名的非對稱(chēng)性加密算法。它易于理解和操作，所以流行甚廣。算法的名字以發(fā)明者的名字命名，他們是：Ron Rivest，Adi Shamir 和Leonard Adleman。雖然RSA的安全性一直未能得到理論上的證實(shí)，但它經(jīng)歷了各種攻擊，至今未被完全攻破。為了讓讀者更容易的理解RSA加密，先大概講述一下信息加密技術(shù)的相關(guān)概念和原理。
我們對于在數字媒體上進(jìn)行交換的數據進(jìn)行加密的方法稱(chēng)為信息交換加密技術(shù)，它分為兩類(lèi)，即對稱(chēng)加密和非對稱(chēng)加密。
在對稱(chēng)加密技術(shù)中，對信息的加密和解密都使用相同的鑰，也就是說(shuō)一把鑰匙開(kāi)一把鎖。這種加密方法可簡(jiǎn)化加密處理過(guò)程，信息交換雙方都不必彼此研究和交換專(zhuān)用的加密算法。如果在交換階段私有密鑰未曾泄露，那么機密性和報文完整性就可以得以保證。對稱(chēng)加密技術(shù)也存在一些不足，如果交換一方有N個(gè)交換對象，那么他就要維護N個(gè)私有密鑰，對稱(chēng)加密存在的另一個(gè)問(wèn)題是雙方共享一把私有密鑰，交換雙方的任何信息都是通過(guò)這把密鑰加密后傳送給對方的。如三重DES是DES（數據加密標準）的一種變形，這種方法使用兩個(gè)獨立的56為密鑰對信息進(jìn)行3次加密，從而使有效密鑰長(cháng)度達到112位。
在非對稱(chēng)加密（或稱(chēng)公開(kāi)密鑰加密）體系中，密鑰被分解為一對，即公開(kāi)密鑰（公鑰）和私有密鑰（私鑰）。這對密鑰中任何一把都可以作為公開(kāi)密鑰，通過(guò)非保密方式向他人公開(kāi)，而另一把作為私有密鑰，加以妥善保存。公開(kāi)密鑰用于加密，私有密鑰用于解密，私有密鑰只能由生成密鑰的交換方掌握，公開(kāi)密鑰可廣泛公布，但它只對應于生成密鑰的交換方。非對稱(chēng)加密方式可以使通信雙方無(wú)須事先交換密鑰就可以建立安全通信，廣泛應用于身份認證、數字簽名等信息交換領(lǐng)域。非對稱(chēng)加密體系一般是建立在某些已知的數學(xué)難題之上，是計算機復雜性理論發(fā)展的必然結果。最具有代表性是RSA公鑰密碼體制。
在RSA算法中，我們先要獲得兩個(gè)不同的質(zhì)數P和Q做為算法因子，再找出一個(gè)正整數E，使得E與 ( P - 1 ) * ( Q - 1 ) 的值互質(zhì)，這個(gè)E就是私鑰。找到一個(gè)整數D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立，D就是公鑰1。設N為P和Q的乘積，N則為公鑰2。加密時(shí)先將明文轉換為一個(gè)或一組小于N的整數I，并計算ID mod N的值M，M就密文。解密時(shí)將密文ME mod N，也就是M的E次方再除以N所得的余數就是明文。
因為私鑰E與( P - 1 ) * ( Q - 1 )互質(zhì)，而公鑰D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必須得出( P - 1 ) * ( Q - 1 )，因而必須先對N進(jìn)行因數分解。如果N很大那么因數分解就會(huì )非常困難，所以要提高加密強度P和Q的數值大小起著(zhù)決定性的因素。一般來(lái)講當P和Q都大于2128時(shí)，按照目前的機算機處理速度破解基本已經(jīng)不大可能了。
·證明
下面將會(huì )開(kāi)始討論RSA算法的原理及其算法證明。如果您只關(guān)心RSA算法的實(shí)現，則可以略過(guò)這一步。我把每一個(gè)有用的定理都用粗標標記了，對于數學(xué)不很在行的朋友可以只了解一下相關(guān)定理的說(shuō)明而不需要驗證求證過(guò)程了。
一、費馬小定理[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互質(zhì)，而互質(zhì)數的最小公倍數為它們的乘積，所以一定存在正整數M使得：N ( NP - 1 - 1 ) = MNP成立。并化簡(jiǎn)為：
NP - 1 - 1 = MP
( NP - 1 - 1 ) mod P = 0
可以變形為：
NP - 1 mod P = 1 （2）
（2）就是費馬小定理的轉化定理，為方便敘述，下文簡(jiǎn)稱(chēng)為定理一。小提示，可能很多人認為費馬小定理本來(lái)就是（2），實(shí)際上不是這樣，因為費馬小定理的轉化非常容易，而轉化定理又是一個(gè)無(wú)論在數學(xué)上還是計算機程序上都很常用的公式，所以人們就普遍認為（2）就是費馬小定理了。
二、積模分解公式
有X、Y和Z三個(gè)正整數，且X * Y大于Z，則有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z
證明如下
當X和Y都比Z大時(shí)，可以將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）式可化簡(jiǎn)為：
AB mod Z
因為A和B實(shí)際上是X和Y分別除以Z的余數，所以有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。
當X比Z大而Y比Z小時(shí)
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大時(shí)，上式也成立。
當X和Y都比Z小時(shí)，X = X mod Z，Y = Y mod Z所以有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。
積模分解公式成立。
三、定理二
有P和Q兩個(gè)互質(zhì)數，如果有X mod P = 0，X mod Q = 0，則有：X mod PQ = 0
證明：
因為P和Q互質(zhì)，所以它們的公倍數為KPQ（K為整數），最小公倍數為PQ。又因為X為P和Q的公倍數，所以X / PQ = K，所以X mod PQ = 0。
四、定理三
有P和Q兩個(gè)互質(zhì)數，設有整數X和Y滿(mǎn)足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ì)，根據定理二可得：
( Y - X ) mod PQ = 0
即
Y mod PQ = X
五、定理三的逆定理
有P和Q兩個(gè)互質(zhì)數，設有整數X和Y滿(mǎn)足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是兩個(gè)相異質(zhì)數，另有正整數R和M，其中M的值與( P - 1 )( Q - 1 )的值互質(zhì)，并使得( RM ) mod ( P - 1 )( Q - 1 ) = 1。有正整數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
根據積模分解公式，可變形為：
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為正整數。
代入（1）得：
B = AK ( P - 1 )( Q - 1 ) + 1 mod PQ （2）
如果ARM < PQ時(shí)，明顯有B = A。
如果ARM > PQ，且A不是P的倍數也不是Q的倍數時(shí)，（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，所以B = A成立。
在述證明過(guò)程中可以總結一點(diǎn)：
當P為素數且A和P互質(zhì)時(shí)，那么當N為任意自然數時(shí)都有AN( P - 1 ) mod P = 1成立，這個(gè)定理下面還要用到，我們稱(chēng)之為定理四。
如果ARM > PQ，且A不是P的倍數而是Q的倍數時(shí)，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作為公因子提出來(lái)，得：
B = ( ( NNK ( P - 1 )( Q - 1 ) ) ( QK ( P - 1 )( Q - 1 ) mod P ) ) Q
用積模分解公式進(jìn)行分解，得：
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 < PQ，所以B = A成立
同理，當A是P的倍數而不是Q的倍數時(shí)，B = A也成立。
又因為A小于PQ，而P和Q又都是質(zhì)數，所以A既是P的倍數又是Q的倍數的情況不存在。
RSA定理成立。
·大整數存儲運算
由于安全需要，目前主流的RSA加密算法都是基于2進(jìn)制的512位或1024位的大整數，而目前的主流高級語(yǔ)言編譯器最多也只能支持到2進(jìn)制64位整數，所以大整數的存儲和運算對于RSA算法的實(shí)現都是至關(guān)重要的。一個(gè)最容易理解的方法就是將大數用十進(jìn)制表示，并將每一位（0 – 9）都做為一個(gè)單獨的數用數組進(jìn)行管理。做加減乘除等運算時(shí)，人工的對其進(jìn)行進(jìn)、借位。然而計算機對于10進(jìn)制數的處理并不在行，而且表示非2n進(jìn)制的數會(huì )浪費很多空間，所以應該采用8進(jìn)制、16進(jìn)制、32進(jìn)制、64進(jìn)制的表示法，使得每一位數字都能占據一個(gè)完整的內存空間。目前絕大多數PC機都是基于32位運算的，所以采用232進(jìn)制表示大數將會(huì )很大提高計算機的處理效率?，F實(shí)中，就使用32位的整數數組進(jìn)行存儲每一位數，另設一個(gè)布爾值表示正負。進(jìn)行計算時(shí)常會(huì )遇到進(jìn)位借位的情況，而且常常會(huì )超過(guò)232次方，幸好目前的編譯器都支持64位整數，可以滿(mǎn)足( 232 - 1 ) * ( 232 - 1 )以?xún)鹊倪\算，所以使用64位整數作為運算中間量將會(huì )是很好的選擇。
大數除了加減乘除等基本運算以外，還有一些如賦值、比較、左右移位、或、與等，為了方便使用，我們可以利用面向對象的方法把大數進(jìn)行封裝，并利用C++的特性進(jìn)行運算符重載，使它成為一個(gè)整體對象來(lái)進(jìn)行操作。這樣我們就可像使用int一樣來(lái)使用它了。當然，大數類(lèi)的實(shí)現并不是一篇文章就可以敘述完的，而且目前有一些很成熟并且開(kāi)源的大數類(lèi)庫，如GTK、HugeCalc等，因此我在這里就不對具體的算法做進(jìn)一步闡釋了。
·冪模運算
冪模運算是RSA算法中的關(guān)鍵，無(wú)論是素數測試，還是加密解密，都要用到冪模運算。簡(jiǎn)單的講，冪模運算就是計算NR mod D的值。但是對于計算機來(lái)講，計算R很大的NR的值時(shí)將會(huì )非常浪費存儲空間，并使計算變的非常緩慢而難以實(shí)現。但是我們通過(guò)上文討論的積模分解公式，可以發(fā)現NR mod D是可以進(jìn)行轉換的。
NR mod D = ( ( N mod D )R ) mod D （1）
這樣，在運算( ( N mod D )R ) mod D的過(guò)程中，在最壞的情況下，可能出現的最大的值就是( D - 1 )R，而D <= N，從而較大的減少了數據量，提高了運算速度。通過(guò)觀(guān)查發(fā)現，（1）式仍然可以進(jìn)行分解以減少運算步驟。計算A13時(shí)，如果讓A直接進(jìn)行連乘，需要12次運算。但是如果把A * A的值保存起來(lái)，我們就只需要進(jìn)行B = A * A和B * B * B * B * B * B * A，一共七次運算，如果我們再把B * B的值保存起來(lái)，那我們就只需要進(jìn)行B = A * A、C = B * B、D = C * C、
D * C * A，一共五次運算?？偨Y這個(gè)規律可以發(fā)現，運算過(guò)程中如果某次的冪數為奇數時(shí)，在乘方過(guò)后還需要乘以上次保留的積。跟據這個(gè)規律，我們把運算分為兩部分的乘積，下面是偽代碼。
算法一：計算N的E次方，令R為計算結果。
R := N ; R用來(lái)存儲2n
K := 1 ; K用于存儲另一部分的乘積
M := 0 ; M表示冪數每次除2的余數
WHILE E > 1
E := E / 2，余數存入M
IF M = 1
K := R * K
END IF
R := R * R
NEXT
R := R * K
再回到我們剛才討論的冪模運算。事實(shí)上在（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
如果再利用上文過(guò)程中提到積模分解公式對算法做進(jìn)一步優(yōu)化，直接把取余的運算代入到乘方中，就成為了著(zhù)名的蒙格馬利快速冪模運算法，偽代碼如下。
算法三：蒙格馬利法計算N的E次方再取D的模，令R為計算結果。
R := 1
A := N
B := E
WHILE Z != 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
蒙格馬利快速冪模運算，是目前世界上效率最高的冪模運算，很多硬件芯片在處理類(lèi)似算法時(shí)都采用的這種方法。
·尋找大素數
為了有效防止破解，必要須找到兩個(gè)很大的素數作為算法因子。而尋找大素數，是數學(xué)家們一個(gè)永恒的話(huà)題。素數的定義是只能被自己和1整除的自然數，按照常規的理解，使用計算機對一個(gè)很大的數進(jìn)行素數測試時(shí)，需要遍歷所有小于它且大于1的自然數，并逐個(gè)判斷是否能被該數整除。這個(gè)過(guò)程對于非常大的素數而言是非常緩慢的。但是根據費馬小定理，我們可以設計一種算法來(lái)快速測試素數。當A和Q互質(zhì)時(shí)，有：AQ - 1 mod Q = 1，那么，我們可以通過(guò)判斷AQ - 1 mod Q的值是否等于1對Q進(jìn)行素數測試。如果取了很多個(gè)A，Q仍未測試失敗，那么則認為Q是素數。當然，測試次數越多越準確，但一般來(lái)講50次就足夠了。另外，預先用常歸算法構造一個(gè)包括500個(gè)素數的數組，先對Q進(jìn)行整除測試，將會(huì )大大提高通過(guò)率，方法如下：
算法四：費馬定理測試可能素數P
C := 500 ;素數表大小
S[ 0 TO C ] ;素數表
B := P - 1
T := 50 ;表示進(jìn)行測試的次數
A := 0
FOR I := 0 TO C ;進(jìn)行素數表初步測試
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[
IF A ^ ( P - 1 ) mod P <> 1
RETURN FAILE
END IF
NEXT I
這個(gè)算法看起來(lái)很完美，但實(shí)際上從一開(kāi)始它就犯了一個(gè)很大的錯，那就是對于任意與Q互質(zhì)的A都有AQ - 1 mod Q = 1，這是素數的性質(zhì)，是素數成立的一個(gè)必要條件，但不是充分條件！讓我們來(lái)看一下29341這個(gè)數，它等于13 * 37 * 61，但任何與它互質(zhì)的A都有A29341 - 1 mod 29341 = 1成立。這種數字還有不少，數學(xué)上把它們稱(chēng)為卡爾麥克數，現在數學(xué)家們已經(jīng)找到所有
首先確定N是否為奇數，不是奇數的判斷失敗。
選擇T個(gè)隨機整數A，并且有 0 < A < N成立。
進(jìn)行費馬小定理測試，計算并判斷AN - 1 mod N的結果是否等于1，如果不是，則測試失敗。
找到R和M，使得N = 2R * M + 1成立。
找R和M的方式如下：
N用二進(jìn)制數B來(lái)表示，令C = B - 1。因為N為奇數，所以C的最低位為0，從C的最低位的0開(kāi)始向高位統計，一直到遇到第一個(gè)1，0的個(gè)數即為R，M為B右移R位的值。
如果AM mod N = 1，則通過(guò)B對于N的測試，然后進(jìn)行下一個(gè)A對N的測試，直到T個(gè)A對N的測試全部通過(guò)。
如果AM mod N的值不是1，那么將AM mod N式子中的AM看做底數S，我們將S乘方后再計算SM mod N的值，并判斷是否等于1，如果是則通過(guò)B對于N的測試，然后進(jìn)行下一個(gè)A對N的測試，直到T個(gè)A對N的測試全部通過(guò)；如果不是則繼續將底數乘方。
如果一直到S = A ^ 2MR時(shí)，并且SM mod N = 1仍未通測試，那么測試失敗。
通過(guò)驗證得知，當T為素數，并且A是平均分布的隨機數，那么測試有效率為1 / 4K。如果T > 50那么測試失誤的機率就會(huì )小于10-30，這對于目前的計算機硬件來(lái)說(shuō)已經(jīng)足夠證明N就是素數了。下面是偽代碼。
算法五：拉賓米勒測試法測試P是否為素數。
C := 500 ;素數表大小
S[ 0 TO C ] ;素數表
B := P - 1
T := 50 ;表示進(jìn)行測試的次數
A := 0 ;用來(lái)測試通過(guò)的隨機整數
FOR I := 0 TO C ;進(jìn)行素數表初步測試
IF P mod S[I] = 0
RETURN FAILE
END IF
IF P < S[I]
BREAK
END IF
NEXT I
M := P - 1 ;使二進(jìn)制N的最后一位變?yōu)榕紨?/span>
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 ] ;先進(jìn)行費馬測試
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
·二元一次不定方程
在算法概述的章節里我們曾經(jīng)討論過(guò)公鑰1的求法：找一個(gè)數D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。為了求D，我們先對這個(gè)方程變形。實(shí)際上這個(gè)方程可以看做AX mod B = 1，即：
AX = BY + 1，Y為一整數。
AX - BY = 1
這就是一個(gè)二元一次不定方程，有已知數A、B，未知數X、Y。我們現在需要求的是X，那么就是求這個(gè)方程對于X的最小整數解。由于方程有兩個(gè)未知數，所以必須化簡(jiǎn)方程，使得一個(gè)未知數的系數為0時(shí)才能得解。設B > A時(shí)有：
AX - BY = 1
那么可以認為B = AN + M，則有：
AX - ( AN + M )Y = 1
AX - ANY - MY = 1
A( X - NY ) - MY = 1
實(shí)際上M就是B mod A的值，設X’ = X - NY，B’ = B mod A則有AX’ - B’Y = 1，且A > M成立。接著(zhù)可以用同樣的方法來(lái)化簡(jiǎn)A，最終必能將一個(gè)系數化為0。此時(shí)求出另一個(gè)未知數的解，再按逆序代入上一步的方程，求出另一個(gè)未知數的解，再代入上一步的方程，一直遞推的第一個(gè)方程，最終即可獲得X和Y的最小整數解。因為每一步遞推的方程的余數相同，所以我們稱(chēng)這些方程為“一次同余式”。這個(gè)算法被稱(chēng)為歐幾里德擴展算法，而歐幾里德算法其實(shí)就是求公因式的輾轉相除法，大多數朋友在中學(xué)時(shí)就學(xué)過(guò)了，但是我們下面會(huì )用到，所以我這里簡(jiǎn)單的用偽代碼來(lái)描述一下歐幾里德算法。
算法六：求A和B兩相異自然數的最大公因數，另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í)會(huì )有很多步的遞歸，此時(shí)對于計算機而言就不是一個(gè)有效的算法了，那么如何才能設計一套真正對于計算機可行的大數二元一次方程的求解算法呢？
事實(shí)上我國古代數學(xué)家發(fā)明的大衍求一術(shù)，就可以非常好的解決這個(gè)問(wèn)題。我國對于余數理論的研究是十分悠久的，而且有著(zhù)卓越的成就。早在公元280到420年間問(wèn)世的《孫子算經(jīng)》中就有著(zhù)對一次同余式的問(wèn)題有了初步的討論。到了南宋時(shí)代，數學(xué)家秦九韶對此加以整理總結，發(fā)展成為一個(gè)解聯(lián)立一次同余式的系統方法，稱(chēng)為“大衍求一術(shù)”，記錄在他所著(zhù)的《九章算術(shù)》中。大衍求一術(shù)的描述是這樣的：“置奇右上，定居右下，立天元一于左上，先以右上除右下，所得商數與左上一相生，入左下，然后乃以右行上下以少除多，于互除這，所得商數隨即于互累乘，于左行上下，須使右上末后奇一而止。乃驗左上所得以為乘率，或奇數已見(jiàn)單一者便為乘率”。這句話(huà)的意思我用偽代碼描述如下。
算法七：已知有自然數N和素數P，N > 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
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
·結語(yǔ)
到現在，RSA算法中所涉及到的所有算法我們都已經(jīng)討論過(guò)了。實(shí)際還有一個(gè)運算，就是私鑰的獲得辦法：計算得到與( P - 1 ) * ( Q - 1 )的值互質(zhì)的整數E。我情愿不把它稱(chēng)之為算法，因為只需要一個(gè)循環(huán)和一個(gè)判斷就可以完成，所以這里也就沒(méi)有必要對它多加論述了。
·附錄
費馬小定理的證明：
引理1：設M，A的最大公約數( M，A ) = 1，且M整除AB，即M mod AB = 0，則M mod B = 0。
引理2：設P是素數，<P，J>表示組合數，即從P個(gè)數中選出J個(gè)數的組合種數，且1 ≤ J ≤ P - 1，則P mod <P，J>。
聯(lián)系客服
