NCTF2024

发表于 2025-03-24

因为一些小细节导致中午就打通的绮云一直到晚上才过了远程/(ㄒoㄒ)/~~，以至于后面心态有点炸了到了第二天晚上才做完前面3题。

故障注入那块是真没研究过只能先搁着了(●'◡'●)

绮云

题目

from Crypto.Util.number import *
from os import getenv,urandom
from hashlib import sha256
from random import randint

class ECDSA:
    def __init__(self):
        self.p = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
        self.a = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
        self.b = 0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
        self.n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
        self.Gx = 0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
        self.Gy = 0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0
        self.G = (self.Gx,self.Gy)

        self.d = getPrime(232)
        self.Q = self.mul(self.d,self.G)
        assert self.is_on_curve(self.Q)

    def is_on_curve(self, point):
        if point is None:
            return True
        x, y = point
        return (y**2 - x**3 - self.a * x - self.b) % self.p == 0

    def add(self, p1, p2):
        if p1 is None or p2 is None:
            return p1 if p2 is None else p2

        x1, y1 = p1
        x2, y2 = p2

        if x1 == x2 and y1 != y2:
            return None
        if x1 == x2:
            m = (3 * x1 * x1 + self.a) * pow(2 * y1, -1,  self.p) % self.p
        else:
            m = (y2 - y1) * pow((x2 - x1) % self.p, -1, self.p) % self.p
        
        x3 = (m * m - x1 - x2) % self.p
        y3 = (m * (x1 - x3) - y1) % self.p
        return (x3, y3)

    def mul(self, k:int, P:tuple[int,int]):
        if P is None:
            return None
        
        R = None        
        while k > 0:
            if k & 1:
                R = self.add(R, P)
            P = self.add(P,P)
            k >>= 1
        return R

    def generate_key_pair(self):
        return self.d,self.Q

    def sign(self, message):
        while True:
            k = randint(1, self.n - 1)
            P = self.mul(k, self.G)
            if P is None:
                continue
            
            r = P[0] % self.n
            if r == 0:
                continue

            s = (pow(k,-1,self.n) * (int.from_bytes(sha256(message).digest())+ self.d * r)) % self.n
            if s != 0:
                return (r, s)

    def verify(self, m:bytes, r:int,s:int):
        if not (1 <= r < self.n and 1 <= s < self.n):
            return False
        
        u1 = (int.from_bytes(sha256(m).digest()) * pow(s,-1,self.n)) % self.n
        u2 = (r * pow(s,-1,self.n)) % self.n

        if u1 == 0 or u2 == 0:
            return False

        P = self.add(self.mul(u1, self.G), self.mul(u2, self.Q))        
        return P[0] % self.n == r

class RSA:
    def __init__(self,d:int):
        p = getStrongPrime(1024)
        q = getStrongPrime(1024)
        
        assert GCD(d,(p-1)*(q-1)) == 1

        self.N = p * q
        self.d = d
        self.e = pow(d,-1,(p-1)*(q-1))

    def encrypt(self,m:int,idx:int):
        return pow(m,self.e ^ (1 << idx),self.N)
    
def check():
    r,s = list(map(int,input('Give me your signature:').split()))
    if e.verify(f'nctf2024-{urandom(1).hex()}'.encode(),r,s):
        print(f'Congratulations! Here is your flag: {getenv("FLAG")}')
        exit()
    else:
        print('Wrong!')


if __name__=='__main__':
    e = ECDSA()
    print('Can you navigate yourself through QiYun Valley with only the encryption orcale?')

    menu = '''
--- Menu ---
[1] Initialize encryption orcale
[2] Check your signature
[3] Exit'''

    while True:
        print(menu)
        opt = input('Your option:').strip()
        
        if opt=='1':
            print('Generating new public key pair for you...')
            rsa = RSA(e.d ** 4)

            while input("Enter 'e' for encryption or other to exit:").strip() == "e":
                m = int(input('Enter your message:'),16)
                x = int(input('Where do you want to interfere?'))

                print(f'Result:{hex(rsa.encrypt(m,x))[2:]}')

        elif opt=='2':
            check()
        
        elif opt=='3':
            print('Bye~')
            exit()

        else:
            print('Invalid option')

题目分为了两部分，第一部分是通过 RSA 来获取 ECDSA 的私钥，第二部分是利用 ECDSA 的私钥来爆破消息的签名。

首先看第一部分，题目给出了一个 RSA 但是并没有给出其的任何公钥，所以我们肯定要先恢复 $n$ 和 $e$ 。

恢复 $n$ 是简单的，我们只要发送多个 $x$ 和 $x^2$ 即可。然后我们看恢复 e，这个 RSA 每次加密时我们可以指定一个 bit 发生翻转。也就是说我们有

m^{e\pm2^i}\equiv c'\mod n

我们固定 $m$ 不动，并且直接假设 $e$ 的最低位为1(虽然的确如此)，那么我们是知道 $m^e\equiv c\mod n$ 的。我们可以通过验证 $c'^{\pm2^i}\equiv c$ 是否成立即可，然后 bit by bit 的恢复出 $e$ 。

然后我们下一步就是恢复私钥了，我们可以发现对于不同的 RSA 公钥都用了相同的私钥，故我们可以考虑共私钥攻击，实测取10个 RSA 的数据即可恢复。

最后就是 ECDSA 了，不过所有参数都有了直接爆破就好了。

from Crypto.Util.number import *
from sage.all import *
from pwn import *
from hashlib import sha256

# preparatory work
def ch(c:int):
    c = str(c).encode()
    while 1:
        a = r.recvline()
        if b'Exit' in a:
            break
    r.sendlineafter(b'Your option:', c)


# r = process(['python', 'chal.py'])
r = remote('39.106.16.204', 55066)

# solve n and e
def solve_(m, x=0, n=True):
    r.sendlineafter(b"Enter 'e' for encryption or other to exit:", b'e')
    r.sendlineafter(b'Enter your message:', hex(m)[2:])
    r.sendlineafter(b'Where do you want to interfere?', str(x).encode())
    c_ = int(r.recvline().decode().split(':')[-1], 16)
    c = c_ * m
    if n: return c
    else: return c_

N = []; E = []
while 1:
    ch(1)
    r.recvline()
    m = 1337; m2 = 1337 ** 2; m3 = 727; m4 = 727 ** 2; m5 = 114514; m6 = 114514 ** 2; m7 = 12345678; m8 = 12345678 ** 2
    c = solve_(m); c2 = solve_(m2); c3 = solve_(m3); c4 = solve_(m4); c5 = solve_(m5); c6 = solve_(m6); c7 = solve_(m7); c8 = solve_(m8)
    n = GCD(c ** 2 - c2, c3 ** 2 - c4)
    n = GCD(n, c5 ** 2 - c6)
    n = GCD(n, c7 ** 2 - c8)
    e_1, x = 1, 0
    while (x:= x + 1) and x <= 2048:
        print(f'x = {x}')
        c_ = solve_(m, x, n=False)
        for i in [-1, 1]:
            c__ = c_ * pow(m, i * 2**x, n) % n
            if c__ == c % n:
                e_1 += (i + 1) // 2 << x
                break
    if pow(m, e_1, n) == c % n:
        e = e_1; N.append(n); E.append(e)
    else: print('error')
    print(f'len = {len(N)}')
    r.sendlineafter(b"Enter 'e' for encryption or other to exit:", b'x')
    if len(N) == 10:
        break

# solve d
def solve_d(N, E):
    M = matrix(len(N)+1)
    D = 2 ** 1024
    M[0, 0] = D
    for i in range(1, len(N) + 1):
        M[i, i] = -N[i - 1]
        M[0, i] = E[i - 1]

    mm = M.LLL()
    d_ = abs(mm[0][0])//D
    return d_

d = sqrt(sqrt(solve_d(N, E)))
print(d)

# solve flag
class ECDSA:
    def __init__(self, d):
        self.p = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
        self.a = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
        self.b = 0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
        self.n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
        self.Gx = 0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
        self.Gy = 0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0
        self.G = (self.Gx,self.Gy)

        self.d = d
        self.Q = self.mul(self.d,self.G)
        assert self.is_on_curve(self.Q)

    def is_on_curve(self, point):
        if point is None:
            return True
        x, y = point
        return (y**2 - x**3 - self.a * x - self.b) % self.p == 0

    def add(self, p1, p2):
        if p1 is None or p2 is None:
            return p1 if p2 is None else p2

        x1, y1 = p1
        x2, y2 = p2

        if x1 == x2 and y1 != y2:
            return None
        if x1 == x2:
            m = (3 * x1 * x1 + self.a) * pow(2 * y1, -1,  self.p) % self.p
        else:
            m = (y2 - y1) * pow((x2 - x1) % self.p, -1, self.p) % self.p
        
        x3 = (m * m - x1 - x2) % self.p
        y3 = (m * (x1 - x3) - y1) % self.p
        return (x3, y3)

    def mul(self, k:int, P:tuple[int,int]):
        if P is None:
            return None
        
        R = None        
        while k > 0:
            if k & 1:
                R = self.add(R, P)
            P = self.add(P,P)
            k >>= 1
        return R

    def generate_key_pair(self):
        return self.d,self.Q

    def sign(self, message):
        while True:
            k = randint(1, self.n - 1)
            P = self.mul(k, self.G)
            if P is None:
                continue
            
            r = P[0] % self.n
            if r == 0:
                continue

            s = (pow(k,-1,self.n) * (int.from_bytes(sha256(message).digest())+ self.d * r)) % self.n
            if s != 0:
                return (r, s)

    def verify(self, m:bytes, r:int,s:int):
        if not (1 <= r < self.n and 1 <= s < self.n):
            return False
        
        u1 = (int.from_bytes(sha256(m).digest()) * pow(s,-1,self.n)) % self.n
        u2 = (r * pow(s,-1,self.n)) % self.n

        if u1 == 0 or u2 == 0:
            return False

        P = self.add(self.mul(u1, self.G), self.mul(u2, self.Q))        
        return P[0] % self.n == r

dsa = ECDSA(int(d))
while 1:
    for i in range(256):
        ch(2)
        msg = f'nctf2024-{hex(i)[2:].zfill(2)}'.encode()
        rr, ss = dsa.sign(msg)
        r.sendlineafter(b'Give me your signature:', str(rr).encode() + b' ' + str(ss).encode())
        a = r.recvline()
        if b'Wrong!' not in a:
            print(a)
            break
        print(a)

Sign

题目

util.py

from os import urandom
from Crypto.Util.number import *

def getrandint(n:int):
    return int.from_bytes(urandom(n//8+1)) % pow(2,n)

class FHE:
    def __init__(self):
        self.p = getPrime(77)
        self.pubkeys = []
        for _ in range(16):
            self.pubkeys.append(self.p * getrandint(177) + (getrandint(17) << 8))

    def encrypt(self,msg:list[int] | bytes):
        result = []
        for m in msg:
            tmp = 0
            shuffle_base = urandom(16)
            for i in shuffle_base:
                x,y = divmod(i,16)
                tmp += x*self.pubkeys[y] + y*self.pubkeys[x]
            result.append(tmp + m)
        return result

srv.py

from Crypto.Util.number import *
from util import *
from os import getenv
from Crypto.Util.Padding import pad
from random import Random
from Crypto.Cipher import AES
from hashlib import md5

string = open('secret.txt').read().strip().encode()
flag = getenv('FLAG').encode()

if __name__=='__main__':
    Keys = []
    for m in string:
        f = FHE()
        s = long_to_bytes(Random().getrandbits(20000))
        for i in s[4:]:
            Keys.extend(f.encrypt([i]))

        for i in s[:4]:
            Keys.extend(f.encrypt([i * (m & 0x03) % 0x101]))
            m >>= 2
        
    assert len(Keys) == 30000

    print(f'[+] Your ciphertext: {AES.new(md5(string).digest(),AES.MODE_ECB).encrypt(pad(flag,16)).hex()}')
    input(f'[+] The keys to retrieve the global internet connection are as follows:')
    for i in range(30000):
        print(f'[+] {Keys[i]}')

FHE 是基于 AGCD 的，然后私钥又很小故可以直接用格打出来。然后 s 是用MT19937生成的，我们可以直接来预测。

from Crypto.Util.number import *
from agcd_attack import attack
from output import output
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import trange

def mt19937(out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = []
    zeros.append(rng.getrandbits(19968) ^ int(out))
    zeros.append(mt[0] ^ int(0x80000000))
    sol = lin.solve_one(zeros)
    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    return pyrand

# solve rng
block = 2500
c = [output[i * block : i * block + block] for i in range(len(output) // block)]
rngs = []
for i in trange(len(c)):
    out = c[i]
    cc = out[:10]
    p = attack(cc, 30)
    cf = out[:-4]
    u = []
    for i in cf:
        u.append(i % p % 256)
    m = bytes_to_long(bytes([0] * 4 + u))
    rng = mt19937(m)
    rngs.append(rng)

# solve key
ms = []
iii = 0
for out in c:
    s = long_to_bytes(rngs[iii].getrandbits(20000))
    cc = out[:10]
    p = attack(cc, 30)
    cf = out[-4:]
    u = []
    for i in cf:
        u.append(i % p % 256)
    ss = [i for i in s[:4]]
    for m in range(256):
        if all(ss[i] * ((m >> 2 * i) & 0x03) % 0x101 == u[i] for i in range(4)):
            ms.append(m)
            break
    print(ms)
    iii += 1

# solve flag
from Crypto.Cipher import AES
from hashlib import md5

enc = 'b76796081756e51e16e937ee2c6b913327cfc2b3008241e9b0b9387e908cfaf1f62d73bcdd98c670b6f84f22d94523c0'
String = bytes(ms)
print(AES.new(md5(String).digest(),AES.MODE_ECB).decrypt(bytes.fromhex(enc)))

agcd_attack.py

# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/ol.py
from sage.all import *

def symmetric_mod(x, m):
    return int((x + m + m // 2) % m) - int(m // 2)

def attack(x, rho):
    assert len(x) >= 2

    R = 2 ** rho

    B = matrix(ZZ, len(x), len(x) + 1)
    for i, xi in enumerate(x):
        B[i, 0] = xi
        B[i, i + 1] = R

    B = B.LLL()

    K = B.submatrix(row=0, col=1, nrows=len(x) - 1, ncols=len(x)).right_kernel()
    q = K.an_element()
    r0 = symmetric_mod(x[0], q[0])
    p = abs((x[0] - r0) // q[0])
    return int(p)

Arcahv

题目

from Crypto.Util.number import *
from os import urandom,getenv
from functools import reduce
from Crypto.Cipher import AES

class LCG:
    def __init__(self,seed:int) -> None:
        self.p = getPrime(1024)
        self.a = getPrime(1023)
        self.b = getPrime(1023)
        self.status = seed

    def next(self) -> int:
        ret = self.status
        self.status = (self.status * self.a + self.b) % self.p
        return ret
    
def crystal_trick(m:bytes) -> bytes:
    m = bytearray(m)
    for i in range(len(m)):
        m[i] = reduce(lambda x,y: x^y^urandom(1)[0],m[:i],m[i])
    return m

class RSA:
    def __init__(self):
        p = getStrongPrime(1024)
        q = getStrongPrime(1024)
        self.p = p
        self.N = p * q
        self.e = 65537
        self.d = pow(self.e, -1, (p-1)*(q-1))

    def encrypt(self,m:int) -> int:
        return pow(m,self.e,self.N)
    
    def decrypt(self,c:int) -> int:
        return pow(c,self.d,self.N) 

class MyRSA1(RSA):
    def encrypt(self,m:bytes) -> bytes:
        return super().encrypt(int.from_bytes(m)).to_bytes(256)
    
    def decrypt(self,c:bytes) -> bytes:
        return super().decrypt(int.from_bytes(c)).to_bytes(256)

class MyRSA2(RSA):
    def encrypt(self,m:bytes) -> bytes:
        return pow(int.from_bytes(m),self.e,self.N).to_bytes(256,'little')
    
    def decrypt(self,c:bytes) -> bytes:
        m = pow(int.from_bytes(c),self.d,self.N).to_bytes(256,'little')
        print('Hibiscus is here to trick your decryption result!!')
        return crystal_trick(m)

menu = '''
Welcome to NCTF 2025 arcahv challenge!

--- Menu ---
[1] View encrypted flag and hint
[2] Play with the decryption orcale
[3] Get some random numbers for fun
[4] Exit

Your Option > '''


if __name__=='__main__':
    print('Loading, please wait...')
    
    # flag = open('flag.txt').read().strip().encode()
    flag = getenv('FLAG').encode()
    attempts = 75
    r1 = MyRSA1()
    r2 = MyRSA2()
    hint1 = r2.encrypt(r1.p.to_bytes(128))

    key = urandom(16)
    hint2 = AES.new(key,AES.MODE_ECB).encrypt(r1.N.to_bytes(256))

    def flag_and_hint():
        print(f'Encrypted flag: {r1.encrypt(flag).hex()}')
        print(f'Hint1: {hint1.hex()}')
        print(f'Hint2: {hint2.hex()}')

    def rsachal(): 
        global attempts

        print("Since you didn't v Hibiscus 50 on crazy thursday, Hibiscus decided to do some trick on your decryption result!")
        print(f'Your pubkey:({hex(r2.N)[2:]},{hex(r2.e)[2:]})')

        while attempts > 0:
            if input('Do you still want to try decryption(y/[n])?') != 'y':
                break

            c = bytes.fromhex(input(f'You have {attempts} remaining access to decryption orcale!\nYour ciphertext(in hex):'))
            print(f'Result: {r2.decrypt(c).hex()}')
            attempts -= 1
        
        if attempts == 0:
            print('Unfortunately, you are out of decryption attempts! Come back again on nctf2026 ~')

    
    def lcgchal():
        lcg = LCG(int.from_bytes(key))

        print('Tempering with LCG generator, please wait...')
        while urandom(1)[0] & 0xff:
            lcg.next()
        
        hexnums = ''.join(hex(lcg.next())[2:] for _ in range(5))
        if len(hexnums) % 16:
            hexnums = hexnums.zfill((len(hexnums) // 16 + 1) * 16)
        
        idx = 0
        while input('Do you want another unsigned long long number(y/[n])?') == 'y':
            print(int(''.join(hexnums[idx:idx+16]),16))
            idx = (idx + 16) % len(hexnums)

    def bye():
        print('Hope you have fun during the challenge XD:)')
        exit(0)

    fundc = {1:flag_and_hint,2:rsachal,3:lcgchal,4:bye}

    while True:
        opt = input(menu)
        if len(opt) == 0 or opt not in '1234':
            opt = '4'
        fundc[int(opt)]()

题目分为两个部分，第一部分是解 RSA2 拿到 RSA1 的 p 高位，第二部分是解 LCG 的参数来拿到 RSA1 的 n，然后解 RSA1 拿 flag。

先看 LCG 的部分，给出了5组数据直接就可以恢复参数了，这个没啥好说的。

然后看 RSA2 的部分，它在解密的时候做了一个混淆，混淆的方式如下：

假如输入的字符串为 abc，那么输出为 a|a xor b xor 未知|a xor b xor c xor 未知

其实可以发现这个就类似 MSB Oracle Attack，具体可以看 solver。

然后这个是不能解出完整的 p 的，只能解出大概 584 位的高位，但是打 copper 已经绰绰有余。

拿到后解个 RSA 就得到 flag 了。

from Crypto.Util.number import *
from sage.all import *
from fractions import Fraction
from pwn import *
from Crypto.Cipher import AES


# preparatory work
def ch(c:int):
    c = str(c).encode()
    while 1:
        a = r.recvline()
        if b'Exit' in a:
            break
    r.sendlineafter(b'Your Option > ', c)

# r = process(['python', 'chal.py'])
r = remote('39.106.16.204', 39702)
ch(1)
enc_flag = int(r.recvline().strip().split(b': ')[-1], 16)
hint1 = r.recvline().strip().split(b': ')[-1]
hint2 = bytes.fromhex(r.recvline().strip().split(b': ')[-1].decode())

# solve lcg
ch(3)

def solve(output):
    t=[]
    for i in range(len(output)-1):
        t.append(output[i+1]-output[i])
    j=[]
    for i in range(len(t)-3):
        j.append(GCD((t[i+2]*t[i]-t[i+1]*t[i+1]), (t[i+3]*t[i+1]-t[i+2]*t[i+2])))
    if not isPrime(j[0]):
        m = list(factor(j[0]))[-1][0]
    else:m = j[0]
    print(f'p = {m}')
    a=(output[2]-output[1])*inverse(output[1]-output[0],m)%m
    b=(output[1]-a*output[0])%m
    if isPrime(a) and isPrime(b) and isPrime(m):
        return a, b, m

r.recvline()
output = []
for i in range(80):
    r.sendlineafter(b'Do you want another unsigned long long number(y/[n])?', b'y')
    output.append(int(r.recvline()))
hexnums = ''.join(hex(i)[2:].zfill((j:=len(hex(i)[2:])) + j % 2) for i in output)
if len(hexnums) % 16:
    hexnums = hexnums.zfill((len(hexnums) // 16 + 1) * 16)

bits = len(hexnums) // 5
out = [int(hexnums[bits * i : bits * i + bits], 16) for i in range(5)]
aa, bb, pp = solve(out)
print(f'p = {pp}, a = {aa}, b = {bb}')
out = out[-1]
for i in range(555):
    key = long_to_bytes(out)
    out = (out - bb) * inverse(aa, pp) % pp
    if len(key) == 16:
        print(f'key = {key}')
        break

N = bytes_to_long(AES.new(key,AES.MODE_ECB).decrypt(hint2))
print(f'N = {N}')
r.sendlineafter(b'Do you want another unsigned long long number(y/[n])?', b'n')

# solve p
ch(2)
r.recvline()
a=r.recvline().strip().split(b':')[-1].decode()
N2=bytes.fromhex(a[1:-7])
e2=65537
N2=bytes_to_long(N2)

hint1=bytes.fromhex(hint1.decode())
hint1=int.from_bytes(hint1,'little')

c=(hint1*pow(2,1016*e2,N2))%N2

map = {}
for i in range(0, 256):
    map[-N2 * i % 256] = i

cipher256 = pow(256,e2,N2)
backup = hint1

L = Fraction(0, 1)
R = Fraction(1, 1)
for i in range(74):
    r.sendlineafter(b"Do you still want to try decryption(y/[n])?",b"y")
    c = c * cipher256 % N2
    hex_c = hex(c)[2:]
    r.sendlineafter("Your ciphertext(in hex):",(hex_c.zfill(len(hex_c) + len(hex_c) % 2)).encode())
    r.recvline()
    m=r.recvline()[8:-1]
    m=bytes.fromhex(m.decode())
    b=m[0]
    k = map[b]
    L, R = L + Fraction(k, 256**(i+1)), L + Fraction(k+1, 256**(i+1))
M = int(L * N2)
r.sendlineafter(b"Do you still want to try decryption(y/[n])?",b"y")
r.recvline()
r.sendlineafter("Your ciphertext(in hex):",(hex(backup)[2:]).encode())
r.recvline()
m=r.recvline()[8:-1]

m=bytes.fromhex(m.decode())
b=m[0]
mmm = M - M % 256 + b
ph = mmm >> (2048-584)
ph <<= (1024-576)
print(ph)
x = PolynomialRing(Zmod(N), 'x').gen()
f = ph + x
pl = int(f.small_roots(X = 2**448, beta=0.4)[0])
p = pl + ph
assert N % p == 0

# solve flag
q = N // p
d = inverse(65537, (p - 1) * (q - 1))
print(long_to_bytes(pow(int(enc_flag), int(d), int(N))))