如何在没有卡牌的情况下玩三国杀

zerray | 十月 27th, 2010 - 17:33

考虑这样一个问题:有两个无聊的人想玩三国杀,但是没有卡牌,他们彼此并不信任对方(我说我摸到了连弩 对面非要说他手上已经有两张连弩了..)。有没有可能仅通过面对面说话来实现扑克牌协议,并且保证游戏的公正性呢?

扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”,一对围棋情侣可 以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了,一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”,就是因为在棋类游戏中, 双方的局面信息都是完全公开的。不过,打牌就是另外一码事了。你说你出方片7,我怎么知道你有一个方片7?事先发牌?那谁来负责发牌呢?怎样发牌呢?难道 我告诉你“发到你手中的是两张3一张5一张8一张9”?这样一看,两个人“盲打扑克牌”似乎是不可能的了,要么需要借助道具,要么需要第三者的帮助。不 过,运用密码学知识,我们可以设计一套扑克牌协议,该协议能够实现随机的、隐蔽的、公平的发牌,并且不需要其它东西的帮助。我们以一手五张牌为例,说明如 何实现“两人各摸五张牌”的程序。
我们首先来看一个趣题:

“A、B两人分别在两座岛上。B生病了,A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东 西,但东西只能放在箱子里。只要箱子没被上锁,C都会偷走箱子里的东西,不管箱子里有什么。如果A和B各自有一把锁和只能开自己那把锁的钥匙,A应该如何 把东西安全递交给B?
答案:A把药放进箱子,用自己的锁把箱子锁上。B拿到箱子后,再在箱子上加一把自己的锁。箱子运回A后,A取下自己的锁。箱子再运到B手中时,B取下自己的锁,获得药物。”

我们的基本思路就是这样。不妨用数字1到54来表示54张牌。发牌前,A在每个数字前附着一个随机字符串前缀,然后给每个字符串都加上一把锁,把 54张加密的扑克牌传给B。B收到了扑克牌一看,傻了,这些牌他一张也不认识,每张牌上面都有A的锁。B从里面挑选5张牌出来。他自己不知道这5张牌是什 么,但是他也不能让A知道,于是他在这5张牌上再各加一把锁,传给A。A可以解开自己当初上的那把锁,但牌上还有一把锁,A拿它没办法,只能原封不动地传 回去。B把剩下的锁解开,得到自己的5张牌。然后呢,B手上不是还剩了49张牌吗?B从中随便挑5张出来给A,由A解开上面的锁,得到A的5张牌。
听起来很完美,但实现起来并不简单。上锁开锁和加密解密并不完全相同:两把锁的地位是相同的,但两次加密则有先后的问题。要想 把上述协议转换为密码学协议的话,我们需要采用这样一种加密方式:明文首先由A加密,B在这个密文的基础上再进行加密,此时A还能够把里面那一层密码解 开,而保持B的那一层密码不动。如果用Ea(x)表示A的加密函数,用Da(x)表示A的解密函数的话,我们需要一种加密系统使得 Db(Da(Eb(Ea(x))))=x。有这样的加密系统吗?有!模数相同的RSA算法就满足这样的“交换律”。
RSA算法之所以起作用,原因就在于你能找到这么一对e和d,使得ed≡1 (mod φ(n))。假如存在两对钥匙(e1, d1)和(e2, d2),容易想到(e1*e2)(d1*d2)=(e1*d1)(e2*d2),它仍然同余于1。因此,计算密文c=m^(e1*e2)之后,再计算 c^(d1*d2)一定能恢复明文m,不管你是先算c的d1次方还是d2次方。
有了RSA算法,我们的协议也就出来了。A、B两人各生成一对RSA公私匙(公钥不必也不能公开,我们这里只用到了RSA的可交换性,没用到RSA的加密 钥匙可公开性)。A把54个加了随机字符串前缀的扑克牌分别用公钥加密并发给B,B从中选5张牌并再用自己的公钥加密,然后A用私钥解开B的这5张牌中里 面一层的密码,B再用自己的私钥解密以得到自己的一手牌。同时,B在剩余的49张牌中挑选5张发给A,A用自己的私钥解密以获得自己的一手牌。这样下来, 每个人都得到了自己的一手牌,而都不知道对方手里捏的是啥牌。以后如果还需要摸牌的话,则可以重复刚才的协议。游戏结束后,双方公开自己的钥匙,你可以验 证看对方的钥匙与游戏中的数据是否吻合,以确定对方在游戏过程中没有作弊。

这个协议可以轻易扩展到多个人的情况,也可以适用于更复杂的卡牌游戏。比如说三国杀。。。只要各方都记得武将的排列顺序以及所有卡牌从黑桃A到方片K都是什么东西就行了…

//本文转载自http://www.matrix67.com/blog/archives/1407

梵蒂冈教皇的天文学家准备给外星人做洗礼

zerray | 九月 23rd, 2010 - 18:23

外星人有自己的宗教吗?他们也相信玉皇大帝,或者上帝吗?如果他们相信教皇的话,这就好办了。梵蒂冈天文台的天文学家Guy Consolmagno 近日表示,如果有人真的见过外星人,如果可能请把他带到梵蒂冈来,接受教皇的洗礼。Consolmagno 认为外星人也应该有灵魂,所以也可以接受洗礼。或许这还能促进人类和外星人的和平进程?!Consolmagno 解释到传统对Soul灵魂的定义是:有智慧、有自由意志、追求爱,自主。实际上任何实体,无论多少,都有点灵魂。同时Consolmagno 还否认了Creationism(创造论,认为人类和地球是由某种高级生物创造出来的)

洗礼(wiki

洗礼(或称浸礼、圣洗圣事),是一宗教仪式,现普遍指基督教的传统仪式。洗礼通过把水倒在、撒向受洗者头上或把受浸者放进水中,然后扶起来施行。现天主教、东正教和大部分的基督新教实施的婴儿洗礼在3世纪时出现。

通过无厘头科技周二:教皇的天文学家准备给外星人做洗礼 / 煎蛋.

梵蒂冈官方声明外星人真的存在

zerray | 八月 31st, 2010 - 18:35

科拉多巴尔杜奇主教,梵蒂冈教廷(理事会)的神学家成员,靠近教皇的内部人士,已经5次在 意大利国家电视台,包括最近几个月的 ,宣告外星接触是一个真实的现象。

巴尔杜奇提供了 一个对外星人的分析,他认识是符合天主教教会的神学理解。主教强调,外星人遭遇“不是魔鬼,他们不是因为心理受到影响,他们不是依附案件的实体,但这些遭遇值得认真研究。”巴尔杜奇作为主教,是恶魔学识的专家和梵蒂冈顾问,天主教会以来,历史妖魔化了许多新现象,他说,教会不谴责这些 遭遇。

From Vatican Official Declares Extraterrestrial Contact Is Real.

难怪法国出了很多大数学家

zerray | 七月 15th, 2010 - 16:40

“要说法语数字还真简单。70说成60+10(Soixante-dix),71是60+11……以此类推

79就是60+10+9。那么,80该怎么说?如果以为是60+20那可就太没有想象力了,我们法国人不光会加法,还会乘法,所以80就是4×20(Quatre-vingts)。

到了说99,那就要用得上三则运算了:4×20+10+9(Quatre-vingts-dix-neuf)。我不知遇到了多少外国人,特别是美国人,就是在念到了99的时候决定放弃法语学习的。

也许是为了进一步迷惑外国人,法国人念电话号码不像我们习惯一个数一个数地念。比如61718098,法国人不是念成6-1-7-1-8-0-9-8,而是两位两位地念

61-71-80-98。

如果法国人告诉你他的电话号码,你可听好了:

60+1,60+11,4×20,4×20+10+8。

听法国人说电话号码,你刚记了一个4,后面突然冒出来个20,

所以得赶紧把4涂了,改成80,精神始终处于准亢奋状态。”

From  难怪法国出了很多大数学家XD – 人人都是艺术家.

原版吃豆人草稿

zerray | 六月 24th, 2010 - 17:19

一代经典的游戏就是这样诞生的:

From: Original Pac-Man sketches – Boing Boing.

X光下的玩具

zerray | 六月 20th, 2010 - 23:07

x光下的艺术,能看出来都是什么玩具吗?

From X-rays of toys – Boing Boing.

嗡嗡世界杯创造的商机:过滤Vuvuzela的软件

zerray | 六月 19th, 2010 - 18:17

不得不佩服,国外的geek们敏锐的嗅觉和创意:

来自德国慕尼黑29岁的混音工程师Clemence Schlieweis 发明了一个anti-Vuvuzela filter(vuvuzela过滤器)。他取样了原始Vuvuzela 的声音,根据声波振幅制造出一个完全相反声音,据说把这个声音在比赛时同时播放,便能够过滤掉那恼人的嗡嗡声。

而目前这个东东,以0.99欧元的价格放在网上出售,据说销量还不错。这里可以购买

但英国Salford 大学的声学教授则认为,Clemence 发明的这个东东理论上是可以消除噪音的,但在实践中可能效果并不理想。

From 无厘头世界杯,致富信息:过滤Vuvuzela 软件 / 煎蛋.

新科技:用手势代替设备

zerray | 六月 11th, 2010 - 15:47

看来钢铁侠里的场景将要实现了,到时程序员们再也不用担心因为久坐引起颈椎病啥的了,跳着舞就把项目做好了,哇哈哈

在空中画几个数字就能表示在拨打电话,或者在空气中点几下就表示在打键盘,这么神奇的东东,你信吗?

德国的研究人员近日展示了他们正在开发中的移动设备,一个小巧的佩戴在胸部的一个手势监测器。它可以记录你挥舞出的各种手势,并将其转换成对应的命 令执行。它将实现的功能,就如上面所描述的那样,在该设备完善之后将变得无比神奇。

来自德国Potsdam 大学的研究人员说“我们能想到这种设备能带来新的输入方式,替换掉现有的那些”。

From 新科技:用手势代 替设备 / 煎蛋.

这个发明不错

zerray | 六月 7th, 2010 - 17:55

1951年,潜望眼镜。用于躺着看书。

From组图,旧时代的超未来发明:大轮车、漂浮器等等 / 煎蛋.

btw,图片上的aids啥意思?艾滋?