ElGamal公钥密码算法的教学设计与思考

李瑞林, 冯 超, 张 琛, 唐朝京

(国防科技大学 电子科学学院， 湖南 长沙 410073)

0 引言

随着网络空间安全成为一级学科，“密码学与网络安全”课程受到高度重视[1]。该课程特有的跨学科特性使很多学生在学习过程中感觉到其知识点繁多、凌乱、不够系统，进而导致学生花相当多的时间精力死记硬背知识要点，这样做既吃力又达不到真正目的。通常来讲，我们通过一门课程的开设，希望学生能够在知识目标、能力目标和素质目标等三个方面得到提升，而知识目标作为基础，其掌握的熟练程度，直接会影响到能力目标和素质目标的实现。因此，系统梳理该课程知识体系，通过精心的教学设计，把看似凌乱的知识点进行有机组合，引导学生主动思考，培养学生学习兴趣，就成为教学过程中的重要环节。

对称密码学、非对称密码学和密码协议是“密码学与网络安全”课程的核心内容。非对称密码学(又称公钥密码学)自1976年由Diffie和Hellman提出之后，由于其颠覆式的创新理念，被视为整个密码学发展史上最伟大的一次革命[2]。因此，相关内容在“密码学与网络安全”课程教学中占有非常重要的地位。最著名也是应用最广的公钥密码算法是RSA算法，该算法是基于大整数分解这一困难问题而设计的， RSA算法的数学原理与编程实现等方面在课程的教学上占用了大量课时，使学生对该算法的掌握较为扎实。除了RSA公钥算法之外，还有另外一类公钥密码算法即ElGamal算法，它针对计算离散对数的困难性问题而设计，虽然没有RSA密码算法应用广泛，但该算法设计新颖巧妙，数学原理简单明了，为后续著名的椭圆曲线密码算法的设计提供了参考[3]。鉴于此，不少课程都将ElGamal算法作为知识点加以讲解，但知识传授仅限于对加解密公式推导的正确性验证，致使很多学生对ElGama算法为何设计成这种形式，它与Diffie-Hellman密钥交换协议之间存在什么样的关系等存在疑惑。

针对这些问题，本文提出了一种ElGamal密码算法的教学设计，充分挖掘Diffie-Hellman密钥交换协议(简称DH密钥交换协议)在该加密算法中所扮演的角色，以问题导向为牵引，引发学生对该加密算法的深入思考和深刻认识，既充分调动了他们学习“密码学与网络安全”课程的兴趣，又逐步培养了他们研究式、自主式学习的能力，最终达到更好的教学质量与效果。

1 教学过程设计

本文给出的ElGamal密码算法的教学设计包括如下四个部分：①回顾公钥密码的背景及基本概念，提出基本问题；②介绍Diffie和Hellman提出的密钥交换协议；③引导学生思考Diffie-Hellman密钥交换协议与公钥密码算法之间的关系；④启发学生分析如何将DH密钥交换协议转化为公钥密码算法，并给出ElGamal密码算法的标准定义。

1.1 教学环节一：公钥密码学背景及基本概念

教师首先引入公钥密码产生的背景：在传统的对称加密方案里，通信双方必须共享一段秘密信息(密钥)，且该密钥不能泄露给任何第三方，否则就无法保证通信的安全。随着网络与通信技术的发展，传统加密技术中涉及的密钥管理，特别是密钥分发问题成为制约对称密码大规模应用的一个主要瓶颈。在包含n个节点的通信网络中，为保障安全通信，每个节点均需要保管与其它n-1个节点共享的密钥。因此，整个网络就需要保护n*(n-1)/2个密钥，大大增加了密钥管理的负担。

为解决这一问题， Diffie(迪菲)和Hellman(赫尔曼)于1976 年在美国国家计算机大会上提出了公开密码学的思想，这项举措被后人称为密码史上最伟大的一次革命，对密码学领域的发展有重要的意义。次年，Diffie和Hellman在IEEE信息论专刊上以邀请报告的名义撰写了“密码学中的新方向”一文，系统阐述了“公钥密码学”的基本思想、核心概念及应用场景。Diffie和Hellman解决问题的出发点与传统对称密码正好相反，即能否让用户的密钥公开。为此，他们假设每个用户至少拥有两个密钥：一个用于加密，称为加密密钥，一个用于解密，称为解密密钥。加密密钥可以公开(又称为公钥)，解密密钥则必须保密(又称为私钥)，而且加密密钥的公开不会危及解密密钥的安全。这样，每个用户只需保存自己的解密密钥，从而大大降低密钥管理的成本与负担，这就是公钥密码解决问题的初衷与基本思想。那么，有什么样的方法可用于公钥密码算法的设计呢？Diffie和Hellman在文中指出了基于单向陷门函数来构造公钥密码的可能性，但遗憾的是当时他们尚未给出一个具体的公钥加密方案。但两位作者基于一类单向陷门函数(离散对数难题)设计了第一个密钥交换协议，该协议允许人们在不安全的信道上通过公开交换信息协商出安全的密钥。

1.2 教学环节二：DH密钥交换协议回顾

这一教学环节主要回顾离散对数难题，并介绍DH密钥交换协议。

1)离散对数

(1)回顾离散对数基本概念：给定素数p，存在p的本原根r，使得r,r2, …,rp-1(modp) 两两不同，且都与p互素。这表明r的各次幂模p后恰好可产生从1到p-1之间的每个整数，即{rmodp,r2modp, …,rp-1modp}={ 1,2,3, …,p-1 }。由此，离散对数可定义：任意s∈{1, 2, …,p-1}，存在唯一的i(1≤i≤p-1)，使得s≡rimodp，此时称i为模p下以r为底s的离散对数，简称i为s的离散对数。

(2)给出离散对数困难问题定义：给定素数p及其本原根r，s≡rimodp，则当p为非常大的素数时，由已知的p,r,s来求离散对数i是非常困难的事情。

2)DH密钥交换协议

DH密钥交换协议借助于离散对数困难问题，在公开信道上交换双方各自的信息从而联合建立了共享的秘密密钥，联合建立的秘密密钥由每个通信参与者分别产生的参数通过一定的计算得出，不需要任何可信第三方参与。如图1所示，假定通信双方共享大素数p及其本原根ro若一方Alice希望与通信方Bob建立安全的连接，则Alice与Bob可按照图中所示的步骤(1)(2)进行信息交互，而后在步骤(3)通过计算获得共享密钥K，后续通信双方可利用该密钥K，基于传统加密算法对通信数据进行加密。对攻击者而言，他可以截获p,r,Sa,Sb，但若想获得共享密钥K=rab的值，他还必须知道a或b的值。因此对于特殊选取的大素数p而言，由Sa和r来计算a(或由Sb和r来计算b)即计算离散对数是困难问题，由此可认为该方案协商出来的K是安全的。

图1 Diffie-Hellman密钥交换协议流程

1.3 教学环节三：DH密钥交换协议思考

这一教学环节主要引导学生对DH密钥交换协议进行思考，并启发学生思考如何将DH密钥交换协议转化为公钥密码算法。

教师可以进行提问，既然DH密钥交换协议基于离散对数困难问题，已经蕴含了公钥密码学的思想，为何当初设计者未能给出一个类似的公钥加密算法呢？由此，引导学生进行如下的思考、讨论和归纳总结：

提问一：如何定义公钥和私钥？根据图1所示，Alice可以将本次通信的随机数a视为她的私钥，而将sa=ramodp视为她的公钥，这样根据离散对数困难问题，由公钥sa来计算私钥a在计算上很困难；同理，Bob也可以产生他此次通信的公私钥对(Sb,b)。

提问二：有了公钥和私钥，如何设计加密和解密算法，满足彼此互逆这一关键问题？DH密钥交换协议的创新之处在于通过双方的公钥{Sa,Sb}联合产生了共享密钥K，很自然一个想法就是双方基于共享的密钥K利用传统的对称加密算法实现加解密功能。但是这样设计的算法不能算是公钥算法，因为里面已经掺和了经典的加密方案。那如果采用更为简洁的“一次一密”方案呢？由于每次通信产生的K都是随机的，我们完全可以利用C=K*Mmodp作为对明文M加密后得到的密文C。

归纳总结：通过对上述问题的讨论，学生们已经对DH密钥交换协议与公钥加密算法的关系有了初步的认识。此时，教师可以进一步总结提问和归纳：既然我们可以利用“一次一密”和DH交换协议来设计一个公钥加密方案原型，那么这一原型还有没有什么缺陷呢？(这里可以请学生深入思考。)教师最后总结：这个原型方案最大的不足之处在于每次加解密时，通信一方的公钥都得随机生成和传输，这非但没能减轻反而加重了密钥管理的负担，这显然是违背于公钥密码思想初衷的。因此，摆在学生面前的一个重要问题就集中在如何突破这个屏障，既能充分利用“一次一密”这一简单加解密方案，又能充分运用公钥密码简化密钥管理的思想，从而设计出一个真正实用的基于离散对数困难问题的公钥加密算法。

1.4 教学环节四： ElGamal加密算法设计

这一教学环节在前面教学环节基础之上，进一步引导学生探讨如何改造DH密钥交换协议来设计基于离散对数难题的公钥加密算法，即ElGamal加密算法。教师同时对ElGamal加密算法进行系统的解释和说明，便于学生更好地理解与掌握。

在这一环节，教师再次回顾公钥密码算法的应用场景：假设Bob要给Alice发送消息M，Bob需要先获得Alice的公钥，利用该公钥对消息M进行加密，并将密文C发送给Alice；而后Alice利用自己的私钥对密文C进行解密从而得到消息M。

紧接着，教师引导学生深入思考，在DH密钥交换协议中，Alice在每次通信前都要产生一个随机数a作为自己的私钥，将Sa=ramodp作为公钥；同理，Bob也要做类似的操作。但在公钥加密场合，能否让Alice每次都采用同样的公私钥对从而减少密钥管理负担呢？

教师抛出这个问题后，可先让学生进行简单的讨论。然后参考图2，与学生一起对DH密钥交换协议做进一步的改造与分析：

(1)假设Alice的私钥为a，公钥为Sa=ramodp，将{a,Sa}作为Alice的永久公私钥对，且Bob预先已知Alice的公钥信息Sa。因此，在图2中，第一次Alice向Bob传输信息时可以用虚线标记，表示Bob已经预先知道了Alice的公钥信息，不需要Alice再次发送；

图2 ElGamal加密算法流程

(2)Bob对应的公私钥信息是否也可以保持不变呢？经分析不可行，否则Alice和Bob每次联合产生的共享密钥K就会保持不变，这是“一次一密”所不允许的。因此，Bob需要每次产生一个随机数k，计算Sk=rkmodp，将{k,Sk}作为Bob的临时公私钥对，同时，Bob将临时公钥Sk传送给Alice；

(3)Alice和Bob都可以独立计算出共享密钥K，Bob计算法方式为K=(sa)kmodp=rakmodp，Alice计算方式为K=(sk)amodp=rkamodp；

(4)Bob依靠共享密钥K，基于“一次一密”方案对明文M加密得到密文：K* M mod p；而Alice依靠自己独立计算得出的共享密钥K就可以完成对上述密文的解密。

以上4个步骤就是基于离散对数问题的ElGamal公钥加密算法分解流程，其中，前3步就是一个完整的DH密钥交换协议过程，最后一步才是真正的加密过程。根据图2中的虚实交互箭头所示，教师进一步提示学生：Bob可以将步骤(2)(4)合并作为最终发给Alice的密文，从而给出如下ElGamal公钥加密算法的标准定义：

密钥建立过程：Alice与Bob共享一组安全参数{p,r}，p为大素数，r为p的本原根；

Alice的私钥为a，公钥为Sa=ramodp。

加密过程：Bob每次随机选取自己的临时私钥k，计算临时公钥sK=rkmodp作为密文的第一部分c1；然后查看Alice的公钥sa，计算共享密钥K=(sa)kmodp=rakmodp，进一步计算密文的第二部分c2=K*Mmodp。因此，密文C=(c1,c2)=(rkmodp, (sa)k*Mmodp)。

解密过程： Alice利用自己的私钥a和密文的第一部分c1，首先计算还原共享密钥K=(sk)amodp=rkamodp，然后利用密文的第二部分c2恢复出原始消息M=c2*K-1 modp。

根据上述流程，教师做最后总结：本次课程，我们引入临时公私钥对和永久公私钥对的概念，基于“一次一密”思想，和大家也一起经历了从DH密钥交换协议到ElGamal加密算法的改造过程，我们发现：ElGamal加密算法与DH密钥交换协议是等价的，它以预先公开sa的方式减少了一次数据交换；但该算法的缺点是“信息扩展”，即密文长度是所对应明文长度的两倍。这里，密文的第一部分是临时公钥，用于交互信息以联合共建共享密钥；第二部分才是真正的一次一密加密过程。

2 教学思考

以上教学设计，经我校2016年“密码学与网络安全”课程本科课堂教学实践，取得了良好的效果。很多学生反映对ElGamal公钥密码加密算法的原理有了非常清晰的理解和深刻的认识，为后续椭圆曲线加密算法的学习打下了扎实的基础。课程内容的讲解更加系统，前后教学知识点也更加连贯，主线突出，达到了预期目的。

通过该教学案例的设计，我们发现充分挖掘课程知识点之间的内在联系，以问题导向为牵引，引导学生对所学知识进行深入思考和主动分析，既能充分调动他们学习“密码学与网络安全”课程的兴趣，又能培养他们主动式和研究式的学习能力，最终达到更好的教学质量与效果，也更好地促进学生的全面发展。在后续的课程教学当中，我们可以更多尝试设计以“问题导向”为牵引的教学案例。

3 结语

“密码学与网络安全”课程固有的特点和难点使不少学生对其存在畏惧心理。如果学生对课程基础知识重视不够、掌握不扎实，就会导致后续缺乏熟练运用已有知识解决专业问题的能力，影响其从事深层次专业研究的创新能力。我们针对ElGamal密码算法的教学内容进行了教学案例设计，将DH密钥交换协议有机融合进来，通过问题导向的方式，激发学生的学习兴趣，引导他们逐步培养研究式和自主式学习的能力。(李瑞林等文)

[1] William Stallings 著．唐明等译．密码编码学与网络安全-原理与实践(第六版)，北京：电子工业出版社，2015.

[2] Diffie W. and Hellman M.E. New directions in cryptography. IEEE Trans. on Information Theory, 22 (6), 644-654, 1976.

[3] ElGamal T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. on Information Theory, 31(4), 469-472, 1985.