【信息安全】安全通论（3）——攻防篇之“非盲对抗”之“石头剪刀布”
杨义先，钮心忻
（北京邮电大学 信息安全中心，北京 100876）
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<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。
同样，还可以统计出二维随机变量（X，Y）的联合分布概率：
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。
由随机变量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）如果C<D，那么，整体上甲方会输；如果C>D，那么，整体上甲方会赢；如果C=D，那么，甲乙双方势均力敌。
由于“甲方信道”和“乙方信道”的信道容量都有现成的计算公式，这里略去C和D的计算细节（有特殊兴趣的读者，可阅读原文网址附件中的Word版本）。
2巧胜策略
由定理1可知，甲乙双方在“石头剪刀布”游戏中的胜负，其实事先就已经“天定”了，某方若想争取更大的胜利，那他就必须努力“改变命运”。下面分几种情况来考虑：
（1）两个傻瓜之间的游戏
所谓“两个傻瓜”，意指甲乙双方都固守自己的习惯，无论过去的输赢情况怎样，他们都按既定习惯“出牌”。这时，由定理1已经知道：如果C<D，则整体上甲方会输；如果C>D，则整体上甲方会赢；如果C=D，则甲乙双方势均力敌。
（2）一个傻瓜与一个智者之间的游戏
如果甲是傻瓜，他仍然坚持其固有的习惯“出牌”，那么，双方对抗足够多的次数后，乙方就可以计算出对应于甲方的，随机变量X的分布概率p和q，以及相关的条件概率分布，并最终计算出“甲方信道”的信道容量，然后，再通过调整自己的习惯（即随机变量Y的概率分布和相应的条件概率分布等），最终增大自己的“乙方信道”的信道容量，从而使得后续的游戏对自己更有利；甚至使“乙方信道”的信道容量大于“甲方信道”的信道容量，最终使得自己稳操胜券。
（3）两个智者之间的游戏
如果甲乙双方都随时在总结对方的习惯，并对自己的“出牌”习惯做调整，即增大自己的信道容量。那么，最终甲乙双方的“信道容量”值将趋于相等，即他们之间的游戏竞争将趋于平衡，达到动态稳定的状态。
3简化版本
虽然上面几节完美地解决了“石头剪刀布”游戏问题，但是，它们在保持“直观形象”的优势下，付出了“复杂”的代价。下面，给出一个更抽象、更简捷的解决办法。
设甲与乙玩“石头剪刀布”，他们可分别用随机变量X和Y来表示：
当甲出拳为剪刀、石头、布时，分别记为X=0、X=1、X=2；
当乙出拳为剪刀、石头、布时，分别记为Y=0、Y=1、Y=2。
根据概率论中的“大数定律”，频率的极限趋于概率，所以甲乙双方的出拳习惯可以用随机变量X和Y的概率分布表示为：
0<Pr(X=x)=px<1，x=0,1,2，p0+p1+p2=1；
0<Pr(Y=y)=qy<1，y=0,1,2，q0+q1+q2=1；
0<Pr(X=x,Y=y)=txy<1，x,y=0,1,2，
∑0≤x,y≤2txy=1；
px=∑0≤y≤2txy，x=0,1,2；
qy=∑0≤x≤2txy，y=0,1,2。
“石头剪刀布”游戏的输赢规则是：若X=x，Y=y，那么，甲（X）赢的充分必要条件是：(y-x)mod3=2。
现在构造另一个随机变量F=(Y-2)mod3。考虑由X和F构成的信道（X；F），即，以X为输入，以F为输出的信道。那么，就有如下事件等式：
若在某个回合中，甲（X）赢了，那么就有(Y-X)mod3=2，从而，F=(Y-2)mod3=［(2+X)-X］mod3=X，也就是说：信道（X；F）的输入（X）始终等于它的输出（F）。换句话说，1个比特就被成功地在该信道中从发端传输到了收端。
反过来，如果“1个比特被成功地在该信道中从发端传输到了收端”，那么就意味着“信道（X；F）的输入（X）始终等于它的输出（F）”，也就是说：F=(Y-2)mod3=X，这刚好就是X赢的充分必要条件。
结合上述正反两个方面的论述，有：甲（X）赢一次，就意味着信道（X；F）成功地把1比特信息从发端送到了收端；反之亦然。因此，信道（X；F）也可以扮演第2节中“甲方信道”的功能。
类似地，若记随机变量G=(X-2)mod3，那么，信道（Y；G）就可以扮演前面“乙方信道”的角色。
而信道（X；F）和（Y；G）的信道容量的形式会更简捷，它们分别是：
（X；F）的信道容量=MaxX［I(X,F)］=MaxX［I(X,(Y-2)mod3)］=MaxX［I(X,Y)］=MaxX［∑txylog(txy/(pxqy))］，这里的最大值是针对所有可能的txy和px而取的，所以，它实际上是q0，q1，q2的函数。
同理，（Y；G）的信道容量=MaxY［I(Y,G)］=MaxY［I(Y,(X-2)mod3)］=MaxY［I(X,Y)］=MaxY［∑txylog(txy/(pxqy))］，这里的最大值是针对所有可能的txy和qy而取的，所以，它实际上是p0，p1，p2的函数。
其他讨论与前面几节相同，不再重复。
4结束语
“攻防”是安全的核心，所以，在建立“安全通论”的过程中，多花一些精力去深入研究“攻防”也是值得的。
在参考文献［2］中，研究了“安全通论”的盲对抗问题，本文研究的“石头剪刀布”游戏则是一种“非盲对抗”，但由于它的普及率极高（几千年来，全世界每个人在童年时代几乎都玩过），所以，我们单独以一篇论文的形式来研究它。有关其他一些有代表性的“非盲对抗”，将在后续文章中研究。
当然，换一个角度来看，也可以说，我们的“安全通论”虽然刚刚诞生，但它已大显身手，成功地扫清了古老“石头剪刀布”游戏中的若干迷雾。所以，“安全通论”确定大有前途。
参考文献
［1］ 杨义先，钮心忻.安全通论（1）——经络篇［J］.微型机与应用，2016，35（15）：14.
［2］ 杨义先，钮心忻.安全通论（2）——攻防篇之“盲对抗”［J］.微型机与应用，2016，35（16）：1 5.
［3］ COVER T M， THOMAS J A著.信息论基础［M］，阮吉寿，张华，译.北京：机械工业出版社，2007.
［4］ Lin Shu， COSTELLO JR D J著.差错控制码［M］.晏坚，何元智，潘亚汉，等，译.北京：机械工业出版社，2007.