5 * General cyclic group abstraction
7 * (c) 2004 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 #ifndef CATACOMB_GROUP_H
31 #define CATACOMB_GROUP_H
37 /*----- Header files ------------------------------------------------------*/
39 #include <mLib/dstr.h>
41 #ifndef CATACOMB_BUF_H
49 #ifndef CATACOMB_GRAND_H
57 #ifndef CATACOMB_QDPARSE_H
61 /*----- Data structures ---------------------------------------------------*/
64 typedef struct ge ge; /* Group element (abstract type) */
67 typedef struct group_ {
68 const struct group_ops *ops; /* Operations table */
69 size_t nbits; /* Size of an element in bits */
70 size_t noctets; /* Size of raw element in octets */
71 ge *i; /* Identity element */
72 ge *g; /* Generator element */
73 mp *r; /* Order of the generator */
77 typedef struct group_expfactor {
78 ge *base; /* The base */
79 mp *exp; /* The exponent */
82 typedef struct group_ops {
84 /* --- General information --- */
86 unsigned ty; /* Type of this group */
87 const char *name; /* Textual name string */
89 /* --- Memory management --- */
91 void (*destroygroup)(group */*g*/);
92 ge *(*create)(group */*g*/);
93 void (*copy)(group */*g*/, ge */*d*/, ge */*x*/);
94 void (*burn)(group */*g*/, ge */*x*/);
95 void (*destroy)(group */*g*/, ge */*e*/);
97 /* --- Comparisons --- */
99 int (*samep)(group */*g*/, group */*h*/);
100 int (*eq)(group */*g*/, ge */*x*/, ge */*y*/);
101 int (*identp)(group */*g*/, ge */*x*/);
103 /* --- Other stuff --- */
105 const char *(*check)(group */*g*/, grand */*gr*/);
107 /* --- Arithmetic --- */
109 void (*mul)(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
110 void (*sqr)(group */*g*/, ge */*d*/, ge */*x*/);
111 void (*inv)(group */*g*/, ge */*d*/, ge */*x*/);
112 void (*div)(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
113 void (*exp)(group */*g*/, ge */*d*/, ge */*x*/, mp */*n*/);
114 void (*mexp)(group */*g*/, ge */*d*/,
115 const group_expfactor */*f*/, size_t /*n*/);
117 /* --- Debugging --- */
119 int (*read)(group */*g*/, ge */*d*/,
120 const mptext_ops */*ops*/, void */*p*/);
121 int (*write)(group */*g*/, ge */*x*/,
122 const mptext_ops */*ops*/, void */*p*/);
124 /* --- Conversions --- */
126 mp *(*toint)(group */*g*/, mp */*d*/, ge */*x*/);
127 int (*fromint)(group */*g*/, ge */*d*/, mp */*x*/);
128 int (*toec)(group */*g*/, ec */*d*/, ge */*x*/);
129 int (*fromec)(group */*g*/, ge */*d*/, const ec */*p*/);
130 int (*tobuf)(group */*h*/, buf */*b*/, ge */*x*/);
131 int (*frombuf)(group */*h*/, buf */*b*/, ge */*d*/);
132 int (*toraw)(group */*h*/, buf */*b*/, ge */*x*/);
133 int (*fromraw)(group */*h*/, buf */*b*/, ge */*d*/);
138 GTY_PRIME, /* Prime field subgroup */
139 GTY_BINARY, /* Binary feld subgroup */
140 GTY_EC /* Elliptic curve group */
143 #define G_NAME(g) (g)->ops->name
144 #define G_TYPE(g) (g)->ops->ty
146 #define G_DESTROYGROUP(g) (g)->ops->destroygroup((g))
147 #define G_CREATE(g) (g)->ops->create((g))
148 #define G_COPY(g, d, x) (g)->ops->copy((g), (d), (x))
149 #define G_BURN(g, x) (g)->ops->burn((g), (x))
150 #define G_DESTROY(g, x) (g)->ops->destroy((g), (x))
152 #define G_SAMEP(g, h) (g)->ops->samep((g), (h))
153 #define G_EQ(g, x, y) (g)->ops->eq((g), (x), (y))
154 #define G_IDENTP(g, x) (g)->ops->identp((g), (x))
156 #define G_CHECK(g, gr) (g)->ops->check((g), (gr))
158 #define G_MUL(g, d, x, y) (g)->ops->mul((g), (d), (x), (y))
159 #define G_SQR(g, d, x) (g)->ops->sqr((g), (d), (x))
160 #define G_INV(g, d, x) (g)->ops->inv((g), (d), (x))
161 #define G_DIV(g, d, x, y) (g)->ops->div((g), (d), (x), (y))
162 #define G_EXP(g, d, x, n) (g)->ops->exp((g), (d), (x), (n))
163 #define G_MEXP(g, d, f, n) (g)->ops->mexp((g), (d), (f), (n))
165 #define G_READ(g, d, o, p) (g)->ops->read((g), (d), (o), (p))
166 #define G_WRITE(g, x, o, p) (g)->ops->write((g), (x), (o), (p))
168 #define G_TOINT(g, d, x) (g)->ops->toint((g), (d), (x))
169 #define G_FROMINT(g, d, x) (g)->ops->fromint((g), (d), (x))
170 #define G_TOEC(g, d, x) (g)->ops->toec((g), (d), (x))
171 #define G_FROMEC(g, d, p) (g)->ops->fromec((g), (d), (p))
172 #define G_TOBUF(g, b, x) (g)->ops->tobuf((g), (b), (x))
173 #define G_FROMBUF(g, b, d) (g)->ops->frombuf((g), (b), (d))
174 #define G_TORAW(g, b, x) (g)->ops->toraw((g), (b), (x))
175 #define G_FROMRAW(g, b, d) (g)->ops->fromraw((g), (b), (d))
177 /*----- Handy functions ---------------------------------------------------*/
179 /* --- @group_check@ --- *
181 * Arguments: @group *g@ = an abstract group
182 * @ge *x@ = a group element
184 * Returns: Zero on success, nonzero for failure.
186 * Use: Checks that @x@ is a valid group element. This may take a
187 * while, since it checks that %$x^h \ne 1$%.
190 extern int group_check(group */*g*/, ge */*x*/);
192 /* --- @group_samep@ --- *
194 * Arguments: @group *g, *h@ = two abstract groups
196 * Returns: Nonzero if the groups are in fact identical (not just
199 * Use: Checks to see whether two groups are actually the same. This
200 * function does the full check: the group operatrion @samep@
201 * just does the group-specific details.
204 extern int group_samep(group */*g*/, group */*h*/);
206 /*----- Textual I/O on group elements -------------------------------------*/
208 extern int group_readstring(group */*g*/, ge */*d*/,
209 const char */*p*/, char **/*end*/);
210 extern int group_writestring(group */*g*/, ge */*d*/,
211 char */*p*/, size_t /*sz*/);
213 extern int group_readfile(group */*g*/, ge */*d*/, FILE */*fp*/);
214 extern int group_writefile(group */*g*/, ge */*x*/, FILE */*fp*/);
216 extern int group_readdstr(group */*g*/, ge */*d*/,
217 dstr */*dd*/, size_t */*off*/);
218 extern int group_writedstr(group */*g*/, ge */*x*/, dstr */*d*/);
220 /*----- Standard implementations ------------------------------------------*/
222 /* --- @group_stdidentp@ --- *
224 * Arguments: @group *g@ = abstract group
225 * @ge *x@ = group element
227 * Returns: Nonzero if %$x$% is the group identity.
230 extern int group_stdidentp(group */*g*/, ge */*x*/);
232 /* --- @group_stdcheck@ --- *
234 * Arguments: @group *g@ = abstract group
235 * @grand *gr@ = random number source.
237 * Returns: Null on success, or a pointer to an error message.
240 extern const char *group_stdcheck(group */*g*/, grand */*gr*/);
242 /* --- @group_stdsqr@ --- *
244 * Arguments: @group *g@ = abstract group
245 * @ge *d@ = destination pointer
246 * @ge *x@ = group element
250 * Use: Computes %$d = x^2$% as %$d = x x$%.
253 extern void group_stdsqr(group */*g*/, ge */*d*/, ge */*x*/);
255 /* --- @group_stddiv@ --- *
257 * Arguments: @group *g@ = abstract group
258 * @ge *d@ = destination pointer
264 * Use: Computes %$d = x/y$% as %$d = x y^{-1}$%.
267 extern void group_stddiv(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
269 /* --- @group_stdexp@ --- *
271 * Arguments: @group *g@ = abstract group
272 * @ge *d@ = destination pointer
273 * @ge *x@ = base element
278 * Use: Computes %$d = x^n$% efficiently.
281 extern void group_stdexp(group */*g*/, ge */*d*/, ge */*x*/, mp */*n*/);
283 /* --- @group_stdmexp@ --- *
285 * Arguments: @group *g@ = abstract group
286 * @ge *d@ = destination pointer
287 * @const group_expfactor *f@ = vector of factors
288 * @size_t n@ = number of factors
292 * Use: Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
295 extern void group_stdmexp(group */*g*/, ge */*d*/,
296 const group_expfactor */*f*/, size_t /*n*/);
298 /* --- @group_stdtoec@ --- *
300 * Arguments: @group *g@ = abstract group
301 * @ec *d@ = destination point
302 * @ge *x@ = group element
304 * Returns: @-1@, indicating failure.
306 * Use: Fails to convert a group element to an elliptic curve point.
309 extern int group_stdtoec(group */*g*/, ec */*d*/, ge */*x*/);
311 /* --- @group_stdfromec@ --- *
313 * Arguments: @group *g@ = abstract group
314 * @ge *d@ = destination pointer
315 * @const ec *p@ = elliptic curve point
317 * Returns: Zero for success, @-1@ on failure.
319 * Use: Converts %$p$% to a group element by converting its %$x$%-
323 extern int group_stdfromec(group */*g*/, ge */*d*/, const ec */*p*/);
325 /*----- Prime field subgroups ---------------------------------------------*/
327 typedef struct gprime_param {
328 mp *p, *q; /* Prime numbers %$p$% and %$q$% */
329 mp *g; /* Generates order-%$q$% subgroup */
332 /* --- @group_prime@ --- *
334 * Arguments: @const gprime_param *gp@ = group parameters
336 * Returns: A pointer to the group, or null.
338 * Use: Constructs an abstract group interface for a subgroup of a
339 * prime field. Group elements are @mp *@ pointers.
342 group *group_prime(const gprime_param */*gp*/);
344 /*----- Binary field subgroups --------------------------------------------*/
346 typedef gprime_param gbin_param;
348 /* --- @group_binary@ --- *
350 * Arguments: @const gbin_param *gb@ = group parameters
352 * Returns: A pointer to the group, or null.
354 * Use: Constructs an abstract group interface for a subgroup of a
355 * prime field. Group elements are @mp *@ pointers.
358 group *group_binary(const gbin_param */*gp*/);
360 /*----- Elliptic curve groups ---------------------------------------------*/
362 /* --- @group_ec@ --- *
364 * Arguments: @const ec_info *ei@ = elliptic curve parameters
366 * Returns: A pointer to the group, or null.
368 * Use: Constructs an abstract group interface for an elliptic curve
369 * group. Group elements are @ec@ structures. The contents of
370 * the @ec_info@ structure becomes the property of the @group@
371 * object; you can (and should) free the structure itself, but
372 * calling @ec_freeinfo@ on it is not allowed.
375 group *group_ec(const ec_info */*ei*/);
377 /*----- General group initialization --------------------------------------*/
379 /* --- @group_parse@ --- *
381 * Arguments: @qd_parse *qd@ = quick-and-dirty parser
383 * Returns: Group pointer, or null for failure.
385 * Use: Parses a group description and returns the group. This has
386 * the form `TYPE { SPEC }' where TYPE is `prime' or `ec', and
387 * SPEC is the appropriate kind of group specification of the
391 extern group *group_parse(qd_parse */*qd*/);
393 /* --- @group_fromstring@ --- *
395 * Arguments: @const char *p@ = pointer to string to read
396 * @group **gg@ = where to put the group pointer
398 * Returns: Null if OK, or an error string.
400 * Use: Parses a group spec from a string, and returns the group.
403 extern const char *group_fromstring(const char */*p*/, group **/*gg*/);
405 /*----- That's all, folks -------------------------------------------------*/