作者isnoneval (流動的語言)
看板puzzle
標題Re: [懸賞] 求黑盒子（Black Box）的編碼原則
時間Mon Dec 17 20:29:04 2007
先回一下之前板友的推文：
1F：→ nakururu:我有一個想法是十六進位，它似乎有個計算公式 12/15 19:34
2F：→ nakururu:因為我大概看了一下就是數字1~9,英文a~f 12/15 19:35
3F：推 geken:好好的十進位不用 用十六進位? ￣▽￣|| 12/15 19:54
如果哪一天強 AI 被做出來，它可能會說好好的二進位不用為什麼要用十進位？ XD
首先講一下程式本身的問題：玩過網頁上其他程式的人就會發現這些程式是同一個
系列的。這是因為網頁作者寫了一個套件，讓其他人可以用這個系統去實作小遊戲，
而 Game ID 的編碼是由那個「其他人」負責的。而既然只有 black box 的編碼方
式比較囉嗦，這代表把這個程式實作完的人很可能不是網站作者。
那十六進位碼 (Hex Code) 的好處在什麼地方呢？就是它很容易進行以 byte 為單
位的運算 (例如 xor)，因為兩個十六進位碼就是一個 byte。 (講這個是因為接下
來我們會一直用 byte 來當單位，反正記得一個 byte 就是 00~ff 就對了。)
4F：→ puzzlez:那是因為黑球有4種位置，所以它的ID也固定只有4種... 12/15 19:15
5F：→ puzzlez:樓上有發現第5種ID嗎？ 12/15 19:16
6F：→ puzzlez:我發現球若只有一個，ID只有一種，球有2個就有2種... 12/15 19:24
7F：推 kjacky:剛剛試了一下，不管長寬多少，若只放一顆球，GameID只有8位 12/15 21:59
8F：推 pphhxx:放0顆球是4位，後來每多1顆多4位 12/15 22:04
9F：→ 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)。
10F：→ kjacky:接下來又發現長寬最大不超過255，而255四次方換成十六進位 12/15 22:10
11F：→ kjacky:的FFFFFFFF，所以有可能作者把全部結果RUN完再扣掉不合理 12/15 22:10
12F：→ kjacky:的結果後，在逐一分類。所以我的結論是他的編碼跟GameID 12/15 22:13
13F：→ kjacky:沒有直接關係Orz..... 12/15 22:14
這個是不可能的，因為需要在程式裡記錄極大量的資訊，這個程式很小。
14F：→ puzzlez:長寬在最前面就寫上了，後面的編碼不一定要把255這數字 12/15 22:19
15F：→ 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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.37.36.74
16F：推 Daigua:推神人 12/17 21:11
17F：推 nakururu:好厲害........ 12/17 21:27
※ 編輯: isnoneval 來自: 71.37.36.74 (12/17 22:16)
18F：推 geken:專業的來了 12/17 23:48
19F：推 didij:推呀>_< 12/18 01:08
20F：推 chung6hc:好強!! 推 12/18 02:21
21F：推 puzzlez:你是神@@"將來有成就的時候別忘了提拔我@@"未來會做game嗎 12/18 03:58
22F：推 puzzlez:本人感動得決定，仍然將這1000P幣送給你，當然.... 12/18 03:59
23F：推 puzzlez:未來若有人繼續將它解出，我還是會送..（嫌太少可以說XD） 12/18 04:00
24F：→ isnoneval:不用啦, 你留著吧, 沒解完就是沒解完 12/18 05:22
25F：→ isnoneval:而且我 po 這篇就 1000p 了 XD 12/18 05:23
26F：推 puzzlez:別客氣，反正應該也不會有人解得出吧？XD 12/18 05:26
27F：→ isnoneval:難講 如果真的有高手願意用心解的話 XD 12/18 05:27