基于EIGamal加密算法的非對稱數字指紋體制

摘 要:將EIGamal公開密鑰方案的思想用于非對稱數字指紋體制的構造，提出一種不使用一般的安全多方計算協議的非對稱數字指紋體制，該方案不僅具有較好的實現效率，還增加了用戶的安全性，降低了發行商的風險，而且還能確定性地跟蹤叛逆者。

關鍵詞:EIGamal加密算法;數字簽名;數字指紋;數字水印

中圖分類號:TP309 文獻標識碼:A

文章編號:1004-373X(2010)03-047-02

Asymmetric Digital Fingerprinting Scheme Based on EIGamal Encryption Algorithm

HE Shaofang

(Science College，Hu′nan Agricultural University，Changsha，410128，China)

Abstract:An asymmetric digital fingerprinting scheme based on the idea of EIGamal encryption algorithm that avoids using the general multiparty computations protocol is introduced.Furthermore，this scheme has rather efficient in implementation.It increases the safety of customs，reduces the risk of distributors and allows efficient deterministic traitor tracing.

Keywords:EIGamal encryption algorithm;digital sign;digital fingerprinting;digital watermark

0 引 言

數字水印技術和數字指紋技術是近幾年發展起來的新型數字版權保護技術，數字水印是將相同的標識嵌入到同一個電子數據中，而數字指紋是將不同的標識嵌入到同一個電子數據中，數字指紋代表與用戶(購買者)或與該次購買過程有關的信息。當發行商發現有被非法分發的授權信息時，可以根據其中所嵌的指紋信息追蹤出非法用戶。但是，傳統的對稱數字指紋體制[1，2]不能對非法分發者的行為進行確定，因為發行商也可以分發帶有某用戶指紋的拷貝以對該用戶進行陷害。針對此問題，Pfitzmann和SchunterDI引入了非對稱指紋的概念[3]，當獲得了非法拷貝時，發行商可以跟蹤出非法分發者并能向審判者提供證據，此概念一經提出便引起了研究者的廣泛關注[4-10]。本文基于EIGamal加密算法的思想構造了一種數字指紋體制。由于該體制主要采用的是對稱密碼體制中的加解密算法，而密鑰的計算只需進行簡單的指數取模再求乘積即可得到，因此具有較好的實現效率。另外，本方案的密鑰由M(發行商)隨機選取，增加了叛逆者陷害其他無辜用戶的難度。由于用戶的個人解密密鑰對M不可見，M無法陷害無辜用戶，這增加了用戶的安全性。再者，本方案引入了第三方，避免使用一般的安全多方計算協議，并且較完全可信的第三方而言，降低了對其信任度的要求，從而降低了M的風險。

1 基于離散對數的EIGamal公開密鑰方案[11]

密鑰產生過程:任意選擇一個素數q，g是Zp的一個生成元，再任意選擇一個小于q的隨機數x，計算y≡gxmod q，以(g，q，y)作為公開的密鑰匙，x作為秘密密鑰。

加密過程:設欲加密明文信息為m，隨機選擇一個與q-1互素的整數k，計算C1≡gk mod q，C2≡mgk mod q，密文為(C1，C2)。

解密過程:C2/Cx1 mod q。

2 基本方案描述

協議的參與實體有:發行商(M)、用戶(B)、指紋分發中心(FIC)、法官(J);基本協議有:初始化協議、帶指紋拷貝生成(即指紋嵌人)協議、跟蹤協議、審判協議。

2.1 初始化協議

所有的實體產生經過認證的公鑰和私鑰對及相應的數字簽名機制(如用戶B的密鑰對為(pkB，skB)，相應的簽名和驗證函數為signskB，verpkB)，并且公開他們相應的公鑰和簽名驗證函數，各個實體之間的少量秘密信息傳遞可以通過該公鑰密碼體制進行，M將要發售的拷貝分成l個子塊blockj，j=1，2，…，l。

2.2 指紋嵌入協議

(1) 設用戶B是第i個向M和FIC提出購買申請的用戶，則用戶B(或稱用戶i)提交自己經過認證的公鑰，對i用pkB簽名得到signB，然后將(i，signB)發送給FIC。

(2) FIC收到用戶i發來的(i，signB)后，檢驗簽名，若通過，則為用戶i隨機選取一個l×k階的矩陣A。

A=a11a12…a1k

a21a22…a2k

al1al2…alk

以A的各個行向量的元素(aj1，aj2，…，ajk)，j=1，2，…，l，為系數，在FG(q)(q為素數)上構造l個多項式fj(x)=aj1+aj2x+…+ajkxk，j=1，2，…，l，設g是Zq的一個生成元，計算yj1=gaj1mod q，yj2=gaj2mod q，…，yjk=gajkmod q，j=1，2，…，l。

ej={q，g，yj1，yj2，…，yjk}，j=1，2，…，l，e={e1，e2，…，el}，FIC對e簽名得到signFIC，然后將(e，signFIC)發送給發行商M，同時對fj(i)簽名，然后將其連同簽名發送給用戶i，其中，fj(i)=aj1+aj2i+…+ajkik。

(3) 發行商M收到FIC發來的(e，signB，signFIC)后檢驗FIC及用戶B的簽名，若通過，則M為用戶i秘密選取一組密鑰{sj}及一組隨機數{rj}，j=1，2，…，l，將這組隨機數作為指紋分別嵌入子塊blockj，j=1，2，…，l中，得到拷貝pj，j=1，2，…，l，M選擇一個對稱密鑰密碼算法，用密鑰組{sj}對帶指紋的拷貝pj進行加密，得到加密塊cipherj，j=1，2，…，l，再用密鑰{ej}將{sj}加密，生成hj(sj，rj)=(grj，sjyrjj1，yrjj2，…，yrjjk)mod q，M對(hj(sj，rj)，cipherj)簽名，得到signM，將((hj(sj，rj)，cipherj)，signM)發送給用戶i。

(4) 用戶i收到FIC經過簽名的fj(i)及B發來的((hj(sj，rj)，cipherj)，signM)后，依次檢驗FIC及B的簽名，若通過，則計算{sjyrjj1×(yrjj2)i×…×(yrjjk)ik}/(grj)fj(i)，得到解密密鑰組{sj}，用它將cipherj解密得到帶指紋的拷貝pj，j=1，2，…，l，最后將pj按順序組成有用的拷貝P。

2.3 跟蹤協議

M若發現非法拷貝Pfound，執行相應的跟蹤算法，從該拷貝中提取指紋，若提不出，則協議終止;否則提取出某一隨機數列{rj′}，j=1，2，…，l，M在銷售記錄中查找與之相等的{rj}，然后輸出相應的pkB及{sj}，并將(({sj}，{rj}，j=1，2，…，l)，signB)作為證據。

2.4 審判協議

M將pkB及(({sj}，{rj}，j=1，2，…，l)，signB)提交給法官J，J用與pkB相應的驗證函數verpkB驗證signB是否為B對i的簽名，若是則認為用戶B是非法分發者，否則認為B是無辜的。

3 正確性及安全性分析

3.1 正確性分析

命題:用戶i由收到的hj(sj，rj)，cipherj及fj(i)通過計算得到的密鑰組{sj}恰是M對拷貝塊pj加密用的密鑰。

證明:因為yj1=gaj1mod q，yj2=gaj2mod q，…，yjk=gajkmod q，j=1，2，…，l



則:{sjyrjj1×(yrjj2)i×…×(yrjjk)ik}/(grj)fj(i)

={sj(gaj1)rj×(gaj2)rji×…×(gajk)rjik}/(grj)fj(i)

={sjgrj(aj1+aj2i+…+ajkik)}/(grj)fj(i)

={sjgrj#8226;fj(i)}/(grj)fj(i)=sj， j=1，2，…，l



3.2 安全性分析

(1) 發行商M的安全性

因為密鑰組{sj}及隨機數組{rj}，j=1，2，…，l，都是發行商秘密隨機選取的，所以未授權用戶i無法偽造({sj}，{rj}，j=1，2，…，l)，這保證了不誠實用戶無法獲得電子數據，發行商的利益得到了保障。另外，M公開的只是其拷貝的加密版本，FIC獲得的只是用于解密的子密鑰，并未獲得原拷貝，這與完全利用可信的第三方比較，本文的方案減少了對可信方信任度的要求，這降低了M的風險，由于引入了第三方，這就避免了使用一般的安全多方計算協議[3]，更有助于在實際中的應用。

(2) 用戶的安全性

一方面，用戶的個人解密密鑰fj(i)對發行商M是不可見的，因此，M想要陷害無辜用戶是不可能的。另一方面，對于用戶來說，由于密鑰組{sj}及隨機數組{rj}由M秘密選取，其他任一用戶都無法仿造({sj}，{rj}，j=1，2，…，l)，因此無法誣陷誠實用戶。

4 結 語

本文基于EIGamal加密算法的思想構造了一種數字指紋體制。由于該體制主要采用的是對稱密碼體制中的加解密算法，而密鑰的計算只需進行簡單的指數取模再求乘積即可得到，因此具有較好的實現效率。另外，本方案的密鑰由M隨機選取，增加了叛逆者陷害其他無辜用戶的難度。由于用戶的個人解密密鑰對M不可見，M無法陷害無辜用戶，這增加了用戶的安全性。再者，本方案引入了第三方FIC，避免使用一般的安全多方計算協議，并且較完全可信的第三方而言，降低了對其信任度的要求，從而降低了M的風險。

參考文獻

[1]Blakley G R，Meadows C，Prudy C B.Finger-printing Long Forgiving Messages[A].Advances in Cryptogogy-CRYPTO′85[C].Berlin，1985:180-189.

[2]Boneh D，Shaw J.Collusion-secure Fingerprinting for Digital Data[J].IEEE Trans.on Inform.Theory，1997(44):1 897-1 905.

[3]Pfitzmann B，Schunter M.Asymmetric Fingerprinting[A].Advances in Cryptology-EUROCRYPT′96[C].Berlin:Springer，1996:84-95.

[4]Pfitzmann B，Waidner M.Asymmetric Fingerprinting for Large Collusions[A].Proc.of the 4th ACM Conf.on Computer and Communications Security[C].Zurich:ACM Press，1997:151-160.

[5]Pfitzmann B，Waidner M.Anonymous Fingerprinting[A].

Advances in Cryptology-EUROCRYPT′ 97[C].Berlin:Springer，1997:88-102.

[6]Camenisch J.Efficient Anonymous Fingerprinting with Group Signatures[A].Advances in Cryptology-Asiacrypt 2000[C].Berlin:Springer，2000:415-428.

[7]Memon N，Wong P W.A Buyer-seller Water-marking Protocol[J].IEEE Trans.on Image Processing，2001，10(4):643-649.

[8]Domingo-Ferrer J.Anonymous Fingerprinting Based on Committed Oblivious Transfer[A].Public Key Cryptography′99[C].Berlin:Springer，1999:43-52.

[9]呂述望，王彥，劉振華.非對稱數字指紋技術[A].全國第四屆信息隱藏研討會論文集[C].北京:機械工業出版社，2002.

[10]Wang Y，Lu S W，Liu Z H.A New Asymmetric Fingerprinting Framework Based on Secret Sharing[A].Commucications and Multimedia Security[C].Dordrecht:Kluwer，2002:29-40.

[11]楊波.現代密碼學[M].北京:清華大學出版社，2007.