一個(gè)基于辮群的密鑰認(rèn)證方案的安全分析

洪東招

(杭州師范大學(xué) 理學(xué)院，浙江 杭州 310036)

0 引 言

辮群這個(gè)概念于1925年由Artin引入[1]，并于1947年嚴(yán)格定義了辮群[2].辮群上的數(shù)學(xué)困難問(wèn)題，比如共軛搜索問(wèn)題、共軛分解問(wèn)題和求根問(wèn)題等，非常適合作為密碼學(xué)系統(tǒng)安全的基本困難假設(shè).Anshel等人[3]和Ko等人[4]開(kāi)創(chuàng)性地將辮群上的數(shù)學(xué)困難問(wèn)題應(yīng)用在密碼學(xué)里，此后，人們開(kāi)始廣泛研究基于辮群的密碼系統(tǒng)，許多基于辮群的密碼學(xué)方案被提出來(lái)[5-13].

密鑰認(rèn)證在傳統(tǒng)公鑰密碼體制中是非常重要的.在傳統(tǒng)公鑰密碼系統(tǒng)中，每一個(gè)用戶都有一個(gè)密鑰對(duì)(公鑰，私鑰)，公鑰是公開(kāi)的，攻擊者可以替換用戶的公鑰，從而仿冒用戶.那么，密鑰認(rèn)證的目的就是保證合法用戶的公鑰不能被偽造.因此，許多密鑰認(rèn)證方案被提出來(lái)[14-16].最近，卓等人[17]提出了基于辮群的密鑰認(rèn)證方案，然而，筆者將指出該方案的不安全性,易受公鑰替換攻擊，因而不滿足用戶公鑰的不可否認(rèn)性.通過(guò)改進(jìn)原方案的注冊(cè)和證書(shū)的生成和認(rèn)證階段，提出一個(gè)改進(jìn)的方案，能有效抵抗密鑰替換攻擊，從而滿足不可否認(rèn)性.

1 文獻(xiàn)[17]基于辮群的密鑰認(rèn)證方案

1.1 辮群簡(jiǎn)介

1.1.1 定 義

辮群Bn(n∈N)是由生成元σ1,σ2,…,σn-1生成的有限表示的非交換無(wú)限群，并且當(dāng)n≥2時(shí)它的生成元滿足如下關(guān)系：

當(dāng)1≤i≤n-2時(shí)，σiσi+1σi=σi+1σiσi+1；當(dāng)|i-j|≥2時(shí)，σiσj=σjσi，因此，辮群Bn可以表示為

則稱LBn為做左辮群，RBn為右辮群，且?α∈LBn,?β∈RBn，有αβ=βα成立.

1.1.2 性 質(zhì)

辮群中的元素都可以通過(guò)標(biāo)準(zhǔn)形式來(lái)統(tǒng)一表示，即由p+1個(gè)參量(u,π1,π2,…,πp)表示，其中，u是整數(shù)；πi是個(gè)n階置換，該表示是唯一的.

1.1.3 困難問(wèn)題

1)共軛查找問(wèn)題(Conjugacy Search Problem, CSP)

條件：x,y共軛，即(x,y)∈Bn×Bn，滿足y=a-1xa,a∈Bn.

找到：b∈Bn，使得y=b-1xb.

2)一般共軛查找問(wèn)題(General Conjugacy Search Problem, GCSP)

條件：(x,y)∈Bn×Bn，滿足y=a-1xa,a∈Bm,m≤n.

找到：b∈Bn，使得y=b-1xb.

3)共軛分解問(wèn)題(Conjugacy Decomposition Problem, CDP)

條件：(x,y)∈Bn×Bn，滿足y=a-1xa,a∈Bm,m

找到：b1,b2∈Bm，使得y=b1xb2.

4)p次根問(wèn)題(Root Problem, RP)

條件：(y,p)∈Bn×Z，滿足y=xp,x∈Bn.

找到：b∈Bn，使得y=bp.

1.2 方案描述

1.2.1 初始參數(shù)

具有左標(biāo)準(zhǔn)型的辮群Bn(一個(gè)辮群稱為是左標(biāo)準(zhǔn)型的，是指對(duì)于辮群中的2個(gè)辮元a,b，從a,b中猜出a或b是困難的)，其中，n是偶數(shù)；4個(gè)整數(shù)s,t,LBs,RBt以及一個(gè)足夠復(fù)雜的辮元x∈Bn.

1.2.2 密鑰產(chǎn)生

用戶選擇p,q∈RZ+,p,q≥2,a∈LBs，計(jì)算X=apxaq，則(X,a)是用戶的公私密鑰對(duì).

1.2.3 注冊(cè)和證書(shū)的生成

在用戶注冊(cè)和生成證書(shū)的時(shí)候，將執(zhí)行以下操作：

1)選擇b∈RRBt作為自己的口令，且滿足RP問(wèn)題對(duì)于a,b是足夠困難的，隨機(jī)數(shù)r∈LBs.

2)計(jì)算W1=bp，W2=bq，Y1=b-1xb，Y2=r-1xr，Y3=b-1Y2b，令α=(W1,W2,Y3),β=(r,Y1).

3)將α,β秘密地提交給服務(wù)器，服務(wù)器將α存放在公開(kāi)口令表中，β存放在秘密口令中.

4)用戶生成證書(shū)C=apbpxbqaq，將X,C存放在公開(kāi)密鑰目錄中.

1.2.4 認(rèn) 證

1)服務(wù)器的認(rèn)證.當(dāng)服務(wù)器收到α,β后，計(jì)算Y4=r-1Y1r，如果Y3=Y4，則認(rèn)為是用戶提交的，否則，拒絕接收.

2)當(dāng)有人(下稱驗(yàn)證者)需要使用X來(lái)加密消息時(shí)，將檢驗(yàn)用戶的公開(kāi)密鑰證書(shū)，驗(yàn)證者執(zhí)行的操作分兩步：

①?gòu)墓_(kāi)密鑰目錄中得到用戶的公鑰X和證書(shū)C，從公開(kāi)口令表中得到α；

②驗(yàn)證C=W1XW2，如果等式成立，則驗(yàn)證者承認(rèn)公鑰證書(shū)的正確性，就可以用X來(lái)加密消息，否則，他就拒絕X.

1.3 方案的不安全性

一個(gè)不誠(chéng)實(shí)的用戶可以偽造用戶的公鑰和證書(shū)，具體攻擊如下：

1)選擇c∈LBs計(jì)算：X′=cXc,C′=cCc

2)將看到C′和X′滿足驗(yàn)證式：

從上述可知，驗(yàn)證式成立，如果使用X′來(lái)加密消息時(shí)，那么合法接收者無(wú)法解密密文，所以卓等人提出的基于辮群的密鑰認(rèn)證方案在公鑰替換攻擊下是不安全的，且不滿足用戶公鑰的不可否認(rèn)性.

2 對(duì)文獻(xiàn)[17]基于辮群的密鑰認(rèn)證方案的改進(jìn)

為了克服上面的攻擊，利用文獻(xiàn)[16]的方法對(duì)基于辮群的密鑰認(rèn)證方案進(jìn)行改進(jìn).初始參數(shù)和密鑰產(chǎn)生階段與原方案一樣.在此修改原方案中注冊(cè)和證書(shū)的生成階段和認(rèn)證階段，具體的過(guò)程如下.

2.1 注冊(cè)和證書(shū)的生成

前三步與原方案相同，主要改進(jìn)的地方在第四步，在存放X,C之前，服務(wù)器分別對(duì)它們簽名，而原方案是直接存放.

1)選擇b∈RRBt作為自己的口令，且滿足RP問(wèn)題對(duì)于a,b是足夠困難的，隨機(jī)數(shù)r∈LBs.

2)計(jì)算W1=bp，W2=bq，Y1=b-1xb，Y2=r-1xr，Y3=b-1Y2b，令α=(W1,W2,Y3),β=(r,Y1).

3)將α,β秘密地提交給服務(wù)器，服務(wù)器將α存放在公開(kāi)口令表中，β存放在秘密口令.

4)用戶生成證書(shū)C=apbpxbqaq，將X,C提交給服務(wù)器，服務(wù)器分別計(jì)算X的簽名SigS(X)，C的簽名SigS(C)，然后存放在公開(kāi)密鑰目錄中.

2.2 認(rèn) 證

第一步與原方案相同，主要改進(jìn)的地方在第二步，由于公開(kāi)密鑰目錄存放的是公鑰簽名SigS(X)和證書(shū)簽名SigS(C)，所以首先要驗(yàn)證簽名.

1)服務(wù)器的認(rèn)證.當(dāng)服務(wù)器收到α,β后，計(jì)算Y4=r-1Y1r，如果Y3=Y4，則認(rèn)為是用戶提交的，否則，拒絕接收.

2)當(dāng)有人(下稱驗(yàn)證者)需要使用X來(lái)加密消息時(shí)，將檢驗(yàn)用戶的公開(kāi)密鑰證書(shū)，驗(yàn)證者執(zhí)行的操作分兩步：

①?gòu)墓_(kāi)密鑰目錄中得到用戶的公鑰簽名SigS(X)和證書(shū)簽名SigS(C)，從公開(kāi)口令表中得到α；

②通過(guò)服務(wù)器的公鑰驗(yàn)證SigS(X)和SigS(C)的正確性.如果正確，驗(yàn)證C=W1XW2，如果等式成立，則驗(yàn)證者承認(rèn)公鑰證書(shū)的正確性，就可以用X來(lái)加密消息，否則，他就拒絕X.

3 安全分析

改進(jìn)后的方案不僅具有原方案的安全性，而且還增加了原方案沒(méi)有的安全性.由于在存放之前對(duì)用戶公鑰X和相應(yīng)的證書(shū)C服務(wù)器對(duì)它們分別進(jìn)行簽名，并且攻擊者不知道服務(wù)器的私鑰，那么攻擊者不能偽造服務(wù)器的簽名SigS(X)和SigS(C)，這使得攻擊者不能偽造出能滿足用戶公鑰驗(yàn)證式的用戶公鑰X和相應(yīng)的證書(shū)C，所以改進(jìn)后的方案能夠抵抗公鑰替換攻擊.

4 結(jié) 論

文章已經(jīng)證明卓等人提出的基于辮群的密鑰認(rèn)證方案是不安全的，不滿足不可否認(rèn)性，這對(duì)于密鑰認(rèn)證方案是致命的缺陷.通過(guò)對(duì)這個(gè)方案進(jìn)行改進(jìn)，能夠抵抗公鑰替換攻擊，滿足不可否認(rèn)性.辮群的公鑰密碼學(xué)有著廣闊的應(yīng)用前景，人們已經(jīng)開(kāi)始尋求更加安全的、效率更高的、實(shí)用性更強(qiáng)的基于辮群的密碼系統(tǒng).

[1] Artin E. Theorie der Z?pfe[J]. Abh Math Sem Univ Hamburg,1926,4:47-72.

[2] Artin E. Theory of braids[J]. The Annals of Mathematics,1947,48(1):101-126.

[3] Anshel I, Anshel M, Goldfeld D. An algebraic method for public-key cryptography[J]. Mathematical Research Letters,1999,6：287-291.

[4] Ko K, Lee S, Cheon J,etal. New public key cryptosystem using braid groups[C]//Advances in Cryptology:Procedings of CRYPTO 2000, LNCS 1880. Berlin: Springer-Verlag,2000:166-183.

[5] Lee E K, Lee S J, Halm S G. Pseudorandomness from braid groups[C]//Advances in Cryptology: Procedings of CRYPTO 2001, LNCS 2139. Berlin: Springer-Verlag,2001:486-502.

[6] Anshel I, Anshel M, Fisher B,etal. New key agreement protocols in braid group cryptography[C]//Progress in Cryptology-CT-RSA 2001, LNCS 2020. Berlin: Springer-Verlag,2001:13-27.

[7] Cha J C, Ko K H, Lee S J,etal. An efficient implementation of braid groups[C]//Advances in Cryptology: Proceedings of ASIACRYPT 2001, LNCS 2248. Berlin: Springer-Verlag,2001:144-156.

[8] Ko K H, Choi D H, Cho M S,etal. New signature scheme using conjugacy problem[EB/OL] .(2002-11-11)[2009-11-19].http://eprint.iacr.org/2002/168.pdf.

[9] Sibert H, Dehornoy P, Girault M. Entity authentication schemes using braid word reduction[EB/OL].(2002-12-13)[2009-11-07].http://eprint.iacr.org/2002/187.pdf.

[10] Kim Z, Kim K. Provably-secure identification scheme based on braid groups[C/OL]//The 2004 Symposium on Cryptography and Information Security-SCIS 2004, Sendai, Japan,2004.[2009-11-10].http://caislab.kaist.ac.kr/Paper/paper_files/2004/SCIS04/scis2004%20-%20zeenkim.pdf.

[11] Thomas T, Lal A K.Group Signature Schemes Using Braid Groups[EB/OL].(2006-02-17)[2009-11-05].http://arxiv.org/abs/cs/0602063.

[12] Verma G K. A Proxy Blind Signature Scheme over Braid Groups[J]. International Journal of Network Security,2009,9(3):214-217.

[13] Lai S, Verma V. Some Proxy Signature and Designated verifier Signature Schemes over Braid Groups[EB/OL].(2009-04-22)[2010-01-05].http://arxiv.org/PS_cache/arxiv/pdf/0904/0904.3422v1.pdf.

[14] Shao Zuhua. A new key authentication scheme for cryptosystems based on discrete logarithms[J]. Applied Mathematics and Computation,2005,167(1):143-152.

[15] Yoon E J, Yoo K Y . Improving the Sun-Cao’s Public Key Authentication Scheme for Non-repudiation[C]//Third International Conference on Intelligent Computing-ICIC 2007. Berlin: Springer-Verlag,2007:1103-1109.

[16] Yoon E J, Yoo K Y. Secure Key Authentication Scheme Based on Discrete Logarithms[C]//Third International Conference on Next Generation Web Services Practices -NWeSP′07. New York: IEEE press,2007:73-78.

[17] 卓澤朋，魏仕民，馬陵勇.基于辮群的密鑰認(rèn)證方案[J].計(jì)算機(jī)工程,2009,35(13):139-140.