安全通论(3)<br/>——攻防篇之“非盲对抗”之“石头剪刀布”

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

2016-10-27杨义先钮心忻

网络安全与数据管理 2016年17期

关键词：信道容量乙方甲方

杨义先，钮心忻

(北京邮电大学信息安全中心，北京 100876)

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

杨义先，钮心忻

(北京邮电大学信息安全中心，北京 100876)

编者按：“石头剪刀布”是一种发源于中国的猜拳游戏，是用来产生随机结果以作决策。但有时它并不随机，因为游戏者可以根据经验，判断对手的手法。本文给出了“石头剪刀布”的一种“白富美”新玩法。所谓“白”，即思路清清楚楚、明明白白；所谓“富”，即理论内涵非常丰富；所谓“美”，即结论绝对数学美。《安全通论》的魅力也在这里得到了幽默体现。本文转自《科学网》杨义先教授与钮心忻教授撰写的博文，为与本刊风格一致，我们对文字略作了一些微调。阅读原文可登录以下网址：http://blog.sciencenet.cn/blog-453322-948089.html。

杨义先教授，博士生导师，灾备技术国家工程实验室主任，北京邮电大学信息安全中心主任，教育部网络攻防重点实验室主任，《微型机与应用》编委，主要研究方向：网络空间安全、现代密码学和纠错编码等。

钮心忻博士，教授，博士生导师。北京邮电大学学士和硕士学位，香港中文大学电子工程系博士学位。1997年起在北京邮电大学信息工程学院(现计算机学院)从事教学与科研工作。主要研究方向：网络与信息安全、信号与信息处理等。

0　引言

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

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

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

1　信道建模

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

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

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

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

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

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

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

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

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

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

同样，还可以统计出二维随机变量(X，Y)的联合分布概率：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

综合以上正反两方面，共6种情况，可得到一个重要引理：

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

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

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

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

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

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

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

(3)如果CD，那么，整体上甲方会赢；如果C=D，那么，甲乙双方势均力敌。

由于“甲方信道”和“乙方信道”的信道容量都有现成的计算公式，这里略去C和D的计算细节(有特殊兴趣的读者，可阅读原文网址附件中的Word版本)。

2　巧胜策略

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

(1)两个傻瓜之间的游戏

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

(2)一个傻瓜与一个智者之间的游戏

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

(3)两个智者之间的游戏

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