Crypto CTF 2021 | Rima

#cryptoctf2021

#!/usr/bin/env python

from Crypto.Util.number import *
from flag import FLAG

def nextPrime(n):
    while True:
        n += (n % 2) + 1
        if isPrime(n):
            return n

f = [int(x) for x in bin(int(FLAG.hex(), 16))[2:]]

f.insert(0, 0)
for i in range(len(f)-1): f[i] += f[i+1]

a = nextPrime(len(f))
b = nextPrime(a)

g, h = [[_ for i in range(x) for _ in f] for x in [a, b]]

c = nextPrime(len(f) >> 2)

for _ in [g, h]:
    for __ in range(c): _.insert(0, 0)
    for i in range(len(_) -  c): _[i] += _[i+c]

g, h = [int(''.join([str(_) for _ in __]), 5) for __ in [g, h]]

for _ in [g, h]:
    if _ == g:
        fname = 'g'
    else:
        fname = 'h'
    of = open(f'{fname}.enc', 'wb')
    of.write(long_to_bytes(_))
    of.close()

ひたすら面倒な問題っぽい

多少わかりやすく書き直すとメインロジックはこう

最初の len(g) = len(f) * a, len(h) = len(f) * b となっている

flag = b"hello world"
f = [int(x) for x in bin(int(flag.hex(), 16))[2:]]

f.insert(0, 0)
for i in range(len(f)-1):
    f[i] += f[i+1]

a = nextPrime(len(f))
b = nextPrime(a)

g = f * a
h = f * b

c = nextPrime(len(f) >> 2)

g = [0 for _ in range(c)] + g
for i in range(len(g) - c):
    g[i] += g[i + c]

h = [0 for _ in range(c)] + h
for i in range(len(h) - c):
    h[i] += h[i + c]



g = int("".join([str(x) for x in g]), 5)
h = int("".join([str(x) for x in h]), 5)

import gmpy2
import numpy
from copy import deepcopy


def decrypt(g, k):
    c = int(gmpy2.next_prime(k >> 2))
    for i in range(len(g)-c)[::-1]:
        g[i] -= g[i+c]
        assert g[i] >= 0

    g = g[c:]
    for i in range(0, k)[::-1]:
        g[i] -= g[i+1]
        assert g[i] >= 0

    return g[1:k]


def main():
    print("loading...")
    with open("g.enc", "rb") as f:
        g = int.from_bytes(f.read(), "big")

    # with open("h.enc", "rb") as f:
    #     h = int.from_bytes(f.read(), "big")

    g = [int(c) for c in numpy.base_repr(g, 5)]
    # h = [int(c) for c in numpy.base_repr(h, 5)]
    print("done")

    for k in range(200, 300):
        try:
            binarr = decrypt(deepcopy(g), k)
        except AssertionError:
            continue
        if all([0 <= b <= 1 for b in binarr]):
            bint = int("".join([str(b) for b in binarr]), 2)
            print(k, hex(bint))

if __name__ == "__main__":
    main()