摘 要：Hashimoto和Ogata提出了一个基于双线性对的签名长度为固定常数的无证书聚合签名方案，在随机预言机模型下，证明该方案对Normal- 类敌手和Ⅱ类敌手是安全的，方案的安全性可归约为CDH困难问题。忽略了Super- 类敌手的攻击是不安全的，首先证明了该方案容易受到Super- 类敌手的攻击，并给出了抵抗这类攻击的改进方案。新方案依赖于签名者的个数，长度为n+1，双线对运算次数为2n+1，与原方案相比，虽然运算略有增加，但是安全性提升，能够抵抗所有Ⅰ类敌手和的Ⅱ类敌手的攻击。
关键词：无证书签名；聚合签名；CDH问题；Ⅰ类敌手；Ⅱ类敌手
中图分类号：TN918.4 文献标识码：A 文章编号：2096-4706（2024）08-0182-04
0 引 言
基于身份的密码体制（IBC）[1]是由Shamir在1984年首次提出的。在IBC中，每个用户拥有一个身份信息（ID）作为其公钥，并由可信第三方（TTP）产生对应的私钥，通过秘密信道发给该用户。由于TTP知道所有用户的私钥，因此该密码体制天生存在密钥托管问题。2003年，Al-Riyami和Paterson [2]提出无证书公钥密码体制（CLPKC），解决了公钥密码体制中的密钥托管问题，同时也有效地解决了证书的存储以及管理问题。在无证书签名（CLS）方案中，由半可信的第三方（Key Generation Center， KGC）利用主密钥生成与用户身份对应的部分私钥，再和用户自己秘密选择的一个值一起组合生成该用户真正的私钥。因此，签名可以通过用户公钥传输并能通过身份和用户公钥进行验证。自Al-Riyami和Paterson提出无证书公钥密码体制后，一系列CLS方案相继被提出。然而，目前大部分CLS方案的安全性是基于双线性对来设计的。与离散对数、大整数分解和RSA [3]等经典的数论问题相比，双线性对是最近二十年才引起学者们注意，还没有经历更多的密码分析[4]。
聚合签名是一种带有特殊性质的多方参与的数字签名。它可以把n个人对n个不同消息的签名聚合成一个签名，从而把对n个签名的验证简化成一次验证，大大减少了签名验证的工作量。无证书聚合签名（CLAS）是无证书公钥密码体制下的聚合签名。它能提高签名的验证效率，同时减少通信时签名的长度，无证书聚合签名方案（CLAS）结合了两种签名方案的优势，在安全性和效率上有很大改进，因此成为学者关注的研究热点。近年来，研究者们提出许多CLAS方案，Hashimoto和Ogata [5]利用在被签名的消息上提供的相同状态信息，提出了一个基于双线性对的常数长度的无证书聚合签名（CLAS）方案。常数长度的CLAS方案是该方案最终生成的聚合签名长度与聚合者的个数无关。他们证明了该方案在随机预言机模型下对Normal- 类敌手和Ⅱ类敌手是安全的，方案的安全性可归约为CDH困难问题。
在本文中，我们首先证明了Hashimoto 和Ogata的方案（简记为Hash-Ogata方案）对Super-I类敌手是不安全的。该敌手能替换公钥，知道与替换公钥相对应的用户密钥。敌手不需要知道主密钥相关的部分私钥，只要利用对应于替换公钥的用户密钥就可以在任何消息上伪造有效的签名。然后提出了防止这类攻击的改进方案。
1 预备知识
本节我们首先回顾一下无证书聚合签名的定义及困难性假设等基础知识。
定义1 无证书聚合签名（CLAS）方案由6个算法构成：
1）Setup算法。该算法由KGC执行，输入安全参数k，输出系统主密钥s系统参数params。
2）部分私钥生成算法由KGC执行，输入params，s和用身份IDi，返回部分私钥 。
3）用户密钥算法由用户IDi执行，输入params，IDi和秘密值xi（xi由用户IDi选取），输出秘密值/公钥（xi /）。
4）签名算法由用户IDi执行，输入params，，xi， 及消息mi输出（普通）签名σi。
5）聚合算法由聚合人执行，输入n个有效的身份-消息-公钥-签名对（IDi，mi，，σi）（1≤i≤n），输出这n个签名σi的聚合签名σ。
6）验证算法。输入params，n个身份-消息-公钥对（IDi，mi，）（1≤i≤n）及聚合签名σ，输出“1”表示签名有效，而“0”则签名无效。
定义2 CDH问题：设G1是循环加法群，阶为安全大素数q，给定g，ag，bg ∈ G1，计算abg ∈ G1是困难的，其中" 是未知随机数。
2 Hash-Ogata方案的回顾
Hash-Ogata方案[5]主要由以下六个算法组成：
1）Setup算法。对于给定的安全参数k，KGC执行以下操作：设G1是加法循环群，G2是乘法循环群，阶为素数q，双线性对e：G1×G1→G2。选择三个抗碰撞的Hash函数H1、H2、H3：{0，1}*×G1→G1。KGC随机选择" 作为系统主密钥，随机选取群G1的一个生成元P计算系统公钥PT = sP。系统公开参数：
params =
2）部分私钥生成算法。输入系统公开参数params和签名者的身份IDi ∈ {0，1}*，KGC计算Qi = H1（IDi）和Di = sQi，输出Di作为IDi的部分私钥。
3）用户密钥生成算法。签名者随机选择" 作为密钥，计算Pi = xiP作为公钥。
4）签名算法。给定参数params，xi，Di和消息m，签名者随机选择 ，计算：
那么σi = （Ri，Si）就是{IDi，Pi}在消息Mi上的签名。
5）聚合算法。对于{IDi，Pi}在消息Mi上的签名σi = （Ri，Si），聚合者计算 ，输出聚合签名σ = （R，S）。
6）聚合签名验证算法。对于{IDi，Pi}（i = 1，2，…，n）在消息{M1，M2，…，Mn}上的聚合签名σ = （R，S），验证者计算：Qi = H1（IDi），Vi = H2（Δ，Mi，IDi，Pi），W = H3（Δ），i = 1，2，…，n。然后检验等式是否成立。如果成立则接受该签名，否则拒绝该签名。
在Hash-Ogata方案中，所有签名者使用相同的状态信息生成聚合签名。鉴于这个特性，他们的聚合方案具有固定签名长度，与聚合者的个数n无关。在随机预言机模型和CDH问题假设下，他们证明了该方案对Normal-Ⅰ类敌手和Ⅱ类敌手是安全的。
3 Hash-Ogata方案的安全分析
在CLS方案中，用户的私钥是由KGC生成的部分私钥和由用户选取的秘密值组成的。根据秘密值的情况敌手可分为以下两种类型[5]：
Ⅰ类敌手不知道系统主密钥和用户的部分私钥，但是可以替换用户公钥。根据秘密值的掌握情况又细化为Normal敌手和Super敌手，Normal- 类敌手无法获得与替换的公钥对应的用户秘密值，而Super- 类敌手知道该用户与替换的公钥对应的秘密值。在这种情况下，能够抵抗Super敌手的攻击就意味着即使知道用户秘密值，如果不知道由KGC所生成的用户部分私钥，也是无法伪造用户签名的。
Ⅱ类敌手是恶意的KGC，拥有系统主密钥，但是不知道用户秘密值，不能替换用户的公钥。能够抵抗这类敌手的攻击意味着拥有主密钥的敌手不能伪造任何用户的任何消息签名。
安全的CLS方案意味着两种类型密钥中的一种密钥的公开不会危及完整密钥的安全。
Hashimoto 和Ogata证明，他们的方案在不考虑Super- 类敌手的情况下，对Normal- 类敌手和Ⅱ类敌手是安全的。下面我们证明Hash-Ogata方案容易受到Super- 类敌手的攻击。
令AI表示一个Super- 类敌手，AI可以访问Sign预言机，并可以获得对应于任意身份及用户公钥的任何消息的签名。AI的目标是在从未被提交给Sign预言机的新消息上伪造签名，AI的伪造过程如下：
1）AI随机选择 ，计算 ，并用" 取代Pi。
2）AI向Sign预言机请求请求{IDi，Pi}在消息Mi上签名，这里AI想要在一个新消息 （）上伪造签名。然后AI得到{IDi，Pi}在Mi上的签名σ = （R，S），这里Ri = riP，，W = H3（Δ），。
3）AI知道被替换公钥" 的秘密值 ，可以计算出Ci，这里：
其中Ci与主密钥s相关，与被签名的消息无关。
4）利用Ci的值AI就能伪造" 在新消息 （）上的签名 ，，，。
5）签名" 是有效的，它可以通过验证等式：
因为：
满足验证方程，故" 是一个有效签名。
因此，攻击者可以对" 在任何不同于Mi的消息上伪造有效的无证书签名，无须知道其部分私钥。所以他们的CLAS方案对Super- 类敌手是不安全的，是可以普遍伪造的。至此我们已经证明，Hash-Ogata方案容易受到Super- 类敌手的攻击，即知道与替换的公钥" 对应的密钥 ，就可以伪造" 任意消息的有效的无证书签名，而且不需要知道与主密钥相关的部分私钥。
我们攻击的一个关键漏洞是对手可以计算Ci = Di + riW的值。因为Ci的值是与被签名的消息无关，使得敌手可以利用Ci对" 的任何消息伪造有效的无证书签名。将依赖被签名消息的哈希（Hash）值与对应部分私钥Di的Ri值相乘就可以防止我们的攻击。
在安全模型中，对于Normal型的敌手，如果相应的公钥已被替换，Sign预言机就无法输出对应于替换公钥的签名，则输出⊥。但是对于Super型的敌手，无论用户IDi对应的公钥是否被替换，Sign预言机都能输出有效签名。因此，Super- 类敌手可以从Sign预言机获取替换公钥的消息签名，这使得我们的攻击能够成功。
4 Hash-Ogatas方案的改进
为了抵抗上述攻击，我们在原方案的基础上进行改进，改进方案仍由6个算法构成，其中部分私钥生成算法和用户密钥生成算法与原方案对应算法相同，下面只给出不同的算法。
1）Setup算法。与原方案的Setup算法相同，只是额外需要KGC选择一个安全的Hash函数H4：，KGC公开参数：
params =
2）签名算法。给定参数params，xi，Di和消息m，签名者选择随机数 ，计算：
那么σi = （Ri，Si）就是{IDi，Pi}在消息Mi上的签名。
3）聚合算法。计算 ，然后输出聚合签名σ = （R1，…，Rn，S）。
4）聚合签名验证算法。对于{IDi，Pi}（i = 1，2，…，n）在消息{M1，M2，…，Mn}上的聚合签名σ = （R1，…，Rn，S），验证者计算：
，（i = 1，2，…，n）
然后检验等式：
是否成立。如果成立则接受该签名，否则拒绝该签名。
将Hash值hi = H4（Δ，Mi，IDi，Pi，Ri）乘以部分私钥Di就可以抵抗我们的攻击。这是因为攻击者虽然可以计算Ci = hiDi + xiVi，但不能使用该值在不同于Mi的消息上伪造签名。如果不能获得Hash函数H4的输入值Ri，我们的攻击仍然可以通过操纵Ri值而起作用。
我们的改进方案依赖于单个的Ri值而不是Ri值的总和 （i = 1，2，…，n）。因此，改进的CLAS方案的签名长度不是固定常数，即聚合签名的长度取决于签名者的数量是（n + 1），聚合签名的验证需要进行（2n + 1）次双线性对运算。原始方案中签名的验证需要进行（n + 2）次双线性对运算，虽然计算效率略占优势，但是我们的改进方案针对Super- 类敌手是安全的，填补了原方案的安全漏洞。
5 结 论
文中证明了Hash-Ogata方案易受Super- 类敌手的攻击，敌手不需要知道主密钥相关的部分私钥，只要利用与替换公钥相应的用户密钥就可以在任何消息上伪造有效的无证书签名。该聚合签名方案的主要思想是构造固定的签名长度，这就产生了容易受到Super- 类敌手攻击的漏洞。我们提出的改进方案在计算效率上略有劣势，但是在安全性上有提升，能够抵抗原方案忽略的Super- 类敌手的攻击。在不增加公钥大小、配对计算和标量乘法以及其他因素的情况下，设计一个紧凑的CLAS方案仍然是一个公开问题，有待今后进一步研究。
参考文献：
[1] AL-RIYAMI S S，PATERSON K G. Certificateless public key cryptography[C]//Advances in Cryptography-Asiacrypt 2003.Springer-Verlag，2003：452–473.
[2] AU M H，CHEN J，LIU J K，et al. Malicious KGC attacks in certificateless cryptography [C]//ASIACCS07.ACM，2007：302–311.
[3] HASHIMOTO K，OGATA W. Unrestricted and compact certificateless aggregate signature scheme[J].Inf. Sci，2019，487：97–114.
[4] BELLARE M，NEVEN G. Identity-based multi-signatures from RSA [C]//CT-RSA 2007.Springer-Verlag，2006：145-162.
[5] 刘莉，金正平.一个基于RSA的无证书多重签名方案 [J].四川大学学报：工程科学版，2016，48（2）：162-168.
作者简介：刘莉（1980—），女，汉族，安徽宿州人，副教授，硕士，主要研究方向：数论及其应用、密码学、数学建模。
收稿日期：2023-09-20
基金项目：安徽省高等学校自然科学研究重点项目（KJ2020A1107，KJ2021A1523）；安徽省质量工程项目（2020kfkc158）
DOI：10.19850/j.cnki.2096-4706.2024.08.039
Attack and Improvement on a Certificateless Aggregate Signature Scheme with Constant Length
LIU Li
（Department of Public Basic Teaching， Anhui Technical College of Mechanical and Electrical Engineering， Wuhu 241002， China）
Abstract： Hashimoto and Ogata propose a certificateless aggregate signature scheme with a fixed signature length based on bilinear pairings. The safety of the protocol can be attributed to the CDH difficulty problem， and it is proved that the scheme is safe for the Normal- and Ⅱ adversaries in the random oracle model. It is unsafe to ignore the attack of Super- adversary. Firstly， it is proved that this scheme is vulnerable to the attack of Super-I adversary， and an improved scheme to resist this attack is given. The new scheme depends on the number of signers， the length is n+1， and the number of operations of the bilinear pairings is 2n+1. Compared with the original scheme， although the operation is slightly increased， the security is enhanced， and it can resist the attacks of all Class" and Class Ⅱ adversaries.
Keywords： certificateless signature; aggregate signature; CDH problem; Class Ⅰ adversary; Class Ⅱ adversary
