作者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