算法思維在密碼學教學中的應用

田有亮 王雪梅

摘 要：該文從算法思維的角度探討密碼學的教學。根據(jù)密碼學課程理論性和應用性均很強的特點，結(jié)合密碼學數(shù)學基礎(chǔ)的算法特性，應用算法的形式化方法、模塊化思想，定義分析密碼學課程中的基本概念，厘清課程中分組密碼、公鑰密碼等密碼系統(tǒng)的思路。在教學過程中應用這些方法深入分析密碼體制設(shè)計的微妙之處及精髓，培養(yǎng)學生的密碼算法思維、密碼設(shè)計和分析的能力。

關(guān)鍵詞：算法思維 密碼學 分組秘密 公鑰密碼

中圖分類號：G642 文獻標識碼：A 文章編號：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

密碼學是信息安全類專業(yè)的重要專業(yè)基礎(chǔ)課程，在很多學校，它也是數(shù)學、計算機、通信等相關(guān)專業(yè)的專業(yè)選修課程。密碼學技術(shù)是信息安全的核心和關(guān)鍵，是數(shù)學在信息安全中的重要應用，特別是初等數(shù)論、抽象代數(shù)等抽象數(shù)學知識在保密通信領(lǐng)域的應用。密碼學課程是理論性和應用性相結(jié)合的課程，充分體現(xiàn)了數(shù)學在具體應用領(lǐng)域的特殊作用和核心地位。密碼學課程的教學主要圍繞基本安全特性，如保密性、認證性、完整性、不可否認性、可用性等，論述各種密碼原語，主要包括傳統(tǒng)密碼體制、序列密碼、分組密碼、公鑰密碼、簽名與認證、密鑰管理和密碼協(xié)議、密碼技術(shù)應用等密碼算法的基本概念、發(fā)展歷程、數(shù)學原理、算法設(shè)計思想和應用場景等。

算法可以說是計算機認識世界的基礎(chǔ)和橋梁，是計算機和網(wǎng)絡(luò)技術(shù)各個發(fā)展階段不可或缺的最基本技術(shù)之一。算法可以描述為一序列的計算步驟，用它來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。其方法主要涉及遞推法、遞歸法、窮舉法、貪心算法、分冶法、動態(tài)規(guī)劃法、迭代法、分支界定法、回溯法等。這些方法和原理已經(jīng)滲透到我們社會生活的方法面面。無論是我們在天上飛、還是在地上跑，或許是在辦工作旁工作，無時無刻算法都在影響和規(guī)劃著我們的一切。同時也給我們的生活和工作帶來前所未有的深刻改變。

該文從算法思維的角度分析密碼學課程教學。主要從形式化算法的概念探究分析密碼學課程中的基本概念；應用程序設(shè)計中模塊化設(shè)計思想，深入分析密碼體制，特別是按照各個模塊的功能作用，分析密碼算法的設(shè)計思想和理念，組合分析密碼學教學中密碼協(xié)議的設(shè)計原理和方法。讓學生進一步理解和掌握密碼學課程的相關(guān)概念和原理。

1 密碼學的數(shù)學基礎(chǔ)滲透著算法思維

密碼學的數(shù)學基礎(chǔ)課程通常包括概率論、初等數(shù)論、抽象代數(shù)等。這些課程具有鮮明的算法特性，特別是初等數(shù)論和抽象代數(shù)更是如此。

在密碼學教學課程中，需要使用很多抽象的數(shù)學概念，比如群、環(huán)、域、因式分解、同余、中國剩余定理、二次剩余、傳統(tǒng)教學仍然停留在課堂講解概念、定理分析證明、課后布置作業(yè)的等模式上。在學生聽完課后，對其抽象概念只能囫圇吞棗，基本不甚理解其真正的應用背景和意義所在。學生僅能做到對抽象數(shù)學概念的死記硬背，在做題過程中生搬硬套，流于固定形式和套路，基本不能做到深入理解、靈活掌握和自如運用，給進一步學習密碼學課程的深層次理解造成一定難度?？梢?，在教學過程中只是讓學生通過做作業(yè)等常規(guī)方式來理解這些結(jié)論，必然不會起到較佳的效果。

因此，在密碼學的數(shù)學基礎(chǔ)的學習過程中，有必要結(jié)合這些知識的特點，用算法的思維方式，模塊化的分析方法，給出初等數(shù)論、抽象代數(shù)中相關(guān)概念中的算法思想，通過算法程序化的思維，庖丁解牛的方式，按照其功能模塊，深入解剖其內(nèi)涵，同時從理論的角度剖析其應用外延，必將使學生更加深入地理解其概念和算法原理。從密碼應用的高度提高抽象數(shù)學教學的趣味性。

2 應用形式化算法模式剖析密碼學概念

密碼學是在研究如何保密傳送信息的過程中發(fā)展起來的，簡單地說，密碼學就是研究在敵對環(huán)境下如何實現(xiàn)保密的安全通信問題。它隨著密碼編碼和密碼分析這對“矛”和“盾”的長期永不停止的斗爭中發(fā)展壯大起來的。隨著先進科學技術(shù)的應用而成為一門融合多學科綜合發(fā)展的尖端科學技術(shù)。目前，在國內(nèi)外眾多高校的本科生均開設(shè)了密碼學課程。因密碼學的軍事用途而使得密碼學本身帶有一定的神秘性，而在日常生活、工作的方方面面均用到秘密技術(shù)。由于密碼學數(shù)學基礎(chǔ)的抽象性，使得對密碼學的基本概念、原理的學習和理解，存在一定的難度。特別是對單向函數(shù)、陷門置換，公鑰密碼等，非常不符合我們傳統(tǒng)的數(shù)學思維模式，這給學生的學習和老師的教學均帶來一定的難度。在對密碼學的這些概念的理解過程中，必須讓學生用“轉(zhuǎn)個彎”的方式，從算法形式化的模式去剖析，增強教學過程中這些知識理解的效果。

在計算機科學、安全協(xié)議等領(lǐng)域，算法的形式化方法是一種基于數(shù)學符合化描述技術(shù)，它適合于相關(guān)系統(tǒng)的描述、開發(fā)和驗證。人們將形式化方法用于這些計算機領(lǐng)域，其目的是為了進一步安全可靠的分析這些系統(tǒng)的相關(guān)性能，期望以一種較為科學的方式提高所設(shè)計算法、系統(tǒng)的可靠性和魯棒性。這里我們主要用算法形式化的模式去剖析密碼學基本概念教學中的一些問題，特別是在公鑰密碼系統(tǒng)下的基本概念分析和理解。

我們知道，在公鑰密碼系統(tǒng)中，人們都會自然的想到RSA密碼算法，在諸多老師和大學本科生的心目中想到的只是基于大整數(shù)分解困難問題的RSA是如何設(shè)計的，沒有深刻的去理解這個密碼體制形式化定義和形式化描述。下面就以公鑰加密算法的講解為例給以說明。

在現(xiàn)代密碼學體系中，公鑰密碼是最能體現(xiàn)當代密碼學思想的科學性之一。在1976年美國斯坦福大學的Diffie和Hellman兩人提出了公開密鑰密碼的新思想后，不僅其加密算法可以公開，甚至加密用的密鑰（主要是公鑰）也可以公開而不降低信息的保密程度，也一定程度上解決了之前密碼體制的密鑰管理問題。那么，在公鑰密碼體制的講解過程中，重點給學生交代清楚其形式化定義。

這里以講解RSA公鑰加密算法為例。首先，詳細論述公鑰加密體制的形式化定義；其次，分析RSA的哪一部分是實現(xiàn)公鑰加密的哪一部分功能；再次，分析算法中可能存在的安全漏洞；最后，給出一個具體的數(shù)字實例。具體地，一個公鑰解密體制，從算法的角度，可以被形式化為一個三元組（K，E，D）。其中K代表的是密鑰生成算法，其形式化功能就是生成一對匹配的公、私鑰對，為后續(xù)算法E、D加解密做準備，K可以是概率算法；E是加密算法，其功能模塊就是實現(xiàn)消息的加密，該算法也可以是概率算法；D是解密算法，改算法的功能是實現(xiàn)相應密文的解密操作。然后給出RSA實現(xiàn)各個功能的具體方法，包括RSA的密鑰生成算法、加密算法和解密算法三個部分；接下來，形式化定義相應的功能模塊，詳細分析可能出現(xiàn)的安全問題，攻擊者可能掌握的資源，明確指出RSA加密算法的安全性的數(shù)學基礎(chǔ)；最后用一個數(shù)字實例說明算法的教學效果，增強學生對該算法的理解。

可見，應用算法形式化模式分析講解公鑰密碼體制及具體的實例，能進一步厘清公鑰密碼算法的思路，讓學生理解RSA加密體制的算法流程和安全性能之關(guān)鍵所在，符合當代大學生在學習過程中分析、解決問題的思維模式，能在教學過程中起到事半功倍的教學效果。該算法形式化方法模式也可以應用到密碼學課程的其他知識的教學過程中。

3 應用模塊化思想分析密碼體制的設(shè)計

本節(jié)討論應用算法的模塊化思想分析密碼體制的設(shè)計。在密碼學的分組密碼體制的教學過程中，根據(jù)密碼體制的功能進行分塊，講解清楚各個分塊的設(shè)計原則和目標，給出相應模塊的實現(xiàn)方法；最后給出各個功能模塊的組合，分析其安全功能沒有因為這些功能的組合而降低。讓學生清楚該部分內(nèi)容的架構(gòu)和“全貌”，能系統(tǒng)的理清密碼體制設(shè)計的方法和規(guī)則，同時做到對知識點的類推和舉一反三的效果。下面以分組密碼的教學為例。

根據(jù)如上分析，在講授分組密碼設(shè)計時，可以分三個層面進行論述。首先，根據(jù)分組密碼的安全需求，論述分組密碼需要具有的安全性質(zhì)。其次，根據(jù)這些安全性質(zhì)，利用算法模塊化思想，按照其性質(zhì)的實現(xiàn)功能，給出相應的功能分塊。最后，根據(jù)不同的實現(xiàn)方法，給出相應實現(xiàn)算法。

我們知道，對分組密碼的主要威脅是已知明文攻擊，因分組密碼的密鑰z被重復使用，即多次一密。為抵抗該類攻擊，要求在設(shè)計密碼時，要求分組密碼具有：（1）混淆性：所設(shè)計的密碼應使得明文、密文、密鑰之間的依賴關(guān)系相當復雜，以至于這種依賴關(guān)系對密碼分析者來說是無法利用的。（2）擴散性：所設(shè)計的密碼應使得密鑰的每一個比特影響密文的每一個比特，以防止對密鑰進行逐段破譯；明文的每一個比特影響密文的每一個比特，以便最充分地隱蔽明文。（3）具有較高的非線性度。根據(jù)這些安全性要求，利用模塊化設(shè)計思想，其分組密碼可模塊化為計算部件、計算部件的組合、SPN（即替換/置換網(wǎng)絡(luò)）及多輪迭代與輪函數(shù)。不同的模塊實現(xiàn)不同的安全性質(zhì)，同時保證各部件之間的功能不是抵消關(guān)系，而是疊加關(guān)系，使得其安全性能只會增加，而不是相互抵消。最后，給出具體的分組密碼算法，詳細分析其具體實現(xiàn)過程，如DES、IDEA、AES等。

可見，應用算法的模塊化思想，闡述分組密碼體制設(shè)計，能做到有的放矢去尋找相應的數(shù)學模型實現(xiàn)相應的功能，也給這些密碼算法的形式化描述和分析帶來諸多便利之處。同時也能讓學生充分理解分組密碼體制設(shè)計的微妙之處及精髓，調(diào)動學生的學習熱情和積極性，培養(yǎng)學生的密碼設(shè)計和分析的能力。

4 結(jié)語

該文應用算法思維模式討論大學密碼學的教學問題。首先，闡述密碼學的相關(guān)數(shù)學基礎(chǔ)課程中無不滲透著算法的思想，特別是在數(shù)論、抽象代數(shù)中更是如此。其次，應用算法形式化方法和模式討論公鑰密碼體制的教學，以提高學生理解公鑰密碼體制的基本概念及安全性。最后，基于算法設(shè)計的模塊化設(shè)計思想，以分組密碼體制設(shè)計為例，分析論述這部分的教學方法，讓教師和學生在學習和教學中都能夠做到有的放矢，以此提高密碼學教學過程中學生學習的接收能力。

參考文獻

[1]毛文波，著.現(xiàn)代密碼學理論與實踐[M].王繼林，等，譯.北京：電子工業(yè)出版社，2004.

[2]李云清.算法形式化推導及其在軟件重用中的應用[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.算法導論[M].潘金貴，等，譯.機械工業(yè)出版社，2006.