I briefly participated in DUCTF 2021, solving three crypto challenges and two simple rev challenges.

The reversing challenges were fun and hard enough for me, but they are labeled easy/medium so I will not explain them here.

Also, joseph (one of the problemsetters) has a very good writeup on https://jsur.in/posts/2021-09-26-ductf-2021-writeups, so check it out. 

 

yadlp

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
def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)
 
def G_mul(A, k):
    out = (10)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out
 
def rand_element():
    while True:
        x = randint(1, p-1)
        d = x^2 * (D + 1- D
        if (x & 1 == d & 1and kronecker(d, p) == 1:
            y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
            return (x, y)
 
= 13337
= 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime
 
FLAG = open('flag.txt''rb').read().strip()
assert len(FLAG) % 8 == 0
= [int.from_bytes(FLAG[i:i+8], 'big'for i in range(0len(FLAG), 8)]
 
= [rand_element() for _ in M]
= (10)
for m, gi in zip(M, G):
    c = G_add(c, G_mul(gi, m))
 
print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')
 
cs

 

Step 1 

In challenges like these, figuring out the curve we are on is usually the first step. To do this, we let $$y = \frac{x +\sqrt{(D+1)x^2 - D}}{D}$$ and work out some algebra to end up with $$(x+y)^2 - (D+1)y^2 = 1$$ which is a Pell's equation. Now we change $(x, y)$ to $(x+y, y)$ and change $D$ to $D+1$ and consider $x^2 - Dy^2 = 1$. 

 

The solutions of Pell's equation satisfy some good properties, which come from the identity $$(a^2-Db^2)(c^2-Dd^2) = (ac+Dbd)^2 - D(ad+bc)^2$$ which shows that if $(a, b), (c, d)$ are solutions of $x^2-Dy^2=1$, then $(ac+Dbd, ad+bc)$ is also such a solution. This turns out to be the group addition as well. The homomorphism to a multiplicative group of $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ written as $$ (a, b) \rightarrow a + bx$$ is also notable. The results here so far can be studied from Pell's equation theory, so the point up to here were straightforward for me.

 

Step 2 

Now we have to look at the group structure. There are various methods to end up with the correct conclusion - that the group is a cyclic group of order $p+1$. You could just guess the group order, or give a solid mathematical proof. joseph gives a proof by using that the multiplicative group of $\mathbb{F}_{p^2}$ is cyclic and $\alpha^{p+1}=1$ for each $\alpha = a + bx$ for $(a, b)$ satisfying $a^2 - Db^2 = 1$. I think technically this proves that the group order is a divisor of $p+1$, but this is quite good as well. Here's another method that I used during my solve.

 

It suffices to show that there are exactly $p+1$ solutions for $a^2 - Db^2 \equiv 1 \pmod{p}$. This is equivalent to computing $$\sum_{b=0}^{p-1} 1 + \left( \frac{Db^2 + 1}{p} \right) = 2 + \sum_{b=1}^{p-1} 1 + \left( \frac{Db^2+1}{p} \right) $$ $$ = 2 + \sum_{b=1}^{p-1} 1+ \left( \frac{D + b^2}{p} \right)$$ which means the value is the number of solutions for $$a^2 - b^2 \equiv D \pmod{p}, \quad b \not\equiv 0 \pmod{p} $$ plus $2$. Of course, the given equation is equivalent to $$(a-b)(a+b) \equiv D \pmod{p}$$ and there are $p-1$ solutions of the form $$a-b \equiv i \pmod{p}, \quad a+b \equiv Di^{-1} \pmod{p}$$ for each $i \in \{1, \cdots , p-1\}$. The key is that none of the solutions have $b \equiv 0 \pmod{p}$ because $D$ is, in this problem, not a quadratic residue. Therefore, the number of solutions is $2 + (p-1) = p+1$, as desired. This concludes the proof.

 

Note that if $D$ was a quadratic residue, there would be $p-1$ solutions.

 

This is really the turning point of the challenge - if $D$ was a quadratic residue, the group order would be $p-1$ and the fact that $p$ is a safe prime will help greatly to make the cipher safe. However, $D$ is not a quadratic residue, which makes the fact that $p$ is "safe" mean absolutely nothing. In fact, $p+1$ is very smooth. I thought that the whole $p$ is "safe" thing in the given script was a very funny joke :)

 

Step 3

Now we compute the actual discrete logarithm. There are many ways to compute this - you could write a custom Pohlig-Hellman algorithm to account for different addition and multiplication formula, which is possible but a hassle. An easier way is to define $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ and work discrete logarithm over this field. Of course, to find a discrete logarithm, we need a generator $g$ for the field. Theoretically, we can just find random points until we find a generator. In my solution, I just tried the given points.

 

Step 4

Now that we know all the discrete logarithms, all we need to do is compute the flag. We see that $$ \sum m_i \log_g(g_i) = \log_g(res) \pmod{p+1}$$ along with $0 \le m_i < 2^{64}$. This condition can be straightforwardly feeded into my CVP repository https://github.com/rkm0959/Inequality_Solving_with_CVP and we have the flag. This was a nice challenge combining a lot of fun math ideas :)

 

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
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
 
= 13337
= 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
= [(824914940549535049134693493358510941451078743259825009611468757037905313350871186248512803517454757191925623544169989938841766683559931596350748072767428510151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (101486582544154755882799565747721968985757181546439671636266944003630091685296458602809598108730283939708536437234250236788574082203309291165264672955425073332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (183932668108693992521485398085562602312041460603947441945549962588535727427581518939988035699537651402132911882906207114481856245726889232477383971353397717502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (31659559589682038792373443499625336425984410444816927701478078393729427158560475807660732222976925740259222603744099204176656000696651625025144031884325799382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (85002940632911245271086232819802558705075497343626042596459840443706586203853513387110519988860262606571329443536753351788719347982001630351902784834916337641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (123526856735509864536970355600066326281947889029213985456688284373398735442238959974405852278389199689296697383935356101033820848429004040054320076371939432453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
= (53885671676587869351584134016741684201444292771720647214726629135637756703202984619499793624021577642727627552363209890189894463607407200724886231027760157420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
 
print(len(G))
 
'''
D = 13338
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
G = [(8249149405495350491346934933585109414510787432598250096114687570379053133508711862485128035174547571919256235441699899388417666835599315963507480727674285, 10151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (10148658254415475588279956574772196898575718154643967163626694400363009168529645860280959810873028393970853643723425023678857408220330929116526467295542507, 3332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (1839326681086939925214853980855626023120414606039474419455499625885357274275815189399880356995376514021329118829062071144818562457268892324773839713533977, 17502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (3165955958968203879237344349962533642598441044481692770147807839372942715856047580766073222297692574025922260374409920417665600069665162502514403188432579, 9382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (8500294063291124527108623281980255870507549734362604259645984044370658620385351338711051998886026260657132944353675335178871934798200163035190278483491633, 7641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (12352685673550986453697035560006632628194788902921398545668828437339873544223895997440585227838919968929669738393535610103382084842900404005432007637193943, 2453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
c = (5388567167658786935158413401674168420144429277172064721472662913563775670320298461949979362402157764272762755236320989018989446360740720072488623102776015, 7420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
GG = []
for a, b in G:
    GG.append((a+b, b))
a, b = c
cc = (a+b, b)
K.<z> = GF(p**2, name='z', modulus=x^2 - D)
tt = (p+1) // 432
L = list(factor(tt))
print(L)
base = (a+b) + b * z
for a, b in GG:
    v = a + b * z
    print(v.log(base))
'''
 
logs = [2816026164685113357819599161916784095343437608176866348054691853599389483035986857942301105700772017038015800856893756018342135280046636282509828459475264
,4454166524908585051122091699367767320812675170250549943320148456830102311369800005419960817723812062960747357335951038181643917358801852112440501578475705
,10592989590744873457884645785658581545224173008189907961231282661924610752981017572693574053983522152348945200152352773129758671274319626386160131388585752
,9412387853225306787772668180506806539830098501890523194264793947862715307266992454894401276064400106485711592745559238039738469223857458389407805014776300
,11705006563236210956123096549924041531532105228094197348728492717298448400356434417842060810409623716614227796999859505036258530445896800424164580386003096
,7526156655082313923417616532606029321209669119704767191155046511306556916835849234170663657892790215760669790225464654694145090868608505033102329054110089]
 
= Matrix(ZZ, 77)
lb = [0* 7
ub = [0* 7
for i in range(6):
    M[i, 0= logs[i]
M[60= p + 1
lb[0= 1
ub[0= 1
 
for i in range(6):
    M[i, i+1= 1
    lb[i+1= 0
    ub[i+1= (1 << 64)
 
result, applied_weights, fin = solve(M, lb, ub)
 
flag = b''
for i in range(6):
    flag += long_to_bytes(int(fin[i]))
 
print(flag)
cs

 

power sign

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
72
73
74
75
76
77
78
79
80
81
82
83
84
#!/usr/bin/env sage
 
proof.arithmetic(False# just makes things faster
 
def get_3m4_prime(N):
    while True:
        p = random_prime(2^N - 1, lbound=2^(N-1))
        if p % 4 == 3:
            return p
 
def generate_key(L, n, m):
    p = get_3m4_prime(L//2)
    q = get_3m4_prime(L//2)
    N = p*q
    r = next_prime(N)
    F.<x> = PolynomialRing(GF(r))
    K = F.quo(F.irreducible_element(n))
    return (K, m), N, (p, q)
 
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h ^= r
    assert len(list(h)) != 0
    return int(h[0])
 
def sign(params, privkey, msg):
    p, q = privkey
    u = 1
    while True:
        c = H(params, msg, u) % (p*q)
        if legendre_symbol(c, p) == legendre_symbol(c, q) == 1:
            break
        u += 1
    xp = pow(c, (p+1)//4, p)
    xq = pow(c, (q+1)//4, q)
    x = crt([int(xp), int(xq)], [p, q])
    return x, u
 
def verify(params, pubkey, msg, sig):
    N = pubkey
    x, u = sig
    c = H(params, msg, u)
    return x^2 % N == c % N
 
def main():
    print('Welcome to the game. To get the flag, give me a message to sign, then sign a random message of mine!')
    FLAG = open('./flag.txt''r').read().strip()
 
    L, n, m = 1024153
    params, pubkey, privkey = generate_key(L, n, m)
    print('N:', pubkey)
 
    msg = int(input('message (in hex): '), 16)
    if msg < pubkey^m:
        print('That message is too small!')
        exit()
    if msg > pubkey^n:
        print('That message is too big!')
        exit()
    x, u = sign(params, privkey, msg)
    print('x:', x)
    print('u:', u)
 
    auth_msg = randint(1, pubkey^5)
    print('Now sign', hex(auth_msg))
    x = int(input('x: '))
    u = int(input('u: '))
 
    if verify(params, pubkey, auth_msg, (x, u)):
        print(FLAG)
    else:
        print('Incorrect!')
 
if __name__ == '__main__':
    main()
 
cs

 

There are a lot of approaches possible, and a lot of solutions are on joseph's writeup linked above. Here, I'll just write my solution. 

 

Ultimately, we need $x, u$ such that $$x^2 \equiv H(msg, u) \pmod{N}$$ holds. Obviously there must be some issue with the whole $H$, so let's take a look in that whole thing. 

 

In $H$, we write $msg$ as a polynomial in $GF(r^n)$ and then computes the constant part of $$(msg + zu)^{r^m}$$ My immediate idea was to utilize frobenius endomorphism to simplify $$(msg + zu)^{r^m} \equiv msg^{r^m} + z^{r^m} u^{r^m} \equiv msg^{r^m} + z^{r^m} u \pmod{r}$$ which was linear in $u$. This gave us $$H(msg, u) = H(msg, 0) + u H(0, 1) \pmod{r}$$ and both $H(msg, 0)$ and $H(0, 1)$ can be computed directly from the given data.

 

Therefore, we can just select $u$ appropriately to make $H(msg, u) \equiv 1 \pmod{r}$ and send $x=1$ to get the flag.

 

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
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h = h ** r
    assert len(list(h)) != 0
    return int(h[0])
 
conn = remote('pwn-2021.duc.tf'31912)
conn.recvline()
 
= int(conn.recvline().split()[1])
 
= next_prime(N)
= PolynomialRing(GF(r), 'x')
= F.quo(F.irreducible_element(15))
params = (K, 3)
pubkey = N
 
conn.sendline(hex(pubkey ** 6)[2:].encode())
conn.recvline()
conn.recvline()
 
target = int(conn.recvline().split()[2][2:].decode(), 16)
 
val_1 = H(params, target, 0)
val_2 = H(params, 01)
 
= ((1 + r - val_1) * inverse(val_2, r)) % r
 
conn.sendline(str(1).encode())
conn.sendline(str(u).encode())
 
print(conn.recvline())
cs

 

l33tcrypt v2

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
from Crypto.Util.number import getPrime, bytes_to_long
 
flag = open('flag.txt''rb').read().strip()
 
p, q = getPrime(1337), getPrime(1337)
= p*q
 
K.<z> = NumberField((x-p)^2 + q^2)
hint1 = p^2 + q^2
hint2 = []
 
= 1+337
for _ in range(1*3*3-7):
    a, b = getrandbits(1337), getrandbits(1337)
    x = K(a + getrandbits(l)/2^l) + K(b + getrandbits(l)/2^l)*z
    y = x*x.conjugate()
    hint2.append((int(y), a, b))
 
Zn.<I> = (ZZ.quo(n*ZZ))[]
ZnI.<I> = Zn.quo(I^2 + 1)
 
= randrange(1, n) + bytes_to_long(flag) * I
= pow(m, 0x1337)
 
print(f'hint1 = {hint1}', f'hint2 = {hint2}', f'c = {c}', sep='\n')
 
cs

 

Hour 1-2

CCE, a local CTF, was going on, but I was done with my part and had some time on my hands. 

That whole number field thing looked very scary, but the "error part" getrandbits and the "error part" from rounding $y$ made me believe that this is not really about number fields, but more about "approximate stuff" like lattices.

 

Also, I saw that after we find $p, q$, the remaining part can be copied from TetCTF 2021. (https://rkm0959.tistory.com/192)

 

After looking at basic conjugate things like $\overline{x} = 2p-x$ and $x \overline{x} = p^2 + q^2$ and doing some calculations on paper, I ended up with $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ where $0 \le r_1, r_2, r_3 < 1$. To make everything integer, multiplying $4^l$ gives $$(2^la + r_1)^2 + 2p(2^la+r_1)(2^lb+r_2) + (2^lb+r_2)^2 (p^2+q^2) + 4^ly + r_3$$ where $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$ are integers. We have two equations, so in total, 6 error terms. 

 

We know $p^2+q^2$, so we only want the $p$ part. I wanted to plug in CVP repo, but it's not possible in this form. This is because the equations have parts like $r_1r_2p$, which is a large unknown value. This situation happened to me before - it was in AeroCTF horcrux (https://rkm0959.tistory.com/211) and I had talked about my solution with joseph before on discord. So I thought this might be the way. The idea is to cancel out $p$, making everything about the 6 error terms only. In the end, I would have a 6-variable polynomial to solve for small roots. 

 

In AeroCTF horcrux, the bounds were good enough that I could finish with CVP repo, not using the full power of the polynomials. To be more exact, I wouldn't need to use that $r_1r_2$ is $r_1$ multiplied by $r_2$ - just the fact that $0 \le r_1r_2 < 2^{2l}$. However, that was not true for this problem, as my CVP repo failed to give a correct solution. This meant that I actually needed the full power of 6 variable polynomials. I tried defund's repo, but it killed my computer. Another idea I had in mind was to use bounding to find one of $r_1, r_2$. However, not knowing $p$ precisely made this impossible. Then I went to work on writing up CCE and had dinner. 

 

Hour 3

I started with the bounding idea again - the part that kept bugging me was that $r_1$ really didn't matter. For example, if I had known $p$, I could find $r_2$ without the knowledge of $r_1$ or $r_3$ as the "impact" of $r_2$ is far greater than $r_1$ or $r_3$ in the whole equation.

 

To be more detailed, consider the equation $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ with $0 \le r_1, r_2, r_3 < 1$. When $r_1$ changes from $0$ to $1$, the LHS increases about 1337 * 2 bits. When $r_3$ changes from $0$ to $1$, the RHS increases about 1 bit. When $r_2$ changes from $0$ to $1$, the LHS increases about 1337 * 3 bits. This made me think about ignoring all $r_1, r_3$ parts as "noises", simplifying the equations at the cost of a looser bound and loss of information. 

 

Consider $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$, with $$\left( a+ \frac{r_1}{2^l} \right)^2 + 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2 (p^2+q^2) = y + \frac{r_3}{2^{2l}}$$ we will divide this by $p^2+q^2$, and denote anything that is around 1 or smaller as $O(1)$. This gives $$ \frac{1}{p^2+q^2} \left( a+ \frac{r_1}{2^l} \right)^2 + \frac{1}{p^2+q^2} 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2  = \frac{1}{p^2+q^2} y + \frac{1}{p^2+q^2} \cdot \frac{r_3}{2^{2l}}$$ First, $a^2$ is 1337 * 2 bits and so is $p^2 + q^2$, implying that the first part is $O(1)$. For the second part, if we fully expand the numerator, the part excluding $2pab$ are all around 1337 * 2 bits, implying that it is $O(1)$ after division by $p^2+q^2$.

We can also see that $(r_2/2^l)^2$ is $O(1)$. Finally, clearly $r_3/4^l$ is already $O(1)$. In conclusion, we have the stunning equation $$O(1) + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} =  \frac{y}{p^2+q^2} $$ and in practice, the inequality $$ \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} \le \frac{y}{p^2+q^2} \le 3 + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l}$$ worked well, which was verified with multiple testing with generated data. After clearing denominators, this was the perfect inequality to plug into CVP repo. Everything was known except $p$ and one error term for each equation, and everything was linear in terms of unknown values. I plugged this into the CVP repository, but there were multiple solutions. It took a few minutes to figure out that my candidates for $p$ were all consecutive integers, and I just had to take the next prime number to find the actual $p$, giving the flag.

 

This was a really really good challenge that taught me a lot. It had an interesting tradeoff of complexity and precision.

 

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
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
 
    m = mat * mat.transpose()
    DET = inthroot(Integer(m.det()), 2)
    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)
        # print(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")
            return NoneNoneNone
            break
    
        # recover x
    fin = None
 
    mat = mat.transpose()
    fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
hint1 = 9474114456792673515431877947943819508105969635542281515830563486137327168661333703401850605206493227243522275742966516648683239582868203596838274343178793480973891177607186024817920580636526398124249438530268326706106084200991464054888550590630591134888356623254262308517945404542523082470069480353068223694311508861801523183513245279545596528410382012946385366699431483305340128165852371328697376926968446708099825429442186214124021086080153564030893750081986851543881131351556953787562383902563532279388285764786107301410609469955447888060120474186646198067390958666731078269768973485409216649415321100676385488676994332545669638759522053210552702128133338413305324201806761866164474398103381334477039479224259925086453057512169480806903881772813089475880157326511289464083589335128877565750510634618850
hint2 = [(732546382458694012527789828012658378094702844241795401426843533262220812770028735455197287163119092985574791815396084039371039996745646333674579318749988785972110472195404257454757344814442424493794011566431937242360848878285030166984149693743077380791443878087350475749876855340312637158554338528312647367781264029940556029591883509296327157870585105957528288777977912893801651347425601258985587330670953298765350018187069720989197539655266126608555068568433785671130844623376557756307700624321155540004939237651224429899583558320317618753120682478549822994855115229255313084828494729871333964260804633974731539710591594817406548163223896591957023800247556355776277803866504762994363248426088927388107745396346246364269053285330511504658050763844166012473791572894552857353549047649195624795947489180260979461063462063828112399114859364813704521025921163040319096254633472956309716047137099678802685979113668885601296025318218875502044310139823328365450929054463143898168438742821823709383772324178942782797995009228644990630313338092741812684409459706859981433655900653533420603781201785114071059836464490109704785152549161122683211537057829631974746267465106271003835623120675868336217957493577419646574917016786960763971105924313670864643113152080247596101761667919974877317059734430884155146853783807463171001928603696124835265895296591581488900411484570933812177545618929573489183920330986109459899431831015221573294655414274883012371358092609067769905057144741729285256290725546405447624734438623235233946301969480294721959115680856021696640872884026385162811995627855934793386619910476937700613082779, 1543824598221623810544208805328287421613768036151947874139391287620165680044273642997713684429385602196228549596953402195253771549624806908757244012787647676921740972118119690619160814867773301029620094485726996907379061963500831983371578370700427374066341469843386724329442101058337650126328673673103875588454070821764869582749550357448526278027673495765146251605639297850930361919443005623694632013303, 278066231056905142305104802223227529510107823582373063981133703297010715328189269872672545717708004188569473458656648620603642909190690880317856689557616399347538953740829444695466029704435732263108744727780955070759083273384356847390585190707938226562580173928509689922077486197504519480359398971760153208230160873276281036727480009843280457680277644007154868247812957266590582948212002647347579597965), (2403931462615300014912573083791207269120927941165936946270714147348589275302782927254153349406751900409737005652653965419293500156635383418370534229776798159799544655491444625223239629070116271649566531509751492007287556686610922243146922720689240769956444136141045389983487722510967341333296316124861289680453311483583713394680884118860739515747245777714794715741583447733115461680095467478792575220154609730018111981467052398055564596522296491712770565301016865613056558617018826541540034369006769600336871572325043701351770219492587170369815095344397680717819930616599208355365092147396589419063661351495695927808384696467907751578957796331366383391221037004742878990846671674314297157060496951084267550785175020195260374151822097301166545332365173007130667658669023236685137146454027881996654859397883138679620794416770836903293285267689375186032800923071081877797299448490161970114063577601307797826188431113415671273120884557490666872780316977507218882738147619244927641770516473541881268874031321080906148751514801419469523784406736104695838521768957591700470012632981881278541917424550592192054960270762406248837436552253011562745897713476468254217503340327771690937113342506707740878371307784138197357653258554320947445665637325825934844545591362876466794093523698691499245458580590045390833227060694376995243735824822120025136206595444317852707366827787780703456414342309744435791623414331744392284997640092463157849832124166944965921884701468913065315740226664124591175781629426506057267248659303310396227692666112080517619152746622372541984530565220811971391954114052398015660212010257113648848847, 1095271776133890944180744243712910546278746562392568011876271303881431329832093376635925871119446466987231888845639447279594831752278087660346437418402997861987783151298417098367490883057794520011454228160352569059415183920272078930149476192223454197039306461996527833603604938471295363667754643414137116188016150205603690898270274189826416464265752825558069478170856048769787582750749123139364050774900, 503722937364073120219172142862403799517933100630972300242952550817433776953552478694914014362767990852845981728951892566080540126804572527879551832311854342967959495035585119889481210539549990451963720802920003582648892828543694739151645941765335597098334960962085798952240875279321239403245884262371088975882015803767312665173035156867269826854927631774910426072984288933637519024572470691768302645082)]
= 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*+ 4029058763453606238903897463441562834907249422434463474076515876575829847522130192389016587404930865750330557087612323698180248796377295462524538856886086398759909290696184205993616487194215215220788562122976961077906744617472657126002125275580071372330371116294688544107523683271239033324714979085342248973341926663953843846046960739886947485863993625451601367382937578510847100654709310703410238862000749364014455073705910890023184023421059288913438268024784676942709153616462894290327611033397199003399769315399282676125251796552761022560343255167268538619398474794249565056809687349530329863724341722260050648912909130315084736439621962322946883555665867960336853966064629555225967168666632969614488585135849531033105444785970372310095381763641123031809302021416125564151419362313796375570121725315170
= 338
 
offset = 3
 
= Matrix(ZZ, 34)
lb = [0* 4
ub = [0* 4
 
y1, a1, b1 = hint2[0]
y2, a2, b2 = hint2[1]
 
target1 = (y1 // hint1 - b1 * b1) * (1 << (l-1)) * hint1
fx = hint1 * (1 << (l-1))
 
M[00= a1 * b1 * (1 << l)
M[10= hint1 * b1 
lb[0= target1 - offset * fx 
ub[0= target1 
 
target2 = (y2 // hint1 - b2 * b2) * (1 << (l-1)) * hint1 
 
M[01= a2 * b2 * (1 << l)
M[21= hint1 * b2
lb[1= target2 - offset * fx
ub[1= target2
 
M[12= 1
lb[2= 0
ub[2= 1 << l
 
M[23= 1
lb[3= 0
ub[3= 1 << l
 
result, applied_weights, fin = solve(M, lb, ub)
 
= next_prime(int(fin[0]))
= inthroot(Integer(hint1 - p * p), 2)
 
print(p * p + q * q - hint1)
 
'''
phi = (p * p - 1) * (q * q - 1)
d = int(inverse_mod(0x1337, phi))
n = p * q
Zn.<I> = (ZZ.quo(n*ZZ))[]
ZnI.<I> = Zn.quo(I^2 + 1)
c = 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*I + 4029058763453606238903897463441562834907249422434463474076515876575829847522130192389016587404930865750330557087612323698180248796377295462524538856886086398759909290696184205993616487194215215220788562122976961077906744617472657126002125275580071372330371116294688544107523683271239033324714979085342248973341926663953843846046960739886947485863993625451601367382937578510847100654709310703410238862000749364014455073705910890023184023421059288913438268024784676942709153616462894290327611033397199003399769315399282676125251796552761022560343255167268538619398474794249565056809687349530329863724341722260050648912909130315084736439621962322946883555665867960336853966064629555225967168666632969614488585135849531033105444785970372310095381763641123031809302021416125564151419362313796375570121725315170
print(pow(c, d))
'''
cs

 

'CTF' 카테고리의 다른 글

PBCTF 2021 Writeups  (0) 2021.10.13
TSGCTF 2021 Writeups  (0) 2021.10.03
ACSC Crypto Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
GoogleCTF Quals 2021 Crypto Writeups  (1) 2021.07.19