真‧程式師用 One-Way Hash 來寫程式

Posted by TJ Wei on 星期四, 9月 11, 2014 with No comments

每隔一段時間,一定會看到關於真‧程式師要使用哪種編輯器的爭論,到最後一定會變成直接用 echo,直接用磁鐵改硬碟之類的。
GNU nano is a text editor - a program often used to edit the source code of other programs. Emacs, Vim and ed are all progressively more "hard core" editors. cat is a Unix program that concatenates and outputs the contents of files. Things get steadily more ridiculous from here. Using a magnetised needle to flip bits on a hard drive requires nanometer precision and binary mastery, but in the early days of programming people did use needles sometimes to fix bugs on Punched cards. The use of a magnetized needle may also be a reference to the Apollo AGC guidance computer, whose instructions were physically written as patterns of wires looped around or through cylindrical magnets in order to record binary code.  -- http://www.explainxkcd.com/wiki/index.php/378:_Real_Programmers
但對一個真‧程式師而言,直接寫 binary code 實在太容易了,即使是用磁鐵也一樣。真正的硬核程式師應該要用像是 sha2、 md5 這樣的東西來寫程式才有挑戰性。

就像之前的 Great Python Challenge 一樣,之前也提出了一個挑戰,挑戰真‧程式師用 one-way hash 來寫程式,比方:
cat 0.c| shasum -a 384 | xxd -p -r > a.out && chmod a+x a.out && ./a.out
會選擇 sha384 是因為他剛好夠長,可以塞進一個 ELF 執行檔(請參考 http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html).

當然也不能只挑戰別人,所以我自己也嘗試求解。最後的解如下面
照下面的步驟就能測試 (Copy& Paste) :
mkdir test
cd test
wget https://raw.githubusercontent.com/tjwei/tjw_ipynb/master/0.c
sh 0.c
gcc 0.c && ./a.out
cat 0.c | shasum -a 384 | xxd -p -r > a.out && chmod a+x a.out
./a.out


過程

第一版的解答很快就出來了 https://github.com/tjwei/tjw_ipynb/blob/master/a.c
基本上能執行,符合要求,但我還是希望至少能印出 "Hello World!"。
第二個解答不久後也出來, https://raw.githubusercontent.com/tjwei/tjw_ipynb/aa733143a5a76f460122e93028f49693d53931e8/0.c
在有些環境下,的確符合要求,能印出 "Hello World!",程式碼看來也挺漂亮的,但不夠完整。
最後我只好用更暴力的方式來搜尋解答,首先將程式碼縮短, comment 都去掉,只留下一個簡短的網址來取代原來的說明。 因為長度小於 112 byte,才能用一次 sha512 block 運算完成編碼。 這樣大概至少讓速度快個五倍。 在沒有超頻的 HD7970 ghz edition,可以用160 mhash/s, 的速度來搜尋。如果單純的 preimage 搜尋,甚至可以接近 180 mhash/s。而且還有一些加速的空間。
總之,結果在 https://github.com/tjwei/tjw_ipynb/blob/master/0.c
中間工作的過程在
http://nbviewer.ipython.org/github/tjwei/tjw_ipynb/blob/master/RealMan2.ipynb

而既然這是一個挑戰,我的確接到一些回應,其中一個由 Kuo-Tung 提供的解答,也挺有趣的,可以在這裡看到  http://paste.plurk.com/show/1982392/