1、計算機安全保密第二講密碼學(xué)數(shù)學(xué)基礎(chǔ),唐明 武漢大學(xué)計算機學(xué)院,本次課的內(nèi)容,2.1信息論 2.2復(fù)雜性理論 2.3初等數(shù)論 2.4因數(shù)分解 2.5 素數(shù)的產(chǎn)生 2.6 有限域內(nèi)的離散對數(shù) 2.7 單向哈希函數(shù),2.1 信息論,2.1.1 熵與疑義度 2.1.2 自然語言率 2.1.3 密碼系統(tǒng)的安全性 2.1.4 確定性距離 2.1.5 混亂與擴(kuò)散,2.1.1 熵與疑義度,1949年，Shannon發(fā)表“Communication Theory of Secrecy Systems” 一條消息中的信息量，形式上由該消息的熵來度量。,一、自信息和熵,1、自信息 文字、圖象、聲音是消息，信息是消息

2、的有價值內(nèi)容。 給定一離散事件集X，它含有N 個事件x1,x2,xN，事件xi 出現(xiàn)的概率記作pi，1pi0 且 自信息定義 定義 事件xi的自信息，記作I(xi),定義為 注意：自信息的定義沒有規(guī)定對數(shù)的底！ 對數(shù)底為2時，自信息單位為比特（bit）； 對數(shù)底取為e時，自信息單位為奈特（nat）； 對數(shù)底為10時，自信息單位為哈特（hart）。,自信息的含義 自信息度量了一個隨機事件xi未出現(xiàn)時所呈現(xiàn)的不確定性，也度量了該事件xi出現(xiàn)后所給出的信息量。 事件的不確定性越大，則一旦出現(xiàn)給出的信息量也就越大。 舉例 例 計算從英文字母表中任選一個字母時所給出的自信息量。 因為從26個字母中任取一

3、個字母的概率為， 所以任選一個字母所給出的信息量為,一、自信息和熵,2、熵 自信息描述了事件集X中一個事件出現(xiàn)給出的信息量，整個集X的平均信息量是該集所有事件自信息的統(tǒng)計平均值（數(shù)學(xué)期望），稱作集X的熵。 定義2.2 集X的熵，記作H(X)，定義為 定義中，規(guī)定0log0=0。 H（X）度量了集X中各個事件未出現(xiàn)時所呈現(xiàn)的平均不確定性(疑義度)，也度量了集X中一個事件出現(xiàn)時所給出的平均信息量。,疑義度：消息的熵同時也可衡量其不確定性（疑義度），即將消息隱藏在密文中時，要破譯它所需的明文比特數(shù)（即當(dāng)消息被加密成密文時，為了獲取明文需要解密的明文的位數(shù)）。,一、自信息和熵,2、熵 舉例 例 給出集

4、 按定義有: I(x1) =-log2 1/2=log2 2 =1比特， I（x2）=I（x3）=-log2 1/4=log2 4=2比特。 于是 一個事件集的熵越大，其不確定性越高。,。,比特。,關(guān)于熵的實際例子,例：X可能在下周某天去釣魚。 星期一，星期日共有七種可能（x1，x7），假設(shè)各種可能性出現(xiàn)概率相等，則：P（Xi）=1/7，H（x）=7(1/7)log21/7=log21/7= log27 同時，H（x）也指出了X中的信息量將消息中所有可能的值進(jìn)行編碼時所需的最少比特數(shù)。 2 H(x)= log27 3 b1b2b3可以表示一周的7個狀態(tài)： 000 星期日 001 星期一 110

5、 星期六 保留,關(guān)于熵的實際例子,甲任意取一個不超過15的整數(shù)，由乙來猜，但允許乙提K個問題，甲只回答“是”或者“非”，問K多大時可以確定猜到該數(shù)。,解：若令乙猜想作為事件V，V可能有16種結(jié)果，假定這16種結(jié)果是等概率的，V的熵為： H（V）= log216 令事件Ak=U1U2U3Uk為提問k個問題，但Ui的熵不超過log22=1，（因為只有“是”或者“非”），故Ak的熵為不超過k比特，則： log216 klog22 =k， k 4 故 k=4,繼續(xù)前面的例子,0到15之間的數(shù)可以由4比特信息來表示。即 而上面的問題實際上可以轉(zhuǎn)化為如何獲得這4個比特信息。因為每個問題的答案只有兩種，故每

6、個問題的答案最多只能提供1比特的信息。 因而如果要確保得到正確結(jié)果，則至少需要4次。,那如何保證每次可以獲得1位的信息呢？,最直接的四個問題： 這個數(shù)被表示為四位二進(jìn)制后，第一位是0嗎？ 這個數(shù)被表示為四位二進(jìn)制后，第二位是0嗎？ 這樣，我們可以確保每次都可以得到一位信息。,思考？,假設(shè)乙的第一個問題是“這個數(shù)字是a嗎？” 其中a是0-15之間的任意一個確定的數(shù)。,如果乙得到“是”的回答，請問該事件提供的信息量是多少？ 如果乙得到“否”的回答，請問乙是否還能夠確保在規(guī)定次數(shù)之內(nèi)得到正確結(jié)果？為什么？,思考？,假設(shè)乙的第一個問題是“這個數(shù)字大于11嗎？”,如果乙得到“是”的回答，請問該事件提供的

7、信息量是多少？ 如果乙得到“否”的回答，請問乙是否還能夠確保在規(guī)定次數(shù)之內(nèi)得到正確結(jié)果？為什么？,關(guān)于熵的實際例子,有25個外表完全相同的硬幣，其中24個重量完全一樣，有一個較輕的偽幣，用無砝碼的天平，試問要做多少次的比較，可以找到這枚偽幣？,繼續(xù)前面的例子,解：事件V為找出偽幣，可能有25個結(jié)論，他們是等概率，故： H（V）= log225， 事件U為天平稱的結(jié)果，可能有3種情況：1.左右平衡；2.左邊重；3.右邊重；故： H（U）= log23 令A(yù)k=U1U2U3Uk為連續(xù)用k次天平的事件， klog23 log225 k （log225）/ log23=2.93 故 k最少為3次,繼續(xù)

8、前面的例子,一種解決方案： 25=8+8+9（第一次） 天平兩端各放8個，如果平衡，則偽幣在剩余的9個之中，跳到ii； 如果不平衡，則偽幣在較輕的8個之中，跳到iii。 9=3+3+3（第二次） 天平兩端各放3個，如果平衡，則從剩下3個中尋找偽幣。否則，從較輕的3個中尋找偽幣。 8=3+3+2（第二次） 天平兩端各放3個，如果平衡，則從剩下2個中尋找偽幣。否則，從較輕的3個中尋找偽幣。,思考？,有25個外表完全相同的硬幣，其中24個重量完全一樣，偽幣重量不一樣，但不知是輕還是重，用無砝碼的天平，試問要做多少次的比較，可以找到這枚偽幣？,2.1.2 自然語言率,自然語言率：對于給定的一種語言，其

9、自然語言率為 r = H(M)/ N 其中N為消息長度。 英語的自然語言率：1.0比特/字母1.5比特/字母 它是一個語言系統(tǒng)的實際表現(xiàn)力，實際上是一個語言系統(tǒng)的實際熵。,絕對語言率,絕對語言率：每個字符編碼的最大比特數(shù)，這里假設(shè)每個字符序列出現(xiàn)的機會相等。 若語言中有L個字母，則絕對語言率為： R = log2L 為單個字母的最大熵。 英語的絕對語言率：log226 4.7比特/字母 它是一個語言系統(tǒng)理論上的最大表現(xiàn)力。當(dāng)每個字符出現(xiàn)的概率相同時，其具有最大表現(xiàn)力。實際上是語言系統(tǒng)的最大熵。,冗余度：語言的冗余度記為D，定義為： D = R - r 其中，R為絕對語言率，r為自然語言率。 英

10、語：r = 1.3比特/字母，則D = 3.4比特/字母。,2.1.3 密碼系統(tǒng)的安全性,絕對安全的密碼系統(tǒng)： M：明文空間；K：密鑰空間；C：密文空間； c= E(m, k)。E： M C。 H(M), H(K) 絕對保密的密碼系統(tǒng)的必要條件： H(K) H(M) 盧開澄，計算機密碼學(xué)，清華大學(xué)出版社。 即：一次一密（密鑰與消息本身一樣長，且密鑰不重復(fù)使用）系統(tǒng)。 密碼系統(tǒng)的熵：衡量密鑰空間K的大小的一個標(biāo)準(zhǔn)，通常是密鑰數(shù)以2為底的對數(shù)。 H（K） = log2k,2.1.4 確定性距離,對于長度為n的消息，能夠?qū)⒁欢蚊芪南⒔饷艹膳c原始明文同種語言的可懂文本的密鑰個數(shù)為：2H(K)- nD

11、 - 1 確定性距離：能夠唯一地確定密鑰的最短的密文長度的近似值。 對稱密碼系統(tǒng)的確定性距離：定義為密碼系統(tǒng)的熵除以語言的冗余度。 U = H（K）/ D 理想安全的密碼系統(tǒng)：確定性距離無限大的密碼系統(tǒng)。,2.1.5 混亂與擴(kuò)散,混亂：在加密變換中，讓密鑰與密文的關(guān)系盡可能復(fù)雜的做法。 實現(xiàn)混亂的方法：代替 擴(kuò)散：在加密過程中，盡可能將明文的位置統(tǒng)計特性在密文中消除。 實現(xiàn)擴(kuò)散的方法：換位,2.2 復(fù)雜性理論,2.2.1 算法復(fù)雜性 2.2.2 問題復(fù)雜性,2.2.1 算法復(fù)雜性,算法的復(fù)雜性通常由兩個變量來衡量：T（時間復(fù)雜性）和S（空間復(fù)雜性，或存儲需求）。 T和S都用n的函數(shù)來表示，其中

12、n為輸入的大小。 數(shù)量級法：當(dāng)n增大時，復(fù)雜性函數(shù)中增加得最快的一項。,多項式時間算法： O(1)：常數(shù)的 O(n)：線性的 O(n2)：平方的 O(nm)：m為常數(shù) 指數(shù)時間算法：O(tf(n)，其中t為大于1的常數(shù)，f(n)為n的多項式函數(shù)。 超多項式時間算法：O(cf(n)，其中c為大于1的常數(shù)，f(n)大于常數(shù)，小于線性。,2.2.2 問題復(fù)雜性,圖靈機：一個有限狀態(tài)機，具有無限的讀寫存儲磁帶，是一個理想化的計算模型。 問題： 易解的問題：可以在多項式時間內(nèi)求解 難解的問題：只能在指數(shù)時間內(nèi)求解 不確定的問題：找不出解決的算法，不考慮算法的時間復(fù)雜性,問題復(fù)雜性的劃分： P問題：可以在

13、多項式時間內(nèi)求解的問題。 NP問題：只能在一個非確定性的圖靈機（能夠進(jìn)行猜測的一種圖靈機）上在多項式時間內(nèi)求解的問題。 NP完全問題：一些特定的NP問題，與其他NP問題同等困難。 P空間問題：可以在多項式空間內(nèi)求解，但不能在多項式時間內(nèi)求解的問題。 P空間完全問題：與其他P空間問題同等困難。 指數(shù)時間問題,2.3 初等數(shù)論,2.3.1 模運算 2.3.2 素數(shù) 2.3.3 最大公因數(shù) 2.3.4 乘法逆元素 2.3.5 Fermat小定理及歐拉函數(shù) 2.3.6 中國剩余定理 2.3.7 二次剩余 2.3.8 Legendre（勒讓得）符號 2.3.9 Jacobi（雅各比）符號 2.3.10

14、生成元 2.3.11 有限域中的計算,2.3.1 模運算,同余：如果a = b + kn，k為整數(shù)，則 a b（mod n） a mod n ：a模n操作，表示a除以n的余數(shù)，為 0到n 1之間的整數(shù)。 例如：(79) mod 12 = 16 mod 12 = 4,模運算（+、 ）滿足交換律、結(jié)合律和分配律。 (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*b) mod n=(a mod n)*(b mod n) mod n (a*(b+c) mod n=(a*b mod n)+(a*c

15、mod n) mod n,按模計算原理：對中間結(jié)果作模運算與做完了全部運算后再做模運算結(jié)果相同。 求:1711mod 26=?,按模指數(shù)運算：am mod n 將指數(shù)運算作為一系列乘法運算，每次做一次模運算。 例：a8 mod n = (a2 mod n)2 mod n)2 mod n 當(dāng)m不是2的乘方時，將m表示成2的乘方和的形式。 例如：25=(11001)2，即25=24+23+20 a25 mod n = (a16 a8 a) mod n = (a2)2)2)2 (a2)2)2 a) mod n = (a2 a)2)2)2 a) mod n 適當(dāng)存儲中間結(jié)果，則只需6次乘法： (a2m

16、od n) a)mod n)2mod n)2mod n)2mod n) a)mod n,求1711mod26=?,2.3.2 素數(shù),素數(shù)（質(zhì)數(shù)）：大于1的整數(shù)，只能被1和本身整除。 有無窮多個素數(shù)。 如：2，73，2521，2365347734339，2756839-1,2.3.3 最大公因數(shù),公因數(shù)：兩個整數(shù)a，b的公因數(shù)定義為能同時整除a，b的所有整數(shù)。 最大公因數(shù)：a與b的公因數(shù)中能被所有a，b的公因數(shù)整除的正整數(shù)，記為gcd(a，b)。 互素（互質(zhì)）：兩個整數(shù)稱為互素的，如果它們除了1以外沒有其他的公因數(shù)，即 gcd(a,b)=1。,最大公因數(shù)的求法：輾轉(zhuǎn)相除法即Euclid算法 例如

17、：求gcd(15,36) 36=15 2+6 15=6 2+3 6=3 2+0 因此，gcd(15,36)=3 原理：若a b (mod c)，則 gcd(a,c) = gcd(b,c) 這里，gcd(15,36) = gcd(15,6) = gcd(6,3) = 3 理論基礎(chǔ):若a=bq+r，則gcd（a,b）=gcd（b,r）,定理：若a=bq+r，則gcd（a,b）=gcd（b,r） 那么：gcd（a,b）=gcd(b, a mod b) until a mod b =0 then b is the result. 證明：d=（a,b），d=（b,r） d|(a bq) d|r，d為b,

18、r的公因數(shù)；d|d d=hd d|(bq+r) d|a，d為a,b的公因數(shù)；d|d d=kd 所以 kh=1, 由于d,d都為正整數(shù)，所以k和h也都為正整數(shù)，故： k=h=1；,2.3.4 乘法逆元素,定理：axb mod n有解的充要條件是d|b，其中d=gcd（a，n）。 我們關(guān)心下列同余式：（b=1時） 當(dāng)b=1時，d=1，即可得： 如果gcd(a,n)=1，則ax 1 mod n有解。 如果ax 1 mod n有解，則gcd(a,n)=1。,2.3.4 乘法逆元素,求x，滿足 (a x) mod n = 1, 即 x a-1(mod n) 當(dāng)a與n互素時, 方程 x a-1(mod n

19、) 有唯一解； 當(dāng)a與n不互素時, 此方程無解。 如果n為素數(shù)，則從1到n-1的任意整數(shù)都與n互素，即在1到n-1之間都恰好有一個關(guān)于模n的乘法逆元。 求乘法逆元：擴(kuò)展的Euclid算法 例：求5關(guān)于模14的乘法逆元素 輾轉(zhuǎn)相除：14 = 5 2 + 4 5 = 4 + 1 逆推：1 = 5 - 4 = 5 - （14 - 5 2）= 5 3 - 14 因此，5關(guān)于模14的乘法逆元為3。,練習(xí),練習(xí)：求17關(guān)于模26的乘法逆元素。,答案：23 26 = 17 + 9 1 = 9 - 8 17 = 9 + 8 = 9 - (17 - 9) 9 = 8 + 1 = 9 2 - 17 = (26 -

20、 17) 2 - 17 = 26 2 - 17 3 = 17 (-3) + 26 2 (17 23 - 26 15),2.3.5 Fermat小定理及歐拉函數(shù),Fermat小定理：如果m為素數(shù)，a不能被m整除，則 am-1 1 (mod m) n為正整數(shù)，Zn=0，1，2，n-1為模n的集合，Zn為模n的完全剩余集。 Zn*=a Zn| gcd(a,n)=1稱為模n的簡化剩余集。 （n）=| Zn*|, 表示Zn*元素的個數(shù)。稱為歐拉函數(shù), （n）為n的歐拉函數(shù)值。 如果n是素數(shù)，則(n) = n-1 設(shè)n = p1r1 p2r2 pmrm, 其中p1, p2, ,pm是n的素數(shù)因子, 則 (

21、n) = n (1-1/p1) (1-1/p2) (1-1/pm) =(n/ (p1 p2 pm) (p1-1) (p2-1) (pm-1) (8)=？,如果n = pq，其中p和q為素數(shù)，則 (n)= (p 1)(q 1)。 例：n=15,求(15). 解： Zn=0，1，2，3，4，14 Zn*=1，2，4，7，8，11，13，14，因此 (15)=8 15=3*5 （15）= (3-1)*(5-1)=8 ,歐拉擴(kuò)展的Fermat小定理,歐拉擴(kuò)展的Fermat小定理： 如果gcd(a,n) = 1，則 a(n) mod n = 1。 即： 如果gcd(a,n) = 1，則a*a (n)-1

22、 mod n=1 即a關(guān)于mod n的乘法逆元素為a (n)-1 再求：17關(guān)于模26的乘法逆元素？,中國剩余定理-韓信點兵,秦朝末年，楚漢相爭。一次，韓信將1500名將士與楚王大將李鋒交戰(zhàn)。苦戰(zhàn)一場，楚軍不敵，敗退回營，漢軍也死傷四五百人，于是韓信整頓兵馬也返回大本營。當(dāng)行至一山坡，忽有后軍來報，說有楚軍騎兵追來。只見遠(yuǎn)方塵土飛揚，殺聲震天。漢軍本來已十分疲憊，這時隊伍大嘩。韓信兵馬到坡頂，見來敵不足五百騎，便急速點兵迎敵。他命令士兵3人一排，結(jié)果多出2名；接著命令士兵5人一排，結(jié)果多出3名；他又命令士兵7人一排，結(jié)果又多出2名。韓信馬上向?qū)⑹總冃迹何臆娪?073名勇士，敵人不足五百，我們

23、居高臨下，以眾擊寡，一定能打敗敵人。漢軍本來就信服自己的統(tǒng)帥，這一來更相信韓信是“神仙下凡”、“神機妙算”。于是士氣大振。一時間旌旗搖動，鼓聲喧天，漢軍步步進(jìn)逼，楚軍亂作一團(tuán)。交戰(zhàn)不久，楚軍大敗而逃。,我國古代數(shù)學(xué)名著孫子算經(jīng)中，提出了聞名于世的“物不知數(shù)”問題。原文是： “今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？”,這個問題的解法,()“笨”算法 原來的問題題意是：求一數(shù)，三除余二，五除余三，七除余二。 因為以3除余2，以7除余2的數(shù)，所以以21除也余2 而23是以3，7除余2的最小數(shù)，它剛好又是以5除余3的數(shù)。,()古代的口訣解法 程大位著的算法統(tǒng)宗，對“物不知

24、其數(shù)”的問題的解答方法用下面的口訣標(biāo)出： “三人同行七十稀，五樹梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知?！?“三人同行七十稀，五樹梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知?！?它的意義是： 以70乘用3除的余數(shù)2，21乘用5除的余數(shù)3，15乘用7除的余數(shù)2，然后總加起來。如果它大于105，則減105，若仍大再減，最后得出來的正整數(shù)就是答案了。,它的形式是： 270321215=233， 兩次減去105，得23，這就是答案了。,70，21，15的性質(zhì),70是用3除余1，5與7都除得盡的數(shù)，所以70a是一個用3除余a而5與7除都除得盡的數(shù)。 21是用5除余1，3與7除得盡的數(shù)，所以21b是用

25、5除余b，而3與7除得盡的數(shù)。 同理，15c是用7除余c而3與5除得盡的數(shù)。 因而： 70a21b15c 是一個3除余a，5除余b，7除余c的數(shù)，也就是可能的解答之一，但可能不是最小的。這數(shù)加減105后都仍然有同樣的性質(zhì)，所以可以多次減去105而得到答案。,“三人同行七十稀，五樹梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知”。用現(xiàn)代術(shù)語翻譯，其口訣實際上是： N=70r121r215r3-105p， 其中ri(i=1，2，3)分別是余數(shù)，p是使N0的任一整數(shù)。,推廣開來,若某數(shù)N分別被稱為定母的d1，d2，d3，dn除得的余數(shù)為r1，r2，r3，rn，則 N=k1r1k2r2k3r3knrn-p

26、q， 其中k1是d2，d3，d4，dn的公倍數(shù)，且被d1除余1；k2是d1，d3，d4，dn的公倍數(shù)，且被d2 除余1；kn是d1，d2，d3，dn-1的公倍數(shù)，且被dn除余1p是任意整數(shù)，q是d1，d2，d3，dn的最小公倍數(shù)。,上式的關(guān)鍵在于“求一”，即求“一個數(shù)的多少倍除以另一數(shù)，所得余數(shù)為1”的方法，也即求出公式中的“ki”,這個方法的研究，是由我國宋代著名數(shù)學(xué)家秦九韶(約12021261)在其名著數(shù)書九章一書中完滿解決的。他把它稱作“大衍求一術(shù)”。 類似的理論成果，在歐洲直到18，19世紀(jì)才由著名數(shù)學(xué)家歐拉和高斯獲得，最早出現(xiàn)在高斯1801年出版的算術(shù)研究一書里。而這，已是秦九韶之后

27、500多年的事了。 因而，上述成果被稱為“中國剩余定理”，或“孫子定理”。,思考?,“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩四。問物幾何？” （70*2+21*3+15*4）mod 3*5*7=? =53,2.3.6 中國剩余定理,定理：如果n的素數(shù)因子分解式為p1p2 pt，則一組方程 (x mod pi）= ai，其中i = 1,2,t，有唯一解x，其中x小于n（其中某些pi可能相等）。 例：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？ x mod 3 = 2 x mod 5 = 3 x mod 7 = 2,定理：令d1，d2，,dt為兩兩互素，并令

28、n=d1d2dt，則 x mod di xi (I=1, t) 在0，n-1范圍內(nèi)有公共解x： x= mod n 其中：mi=n/di，yi=mi-1 mod di,解法： 令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7， n=p1 p2 p3=105， M1=n/p1=35, M2=n/p2=21, M3=n/p3=15 求解 35 x1 mod 3=1, 得x1=2 求解 21 x2 mod 5=1, 得x2=1 求解 15 x3 mod 3=1, 得x3=1 則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 2 2+21 1 3

29、+15 1 2) mod 105 = 233 mod 105 = 23,2.3.7 二次剩余,定義：設(shè)整數(shù)n1。對于aZn*，如果存在x Zn ，滿足x2a（modn）有解，則稱a為模n的二次剩余（或平方剩余）；否則，稱a為模n二次非剩余（或平方非剩余）。用QRn表示模n的二次剩余集合，用QNRn表示模n的二次非剩余集合。,例如： 322（mod7），則2 QR7 求QR7 =？ QNR7 =？,2.3.8 Legendre（勒讓德）符號,記為L(a,p)，叫做a模p的勒讓德符號。其中a為任意整數(shù)，p為大于2的素數(shù)。 定義： L(a,p) = 0，如果a能被p整除； L(a,p) = 1，如果

30、a是模p的二次剩余； L(a,p) = -1，如果a是模p的非二次剩余； 計算：L(a,p) = a(p-1)/2 mod p 計算法則（略）,計 算,L(1,7) =？ L(2,7) =？ L(3,7) =？ L(4,7) =？ L(5,7) =？ L(6,7) =？,2.3.9 Jacobi（雅各比）符號,記為J(a,n)，是Legendre符號的擴(kuò)展，其中a為任意整數(shù)，而n為任意奇數(shù)。 定義： J(a,n)只對n為奇數(shù)時有意義 J(0,n)=0 如果n為素數(shù)，且n|a，則J(a,n)=0 如果n為素數(shù)，且a是模n的二次剩余，則J(a,n) = 1 如果n為素數(shù)，且a是模n的非二次剩余，則

31、J(a,n) = -1 如果n是合數(shù)，則J(a,n)=J(a,p1)J(a,p2)J(a,pm)，其中將n因數(shù)分解為p1p2pm,Jacobi符號的計算（P19） Blum整數(shù)： 若p和q為兩個素數(shù)，且都與3模4同余，則n = pq稱為Blum整數(shù)。 若n為Blum整數(shù)，則每個模n的二次剩余恰好有4個平方根，其中一個也是一個二次剩余，稱為原平方根。 例如，139的模437的原平方根為24，另三個平方根為185，252和413。,2.3.10 生成元,定義：如果p為素數(shù)，g小于p，如果對每個b從1到p-1，存在a，使ga b (mod p)，則g為模p的生成元?；蛘哒fg是關(guān)于模p的原根。 例：p

32、=11，2為模11的生成元 P20,生成元的測試,測試一個數(shù)是否為生成元不太容易。如果知道p 1的因數(shù)分解式，就很容易。 令q1，q2，qn為p 1的素數(shù)因子，且q1，q2，qn兩兩不同，則測試給定數(shù)g是否為p的生成元時，對所有的q = q1，q2，qn計算 g（p - 1）/ q mod p 若對某個q值，g（p - 1）/ q mod p為1，則g不是生成元。反之，則是生成元。,生成元的測試,測試3是否為模11的生成元.,測試如下： 即p=11，則p-1=10=2*5 g（p - 1）/ q mod p=？ 3（11-1）/2 mod 11=1 3（11-1）/5 mod 11=9,所以3

33、不是模11的生成元。,伽羅瓦Galois, Evariste （1811-1832）,Galois（伽羅瓦）一共參加了2次Ecole Polytechnique（巴黎理工大學(xué)）的考試 第一次，由于口試的時候不愿意做解釋，并且顯得無理，結(jié)果被據(jù)了。他當(dāng)時大概十七八歲，年輕氣盛，大部分東西的論證都是馬馬虎虎，一般懶的寫清楚,并且拒絕采取考官給的建議。 第二次口試的時候，邏輯上的跳躍使考官Dinet感到困惑，后來Galois感覺很不好，一怒之下，把黑板擦擲向Dinet,并且直接命中。 最后和Galois決斗的那個人，是當(dāng)時法國最好的槍手，Galois的勇氣令人欽佩。兩個人決斗的時候，相距25步，Ga

34、lois被擊中了腹部。,伽羅瓦(Evariste Galois)1811年10月25日生于巴黎附近的一個小城。 1829年他兩次投考巴黎理工大學(xué)，卻因思想激進(jìn)，兩次被拒絕錄取，最后只好進(jìn)入高等師范學(xué)校學(xué)習(xí)。 1829年5月，17歲的他寫出了關(guān)于五次方程的代數(shù)解法的論文，論文中首次引入“群”的概念。他把論文寄給柯西，請他交給法蘭西科學(xué)院審查?？挛鲗Υ烁静恍家活?，把這個中學(xué)生的文章給弄丟了。 1830年2月伽羅瓦再次將他的研究成果寫成一篇詳細(xì)的論文，寄給科學(xué)院秘書傅立葉，希望能得到數(shù)學(xué)大獎，不料當(dāng)年5月傅立葉病死，伽羅瓦的文稿再次被丟失。 1831年伽羅瓦第三次將論文送交法國科學(xué)院。泊松院士看了

35、4個月，最后在論文上批道：“完全無法理解”。泊松的不公正評價，使他受到很大打擊。 這些大數(shù)學(xué)家的傲慢和自大，使得伽羅瓦的理論被埋沒了將近50年。,伽羅瓦因為政治激進(jìn)，被陰謀的政客們用一件小事慫恿和一個軍官決斗。在決斗前一個晚上，他急切地寫著他的遺言。 想在死亡來臨之前盡快把他的思想中那些有意義的東西寫出來。他不時中斷，在紙邊空白處寫上“我沒有時間，我沒有時間?！?接著伽羅瓦又寫下一個潦草的大綱。 他在天亮之前那最后幾個小時寫出的東西，一勞永逸地給一個折磨了數(shù)學(xué)家?guī)讉€世紀(jì)的難題找到了真正的答案，開創(chuàng)了數(shù)學(xué)上的一個重要的分支群論。 伽羅瓦在決斗中被打成重傷，死在家里，年僅21歲。,年，也就是伽羅瓦

36、死后年，他的遺稿才得以發(fā)表。隨著數(shù)學(xué)的發(fā)展和時間的推移，伽羅瓦研究成果的重要意義愈來愈為人們所認(rèn)識。 他的最主要成就是提出了群的概念，用群論徹底解決了根式求解代數(shù)方程的問題，而且由此發(fā)展了一整套關(guān)于群和域的理論，為了紀(jì)念他，人們稱之為伽羅瓦理論。伽羅瓦理論對近代數(shù)學(xué)的發(fā)展產(chǎn)生了深遠(yuǎn)影響，它已滲透到數(shù)學(xué)的很多分支中。,2.3.11 有限域中的計算,有限域：元素個數(shù)有限的域，也叫伽羅瓦（Galois）域。 在有限域中，非0數(shù)的加、減、乘、除都有定義。加法單位元是0，乘法單位元是1，每個非0元素都有一個唯一的乘法逆元。 有限域中運算滿足交換律、結(jié)合律和分配律。 有限域中元素個數(shù)為素數(shù)或素數(shù)的乘方：設(shè)

37、p為素數(shù)，則有限域可記為GF(p)或GF(pn)。,不可約多項式：一個多項式如果除了1和本身外，不能分解成其他多項式的乘積形式，則成為不可約多項式。 本原多項式：一個有限域內(nèi)的生成元多項式，其系數(shù)是互素的。 在GF(qn)中，所有運算都是模p(x)的運算，其中p(x)是n階不可約多項式。,一般研究GF（2n），如GF（25）：a(x)=x4+x3+1表示11001。 若p（x）不能分解為次數(shù)小于n的多項式之積，則p（x）稱既約多項式。 二元多項式系數(shù)的運算： （U +V）mod 2 =U V UV = U V UV = U V,例：GF（25）：a(x)= x4+x2+1,b(x)= x3+

38、x2 ab=10101+01100=11001 例：a=101，p（x）=x+x+1，GF（2），求（aa）mod p（x） aa=10001，p（x）= x+x+1=1011 （aa）mod p（x）=10001 mod 1011 = 111 =x+x+1,2.4 因數(shù)分解,對一個數(shù)進(jìn)行因數(shù)分解，是指找出這個數(shù)的素數(shù)因子。 60=2*2*3*5 252601=41*61*101 2113-1=3391*23279* 現(xiàn)代因數(shù)分解的一些算法P21,2.5 素數(shù)的產(chǎn)生,2.5.1 Solovay-Strassen方法 2.5.2 Lehmann法 2.5.3 Rabin-Miller法 2.5.

39、4 實際應(yīng)用 2.5.5 強素數(shù),2.5.1 Solovay-Strassen方法,用Jacobi符號來測試p是否為素數(shù)： （1）選擇一個隨機數(shù)a，ap； （2）如果gcd(a,p)1，則p是合數(shù)，停止檢測； （3）計算i=a(p-1)/2 mod p； =L(a,p)? （4）計算Jacobi符號J(a,p)； （5）如果i J(a,p)，則p不是素數(shù)； （6）如果i= J(a,p)，則p不是素數(shù)的概率小于50%。 對t個不同的隨機數(shù)a，重復(fù)進(jìn)行這個測試。能通過所有t個測試的奇數(shù)是合數(shù)的概率小于1/2t。,2.5.2 Lehmann法,測試p是否為素數(shù)： （1）選擇一個小于p的隨機數(shù)a； （

40、2）計算a(p-1)/2 mod p； （3）如果a(p-1)/2 mod p 1或1( mod p) ，則p不是素數(shù)； （4）如果a(p-1)/2 mod p 1或1( mod p) ，則p不是素數(shù)的概率小于50%。,2.5.3 Rabin-Miller法,選擇一個隨機數(shù)p，進(jìn)行測試。 計算b，其中b是能整除p-1的2的次方數(shù)（即2b是指整除p-1的最大的2的冪），然后計算m，使得p=1+2b*m。 （1）選擇一個隨機數(shù)a，使a小于p； （2）令i=0，Z=am mod p； （3）如果Z=1，或Z=p-1，則p可能是素數(shù)，通過了檢測； （4）如果i0，且Z=1，則p不是素數(shù)； （5）令i=

41、i+1，如果ib且Z p-1，令Z=Z2 mod p，返回第（4）步。如果Z =p-1，則p通過檢測，可能是素數(shù)； （6）如果i=b且Z p-1，則p不是素數(shù)。 一個奇合數(shù)通過t次測試的概率小于1/4t。,2.5.4 實際應(yīng)用,（1）產(chǎn)生一個n位隨機數(shù)p（n位二進(jìn)制）； （2）將最高位和最低位置為1； （3）檢查p是否能被小素數(shù)整除：3，5，7，11，等等。許多實際應(yīng)用中都用小于256地所有素數(shù)去除p； （4）對于隨機數(shù)a，進(jìn)行Rabin-Miller測試，如果p通過了，則產(chǎn)生另一個隨機數(shù)a，再進(jìn)行測試。選擇值小一些的a可以令計算更快。做5次測試，如果p沒通過其中的一次，則產(chǎn)生另一個p再測試。

42、,2.5.5 強素數(shù),強素數(shù)p,q：能令乘積n難以用特定的因數(shù)分解算法進(jìn)行因數(shù)分解的素數(shù)。 性質(zhì)： p-1和q - 1的最大公因數(shù)很小 p-1和q-1都有大素數(shù)因子，記為p，q； p -1和q-1都有大素數(shù)因子； p +1和q+1應(yīng)該都有大素數(shù)因子； (p-1)/2和(q-1)/2都是素數(shù)。,2.6 有限域內(nèi)的離散對數(shù),求x，使ax b (mod n) 當(dāng)n很大時，這是一個困難的問題 并非所有的離散對數(shù)問題都有解 密碼學(xué)中常用的離散對數(shù)： GF(p)的乘法群 GF(2n)的乘法群 EC(F),2.7 單向哈希函數(shù),定義：一個單向哈希函數(shù)H(M)，操作一個任意長度的消息M，返回一個固定長度的值h。h = H(M) 。 性質(zhì)： 給定M，很容易計算h； 給定h，很難計算M，使H(M)=h； 給定M，很難找到另一個消息M，使H(M)=H(M)。,MD5算法(P27),輸入：將明文分成512位的塊,再將其分成16個32位的子塊M0M15 輸出：4個32位的塊（a,b,c,d），將這四個32位分組級聯(lián)后將生成一個128位散列值。,消息填充,在md5算法中，首先需要對信息進(jìn)行填充，使其字節(jié)長度對512求余的結(jié)果等于448。 因此，信息的字節(jié)長度（bits length）將被擴(kuò)展至n*512+448，即n*64+56個字節(jié)（bytes），n為一個正整數(shù)。 填充方法：在信息的后