ictf recurring

22 May 2025

More details

In this challenge, we’re given chall.py and the output.

# chall.py
assert len(flag) == 64
m1 = bytes_to_long(flag[:32].encode())
m2 = bytes_to_long(flag[32:].encode())

p = getPrime(256)
def release(m):
print(hex((m \* pow(2, m, p)) % p)[2:].rjust(64, '0'))

print(hex(p)[2:])
release(m1)
release(m2)
release(m2-m1)
release(m2+m1)

So m1 converts the first 32 bytes of the flag to a long integer, and m2 converts the last 32 bytes of the flag to a long integer.

release(m) is a function that takes an integer m, computes (m * pow(2, m, p)) % p, and prints the result in hexadecimal format, padded to 64 characters with leading zeros.

Outputs:

• hex(p)[2:]: The prime p in hex, without the ‘0x’ prefix. (call this p)
• release(m1): Output for m1. (call this c1)
• release(m2): Output for m2. (call this c2)
• release(m2 - m1): Output for the difference. (call this c3)
• release(m2 + m1): Output for the sum. (call this c4)

So we get the following equations:

• c1 = (m1 * pow(2, m1, p)) % p
• c2 = (m2 * pow(2, m2, p)) % p
• c3 = ((m2 - m1) * pow(2, m2 - m1, p)) % p
• c4 = ((m2 + m1) * pow(2, m2 + m1, p)) % p

The goal is to find the flag, which is m1 and m2.

An initial exploit idea which doesn’t work is to assume that m2 - m1 in c3 is small enough to be brute-forced. And then once we get d, we can get m1 and m2 from c1 and c2. But this doesn’t work.

So nvm, let’s try to solve the equations.

With

• a = 2^{m1} mod p
• b = 2^{m2} mod p

We can rewrite the equations as:

1. c1 = (m1 * a) % p
2. c2 = (m2 * b) % p
3. c3 = (m2 - m1) * (b/a) % p
4. c4 = (m2 + m1) * (b * a) % p

From equation 1, we can rearrange to get m1 = (c1 * a^{-1}) % p.

From equation 2, we can rearrange to get m2 = (c2 * b^{-1}) % p.

Equation 4,

c4 = (m2 + m1) * (b * a) % p
= (c1 * a^{-1} + c2 * b^{-1}) * (b * a) % p
= (c1 * b + c2 * a) % p

Equation 3,

c3 = (m2 - m1) * (b/a) % p
= ((c2 * b^{-1}) - (c1 * a^{-1})) * (b/a) % p
= (c2 * a - c1 * b) / a^{2} % p

c3 * a^{2} = (c2 * a - c1 * b) % p

So we need to solve

c3 * a^{2} = (c2 * a - c1 * b) % p
c4 = (c1 * b + c2 * a) % p

Rearranging the second equation, we get b = (c4 - c2 * a) / c1 % p where c1 is not zero.

Substituting this into the first equation gives us a quadratic equation in a:

c3 * a^{2}
= c2 * a - (c4 - c2 * a)
= c2 * a - c4 + c2 * a
= 2 * c2 * a - c4

So we have c3 * a^{2} - 2 * c2 * a + c4 = 0 mod p.

This is a quadratic equation in a.

• Form

  c3 * a^{2} + b * a + c = 0 mod p

• Discriminant (b^2 - 4ac)

  D = (-2 * c2)^{2} - 4 * c3 * c4 = 4 * c2^{2} - 4 * c3 * c4 mod p

• Roots: x = (-b ± sqrt(D)) / 2a mod p

  a = [2 * c2 ± sqrt(D)] / (2 * c3) mod p

Sagemath has a nice built-in function to solve quadratic equations in finite fields. So we run this in Sage:

# solve.sage
p = 0xafe4dfec75d05b8204f949749dce9d69eaee982528f7e2c177862b4f12b635d9
c1 = 0x6d04f0ebde78ca72c0a65629cd6f2cc337319c05b266ed789843ea2bdf11551f
c2 = 0x61483d050ad72a0e6dda11e3f683fbac20ab17b4a26615ac3eb4fbaecef519bd
c3 = 0x13c9395628b7f90ff1675d73cc97ae24ea5c9993366364627d20f9f52b19fabb
c4 = 0x75e04f3f38420029fa57934de57b6fb59f9615e4be32eaa4460c57a47c2842ae

# Define the finite field
F = GF(p)

# discriminant
D = F(4 * (c2^2 - c3 * c4))

# Check if D is a quadratic residue
if D.is_square():
    sqrt_D = D.sqrt()
    inv2 = F(2)^(-1)  # Inverse of 2 mod p
    inv_c3 = F(c3)^(-1)  # Inverse of c3 mod p

    # possible values of a
    a1 = (F(c2) + sqrt_D * inv2) * inv_c3
    a2 = (F(c2) - sqrt_D * inv2) * inv_c3

    # for each possible a, compute b, m1, m2
    for a in [a1, a2]:
        b = (F(c4) - F(c2) * a) * F(c1)^(-1)
        m1 = F(c1) * a^(-1)
        m2 = F(c2) * b^(-1)

        m1_int = Integer(m1)
        m2_int = Integer(m2)

        if m1_int < 2^256 and m2_int < 2^256:
            flag_part1 = m1_int.to_bytes(32, byteorder='big')
            flag_part2 = m2_int.to_bytes(32, byteorder='big')
            flag = flag_part1 + flag_part2
            print("Possible flag:", flag.decode('utf-8', errors='ignore'))
else:
    print("Discriminant is not a square, no solutions.")

Then we get the flag. Tbh I think the intended solution has to do with some recurrence relation, but I couldn’t find it so owells.