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

（新疆大學信息科學與工程學院 新疆烏魯木齊 830046）

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

一、教學現(xiàn)狀

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

二、融合算法的教學模式

從本科專業(yè)培養(yǎng)方案上來說應該在信息安全數(shù)學基礎之前開設程序設計語言課程如C語言、Python語言等、線性代數(shù)、數(shù)據(jù)結(jié)構(gòu)和算法設計與分析等課程。學生有一定的編程基礎后，再學習信息安全數(shù)學基礎理論時，就可以使用有關數(shù)據(jù)結(jié)構(gòu)和編程語言實現(xiàn)擴展歐幾里得、模重復平方、原根等的具體計算，當編寫出相應的程序后，學生比較有成就感和獲得感，又鍛煉了學生編程能力，使學生體會到信息安全數(shù)學基礎不僅可以從數(shù)學角度去理解和計算也可以從計算機科學的計算角度去理解和計算。其次應該設置信息安全數(shù)學基礎課程實踐課程?？梢栽O置廣義歐幾里得算法、模重復平方算法、一次同余式求解算法、中國剩余定理算法、勒讓德符號計算算法、原根求解算法、Miller-Rabin算法和有限域構(gòu)造算法等，每個算法實踐大約4學時，涵蓋了信息安全數(shù)學基礎主要概念、定理和結(jié)論[4]等。若無法在信息安全數(shù)學基礎課時內(nèi)安排實踐課程，可以安排為實踐類課程作業(yè)。學生除了需要進行實踐外，應該理解廣義歐幾里得算法和模重復平方算法等算法設計思想和計算機復雜度，理解為什么可以將廣義歐幾里得算法和模重復平方算法等算法應該密碼理論中，從算法角度理解這些迭代算法的循環(huán)不變式[5]其實就是信息安全數(shù)學基礎中有關定理的體現(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ù)學基礎中廣義歐幾里得除法的一個定理，因而是正確的。其計算過程如下表所示。計算時間復雜度是O（lg n），其中n是整數(shù)a，b中絕對值較大者。該算法主要用于求模n乘法逆元，在密碼學RSA算法等涉及求逆元的算法都會使用到該算法，是必須要掌握的一個算法。該算法計算過程代碼如下。[4]

2.模重復平方算法

模重復平方算法主要用于計算bn（mod m），該算法主要應用在密碼學中RSA和Diffie-Hellman等算法的模大整數(shù)冪運算，可以極大加速其計算過程。當n=n0+n12+…+nk-12k-1，其計算過程如下表所示，該迭代算法維持了一個循環(huán)不變式（i=0，1，…，k-1），因而算法結(jié)束時可以正確計算bn（mod m）。該算法的計算時間復雜度是O（lg n），n是模重復平方算法的冪指數(shù)。該算法計算過程如表1所示。

表1 模重復平方算法

該算法主要代碼如下。

ULONG64 Rsa::modPower（ULONG64 b，ULONG64 n，ULONG64 m）

3.模m原根計算算法

根據(jù)信息安全數(shù)學基礎中初等數(shù)論結(jié)論模m有原根的重要條件是m=2、4、pa、2pa，其中p是素數(shù)。計算原根的關鍵是找到素數(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ù)學基礎教。

結(jié)語

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

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

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

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

[4]陳恭亮.信息安全數(shù)學基礎(第二版)[M].清華大學出版社,2016.

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