第五空间复现writeup

ecc

Ecc套娃，第一部分直接ECDLP，第二部分Pohlig-Hellman算法，题目直接给了不是很懂，第三部分Smart’s Attack。

from Crypto.Util.number import long_to_bytes
p1 = 146808027458411567
A1 = 46056180
B1 = 2316783294673
E1 = EllipticCurve(GF(p1),[A1,B1])
P1 = E1(119851377153561800 , 50725039619018388)
Q1 = E1(22306318711744209 , 111808951703508717)
n1=discrete_log(Q1,P1,operation='+')
print(long_to_bytes(n1))

p2 = 1256438680873352167711863680253958927079458741172412327087203
A2 = 377999945830334462584412960368612
B2 = 604811648267717218711247799143415167229480
E2 = EllipticCurve(GF(p2),[A2,B2])
P2=E2(550637390822762334900354060650869238926454800955557622817950 , 700751312208881169841494663466728684704743091638451132521079)
Q2=E2(1152079922659509908913443110457333432642379532625238229329830 , 819973744403969324837069647827669815566569448190043645544592)
factors, exponents = zip(*factor(E2.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
print (primes)
dlogs = []
for fac in primes:
    t = int(int(P2.order()) // int(fac))
    dlog = discrete_log(t*Q2,t*P2,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
n2=crt(dlogs,primes)
print (long_to_bytes(n2))

p3 = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A3 = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B3 = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E3 = EllipticCurve(GF(p3),[A3,B3])
P3=E3(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 ,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q3=E3(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 ,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)
factor(E3.order())
def SmartsAttack(P, Q, p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p) * p for t in E.a_invariants()])
    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break
    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break
    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp
    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()
    phi_P = -(x_P // y_P)
    phi_Q = -(x_Q // y_Q)
    k = phi_Q // phi_P
    return ZZ(k)
n3=SmartsAttack(P3,Q3,p3)
print(long_to_bytes(n3))
#https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp

print(b'flag{'+long_to_bytes(n1)+long_to_bytes(n2)+long_to_bytes(n3)+b'}')
#b'flag{025ab3d9-2521-4a81-9957-8c3381622434}'

doublesage

看着是个LWE问题，当时比赛的时候直接摆烂随便传，每次都传[1-23]和[1-143]，然后试了十几次就过了哈哈。赛后学习一下别的师傅的做法。

方法一：

模$p$​意义下，求$x$​使得$|xA-b|$​尽可能小，很容易想到的是让这个式子等于0，于是就只需要解方程$Ax=b$​，但是我们知道矩阵A不一定存在逆矩阵，所以需要引入概念伪逆矩阵（pseudo-inverse），或者称其为摩尔彭若斯广义逆（Moore–Penrosepseudoinverse）。

• m*n 矩阵 A 的 Moore–Penrose 伪逆 $A^+$ 是满足以下条件的唯一确定的 n*m矩阵：

  $AA^+A=A,\ \ A^+AA^+=A^+,\ \ (AA^+)^T=AA^+,\ \ (A^+A)^T=A^+A.$​​​​​

  如果 A 是列满秩，则 $A^+=(A^T\ A)^{-1}A^T$

  如果 A 是行满秩，则 $A^+=A\ T（A\ A^T)^{-1}$

• 如果没有特别指明，矩阵的伪逆就是指摩尔－彭若斯广义逆。广义逆有时也被当作摩尔－彭若斯广义逆的同义词用。摩尔－彭若斯广义逆常应用于求非一致线性方程组的最小范数最小二乘解（最小二乘法），并使得解的形式变得简单。矩阵的摩尔－彭若斯广义逆在实数域和复数域上都是唯一的，并且可以通过奇异值分解求得。

可以看到矩阵伪逆正是解决最小范数问题的一种方法。所以我们只需要求出矩阵A的伪逆，然后和b相乘后得到x。

from pwn import *
def solve(p, rows):
    r.recvuntil(b'Matrix A')
    r.recvline()

    def get_vector():
        r.recvuntil(b'[')
        s = r.recvuntil(b']')[:-1]    
        return [int(x) for x in s.split()]

    A = []

    for i in range(rows):
        s = get_vector(p)
        A.append(s)

    r.recvline()
    b = r.recvline()
    b = get_vector()

    Zp = Zmod(p)

    A = Matrix(Zp, A)
    b = vector(Zp, b)

    x = A.transpose().pseudoinverse() * b

    x = str(x).replace('(', '[').replace(')', ']')
    r.sendline(x.encode())
    r.recvuntil(b'The norm of vector x*A-C is')
    res = r.recvline()
    if (b'True' in res):
        print('Pass chall {}'.format(p))
        return True
    else:
        print('Fail chall {}'.format(p))
        return False

while True:
    r = remote('122.112.210.186',51436)
    if solve(23, 5) and solve(143, 15):
        r.interactive()
    else:
        r.close()
#https://wp.n03tack.top/posts/56002/#doublesage

这波学到了，还有矩阵伪逆这玩意

方法二：

LWE问题，找LWE的脚本直接梭，脚本来自NaN。（LWE脚本先存了）

from pwn import *
from sage.modules.free_module_integer import IntegerLattice
def Babai_closest_vector(L, w):
    '''
    Yet another method to solve apprCVP, using a given good basis.
    INPUT:
    * "L" -- a matrix representing the LLL-reduced basis (v1, ..., vn) of a
    lattice.
    * "w" -- a target vector to approach to.
    OUTPUT:
    * "v" -- a approximate closest vector.
    Quoted from "An Introduction to Mathematical Cryptography":
    In both theory and practice, Babai's closest plane algorithm
    seems to yield better results than Babai's closest vertex algorithm.
    '''
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()^2 ) * L[i]
        i -= 1
    return t - w
r = remote('122.112.210.186', 51436)
context(log_level='debug')
r.recvuntil('modulus')
r.recvline()
r.recvline()
data = r.recvline().decode()
M = []
for i in range(5):
    t_vec = []
    vec = r.recvline().decode()[1:-2]
    vec = vec.split(' ')
    for x in vec:
        if x.isdecimal():
            t_vec.append(int(x))
    assert len(t_vec) == 23
    M.append(t_vec)
assert len(M) == 5
M = Matrix(ZZ, M)
m, n = 5, 23
r.recvline()
r.recvline()
vec = r.recvline().decode()[1:-2]
vec = vec.split(' ')
b_vec = []
for x in vec:
    if x.isdecimal():
        b_vec.append(int(x))
assert len(b_vec) == 23
A_value = M # exactly 'A' in General situation
A_value = A_value.transpose()
b_value = b_vec # exactly 'a' in General situation
m = 23
n = 5
p = 29
# construct the lattice L after applying LLL
Lattice = Matrix(ZZ, m + n, m)
for x in range(m):
    for y in range(n):
        Lattice[m + y, x] = A_value[x, y]
    Lattice[x, x] = p
lattice = IntegerLattice(Lattice, lll_reduce=True)
print('LLL done')
# prepare for Babai's algorithm
target = vector(ZZ, b_value)
closest_v = Babai_closest_vector(lattice.reduced_basis, target)
print('Find closest vector:{} '.format(closest_v))
# solve the equation: A*s = b
A_LWE = matrix(Zmod(p), A_value)
s = A_LWE.solve_right(closest_v)
s = list(s)
r.sendlineafter('modulus 29 :', str(s))
r.recvuntil('modulus')
r.recvline()
r.recvline()
data = r.recvline().decode()
M = []
for i in range(15):
    t_vec = []
    vec = r.recvline().decode()[1:-2]
    vec = vec.split(' ')
    for x in vec:
        if x.isdecimal():
            t_vec.append(int(x))
    assert len(t_vec) == 143
    M.append(t_vec)
    assert len(M) == 15
    M = Matrix(ZZ, M)
r.recvline()
r.recvline()
b_vec = []
for i in range(7):
    if i != 6:
        vec = r.recvline().decode()[1:-1]
    else:
        vec = r.recvline().decode()[1:-2]
    vec = vec.split(' ')
    for x in vec:
        if x.isdecimal():
            b_vec.append(int(x))
assert len(b_vec) == 143
print(b_value)

A_value = M # exactly 'A' in General situation
A_value = A_value.transpose()
b_value = b_vec # exactly 'a' in General situation
m = 143
n = 15
p = 227
# construct the lattice L after applying LLL
Lattice = Matrix(ZZ, m + n, m)
for x in range(m):
    for y in range(n):
        Lattice[m + y, x] = A_value[x, y]
    Lattice[x, x] = p
lattice = IntegerLattice(Lattice, lll_reduce=True)
print('LLL done')
# prepare for Babai's algorithm
target = vector(ZZ, b_value)
closest_v = Babai_closest_vector(lattice.reduced_basis, target)
print('Find closest vector:{} '.format(closest_v))
# solve the equation: A*s = b
A_LWE = matrix(Zmod(p), A_value)
s = A_LWE.solve_right(closest_v)
s = list(s)
print(s)
r.sendlineafter('modulus 227 :', str(s))
r.interactive()

signin

这题已知p^q的低400位，和p*q，实际上还是一种解方程，只不过需要一位一位枚举p和q，然后在已知p的低位的情况，使用coppersmith。（最近这种异或爆破好像挺多的，学一手）

from Crypto.Util.number import *
c = 20447834080716676861260898086596427975708825833039405478043730491684492090126834957765281802337614379260353025780350269473938100277831839834052494528642858771208829522444199753332668288237520529204598641192166056115125100497251758639697188043033677583625259284290926751392026007345743270672794001549260660437
e = 65537
n = 51829690315852722180065756920738886752496164137616266689326816383511598394192418757462476837101165832835728876608898794315487561791469438010457161419486159257838354726118084197036612143071280955688965597991177195321580364900266798655104065461134993248598785717447158334659990278280156559953140328939918569751
x = 1458992978872343557099505109358348200022788430032606776639391204880828365157718281673562914452477666861716725617956844822
x = bin(x)[2:]
P = []

def find(guessp, i):
    p = int(guessp, 2)
    q = int(x[-i:], 2) ^^ p

    if (q * p) % 2 ** i == n % 2 ** i:
        if i == 399:
            P.append(p)
        else:
            find('1'+guessp, i+1)
            find('0'+guessp, i+1)
find('1',1)
for i in range(len(P)):
    pb=len(bin(_p)[2:])
    _p = P[i]
    kbits = 512 - pb
    R.<x> = Zmod(n)[]
    f = P[i] + x * 2^pb
    f = f.monic()
    roots = f.small_roots(X=2^kbits,beta=0.4)
    if roots:
        p = int(_p + roots[0]* 2^pb)
        print(p)
        break
q = n // p
assert p * q == n
phi = (q - 1) * (p - 1)
d = inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,n)))

secrets

哭了，格子构造出来不能出，用了NaN的svp方法也没用，求一个密码爷爷教教怎么做。

当时写出了这个式子

然后就可以构造一个格子

这里R用来调格子的det，让它满足LLL规约的不等式要求。下面的脚本是NaN的脚本，但是并不能出。

from Crypto.Util.number import *
import itertools
from sage.modules.free_module_integer import IntegerLattice
p =9990023055834814541617846807430043006619434399269736419836238596241876512761228099716117843097392140738452382394167885743945642291607707968961478893802663
a =[5966930779052686477031701769573660079506373243735898860732951813437052962193127602437592171689011479433096174113531891952361650308071688129029761338139979, 5970641925133316779789534939731049546081094069820251739654111253332315359322044145559737555982279747038885936478125413531493247569529490923909073652886513, 5647457807686675609383359511965317690655998242830631042112382847759941921904234938861931780977072229311090688925189099391590810644016635012424277294034433]
e = [[0, 1, 2], [2, 2, 2], [0, 2, 0]]
c =5011570647869537688965619278497453589689533788035020706968424121134157038323546474418039082230117040297759615283099576609259094217120003896586061782747210
cc =bytes.fromhex('4f79c22cea53737e05f284dd1ff6b3eba6d8aa9d1bb31cc47835d1057052bab5')
M = Matrix(ZZ, [
[1, 0, 0, 0, a[0]],
[0, 1, 0, 0, a[1]],
[0, 0, 1, 0, a[2]],
[0, 0, 0, 1, p],
[0, 0, 0, 0, c]
])
# print(M.LLL())
from sage.modules.free_module_integer import IntegerLattice
#https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
def solve(mat, lb, ub, weight = None):
    num_var = mat.nrows()
    num_ineq = mat.ncols()
    max_element = 0
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
            
    if weight == None:
        weight = num_ineq * max_element
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
    # heuristic for number of solutions
    DET = 0
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
        # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
    applied_weights.append(ineq_weight)
    for j in range(num_var):
        mat[j, i] *= ineq_weight
    lb[i] *= ineq_weight
    ub[i] *= ineq_weight
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
    
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    # recover x
    fin = None
    
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
        
    ## recover your result
    return result, applied_weights, fin
lb = [2^93, 2^190, 2^60, 2^185, 0]
ub = [2^97, 2^195, 2^70, 2^195, 1]
print(solve(M, lb, ub))

个人信息保护

五层套娃密码，有点搞其实。

第一层的n可以直接查库分解

from Crypto.Util.number import *

with open('out') as f:
    s = f.read().splitlines()

c = eval(s[0])
n = eval(s[1])
p = 22186905890293167337018474103
q = 64390888389278700958517837593
e = 65537
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))
#XIAOming

第二层可以把n除p，然后查库分解q，q的因数很多算phi要注意一下。当然注意到m是小于p的，也可以直接模p。

c = eval(s[2])
n = eval(s[3])
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
e = 65537
q = n // p
dp = inverse(e, (p-1))
m = pow(c, dp, p)
print(long_to_bytes(m))
#17810111101

第三层是矩阵乘法，直接sage解方程就可以了

with open('out') as f:
    s = f.read()
s = s.splitlines()

q = eval(s[4])
A = eval(s[5])
b = eval(s[6])

A = Matrix(Zmod(q), A)
b = vector(Zmod(q), b)

x = A.solve_right(b)
x = ''.join([chr(i) for i in x])
print(x)
#XIAOming@cmail.com

第四层就很搞了，乍一看是一个没有任何问题的AES，但是细想，前面用了这么多random，怕不是MT19937。数一下：第一层的a、b是两个96bits数，就是6个state；第二层q用了randrange，取的两个数的范围相差$2^{31}$​​​​​，需要爆破最后一位，得到一个state；第三层的key每个都是32bits，一共有34*18=612个state。这时一共有619个state，还差5个state。注意到在第二层里的message，结尾填充了160bits随机数，正好5个state。

这样就凑齐了624位数，不过需要合理爆破一下第一层的a、b。

from sympy import prevprime
from Crypto.Util.number import *
from randcrack import RandCrack
from Crypto.Cipher import AES
from string import printable


def sendstate(x, tmp):
    for i in range(tmp):
        rc.submit(x % (1 << 32))
        x >>= 32


p1 = 22186905890293167337018474103
q1 = 64390888389278700958517837593
prep1 = prevprime(p1)
preq1 = prevprime(q1)
with open('out') as f:
    s = f.read().splitlines()
n = eval(s[3])
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
e = 65537
q = n // p
key = eval(s[5])
key = [x for y in key for x in y]
pads = b'\xf1\x0f\xb5\xb5\xae\xf0\x05\x92BWR\xd0>\x91\x0cv\xbc ]\x81'
pads = bytes_to_long(pads)

c4 = eval(s[7])
c4 = long_to_bytes(c4)
for a in range(prep1, p1):
    for b in range(preq1, q1):
        for c in range(2):
            rc = RandCrack()
            fq = (q << 1) + c
            sendstate(a, 3)
            sendstate(b, 3)
            sendstate(pads, 5)
            sendstate(fq, 1)
            for i in key:
                rc.submit(i)
            aeskey = long_to_bytes(rc.predict_getrandbits(128))
            cipher = AES.new(aeskey, AES.MODE_ECB)
            try:
                m = cipher.decrypt(c4).decode()
                if all(char in printable for char in m):
                    print(m, a, b)
            except:
                continue
#No.555_hack_road 22186905890293167337018474052 64390888389278700958517837515

然后就可以用第四层求出来的随机数的state，预测第五层的ElGamal中的所有参数，然后直接梭就完事了。

from Crypto.Util.number import *
from randcrack import RandCrack


def sendstate(x, tmp):
    for i in range(tmp):
        rc.submit(x % (1 << 32))
        x >>= 32


with open('out') as f:
    s = f.read().splitlines()
n = eval(s[3])
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
e = 65537
q = n // p
key = eval(s[5])
key = [x for y in key for x in y]
pads = b'\xf1\x0f\xb5\xb5\xae\xf0\x05\x92BWR\xd0>\x91\x0cv\xbc ]\x81'
pads = bytes_to_long(pads)
a=22186905890293167337018474052
b=64390888389278700958517837515
rc=RandCrack()
sendstate(a, 3)
sendstate(b, 3)
sendstate(pads, 5)
sendstate(q << 1, 1)
for i in key:
    rc.submit(i)
aeskey = long_to_bytes(rc.predict_getrandbits(128))
q, g, h = [eval(x) for x in s[8].split()]
c1, c2 = [eval(x) for x in s[9].split()]
gg = rc.predict_randrange(q-1)
x = rc.predict_randrange(q-1)
y = rc.predict_randrange(q-1)
s = pow(g, x*y, q)
m5 = c2 * inverse(s, q) % q
print(long_to_bytes(m5))
#MakeDSAGreatAgain_University

from hashlib import *

name = b'XIAOming'
phone = b'17810111101'
mail = b'XIAOming@cmail.com'
address = b'No.555_hack_road'
school = b'MakeDSAGreatAgain_University'
flag = 'flag{' + sha256(name).hexdigest()[:8] + '-' + sha256(phone).hexdigest()[:4] + '-' + sha256(mail).hexdigest()[:4] + '-' + sha256(address).hexdigest()[:4] + '-' + sha256(school).hexdigest()[:12] + '}'
print(flag)
#flag{9cb2979a-d651-b79e-a86b-ee01181ded94}