[HITCON CTF 2019 Quals] Very Simple Haskell

prob.hs

import Data.Char
import System.IO

n :: Integer
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667

k :: Int
k = 131

primes :: [Integer]
primes = take k $ sieve (2 : [3, 5..])
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

stringToInteger :: String -> Integer
stringToInteger str = foldl (\x y -> (toInteger $ ord y) + x*256) 0 str

integerToString :: Integer -> String
integerToString num = f num ""
    where
        f 0 str = str
        f num str = f (div num 256) $ (:) (chr $ fromIntegral $ num `mod` 256) str

numToBits :: Integer -> [Int]
numToBits num = f num []
    where 
        f 0 arr = arr
        f x arr = f (div x 2) ((fromInteger $ x `mod` 2) : arr)

extendBits :: Int -> [Int] -> [Int]
extendBits blockLen arr
    | len == 0 = arr
    | len > 0 = (replicate (blockLen-len) 0) ++ arr
    where len = (length arr) `mod` blockLen

calc :: Integer -> [Int] -> Integer
calc num [] = num
calc num arr = calc result restArr
    where
        num2 = num*num `mod` n
        (block, restArr) = splitAt k arr
        zipped = zipWith (\x y -> ((fromIntegral x)*y) `mod` n) block primes  
        mul = product $ filter (/=0) zipped
        result = num2*mul `mod` n

magic :: String -> String
magic input = result
    where 
        num = stringToInteger input
        bits = numToBits num
        extended = reverse $ extendBits 8 bits
        oriLen = length extended
        extendedBits = extendBits k extended
        oriLenBits = numToBits $ fromIntegral oriLen
        extendedOriLenBits = extendBits k oriLenBits
        finalBits = extendedOriLenBits ++ extendedBits
        result = show $ calc 1 (reverse finalBits)

main = do
    flag <- readFile "flag"
    putStrLn.show $ length flag
    putStrLn $ magic ("the flag is hitcon{" ++ flag ++ "}") 

Output

6
84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096

Since I'm not that familiar with haskell, I waste a lot of time to understand the logic. The logic is not that hard. It is a Naccache-Stern Knapsack Cryptosystem. Some wise guy in GoN ports haskell code to python, so if you are interested, you can check it.

 

The candidates of flag are total $10^{12}$. But using Meet-In-The-Middle, You can solve it in $O(10^6log(10^6))$.

 

Solver.py

from Crypto.Util.number import *
import string
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667
k = 131
enc = 84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096
prlist = []
for i in range(2,1000000):
  if isPrime(i): prlist.append(i)
  if len(prlist) == k: break


def calc1(L1, L2):
  L1.reverse()
  val = 1
  for i in range(0, len(L1), k):
    print(i)
    val = val*val%n
    for j in range(0,k):
      if L1[i+j] == 1: val = val * prlist[j] % n
  L2.reverse()
  for i in range(0, len(L2), k):
    val = val*val%n
    for j in range(0,k):
      if L2[i+j] == 1: val = val * prlist[j] % n
  
  return val


base = 129105988525739869308153101831605950072860268575706582195774923614094296354415364173823406181109200888049609207238266506466864447780824680862439187440797565555486108716502098901182492654356397840996322893263870349262138909453630565384869193972124927953237311411285678188486737576555535085444384901167109670365



target = enc * inverse(base, n)
D = dict()
for a1 in string.printable:
  for a2 in string.printable:
    for a3 in string.printable:
      i = bytes_to_long((a1+a2+a3).encode())
      s = bin(i)[2:].zfill(24)
      val = 1
      for j in range(24):
        if s[j]=='1':
          val = val * prlist[j+21] * prlist[j+21] % n
      D[val] = a1+a2+a3

for a1 in string.printable:
  print("now2 ", a1)
  for a2 in string.printable:
    for a3 in string.printable:
      i = bytes_to_long((a1+a2+a3).encode())
      s = bin(i)[2:].zfill(24)
      val = 1
      for j in range(24):
        if s[j]=='1':
          val = val * prlist[j+45] * prlist[j+45] % n
      tt = target * inverse(val, n) % n
      if tt in D:
        print("flag : hitcon{"+D[tt]+a1+a2+a3+"}")