bachpc / ecgen Goto Github PK

Tool for generating Elliptic curve domain parameters.

ecgen --fp/--f2m BITS

• --f2m Binary field.
• --fp Prime field.

• --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).
• -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.
• --twist Generate a twist of a given curve.

• -c / --count=COUNT Generate multiple curves.
• -k / --cofactor=VALUE Generate a curve with cofactor of VALUE.
• -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.
• --metadata Compute the curve metadata (j-invariant, discriminant, trace of Frobenius, CM discriminant, embedding degree)

• -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).

• -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).

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, uniquely generated random curve, of size 192 bits, also display its metadata:

> ecgen --fp -r -u --metadata 192
[{
    "field": {
        "p": "0xc61cc69c570f03c690df1177fa1ac8c5b295587f876df1bf"
    },
    "a": "0xaa67a35fbec93655b4a9dc2fa84e2deff18077a4fa12d2ef",
    "b": "0x4477eabe9abbcfccaa3f996ed03d58f32b149c42cb22d1b9",
    "order": "0xc61cc69c570f03c690df1178443ec606114599ad0f6d8790",
    "subgroups": [
        {
            "x": "0x909b1f3b6378fb77a2c1d2117fe7229c329a4fa400605a62",
            "y": "0x2da7e3fafdd4c3b4b149cf6693151dd559eebf8b081435fd",
            "order": "0xc61cc69c570f03c690df1178443ec606114599ad0f6d8790",
            "cofactor": "0x1",
            "points": [
                {
                    "x": "0x6831806c80fbd016fb59c2eb20700716eeb392c601deda25",
                    "y": "0x000000000000000000000000000000000000000000000000",
                    "order": "0x2"
                },
                {
                    "x": "0x6206b8e9d56a22485c1b2baa6c61292ff51aa0848097e823",
                    "y": "0xbd0a1bda7ba13c81bb3ecaf4abfd34c054d9e4a41aa00733",
                    "order": "0xa3"
                },
                {
                    "x": "0x9e196e607959b78f821600fdf263834d4ad2b10046b5921c",
                    "y": "0x26f2c864a472bacd4bbb3e513b0a1c1f59a919a187fa4b47",
                    "order": "0xbe3b5"
                },
                {
                    "x": "0x0220c948fbb6403608563efc5cf16a630953281155e62d47",
                    "y": "0x3a630cd359f8028da08b27df562ab8749e3c2430b8a9f3a9",
                    "order": "0x202205798a8a981b"
                },
                {
                    "x": "0x76f971b3722e4b8bfc284c7c39adb395ade0baa61b1e6820",
                    "y": "0xb7304431b86e6a06576005a6da2afcd96b43e1ce62056724",
                    "order": "0xd07e2df2cc0790a9a06ccfa45"
                }
            ]
        }
    ],
    "meta": {
        "j": "2147872786867739581244581376066320780390424557746041800843",
        "discriminant": "1437087699540380117015716490177070508119149165688061690066",
        "embedding_degree": "4857702049745916698354329148965234205490318980592629024655",
        "frobenius": "-22945399076600858943676192208",
        "cm_discriminant": "4726079215049797810784721872708419089129671954601412853631"
    }
}]

See docs. Also:

make docs

for Doxygen.

Four 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]

• 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..

• 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]

• 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]

• CONSTRUCTING SUPERSINGULAR ELLIPTIC CURVES - [Broker]

• 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]

ecgen can be built using Make or CMake.

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

git clone https://github.com/J08nY/ecgen.git
cd ecgen
git submodule update --init
mkdir build && cd build && cmake .. && make

• 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.

• 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.

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