安全通论(4)<br/>——攻防篇之“非盲对抗”之“童趣游戏”

安全通论(4)
——攻防篇之“非盲对抗”之“童趣游戏”

2016-10-28杨义先钮心忻

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

关键词：信道容量庄家手背

杨义先，钮心忻

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

安全通论(4)
——攻防篇之“非盲对抗”之“童趣游戏”

杨义先，钮心忻

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

编者按：作者将《安全通论》这个工具用于两个家喻户晓的童趣游戏：“猜正反面游戏”和“手心手背游戏”。当然，这些成果亦即成为了《安全通论》攻防篇之“非盲对抗”的重要内容。作者用游戏方式来表述，增加了研究工作的趣味性，寓庄于谐，按照作者的话讲，可以让读者体会一下“如何用大炮打蚊子”——正如作者所说，能打中蚊子的大炮，才是好大炮！

0　引言

以“网络空间安全”、“经济安全”、“领土安全”为代表的所有安全问题的核心，就是“对抗”！所以，多花一些篇幅，从不同角度，甚至利用古老游戏来全面深入地研究安全对抗问题是值得的。

“安全经络”[1]是《安全通论》的第一块基石。“安全对抗”是《安全通论》的第二块基石。为了打好这第二块基石，文献[2]中研究了两大安全对抗之一(盲对抗)，并给出了黑客(红客)攻击(防守)能力的精确极限；并在文献[3]中，以著名的“石头剪刀布游戏”为对象，研究了另一种安全对抗(非盲对抗)，给出了输赢极限和获胜技巧。

与“盲对抗”相比，虽然一般来说“非盲对抗”不那么血腥，但是，这绝不意味着“非盲对抗”就容易研究，相反，“非盲对抗”的胜败规则等更加千变万化。由于“非盲对抗”的外在表现形式千差万别，因此此文中利用信道容量法来研究两个家喻户晓的“非盲对抗”童趣游戏：“猜正反面游戏”和“手心手背游戏”。

1　“猜正反面游戏”的信道容量法

猜正反面游戏：“庄家”用手把一枚硬币掩在桌上，“玩家”来猜是“正面”还是“反面”。若猜中，则“玩家”赢；若猜错，则“庄家”赢。

这个游戏显然是一种“非盲对抗”。他们到底会谁输，谁赢呢？怎样才能赢呢？下面就用看似毫不相关的“信道容量法”来回答这些问题。

由概率论中的大数定律，频率趋于概率，所以，根据“庄家”和“玩家”的习惯，即过去的统计规律，就可以分别给出他们的概率分布：

用随机变量X代表“庄家”，当他把“正面”向上时，记为X=0；否则，记为X=1。所以，“庄家”的习惯就可以用X的概率分布来描述，比如，Pr(X=0)=p，Pr(X=1)=1

杨义先

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

钮心忻

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

-p(1

用随机变量Y代表“玩家”，当他猜“正面”时，记为Y=0；否则，记为Y=1。所以，“玩家”的习惯就可以用Y的概率分布来描述，比如，Pr(Y=0)=q，Pr(Y=1)=1-q(1

同样，根据过去“庄家”和“玩家”的记录，可以知道随机变量(X，Y)的联合概率分布，比如：

Pr(X=0,Y=0)=a；

Pr(X=0,Y=1)=b；

Pr(X=1,Y=0)=c；

Pr(X=1,Y=1)=d。

这里各个参数0

a+b+c+d=1；

p=Pr(X=0)=Pr(X=0,Y=0)+Pr(X=0,Y=1)=a+b；

q=Pr(Y=0)=Pr(X=0,Y=0)+Pr(X=1,Y=0)=a+c。

考虑信道(X，Y)，即以X为输入，以Y为输出的信道，称之为“庄家信道”。

由于有事件等式：{玩家猜中}={X=0，Y=0}∪{X=1，Y=1}={1 bit信息被从“庄家信道”的发送端X成功地传输到了收信端Y}，所以，“玩家”每赢一次，就相当于“庄家信道”成功地传输了1 bit信息。由此，再结合仙农信息论的著名“信道编码定理”[4-5]：如果“庄家信道”的容量为C，那么，对于任意传输率k/n≤C，都可以在译码错误概率任意小的情况下，通过某个n比特长的码字，成功地把k个比特传输到收信端。反过来，如果“庄家信道”能够用n长码字把Sbit信息无误差地传输到收端，那么，一定有S≤nC。把这段话翻译一下，便有如下定理：

定理1(庄家定理)：设由随机变量(X，Y)组成的“庄家信道”的信道容量为C。那么:(1)如果玩家想胜k次，那么，一定有某种技巧(对应于仙农编码)，使得他能够在k/C次游戏中以任意接近1的概率达到目的；(2)反过来，如果玩家在n次游戏中赢了S次，那么，一定有S≤nC。

由定理1可知，只要求出“庄家信道”的信道容量C，那么，玩家获胜的极限就确定了。下面来求“庄家信道”的转移概率矩阵A=[A(i,j)],i,j=0,1：

A(0,0)=Pr(Y=0│X=0)=Pr(Y=0,X=0)/Pr(X=0)=a/p;

A(0,1)=Pr(Y=1│X=0)=Pr(Y=1,X=0)/Pr(X=0)=b/p=1-a/p;

A(1,0)=Pr(Y=0│X=1)=Pr(Y=0,X=1)/Pr(X=1)=c/(1-p)=(q-a)/(1-p);

A(1,1)=Pr(Y=1│X=1)=Pr(Y=1,X=1)/Pr(X=1)=d/(1-p)=1-(q-a)/(1-p)。

于是，X与Y之间的互信息I(X，Y)如下：

I(X,Y)

=∑X∑Yp(X,Y)log(p(X,Y)/[p(X)p(Y)])

=alog[a/(pq)]+blog[b/[p(1-q)]]

+clog[c/[(1-p)q]]+dlog[d/[(1-p)(1-q)]]

=alog[a/(pq)]+(p-a)log[(p-a)/[p(1-q)]]

+(q-a)log[(q-a)/[(1-p)q]]+(1+a-p-q)log[(1+a-p-q)/[(1-p)(1-q)]]

所以，“庄家信道”的信道容量C就等于Max[I(X,Y)](这里的最大值是对所有可能的二元随机变量X来取的)，或者更简单地说：

C=Max[I(X,Y)]0

设随机变量Z=(X+1)mod2。下面再考虑另一个信道(Y，Z)，它以Y为输入，以Z为输出，称该信道为“玩家信道”。

由于有事件等式：{庄家赢}={Y=0，X=1}∪{Y=1，X=0}={Y=0，Z=0}∪{Y=1，Z=1}={1 bit信息被从“玩家信道”的发送端Y成功地传输到了收信端Z}，因此，“庄家”每赢一次，就相当于“玩家信道”成功地传输了1 bit信息。由此，再结合仙农信息论的著名“信道编码定理”[4-5]可得：如果“玩家信道”的容量为D，那么，对于任意传输率k/n≤D，都可以在译码错误概率任意小的情况下，通过某个nbit长的码字，成功地把k个比特传输到收信端。反过来，如果“玩家信道”能够用n长码字把Sbit信息无误差地传输到收端，那么，一定有S≤nD。把这段话翻译一下，便有如下定理2。

定理2(玩家定理)：设由随机变量(Y，Z)组成的“玩家信道”的信道容量为D。那么：(1)如果庄家想胜k次，那么，一定有某种技巧(对应于仙农编码)，使得他能够在k/D次游戏中以任意接近1的概率达到目的；(2)反过来，如果庄家在n次游戏中赢了S次，那么，一定有S≤nD。

由定理2可知，只要求出“玩家信道”的信道容量D，那么，庄家获胜的极限就确定了。

与上面求“庄家信道”的步骤类似，可以求出“玩家信道”的信道容量D=Max[I(Y,Z)]0

I(Y,Z)=∑Y∑Zp(Y,Z)log(p(Y,Z)/[p(Y)p(Z)])

=alog[a/(pq)]+(p-a)log[(p-a)/[p(1-q)]]+

(q-a)log[(q-a)/[(1-p)q]]+(1+a-p-q)log[(1+a-p-q)/[(1-p)(1-q)]]

一是要充分利用退伍转业军人。从国家层面，要加强立法，严格执法，通过完善和落实预备役登记制度及约束措施，确保把退伍、复员、转业、自主择业等有服现役经历的人全部纳入管理范围，为参加预备役组织提供政策保障。对于预备役部队而言，要采取多种渠道掌握信息，特别是要加强与省军区系统兵役机关的沟通协调，并结合每年一度的预备役整组搞好潜力调查，确保把有现役经历的人优先作为预任军官、预编士兵对象，最大限度利用军事资源。原则上，预备役军官中服现役经历的比例不低于90%，预备役士兵中服现役经历的比例不低于70%。

结合定理1和定理2，便可以对“庄家和玩家的最终输赢情况”以及“玩家和庄家的游戏技巧”给出一个量化的结果，即定理3。

定理3(实力定理)：在“猜正反面游戏”中，如果“庄家信道”和“玩家信道”的信道容量分别是C(q)和D(p)，那么有以下3种情况:

情况1：如果庄家和玩家都是老实人，即他们在游戏过程中不试图去调整自己的习惯，即p和q都恒定不变。那么，如果C(q)大于D(p)，则总体上玩家会赢；如果C(q)小于D(p)，则总体上庄家赢；如果C(q)=D(p)，则总体上玩家和庄家持平。

情况2：如果庄家和玩家中的某一方(比如玩家)是老实人，但是另一方(比如庄家)却不老实，他会悄悄调整自己的习惯，即改变随机变量X的概率分布p，使得“玩家信道”的D(p)变大，并最终大于“庄家信道”的C(q)，那么，庄家将整体上赢得该游戏。反之，若只有庄家是老实人，那么玩家也可以通过调整自己的习惯，即调整Y的概率分布q，使得“庄家信道”的C(q)变大，并最终大于“玩家信道”的D(p)，那么玩家将整体上赢得该游戏。

情况3：如果玩家和庄家都不是老实人，他们都在不断地调整自己的习惯，使C(q)和D(p)不断变大，出现“水涨船高”的态势，那么最终他们将在p=q=0.5的地方达到动态平衡，此时他们都没有输赢。“猜正反面游戏”出现“握手言和”的局面。

2　“手心手背游戏”的信道容量法

手心手背游戏：三个小朋友，同时亮出自己的“手心”或“手背”，如果其中某个小朋友的手势与别人的相反(比如，别人都出“手心”，他却出“手背”)，那么他在本次游戏中就赢了。

这个家喻户晓的游戏显然也是一种“非盲对抗”，只不过相互对抗的是三人而非常见的二人。他们到底谁会输，谁会赢呢？他们怎样才能赢呢？下面仍然用“信道容量法”来回答这些问题。

由概率论中的大数定律，频率趋于概率，所以，根据甲、乙、丙过去习惯的统计规律就可以分别给出他们的概率分布。

用随机变量X代表甲，当他出“手心”时，记为X=0；出“手背”时，记为X=1。所以，甲的习惯就可以用X的概率分布来描述，比如，Pr(X=0)=p，Pr(X=1)=1-p(1

用随机变量Z代表丙，当他出“手心”时，记为Z=0；出“手背”时，记为Z=1。所以，丙的习惯就可以用Z的概率分布来描述，比如，Pr(Z=0)=r，Pr(Z=1)=1-r(1

同样，由大数定律的“频率趋于概率”可知，先让甲乙丙三个小朋友玩一段时间后，根据他们的游戏结果情况，就可以知道随机变量(X，Y，Z)的联合概率分布，比如，

Pr(甲手心，乙手心，丙手心)=Pr(X=0，Y=0，Z=0)=a

Pr(甲手心，乙手心，丙手背)=Pr(X=0，Y=0，Z=1)=b

Pr(甲手心，乙手背，丙手心)=Pr(X=0，Y=1，Z=0)=c

Pr(甲手心，乙手背，丙手背)=Pr(X=0，Y=1，Z=1)=d

Pr(甲手背，乙手心，丙手心)=Pr(X=1，Y=0，Z=0)=e

Pr(甲手背，乙手心，丙手背)=Pr(X=1，Y=0，Z=1)=f

Pr(甲手背，乙手背，丙手心)=Pr(X=1，Y=1，Z=0)=g

Pr(甲手背，乙手背，丙手背)=Pr(X=1，Y=1，Z=1)=h

这里各个参数0

a+b+c+d+e+f+g+h=1;

p=Pr(甲手心)=Pr(X=0)=a+b+c+d

q=Pr(乙手心)=Pr(Y=0)=a+b+e+f

r=Pr(丙手心)=Pr(Z=0)=a+c+e+g

设随机变量M=(X+Y+Z)mod2，于是，M的概率分布为：

Pr(M=0)

=Pr(X=0,Y=0,Z=0)+Pr(X=0,Y=1,Z=1)+

Pr(X=1,Y=1,Z=0)+Pr(X=1,Y=0,Z=1)

=a+d+g+f

Pr(M=1)

=Pr(X=0,Y=0,Z=1)+Pr(X=0,Y=1,Z=0)+Pr(X=1,Y=0,Z=0)+Pr(X=1,Y=1,Z=1)

=b+c+e+h

再考虑信道(X，M)，即以X为输入、以M为输出的信道，称之为“甲信道”。

若剔除三个小朋友的手势相同的情况，那么，由于有事件等式：

{甲赢}={甲手心，乙手背，丙手背}∪{甲手背，乙手心，丙手心}={X=0,Y=1,Z=1}∪{X=1,Y=0,Z=0}={X=0,M=0}∪{X=1,M=1}={1 bit信息被成功地在“甲信道”中从发端(X)传输到收端(M)}。

反过来，在剔除三个小朋友的手势相同的情况后，若{1 bit信息被成功地在“甲信道”中从发端(X)传输到收端(M)}，那么就有{X=0,M=0}∪{X=1,M=1}= {X=0,Y=1,Z=1}∪{X=1,Y=0,Z=0}={甲手心，乙手背，丙手背}∪{甲手背，乙手心，丙手心}={甲赢}。所以，甲每赢一次，就相当于“甲信道”成功地把1 bit信息从发端X传输到了收端M。由此，再结合仙农信息论的著名“信道编码定理”[4-5]：如果“甲信道”的容量为E，那么，对于任意传输率k/n≤E，都可以在译码错误概率任意小的情况下，通过某个nbit长的码字成功地把k个比特传输到收信端。反过来，如果“甲信道”能够用n长码字，把Sbit信息无误差地传输到收端，那么一定有S≤nE。把这段话翻译一下，便有如下定理：

定理4：设由随机变量(X,M)组成的“甲信道”的信道容量为E。那么，在剔除平局(即三人的手势相同)的情况下：(1)如果甲想赢k次，那么一定有某种技巧(对应于仙农编码)，使得他能够在k/E次游戏中，以任意接近1的概率达到目的；(2)反过来，如果甲在n次游戏中赢了S次，那么一定有S≤nE。

为了计算信道(X,M)的信道容量，首先来计算随机变量(X，M)的联合概率分布：

Pr(X=0,M=0)=Pr(X=0,Y=0,Z=0)+Pr(X=0,Y=1,Z=1)=a+d

Pr(X=0,M=1)=Pr(X=0,Y=1,Z=0)+Pr(X=0,Y=0,Z=1)=c+b

Pr(X=1,M=0)=Pr(X=1,Y=1,Z=0)+Pr(X=1,Y=0,Z=1)=g+f

Pr(X=1,M=1)=Pr(X=1,Y=0,Z=0)+Pr(X=1,Y=1,Z=1)=e+h

所以，随机变量X和M之间的互信息就等于：I(X,M)

=(a+d)log[(a+d)/[p(a+d+g+f)]]+

(g+f)log[(g+f)/[(1-p)(a+d+g+f)]]+

(c+b)log[(c+b)/[p(b+c+e+h)]]+

(e+h)log[(e+h)/[(1-p)(b+c+e+h)]]

=(a+d)log[(a+d)/[p(a+d+g+f)]]+

(g+f)log[(g+f)/[(1-p)(a+d+g+f)]]+

(p-a-d)log[(p-a-d)/[p(1-(a+d+f+g))]]+

(1-(p+f+g))log[(1-(p+f+g))/[(1-p)(1-(a+d+f+g))]]

于是，“甲信道”的信道容量就等于E=Max[I(X,M)]，这里的最大值是针对自然数0

再考虑信道(Y,M)，即以Y为输入，以M为输出的信道，称之为“乙信道”。由于在“手心手背”游戏中，甲、乙、丙的地位是相同的，因此，仿照定理4，就有定理5。

定理5：设由随机变量(Y,M)组成的“乙信道”的信道容量为F。那么在剔除平局(即三人的手势相同)的情况下；(1)如果乙想赢k次，那么一定有某种技巧(对应于仙农编码)，使得他能够在k/F次游戏中以任意接近1的概率达到目的；(2)反过来，如果乙在n次游戏中赢了S次，那么一定有S≤nF。

关于信道容量F的值，可以完全仿照E值来计算，不过，“乙信道”的容量其实是p和r的函数，可以记为F(p,r)。

同样，再考虑信道(Z,M)，即以Z为输入，以M为输出的信道，称之为“丙信道”。由于在“手心手背”游戏中，甲乙丙的地位是相同的，因此，仿照定理4，就有了定理6。

定理6：设由随机变量(Z,M)组成的“乙信道”的信道容量为G。那么，在剔除平局(即三人的手势相同)的情况下：(1)如果丙想赢k次，那么一定有某种技巧(对应于仙农编码)，使得他能够在k/G次游戏中以任意接近1的概率达到目的；(2)反过来，如果乙在n次游戏中赢了S次，那么，一定有S≤nG。

关于信道容量G的值，可以完全仿照E值来计算，不过，“丙信道”的容量其实是p和q的函数，可以记为G(p,q)。

结合定理4、5、6，便可以对甲、乙、丙三方在“手心手背”游戏中的宏观输赢情况进行如下描述，即定理7。

定理7：在“手心手背游戏”中，如果“甲信道”、“乙信道”和“丙信道”的信道容量分别是E、F和G，那么，在该游戏中，甲、乙、丙三方的最终输赢情况，整体上依赖于E、F和G的大小，谁的信道容量大，谁就占优势。注意到这三个信道容量不能由任何一方单独调整，除非有某两方合谋，否则，很难通过改变自己的习惯(即单独改变p,q或r)来改变最终的输赢情况。