NO CTF NO LIFE

VolgaCTF 2014 crypto 100

crypto 只有解出 100 分而已
其他都沒解出來...
早知道去解別題了 ORZ
p.s 所有題目時間一到就關了阿 只好紙上談兵 write up


密文是一個超級大的數字...

1905694757010194129377052316807005134650154624785748720800260367070494342853771103775818843380502907741475193260779863270238144595627109389899876016221140276495844115010295974424043805357062875067518106305181371808403860956809501726678236547457840650
...

題目還有給一個遠端的加密程式
試了一下規則有:

  1. 非英文字母都 = 1
  2. 英文字母不分大小寫
  3. a=4,b=9,c=25,d=49,...,z=10201

很輕易可以看出來對應的數字就是質數的平方
但是如果兩個字元以上就還有一些變化
ex: a=4, aa=32, aaa=1024, aaaa=131072
收集一些密文後可以推得遞迴式:

  • F(d) = F(d-1) * prime[c] ^ 2 * prime[c] ^ prime[d]
  • prime[] = 質數陣列, 2,3,5....
  • d = 第 d 個字元
  • c = 字元 (ex:a=0,b=1,c=2...)

ex : aaa = 32 (aa 的 值) * 4 (a 對應的值) * 2 ^ 5 (5 是第 3 個質數) = 1024

我們可以把 cipher 做因式分解
所包含的質數就代表 plain 包含該字元
並且計算其次方
如果 次方-2 是質數
就表示是該字元只出現過一次

至此也就只能分析出用上的字元有 a c e i l m n o p q r s t u v
以及第三個字元是 q
某個字元是 v
某個字元是 m
其它會有 collision 無法正確判斷位置

直到提示給了 plain text is a meaningful word
抱著隨意嘗試的心態去找超級長的單字
結果還真的有符合條件的 = =

flag: aequeosalinocalcalinoceraceoaluminosocupreovitriolic