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
from Crypto.Util.Padding import pad

def encrypt(n):
    IV = os.urandom(16)
    FLAG = open("flag.txt", "rb").read()

    k = int.to_bytes(n, 32, "big")
    aes = AES.new(k, AES.MODE_CBC, iv = IV)
    ctxt = aes.encrypt(pad(FLAG, 16))
    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:
        print("Error: check your inputs.")
# {"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 !

humorous image: toy story says "ellpitic curves! elliptic curves everywhere"

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)[2] 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)[2] 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> ]

No crash, but no results either… Same with Pari/GP…

image humoristique: "If sage doesn't work, try magma or pari/GP, none of them work!"

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}