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.

diff --git a/Makefile.m4 b/Makefile.m4
index fccb60d..d593d8c 100644 (file)
--- 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 (file)
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 <math.h>
+
+#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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+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 (file)
--- 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