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(tQ2,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}