mpint.c (touint): Compare unsigned with unsigned, not unsigned long.

[u/mdw/catacomb] / keysz-conv.c

/* -*-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 -------------------------------------------------*/