付竟芝，斯桃枝，周振江

（1. 南京人口管理干部學(xué)院信息科學(xué)系，南京 210042；2. 上海第二工業(yè)大學(xué)計算機與信息學(xué)院，上海 201209）

一個前向安全的結(jié)構(gòu)化多重簽名方案

付竟芝1，斯桃枝2，周振江1

（1. 南京人口管理干部學(xué)院信息科學(xué)系，南京 210042；2. 上海第二工業(yè)大學(xué)計算機與信息學(xué)院，上海 201209）

基于有限域上計算離散對數(shù)的困難性，將前向安全的概念引入到結(jié)構(gòu)化簽名方案中，提出了一個新的具有前向安全性質(zhì)的結(jié)構(gòu)化簽名方案。該方案同時具有一般結(jié)構(gòu)化簽名和前向安全簽名的特點。

前向安全；數(shù)字簽名；結(jié)構(gòu)化數(shù)字簽名

0 引言

結(jié)構(gòu)化數(shù)字簽名[1-2]是一種特殊的多重數(shù)字簽名，即在簽名的過程中每個簽名成員必須按照預(yù)先規(guī)定好的順序簽名，簽名的順序是固定不變的。完成多重數(shù)字簽名的全體成員構(gòu)成了一個群組。成員簽名的順序稱為群組的結(jié)構(gòu)，群組的結(jié)構(gòu)有順序結(jié)構(gòu)、并行結(jié)構(gòu)和混合結(jié)構(gòu)。順序結(jié)構(gòu)是指在簽名時，群組中的成員按照順序方式執(zhí)行簽名；而并行結(jié)構(gòu)是指群組成員可以按任意順序執(zhí)行簽名協(xié)議；混合結(jié)構(gòu)是將以上兩種結(jié)構(gòu)混合而得到的群組結(jié)構(gòu)。結(jié)構(gòu)化簽名的產(chǎn)生和驗證都依賴于群組的結(jié)構(gòu)，如果成員不按照指定的結(jié)構(gòu)進行簽名，就不會得到有效的簽名。一個簽名的前向安全性是將簽名的有效時間分割成多個簽名周期，在每個簽名周期開始時，群組的全體成員同時使用密鑰更新算法產(chǎn)生新周期的簽名密鑰，而驗證簽名的公鑰在整個有效時間內(nèi)都不改變。當(dāng)?shù)趈個周期的密鑰暴露時，前向安全的簽名方案能夠保證前面的j ?1個周期內(nèi)的簽名的有效性。實現(xiàn)前向安全性主要是依賴求模大素數(shù)乘積的平方根難題，依據(jù)該難題設(shè)計出了許多具有前向安全性的簽名方案[4-6]。本文將前向安全性的概念引入到結(jié)構(gòu)化多重簽名中，提出了一個ELGamal類型的前向安全的結(jié)構(gòu)化簽名方案。該方案不僅實現(xiàn)了結(jié)構(gòu)化簽名，而且也滿足了簽名前向安全的特性。

1 ELGamal類型的前向安全的結(jié)構(gòu)化簽名方案

假設(shè)群組G由n個成員組成，G = {P1, P2,…, Pn}。群組G的結(jié)構(gòu)是順序結(jié)構(gòu)，是指成員簽名的順序為順序方式簽名，即P1→P2→P3→…→Pn；群組G為并行結(jié)構(gòu)是指P1, P2,…, Pn可以按任意順序完成簽名；群組G為混合結(jié)構(gòu)則是指有部分成員是并行結(jié)構(gòu)，其它成員構(gòu)成順序結(jié)構(gòu)。

1.1 系統(tǒng)參數(shù)

選擇三個大素數(shù)p, p1和p2, 使得p = 2p1p2?1, 令N = p1p2, g是Zp的生成元,是安全的單向Hash函數(shù)。簽名密鑰的有效期分為T個時間段，即1, 2,…, T。

1.2 順序結(jié)構(gòu)時成員Pi(i=1,2,…, n) 和群組的公鑰和私鑰產(chǎn)生

Pi(i = 1, 2,…, n) 隨機選取作為他的初始私鑰，其公鑰yi的計算為

1.3 順序結(jié)構(gòu)時成員Pi的簽名私鑰更新算法

第j+1個周期的簽名密鑰由以下公式計算得到

1.4 順序結(jié)構(gòu)簽名的生成

群組中的成員Pi(i = 1, 2,…, n)，隨機取一個數(shù)ki，并計算r=(y)kimodp( i=1,2,…,n)，其中y=g，

ii+1n+1并在群組中廣播ri。當(dāng)群組中的每個成員收到全部的ri后，計算R=r1r2…rnmodp 和Y=H( M, j, R)，其中M是簽名消息，j是周期數(shù)。再按P1→P2→P3→…→Pn的順序計算si(i=1,2,…,n)

其中0sY=。當(dāng)Pi(i = 1, 2,…, n)在計算si之前可以通過如下驗證方程來驗證si?1的有效性

如果驗證方程不成立，Pi終止簽名；如果驗證方程成立，則說明si?1是正確的。則群組的簽名為(R, s)，其中s=sn。

1.5 順序結(jié)構(gòu)簽名的驗證

驗證者先計算Y=H( M, j, R)，再驗證以下方程是否成立

如果簽名通過驗證方程，則關(guān)于消息M的簽名(R, s=sn)是一個有效的前向安全的結(jié)構(gòu)化簽名。如果簽名的計算過程沒有按前面的順序進行，則驗證方程是不成立的。因為1.6 混合結(jié)構(gòu)時簽名的產(chǎn)生

在混合結(jié)構(gòu)中，不妨假設(shè)P1, P2,…, Pi?1組成順序結(jié)構(gòu)，Pi是由m個并行簽名的成員組成，設(shè)為pi,1, pi,2, …, pi,l, 而Pi+1,…, Pn還是順序結(jié)構(gòu)，從總體上看，群組中的成員還是順序結(jié)構(gòu)，為了描述方便，用Pi表示m個并行簽名的成員。Pi的簽名實際上就是由并行簽名得到。在混合結(jié)構(gòu)中的系統(tǒng)參數(shù)與順序結(jié)構(gòu)相同，首先群組G的成員按以順序結(jié)構(gòu)的方式產(chǎn)生它們的公鑰和初始私鑰。Pi的m個成員Pi,l(l=1,2,…,m)，隨機選取奇數(shù)作為它的初始私鑰，它的公鑰為

則Pi對應(yīng)的。si滿足以下驗證方程

當(dāng)Pi計算出自己的ri和si時，群組G的其它成員Pi+1,…, Pn可以按照順序結(jié)構(gòu)簽名的操作步驟計算出它們自己的簽名，則混合結(jié)構(gòu)的簽名為(s, R)，其中s=sn。混合結(jié)構(gòu)的簽名驗證方程和順序結(jié)構(gòu)的驗證方程相同。

2 安全性分析

（1）無法從Pi的第j個周期的密鑰推導(dǎo)出第j+1個周期的密鑰因為面臨求解模p平方根的難題；也無法從公鑰中解出簽名成員的初始簽名密鑰，因為這會遇到解離散對數(shù)的難題。

（2）如果群組成員不按規(guī)定的順序生成簽名(R′, s′)，根據(jù)驗證方程可知，該簽名是無法通過驗證方程的，所以文中提出的簽名方案滿足結(jié)構(gòu)化簽名的要求。

（3）由于在每個不同的周期，群組成員的簽名密鑰都是不同的，當(dāng)?shù)趈個周期的簽名密鑰被暴露時，要想利用第j個周期的簽名密鑰來偽造前面的簽名，就必須推出第j?i ( i=1, 2,…, j?1) 個周期的簽名密鑰，這就面臨了求解模p平方根的難題，所以保證了前面各周期簽名的有效性。

（4）偽造一個簽名是不可能的，因為在簽名的過程中需要整個群組成員的私鑰和公鑰信息，部分成員來偽造一個有效的簽名是不可行的。

3 結(jié)束語

群簽名是一種多人對同一個消息進行的一種簽名。在實際工作中的一些特殊的部門可能需要多個人對同一個消息進行簽名，這就需要多重簽名。多重簽名的順序可能相同，也可能不同，那么不同的簽名順序就是不同的簽名結(jié)構(gòu)。標(biāo)準(zhǔn)的多重簽名存在一個固有的弱點，那就是：一旦所有參與者的密鑰泄漏，所有的多重簽名（包括產(chǎn)生在密鑰泄露之前的簽名）都不可信任了。因此，如何減小密鑰泄漏的危害是一項重要的研究工作。前向安全簽名可以減小密鑰泄漏的危害，將系統(tǒng)的整個生命周期劃分成若干個時間段，每個時間段都通過單向的演化函數(shù)演化新密鑰，并刪除以前的舊密鑰，而公鑰在整個生命周期中保持不變。即便當(dāng)前的密鑰泄漏了，以前時間段的簽名仍然是有效的。同時，在這種情況下不同的簽名結(jié)構(gòu)可以對應(yīng)不同部門的需要，這樣可以滿足許多部門的不同的需求，節(jié)省部門的資源，提高簽名的效率。結(jié)構(gòu)化的多重簽名就是在這種需求下提出的。這種特殊簽名的使用可以大大提高簽名的速度，提高工作效率。因此這是一種有一定實際應(yīng)用價值的特殊簽名。

本文將前向安全的概念引入到結(jié)構(gòu)化簽名方案中，構(gòu)造了一個新的ELGamal類型的前向安全的結(jié)構(gòu)化簽名方案，它不僅保持了結(jié)構(gòu)簽名的特點，并且又具有前向安全的性質(zhì)，在計算方面沒有大的增加，其安全性要比一般的結(jié)構(gòu)化簽名更高。

[1] BURMESTER M, DESMEDT Y, DOI H, et al. A structured ElGamal-type multisignature scheme[J]. Proceedings of Third International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2000), Springer-Verlag, 2000, 1751: 466-483.

[2] HARN L, LIN C Y, WU T C. Structured multisignature algorithms[J]. IEE Proceedings, Computers and Digital Techniques, 2004, 151(3): 231-234.

[3] ITAKURA K, NAKAMURA K. A public-key cryptosystem suitable for digital multisignature[J]. NEC Research and Development, 1983, 71: 1-8.

[4] MICALI S, OHTA K, REYZIN L. Accountable-subgroup multisignatures: extended abstract[C]//Proceedings of the ACM Conference on Computer and Communications Security 2001 (CCS2001), New York: ACM Press, 2001: 245-254.

[5] BELLARE M, MINER S K. A forward-secure digital signature scheme[J].Wiener M J, Advances in Cryptology-CRYPTO’99, Lecture Notes in Computer Science, 1999,1666: 431-448.

[6] BELLARE M, YEE B. Forward security in private key cryptography[J].Joye M, Topics in Cryptology-CT-RSA 2003, Lecture Notes in Computer Science, 2003, 2612: 1-8.

A Forward-Secure structured Multisignature Scheme

FU Jing-zhi1, SI Tao-zhi2, ZHOU Zhen-jiang1
( 1. Department of Information Science, Nanjing College for Population Programm Management, Nanjing 210042, P. R. China; 2. Institute of Computer and Information, Shanghai Second Industrial University, Shanghai 201209, P. R. China )

Based on the difficulty of computing discrete logarithm over finite field of large prime order, forward-secure technique is introduced into structured multisignature signature, then a new structured multisignature scheme with forward-secure is presented. It has not only characteristic of general structured multisignature, but characteristic of forward-secure .

forward security; data signature; structured multisignature

TN918.91

A

1001-4543(2012)03-0187-04

2012-04-18;

2012-08-30

付竟芝（1964－），女，黑龍江人，高級統(tǒng)計師，學(xué)士，主要研究方向為計算機網(wǎng)絡(luò)，電子郵箱fujingzhi1964@163.com。