田有亮 王雪梅
摘 要:該文從算法思維的角度探討密碼學(xué)的教學(xué)。根據(jù)密碼學(xué)課程理論性和應(yīng)用性均很強(qiáng)的特點(diǎn),結(jié)合密碼學(xué)數(shù)學(xué)基礎(chǔ)的算法特性,應(yīng)用算法的形式化方法、模塊化思想,定義分析密碼學(xué)課程中的基本概念,厘清課程中分組密碼、公鑰密碼等密碼系統(tǒng)的思路。在教學(xué)過(guò)程中應(yīng)用這些方法深入分析密碼體制設(shè)計(jì)的微妙之處及精髓,培養(yǎng)學(xué)生的密碼算法思維、密碼設(shè)計(jì)和分析的能力。
關(guān)鍵詞:算法思維 密碼學(xué) 分組秘密 公鑰密碼
中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1674-098X(2015)08(a)-0188-02
Algorithm Thinking Application of Cryptography Teaching
Tian Youliang1 Wang Xuemei2
(1. College of Science, Guizhou University, Guiyang GuiZhou,550025, China; 2. Guiyang Vocational and Technical College, Guiyang GuiZhou,550081, China)
Abstract:This paper discusses the problem of cryptography teaching from the algorithm thinking perspective. According to the theory and application features of the cryptography teaching, combining with the character of mathematic foundation of cryptographic, the cryptographic concept is defined and analyzed and thinking of cryptographic system is clarified by using the formalization and modularization method. Using these methods, the subtlety of cryptographic protocol design is the in-depth analysis in this teaching. By this way, we can cultivate our students abilities of the algorithm thinking, the Cipher design and the cryptanalysis.
Key words:Algorithm Thinking;Cryptography;Block Cipher;Public Key Cryptography
密碼學(xué)是信息安全類專業(yè)的重要專業(yè)基礎(chǔ)課程,在很多學(xué)校,它也是數(shù)學(xué)、計(jì)算機(jī)、通信等相關(guān)專業(yè)的專業(yè)選修課程。密碼學(xué)技術(shù)是信息安全的核心和關(guān)鍵,是數(shù)學(xué)在信息安全中的重要應(yīng)用,特別是初等數(shù)論、抽象代數(shù)等抽象數(shù)學(xué)知識(shí)在保密通信領(lǐng)域的應(yīng)用。密碼學(xué)課程是理論性和應(yīng)用性相結(jié)合的課程,充分體現(xiàn)了數(shù)學(xué)在具體應(yīng)用領(lǐng)域的特殊作用和核心地位。密碼學(xué)課程的教學(xué)主要圍繞基本安全特性,如保密性、認(rèn)證性、完整性、不可否認(rèn)性、可用性等,論述各種密碼原語(yǔ),主要包括傳統(tǒng)密碼體制、序列密碼、分組密碼、公鑰密碼、簽名與認(rèn)證、密鑰管理和密碼協(xié)議、密碼技術(shù)應(yīng)用等密碼算法的基本概念、發(fā)展歷程、數(shù)學(xué)原理、算法設(shè)計(jì)思想和應(yīng)用場(chǎng)景等。
算法可以說(shuō)是計(jì)算機(jī)認(rèn)識(shí)世界的基礎(chǔ)和橋梁,是計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)各個(gè)發(fā)展階段不可或缺的最基本技術(shù)之一。算法可以描述為一序列的計(jì)算步驟,用它來(lái)將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。其方法主要涉及遞推法、遞歸法、窮舉法、貪心算法、分冶法、動(dòng)態(tài)規(guī)劃法、迭代法、分支界定法、回溯法等。這些方法和原理已經(jīng)滲透到我們社會(huì)生活的方法面面。無(wú)論是我們?cè)谔焐巷w、還是在地上跑,或許是在辦工作旁工作,無(wú)時(shí)無(wú)刻算法都在影響和規(guī)劃著我們的一切。同時(shí)也給我們的生活和工作帶來(lái)前所未有的深刻改變。
該文從算法思維的角度分析密碼學(xué)課程教學(xué)。主要從形式化算法的概念探究分析密碼學(xué)課程中的基本概念;應(yīng)用程序設(shè)計(jì)中模塊化設(shè)計(jì)思想,深入分析密碼體制,特別是按照各個(gè)模塊的功能作用,分析密碼算法的設(shè)計(jì)思想和理念,組合分析密碼學(xué)教學(xué)中密碼協(xié)議的設(shè)計(jì)原理和方法。讓學(xué)生進(jìn)一步理解和掌握密碼學(xué)課程的相關(guān)概念和原理。
1 密碼學(xué)的數(shù)學(xué)基礎(chǔ)滲透著算法思維
密碼學(xué)的數(shù)學(xué)基礎(chǔ)課程通常包括概率論、初等數(shù)論、抽象代數(shù)等。這些課程具有鮮明的算法特性,特別是初等數(shù)論和抽象代數(shù)更是如此。
在密碼學(xué)教學(xué)課程中,需要使用很多抽象的數(shù)學(xué)概念,比如群、環(huán)、域、因式分解、同余、中國(guó)剩余定理、二次剩余、傳統(tǒng)教學(xué)仍然停留在課堂講解概念、定理分析證明、課后布置作業(yè)的等模式上。在學(xué)生聽(tīng)完課后,對(duì)其抽象概念只能囫圇吞棗,基本不甚理解其真正的應(yīng)用背景和意義所在。學(xué)生僅能做到對(duì)抽象數(shù)學(xué)概念的死記硬背,在做題過(guò)程中生搬硬套,流于固定形式和套路,基本不能做到深入理解、靈活掌握和自如運(yùn)用,給進(jìn)一步學(xué)習(xí)密碼學(xué)課程的深層次理解造成一定難度??梢?jiàn),在教學(xué)過(guò)程中只是讓學(xué)生通過(guò)做作業(yè)等常規(guī)方式來(lái)理解這些結(jié)論,必然不會(huì)起到較佳的效果。
因此,在密碼學(xué)的數(shù)學(xué)基礎(chǔ)的學(xué)習(xí)過(guò)程中,有必要結(jié)合這些知識(shí)的特點(diǎn),用算法的思維方式,模塊化的分析方法,給出初等數(shù)論、抽象代數(shù)中相關(guān)概念中的算法思想,通過(guò)算法程序化的思維,庖丁解牛的方式,按照其功能模塊,深入解剖其內(nèi)涵,同時(shí)從理論的角度剖析其應(yīng)用外延,必將使學(xué)生更加深入地理解其概念和算法原理。從密碼應(yīng)用的高度提高抽象數(shù)學(xué)教學(xué)的趣味性。
2 應(yīng)用形式化算法模式剖析密碼學(xué)概念
密碼學(xué)是在研究如何保密傳送信息的過(guò)程中發(fā)展起來(lái)的,簡(jiǎn)單地說(shuō),密碼學(xué)就是研究在敵對(duì)環(huán)境下如何實(shí)現(xiàn)保密的安全通信問(wèn)題。它隨著密碼編碼和密碼分析這對(duì)“矛”和“盾”的長(zhǎng)期永不停止的斗爭(zhēng)中發(fā)展壯大起來(lái)的。隨著先進(jìn)科學(xué)技術(shù)的應(yīng)用而成為一門融合多學(xué)科綜合發(fā)展的尖端科學(xué)技術(shù)。目前,在國(guó)內(nèi)外眾多高校的本科生均開(kāi)設(shè)了密碼學(xué)課程。因密碼學(xué)的軍事用途而使得密碼學(xué)本身帶有一定的神秘性,而在日常生活、工作的方方面面均用到秘密技術(shù)。由于密碼學(xué)數(shù)學(xué)基礎(chǔ)的抽象性,使得對(duì)密碼學(xué)的基本概念、原理的學(xué)習(xí)和理解,存在一定的難度。特別是對(duì)單向函數(shù)、陷門置換,公鑰密碼等,非常不符合我們傳統(tǒng)的數(shù)學(xué)思維模式,這給學(xué)生的學(xué)習(xí)和老師的教學(xué)均帶來(lái)一定的難度。在對(duì)密碼學(xué)的這些概念的理解過(guò)程中,必須讓學(xué)生用“轉(zhuǎn)個(gè)彎”的方式,從算法形式化的模式去剖析,增強(qiáng)教學(xué)過(guò)程中這些知識(shí)理解的效果。
在計(jì)算機(jī)科學(xué)、安全協(xié)議等領(lǐng)域,算法的形式化方法是一種基于數(shù)學(xué)符合化描述技術(shù),它適合于相關(guān)系統(tǒng)的描述、開(kāi)發(fā)和驗(yàn)證。人們將形式化方法用于這些計(jì)算機(jī)領(lǐng)域,其目的是為了進(jìn)一步安全可靠的分析這些系統(tǒng)的相關(guān)性能,期望以一種較為科學(xué)的方式提高所設(shè)計(jì)算法、系統(tǒng)的可靠性和魯棒性。這里我們主要用算法形式化的模式去剖析密碼學(xué)基本概念教學(xué)中的一些問(wèn)題,特別是在公鑰密碼系統(tǒng)下的基本概念分析和理解。
我們知道,在公鑰密碼系統(tǒng)中,人們都會(huì)自然的想到RSA密碼算法,在諸多老師和大學(xué)本科生的心目中想到的只是基于大整數(shù)分解困難問(wèn)題的RSA是如何設(shè)計(jì)的,沒(méi)有深刻的去理解這個(gè)密碼體制形式化定義和形式化描述。下面就以公鑰加密算法的講解為例給以說(shuō)明。
在現(xiàn)代密碼學(xué)體系中,公鑰密碼是最能體現(xiàn)當(dāng)代密碼學(xué)思想的科學(xué)性之一。在1976年美國(guó)斯坦福大學(xué)的Diffie和Hellman兩人提出了公開(kāi)密鑰密碼的新思想后,不僅其加密算法可以公開(kāi),甚至加密用的密鑰(主要是公鑰)也可以公開(kāi)而不降低信息的保密程度,也一定程度上解決了之前密碼體制的密鑰管理問(wèn)題。那么,在公鑰密碼體制的講解過(guò)程中,重點(diǎn)給學(xué)生交代清楚其形式化定義。
這里以講解RSA公鑰加密算法為例。首先,詳細(xì)論述公鑰加密體制的形式化定義;其次,分析RSA的哪一部分是實(shí)現(xiàn)公鑰加密的哪一部分功能;再次,分析算法中可能存在的安全漏洞;最后,給出一個(gè)具體的數(shù)字實(shí)例。具體地,一個(gè)公鑰解密體制,從算法的角度,可以被形式化為一個(gè)三元組(K,E,D)。其中K代表的是密鑰生成算法,其形式化功能就是生成一對(duì)匹配的公、私鑰對(duì),為后續(xù)算法E、D加解密做準(zhǔn)備,K可以是概率算法;E是加密算法,其功能模塊就是實(shí)現(xiàn)消息的加密,該算法也可以是概率算法;D是解密算法,改算法的功能是實(shí)現(xiàn)相應(yīng)密文的解密操作。然后給出RSA實(shí)現(xiàn)各個(gè)功能的具體方法,包括RSA的密鑰生成算法、加密算法和解密算法三個(gè)部分;接下來(lái),形式化定義相應(yīng)的功能模塊,詳細(xì)分析可能出現(xiàn)的安全問(wèn)題,攻擊者可能掌握的資源,明確指出RSA加密算法的安全性的數(shù)學(xué)基礎(chǔ);最后用一個(gè)數(shù)字實(shí)例說(shuō)明算法的教學(xué)效果,增強(qiáng)學(xué)生對(duì)該算法的理解。
可見(jiàn),應(yīng)用算法形式化模式分析講解公鑰密碼體制及具體的實(shí)例,能進(jìn)一步厘清公鑰密碼算法的思路,讓學(xué)生理解RSA加密體制的算法流程和安全性能之關(guān)鍵所在,符合當(dāng)代大學(xué)生在學(xué)習(xí)過(guò)程中分析、解決問(wèn)題的思維模式,能在教學(xué)過(guò)程中起到事半功倍的教學(xué)效果。該算法形式化方法模式也可以應(yīng)用到密碼學(xué)課程的其他知識(shí)的教學(xué)過(guò)程中。
3 應(yīng)用模塊化思想分析密碼體制的設(shè)計(jì)
本節(jié)討論應(yīng)用算法的模塊化思想分析密碼體制的設(shè)計(jì)。在密碼學(xué)的分組密碼體制的教學(xué)過(guò)程中,根據(jù)密碼體制的功能進(jìn)行分塊,講解清楚各個(gè)分塊的設(shè)計(jì)原則和目標(biāo),給出相應(yīng)模塊的實(shí)現(xiàn)方法;最后給出各個(gè)功能模塊的組合,分析其安全功能沒(méi)有因?yàn)檫@些功能的組合而降低。讓學(xué)生清楚該部分內(nèi)容的架構(gòu)和“全貌”,能系統(tǒng)的理清密碼體制設(shè)計(jì)的方法和規(guī)則,同時(shí)做到對(duì)知識(shí)點(diǎn)的類推和舉一反三的效果。下面以分組密碼的教學(xué)為例。
根據(jù)如上分析,在講授分組密碼設(shè)計(jì)時(shí),可以分三個(gè)層面進(jìn)行論述。首先,根據(jù)分組密碼的安全需求,論述分組密碼需要具有的安全性質(zhì)。其次,根據(jù)這些安全性質(zhì),利用算法模塊化思想,按照其性質(zhì)的實(shí)現(xiàn)功能,給出相應(yīng)的功能分塊。最后,根據(jù)不同的實(shí)現(xiàn)方法,給出相應(yīng)實(shí)現(xiàn)算法。
我們知道,對(duì)分組密碼的主要威脅是已知明文攻擊,因分組密碼的密鑰z被重復(fù)使用,即多次一密。為抵抗該類攻擊,要求在設(shè)計(jì)密碼時(shí),要求分組密碼具有:(1)混淆性:所設(shè)計(jì)的密碼應(yīng)使得明文、密文、密鑰之間的依賴關(guān)系相當(dāng)復(fù)雜,以至于這種依賴關(guān)系對(duì)密碼分析者來(lái)說(shuō)是無(wú)法利用的。(2)擴(kuò)散性:所設(shè)計(jì)的密碼應(yīng)使得密鑰的每一個(gè)比特影響密文的每一個(gè)比特,以防止對(duì)密鑰進(jìn)行逐段破譯;明文的每一個(gè)比特影響密文的每一個(gè)比特,以便最充分地隱蔽明文。(3)具有較高的非線性度。根據(jù)這些安全性要求,利用模塊化設(shè)計(jì)思想,其分組密碼可模塊化為計(jì)算部件、計(jì)算部件的組合、SPN(即替換/置換網(wǎng)絡(luò))及多輪迭代與輪函數(shù)。不同的模塊實(shí)現(xiàn)不同的安全性質(zhì),同時(shí)保證各部件之間的功能不是抵消關(guān)系,而是疊加關(guān)系,使得其安全性能只會(huì)增加,而不是相互抵消。最后,給出具體的分組密碼算法,詳細(xì)分析其具體實(shí)現(xiàn)過(guò)程,如DES、IDEA、AES等。
可見(jiàn),應(yīng)用算法的模塊化思想,闡述分組密碼體制設(shè)計(jì),能做到有的放矢去尋找相應(yīng)的數(shù)學(xué)模型實(shí)現(xiàn)相應(yīng)的功能,也給這些密碼算法的形式化描述和分析帶來(lái)諸多便利之處。同時(shí)也能讓學(xué)生充分理解分組密碼體制設(shè)計(jì)的微妙之處及精髓,調(diào)動(dòng)學(xué)生的學(xué)習(xí)熱情和積極性,培養(yǎng)學(xué)生的密碼設(shè)計(jì)和分析的能力。
4 結(jié)語(yǔ)
該文應(yīng)用算法思維模式討論大學(xué)密碼學(xué)的教學(xué)問(wèn)題。首先,闡述密碼學(xué)的相關(guān)數(shù)學(xué)基礎(chǔ)課程中無(wú)不滲透著算法的思想,特別是在數(shù)論、抽象代數(shù)中更是如此。其次,應(yīng)用算法形式化方法和模式討論公鑰密碼體制的教學(xué),以提高學(xué)生理解公鑰密碼體制的基本概念及安全性。最后,基于算法設(shè)計(jì)的模塊化設(shè)計(jì)思想,以分組密碼體制設(shè)計(jì)為例,分析論述這部分的教學(xué)方法,讓教師和學(xué)生在學(xué)習(xí)和教學(xué)中都能夠做到有的放矢,以此提高密碼學(xué)教學(xué)過(guò)程中學(xué)生學(xué)習(xí)的接收能力。
參考文獻(xiàn)
[1]毛文波,著.現(xiàn)代密碼學(xué)理論與實(shí)踐[M].王繼林,等,譯.北京:電子工業(yè)出版社,2004.
[2]李云清.算法形式化推導(dǎo)及其在軟件重用中的應(yīng)用[J].計(jì)算機(jī)工程,2003(9):22-23.
[3]Katz J and Lindell Y. Modern Cryptography.Chapman & Hall/CRC,2007.
[4]Cormen H T, Leiserson E C, Rivest L R and Stein C.算法導(dǎo)論[M].潘金貴,等,譯.機(jī)械工業(yè)出版社,2006.