Re: [懸賞] 求黑盒子（Black Box）的編碼原則

12/15 19:34,

12/15 19:34

→

12/15 19:35,

12/15 19:35

推

geken

12/15 19:54,

12/15 19:54

如果哪一天強 AI 被做出來，它可能會說好好的二進位不用為什麼要用十進位？ XD 首先講一下程式本身的問題：玩過網頁上其他程式的人就會發現這些程式是同一個系列的。這是因為網頁作者寫了一個套件，讓其他人可以用這個系統去實作小遊戲，而 Game ID 的編碼是由那個「其他人」負責的。而既然只有 black box 的編碼方式比較囉嗦，這代表把這個程式實作完的人很可能不是網站作者。那十六進位碼 (Hex Code) 的好處在什麼地方呢？就是它很容易進行以 byte 為單位的運算 (例如 xor)，因為兩個十六進位碼就是一個 byte。 (講這個是因為接下來我們會一直用 byte 來當單位，反正記得一個 byte 就是 00~ff 就對了。)

→

12/15 19:15,

12/15 19:15

→

12/15 19:16,

12/15 19:16

→

12/15 19:24,

12/15 19:24

推

12/15 21:59,

12/15 21:59

推

pphhxx

12/15 22:04,

12/15 22:04

→

12/15 22:05,

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)。

→

12/15 22:10,

12/15 22:10

→

12/15 22:10,

12/15 22:10

→

12/15 22:13,

12/15 22:13

→

12/15 22:14,

12/15 22:14

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

→

12/15 22:19,

12/15 22:19

→

但是現在就有兩個問題： 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

推

Daigua

12/17 21:11, , 1^F

12/17 21:11, 1^F

推