R3CTF 2025
ottol r3pus
Challenge:
from Crypto.Util.number import getPrime
from random import randint
import signal
def _handle_timeout(signum, frame):
raise TimeoutError('function timeout')
timeout = 60
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)
print("Welcome to ottoL repus.")
bitsize = 1024
flag = open("flag",'r').read()
p,q = getPrime(bitsize // 2),getPrime(bitsize // 2)
score = 0
chances = 0
for _ in range(16):
print("1. Game Start.")
print("2. Check score.")
print("Score:", score)
coi = int(input())
if coi == 1:
secret = randint(0, 2 ** 64)
r1,r2 = randint(0, q), randint(0,p)
u = randint(0, 2 ** (bitsize // 2))
v = (secret * 2 ** 128 + randint(0, 2 ** 128)) - u
x = u + r1 * p
y = v + r2 * q
print("x =", x)
print("y =", y)
guess = int(input("Give me the secret number: "))
if guess == secret:
score += 1
print("You are smart!")
else:
print("~")
elif coi == 2:
print("Your scores:", score)
if score >= 10:
print(flag)
else:
print("Fighting!")
elif coi == p:
print("Wtf? You known the real secret number!")
print(flag)
Cleanup:
from Crypto.Util.number import getPrime
p, q = getPrime(512),getPrime(512)
xs = []
ys = []
for _ in range(6):
secret = randint(0, 2**64)
r1, r2 = randint(0, q), randint(0, p)
u = randint(0, 2**512)
r3 = randint(0, 2**128)
v = (secret * 2**128 + r3) - u
x = u + r1 * p
y = v + r2 * q
xs.append(x)
ys.append(y)
#print(xs)
#print(ys)
Author’s solve:
from os import environ
environ['TERM'] = 'kitty'
from pwn import process, remote
from Crypto.Util.number import isPrime
from re import findall
from tqdm import tqdm
import sys
from itertools import product
range_values = range(-2, 3)
triplets = list(product(range_values, repeat=3))
def Solve(x_v, y_v, n):
Mxk = Matrix(ZZ, x_v).right_kernel_matrix()
Myk = Matrix(ZZ, y_v).right_kernel_matrix()
Lxk = IntegralLattice(identity_matrix(ZZ, n), Mxk)
Lyk = IntegralLattice(identity_matrix(ZZ, n), Myk)
Lxyk = Lxk.intersection(Lyk)
Mxyk = Lxyk.basis_matrix()
MxykL = Mxyk.LLL()
Mek = MxykL[:11].right_kernel_matrix()
m_v = Mek[0]
Myk = Matrix(ZZ, y_v - m_v).right_kernel_matrix()
Lyk = IntegralLattice(identity_matrix(ZZ, n), Myk)
Lxyk = Lxk.intersection(Lyk)
Mxyk = Lxyk.basis_matrix()
MxykL = Mxyk.LLL()
Muk = MxykL[:12].right_kernel_matrix()
for triple in triplets:
u_v = vector(triple) * Muk
p = gcd(list(x_v - u_v))
if p > 2 ** 100 and isPrime(p):
return p
while True:
conn = process(["python", "chall.py"])
xs = []
ys = []
for _ in tqdm(range(15)):
resp = conn.recvuntil(b"0\n").decode()
conn.sendline(b"1")
resp = conn.recvuntil(b"number: ").decode()
xs.append(int(findall("x = (.*)", resp)[0]))
ys.append(int(findall("y = (.*)", resp)[0]))
conn.sendline(b"1")
x_v = vector(xs)
y_v = vector(ys)
resp = conn.recvuntil(b"0\n").decode()
p = Solve(x_v, y_v, 15)
print(f'{p = }')
if p is None:
conn.close()
continue
else:
conn.sendline(str(p).encode())
print(conn.recv())
break
ks solve:
import os; os.environ["TERM"] = 'linux'
from pwn import *
r = process(["python", "task.py"])
def get_xy():
r.sendline(b'1')
r.recvuntil(b'x = ')
x = int(r.recvline())
r.recvuntil(b'y = ')
y = int(r.recvline())
return x, y
def get_integer_kernel(M):
import sage.matrix.matrix_integer_dense_hnf as matrix_integer_dense_hnf
H, U = matrix_integer_dense_hnf.hnf_with_transformation(M.transpose())
n = H.nrows()
for i in range(n):
if H[i] == 0:
assert M * U[i:].transpose() == 0
return U[i:]
xs = []
ys = []
for i in range(15):
x, y = get_xy()
xs.append(x)
ys.append(y)
r.sendline(b'1')
x_v = vector(xs)
y_v = vector(ys)
M = (identity_matrix(15)).stack(x_v).stack(y_v).transpose()
vs = []
for v in M.LLL():
v = v[:-2]
#print(sum(abs(_) for _ in v).nbits(), (x_v * v).nbits(), (y_v * v).nbits())
vs.append(v)
r_o = Matrix(vs[:-2])
# r_l[0] = r1 - r2, r_l[1] = r1 or r2
r_l = get_integer_kernel(r_o).LLL()
r_i = r_l[1]
for i in [-1, 0, 1]:
r1_v = r_l[1] + i * r_l[0]
ratios = [round(x_v[j] / r1_v[j]) for j in range(15)]
if len(set(ratios)) != 15:
for p in range(ratios[0] - 10, ratios[0] + 10):
if abs(p) in Primes():
r.sendline(str(abs(p)).encode())
break
r.interactive()
When observing the LLL-reduced basis of matrix M, we can see that the norm of the basis vectors dramatically increases at the 14th and 15th rows.
I believe this is because the first 13 basis vectors are orthogonal to both r1_v and r2_v. Since the 14th and 15th vectors must be linearly independent from the previous ones, they cannot lie in this orthogonal subspace, which results in their significantly larger norms.
This implies that r1_v and r2_v are in the integer kernel of the matrix formed by these first 13 short vectors (r_o). By computing this kernel, we obtain a new basis (r_l) for a 2-dimensional lattice that contains r1_v and r2_v.
Typically, after applying LLL to this new basis, the first vector of the reduced basis is a short combination of the original vectors (often their difference), and the second vector is one of the original vectors (r1_v or r2_v).
Therefore, the set {r_l[1] - r_l[0], r_l[1], r_l[1] + r_l[0]} is highly likely to contain r1_v. Once we find r1_v, we can recover the prime p.
quite surprised to find that my solution is quite different from the intended one 😅
The main concept is the same, I was just personally surprised because I didn’t expect that both the process of slicing out a specific basis from the given vectors, and the process of using that basis to extract p, would be different approaches in my solution compared to the intended one
ETA builtin r_l = r_o.right_kernel_matrix().LLL() can also be used in place of r_l = get_integer_kernel(r_o).LLL()