<h1 style="text-align:center; color:#3832a8">HolaCTF 2025</h1>

<p>
Cuộc thi CTF này nhìn chung khá nhẹ nhàng với những người chơi cryptography. Dưới đây sẽ là lời giải của một số bài <s>không phải đoán mò</s> liên quan đến việc lập trình trong cuộc thi CTF này.
</p>

<h2>Cs2RTrash</h2>

:::spoiler <b>chall.py</b>

from Crypto.Util.number import bytes_to_long, long_to_bytes
import random

e = 65537
n1 = 106274132069853085771962684070654057294853035674691451636354054913790308627721
n2 = 73202720518342632558813895439681594395095017145510800999002057461861058762579
n3 = 58129476807669651703262865829974447479957080526429581698674448004236654958847
message = b'HOLACTF{...}'
m = bytes_to_long(message)


c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)


print(f"c1: {c1}")
print(f"c2: {c2}")
print(f"c3: {c3}")

:::

:::spoiler <b>output.txt</b>

c1: 40409669713698525444927116587938485167766997176959778633087672968720888190012
c2: 50418608792183022472533104230595523000246213655735834753443442906871618770832
c3: 7151799367443802424297049002310776844321501905398348074481144597918413565153

:::

Ta có thể thấy $n1, n2, n3$ là các số khá nhỏ nên bạn có thể dùng **Sagemath** để phân tích thừa số nguyên tố cũng được. Tuy nhiên hãy để ý rằng cả 3 số này đều là số nguyên tố nên ta có thể thực hiện lời giải ngay luôn mà không cần phải phân tích thừa số nguyên tố.

:bulb: Script lời giải:
:::spoiler <b style="color:tomato">solution.py</b>

from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime

e = 65537
n1 = 106274132069853085771962684070654057294853035674691451636354054913790308627721
n2 = 73202720518342632558813895439681594395095017145510800999002057461861058762579
n3 = 58129476807669651703262865829974447479957080526429581698674448004236654958847

assert isPrime(n1) == isPrime(n2) == isPrime(n3), "something's gone wrong!"

c1 = 40409669713698525444927116587938485167766997176959778633087672968720888190012
c2 = 50418608792183022472533104230595523000246213655735834753443442906871618770832
c3 = 7151799367443802424297049002310776844321501905398348074481144597918413565153

d = pow(e, -1, n1 - 1)

m1 = pow(c1, d, n1)
print("[!] Got flag:", long_to_bytes(m1).decode())
# [!] Got flag: HOLACTF{ju5t_a_b4s1c_CRT}

:::

:::success
**Flag:** <b style="color:#d4195e">HOLACTF{ju5t_a_b4s1c_CRT}</b>
:::

<h2>ImLosingYou</h2>

:::spoiler <b>encrypt.py</b>

from random import getrandbits, FLAG
from Crypto.Util.number import *

e = 2
n = getPrime(256) * getPrime(256)

m = bytes_to_long(FLAG)
mod_m = m - getrandbits(80)
c = pow(m, 2, n)
print(f"n = {n}")
print(f"c = {c}")
print(f"mod_m = {mod_m}")

:::

:::spoiler <b>out.txt</b>

n = 5655306554322573090396099186606396534230961323765470852969315242956396512318053585607579359989407371627321079880719083136343885009234351073645372666488587
c = 249064480176144876250402041707185886135379496538171928784862949393878232927200977890895568473400681389529997203697206006850790029940405682934025
mod_m = 499063603337435213780295973826237775412685978121823376141602090122856806

:::

Nhìn vào đề bài, ta được cho giá trị của $n, c, e = 2$ và quan trọng nhất là $mod\_m = m - x$ với $x$ = getrandbits(80).
<br>
Như vậy, ta có thể nghĩ ngay đến <a href="https://en.wikipedia.org/wiki/Coppersmith%27s_attack" target = "_blank"><b>Coppersmith's attack</b></a> để có thể tìm được $x$, từ đó tìm được $c$. May mắn thay **Sagemath** đã có phương thức để làm điều đó và ta không cần phải viết lại chương trình từ đầu.

:bulb: Script bài giải:

:::spoiler <b style="color:tomato">solution.py</b>

from sage.all import PolynomialRing, Zmod
from Crypto.Util.number import long_to_bytes

e = 2
n = 5655306554322573090396099186606396534230961323765470852969315242956396512318053585607579359989407371627321079880719083136343885009234351073645372666488587
c = 249064480176144876250402041707185886135379496538171928784862949393878232927200977890895568473400681389529997203697206006850790029940405682934025
mod_m = 499063603337435213780295973826237775412685978121823376141602090122856806

P = PolynomialRing(Zmod(n), name="x")
x = P.gen()

f = (x + mod_m)**e - c
f = f.monic()

x = int(f.small_roots()[0])
m = mod_m + x

flag = long_to_bytes(m).decode()

print("[!] Got flag:", flag)
# [!] Got flag: HOLACTF{f33ls_l1k3_l0s1ng_h3r}

:::

:::success
**Flag:** <b style="color:#d4195e">HOLACTF{f33ls_l1k3_l0s1ng_h3r}</b>
:::

<h2>High School Smurf</h2>

:::spoiler <b>chall.py</b>

import secrets
from sympy import Float, Point, Triangle, simplify
import signal
import sys
import time

FLAG = "HOLACTF{REDACTED}"
P = 2025

class Line:
    def __init__(self):
        self.x = self._r()
        self.y = self._r()
        self.dx = self._r()
        self.dy = self._r()

    def at(self, t):
        return Point(self.x + self.dx * t, self.y + self.dy * t, evaluate=False)

    def _r(self):
        return -1 + 2 * Float(secrets.randbits(P), P) / (1 << P)
    
def timeout_handler(signum, frame):
    print("Timeout")
    sys.exit(1)

def run():
    try:
        signal.signal(signal.SIGALRM, timeout_handler)
        signal.alarm(25)
        
        start_time = time.time()
        
        lines = [Line() for _ in range(3)]
        for L in lines:
            print(f'{L.x}, {L.y}, {L.dx}, {L.dy}')
        i, j, k = [secrets.randbits(32) for _ in range(3)]
        tri = Triangle(*[L.at(n) for L, n in zip(lines, [i, j, k])])
        s, v = tri.sides, tri.vertices
        a, b, c = s[1].length, s[2].length, s[0].length
        x, y = [v[i].x for i in range(3)], [v[i].y for i in range(3)]
        exc = {
            s[0]: Point(simplify((-a*x[0]+b*x[1]+c*x[2])/(-a+b+c)), simplify((-a*y[0]+b*y[1]+c*y[2])/(-a+b+c))),
            s[1]: Point(simplify((a*x[0]-b*x[1]+c*x[2])/(a-b+c)), simplify((a*y[0]-b*y[1]+c*y[2])/(a-b+c))),
            s[2]: Point(simplify((a*x[0]+b*x[1]-c*x[2])/(a+b-c)), simplify((a*y[0]+b*y[1]-c*y[2])/(a+b-c)))
        }
        pt = exc[secrets.choice(s)]
        print(f'{Float(pt.x, P)}, {Float(pt.y, P)}')
        print("Can you guess the indices of the lines? (i j k)")

        if time.time() - start_time <= 25.0:
            if [int(n) for n in input().split()] == [i, j, k]:
                print(f"Congratulations! Here is your flag: {FLAG}")
            else:
                print("Wrong, try harder next time!")
        else:
            print("Timeout")
            
        signal.alarm(0)
        
    except Exception as e:
        print("Wrong, try harder next time!")
        sys.exit(1)

if __name__ == "__main__":
    run()

:::

Diễn giải theo ngôn ngữ hình học phẳng thì bài này sẽ cho trước 3 phương trình tham số của đường thẳng mà chúng ta được biết, trên mỗi đường thẳng server sẽ chọn ra một điểm bí mật mà chúng ta không được biết. Server sau đó sẽ tính tọa độ của các tâm đường bàng tiếp của tam giác được tạo thành từ 3 điểm đó, cuối cùng sẽ trả về ngẫu nhiên tọa độ của 1 trong 3 điểm này cho chúng ta.
<br>
Nhiệm vụ của chúng ta là sẽ tìm ra vị trị của 3 điểm bí mật này (theo đề bài sẽ là tìm ra các tham số t được chọn cho mỗi đường thẳng).

Ban đầu mình đã nghĩ rằng đây có thể là một thử thách liên quan đến tấn công giảm cơ sở mạng, nhưng mình không biết bắt đầu từ đâu. May mắn thay, có một <a href="https://connor-mccartney.github.io/cryptography/other/Geometry-Hash-Balsn-CTF-2023"><b>bài viết</b></a> liên quan đến một thử thách tương tự do **ConnorM** trình bày đã giúp mình giải quyết những phần khó nhất.

Thử thách này liên quan đến **Part 3 - Incenter** trong bài viết của ConnorM.


Thử thách của chúng ta cho một tọa độ tâm đường tròn bàng tiếp bất kỳ, còn thử thách trong bài viết của ConnorM sẽ cho tọa độ tâm đường tròn nội tiếp. Tuy nhiên, vì chúng đều là điểm đồng quy của các đường phân giác trong (hoặc phân giác ngoài) nên về cơ bản lời giải sẽ giống nhau.

:bulb: Script bài giải:

:::spoiler <b style="color:tomato">solution.py</b>

from pwn import *
from tqdm import trange
from sage.all import matrix, identity_matrix, QQ, RealField, var


def solve(equation, P = 23120404):
    coeffs = equation.polynomial(QQ).coefficients()
    M = matrix(coeffs).transpose()
    n = M.nrows()
    M = M.augment(identity_matrix(n))
    M[-1, -1] = 0

    # resize
    for i in range(n):
        M[i, 0] = M[i, 0] * 10**P

    M = M.LLL()

    return " ".join([str(i) for i in M[0][-4:-1]])


R = RealField(8888); P = 2025
HOST = "0.0.0.0"; PORT = 35645

connection = remote(HOST, PORT)

output_1_list = []
for i in trange(3):
    output_1_list.append(connection.recvline().strip().decode().split(','))

Ax, Ay, Adx, Ady = tuple(map(R, output_1_list[0]))
Bx, By, Bdx, Bdy = tuple(map(R, output_1_list[1]))
Cx, Cy, Cdx, Cdy = tuple(map(R, output_1_list[2]))

Ix, Iy = tuple(map(R, connection.recvline().strip().decode().split(',')))
connection.recvuntil(b"Can you guess the indices of the lines? (i j k)\n")

i, j, k = var('i'), var('j'), var('k')
x1, y1 = Ax + Adx*i, Ay + Ady*i
x2, y2 = Bx + Bdx*j, By + Bdy*j
x3, y3 = Cx + Cdx*k, Cy + Cdy*k

lhs = ((x3-x2)*(Iy-y2)-(y3-y2)*(Ix-x2)) * ((x1-x2)*(Ix-x2)+(y1-y2)*(Iy-y2))
rhs = ((y1-y2)*(Ix-x2)-(x1-x2)*(Iy-y2)) * ((x3-x2)*(Ix-x2)+(y3-y2)*(Iy-y2))

equation = lhs - rhs

answer = solve(equation, P)

connection.sendline(answer.encode())

connection.recvuntil(b"Congratulations! Here is your flag: ")
flag = connection.recvline().strip().decode()

connection.success(f"Got flag: {flag}")
# [+] Got flag: HOLACTF{l_wI5h_1_h4D_ILl_1n_My_hIgHSchO01_GE0meTRY_cLAs5_1e9a67a695ee}

connection.close()




# https://connor-mccartney.github.io/cryptography/other/Geometry-Hash-Balsn-CTF-2023

:::

:::success
**Flag:** <b style="color:#d4195e">HOLACTF{l_wI5h_1_h4D_ILl_1n_My_hIgHSchO01_GE0meTRY_cLAs5_1e9a67a695ee}</b>
:::

>[!Important] Chú ý
>Nên đặt độ chính xác càng cao càng tốt nhé, vì nếu bạn để độ chính xác quá thấp thì lời giải sẽ thất bại!

## Tổng kết
Bài viết này đã trình bài lời giải cho các bài cryptography liên quan đến việc viết script của cuộc thi. Mong rằng bài viết này sẽ giúp ích cho các bạn. Hẹn gặp lại các bạn ở những bài tiếp theo (<s>nếu mình rảnh</s> :penguin:).