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

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

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

一、教學現狀

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

二、融合算法的教學模式

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

三、具體實例

1.擴展歐幾里得算法

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

2.模重復平方算法

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

表1 模重復平方算法

該算法主要代碼如下。

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

3.模m原根計算算法

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

本文探討了融合算法設計與分析思想到信息安全數學基礎教學中，一方面可以提高知識綜合應用的能力，另一方面可以提高信息安全數學基礎教。

結語

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

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

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

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

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

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