Very Simple Haskell (HITCON CTF 2019) writeup by NGG from !SpamAndHex

solve.py

#!/usr/bin/env python2

"""
As I'm not confident enough in my own Haskell comprehension skills, I started with reimplementing the whole thing in Python,
checking each function if it does the same thing.

At the end it seemed like it does the following:
- There is some padding of the flag based on its length (which we know, so it will be irrelevant)
- The flag is treated as a bit string
- Each bit position has a value assigned to it based on primes
- For every 1-bit in the padded flag, the corresponding values are multiplied together (mod n)

So I tried the easiest method to find the flag, and fortunately it worked:
- Calculate the value for the 0..0 input (as a bitstring) -> the base value
- Calculate the value for each input that has exactly 1 1-bit, dividing it by the base value -> these are the values corresponding to bitpositions
- Try to set those bits to 1 for which the output is divisible by the bit-position value
- It worked...
"""

from sage.all import *
import binascii
n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667
k = 131
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739]

def stringToInteger(s):
    return int(binascii.hexlify(s), 16)

def integerToString(n):
    x = '%x'%n
    if len(x)%2 == 1:
        x = '0'+x
    return binascii.unhexlify(x)

def numToBits(n):
    return map(int, bin(n)[2:])

def extendBits(bl, arr):
    if len(arr)%bl == 0:
        return arr
    return [0]*(bl - len(arr)%bl) + arr

def calc(num, arr):
    if len(arr) == 0:
        return num
    num2 = pow(num, 2, n)
    block, restArr = arr[:k], arr[k:]
    zipped = [block[i]*primes[i]%n for i in range(k)]
    mul = 1
    for z in zipped:
        if z != 0:
            mul *= z
    result = num2*mul%n
    return calc(result, restArr)

def magic(inp):
    num = stringToInteger(inp)
    bits = numToBits(num)
    extended = list(reversed(extendBits(8, bits)))
    oriLen = len(extended)
    extendedBits = extendBits(k, extended)
    oriLenBits = numToBits(oriLen)
    extendedOriLenBits = extendBits(k, oriLenBits)
    finalBits = extendedOriLenBits + extendedBits
    return calc(1, list(reversed(finalBits)))

def magicflag(n):
    flag = integerToString(n)
    if len(flag) < 6:
        flag = '\x00'*(6-len(flag)) + flag
    assert len(flag) == 6
    return magic('the flag is hitcon{' + flag + '}')

m0 = magicflag(0)
m0inv = inverse_mod(m0, n)
d = [magicflag(2**b)*m0inv%n for b in range(6*8)]
out = 84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096
diff = out*m0inv%n

bits = ['1' if diff%d[b] == 0 else '0' for b in range(6*8)]
assert magicflag(int(''.join(reversed(bits)), 2)) == out
print 'hitcon{' + integerToString(int(''.join(reversed(bits)), 2)) + '}'