第四章_公鑰密碼-new

1、信息信息安全理論及應(yīng)用安全理論及應(yīng)用第第4章章 公鑰密碼公鑰密碼1.公鑰密碼體制簡(jiǎn)介公鑰密碼體制簡(jiǎn)介2. 常用數(shù)論知識(shí)常用數(shù)論知識(shí)3. RSA算法算法4. Rabin密碼體制密碼體制5. 橢圓曲線密碼體制橢圓曲線密碼體制信息信息安全理論及應(yīng)用安全理論及應(yīng)用1.1 公鑰密碼體制簡(jiǎn)介公鑰密碼體制簡(jiǎn)介對(duì)稱密碼體制：對(duì)稱密碼體制：保密性，運(yùn)算速度快，適合加密保密性，運(yùn)算速度快，適合加密 大量數(shù)據(jù)大量數(shù)據(jù)公鑰密碼體制：公鑰密碼體制：保密性，密鑰分配，認(rèn)證；運(yùn)算保密性，密鑰分配，認(rèn)證；運(yùn)算 速度慢，適合加密少量數(shù)據(jù)。如：速度慢，適合加密少量數(shù)據(jù)。如： 用公鑰密碼加密傳送分組密碼的密鑰。用公鑰密碼加密傳送分

2、組密碼的密鑰。(1) 公鑰密碼體制與對(duì)稱密碼體制比較公鑰密碼體制與對(duì)稱密碼體制比較:信息信息安全理論及應(yīng)用安全理論及應(yīng)用公鑰密碼的理論基礎(chǔ)公鑰密碼的理論基礎(chǔ): 陷門單向函數(shù)陷門單向函數(shù)單向函數(shù)單向函數(shù): 已知已知x, 計(jì)算計(jì)算y使得使得y=f(x)容易容易; 已知已知y, 計(jì)算計(jì)算x使得使得y=f(x)是難解的。是難解的。陷門單向函數(shù)陷門單向函數(shù): t是與是與f有關(guān)的一個(gè)參數(shù)有關(guān)的一個(gè)參數(shù) 已知已知x, 計(jì)算計(jì)算y使得使得y=f(x)容易容易; 如果不知道如果不知道t，已知已知y, 計(jì)算計(jì)算x使得使得y=f(x)是難的，是難的， 但知道但知道t時(shí)，已知時(shí)，已知y, 計(jì)算計(jì)算x使得使得y=f(x

3、)是容易的。是容易的。 參數(shù)參數(shù)t稱為陷門（稱為陷門（Trapdoor）。信息信息安全理論及應(yīng)用安全理論及應(yīng)用最大特點(diǎn)是采用兩個(gè)相關(guān)密鑰將加密和解密能力分最大特點(diǎn)是采用兩個(gè)相關(guān)密鑰將加密和解密能力分開，其中一個(gè)密鑰是公開的，稱為公開密鑰，簡(jiǎn)稱公開開，其中一個(gè)密鑰是公開的，稱為公開密鑰，簡(jiǎn)稱公開鑰，用于加密；另一個(gè)密鑰是為用戶專用，因而是保密鑰，用于加密；另一個(gè)密鑰是為用戶專用，因而是保密的，稱為秘密密鑰，簡(jiǎn)稱秘密鑰，用于解密。的，稱為秘密密鑰，簡(jiǎn)稱秘密鑰，用于解密。公鑰密碼體制也稱為公鑰密碼體制也稱為雙鑰密碼體制或非對(duì)稱密碼體制雙鑰密碼體制或非對(duì)稱密碼體制。算法有以下重要特性：算法有以下重要特

4、性： 已知密碼算法和加密密鑰，求解密密鑰在計(jì)算上是已知密碼算法和加密密鑰，求解密密鑰在計(jì)算上是不可行的。不可行的。(2) 公鑰密碼體制的原理公鑰密碼體制的原理信息信息安全理論及應(yīng)用安全理論及應(yīng)用圖圖4.1 公鑰體制加密的框圖公鑰體制加密的框圖信息信息安全理論及應(yīng)用安全理論及應(yīng)用公鑰密碼算法應(yīng)滿足以下要求公鑰密碼算法應(yīng)滿足以下要求: 接收方接收方B產(chǎn)生密鑰對(duì)（產(chǎn)生密鑰對(duì)（PKB和和SKB）在計(jì)算上是在計(jì)算上是容易的。容易的。 發(fā)方發(fā)方A對(duì)消息對(duì)消息m加密以產(chǎn)生加密以產(chǎn)生密文密文c，即即c=EPKBm在計(jì)算上是容易的。在計(jì)算上是容易的。 收方收方B用自己的秘密鑰對(duì)用自己的秘密鑰對(duì)c解密，即解密，即

5、m=DSKBc在在計(jì)算上是容易的。計(jì)算上是容易的。(3) 公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足的要求信息信息安全理論及應(yīng)用安全理論及應(yīng)用 敵手?jǐn)呈钟捎蒔KB求求SKB在計(jì)算上是不可行的。在計(jì)算上是不可行的。 敵手由敵手由密文密文c和和PKB恢復(fù)明文恢復(fù)明文m在計(jì)算上是不可在計(jì)算上是不可行的。行的。以上要求的本質(zhì)之處在于要求一個(gè)陷門單向函數(shù)。以上要求的本質(zhì)之處在于要求一個(gè)陷門單向函數(shù)。因此，研究公鑰密碼算法就是要找出合適的陷門單因此，研究公鑰密碼算法就是要找出合適的陷門單向函數(shù)。向函數(shù)。信息信息安全理論及應(yīng)用安全理論及應(yīng)用數(shù)論是密碼學(xué)特別是公鑰密碼學(xué)的基本工具，本章數(shù)論是密碼學(xué)特別是公鑰密

6、碼學(xué)的基本工具，本章首先介紹密碼學(xué)中常用的一些數(shù)論知識(shí)，然后介紹首先介紹密碼學(xué)中常用的一些數(shù)論知識(shí)，然后介紹公鑰密碼體制幾種重要算法。公鑰密碼體制幾種重要算法。信息信息安全理論及應(yīng)用安全理論及應(yīng)用1.2 常用數(shù)論知識(shí)常用數(shù)論知識(shí)1. 費(fèi)爾瑪定理和歐拉定理費(fèi)爾瑪定理和歐拉定理2. 素性檢驗(yàn)素性檢驗(yàn): Miller-Rabin的素性概率檢測(cè)法的素性概率檢測(cè)法3. 廣義歐幾里得除法廣義歐幾里得除法4. 中國(guó)剩余定理中國(guó)剩余定理5. 離散對(duì)數(shù)離散對(duì)數(shù)6. 平方剩余平方剩余信息信息安全理論及應(yīng)用安全理論及應(yīng)用定理定理4.1 設(shè)設(shè)aZn，gcd(a, n)=1，則則a在在Zn中有乘法逆元。中有乘法逆元。證

7、明：證明： 首先證明首先證明a與與Zn中任意兩個(gè)不相同的數(shù)中任意兩個(gè)不相同的數(shù)b、c（不妨設(shè)不妨設(shè)cb）相乘，其結(jié)果必然不同。相乘，其結(jié)果必然不同。 否則設(shè)否則設(shè)abac mod n，則則存在兩個(gè)整數(shù)存在兩個(gè)整數(shù)k1,k2，使得使得ab=k1n+r，ac=k2n+r，可得可得a(b-c)=(k1-k2)n，所以所以a是是(k1-k2)n的一個(gè)因子。又由的一個(gè)因子。又由gcd(a，n)=1，得得a是是k1-k2的的一個(gè)因子，設(shè)一個(gè)因子，設(shè)k1-k2=k3a，所以所以a(b-c)=k3an，即即b-c=k3n，與與0cb0. 則則存在唯一的整數(shù)存在唯一的整數(shù)q, r使得使得 a=bq+r, 0 r

8、b信息信息安全理論及應(yīng)用安全理論及應(yīng)用廣義廣義歐幾里得歐幾里得除法除法設(shè)設(shè)a, b是任意兩個(gè)正整數(shù)是任意兩個(gè)正整數(shù), 記記 r0=a, r1=b, 用用歐幾里得歐幾里得除法除法:1221100,rrrqrr 2332210,rrrqrr 11120, nnnnnnrrrqrr0,111 nnnnnrrqrrbrrrrrnnn 12110定理定理4 設(shè)設(shè)a, b是任意兩個(gè)正整數(shù)是任意兩個(gè)正整數(shù), 則則 (a, b)=rn信息信息安全理論及應(yīng)用安全理論及應(yīng)用定理定理 設(shè)設(shè)a, b是任意兩個(gè)正整數(shù)是任意兩個(gè)正整數(shù), 則則 (a, b)=rn1221100,rrrqrr 2332210,rrrqrr

9、11120, nnnnnnrrrqrr0,111 nnnnnrrqrr證證),(),(2rbba ),(32rr),(1nnrr nnnnrrrr ) 0 ,(),(1信息信息安全理論及應(yīng)用安全理論及應(yīng)用1102qrrr 2213qrrr 112 nnnnqrrr1221100,rrrqrr 2332210,rrrqrr 11120, nnnnnnrrrqrr0,111 nnnnnrrqrrr0=a, r1=b有有s, t 滿足滿足 s a + t b =(a, b) 信息信息安全理論及應(yīng)用安全理論及應(yīng)用定理定理 整數(shù)整數(shù)a, b互素互素 存在整數(shù)存在整數(shù) s, t 滿足滿足 s a + t

10、b =1證證: 必要性顯然必要性顯然。充分性：已知充分性：已知s a + t b =1，則則a, b互素互素 設(shè)設(shè) d=(a, b), 則則d|a, d|b, 有有d | s a + t b =1，則則d=1, 故故a, b互素互素 求乘法逆元：求乘法逆元：如果如果gcd(a, b)=1 ，則則b在在mod a下有乘法逆元下有乘法逆元, 即即存在一存在一x (xa)，使得使得bx1 mod a。信息信息安全理論及應(yīng)用安全理論及應(yīng)用 中國(guó)剩余定理是數(shù)論中最有用的一個(gè)工具，中國(guó)剩余定理是數(shù)論中最有用的一個(gè)工具，定理說如果已知某個(gè)數(shù)關(guān)于一些兩兩互素的數(shù)的同定理說如果已知某個(gè)數(shù)關(guān)于一些兩兩互素的數(shù)的同

11、余類集，就可重構(gòu)這個(gè)數(shù)。余類集，就可重構(gòu)這個(gè)數(shù)。 例如：例如：Z10中每個(gè)數(shù)都可從這個(gè)數(shù)關(guān)于中每個(gè)數(shù)都可從這個(gè)數(shù)關(guān)于2和和5（10的兩個(gè)互素的因子）的同余類重構(gòu)。的兩個(gè)互素的因子）的同余類重構(gòu)。 比如已知比如已知x關(guān)于關(guān)于2和和5的同余類分別是的同余類分別是0和和3，即即x mod 20，x mod 53?？芍桥紨?shù)且被可知是偶數(shù)且被5除后除后余數(shù)是余數(shù)是3，所以可得，所以可得8是滿足這一關(guān)系的惟一的是滿足這一關(guān)系的惟一的x。4. 中國(guó)剩余定理中國(guó)剩余定理信息信息安全理論及應(yīng)用安全理論及應(yīng)用定理定理4.6（中國(guó)剩余定理）（中國(guó)剩余定理） 設(shè)設(shè)m1,m2,mk是兩兩互是兩兩互素的正整數(shù)，素的正整

12、數(shù)， ，則一次同余方程組則一次同余方程組對(duì)模對(duì)模M有惟一解有惟一解:其中其中ei滿足滿足1122modmodmodkkamxamxamx1kiiMm1 12212modkkkMMMxe ae ae aMmmm1 mod1, 2,iiiMemikm信息信息安全理論及應(yīng)用安全理論及應(yīng)用證明：設(shè)證明：設(shè) ,i=1,2,k，由由Mi的定的定義得義得Mi與與mi是互素的，可知是互素的，可知Mi在模在模mi下有惟一的下有惟一的乘法逆元，即滿足乘法逆元，即滿足 的的ei是惟一的。是惟一的。1kilill iMMmm1 modiiiMemm信息信息安全理論及應(yīng)用安全理論及應(yīng)用下面證明對(duì)下面證明對(duì) i1,2,k

13、，上述上述x滿足滿足ai(mod mi)x。注意到當(dāng)注意到當(dāng)ji時(shí)，時(shí)，mi|Mj，即即Mj0(mod mi)。所以所以(Mjej mod mj) mod mi (Mj mod mi)(ej mod mj) mod mi) mod mi 0而而(Mi(ei mod mi) mod mi(Miei) mod mi1所以所以x(mod mi)ai，即即ai(mod mi)x信息信息安全理論及應(yīng)用安全理論及應(yīng)用下面證明方程組的解是惟一的。設(shè)下面證明方程組的解是惟一的。設(shè)x是方程組的另是方程組的另一解，即一解，即xai(mod mi)(i=1,2,k)由由xai(mod mi)得得x-x0(mod m

14、i)，即即mi|(x-x)。再再根據(jù)根據(jù)mi兩兩互素，有兩兩互素，有M|(x-x)，即即x-x0(mod M)，所以所以x(mod M)=x(mod M)。(證畢證畢) 中國(guó)剩余定理提供了一個(gè)非常有用的特性，即中國(guó)剩余定理提供了一個(gè)非常有用的特性，即在模在模M下可將非常大的數(shù)下可將非常大的數(shù)x由一組小數(shù)由一組小數(shù)(a1,a2,ak)表達(dá)。表達(dá)。信息信息安全理論及應(yīng)用安全理論及應(yīng)用例例4.14 由以下方程組求由以下方程組求x。解：解： M=2357=210，M1=105，M2=70，M3=42，M4=30,易求易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,

15、e4M-14 mod 74, 所以所以x mod 210(10511+7012+4233+3045) mod 210173，或?qū)懗苫驅(qū)懗蓌173 mod 210。1mod22mod33mod55mod7xxxx信息信息安全理論及應(yīng)用安全理論及應(yīng)用例例4.15 將將973 mod 1813由模數(shù)分別為由模數(shù)分別為37和和49的兩個(gè)的兩個(gè)數(shù)表示。數(shù)表示。解：解： 取取x=973, M=1813, m1=37,m2=49。由由a1973 mod m111,a2973 mod m342得得x在模在模37和模和模49下的表達(dá)為（下的表達(dá)為（11,42）。）。信息信息安全理論及應(yīng)用安全理論及應(yīng)用1. 求模

16、下的整數(shù)冪求模下的整數(shù)冪Euler定理指出如果定理指出如果gcd(a, n)=1，則則a(n)1 mod n?，F(xiàn)在考慮如下的一般形式現(xiàn)在考慮如下的一般形式:am1 mod n如果如果a與與n互素，則至少有一整數(shù)互素，則至少有一整數(shù)m（比如比如m=(n)）滿足這一方程。稱滿足方程的最小正整數(shù)滿足這一方程。稱滿足方程的最小正整數(shù)m為模為模n下下a的階。的階。5. 離散對(duì)數(shù)離散對(duì)數(shù)信息信息安全理論及應(yīng)用安全理論及應(yīng)用例如：例如： a=7，n=19，則易求出則易求出717 mod 19,7211 mod 19,731 mod 19，即即7在模在模19下的階為下的階為3。由于由于73+j=737j7j

17、mod 19, 所以所以747 mod 19,7572 mod 19, , 即從即從74 mod 19開始所求的冪出現(xiàn)循環(huán)，循環(huán)周期開始所求的冪出現(xiàn)循環(huán)，循環(huán)周期為為3，即循環(huán)周期等于元素的階。，即循環(huán)周期等于元素的階。信息信息安全理論及應(yīng)用安全理論及應(yīng)用定理定理4.7設(shè)設(shè)a的階為的階為m，則則ak1 mod n的充要條件是的充要條件是k為為m的倍數(shù)。的倍數(shù)。證明：設(shè)存在整數(shù)證明：設(shè)存在整數(shù)q，使得使得k=qm，則則ak(am)q1 mod n。反之，假定反之，假定ak1 mod n，令令k=qm+r,其中其中00,a1)的逆函數(shù)稱為以的逆函數(shù)稱為以a為底為底x的對(duì)數(shù)，記為的對(duì)數(shù)，記為y=lo

18、gax。對(duì)數(shù)函數(shù)有以下性質(zhì)：對(duì)數(shù)函數(shù)有以下性質(zhì)： loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模運(yùn)算中也有類似的函數(shù)。在模運(yùn)算中也有類似的函數(shù)。p是一素?cái)?shù)，是一素?cái)?shù)，a是是p的本原根，則的本原根，則a,a2,ap-1產(chǎn)生出產(chǎn)生出1到到p-1之間的所有值，且每一值只出現(xiàn)一次。因此之間的所有值，且每一值只出現(xiàn)一次。因此對(duì)任意對(duì)任意b1,p-1，都存在惟一的都存在惟一的i(1ip-1)，使使得得bai mod p。稱稱i為模為模p下以下以a為底為底b的指標(biāo)，記為的指標(biāo)，記為i=inda,p(b)。信息信息安全理論及應(yīng)用安全理論及應(yīng)用指標(biāo)有以下性質(zhì)

19、：指標(biāo)有以下性質(zhì)： inda,p(1)=0。 inda,p(a)=1。 分別由以下關(guān)系得出：分別由以下關(guān)系得出： a0 mod p=1 mod p=1,a1 mod p=a。以上假定模數(shù)以上假定模數(shù)p是素?cái)?shù)，對(duì)于非素?cái)?shù)也有類似的結(jié)是素?cái)?shù)，對(duì)于非素?cái)?shù)也有類似的結(jié)論。論。信息信息安全理論及應(yīng)用安全理論及應(yīng)用例例4.6 設(shè)設(shè)p=9，則則(p)=6，a=2是是p的一個(gè)本原根，的一個(gè)本原根，a的不同的冪為（模的不同的冪為（模9下）下）201, 212, 224,238, 247, 255, 261由此可得由此可得a的指數(shù)表如表的指數(shù)表如表4.3（a）所示。所示。重新排列表重新排列表4.4（a），），可求

20、每一與可求每一與9互素的數(shù)的指互素的數(shù)的指標(biāo)如表標(biāo)如表4.4（b）所示。所示。 在討論指標(biāo)的另兩個(gè)性質(zhì)時(shí)，需要利用如下在討論指標(biāo)的另兩個(gè)性質(zhì)時(shí)，需要利用如下結(jié)論：結(jié)論： 若若azaq mod p，其中其中a和和p互素，則有互素，則有zq mod (p)。信息信息安全理論及應(yīng)用安全理論及應(yīng)用證明：因證明：因a和和p互素，所以互素，所以a在模在模p下存在逆元下存在逆元a-1，在在azaq mod p兩邊同乘以兩邊同乘以(a-1)q，得得az-q1 mod p。由由Euler定理定理a(p)1 mod p知知, 存在一整數(shù)存在一整數(shù)k，使得使得z-qk(p)，所以所以zq mod (p)。由上述結(jié)論

21、可得指標(biāo)的以下兩個(gè)性質(zhì)：由上述結(jié)論可得指標(biāo)的以下兩個(gè)性質(zhì)： inda,p(xy)=inda,p(x)+inda,p(y) mod (p)。 inda,p(yr)=rinda,p(y) mod (p)。信息信息安全理論及應(yīng)用安全理論及應(yīng)用性質(zhì)的證明：設(shè)性質(zhì)的證明：設(shè)由模運(yùn)算的性質(zhì)得：由模運(yùn)算的性質(zhì)得：所以所以inda,p(xy)=inda,p(x)+inda,p(y) mod (p)（證畢）證畢） ,mod ,mod ,mod ,a pa pa pindxindyindxyxap yap xyap ,mod(mod) (mod)()moda pa pa pa pa pindxyindxindyi

22、ndxindyapapapap性質(zhì)是性質(zhì)的推廣。性質(zhì)是性質(zhì)的推廣。從指標(biāo)的以上性質(zhì)可見，指標(biāo)與對(duì)數(shù)的概念極為相從指標(biāo)的以上性質(zhì)可見，指標(biāo)與對(duì)數(shù)的概念極為相似。似。信息信息安全理論及應(yīng)用安全理論及應(yīng)用離散對(duì)數(shù)離散對(duì)數(shù)設(shè)設(shè)p是素?cái)?shù)，是素?cái)?shù)，a是是p的本原根，即的本原根，即a1,a2,ap-1在在 mod p下產(chǎn)生下產(chǎn)生1到到p-1的所有值，所以對(duì)的所有值，所以對(duì)b1,p-1，有惟一的有惟一的i1,p-1使得使得bai mod p。稱稱i為模為模p下以下以a為底為底b的離散對(duì)數(shù)，記為的離散對(duì)數(shù)，記為ilogab(mod p)。當(dāng)當(dāng)a、p、i已知時(shí)，用快速指數(shù)算法可比較容易地已知時(shí)，用快速指數(shù)算法可比

23、較容易地求出求出b，但如果已知但如果已知a、b和和p，求求i則非常困難。目則非常困難。目前已知的最快的求離散對(duì)數(shù)算法其時(shí)間復(fù)雜度為：前已知的最快的求離散對(duì)數(shù)算法其時(shí)間復(fù)雜度為：所以當(dāng)所以當(dāng)p很大時(shí)，該算法也是不可行的。很大時(shí)，該算法也是不可行的。2133explnln lnOpp信息信息安全理論及應(yīng)用安全理論及應(yīng)用2 (mod), ( ,)1 mxama mamam 設(shè)設(shè) 是是正正整整數(shù)數(shù), ,若若同同余余式式有有解解, ,則則 叫叫做做模模 的的( (或或),),否否則則 叫叫做做模模 的的平平方方剩剩余余平平方方非非剩剩余余 定定二二次次剩剩余余二二次次非非義義( (或或剩剩余余) ).

24、.6 6、平方剩余、平方剩余信息信息安全理論及應(yīng)用安全理論及應(yīng)用 11 4, 14 是是模模 平平方方剩剩余余是是模模 平平方方例例非非剩剩余余. .21 (mod4)1,3 (mod4)xx解解 因因 有有解解 21 (mod4)x 而而 無無解解. .1,2,4,7, 1,3 ,25 7 是是模模 平平方方剩剩余余是是模模 平平方方 例例非非剩剩余余. .22 24, 54 (mod7)2211, 61 (mod7) 解解 因因 22 32, 42 (mod7) 2221 (mod7),3 (mod7),5 (mod7)xxx 而而 均均無無解解. .信息信息安全理論及應(yīng)用安全理論及應(yīng)用2

25、3 :1 (m3 od7)Eyxx求求 滿滿足足方方 程程例例的的所所有有點(diǎn)點(diǎn). .0,1,2,3,4,5,6, .xy 解解 對(duì)對(duì)分分別別求求出出20,1 (mod7),xy時(shí)時(shí)1,6 (mod7)y21,3 (mod7),xy時(shí)時(shí)無無解解22,4 (mod7),xy 時(shí)時(shí)2,5 (mod7)y 23,3 (mod7),xy時(shí)時(shí)無無解解24,6 (mod7),xy時(shí)時(shí)無無解解25,5 (mod7),xy時(shí)時(shí)無無解解26,6 (mod7),xy時(shí)時(shí)無無解解信息信息安全理論及應(yīng)用安全理論及應(yīng)用模為奇素?cái)?shù)的平方剩余與平方非剩余模為奇素?cái)?shù)的平方剩余與平方非剩余 奇素?cái)?shù)模奇素?cái)?shù)模 p 的平方的平方(

26、(非非) )剩余判別條件剩余判別條件2 (mod), ( , )1apxapa p且且若若 是是模模 的的平平方方剩剩余余, ,則則同同余余式式恰恰有有兩兩解解. .11()( , )1, (i) 1 (mod);(ii) 1 (mod);ppa papapapap 2 22 2 若若則則是是模模 的的平平方方剩剩歐歐拉拉判判別別條條件件余余是是模模 的的平平方方非非剩剩定定余余理理1 1奇素?cái)?shù)模的二次同余式要奇素?cái)?shù)模的二次同余式要么無解，要么恰有兩解么無解，要么恰有兩解信息信息安全理論及應(yīng)用安全理論及應(yīng)用(i)p證證因因 是是奇奇素素?cái)?shù)數(shù)所所以以有有 ， ，122()( )(1)pxa xq

27、 xax ( )q x其其中中是是整整系系數(shù)數(shù)多多項(xiàng)項(xiàng)式式. .0 (mod),()pxxp因因費(fèi)費(fèi)爾爾馬馬定定理理 1220 (mod)10 (mod)pxapap 于于是是有有兩兩解解1112222()(1)ppppxxxxaax122()( )(1)0 (mod)pxa xq xaxp 所所以以 信息信息安全理論及應(yīng)用安全理論及應(yīng)用1(ii) 1 (mod), pa, pap 因因()=1,()=1,由由有有1122|1) |1)pppapa于于是是( (或或( ( 12|1)papa 但但 是是平平方方剩剩余余( (12|1)papa 故故 是是平平方方非非剩剩余余( (1122 1)

28、1)0 (mod)ppaap(121 (mod)pap 即即 信息信息安全理論及應(yīng)用安全理論及應(yīng)用12121212121212 (, )1,(, )1, (i) , , (ii) , , (iii) , , papapa apa apa apa apapapa ap設(shè)設(shè)是是奇奇素素?cái)?shù)數(shù), ,則則如如果果都都是是模模的的平平方方剩剩余余 則則是是模模的的平平方方剩剩余余；如如果果都都是是模模的的平平方方非非剩剩余余 則則是是模模的的平平方方剩剩余余；如如果果是是模模的的平平 推推論論方方剩剩余余是是模模的的平平方方非非剩剩余余 則則是是模模 的的平平方方非非剩剩余余. .1112221212()

29、pppa aaa 證證 因因 1由由定定理理 即即得得結(jié)結(jié)論論. .信息信息安全理論及應(yīng)用安全理論及應(yīng)用奇素?cái)?shù)模奇素?cái)?shù)模 p 的平方的平方( (非非) )剩余的個(gè)數(shù)剩余的個(gè)數(shù)222112211 , 2 , ()2ppppp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù), ,則則模模 的的簡(jiǎn)簡(jiǎn)化化剩剩余余系系中中平平方方剩剩余余與與平平方方非非剩剩余余的的個(gè)個(gè)數(shù)數(shù)各各為為, ,且且個(gè)個(gè)平平方方 定定理理剩剩余余與與序序列列 中中的的一一個(gè)個(gè)數(shù)數(shù)同同余余, ,且且僅僅與與2 2一一個(gè)個(gè)數(shù)數(shù)同同余余. .12 1 (mod)pxp 證證 由由定定理理1 1知知平平方方剩剩余余的的個(gè)個(gè)數(shù)數(shù)等等于于同同余余式式信息信息安全理

30、論及應(yīng)用安全理論及應(yīng)用的的解解數(shù)數(shù). .1121|1, ppxx 但但 121|ppxxx 即即 112pp 而而平平方方非非剩剩余余的的個(gè)個(gè)數(shù)數(shù)是是1,2p 所所以以此此同同余余式式的的解解數(shù)數(shù)為為故故平平方方剩剩余余的的個(gè)個(gè)數(shù)數(shù)1.2p 1,2p 是是再再證證定定理理的的第第二二部部分分. .p顯顯然然序序列列中中的的數(shù)數(shù)都都是是平平方方剩剩余余, ,下下面面只只需需證證明明它它們們對(duì)對(duì)于于模模 互互不不同同余余即即可可. .信息信息安全理論及應(yīng)用安全理論及應(yīng)用|() |(), pklpkl因因此此或或 11,2pk l 但但 21, |1,klppklpp故故 , .kl 從從而而矛矛盾

31、盾()()0 (mod)klklp則則 22, (mod)klklp 若若存存在在使使得得信息信息安全理論及應(yīng)用安全理論及應(yīng)用求求出出模模7 7的的平平方方剩剩余余與與平平例例2 2 方方非非剩剩余余. .222 1 ,2 ,3 (mod7)a 解解 模模7 7的的平平方方剩剩余余為為1,2,3,4,5,6又又模模7 7的的簡(jiǎn)簡(jiǎn)化化剩剩余余系系為為 232 (mod7) 而而 1,2,4 (mod7)a 所所以以模模7 7的的平平方方剩剩余余為為 3,5,6 (mod7)a 而而平平方方非非剩剩余余為為 信息信息安全理論及應(yīng)用安全理論及應(yīng)用819 23例例 、求求出出， 的的平平方方剩剩余余和

32、和平平方方非非剩剩余余。731例例 、在在與與模?；セニ厮氐牡氖ＪＳ嘤嘀兄校钢赋龀銎狡椒椒绞ＪＳ嘤?。信息信息安全理論及應(yīng)用安全理論及應(yīng)用Legendre符號(hào)符號(hào)Legendre | .appapaappp a 設(shè)設(shè) 是是素素?cái)?shù)數(shù), ,符符號(hào)號(hào)定定義義如如下下: :1, 1, 若若 是是模模的的平平方方剩剩余余; ; -1, -1, 若若 是是模模的的平平方方非非剩剩余余; ;0, 0, 若若 定定義義由由定定義義可可知知, , 同同余余式式2 (mod) 1.axapp有有解解信息信息安全理論及應(yīng)用安全理論及應(yīng)用1,2,4,7, 1,3,51 7 因因是是模模 平平方方剩剩余余是是模模 平平

33、方方 例例非非剩剩余余. .1241,777所所以以 1351777 12() , (m1od) ppaaapp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù) 則則對(duì)對(duì)任任意意歐歐拉拉判判 整整別別定定理理法法數(shù)數(shù)Legendre,4.21利利用用符符號(hào)號(hào)定定理理 歐歐拉拉判判別別條條件件可可敘敘述述為為信息信息安全理論及應(yīng)用安全理論及應(yīng)用12 ,1(1) 11;1(2) ( 1)pppp 則則推推設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù)論論 ,1, 1 (mod4)1 1, 3 (mod ) 24pppp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù) 則則推推論論若若 若若 信息信息安全理論及應(yīng)用安全理論及應(yīng)用12,1 ( 1)pp 證證 由由推推論論

34、1 1 有有1 (mod4),14 ,pkpk若若則則存存在在正正整整數(shù)數(shù)使使得得則則1221( 1)( 1)1pkp 3 (mod4),34 ,pkpk若若則則存存在在正正整整數(shù)數(shù)使使得得則則12121( 1)( 1)1pkp 信息信息安全理論及應(yīng)用安全理論及應(yīng)用Legendre符號(hào)符號(hào)Legendre | .appapaappp a 設(shè)設(shè) 是是素素?cái)?shù)數(shù), ,符符號(hào)號(hào)定定義義如如下下: :1, 1, 若若 是是模模的的平平方方剩剩余余; ; -1, -1, 若若 是是模模的的平平方方非非剩剩余余; ;0, 0, 若若 定定義義1 1由由定定義義可可知知, , 同同余余式式2 (mod) 1.

35、axapp有有解解信息信息安全理論及應(yīng)用安全理論及應(yīng)用1,2,4,7, 1,3,51 7 因因是是模模 平平方方剩剩余余是是模模 平平方方 例例非非剩剩余余. .1241,777所所以以 1351777 12() , (m1od) ppaaapp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù) 則則對(duì)對(duì)任任意意歐歐拉拉判判 整整別別定定理理法法數(shù)數(shù)Legendre,1利利用用符符號(hào)號(hào) 定定理理 歐歐拉拉判判別別條條件件可可敘敘述述為為信息信息安全理論及應(yīng)用安全理論及應(yīng)用12 ,1(1) 11;1(2) ( 1)pppp 則則推推設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù)論論 ,1, 1 (mod4)1 1, 3 (mod ) 24ppp

36、p 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù) 則則推推論論若若 若若 信息信息安全理論及應(yīng)用安全理論及應(yīng)用12,1 ( 1)pp 證證 由由推推論論1 1 有有1 (mod4),14 ,pkpk若若則則存存在在正正整整數(shù)數(shù)使使得得則則1221( 1)( 1)1pkp 3 (mod4),34 ,pkpk若若則則存存在在正正整整數(shù)數(shù)使使得得則則12121( 1)( 1)1pkp 信息信息安全理論及應(yīng)用安全理論及應(yīng)用1212 (i) ;(ii) ; (iii) ( , )1, 21nniipapappababpppa aaappaa pp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù), ,則則設(shè)設(shè)則則定定理理信息信息安全理論及應(yīng)用安全理論

37、及應(yīng)用2 (mod)xap apapp 所所以以 (ii) 由由歐歐拉拉判判別別法法, ,有有 1122(mod),(mod)ppabapbppp 12()(mod)pababpp 及及(i) 證證 因因同同余余式式2 (mod)xapp等等價(jià)價(jià)于于同同余余式式信息信息安全理論及應(yīng)用安全理論及應(yīng)用(iii)( , )=1,|,1 ,aa ppap 因因所所以以于于是是 = 111222()pppabababp 因因此此 (mod)abppp 22ababpppp又又而而 ababppp 所所以以22 1aapp所所以以信息信息安全理論及應(yīng)用安全理論及應(yīng)用 (mod),. ababppp若若則則

38、推推論論2 22 , |,1 .abappbpp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù) 若若則則推推論論 11 (1,2,)22 (Gauss ( 1) .)mpaa , ppakk =ppmap 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù), , 是是整整數(shù)數(shù), ,如如果果整整數(shù)數(shù)中中模模 的的最最小小正正剩剩余余大大于于的的個(gè)個(gè)數(shù)數(shù)是是, ,則則 引引理理(),(),信息信息安全理論及應(yīng)用安全理論及應(yīng)用,2p于于的的最最小小正正剩剩余余 則則121,1,2,2tpa aaaaa 證證 設(shè)設(shè)是是整整數(shù)數(shù)關(guān)關(guān)2pp于于模模 的的小小于于的的最最小小正正剩剩余余, ,12 ,mb bb是是一一切切大大1211!(1)(2)()22

39、pppaaaa 1212 (mod)tma aa b bbp 1212( 1)()()() (mod)mtma aapbpbpbp ()(mod)jjpbbp信息信息安全理論及應(yīng)用安全理論及應(yīng)用 0 (mod)jiijpakakakakp或或111.22ijppkkp因因?yàn)闉?12, mpbpbpbp是是模模 兩兩兩兩不不同同余余的的. .1212, tma aapbpbpbp易易知知是是模模 兩兩兩兩不不同同余余的的. .12,ta aap事事實(shí)實(shí)上上, ,是是模模 兩兩兩兩不不同同余余的的, ,若若有有 (mod),jipbap ,ijk k則則有有使使( , )1, 0 (mod),ij

40、p akkp因因所所以以這這不不可可能能, ,信息信息安全理論及應(yīng)用安全理論及應(yīng)用12121,1,2,2tmpa aapbpbpb 是是的的一一1211!(1)(2)()22pppaaaa 1212(1)()()()mtma aapbpbpb1(1)! (mod)2mpp 于于是是1(, )1, 1,2,2pak pk 因因?yàn)闉? 2p 所所以以個(gè)個(gè)整整數(shù)數(shù)個(gè)個(gè)排排列列. .信息信息安全理論及應(yīng)用安全理論及應(yīng)用12 (1) (mod)pmaapp 因因此此引引理理得得證證. .1,ap 注注意意到到 ( 1) .map 故故 信息信息安全理論及應(yīng)用安全理論及應(yīng)用212118 (i) ( 1)(

41、ii) ( ,2 )1, ( 1)pkpakpppapap 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù)定定理理若若3 32 2則則 , ,1,0,1,2,2kkakpakprrp kp 證證 因因11,2,2pk 對(duì)對(duì)求求和和 有有信息信息安全理論及應(yīng)用安全理論及應(yīng)用111222111()pppkkkkakakprp12211118ptmijkijpakapabp 即即 121111()2ptmmijjkijjakpapbbmpp 由引理由引理的證明的證明12211128pmjkjakppmpbp 信息信息安全理論及應(yīng)用安全理論及應(yīng)用122111, (1)28pmjkjpakapmpbp 因因此此1122111(

42、1)(1)2ppmjkkjakakmpm pbpp12211 (1) (mod2)8pkpakamp 所所以以2 2的倍數(shù)的倍數(shù)12,00,akpapp 若若則則21 (mod2)8pm 于于是是212 8pmr 信息信息安全理論及應(yīng)用安全理論及應(yīng)用22112222( 1)( 1)( 1)pprmp 由由引引理理121 (mod2)pkakamp 若若 為為奇奇數(shù)數(shù), , 則則112211 +2( 1)( 1)( 1)ppkkakaktppmap 由由引引理理121 +2pkakmtp 即即 信息信息安全理論及應(yīng)用安全理論及應(yīng)用 81, 2 83, 2pmpm即即 當(dāng)當(dāng)時(shí)時(shí)是是平平方方剩剩余余

43、當(dāng)當(dāng)時(shí)時(shí)是是平平方方非非剩剩余余, , . .,1, 1 (mod8)2 1, 3 (mod8) pppp 設(shè)設(shè) 是是奇奇素素?cái)?shù)數(shù) 則則若若推推論論 若若= =3, 證證 由由定定理理2182 ( 1)pp 1 (mod8),81,ppm 若若即即有有于于是是信息信息安全理論及應(yīng)用安全理論及應(yīng)用22(81)18282 ( 1)( 1)1mmmp 3 (mod8),83,ppm 若若即即有有于于是是22(83)1(86) 182 ( 1)( 1)1mmmp 1122 ( 1)pqpqqppq () () 若若 及及定定理理是是互互素素的的奇奇素素?cái)?shù)數(shù)二二律律4 4次次, ,則則互互反反信息信息安

44、全理論及應(yīng)用安全理論及應(yīng)用717 213是是模模的的平平方方剩剩余余，是是模模的的平平方方例例2 2 非非剩剩余余. .21713682 ( 1)( 1)117 解解 因因217所所以以, , 是是模模的的平平方方剩剩余余. .17 1 3 122317( 1)173 3 12( 1) 173 13 1 317所所以以, , 是是模模的的平平方方非非剩剩余余. .信息信息安全理論及應(yīng)用安全理論及應(yīng)用2 1 (mod 365) x 判判斷斷同同余余式式是是否否有有解解, ,有有解解時(shí)時(shí), , 求求出出例例4 4 其其解解數(shù)數(shù). .221 (mod 5) 1 (mod 73)xx 解解 365=5

45、73, 365=573,原原同同余余式式等等價(jià)價(jià)于于同同余余式式組組5 121( 1)1, 5 因因4.故故同同余余式式組組有有解解, , 因因而而原原同同余余式式有有解解, ,解解數(shù)數(shù)為為73 121 ( 1)173 信息信息安全理論及應(yīng)用安全理論及應(yīng)用Jacobi 符號(hào)符號(hào)信息信息安全理論及應(yīng)用安全理論及應(yīng)用3.3 Jacobi 符號(hào)符號(hào)信息信息安全理論及應(yīng)用安全理論及應(yīng)用3.3 Jacobi 符號(hào)符號(hào)信息信息安全理論及應(yīng)用安全理論及應(yīng)用3.3 Jacobi 符號(hào)符號(hào)信息信息安全理論及應(yīng)用安全理論及應(yīng)用3.3 Jacobi 符號(hào)符號(hào) Jacobi 符號(hào)與Legendre 符號(hào)的關(guān)系：信息信

46、息安全理論及應(yīng)用安全理論及應(yīng)用定理定理 已知已知n為兩個(gè)素?cái)?shù)乘積為兩個(gè)素?cái)?shù)乘積, a是模是模n的平方剩余，則的平方剩余，則求解方程求解方程x2a mod n與分解與分解n是等價(jià)的。是等價(jià)的。(1)已知已知n的分解的分解n=pq，且且a是模是模n的平方剩余，的平方剩余，就可求得就可求得a mod n的的4個(gè)平方根個(gè)平方根由中國(guó)剩余定理可求得由中國(guó)剩余定理可求得a mod n的的4個(gè)平方根，記為個(gè)平方根，記為u mod n和和w mod n，且且u w mod n。 qzxpyxmodmod qzxpyxmodmod qzxpyxmodmod qzxpyxmodmodnaxmod2 qaxpaxm

47、odmod22 qzxpyxmodmod信息信息安全理論及應(yīng)用安全理論及應(yīng)用(2) 已知已知a mod n的兩個(gè)不同的平方根（的兩個(gè)不同的平方根（u mod n和和w mod n，且且u w mod n），），就可分解就可分解n。由由u2w2 mod n,得得(u+w)(u-w)0 mod n，但但n不能整不能整除除u+w也不能整除也不能整除u-w，所以必有所以必有p|(u+w), q|(u-w)或或 p|(u-w), q|(u+w)所以所以 gcd(n, u+w)=p, gcd(n, u-w)=q或或gcd(n, u-w)=p, gcd(n, u+w)=q因此得到了因此得到了n的分解式。的分

48、解式。信息信息安全理論及應(yīng)用安全理論及應(yīng)用1. 費(fèi)爾瑪定理和歐拉定理費(fèi)爾瑪定理和歐拉定理2. 素性檢驗(yàn)素性檢驗(yàn): Miller-Rabin的素性概率檢測(cè)法的素性概率檢測(cè)法3. 廣義歐幾里得除法廣義歐幾里得除法4. 中國(guó)剩余定理中國(guó)剩余定理5. 離散對(duì)數(shù)離散對(duì)數(shù)6. 求解求解x2a mod n與分解與分解n等價(jià)等價(jià)數(shù)論知識(shí)總結(jié)數(shù)論知識(shí)總結(jié)信息信息安全理論及應(yīng)用安全理論及應(yīng)用4.3 RSA密碼算法密碼算法 MIT三位年青學(xué)者三位年青學(xué)者Rivest，Shamir和和Adleman 在在1978年發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰體制的方法，年發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰體制的方法，稱作稱作MIT體制，后來被廣泛

49、稱之為體制，后來被廣泛稱之為RSA體制。體制。 它既可用于加密、又可用于數(shù)字簽名。它既可用于加密、又可用于數(shù)字簽名。 RSARSA算法的安全性基于數(shù)論中大整數(shù)分解的困難算法的安全性基于數(shù)論中大整數(shù)分解的困難性性。信息信息安全理論及應(yīng)用安全理論及應(yīng)用4.3.1 算法描述算法描述-密鑰生成密鑰生成 選取兩互異大素?cái)?shù)選取兩互異大素?cái)?shù)p p和和q q 計(jì)算計(jì)算 n n=p pq q 和其歐拉函數(shù)值和其歐拉函數(shù)值 ( (n n)=()=(p p1)(1)(q q1) 1) 選一整數(shù)選一整數(shù)e e，1 1 e e ( (n n) )，使得，使得 gcd(gcd( ( (n n), ), e e)=1)=1

50、 在模在模 ( (n n) )下，計(jì)算下，計(jì)算e e的逆元的逆元d d. . 即求即求d, d, 使得使得 e ed d 1 1 mod mod ( (n n) ) 以以( (n n，e e ) )為公鑰。為公鑰。d d 為秘密鑰。為秘密鑰。 ( (p p, , q q不再需要，可以銷毀。不再需要，可以銷毀。) ) 信息信息安全理論及應(yīng)用安全理論及應(yīng)用 加密 將明文分組，各組對(duì)應(yīng)的十進(jìn)制數(shù)mn, 計(jì)算 c =E(m) me mod n 解密 m = D(c) cd mod n信息信息安全理論及應(yīng)用安全理論及應(yīng)用RSA算法算法解密過程的正確性解密過程的正確性。證明：證明： 由加密過程知由加密過程

51、知cme mod n，所以所以cd mod nmed mod n mk(n)+1 mod n分兩種情況：分兩種情況： m與與n互素互素，則由，則由Euler定理得定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n即即cd mod nm。加密：加密： cme mod n解密：解密：mcd mod n信息信息安全理論及應(yīng)用安全理論及應(yīng)用由由gcd(m,q)=1及及Euler定理得定理得m(q)1 mod q，所以所以mk(q)1 mod q,mk(q)(p)1 mod q, mk(n)1 mod q因此存在一整數(shù)因此存在一整數(shù)r，使得使得mk(n)=1+rq，兩邊

52、同乘以兩邊同乘以m=cp得得mk(n)+1=m+rcpq=m+rcn即即mk(n)+1m mod n，所以所以cd mod nm。(證畢證畢)qcnm 1 ,1 gcd(m,n)1, 不妨設(shè)不妨設(shè) m=cp，信息信息安全理論及應(yīng)用安全理論及應(yīng)用例例: p=7, q=17. n=pq=119, (n)=(p-1)(q-1)=96。取取e=5，滿足滿足1e(n)，且且gcd(n),e)=1。確定滿足確定滿足de=1 mod 96且小于且小于96的的d，因?yàn)橐驗(yàn)?75=385=496+1，故，故d=77。因此公鑰為因此公鑰為5, 119，私鑰為，私鑰為77, 119。設(shè)明文設(shè)明文m=19，則由加密過

53、程得密文為則由加密過程得密文為c195 mod 1192476099 mod 11966解密為解密為6677mod 11919信息信息安全理論及應(yīng)用安全理論及應(yīng)用1. RSA的加密與解密過程的加密與解密過程 RSA的加密、解密過程都為求一個(gè)的加密、解密過程都為求一個(gè)整數(shù)的整數(shù)次整數(shù)的整數(shù)次冪冪，再取模再取模。如果按其含義直接計(jì)算，則中間結(jié)果。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：而用模運(yùn)算的性質(zhì)：(ab) mod n=(a mod n)(b mod n) mod n就可減小中間結(jié)果。就可減小

54、中間結(jié)果。4.3.2 RSA算法中的計(jì)算問題算法中的計(jì)算問題信息信息安全理論及應(yīng)用安全理論及應(yīng)用 再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求有效性。例如求x16，直接計(jì)算的話需做直接計(jì)算的話需做15次乘法。次乘法。然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求x，x2，x4，x8，x16則只需則只需4次乘法。次乘法。求求am可如下進(jìn)行，其中可如下進(jìn)行，其中a，m是正整數(shù)：是正整數(shù)： 將將m表示為二進(jìn)制形式表示為二進(jìn)制形式bk bk-1b0，即即因此因此12012222kkkbbbbbmaaaaaa 信息信

55、息安全理論及應(yīng)用安全理論及應(yīng)用d=1；For i=k downto 0 do d=(dd) mod n;if bi=1 then d=(da) mod nreturn d.m=bk2k+bk-12k-1+b12+b012012222kkkbbbbbmaaaaaa 快速指數(shù)算法快速指數(shù)算法信息信息安全理論及應(yīng)用安全理論及應(yīng)用2. RSA密鑰的產(chǎn)生密鑰的產(chǎn)生(1) 兩個(gè)大素?cái)?shù)兩個(gè)大素?cái)?shù)p、q的選取。的選取。 Miller-Rabin算法算法;(2) e的選取和的選取和d的計(jì)算。的計(jì)算。 選取滿足選取滿足1eq，由由(n)=(p-1)(q-1)，則有則有p+q=n-(n)+1以及以及得：得：由此可見

56、，由此可見，不對(duì)不對(duì)n進(jìn)行因式分解而直接計(jì)算進(jìn)行因式分解而直接計(jì)算(n)并不比對(duì)并不比對(duì)n進(jìn)行因式分解更容易。進(jìn)行因式分解更容易。224( ) 14pqpqnnnn1212ppqpqqpqpq信息信息安全理論及應(yīng)用安全理論及應(yīng)用為保證算法的安全性，還對(duì)為保證算法的安全性，還對(duì)p和和q提出以下要求：提出以下要求： （1） |p-q|要大。要大。（2）p和和q的長(zhǎng)度應(yīng)該相差不多。的長(zhǎng)度應(yīng)該相差不多。（3） p-1和和q-1都應(yīng)有大素因子。都應(yīng)有大素因子。（4） gcd(p-1, q-1)應(yīng)該很小。應(yīng)該很小。信息信息安全理論及應(yīng)用安全理論及應(yīng)用1. 共模攻擊共模攻擊 在實(shí)現(xiàn)在實(shí)現(xiàn)RSA時(shí)，為方便起見

57、，可能給每一用戶相時(shí)，為方便起見，可能給每一用戶相同的模數(shù)同的模數(shù)n，雖然加解密密鑰不同，然而這樣做是雖然加解密密鑰不同，然而這樣做是不行的。不行的。4.3.4 對(duì)對(duì)RSA的攻擊的攻擊信息信息安全理論及應(yīng)用安全理論及應(yīng)用設(shè)兩個(gè)用戶的公開鑰分別為設(shè)兩個(gè)用戶的公開鑰分別為e1和和e2，且且e1和和e2互素，互素，明文消息是明文消息是m，密文分別是密文分別是敵手截獲敵手截獲c1和和c2后，可如下恢復(fù)后，可如下恢復(fù)m。用推廣的用推廣的Euclid算法求出滿足算法求出滿足re1+se2=1的兩個(gè)整數(shù)的兩個(gè)整數(shù)r和和s，其中一個(gè)為負(fù)，設(shè)為其中一個(gè)為負(fù)，設(shè)為r。再次用再次用推廣的推廣的Euclid算法求出算

58、法求出 ，由此得由此得11 cnmccccsrsrmod)(21121 nmcnmceemodmod2121 信息信息安全理論及應(yīng)用安全理論及應(yīng)用2. 低指數(shù)攻擊低指數(shù)攻擊 將將RSA同時(shí)用于多個(gè)用戶，然而每個(gè)用戶的同時(shí)用于多個(gè)用戶，然而每個(gè)用戶的加密加密指數(shù)指數(shù)都很小。設(shè)都很小。設(shè)3個(gè)用戶的模數(shù)分別為個(gè)用戶的模數(shù)分別為ni(i=1,2,3)，當(dāng)當(dāng)ij時(shí)，時(shí)，gcd(ni, nj)=1，否則通過否則通過gcd(ni, nj)有可能有可能得出得出ni 和和nj 的分解。設(shè)明文消息是的分解。設(shè)明文消息是m，密文分別是密文分別是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)

59、由中國(guó)剩余定理可求出由中國(guó)剩余定理可求出m3(mod n1 n2 n3 )。由于由于m3 n1 n2 n3 ，可直接由可直接由m3開立方根得到開立方根得到m。信息信息安全理論及應(yīng)用安全理論及應(yīng)用RSA是是確定性的加密算法確定性的加密算法, 不能抵御不能抵御選擇密文攻擊選擇密文攻擊。3. 選擇密文攻擊選擇密文攻擊假設(shè)攻擊者得到了假設(shè)攻擊者得到了RSA公鑰公鑰(n,e)，截獲到某個(gè)密文，截獲到某個(gè)密文c1，假設(shè)其明文為，假設(shè)其明文為m1,即即 11modecmn然后，攻擊者選取明文然后，攻擊者選取明文m，構(gòu)造新密文，構(gòu)造新密文c2：21modeccmn攻擊者讓解密者對(duì)攻擊者讓解密者對(duì)c2解密，獲得

60、明文解密，獲得明文m2，則計(jì)算，則計(jì)算 ：21modmmnm信息信息安全理論及應(yīng)用安全理論及應(yīng)用 鶚鳥（鶚鳥（ossifrage），又名髭兀鷹（），又名髭兀鷹（lammergeier），是阿），是阿爾卑斯山上一種稀有的肉食禿鷹。它的翅膀展開將近十米爾卑斯山上一種稀有的肉食禿鷹。它的翅膀展開將近十米寬。鳥名的字面含義是寬。鳥名的字面含義是“碎骨碎骨”。顧名思義，其習(xí)性令人。顧名思義，其習(xí)性令人毛骨悚然。毛骨悚然。 Mirtin Gardner在在1977年年“Scientific American”的專欄文的專欄文章中介紹了章中介紹了RSA碼。為了顯示這一技術(shù)的威力，碼。為了顯示這一技術(shù)的威力，