3 * General cyclic group abstraction
5 * (c) 2004 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 #ifndef CATACOMB_GROUP_H
29 #define CATACOMB_GROUP_H
35 /*----- Header files ------------------------------------------------------*/
37 #include <mLib/dstr.h>
39 #ifndef CATACOMB_BUF_H
47 #ifndef CATACOMB_GRAND_H
55 #ifndef CATACOMB_QDPARSE_H
59 /*----- Data structures ---------------------------------------------------*/
62 typedef struct ge ge
; /* Group element (abstract type) */
65 typedef struct group_
{
66 const struct group_ops
*ops
; /* Operations table */
67 size_t nbits
; /* Size of an element in bits */
68 size_t noctets
; /* Size of raw element in octets */
69 ge
*i
; /* Identity element */
70 ge
*g
; /* Generator element */
71 mp
*r
; /* Order of the generator */
75 typedef struct group_expfactor
{
76 ge
*base
; /* The base */
77 mp
*exp
; /* The exponent */
80 typedef struct group_ops
{
82 /* --- General information --- */
84 unsigned ty
; /* Type of this group */
85 const char *name
; /* Textual name string */
87 /* --- Memory management --- */
89 void (*destroygroup
)(group */
*g*/
);
90 ge
*(*create
)(group */
*g*/
);
91 void (*copy
)(group */
*g*/
, ge */
*d*/
, ge */
*x*/
);
92 void (*burn
)(group */
*g*/
, ge */
*x*/
);
93 void (*destroy
)(group */
*g*/
, ge */
*e*/
);
95 /* --- Comparisons --- */
97 int (*samep
)(group */
*g*/
, group */
*h*/
);
98 int (*eq
)(group */
*g*/
, ge */
*x*/
, ge */
*y*/
);
99 int (*identp
)(group */
*g*/
, ge */
*x*/
);
101 /* --- Other stuff --- */
103 const char *(*check
)(group */
*g*/
, grand */
*gr*/
);
105 /* --- Arithmetic --- */
107 void (*mul
)(group */
*g*/
, ge */
*d*/
, ge */
*x*/
, ge */
*y*/
);
108 void (*sqr
)(group */
*g*/
, ge */
*d*/
, ge */
*x*/
);
109 void (*inv
)(group */
*g*/
, ge */
*d*/
, ge */
*x*/
);
110 void (*div
)(group */
*g*/
, ge */
*d*/
, ge */
*x*/
, ge */
*y*/
);
111 void (*exp
)(group */
*g*/
, ge */
*d*/
, ge */
*x*/
, mp */
*n*/
);
112 void (*mexp
)(group */
*g*/
, ge */
*d*/
,
113 const group_expfactor */
*f*/
, size_t /*n*/);
115 /* --- Debugging --- */
117 int (*read
)(group */
*g*/
, ge */
*d*/
,
118 const mptext_ops */
*ops*/
, void */
*p*/
);
119 int (*write
)(group */
*g*/
, ge */
*x*/
,
120 const mptext_ops */
*ops*/
, void */
*p*/
);
122 /* --- Conversions --- */
124 mp
*(*toint
)(group */
*g*/
, mp */
*d*/
, ge */
*x*/
);
125 int (*fromint
)(group */
*g*/
, ge */
*d*/
, mp */
*x*/
);
126 int (*toec
)(group */
*g*/
, ec */
*d*/
, ge */
*x*/
);
127 int (*fromec
)(group */
*g*/
, ge */
*d*/
, const ec */
*p*/
);
128 int (*tobuf
)(group */
*h*/
, buf */
*b*/
, ge */
*x*/
);
129 int (*frombuf
)(group */
*h*/
, buf */
*b*/
, ge */
*d*/
);
130 int (*toraw
)(group */
*h*/
, buf */
*b*/
, ge */
*x*/
);
131 int (*fromraw
)(group */
*h*/
, buf */
*b*/
, ge */
*d*/
);
136 GTY_PRIME
, /* Prime field subgroup */
137 GTY_BINARY
, /* Binary feld subgroup */
138 GTY_EC
/* Elliptic curve group */
141 #define G_NAME(g) (g)->ops->name
142 #define G_TYPE(g) (g)->ops->ty
144 #define G_DESTROYGROUP(g) (g)->ops->destroygroup((g))
145 #define G_CREATE(g) (g)->ops->create((g))
146 #define G_COPY(g, d, x) (g)->ops->copy((g), (d), (x))
147 #define G_BURN(g, x) (g)->ops->burn((g), (x))
148 #define G_DESTROY(g, x) (g)->ops->destroy((g), (x))
150 #define G_SAMEP(g, h) (g)->ops->samep((g), (h))
151 #define G_EQ(g, x, y) (g)->ops->eq((g), (x), (y))
152 #define G_IDENTP(g, x) (g)->ops->identp((g), (x))
154 #define G_CHECK(g, gr) (g)->ops->check((g), (gr))
156 #define G_MUL(g, d, x, y) (g)->ops->mul((g), (d), (x), (y))
157 #define G_SQR(g, d, x) (g)->ops->sqr((g), (d), (x))
158 #define G_INV(g, d, x) (g)->ops->inv((g), (d), (x))
159 #define G_DIV(g, d, x, y) (g)->ops->div((g), (d), (x), (y))
160 #define G_EXP(g, d, x, n) (g)->ops->exp((g), (d), (x), (n))
161 #define G_MEXP(g, d, f, n) (g)->ops->mexp((g), (d), (f), (n))
163 #define G_READ(g, d, o, p) (g)->ops->read((g), (d), (o), (p))
164 #define G_WRITE(g, x, o, p) (g)->ops->write((g), (x), (o), (p))
166 #define G_TOINT(g, d, x) (g)->ops->toint((g), (d), (x))
167 #define G_FROMINT(g, d, x) (g)->ops->fromint((g), (d), (x))
168 #define G_TOEC(g, d, x) (g)->ops->toec((g), (d), (x))
169 #define G_FROMEC(g, d, p) (g)->ops->fromec((g), (d), (p))
170 #define G_TOBUF(g, b, x) (g)->ops->tobuf((g), (b), (x))
171 #define G_FROMBUF(g, b, d) (g)->ops->frombuf((g), (b), (d))
172 #define G_TORAW(g, b, x) (g)->ops->toraw((g), (b), (x))
173 #define G_FROMRAW(g, b, d) (g)->ops->fromraw((g), (b), (d))
175 /*----- Handy functions ---------------------------------------------------*/
177 /* --- @group_check@ --- *
179 * Arguments: @group *g@ = an abstract group
180 * @ge *x@ = a group element
182 * Returns: Zero on success, nonzero for failure.
184 * Use: Checks that @x@ is a valid group element. This may take a
185 * while, since it checks that %$x^h \ne 1$%.
188 extern int group_check(group */
*g*/
, ge */
*x*/
);
190 /* --- @group_samep@ --- *
192 * Arguments: @group *g, *h@ = two abstract groups
194 * Returns: Nonzero if the groups are in fact identical (not just
197 * Use: Checks to see whether two groups are actually the same. This
198 * function does the full check: the group operatrion @samep@
199 * just does the group-specific details.
202 extern int group_samep(group */
*g*/
, group */
*h*/
);
204 /*----- Textual I/O on group elements -------------------------------------*/
206 extern int group_readstring(group */
*g*/
, ge */
*d*/
,
207 const char */
*p*/
, char **/
*end*/
);
208 extern int group_writestring(group */
*g*/
, ge */
*d*/
,
209 char */
*p*/
, size_t /*sz*/);
211 extern int group_readfile(group */
*g*/
, ge */
*d*/
, FILE */
*fp*/
);
212 extern int group_writefile(group */
*g*/
, ge */
*x*/
, FILE */
*fp*/
);
214 extern int group_readdstr(group */
*g*/
, ge */
*d*/
,
215 dstr */
*dd*/
, size_t */
*off*/
);
216 extern int group_writedstr(group */
*g*/
, ge */
*x*/
, dstr */
*d*/
);
218 /*----- Standard implementations ------------------------------------------*/
220 /* --- @group_stdidentp@ --- *
222 * Arguments: @group *g@ = abstract group
223 * @ge *x@ = group element
225 * Returns: Nonzero if %$x$% is the group identity.
228 extern int group_stdidentp(group */
*g*/
, ge */
*x*/
);
230 /* --- @group_stdcheck@ --- *
232 * Arguments: @group *g@ = abstract group
233 * @grand *gr@ = random number source.
235 * Returns: Null on success, or a pointer to an error message.
238 extern const char *group_stdcheck(group */
*g*/
, grand */
*gr*/
);
240 /* --- @group_stdsqr@ --- *
242 * Arguments: @group *g@ = abstract group
243 * @ge *d@ = destination pointer
244 * @ge *x@ = group element
248 * Use: Computes %$d = x^2$% as %$d = x x$%.
251 extern void group_stdsqr(group */
*g*/
, ge */
*d*/
, ge */
*x*/
);
253 /* --- @group_stddiv@ --- *
255 * Arguments: @group *g@ = abstract group
256 * @ge *d@ = destination pointer
262 * Use: Computes %$d = x/y$% as %$d = x y^{-1}$%.
265 extern void group_stddiv(group */
*g*/
, ge */
*d*/
, ge */
*x*/
, ge */
*y*/
);
267 /* --- @group_stdexp@ --- *
269 * Arguments: @group *g@ = abstract group
270 * @ge *d@ = destination pointer
271 * @ge *x@ = base element
276 * Use: Computes %$d = x^n$% efficiently.
279 extern void group_stdexp(group */
*g*/
, ge */
*d*/
, ge */
*x*/
, mp */
*n*/
);
281 /* --- @group_stdmexp@ --- *
283 * Arguments: @group *g@ = abstract group
284 * @ge *d@ = destination pointer
285 * @const group_expfactor *f@ = vector of factors
286 * @size_t n@ = number of factors
290 * Use: Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
293 extern void group_stdmexp(group */
*g*/
, ge */
*d*/
,
294 const group_expfactor */
*f*/
, size_t /*n*/);
296 /* --- @group_stdtoec@ --- *
298 * Arguments: @group *g@ = abstract group
299 * @ec *d@ = destination point
300 * @ge *x@ = group element
302 * Returns: @-1@, indicating failure.
304 * Use: Fails to convert a group element to an elliptic curve point.
307 extern int group_stdtoec(group */
*g*/
, ec */
*d*/
, ge */
*x*/
);
309 /* --- @group_stdfromec@ --- *
311 * Arguments: @group *g@ = abstract group
312 * @ge *d@ = destination pointer
313 * @const ec *p@ = elliptic curve point
315 * Returns: Zero for success, @-1@ on failure.
317 * Use: Converts %$p$% to a group element by converting its %$x$%-
321 extern int group_stdfromec(group */
*g*/
, ge */
*d*/
, const ec */
*p*/
);
323 /*----- Prime field subgroups ---------------------------------------------*/
325 typedef struct gprime_param
{
326 mp
*p
, *q
; /* Prime numbers %$p$% and %$q$% */
327 mp
*g
; /* Generates order-%$q$% subgroup */
330 /* --- @group_prime@ --- *
332 * Arguments: @const gprime_param *gp@ = group parameters
334 * Returns: A pointer to the group, or null.
336 * Use: Constructs an abstract group interface for a subgroup of a
337 * prime field. Group elements are @mp *@ pointers.
340 group
*group_prime(const gprime_param */
*gp*/
);
342 /*----- Binary field subgroups --------------------------------------------*/
344 typedef gprime_param gbin_param
;
346 /* --- @group_binary@ --- *
348 * Arguments: @const gbin_param *gb@ = group parameters
350 * Returns: A pointer to the group, or null.
352 * Use: Constructs an abstract group interface for a subgroup of a
353 * prime field. Group elements are @mp *@ pointers.
356 group
*group_binary(const gbin_param */
*gp*/
);
358 /*----- Elliptic curve groups ---------------------------------------------*/
360 /* --- @group_ec@ --- *
362 * Arguments: @const ec_info *ei@ = elliptic curve parameters
364 * Returns: A pointer to the group, or null.
366 * Use: Constructs an abstract group interface for an elliptic curve
367 * group. Group elements are @ec@ structures. The contents of
368 * the @ec_info@ structure becomes the property of the @group@
369 * object; you can (and should) free the structure itself, but
370 * calling @ec_freeinfo@ on it is not allowed.
373 group
*group_ec(const ec_info */
*ei*/
);
375 /*----- General group initialization --------------------------------------*/
377 /* --- @group_parse@ --- *
379 * Arguments: @qd_parse *qd@ = quick-and-dirty parser
381 * Returns: Group pointer, or null for failure.
383 * Use: Parses a group description and returns the group. This has
384 * the form `TYPE { SPEC }' where TYPE is `prime' or `ec', and
385 * SPEC is the appropriate kind of group specification of the
389 extern group
*group_parse(qd_parse */
*qd*/
);
391 /* --- @group_fromstring@ --- *
393 * Arguments: @const char *p@ = pointer to string to read
394 * @group **gg@ = where to put the group pointer
396 * Returns: Null if OK, or an error string.
398 * Use: Parses a group spec from a string, and returns the group.
401 extern const char *group_fromstring(const char */
*p*/
, group
**/
*gg*/
);
403 /*----- That's all, folks -------------------------------------------------*/