chiark - git - mdw - catacomb/blob - base/keysz-conv.c

   1 /* -*-c-*-
   2  *
   3  * Key length conversions
   4  *
   5  * (c) 2007 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <math.h>
  31
  32 #include "keysz.h"
  33
  34 /*----- Main code ---------------------------------------------------------*/
  35
  36 /* --- Primitive conversions --- */
  37
  38 static double fromnfs(double nbits)
  39 {
  40   /* --- Magic taken from P1363 --- */
  41 #define LOG2 0.6931471805599453094172321214581765680755
  42 #define MAGIC 8.567936                  /* = 17.135872 / 2 */
  43   double z = log(nbits * LOG2)/LOG2;
  44   return 4.0/3.0 * pow(3 * nbits * z*z, 1.0/3.0) - MAGIC;
  45 }
  46
  47 static double tonfs(double nbits)
  48 {
  49   double hi, lo, mid, val;
  50
  51   /* --- Find upper and lower bounds --- */
  52
  53   for (hi = nbits; fromnfs(hi) < nbits; hi *= 2);
  54   for (lo = nbits; fromnfs(lo) > nbits; lo /= 2);
  55
  56   /* --- Bisect the interval until we get an answer --- */
  57
  58 #define THRESH 0.01
  59   for (;;) {
  60     mid = (hi + lo)/2;
  61     val = fromnfs(mid);
  62     if (fabs(val - nbits) < THRESH)
  63       return (mid);
  64     else if (val < nbits)
  65       lo = mid;
  66     else
  67       hi = mid;
  68   }
  69 }
  70
  71 static double torho(double nbits) { return 2*nbits; }
  72 static double fromrho(double nbits) { return nbits/2; }
  73
  74 /* --- @keysz_fromdl@, @_fromschnorr@, @_fromif@, @_fromec@ --- *
  75  *
  76  * Arguments:   @double nbits@ = key size
  77  *
  78  * Returns:     Equivalent symmetric key size.
  79  *
  80  * Use:         Converts key lengths of various kinds of reference problems
  81  *              to (roughly) equivalent symmetric key sizes.
  82  *
  83  *                * Given the bit length of %$p$%, @keysz_fromdl@ returns a
  84  *                  key size representing the difficulty of computing
  85  *                  discrete logarithms in %$\gf{p}$%, for %$p$% prime or a
  86  *                  small power of a prime.
  87  *
  88  *                * Given the bit length of %$r$%, @keysz_fromschnorr@
  89  *                  returns a key size representing the difficulty of
  90  *                  computing discrete logarithms in a subgroup of %$\gf{q}$%
  91  *                  of order %$r$%.
  92  *
  93  *                * Given the bit length of %$n$%, @keysz_fromif@ returns a
  94  *                  key size representing the difficulty of factoring a
  95  *                  `hard' number %$n = p q$%, where %$p$% and %$q$% are
  96  *                  primes of (near enough) the same length.
  97  *
  98  *                * Given the bit length of %$r$%, @keysz_fromec@ returns a
  99  *                  key size representing the difficulty of computing
 100  *                  discrete logarithms in a subgroup of order-%$r$% of an
 101  *                  elliptic curve over a finite field.
 102  *
 103  *              These functions take and return @double@ rather than an
 104  *              integer type in order to preserve precision between
 105  *              conversions.
 106  */
 107
 108 #define CONVERSIONS(_)                                                  \
 109   _(dl, nfs)                                                            \
 110   _(schnorr, rho)                                                       \
 111   _(if, nfs)                                                            \
 112   _(ec, rho)
 113
 114 #define DEFINE_FROM(what, how)                                          \
 115   double keysz_from##what(double nbits) { return from##how(nbits); }
 116
 117 CONVERSIONS(DEFINE_FROM)
 118
 119 /* --- @keysz_todl@, @_toschnorr@, @_toif@, @_toec@ --- *
 120  *
 121  * Arguments:   @unsigned long nbits@ = symmetric key size
 122  *
 123  * Returns:     Equivalent key size.
 124  *
 125  * Use:         Converts symmetric key sizes to (roughly) equivalent key
 126  *              sizes for various kinds of reference problems.  These are the
 127  *              approximate inverses of the functions above.
 128  */
 129
 130 #define DEFINE_TO(what, how)                                            \
 131   double keysz_to##what(double nbits) { return to##how(nbits); }
 132
 133 CONVERSIONS(DEFINE_TO)
 134
 135 /*----- Interactive mode for testing --------------------------------------*/
 136
 137 #ifdef TEST_RIG
 138
 139 #include <stdio.h>
 140 #include <stdlib.h>
 141 #include <string.h>
 142
 143 static const struct entry {
 144   const char *name;
 145   double (*func)(double);
 146 } tab[] = {
 147 #define ENTRY_FROM(what, how) { "from" #what, keysz_from##what },
 148 #define ENTRY_TO(what, how) { "to" #what, keysz_to##what },
 149   CONVERSIONS(ENTRY_FROM)
 150   CONVERSIONS(ENTRY_TO)
 151   { 0 }
 152 };
 153
 154 int main(int argc, char *argv[])
 155 {
 156   const struct entry *e;
 157   double d;
 158
 159   if (!argv[1]) {
 160     fprintf(stderr, "conversions:");
 161     for (e = tab; e->name; e++) fprintf(stderr, " %s", e->name);
 162     putc('\n', stderr);
 163     return (1);
 164   }
 165   for (e = tab; e->name && strcmp(e->name, argv[1]); e++);
 166   if (!e) {
 167     fprintf(stderr, "unknown conversion `%s'\n", argv[1]);
 168     return (1);
 169   }
 170   for (argv += 2; *argv; argv++) {
 171     d = strtod(*argv, 0);
 172     printf("%s(%g) = %g\n", e->name, d, e->func(d));
 173   }
 174   return (0);
 175 }
 176
 177 #endif
 178
 179 /*----- That's all, folks -------------------------------------------------*/