楊義先,鈕心忻
(北京郵電大學(xué) 信息安全中心,北京 100076)
?
安全通論(4)
——攻防篇之“非盲對(duì)抗”之“童趣游戲”
楊義先,鈕心忻
(北京郵電大學(xué) 信息安全中心,北京 100076)
編者按:作者將《安全通論》這個(gè)工具用于兩個(gè)家喻戶(hù)曉的童趣游戲:“猜正反面游戲”和“手心手背游戲”。當(dāng)然,這些成果亦即成為了《安全通論》攻防篇之“非盲對(duì)抗”的重要內(nèi)容。作者用游戲方式來(lái)表述,增加了研究工作的趣味性,寓莊于諧,按照作者的話(huà)講,可以讓讀者體會(huì)一下“如何用大炮打蚊子”——正如作者所說(shuō),能打中蚊子的大炮,才是好大炮!
以“網(wǎng)絡(luò)空間安全”、“經(jīng)濟(jì)安全”、“領(lǐng)土安全”為代表的所有安全問(wèn)題的核心,就是“對(duì)抗”!所以,多花一些篇幅,從不同角度,甚至利用古老游戲來(lái)全面深入地研究安全對(duì)抗問(wèn)題是值得的。
“安全經(jīng)絡(luò)”[1]是《安全通論》的第一塊基石?!鞍踩珜?duì)抗”是《安全通論》的第二塊基石。為了打好這第二塊基石,文獻(xiàn)[2]中研究了兩大安全對(duì)抗之一(盲對(duì)抗),并給出了黑客(紅客)攻擊(防守)能力的精確極限;并在文獻(xiàn)[3]中,以著名的“石頭剪刀布游戲”為對(duì)象,研究了另一種安全對(duì)抗(非盲對(duì)抗),給出了輸贏(yíng)極限和獲勝技巧。
與“盲對(duì)抗”相比,雖然一般來(lái)說(shuō)“非盲對(duì)抗”不那么血腥,但是,這絕不意味著“非盲對(duì)抗”就容易研究,相反,“非盲對(duì)抗”的勝敗規(guī)則等更加千變?nèi)f化。由于“非盲對(duì)抗”的外在表現(xiàn)形式千差萬(wàn)別,因此此文中利用信道容量法來(lái)研究?jī)蓚€(gè)家喻戶(hù)曉的“非盲對(duì)抗”童趣游戲:“猜正反面游戲”和“手心手背游戲”。
猜正反面游戲:“莊家”用手把一枚硬幣掩在桌上,“玩家”來(lái)猜是“正面”還是“反面”。若猜中,則“玩家”贏(yíng);若猜錯(cuò),則“莊家”贏(yíng)。
這個(gè)游戲顯然是一種“非盲對(duì)抗”。他們到底會(huì)誰(shuí)輸,誰(shuí)贏(yíng)呢?怎樣才能贏(yíng)呢?下面就用看似毫不相關(guān)的“信道容量法”來(lái)回答這些問(wèn)題。
由概率論中的大數(shù)定律,頻率趨于概率,所以,根據(jù)“莊家”和“玩家”的習(xí)慣,即過(guò)去的統(tǒng)計(jì)規(guī)律,就可以分別給出他們的概率分布:
用隨機(jī)變量X代表“莊家”,當(dāng)他把“正面”向上時(shí),記為X=0;否則,記為X=1。所以,“莊家”的習(xí)慣就可以用X的概率分布來(lái)描述,比如,Pr(X=0)=p,Pr(X=1)=1
楊義先
教授,博士生導(dǎo)師,災(zāi)備技術(shù)國(guó)家工程實(shí)驗(yàn)室主任,北京郵電大學(xué)信息安全中心主任,教育部網(wǎng)絡(luò)攻防重點(diǎn)實(shí)驗(yàn)室主任,《微型機(jī)與應(yīng)用》編委。主要研究方向:網(wǎng)絡(luò)空間安全、現(xiàn)代密碼學(xué)和糾錯(cuò)編碼等。
鈕心忻
博士,教授,博士生導(dǎo)師。北京郵電大學(xué)學(xué)士和碩士學(xué)位,香港中文大學(xué)電子工程系博士學(xué)位。1997年起在北京郵電大學(xué)信息工程學(xué)院(現(xiàn)計(jì)算機(jī)學(xué)院)從事教學(xué)與科研工作。主要研究方向:網(wǎng)絡(luò)與信息安全、信號(hào)與信息處理等。
-p(1
用隨機(jī)變量Y代表“玩家”,當(dāng)他猜“正面”時(shí),記為Y=0;否則,記為Y=1。所以,“玩家”的習(xí)慣就可以用Y的概率分布來(lái)描述,比如,Pr(Y=0)=q,Pr(Y=1)=1-q(1 同樣,根據(jù)過(guò)去“莊家”和“玩家”的記錄,可以知道隨機(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。 這里各個(gè)參數(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為輸出的信道,稱(chēng)之為“莊家信道”。 由于有事件等式:{玩家猜中}={X=0,Y=0}∪{X=1,Y=1}={1 bit信息被從“莊家信道”的發(fā)送端X成功地傳輸?shù)搅耸招哦薡},所以,“玩家”每贏(yíng)一次,就相當(dāng)于“莊家信道”成功地傳輸了1 bit信息。由此,再結(jié)合仙農(nóng)信息論的著名“信道編碼定理”[4-5]:如果“莊家信道”的容量為C,那么,對(duì)于任意傳輸率k/n≤C,都可以在譯碼錯(cuò)誤概率任意小的情況下,通過(guò)某個(gè)n比特長(zhǎng)的碼字,成功地把k個(gè)比特傳輸?shù)绞招哦?。反過(guò)來(lái),如果“莊家信道”能夠用n長(zhǎng)碼字把Sbit信息無(wú)誤差地傳輸?shù)绞斩耍敲?,一定有S≤nC。把這段話(huà)翻譯一下,便有如下定理: 定理1(莊家定理):設(shè)由隨機(jī)變量(X,Y)組成的“莊家信道”的信道容量為C。那么:(1)如果玩家想勝k次,那么,一定有某種技巧(對(duì)應(yīng)于仙農(nóng)編碼),使得他能夠在k/C次游戲中以任意接近1的概率達(dá)到目的;(2)反過(guò)來(lái),如果玩家在n次游戲中贏(yíng)了S次,那么,一定有S≤nC。 由定理1可知,只要求出“莊家信道”的信道容量C,那么,玩家獲勝的極限就確定了。下面來(lái)求“莊家信道”的轉(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)](這里的最大值是對(duì)所有可能的二元隨機(jī)變量X來(lái)取的),或者更簡(jiǎn)單地說(shuō): C=Max[I(X,Y)]0 設(shè)隨機(jī)變量Z=(X+1)mod2。下面再考慮另一個(gè)信道(Y,Z),它以Y為輸入,以Z為輸出,稱(chēng)該信道為“玩家信道”。 由于有事件等式:{莊家贏(yíng)}={Y=0,X=1}∪{Y=1,X=0}={Y=0,Z=0}∪{Y=1,Z=1}={1 bit信息被從“玩家信道”的發(fā)送端Y成功地傳輸?shù)搅耸招哦薢},因此,“莊家”每贏(yíng)一次,就相當(dāng)于“玩家信道”成功地傳輸了1 bit信息。由此,再結(jié)合仙農(nóng)信息論的著名“信道編碼定理”[4-5]可得:如果“玩家信道”的容量為D,那么,對(duì)于任意傳輸率k/n≤D,都可以在譯碼錯(cuò)誤概率任意小的情況下,通過(guò)某個(gè)nbit長(zhǎng)的碼字,成功地把k個(gè)比特傳輸?shù)绞招哦恕7催^(guò)來(lái),如果“玩家信道”能夠用n長(zhǎng)碼字把Sbit信息無(wú)誤差地傳輸?shù)绞斩耍敲?,一定有S≤nD。把這段話(huà)翻譯一下,便有如下定理2。 定理2(玩家定理):設(shè)由隨機(jī)變量(Y,Z)組成的“玩家信道”的信道容量為D。那么:(1)如果莊家想勝k次,那么,一定有某種技巧(對(duì)應(yīng)于仙農(nóng)編碼),使得他能夠在k/D次游戲中以任意接近1的概率達(dá)到目的;(2)反過(guò)來(lái),如果莊家在n次游戲中贏(yíng)了S次,那么,一定有S≤nD。 由定理2可知,只要求出“玩家信道”的信道容量D,那么,莊家獲勝的極限就確定了。 與上面求“莊家信道”的步驟類(lèi)似,可以求出“玩家信道”的信道容量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è)軍人。從國(guó)家層面,要加強(qiáng)立法,嚴(yán)格執(zhí)法,通過(guò)完善和落實(shí)預(yù)備役登記制度及約束措施,確保把退伍、復(fù)員、轉(zhuǎn)業(yè)、自主擇業(yè)等有服現(xiàn)役經(jīng)歷的人全部納入管理范圍,為參加預(yù)備役組織提供政策保障。對(duì)于預(yù)備役部隊(duì)而言,要采取多種渠道掌握信息,特別是要加強(qiáng)與省軍區(qū)系統(tǒng)兵役機(jī)關(guān)的溝通協(xié)調(diào),并結(jié)合每年一度的預(yù)備役整組搞好潛力調(diào)查,確保把有現(xiàn)役經(jīng)歷的人優(yōu)先作為預(yù)任軍官、預(yù)編士兵對(duì)象,最大限度利用軍事資源。原則上,預(yù)備役軍官中服現(xiàn)役經(jīng)歷的比例不低于90%,預(yù)備役士兵中服現(xiàn)役經(jīng)歷的比例不低于70%。 結(jié)合定理1和定理2,便可以對(duì)“莊家和玩家的最終輸贏(yíng)情況”以及“玩家和莊家的游戲技巧”給出一個(gè)量化的結(jié)果,即定理3。 定理3(實(shí)力定理):在“猜正反面游戲”中,如果“莊家信道”和“玩家信道”的信道容量分別是C(q)和D(p),那么有以下3種情況: 情況1:如果莊家和玩家都是老實(shí)人,即他們?cè)谟螒蜻^(guò)程中不試圖去調(diào)整自己的習(xí)慣,即p和q都恒定不變。那么,如果C(q)大于D(p),則總體上玩家會(huì)贏(yíng);如果C(q)小于D(p),則總體上莊家贏(yíng);如果C(q)=D(p),則總體上玩家和莊家持平。 情況2:如果莊家和玩家中的某一方(比如玩家)是老實(shí)人,但是另一方(比如莊家)卻不老實(shí),他會(huì)悄悄調(diào)整自己的習(xí)慣,即改變隨機(jī)變量X的概率分布p,使得“玩家信道”的D(p)變大,并最終大于“莊家信道”的C(q),那么,莊家將整體上贏(yíng)得該游戲。反之,若只有莊家是老實(shí)人,那么玩家也可以通過(guò)調(diào)整自己的習(xí)慣,即調(diào)整Y的概率分布q,使得“莊家信道”的C(q)變大,并最終大于“玩家信道”的D(p),那么玩家將整體上贏(yíng)得該游戲。 情況3:如果玩家和莊家都不是老實(shí)人,他們都在不斷地調(diào)整自己的習(xí)慣,使C(q)和D(p)不斷變大,出現(xiàn)“水漲船高”的態(tài)勢(shì),那么最終他們將在p=q=0.5的地方達(dá)到動(dòng)態(tài)平衡,此時(shí)他們都沒(méi)有輸贏(yíng)?!安抡疵嬗螒颉背霈F(xiàn)“握手言和”的局面。 手心手背游戲:三個(gè)小朋友,同時(shí)亮出自己的“手心”或“手背”,如果其中某個(gè)小朋友的手勢(shì)與別人的相反(比如,別人都出“手心”,他卻出“手背”),那么他在本次游戲中就贏(yíng)了。 這個(gè)家喻戶(hù)曉的游戲顯然也是一種“非盲對(duì)抗”,只不過(guò)相互對(duì)抗的是三人而非常見(jiàn)的二人。他們到底誰(shuí)會(huì)輸,誰(shuí)會(huì)贏(yíng)呢?他們?cè)鯓硬拍苴A(yíng)呢?下面仍然用“信道容量法”來(lái)回答這些問(wèn)題。 由概率論中的大數(shù)定律,頻率趨于概率,所以,根據(jù)甲、乙、丙過(guò)去習(xí)慣的統(tǒng)計(jì)規(guī)律就可以分別給出他們的概率分布。 用隨機(jī)變量X代表甲,當(dāng)他出“手心”時(shí),記為X=0;出“手背”時(shí),記為X=1。所以,甲的習(xí)慣就可以用X的概率分布來(lái)描述,比如,Pr(X=0)=p,Pr(X=1)=1-p(1 用隨機(jī)變量Z代表丙,當(dāng)他出“手心”時(shí),記為Z=0;出“手背”時(shí),記為Z=1。所以,丙的習(xí)慣就可以用Z的概率分布來(lái)描述,比如,Pr(Z=0)=r,Pr(Z=1)=1-r(1 同樣,由大數(shù)定律的“頻率趨于概率”可知,先讓甲乙丙三個(gè)小朋友玩一段時(shí)間后,根據(jù)他們的游戲結(jié)果情況,就可以知道隨機(jī)變量(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 這里各個(gè)參數(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è)隨機(jī)變量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為輸出的信道,稱(chēng)之為“甲信道”。 若剔除三個(gè)小朋友的手勢(shì)相同的情況,那么,由于有事件等式: {甲贏(yíng)}={甲手心,乙手背,丙手背}∪{甲手背,乙手心,丙手心}={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)}。 反過(guò)來(lái),在剔除三個(gè)小朋友的手勢(shì)相同的情況后,若{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}={甲手心,乙手背,丙手背}∪{甲手背,乙手心,丙手心}={甲贏(yíng)}。所以,甲每贏(yíng)一次,就相當(dāng)于“甲信道”成功地把1 bit信息從發(fā)端X傳輸?shù)搅耸斩薓。由此,再結(jié)合仙農(nóng)信息論的著名“信道編碼定理”[4-5]:如果“甲信道”的容量為E,那么,對(duì)于任意傳輸率k/n≤E,都可以在譯碼錯(cuò)誤概率任意小的情況下,通過(guò)某個(gè)nbit長(zhǎng)的碼字成功地把k個(gè)比特傳輸?shù)绞招哦?。反過(guò)來(lái),如果“甲信道”能夠用n長(zhǎng)碼字,把Sbit信息無(wú)誤差地傳輸?shù)绞斩?,那么一定有S≤nE。把這段話(huà)翻譯一下,便有如下定理: 定理4:設(shè)由隨機(jī)變量(X,M)組成的“甲信道”的信道容量為E。那么,在剔除平局(即三人的手勢(shì)相同)的情況下:(1)如果甲想贏(yíng)k次,那么一定有某種技巧(對(duì)應(yīng)于仙農(nóng)編碼),使得他能夠在k/E次游戲中,以任意接近1的概率達(dá)到目的;(2)反過(guò)來(lái),如果甲在n次游戲中贏(yíng)了S次,那么一定有S≤nE。 為了計(jì)算信道(X,M)的信道容量,首先來(lái)計(jì)算隨機(jī)變量(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 所以,隨機(jī)變量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))]]2 “手心手背游戲”的信道容量法