# PicoCTF 2k14 - ECC

Problem

String Encoding: ASCII

def STR(a):
    a = str(a)
    # Yes, this is a little bit silly :-)
    for i in range(0, len(a) - 1, 2):
            print(chr(int(a[i:i+2]))),

e.g. STR(7269767679) = "HELLO"

Cryptosystem:
Elliptic Curve: y^2 = x^3 + ax + b mod n
a = 0
b = ?
n = 928669833265826932708591

Encryption: C = e * M mod n
Decryption: M = d * C mod n
e = 141597355687225811174313
d = 87441340171043308346177
C = (236857987845294655469221, 12418605208975891779391)
STR(M.x) + STR(M.y) = ?

Solution

# apt-add-repository -y ppa:aims/sagemath
# apt-get update
# apt-get install sagemath-upstream-binary
# sage

sage: y = 12418605208975891779391
sage: x = 236857987845294655469221
sage: a = 0
sage: n = 928669833265826932708591
sage: b = (y**2 - x**3 - a*x) % n
sage: b
268892790095131465246420

sage: F = FiniteField(n)
sage: E = EllipticCurve(F, [a, b])
sage: G = E.point((x, y))
sage: d = 87441340171043308346177
sage: M = G * d
sage: M
(6976767380847367326785 : 828669833265826932708578 : 1)

In [1]: print STR(6976767380847367326785), STR(828669833265826932708578)
ELLIPTIC CURVES ARE FUN

References

https://www.youtube.com/watch?v=vnpZXJL6QCQ