當(dāng)隨機(jī)不夠隨機(jī)：一個(gè)在線撲克游戲的教訓(xùn)

　　英文原文：When Random Isn't Random Enough: Lessons from an Online Poker Exploit

　　今天我要講一個(gè)發(fā)生于1999年，一個(gè)很流行的在線撲克平臺(tái)的開(kāi)發(fā)者開(kāi)發(fā)的洗牌軟件，帶有很微小但很致命的漏洞的故事。雖然這個(gè)故事已經(jīng)15年了，但它給算法開(kāi)發(fā)者帶來(lái)的教訓(xùn)仍有重要意義。

　　在隨機(jī)數(shù)產(chǎn)生器或算法中，很容易出現(xiàn)一些微小的漏洞，但這些漏洞可能會(huì)導(dǎo)致災(zāi)難性的結(jié)果。在線撲克和真正的撲克一樣，是以洗牌開(kāi)始的。保證洗牌的隨機(jī)性尤為重要。

　　一副正常的牌有52張，并且各不相同，這樣就有52！，也就是8.0658×10^67種不同的洗牌方式。這是一個(gè)巨大的數(shù)字。

　　1999年，ASF軟件公司發(fā)布了這個(gè)軟件，支持那個(gè)年代許多流行的在線撲克平臺(tái)。他們發(fā)布了洗牌算法。

　　算法如下， 看看能否找到不對(duì)的地方。

procedure TDeck.Shuffle;
var
    ctr: Byte;
    tmp: Byte;
    random_number: Byte;
begin
    { Fill the deck with unique cards }
    for ctr := 1 to 52 do
        Card[ctr] := ctr;
    { Generate a new seed based on the system clock }
    randomize;
    { Randomly rearrange each card }
    for ctr := 1 to 52 do begin
        random_number := random(51)+1;
        tmp := card[random_number];
        card[random_number] := card[ctr];
        card[ctr] := tmp;
    end;
    CurrentCard := 1;
    JustShuffled := True;
end;

　　錯(cuò)誤1： 差一錯(cuò)誤 

　　上述算法試圖遍歷所有牌，將每一張牌跟另外一張隨機(jī)選擇的牌進(jìn)行交換。但是犯了每個(gè)程序員都犯過(guò)的錯(cuò)誤——差一錯(cuò)誤。函數(shù)random(n)返回一個(gè)0到n-1之間的隨機(jī)數(shù)，而不是程序員所想的1到n之間的。因此，這個(gè)算法中第52張牌永遠(yuǎn)不會(huì)和他自己進(jìn)行交換，也就是說(shuō)第52張牌永遠(yuǎn)不會(huì)停在第52個(gè)位置。這是隨機(jī)洗牌不夠隨機(jī)的第一個(gè)原因。

　　錯(cuò)誤2：洗牌不均勻

　　上述算法將第i張牌和另外一張從整副也就是52張牌中隨機(jī)選擇的牌進(jìn)行交換。而合適的洗牌算法應(yīng)該只和第i到第n張牌中的一張進(jìn)行交換。這是因?yàn)榭紤]到每一張牌應(yīng)該只進(jìn)行一次隨機(jī)交換。一副牌有n!種不同的排列，合適的洗牌算法應(yīng)該只產(chǎn)生每種排列一次。原算法使一些排列出現(xiàn)的概率明顯高于另一些排列，是個(gè)不好的實(shí)現(xiàn)。 

　　錯(cuò)誤3：32位種子

　　如果你的業(yè)務(wù)或技術(shù)依賴于隨機(jī)數(shù)的使用，最好的選擇是采用一個(gè)硬件隨機(jī)數(shù)產(chǎn)生器。ASF卻不是，他用了一個(gè)帶有偽隨機(jī)數(shù)產(chǎn)生器的確定機(jī)。更糟糕的是，他使用的是32位的種子。由于種子100%的決定了偽隨機(jī)數(shù)產(chǎn)生器的輸出，只有N^32種可能的種子值就意味著只有N^32種可能的打亂順序。所以在理論上有8.0658×10^67種打亂順序的情況下，他只有4百萬(wàn)可能。

　　錯(cuò)誤4：系統(tǒng)時(shí)鐘作為種子

　　上述算法使用Pascal函數(shù)Randomize()生成隨機(jī)數(shù)，而這個(gè)函數(shù)是根據(jù)從午夜開(kāi)始的毫秒數(shù)來(lái)選擇種子的。由于一天之中只有86,400,000毫秒，也就意味著上述算法只能產(chǎn)生86,400,000種可能的亂序。

　　但更糟糕的是，由于隨機(jī)數(shù)產(chǎn)生器的種子是基于服務(wù)器時(shí)鐘的，黑客們只要將他們的程序與服務(wù)器時(shí)鐘同步就能夠?qū)⒖赡艹霈F(xiàn)的亂序減少到只有200,000種。到那個(gè)時(shí)候一旦黑客知道5張牌，他就可以實(shí)時(shí)的對(duì)200,000種可能的亂序進(jìn)行快速搜索，找到游戲中的那種。所以一旦黑客知道手中的兩張牌和3張公用牌，就可以猜出轉(zhuǎn)牌和河牌時(shí)會(huì)來(lái)什么牌，以及其他玩家的牌。（注：在德州撲克中，倒數(shù)第二張公共牌，叫“轉(zhuǎn)牌”，最后一張牌，叫“河牌”。）

　　以《算法》的作者Robert Sedgewick的一段話作為結(jié)束語(yǔ)：

“That’s a pretty tough thing to have happen if you’re implementing online poker. You might want to make sure that if you’re advertising that you’re doing a random shuffle that you go ahead and do so.”—Robert Sedgewick, Professor of Computer Science, Princeton

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)