改进的三方扑克协议
2010-09-25樊相奎高昌苗
樊相奎, 高昌苗
(①四川师范大学计算机科学学院,四川 成都 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.