2023N1CTF

周末和吉大东大的好哥哥们打了 n1，最后拿了 rank7，被 web👴 和 pwn👴 带飞

DJB 战队 wp:https://mp.weixin.qq.com/s/N03QtNsMvpux42xIAXxvrA

e2W@rmup

ECDSA 椭圆曲线签名，之前没用过ecdsa库，结果发现 d 就是私钥，拆分一下高低位，二元 coppersmith 梭一下，中间可能要补一位，补了 0 之后就可以了。

后面看师傅们博客还可以用格做，学到了。

from Crypto.Util.number import *
import itertools
import hashlib
from Crypto.Cipher import AES

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

msg = b'welcome to n1ctf2023!'
msg_hash = bytes_to_long(hashlib.sha256(msg).digest())

s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340

p = 115792089210356248762697446949407573529996955224135760342422259061068512044369
leak = int("10000111001100100010110100100000000100101000111011000001001011010100001010010000101001100011011010100000010010011011100010111001", 2)
P.<low,small> = PolynomialRing(Zmod(p))

f = r*((small*(2^128))+low)+msg_hash-(leak<<128)*s-small*s
roots = small_roots(f, [2^129, 2^130], m=3, d=4)
print(roots)

low = 109657576978117277727118025094273115603
high = 222660286808164019769040839717358598716

d = bin(high)[2:]+'0'+bin(low)[2:]
d = int(d, 2)
print(d.bit_length())
aes = AES.new(long_to_bytes(d), mode=AES.MODE_ECB)
cipher = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'
flag = aes.decrypt(cipher)
print(flag)
# b'n1ctf{Wow!__You_bre4k_my_s1gn_chal1enge!!___}\x03\x03\x03'

e2d1p[赛后复现]

参考文章：

https://tl2cents.github.io/2023/10/23/2023-N1CTF-Crypto-Writeups/

https://github.com/Nu1LCTF/n1ctf-2023/tree/main/crypto/e2D1p

题目

Based on N1CTF 2022 “ezdlp”. Easy dlp too, try again : ).

from Crypto.Util.number import *
import os
FLAG = os.environ.get('FLAG', b'n1ctf{XXXXFAKE_FLAGXXXX}')
assert FLAG[:6] == b'n1ctf{' and FLAG[-1:] == b'}'
FLAG = FLAG[6:-1]


def keygen(nbits):
    while True:
        q = getPrime(nbits)
        if isPrime(2*q+1):
            if pow(0x10001, q, 2*q+1) == 1:
                return 2*q+1

def encrypt(key, message, mask):
    return pow(0x10001, message^mask, key)


p = keygen(512)
flag = bytes_to_long(FLAG)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

print(f'message = {messages}')
print(f'enc = {enc}')

0x01 恢复模数 p

给了 200 组 m、c 满足等式\(65537^{m_i⊕mask}=c_i (mod p)\)

异或运算在指数上，没有什么运算性质。但异或的本质还是按位异或，以下用 m[i]表示 m 的第 i 位，对于一组 m 和 c 而言

\[m\oplus mask = mask+ \sum\limits_{j=0}\limits^{158}(m[j]\cdot2^i\cdot(-1)^{s[i]})\]

这样转换后即可把底数看作\(c_i=65537^{mask}\)，下一步的目的就是找到某个向量\(e_i\)使得\(c_i^{e_i}≡0\;mod\;p\)，这样即可恢复出模数\(gcd(e_i,e_j)=p\)

找到满足条件的\(e_i\)需要\(m_i\)，构造如下格：

\(m_{i,j}=m_{i,j}*2^{256}\)

\[ \begin{bmatrix} m_{0,0} & m_{0,1} & \ldots & m_{0,158} & 1 & 0 & \ldots &0\\ m_{1,0} & m_{1,1} & \ldots & m_{1,158} & 0 & 1& \ldots &0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots\\ m_{199,0} & m_{199,1} & \ldots & m_{199,158} & 0 &0& \ldots &1\\ \end{bmatrix} \]

利用LLL算法得到的\(e_i\)满足\(\sum\limits_{i=1}\limits^{200}e_i=0\)，那么也就满足\(\sum\limits_{i=1}\limits^{200}e_i\cdot m_i=\vec{0}\)

0x02 求解 mask

x=mask

\[65537^{\sum2^i\cdot(x_i\oplus m_i)}=c (mod \;p)\]

变换成如下形式

\[(65537)^{\sum\limits_{\{i|m_i=0\}}2^i\cdot x_i+\sum\limits_{\{j|m_j=1\}}2^j\cdot(1-x_j)}=c\;(mod \;p)\]

\[(65537)^{\sum\limits_{\{i|m_i=0\}}2^i\cdot x_i+\sum\limits_{\{j|m_j=1\}}2^j\cdot(-x_j)}=c\cdot 65537^{-\sum\limits_{\{j|m_j=1\}}2^j} (mod \;p)\]

根据上式中\(m_i\)为 0 或 1 的情况构造对应\(x_i\)的系数矩阵\(A\)，系数只为 1 或-1

计算向量\(u\cdot A=(1,0,\cdots,0)\;(mod \;q)\)（模 q 是保证阶为素数，使得向量有解）

当\(mask_i=0\)时，便可按下式逐位恢复 mask

\[\prod\limits_{i=1}\limits^{200}c_i^{u_i}=65537^0=1(mod\;p)\] \[c_i=c_i\cdot 65537^{-\sum\limits_{\{j|m_j=1\}}2^j}(mod\;p)\]

exp

from tqdm import tqdm
from Crypto.Util.number import *
from ast import literal_eval
from Crypto.Util.number import *

lines = open("./output.txt", "r").readlines()
message = literal_eval(lines[0].strip())
enc = literal_eval(lines[1].strip())


m_l = 159
dim = 200
L = matrix(ZZ, dim, dim+m_l+1)
g = 2 ^ 512
for i in range(dim):
    L[i, i] = 1
    L[i, dim+m_l] = g

for i in range(dim):
    line = bin(message[i])[2:].rjust(m_l, '0')
    for j in range(len(line)):
        if int(line[j]):
            L[i, dim+j] = g
        else:
            L[i, dim+j] = 0


basis = L.LLL()[:40]
p = []
for item in basis:
    g1 = 1
    g2 = 1
    vec = item[:dim]
    for i in range(len(vec)):
        if vec[i] >= 0:
            g1 *= pow(enc[i], vec[i])
        else:
            g2 *= pow(enc[i], -vec[i])
    p.append(g1-g2)

p = list(factor(reduce(GCD, p)))[-1][0]
q = (p-1)//2
A = matrix(Zmod(q), dim, m_l)
for i in range(dim):
    line = bin(message[i])[2:].rjust(m_l, '0')
    for j in range(len(line)):
        if int(line[j]):
            A[i, j] = -1
            enc[i] = enc[i]*inverse_mod(pow(0x10001, 2 ^ (m_l-1-j), p), p) % p
        else:
            A[i, j] = 1

m = ''

for _ in tqdm(range(m_l)):
    v = vector(Zmod(q), [0]*_+[1]+[0]*(m_l-1-_))
    u = A.solve_left(v)
    sign = 1
    for i in range(len(u)):
        if u[i] >= 0:
            sign = sign*pow(enc[i], int(u[i]), p) % p
        else:
            sign = sign*inverse_mod(pow(enc[i], -int(u[i]), p), p) % p
    if sign != 1:
        m += '1'
    else:
        m += '0'

print(bytes.fromhex(hex(int(m, 2))[2:]))