【文章內(nèi)容簡介】 的結(jié)果是未知的。我們用乘法性質(zhì)和模性質(zhì)做特殊處理。乘法性質(zhì)：49022*words[i]* 10i其中：words[i] = {2，2，0，9，4} ，i 是 49022 的位數(shù)。再利用模的性質(zhì)：(a + b )mod n = ((a mod n) + (b mod n)) mod n(a*b) mod n = (a mod n )*(b mod n) mod n盡可以把 a*c，a*a 的范圍縮的很小。這樣中間結(jié)果就不會超出整數(shù)范圍。 乘法逆元 如果 [1] ，則 如果 a 與 n 互素()modab??odb? 例如：為了說明這一點，考慮一個附加條件不滿足的例子： 63＝18 28 67＝42 od?但 。?造成這個奇怪結(jié)果的原因是對于乘數(shù) a，模 n 的乘法運(yùn)算返回的結(jié)果是 0 到 n1之間的數(shù)，如果 a 和 n 有除 1 以外的共同因子時將不會產(chǎn)生完整的余數(shù)集合。例如：取 a = 6 和 n = 8； 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識14因為乘以 6 的模 8 運(yùn)算不會產(chǎn)生完整的余數(shù)集． 中的多個數(shù)將映射到同一個余8z數(shù)上。如： 60mod4??185因為這是一個多對一的映射，對乘法運(yùn)算不存在惟一的逆元。 然而，如果取 a = 5, n = 8 ：余數(shù)行以不同的順序包含了 集合中所有的數(shù)。最后，還可觀察到如果 P 是一個8z素數(shù)．則集合中的所有數(shù)均與 p 互素 。 這樣就能在之前所列的性質(zhì)中再加上一條性質(zhì)： 乘法逆元( )對每一個 ，存在一個 z，使得1w?pz?1modwzp??因為 與 P 互素，如果用 乘以 中的所有數(shù)模 P，得到的余數(shù)將以不同次序涵蓋 中的所有數(shù)。那么，至少有一個余數(shù)的值為 1。因此，在 中的某個數(shù)與 相乘pz pw模 p 的余數(shù)為 1。這個數(shù)就是 的乘法逆元，命名為 。這樣．等式：?()odab??與存在乘法逆元是一致的。對上等式的兩邊乘以 a 的乘法逆元，有：11()()m??odb?最后一點：某些整數(shù)但不是全部整數(shù)存在一個乘法逆元就將使模數(shù)不是一個素數(shù)。如果如 gcd(a,n)= 1，則能在 中找到 b，使得：nz1odap?原因與前一段是相同的。因為 a 與 n 互素，如果用 a 與 中的所有數(shù)相乘模 n，得到的nz余數(shù)將以不同次序涵蓋 中的所有數(shù)。因此在 中存在某個數(shù) b，使得：nzn1modbp? 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識15 RSA 中重要定理 費(fèi)馬定理費(fèi)馬定理可表述為：如果 p 是素數(shù)，a 是個不能被 p 整除的正整數(shù)，則：1modp??證明 [1]：從以前的討論得出，如果 中的所有數(shù)均與 a 相乘模 p，結(jié)果將以某種z次序涵蓋 中的數(shù)。并且 ：pz 0odap?因此，(p —1)個數(shù)：}{mod,2,.(1)mapa?恰好是某種次序的{1,2,…,(p1)}。將這些數(shù)相乘可得：2.(1)[()(od).()od)]a pp????? !odp但 ： 12.(1)()!papa????因此 1()!()!modp??可在兩端去掉(p1)!，因為它與 p 互素，這可以得到費(fèi)馬定理。例如 ：a = 7,p = 19 24816816279od1m771od9pa?????費(fèi)馬定理的另一種等價形式也很有用：如果 p 是素數(shù),a 是任意正整數(shù)，則 ：ma 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識16 歐拉定理在引入歐拉定理之前，需首先介紹數(shù)論中的一個重要的量，即歐拉函數(shù) (Euler’s totient function ),記為 ， 表示小于 n 的且與 n 互素的正整數(shù)個數(shù)。()n?例如；下表列出了 30 以內(nèi)的整數(shù)的 值， 被定義為 1，但沒有實際意義。()?()某些歐拉函數(shù)的值很顯然，對于一個素數(shù) p，有： ()1p???現(xiàn)假定有兩個不同的素數(shù) p 和 q， 則對 n=q*p，有：()nqp?? (1)??為了證明這一命題 [1]，考慮 的完全余數(shù)集為：nz{0,1,2,…,(p q1)}?而不與 n 互素的余數(shù)包括 0 和集合{p,2p,…,(q1)p}{q,2q,…,(p1)1}因此，有 ： ()[(1)]npqp???? 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識17 (1)pq??? ?歐拉定理可表述為對于任何互素的整數(shù) a 和 n，有：()1mod??例如 ：a = 3。n = 10。 = 4。(10)?438od??證明：如果 n 為素數(shù)，則等式 為真，因為此時()mna?1?根據(jù)費(fèi)馬定理可證。然而，對于其他任意整數(shù)，它也成文： 表示不小于 n 且與 n 互素的正整數(shù)個數(shù)，()n?假定這樣的整數(shù)集合標(biāo)記如下： 12(){,.}nRx?? 現(xiàn)在對該集合中的每個整數(shù)乘以 a 模 n：12(){(mod),(),.mod}nsxax? 集合 s 是集合 R 的—個置換，原因如下：1. 因為 a 與 n 互素， 也與 n 互素，則 一定與 n 互素。因此，S 中的所有數(shù)均小于i ixn 且與 n 互素。2. 有 s 個不存在重復(fù)的整數(shù)。根據(jù)等式：如果 ，則 如果 a 與 n 互素()modab??odb?如果： ijaxx?則 ： 。ijx?因此 ：()()11modnni iiax????? ()()11)nniiix?????? ()()()11od)nniiax??? 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識18()1modna??歐拉定理的另一種等價形式也很有用： ()1mod)na???歐拉定理的推論在說明 RSA 算法的有效時是很有用的。給定兩個素數(shù) p 和 q，以及整數(shù) n=p*q 和 m,其中 0mn，則下面關(guān)系成立 ：()1()1odnpqn???????如果如 gcd(m,n)=1，即如果 m 和 n 互素，則根據(jù)歐拉定理上面等式顯然成立。假設(shè)gcd(m，n) 1，這意味著什么 ?因為 n＝p*q，等式 gcd(m，n)=1 等價于邏輯表達(dá)式(m?不是 p 的倍數(shù))和(n 不是 q 的倍數(shù))。如果 m 是 p 的倍數(shù)．則 m 和 n 有公因子 p，因而不可能是互素的。同樣．如果 m 是 q 的倍數(shù)，則 m 和 n 有公因子 q，因而也不可能是互素的。因此，表達(dá)式 gcd(m，n) 1 必須等價于前面邏輯表達(dá)式的非，故 gcd(m，n)?1 等價于(m 是 p 的倍數(shù))或者(m 是 q 的倍數(shù)) 。?下面討論一下 m 是 p 倍數(shù)的情況，顯然 m=c*p，c 為某個正整數(shù)。在這種情況下．必然有 gcd(m，n) 1。有 m 是 p 倍數(shù)，也是 q 的倍數(shù)，但 mp*q。如果 gcd(m，q)=1，則根據(jù)歐拉定理并且： ()1odq??但根據(jù)模運(yùn)算的規(guī)則，有 ： ()[]qpm?1odn因此，存在某個整數(shù) k 使得： ()nkq????在等式兩邊同乘 m＝cp，有： ()1nmcpn??()od?m 是 q 的倍數(shù)的情況也可采用類似的方法得出，故等式： ()1()1npqn??????得證。這個推論的另一等價形式也很有用。 ()[]modnk?1??()()1odknkpqn????? 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識19 歐幾里德算法歐幾里德算法是數(shù)論中的一項基本技術(shù)，它通過簡單的過程來確定兩個正整數(shù)的最大公因子。擴(kuò)展的歐幾里德算法不僅能確定兩個正整數(shù)的最大公出于，如果這兩個數(shù)互素，還能確定它們各自的乘法逆元。歐幾里德算法基于下面的定理 [1]：對任何非負(fù)整數(shù) a 和非負(fù)整數(shù) bgcd(,)(,mod)abb?例如： c(5,2)52 (,1) 證明 [1]：假定 d 。根據(jù) 的定義，有 和 。對任何正整數(shù) b，ag(,)ab?gcd|da|b可表示為如下形式： mokbr????da因此，有： obk?其中 k 為某個整數(shù)。但由于 ，b 也能整除 kb，而 ，故有：|d|da|(m)a這表明 d 也是 b 和 的公因子。由于這是可逆的，如果 d 是(o)b 和 的公因子，那么 ，且 ，這等同于 。這樣 a 和 b(mo)a|k|[(od)]db?|b的公因子集合等同于 b 和 的公因子集合。因此它們的最大公因子相同。定理()a得證?？芍貜?fù)使用等式： gcd(,)(,mod)abab?來求出最大公因子。 例如： gcd(18,2)c(,6)gcd(,0)6?011?下面的歐幾里德算法重復(fù)使用等式： gcd(,)(,mod)abab 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識20來求出最大公因子。算法假定 。限制算法僅考慮正整數(shù)是可以接受的，0df?因為 ： gc(,)d(|,|)abb?EUCLID(d,f)，即 d 和 f 的最大公因子例如： 1) 。xyf? 2)if return 0?gcd(,)xf 3) mor 4) xy 5) 6)goto 2 要找出 (1970,6) 462451298686014620????????? gcd(106,94)2,(8)gcd6,21(,0)gcd6,4(2),0因此 ： gcd(197,6)2? 我們會發(fā)現(xiàn)這個過程是在 中 時停止的（ 為正整數(shù)） ，即如何確gcd(,)iabi?i定在某一點上 整除 ?如果不能，這就將得到一個無窮盡的正整數(shù)序列，序列中每一yx個均比前面的整數(shù)小，這顯然是不可能的。如果 ： gcd(,)1f?那么 d 有一個模 f 的乘法逆元。即對小于 f 的正整數(shù) d，存在一個小于 f 的整數(shù) ，使1d?得 ： 1modf?? 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識21對歐幾里德算法進(jìn)行擴(kuò)展使得它不僅能找出 ，如果 ，算法還能返gcd(,)fgcd(,)1f?回 d 的乘法逆元。EXTENDED EUCLIB(d,f)(語言描寫)1) (1,23)(,0。1,23(0,1)xfyd?2) if return ；無逆元y?gcd()xf3) if return ；,?1moyf??4) 3xQy????5) (1,2)(1,2,3)tyxQxy????6) 3)x?7) (,3)(,yt8) goto 2VC++的描述 ：long CRsaMY::euclib(long x, long y) //求乘法逆元，或者私鑰，擴(kuò)展歐幾里德算法{long x1,x2,x3。 long y1,y2,y3。long t1,t2,t3。long m,d。 x1 = 1。 x2 = 0。 x3 = y。 y1 = 0。 y2 = 1。 y3 = x。if(gcd(x,y) == 1){ 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識22while(y3 != 1) { m = x3 / y3。 t1 = x1 m*y1。 t2 = x2 m*y2。 t3 = x3 m*y3。 x1 = y1。 x2 = y2。 x3 = y3。 y1 = t1。 y2 = t2。 y3 = t3。}}d = y2。 if(d 0)return d。else return d = y + d。}結(jié)果分析 ：d 是要求的私鑰。通過計算，廠面的關(guān)系成立： 123ftdt???xxfyy下面說明算法能正確返回 。如果將歐幾里德算法中的 和看 作是擴(kuò)展gcd(,) xy歐幾里德算法中的 和 ，那么這兩個變量的處理是完全相同的。在歐幾里德算法的3xy每次迭代中， 被設(shè)置為前一個 值，而 被設(shè)置為前一個 。同樣．在擴(kuò)展的ymod歐幾里德算法中，x3 被設(shè)置為前一個 值，而 被設(shè)置為前一個 減大 除以 的33x3y商，后一個數(shù)即為 除以 所得的余數(shù)，然后再乘以 ，也就是 。3xyy 學(xué)院理學(xué)學(xué)士學(xué)位論文 第二章 RSA 加密算法的有關(guān)數(shù)學(xué)知識23另外，如果 ，則最后一個步驟可得 =0 且 =1。因此在之前的步驟