# Generating EC domain parameters - ecgen

ecgen is a tool for generating Elliptic curve domain parameters. While working on generating some interesting EC domain parameters for ECTester I found out there aren’t really any good tools for doing so. Cryptographic libraries don’t offer generating custom curves, they just offer preset ones or let you set custom ones. The only tools I found were ECB, LiDIA/GEC, MIRACL and cm. They all have their drawbacks however, ECB is limited in what parameters are modifiable and is closed source, LiDIA is unmaintained, and cm also doesn’t support the flexibility in parameters I needed. To add to that I lost the link to MIRACL and could not remember it’s name. So ecgen is what I started working on.

Since Elliptic Curve domain parameters are a rather complex object, generating them with various constraints and parameters is also complex and there are various algorithms for doing so. Generally two methods are used in practice. One is randomized and works as you might imagine from the name, by generating random domain parameters within some constraints, computing the rest of the parameters and hoping they satisfy the rest of the constraints. A variation of this is the *ANSI X9.62* verifiably random algorithm. The other method is based on the theory of Complex Multiplication and is able to directly generate Elliptic Curve domain parameters with required constraints.

Generally the biggest problem when generating Elliptic Curve domain parameters is calculating the order of the curve specified by the curve equation. Since when this order is known the rest of the parameters (generators, group structure…) are found rather easily.

Computing this order given the equation is hard, there are several rather complex algorithms, some of which are fast for curves over (AGM), some for curves over (Schoof’s, SEA).

## Usage#

ecgen --fp/--f2m BITS

### Field specification#

`--f2m`

Binary field.`--fp`

Prime field.

### Generation options#

`-c / --count=COUNT`

Generate multiple curves.`-i / --invalid`

Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).`-k / --cofactor=BOUND`

Generate a curve with cofactor up to`BOUND`

**TODO - NOT FINISHED**`--anomalous`

Generate an anomalous curve (of trace one, with field order equal to curve order).`-K / --koblitz`

Generate a Koblitz curve (a = 0).`-n / --order=ORDER`

Generate a curve with given`ORDER`

(using Complex Multiplication).**TODO - NOT IMPLEMENTED**`-p / --prime`

Generate a curve with prime order.`--points=TYPE`

Generate points of given`TYPE`

(random/prime/none).`-r / --random`

Generate a random curve (using Random approach).`-s / --seed[=SEED]`

Generate a curve from`SEED`

(ANSI X9.62 verifiable procedure).**TODO - NOT IMPLEMENTED**`-u / --unique`

Generate a curve with only one generator.

### IO options#

`-t / --format=FORMAT`

Format to output in. One of [csv,json], default is json.`-f / --input=FILE`

Input from`FILE`

.`-o / --output=FILE`

Output into`FILE`

. Overwrites any existing file!`-a / --append`

Append to output file (don’t overwrite).`-v / --verbose[=FILE]`

Verbose logging (to stdout or`FILE`

).

### Other#

`-d / --data-dir=DIR`

Set PARI/GP data directory (containing seadata package).`-m / --memory=SIZE`

Use PARI stack of`SIZE`

(can have suffix k/m/g).`--threads=NUM`

Use`NUM`

threads.`--thread-stack=SIZE`

Use PARI stack of`SIZE`

(per thread, can have suffix k/m/g).

## Examples#

Generate a prime field, prime order, uniquely generated 192-bit curve, don’t ask for input try random values:

```
> ecgen --fp -r -p -u 192
```

Generate 5 random, binary field, 163-bit koblitz curves:

```
> ecgen --f2m -r -k -c5 163
```

Generate invalid curves to a file, for a given prime field 192-bit curve:

> ecgen --fp -i --output=invalid.json 192 p: <input prime> a: <input a param> b: <input b param>

## Generation methods#

Three different EC curve parameters generation methods are implemented.

Generation Methods of Elliptic Curves - [Baier, Buchmann]

### Random approach#

- Generates field and equation parameters:
- randomly
- using ANSI X9.62 verifiably random method(from seed), until a curve with requested properties appears.
- given input

- Can generate curves repeatedly until one satisfies requested properties:
`-p / --prime`

generates curves until a prime order curve is found.`-K / --koblitz`

generates a curve with fixed*A = 0*parameter.`-u / --unique`

generates a uniquely generated curve (with one generator/cyclic group).- etc..

### Invalid curve generation#

- Generates
*invalid*curves for a given curve. - These curves have the same field, and
*A*parameter in the short Weierstrass equation. - Multiplication using some(most?) scalar multiplication algorithm proceeds the same way multiplication on the input curve would.
- Used with the
`-i / --invalid`

option - Validation of Elliptic Curve Public Keys - [Antipa, Brown, Menezes, Struik, Vanstone]
- Differential Fault Attacks on Elliptic Curve Cryptosystems - [Biehl, Mayer, Muller]
- Practical Invalid Curve Attacks on TLS-ECDH - [Jager, Schwenk, Somorovksy]

### Complex multiplication#

- Capable of generating a curve of a given (prime) order.
- Generates a subset of all Elliptic Curves over a given field.
- Used with the
`-n / --order`

option - Constructing elliptic curves of prime order - [Broker, Stevenhagen]
- Generating Elliptic Curves of Prime Order - [Savas, Schmidt, Koc]
*Currently not implemented.*

## Build#

```
git clone https://github.com/J08nY/ecgen.git
cd ecgen
git submodule update --init
make
```

## Requirements#

- PARI/GP

ecgen uses the PARI/GP library for elliptic curve arithmetic and it’s SEA point counting algorithm implementation. It also requires the additional seadata package (seadata and seadata-big recommended for large curves).

## Libraries#

`lib/parson`

*©MIT*`lib/sha1`

*©MPL / GPLv2 or later*

parson is used to input and output JSON and is included in the `lib/`

directory.

A SHA-1 implementation by Paul Kocher, based on the SHA 180-1 Reference Implementation (for ANSI X9.62 algorithm) is used and also included in the `lib/`

directory.

## License#

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

*© Eastern Seaboard Phishing Authority*