DASCTF NOVX联合出题人2022

2023-02-05

刷刷之前没打的小比赛，持续学习。

easy_hash

根据encode，在已知$a_1$的情况下直接两次hash可求$a_2,a_3$，那么$a_0$也可以联立secret求出，由于题目的$a_0$正好小于500比特(如果不满足则无法恢复flag)，直接转为字节去掉crc校验部分即可。

from Crypto.Util.number import bytes_to_long, long_to_bytes
from zlib import crc32

P = 93327214260434303138080906179883696131283277062733597039773430143631378719403851851296505697016458801222349445773245718371527858795457860775687842513513120173676986599209741174960099561600915819416543039173509037555167973076303047419790245327596338909743308199889740594091849756693219926218111062780849456373
print(P.bit_length())
def myhash(x):
    res = []
    end = b""
    bytescipher = long_to_bytes(x)
    a = bytescipher[:len(bytescipher) % 8]
    res.append(a)
    res.append(long_to_bytes(crc32(a)))
    t = (len(bytescipher) // 8)
    bytescipher = bytescipher[len(bytescipher) % 8:]
    for i in range(t):
        a = bytescipher[i*8:i*8+8]
        res.append(a)
        res.append(long_to_bytes(crc32(a)))
    for i in res:
        end += i
    res = bytes_to_long(end)
    res = (res + (res >> 500)) & 2**(500)-1
    return res

a1, secret = (1768672211043417187765307394749760760531160781992300779145800061219666992833602547480090118225665457075744297987672863699370162614965380859290914620736, 89139545215288033432210221492974990584987914397112840989583439688211128705545477536596587262069032020212762581490561288493533363888589066045095054475929099275247145877699370608950340925139625068446642116123285918461312297390611577025368805438078034230342490499137494400676347225155752865648820807846513044723)
a2 = myhash(a1)
a3 = myhash(a2)
a0 = secret - (a1 ** 2 + a2 * a1 ** 2 + a3 * a1 ** 3) % P
print(long_to_bytes(a0))

LLLCCCGGG

output为连续输出的序列，可构造两组kn求公因子恢复n，进一步求出$a_1,a_2,seed$，下一步就是利用背包格求key，背包格普通对角矩阵类型不能成功(系数很难调)：

n = len(m)
d = n / (max(m).log(2))
N = ceil(1 / 2 * sqrt(n))
print(N)
assert d < 0.9408, f"Density should be less than 0.9408 but was {d}."
L=Matrix(n+1,n+1)
for i in range(n):
    L[i,-1]=m[i] * N
    L[i,i]=1 

L[-1,-1]=-s * N
L=L.LLL()
print(L)

利用提高密度的格来处理会更容易做出来，得到序列为 [1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1]，拿到初始的state，构造矩阵快速幂来求最终的state。最后求哈希并异或。

from gmpy2 import *
from Crypto.Util.number import *
import hashlib

output= []
a= 102146678855348749881681741830301892566150942749854546938156269348575567682569
b= 57926598868103510549704115342815226386495366694945712679089221082045615713293
c= 79112540456632613121737537841885533313599936328220061653608162113976717833173
xorflag= 0x2079677330734e7d07116d73543d03316c6501555c02403b7201080612101049

t0 = output[1] - output[0]
t1 = output[2] - output[1]
t2 = output[3] - output[2]
t3 = output[4] - output[3]
n = gcd(t2*t0 - t1**2,t3*t1 - t2**2)
a1 = (output[2] - output[1]) * invert(output[1] - output[0],n) % n
b1 = (output[1] - a1 * output[0]) % n

seed = (output[0] - b1)*invert(a1,n) % n
print(seed)

key = [1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1,
       1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,
       1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1,
       1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1]
state = int(''.join([str(i) for i in key]), 2)
A = matrix(Zmod(c), [[a, 1], [0, 1]])
B = vector(Zmod(c), [state, b])
state = int((A ^ (10 ** 10000) * B)[0])
state_md5 = hashlib.md5(str(state).encode()).hexdigest()
state_md5 = bytes_to_long(state_md5.encode())
print(long_to_bytes(state_md5 ^^ xorflag))
# DASCTF{D0u_Ge_1S_R4al1y_G00d!!!}'

easyrsa

分解n用two_squares(n)，然后再构造整环多项式，以q为基底分解n2，由于flag未pad，而n3的phi是e的倍数，所以应该在模p1的域下解方程。

from sage.all import *
from Crypto.Util.number import long_to_bytes

c= 260434870216758498838321584935711394249835963213639852217120194663627852693180232036075839403208332707552953757185774603238436545434522971149891312380970896040823539050341723863717581297624370198483155582245220695123793458717418658539983101802256991837534210806768587736557644192367876024337837658337683388449336720569707094997412847022794461117019613124291022681935875774139147643806772608929174881451749463825639214096129554621195116737322890163556732291246108250543079041977037626755130422879778449546701988814607595746282148723362288451970833214072743929855505520539885650891349827459470540263153862109871050950881032032388185414677989393461533362690744724752363346530211163516319373099647590952338730
n2= 77582485123791158683121280616703899430016469065264033598472741751344256774648355531493586310864150337351815051848231793841751148287075688226384710343269278032576253497728407800522536152937473072438970839941923618053297480433385258911357458745700958378269978384670108026994918504237309072908971746160378531040480539649223970964653553804442759847964633088481940435582792404175653758785321463055628690804551479982557193366035172983893595403859872458966844805671311011033726279121149599533093604586152158331657286488305064843651636225644328162652701896037366058322959361248649656784810609391313
p1, q1 = (200170033707580057053975766783012322797, 214489650309129059054871357172058931331)
q1=q1+63066105847160076051036559850646146794

poly = sum(e * x^i for i,e in enumerate(Integer(n2).digits(q1)))
(p, _), (q, _), (r, _) = poly.factor_list()
p, q, r = p(x=q1), q(x=q1), r(x=q1)
assert p*q*r == n2

# while True:
#     p1=next_prime(p1)
#     p=next_prime(p)
#     q=next_prime(q)
#     r=next_prime(r)
#     if (p-1)%7==0 and (q-1)%7 ==0 and (r-1)%7==0 and (p1-1)%7==0:
#         break

p1 = 65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570389431
p = 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406292679
q = 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326229291
r = 200170033707580057053975766783012328327
print(int(p1).bit_length())
# flag未padding，所以可以在p的域下解方程

P.<x> = Zmod(p1)[]
f = x^7 - c
res = f.roots()
for i in res:
    if b'DASCTF' in long_to_bytes(int(i[0])):
        print(long_to_bytes(int(i[0])))

Matrix

把A和enc都化为 Jordan 标准型，打印可以发现直接就是对角矩阵了，那么由于$a=p^{-1}AP$，有$a^e=p^{-1}A^ep$，所以求矩阵的dlp转化为求logA(A^e)，进一步可以转化为求对角线对应位置的元素的dlp。

A=
B=
p=12143520799543738643
orders = []
for i in factor(p-1):
    print(i)
    orders.append(i[0])
    
n = 12
G = matrix(GF(p), n, n, A)
H = matrix(GF(p), n, n, B)
G_Jor, P = G.jordan_form(transformation=True)
H_Jor = ~P * H * P

for i in G_Jor:
    print(i)
for j in H_Jor:
    print(j)

print(GF(p)(3789608816284836580).log(GF(p)(37)))