Commit | Line | Data |
---|---|---|
518452de MW |
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 -------------------------------------------------*/ |