From: mdw Date: Sat, 2 Oct 2004 15:03:34 +0000 (+0000) Subject: Slight reorganization. Add elliptic curves from X9.62. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/38b901110909d19388502b487f0529514cf853ff Slight reorganization. Add elliptic curves from X9.62. --- diff --git a/catcrypt.c b/catcrypt.c index cc1ab39..c57fe70 100644 --- a/catcrypt.c +++ b/catcrypt.c @@ -88,17 +88,16 @@ static const char *keyring = "keyring"; * the verification key-id if the message is signed. * * Next comes the key-encapsulation chunk. This is decrypted in some - * KEM-specific way to yield a secret hash. This hash is what is signed if - * the message is signed. The hash is expanded using an MGF (or similar) to - * make a symmetric encryption and MAC key. + * KEM-specific way to yield a secret hash. The hash is expanded using an + * MGF (or similar) to make a symmetric encryption and MAC key. * * If the message is signed, there comes a signature chunk. The signature is - * on the secret hash. This means that the recipient can modify the message - * and still have a valid signature, so it's not useful for proving things to - * other people; but it also means that the recipient knows that the message - * is from someone who knows the hash, which limits the possiblities to (a) - * whoever encrypted the message (good!) and (b) whoever knows the - * recipient's private key. + * on the further output of the MGF. This means that the recipient can + * modify the message and still have a valid signature, so it's not useful + * for proving things to other people; but it also means that the recipient + * knows that the message is from someone who knows the hash, which limits + * the possiblities to (a) whoever encrypted the message (good!) and (b) + * whoever knows the recipient's private key. * * Then come message chunks. Each one begins with a MAC over an implicit * sequence number and the ciphertext. The final chunk's ciphertext is diff --git a/ectab.in b/ectab.in index ce4078d..4436b7e 100644 --- a/ectab.in +++ b/ectab.in @@ -1,4 +1,4 @@ -# $Id: ectab.in,v 1.2 2004/04/01 21:28:41 mdw Exp $ +# $Id$ # # Standard ellipic curves @@ -12,7 +12,6 @@ curve secp112r1 prime h 1 gx 0x09487239995a5ee76b55f9c2f098 gy 0xa89ce5af8724c0a23e0e0ff77500 - curve secp112r2 prime p 0xdb7c2abf62e35e668076bead208b a 0x6127c24c05f38a0aaaf65c0ef02c @@ -30,7 +29,6 @@ curve secp128r1 niceprime h 1 gx 0x161ff7528b899b2d0c28607ca52c5b86 gy 0xcf5ac8395bafeb13c02da292dded7a83 - curve secp128r2 niceprime p 0xfffffffdffffffffffffffffffffffff a 0xd6031998d1b3bbfebf59cc9bbff9aee1 @@ -48,7 +46,6 @@ curve secp160k1 niceprime h 1 gx 0x3b4c382ce37aa192a4019e763036f4f5dd4d7ebb gy 0x938cf935318fdced6bc28286531733c3f03c4fee - curve secp160r1 niceprime p 0xffffffffffffffffffffffffffffffff7fffffff a 0xffffffffffffffffffffffffffffffff7ffffffc @@ -57,7 +54,6 @@ curve secp160r1 niceprime h 1 gx 0x4a96b5688ef573284664698968c38bb913cbfc82 gy 0x23a628553168947d59dcc912042351377ac5fb32 - curve secp160r2 niceprime p 0xfffffffffffffffffffffffffffffffeffffac73 a 0xfffffffffffffffffffffffffffffffeffffac70 @@ -75,7 +71,6 @@ curve secp192k1 niceprime h 1 gx 0xdb4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d gy 0x9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d - curve secp192r1 niceprime p 0xfffffffffffffffffffffffffffffffeffffffffffffffff a 0xfffffffffffffffffffffffffffffffefffffffffffffffc @@ -93,7 +88,6 @@ curve secp224k1 niceprime h 1 gx 0xa1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c gy 0x7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5 - curve secp224r1 niceprime p 0xffffffffffffffffffffffffffffffff000000000000000000000001 a 0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe @@ -111,7 +105,6 @@ curve secp256k1 niceprime h 1 gx 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 gy 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 - curve secp256r1 niceprime p 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff a 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc @@ -147,7 +140,6 @@ curve sect113r1 binpoly h 2 gx 0x009d73616f35f4ab1407d73562c10f gy 0x00a52830277958ee84d1315ed31886 - curve sect113r2 binpoly p 0x20000000000000000000000000201 a 0x00689918dbec7e5a0dd6dfc0aa55c7 @@ -165,7 +157,6 @@ curve sect131r1 binpoly h 2 gx 0x0081baf91fdf9833c40f9c181343638399 gy 0x078c6e7ea38c001f73c8134b1b4ef9e150 - curve sect131r2 binpoly p 0x80000000000000000000000000000010d a 0x03e5a88919d7cafcbf415f07c2176573b2 @@ -183,7 +174,6 @@ curve sect163k1 binpoly h 2 gx 0x02fe13c0537bbc11acaa07d793de4e6d5e5c94eee8 gy 0x0289070fb05d38ff58321f2e800536d538ccdaa3d9 - curve sect163r1 binpoly p 0x800000000000000000000000000000000000000c9 a 0x07b6882caaefa84f9554ff8428bd88e246d2782ae2 @@ -192,7 +182,6 @@ curve sect163r1 binpoly h 2 gx 0x0369979697ab43897789566789567f787a7876a654 gy 0x00435edb42efafb2989d51fefce3c80988f41ff883 - curve sect163r2 binpoly p 0x800000000000000000000000000000000000000c9 a 1 @@ -210,7 +199,6 @@ curve sect193r1 binpoly h 2 gx 0x01f481bc5f0ff84a74ad6cdf6fdef4bf6179625372d8c0c5e1 gy 0x0025e399f2903712ccf3ea9e3a1ad17fb0b3201b6af7ce1b05 - curve sect193r2 binpoly p 0x2000000000000000000000000000000000000000000008001 a 0x0163f35a5137c2ce3ea6ed8667190b0bc43ecd69977702709b @@ -228,7 +216,6 @@ curve sect233k1 binpoly h 4 gx 0x017232ba853a7e731af129f22ff4149563a419c26bf50a4c9d6eefad6126 gy 0x01db537dece819b7f70f555a67c427a8cd9bf18aeb9b56e0c11056fae6a3 - curve sect233r1 binpoly p 0x20000000000000000000000000000000000000004000000000000000001 a 1 @@ -273,7 +260,6 @@ curve sect409k1 binpoly h 4 gx 0x0060f05f658f49c1ad3ab1890f7184210efd0987e307c84c27accfb8f9f67cc2c460189eb5aaaa62ee222eb1b35540cfe9023746 gy 0x01e369050b7c4e42acba1dacbf04299c3460782f918ea427e6325165e9ea10e3da5f6c42e9c55215aa9ca27a5863ec48d8e0286b - curve sect409r1 binpoly p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 a 1 @@ -291,7 +277,6 @@ curve sect571k1 binpoly h 4 gx 0x026eb7a859923fbc82189631f8103fe4ac9ca2970012d5d46024804801841ca44370958493b205e647da304db4ceb08cbbd1ba39494776fb988b47174dca88c7e2945283a01c8972 gy 0x0349dc807f4fbf374f4aeade3bca95314dd58cec9f307a54ffc61efc006d8a2c9d4979c0ac44aea74fbebbb9f772aedcb620b01a7ba7af1b320430c8591984f601cd4c143ef1c7a3 - curve sect571r1 binpoly p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425 a 1 @@ -301,6 +286,121 @@ curve sect571r1 binpoly gx 0x0303001d34b856296c16c0d40d3cd7750a93d1d2955fa80aa5f40fc8db7b2abdbde53950f4c0d293cdd711a35b67fb1499ae60038614f1394abfa3b4c850d927e1e7769c8eec2d19 gy 0x037bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b +#----- Curves from ANSI X9.62 ----------------------------------------------- + +curve ansi-b163-1 binpoly + p 0x080000000000000000000000000000000000000107 + a 0x072546b5435234a422e0789675f432c89435de5242 + b 0x00c9517d06d5240d3cff38c74b20b6cd4d6f9dd4d9 + r 0x0400000000000000000001e60fc8821cc74daeafc1 + h 2 + gx 0x07af69989546103d79329fcc3d74880f33bbe803cb + gy 0x01ec23211b5966adea1d3f87f7ea5848aef0b7ca9f +curve ansi-b163-2 binpoly + p 0x080000000000000000000000000000000000000107 + a 0x0108b39e77c4b108bed981ed0e890e117c511cf072 + b 0x0667aceb38af4e488c407433ffae4f1c811638df20 + r 0x03fffffffffffffffffffdf64de1151adbb78f10a7 + h 2 + gx 0x0024266e4eb5106d0a964d92c4860e2671db9b6cc5 + gy 0x079f684ddf6684c5cd258b3890021b2386dfd19fc5 +curve ansi-b163-3 binpoly + p 0x080000000000000000000000000000000000000107 + a 0x07a526c63d3e25a256a007699f5447e32ae456b50e + b 0x03f7061798eb99e238fd6f1bf95b48feeb4854252b + r 0x03fffffffffffffffffffe1aee140f110aff961309 + h 2 + gx 0x02f9f87b7c574d0bdecf8a22e6524775f98cdebdcb + gy 0x05b935590c155e17ea48eb3ff3718b893df59a05d0 +# ansi-b176 has an unacceptable cofactor + +curve ansi-b191-1 binpoly + p 0x800000000000000000000000000000000000000000000201 + a 0x2866537b676752636a68f56554e12640276b649ef7526267 + b 0x2e45ef571f00786f67b0081b9495a3d95462f5de0aa185ec + r 0x40000000000000000000000004a20e90c39067c893bbb9a5 + h 2 + gx 0x36b3daf8a23206f9c4f299d7b21a9c369137f2c84ae1aa0d + gy 0x765be73433b3f95e332932e70ea245ca2418ea0ef98018fb +curve ansi-b191-2 binpoly + p 0x800000000000000000000000000000000000000000000201 + a 0x401028774d7777c7b7666d1366ea432071274f89ff01e718 + b 0x0620048d28bcbd03b6249c99182b7c8cd19700c362c46a01 + r 0x20000000000000000000000050508cb89f652824e06b8173 + h 4 + gx 0x3809b2b7cc1b28cc5a87926aad83fd28789e81e2c9e3bf10 + gy 0x17434386626d14f3dbf01760d9213a3e1cf37aec437d668a +# ansi-b191-3 has an unacceptable cofactor +# ansi-b191n-{1,2} don't include conversion factors + +# ansi-b208 has an unacceptable cofactor; and 208 isn't prime anyway + +curve ansi-b239-1 binpoly + p 0x800000000000000000000000000000000000000000000000001000000001 + a 0x32010857077c5431123a46b808906756f543423e8d27877578125778ac76 + b 0x790408f2eedaf392b012edefb3392f30f4327c0ca3f31fc383c422aa8c16 + r 0x2000000000000000000000000000000f4d42ffe1492a4993f1cad666e447 + h 4 + gx 0x57927098fa932e7c0a96d3fd5b706ef7e5f5c156e16b7e7c86038552e91d + gy 0x61d8ee5077c33fecf6f1a16b268de469c3c7744ea9a971649fc7a9616305 +# ansi-b239-{2,3} have unacceptable cofactors +# ansi-b239n-{1,2} don't include conversion factors + +# ansi-b272-1 has an unacceptable cofactor; and 272 isn't prime anyway + +# ansi-b304-1 has an unacceptable cofactor; and 304 isn't prime anyway + +# ansi-b359-1 has an unacceptable cofactor + +# ansi-b368-1 has an unacceptable cofactor; and 368 isn't prime anyway + +# ansi-b431-1 has an unacceptable cofactor + +alias ansi-p192-1 secp192r1 +curve ansi-p192-2 niceprime + p 0xfffffffffffffffffffffffffffffffeffffffffffffffff + a 0xfffffffffffffffffffffffffffffffefffffffffffffffc + b 0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953 + r 0xfffffffffffffffffffffffe5fb1a724dc80418648d8dd31 + h 1 + gx 0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a + gy 0x6574d11d69b6ec7a672bb82a083df2f2b0847de970b2de15 +curve ansi-p192-3 niceprime + p 0xfffffffffffffffffffffffffffffffeffffffffffffffff + a 0xfffffffffffffffffffffffffffffffefffffffffffffffc + b 0x22123dc2395a05caa7423daeccc94760a7d462256bd56916 + r 0xffffffffffffffffffffffff7a62d031c83f4294f640ec13 + h 1 + gx 0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896 + gy 0x38a90f22637337334b49dcb66a6dc8f9978aca7648a943b0 + +curve ansi-p239-1 niceprime + p 0x7fffffffffffffffffffffff7fffffffffff8000000000007fffffffffff + a 0x7fffffffffffffffffffffff7fffffffffff8000000000007ffffffffffc + b 0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a + r 0x7fffffffffffffffffffffff7fffff9e5e9a9f5d9071fbd1522688909d0b + h 1 + gx 0x0ffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf + gy 0x7debe8e4e90a5dae6e4054ca530ba04654b36818ce226b39fccb7b02f1ae +curve ansi-p239-2 niceprime + p 0x7fffffffffffffffffffffff7fffffffffff8000000000007fffffffffff + a 0x7fffffffffffffffffffffff7fffffffffff8000000000007ffffffffffc + b 0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c + r 0x7fffffffffffffffffffffff800000cfa7e8594377d414c03821bc582063 + h 1 + gx 0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7 + gy 0x5b0125e4dbea0ec7206da0fc01d9b081329fb555de6ef460237dff8be4ba +curve ansi-p239-3 niceprime + p 0x7fffffffffffffffffffffff7fffffffffff8000000000007fffffffffff + a 0x7fffffffffffffffffffffff7fffffffffff8000000000007ffffffffffc + b 0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e + r 0x7fffffffffffffffffffffff7fffff975deb41b3a6057c3c432146526551 + h 1 + gx 0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a + gy 0x1607e6898f390c06bc1d552bad226f3b6fcfe48b6e818499af18e3ed6cf3 + +alias ansi-p256-1 secp256r1 + #----- Curves from RFC2414 (Oakley) ----------------------------------------- # # oakley155 has too large a cofactor diff --git a/utils/README b/utils/README new file mode 100644 index 0000000..b30a370 --- /dev/null +++ b/utils/README @@ -0,0 +1,29 @@ +Utilities + + This directory contains various random poorly-documented tools + which are useful to maintainers of the software. + + Don't put this stuff in the distribution until it's much better. + +ecptdecompress.c + Compile (using qcc) to ecptd. Run + ecptd CURVE R H G + where CURVE is a curve-spec, R and H are the curve's order and + cofactor, and G is the common point in standard point + representation, hybrid, compressed or uncomressed. It either + prints an error indicating that the curve or point was bad, or a + chunk to be inserted into ectab.in. + +ecentry-prettify.pl + Run + ecentry-prettify.pl NAME FIELD-TYPE + and enter P, A, B, R, H and G by pasting from some appropriate + standard, terminating each one by a `.' on its own line. + Spacing and punctuation in each is stripped. and ecptdecompress + is run to format the whole thing into a nice ectab.in chunk. + + +Local variables: +mode: text +End: + diff --git a/utils/ecentry-prettify.pl b/utils/ecentry-prettify.pl new file mode 100644 index 0000000..3b72053 --- /dev/null +++ b/utils/ecentry-prettify.pl @@ -0,0 +1,34 @@ +#! /usr/bin/perl + +sub gather { + my ($what) = @_; + print "$what?\n"; + my $x = ""; + while (<>) { + chomp; + last if $_ eq "."; + $x .= $_; + } + $x =~ s/\s+//g; + $x =~ s/[.,]//g; + return lc($x); +} + +my %CTYPE = ("niceprime" => "primeproj", + "prime" => "primeproj", + "binpoly" => "binproj", + "binnorm" => "binproj"); + +my $name = shift; +my $kind = shift; + +my $p = gather("p"); +my $a = gather("a"); +my $b = gather("b"); +my $r = gather("r"); +my $h = gather("h"); +my $g = gather("g"); + +print "curve $name $kind\n"; +$p = "0x".$p if $kind =~ /bin/; +system "./ecptd", "$kind $p $CTYPE{$kind} 0x$a 0x$b", "0x$r", $h, $g; diff --git a/utils/ecptdecompress.c b/utils/ecptdecompress.c new file mode 100644 index 0000000..dcfdcbd --- /dev/null +++ b/utils/ecptdecompress.c @@ -0,0 +1,137 @@ +#include +#include +#include + +#include +#include +#include + +#include "ec.h" +#include "mp.h" +#include "rand.h" + +static void puthex(const char *name, mp *x, size_t n) +{ + dstr d = DSTR_INIT; + hex_ctx hc; + char *p; + + if (!n) n = mp_octets(x); + p = xmalloc(n); + hex_init(&hc); + hc.indent = ""; + hc.maxline = 0; + mp_storeb(x, p, n); + hex_encode(&hc, p, n, &d); + hex_encode(&hc, 0, 0, &d); + printf(" %s 0x", name); + dstr_write(&d, stdout); + putchar('\n'); + dstr_destroy(&d); + xfree(p); +} + +int main(int argc, char *argv[]) +{ + ec_curve *c; + ec_info ei; + ec pt = EC_INIT; + qd_parse qd; + hex_ctx hc; + dstr d = DSTR_INIT; + size_t n; + octet *p; + mp *x, *y = 0, *yy = 0; + const char *err; + + qd.p = argv[1]; + qd.e = 0; + if ((c = ec_curveparse(&qd)) == 0 || !qd_eofp(&qd)) { + fprintf(stderr, "bad curve: %s\n", qd.e); + exit(1); + } + n = c->f->noctets; + + ei.c = c; + ei.r = mp_readstring(MP_NEW, argv[2], 0, 0); + ei.h = mp_readstring(MP_NEW, argv[3], 0, 0); + + EC_CREATE(&ei.g); + hex_init(&hc); + hex_decode(&hc, argv[4], strlen(argv[4]), &d); + hex_decode(&hc, 0, 0, &d); + p = (octet *)d.buf; + if (p[0] == 0) { + EC_SETINF(&ei.g); + } else { + if (d.len < n + 1) { + fprintf(stderr, "missing x\n"); + exit(1); + } + x = mp_loadb(MP_NEW, p + 1, n); + if (p[0] & 0x04) { + if (d.len < 2 * n + 1) { + fprintf(stderr, "missing y\n"); + exit(1); + } + y = mp_loadb(MP_NEW, p + n + 1, n); + } + if (p[0] & 0x02) { + if (!EC_FIND(c, &pt, x)) { + fprintf(stderr, "no matching y\n"); + exit(1); + } + yy = MP_COPY(pt.y); + ec_destroy(&pt); + switch (F_TYPE(c->f)) { + case FTY_PRIME: + if (!MP_ISODD(yy) != !(p[0] & 1)) + yy = mp_sub(yy, c->f->m, yy); + break; + case FTY_BINARY: + if (MP_ISZERO(x)) + yy = F_SQRT(c->f, MP_NEW, c->b); + else { + mp *xx = F_SQR(c->f, MP_NEW, x); + mp *b = F_MUL(c->f, MP_NEW, xx, c->a); + mp *xxx = F_MUL(c->f, MP_NEW, xx, x); + b = F_ADD(c->f, b, b, xxx); + b = F_ADD(c->f, b, b, c->b); + xx = F_INV(c->f, xx, xx); + b = F_MUL(c->f, b, b, xx); + mp_drop(xxx); + mp_drop(xx); + yy = F_QUADSOLVE(c->f, MP_NEW, b); + if (!MP_ISODD(yy) != !(p[0] & 1)) + yy = mp_add(yy, yy, MP_ONE); + yy = F_MUL(c->f, yy, yy, x); + } + break; + default: + abort(); + } + } + if (y && yy && !MP_EQ(y, yy)) { + fprintf(stderr, "inconsistent answers\n"); + exit(1); + } + ei.g.x = x; + ei.g.y = mp_copy(y ? y : yy); + mp_drop(y); mp_drop(yy); + } + + if ((err = ec_checkinfo(&ei, &rand_global)) != 0) { + fprintf(stderr, "bad curve: %s\n", err); + exit(0); + } + puthex("p", ei.c->f->m, 0); + puthex("a", ei.c->a, c->f->noctets); + puthex("b", ei.c->b, c->f->noctets); + puthex("r", ei.r, c->f->noctets); + printf(" h "); mp_writefile(ei.h, stdout, 10); putchar('\n'); + puthex("gx", ei.g.x, c->f->noctets); + puthex("gy", ei.g.y, c->f->noctets); + ec_freeinfo(&ei); + dstr_destroy(&d); + return (0); +} diff --git a/ectab-canonify.pl b/utils/ectab-canonify.pl similarity index 100% rename from ectab-canonify.pl rename to utils/ectab-canonify.pl