一個常數長度的無證書聚合簽名方案的攻擊與改進

摘 要：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）產生對應的私鑰，通過秘密信道發(fā)給該用戶。由于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）結合了兩種簽名方案的優(yōu)勢，在安全性和效率上有很大改進，因此成為學者關注的研究熱點。近年來，研究者們提出許多CLAS方案，Hashimoto和Ogata [5]利用在被簽名的消息上提供的相同狀態(tài)信息，提出了一個基于雙線性對的常數長度的無證書聚合簽名（CLAS）方案。常數長度的CLAS方案是該方案最終生成的聚合簽名長度與聚合者的個數無關。他們證明了該方案在隨機預言機模型下對Normal- 類敵手和Ⅱ類敵手是安全的，方案的安全性可歸約為CDH困難問題。

在本文中，我們首先證明了Hashimoto 和Ogata的方案（簡記為Hash-Ogata方案）對Super-I類敵手是不安全的。該敵手能替換公鑰，知道與替換公鑰相對應的用戶密鑰。敵手不需要知道主密鑰相關的部分私鑰，只要利用對應于替換公鑰的用戶密鑰就可以在任何消息上偽造有效的簽名。然后提出了防止這類攻擊的改進方案。

1 預備知識

本節(jié)我們首先回顧一下無證書聚合簽名的定義及困難性假設等基礎知識。

定義1 無證書聚合簽名（CLAS）方案由6個算法構成：

1）Setup算法。該算法由KGC執(zhí)行，輸入安全參數k，輸出系統(tǒng)主密鑰s系統(tǒng)參數params。

2）部分私鑰生成算法由KGC執(zhí)行，輸入params，s和用身份IDi，返回部分私鑰 。

3）用戶密鑰算法由用戶IDi執(zhí)行，輸入params，IDi和秘密值xi（xi由用戶IDi選?。?，輸出秘密值/公鑰（xi /）。

4）簽名算法由用戶IDi執(zhí)行，輸入params，，xi， 及消息mi輸出（普通）簽名σi。

5）聚合算法由聚合人執(zhí)行，輸入n個有效的身份-消息-公鑰-簽名對（IDi，mi，，σi）（1≤i≤n），輸出這n個簽名σi的聚合簽名σ。

6）驗證算法。輸入params，n個身份-消息-公鑰對（IDi，mi，）（1≤i≤n）及聚合簽名σ，輸出“1”表示簽名有效，而“0”則簽名無效。

定義2 CDH問題：設G1是循環(huán)加法群，階為安全大素數q，給定g，ag，bg ∈ G1，計算abg ∈ G1是困難的，其中" 是未知隨機數。

2 Hash-Ogata方案的回顧

Hash-Ogata方案[5]主要由以下六個算法組成：

1）Setup算法。對于給定的安全參數k，KGC執(zhí)行以下操作：設G1是加法循環(huán)群，G2是乘法循環(huán)群，階為素數q，雙線性對e：G1×G1→G2。選擇三個抗碰撞的Hash函數H1、H2、H3：{0，1}*×G1→G1。KGC隨機選擇" 作為系統(tǒng)主密鑰，隨機選取群G1的一個生成元P計算系統(tǒng)公鑰PT = sP。系統(tǒng)公開參數：

params =

2）部分私鑰生成算法。輸入系統(tǒng)公開參數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方案中，所有簽名者使用相同的狀態(tài)信息生成聚合簽名。鑒于這個特性，他們的聚合方案具有固定簽名長度，與聚合者的個數n無關。在隨機預言機模型和CDH問題假設下，他們證明了該方案對Normal-Ⅰ類敵手和Ⅱ類敵手是安全的。

3 Hash-Ogata方案的安全分析

在CLS方案中，用戶的私鑰是由KGC生成的部分私鑰和由用戶選取的秘密值組成的。根據秘密值的情況敵手可分為以下兩種類型[5]：

Ⅰ類敵手不知道系統(tǒng)主密鑰和用戶的部分私鑰，但是可以替換用戶公鑰。根據秘密值的掌握情況又細化為Normal敵手和Super敵手，Normal- 類敵手無法獲得與替換的公鑰對應的用戶秘密值，而Super- 類敵手知道該用戶與替換的公鑰對應的秘密值。在這種情況下，能夠抵抗Super敵手的攻擊就意味著即使知道用戶秘密值，如果不知道由KGC所生成的用戶部分私鑰，也是無法偽造用戶簽名的。

Ⅱ類敵手是惡意的KGC，擁有系統(tǒng)主密鑰，但是不知道用戶秘密值，不能替換用戶的公鑰。能夠抵抗這類敵手的攻擊意味著擁有主密鑰的敵手不能偽造任何用戶的任何消息簽名。

安全的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-Ogata's方案的改進

為了抵抗上述攻擊，我們在原方案的基礎上進行改進，改進方案仍由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）次雙線性對運算，雖然計算效率略占優(yōu)勢，但是我們的改進方案針對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]//ASIACCS’07.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