Skip to content

Instantly share code, notes, and snippets.

@elliptic-shiho
Created December 27, 2023 04:32
Show Gist options
  • Save elliptic-shiho/1597fbcd0363a4d1b731373545fad2de to your computer and use it in GitHub Desktop.
Save elliptic-shiho/1597fbcd0363a4d1b731373545fad2de to your computer and use it in GitHub Desktop.
SECCON CTF Finals 2023 DLP 4.0
from socket import create_connection
class Tube:
def __init__(s, host, port, debug=False):
s.host = host
s.port = port
s.sock = create_connection((host, port))
s.debug = debug
def recv(s, size=1024) -> bytes:
buf = s.sock.recv(size)
if s.debug:
print(f"[Tube#recv] {buf=}")
return buf
def recv_until(s, expected: bytes) -> bytes:
buf = b""
while True:
buf += s.sock.recv(1)
if expected in buf:
break
if s.debug:
print(f"[Tube#recv_until] {buf=}")
return buf
def send(s, buf: bytes):
if s.debug:
print(f"[Tube#send] {buf=}")
s.sock.send(buf)
def send_line(s, buf: bytes):
s.send(buf + b"\n")
def close(s):
s.sock.close()
if s.debug:
print("[Tube#close] closed")
def read_quarternion(tube) -> (int, int, int, int):
a = int(tube.recv_until(b" ").strip())
tube.recv_until(b"+ ")
b = int(tube.recv_until(b"*i").rstrip(b"*i"))
tube.recv_until(b"+ ")
c = int(tube.recv_until(b"*j").rstrip(b"*j"))
tube.recv_until(b"+ ")
d = int(tube.recv_until(b"*k").rstrip(b"*k"))
return (a, b, c, d)
def get_eigenvalue(F, a, b, c, d):
A = 1
B = -2 * a
C = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2
D = sqrt(F(B ^ 2 - 4 * A * C))
L1 = (-B + D) / (2 * A)
L2 = (-B - D) / (2 * A)
return (L1, L2)
def challenge(tube):
tube.recv_until(b"favorite 333-bit p:")
p = 15614383950057174190349598797195341142783317747682448840361363700794291170123950129507898918000642787
tube.send_line(str(p).encode())
tube.recv_until(b"g = ")
g_raw = read_quarternion(tube)
tube.recv_until(b"h = ")
h_raw = read_quarternion(tube)
x = var("x")
F = GF(p ^ 2, "i", modulus=x ^ 2 + 1)
ii = F.gen()
ga, gb, gc, gd = g_raw
ha, hb, hc, hd = h_raw
G = Matrix(2, 2, [ga + gb * ii, gc + gd * ii, -gc + gd * ii, ga - gb * ii])
H = Matrix(2, 2, [ha + hb * ii, hc + hd * ii, -hc + hd * ii, ha - hb * ii])
E = Matrix(2, 2, [1, 0, 0, 1])
order = p ^ 2 - 1
print(G)
print(H)
assert G ^ order == E
assert H ^ order == E
# print(discrete_log(H, G, order))
# print(factor(order))
L1, L2 = get_eigenvalue(F, ga, gb, gc, gd)
M1, M2 = get_eigenvalue(F, ha, hb, hc, hd)
print(M1, L1)
print(M2, L2)
x = None
y = None
if "i" not in str(M1):
y = M1
elif "i" not in str(M2):
y = M2
else:
return False
if "i" not in str(L1):
x = L1
elif "i" not in str(L2):
x = L2
else:
return False
K = GF(p)
x = K(x)
y = K(y)
exponent = y.log(x)
print(exponent)
tube.send_line(f"{exponent}".encode())
print(tube.recv(1024))
print(tube.recv(1024))
print(tube.recv(1024))
print(tube.recv(1024))
return True
def main():
res = False
while not res:
tube = Tube("dlp-4-0.int.seccon.games", int(8888), False)
res = challenge(tube)
tube.close()
if __name__ == "__main__":
main()
"""
Sat Dec 23 15:15:53 JST 2023 ~/Downloads/seccon/dlp40
> sage solve.sage
[ 6631464687709964401638593584282317698086002418701370403451375298554143352342218518442929071743687214*i + 3765457014279809956954260428460280043908869382556850885683433873161873968349753755711085812309759210 1756077780020567359443754915888514185407371957577724923461216434521905705877637149988978040124045765*i + 1881684727616963945842060796788171278039491185096740965627887778594179476105202541456478557304673086]
[1756077780020567359443754915888514185407371957577724923461216434521905705877637149988978040124045765*i + 13732699222440210244507538000407169864743826562585707874733475922200111694018747588051420360695969701 8982919262347209788711005212913023444697315328981078436909988402240147817781731611064969846256955573*i + 3765457014279809956954260428460280043908869382556850885683433873161873968349753755711085812309759210]
[ 1881371858615367495979936456052833089872096441628283057598121060625192177926987544203162878521148159*i + 2786543516685313266376357758565837454350585473891921861545979837196340717363293199705315241832288765 11256877498661346110604063673865090970528886708319285248471932347487536611717097833493040746484556862*i + 7894130681478798794027079182653982044748502187803860895609544400580668595047811770360215666587674870]
[11256877498661346110604063673865090970528886708319285248471932347487536611717097833493040746484556862*i + 7720253268578375396322519614541359098034815559878587944751819300213622575076138359147683251412967917 13733012091441806694369662341142508052911221306054165782763242640169098992196962585304736039479494628*i + 2786543516685313266376357758565837454350585473891921861545979837196340717363293199705315241832288765]
2418647487938229570796016168675436284876845327648781656081662061111385418663188068833989750891784650 5415892221835400173647908582958920513903911956526191842594953242062956188629818670097956727183023943
3154439545432396961956699348456238623824325620135062067010297613281296016063398330576640732772792880 2115021806724219740260612273961639573913826808587509928771914504260791748069688841324214897436494477
8387334036474732265753636830045470359800171486506787888726375311651688036101558463050370202509442336
b'\nGuess x: '
b"SECCON{Yay! You've got a 333-bit useful prime for CTF! <333}\n"
b''
b''
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment