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

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

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

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

4、互素,設a,b是自然數(shù)，則存在兩個整數(shù)u和v使得： u·a+v·b=gcd(a,b),最大公因數(shù)的線性表示,算術基本定理：任何一個正整數(shù)m都存在唯一的因數(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,兩個整數(shù)同余：設a,b是兩個整數(shù)，m是一個正整數(shù)。如果 m|(b-a), 則稱a與b對模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的算術運算：Zm={0，1，…，m-1},它有兩種運算+和? 。在Zm中的加法和乘法，除了將結(jié)果被模m約簡外，恰好像實數(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）,模運算,定義4 歐拉函數(shù) 是定義在正整數(shù)上的函數(shù)，它在正整數(shù)m的值等于1，2，…，m-1中與m互素的數(shù)的個數(shù)，記為,,m=6, {1,2,3,4,5}中與m互素的數(shù)為{1，5}，共兩個，因此,=2,歐拉函數(shù),設正整數(shù)m的標準分解形式為,則,,例如 6=2? 3,,歐拉函數(shù),歐拉定理：如果a和m互素，則,,費爾馬定理

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

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

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

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

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

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

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