基于C語言的“密碼學實驗”課程教學設計

王會勇，唐士杰

（1. 桂林電子科技大學 數學與計算科學學院，廣西 桂林；2. 桂林電子科技大學 電子工程與自動化學院，廣西 桂林）

一 引言

隨著現代信息技術的發展，信息安全越來越受到重視，使得“密碼學”成為很多工科高校信息安全專業的基礎課程。但該課程的教學卻一直存在一些困難，存在著“高不成低不就”的現象，即一方面，本課程的學習門檻較高；另一方面，學完本課程后，卻常有很難用上所學知識的感覺。一個明顯表現是信息安全專業的畢業生，無論是本科生還是研究生，都很難在畢業后直接就職于對口職業。究其原因，除課程本身內容豐富、應用要求高等原因之外，實踐教學的設計困難、教學效果難以保障也是一個重要原因。

二 “密碼學”課程教學的主要困難

從“密碼學”課程的內容和教學現狀來看，本課程的教學主要存在以下三方面困難。

（一） 密碼學的學習門檻較高，且內容十分豐富，學習難度較大

首先，現代密碼學的內容主要包含“密碼學”的數學與計算機理論基礎、“密碼學”的理論主體和“密碼學”應用三個方面[1]。其中，學習“密碼學”所需的數學基礎主要包含抽象代數、概率論和數論基礎，但學習這些內容首先要求學生具備一些數學基礎課程，如線性代數、離散數學、組合數學等，以及一些計算機基礎課程，主要包括算法分析、數據結構、編程工具等。除此之外，密碼學的學習中還有可能需要信息論和語言學等方面的知識。

其次，現代密碼學的主要內容是對稱密碼與非對稱密碼，但這兩部分內容都存在一些非常復雜、學習難度很高的部分，如對稱密碼中的DES、AES、SMS4加解密算法、一些HASH算法和非對稱密碼中的橢圓曲線密碼、RSA密碼等。即使對具備良好基礎的初學者來說，這些內容都是有較大難度的。

另外，為取得良好的教學效果，本課程一般設置理論課和實驗課兩個部分。理論課程主要學習相關的數學基礎、算法基礎和密碼學基礎知識，實驗課程的主要目標則是加深學生對理論知識的掌握和理解，并在理論知識與實用技能之間架起橋梁。因此，實驗教學的設計在很大程度上決定了本課程的實際教學效果。但“密碼學”實驗課程的內容也非常豐富，既可以包含基礎性內容，如古典密碼、對稱密碼和非對稱密碼技術，也可以包含擴展應用型內容，如網絡基礎、漏洞掃描、密碼破解、數據庫入侵、Web 攻擊、緩沖區溢出等。其中有些內容復雜度很高，用基礎性工具編程實現的難度很大。

（二） 學生的數學基礎與計算機基礎薄弱，編程能力普遍不足

如前所述，學習“密碼學”課程需要具備較多的數學與計算機基礎知識。因此，國內大多數高等院校將本課程設置到本科三年級或四年級開設。但從實際情況來看，多數高校在本科生的一年級和二年級并沒有開設“密碼學”所需的群論、抽象代數、數論等基礎課程，且即使開設了此類課程，很多學生也無法達到課程的考核要求。這就使得“密碼學”課程的教學過程不得不預留大量時間來補充相關數學與計算機基礎。另一方面，雖然國內大多數高校都為低年級學生開設了C語言等編程類課程，但學生的實際學習效果也很難達到能夠編程實現某些較為復雜的密碼學算法（如DES、AES等）的程度。

（三） 缺乏實驗設備和工具

在設計密碼學實驗的內容時，通常有兩種做法[2]。一種是要求學生用某種高級語言編程實現某些密碼算法程序，另一種是要求學生利用實現了特定密碼算法的軟件工具對某些密碼算法進行驗證。

對于第一種做法，由于很多密碼算法原理比較復雜，編程實現的工作量很大。解決這個問題的一個理想方法是由教師提供程序的主體架構，只要求學生添加少量的關鍵代碼。但在目前，在大多數在線學習平臺還很難看到此類程序資源，而讓教師自己編寫所有程序框架也存在很大困難。

第二種做法只要求學生對某些密碼算法做驗證，且目前已經有了一些工具，如西普信息安全實驗平臺、四川農業大學密碼學實驗課程學習平臺[3]、CrypTool[4]等。但此類實驗一方面可能需要付費購買實驗平臺，另一方面對學生的要求通常很低，即學生只需按部就班地操作，基本不需要理解相關密碼算法的細節就可以完成任務，因此對學生理解算法幫助較小。

為解決上述困難，有的教師設計了分層教學模式，收到了良好的教學效果。在陸向艷等人[5]的教學設計中，第一層是展示層，即在理論課或實驗課開始由教師向學生展示密碼算法的原理與基本實現過程。第二層是驗證層，包含兩種模式：無需編寫代碼模式和需要編寫代碼模式。無需編寫代碼的模式主要針對某些復雜的教學內容，要求學生利用某種已有工具驗證密碼算法，而需要編寫代碼的模式則針對某些相對容易編碼的內容，要求學生使用某種高級語言編程實現；第三層是應用層，教學目的是訓練學生對密碼算法綜合應用和創新應用的能力，主要采用三種模式開展：課程設計、創新項目和學科競賽。該教學模式的主要教學內容如表1所示。

表1 密碼學實驗課程分層教學內容

三 我們的設計

（一） 實驗內容

在綜合考慮學生實際情況和現有軟硬件條件之后，我們將本校數學與計算科學學院信息與計算科學專業16課時的“密碼學實驗”課程的教學內容分為兩類，分別為編程實現類內容和驗證類內容。

編程實現類學習內容是教學重點，主要包含四個部分，分別為古典密碼（移位密碼、仿射密碼[6]和 Vigenère密碼）[7]、公鑰密碼（RSA密碼和ElGamal密碼）[8]、實用密碼算法（主要包含偽隨機數產生和中國剩余定理）、Diffie-Hellman密鑰交換算法[9]。每個部分大約需要3~4學時。

選擇上述內容作為編程實現內容的首要原因是上述內容屬于密碼學中的核心內容，其次是上述內容都較易用高級編程語言實現。另外，上述算法中的一些核心算法是可以反復使用的，如在RSA方案、ElGamal方案和中國剩余定理算法中，都需要用到求乘法模逆元的操作等。反復的使用能夠進一步加深學生對這些關鍵算法的理解和掌握程度。

編程驗證類學習內容主要包含對稱密碼DES算法、哈希函數和數字簽名，要求學生在指定的學習平臺（目前主要利用四川農業大學密碼學實驗課程學習平臺）完成對指定密碼算法的驗證，并提交驗證報告。此部分可要求學生在上課時間完成（大約需要2~3學時），也可要求學生利用課后時間完成。上述內容雖然也是密碼學的基礎核心內容，但編程實現的難度太大，故只要求學生完成驗證任務。

（二） 實驗設計

（1）古典密碼學實驗?；灸繕耸峭ㄟ^編程實現經典的代替密碼和置換密碼，為現代分組密碼實驗奠定基礎?？紤]到實現難度和課時限制，我們選擇了移位密碼、仿射密碼和Vigenère密碼作為主要實驗內容。

移位密碼的加密過程是將明文中的每個字母用其后面的第k個字母替代。由于其加解密過程非常直觀、簡單，因此適于作為學生實驗的第一個案例。

仿射密碼需引入兩個參數α和β，且在解密時需求解有限域Zn上的乘法逆元α-1∈Zn。這可借助擴展歐幾里得算法實現。但由于求乘法逆元的操作涉及到較為復雜的代數知識，故可將此內容放在下一次實驗課。在本次實驗中，由于n通常取為字母表中字母的個數，即n=26，且要求α與n互素，故可直接將Z26上所有與26互素的元素的乘法逆元列表給出，方面學生直接使用（表2）。

表2 Z26上與26互素的元素的乘法逆元表

Vigenère密碼是一種多表代換密碼，其本質是周期移位密碼。Vigenère密碼的密鑰為一含有d個字母的有限字母序列。當d=1時，Vigenère密碼就是移位密碼。

由于完整實現該算法的難度較大，我們要求學生使用固定密鑰“cat”，并取n=26，對明文“vigenere cipher”進行加密，并計算密文“xizgnxtevkpagr”，然后實現解密過程。

（2）公鑰密碼實驗。實驗目標是編寫RSA算法和ElGamal算法的簡單加解密程序。

由于此實驗需要用到乘法逆元，首先需要學生實現乘法逆元的求解過程。這個內容需要實現4個子算法，分別是素數判定算法（此算法在以前的C語言程序設計課程中學習過）、最大公約數算法（使用擴展歐幾里得算法）、求乘法模逆元算法和整數冪模算法。

在實驗中，為減小實現難度，我們對多項設置做了簡化。首先，只要求學生使用較小的參數（如兩個素數分別取為3和5，并令n=3×5）。其次，為減小難度，要求學生采用簡單映射實現字符到整數的轉換（表3）。另外，為簡化實現過程，我們沒有考慮實用RSA算法所需的填充、分割、通信等算法，只考慮了加解密過程。

表3 字符與整數的轉換算法表

在ElGamal算法的實現過程中，需要介紹素數的原根和循環群的生成元的尋找方法。

（3）實用密碼算法。本次實驗重點是實現一些常用的密碼學算法。實驗內容主要包括偽隨機數產生和中國剩余定理。

偽隨機數的產生算法主要要求學生使用C語言中的srand()函數實現，并使用time函數獲得系統時間作為srand()函數的種子。中國剩余定理的實現過程則要求學生求解如下一次同余方程組，其中m1，m2，L，mk兩兩互素。

上述方程組的求解步驟如下：

①判斷m1，m2，L，mk是否兩兩互素。若不滿足，輸出“不能直接利用中國剩余定理”。

②計算M=m1·m2·L·mk。

⑥判斷上述結果是否大于M，若是，將其減去M的若干倍。

⑦輸出最終結果。

（4）Diffie-Hellman密鑰交換。本次實驗的主要目標是理解Diffie-Hellman算法的實現原理，用C語言編程實現Diffie-Hellman密鑰協商過程。

該算法的實現過程需要用到歐拉函數計算算法、排序算法（如冒泡排序）、整數冪模算法、求本原根算法、素性判定算法和隨機數生成算法。因此，本算法綜合性較高，實現難度較大。這也是我們將本算法作為最后一個實驗的原因。

首先介紹該算法的基本實現原理與步驟。其次，要求學生采用一些較小的參數模擬實現該算法，如：

對部分心有余力的學生，可要求其在完成基本算法的實現后，額外考慮中間人攻擊的模擬實現過程。

（三） 實驗過程與結果

對于編程實現類教學內容，我們要求學生利用C語言或其他高級語言編程實現，但推薦使用C語言。這是因為一方面學生已經在前期統一學習了“C語言程序設計”課程，使用C語言能夠幫助學生進一步掌握該語言。另一方面，在對某些較復雜的算法任務做簡化之后，使用C語言實現的難度并不會很高，是可以接受的。

例如，在所有實驗中，我們不要求學生設計可視化輸入輸出界面；在某些密碼算法中，只要求學生使用較小參數完成設計。如在RSA算法和ElGamal算法的實現中，只要求學生使用較小的素數實現算法即可。這種做法極大地降低了使用C語言編程的難度，又可以讓學生真正理解所學算法的實現方法。從實驗過程來看，幾乎所有學生都采用了C語言作為編程工具，并成功完成了編程任務。圖2是其中一個學生對“中國剩余定理”的實現代碼與運行結果截圖。

圖2 對中國剩余的定理的實現代碼與結果

四 結語

“密碼學實驗”課程的設計一直是一個比較困難的問題。我們結合本校實際情況與相關文獻的經驗，設計了一個可行的基于C語言的授課方案。按照我們的方案，學生能夠在有限的課時內編程實現課程中的關鍵密碼算法，從而深刻理解并掌握這些內容。對于一些較為復雜的程序，學生也能夠通過既有工具驗證算法的實際效果，從而在一定程度上掌握這些算法。

為進一步提升學生對某些較復雜算法的驗證效果，我們正在設計基于一些在線編程平臺（如EduCoder[10]）的測試框架，使得學生能夠通過編輯部分關鍵代碼完成整個算法。