ElGamal公鑰密碼算法的教學設計與思考

李瑞林, 馮 超, 張 琛, 唐朝京

(國防科技大學 電子科學學院， 湖南 長沙 410073)

0 引言

隨著網(wǎng)絡空間安全成為一級學科，“密碼學與網(wǎng)絡安全”課程受到高度重視[1]。該課程特有的跨學科特性使很多學生在學習過程中感覺到其知識點繁多、凌亂、不夠系統(tǒng)，進而導致學生花相當多的時間精力死記硬背知識要點，這樣做既吃力又達不到真正目的。通常來講，我們通過一門課程的開設，希望學生能夠在知識目標、能力目標和素質(zhì)目標等三個方面得到提升，而知識目標作為基礎，其掌握的熟練程度，直接會影響到能力目標和素質(zhì)目標的實現(xiàn)。因此，系統(tǒng)梳理該課程知識體系，通過精心的教學設計，把看似凌亂的知識點進行有機組合，引導學生主動思考，培養(yǎng)學生學習興趣，就成為教學過程中的重要環(huán)節(jié)。

對稱密碼學、非對稱密碼學和密碼協(xié)議是“密碼學與網(wǎng)絡安全”課程的核心內(nèi)容。非對稱密碼學(又稱公鑰密碼學)自1976年由Diffie和Hellman提出之后，由于其顛覆式的創(chuàng)新理念，被視為整個密碼學發(fā)展史上最偉大的一次革命[2]。因此，相關內(nèi)容在“密碼學與網(wǎng)絡安全”課程教學中占有非常重要的地位。最著名也是應用最廣的公鑰密碼算法是RSA算法，該算法是基于大整數(shù)分解這一困難問題而設計的， RSA算法的數(shù)學原理與編程實現(xiàn)等方面在課程的教學上占用了大量課時，使學生對該算法的掌握較為扎實。除了RSA公鑰算法之外，還有另外一類公鑰密碼算法即ElGamal算法，它針對計算離散對數(shù)的困難性問題而設計，雖然沒有RSA密碼算法應用廣泛，但該算法設計新穎巧妙，數(shù)學原理簡單明了，為后續(xù)著名的橢圓曲線密碼算法的設計提供了參考[3]。鑒于此，不少課程都將ElGamal算法作為知識點加以講解，但知識傳授僅限于對加解密公式推導的正確性驗證，致使很多學生對ElGama算法為何設計成這種形式，它與Diffie-Hellman密鑰交換協(xié)議之間存在什么樣的關系等存在疑惑。

針對這些問題，本文提出了一種ElGamal密碼算法的教學設計，充分挖掘Diffie-Hellman密鑰交換協(xié)議(簡稱DH密鑰交換協(xié)議)在該加密算法中所扮演的角色，以問題導向為牽引，引發(fā)學生對該加密算法的深入思考和深刻認識，既充分調(diào)動了他們學習“密碼學與網(wǎng)絡安全”課程的興趣，又逐步培養(yǎng)了他們研究式、自主式學習的能力，最終達到更好的教學質(zhì)量與效果。

1 教學過程設計

本文給出的ElGamal密碼算法的教學設計包括如下四個部分：①回顧公鑰密碼的背景及基本概念，提出基本問題；②介紹Diffie和Hellman提出的密鑰交換協(xié)議；③引導學生思考Diffie-Hellman密鑰交換協(xié)議與公鑰密碼算法之間的關系；④啟發(fā)學生分析如何將DH密鑰交換協(xié)議轉(zhuǎn)化為公鑰密碼算法，并給出ElGamal密碼算法的標準定義。

1.1 教學環(huán)節(jié)一：公鑰密碼學背景及基本概念

教師首先引入公鑰密碼產(chǎn)生的背景：在傳統(tǒng)的對稱加密方案里，通信雙方必須共享一段秘密信息(密鑰)，且該密鑰不能泄露給任何第三方，否則就無法保證通信的安全。隨著網(wǎng)絡與通信技術(shù)的發(fā)展，傳統(tǒng)加密技術(shù)中涉及的密鑰管理，特別是密鑰分發(fā)問題成為制約對稱密碼大規(guī)模應用的一個主要瓶頸。在包含n個節(jié)點的通信網(wǎng)絡中，為保障安全通信，每個節(jié)點均需要保管與其它n-1個節(jié)點共享的密鑰。因此，整個網(wǎng)絡就需要保護n*(n-1)/2個密鑰，大大增加了密鑰管理的負擔。

為解決這一問題， Diffie(迪菲)和Hellman(赫爾曼)于1976 年在美國國家計算機大會上提出了公開密碼學的思想，這項舉措被后人稱為密碼史上最偉大的一次革命，對密碼學領域的發(fā)展有重要的意義。次年，Diffie和Hellman在IEEE信息論?？弦匝垐蟾娴拿x撰寫了“密碼學中的新方向”一文，系統(tǒng)闡述了“公鑰密碼學”的基本思想、核心概念及應用場景。Diffie和Hellman解決問題的出發(fā)點與傳統(tǒng)對稱密碼正好相反，即能否讓用戶的密鑰公開。為此，他們假設每個用戶至少擁有兩個密鑰：一個用于加密，稱為加密密鑰，一個用于解密，稱為解密密鑰。加密密鑰可以公開(又稱為公鑰)，解密密鑰則必須保密(又稱為私鑰)，而且加密密鑰的公開不會危及解密密鑰的安全。這樣，每個用戶只需保存自己的解密密鑰，從而大大降低密鑰管理的成本與負擔，這就是公鑰密碼解決問題的初衷與基本思想。那么，有什么樣的方法可用于公鑰密碼算法的設計呢？Diffie和Hellman在文中指出了基于單向陷門函數(shù)來構(gòu)造公鑰密碼的可能性，但遺憾的是當時他們尚未給出一個具體的公鑰加密方案。但兩位作者基于一類單向陷門函數(shù)(離散對數(shù)難題)設計了第一個密鑰交換協(xié)議，該協(xié)議允許人們在不安全的信道上通過公開交換信息協(xié)商出安全的密鑰。

1.2 教學環(huán)節(jié)二：DH密鑰交換協(xié)議回顧

這一教學環(huán)節(jié)主要回顧離散對數(shù)難題，并介紹DH密鑰交換協(xié)議。

1)離散對數(shù)

(1)回顧離散對數(shù)基本概念：給定素數(shù)p，存在p的本原根r，使得r,r2, …,rp-1(modp) 兩兩不同，且都與p互素。這表明r的各次冪模p后恰好可產(chǎn)生從1到p-1之間的每個整數(shù)，即{rmodp,r2modp, …,rp-1modp}={ 1,2,3, …,p-1 }。由此，離散對數(shù)可定義：任意s∈{1, 2, …,p-1}，存在唯一的i(1≤i≤p-1)，使得s≡rimodp，此時稱i為模p下以r為底s的離散對數(shù)，簡稱i為s的離散對數(shù)。

(2)給出離散對數(shù)困難問題定義：給定素數(shù)p及其本原根r，s≡rimodp，則當p為非常大的素數(shù)時，由已知的p,r,s來求離散對數(shù)i是非常困難的事情。

2)DH密鑰交換協(xié)議

DH密鑰交換協(xié)議借助于離散對數(shù)困難問題，在公開信道上交換雙方各自的信息從而聯(lián)合建立了共享的秘密密鑰，聯(lián)合建立的秘密密鑰由每個通信參與者分別產(chǎn)生的參數(shù)通過一定的計算得出，不需要任何可信第三方參與。如圖1所示，假定通信雙方共享大素數(shù)p及其本原根ro若一方Alice希望與通信方Bob建立安全的連接，則Alice與Bob可按照圖中所示的步驟(1)(2)進行信息交互，而后在步驟(3)通過計算獲得共享密鑰K，后續(xù)通信雙方可利用該密鑰K，基于傳統(tǒng)加密算法對通信數(shù)據(jù)進行加密。對攻擊者而言，他可以截獲p,r,Sa,Sb，但若想獲得共享密鑰K=rab的值，他還必須知道a或b的值。因此對于特殊選取的大素數(shù)p而言，由Sa和r來計算a(或由Sb和r來計算b)即計算離散對數(shù)是困難問題，由此可認為該方案協(xié)商出來的K是安全的。

圖1 Diffie-Hellman密鑰交換協(xié)議流程

1.3 教學環(huán)節(jié)三：DH密鑰交換協(xié)議思考

這一教學環(huán)節(jié)主要引導學生對DH密鑰交換協(xié)議進行思考，并啟發(fā)學生思考如何將DH密鑰交換協(xié)議轉(zhuǎn)化為公鑰密碼算法。

教師可以進行提問，既然DH密鑰交換協(xié)議基于離散對數(shù)困難問題，已經(jīng)蘊含了公鑰密碼學的思想，為何當初設計者未能給出一個類似的公鑰加密算法呢？由此，引導學生進行如下的思考、討論和歸納總結(jié)：

提問一：如何定義公鑰和私鑰？根據(jù)圖1所示，Alice可以將本次通信的隨機數(shù)a視為她的私鑰，而將sa=ramodp視為她的公鑰，這樣根據(jù)離散對數(shù)困難問題，由公鑰sa來計算私鑰a在計算上很困難；同理，Bob也可以產(chǎn)生他此次通信的公私鑰對(Sb,b)。

提問二：有了公鑰和私鑰，如何設計加密和解密算法，滿足彼此互逆這一關鍵問題？DH密鑰交換協(xié)議的創(chuàng)新之處在于通過雙方的公鑰{Sa,Sb}聯(lián)合產(chǎn)生了共享密鑰K，很自然一個想法就是雙方基于共享的密鑰K利用傳統(tǒng)的對稱加密算法實現(xiàn)加解密功能。但是這樣設計的算法不能算是公鑰算法，因為里面已經(jīng)摻和了經(jīng)典的加密方案。那如果采用更為簡潔的“一次一密”方案呢？由于每次通信產(chǎn)生的K都是隨機的，我們完全可以利用C=K*Mmodp作為對明文M加密后得到的密文C。

歸納總結(jié)：通過對上述問題的討論，學生們已經(jīng)對DH密鑰交換協(xié)議與公鑰加密算法的關系有了初步的認識。此時，教師可以進一步總結(jié)提問和歸納：既然我們可以利用“一次一密”和DH交換協(xié)議來設計一個公鑰加密方案原型，那么這一原型還有沒有什么缺陷呢？(這里可以請學生深入思考。)教師最后總結(jié)：這個原型方案最大的不足之處在于每次加解密時，通信一方的公鑰都得隨機生成和傳輸，這非但沒能減輕反而加重了密鑰管理的負擔，這顯然是違背于公鑰密碼思想初衷的。因此，擺在學生面前的一個重要問題就集中在如何突破這個屏障，既能充分利用“一次一密”這一簡單加解密方案，又能充分運用公鑰密碼簡化密鑰管理的思想，從而設計出一個真正實用的基于離散對數(shù)困難問題的公鑰加密算法。

1.4 教學環(huán)節(jié)四： ElGamal加密算法設計

這一教學環(huán)節(jié)在前面教學環(huán)節(jié)基礎之上，進一步引導學生探討如何改造DH密鑰交換協(xié)議來設計基于離散對數(shù)難題的公鑰加密算法，即ElGamal加密算法。教師同時對ElGamal加密算法進行系統(tǒng)的解釋和說明，便于學生更好地理解與掌握。

在這一環(huán)節(jié)，教師再次回顧公鑰密碼算法的應用場景：假設Bob要給Alice發(fā)送消息M，Bob需要先獲得Alice的公鑰，利用該公鑰對消息M進行加密，并將密文C發(fā)送給Alice；而后Alice利用自己的私鑰對密文C進行解密從而得到消息M。

緊接著，教師引導學生深入思考，在DH密鑰交換協(xié)議中，Alice在每次通信前都要產(chǎn)生一個隨機數(shù)a作為自己的私鑰，將Sa=ramodp作為公鑰；同理，Bob也要做類似的操作。但在公鑰加密場合，能否讓Alice每次都采用同樣的公私鑰對從而減少密鑰管理負擔呢？

教師拋出這個問題后，可先讓學生進行簡單的討論。然后參考圖2，與學生一起對DH密鑰交換協(xié)議做進一步的改造與分析：

(1)假設Alice的私鑰為a，公鑰為Sa=ramodp，將{a,Sa}作為Alice的永久公私鑰對，且Bob預先已知Alice的公鑰信息Sa。因此，在圖2中，第一次Alice向Bob傳輸信息時可以用虛線標記，表示Bob已經(jīng)預先知道了Alice的公鑰信息，不需要Alice再次發(fā)送；

圖2 ElGamal加密算法流程

(2)Bob對應的公私鑰信息是否也可以保持不變呢？經(jīng)分析不可行，否則Alice和Bob每次聯(lián)合產(chǎn)生的共享密鑰K就會保持不變，這是“一次一密”所不允許的。因此，Bob需要每次產(chǎn)生一個隨機數(shù)k，計算Sk=rkmodp，將{k,Sk}作為Bob的臨時公私鑰對，同時，Bob將臨時公鑰Sk傳送給Alice；

(3)Alice和Bob都可以獨立計算出共享密鑰K，Bob計算法方式為K=(sa)kmodp=rakmodp，Alice計算方式為K=(sk)amodp=rkamodp；

(4)Bob依靠共享密鑰K，基于“一次一密”方案對明文M加密得到密文：K* M mod p；而Alice依靠自己獨立計算得出的共享密鑰K就可以完成對上述密文的解密。

以上4個步驟就是基于離散對數(shù)問題的ElGamal公鑰加密算法分解流程，其中，前3步就是一個完整的DH密鑰交換協(xié)議過程，最后一步才是真正的加密過程。根據(jù)圖2中的虛實交互箭頭所示，教師進一步提示學生：Bob可以將步驟(2)(4)合并作為最終發(fā)給Alice的密文，從而給出如下ElGamal公鑰加密算法的標準定義：

密鑰建立過程：Alice與Bob共享一組安全參數(shù){p,r}，p為大素數(shù)，r為p的本原根；

Alice的私鑰為a，公鑰為Sa=ramodp。

加密過程：Bob每次隨機選取自己的臨時私鑰k，計算臨時公鑰sK=rkmodp作為密文的第一部分c1；然后查看Alice的公鑰sa，計算共享密鑰K=(sa)kmodp=rakmodp，進一步計算密文的第二部分c2=K*Mmodp。因此，密文C=(c1,c2)=(rkmodp, (sa)k*Mmodp)。

解密過程： Alice利用自己的私鑰a和密文的第一部分c1，首先計算還原共享密鑰K=(sk)amodp=rkamodp，然后利用密文的第二部分c2恢復出原始消息M=c2*K-1 modp。

根據(jù)上述流程，教師做最后總結(jié)：本次課程，我們引入臨時公私鑰對和永久公私鑰對的概念，基于“一次一密”思想，和大家也一起經(jīng)歷了從DH密鑰交換協(xié)議到ElGamal加密算法的改造過程，我們發(fā)現(xiàn)：ElGamal加密算法與DH密鑰交換協(xié)議是等價的，它以預先公開sa的方式減少了一次數(shù)據(jù)交換；但該算法的缺點是“信息擴展”，即密文長度是所對應明文長度的兩倍。這里，密文的第一部分是臨時公鑰，用于交互信息以聯(lián)合共建共享密鑰；第二部分才是真正的一次一密加密過程。

2 教學思考

以上教學設計，經(jīng)我校2016年“密碼學與網(wǎng)絡安全”課程本科課堂教學實踐，取得了良好的效果。很多學生反映對ElGamal公鑰密碼加密算法的原理有了非常清晰的理解和深刻的認識，為后續(xù)橢圓曲線加密算法的學習打下了扎實的基礎。課程內(nèi)容的講解更加系統(tǒng)，前后教學知識點也更加連貫，主線突出，達到了預期目的。

通過該教學案例的設計，我們發(fā)現(xiàn)充分挖掘課程知識點之間的內(nèi)在聯(lián)系，以問題導向為牽引，引導學生對所學知識進行深入思考和主動分析，既能充分調(diào)動他們學習“密碼學與網(wǎng)絡安全”課程的興趣，又能培養(yǎng)他們主動式和研究式的學習能力，最終達到更好的教學質(zhì)量與效果，也更好地促進學生的全面發(fā)展。在后續(xù)的課程教學當中，我們可以更多嘗試設計以“問題導向”為牽引的教學案例。

3 結(jié)語

“密碼學與網(wǎng)絡安全”課程固有的特點和難點使不少學生對其存在畏懼心理。如果學生對課程基礎知識重視不夠、掌握不扎實，就會導致后續(xù)缺乏熟練運用已有知識解決專業(yè)問題的能力，影響其從事深層次專業(yè)研究的創(chuàng)新能力。我們針對ElGamal密碼算法的教學內(nèi)容進行了教學案例設計，將DH密鑰交換協(xié)議有機融合進來，通過問題導向的方式，激發(fā)學生的學習興趣，引導他們逐步培養(yǎng)研究式和自主式學習的能力。(李瑞林等文)

[1] William Stallings 著．唐明等譯．密碼編碼學與網(wǎng)絡安全-原理與實踐(第六版)，北京：電子工業(yè)出版社，2015.

[2] Diffie W. and Hellman M.E. New directions in cryptography. IEEE Trans. on Information Theory, 22 (6), 644-654, 1976.

[3] ElGamal T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. on Information Theory, 31(4), 469-472, 1985.