# Elliptic Curves and Finite Abelian Groups

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.

• 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$? Commented Apr 21, 2021 at 18:48
• Ok, I went to go forward and write a little for you. Commented Apr 21, 2021 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