Triple Curves
2600 training · Crypto
From the chall.py:
from Crypto.Util.number import *
from flag import FLAG
FLAG = bytes_to_long(FLAG)
p = 2^222 - 117 # strong prime from https://safecurves.cr.yp.to/
F1 = FiniteField(p)
E1 = EllipticCurve(F1, [0, 1, 0, 1, 3])
q = 2^221 - 3 # strong prime from https://safecurves.cr.yp.to/
F2 = FiniteField(q)
E2 = EllipticCurve(F2, [0, 1, 0, 1, 3])
r = 2^224 - 2^96 + 1 # strong prime from https://safecurves.cr.yp.to/
F3 = FiniteField(r)
E3 = EllipticCurve(F3, [0, 1, 0, 1, 3])
P = E1.random_point()
Q = E2.random_point()
R = E3.random_point()
s = (int(P[0]) * int(Q[0]) * int(R[0]))
print(f"{F1(s)=}")
print(f"{F2(s)=}")
print(f"{F3(s)=}")
s += int(R[0])
assert s > FLAG
print(f"s XOR flag={s ^^ FLAG}")
print(f"{R[1]=}")Known infos
Goal: The challenge generates three elliptic curve points ,
, and
from
three different finite fields. The goal is to recover the flag, which has been
XORed with a masked value
, derived from the
-coordinates of these
points.
Informations from chall.py:
p = 2^222 - 117
q = 2^221 - 3
r = 2^224 - 2^96 + 1
print(f"{F1(s)=}") # i.e. s % p
print(f"{F2(s)=}") # i.e. s % q
print(f"{F3(s)=}") # i.e. s % r
assert s > FLAG # i.e. the xor will be a one-time pad
print(f"s XOR flag={s ^^ FLAG}")
print(f"{R[1]=}")The -coordinates of the points
,
, and
are multiplied together to
produce
, and then masked. Our goal is to reverse this process and recover
the original flag.
Analyse
Key Points
1. Three Strong Primes: The primes ,
, and
used to define the finite
fields are strong primes chosen from secure cryptographic sources. These
primes are also pairwise co-prime, which is important for the next step in
solving the challenge using the Chinese Remainder Theorem (CRT).
2. CRT Application: Since ,
, and
are pairwise co-prime, we can
apply the Chinese Remainder Theorem to reconstruct
modulo
.
This property allows us to uniquely determine
because the product
will be smaller than
, making
recoverable.
3. XOR Masking: The script adds to
and then XORs the result
with the flag. Once
is recovered, reversing the XOR operation will allow
us to recover the original flag.
How to solve
Recovering 
To solve this challenge, we need to reverse the process:
1. The first step is to recover modulo
,
, and
. These values are given
as
F1(s), F2(s), and F3(s) in the output.
2. Since ,
, and
are prime and co-prime, we can apply the Chinese
Remainder Theorem to reconstruct
modulo
. This works because
the values of
,
, and
are smaller than their respective field
moduli, ensuring that
is fully recoverable.
3. Once we have , we add
to match the value before the XOR operation, and then XOR the result with the value stored in
s XOR flag to
recover the flag.
Solve script
from Crypto.Util.number import *
p = 2^222 - 117
F1 = FiniteField(p)
E1 = EllipticCurve(F1, [0, 1, 0, 1, 3])
q = 2^221 - 3
F2 = FiniteField(q)
E2 = EllipticCurve(F2, [0, 1, 0, 1, 3])
r = 2^224 - 2^96 + 1
F3 = FiniteField(r)
E3 = EllipticCurve(F3, [0, 1, 0, 1, 3])
s_xor_flag, F1_s, F2_s, F3_s, yR = None, None, None, None, None
with open("output.txt", 'r') as file:
for line in file:
line = line.strip()
if line.startswith("s XOR flag="):
s_xor_flag = int(line.split("=")[1])
elif line.startswith("F1(s)="):
F1_s = int(line.split("=")[1])
elif line.startswith("F2(s)="):
F2_s = int(line.split("=")[1])
elif line.startswith("F3(s)="):
F3_s = int(line.split("=")[1])
elif line.startswith("R[_sage_const_1 ]="):
yR = int(line.split("=")[1])
polR = E3.defining_polynomial()
xRs = polR(y=yR,z=1).univariate_polynomial().roots(multiplicities=False)
for x in xRs:
s = int(CRT([F1_s, F2_s, F3_s], [p, q ,r]))
s += int(x)
flag = long_to_bytes(s_xor_flag ^^ int(s))
print(flag) if b"}" in flag else ...Explanation
Chinese Remainder Theorem: By leveraging the fact that ,
, and
are co-prime, we can apply the CRT to reconstruct
modulo
,
which directly gives us the value of
. This is feasible because the product
is smaller than
.
And finally:
Recovering the Flag: After recovering , we need to add
to reverse
the addition in the original script. Once done, we can XOR the result with
the masked flag value
s XOR flag to recover the original flag.
Note: To recover
-coordinate, (needed to recover
before
s += int(R[0])), the
code extracts the -coordinate
of the elliptic curve point
and then computes the
possible
-coordinates that satisfy the curve’s equation. Mathematically, this is equivalent
to solving the elliptic curve equation for
given
and
in
. So by substituting
and
(the
value is used for projective elliptic curves),
the code transforms the elliptic curve equation into an univariate polynomial in
and finds
the roots (possible
-values) that correspond to
. These roots are stored in
xRs for further
iteration.
Conclusion
This challenge highlights the power of the Chinese Remainder Theorem in
modular arithmetic, especially when working with cryptographic systems
based on finite fields. By correctly reconstructing through CRT and reversing the XOR operation, we are able to successfully recover the flag.