3 * Key length conversions
5 * (c) 2007 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
34 /*----- Main code ---------------------------------------------------------*/
36 /* --- Primitive conversions --- */
38 static double fromnfs(double nbits
)
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
;
47 static double tonfs(double nbits
)
49 double hi
, lo
, mid
, val
;
51 /* --- Find upper and lower bounds --- */
53 for (hi
= nbits
; fromnfs(hi
) < nbits
; hi
*= 2);
54 for (lo
= nbits
; fromnfs(lo
) > nbits
; lo
/= 2);
56 /* --- Bisect the interval until we get an answer --- */
62 if (fabs(val
- nbits
) < THRESH
)
71 static double torho(double nbits
) { return 2*nbits
; }
72 static double fromrho(double nbits
) { return nbits
/2; }
74 /* --- @keysz_fromdl@, @_fromschnorr@, @_fromif@, @_fromec@ --- *
76 * Arguments: @double nbits@ = key size
78 * Returns: Equivalent symmetric key size.
80 * Use: Converts key lengths of various kinds of reference problems
81 * to (roughly) equivalent symmetric key sizes.
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.
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}$%
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.
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.
103 * These functions take and return @double@ rather than an
104 * integer type in order to preserve precision between
108 #define CONVERSIONS(_) \
114 #define DEFINE_FROM(what, how) \
115 double keysz_from##what(double nbits) { return from##how(nbits); }
117 CONVERSIONS(DEFINE_FROM
)
119 /* --- @keysz_todl@, @_toschnorr@, @_toif@, @_toec@ --- *
121 * Arguments: @unsigned long nbits@ = symmetric key size
123 * Returns: Equivalent key size.
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.
130 #define DEFINE_TO(what, how) \
131 double keysz_to##what(double nbits) { return to##how(nbits); }
133 CONVERSIONS(DEFINE_TO
)
135 /*----- Interactive mode for testing --------------------------------------*/
143 static const struct entry
{
145 double (*func
)(double);
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
)
154 int main(int argc
, char *argv
[])
156 const struct entry
*e
;
160 fprintf(stderr
, "conversions:");
161 for (e
= tab
; e
->name
; e
++) fprintf(stderr
, " %s", e
->name
);
165 for (e
= tab
; e
->name
&& strcmp(e
->name
, argv
[1]); e
++);
167 fprintf(stderr
, "unknown conversion `%s'\n", argv
[1]);
170 for (argv
+= 2; *argv
; argv
++) {
171 d
= strtod(*argv
, 0);
172 printf("%s(%g) = %g\n", e
->name
, d
, e
->func(d
));
179 /*----- That's all, folks -------------------------------------------------*/