NCTF2024 Crypto Official Writeup

2025-03-19

Hibiscus 为~~鸽到2025年的nctf2024~~命制了三道Crypto题，下述为官方Writeup。

NCTF2024 Crypto部分附件：github
NCTF2024 全部附件：github

Sign

这是恢复互联网的密钥，密码是实时生成的三万个随机数。

解析

~~签到题~~，主要是两部分：MT19937的逆向、和基于AGCD问题的FHE（全同态加密）。

显然我们的目标就是恢复string。而题目对string实行了逐字节加密，具体地：

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

对于每一个字节，分别初始化了一个FHE、使用Random().getrandbits(20000)拿到了20000位随机数，将随机数的后19968位加密后直接输出，前32位用于和string的当前字节m按一个自定义规则进行加密。

python中getrandbits(n) 在 $n > 32$ 时会多次调用getrandbits(32)，将新随机数拼接在既有随机数的高位。如此，显然我们需要利用这个大随机数的后（低）19968位来预测前（高）32位的值。
已知完整的一组state的情况下随机数预测部分的资料/既有脚本都比较多~~实在不行问deepseek~~，这里不再赘述。任务由此变成了解密FHE。

FHE（全同态加密）相关：对于一个加/解密系统 $(E,D)$ 和其域下任意的 $(m_i,c_i)$ ，
若其满足 $E(\sum_{i=1}^{n} m_i) = \sum_{i=1}{n} c_i$ 且 $D(\sum_{i=1}^{n} c_i) = \sum_{i=1}^{n} m_i$ ，则称其是（完全）加法同态的；
若其满足 $E(\prod_{i=1}^{n} m_i) = \prod_{i=1}{n} c_i$ 且 $D(\prod_{i=1}^{n} c_i) = \prod_{i=1}^{n} m_i$ ，则称其是（完全）乘法同态的；
若 $(E,D)$ 既是加法同态又是乘法同态的，则称之为全同态加密系统。

再观察FHE的加密逻辑：

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

初始化时，其会选定一个质数 $p$ ，随后生成了一个公钥集 $\{pk_i\}$ ，其中 $pk_i = pa_i + 256*b_i$ ， $\log_{2}a_i \approx 177$ ， $\log_{2}b_i \approx 17$ 。
每次加密 $m < 256$ ，选择公钥集的一个随机小系数（各维度不大于16）的线性组合，与 $m$ 求和得到密文。

首先考虑解密逻辑：AGCD-FHE的解密关键点在于获得私钥 $p$ 。
获得 $p$ 后，对于任意密文 $c = k_1p + 256*k_2 + m$ ， $m < 256$ 、 $256*k_2 < p$ 时不难证明存在 $m \equiv (c \bmod p) \bmod 256$ 。

此处不难发现FHE（全同态加密）性质的具体体现：
记加密函数为 $E$ ，显然 $Z_{256}$ 下 $E(\sum_{i=1}{n} m_i) = \sum_{i=1}{n} c_i$ 。解密亦然，在 $n$ 不太大时近似认为其是完全加法同态的。
同理可知其也存在乘法同态，但基于AGCD的FHE在进行密文乘时误差累积非常快，因而某种意义上只能算“部分”乘法同态。相比之下如RSA就满足完全乘法同态。

而对AGCD-FHE的攻击可以通过构造格进行。

AGCD(Approximate Greatest Common Divisor)/近似最大公约数问题简介：
已知 $\{pq_1 + e_1,pq_2 + e_2, \cdots, pq_n + e_n\}$ ，满足 $e_i << p$ ，求 $p$ 。
可以发现其相较传统的GCD问题“无非”就是多了误差 $e_i$ ，但这会让求最大公约数的经典算法全部失效，必须另辟蹊径。

以上述AGCD的参数名为例：
记 $x_i = pq_i + e_i$ ，注意到存在 $x_0q_i - x_iq_0 = e_0q_i - e_iq_0$ ，其中 $\{x_i\}$ 均已知， $\{q_i\}$ 是未知的整数， $\{e_i\}$ 是未知的小整数。
构造格的矩阵等式如下：

$\begin{bmatrix}q_1 & q_2 & \cdots & q_n & q_0 \end{bmatrix} \cdot \begin{bmatrix} \\ -x_0 \\ & -x_0 \\ && \ddots \\ &&& -x_0 \\ x_1 & x_2 & \cdots & x_n & 2^{\rho + 1} \end{bmatrix} = \begin{bmatrix} e_1q_0 - e_0q_1 & e_2q_0 - e_0q_2 & \cdots & e_nq_0 - e_0q_n & q_{0}2^{\rho+1} \end{bmatrix}$

显然锚定的是格中的短向量（ $2^{\rho + 1}$ 用于配平），对格进行规约即可还原出 $q_0$ ，随后计算 $e_0 \equiv x_0 (\bmod q_0)$ 、 $p = \frac{x_0-e_0}{q_0}$ 。
获得 $p$ 后，完成对加密后数字的解密，随后MT19937逆向+预测随机数后，梳理下后续的模乘逻辑等步骤就都比较普通了。

完整exp

# sage
__import__('os').environ['TERM'] = 'xterm'

from sage.all import * 
from Crypto.Util.number import *
from functools import reduce
from random import *
from pwn import *
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from hashlib import md5

def inv_shift_right(x:int,bit:int,mask:int = 0xffffffff) -> int:
    tmp = x 
    for _ in range(32//bit):
        tmp = x ^^ tmp >> bit & mask
    return tmp

def inv_shift_left(x:int,bit:int,mask:int = 0xffffffff) -> int:
    tmp = x
    for _ in range(32//bit):
        tmp = x ^^ tmp << bit & mask
    return tmp

def rev_extract(y:int) -> int:
    y = inv_shift_right(y,18)
    y = inv_shift_left(y,15,4022730752)
    y = inv_shift_left(y,7,2636928640)
    y = inv_shift_right(y,11)
    return y

def exp_mt19937(output:list) -> int:
    assert len(output) == 624
    cur_stat = [rev_extract(i) for i in output]
    r = Random()
    r.setstate((3, tuple([int(i) for i in cur_stat] + [624]), None))
    return r.getrandbits(32)

io = remote('39.106.16.204',24259)
io.recvuntil(b':')
aes_cipher = bytes.fromhex(io.recvline().strip().decode())
io.sendlineafter(b':',b'')
msg = []
for _ in range(30000):
    io.recvuntil(b'[+]')
    msg.append(int(io.recvline().strip().decode()))

io.close()
msg = [msg[i:i+2500] for i in range(0,30000,2500)]


d1 = []
for dx in range(12):
    cp = msg[dx]

    mt = matrix(ZZ,21,21)
    for i in range(20):
        mt[i,i] = cp[-1]
        mt[-1,i] = cp[i]
    
    const = 2 ^ 30
    mt[-1,-1] = const
    mt = mt.LLL()

    temp = abs(mt[0,-1])
    assert temp % const == 0

    q0 = temp / const
    e0 = ZZ(cp[-1] % q0)
    p = ZZ((cp[-1] - e0) / q0)

    d1.append(list(map(lambda x: x % p % 256,cp)))

d2 = b''

for dx in range(12):
    ran_output = [bytes_to_long(bytes(d1[dx][i:i+4])) for i in range(0,2496,4)]
    invmul_key = [pow(i,-1,0x101) for i in long_to_bytes(exp_mt19937(ran_output[::-1]))]

    res = []
    for i in range(4):
        res.append(invmul_key[i] * d1[dx][-4 + i] % 0x101)

    assert all(0 <= i < 4 for i in res)
    res.reverse()
    d2 += bytes([reduce(lambda x,y: 4*x+y,res)])
    
print(unpad(AES.new(md5(d2).digest(),AES.MODE_ECB).decrypt(aes_cipher),16).decode())

Arcahv

Delightful.

解析

题如其名 —— Arcahv，聚合，大杂烩。
核心考点包括 RSA LSB Orcale ~~Pro Max版~~，LCG，Coppersmith。

RSA LSB Orcale

最简单的RSA LSB Orcale应是RSA Parity Orcale（奇偶Orcale，每次解密返回结果的奇偶性），此时攻击所需要的次数为 $\lceil \log_{2}N \rceil$ 。
同样地，如果LSB Orcale每次返回的值是解密结果对 $2^{k}$ 取模的结果，则解密所需要的次数应为 $\lceil log_{2^{k}}N = \lceil \frac{log_{2}N}{k} \rceil$ 。

本题首先大幅约束了解密次数，旨在考验各位师傅对于 Parity Orcale的理解和数论推导。

Parity Orcale的核心就是“溢出”导致的余数变化，以及我们根据RSA的乘法同态能构造出使解密结果为 $Cm (\bmod N)$ 的密文。

通过在 $Z_{p}$ 下将密文乘以 $C^{e}$ ，我们解密得到的明文即为。显然存在等式。本题中由于我们可以得到，因而亦令 $C = 256$ 。由此，
- 若 $k = 0$ ，由于 $256m \equiv 0 (\bmod 256)$ ，则显然 $m^{'} \bmod 256 = 0$ 。
- 若 $k \neq 0$ ，则 $m^{'} \equiv kN (\bmod 256)$ 。又因为 $N$ 必为奇数， $gcd(N,256) = 1$ ，因而 $Z_{256}$ 下 $N^{-1}$ 存在，即可以计算 $k \equiv m^{'}N^{-1} (\bmod 256)$ 。
又 $m^{'} \in (0,N)$ ，推定 $256m = m^{'} + kN \in (kN,(k+1)N)$ ，即 $m \in (\frac{k}{256}N,\frac{k+1}{256}N)$ 。

重复上述步骤（每次将上一次得到的 $m$ 在 $Z_{N}$ 下乘以 $256$ ），每次可以将原明文 $m$ 的取值范围缩小至原来的 $\frac{1}{256}$ ，近似于获得了高8位的信息。

同时，题目中原明文是 $p \in (0,2^{1024})$ ，在交互次数有限的情况下，应选择跳过前127次交互（因为已知这127次交互必定会得到 $k = 0$ ；注意明文仍需直接乘以 $2^{1016e} \bmod N$ ）。最终我们近似可以得到 r1.p 的高600位信息。

LCG

LCG部分是非常经典的PRNG逆向。
本题中LCG没有给出任何参数~~而且还被玩坏了~~，但难度依然不大。唯一稍微有些迷惑性的点就是不会告诉你随机数的分隔点在哪里，但通过简单分析~~乱糊+瞎猜~~和获得随机数后的存在性校验也不难从一堆unsigned long long里得到五个LCG的连续输出随机数。

得到随机数后，由于LCG的参数 $(p,a,b)$ 均未知，因此需要通过这些随机数来从前向后逐个恢复，这里只讲恢复 $p$ 。
记恢复的随机数序列为 $\{x_i\} (i \in [0,5))$ ，
$x_{i+1} \equiv ax_i + b \bmod p, x_{i+2} \equiv ax_{i+1} + b \bmod p \rightarrow x_{i+2}-x_{i+1} \equiv a(x_{i+1}-x_i) \bmod p$ 。
再记 $x_{i+1}-x_{i} = D_{i} (i \in [0,4))$ ，既有 $D_{i+2} \equiv aD_{i+1} \bmod p, D_{i+1} \equiv aD_i \bmod p \rightarrow D^{2}_{i+1} \equiv D_{i+2}D_{i} \bmod p$ ，即 $D^{2}_{i+1} - D_{i+2}D_{i} \equiv 0 \bmod p$ 。
对上式取 $i = 0,1$ ，得到的二式取最大公约数（即 $gcd(D^{2}_{2} - D_{3}D_{1}, D^{2}_{1} - D_{2}D_{0})$ ），即有很大概率得到 $p$ 。

可以发现5个连续随机数是LCG参数完全未知时下还原 $p$ 所需的最小数目，因此构造的最大公约数经常会掺杂一些其它的小因子，简单factor一下的成功率还是不低的。

得到 $p$ 后依述推导过程中的部分式即可得到 $a,b$ ，过程不再赘述。
至于被“玩坏”的LCG，注意到作为种子的AES密钥key只有128位长，而LCG的 $p$ 为1024位，因此只需一直向前逆向，即可认为第一个遇到的不大于128位的数就是key。

相当于整道 Arcahv 两次应用到了“小明文攻击”的思想，即已知明文的部分信息的前提下攻击可以另辟蹊径，~~同时也强调了密码学应用中pad的重要性~~

Coppersmith

RSA LSB Orcale中并没有获得 $p$ 的全部信息，但已知其高位的情况下即可通过 Coppersmith 对 $N$ 进行分解，具体构造方法也非常简单~~而且没有技巧~~，同样不再赘述。

完整exp

#sage
__import__('os').environ['TERM'] = 'xterm'

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

def hexify_send(num:int) -> bytes:
    return long_to_bytes(num).hex().encode()

io = remote('39.106.16.204',28575)
# io = process(['python3','arcahv.py'])

io.sendlineafter(b'>',b'1')

io.recvuntil(b':')
enc_flag = int(io.recvline().strip().decode(),16)
io.recvuntil(b':')
enc_hint = int.from_bytes(bytes.fromhex(io.recvline().strip().decode()),'little')
io.recvuntil(b':')
enc_hint2 = bytes.fromhex(io.recvline().strip().decode())

# RSA LSB Orcale

m = enc_hint
omit_count = 127
io.sendlineafter(b'>',b'2')
io.recvuntil(b'(')
rn = int(io.recvuntil(b',',drop=True).strip().decode(),16)
re = int(io.recvuntil(b')',drop=True).strip().decode(),16)

upper_bound = reduce(lambda x,y:floor(x/256),range(omit_count),rn)

lower_bound = 0
single_mul = pow(256,re,rn)
inv = pow(rn,-1,256)

m = m * pow(single_mul,omit_count,rn) % rn

for i in range(75):
    m = int(m * single_mul % rn)
    
    io.sendlineafter(b'?',b'y')
    io.sendlineafter(b':',hexify_send(m))
    io.recvuntil(b':')
    this = int(io.recvline().strip().decode()[:2],16)

    k = int(-this * inv % 256)
    ttl = (upper_bound - lower_bound) / 256

    lower_bound += ceil(k * ttl)
    upper_bound = lower_bound + floor(ttl)

res_pp = lower_bound

# LCG

io.sendlineafter(b'>',b'3')
ls = []
for _ in range(80):
    io.sendlineafter(b'?',b'y')
    ls.append(int(io.recvline().strip().decode()))


hexstr = ''.join(hex(i)[2:].zfill(16) for i in ls)
lcgnums = [int(hexstr[i:i+256],16) for i in range(0,len(hexstr),256)]


A = [lcgnums[i+1]-lcgnums[i] for i in range(4)]
p = gcd(A[1]^2 - A[2]*A[0],A[2]^2 - A[3]*A[1])

if not isPrime(p):
    p = factor(p)[-1][0]

assert isPrime(p)

a = int(A[1] * int(pow(A[0],-1,p)) % p)
b = int((lcgnums[1] - a * lcgnums[0]) % p)

cur = Zmod(p)(lcgnums[0])
count = 0
while int(cur).bit_length() > 128:
    cur = (cur - b) * pow(a,-1,p)
    count += 1

key = int(cur).to_bytes(16,'big')
res_n = int.from_bytes(AES.new(key,AES.MODE_ECB).decrypt(enc_hint2),'big')

# Coppersmith
P.<x> = Zmod(res_n)[]
rt = (res_pp + x).small_roots(X=2^453,beta=0.4)[0]

p0 = int(res_pp + rt)

assert res_n % p0 == 0
q0 = res_n // p0

d0 = int(pow(65537,-1,(p0-1)*(q0-1)))
print(long_to_bytes(int(pow(enc_flag,d0,res_n))))

绮云

花灯百盏遥遥一线牵

解析

某种意义上的水题，RSA双Orcale(N-Orcale + fault injection orcale) 和简单的ECDSA守个门。

笔者设想过此类Encryption Orcale有一些偏现实的应用场景，比如存在一个小型的加密器，其提供由一个既定私钥 $d$ 生成大量公钥对 $(N,e)$ 对输入的任意消息进行加密的功能，同时其并不会主动暴露自身公钥对（相当于攻击者/加密者只能得到密文，~~唯密文攻击Plus~~）。攻击者可以对其进行 Fault injection，而现实中对于小型加密设备，通过侧信道攻击等方式同样也可以获取 $e$ 。

RSA N-Orcale

首先我们希望在没有公钥的情况下获得 $N$ 。
传递 $m \in \{2,2^2,2^3,2^4,\cdots\}$ ，收集加密的密文。
设 $m_i = 2^{i} (i \in Z_+)$ ，显然 $m_i = m_1^{i}$ 。
又， $c_i \equiv m_i^e (\bmod N)$ ，推定 $c_1 \equiv m_1^e (\bmod N)$ ，结合上式可得 $c_1^i - c_i \equiv 0 (\bmod N)$ ，即 $c_1^i - c_i = kN (k \in Z)$ 。
在加密了足够多的 $m_i$ 后，对 ${c_1^i - c_i}$ 求其最大公约数，即可有很大把握得到 $N$ 。

RSA N-Orcale步中，由于 $e < 2^{2048}$ ，所以建议选择传输interfere位为2048。尽管单从 N-Orcale 这一步来看没有区别，但如此可以在解出 $N$ 后立即获得 $m^{e} \bmod N$ 的确值~~进而避开了一些奇奇怪怪的if-elif的纠缠~~

RSA Fault injection

单个RSA Encryption Orcale的剩下部分就是比较经典的RSA Fault injection攻击，虽然攻击目标不一样（从传统fault的针对私钥 $d$ 变为现在针对公钥 $e$ ），但数学逻辑完全相同。具体原理不再赘述（~~既有wp太多了~~）。

格攻击

但至此我们得到的依然只是大量的公钥对 $(N,e)$ ，题目中的 $d$ 并不能通过 Wiener's Attack获得（应用的私钥 $d = x^{4}$ 仍有928位）。
注意到每次RSA生成公钥对对应的私钥是相同的，由RSA的基本关系式可以列出： $e_{i}d \equiv 1 \bmod \varphi(N_{i})$
进而， $e_{i}d + k_{i}\varphi(N_{i}) - 1 = 0$ ，得到 $e_{i}d + k_{i}N_{i} - C_{i} = 0$ ，其中 $C_{i}$ 的数量级与 $k_{i}p_{i}$ 相当。

又，RSA中存在 $e_{i}d \approx |k_i|(N_{i})$ （Wiener's attack 连分数逼近的基础），因此 $k_{i} \approx \frac{e_{i}d}{N_{i}}$ ，结合 $e_{i}d \equiv 1 \bmod \varphi(N)$ ，可以认为 $k_{i}$ 数量级与 $d$ 相当。

结合本题的实例， $p_{i}$ 约为1024位， $d_{i}$ 为928位，因而 $C_{i}$ 应在1950位左右，满足明显小于 $e_{i}$ 、 $N_{i}$ 的条件。考虑下述行向量的线性组合：

$\begin{bmatrix} k_{1} & k_{2} & \cdots & k_{n} & d\end{bmatrix} \cdot \begin{bmatrix} N_{1} \\&N_{2} \\ && \ddots \\ &&& N_{n} \\ e_{1} & e_{2} & \cdots & e_{n} & K \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} & \cdots & C_{n} & Kd \end{bmatrix}$

可以认为，等号右侧的向量是该矩阵构成的格中的短向量。因此由该矩阵构造格 $L$ ，对之进行规约即可从中提取出私钥 $d$ 。

关于配平和格维度的选择，笔者建议 $K = 2^{1024}$ ， $n \geq 10$ 。同时本题也因为格维度的问题非常耗时，众所周知Fault injection交互的时间开销非常大，而本题中需要将这个步骤重复数遍，因而出现了大半个小时出flag的奇观，笔者最后懒得改题了，在这给各位师傅磕一个

ECDSA

这部分就没什么了~~为了让各位拿flag更舒服点，ECDSA类的sign方法都留给各位了，不是坑~~。唯一的小插曲是需要进行非常轻度的爆破，不过每次交互 $\frac{1}{256}$ 的概率出flag也不算太低（？）

完整exp

远程交互时本exp耗时预计为45-90分钟。时间开销主要在每次 fault injection 获取 $e$ 时都需要进行2048次交互才能得到结果，本应微不足道的ping、计算耗时等累加数万次后耗时依然极为可观~~在这里给因为交互压力没做出来的师傅磕一个~~

#sage
__import__('os').environ['TERM'] = 'xterm'

from pwn import *
from sage.all import *
from time import time
from hashlib import sha256

io = remote('39.106.16.204',10645)
# io = process(['python3','task.py'])

nls = []
els = []

recv_hexint = lambda: int(io.recvline().strip().decode(),16)

t0 = time()

for _ in range(10):
    io.sendlineafter(b'option:',b'1')
    #decipher N via GCD

    numls = []
    for i in range(9):
        msg = int(1 << (i + 1)).to_bytes(2,'big')
        io.sendlineafter(b'exit:',b'e')
        io.sendlineafter(b'message:',msg.hex().encode())
        io.sendlineafter(b'interfere?',b'0')
        io.recvuntil(b'Result:')
        numls.append(int(io.recvline().strip().decode(),16))

    gcdls = []
    for i in range(1,9):
        gcdls.append(numls[0] ^ (i+1) - numls[i])

    n = gcd(gcdls)
    nls.append(n)
    print(f'n #{_} = {n}')

    #decipher e via fault injection of e

    orcale_msg = 3

    io.sendlineafter(b'exit:',b'e')
    io.sendlineafter(b'message:',int(orcale_msg).to_bytes(1,'big').hex().encode())
    io.sendlineafter(b'interfere?',b'2048')
    io.recvuntil(b'Result:')
    basis = recv_hexint() * pow(orcale_msg, -2^2048, n) % n #basis, = pow(m,e,n)    

    e_rng = [0] * 2048

    for i in range(2048):
        io.sendlineafter(b'exit:',b'e')
        io.sendlineafter(b'message:',int(orcale_msg).to_bytes(1,'big').hex().encode())
        io.sendlineafter(b'interfere?',str(i).encode())
        io.recvuntil(b'Result:')
        
        temp = recv_hexint()
        multiplier = pow(orcale_msg,2^i,n)

        if temp == basis * multiplier % n: #0 -> 1, original = 0
            e_rng[i] = 0
        else: #1 -> 0, original = 1
            assert temp == basis * pow(multiplier,-1,n) % n #ensure
            e_rng[i] = 1

    e_res = int(''.join(str(i) for i in e_rng)[::-1],2)
    assert pow(orcale_msg,e_res,n) == basis
    els.append(e_res)

    print(f'e #{_} = {e_res}')
    print(f'Time elasped: {time()-t0:.2f}s')
    io.sendlineafter(b'exit:',b'')


const = 2^1024
mt = matrix.diagonal(ZZ,nls + [0]).dense_matrix()
mt[-1] = els + [const]
mt = mt.LLL()

temp = abs(mt[0,-1])
assert temp % const == 0
d = ZZ(temp / const)

x = d.nth_root(4)
E = EllipticCurve(Zmod(0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF),[0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC,0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93])
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
assert E.order() == n

G = E((0x32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7,0xBC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0))
m0 = int.from_bytes(sha256('nctf2024-00'.encode()).digest(),'big')

while True:
    k = int(time() * 1000) #should be smaller than n
    P = k * G
    r = int(P.xy()[0]) % n
    s = (pow(k,-1,n) * (m0 + x*r)) % n
    if r != 0 and s != 0:
        break

send = f'{r} {s}'.encode()
while True:
    io.sendlineafter(b'option:',b'2')
    io.sendlineafter(b':',send)
    msg = io.recvline()
    if b'flag' in msg:
        print(msg.decode())
        break

io.close()