ecgen
#
Tool for generating Elliptic curve domain parameters.
Usage#
ecgen --fp/--f2m BITS
Field specification#
--f2m
Binary field.--fp
Prime field.
Generation methods#
--anomalous
Generate an anomalous curve (of trace one, with field order equal to curve order).-i / --invalid
Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).-n / --order=ORDER
Generate a curve with givenORDER
(using Complex Multiplication).-s / --ansi[=SEED]
Generate a curve fromSEED
(ANSI X9.62 verifiable procedure).-b / --brainpool[=SEED]
Generate a curve using the Brainpool verifiably pseudorandom algorithm from the original paper.--brainpool-rfc[=SEED]
Generate a curve using the Brainpool verifiably pseudorandom algorithm as per RFC 5639.--twist
Generate a twist of a given curve.
Generation options#
-c / --count=COUNT
Generate multiple curves.-k / --cofactor=VALUE
Generate a curve with cofactor ofVALUE
.-K / --koblitz[=A]
Generate a Koblitz curve (a in {0, 1}, b = 1).-p / --prime
Generate a curve with prime order.--points=TYPE
Generate points of givenTYPE
(random/prime/all/nonprime/none).-r / --random
Generate a random curve (using Random approach).-u / --unique
Generate a curve with only one generator.
IO options#
-f / --input=FILE
Input fromFILE
.-o / --output=FILE
Output intoFILE
. Overwrites any existing file!-a / --append
Append to output file (don’t overwrite).-v / --verbose[=FILE]
Verbose logging (to stdout orFILE
).
Other#
-d / --data-dir=DIR
Set PARI/GP data directory (containing seadata package).-m / --memory=SIZE
Use PARI stack ofSIZE
(can have suffix k/m/g).--threads=NUM
UseNUM
threads.--thread-stack=SIZE
Use PARI stack ofSIZE
(per thread, can have suffix k/m/g).--timeout=TIME
Timeout computation of a curve parameter afterTIME
(can have suffix s/m/h/d).
Examples#
Generate a prime field, uniquely generated, prime order, 192-bit curve, don’t ask for input try random values:
> ecgen --fp -u -p -r 192
Generate 5 random, binary field, 163-bit curves:
> ecgen --f2m -r -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>
Generate a prime field, uniquely generated, prime order curve, don’t ask for input try random values, verbose output (shown with example output here):
> ecgen --fp -u -p -r -v 128 +++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-++++-+++++++ { "field": { "p": "0xa5393890f26881d94ad670171ce67b79" }, "a": "0x9c083973bdca36ea71078bbaabab4947", "b": "0x3d986a0206bfbe1ba62c858df54385e9", "order": "0xa5393890f26881d9394aece3bc2d9b47", "subgroups": [ { "x": "0x5acc17d6a44e8f8d30e877f4fef8712f", "y": "0x6864dd64e80609abd1797c8de1febb9f", "order": "0xa5393890f26881d9394aece3bc2d9b47", "cofactor": "0x1", "points": [ { "x": "0x9c7878930ddf5bfb705102f652754e7", "y": "0x4b15a7bb808cb3579fd4c2ce42f628de", "order": "0xa5393890f26881d9394aece3bc2d9b47" } ] } ] }
Docs#
See docs. Also:
make docs
for Doxygen.
Generation methods#
Four 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 Koblitz curve.-u / --unique
generates a uniquely generated curve (with one generator/cyclic group).--twist
generates a curve and then produces it quadratic twist.- 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. - These curves are NOT SECURE and are useful for implementation testing.
- 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.
- Only works over a prime field.
- Used with the
-n / --order
option. - Uses generation method from: Constructing elliptic curves of prime order - [Broker, Stevenhagen] (see Algorithm 2.2)
- Creates the class polynomials using the built in PARI/GP
polclass()
function or the implemented class polynomial algorithm from IEEE P1363 - Constructing elliptic curves of prescribed order - [Broker (thesis)]
- Generating Elliptic Curves of Prime Order - [Savas, Schmidt, Koc]
Anomalous curve generation#
- Generates curves of order equal to field order.
- Used with the
--anomalous
option. - These curves are NOT SECURE and are useful for implementation testing.
- Elliptic curves over F_p suitable for cryptosystems - [Miyaji]
Build#
ecgen can be built using Make or CMake.
Make#
git clone https://github.com/J08nY/ecgen.git cd ecgen git submodule update --init make
CMake#
git clone https://github.com/J08nY/ecgen.git cd ecgen git submodule update --init mkdir build && cd build && cmake .. && make
Requirements#
- PARI/GP
- gcc / clang
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).
ecgen uses some extensions supported by the gcc and clang compilers, namely __thread
-local storage.
Libraries#
lib/parson
©MITlib/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 2 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
© Eastern Seaboard Phishing Authority