改進(jìn)的三方撲克協(xié)議

樊相奎， 高昌苗

（①四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610068；②四川師范大學(xué)服裝學(xué)院，四川 成都 610068）

0 引言

撲克協(xié)議[1]：①比賽必須從“公平發(fā)牌”開(kāi)始。假定牌手們通過(guò)一系列消息實(shí)現(xiàn)了這一要求，則：a.牌手知道自己手中的牌，但不知道其他人的；b.手中的牌應(yīng)不相連貫；c.所有可能的手中牌對(duì)每位牌手是等可能的；②在比賽中，牌手可能要從剩下的牌中補(bǔ)抓幾張牌，這也要求像①中所述那樣公平地處理；③比賽結(jié)束時(shí)，牌手們應(yīng)能檢驗(yàn)比賽是否公平，以及他們的對(duì)手有沒(méi)有騙人，特別是對(duì)贏家是否作弊感興趣。

要完成電子撲克游戲，加密變換必須是可交換的，即對(duì)于任何消息 M，有：EA(EB(M))=EB(EA(M))。顯然RSA加密算法是可以交換的[2-3]。

1 常規(guī)三方協(xié)議

常規(guī)三方協(xié)議參考文獻(xiàn)[4]。

Alice,Bob,Carol三人都產(chǎn)生一個(gè)公鑰/私鑰對(duì)。

Alice:

產(chǎn)生54個(gè)消息M1,M2,…,M54

EA(Mn)-＞Bob (n=1,2,…,54),

Bob(不能閱讀任何消息)隨機(jī)選3個(gè)消息MB:

EB(EA(MB))-＞Alice,

將余下的51張（MB-）發(fā)送給Carol: EA(MB-)-＞Carol,Carol(不能閱讀任何消息)隨機(jī)選3個(gè)消息Mc:

Ec(EA(Mc))-＞Alice,

Alice:也不能閱讀回送的消息:

DA(EB(EA(MB)))= EB(MB)-＞Bob,

DA(EC(EA(MC)))=EC(MC)-＞Carol,

Bob取得EB(MB):

DB(EB(MB))=MB,

Carol取得EC(MC),

DC(EC(MC))=MC,

Carol從余下的48張中選擇3個(gè)消息:

EA(MA)-＞Alice,

Alice用私鑰解密DA(EA(MA))=MA。

游戲結(jié)束時(shí),Alice,Bob,Carol出示消息以及密鑰,以便確認(rèn)每人都沒(méi)有作弊。從上面的過(guò)程可以看出,如果 Alice和Carol聯(lián)合起來(lái)對(duì)付Bob的時(shí)候,該協(xié)議可以在不引起懷疑的情況欺騙 Bob。具體作法為：當(dāng) Carol在提前取得了 Alice的私鑰DA時(shí)，就可以在得到51個(gè)消息的時(shí)候看到自己的3個(gè)消息和Alice要取得的3個(gè)消息。

2 改進(jìn)協(xié)議

步驟1 三位玩家使用自己的公鑰都對(duì)54張牌進(jìn)行一次加密。

Alice,Bob,Carol三人都產(chǎn)生一個(gè)公鑰/私鑰對(duì)；Alice：EA/DA;Bob:EB/DB;Carol:EC/DC；Alice：產(chǎn)生 54個(gè)隨機(jī)消息M1,M2,…,M54，使用公鑰 EA加密產(chǎn)生的 54個(gè)消息后發(fā)送給Bob。過(guò)程如下：

產(chǎn)生54個(gè)隨機(jī)消息M1,M2,…,M54：

EA(Mn)-＞Bob (n=1,2,…,54)，

Bob：接收到Alice加密后的54個(gè)消息后，使用公鑰EB對(duì)54個(gè)消息再次加密后發(fā)送給Carol。過(guò)程如下：

EB(EA(Mn))-＞Carol，

Carol：接收到Bob加密后的54個(gè)消息后，使用公鑰EC對(duì)54個(gè)消息進(jìn)行再次加密后發(fā)送給Alice。過(guò)程如下：

EC(EB(EA(Mn)))-＞Alice。

經(jīng)過(guò)三個(gè)人使用各自的公鑰加密后的54個(gè)消息回到了Alice手中，而其中任何兩個(gè)人都沒(méi)有能力使用各自的私鑰來(lái)查看54個(gè)消息的明文。

步驟 2 三位分別取得自己的三個(gè)消息后發(fā)送給下一位玩家，下一位玩家使用私鑰對(duì)上位玩家的消息進(jìn)行解密。

Alice：隨機(jī)選3個(gè)消息作為自己的消息MA發(fā)送給Bob；將余下51個(gè)消息MH也發(fā)送給Bob。過(guò)程如下：

EC(EB(EA(MA)))-＞Bob，

EC(EB(EA(MH)))-＞Bob，

Bob：使用私鑰DB解密Alice發(fā)送的Alice的三個(gè)消息；在余下 51個(gè)消息隨機(jī)選擇 3個(gè)消息作為自己的消息 MB；將EC(EA(MA))，EC(EB(EA(MB)))，余下48個(gè)消息MI一起發(fā)送給Carol。過(guò)程如下：

DBEC(EB(EA(MA))))= EC(EA(MA))-＞Carol，

EC(EB( EA(MB))) -＞Carol，

EC(EB( EA(MI))) -＞Carol，

Carol：使用私鑰DC解密MA；使用私鑰DC解密MB；在余下的 48個(gè)消息中隨機(jī)選擇 3個(gè)消息作為自己的消息 MC；將EA(MA)，EB(EA(MB))，EC(EB(EA(MC)))發(fā)送給 Alice。過(guò)程如下：

DC(EC(EA(MA)))=EA(MA)-＞Alice，

DC(EC(EB(EA(MB))))=EB(EA(MB))-＞Alice，

EC(EB(EA(MC)))-＞Alice。

步驟 3 三位玩家再次拿到自己牌的時(shí)候再使用自己的私鑰解密即可得到自己牌。

Alice：使用 DA解密EA(MA)即可得到MA的明文；使用私鑰DA解密 EB(EA(MB))后發(fā)送給 Bob；使用私鑰 DA解密EC(EB(EA(MC)后發(fā)送給Bob。過(guò)程如下：

DA(EA(MA)))=MA，

DA(EB(EA(MB)))=EB(MB)-＞Bob，

DA(EC(EB(EA(MC))))=EC(EB(MC))-＞Bob，

Bob：使用私鑰DB解密EB(MB)即可得到MB的明文；使用私鑰DB解密EC(EB(MC))后發(fā)送給Carol。過(guò)程如下：

DB(EB(MB))=MB，

DB(EC(EB(MC)))=EC(MC)-＞Carol，

Carol：使用DC解密EC(MC)即可得到MC的明文。過(guò)程如下：DC(EC(MC)))=MC。

游戲結(jié)束時(shí),Alice,Bob,Carol出示牌以及密鑰, 來(lái)對(duì)C手上的45個(gè)消息解密，以便確認(rèn)每人都沒(méi)有作弊。

3 協(xié)議分析

3.1 正確性

如果游戲三方都是誠(chéng)實(shí)的，根據(jù)協(xié)議的過(guò)程，Alice,Bob,Carol在協(xié)議的步驟三都可以得到自己的牌,顯然該協(xié)議是正確的。

3.2 安全性

該協(xié)議的安全性體現(xiàn)在以下幾點(diǎn)，該協(xié)議能確保游戲雙方的公平性：

① 任一副牌是等可能的；

② Alice,Bob,Carol手中的牌沒(méi)有重復(fù)；

③ 每人都知道自己手中的牌，但卻不知對(duì)方手中的牌。即使有任何兩人作弊也不能夠知道第三方牌手中的牌。

3.3 效率

該協(xié)議共需Alice,Bob,Carol三方進(jìn)行九次通信，在計(jì)算方面，消耗計(jì)算資源的主要是加解密運(yùn)算，由于該協(xié)議沒(méi)有用到非常耗時(shí)的模指數(shù)運(yùn)算，計(jì)算效率不會(huì)太低。由于該協(xié)議不需可信第四方介入，以較低的效率犧牲帶來(lái)較高的安全性是值得的。

4 結(jié)語(yǔ)

改進(jìn)的三方撲克協(xié)議能夠在不需要第三方（或第四方）參與的情況下實(shí)現(xiàn)撲克游戲的公平性，在實(shí)驗(yàn)室的局域網(wǎng)情況下運(yùn)行的效率也很高。由于該協(xié)議是通過(guò)三次循環(huán)來(lái)實(shí)現(xiàn)的，所以改進(jìn)的三方撲克協(xié)議主要在于犧牲時(shí)間為代價(jià)來(lái)?yè)Q取安全性和公平性，是否還有更好的辦法來(lái)改進(jìn)循環(huán)的次數(shù)呢？這是今后需要進(jìn)一步完善之處。

[1] Shamir A,Rivest R,Adleman L.Mental Poker[EB/OL].(2008-11-12).[2009-09-15].http：//en.wikipedia.org/wiki/mental-poker.

[2] 吳鋌.一個(gè)安全有效的RSA門(mén)限簽名體制[J].通信技術(shù), 2001(08)：93-95.

[3] 劉傳領(lǐng),范建華.RSA非對(duì)稱(chēng)加密算法在數(shù)字簽名中的應(yīng)用研究[J].通信技術(shù), 2009, 42(03)： 192-914.

[4] Wenbo M. Modern Cryptography：Theory and Practice[M].北京：電子工業(yè)出版社,2004：316-323.