TJCTF 2016 Crypto 200 curvature2 Writeup

solve.py

from scryptos import *
from ecpy import * # https://github.com/elliptic-shiho/ecpy

p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
Gx = 0xcf634030986cf41c1add87e71d638b9cc723c764059cf4c9b8ed2a0aaf5d51dc770372503ebfaad746ab9220e992c09822916978226465ad31d354a3efee51da
Gy = 0x65eaad8848b2787103fce02358b45d8a61420031989eb6b4b70d82fe20d85583ae542eb8f76749dc640b0f13f682228819b8b2f04bd7a5a17a4c675540fe1c90
Px = 10150325274093651859575658519947563789222194633356867789068177057343771571940302488270622886585658965620106459791565259790154958179860547267338437952379763
Py = 6795014289013853849339410895464797184780777251924203530417684718894057583288011725702609805686960505075072642102076744937056900144377846048950215257629102

F = FiniteField(p)
E = EllipticCurve(F, A, B)

G = E(Gx, Gy)
P = E(Px, Py)
print G

x = SSSA_Attack(F, E, G, P)
print "[+] x = %d" % x
print hex(x)

assert G * x == P

print long_to_bytes(x)

solve_log

Wed Jun  1 03:37:18 JST 2016 ~/ctf/tjctf-2016/cr200 100%
> python solve.py 
[+] found gmpy! use gmpy.is_prime
Point (10861775096169286150205319688117417914848123109121745067635541337017032620284063473400066861512935256258915840659666881491995138752871261707640938043429338 : 5337811241444738635104333336651682435333375485474589886962155976578217543214247962118129491172191299739399710969955348487423009201403727326401683735321744 : 1) on Elliptic Curve y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671Lx + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466L over FiniteField(11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419)
[+] p, q = 3450880828084072449998818663271808542767631363147343225817395542202114481551729789, 1
[+] x = 3450880828084072449998818663271808542767631363147343225817395542202114481551729789
0x746a6374667b6f6f70735f656c6c31707431635f6375727665735f525f683472647d
tjctf{oops_ell1pt1c_curves_R_h4rd}

Writeup: Solve ECDLP by SSSA Attack

First, given script doesn't have a parameter b. so, I calculate b as follows:

y^2 = x^3 + ax + b
y^2 - x^3 - ax = b

In sage:

sage: P = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
sage: F = GF(P)
sage: Gx = F(0xcf634030986cf41c1add87e71d638b9cc723c764059cf4c9b8ed2a0aaf5d51dc770372503ebfaad746ab9220e992c09822916978226465ad31d354a3efee51da)
sage: Gy = F(0x65eaad8848b2787103fce02358b45d8a61420031989eb6b4b70d82fe20d85583ae542eb8f76749dc640b0f13f682228819b8b2f04bd7a5a17a4c675540fe1c90)
sage: PR.<x> = PolynomialRing(F)
sage: A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
sage: f = x^3 + A*x
sage: B = Gy ^ 2 - f(Gx)
sage: E = EllipticCurve(F, [A, B])
sage: E(Gx, Gy)
(10861775096169286150205319688117417914848123109121745067635541337017032620284063473400066861512935256258915840659666881491995138752871261707640938043429338 : 5337811241444738635104333336651682435333375485474589886962155976578217543214247962118129491172191299739399710969955348487423009201403727326401683735321744 : 1)

Well, I got b. I calculate order of that curve:

sage: E.order()
11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
sage: E.order() - P
0

Oh, #E = p ! This is Anomalous Elliptic Curve. well, I wrote some script and (first) solve challenge!

Flag: tjctf{oops_ell1pt1c_curves_R_h4rd}

I can't load "scryptos" in the first,can you help me?thanks:-)

packages : scryptos
From https://github.com/scryptos/scryptoslib