projects / u / mdw / catacomb / blob
? search:


0e32de641ef8a842f4f99f7e11c532190812462b
[u/mdw/catacomb] / group.h
1 /* -*-c-*-
2 *
3 * $Id: group.h,v 1.3 2004/04/04 19:04:11 mdw Exp $
4 *
5 * General cyclic group abstraction
6 *
7 * (c) 2004 Straylight/Edgeware
8 */
9
10 /*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of Catacomb.
13 *
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
28 */
29
30 /*----- Revision history --------------------------------------------------*
31 *
32 * $Log: group.h,v $
33 * Revision 1.3 2004/04/04 19:04:11 mdw
34 * Raw I/O of elliptic curve points and group elements.
35 *
36 * Revision 1.2 2004/04/03 03:32:05 mdw
37 * General robustification.
38 *
39 * Revision 1.1 2004/04/01 12:50:09 mdw
40 * Add cyclic group abstraction, with test code. Separate off exponentation
41 * functions for better static linking. Fix a buttload of bugs on the way.
42 * Generally ensure that negative exponents do inversion correctly. Add
43 * table of standard prime-field subgroups. (Binary field subgroups are
44 * currently unimplemented but easy to add if anyone ever finds a good one.)
45 *
46 */
47
48 #ifndef CATACOMB_GROUP_H
49 #define CATACOMB_GROUP_H
50
51 #ifdef __cplusplus
52 extern "C" {
53 #endif
54
55 /*----- Header files ------------------------------------------------------*/
56
57 #include <mLib/dstr.h>
58
59 #ifndef CATACOMB_BUF_H
60 # include "buf.h"
61 #endif
62
63 #ifndef CATACOMB_DH_H
64 # include "ec.h"
65 #endif
66
67 #ifndef CATACOMB_GRAND_H
68 # include "grand.h"
69 #endif
70
71 #ifndef CATACOMB_MP_H
72 # include "mp.h"
73 #endif
74
75 #ifndef CATACOMB_QDPARSE_H
76 # include "qdparse.h"
77 #endif
78
79 /*----- Data structures ---------------------------------------------------*/
80
81 #ifndef ge
82 typedef struct ge ge; /* Group element (abstract type) */
83 #endif
84
85 typedef struct group_ {
86 const struct group_ops *ops; /* Operations table */
87 size_t nbits; /* Size of an element in bits */
88 size_t noctets; /* Size of raw element in octets */
89 ge *i; /* Identity element */
90 ge *g; /* Generator element */
91 mp *r; /* Order of the generator */
92 mp *h; /* Cofactor */
93 } group;
94
95 typedef struct group_expfactor {
96 ge *base; /* The base */
97 mp *exp; /* The exponent */
98 } group_expfactor;
99
100 typedef struct group_ops {
101 unsigned ty; /* Type of this group */
102
103 /* --- Memory management --- */
104
105 void (*destroygroup)(group */*g*/);
106 ge *(*create)(group */*g*/);
107 void (*copy)(group */*g*/, ge */*d*/, ge */*x*/);
108 void (*burn)(group */*g*/, ge */*x*/);
109 void (*destroy)(group */*g*/, ge */*e*/);
110
111 /* --- Comparisons --- */
112
113 int (*samep)(group */*g*/, group */*h*/);
114 int (*eq)(group */*g*/, ge */*x*/, ge */*y*/);
115 int (*identp)(group */*g*/, ge */*x*/);
116
117 /* --- Other stuff --- */
118
119 const char *(*check)(group */*g*/, grand */*gr*/);
120
121 /* --- Arithmetic --- */
122
123 void (*mul)(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
124 void (*sqr)(group */*g*/, ge */*d*/, ge */*x*/);
125 void (*inv)(group */*g*/, ge */*d*/, ge */*x*/);
126 void (*div)(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
127 void (*exp)(group */*g*/, ge */*d*/, ge */*x*/, mp */*n*/);
128 void (*mexp)(group */*g*/, ge */*d*/,
129 const group_expfactor */*f*/, size_t /*n*/);
130
131 /* --- Debugging --- */
132
133 int (*read)(group */*g*/, ge */*d*/,
134 const mptext_ops */*ops*/, void */*p*/);
135 int (*write)(group */*g*/, ge */*x*/,
136 const mptext_ops */*ops*/, void */*p*/);
137
138 /* --- Conversions --- */
139
140 mp *(*toint)(group */*g*/, mp */*d*/, ge */*x*/);
141 int (*fromint)(group */*g*/, ge */*d*/, mp */*x*/);
142 int (*toec)(group */*g*/, ec */*d*/, ge */*x*/);
143 int (*fromec)(group */*g*/, ge */*d*/, ec */*p*/);
144 int (*tobuf)(group */*h*/, buf */*b*/, ge */*x*/);
145 int (*frombuf)(group */*h*/, buf */*b*/, ge */*d*/);
146 int (*toraw)(group */*h*/, buf */*b*/, ge */*x*/);
147 int (*fromraw)(group */*h*/, buf */*b*/, ge */*d*/);
148
149 } group_ops;
150
151 enum {
152 GTY_PRIME, /* Prime field subgroup */
153 GTY_BINARY, /* Binary feld subgroup */
154 GTY_EC /* Elliptic curve group */
155 };
156
157 #define G_DESTROYGROUP(g) (g)->ops->destroygroup((g))
158 #define G_CREATE(g) (g)->ops->create((g))
159 #define G_COPY(g, d, x) (g)->ops->copy((g), (d), (x))
160 #define G_BURN(g, x) (g)->ops->burn((g), (x))
161 #define G_DESTROY(g, x) (g)->ops->destroy((g), (x))
162
163 #define G_SAMEP(g, h) (g)->ops->samep((g), (h))
164 #define G_EQ(g, x, y) (g)->ops->eq((g), (x), (y))
165 #define G_IDENTP(g, x) (g)->ops->identp((g), (x))
166
167 #define G_CHECK(g, gr) (g)->ops->check((g), (gr))
168
169 #define G_MUL(g, d, x, y) (g)->ops->mul((g), (d), (x), (y))
170 #define G_SQR(g, d, x) (g)->ops->sqr((g), (d), (x))
171 #define G_INV(g, d, x) (g)->ops->inv((g), (d), (x))
172 #define G_DIV(g, d, x, y) (g)->ops->div((g), (d), (x), (y))
173 #define G_EXP(g, d, x, n) (g)->ops->exp((g), (d), (x), (n))
174 #define G_MEXP(g, d, f, n) (g)->ops->mexp((g), (d), (f), (n))
175
176 #define G_READ(g, d, o, p) (g)->ops->read((g), (d), (o), (p))
177 #define G_WRITE(g, x, o, p) (g)->ops->write((g), (x), (o), (p))
178
179 #define G_TOINT(g, d, x) (g)->ops->toint((g), (d), (x))
180 #define G_FROMINT(g, d, x) (g)->ops->fromint((g), (d), (x))
181 #define G_TOEC(g, d, x) (g)->ops->toec((g), (d), (x))
182 #define G_FROMEC(g, d, p) (g)->ops->fromec((g), (d), (p))
183 #define G_TOBUF(g, b, x) (g)->ops->tobuf((g), (b), (x))
184 #define G_FROMBUF(g, b, d) (g)->ops->frombuf((g), (b), (d))
185 #define G_TORAW(g, b, x) (g)->ops->toraw((g), (b), (x))
186 #define G_FROMRAW(g, b, d) (g)->ops->fromraw((g), (b), (d))
187
188 /*----- Handy functions ---------------------------------------------------*/
189
190 /* --- @group_check@ --- *
191 *
192 * Arguments: @group *g@ = an abstract group
193 * @ge *x@ = a group element
194 *
195 * Returns: Zero on success, nonzero for failure.
196 *
197 * Use: Checks that @x@ is a valid group element. This may take a
198 * while, since it checks that %$x^h \ne 1$%.
199 */
200
201 extern int group_check(group */*g*/, ge */*x*/);
202
203 /* --- @group_samep@ --- *
204 *
205 * Arguments: @group *g, *h@ = two abstract groups
206 *
207 * Returns: Nonzero if the groups are in fact identical (not just
208 * isomorphic).
209 *
210 * Use: Checks to see whether two groups are actually the same. This
211 * function does the full check: the group operatrion @samep@
212 * just does the group-specific details.
213 */
214
215 extern int group_samep(group */*g*/, group */*h*/);
216
217 /*----- Textual I/O on group elements -------------------------------------*/
218
219 extern int group_readstring(group */*g*/, ge */*d*/,
220 const char */*p*/, char **/*end*/);
221 extern int group_writestring(group */*g*/, ge */*d*/,
222 char */*p*/, size_t /*sz*/);
223
224 extern int group_readfile(group */*g*/, ge */*d*/, FILE */*fp*/);
225 extern int group_writefile(group */*g*/, ge */*x*/, FILE */*fp*/);
226
227 extern int group_readdstr(group */*g*/, ge */*d*/,
228 dstr */*dd*/, size_t */*off*/);
229 extern int group_writedstr(group */*g*/, ge */*x*/, dstr */*d*/);
230
231 /*----- Standard implementations ------------------------------------------*/
232
233 /* --- @group_stdidentp@ --- *
234 *
235 * Arguments: @group *g@ = abstract group
236 * @ge *x@ = group element
237 *
238 * Returns: Nonzero if %$x$% is the group identity.
239 */
240
241 extern int group_stdidentp(group */*g*/, ge */*x*/);
242
243 /* --- @group_stdcheck@ --- *
244 *
245 * Arguments: @group *g@ = abstract group
246 * @grand *gr@ = random number source.
247 *
248 * Returns: Null on success, or a pointer to an error message.
249 */
250
251 extern const char *group_stdcheck(group */*g*/, grand */*gr*/);
252
253 /* --- @group_stdsqr@ --- *
254 *
255 * Arguments: @group *g@ = abstract group
256 * @ge *d@ = destination pointer
257 * @ge *x@ = group element
258 *
259 * Returns: ---
260 *
261 * Use: Computes %$d = x^2$% as %$d = x x$%.
262 */
263
264 extern void group_stdsqr(group */*g*/, ge */*d*/, ge */*x*/);
265
266 /* --- @group_stddiv@ --- *
267 *
268 * Arguments: @group *g@ = abstract group
269 * @ge *d@ = destination pointer
270 * @ge *x@ = dividend
271 * @ge *y@ = divisor
272 *
273 * Returns: ---
274 *
275 * Use: Computes %$d = x/y$% as %$d = x y^{-1}$%.
276 */
277
278 extern void group_stddiv(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
279
280 /* --- @group_stdexp@ --- *
281 *
282 * Arguments: @group *g@ = abstract group
283 * @ge *d@ = destination pointer
284 * @ge *x@ = base element
285 * @mp *n@ = exponent
286 *
287 * Returns: ---
288 *
289 * Use: Computes %$d = x^n$% efficiently.
290 */
291
292 extern void group_stdexp(group */*g*/, ge */*d*/, ge */*x*/, mp */*n*/);
293
294 /* --- @group_stdmexp@ --- *
295 *
296 * Arguments: @group *g@ = abstract group
297 * @ge *d@ = destination pointer
298 * @const group_expfactor *f@ = vector of factors
299 * @size_t n@ = number of factors
300 *
301 * Returns: ---
302 *
303 * Use: Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
304 */
305
306 extern void group_stdmexp(group */*g*/, ge */*d*/,
307 const group_expfactor */*f*/, size_t /*n*/);
308
309 /* --- @group_stdtoec@ --- *
310 *
311 * Arguments: @group *g@ = abstract group
312 * @ec *d@ = destination point
313 * @ge *x@ = group element
314 *
315 * Returns: @-1@, indicating failure.
316 *
317 * Use: Fails to convert a group element to an elliptic curve point.
318 */
319
320 extern int group_stdtoec(group */*g*/, ec */*d*/, ge */*x*/);
321
322 /* --- @group_stdfromec@ --- *
323 *
324 * Arguments: @group *g@ = abstract group
325 * @ge *d@ = destination pointer
326 * @ec *p@ = elliptic curve point
327 *
328 * Returns: Zero for success, @-1@ on failure.
329 *
330 * Use: Converts %$p$% to a group element by converting its %$x$%-
331 * coordinate.
332 */
333
334 extern int group_stdfromec(group */*g*/, ge */*d*/, ec */*p*/);
335
336 /*----- Prime field subgroups ---------------------------------------------*/
337
338 typedef struct gprime_param {
339 mp *p, *q; /* Prime numbers %$p$% and %$q$% */
340 mp *g; /* Generates order-%$q$% subgroup */
341 } gprime_param;
342
343 /* --- @group_prime@ --- *
344 *
345 * Arguments: @const gprime_param *gp@ = group parameters
346 *
347 * Returns: A pointer to the group, or null.
348 *
349 * Use: Constructs an abstract group interface for a subgroup of a
350 * prime field. Group elements are @mp *@ pointers.
351 */
352
353 group *group_prime(const gprime_param */*gp*/);
354
355 /*----- Elliptic curve groups ---------------------------------------------*/
356
357 /* --- @group_ec@ --- *
358 *
359 * Arguments: @const ec_info *ei@ = elliptic curve parameters
360 *
361 * Returns: A pointer to the group, or null.
362 *
363 * Use: Constructs an abstract group interface for an elliptic curve
364 * group. Group elements are @ec@ structures. The contents of
365 * the @ec_info@ structure becomes the property of the @group@
366 * object; you can (and should) free the structure itself, but
367 * calling @ec_freeinfo@ on it is not allowed.
368 */
369
370 group *group_ec(const ec_info */*ei*/);
371
372 /*----- General group initialization --------------------------------------*/
373
374 /* --- @group_parse@ --- *
375 *
376 * Arguments: @qd_parse *qd@ = quick-and-dirty parser
377 *
378 * Returns: Group pointer, or null for failure.
379 *
380 * Use: Parses a group description and returns the group. This has
381 * the form `TYPE { SPEC }' where TYPE is `prime' or `ec', and
382 * SPEC is the appropriate kind of group specification of the
383 * given type.
384 */
385
386 extern group *group_parse(qd_parse */*qd*/);
387
388 /* --- @group_fromstring@ --- *
389 *
390 * Arguments: @const char *p@ = pointer to string to read
391 * @group **gg@ = where to put the group pointer
392 *
393 * Returns: Null if OK, or an error string.
394 *
395 * Use: Parses a group spec from a string, and returns the group.
396 */
397
398 extern const char *group_fromstring(const char */*p*/, group **/*gg*/);
399
400 /*----- That's all, folks -------------------------------------------------*/
401
402 #ifdef __cplusplus
403 }
404 #endif
405
406 #endif
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)