基于C語言的“密碼學(xué)實(shí)驗(yàn)”課程教學(xué)設(shè)計(jì)

王會(huì)勇，唐士杰

（1. 桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林；2. 桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林）

一 引言

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

二 “密碼學(xué)”課程教學(xué)的主要困難

從“密碼學(xué)”課程的內(nèi)容和教學(xué)現(xiàn)狀來看，本課程的教學(xué)主要存在以下三方面困難。

（一） 密碼學(xué)的學(xué)習(xí)門檻較高，且內(nèi)容十分豐富，學(xué)習(xí)難度較大

首先，現(xiàn)代密碼學(xué)的內(nèi)容主要包含“密碼學(xué)”的數(shù)學(xué)與計(jì)算機(jī)理論基礎(chǔ)、“密碼學(xué)”的理論主體和“密碼學(xué)”應(yīng)用三個(gè)方面[1]。其中，學(xué)習(xí)“密碼學(xué)”所需的數(shù)學(xué)基礎(chǔ)主要包含抽象代數(shù)、概率論和數(shù)論基礎(chǔ)，但學(xué)習(xí)這些內(nèi)容首先要求學(xué)生具備一些數(shù)學(xué)基礎(chǔ)課程，如線性代數(shù)、離散數(shù)學(xué)、組合數(shù)學(xué)等，以及一些計(jì)算機(jī)基礎(chǔ)課程，主要包括算法分析、數(shù)據(jù)結(jié)構(gòu)、編程工具等。除此之外，密碼學(xué)的學(xué)習(xí)中還有可能需要信息論和語言學(xué)等方面的知識(shí)。

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

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

（二） 學(xué)生的數(shù)學(xué)基礎(chǔ)與計(jì)算機(jī)基礎(chǔ)薄弱，編程能力普遍不足

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

（三） 缺乏實(shí)驗(yàn)設(shè)備和工具

在設(shè)計(jì)密碼學(xué)實(shí)驗(yàn)的內(nèi)容時(shí)，通常有兩種做法[2]。一種是要求學(xué)生用某種高級(jí)語言編程實(shí)現(xiàn)某些密碼算法程序，另一種是要求學(xué)生利用實(shí)現(xiàn)了特定密碼算法的軟件工具對(duì)某些密碼算法進(jìn)行驗(yàn)證。

對(duì)于第一種做法，由于很多密碼算法原理比較復(fù)雜，編程實(shí)現(xiàn)的工作量很大。解決這個(gè)問題的一個(gè)理想方法是由教師提供程序的主體架構(gòu)，只要求學(xué)生添加少量的關(guān)鍵代碼。但在目前，在大多數(shù)在線學(xué)習(xí)平臺(tái)還很難看到此類程序資源，而讓教師自己編寫所有程序框架也存在很大困難。

第二種做法只要求學(xué)生對(duì)某些密碼算法做驗(yàn)證，且目前已經(jīng)有了一些工具，如西普信息安全實(shí)驗(yàn)平臺(tái)、四川農(nóng)業(yè)大學(xué)密碼學(xué)實(shí)驗(yàn)課程學(xué)習(xí)平臺(tái)[3]、CrypTool[4]等。但此類實(shí)驗(yàn)一方面可能需要付費(fèi)購買實(shí)驗(yàn)平臺(tái)，另一方面對(duì)學(xué)生的要求通常很低，即學(xué)生只需按部就班地操作，基本不需要理解相關(guān)密碼算法的細(xì)節(jié)就可以完成任務(wù)，因此對(duì)學(xué)生理解算法幫助較小。

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

表1 密碼學(xué)實(shí)驗(yàn)課程分層教學(xué)內(nèi)容

三 我們的設(shè)計(jì)

（一） 實(shí)驗(yàn)內(nèi)容

在綜合考慮學(xué)生實(shí)際情況和現(xiàn)有軟硬件條件之后，我們將本校數(shù)學(xué)與計(jì)算科學(xué)學(xué)院信息與計(jì)算科學(xué)專業(yè)16課時(shí)的“密碼學(xué)實(shí)驗(yàn)”課程的教學(xué)內(nèi)容分為兩類，分別為編程實(shí)現(xiàn)類內(nèi)容和驗(yàn)證類內(nèi)容。

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

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

編程驗(yàn)證類學(xué)習(xí)內(nèi)容主要包含對(duì)稱密碼DES算法、哈希函數(shù)和數(shù)字簽名，要求學(xué)生在指定的學(xué)習(xí)平臺(tái)（目前主要利用四川農(nóng)業(yè)大學(xué)密碼學(xué)實(shí)驗(yàn)課程學(xué)習(xí)平臺(tái)）完成對(duì)指定密碼算法的驗(yàn)證，并提交驗(yàn)證報(bào)告。此部分可要求學(xué)生在上課時(shí)間完成（大約需要2~3學(xué)時(shí)），也可要求學(xué)生利用課后時(shí)間完成。上述內(nèi)容雖然也是密碼學(xué)的基礎(chǔ)核心內(nèi)容，但編程實(shí)現(xiàn)的難度太大，故只要求學(xué)生完成驗(yàn)證任務(wù)。

（二） 實(shí)驗(yàn)設(shè)計(jì)

（1）古典密碼學(xué)實(shí)驗(yàn)?；灸繕?biāo)是通過編程實(shí)現(xiàn)經(jīng)典的代替密碼和置換密碼，為現(xiàn)代分組密碼實(shí)驗(yàn)奠定基礎(chǔ)?？紤]到實(shí)現(xiàn)難度和課時(shí)限制，我們選擇了移位密碼、仿射密碼和Vigenère密碼作為主要實(shí)驗(yàn)內(nèi)容。

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

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

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

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

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

（2）公鑰密碼實(shí)驗(yàn)。實(shí)驗(yàn)?zāi)繕?biāo)是編寫RSA算法和ElGamal算法的簡單加解密程序。

由于此實(shí)驗(yàn)需要用到乘法逆元，首先需要學(xué)生實(shí)現(xiàn)乘法逆元的求解過程。這個(gè)內(nèi)容需要實(shí)現(xiàn)4個(gè)子算法，分別是素?cái)?shù)判定算法（此算法在以前的C語言程序設(shè)計(jì)課程中學(xué)習(xí)過）、最大公約數(shù)算法（使用擴(kuò)展歐幾里得算法）、求乘法模逆元算法和整數(shù)冪模算法。

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

表3 字符與整數(shù)的轉(zhuǎn)換算法表

在ElGamal算法的實(shí)現(xiàn)過程中，需要介紹素?cái)?shù)的原根和循環(huán)群的生成元的尋找方法。

（3）實(shí)用密碼算法。本次實(shí)驗(yàn)重點(diǎn)是實(shí)現(xiàn)一些常用的密碼學(xué)算法。實(shí)驗(yàn)內(nèi)容主要包括偽隨機(jī)數(shù)產(chǎn)生和中國剩余定理。

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

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

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

②計(jì)算M=m1·m2·L·mk。

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

⑦輸出最終結(jié)果。

（4）Diffie-Hellman密鑰交換。本次實(shí)驗(yàn)的主要目標(biāo)是理解Diffie-Hellman算法的實(shí)現(xiàn)原理，用C語言編程實(shí)現(xiàn)Diffie-Hellman密鑰協(xié)商過程。

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

首先介紹該算法的基本實(shí)現(xiàn)原理與步驟。其次，要求學(xué)生采用一些較小的參數(shù)模擬實(shí)現(xiàn)該算法，如：

對(duì)部分心有余力的學(xué)生，可要求其在完成基本算法的實(shí)現(xiàn)后，額外考慮中間人攻擊的模擬實(shí)現(xiàn)過程。

（三） 實(shí)驗(yàn)過程與結(jié)果

對(duì)于編程實(shí)現(xiàn)類教學(xué)內(nèi)容，我們要求學(xué)生利用C語言或其他高級(jí)語言編程實(shí)現(xiàn)，但推薦使用C語言。這是因?yàn)橐环矫鎸W(xué)生已經(jīng)在前期統(tǒng)一學(xué)習(xí)了“C語言程序設(shè)計(jì)”課程，使用C語言能夠幫助學(xué)生進(jìn)一步掌握該語言。另一方面，在對(duì)某些較復(fù)雜的算法任務(wù)做簡化之后，使用C語言實(shí)現(xiàn)的難度并不會(huì)很高，是可以接受的。

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

圖2 對(duì)中國剩余的定理的實(shí)現(xiàn)代碼與結(jié)果

四 結(jié)語

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

為進(jìn)一步提升學(xué)生對(duì)某些較復(fù)雜算法的驗(yàn)證效果，我們正在設(shè)計(jì)基于一些在線編程平臺(tái)（如EduCoder[10]）的測(cè)試框架，使得學(xué)生能夠通過編輯部分關(guān)鍵代碼完成整個(gè)算法。