基于算法的信息安全數(shù)學(xué)基礎(chǔ)教學(xué)模式研究

楊文忠　劉淑嫻　余廣新　李偉

摘 要：針對信息安全數(shù)學(xué)基礎(chǔ)理論性太強，教材沒有很好融合算法設(shè)計與分析思想和信息安全數(shù)學(xué)基礎(chǔ)的概念、定理和結(jié)論，提出融合算法、編程實踐和信息安全數(shù)學(xué)基礎(chǔ)關(guān)鍵概念、定理和結(jié)論的教學(xué)模式觀點，經(jīng)過幾年實際檢驗，表明這種教學(xué)模式既高了學(xué)生的學(xué)習(xí)積極性有提高了教學(xué)效果。

關(guān)鍵詞：信息安全數(shù)學(xué)基礎(chǔ)算法編程教學(xué)研究

信息安全數(shù)學(xué)基礎(chǔ)是信息安全專業(yè)的一門專業(yè)基礎(chǔ)課程，有很強的理論性和應(yīng)用空間，是信息安全后續(xù)專業(yè)課程現(xiàn)代密碼學(xué)、網(wǎng)絡(luò)安全等課程的基礎(chǔ)。這門課程掌握不好直接影響現(xiàn)代密碼學(xué)的學(xué)習(xí)，而現(xiàn)代密碼學(xué)又直接影響網(wǎng)絡(luò)安全和網(wǎng)絡(luò)安全編程的學(xué)習(xí)，有著多米諾骨牌式的效應(yīng)。信息安全數(shù)學(xué)基礎(chǔ)主要強調(diào)數(shù)論和近世代數(shù)，較為抽象，數(shù)學(xué)專業(yè)的學(xué)生學(xué)習(xí)數(shù)論和近世代數(shù)有時也會有些吃力，通過對新疆大學(xué)2011級到2014級信息安全專業(yè)的本科學(xué)生的上課情況看，有些學(xué)生在學(xué)習(xí)信息安全數(shù)學(xué)基礎(chǔ)課程還是有些吃力的，這些學(xué)生本來數(shù)學(xué)基礎(chǔ)就有點差，若再提不起興趣，就會直接導(dǎo)致后面許多課程無法同步跟上。通過對2011級到2014級學(xué)生觀察發(fā)現(xiàn)大部分學(xué)生其實喜歡動手實踐，這可提高學(xué)生的參與度和成就感。信息安全數(shù)學(xué)基礎(chǔ)雖然理論性很強，但也是有規(guī)律可循，需要讓學(xué)生掌握的許多理論本質(zhì)是讓學(xué)生掌握基于這些理論背后的算法，如講解整數(shù)整除基本性質(zhì)就是為了讓學(xué)生掌握擴展歐幾里得算法，講解同余性質(zhì)及歐拉定理等也是為了讓學(xué)生掌握模重復(fù)平方計算算法，講解一次同余式和中國剩余定理其實也是在講解其算法原理，諸如此類還很多。由于大部分學(xué)生喜歡編程，將枯燥的信息安全數(shù)學(xué)基礎(chǔ)理論模型化并提出算法實現(xiàn)需求，然后讓學(xué)生去動手實踐，學(xué)生就不會感到數(shù)學(xué)理論和公式的枯燥，這樣大部分學(xué)生就很感興趣，也提高了學(xué)生的學(xué)習(xí)的主動性和成就感。在2012級到2014及部分學(xué)生中經(jīng)過試點后，學(xué)生反映還是比較好的，有些學(xué)生的創(chuàng)造力還是很突出的，改革信息安全數(shù)學(xué)基礎(chǔ)課程，刪除較為枯燥的無用的某些數(shù)學(xué)理論，精講較為實用的理論，講透實用理論的目標和應(yīng)用場合，將算法融入的信息安全數(shù)學(xué)基礎(chǔ)中可使信息安全專業(yè)學(xué)生將先前學(xué)習(xí)的程序設(shè)計及數(shù)據(jù)結(jié)構(gòu)與信息安全數(shù)學(xué)基礎(chǔ)銜接在一起，支撐起后續(xù)課程的學(xué)習(xí)，又鍛煉的學(xué)生的算法設(shè)計和編程能力。因而很有必要改革傳統(tǒng)信息安全數(shù)學(xué)基礎(chǔ)課程的上課模式及授課內(nèi)容，切實讓學(xué)生能夠?qū)W得輕松也能讓學(xué)生學(xué)有所成。[1]

一、教學(xué)現(xiàn)狀

國外許多大學(xué)如麻省理工、斯坦福大學(xué)等都開設(shè)有密碼學(xué)課程，他們大都將密碼學(xué)課程分為兩個學(xué)期，前一個學(xué)期主要講解密碼學(xué)基礎(chǔ)，即信息安全數(shù)學(xué)基礎(chǔ)，他們留有大量有關(guān)信息安全數(shù)學(xué)基礎(chǔ)的實踐項目，以幫助學(xué)生更好的掌握有關(guān)理論及如何應(yīng)用，開闊學(xué)生的視野。國內(nèi)上海交通大學(xué)將信息安全數(shù)學(xué)基礎(chǔ)也分為兩個學(xué)期上，但主要是強調(diào)其數(shù)學(xué)基礎(chǔ)和數(shù)學(xué)理論，山東大學(xué)有著數(shù)學(xué)上的優(yōu)勢，他們的信息安全數(shù)學(xué)基礎(chǔ)就是從數(shù)學(xué)角度來傳授的，武漢大學(xué)和華中科技大學(xué)也沒有將算法有關(guān)思想融入到信息安全數(shù)學(xué)基礎(chǔ)中。緊跟國家和自治區(qū)經(jīng)濟和政治的需要，2006年新疆大學(xué)信息科學(xué)與工程學(xué)院開設(shè)信息安全專業(yè)。2012年信息安全專業(yè)被批準為自治區(qū)緊缺專業(yè)，2017年獲批為新疆維吾爾自治區(qū)戰(zhàn)略新興專業(yè)。雖然開設(shè)了信息安全專業(yè)，但與內(nèi)地高校的生源質(zhì)量還是有些差距，鑒于信息安全專業(yè)學(xué)生的數(shù)學(xué)功底，在信息安全專業(yè)學(xué)生中主要傳授信息安全數(shù)學(xué)基礎(chǔ)背后的算法，而不是大力強化理論，會使以后更多信息安全專業(yè)學(xué)生受益。閆璽璽[1]提到教師是課堂教學(xué)的策劃者，要上好信息安全數(shù)學(xué)基礎(chǔ)這門課，教師必須針對該課程的特點和內(nèi)容，制訂好教學(xué)方案，激發(fā)學(xué)生的興趣，提高學(xué)生的積極性，為密碼學(xué)技術(shù)的學(xué)習(xí)打好基礎(chǔ)。但沒有提到融合算法和信息安全數(shù)學(xué)基礎(chǔ)基本定理和結(jié)論。李瑞琪[2]提出了信息安全數(shù)學(xué)基礎(chǔ)教學(xué)應(yīng)該“講一練二考三”，即精講、多練、廣考來提高學(xué)生學(xué)習(xí)積極性，仍然沒有解決學(xué)生算法、數(shù)據(jù)結(jié)構(gòu)、編程和信息安全數(shù)學(xué)基礎(chǔ)的知識綜合應(yīng)用問題。秦艷琳[3]提出要精心設(shè)計課堂互動，提高學(xué)生學(xué)習(xí)興趣和注重介紹數(shù)學(xué)基礎(chǔ)知識在密碼學(xué)和信息安全領(lǐng)域中的應(yīng)用實例，突出了信息安全數(shù)學(xué)基礎(chǔ)在密碼學(xué)中的應(yīng)用實例，但沒有將學(xué)生可能已經(jīng)具備的算法、數(shù)據(jù)結(jié)構(gòu)、編程能力綜合利用進一步引導(dǎo)學(xué)生綜合應(yīng)用所學(xué)知識能力和提高學(xué)生自主學(xué)習(xí)信息安全數(shù)學(xué)基礎(chǔ)中枯燥的定理和結(jié)論能力。本文主要探索了信息安全數(shù)學(xué)基礎(chǔ)中有關(guān)定理和結(jié)論如何與算法結(jié)合在一起，基于這些定理如何設(shè)計算法及這些定理可以現(xiàn)在算法什么地方，為進一步探索多課程交叉融合的信息安全數(shù)學(xué)基礎(chǔ)教學(xué)模式提供了思路。[2]

二、融合算法的教學(xué)模式

從本科專業(yè)培養(yǎng)方案上來說應(yīng)該在信息安全數(shù)學(xué)基礎(chǔ)之前開設(shè)程序設(shè)計語言課程如C語言、Python語言等、線性代數(shù)、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計與分析等課程。學(xué)生有一定的編程基礎(chǔ)后，再學(xué)習(xí)信息安全數(shù)學(xué)基礎(chǔ)理論時，就可以使用有關(guān)數(shù)據(jù)結(jié)構(gòu)和編程語言實現(xiàn)擴展歐幾里得、模重復(fù)平方、原根等的具體計算，當編寫出相應(yīng)的程序后，學(xué)生比較有成就感和獲得感，又鍛煉了學(xué)生編程能力，使學(xué)生體會到信息安全數(shù)學(xué)基礎(chǔ)不僅可以從數(shù)學(xué)角度去理解和計算也可以從計算機科學(xué)的計算角度去理解和計算。其次應(yīng)該設(shè)置信息安全數(shù)學(xué)基礎(chǔ)課程實踐課程。可以設(shè)置廣義歐幾里得算法、模重復(fù)平方算法、一次同余式求解算法、中國剩余定理算法、勒讓德符號計算算法、原根求解算法、Miller-Rabin算法和有限域構(gòu)造算法等，每個算法實踐大約4學(xué)時，涵蓋了信息安全數(shù)學(xué)基礎(chǔ)主要概念、定理和結(jié)論[4]等。若無法在信息安全數(shù)學(xué)基礎(chǔ)課時內(nèi)安排實踐課程，可以安排為實踐類課程作業(yè)。學(xué)生除了需要進行實踐外，應(yīng)該理解廣義歐幾里得算法和模重復(fù)平方算法等算法設(shè)計思想和計算機復(fù)雜度，理解為什么可以將廣義歐幾里得算法和模重復(fù)平方算法等算法應(yīng)該密碼理論中，從算法角度理解這些迭代算法的循環(huán)不變式[5]其實就是信息安全數(shù)學(xué)基礎(chǔ)中有關(guān)定理的體現(xiàn)。[3]

三、具體實例

1.擴展歐幾里得算法

歐幾里得除法是a，b是兩個整數(shù)，其中b>0，則對任意的整數(shù)c，存在唯一的整數(shù)q，r使得a=q·b+r 。擴展或廣義歐幾里得除法主要求兩個整數(shù)a，b的最大公約數(shù)的。即，gcd（a，b）=（a，b）= s·a+ t·b，其中最大公約數(shù)（a，b）、整數(shù)s和t可以使用下面的算法計算得到。該算法的輸入是整數(shù)a，b，輸出是整數(shù)sn， tn和rn，滿足sn·a+ tn·b= s·a+ t·b=rn=gcd（a，b）=（a，b），該算法的循環(huán)不變式是si·a+ ti·b=ri（i=1，2，…n），此循環(huán)不變式也是信息安全數(shù)學(xué)基礎(chǔ)中廣義歐幾里得除法的一個定理，因而是正確的。其計算過程如下表所示。計算時間復(fù)雜度是O（lg n），其中n是整數(shù)a，b中絕對值較大者。該算法主要用于求模n乘法逆元，在密碼學(xué)RSA算法等涉及求逆元的算法都會使用到該算法，是必須要掌握的一個算法。該算法計算過程代碼如下。[4]

3.模m原根計算算法

根據(jù)信息安全數(shù)學(xué)基礎(chǔ)中初等數(shù)論結(jié)論模m有原根的重要條件是m=2、4、pa、2pa，其中p是素數(shù)。計算原根的關(guān)鍵是找到素數(shù)p其中一個原根g，素數(shù)p的其他原根可以通過計算gd的得到，這里的d是一個與p-1互素的正整數(shù)，即（d，p-1）=1。只要找到素數(shù)p的一個原根，就可計算pa、2pa的原根，從而可以計算從有原根的任意模數(shù)m的原根。奇素數(shù)p的原根計算算法是首先計算p-1的不同素因子q1，…，qs，g從小到大遍歷這s個素因子，若，則此素因子g就是素數(shù)p的一個原根。該計算機算法計算工作量主要是p-1的素因子分解，當p是非常大的素數(shù)時，該計算機問題NP問題，計算機工作量是比較大的，但對一般意義的奇素數(shù)p，這個計算算法還是可以接受的。[5]

本文探討了融合算法設(shè)計與分析思想到信息安全數(shù)學(xué)基礎(chǔ)教學(xué)中，一方面可以提高知識綜合應(yīng)用的能力，另一方面可以提高信息安全數(shù)學(xué)基礎(chǔ)教。

結(jié)語

本文探討了融合學(xué)的效果，提高了學(xué)生學(xué)習(xí)的積極性和主動性。如何應(yīng)用算法設(shè)計與分析的思想設(shè)計更為有效的信息安全數(shù)學(xué)基礎(chǔ)中有關(guān)問題的算法及更加有效地融合算法設(shè)計和信息安全數(shù)學(xué)基礎(chǔ)是下一步要考慮的問題之一，其次需要利用微信等社交網(wǎng)絡(luò)工具和聊天機器人技術(shù)進一步搭建信息安全數(shù)學(xué)基礎(chǔ)課程答疑服務(wù)系統(tǒng)也是下一步考慮的問題之一。

參考文獻

[1]閆璽璽，劉琨.《信息安全數(shù)學(xué)基礎(chǔ)》教學(xué)方法探索與體會[J].考試周刊，2014（06）：114-115.

[2]李瑞琪，高敏芬，賈春福等.信息安全數(shù)學(xué)基礎(chǔ)的“講一練二考三”改革方案設(shè)計[J].計算機教育，2016（11）：27-29.

[3]秦艷琳，吳曉平.提高信息安全數(shù)學(xué)基礎(chǔ)課程教學(xué)效果的幾種途徑[J].計算機教育，2016（3）：132-135.

[4]陳恭亮.信息安全數(shù)學(xué)基礎(chǔ)（第二版）[M].清華大學(xué)出版社，2016.

[5]殷建平，徐云，王剛等譯.算法導(dǎo)論（第三版）[M].機械工業(yè)出版社，2014.

作者簡介

楊文忠，（1971.7—），男，河南，博士研究生，副主任，副教授，信息安全博士，碩士生導(dǎo)師。研究方向為網(wǎng)絡(luò)空間內(nèi)容安全、算法設(shè)計與分析、無線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)路由等。已發(fā)表文章20多篇，主持和參與國家級和省部級項目10多項。