导弹业务是航空导弹装备管理中的一项重要的经常性工作，覆盖了航空导弹的管理、维护、使用、运输等多个方面，其中涉及到需要登记记录的数据项多，数据量较大。目前大多数部队仍然采用的是传统手工纸质登记的形式进行导弹业务的记录工作，然而这种工作方式效率低下，记录的过程中会由于记录人的疏忽出现各种各样的错误，同时在登记过程中还可能存在着责任人不明确、签字代签等情况，在需要进行检查追责时比较困难。
数字签名技术是信息与数据安全的核心技术之一，可以实现身份认证、数据完整性保护、防篡改、防冒充和不可否认性等数据传输中的重要需求。自从Diffie和Hellman提出公钥密码思想后[1]，便出现了基于公钥密码学的数字签名技术。发展至今已经产生了基于离散对数的签名、基于椭圆曲线的签名[2]、基于身份识别协议的签名[3]、盲签名[4]、代理签名[5]、多重数字签名[6]、环签名[7]等签名方案，随着大数据时代的到来，数字签名技术将会发挥更为重要的作用。
ElGamal算法是一种非确定的基于离散对数的数字签名算法，使用较为广泛[8]。本文针对导弹数据记录、存储及使用现状，在对原ElGamal算法进行了安全性和执行效率改进的基础上，将改进的ElGamal算法应用于开发的导弹业务数字化登记系统中。
1 数字签名技术与ElGamal算法
1.1 数字签名技术
在公钥密码体制中，用户的密钥是由公钥和私钥组成的密钥对，私钥秘密保存，公钥公开。由于公钥不能推出私钥，因此公开公钥不会损害私钥额安全，数字签名就是签名方用自己的私钥对某消息进行加密，验证方如果能够利用签名方的公钥正确解密，则确定该消息是签名方进行了数字签名[9]。一般来说，数字签名方案是由一个5元组(M,S,K,SIGN,VRFY)构成的，且满足以下条件：
1) M是一个可能消息的有限集。
2) S是一个可能签名的有限集。
3) 密钥空间K是一个可能密钥的有限集。
4) 对每一个k=(ks,kv)∈K都对应一个签名算法Signks∈SIGN和验证算法Vrfykv∈VRFY。每一个Signks：M→S和验证函数Vrfykv：M×S→{True,False}是一个对任何消息m∈M和任意签名s∈S满足下列方程的函数：
(1)
1.2 基于离散对数的ElGamal数字签名算法
基于数学难题的分类，数字签名算法可以分为基于离散对数问题的数字签名算法、基于大整数素数因子分解的签名算法、基于椭圆曲线离散对数问题的签名算法和基于二次剩余问题的签名算法[10]。ElGamal算法属于基于离散对数问题的签名算法，主要包括参数与密钥生成、签名算法以及验证算法三部分[11]。
设P是一个大素数，并且在Zp中求解离散对数困难。然后选一个生成元
和随机数
计算：
y=gxmod P
(2)
则公钥为(y,g,P)，私钥为x。
假设需要进行签名的消息为M，签名者选择秘密随机数
计算：
r=gkmod P
(3)
s=(h(m)-xr)k-1mod (P-1)
(4)
则对M的签名为(s,r)，其中h是Hash函数。
签名的接收者拥有公钥(y,g,P)，收到消息M的签名(s,r)之后，首先计算h(m)，然后验证：
yrrs≡gh(m)mod (P)
(5)
如果式(5)成立，则数字签名有效，否则签名无效。
对ElGamal数字签名算法验证签名的正确性证明如下：
首先对式(4)进行变形，可以得到：
ks≡(h(m)-xr)mod (P-1)
(6)
即：
ks≡λ(P-1)+(h(m)-xr)
(7)
于是有：
gks=gλ(P-1)+(h(m)-xr)
(8)
根据欧拉定理gP-1(mod p)≡1可得：
gλ(P-1)≡(gP-1)λ(mod P)≡1(mod P)
(9)
所以有：
gks≡g(h(m)-xr)(mod P)
(10)
又
y≡gx(mod P)
(11)
因此有：
yrrs≡gxrgks≡gxrg(h(m)-xr)(mod P)≡
gh(m)(mod P)
(12)
以上过程即可验证签名，如果式(5)成立，则该数字签名有效。
2 ElGamal数字签名算法的改进及其分析
2.1 ElGamal算法的改进
从签名的安全性方面分析，通过前文对ElGamal数字签名算法的描述可以看出，该算法的安全性很大程度上是依赖于选择随机数。不同的随机数会产生不同的数字签名，给攻击行为带来很大的难度。同时攻击者对ElGamal算法的攻击目标大多都是随机数，因为对密钥的攻击难度更大，而随机数与密钥的关联性较小，攻击容易实现。因此随机数选取是该算法安全性的重要保证。同时式(4)中的Hash函数也能从很大程度上保证签名不易被破解，而原始ElGamal数字签名算法中的Hash函数的输入只有签名消息的明文，如果明文泄露则Hash函数将不存在安全保护能力，因此对Hash函数增加数据的数据量也能够从一定程度上提高抗攻击能力。在保证签名验证正确性的前提下，改进的思路主要有两点：通过改进随机数的选取以及增加Hash函数输入的数据，使原算法具有更高的安全性；通过对求逆运算的改进以及改变公钥生成方式使原算法的执行效率提高。
2.1.1 安全性改进
提高安全性方面的具体改进方案如下：在原先已经选择了一个随机数k的基础上，再选择一个随机数n。在签名过程中，在已有签名公式(3)的基础上，增加一个关于随机数n的签名公式：
t=gnmod P
(13)
在增加了式(13)的基础上，再将私钥x与消息明文m一起作为Hash函数的输入，则式(4)变为：
s=(h(m‖y)-xr-xt)n-1mod (P-1)
(14)
验证方程为：
yrrtts≡gh(m‖y)mod (P)
(15)
2.1.2 签名效率改进
从签名效率上分析，式(14)中的求逆运算通常需要在计算机中通过扩展的欧几里得算法来实现的，计算过程复杂。具体改进方案如下：
将h(m)作为私钥，将公钥生成式(2)改为：
e=gh(m)mod P
(16)
此时公钥为e，并且仍然保留式(2)，将其作为下一步模逆运算改进的中间过程。
去除签名方程(式(14))中签名s与模逆运算的关联性，将式(14)变为：
s=(t+nr+h(m))mod (P-1)
(17)
同时再增加一个签名方程：
λ=(k-nr-xy)mod (P-1)
(18)
新增加的式(18)的作用是代替式(14)中签名s的模逆运算的相关性。最终得到的数字签名为(r,s,y,λ)。
再根据式(17)、(18)，将验证方程改为：
gβmod P≡remod P
(19)
其中，
β=(s-t+xy+λ)
(20)
得到的改进ElGamal数字签名算法的公钥生成方程为式(16)，签名方程为式(2)、(3)、(13)、(17)、(18)，验证方程为式(19)。
2.2 改进ElGamal算法的正确性分析
本文提出的改进ElGamal算法正确性验证过程如下：
由式(19)与式(20)，可以有：
gβmod P≡g(s-t+xy+λ)mod P
(21)
假设签名正确，即签名方程式(17)成立。由式(17)、(18)与式(21)可得：
gβmod P≡g(t+nr+h(m)-t+xy-nr-xy)mod P≡
g(h(m)+k)mod P
(22)
最后由式(3)、式(16)、式(22)可以得到：
gβmod P≡gh(m)gkmod P≡remod P
(23)
得到的等式(23)与验证方程式(19)一致，证明改进ElGamal算法能够正确地验证合法数字签名。
2.3 改进ElGamal算法的安全性分析
对数字签名算法的攻击主要有直接攻击私钥和伪造签名两种攻击方式。本文通过攻击者的各种攻击方式模拟进行安全性分析。
若攻击者想要从公钥中直接解出私钥，则根据公钥生成式(16)可知，要解出私钥就需要求解h(m)=logge的离散对数问题，解决难度很大。
若攻击者截获了签名组(x,y,r,t,s,λ)，想要根据签名组求出私钥，则根据签名公式(17)、(18)可知，攻击者需要从这两个方程中解出三个未知数(n,k,h(m))，求解难度很大，无法求得私钥。
若攻击者截获了发送的签名消息，想要通过替换消息的方式进行签名伪造，在公、私钥安全的前提下，根据式(17)可知，签名时加入了真实消息的Hash函数值，而Hash函数的一个重要特性是：难以找出两条Hash值相同的消息，即强抗碰撞性，因此被替换的消息除非与原消息完全一致，否则得不到与原签名一致的数字签名。
若攻击者截获了发送的签名消息，想要通过替换随机数的方式进行签名伪造，假设攻击者用w替换了随机数k，则根据式(3)可以得到rw，再由公式(17)、(18)可知，还需要由这两个方程解出4个未知数才能进行签名的伪造，因此攻击者得到的签名是无效的，在验证过程中会被拒绝。
根据安全性分析也可以得知，改进ElGamal算法中的随机数k和n是保证算法安全性的重要手段，因此在选取时必须要保证gcd(k,n)=1，并且存储时必须秘密存储，不能泄露。
2.4 改进ElGamal算法的计算复杂性分析
使用Visual C#语言对原始ElGamal算法进行实现，运行环境为CPU Intel Core i7-6700HQ 2.60 GHz，Windows7 SP1，Visual Studio 2012。使用Stopwatch方法统计各种运算的耗时占比，统计结果如表1所示。
表1 ElGamal算法运算耗时占比 %
运算类型耗时占比运算类型耗时占比指数运算4.6点积运算1.1模逆运算63.6Hash运算30.7
原始ElGamal算法涉及到的各类运算次数如表2所示，本文提出的改进ElGamal算法涉及到的各类运算次数如表3所示。
表2 原始ElGamal算法运算类型及次数
公钥生成签名验证总计指数运算次数1135模逆运算次数0101点积运算次数0112Hash运算次数0112
表3 改进ElGamal算法运算类型及次数
公钥生成签名验证总计指数运算次数1315模逆运算次数0000点积运算次数0224Hash运算次数1001
根据表2与表3的对比，两种方案都使用了5次指数运算。改进ElGamal算法中模逆运算次数为0，根据表1可知，模逆运算是四种运算中耗时最长的运算，因此降低模逆运算次数可以有效提高算法执行效率；改进ElGamal算法比原算法多用了两次点积运算，点积运算是一种非常快的运算，根据表1中可知点积运算耗时占比仅为1.1%，同时还减少了一次Hash运算，因此本文改进ElGamal算法计算复杂性低于原始ElGamal算法。
3 改进的ElGamal数字签名算法在航空导弹数字化登记中的应用
使用Visual C#语言进行某型航空导弹业务数据数字化登统计系统的开发，并应用基于本文提出的改进ElGamal算法的数字签名技术。开发完成后的具体界面如图1所示(数据仅供系统演示使用，涉密数据已隐去)。
图1 数字化登统计系统数字签名界面
在完成某型导弹的数据登记后进行数字签名，使用该用户自己的公钥(即个人签名密钥)对本次录入的数据进行数字签名，查询时可以通过认证该数字签名来验证数据录入人员的身份。
4 结论
本文提出了一种改进的ElGamal数字签名算法，对改进ElGamal算法的正确性、安全性以及复杂度进行了分析，并将基于该算法的数字签名技术应用于导弹数据数字化登记系统中；分析结果表明改进的ElGamal数字签名算法相比于原算法，具有更强的抗攻击性以及更低的运算复杂度，在导弹数据数字化登记系统中取得了较好的应用效果。为下一步将数据签名技术应用于其他部队日常业务工作中提供了理论与实践基础。
[1] DIFFIE W,HELLMAN M.New direction in cryptography[J].IEEE Transaction on Information Theory,1976,22(6):644-654.
[2] 徐紫枫,曾康,周福才.基于时间释放加密和数字签名的匿名电子投票方案[J].计算机应用与软件,2016,33(12):325-328.
[3] 曹阳.基于身份的ElGamal多重数字签名方案[J].科技通报,2015,31(5):197-199.
[4] 赵振国.可证安全的无证书部分盲签名机制[J].电子科技大学学报,2016,45(5):812-818.
[5] 葛丽霞,李虓,何明星,等.一个改进的无证书代理签名方案[J].计算机工程与应用,2017,53(8):92-94.
[6] 张键红,肖晗,王继林.高效的基于身份RSA多重数字签名[J].小型微型计算机系统,2018,39(9):1978-1981.
[7] 贾小英,何德彪,许芷岩,等.格上高效的基于身份的环签名体制[J].密码学报,2017(4):392-404.
[8] 李丽娟,郭亚杰.一种改进的ElGamal数字签名方案[J].计算机工程与科学,2016,38(6):1097-1102.
[9] 杜红珍.数字签名技术的若干问题研究[D].北京：北京邮电大学,2009.
[10] 郑东,赵庆兰,张应辉.密码学综述[J].西安邮电大学学报,2013,18(6):1-10.
[11] ELGAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Trans information Theory,1985,31(4):469-472.