第31章-數(shù)論算法

1、第31章 數(shù)論算法,預(yù)備知識(shí),1數(shù)論基礎(chǔ),數(shù)論是一門(mén)古老的數(shù)學(xué)分支。以前人們都認(rèn)為它是完全純粹數(shù)學(xué)，在現(xiàn)實(shí)生活中很難找到它的實(shí)際應(yīng)用。自從1976年公開(kāi)密鑰密碼體制誕生以來(lái)，現(xiàn)代密碼學(xué)就和數(shù)論有著千絲萬(wàn)縷的聯(lián)系。,一、引言,約定：字母N表示全體自然數(shù)集合，Z表示整數(shù)集合，即N={0，1，2，…}Z={…，-2，-1，0，1，2，…},自然數(shù)與整數(shù),定義1：如果存在一個(gè)整數(shù)k使得n=kd，則稱(chēng)d整除n,記作d|n，其中d稱(chēng)作n的因子，

2、n稱(chēng)作d的倍數(shù)。如果不存在這樣一個(gè)整數(shù)使得n=kd，則稱(chēng)d不整除n，記為d?n。,整除,定義2：整數(shù)p>1稱(chēng)為素?cái)?shù)，如果除了1和其本身外，p沒(méi)有任何其它因數(shù)。不是素?cái)?shù)的整數(shù)稱(chēng)為合數(shù)。,素?cái)?shù)與合數(shù),帶余除法：設(shè)a,b是兩個(gè)整數(shù)，其中b>0。則存在兩個(gè)整數(shù)q,r使得a=q·b+r。其中q和r是唯一確定的。,帶余除法,公因數(shù)：設(shè)a,b是兩個(gè)整數(shù)，既是a的因數(shù)又是b的因數(shù)的數(shù)稱(chēng)為a,b的公因數(shù)。,公因數(shù),最大公因數(shù)：a和b

3、的所有公因數(shù)中最大者，稱(chēng)為a和b的最大公因數(shù)，記作gcd(a,b)。,最大公因數(shù),公倍數(shù)：設(shè)a,b是兩個(gè)整數(shù)，既是a的倍數(shù)又是b的倍數(shù)的數(shù)稱(chēng)為a,b的公倍數(shù)。最小公倍數(shù)：a和b的所有公倍數(shù)中最小者，稱(chēng)為a和b的最小公倍數(shù)，記作lcm(a,b)。,公倍數(shù)與最小公倍數(shù),lcm(a,b) ·gcd(a,b)=a·b.,最小公倍數(shù)與最大公因數(shù),a與b互素：如果對(duì)兩個(gè)整數(shù)a,b有g(shù)cd(a,b)=1,則稱(chēng)a與b互素。,整數(shù)的

4、互素,設(shè)a,b是自然數(shù)，則存在兩個(gè)整數(shù)u和v使得： u·a+v·b=gcd(a,b),最大公因數(shù)的線(xiàn)性表示,算術(shù)基本定理：任何一個(gè)正整數(shù)m都存在唯一的因數(shù)分解形式：,,,算術(shù)基本定理,,例如：,算術(shù)基本定理,,,算術(shù)基本定理,歐幾里德（Euclid）算法（輾轉(zhuǎn)相除法）,,歐幾里德算法,1694=1?917+777917=1?777+140777=5?1

5、40+77140=1?77+6377=1?63+1463=4?14+714=2?7+0gcd(1694,917)=7,7=63-4 ?14 =63-4 ?(77-63) =-4 ?77+5 ?63 = -4 ?77+ 5 ?(140-77) =5 ?140-9 ?77 = 5 ?140 -9 ?(777- 5 ?140) =-9 ?777+50 ?140 =-9 ?777+50 ?(917-777)

6、 =50 ?917-59 ?777 = 50 ?917-59?(1694-917) = -59?1694+109 ?917,兩個(gè)整數(shù)同余：設(shè)a,b是兩個(gè)整數(shù)，m是一個(gè)正整數(shù)。如果 m|(b-a), 則稱(chēng)a與b對(duì)模m同余。記作a? b(mod m).例如，3? 1（mod 2） 4? 1 (mod 3),a? a (mod m),a? b (mod m),,b? a (mod m),a? b (mod m),,,b?

7、c (mod m),a? bc(mod m),同余,定義模m的算術(shù)運(yùn)算：Zm={0，1，…，m-1},它有兩種運(yùn)算+和? 。在Zm中的加法和乘法，除了將結(jié)果被模m約簡(jiǎn)外，恰好像實(shí)數(shù)加法和乘法。例如：在Z2中的加法0+0? 0 (mod 2) 0+1? 1 (mod 2) 1+0? 1 (mod 2) 1+1? 0 (mod 2) 例如：在Z16中的乘法1

8、1 ?13 11 ?13=143 ?15 （mod 16）,模運(yùn)算,定義4 歐拉函數(shù) 是定義在正整數(shù)上的函數(shù)，它在正整數(shù)m的值等于1，2，…，m-1中與m互素的數(shù)的個(gè)數(shù)，記為,,m=6, {1,2,3,4,5}中與m互素的數(shù)為{1，5}，共兩個(gè)，因此,=2,歐拉函數(shù),設(shè)正整數(shù)m的標(biāo)準(zhǔn)分解形式為,則,,例如 6=2? 3,,歐拉函數(shù),歐拉定理：如果a和m互素，則,,費(fèi)爾馬定理

9、 若p是素?cái)?shù)，則,歐拉定理與費(fèi)爾馬定理,中國(guó)剩余定理：設(shè)m1, m2,…, mk 是k個(gè)兩兩互素的整數(shù)，m= m1·m2,…·mk , Mi=m/mi，I=1,2,…,k。則同余方程組,x? b1 (mod m1),x? bk (mod mk),x? b2 (mod m2),………,有解,,可由歐幾里德算法求出。,中國(guó)剩余定理,,離散對(duì)數(shù),離散對(duì)數(shù)問(wèn)題,設(shè)x, r, n是正整數(shù)。已知x, r和n, 可以很快地求出,反

10、過(guò)來(lái)，如果已知y, x和n, 求r使得：,成立，這就是離散對(duì)數(shù)問(wèn)題。,,離散對(duì)數(shù),當(dāng)y, x和n都比較小時(shí)，可以用窮舉搜索求得r, 如果這些數(shù)都比較大，這是非常困難的。如果給定一個(gè)整數(shù)r, 那么可以很容易驗(yàn)證它是否為,的解。因此，離散對(duì)數(shù)問(wèn)題是NP問(wèn)題。計(jì)算機(jī)理論科學(xué)已經(jīng)證明，離散對(duì)數(shù)問(wèn)題是NP－完全問(wèn)題。,,加密機(jī)制,一個(gè)密碼體制被定義為一對(duì)數(shù)據(jù)變換，其中一個(gè)變換應(yīng)用于稱(chēng)之為明文的數(shù)據(jù)項(xiàng)，變換后產(chǎn)生的相應(yīng)數(shù)據(jù)項(xiàng)稱(chēng)為密文；而另一個(gè)變換

11、應(yīng)用于密文，變換后的結(jié)果為明文。,加密,,KE,,Ｍ,,Ｃ,解密,,KD,,Ｃ,,Ｍ,加密過(guò)程,解密過(guò)程,公開(kāi)密鑰密碼體制,利用計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行商務(wù)活動(dòng)，其信息的真實(shí)性是人們迫切需要的。為了防止欺詐，通信雙方必須對(duì)對(duì)方的身份、消息的真?zhèn)芜M(jìn)行驗(yàn)證。有時(shí)還需要通信雙方對(duì)信息進(jìn)行數(shù)字簽名，以便在發(fā)生糾紛時(shí)，能夠提交第三者（如法院）進(jìn)行仲裁。這一切都使得傳統(tǒng)密碼體制越來(lái)越不能適應(yīng)計(jì)算機(jī)網(wǎng)絡(luò)保密通信要求了，人們迫切需要尋找新的密碼體制。,單向函數(shù),

12、單向函數(shù)：如果給定x，求f(x)是容易的；而給定f(x)，求x是困難的。,1976年，美國(guó)學(xué)者Diffie和Hellman根據(jù)單向函數(shù)的概述提出了公開(kāi)密鑰密碼體制。公開(kāi)密鑰密碼體制從根本上克服了傳統(tǒng)密碼體制的困難，解決了密鑰分配和消息認(rèn)證等問(wèn)題,RSA公開(kāi)密鑰密碼體制,1.RSA體制,RSA體制是美國(guó)麻省理工學(xué)院（MIT）Rivest,Shamir和Adleman于1978年提出來(lái)的，它是第一個(gè)成熟的、迄今為止理論上最為成功的公開(kāi)密鑰密

13、碼體制。它的安全性基于數(shù)論中的Euler定理和計(jì)算復(fù)雜性理論中的下述論斷：求兩個(gè)大素?cái)?shù)的乘積是容易計(jì)算的，但要分解兩個(gè)大素?cái)?shù)的乘積是難的。,RSA公開(kāi)密鑰密碼體制,2.RSA加密、解密過(guò)程,1）密鑰生成,（1）隨機(jī)選取兩個(gè)大素?cái)?shù)（200位的十進(jìn)制數(shù)）p和q，令N=p﹒q，隨機(jī)選取兩個(gè)整數(shù)e和d，使得e,d與,(2) 公開(kāi)N,e,作為E，記為E＝（N，e）；,(3) 保密p,q,d與　　，作為D，記為D＝（p,q,d, ?。?RS

14、A公開(kāi)密鑰密碼體制,2.RSA加密、解密過(guò)程,2）加密過(guò)程,（1）在公開(kāi)密鑰數(shù)據(jù)庫(kù)中，查得用戶(hù)U得公鑰：E＝（N, e）,（2）將明文分組：,RSA公開(kāi)密鑰密碼體制,2.RSA加密、解密過(guò)程,2）加密過(guò)程,（3）對(duì)每組明文作加密變換,（4）將密文　　　　　　　傳送給用戶(hù)U。,RSA公開(kāi)密鑰密碼體制,2.RSA加密、解密過(guò)程,3）解密過(guò)程,（1）對(duì)每組密文作解密變換,（2）合并分組得到明文,RSA公開(kāi)密鑰密碼體制,2.RSA加密、解密實(shí)例

15、,設(shè)B選擇p=101和q=113,那么N=pxq=101x113=11413, ; 選擇e=3533,則 　　B公開(kāi)n=11413和e=3533.現(xiàn)假設(shè)A要發(fā)送9226給B。A計(jì)算92263533mod(11413)=5761,將5761通過(guò)公開(kāi)信道