ddaa's blog
Write-ups for CTF.
ddaa's blog

VolgaCTF 2014 Crypto 100 Crypto100

Other CTF

Share Tweet Share

crypto 只有解出 100 分而已
其他都沒解出來...
早知道去解別題了 ORZ


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

190569475701019412937705231680700513465015462478574872080026036707049434285377110377581884338050290774147519326077986327023814459562710938989987601622114027649584411501029597442404380535706287506751810630518137180840386095680950172667823654745784065

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

  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 (3rd prime) = 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