One can note that, given an elliptic curve mod $p$, that the set of points together with the usual addition law gives a finite Abelian group.

Now by the fundamental theorem of finite abelian groups, $$E\cong\mathbb{Z}/p_1^{a_1}\mathbb{Z}\otimes\dots\otimes\mathbb{Z}/p_k^{a_k}\mathbb{Z},$$ where $$E=\{(x,y)\in\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}:y^2\equiv x^3+ax+b\}\cup\{O\}$$ and $n=p_1^{a_1}\dots p_k^{a_k}$.

Are there any cryptographic attacks on elliptic curve cryptography that utilize this decomposition? $n$ can be obtained easily enough by Schoof's algorithm.

  • $\begingroup$ I had tried doing some Google searching but was having trouble finding anything. I remember learning about Pohlig-Hellman but we only discussed its implementation for $\mathbb{Z}/p\mathbb{Z}$ particularly. Is there a good way of determining $a$ and $b$ to achieve these desired properties of $n$? $\endgroup$ Apr 21 at 18:48
  • $\begingroup$ Ok, I went to go forward and write a little for you. $\endgroup$
    – kelalaka
    Apr 21 at 23:00

Let $E$ be an elliptic curve over a finite field $K$ with an order $n$ such that $n =p_1^{a_1}\dots p_k^{a_k}$. The order is the number of rational points of the curve.

There are various point for a curve to be secure;

  • Discrete logarithm

    The basic security of ECC is the Dlog that is given a base point $G$ and another point $P$ with $P= [x]G$

    There are many Dlog algorithms, however, two of them are important here

    1. Pollards' Rho and this defines the bound; that is a curve with $n$ elements the cost of Pollard's $\rho$ is $\mathcal{O}(\sqrt{n})$, therefore a curve with $n$ point cannot be secure than this.

    2. Pohlig-Hellman is applicable if $n$ is a smooth integer. It has $$\mathcal O\left(\sum_i {a_i(\log n+\sqrt {p_i})}\right)$$ time complexity where $\prod_i p_i^{a_i}$ is the prime factorization of group order $n$.

    To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time. Or the order must have at least one large factor where DLog is hard.

    If you are looking an example then this curve $E(F_p) : y^2 = x^3 + 7x + 1$ with $p = 9254331510119 $ is a concrete case for Pohlig-Hellman.

  • Co-factor

    Co-factor $h$ is defined as $h = \#E(K)/n$. We want the cofactor small or equal to 1. If not, then;

    The attacker may choose one of the small sub-group to use the Lim–Lee active small-subgroup attacks. This attack is very effective if the $n$ has many small factors. Then, the attackers can use CRT to combine the results.

    For each query the attacker can reveal by $[a]P$ is at most $\lceil log_2 h\rceil$ bits. To mitigate this a curve with co-factor is small or 1 or a strict point validation is required.

The above are the obvious security issues when the order is of the form $\prod_i p_i^{a_i}$ for some distinct primes $p_i$ and $a_i \in \mathbb{Z}^+$. The list, however, is not complete;

  • The twist security

    From the factorization, one can say that our curve's one of the primes is large enough to be secure against DLog. If the attacker sends a point on the twist with low order, then can use Lim-Lee's attack to combine the results. To mitigate, a curve with a large prime factor of the twisted order is required as in Curve25519 and point validation!

  • And, more see in safecurves


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.