Tags: ellipticcurve crypto ecc
Rating:
# Problem [Crypto, 266 Points]
> 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}
```
# Resources
- [Excellent intro to ECC](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/?fbclid=IwAR2DuwJlpS2gsTWg38EN7BRrcJBw_aGDBrkUvvYb9TDsqjrNrH2CSPB0SWk)
- [Sage Docs on ECC Discrete Logarithms](http://doc.sagemath.org/html/en/reference/groups/sage/groups/generic.html)
- [Article on Attacking ECC](https://wstein.org/edu/2010/414/projects/novotney.pdf)
# Solution
## TLDR
Calculate `B` with algebra then plug everything into an ECC discrete logarithm solver.
## Solution
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](http://doc.sagemath.org/html/en/reference/groups/sage/groups/generic.html) 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}`.
