RSA加密算法初探

1、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í)并不難。 文中的算法均為偽代碼，由于偽代碼沒有辦法進(jìn)行測試，再加上我個(gè)人數(shù)學(xué)功底比較薄弱，所以錯(cuò)漏之處在所難免，還請各位老師給予指教。質(zhì)疑或指正請發(fā)送電子郵件到，我會認(rèn)真閱讀并回復(fù)的！ 感謝北航數(shù)學(xué)系（畢業(yè)）李楨老師、西工大計(jì)算機(jī)系（畢業(yè)）張小寧老師

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

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

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

5、與 ( P - 1 ) * ( Q - 1 ) 的值互質(zhì)，這個(gè)E就是私鑰。找到一個(gè)整數(shù)D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立1，D就是公鑰1。設(shè)N為P和Q的乘積，N則為公鑰2。加密時(shí)先將文轉(zhuǎn)換為一個(gè)或一組小于N的整數(shù)I，并計(jì)算ID mod N的值M，M就密文。解密時(shí)將密文ME 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，必須

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

7、 費(fèi)馬小定理可變形為： NP - N mod P = 0 ( N ( NP - 1 - 1 ) ) mod P = 0 因?yàn)?( N ( NP - 1 - 1 ) ) mod N = 0 所以N和P的公倍數(shù)為： N ( NP - 1 - 1 )（1） 又因?yàn)镹與P互質(zhì)，而互質(zhì)數(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）就是費(fèi)馬小定理的轉(zhuǎn)化定理，為方便敘述，下文簡稱為定理一。小提示，可

8、能很多人認(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 ) ) mo

9、d Z ( Z( ZIJ + IA + IB ) + AB ) mod Z（3） 因?yàn)閆( ZIJ + IA + IB )是Z的整數(shù)倍，所以（3）式可化簡為： AB mod Z 因?yàn)锳和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)锳 = X mod Z， 又因?yàn)閅 mod Z = Y，所以有： ( X * Y ) mod Z = ( (

10、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)镻和Q互質(zhì)，所以它們的公倍數(shù)為KPQ（K為整數(shù)），最小公倍數(shù)為PQ。又因?yàn)閄為P和Q的公倍數(shù)，所以X / PQ = K，所以X mo

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

12、- 1 ) = 1。有正整數(shù)A，且A < PQ，設(shè)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） 因?yàn)橛? 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時(shí)，明顯有B = A。 如果ARM > PQ，且A不是P的倍數(shù)也不是Q的倍數(shù)時(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） 因?yàn)镻為素?cái)?shù)，所以A和P互質(zhì)。根據(jù)定理一，有AP - 1 mod P = 1成立 兩邊同乘K ( Q - 1 )次方 ( AP - 1 mod P )K ( Q - 1 ) = 1 1關(guān)于任何正整數(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 因?yàn)锳 < PQ，所以B = A成立 在述證明過程中可以總結(jié)一點(diǎn)： 當(dāng)P為素?cái)?shù)且A和P互質(zhì)時(shí)，那么當(dāng)N為任意自然數(shù)時(shí)都有AN( P - 1 ) mod P = 1成立，這個(gè)定理下面還要用到，我們稱

15、之為定理四。 如果ARM > PQ，且A不是P的倍數(shù)而是Q的倍數(shù)時(shí)，（一些證明過程如上，此項(xiàng)情況的證明過程就不再贅述了）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 用積模分解公式進(jìn)行分解

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 因?yàn)锳 < PQ，所以B = A成立 同理，當(dāng)A是P的倍數(shù)而不是Q的倍數(shù)時(shí)，B = A也成立。 因?yàn)锳小于

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

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

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

20、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ì)算A13時(shí)，如果讓A直接進(jìn)行連乘，需要12次運(yùn)算。但是如果把A * A的值保存起來，我們就只需要進(jìn)行B = A * A和B * B * B * B * B * B * A，一共七次運(yùn)算，如果我們再把B * B的值保存起來，那我們就只需要進(jìn)行B = A * A、C = B * B、D = C * C、 D * C

21、 * 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用來存儲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 再回到我們剛才討論的冪模運(yùn)算。事實(shí)上在（1）式中，我們需要求出的就是( N mod D )R的值，

22、那么只要令上面?zhèn)未a中參量N的值為N mod D，并對結(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 如果再利用上文過程中提到積模分解公式對算法做進(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 :

23、= 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ī)對一個(gè)很大的數(shù)進(jìn)行素?cái)?shù)測試時(shí)，需要遍歷所有小于它且大于1的自然數(shù)，并逐個(gè)判斷是否能被該數(shù)整除。這個(gè)過程對于非常大的素?cái)?shù)而言是非常緩慢的。但是根據(jù)費(fèi)馬小定理，我們可

24、以設(shè)計(jì)一種算法來快速測試素?cái)?shù)。當(dāng)A和Q互質(zhì)時(shí)，有：AQ - 1 mod Q = 1，那么，我們可以通過判斷AQ - 1 mod Q的值是否等于1對Q進(jìn)行素?cái)?shù)測試。如果取了很多個(gè)A，Q仍未測試失敗，那么則認(rèn)為Q是素?cái)?shù)。當(dāng)然，測試次數(shù)越多越準(zhǔn)確，但一般來講50次就足夠了。另外，預(yù)先用常歸算法構(gòu)造一個(gè)包括500個(gè)素?cái)?shù)的數(shù)組，先對Q進(jìn)行整除測試，將會大大提高通過率，方法如下： 算法四：費(fèi)馬定理測試可能素?cái)?shù)P C := 500;素?cái)?shù)表大小 S 0 TO C ;素?cái)?shù)表 B := P - 1 T := 50;表示進(jìn)行測試的次數(shù) A := 0 FOR I := 0 TO C;進(jìn)行素?cái)?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 這個(gè)算法看起來很完美，但實(shí)際上從一開始它就犯了一個(gè)很大的錯(cuò)，那就是對于任意與Q互質(zhì)的A都有AQ - 1 mod Q = 1，這是素?cái)?shù)的性質(zhì)，是素?cái)?shù)成立的一個(gè)必要條件，但不是充分條件！讓我們來看一下29341這個(gè)數(shù)，它等于13 * 37 * 61，但任何與它互質(zhì)的

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

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

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

29、 < SI 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 Y := 0FOR I := 0 TO T A := S RAND() mod C ;先進(jìn)行費(fèi)馬測試 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é)里我們曾經(jīng)討論過公鑰1的求法：找一個(gè)數(shù)D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。為了求D，我們先對這個(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è)方程

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

32、一個(gè)方程，最終即可獲得X和Y的最小整數(shù)解。因?yàn)槊恳徊竭f推的方程的余數(shù)相同，所以我們稱這些方程為“一次同余式”。這個(gè)算法被稱為歐幾里德擴(kuò)展算法，而歐幾里德算法其實(shí)就是求公因式的輾轉(zhuǎn)相除法，大多數(shù)朋友在中學(xué)時(shí)就學(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 歐幾里德擴(kuò)展算法雖然容易理解，但當(dāng)A和B較大時(shí)會有很多步的遞歸，此時(shí)對于計(jì)算機(jī)而言就不是一個(gè)有效的算法了，那么如何才能設(shè)計(jì)一套真正對于計(jì)算機(jī)可行的大數(shù)二元一次方程的求解算法呢？ 事實(shí)上我國古代數(shù)學(xué)家發(fā)明的大衍求一術(shù)，就可以非常好的解決這個(gè)問題。 我國對于余數(shù)理論的研究是十分悠久的，而且有著卓越的成就。早在公元280到420年間問世的孫子算經(jīng)中就有著對一次同余式的問題有了初步的討論。到了南宋時(shí)代，數(shù)學(xué)家秦九韶對此加以整理總結(jié)，發(fā)展成為一個(gè)解聯(lián)立一次同余式的系統(tǒng)方法，稱為“大衍求一術(shù)”，記錄在他所著的九章算術(shù)中。大衍求一術(shù)的描述是這