“信息安全数学基础”案例教学
摘要:本文针对“信息安全数学基础”课程教学中存在的问题和困境,结合教学实践经验,给出几个课程教学案例,对激发学生学习兴趣,提高课程教学质量具有积极的借鉴意义。
关键词:案例教学;信息安全数学基础;密码学
在当今的信息时代,信息已成为国家的重要战略资源。信息的安全直接关系到一个国家的政治稳定、经济发展和社会进步。为加强对信息安全人才的培养,我国教育部、科技部、信息产业部、国防科工委、国家自然科学基金都把“信息安全”作为优先发展的领域。2001年以来国内已有50多所高等院校建立了信息安全本科专业,部分院校还设立了信息安全相关的硕士点、博士点。而“未来的信息战争在某种程度上是数学的战争”,数学在信息安全中占有非常重要的地位。如信息安全模型的建立、密码体制的设计、安全性证明以及对密码体制的形式化分析和密码分析,涉及数论、代数、组合数学、椭圆曲线理论等方面的知识,而这些数学知识是学生在“高等数学”、“线性代数”、“概率统计”等工科必修数学课程中没有学习过的。因此考虑到相关数学基础知识在信息安全专业学习中的重要性,绝大部分院校在各自的信息安全专业人才培养方案中都将“信息安全数学基础”课程作为一门专业必修课。[1]
1课程现状
笔者自本校2004年设立信息研究与安全本科专业以来,已连续讲授了3届本科生的“信息安全数学基础”课程,并编写了《信息安全数学基础》教材(国防工业大学出版社2009年3月出版),积累了比较丰富的授课经验,希望能与大家共享。
由于“信息安全数学基础”课程课时紧、内容多、
难度大,各个知识点之间缺少联系,是对数论、近世代数、椭圆曲线理论等数学专业知识的简单集成和压缩,理解起来比较困难。笔者在教学过程中边摸索边改进,注重数学理论的引入,介绍相关知识的实际背景和科学史实,激发学生的学习兴趣,避免学生学习的盲目性。尤其是笔者在教学过程中集中体现启发式教学的理念,大量使用案例教学,将枯燥无味的数学理论知识做成实践—理论—实践的三明治,色、香、味俱全,使学生“吃”起来津津有味,很好的调动了学生的积极性和主动性,使课堂气氛活跃,充分体现了学生的主体地位和老师的主导作用。学生不仅轻松愉悦的掌握了教材中的数学知识,还主动在课后阅读其他参考资料,收到了很好的学习效果。以下是笔者在教学过程中使用的教学案例,希望能起到抛砖引玉的作用。[2]
2教学过程中的几个案例
2.1单向函数概念教学案例
T:(幻灯片)两个朋友Alice和Bob想在晚上一起外出,但他们定不下来是去电影院还是歌剧院。于是他们达成一个通过投掷硬币来决定的协议。Alice拿着一枚硬币并对Bob说:“你选择一面,然后我来抛”。Bob选择后,Alice把硬币抛向空中。然后他们都注视硬币,看结果是哪一面朝上。如果Bob选择的那面朝上,则他就可决定要去的地方,否则由Alice决定。
作者简介:秦艳琳(1980-),女,讲师,博士研究生,研究方向为信息安全与密码学。
现在假想这两个朋友尝试在电话上执行上述协议,Alice向Bob说:“你选一面,然后我抛硬币并告诉你是否赢”。
向学生提问Bob能否接受Alice的提议?
S:(共同回答) Bob显然不会同意,因为他不能验证Alice抛掷硬币的结果,也即Alice为了达到自己的目的可以给出虚假的抛硬币结果。
T:解决上述问题的方法之一是:我们可以在这个协议中加入一个奇妙的数学函数——单向函数,把它变成一个适合在电话上工作的密码协议。
(幻灯片)单向函数f是满足以下条件的一类函数:
(I) 对任意整数x,由x计算f(x)是容易的,而给出f(x),要找出对应的原像x是不可能的,不管x是奇数还是偶数。
(II) 不可能找出一对整数(x,y),满足x≠y且f(x)=f(y)。
T:假定两个朋友已经就奇妙函数f(x)达成了一致,并一致同意用偶数x来表示“正面”,用奇数x代表“背面”,然后进行如下步骤(幻灯片):
(1)Alice选择一个大随机数x并计算f(x),然后通过电话告诉Bob f(x)的值;
(2)Bob告诉Alice自己对x的奇偶性猜测;
(3)Alice告诉Bob x的值;
(4)Bob验证f(x)并察看他所做的猜测是正确或是错误。
T:请同学结合单向函数的性质来对上述协议的有效性进行分析
S:展开小组讨论。
T:请×××同学回答。(学生回答不够全面)
T:还有没有人进行补充?(在学生补充后,给出准确的分析)。
首先,根据f具有性质II,Alice无法找到不同的两个数x和y,其中一个是奇数而另一个是偶数,使其满足f(x)=f(y)。因此,Alice一旦通过电话告诉Bob f(x)的值,她也就向Bob就x的值做出了承诺,她无法再改变x的值,也即Alice已经完成了其掷硬币过程。其次,由于f具有性质I,已知f(x),Bob不能判定出Alice所使用的x是奇数还是偶数,因而他不得不把自己的猜测(步骤2))真实的给出。之后Alice可给出x的值令Bob相信其猜测是否正确。事实上,如果Bob利用Alice告诉的x对f(x)进行计算的结果与Alice在第1步给出的结果一样,且Bob相信f所具有的性质,则Bob应该相信最终的输赢。
2.2同余式的基本概念和性质教学案例
T:由生活中的同余现象引入同余式的概念,如:5月2日是周六,5月份还有哪几天是周六?
S:(共同回答)5月9日,5月16日,5月23日,5月30日。
T:这些日期之间有什么联系呢?请×××同学回答。
S:9,16,23和30被7除了之后余数都是2。
T:很正确。我们也可以说9,16,23和30是关于模数7同余的,今天我们就来研究同余式的基本概念和性质。
T:(幻灯片)介绍同余式的基本概念和相关性质。
然后给出同余式在古典密码中的简单应用以加深学员对同余概念及性质的印象。
凯撒密码是古罗马的凯撒大帝使用过的一种密码。凯撒大帝在作战中为了防止下达给部属的命令在传送过程中被敌人截获,使用了一种加密手段:把明文字母循环右移3位后得到的密文字母。即明文字母和密文字母的对应关系如下:
A→D,B→E,C→F,D→G,E→H,F→I,G→J,H→K,I→L,J→M,K→N,L→O,M→P,N→Q,O→R,P→S,Q→T,R→U,S→V,T→W,U→X,V→Y,W→Z,X→A,Y→B,Z→C,
T:在学习了同余式的概念之后,能否用公式表达出凯撒密码的加解密算法?(提示用M表示明文字母,C表示密文字母,并分别用0～25代表A～Z)
S:部分同学将加密公式写为:C=M+3;解密公式写为:M=C-3。
T:指出上述加解密公式的错误,给出正确写法:
加密算法可表示为C≡ M+3(mod26),解密算法可表示为M≡ C-3(mod26)。
T:给出另外一个实例——仿射密码(幻灯片):
Alice与Bob进行保密通信,他们认为凯撒密码过于简单,容易被敌手破获,就采用了以下的加密手段:将每个字母对应的数字乘以k再加上b作为密文字母对应的数字。用公式表达加密算法为:
C≡ kM+b(mod26),(k,26)=1。
向学生提问为什么k必须取与26互素的整数?Bob收到密信后怎么解密?
S:这是因为只有(k,26)=1时,才存在k-1,满足k•k-1≡ 1(mod26),这样才能对C进行解密,即解密公式为
M≡ k-1C-k-1b(mod26)。
T:请学生练习k=7,b=6时,仿射密码的加密公式和解密公式的写法。
2.3欧拉函数和欧拉定理教学案例
T:Bob想通过一种比较安全的手段向Alice传送一份高密级的文件M,他们决定采取目前最流行的公钥密码算法RSA[3]。
首先,Alice执行以下步骤产生自己的公私钥对,如图1所示。
图1产生公开钥e和私钥d的过程
Bob要发给A的文件为M=(m0,m1,…,ml),mi=0或1。利用二进制,可将M表成一个整数m=m0+2m1+…+2lml。这里假设m T:大家能否说明解密公式的正确性? S:进行思考并展开讨论。 T:给出解密公式正确性的证明: 由欧拉定理可知,若(m,n)=1,有 mφ(n)≡ 1(modn), cd≡ med≡ m1-xφ(n)≡ m•(mφ(n))-x≡ m(modn)。 所以利用解密公式Alice是可以正确恢复出明文m的。 进一步提问,Alice和Bob所采用的这种加密方式安全吗?提示:假设黑客截取了密文c,他必须要 图2加密解密过程 知道d才能正确解密,那么在已知公开参数n,e的情况下能否容易的得到d?(给学生思考的时间)。然后进行解释,如图3所示。 图3RSA算法安全性分析 由公开钥e找到私钥d必须已知φ(n),而φ(n)=(p-1)(q-1),这就需要对大整数n进行素因子分解以求得p和q,只要n取的足够大(比如2048比特),对n进行分解是十分困难的。 2.4二次剩余理论教学案例 T:(幻灯片)依次介绍二次剩余的基本概念、勒让德符号及雅可比符号的定义和相关性质。最后,给出以下应用实例: Alice和Bob在认真研究了二次剩余的相关理论后,设计了一种巧妙的公钥密码算法来实现他们之间的保密通信。 首先Alice执行下列步骤产生自己的公私钥,如图4所示。 Bob和Alice按照以下幻灯片所示进行保密通信,如图5所示。 图4产生公私钥对的过程 图5保密通信过程 T:请大家思考Alice按照上述方法解密能否恢复出正确的明文? S:分小组进行讨论。 T:给出解密正确性的证明: 对于明文比特0,相应的密文为c=x2,故有 , ,因此明文比特0被加密成模n的一个二次剩余。 对于明文比特1,相应的密文为c=yx2。由于 ,故有 和 ,也即明文比特1被加密成模n的二次非剩余(尽管 )。 因为Alice知道p,q所以她可以确定ci是二次剩余还是二次非剩余,而其他人由于无法得到p,q,即使求出 ,也无法确定ci是二次剩余还是二次非剩余,因此无法正确恢复出ci对应的明文比特。 上述算法就是著名的Goldwasser-Micali密码体制。 2.5原根及离散对数教学案例 T:在介绍完原根的概念、求法以及离散对数问题之后,给出以下实例(幻灯片): Bob想通过一种安全的手段向Alice传送一份高密级的文件M,他们决定采取目前广泛应用的公钥密码算法ElGamal[4]。 首先,Alice按照以下步骤产生自己的公私钥对,如图6所示。 图6ElGamal算法的公私钥对产生过程 Bob要发给A的文件为 M=(m0,m1,…,ml),mi=0或1。 利用二进制可将M表成一个整数m=m0+2m1+…+2lml。只要p选择的足够大,可以保证m 图7ElGamal保密通信过程 请同学们思考解密算法能否恢复出正确的m。 S:因为c1=ak(modp),c2=myk(modp),y=ad(modp),故 ,即解密变换能正确地从密文恢复出相应的明文。 T:再请同学们思考这种公钥密码算法是否安全? S:是安全的。由公开密钥y求出私钥d需要求解离散对数问题,只要参数p选择的足够大,那么离散对数问题是难解的。 3结束语 本文给出了笔者在教学过程中使用的几个案例,这些案例将各个相关数学知识点有机的联系在一起, 突出了“信息安全数学基础”课程的实用性,增加了课程学习的趣味性,使学生在实际应用中理解和掌握相关数学理论,避免了单纯讲授数学知识给学生带来的枯燥感和盲目感,使学生由被动接受老师讲授的内容改为在老师的引导下主动思考,积极响应,活跃了原本沉闷的课堂气氛,收到了良好的教学效果。但在进行实际的案例教学过程中,笔者也发现由于大部分学生没有学习过“密码学”课程,因此对案例中的部分密码学术语比较陌生,这在一定程度上影响了案例教学的效果。笔者也将在今后的教学研究过程中不断改进相关案例,使其更加浅显易懂,贴近生活,充分发挥出案例教学的优势。 参考文献: [1] 余琍,徐霜. 信息安全专业人才培养模式创新思路与实践教学改革[J]. 计算机教育,2008(23):38-40. [2] 邱卫东,陈克非.信息安全数学教学的新型互动模式[J]. 计算机教育,2007(10):19-21. [3] Wenbo Mao. 现代密码学理论与实践[M]. 北京:电子工业出版社,2004. [4] Willian Stallings. 密码编码学与网络安全:原理与实践[M]. 2版. 北京:电子工业出版社,2001. (编辑:白杰)