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 P-Adic 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 itself
• log.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

• https://wstein.org/edu/2010/414/projects/novotney.pdf

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