NO CTF NO LIFE

GiTs 2014 Reverse Engineering 150 PapSmear

這題很慢才打開
解出來的時後竟然超過時間了阿阿阿
悲劇 看來還是對 python 不夠熟


根據說明用 nc 連至目標後
隨便輸入一些字串
得到錯誤訊息 :

Serial: asd
Bzzt. Wrong!

直接打開檔案發現是一個python寫成的code
裡面有兩行 :

with open('flag.txt','r') as f:
print f.read()

看來這題的目的很明顯了
需要找出一個正確 Serial
Server 就會把 key 給噴出來
剩下的就是 trace code...
首先,程式將 Serial 以'-'分開,變成6個 num
每次取1對 (num1,num2) 做判斷

先解釋一下每個函數代表的意思:

  1. _a() : 得到數個質數,大小為 2~x ,每次呼叫後都會改變下一次呼叫的值
  2. __a(n) : 為 _a() 所得到的質數做過濾,如果是 n 的因數,則過濾此質數
  3. ___a(n) : 將 __a() 過濾後的質數做 (1 - 1.0 / p) 取整數後相乘
  4. ____a(n) : ___(num1*num2) == ___a(num1) * ___a(num2)
  5. _____a(num1,num2) : 限制 num1 介於10001~100000,num2 介於100~999

程式有幾條限制,任何一條沒滿足都會發生exception並結束:

  1. _____a() 回傳 True
  2. ___a(num1)) == num1 - 1
  3. ____a() 回傳 True
  4. 3個(num1,num2)組合不能相同
  5. 最後一個條件有點複雜,直接看 code
for k in range(7,10):
  a,b = int(c.pop()),int(c.pop())
  for x in [a+b*n for n in range(k)]:
    y = [p for p in __a(x)]
    if not (len(y)==1 and y[0]==x):raise

看似條件很多
但是其實條件(1)是限制input size
條件(3)很容易滿足
所以暫時不考慮
我們先找出滿足(2)的所有num1
再用暴力解去找出滿足(5)的條件
最後再用(3)來檢查是不是正確的解

k = 7 or 8 or 9
分別對應到3組num
有些解是共同的
因為(4)的限制所以要挑不一樣的解
隨便選一組送過去就拿到key了

Serial:
10243-420-11003-630-10859-210
The flag is: ThesePrimesAreNotIllegal

key: ThesePrimesAreNotIllegal