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.

 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 = (1, 0)     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 & 1) and kronecker(d, p) == 1:             y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p             return (x, y)   D = 13337 p = 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 M = [int.from_bytes(FLAG[i:i+8], 'big') for i in range(0, len(FLAG), 8)]   G = [rand_element() for _ in M] c = (1, 0) 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 = }')   Colored by Color Scripter 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()     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   D = 13337 p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583 G = [(8249149405495350491346934933585109414510787432598250096114687570379053133508711862485128035174547571919256235441699899388417666835599315963507480727674285, 10151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (10148658254415475588279956574772196898575718154643967163626694400363009168529645860280959810873028393970853643723425023678857408220330929116526467295542507, 3332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (1839326681086939925214853980855626023120414606039474419455499625885357274275815189399880356995376514021329118829062071144818562457268892324773839713533977, 17502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (3165955958968203879237344349962533642598441044481692770147807839372942715856047580766073222297692574025922260374409920417665600069665162502514403188432579, 9382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (8500294063291124527108623281980255870507549734362604259645984044370658620385351338711051998886026260657132944353675335178871934798200163035190278483491633, 7641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (12352685673550986453697035560006632628194788902921398545668828437339873544223895997440585227838919968929669738393535610103382084842900404005432007637193943, 2453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)] c = (5388567167658786935158413401674168420144429277172064721472662913563775670320298461949979362402157764272762755236320989018989446360740720072488623102776015, 7420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)   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. = 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]   M = Matrix(ZZ, 7, 7) lb =  * 7 ub =  * 7 for i in range(6):     M[i, 0] = logs[i] M[6, 0] = p + 1 lb = 1 ub = 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) Colored by Color Scripter 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. = 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()     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)   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 = 1024, 15, 3     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()   Colored by Color Scripter 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()     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)   conn = remote('pwn-2021.duc.tf', 31912) conn.recvline()   N = int(conn.recvline().split())   r = next_prime(N) F = PolynomialRing(GF(r), 'x') K = 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:].decode(), 16)   val_1 = H(params, target, 0) val_2 = H(params, 0, 1)   u = ((1 + r - val_1) * inverse(val_2, r)) % r   conn.sendline(str(1).encode()) conn.sendline(str(u).encode())   print(conn.recvline()) Colored by Color Scripter 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) n = p*q   K. = NumberField((x-p)^2 + q^2) hint1 = p^2 + q^2 hint2 = []   l = 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. = (ZZ.quo(n*ZZ))[] ZnI. = Zn.quo(I^2 + 1)   m = randrange(1, n) + bytes_to_long(flag) * I c = pow(m, 0x1337)   print(f'hint1 = {hint1}', f'hint2 = {hint2}', f'c = {c}', sep='\n')   Colored by Color Scripter 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)   # 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()     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 None, None, None             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)] c = 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*I + 4029058763453606238903897463441562834907249422434463474076515876575829847522130192389016587404930865750330557087612323698180248796377295462524538856886086398759909290696184205993616487194215215220788562122976961077906744617472657126002125275580071372330371116294688544107523683271239033324714979085342248973341926663953843846046960739886947485863993625451601367382937578510847100654709310703410238862000749364014455073705910890023184023421059288913438268024784676942709153616462894290327611033397199003399769315399282676125251796552761022560343255167268538619398474794249565056809687349530329863724341722260050648912909130315084736439621962322946883555665867960336853966064629555225967168666632969614488585135849531033105444785970372310095381763641123031809302021416125564151419362313796375570121725315170 l = 338   offset = 3   M = Matrix(ZZ, 3, 4) lb =  * 4 ub =  * 4   y1, a1, b1 = hint2 y2, a2, b2 = hint2   target1 = (y1 // hint1 - b1 * b1) * (1 << (l-1)) * hint1 fx = hint1 * (1 << (l-1))   M[0, 0] = a1 * b1 * (1 << l) M[1, 0] = hint1 * b1  lb = target1 - offset * fx  ub = target1    target2 = (y2 // hint1 - b2 * b2) * (1 << (l-1)) * hint1    M[0, 1] = a2 * b2 * (1 << l) M[2, 1] = hint1 * b2 lb = target2 - offset * fx ub = target2   M[1, 2] = 1 lb = 0 ub = 1 << l   M[2, 3] = 1 lb = 0 ub = 1 << l   result, applied_weights, fin = solve(M, lb, ub)   p = next_prime(int(fin)) q = 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. = (ZZ.quo(n*ZZ))[] ZnI. = Zn.quo(I^2 + 1) c = 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*I + 4029058763453606238903897463441562834907249422434463474076515876575829847522130192389016587404930865750330557087612323698180248796377295462524538856886086398759909290696184205993616487194215215220788562122976961077906744617472657126002125275580071372330371116294688544107523683271239033324714979085342248973341926663953843846046960739886947485863993625451601367382937578510847100654709310703410238862000749364014455073705910890023184023421059288913438268024784676942709153616462894290327611033397199003399769315399282676125251796552761022560343255167268538619398474794249565056809687349530329863724341722260050648912909130315084736439621962322946883555665867960336853966064629555225967168666632969614488585135849531033105444785970372310095381763641123031809302021416125564151419362313796375570121725315170 print(pow(c, d)) ''' Colored by Color Scripter cs

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 PBCTF 2021 Writeups  (0) 2021.10.13 2021.10.03 2021.09.26 2021.09.26 2021.08.05 2021.07.22