無證書聚合簽名方案的分析*

(三亞學院信息與智能工程學院,海南三亞 572000)

0 引言

2003年Al-Riyami和Paterson第一次提出無證書密碼[1]。該方法可以作為解決傳統公鑰基礎設施(Public Key Infrastructure,PKI)和基于身份的公鑰密碼(identity-based Public Key Cryptography,ID-PKC)問題的中間方案。傳統的PK I需要一個可信機構來將實體的身份與其公鑰綁定,而ID-PKC需要一個可信的私鑰生成器(Private Key Generator,PKG)來根據用戶身份生成用戶的私鑰。因此,在基于身份的密碼中,公鑰設置的證書管理問題實際上被密鑰托管問題所取代。

在無證書公鑰密碼體制(Certificateless Public Key Cryptography,CL-PKC)中,仍然使用第三方密鑰生成中心(Key Generation Center,KGC)來幫助用戶生成私鑰[2-4]。然而,KGC 不能訪問用戶自己選擇的秘密信息和從KGC接收的部分私鑰生成的最終私鑰。KGC 使用一個稱為主密鑰的秘密值產生部分私鑰。用戶的公鑰由用戶根據自己選擇的秘密信息和KGC 的公共參數計算出來,并由用戶自己發布。

無證書密碼提出來以后,出現了很多基于無證書環境的密碼方案。無證書密碼體制的安全性也備受關注。無證書環境下的敵手模型主要包括兩種類型的對手。I類對手A1無權訪問主密鑰,但可以訪問任何實體的秘密值,并可以用另一個值替換其公鑰;II類對手A2可以訪問主密鑰,但無法執行公鑰替換。

2003年,Boneh等人提出了聚合簽名的概念[5]。聚合簽名方案是一種數字簽名方案,它允許將n個不同的簽名者在n個不同消息上產生的簽名聚合為單個簽名。發送和驗證聚合簽名分別需要較少的通信和計算開銷。這樣就產生了很多無證書聚合簽名[6-8](Certificateless Aggregate Signature,CLAS)。在大多數的CLAS方案中,配對操作(這是基于配對的密碼方案中常用的最耗時的操作)的數量和聚合簽名的大小隨著簽名者的數量線性增長。在文獻[8]中,Nie等人提出了一個有效的CLAS方案,其中聚合簽名的長度和在聚合簽名驗證過程中執行的配對操作的數量都不取決于簽名者的數量。

文獻[8]聲稱他們的聚合簽名方案在隨機預言模型中對自適應選擇消息攻擊是存在不可偽造的,并試圖在包含上述兩種對抗類型CLAS 方案的標準安全模型中證明這一點。在本文中,我們根據該安全模型證明了Nie等人的CLAS方案是不安全的,即它對于無證書密碼學中的I型對手不存在不可偽造性。更具體地說,我們證明了A1可以通過獲得一對消息和該簽名者的相應簽名,可以在任何消息上偽造任何簽名者的簽名。

1 無證書聚合簽名方案

在本節中,提供了CLAS方案的框架及其安全性定義。

1.1 CLAS方案框架

假設KGC是密鑰生成中心,U1、U2、……Un表示n個參與者,其身份標識分別為ID1、ID2、……、IDn。

一個CLAS方案由六個算法(algorithm)組成:系統建立、用戶密鑰生成、部分私鑰提取、簽名、聚合簽名和聚合驗證。

系統建立:輸入為安全參數k,輸出為主密鑰λ和系統參數列表params。該算法由密鑰生成中心KGC運行。

用戶密鑰生成:輸入為系統參數params和用戶身份IDi,生成用戶公鑰/密鑰對(xi,pki)。該算法由系統中得每個用戶運行。

部分私鑰提取:輸入為主密鑰λ、系統參數params和用戶Ui的身份標IDi∈{0,1}*;生成一個部分私鑰Di。該算法由KGC對每個用戶運行一次,并假設通過安全信道將Di安全地發送給對應的用戶。

簽名:由身份為IDi的簽名者Ui運行,輸入為系統參數params、兩個狀態信息Δ和、消息mi∈{0,1}*以及Ui的私鑰(Di,xi),輸出為簽名σi。

聚合簽名:輸入為用戶U1、U2、……、Un生成的n 個簽名σ1、σ2、……、σn,輸出為消息(m1、m2、……、mn)的聚合簽名σ。

1.2 安全模型

在無證書環境下,對抗模型由兩種類型的對手組成。I型對手A1沒有訪問主密鑰權限,但可以訪問任何實體的密鑰值并用另一個值替換其公鑰;II型對手A2可以訪問主密鑰,但無法執行公鑰替換。

CLAS方案的安全性是通過挑戰者C和對手A1或對手A2之間的兩次攻擊游戲來建模的。我們的目的是證明文獻[8]的CLAS方案沒有提供針對I型對手A1所需的安全性。這里僅介紹包含A1的游戲1,定義如下:

C通過輸入一個安全參數k,運行系統建立算法,得到系統參數params和主密鑰λ;然后C將params發送給對手A1,同時保留主密鑰λ。

對手A1可以自適應地進行多項式有界次數的下列查詢操作:

(1)哈希查詢:輸入消息的時候,由C返回對應的哈希值。

(2)部分私鑰提取查詢:在輸入簽名者Ui的身份IDi時,C運行部分私鑰提取算法生成Di并輸出。

(3)公鑰查詢:輸入用戶Ui的身份IDi后,C通過運行用戶密鑰生成算法返回相應的公鑰pki。

(4)秘密值查詢:輸入用戶Ui的身份IDi時,如果Ui的公鑰沒有被替換則C返回秘密值xi,否則返回⊥。

(5)公鑰替換查詢:輸入用戶Ui的身份IDi和公鑰pki’后,C用新的接收值替換用戶Ui的公鑰,并記錄此替換。

(6)簽名查詢:在輸入用戶Ui身份、消息mi和狀態信息Δ和時,C通過運行簽名算法以響應對應的簽名σi。

·A1輸出一個元組(m*,Δ*,,ID*,σ*),其中Δ*和是狀態信息,m*=(m*1,m*2,…,m*n),ID*=(ID*1,ID*2,…,ID*n),σ*是聚合簽名。

當且僅當滿足下列條件時,A1贏:

(1)σ*是用戶身份ID*=(ID*1,ID*2,…,ID*n)、狀態信息為Δ*和、對應公鑰為(pk*1,pk*2,…,pk*n)的消息m*上的有效聚合簽名;

(2)在部分私鑰查詢中至少有一個身份(假設為ID*1∈ID*)沒有被查詢到,且在簽名查詢中未查詢到(Δ*,,m*1,ID*1,)。

定義1:如果對手A1不能在概率多項式時間以不可忽視的優勢贏得游戲I,那么該CLAS方案是類型I安全的。

2 CLAS方案評述

這里將對文獻[8]提出的CLAS方案進行簡單的評述。

假設KGC 是密鑰生成中心,U1、U2、……、Un表示一組參與者。該CLAS 方案包含下述算法:

2.1 系統建立:由KGC執行

輸入:安全參數k∈Z;

過程:

(1)在生成器P上生成的素數階q≥2k的橢圓曲線上選取一個循環加群G1;

(2)選擇具有相同階數和雙線性映射e:G1×G1→G2的循環乘法群G2;

(3)選擇加密哈希函數:H1:{0,1}*×G1→G1,H2:{0,1}*→G1,H3:{0,1}*×G1→Z*q;

(4)選擇一個隨機數λ∈Zq并計算Ppub=λP。

輸出:KGC保護的主密鑰λ和發布的系統參數params=(q,G1,G2,e,P,Ppub,H1,H2,H3)。

2.2 用戶密鑰生成:由系統中的每個簽名者Ui執行

輸入:系統參數params和用戶身份IDi;

過程:

(1)選擇一個隨機值xi∈Z*q作為該用戶的秘密值;

(2)計算Pi=xiP;

輸出:由Ui保護的秘密值xi和公開發布的公鑰pki=。

2.3 部分私鑰提取:KGC執行

輸入:系統參數params、主密鑰λ、用戶身份IDi∈{0,1}*及其公鑰Pi;

過程:

(1)計算Qi=H1(IDi||Pi);

(2)計算Di=λQi;

輸出:安全地發送給身份為IDi的用戶的部分私鑰Di。

2.4 簽名:身份為IDi的用戶執行

輸入:系統參數params、任意消息mi∈{0,1}*、狀態信息Δ和和簽名者Ui’的秘密值xi、部分私鑰Di以及其公鑰pki;

過程:

(1)選擇一個隨機的ri∈Z*q并計算Ri=riP;

(2)計算W=H2(Δ),

(3)計算Si=Di+hixiW+(xi+ri)T

輸出:Ui’在消息mi的簽名σi=(Ri,Si)

2.5 聚合簽名

輸入:系統參數params、n個不同簽名者的n個簽名(R1,S1),…,(Rn,Sn);

輸出:聚合簽名σ=(R,S)。

2.6 聚合驗證

輸入:n個簽名者以公鑰(pk1,…,pkn)在消息(m1,…,mn)上狀態為Δ和的聚合簽名σ=(R,S)

過程:

(1)計算W=H2(Δ),T=H3();

(2)對于i=1,…,n,計算Qi=H1(IDi||Pi),hi=H3(mi||IDi||Δ||||Pi);

(3)驗證e(S,P)=e(∑ni=1Qi,Ppub)e(∑ni=1hiPi,W)e(R+∑ni=1Pi,T)

輸出:如果(3)的等式成立返回True,否則為False。

3 密碼分析

定理1:在[8]的方案在定義1的意義上是不安全的,即類型I對手可以在游戲1中成功的偽造聚合簽名。

證明:為了簡單起見,先假設n=1。設簽名者U,其公鑰為pk=,使用該CLAS方案。為了在狀態信息Δ和下代表U在消息m’生成有效的偽造簽名σ’,A1在游戲1中針對挑戰者C 采取如下行動:

(1)C運行系統建立算法并輸出系統參數params;

(3)以U的身份ID進行秘密值查詢,獲取輸出x;

(4)計算S’=S-hxW,其中W=H2(Δ),h=H3(m||ID||Δ||||PU);

如上所述,只是考慮到一個簽名者的情況。偽造的過程很容易推廣到一般情況:首先偽造一個簽名人的簽名,然后在聚合簽名中用原始簽名替換偽造簽名。

4 小結

本文研究了最近提出的一個無證書聚合簽名方案的安全性,并證明了該方案對于無證書密碼學中的I型對手不存在不可偽造性。更具體地說,我們證明了A1可以通過獲得一對消息和該簽名者的相應簽名,可以在任何消息上偽造任何簽名者的簽名。