2022 D^3ctf密码题赛后复现(ing)

发表于 更新于 分类于

d3factor

方法1

造格子 设\(\epsilon=d_2-d_1\)，有 \(e_1e_2\epsilon +e_2-e_1\equiv0\ mod\ p^6\) 化为\(\epsilon+b=kp^6,\ b\equiv(e_1e_2)^{-1}(e_2-e_1)\ mod\ p^6\) 设\(M=N^{\frac{1}{2}}\)， \(L=\begin{pmatrix}M&b\\\\ 0&N\end{pmatrix}\) \((pq\ -k)L=(pqM\ -pq\epsilon)\) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
b=inverse_mod(e1*e2,N)*(e2-e1)%N
M=floor(N^(1/2))
A=matrix(ZZ,[[M,b],[0,N]])
pq=abs(A.LLL()[0][0])//M
p6=N//pq
p=gmpy2.gcd(p6,pq)
q=pq//p

print(p,q)
解出flag 
1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from hashlib import md5

c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967

p=81911394167511996830305370213894554209992159667974516868378702592733037962549
q=59689394622751323780317475130818337618980301243859922297121750335804594909859
n=p*q
phi=pow(p,6)*(p-1)*(q-1)
d=inverse(0x10001,phi)
msg=long_to_bytes(pow(c,d,n))
flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
print(flag)

方法2

直接上coppersmith梭 \(e_1e_2\epsilon +e_2-e_1\equiv0\ mod\ p^6\) \(b=p^6\ge N^\beta\)得到$=$0.75

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
from hashlib import md5
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
P.<x>=PolynomialRing(Zmod(N))
f=e1*e2*x+e2-e1
f=f.monic()
res=f.small_roots(X=2^1000,beta=0.75)[0]
p6=gmpy2.gcd(int(f(res)),N)
n=N//p6
p=gmpy2.gcd(p6,n)
q=n//p
n=p*q

phi=pow(p,6)*(p-1)*(q-1)
d=inverse_mod(0x10001,phi)
msg=bytes.fromhex(hex(gmpy2.powmod(c,d,n))[2:])
print(msg)
flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
print(flag)

d3qcg

多元coppersmith \(s_1=as^2+c\ mod\ p\ ,\ s_2=as_1^2+c\ mod\ p\) \(s_1,s_2\)高位已知，求出\(s_1,s_2\)，在有限域求根\(s\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import itertools
import hashlib


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 []


d = {'a': 3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101,
     'c': 6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833, 'p': 7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347}
a, c, p = d['a'], d['c'], d['p']
h = [67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833,
     70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422]
enc = 6176615302812247165125832378994890837952704874849571780971393318502417187945089718911116370840334873574762045429920150244413817389304969294624001945527125
P. < x, y > = PolynomialRing(GF(p))
f = a*(2 ^ 146*h[0]+x) ^ 2+c-(2 ^ 146*h[1]+y)
l = small_roots(f, (2 ^ 146, 2 ^ 146), m=4, d=4)
assert len(l) > 0
l1, l2 = l[0]
s1, s2 = 2 ^ 146*h[0]+l1, 2 ^ 146*h[1]+l2
P. < z >= PolynomialRing(GF(p))
f = a*z ^ 2+c-s1
l = [int(i[0]) for i in f.roots()]
for i in l:
    flag = int.from_bytes(hashlib.sha512(b'%d' % (i)).digest(), 'big') ^ ^enc
    flag = bytes.fromhex(hex(flag)[2:])
    if b'd3ctf' in flag:
        print(flag)

核心代码来自https://github.com/defund/coppersmith

d3bug

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
mask = 0b1010010000001000000010001001010010100100000010000000100010010100
A = matrix(GF(2), 70, 64)
T1 = matrix(GF(2), 64, 64)
T2 = matrix(GF(2), 64, 64)
for i in range(63):
    T1[i, i+1] = 1
    T2[i, i+1] = 1
T1[-1] = [int(i) for i in bin(mask)[2:]]
T2[-1] = [1]*64
E1 = T1 ^ 64
E2 = T2 ^ 64
r1 = '01111101111010111000010010111001101'
r2 = '00100110001000110001101010101001001'
for i in range(35):
    A[i] = E1[i]
    A[i+35] = E2[i]
b = [int(i) for i in r1+r2]
ans = A.solve_right(b)
print(ans)
flag = 0
for i in ans:
    flag = (flag << 1)+int(i)
print(bytes.fromhex(hex(flag)[2:]))