“背包公鑰密碼體制”的啟發式教學設計與思考

趙秀鳳　關杰　李信然

摘要：啟發式教學就是教師根據教學目的、教學內容、學生的知識水平和知識規律，運用各種教學手段，采用啟廢誘導的辦法傳授知識、培養能力，使學生積極主動地學習，以促進他們的身心發展的教學方法。1976年，Diffie（笛菲）和Hellman（赫爾曼）提出了公鑰密碼學的思想。隨后，Merkel（摩克）和Hellman（赫爾曼）基于背包問題構造了陷門單向函數，給出了背包公鑰密碼體制。背包公鑰密碼體制體現了公鑰密碼的設計思想，揭示了公鑰密碼的本質，被譽為打開公鑰密碼學大門的一塊敲門磚。因此，背包公鑰密碼體制是《密碼學》的一個重要的教學內容。在建構主義教學理論的指導下，以學員為主體的背包公鑰密碼體制的啟發式教學設計有非常重要的意義，多次課堂教學實踐證明了啟發式教學設計有非常良好的教學效果。

關鍵詞：啟發式教學；背包公鑰密碼體制；教學設計；教學反思

一、引言

北京大學錢理群教授認為，“教育就是牽著學生的手，把他們引領到大師面前、巨人面前，互相介紹之后就悄悄地離開，讓他們進行心貼心的談話”。錢理群的教育理念放在當今社會仍具有重要的現實意義，在這樣的教育理念指導下的實踐教學，很容易培養學生主動學習、主動思考、主動發現的習慣，在這個過程中學生也可以領略到豁然頓悟或悠然會心的快樂以及成就感，從而保持樂此不疲的求知與學習興趣。錢理群的教育思想落實到具體的教學實踐中就是啟發式教學方法。所謂啟發式教學，就是教師根據教學目的、教學內容、學生的知識水平和知識規律，運用各種教學手段，采用啟發誘導的辦法傳授知識、培養能力，使學生積極主動地學習，以促進他們的身心發展的教學方法。如今，許多高校及教師都在積極探索啟發式教學方法。

《密碼學》是中國人民解放軍信息工程大學面向信息安全專業本科生開設的專業基礎課程，通過課程的學習，學生可以理解編制密碼的基本原理，掌握實現信息機密性和認證性的密碼技術。課程組在建構主義教學理論的指導下，對《密碼學》中的“背包公鑰密碼體制”進行了啟發式教學設計，課堂教學實踐證明了啟發式教學設計有非常良好的教學效果。

1976年，Diffie（笛菲）和Hellman（赫爾曼）提出了公鑰密碼學的思想。1978年，Merkel（摩克）和Hellman（赫爾曼）在論文“Hiding informationand signatures in trapdoor knapsacks”中基于背包問題構造了陷門單向函數，給出了著名的背包公鑰密碼體制。背包公鑰密碼體制體現了公鑰密碼的設計思想，揭示了公鑰密碼的本質，被譽為打開公鑰密碼大門的一塊敲門磚。因此，背包公鑰密碼體制對于公鑰密碼研究有著非常重要的理論意義和應用價值，是《密碼學》的一個重要的教學內容。

二、教學過程設計

背包公鑰密碼體制的啟發式教學過程設計分為四個教學環節：首先，教師由密鑰管理問題引出公鑰密碼思想；其次，給出背包問題的定義；再次，通過啟發誘導，探索背包公鑰密碼體制的設計原理：最后，總結背包公鑰密碼體制的意義，并給出安全性分析，再以花絮的形式引出下次課程的學習內容。

（一）第一個教學環節：任務驅動，引出公鑰密碼思想

在利用序列密碼和分組密碼系統進行保密信息傳輸時，發方和收方需要預先共享一個密鑰。例如：Bob想給Alice發送一個保密郵件，那么，他首先利用共享密鑰與加密算法對明文進行加密，然后將密文發送給Alice，Alice收到密文之后，利用共享密鑰與解密算法得到明文。這種密碼體制要求通信雙方在進行保密通信之前，預先共享密鑰，因此，必須首先解決密鑰分發問題。

隨著網絡科技的發展與廣泛應用，尤其是在大型通信網絡中，密鑰管理問題日益成為一個影響發展的瓶頸。比如，在1000個人的通信網絡中，每個人需要保管999個密鑰，整個網絡就需要（1000×999）/2=499500個密鑰。此時，問題就出來了：

問題1：如何降低密鑰管理的代價呢？

教師可以啟發學生思考：密鑰管理的關鍵問題是密鑰分發，如果可以將加密密鑰公開，就無須密鑰分發這個步驟了，但是這樣就會危及到解密密鑰的安全性。在研究中教師可以利用生活中“鎖和鑰匙”的原理，引導學生將加密密鑰和解密密鑰進行區分，并且加密密鑰的公開不影響解密密鑰的安全性。然后，教師給出總結：1976年，Diffie（笛菲）和Hellman（赫爾曼）在美國國家計算機大會上提出了公開密碼學的思想，這項舉措成為密碼史上的里程碑，對密碼學領域的后續發展有重要的意義。如果每個用戶都有一對密鑰，一個用于加密，稱加密密鑰，一個用于脫密，稱脫密密鑰，加密密鑰是公開的，而脫密密鑰是保密的，且加密密鑰的公開不會危及脫密密鑰的安全。這樣，用戶只要保存一個脫密密鑰，就可以大大降低密鑰管理的成本與負擔。這就是公鑰密碼的思想。緊接著，又會有一個非常自然的問題出現：

問題2：如何構造一個具體的公鑰密碼體制呢？

從這個問題教師可以引出陷門單向函數的概念。具體而言，從“加密密鑰→解密密鑰”的難解性引出單向性的概念：從“密文→明文”的難解性和“密文（解密密匙）→明文”的可解密性引出陷門單向函數的定義。從而總結出：設計公鑰密碼體制的關鍵是構造一個陷門單向函數。

問題3：如何構造陷門單向函數？

教師啟發學生思考：從單向函數的難解性，引出數學上的難解問題，進而引出背包問題。

（二）第二個教學環節：背包問題

問題4：什么是背包問題呢？

定義1：設長度為b的背包和一組直徑相同的圓盤共n個，圓盤厚度分別為a₁，…，a_n，試問能否從中選出一部分盤子，正好裝滿這個背包？如果能，應該如何選取？這個問題形式化描述為：

a₁X₁+a₂X₂+…+a_nX_n=bendprint

這個方程是否有二進制解（X₁，X₂，…，X_n）？如果有，則求解。

教師帶領學生分析這個問題的計算復雜度為○（2ⁿ），即該問題是多項式時間難解問題。那么，能否利用背包問題設計公鑰加密算法呢？

教師可以啟發學生思考：背包問題可以設計加密算法，即將明文對應二進制串X₁，X₂，…，X_n，將b對應密文c，方案能保證明文的安全性，但是合法的接收者也無法正確解密，原因就在于背包問題是NP困難問題。教師給出總結：背包問題可以用于加密，但無法解密。

下面給出一種特殊的背包問題。

定義2：簡單背包問題

如果序列a₁，…，a_n滿足則該序列稱為超遞增序列，超遞增序列對應的背包問題被稱為簡單背包問題。

一般背包問題難解，簡單背包問題可解嗎？通過一個例子可以說明解簡單背包問題的算法。

例1：求簡單背包問題3X₁+11X₂+24X₃+50X₄+115X₅=142.

那么，能否利用簡單背包問題設計公鑰密碼算法？

教師引導學生思考：由簡單背包問題的可解性，考慮利用簡單背包問題設計解密算法，即簡單背包問題適用于設計解密算法，但是無法保證明文的安全性。

問題5：那么，能否綜合利用簡單背包問題和背包問題構造陷門單向函數呢？

（三）第三個教學環節：探討背包公鑰密碼體制的原理

背包密碼體制的基本思想是：選取一個超遞增的背包序列，通過一個保密的置亂變化，把這個序列變成一個普通的背包序列。然后，將變化后的普通背包序列作為公鑰，將超遞增的背包序列作為私鑰保密。

值得注意的是，在這個教學環節中，研究者不是把上述思想直接呈現給大家，而是帶領大家一起去發現、去探索，一起去經歷這個難得的過程。這是課程的重點內容，也是難點內容。

同時，教師也要引導大家思考：簡單背包問題可以解密，而普通背包問題可以加密，那么，如果大家利用簡單背包問題經過一個保密變化F，把它變成一個普通背包問題，然后利用普通背包問題就可以加密得到密文，而密文對應一個背包問題，因此，明文無法恢復，從而保證了明文的安全性。另外，對于接收者來說，他掌握了保密變化，所以可以利用保密變化的逆變換將密文變換一個C，C對應一個簡單背包問題，從而可以利用超遞增序列進行解密。

保密變換F的作用是把超遞增序列的特性隱藏。下面，研究者帶領學生一起探討如何選擇保密變化F。首先，F應該保證解密的正確性，即應該保證C對應簡單背包問題。

已知超遞增序列γ=（γ₁，γ₂，…，γ_n），Mi=F（γ_i，c=∑ⁿ_i=1=lm_iM_i，c'=F^-1（c）=（∑ⁿ_i=1lm_iM_i）=F^-1（∑¹_i=1m_iF（γ_i）

為了保證解密的正確性，上式必須等于∑ⁿ_i=m_iγ_i.因此，F必須滿足線性疊加性，即同態性。那么，什么運算具備同態性呢？乘法運算。但是乘法運算無法保證將超遞增序列的超遞增性隱藏，因此，無法滿足研究的需求。什么運算可以隱藏超遞增性呢？教師要鼓勵學生發散思維，最后的結論是模約減運算（同余運算）。

在實施課堂教學時，教師應該力求將以上背包公鑰密碼的設計原理部分分析透徹。然后，給出Merkle-Hellman背包公鑰密碼體制，并利用一個實例加深理解。

（四）第四個教學環節：總結

研究者從兩個方面對本次課程進行總結，首先是背包公鑰密碼體制在公鑰密碼研究領域的意義，其次是通過背包公鑰密碼體制的安全性分析，以花絮的形式引出下次課程的學習內容。

1.背包公鑰密碼的意義

背包公鑰密碼體制利用簡單背包問題和背包問題設計了陷門單向函數，體現了公鑰密碼體制的設計思想，揭示了公鑰密碼算法的本質。其設計思想至今依然閃耀著智慧的光輝，閃爍著創新的光芒，在新型公鑰密碼體制設計以及全同態密碼設計方面都有應用，對現代密碼設計與分析都有重要的參考價值和指導意義。

2.背包公鑰密碼體制的安全性

雖然背包問題是數學上的難解問題，但是背包公鑰密碼體制并不是無堅不摧的。起初，Merkle（摩克）和Hellman（赫爾曼）認為這算法無懈可擊，就懸賞100美元給第一個破譯它的人。作為公鑰的序列畢竟還是有原來的超遞增序列的影子的，Shamir，即薩莫爾（RSA中的“S”），在兩年后抓住了變換的“尾巴”，將它破譯并得到了獎金。隨后，Merkle（摩克）和Hellman（赫爾曼）又加大了變換的強度，并懸賞1000美元。但這次Rivest，即李維斯特（RsA中的“R”），又成功將它破解了。Merkle（摩克）和Hellman（赫爾曼）不敢再對下一個版本懸賞10000美元，所以Adleman，即阿德曼（也就是RSA中的“A”）就沒有好運氣了。后來，背包公鑰密碼算法又被加強了，但是應用并不廣泛。

最著名的公鑰密碼算法是RSA公鑰密碼算法，它是由麻省理工學院（MIT）的一個研究小組在1978年發明的。RSA這個名稱來自它的三個發明人的姓氏的首字母（R1vest、Shamir、Adleman）。RSA公鑰密碼算法自提出以來就受到廣泛的重視，也得到了廣泛的應用。那么，RSA公鑰密碼算法是endprint

如何構造陷門單向函數的，其安全性又如何呢7這是下次課程的學習內容。

三、教學反思

經過多次課堂教學實踐的檢驗，事實表明“以學生為主體”的啟發式教學設計有助于培養學生主動學習、主動思考、主動發現的能力，能更好地促進學生的全面發展，提高整體的教學質量與效果。啟發式教學設計以及課堂教學實踐主要體現在以下兩個方面：

（一）關注能力達成而非知識獲取

在教學設計與教學實踐中要彰顯學生的主體地位，讓學生成為學習的主人。學生在整個學習過程中不僅僅是接受知識，更要面對面、心貼心地與知識對話，從而培養自己的批判性思維和創新思維。學生在主動獲取知識的過程中培養了個人對知識的建構能力，并且在這個過程中獲得的間接經驗和直接經驗將融入他今后的學習和工作中，從而為未來的發展打下堅實的基礎。正如清華大學姚期智先生所說的那樣，“希望我們的學生能感受到學習、研究過程中面臨的挑戰與取得的突破，以及由此帶來的幸福感。唯有這樣，我們才能培養出世界最頂尖的年輕人，不管他們將來是做學問還是去創業”。研究者也希望自己的學生能體會到挑戰與突破的樂趣，從而不斷超越自我，成為真正有價值、有意義的人。

（二）以“問題解決”作為教學過程設計的主線

背包公鑰密碼體制的教學設計是以研究問題的思路為切入點的，力求尋根探源，在潛移默化之中傳授給學生基本的學術素養。同時，教師通過提出問題引出教學內容的方式，可以提高學生對教學內容的關注度。學生通過解決具體情景中的問題來達到學習目標，并內化為自我的思維方式和能力。根據調查，學生特別喜歡課堂上的互動和研討，師生和諧互動的教學模式可以激發學生的學習興趣，從而引導、促進學生獨立思考，促進學生能力的全面提升。

然而，設計科學合理的問題是師生互動課堂教學成敗的關鍵。所謂“取法乎上，僅得其中；取法乎中，僅得其下”，教師要把握好研討問題的難易程度，設計“跳起來才夠得著的蘋果”作為研討題目，這樣才可以使學生樂于接受挑戰，并積極應對挑戰。通過討論，學生能比較深入地理解課堂上涉及的概念，掌握處理實際問題的方法，培養自己解決問題的能力。但是開放式的互動課堂對教師提出了更高的要求，教師不僅要對學科思想有深刻的理解，還需具備妥善處理傳授知識的準確性與開放式研討的矛盾的能力，以及掌握課堂研究的能力，并能實現對學生自主學習能力的開發。

四、結束語

背包公鑰密碼體制是公鑰密碼體制的一個典型算法，體現了公鑰密碼學的設計思想，在密碼史上具有重要的理論意義和應用價值，也是《密碼學》課程中一個重要的教學與研究內容。“背包公鑰密碼體制”的啟發式教學設計案例，在課堂教學實踐中取得了良好的教學效果，在信息安全與密碼學教學理論與實踐方面具有一定的參考價值。

責編：清善endprint