改進的三方撲克協議

樊相奎， 高昌苗

（①四川師范大學計算機科學學院，四川 成都 610068；②四川師范大學服裝學院，四川 成都 610068）

0 引言

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

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

1 常規三方協議

常規三方協議參考文獻[4]。

Alice,Bob,Carol三人都產生一個公鑰/私鑰對。

Alice:

產生54個消息M1,M2,…,M54

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

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

EB(EA(MB))-＞Alice,

將余下的51張（MB-）發送給Carol: EA(MB-)-＞Carol,Carol(不能閱讀任何消息)隨機選3個消息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個消息:

EA(MA)-＞Alice,

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

游戲結束時,Alice,Bob,Carol出示消息以及密鑰,以便確認每人都沒有作弊。從上面的過程可以看出,如果 Alice和Carol聯合起來對付Bob的時候,該協議可以在不引起懷疑的情況欺騙 Bob。具體作法為：當 Carol在提前取得了 Alice的私鑰DA時，就可以在得到51個消息的時候看到自己的3個消息和Alice要取得的3個消息。

2 改進協議

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

Alice,Bob,Carol三人都產生一個公鑰/私鑰對；Alice：EA/DA;Bob:EB/DB;Carol:EC/DC；Alice：產生 54個隨機消息M1,M2,…,M54，使用公鑰 EA加密產生的 54個消息后發送給Bob。過程如下：

產生54個隨機消息M1,M2,…,M54：

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

Bob：接收到Alice加密后的54個消息后，使用公鑰EB對54個消息再次加密后發送給Carol。過程如下：

EB(EA(Mn))-＞Carol，

Carol：接收到Bob加密后的54個消息后，使用公鑰EC對54個消息進行再次加密后發送給Alice。過程如下：

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

經過三個人使用各自的公鑰加密后的54個消息回到了Alice手中，而其中任何兩個人都沒有能力使用各自的私鑰來查看54個消息的明文。

步驟 2 三位分別取得自己的三個消息后發送給下一位玩家，下一位玩家使用私鑰對上位玩家的消息進行解密。

Alice：隨機選3個消息作為自己的消息MA發送給Bob；將余下51個消息MH也發送給Bob。過程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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))后發送給Carol。過程如下：

DB(EB(MB))=MB，

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

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

游戲結束時,Alice,Bob,Carol出示牌以及密鑰, 來對C手上的45個消息解密，以便確認每人都沒有作弊。

3 協議分析

3.1 正確性

如果游戲三方都是誠實的，根據協議的過程，Alice,Bob,Carol在協議的步驟三都可以得到自己的牌,顯然該協議是正確的。

3.2 安全性

該協議的安全性體現在以下幾點，該協議能確保游戲雙方的公平性：

① 任一副牌是等可能的；

② Alice,Bob,Carol手中的牌沒有重復；

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

3.3 效率

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

4 結語

改進的三方撲克協議能夠在不需要第三方（或第四方）參與的情況下實現撲克游戲的公平性，在實驗室的局域網情況下運行的效率也很高。由于該協議是通過三次循環來實現的，所以改進的三方撲克協議主要在于犧牲時間為代價來換取安全性和公平性，是否還有更好的辦法來改進循環的次數呢？這是今后需要進一步完善之處。

[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] 吳鋌.一個安全有效的RSA門限簽名體制[J].通信技術, 2001(08)：93-95.

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

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