← CTF
ctf
Challenge author

Triple Curves

2600 training · Crypto

Difficulty: Easy

Original PDF

From the chall.py:

python
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:

python
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 𝑃 [0] ∗𝑄[0] ∗ 𝑅[0] will be smaller than 𝑝 ∗ 𝑞 ∗ 𝑟, making 𝑠 recoverable.

3. XOR Masking: The script adds 𝑅[0] 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 𝑃 [0], 𝑄[0], and 𝑅[0] are smaller than their respective field moduli, ensuring that 𝑠 is fully recoverable.

3. Once we have 𝑠, we add 𝑅[0] 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

python
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 𝑃 [0] ∗ 𝑄[0] ∗ 𝑅[0] is smaller than 𝑝 ∗ 𝑞 ∗ 𝑟.

⎩{⎨{⎧𝑠 = F1(𝑠) mod 𝑝𝑠 = F2(𝑠) mod 𝑞𝑠 = F3(𝑠) mod 𝑟
⇒ {CRT([F1(𝑠), F2(𝑠), F3(𝑠)], [𝑝, 𝑞, 𝑟]) = 𝑠 mod(𝑝 ∗ 𝑞 ∗ 𝑟)

And finally:𝑃 [0] ∗ 𝑄[0] ∗ 𝑅[0] < 𝑝 ∗ 𝑞 ∗ 𝑟 ⇒ 𝑠 mod(𝑝 ∗ 𝑞 ∗ 𝑟) = 𝑠

Recovering the Flag: After recovering 𝑠, we need to add 𝑅[0] 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 𝑧 = 1 in −𝑥3− 𝑥2∗ 𝑧 + 𝑦2∗𝑧 − 𝑥 ∗ 𝑧2+ 26959946667150639794667015087019630673557916260026308143510066298878 ∗𝑧3= 0. So by substituting 𝑦 = 𝑦𝑅 and 𝑧 = 1 (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.