Tags: ellipticcurve crypto ecc
Rating:
Sent this curve to NIST for an approval, got rejected. I can't figure out why?
We get a file with the following contents:
Elliptic Curve: y^2 = x^3 + A*x + B mod N
N = 58738485967040967283590643918006240808790184776077323544750172596357004242953
A = 76727570604275129576071347306603709762219034167050511215297136720584179974657
B = ???
P = (1499223386326383661524589770996693829399568387777849887556841520506306635197, 18509752623395560148909577815970815579696746171847377654079329916213349431951)
Q = (29269524564002256949792104801311755011410313401000538744897527268133583311507, 29103379885505292913479681472487667587485926778997205945316050421132313574991)
Q = n*P
The flag is utc{n}
Calculate B with algebra then plug everything into an ECC discrete logarithm solver.
Having not learned about ECC in depth, I did a lot of reading for this one. The resources above are highly recommended, especially the first.
First, I solved for B, which is doable with even one point on the curve, but having two was nice to confirm that they were consistent. This is pretty straightforward algebra:
B = y^2 - x^3 - A*x (mod N)
I checked that N was prime and that the order of the subgroup generated by P was relatively large. Without any glaring weaknesses, I searched for existing implementations of discrete logarithm solvers like the one described in the "Article on Attacking ECC" above. I found the Sage documentation and after installing Sage was able to solve the problem pretty easily.
sage: p = 58738485967040967283590643918006240808790184776077323544750172596357004242953
sage: a = 76727570604275129576071347306603709762219034167050511215297136720584179974657
sage: b = 6922870007550502185107402034529582240539099403142158978076525908900094966208
sage: E = EllipticCurve(GF(p), [a, b])
sage: P = E(1499223386326383661524589770996693829399568387777849887556841520506306635197, 185097526233955601489095778159708155796967461718473776540793299162133
....: 49431951)
sage: Q = E(29269524564002256949792104801311755011410313401000538744897527268133583311507, 291033798855052929134796814724876675874859267789972059453160504211323
....: 13574991)
sage: P.order()
19579495322346989094530214639335413602950719348636677951534239261159390383026
sage: discrete_log(Q,P,P.order(),operation='+')
314159
The flag is utc{314159}.
