J08nY/ecgen

Tool for generating Elliptic curve domain parameters

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).
• --supersingular Generate a supersingular curve.
• -i / --invalid Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).
• -n / --order=ORDER Generate a curve with given ORDER (using Complex Multiplication), order can be a comma-separated(no spaces) list of factors.
• -s / --ansi[=SEED] Generate a curve from SEED (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.
• -F / --family=FAMILY Generate a pairing friendly curve from a curve family (e.g. "BN", "BLS12", "BLS24", "KSS16", "KSS18", "KSS36", "KSS40").
• --nums Generate a curve using the NUMS procedure (as per draft-black-numscurves-02).
• --twist Generate a twist of a given curve.

Generation options

• -c / --count=COUNT Generate multiple curves.
• -k / --cofactor=VALUE Generate a curve with cofactor of VALUE.
• -B / --smooth=BOUND Generate a smooth order curve with bit-lengths of factors bounded by BOUND.
• -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 given TYPE (random/prime/all/nonprime/none).
• -r / --random Generate a random curve (using Random approach).
• -u / --unique Generate a curve with only one generator.
• --hex-check=HEX Generate a curve with HEX string in the hex expansion of its parameters.
• --metadata Compute the curve metadata (j-invariant, discriminant, trace of Frobenius, CM discriminant, embedding degree)

IO options

• -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).
• --timeout=TIME Timeout computation of a curve parameter after TIME (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"
                }
            ]
        }
    ]
}

Generate a prime field curve with given order (given as a list of factors) of size 128 bits and do not output any points on subgroups:

> ecgen --fp -n 7,43,83,503,653,823,863,887,1019,1279,2011,2311,2381,2957 --points=none 128
[{
    "field": {
        "p": "0xa5dad2cb65b65ab89ed2248be2971c0d"
    },
    "a": "0x2407ec02a74565af4952f552fee14588",
    "b": "0x5e80456d719dcb64df00923e8b7aa726",
    "order": "0xa5dad2cb65b65ab704d75427e1e4f81b",
    "subgroups": [
        {
            "x": "0x3219e70cb3b557dd8f8ddf9e6264a28d",
            "y": "0x0aa1274c0272f13411833fd7eb7e86d8",
            "order": "0xa5dad2cb65b65ab704d75427e1e4f81b",
            "cofactor": "0x1"
        }
    ]
}]

Generate a prime field, uniquely generated random curve, of size 192 bits, also display its metadata:

> ecgen --fp -r -u --metadata 192
[{
    "field": {
        "p": "0xf0886302f64dfdd33035064e0f0a346a74c0cf0c22e22a79"
    },
    "a": "0x54c517a28dd47c296842f20273a0ec1840e576e6c06bb4e8",
    "b": "0x3ee3025dc7d8c26104e6fb3e11f3bdaabc15c73b9df27c8f",
    "order": "0xf0886302f64dfdd33035064df1a3dc1e3c4577ad590bfaa6",
    "subgroups": [
        {
            "x": "0x9e886fbe1f155acdd790183bf1ceb5c92cfa112e693d34ef",
            "y": "0x9723f733f48229287d173ce4a5147cd947de0637def3f3ed",
            "order": "0xf0886302f64dfdd33035064df1a3dc1e3c4577ad590bfaa6",
            "cofactor": "0x1",
            "points": [
                {
                    "x": "0x1f7b95e47d5224164880e9809082c60194152901d1bc613e",
                    "y": "0x000000000000000000000000000000000000000000000000",
                    "order": "0x2"
                },
                {
                    "x": "0xce3e0c542060d6e2b244ba5850e7ccdda413854454b464ff",
                    "y": "0x38c193df5bb67817128fbf9f63d4c7af55535110553d247f",
                    "order": "0x3"
                },
                {
                    "x": "0x73d0035006dc8c9e63c65d76f96cbb5da7ab9735980ece74",
                    "y": "0x420a85069882811d44458106bba9b2aedd4820f25ca7761c",
                    "order": "0x9d"
                },
                {
                    "x": "0x68f998d413b99520fe2ba1501f8ea22db0357cf88e4ab80f",
                    "y": "0x6321a63274a60d2d0db49800e806d8d7923a5eb8bcd990a6",
                    "order": "0x1ca3"
                },
                {
                    "x": "0xd81d2b8eb95474be0e456dfd3e85d17d7832775a9e867ad4",
                    "y": "0x6dc2c4c566616b1b959935192e14d403d7cfcaac4a9f0b90",
                    "order": "0x67a21"
                },
                {
                    "x": "0x919460438753800b0332685fc9294d0ae44d61fd8d7d4403",
                    "y": "0xefa307fb3d2946939461fa3b6ac2a1c658821e69837d0122",
                    "order": "0x1053aa57a15ae784f7"
                },
                {
                    "x": "0xce1773b3b404b78923f0e8ba5493e806c088ef527c712dfb",
                    "y": "0x451aa2ca72326983381c77a1965517787333ffe8c036073d",
                    "order": "0x5869ef97eaf9885325d01"
                }
            ]
        }
    ],
    "meta": {
        "j": "1634327697577408300542081333151383474217426785000945527408",
        "discriminant": "4412636550389189038392233746786780978750224170644136456036",
        "embedding_degree": "529827387818798217347035546078799382319810259857040",
        "frobenius": "9098792692692684052427583444",
        "cm_discriminant": "-23508596506131498450876986604994502392929597678959240749652",
        "conductor": "1"
    }
}]

Note

The command-line interface is quite tricky and will ignore options somewhat silently, meaning that the computation will go on and some properties of the output curve will be wrong.

If this happens, you will get a warning such as:

Warning: Ignored command-line argument prime (-p/--prime).

Docs

See docs. Also:

make docs

for Doxygen.

Generation methods

Five different EC curve parameters generation methods are implemented.

Efficient Algorithms for Generating Elliptic Curves over Finite Fields Suitable for Use in Cryptography - [Baier]

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]

Supersingular curves

• Generates curves of order equal to prime + 1 (trace of Frobenius equal to zero).
• Used with the --supersingular option.
• These curves are NOT SECURE and are useful for implementation testing.
• CONSTRUCTING SUPERSINGULAR ELLIPTIC CURVES - [Broker]

Anomalous curve generation

• Generates curves of order equal to field order (trace of Frobenius equal to 1).
• 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]
• TODO: Extend with Generating Anomalous Elliptic Curves - [Leprevost, Monnerat, Varrette, Vaydenay]

Curve families

• Generates pairing friendly curves.
• Used with the -F / --family option. Select from BN, BLS12 or BLS24 currently.

Build

ecgen can be built using Make or CMake. ecgen uses git submodules for testing at:

• test/lib/assert.sh pointing at https://github.com/J08nY/assert.sh
• test/lib/JSON.sh pointing at https://github.com/J08nY/JSON.sh
• test/lib/criterion pointing at https://github.com/Snaipe/Criterion, its build requires meson.

these need to be initialized for make test to work.

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
• posix-macos-addons for macOS

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 ©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 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