楊義先，鈕心忻

(北京郵電大學 信息安全中心，北京 100876)

?

安全通論(3)
——攻防篇之“非盲對抗”之“石頭剪刀布”

楊義先，鈕心忻

(北京郵電大學 信息安全中心，北京 100876)

編者按：“石頭剪刀布”是一種發(fā)源于中國的猜拳游戲，是用來產(chǎn)生隨機結(jié)果以作決策。但有時它并不隨機，因為游戲者可以根據(jù)經(jīng)驗，判斷對手的手法。本文給出了“石頭剪刀布”的一種“白富美”新玩法。所謂“白”，即思路清清楚楚、明明白白；所謂“富”，即理論內(nèi)涵非常豐富；所謂“美”，即結(jié)論絕對數(shù)學美?！栋踩ㄕ摗返镊攘σ苍谶@里得到了幽默體現(xiàn)。本文轉(zhuǎn)自《科學網(wǎng)》楊義先教授與鈕心忻教授撰寫的博文，為與本刊風格一致，我們對文字略作了一些微調(diào)。閱讀原文可登錄以下網(wǎng)址：http://blog.sciencenet.cn/blog-453322-948089.html。

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

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

0　引言

全人類，數(shù)千年來，都在玩“石頭剪刀布”，而且，玩出了無盡幸福！

由浙江大學、浙江工商大學、中國科學院等單位組成的跨學科團隊，在300多名志愿者的配合下，歷時4年，終于把“石頭剪刀布”玩成了“高大上”，其成果被評為“麻省理工學院科技評論2014年度最優(yōu)”，這也是我國社科成果首次入選該頂級國際科技評論。

本文利用《安全通論》，只需一張紙、一支筆，就把“石頭剪刀布”玩成“白富美”。所謂“白”，即思路清清楚楚、明明白白；所謂“富”，即理論內(nèi)涵非常豐富；所謂“美”，即結(jié)論絕對數(shù)學美。

1　信道建模

設(shè)甲與乙玩“石頭剪刀布”。他們可分別用隨機變量X和Y來表示：

當甲出拳為剪刀、石頭、布時，分別記為X=0、X=1、X=2；

當乙出拳為剪刀、石頭、布時，分別記為Y=0、Y=1、Y=2。

根據(jù)概率論中的“大數(shù)定律”，頻率的極限趨于概率，所以甲乙雙方的出拳習慣，可以用隨機變量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

同樣，還可以統(tǒng)計出二維隨機變量(X，Y)的聯(lián)合分布概率：

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，構(gòu)造另一個隨機變量Z=[2(1+X+Y)]mod3。由于任意兩個隨機變量都可構(gòu)成一個通信信道，所以，以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比特信息成功地從發(fā)端送到了收端，那么，也只有三種可能的情況：

情況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比特信息從發(fā)端送到了收端；反之亦然。

再利用隨機變量Y和Z構(gòu)造一個信道(Y；Z)，稱之為“乙方信道”，它以Y為輸入，以Z為輸出。那么，仿照前面的論述，可得如下引理：

引理2：乙方贏一次，就意味著“乙方信道”成功地把1比特信息，從發(fā)端送到了收端；反之亦然。

由此可見，甲乙雙方玩“石頭剪刀布”的輸贏問題，就轉(zhuǎn)化成了“甲方信道”和“乙方信道”能否成功地傳輸信息比特的問題。根據(jù)仙農(nóng)第二定理[3]可知：信道容量就等于該信道能夠成功傳輸?shù)男畔⒈忍財?shù)。所以，“石頭剪刀布”的游戲問題就轉(zhuǎn)化成了信道容量問題。更準確地說，本文有如下定理：

定理1(“石頭剪刀布”定理)：如果剔除“平局”不考慮(即忽略甲乙雙方都出相同手勢的情況)，那么，

(1)針對甲方來說，對任意k/n≤C，都一定有某種技巧(對應于仙農(nóng)編碼)使得在nC次游戲中，甲方能夠勝乙方k次；如果在某m次游戲中，甲方已經(jīng)勝出乙方u次，那么，一定有u≤mC。這里C是“甲方信道”的容量。

(2)針對乙方來說，對任意k/n≤D，都一定有某種技巧(對應于仙農(nóng)編碼)使得在nD次游戲中，乙方能夠勝甲方k次；如果在某m次游戲中，乙方已經(jīng)勝出甲方u次，那么，一定有u≤mD。這里D是“乙方信道”的容量。

(3)如果CD，那么，整體上甲方會贏；如果C=D，那么，甲乙雙方勢均力敵。

由于“甲方信道”和“乙方信道”的信道容量都有現(xiàn)成的計算公式，這里略去C和D的計算細節(jié)(有特殊興趣的讀者，可閱讀原文網(wǎng)址附件中的Word版本)。

2　巧勝策略

由定理1可知，甲乙雙方在“石頭剪刀布”游戲中的勝負，其實事先就已經(jīng)“天定”了，某方若想爭取更大的勝利，那他就必須努力“改變命運”。下面分幾種情況來考慮：

(1)兩個傻瓜之間的游戲

所謂“兩個傻瓜”，意指甲乙雙方都固守自己的習慣，無論過去的輸贏情況怎樣，他們都按既定習慣“出牌”。這時，由定理1已經(jīng)知道：如果CD，則整體上甲方會贏；如果C=D，則甲乙雙方勢均力敵。

(2)一個傻瓜與一個智者之間的游戲

如果甲是傻瓜，他仍然堅持其固有的習慣“出牌”，那么，雙方對抗足夠多的次數(shù)后，乙方就可以計算出對應于甲方的，隨機變量X的分布概率p和q，以及相關(guān)的條件概率分布，并最終計算出“甲方信道”的信道容量，然后，再通過調(diào)整自己的習慣(即隨機變量Y的概率分布和相應的條件概率分布等)，最終增大自己的“乙方信道”的信道容量，從而使得后續(xù)的游戲?qū)ψ约焊欣?；甚至使“乙方信道”的信道容量大于“甲方信道”的信道容量，最終使得自己穩(wěn)操勝券。

(3)兩個智者之間的游戲

如果甲乙雙方都隨時在總結(jié)對方的習慣，并對自己的“出牌”習慣做調(diào)整，即增大自己的信道容量。那么，最終甲乙雙方的“信道容量”值將趨于相等，即他們之間的游戲競爭將趨于平衡，達到動態(tài)穩(wěn)定的狀態(tài)。

3　簡化版本

雖然上面幾節(jié)完美地解決了“石頭剪刀布”游戲問題，但是，它們在保持“直觀形象”的優(yōu)勢下，付出了“復雜”的代價。下面，給出一個更抽象、更簡捷的解決辦法。

設(shè)甲與乙玩“石頭剪刀布”，他們可分別用隨機變量X和Y來表示：

當甲出拳為剪刀、石頭、布時，分別記為X=0、X=1、X=2；

當乙出拳為剪刀、石頭、布時，分別記為Y=0、Y=1、Y=2。

根據(jù)概率論中的“大數(shù)定律”，頻率的極限趨于概率，所以甲乙雙方的出拳習慣可以用隨機變量X和Y的概率分布表示為：

0

0

0

∑0≤x,y≤2txy=1；

px=∑0≤y≤2txy，x=0,1,2；

qy=∑0≤x≤2txy，y=0,1,2。

“石頭剪刀布”游戲的輸贏規(guī)則是：若X=x，Y=y，那么，甲(X)贏的充分必要條件是：(y-x)mod3=2。

現(xiàn)在構(gòu)造另一個隨機變量F=(Y-2)mod3。考慮由X和F構(gòu)成的信道(X；F)，即，以X為輸入，以F為輸出的信道。那么，就有如下事件等式：

若在某個回合中，甲(X)贏了，那么就有(Y-X)mod3=2，從而，F(xiàn)=(Y-2)mod3=[(2+X)-X]mod3=X，也就是說：信道(X；F)的輸入(X)始終等于它的輸出(F)。換句話說，1個比特就被成功地在該信道中從發(fā)端傳輸?shù)搅耸斩恕?/p>

反過來，如果“1個比特被成功地在該信道中從發(fā)端傳輸?shù)搅耸斩恕保敲淳鸵馕吨靶诺?X；F)的輸入(X)始終等于它的輸出(F)”，也就是說：F=(Y-2)mod3=X，這剛好就是X贏的充分必要條件。

結(jié)合上述正反兩個方面的論述，有：甲(X)贏一次，就意味著信道(X；F)成功地把1比特信息從發(fā)端送到了收端；反之亦然。因此，信道(X；F)也可以扮演第2節(jié)中“甲方信道”的功能。

類似地，若記隨機變量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的函數(shù)。

同理，(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的函數(shù)。

其他討論與前面幾節(jié)相同，不再重復。

4　結(jié)束語

“攻防”是安全的核心，所以，在建立“安全通論”的過程中，多花一些精力去深入研究“攻防”也是值得的。

[2]中，研究了“安全通論”的盲對抗問題，本文研究的“石頭剪刀布”游戲則是一種“非盲對抗”，但由于它的普及率極高(幾千年來，全世界每個人在童年時代幾乎都玩過)，所以，我們單獨以一篇論文的形式來研究它。有關(guān)其他一些有代表性的“非盲對抗”，將在后續(xù)文章中研究。

當然，換一個角度來看，也可以說，我們的“安全通論”雖然剛剛誕生，但它已大顯身手，成功地掃清了古老“石頭剪刀布”游戲中的若干迷霧。所以，“安全通論”確定大有前途。

參考文獻

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

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

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

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

(未完待續(xù)，系列之四《安全通論(4)——攻防篇之“非盲對抗”之“童趣游戲”》見下期)