初等數(shù)論 t第五、六章復習

1、初等數(shù)論 - 第六章 指數(shù)與原根,,第五章 二次同余式與平方剩余,2,掌握平方剩余與平方非剩余定義；求解平方剩余與平方非剩余；判斷二次同余式是否有解及解數(shù)掌握歐拉判別條件內容及證明掌握勒讓德符號定義及性質；求解勒讓德符號掌握雅克比符號定義及性質；求解雅克比符號,§1 一般二次同余式,3,4,§2 平方剩余和平方非剩余,5,6,7,8,9,10,11,12,13,14,§3 Leg

2、endre符號, Gauss二次互反律,15,16,17,18,19,20,21,22,23,24,§5 Jacobi符號,25,26,27,28,29,30,31,§6 合數(shù)模的情形,32,33,34,35,36,37,第六章 指數(shù)與原根,38,掌握指數(shù)定義及性質；求解指數(shù)掌握原根的定義；原根存在的條件；求解原根掌握指標的定義及性質；求解指標表掌握n次剩余與n次非剩余的定義；掌握二項同余方程有解的條件及解

3、數(shù)掌握離散對數(shù)問題，DH密鑰交換算法、ElGamal數(shù)字簽名算法,§1 指數(shù),§2 原根,§3 指標、二項同余方程,離散對數(shù),,,,Diffie 和Hellman在1976年提出的Diffie-Hellman密鑰交換協(xié)議，是一個典型的密鑰協(xié)商協(xié)議；允許兩個用戶可以安全地交換一個秘密信息，用于后續(xù)的通訊過程算法的安全性依賴于計算離散對數(shù)的難度,生成元,,,,離散對數(shù)的概念,對于一個整數(shù)b和素數(shù)q的

4、一個生成元a，可以找到一個唯一的指數(shù)i，使得： 成立，則指數(shù)i稱為b的以a為底數(shù)的模q的離散對數(shù)。,離散對數(shù)的難解性,對于給定的a、i和q，容易計算出b，但給定b、a和q，計算出i一般非常困難。這就是包括DH密鑰交換算法和DSA數(shù)字簽名算法等在內的許多公鑰密碼算法的基礎。,Diffie-Hellman密鑰交換算法,目的：用戶A和用戶B需要安全地交換一個密鑰（即秘密共享一個密鑰，這個密鑰可以用于對稱密碼加密）步驟：（1）

5、A和B都知道一個素數(shù)q和一個整數(shù)a（均公開）， a是q的一個原根（2）用戶A選擇一個隨機數(shù) XA<q ，并計算 類似地，用戶B選擇一個隨機數(shù) XB<q , 并計算,Diffie-Hellman密鑰交換算法,（3）每一方都對X的值保密存放；使Y的值公開，另一方可以得到（4）用戶A計算密鑰：

6、 用戶B計算密鑰：（5）這里雙方計算出的K就是共享的密鑰，雙方以K作為加、解密密鑰，以對稱密鑰算法進行保密通信。（6）整個系統(tǒng)中，A、B雙方各自的X值為各自的私鑰，保密；各自的Y值為公鑰，公開。,DH例子,素數(shù)q=97,它的一個本原元a=5A和B分別選擇隨機數(shù)Xa=36和Xb=58A計算公開密鑰：Ya=536mod97=50mod97 B計算公開密鑰：Yb=558mod97=44mod97 A計算會話密鑰：K

7、= 4436mod97=75mod97B計算會話密鑰：K= 5058mod97=75mod97,DH算法的證明,下面證明A、B雙方計算出的K是相同的：,由于攻擊者不知道XA和XB，它可以利用的信息包括：素數(shù)q、整數(shù)a、中間值YA和YB，因此它若想求得XA和XB，據(jù)知，這是求離散對數(shù)的問題，因此，DH算法的安全性依賴于離散對數(shù)的難解性。,攻擊者,ElGamal Signature Scheme,存在一個相關的簽名算法 安全性是基

8、于計算離散對數(shù)的困難性方案的密鑰生成是相同的: 有個共享的素數(shù) p, 公開的本原根 a 每個用戶選擇一個隨機數(shù)作為私鑰 x 計算各自的公開密鑰: y = ax mod p 公鑰是 (y,a,p) 私鑰是 (x),ElGamal 簽名方案的使用,簽名消息 M: 選擇隨機數(shù) k, GCD(k,p-1)=1 計算 K = ak(mod p) 用 Euclidean (inverse) 擴展算法求S:M = xK + kS

9、mod (p-1); 即求S = k-1(M - x.K) mod (p-1) 簽名是 (K,S) k 應該被銷毀同ElGamal 加密方案， 簽名信息也是消息的2倍驗證 (K,S) 是 對M的簽名: yK.KSmod p = aMmod p,ElGamal 簽名方案舉例,取 p=11, g=2 選擇私鑰 x=8 計算: y = ax mod p = 28 mod 11 = 3 公鑰是: y=3,g=2,p=11 對

10、 M=5 簽名：選擇隨機數(shù) k=9 確定 GCD(10,9)=1 計算: K = ak mod p = 29 mod 11 = 6 解: 5 = 8×6+9×S mod 10; nb 9-1 = 9 mod 10;因此 S = 9×(5-8×6) = 3 mod 10 簽名是 (K=6,S=3) 要驗證簽名, 確認:36.63 = 25 mod 113.7 = 32 = 10 m