[閒聊] selfmd5已回收
輸出自己的 MD5 值的程式
這樣的程式存在其實不太意外
畢竟有無限多種程式，但 MD5 的值是有限的
讓我意外的是要找出這樣的程式不需要爆搜
而是可以簡單的建構出來
參考 http://www.madore.org/~david/computers/quine.html
寫了一個 Python3 版本的
from hashlib import md5
data = """
m = md5()
m.update(b"from hashlib import md5\\n\\n")
m.update(b"data = \\"\\"\\"")
for ch in data:
m.update(ch.encode() if ch != '\\\\' else b"\\\\\\\\")
m.update(b"\\"\\"\\"\\n")
m.update(data.encode())
print(m.hexdigest())
"""
m = md5()
m.update(b"from hashlib import md5\n\n")
m.update(b"data = \"\"\"")
for ch in data:
m.update(ch.encode() if ch != '\\' else b"\\\\")
m.update(b"\"\"\"\n")
m.update(data.encode())
print(m.hexdigest())
（結尾有換行）
這個程式碼的 MD5 是 a509ddcd25429679ea474625b7cc39c5
執行之後的輸出也的確是這個值
可以看到其實在上面的程式把 MD5 換成其他的 function 也沒有差
查了一下後發現有這樣一個定理：
https://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem
Rogers's fixed-point theorem.
If F is a total computable function,
there is an index e such that φ_e = φ_{F(e)}.
可以想成是假如 F 可以將一個程式碼轉成另一個程式碼
那就一定會有程式碼在轉之前 (e) 和轉之後 (F(e)) 的行為是一樣的
這一開始是拿來造出會印出自己本身的程式
假如把 F 設為「輸入 x, 輸出會印出 MD5(x) 的程式碼」
根據這個定理，就一定有程式碼 p 他的行為和 F(p)一樣
也就是印出 MD5(p)，他自己的 MD5 值
然後這個定理的證明是 constructive，所以可以照著他的證明建構出這樣的程式
好酷喔
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1650469243.A.AC2.html
→
04/20 23:44,
3年前
, 1F
04/20 23:44, 1F
推
04/20 23:45,
3年前
, 2F
04/20 23:45, 2F