“背包公钥密码体制”的启发式教学设计与思考

赵秀凤　关杰　李信然

摘要：启发式教学就是教师根据教学目的、教学内容、学生的知识水平和知识规律，运用各种教学手段，采用启废诱导的办法传授知识、培养能力，使学生积极主动地学习，以促进他们的身心发展的教学方法。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