初等數(shù)論ppt(12)第六章---指數(shù)與原根

1、初等數(shù)論 - 第六章 指數(shù)與原根,,本章內(nèi)容,§1 指數(shù),§1 指數(shù),§2 原根,§3 指標(biāo)、二項(xiàng)同余方程,離散對(duì)數(shù),,,,Diffie 和Hellman在1976年提出的Diffie-Hellman密鑰交換協(xié)議，是一個(gè)典型的密鑰協(xié)商協(xié)議；允許兩個(gè)用戶可以安全地交換一個(gè)秘密信息，用于后續(xù)的通訊過(guò)程算法的安全性依賴于計(jì)算離散對(duì)數(shù)的難度,生成元,,,,離散對(duì)數(shù)的概念,對(duì)于一

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

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

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

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

6、名算法 安全性是基于計(jì)算離散對(duì)數(shù)的困難性方案的密鑰生成是相同的: 有個(gè)共享的素?cái)?shù) p, 公開的本原根 a 每個(gè)用戶選擇一個(gè)隨機(jī)數(shù)作為私鑰 x 計(jì)算各自的公開密鑰: y = ax mod p 公鑰是 (y,a,p) 私鑰是 (x),El Gamal 簽名方案的使用,簽名消息 M: 選擇隨機(jī)數(shù) k, GCD(k,p-1)=1 計(jì)算 K = ak(mod p) 用 Euclidean (inverse) 擴(kuò)展算法求S:M

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

8、g=2,p=11 對(duì) M=5 簽名：選擇隨機(jī)數(shù) k=9 確定 gcd(10,9)=1 計(jì)算: 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) 要驗(yàn)證簽名, 確認(rèn):36.63 = 25 mod 113.7 = 32 = 10 mod 11,作業(yè)1