From 518452dea7d3ef127aa6ea3bb7971154994e6977 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Mon, 19 Feb 2007 13:09:58 +0000 Subject: [PATCH] keysz-conv: Conversions between different kinds of key types. It's useful to be able to convert between, say, a DL key length and an EC key length. The functions are here; they'll probably want to be fiddled with as time goes on and the relationships change. --- Makefile.m4 | 2 +- keysz-conv.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ keysz.h | 57 +++++++++++++++++++ 3 files changed, 237 insertions(+), 1 deletion(-) create mode 100644 keysz-conv.c diff --git a/Makefile.m4 b/Makefile.m4 index fccb60d..d593d8c 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -230,7 +230,7 @@ define(`PGEN_SOURCES', primetab.c share.c') libcatacomb_la_SOURCES = \ - grand.c keysz.c \ + grand.c keysz.c keysz-conv.c \ lcrand.c fibrand.c rc4.c seal.c rand.c noise.c fipstest.c maurer.c \ arena.c \ passphrase.c pixie-common.c lmem.c \ diff --git a/keysz-conv.c b/keysz-conv.c new file mode 100644 index 0000000..2d40558 --- /dev/null +++ b/keysz-conv.c @@ -0,0 +1,179 @@ +/* -*-c-*- + * + * Key length conversions + * + * (c) 2007 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include "keysz.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- Primitive conversions --- */ + +static double fromnfs(double nbits) +{ + /* --- Magic taken from P1363 --- */ +#define LOG2 0.6931471805599453094172321214581765680755 +#define MAGIC 8.567936 /* = 17.135872 / 2 */ + double z = log(nbits * LOG2)/LOG2; + return 4.0/3.0 * pow(3 * nbits * z*z, 1.0/3.0) - MAGIC; +} + +static double tonfs(double nbits) +{ + double hi, lo, mid, val; + + /* --- Find upper and lower bounds --- */ + + for (hi = nbits; fromnfs(hi) < nbits; hi *= 2); + for (lo = nbits; fromnfs(lo) > nbits; lo /= 2); + + /* --- Bisect the interval until we get an answer --- */ + +#define THRESH 0.01 + for (;;) { + mid = (hi + lo)/2; + val = fromnfs(mid); + if (fabs(val - nbits) < THRESH) + return (mid); + else if (val < nbits) + lo = mid; + else + hi = mid; + } +} + +static double torho(double nbits) { return 2*nbits; } +static double fromrho(double nbits) { return nbits/2; } + +/* --- @keysz_fromdl@, @_fromschnorr@, @_fromif@, @_fromec@ --- * + * + * Arguments: @double nbits@ = key size + * + * Returns: Equivalent symmetric key size. + * + * Use: Converts key lengths of various kinds of reference problems + * to (roughly) equivalent symmetric key sizes. + * + * * Given the bit length of %$p$%, @keysz_fromdl@ returns a + * key size representing the difficulty of computing + * discrete logarithms in %$\gf{p}$%, for %$p$% prime or a + * small power of a prime. + * + * * Given the bit length of %$r$%, @keysz_fromschnorr@ + * returns a key size representing the difficulty of + * computing discrete logarithms in a subgroup of %$\gf{q}$% + * of order %$r$%. + * + * * Given the bit length of %$n$%, @keysz_fromif@ returns a + * key size representing the difficulty of factoring a + * `hard' number %$n = p q$%, where %$p$% and %$q$% are + * primes of (near enough) the same length. + * + * * Given the bit length of %$r$%, @keysz_fromec@ returns a + * key size representing the difficulty of computing + * discrete logarithms in a subgroup of order-%$r$% of an + * elliptic curve over a finite field. + * + * These functions take and return @double@ rather than an + * integer type in order to preserve precision between + * conversions. + */ + +#define CONVERSIONS(_) \ + _(dl, nfs) \ + _(schnorr, rho) \ + _(if, nfs) \ + _(ec, rho) + +#define DEFINE_FROM(what, how) \ + double keysz_from##what(double nbits) { return from##how(nbits); } + +CONVERSIONS(DEFINE_FROM) + +/* --- @keysz_todl@, @_toschnorr@, @_toif@, @_toec@ --- * + * + * Arguments: @unsigned long nbits@ = symmetric key size + * + * Returns: Equivalent key size. + * + * Use: Converts symmetric key sizes to (roughly) equivalent key + * sizes for various kinds of reference problems. These are the + * approximate inverses of the functions above. + */ + +#define DEFINE_TO(what, how) \ + double keysz_to##what(double nbits) { return to##how(nbits); } + +CONVERSIONS(DEFINE_TO) + +/*----- Interactive mode for testing --------------------------------------*/ + +#ifdef TEST_RIG + +#include +#include +#include + +static const struct entry { + const char *name; + double (*func)(double); +} tab[] = { +#define ENTRY_FROM(what, how) { "from" #what, keysz_from##what }, +#define ENTRY_TO(what, how) { "to" #what, keysz_to##what }, + CONVERSIONS(ENTRY_FROM) + CONVERSIONS(ENTRY_TO) + { 0 } +}; + +int main(int argc, char *argv[]) +{ + const struct entry *e; + double d; + + if (!argv[1]) { + fprintf(stderr, "conversions:"); + for (e = tab; e->name; e++) fprintf(stderr, " %s", e->name); + putc('\n', stderr); + return (1); + } + for (e = tab; e->name && strcmp(e->name, argv[1]); e++); + if (!e) { + fprintf(stderr, "unknown conversion `%s'\n", argv[1]); + return (1); + } + for (argv += 2; *argv; argv++) { + d = strtod(*argv, 0); + printf("%s(%g) = %g\n", e->name, d, e->func(d)); + } + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/keysz.h b/keysz.h index 5a49740..97ed144 100644 --- a/keysz.h +++ b/keysz.h @@ -85,6 +85,63 @@ extern size_t keysz(size_t /*sz*/, const octet */*ksz*/); #define KSZ_ASSERT(pre, sz) \ assert(((void)"Bad key size for " #pre, KSZ_CHECK(pre, sz))) +/*----- Key size conversions ----------------------------------------------*/ + +/* --- @keysz_fromdl@, @_fromschnorr@, @_fromif@, @_fromec@ --- * + * + * Arguments: @double nbits@ = key size + * + * Returns: Equivalent symmetric key size. + * + * Use: Converts key lengths of various kinds of reference problems + * to (roughly) equivalent symmetric key sizes. + * + * * Given the bit length of %$p$%, @keysz_fromdl@ returns a + * key size representing the difficulty of computing + * discrete logarithms in %$\gf{p}$%, for %$p$% prime or a + * small power of a prime. + * + * * Given the bit length of %$r$%, @keysz_fromschnorr@ + * returns a key size representing the difficulty of + * computing discrete logarithms in a subgroup of %$\gf{q}$% + * of order %$r$%. + * + * * Given the bit length of %$n$%, @keysz_fromif@ returns a + * key size representing the difficulty of factoring a + * `hard' number %$n = p q$%, where %$p$% and %$q$% are + * primes of (near enough) the same length. + * + * * Given the bit length of %$r$%, @keysz_fromec@ returns a + * key size representing the difficulty of computing + * discrete logarithms in a subgroup of order-%$r$% of an + * elliptic curve over a finite field. + * + * These functions take and return @double@ rather than an + * integer type in order to preserve precision between + * conversions. + */ + +extern double keysz_fromdl(double /*nbits*/); +extern double keysz_fromschnorr(double /*nbits*/); +extern double keysz_fromif(double /*nbits*/); +extern double keysz_fromec(double /*nbits*/); + +/* --- @keysz_todl@, @_toschnorr@, @_toif@, @_toec@ --- * + * + * Arguments: @unsigned long nbits@ = symmetric key size + * + * Returns: Equivalent key size. + * + * Use: Converts symmetric key sizes to (roughly) equivalent key + * sizes for various kinds of reference problems. These are the + * approximate inverses of the functions above. + */ + +extern double keysz_todl(double /*nbits*/); +extern double keysz_toschnorr(double /*nbits*/); +extern double keysz_toif(double /*nbits*/); +extern double keysz_toec(double /*nbits*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus -- 2.11.0