From fb8db84dbea9dfe0f945f88730aed56ebba1dbd7 Mon Sep 17 00:00:00 2001 From: mdw Date: Sun, 17 Oct 2004 13:29:00 +0000 Subject: [PATCH] Fix up ectab.in a little more. Fix group test vectors broken by new composite-degree check. Abortive attempt at determining conversions for non-optimal Gaussian normal bases -- may as well check in anyway. --- ectab.in | 13 ++++++------ tests/group | 34 +++++++++++++++---------------- utils/fnb.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++++-------- 3 files changed, 83 insertions(+), 32 deletions(-) diff --git a/ectab.in b/ectab.in index de594e1..7520b03 100644 --- a/ectab.in +++ b/ectab.in @@ -286,6 +286,9 @@ curve sect571r1 binpoly gy 0x037bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b #----- Curves from ANSI X9.62 ----------------------------------------------- +# +# The conversion factors for the normal basis representations were generated +# because none were given in the document. curve ansi-c2pnb163v1 binpoly p 0x080000000000000000000000000000000000000107 @@ -457,7 +460,9 @@ alias ansip521r1 secp521r1 #----- NIST curves from FIPS186-2 ------------------------------------------- # -# Most of these are duplicates of SEC2 curves. +# These are duplicates of SEC2 curves. However, the normal basis +# representations aren't in SEC, so we give them here. (Conversion factors +# from FIPS186-2. alias nist-p192 secp192r1 alias nist-p224 secp224r1 @@ -486,7 +491,6 @@ curve nist-k163n binnorm h 2 gx 0x05679b353caa46825fea2d3713ba450da0c2a4541 gy 0x235b7c6710050689906bac3d9dec76a835591edb2 - curve nist-b163n binnorm p 0x800000000000000000000000000000000000000c9 beta 0x715169c109c612e390d347c748342bcd3b02a0bef @@ -506,7 +510,6 @@ curve nist-k233n binnorm h 4 gx 0x0fde76d9dcd26e643ac26f1aa901aa129784b71fc0722b2d05614d650b3 gy 0x0643e317633155c9e0447ba8020a3c43177450ee036d633501434cac978 - curve nist-b233n binnorm p 0x20000000000000000000000000000000000000004000000000000000001 beta 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9 @@ -526,7 +529,6 @@ curve nist-k283n binnorm h 4 gx 0x3ab9593f8db09fc188f1d7c4ac9fcc3e57fcd3bdb15024b212c70229de5fcd92eb0ea60 gy 0x2118c4755e7345cd8f603ef93b98b106fe8854ffeb9a3b304634cc83a0e759f0c2686b1 - curve nist-b283n binnorm p 0x800000000000000000000000000000000000000000000000000000000000000000010a1 beta 0x31e0ed791c3282dc5624a720818049d053e8c7ab8663792bc1d792eba9867fc7b317a99 @@ -546,7 +548,6 @@ curve nist-k409n binnorm h 4 gx 0x1b559c7cba2422e3affe13343e808b55e012d726ca0b7e6a63aeafbc1e3a98e10ca0fcf98350c3b7f89a9754a8e1dc0713cec4a gy 0x16d8c42052f07e7713e7490eff318ba1abd6fef8a5433c894b24f5c817aeb79852496fbee803a47bc8a203878ebf1c499afd7d6 - curve nist-b409n binnorm p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 beta 0x0dfa06be206aa97b7a41fffb9b0c55f8f048062fbe8381b4248adf92912ccc8e3f91a24e1cfb3950532b988971c23042e85708d @@ -566,13 +567,11 @@ curve nist-k571n binnorm h 4 gx 0x04bb2dba418d0db107adae003427e5d7cc139acb465e5934f0bea2ab2f3622bc29b3d5b9aa7a1fdfd5d8be66057c1008e71e484bcd98f22bf8476423767367429ef2ec5bc3ebcf7 gy 0x44cbb57de20788d2c952d7b56cf39bd3e89b18984bd124e751ceff4369dd8dac6a59e6e745df44d8220ce22aa2c852cfcbbef49ebaa98bd2483e33180e04286feaa253050caff60 - curve nist-b571n binnorm p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425 beta 0x452186bbf5840a0bcf8c9f02a54efa04e813b43c3d4149606c4d27b487bf107393c8907f79d9778beb35ee87467d3288274caebda6ce05aeb4ca5cf3c3044bd4372232f2c1a27c4 a 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff b 0x3762d0d47116006179da35688eeaccf591a5cdea75000118d9608c59132d43426101a1dfb3774115f586623f75f00001ce611983c1275fa31f5bc9f4be1a0f467f01ca885c74777 - r 0x03ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe661ce18ff55987308059b186823851ec7dd9ca1161de93d5174d66e8382e9bb2fe84e47 h 2 gx 0x0735e035def5925cc33173eb2a8ce7767522b466d278b650a2916127dfea9d2d361089f0a7a0247a184e1c70d417866e0fe0feb0ff8f2f3f9176418f97d117e624e2015df1662a8 diff --git a/tests/group b/tests/group index 0c2035a..e7ff8e8 100644 --- a/tests/group +++ b/tests/group @@ -1,4 +1,4 @@ -# $Id: group,v 1.2 2004/04/04 19:04:11 mdw Exp $ +# $Id$ # # Test group abstraction, and a bunch of other things. @@ -38,7 +38,7 @@ check { 0xaa089ae4666a422e714651ad9372213fa65a93, 0x12d29c630dda76010397809a6816be6d2ffa815 0xaaaaaaaaaaaaaaaaaab1fcf1e206f421a3ea1b * 12 - }" "cofactor out of range"; + }" "degree not prime"; } @@ -253,10 +253,10 @@ fromec { } tobuf { - "prime { 29, 7, 16}" 22 -1 "00"; - "prime { 29, 7, 16}" 22 0 "000116"; - "prime { 29, 7, 16}" 0 -1 "0000"; - "prime { 29, 7, 16}" 0 0 "000100"; + "prime { 29, 7, 16 }" 22 -1 "00"; + "prime { 29, 7, 16 }" 22 0 "000116"; + "prime { 29, 7, 16 }" 0 -1 "0000"; + "prime { 29, 7, 16 }" 0 0 "000100"; "ec { secp112r1 }" inf 0 "0000"; "ec { secp112r1 }" @@ -268,10 +268,10 @@ tobuf { } frombuf { - "prime { 29, 7, 16}" "00" -1 0; - "prime { 29, 7, 16}" "000116" 3 22; - "prime { 29, 7, 16}" "00000e" 2 0; - "prime { 29, 7, 16}" "000100ff" 3 0; + "prime { 29, 7, 16 }" "00" -1 0; + "prime { 29, 7, 16 }" "000116" 3 22; + "prime { 29, 7, 16 }" "00000e" 2 0; + "prime { 29, 7, 16 }" "000100ff" 3 0; "ec { secp112r1 }" "0000" 2 inf; "ec { secp112r1 }" @@ -284,10 +284,10 @@ frombuf { } toraw { - "prime { 29, 7, 16}" 22 -1 ""; - "prime { 29, 7, 16}" 22 0 "16"; - "prime { 29, 7, 16}" 0 -1 ""; - "prime { 29, 7, 16}" 0 0 "00"; + "prime { 29, 7, 16 }" 22 -1 ""; + "prime { 29, 7, 16 }" 22 0 "16"; + "prime { 29, 7, 16 }" 0 -1 ""; + "prime { 29, 7, 16 }" 0 0 "00"; "prime { 4294967311, 364289, 18767 }" 4285559121 0 "00ff707151"; "prime { 4294967311, 364289, 18767 }" 4285559121 -1 "ff707151"; @@ -301,9 +301,9 @@ toraw { } fromraw { - "prime { 29, 7, 16}" "" -1 0; - "prime { 29, 7, 16}" "160bad" 1 22; - "prime { 29, 7, 16}" "00" 1 0; + "prime { 29, 7, 16 }" "" -1 0; + "prime { 29, 7, 16 }" "160bad" 1 22; + "prime { 29, 7, 16 }" "00" 1 0; "prime { 4294967311, 364289, 18767 }" "00ff707151e7c0" 5 4285559121; "prime { 4294967311, 364289, 18767 }" "ff707151" -1 0; diff --git a/utils/fnb.c b/utils/fnb.c index 8b7c1ab..98941c9 100644 --- a/utils/fnb.c +++ b/utils/fnb.c @@ -1,3 +1,4 @@ +#include #include #include @@ -349,19 +350,28 @@ static unsigned gcd(unsigned u, unsigned v) } } +static unsigned order(unsigned x, unsigned p) +{ + unsigned y, k; + + if (!x || x == 1) return (0); + for (y = x, k = 1; y != 1; y = (y*x)%p, k++); + return (k); +} + static int onbtype(unsigned m) { unsigned t; unsigned p, h; - unsigned k, x, d; + unsigned k, d; if (m%8 == 0) return (0); - for (t = 1; t <= 2; t++) { + for (t = 1;; t++) { p = t*m + 1; if (!primep(p)) continue; - for (x = 2, k = 1; x != 1; x = (2*x)%p, k++); + k = order(2, p); h = t*m/k; d = gcd(h, m); if (d == 1) @@ -370,7 +380,9 @@ static int onbtype(unsigned m) return (0); } -static mp *fieldpoly(unsigned m, int t) +#define PI 3.1415926535897932384626433832795028841971693993751 + +static mp *fieldpoly(unsigned m, int t, grand *rr) { mp *p, *q, *r, *z; unsigned i; @@ -393,8 +405,48 @@ static mp *fieldpoly(unsigned m, int t) mp_drop(q); mp_drop(r); break; - default: - abort(); + default: { +#ifdef notdef + unsigned pp = t*m + 1; + unsigned uu; + unsigned j; + struct cplx { double r, i; }; + struct cplx e, n; + struct cplx *f; + + do uu = GR_RANGE(rr, pp); while (order(uu, pp) != t); + f = xmalloc(sizeof(struct cplx) * (m + 1)); + for (i = 0; i <= m; i++) f[i].r = f[i].i = 0; + f[0].r = 1; + printf("poly init; type = %u\n", t); + for (i = m + 1; i--; ) + printf("%3u: %g + %g i\n", i, f[i].r, f[i].i); + putchar('\n'); + for (i = 1; i <= m; i++) { + e.r = e.i = 0; + for (j = 0; j < t; j++) { + double z = (pow(2, i) * pow(uu, j) * PI)/pp; + e.r -= cos(z); e.i -= sin(z); + } + printf("new factor: %g + %g i\n", e.r, e.i); + for (j = i; j--; ) { + f[j + 1].r += f[j].r; + f[j + 1].i += f[j].i; + n.r = f[j].r * e.r - f[j].i * e.i; + n.i = f[j].r * e.i + f[j].i * e.r; + f[j] = n; + } + printf("poly after %u iters\n", i); + for (j = m + 1; j--; ) + printf("%3u: %g + %g i\n", j, f[j].r, f[j].i); + putchar('\n'); + } + xfree(f); + p = MP_ZERO; +#else + abort(); +#endif + } break; } return (p); } @@ -432,10 +484,10 @@ static mp *fnb(mp *p) mp *q, *x; unsigned m = mp_bits(p) - 1; - if ((t = onbtype(m)) == 0) + if ((t = onbtype(m)) == 0 || t > 2) return (0); f = field_binpoly(p); - q = fieldpoly(m, t); + q = fieldpoly(m, t, r); x = poly_solve(f, MP_NEW, q, r); MP_DROP(q); F_DESTROY(f); -- 2.11.0