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

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

0 引言

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

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

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

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

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

1 無證書聚合簽名方案

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

1.1 CLAS方案框架

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

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

系統(tǒng)建立:輸入為安全參數(shù)k,輸出為主密鑰λ和系統(tǒng)參數(shù)列表params。該算法由密鑰生成中心KGC運(yùn)行。

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

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

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

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

1.2 安全模型

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

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

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

對手A1可以自適應(yīng)地進(jìn)行多項式有界次數(shù)的下列查詢操作:

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

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

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

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

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

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

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

當(dāng)且僅當(dāng)滿足下列條件時,A1贏:

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

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

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

2 CLAS方案評述

這里將對文獻(xiàn)[8]提出的CLAS方案進(jìn)行簡單的評述。

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

2.1 系統(tǒng)建立:由KGC執(zhí)行

輸入:安全參數(shù)k∈Z;

過程:

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

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

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

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

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

2.2 用戶密鑰生成:由系統(tǒng)中的每個簽名者Ui執(zhí)行

輸入:系統(tǒng)參數(shù)params和用戶身份IDi;

過程:

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

(2)計算Pi=xiP;

輸出:由Ui保護(hù)的秘密值xi和公開發(fā)布的公鑰pki=。

2.3 部分私鑰提取:KGC執(zhí)行

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

過程:

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

(2)計算Di=λQi;

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

2.4 簽名:身份為IDi的用戶執(zhí)行

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

過程:

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

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

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

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

2.5 聚合簽名

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

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

2.6 聚合驗證

輸入:n個簽名者以公鑰(pk1,…,pkn)在消息(m1,…,mn)上狀態(tài)為Δ和的聚合簽名σ=(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中成功的偽造聚合簽名。

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

(1)C運(yùn)行系統(tǒng)建立算法并輸出系統(tǒng)參數(shù)params;

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

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

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

4 小結(jié)

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