Smart attack on anomalous curves¶
Description¶
If a curve E defined over finite field of size \(p\), has a subproup with order of \(p\), then ECDLP problem can be solved in \(O(1)\) time.
Task¶
Given arbitary curve \(E\) over finite field of size \(p\) (\(\mathbb{F}_{p}\)) with \(E.order == p\) and some point \(P = d*G\), find \(d\).
Solution¶
This is a general ECDLP problem, but it can be simplified using Smart's attack.
First, we generate \(P'\) and \(G'\) in \(p\)adic field \(Q_{p}\) using Hensel's lift
Next, we reduce new curve \(E_{1}(Q_p)\) to new curve \(E_{2}(Q_p)\).
Apply PAdic Elliptic log to get final equation for \(d\)
How to generate task¶

Install ecgen

Generate task:
(ecgen anomalous fp 521  ./gen_task.py) > >(tee task.txt) 2> >(tee log.txt >&2)
You will get two files:
task.txt
— task itselflog.txt
— task generator log with answer
Other tasks¶
 PoliCTF 2012 Crypto 200. Writeup by MSLC
 SharifCTF 2016 Crypto 350 — British Elevator. Writeup 1 by hxp team. Writeup 2 by Shiho Midorikawa
 DEFCON Quals 2020  nottobefooled. Writeup by Ariana1729 (interesting thing here is that we need to do the opposite  generate an anamolous curve which is not affected by Smart attack)
Links¶
Note
There is a problem when an anomalous curve is isomorphic to its lifted curve over Q_p.
Then we randomize the lift to some curve \(y^2 = x^3 + (p+a')*x + (b + p*b')\)
More info here