Skip to content

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

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