求黑盒子（Black Box）的編碼原則 - 拼圖

By Lydia
at 2007-12-17T20:29

Table of Contents

先回一下之前板友的推文：

→ nakururu:我有一個想法是十六進位，它似乎有個計算公式 12/15 19:34

→ nakururu:因為我大概看了一下就是數字1~9,英文a~f 12/15 19:35

推 geken:好好的十進位不用用十六進位? ￣▽￣|| 12/15 19:54

如果哪一天強 AI 被做出來，它可能會說好好的二進位不用為什麼要用十進位？ XD

首先講一下程式本身的問題：玩過網頁上其他程式的人就會發現這些程式是同一個
系列的。這是因為網頁作者寫了一個套件，讓其他人可以用這個系統去實作小遊戲，
而 Game ID 的編碼是由那個「其他人」負責的。而既然只有 black box 的編碼方
式比較囉嗦，這代表把這個程式實作完的人很可能不是網站作者。

那十六進位碼 (Hex Code) 的好處在什麼地方呢？就是它很容易進行以 byte 為單
位的運算 (例如 xor)，因為兩個十六進位碼就是一個 byte。 (講這個是因為接下
來我們會一直用 byte 來當單位，反正記得一個 byte 就是 00~ff 就對了。)

→ puzzlez:那是因為黑球有4種位置，所以它的ID也固定只有4種... 12/15 19:15

→ puzzlez:樓上有發現第5種ID嗎？ 12/15 19:16

→ puzzlez:我發現球若只有一個，ID只有一種，球有2個就有2種... 12/15 19:24

推 kjacky:剛剛試了一下，不管長寬多少，若只放一顆球，GameID只有8位 12/15 21:59

推 pphhxx:放0顆球是4位，後來每多1顆多4位 12/15 22:04

→ nakururu:應該是指球的座標... 12/15 22:05

以上都是正確的，Game ID 編碼長度 = 球數 * 2 + 2 (bytes)，
一個 Game ID 由 w_h_m_M_: 後面接 2n+2 bytes 的 Hex code 組成，n 為球數。
前面很明顯是 w:棋盤寬 h:棋盤高 m:球數下限(含) M:球數上限(含)

因為棋盤大小最大只能到 255x255，所以一顆球的座標花 2 bytes 剛好 ok；
剛好每多一顆球 ID 就多 2 bytes，故它記錄的是球座標是最合理的猜測。
因為對寫程式的人來說數字是從零開始的，所以先假設第一格是 (0,0)。

→ kjacky:接下來又發現長寬最大不超過255，而255四次方換成十六進位 12/15 22:10

→ kjacky:的FFFFFFFF，所以有可能作者把全部結果RUN完再扣掉不合理 12/15 22:10

→ kjacky:的結果後，在逐一分類。所以我的結論是他的編碼跟GameID 12/15 22:13

→ kjacky:沒有直接關係Orz..... 12/15 22:14

這個是不可能的，因為需要在程式裡記錄極大量的資訊，這個程式很小。

→ puzzlez:長寬在最前面就寫上了，後面的編碼不一定要把255這數字 12/15 22:19

→ puzzlez:也編進去，就算真有一球落在最後一格也是一樣....

但是現在就有兩個問題：
1.這樣長寬其實可以設到 256x256，為什麼他不讓我們玩 256 的？
2.多出來那兩個 byte 是做什麼用的？

先講第二個。如果沒有多 2 bytes 會發生什麼事呢？
因為 Board Config → Game ID 是一對一，這樣在 w255h255m1M1 的情況下，
後面的碼隨便填都會中。也就是說為了故意表我們，那兩個 byte 有檢查碼的作用。

接下來當然去把一些小的數據洗出來，首先是 w2h2m1M1 的四組：

Game ID 座標格序 ┌─┬─┐
w2h2m1M1:3973 3bf9 (0,0) 1 │１│２│
w2h2m1M1:f572 366b (0,1) 2 ├─┼─┤
w2h2m1M1:8ca5 99f4 (1,0) 3 │３│４│
w2h2m1M1:191b 4f78 (1,1) 4 └─┴─┘

可以說是一點規律也沒有，很好!! (怒)

但是接下來我們來看 w2h2m2M2 的其中八組：

Game ID y1 x1 y2 x2
w2h2m2M2:6bec91 7d8bf8 (1,0)-(0,0)
w2h2m2M2:6bec90 d1a182 (1,0)-(0,1)
w2h2m2M2:fa010c 75e762 (0,0)-(1,0)
w2h2m2M2:fa010d 8f576f (0,0)-(1,1)
w2h2m2M2:cac414 929e17 (1,1)-(0,0)
w2h2m2M2:cac415 468393 (1,1)-(0,1)
w2h2m2M2:13e4ea 94a83f (0,1)-(1,0)
w2h2m2M2:13e4eb b913e9 (0,1)-(1,1)

當然我們從板面上看不出來球的順序，但是不失一般性可以先這樣定義：
當兩個 Game ID 前半段相似的時候，把位置不同的球定義在後面。

再來幾個有趣的例子：
w2h2m3M3:a1c3d33d 9f2f22b5 (1,0)-(1,1)-(0,0) (前兩球順序分不出來)
w2h2m3M3:a1c3d23d 5bbaf152 (1,0)-(1,1)-(0,1)
w2h2m3M3:ce176436 7d24050a (0,0)-(1,1)-(0,1)
w2h2m3M3:ce176537 fc9eb5c1 (0,0)-(1,1)-(1,0)
w3h3m4M4:031e20fc6c 1bdae83087 (1,0)-(1,1)-(0,1)-(2,1)
w3h3m4M4:031e23ff6d af94a47214 (1,0)-(1,1)-(0,0)-(1,2)

對二進位運算比較熟悉的板友到這裡一定看出來了：
每組前半段的微小差異 xor 起來剛好與後面幾個座標 xor 起來是一樣的
(http://en.wikipedia.org/wiki/Xor 不熟的人自己看 XD)
(又，這證實了把第一格設為 (0,0) 的假設是對的)

下一步為了測 w h 值的影響，我們要比較球座標相同但棋盤長寬不同的情況：

w2h2m1M1:8ca5 99f4 以下都是 (1,0)
w3h3m1M1:8da4 5c2e
w4h4m1M1:8aa3 8923
w5h5m1M1:8ba2 27fd

這說明了前兩個 byte 和 w h 值的 xor 是一致的，並且這回答了第一個問題：
因為事實上 w h 也要進編碼參一腳，所以作者不讓它們超過 255。

什麼？你說如果 w != h 會怎麼樣呢？會這樣：

w3h2m5M5:8ae480711844 c1ac84721821 crash
w3h2m5M5:8ae482701a44 e8bd597cb1ce crash

沒錯，在長寬不等而且球數比較多的時候這程式必當。
雖然以上兩組仍然很有默契的秀出了預期中的相似性，但是我還是決定不予錄用。

回到主題上，再來是幾個重點：
1.前半段有相似性若且唯若前 n+1 bytes 座標值完全一樣； (y 座標排在 x 之前)
也就是前半段大致上由前 n+1 bytes 座標值決定。
2.只要前 n+1 bytes 座標值差一點點，前半段就會完全看不出關連。
也就是說前半段對前 n+1 bytes 座標值敏感 (sensitive)。
3.前半段與後半段的關係完全看不出來。
4.後半段的值對 w h 與所有座標都敏感。

用最簡單的方式來說明這套規則就是：

令 P = w h x_n y_n ... x_2 y_2 x_1 y_1 (共 2n+2 bytes 的十六進位碼)
C = Game ID 編碼部分
P1 = P 前半段, P2 = P後半段, C1 = C 前半段, C2 = C 後半段

則 C1 = P1 xor f(P2), f 為 n+1 bytes → n+1 bytes 的 hash function (雜湊函數)
(http://en.wikipedia.org/wiki/Hash_function)

絕望啦!!我對寫個小遊戲都要用編碼技術的社會絕望啦!!

所以基本上我只有解到這裡而已。其實利用多出來的 2 bytes 是可以寫出沒有這種
弱點的編碼方法的，我不知道作者為什麼要這樣設計。不過最最合理的猜測是：程
式在解碼的是時候是先解出 P2，再用 P2 去解 P1，所以應該是這樣：

C2 = P2 xor g(C1), g 是另一個 hash function

如果 C2 的猜測是對的有沒有可能 g = f 呢？這個以目前的條件來說我們無法測試。

因為這個東西反編譯的結果看來是用 GNU C 來寫的，所以我猜他大概是用了內建的
那個 encrypt 來編碼，那大概就是 MD5 或是 DES。但是我覺得會心機到寫小遊戲
也用 MD5 的人大概也會在裡面加鹽... 所以我不要試了。 XD

如果有人有進一步結果或能拿到 source 我會很想看看。 :3

--

Tags: 拼圖