楊義先，鈕心忻

(北京郵電大學(xué) 信息安全中心，北京 100076)

?

安全通論(4)
——攻防篇之“非盲對抗”之“童趣游戲”

楊義先，鈕心忻

(北京郵電大學(xué) 信息安全中心，北京 100076)

編者按：作者將《安全通論》這個工具用于兩個家喻戶曉的童趣游戲：“猜正反面游戲”和“手心手背游戲”。當然，這些成果亦即成為了《安全通論》攻防篇之“非盲對抗”的重要內(nèi)容。作者用游戲方式來表述，增加了研究工作的趣味性，寓莊于諧，按照作者的話講，可以讓讀者體會一下“如何用大炮打蚊子”——正如作者所說，能打中蚊子的大炮，才是好大炮！

0　引言

以“網(wǎng)絡(luò)空間安全”、“經(jīng)濟安全”、“領(lǐng)土安全”為代表的所有安全問題的核心，就是“對抗”！所以，多花一些篇幅，從不同角度，甚至利用古老游戲來全面深入地研究安全對抗問題是值得的。

“安全經(jīng)絡(luò)”[1]是《安全通論》的第一塊基石?！鞍踩珜埂笔恰栋踩ㄕ摗返牡诙K基石。為了打好這第二塊基石，文獻[2]中研究了兩大安全對抗之一(盲對抗)，并給出了黑客(紅客)攻擊(防守)能力的精確極限；并在文獻[3]中，以著名的“石頭剪刀布游戲”為對象，研究了另一種安全對抗(非盲對抗)，給出了輸贏極限和獲勝技巧。

與“盲對抗”相比，雖然一般來說“非盲對抗”不那么血腥，但是，這絕不意味著“非盲對抗”就容易研究，相反，“非盲對抗”的勝敗規(guī)則等更加千變?nèi)f化。由于“非盲對抗”的外在表現(xiàn)形式千差萬別，因此此文中利用信道容量法來研究兩個家喻戶曉的“非盲對抗”童趣游戲：“猜正反面游戲”和“手心手背游戲”。

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

猜正反面游戲：“莊家”用手把一枚硬幣掩在桌上，“玩家”來猜是“正面”還是“反面”。若猜中，則“玩家”贏；若猜錯，則“莊家”贏。

這個游戲顯然是一種“非盲對抗”。他們到底會誰輸，誰贏呢？怎樣才能贏呢？下面就用看似毫不相關(guān)的“信道容量法”來回答這些問題。

由概率論中的大數(shù)定律，頻率趨于概率，所以，根據(jù)“莊家”和“玩家”的習(xí)慣，即過去的統(tǒng)計規(guī)律，就可以分別給出他們的概率分布：

用隨機變量X代表“莊家”，當他把“正面”向上時，記為X=0；否則，記為X=1。所以，“莊家”的習(xí)慣就可以用X的概率分布來描述，比如，Pr(X=0)=p，Pr(X=1)=1

楊義先

教授，博士生導(dǎo)師，災(zāi)備技術(shù)國家工程實驗室主任，北京郵電大學(xué)信息安全中心主任，教育部網(wǎng)絡(luò)攻防重點實驗室主任，《微型機與應(yīng)用》編委。主要研究方向：網(wǎng)絡(luò)空間安全、現(xiàn)代密碼學(xué)和糾錯編碼等。

鈕心忻

博士，教授，博士生導(dǎo)師。北京郵電大學(xué)學(xué)士和碩士學(xué)位，香港中文大學(xué)電子工程系博士學(xué)位。1997年起在北京郵電大學(xué)信息工程學(xué)院(現(xiàn)計算機學(xué)院)從事教學(xué)與科研工作。主要研究方向：網(wǎng)絡(luò)與信息安全、信號與信息處理等。

-p(1

用隨機變量Y代表“玩家”，當他猜“正面”時，記為Y=0；否則，記為Y=1。所以，“玩家”的習(xí)慣就可以用Y的概率分布來描述，比如，Pr(Y=0)=q，Pr(Y=1)=1-q(1

同樣，根據(jù)過去“莊家”和“玩家”的記錄，可以知道隨機變量(X，Y)的聯(lián)合概率分布，比如：

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

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

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

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

這里各個參數(shù)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信息被從“莊家信道”的發(fā)送端X成功地傳輸?shù)搅耸招哦薡}，所以，“玩家”每贏一次，就相當于“莊家信道”成功地傳輸了1 bit信息。由此，再結(jié)合仙農(nóng)信息論的著名“信道編碼定理”[4-5]：如果“莊家信道”的容量為C，那么，對于任意傳輸率k/n≤C，都可以在譯碼錯誤概率任意小的情況下，通過某個n比特長的碼字，成功地把k個比特傳輸?shù)绞招哦恕７催^來，如果“莊家信道”能夠用n長碼字把Sbit信息無誤差地傳輸?shù)绞斩?，那么，一定有S≤nC。把這段話翻譯一下，便有如下定理：

定理1(莊家定理)：設(shè)由隨機變量(X，Y)組成的“莊家信道”的信道容量為C。那么:(1)如果玩家想勝k次，那么，一定有某種技巧(對應(yīng)于仙農(nóng)編碼)，使得他能夠在k/C次游戲中以任意接近1的概率達到目的；(2)反過來，如果玩家在n次游戲中贏了S次，那么，一定有S≤nC。

由定理1可知，只要求出“莊家信道”的信道容量C，那么，玩家獲勝的極限就確定了。下面來求“莊家信道”的轉(zhuǎn)移概率矩陣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

設(shè)隨機變量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信息被從“玩家信道”的發(fā)送端Y成功地傳輸?shù)搅耸招哦薢}，因此，“莊家”每贏一次，就相當于“玩家信道”成功地傳輸了1 bit信息。由此，再結(jié)合仙農(nóng)信息論的著名“信道編碼定理”[4-5]可得：如果“玩家信道”的容量為D，那么，對于任意傳輸率k/n≤D，都可以在譯碼錯誤概率任意小的情況下，通過某個nbit長的碼字，成功地把k個比特傳輸?shù)绞招哦?。反過來，如果“玩家信道”能夠用n長碼字把Sbit信息無誤差地傳輸?shù)绞斩?，那么，一定有S≤nD。把這段話翻譯一下，便有如下定理2。

定理2(玩家定理)：設(shè)由隨機變量(Y，Z)組成的“玩家信道”的信道容量為D。那么：(1)如果莊家想勝k次，那么，一定有某種技巧(對應(yīng)于仙農(nóng)編碼)，使得他能夠在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)]]

一是要充分利用退伍轉(zhuǎn)業(yè)軍人。從國家層面，要加強立法，嚴格執(zhí)法，通過完善和落實預(yù)備役登記制度及約束措施，確保把退伍、復(fù)員、轉(zhuǎn)業(yè)、自主擇業(yè)等有服現(xiàn)役經(jīng)歷的人全部納入管理范圍，為參加預(yù)備役組織提供政策保障。對于預(yù)備役部隊而言，要采取多種渠道掌握信息，特別是要加強與省軍區(qū)系統(tǒng)兵役機關(guān)的溝通協(xié)調(diào)，并結(jié)合每年一度的預(yù)備役整組搞好潛力調(diào)查，確保把有現(xiàn)役經(jīng)歷的人優(yōu)先作為預(yù)任軍官、預(yù)編士兵對象，最大限度利用軍事資源。原則上，預(yù)備役軍官中服現(xiàn)役經(jīng)歷的比例不低于90%，預(yù)備役士兵中服現(xiàn)役經(jīng)歷的比例不低于70%。

結(jié)合定理1和定理2，便可以對“莊家和玩家的最終輸贏情況”以及“玩家和莊家的游戲技巧”給出一個量化的結(jié)果，即定理3。

定理3(實力定理)：在“猜正反面游戲”中，如果“莊家信道”和“玩家信道”的信道容量分別是C(q)和D(p)，那么有以下3種情況:

情況1：如果莊家和玩家都是老實人，即他們在游戲過程中不試圖去調(diào)整自己的習(xí)慣，即p和q都恒定不變。那么，如果C(q)大于D(p)，則總體上玩家會贏；如果C(q)小于D(p)，則總體上莊家贏；如果C(q)=D(p)，則總體上玩家和莊家持平。

情況2：如果莊家和玩家中的某一方(比如玩家)是老實人，但是另一方(比如莊家)卻不老實，他會悄悄調(diào)整自己的習(xí)慣，即改變隨機變量X的概率分布p，使得“玩家信道”的D(p)變大，并最終大于“莊家信道”的C(q)，那么，莊家將整體上贏得該游戲。反之，若只有莊家是老實人，那么玩家也可以通過調(diào)整自己的習(xí)慣，即調(diào)整Y的概率分布q，使得“莊家信道”的C(q)變大，并最終大于“玩家信道”的D(p)，那么玩家將整體上贏得該游戲。

情況3：如果玩家和莊家都不是老實人，他們都在不斷地調(diào)整自己的習(xí)慣，使C(q)和D(p)不斷變大，出現(xiàn)“水漲船高”的態(tài)勢，那么最終他們將在p=q=0.5的地方達到動態(tài)平衡，此時他們都沒有輸贏?！安抡疵嬗螒颉背霈F(xiàn)“握手言和”的局面。

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

手心手背游戲：三個小朋友，同時亮出自己的“手心”或“手背”，如果其中某個小朋友的手勢與別人的相反(比如，別人都出“手心”，他卻出“手背”)，那么他在本次游戲中就贏了。

這個家喻戶曉的游戲顯然也是一種“非盲對抗”，只不過相互對抗的是三人而非常見的二人。他們到底誰會輸，誰會贏呢？他們怎樣才能贏呢？下面仍然用“信道容量法”來回答這些問題。

由概率論中的大數(shù)定律，頻率趨于概率，所以，根據(jù)甲、乙、丙過去習(xí)慣的統(tǒng)計規(guī)律就可以分別給出他們的概率分布。

用隨機變量X代表甲，當他出“手心”時，記為X=0；出“手背”時，記為X=1。所以，甲的習(xí)慣就可以用X的概率分布來描述，比如，Pr(X=0)=p，Pr(X=1)=1-p(1

用隨機變量Z代表丙，當他出“手心”時，記為Z=0；出“手背”時，記為Z=1。所以，丙的習(xí)慣就可以用Z的概率分布來描述，比如，Pr(Z=0)=r，Pr(Z=1)=1-r(1

同樣，由大數(shù)定律的“頻率趨于概率”可知，先讓甲乙丙三個小朋友玩一段時間后，根據(jù)他們的游戲結(jié)果情況，就可以知道隨機變量(X，Y，Z)的聯(lián)合概率分布，比如，

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

這里各個參數(shù)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

設(shè)隨機變量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信息被成功地在“甲信道”中從發(fā)端(X)傳輸?shù)绞斩?M)}。

反過來，在剔除三個小朋友的手勢相同的情況后，若{1 bit信息被成功地在“甲信道”中從發(fā)端(X)傳輸?shù)绞斩?M)}，那么就有{X=0,M=0}∪{X=1,M=1}= {X=0,Y=1,Z=1}∪{X=1,Y=0,Z=0}={甲手心，乙手背，丙手背}∪{甲手背，乙手心，丙手心}={甲贏}。所以，甲每贏一次，就相當于“甲信道”成功地把1 bit信息從發(fā)端X傳輸?shù)搅耸斩薓。由此，再結(jié)合仙農(nóng)信息論的著名“信道編碼定理”[4-5]：如果“甲信道”的容量為E，那么，對于任意傳輸率k/n≤E，都可以在譯碼錯誤概率任意小的情況下，通過某個nbit長的碼字成功地把k個比特傳輸?shù)绞招哦?。反過來，如果“甲信道”能夠用n長碼字，把Sbit信息無誤差地傳輸?shù)绞斩耍敲匆欢ㄓ蠸≤nE。把這段話翻譯一下，便有如下定理：

定理4：設(shè)由隨機變量(X,M)組成的“甲信道”的信道容量為E。那么，在剔除平局(即三人的手勢相同)的情況下：(1)如果甲想贏k次，那么一定有某種技巧(對應(yīng)于仙農(nóng)編碼)，使得他能夠在k/E次游戲中，以任意接近1的概率達到目的；(2)反過來，如果甲在n次游戲中贏了S次，那么一定有S≤nE。

為了計算信道(X,M)的信道容量，首先來計算隨機變量(X，M)的聯(lián)合概率分布：

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)]，這里的最大值是針對自然數(shù)0

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

定理5：設(shè)由隨機變量(Y,M)組成的“乙信道”的信道容量為F。那么在剔除平局(即三人的手勢相同)的情況下；(1)如果乙想贏k次，那么一定有某種技巧(對應(yīng)于仙農(nóng)編碼)，使得他能夠在k/F次游戲中以任意接近1的概率達到目的；(2)反過來，如果乙在n次游戲中贏了S次，那么一定有S≤nF。

關(guān)于信道容量F的值，可以完全仿照E值來計算，不過，“乙信道”的容量其實是p和r的函數(shù)，可以記為F(p,r)。

同樣，再考慮信道(Z,M)，即以Z為輸入，以M為輸出的信道，稱之為“丙信道”。由于在“手心手背”游戲中，甲乙丙的地位是相同的，因此，仿照定理4，就有了定理6。

定理6：設(shè)由隨機變量(Z,M)組成的“乙信道”的信道容量為G。那么，在剔除平局(即三人的手勢相同)的情況下：(1)如果丙想贏k次，那么一定有某種技巧(對應(yīng)于仙農(nóng)編碼)，使得他能夠在k/G次游戲中以任意接近1的概率達到目的；(2)反過來，如果乙在n次游戲中贏了S次，那么，一定有S≤nG。

關(guān)于信道容量G的值，可以完全仿照E值來計算，不過，“丙信道”的容量其實是p和q的函數(shù)，可以記為G(p,q)。

結(jié)合定理4、5、6，便可以對甲、乙、丙三方在“手心手背”游戲中的宏觀輸贏情況進行如下描述，即定理7。

定理7：在“手心手背游戲”中，如果“甲信道”、“乙信道”和“丙信道”的信道容量分別是E、F和G，那么，在該游戲中，甲、乙、丙三方的最終輸贏情況，整體上依賴于E、F和G的大小，誰的信道容量大，誰就占優(yōu)勢。注意到這三個信道容量不能由任何一方單獨調(diào)整，除非有某兩方合謀，否則，很難通過改變自己的習(xí)慣(即單獨改變p,q或r)來改變最終的輸贏情況。

3　結(jié)論

本文的游戲和參考文獻[3]中的“石頭剪刀布游戲”看似千差萬別，但是卻巧妙地應(yīng)用了一個幾乎相同的方法，給出了出人意料的答案，即建立某個信道，把攻防某方的“一次勝利”轉(zhuǎn)化為“1 bit信息在該信道中被成功傳輸”，于是，利用仙農(nóng)編碼定理，攻防雙方的對抗問題就轉(zhuǎn)化為了信道容量的計算問題了。

當然，安全通論之“信道容量法”的威力還遠不止于此。

[1] 楊義先，鈕心忻，安全通論(1)——經(jīng)絡(luò)篇[J].微型機與應(yīng)用，2016,35(15)：1-4.

[2] 楊義先，鈕心忻，安全通論(2)——攻防篇之“盲對抗”[J]，微型機與應(yīng)用，2016,35(16)：1-5.

[3] 楊義先，鈕心忻，安全通論(3)——攻防篇之“非盲對抗”之“石頭剪刀布”[J].微型機與應(yīng)用，2016,35(17)：1-3.

[4] COVER T M， THOMAS J A.信息論基礎(chǔ)[M].阮吉壽，張華,譯. 北京:機械工業(yè)出版社，2007.

[5] Lin Shu ,COSTELLO D J. 差錯控制編碼[M]. 晏堅, 何元智, 潘亞漢, 等, 譯. 北京: 機械工業(yè)出版社, 2007.