題解：DeeCamp識別圖靈獎獲得者（破譯密鑰，非暴力）

08-21

7 人贊了文章

一些廢話

DeeCamp的筆試已經結束了，面試也在開展之中，剛剛完成了視頻面試，現在將DeeCamp壓軸題目的答案分享給大家。看到知乎上已經有很多題解了，但是對於6.8晚上DeeCampB卷最後一題圖靈獎圖片識別題目的答案很少，而且也不夠好。因此分享自己的方法給大家！

先上原題

有一張圖靈獎得主的肖像照片，被一個學生用簡單的異或加密方法，編碼成了如下這樣的字元串：vOy67L3rveu667rsveu97b3rveq67L3qvey67L3rvey77brruuy667rquuy667zrvey97b3quuy66rzsu+u967rsu+u87L3tu+y96r3svey77Lzruuy66rrtuuu97Lvtuuu77b3svey67b3sveq67L3qveu67Lrsuuy6673rvOy77brsveu96r3suuu967rtveq67L3sveu9673quuy967rsveu767rsu+y967rsu+q967rsu+q86r3suu267b3ruu267Lvruuy6（太多了就不全貼上了）
已知肖像照片是64x64像素的0~255級灰度圖片，內存中用raw bitmap方式，每個像素用一個位元組存儲。對肖像照片的原始數據，學生使用的加密代碼片段如下（Python3代碼，代碼中的key值是未知的加密密鑰）：

_KEY_LEN = 2
bitmap = PIL.Image.open(image_path).tobytes()
encrypted = []
for index, byte in enumerate(bitmap):
encrypted.append(byte ^ key[index % _KEY_LEN])
return base64.standard_b64encode(bytes(encrypted))

請問：這張被加密的照片，是以下哪點陣圖靈獎得主的肖像？請從下方A至H的選項中，選擇正確答案的字母序號填入：

(A) Marvin Minsky
(B) John L. Hennessy
(C) Donald E. Knuth
(D) Raj Reddy
(E) John McCarthy
(F) Edsger W. Dijkstra
(G) John Hopcroft
(H) Alan Kay

題意解釋

題目的意思大概如下：給了一段加密後的比特流數據，要你解密（當然是再不給你密鑰的情況下）。根據解密的信息生成圖片，判斷圖片是哪點陣圖靈獎獲得者。

選項有A-H共8個，基本上猜對的幾率還是很小的，前面的選擇題目都很簡單，個人感覺都是熱身，其實只有做出這道題來才能進面試環節（個人猜測，僅供參考）。

有用信息如下：密文（我們的輸入），KEY_LEN=2(密鑰是兩個比特的數據)，加密方法是異或，圖像是64x64的灰度圖（0-255，8位）。

一種容易想到但是很Low的方法

既然密鑰只有兩個比特，也就是一共16位，那麼顯然是可以枚舉的。2^16=65536，計算機上大概2-5分鐘就可以全部解密出來。通過瀏覽這些圖片，有一些能夠分辨出人臉的，可以用來做出選擇，這也是大部分人的解決方法。

核心代碼如下

for i in range(0,255): for j in range(0,255): key.append([i,j]) # 生成所有可能的密鑰for name, item in enumerate(key): afterDecode = [] for index, element in enumerate(codes): if index % 2 == 0: afterDecode.append(element ^ item[0]) else: afterDecode.append(element ^ item[1]) #分別用兩種密鑰解密 #print(afterDecode) for i in range(len(afterDecode)): afterDecode[i] = 255-afterDecode[i] arra = np.array(afterDecode).reshape((64, 64)) #print(arra) pict = Image.fromarray(arra).convert("L") #pict.show() pict.save("./pictures/"+str(name)+".png", "PNG") #存儲到本地

這種方法可以生成所有可能的原圖像，結果如下

有一些圖像比較清楚，就可以看到人臉，知道是誰了。

這種方法的話非常容易想到，門檻主要在寫代碼上，壓力應該不大。本質上就是暴力破解，到最後也不知道密鑰是什麼。

如何破解密鑰？一種巧妙的演算法

如果我們不考慮加密解密，直接將比特流輸出成圖片，會得到什麼呢？

值得一提的是，你甚至都不需要解密。從這個未解密圖像上可以得知，這個人是有鬍子的，而且很長，有濃密頭髮（這對於程序員來說是稀缺特徵），最關鍵的是還戴眼鏡。其實根據這些特徵，基本上就可以鎖定選項了。

如何破解密鑰呢？可以看到，這個圖像很明顯是有背景色的！一般來說，背景色非白即黑，也就是255或者0。

列印一下未解密的圖像矩陣形式，是這個樣子的：

[[188 236 186 ..., 235 189 235] [186 236 187 ..., 235 188 236] [187 237 186 ..., 237 189 235] ..., [184 238 187 ..., 100 19 123] [189 236 186 ..., 91 101 119] [184 237 187 ..., 165 196 72]]

發現什麼規律了嗎？就看左側邊界未知，第一列基本都是186，第二列基本都是236，第三列又是186，第四列又是236。而這幾列在加密前肯定都是背景色，都是255！（或者0，對應背景色為黑色）

於是就有了這個等式組

255 XOR KEY1 = 186255 XOR KEY2 = 236

解出來，得到KEY1=69，KEY2=19，用這個密鑰解密

主要代碼如下：

key = [[69, 19]]for i in range(0,255): for j in range(0,255): key.append([i,j])for name, item in enumerate(key): afterDecode = [] for index, element in enumerate(codes): if index % 2 == 0: afterDecode.append(element ^ item[0]) else: afterDecode.append(element ^ item[1]) #print(afterDecode) for i in range(len(afterDecode)): afterDecode[i] = 255-afterDecode[i] arra = np.array(afterDecode).reshape((64, 64)) #print(arra) pict = Image.fromarray(arra).convert("L") pict.show() pict.save("./pictures/"+str(name)+".png", "PNG")

最後，就可以得到解密的圖像！

谷歌搜一下就找到答案啦！

值得一提的是，這裡的背景色是白色，我加了一句代碼翻轉了一下，這樣的圖片應該更好找。

最後，相關演算法的全部代碼可以在我的公眾號「機器學習社團」找到！

以及歡迎大家關注我的Bilibili賬號，會一直更新一些機器學習入門的教學視頻

https://space.bilibili.com/237838762 (二維碼自動識別)

祝大家都可以成功進入DeeCamp！

Good Luck !