 # FCSC 2022 Surface

Top News05/17/2022

By Florian Picca

In this challenge we need to solve the congruent number problem to recover an AES key.

## Details

• Category : Crypto
• Points : 477
• Solves : 10

## Description

This script implements an exotic way to generate an AES key that protects the flag. Can you find this key?

Source code :

``````import os
import json
import gmpy2
from fractions import Fraction
from Crypto.Cipher import AES

def encrypt(n):
IV = os.urandom(16)

k = int.to_bytes(n, 32, "big")
aes = AES.new(k, AES.MODE_CBC, iv = IV)
output = {
"iv": IV.hex(),
"ciphertext": ctxt.hex(),
}
return output

if __name__ == "__main__":

try:
a = Fraction(input(">>> a = "))
b = Fraction(input(">>> b = "))

c = a ** 2 + b ** 2
assert gmpy2.is_square(c.numerator)
assert gmpy2.is_square(c.denominator)
assert a * b == 20478

n = int(gmpy2.isqrt(c.numerator))

output = encrypt(n)
print(json.dumps(output))

except:
# {"iv": "a79ec4a60d33eae0e0d9e06f8b309348", "ciphertext": "29d4c8dceecb461cfc7c06242d25879cdcf47fca47ded512ea830d09613ecd497a9720231cb423e95ed2463f5f74d8f5c4c9b75704ff738fe48475191b62f14280f32c05daf9300ab1d692d8717371dc"}``````

## Understanding the problem

After a lot of research online, this problem is known as the congruent number problem.

The goal is to find two rational sides of a triangle so that the area is equal to 10239.

What does this have to do with crypto you might wonder. The answer is : Elliptic curves ! ## Solving the problem

I must admit, I didn’t find the relation with elliptic curves until several hours of searching.

Starting with the two equations of the problem: `a^2 + b^2 = c^2` and `1/2ab = n`. If you set `x = n(a+c)/b` and `y = 2n^2(a+c)/b^2`, you can derive the equation of an Elliptic curve : `y^2 = x^3 - n^2x`. Converting a point back to triangle sides can be done by computing `a = (x^2 - n^2)/y` and `b = 2nx/y`.

Solving the congruent number problem is equivalent to finding integral points on the above curve, whose Y-coordinates are non-zero.

Thankfully sage has a builtin function for that !

Let’s try it :

``````E=EllipticCurve([-5**2, 0])
E.integral_points()
# [(-5 : 0 : 1), (-4 : 6 : 1), (0 : 0 : 1), (5 : 0 : 1), (45 : 300 : 1)]``````

If we convert the points (-4, 6) and (45, 300) to sides of the triangle, we get:

``````from fractions import Fraction
def convert(x, y, n):
a = abs(x**2-n**2)
b = abs(2*n*x)
a = Fraction(f"{a}/{y}")
b = Fraction(f"{b}/{y}")
return a, b

convert(-4, 6, 5)
# (Fraction(3, 2), Fraction(20, 3))
convert(45, 300, 5)
# (Fraction(20, 3), Fraction(3, 2))``````

This is exaclty the expected results. We just have to do that for the challenge value :

``````E=EllipticCurve([-10239**2, 0])
E.integral_points()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
/usr/lib/python3/dist-packages/sage/schemes/elliptic_curves/ell_rational_field.py in integral_points(self, mw_base, both_signs, verbose)
5810             try:
-> 5811                 mw_base = self.gens()
5812             except RuntimeError:

/usr/lib/python3/dist-packages/sage/schemes/elliptic_curves/ell_rational_field.py in gens(self, proof, **kwds)
2229
-> 2230         gens, proved = self._compute_gens(proof, **kwds)
2231         self.__gens = (gens, proved)

/usr/lib/python3/dist-packages/sage/schemes/elliptic_curves/ell_rational_field.py in _compute_gens(self, proof, verbose, rank1_search, algorithm, only_use_mwrank, use_database, descent_second_limit, sat_bound)
2337                 del self.__mwrank_curve
-> 2338                 raise RuntimeError("Unable to compute the rank, hence generators, with certainty (lower bound=%s, generators found=%s).  This could be because Sha(E/Q) is nontrivial."%(C.rank(),G) + \
2339                       "\nTry increasing descent_second_limit then trying this command again.")

RuntimeError: Unable to compute the rank, hence generators, with certainty (lower bound=0, generators found=[]).  This could be because Sha(E/Q) is nontrivial.
Try increasing descent_second_limit then trying this command again.

During handling of the above exception, another exception occurred:

RuntimeError                              Traceback (most recent call last)
<ipython-input-1-0352cc7046c9> in <module>
1 E=EllipticCurve([-Integer(10239)**Integer(2), Integer(0)])
----> 2 E.integral_points()

/usr/lib/python3/dist-packages/sage/schemes/elliptic_curves/ell_rational_field.py in integral_points(self, mw_base, both_signs, verbose)
5811                 mw_base = self.gens()
5812             except RuntimeError:
-> 5813                 raise RuntimeError("Unable to compute Mordell-Weil basis of {}, hence unable to compute integral points.".format(self))
5814             r = len(mw_base)
5815         else:

RuntimeError: Unable to compute Mordell-Weil basis of Elliptic Curve defined by y^2 = x^3 - 104837121*x over Rational Field, hence unable to compute integral points.``````

Well… Let’s use Magma then :

``````E := EllipticCurve([-10239*10239, 0]);
IntegralPoints(E);
# [ (-10239 : 0 : 1), (0 : 0 : 1), (10239 : 0 : 1) ]
# [ <(-10239 : 0 : 1), 1>, <(0 : 0 : 1), 1>, <(10239 : 0 : 1), 1> ]`````` Back to the beginning !

After a lot of hours searching for another solution, I stumbled upon this paper, which gives another way to compute such points in section 4 :

``````N = 10239
E = EllipticCurve([-N*N, 0])
pari(E).ellheegner()
# 737343773862301088045509418793921869066076/10893159238600577313677917228652511841, 625862116444448047393458603029555713662450024330982757172975030/35952639365198540562613869494033558726733788804390127889``````

The above computation took ONLY 3 hours to give a result.

## Implementing the solution

From the result of `ellheegner()` we just need to convert both fractions to sides of the triangle.

The full solution script is given below :

``````from sage.all import gcd, QQ
from fractions import Fraction
import gmpy2
from Crypto.Cipher import AES

def decrypt(x, y):

a = Fraction(x)
b = Fraction(y)

c = a ** 2 + b ** 2
n = int(gmpy2.isqrt(c.numerator))
k = int.to_bytes(n, 32, "big")
iv = bytes.fromhex("a79ec4a60d33eae0e0d9e06f8b309348")
flag = bytes.fromhex("29d4c8dceecb461cfc7c06242d25879cdcf47fca47ded512ea830d09613ecd497a9720231cb423e95ed2463f5f74d8f5c4c9b75704ff738fe48475191b62f14280f32c05daf9300ab1d692d8717371dc")
aes = AES.new(k, AES.MODE_CBC, iv=iv)
print(aes.decrypt(flag))

# https://arxiv.org/pdf/2106.07373.pdf
N = 10239
#E = EllipticCurve([-N*N, 0])
#pari(E).ellheegner()
# 737343773862301088045509418793921869066076/10893159238600577313677917228652511841, 625862116444448047393458603029555713662450024330982757172975030/35952639365198540562613869494033558726733788804390127889
# s/t, u/v
s = QQ(737343773862301088045509418793921869066076)
t = QQ(10893159238600577313677917228652511841)
u = QQ(625862116444448047393458603029555713662450024330982757172975030)
v = QQ(35952639365198540562613869494033558726733788804390127889)
x = abs(s/t)
y = abs(u/v)
a = abs(x**2 - N**2)
b = 2*N*x
g_a = gcd(a,y);
g_b = gcd(b, y);
a = a/g_a;
d = y/g_a;
b = b/g_b;
e = y/g_b;
print(a, b, d, e)
decrypt(f"{a}/{d}", f"{b}/{e}")``````

Flag : FCSC{67084c2bc8acfbf5e8a0d5e2809e230d092ab56630713dbe33ca42b8430a992b}