yangleader的个人博客分享 http://blog.sciencenet.cn/u/yangleader 教授,博士生导师,北邮信息安全中心主任

博文

安全通论(3):攻防篇之“非盲对抗”之“石头剪刀布” 精选

已有 9011 次阅读 2016-1-4 21:57 |个人分类:爽玩人生|系统分类:论文交流

安全通论(3

------攻防篇之“非盲对抗”之“石头剪刀布”

杨义先,钮心忻

北京邮电大学信息安全中心

摘要:本文给出了“石头剪刀布”的一种“白富美”新玩法。所谓“白”,即思路清清楚楚、明明白;所谓“富”,即理论内涵非常丰;所谓“美”,即结论绝对数学。《安全通论》的魅力也在这里得到了幽默体现。

(一)前言

全人类,数千年来,都在玩“石头剪刀布”,而且,玩出了无尽幸福!

由浙江大学、浙江工商大学、中国科学院等单位组成的跨学科团队,在三百多名自愿者的配合下,历时4年,终于把“石头剪刀布”玩成了“高大上”:其成果被评为“麻省理工学院科技评论2014年度最优”,这也是我国社科成果首次入选该顶级国际科技评论。

本文利用《安全通论》,只需一张纸、一支笔,就把“石头剪刀布”玩成“白富美”。所谓“白”,即思路清清楚楚、明明白白;所谓“富”,即理论内涵非常丰富;所谓“美”,即结论绝对数学美。

不信?请读下文!

(二)信道建模

设甲与乙玩“石头剪刀布”。他们可分别用随机变量XY来表示:

当甲出拳为剪刀、石头、布时,分别记为X=0X=1X=2

当乙出拳为剪刀、石头、布时,分别记为Y=0Y=1Y=2

根据概率论中的“大数定律”,频率的极限趋于概率,所以甲乙双方的出拳习惯,可以用随机变量XY的概率分布表示为:

Pr(X=0)=p,即,甲出“剪刀”的概率;

Pr(X=1)=q,即,甲出“石头”的概率;

Pr(X=2)=1-p-q,即,甲出“布”的概率。这里0<p,q,p+q<1

Pr(Y=0)=r,即,乙出“剪刀”的概率;

Pr(Y=1)=s,即,乙出“石头”的概率;

Pr(Y=2)=1-r-s,即,乙出“布”的概率。这里0<r,s,r+s<1

同样,还可以统计出二维随机变量(XY)的联合分布概率如下:

Pr(X=0,Y=0)=a,即,甲出“剪刀”,乙出“剪刀”的概率;

Pr(X=0,Y=1)=b,即,甲出“剪刀”,乙出“石头”的概率;

Pr(X=0,Y=2)=1-a-b,即,甲出“剪刀”,乙出“布”的概率。这里0<a,b,a+b<1

Pr(X=1,Y=0)=e,即,甲出“石头”,乙出“剪刀”的概率;

Pr(X=1,Y=1)=f,即,甲出“石头”,乙出“石头”的概率;

Pr(X=1,Y=2)=1-e-f,即,甲出“石头”,乙出“布”的概率。这里0<e,f,e+f<1

Pr(X=2,Y=0)=g,即,甲出“布”,乙出“剪刀”的概率;

Pr(X=2,Y=1)=h,即,甲出“布”,乙出“石头”的概率;

Pr(X=2,Y=2)=1-g-h,即,甲出“布”,乙出“布”的概率。这里0<g,h,g+h<1

由随机变量XY,构造另一个随机变量Z=[2(1+X+Y)]mod3。由于任意两个随机变量都可构成一个通信信道,所以,以X为输入,以Z为输出,我们就得到一个通信信道(XZ),称之为“甲方信道”。

如果在某次游戏中甲方赢,那么,就只可能有三种情况:

情况1,“甲出剪刀,乙出布”,即,“X=0Y=2”,这也等价于“X=0Z=0”,即,“甲方信道”的输入等于输出;

情况2,“甲出石头,乙出剪刀”,即,“X=1Y=0”,这也等价于“X=1Z=1”,即,“甲方信道”的输入等于输出;

情况3,“甲出布,乙出石头”,即,“X=2Y=1”,这也等价于“X=2Z=2”,即,“甲方信道”的输入等于输出。

反过来,如果“甲方信道”将1比特信息成功地从发端送到了收端,那么,也只有三种可能的情况:

情况1,输入和输出都等于0,即,“X=0Z=0”,这也等价于“X=0Y=2”,即,“甲出剪刀,乙出布”,即,甲赢;

情况2,输入和输出都等于1,即,“X=1Z=1”,这也等价于“X=1Y=0”,即,“甲出石头,乙出剪刀”,即,甲赢;

情况3,输入和输出都等于2,即,“X=2Z=2”,这也等价于“X=2Y=1”,即,“甲出布,乙出石头”,即,甲赢。

综合以上正反两方面,共六种情况,就得到一个重要引理:

引理1:甲赢一次,就意味着“甲方信道”成功地把1比特信息,从发端送到了收端;反之亦然。

再利用随机变量YZ构造一个信道(YZ),称之为“乙方信道”,它以Y为输入,以Z为输出。那么,仿照前面的论述,我们可得如下引理:

引理2:乙方赢一次,就意味着“乙方信道”成功地把1比特信息,从发端送到了收端;反之亦然。

由此可见,甲乙双方玩“石头剪刀布”的输赢问题,就转化成了“甲方信道”和“乙方信道”能否成功地传输信息比特的问题。根据仙农第二定理[3],我们知道:信道容量就等于该信道能够成功传输的信息比特数。所以,“石头剪刀布”的游戏问题,就转化成了信道容量问题。更准确地说,我们有如下定理:

定理1(“石头剪刀布”定理):如果剔除“平局”不考虑(即,忽略甲乙双方都出相同手势的情况),那么,

1)针对甲方来说,对任意k/nC,都一定有某种技巧(对应于仙农编码),使得,在nC次游戏中,甲方能够胜乙方k次;如果在某m次游戏中,甲方已经胜出乙方u次,那么,一定有umC。这里C是“甲方信道”的容量。

2)针对乙方来说,对任意k/nD,都一定有某种技巧(对应于仙农编码),使得,在nD次游戏中,乙方能够胜甲方k次;如果在某m次游戏中,乙方已经胜出甲方u次,那么,一定有umD。这里D是“乙方信道”的容量。

3)如果C<D,那么,整体上甲方会输;如果C>D,那么,整体上甲方会赢;如果C=D,那么,甲乙双方势均力敌。

由于“甲方信道”和“乙方信道”的信道容量都有现成的计算公式,为避免喧宾夺主,更为了不少读者朋友被过多的数学公式吓跑,我们就在些略去C和D的计算细节了(有特殊兴趣的读者,可见附件中的Word版 本    )。

(三)巧胜策略

根据定理1,可知,甲乙双方在“石头剪刀布”游戏中的胜负,其实已经事先就“天定”了,某方若想争取更大的胜利,那么,他就必须努力“改变命运”。下面分几种情况来考虑:

3.1:两个傻瓜之间的游戏

所谓“两个傻瓜”,意指甲乙双方都固守自己的习惯,无论过去的输赢情况怎样,他们都按既定习惯“出牌”。这时,从定理1,我们已经知道:如果C<D,那么,整体上甲方会输;如果C>D,那么,整体上甲方会赢;如果C=D,那么,甲乙双方势均力敌。

3.2 一个傻瓜与一个智者之间的游戏

如果甲是傻瓜,他仍然坚持其固有的习惯“出牌”,那么,双方对抗足够多的次数后,乙方就可以计算出对应于甲方的,随机变量X的分布概率pq,以及相关的条件概率分布,并最终计算出“甲方信道”的信道容量,然后,再通过调整自己的习惯(即,随机变量Y的概率分布和相应的条件概率分布等),最终增大自己的“乙方信道”的信道容量,从而,使得后续的游戏对自己更有利;甚至使“乙方信道”的信道容量大于“甲方信道”的信道容量,最终使得自己稳操胜券。

3.3 两个智者之间的游戏

如果甲和乙双方,都随时在总结对方的习惯,并对自己的“出牌”习惯做调整,即,增大自己的信道容量。那么,最终,甲乙双方的“信道容量”值将趋于相等,即,他们之间的游戏竞争将趋于平衡,达到动态稳定的状态。


(四)简化版本

虽然上面几节,完美地解决了“石头剪刀布”游戏问题,但是,它们在保持“直观形象”的优势下,付出了“复杂”的代价。下面,我们再给出一个更抽象,更简捷的解决办法。

设甲与乙玩“石头剪刀布”。他们可分别用随机变量XY来表示:

当甲出拳为剪刀、石头、布时,分别记为X=0X=1X=2

当乙出拳为剪刀、石头、布时,分别记为Y=0Y=1Y=2

根据概率论中的“大数定律”,频率的极限趋于概率,所以甲乙双方的出拳习惯,可以用随机变量XY的概率分布表示为:

0<Pr(X=x)=px<1x=0,1,2p0+p1+p2=1

0<Pr(Y=y)=qy<1y=0,1,2q0+q1+q2=1

0<Pr(X=x,Y=y)=txy<1x,y=0,1,20≤x,y≤2txy=1

px=0≤y≤2txyx=0,1,2

qy=0≤x≤2txyy=0,1,2

“石头剪刀布”游戏的输赢规则是:若X=xY=y,那么,甲(X)赢的充分必要条件是:(y-x)mod3=2

现在构造另一个随机变量F=(Y-2)mod3。考虑由XF构成的信道(XF),即,以X为输入,以F为输出的信道。那么,就有如下事件等式:

若在某个回合中,甲(X)赢了,那么,就有(Y-X)mod3=2,从而,F=(Y-2)mod3=[(2+X)-X]mod3=X,也就是说:信道(XF)的输入(X)始终等于它的输出(F)。换句话说,1个比特就被成功地在该信道中被从发端传输到了收端。

反过来,如果“1个比特就被成功地在该信道中被从发端传输到了收端”,那么,就意味着“信道(XF)的输入(X)始终等于它的输出(F)”,也就是说:F=(Y-2)mod3=X,这刚好就是X赢的充分必要条件。

结合上述正反两个方面的论述,就有:甲(X)赢一次,就意味着信道(XF)成功地把1比特信息,从发端送到了收端;反之亦然。因此,信道(XF)也可以扮演第三节中“甲方信道”的功能。

类似地,若记随机变量G=(X-2)mod3,那么,信道(YG)就可以扮演前面“乙方信道”的角色。

而现在信道(XF)和(YG)的信道容量的形式会更简捷,它们分别是:

XF)的信道容量=MaxX[I(X,F)]=MaxX[I(X,(Y-2)mod3)]=MaxX[I(X,Y)]=MaxX[txylog(txy/(pxqy))],这里的最大值,是针对所有可能的txypx而取的,所以,它实际上是q0q1q2的函数。

同理,

YG)的信道容量=MaxY[I(Y,G)]=MaxY[I(Y,(X-2)mod3)]=MaxY[I(X,Y)]=MaxY[txylog(txy/(pxqy))],这里的最大值,是针对所有可能的txyqy而取的,所以,它实际上是p0p1p2的函数。

其它讨论就与上面几节相同的,不再重复了。


(五)结束语

“攻防”是安全的核心,所以,在建立“安全通论”的过程中,多花一些精力去深入研究“攻防”也是值得的。

[2]中,我们研究了“安全通论”的盲对抗问题,本文研究的“石头剪刀布”游戏则是一种“非盲对抗”,但由于它的普及率极高(几千年来,全世界每个人在童年时代几乎都玩过),所以,我们以单独一篇论文的形式来研究它。有关其它一些有代表性的“非盲对抗”,我们将在随后的文章中研究。

当然,换一个角度来看,也可以说:我们的“安全通论”虽然刚刚诞生,它就大显身手,成功地扫清了古老“石头剪刀布”游戏中的若干迷雾。所以,“安全通论”确定大有前途。

特别说明:这本该是一篇高影响因子的SCI论文,但是,如今国人已被SCI绑架了,所以,老夫想带头摆脱SCI的束搏,故将此文在这里发表。本文欢迎所有媒体转载。


 

安全通论(3),攻防篇之”非盲对抗“之“石头剪刀布”.docx



参考文献

[1]杨义先,钮心忻,安全通论(1)之“经络篇”,见杨义先的科学网实名博客(http://blog.sciencenet.cn/blog-453322-944217.html  

[2]杨义先,钮心忻,安全通论(2):攻防篇之“盲对抗”,见杨义先的科学网实名博客,(http://blog.sciencenet.cn/blog-453322-947304.html

[3]Thomas M. Cover Joy A. Thomas著,信息论基础,机械工业出版社出版,200711月,北京。阮吉寿,张华译;沈世镒审校。

[4]Shu LinDaniel J. Costello,Jr.著,差错控制码,机械工业出版社,20076月,北京。晏坚,何元智,潘亚汉等译。




https://wap.sciencenet.cn/blog-453322-948089.html

上一篇:安全通论(2):攻防篇之“盲对抗”
下一篇:《安全通论》(4):攻防篇之“非盲对抗”之“童趣游戏”

9 武夷山 许培扬 孙学军 黄永义 毕美华 赵凤光 邓松柏 黄华军 ncepuztf

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-5-28 21:59

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部