RSA加密算法初探

·前言

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

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

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

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

·概述

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

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

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

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

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

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

·證明

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

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

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

N^P mod P = N

費(fèi)馬小定理可變形為：

N^{P - N} mod P = 0

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

因?yàn)?/span>

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

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

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

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

N^{P - 1} - 1 = MP

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

可以變形為：

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

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

二、積模分解公式

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

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

證明如下

當(dāng)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）

因?yàn)?/span>Z( ZIJ + IA + IB )是Z的整數(shù)倍，所以（3）式可化簡(jiǎn)為：

AB mod Z

因?yàn)?/span>A和B實(shí)際上是X和Y分別除以Z的余數(shù)，所以有：

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

當(dāng)X比Z大而Y比Z小時(shí)

X = ZI + A

代入( X * Y ) mod Z得：

( ZIY + AY ) mod Z

AY mod Z

因?yàn)?/span>A = X mod Z，又因?yàn)?/span>Y mod Z = Y，所以有：

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

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

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

證明：

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

四、定理三

有P和Q兩個(gè)互質(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整除。又因?yàn)?/span>P、Q互質(zhì)，根據(jù)定理二可得：

( Y - X ) mod PQ = 0

即

Y mod PQ = X

五、定理三的逆定理

有P和Q兩個(gè)互質(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是兩個(gè)相異質(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）

因?yàn)橛?/span>( 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時(shí)，明顯有B = A。

如果A^RM > PQ，且A不是P的倍數(shù)也不是Q的倍數(shù)時(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ù)費(fèi)馬小定理可得：

( 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

因?yàn)?/span>A < PQ，所以B = A成立。

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

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

如果A^RM > PQ，且A不是P的倍數(shù)而是Q的倍數(shù)時(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

用積模分解公式進(jìn)行分解，得：

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

因?yàn)?/span>A < PQ，所以B = A成立

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

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

RSA定理成立。

·大整數(shù)存儲(chǔ)運(yùn)算

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

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

·冪模運(yùn)算

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

N^R mod D = ( ( N mod D )^R ) mod D                    （1）

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

D * C * A，一共五次運(yùn)算?？偨Y(jié)這個(gè)規(guī)律可以發(fā)現(xiàn)，運(yùn)算過程中如果某次的冪數(shù)為奇數(shù)時(shí)，在乘方過后還需要乘以上次保留的積。跟據(jù)這個(gè)規(guī)律，我們把運(yùn)算分為兩部分的乘積，下面是偽代碼。

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

R := N           ; R用來存儲(chǔ)2ⁿ

K := 1           ; K用于存儲(chǔ)另一部分的乘積

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

再回到我們剛才討論的冪模運(yùn)算。事實(shí)上在（1）式中，我們需要求出的就是( N mod D )^R的值，那么只要令上面?zhèn)未a中參量N的值為N mod D，并對(duì)結(jié)果R求R mod D就可以了，下面是基于上面求乘方算法的冪模運(yùn)算的偽代碼。

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

R := N mod D

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

R := R % D

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

算法三：蒙格馬利法計(jì)算N的E次方再取D的模，令R為計(jì)算結(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

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

·尋找大素?cái)?shù)

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

算法四：費(fèi)馬定理測(cè)試可能素?cái)?shù)P

C := 500              ;素?cái)?shù)表大小

S[ 0 TO C ]         ;素?cái)?shù)表

B := P - 1

T := 50          ;表示進(jìn)行測(cè)試的次數(shù)

A := 0

FOR I := 0 TO C               ;進(jìn)行素?cái)?shù)表初步測(cè)試

       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

這個(gè)算法看起來很完美，但實(shí)際上從一開始它就犯了一個(gè)很大的錯(cuò)，那就是對(duì)于任意與Q互質(zhì)的A都有A^{Q - 1} mod Q = 1，這是素?cái)?shù)的性質(zhì)，是素?cái)?shù)成立的一個(gè)必要條件，但不是充分條件！讓我們來看一下29341這個(gè)數(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ù)，最大的一個(gè)是9585921133193329。我們必須尋找更為有效的測(cè)試方法。數(shù)學(xué)家們通過對(duì)費(fèi)馬小定理的研究，并加以擴(kuò)展，總結(jié)出了多種快速有效的素?cái)?shù)測(cè)試方法，目前最快的算法是拉賓米勒測(cè)試算法，其過程如下：

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

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

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

找到R和M，使得N = 2^R * M + 1成立。

找R和M的方式如下：

N用二進(jìn)制數(shù)B來表示，令C = B - 1。因?yàn)?/span>N為奇數(shù)，所以C的最低位為0，從C的最低位的0開始向高位統(tǒng)計(jì)，一直到遇到第一個(gè)1，0的個(gè)數(shù)即為R，M為B右移R位的值。

如果A^M mod N = 1，則通過B對(duì)于N的測(cè)試，然后進(jìn)行下一個(gè)A對(duì)N的測(cè)試，直到T個(gè)A對(duì)N的測(cè)試全部通過。

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

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

通過驗(yàn)證得知，當(dāng)T為素?cái)?shù)，并且A是平均分布的隨機(jī)數(shù)，那么測(cè)試有效率為1 / 4^K。如果T > 50那么測(cè)試失誤的機(jī)率就會(huì)小于10^-30，這對(duì)于目前的計(jì)算機(jī)硬件來說已經(jīng)足夠證明N就是素?cái)?shù)了。下面是偽代碼。

算法五：拉賓米勒測(cè)試法測(cè)試P是否為素?cái)?shù)。

C := 500              ;素?cái)?shù)表大小

S[ 0 TO C ]         ;素?cái)?shù)表

B := P - 1

T := 50          ;表示進(jìn)行測(cè)試的次數(shù)

A := 0            ;用來測(cè)試通過的隨機(jī)整數(shù)

FOR I := 0 TO C               ;進(jìn)行素?cái)?shù)表初步測(cè)試

       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)榕紨?shù)

R := 0

WHILE M & 1 = 0            ;一直到有某一位為1為止

       M := M >> 1

       R := R + 1            ;計(jì)算R

NEXT

X := 0

FOR I := 0 TO T

       A := S[ RAND() mod C ]          ;先進(jìn)行費(fèi)馬測(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é)里我們?cè)?jīng)討論過公鑰1的求法：找一個(gè)數(shù)D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。為了求D，我們先對(duì)這個(gè)方程變形。實(shí)際上這個(gè)方程可以看做AX mod B = 1，即：

AX = BY + 1，Y為一整數(shù)。

AX - BY = 1

這就是一個(gè)二元一次不定方程，有已知數(shù)A、B，未知數(shù)X、Y。我們現(xiàn)在需要求的是X，那么就是求這個(gè)方程對(duì)于X的最小整數(shù)解。由于方程有兩個(gè)未知數(shù)，所以必須化簡(jiǎn)方程，使得一個(gè)未知數(shù)的系數(shù)為0時(shí)才能得解。設(shè)B > A時(shí)有：

AX - BY = 1

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

AX - ( AN + M )Y = 1

AX - ANY - MY = 1

A( X - NY ) - MY = 1

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

算法六：求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

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

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

算法七：已知有自然數(shù)N和素?cái)?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)討論過了。實(shí)際還有一個(gè)運(yùn)算，就是私鑰的獲得辦法：計(jì)算得到與( P - 1 ) * ( Q - 1 )的值互質(zhì)的整數(shù)E。我情愿不把它稱之為算法，因?yàn)橹恍枰粋€(gè)循環(huán)和一個(gè)判斷就可以完成，所以這里也就沒有必要對(duì)它多加論述了。

·附錄

費(fèi)馬小定理的證明：

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

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