3 * $Id: g-prime.c,v 1.3 2004/04/04 19:04:11 mdw Exp $
5 * Abstraction for prime groups
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 /*----- Revision history --------------------------------------------------*
33 * Revision 1.3 2004/04/04 19:04:11 mdw
34 * Raw I/O of elliptic curve points and group elements.
36 * Revision 1.2 2004/04/03 03:32:05 mdw
37 * General robustification.
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.)
48 /*----- Header files ------------------------------------------------------*/
58 /*----- Data structures ---------------------------------------------------*/
66 /*----- Main code ---------------------------------------------------------*/
68 /* --- Group operations --- */
70 static void gdestroygroup(group *gg) {
72 mp_drop(g->gen); mp_drop(g->g.r); mp_drop(g->g.h);
73 mpmont_destroy(&g->mm);
77 static mp **gcreate(group *gg)
78 { mp **x = CREATE(mp *); *x = MP_COPY(*gg->i); return (x); }
80 static void gcopy(group *gg, mp **d, mp **x)
81 { mp *t = MP_COPY(*x); MP_DROP(*d); *d = t; }
83 static void gburn(group *gg, mp **x) { (*x)->f |= MP_BURN; }
85 static void gdestroy(group *gg, mp **x) { MP_DROP(*x); DESTROY(x); }
87 static int gsamep(group *gg, group *hh) {
88 gctx *g = (gctx *)gg, *h = (gctx *)hh;
89 return (MP_EQ(g->mm.m, h->mm.m));
92 static int geq(group *gg, mp **x, mp **y) { return (MP_EQ(*x, *y)); }
94 static const char *gcheck(group *gg, grand *gr) {
95 gctx *g = (gctx *)gg; int rc; mp *t;
96 if (!pgen_primep(g->mm.m, gr)) return ("p is not prime");
97 t = mp_mul(MP_NEW, g->g.r, g->g.h); t = mp_add(t, t, MP_ONE);
98 rc = MP_EQ(t, g->mm.m); MP_DROP(t); if (!rc) return ("not a subgroup");
99 return (group_stdcheck(gg, gr));
102 static void gmul(group *gg, mp **d, mp **x, mp **y)
103 { gctx *g = (gctx *)gg; *d = mpmont_mul(&g->mm, *d, *x, *y); }
105 static void gsqr(group *gg, mp **d, mp **x) {
106 gctx *g = (gctx *)gg; mp *r = mp_sqr(*d, *x);
107 *d = mpmont_reduce(&g->mm, r, r);
110 static void ginv(group *gg, mp **d, mp **x) {
111 gctx *g = (gctx *)gg; mp *r = mpmont_reduce(&g->mm, *d, *x);
112 mp_gcd(0, 0, &r, g->mm.m, r); *d = mpmont_mul(&g->mm, r, r, g->mm.r2);
115 static void gexp(group *gg, mp **d, mp **x, mp *n)
116 { gctx *g = (gctx *)gg; *d = mpmont_expr(&g->mm, *d, *x, n); }
118 static void gmexp(group *gg, mp **d, const group_expfactor *f, size_t n) {
119 gctx *g = (gctx *)gg; size_t i;
120 mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
121 for (i = 0; i < n; i++) { ff[i].base = *f[i].base; ff[i].exp = f[i].exp; }
122 *d = mpmont_mexpr(&g->mm, *d, ff, n); xfree(ff);
125 static int gread(group *gg, mp **d, const mptext_ops *ops, void *p) {
126 gctx *g = (gctx *)gg; mp *t;
127 if ((t = mp_read(MP_NEW, 0, ops, p)) == 0) return (-1);
128 mp_drop(*d); *d = mpmont_mul(&g->mm, t, t, g->mm.r2); return (0);
131 static int gwrite(group *gg, mp **x, const mptext_ops *ops, void *p) {
132 gctx *g = (gctx *)gg; mp *t = mpmont_reduce(&g->mm, MP_NEW, *x);
133 int rc = mp_write(t, 10, ops, p); MP_DROP(t); return (rc);
136 static mp *gtoint(group *gg, mp *d, mp **x)
137 { gctx *g = (gctx *)gg; return (mpmont_reduce(&g->mm, d, *x)); }
139 static int gfromint(group *gg, mp **d, mp *x) {
140 gctx *g = (gctx *)gg; mp_div(0, &x, x, g->mm.m); mp_drop(*d);
141 *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return (0);
144 static int gtobuf(group *gg, buf *b, mp **x) {
145 gctx *g = (gctx *)gg; mp *t = mpmont_reduce(&g->mm, MP_NEW, *x);
146 int rc = buf_putmp(b, t); MP_DROP(t); return (rc);
149 static int gfrombuf(group *gg, buf *b, mp **d) {
150 gctx * g = (gctx *)gg; mp *x; if ((x = buf_getmp(b)) == 0) return (-1);
151 mp_div(0, &x, x, g->mm.m); mp_drop(*d);
152 *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return(0);
155 static int gtoraw(group *gg, buf *b, mp **x) {
156 gctx *g = (gctx *)gg; octet *q; mp *t = mpmont_reduce(&g->mm, MP_NEW, *x);
157 if ((q = buf_get(b, g->g.noctets)) == 0) { MP_DROP(t); return (-1); }
158 mp_storeb(t, q, g->g.noctets); MP_DROP(t); return (0);
161 static int gfromraw(group *gg, buf *b, mp **d) {
162 gctx * g = (gctx *)gg; mp *x; octet *q;
163 if ((q = buf_get(b, g->g.noctets)) == 0) return (-1);
164 x = mp_loadb(MP_NEW, q, g->g.noctets);
165 mp_div(0, &x, x, g->mm.m); mp_drop(*d);
166 *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return(0);
169 /* --- @group_prime@ --- *
171 * Arguments: @const gprime_param *gp@ = group parameters
173 * Returns: A pointer to the group, or null.
175 * Use: Constructs an abstract group interface for a subgroup of a
176 * prime field. Group elements are @mp *@ pointers.
179 static const group_ops gops = {
181 gdestroygroup, gcreate, gcopy, gburn, gdestroy,
182 gsamep, geq, group_stdidentp,
184 gmul, gsqr, ginv, group_stddiv, gexp, gmexp,
186 gtoint, gfromint, group_stdtoec, group_stdfromec, gtobuf, gfrombuf,
190 group *group_prime(const gprime_param *gp)
194 if (!MP_ISPOS(gp->p) || !MP_ISODD(gp->p))
198 g->g.nbits = mp_bits(gp->p);
199 g->g.noctets = (g->g.nbits + 7) >> 3;
200 mpmont_create(&g->mm, gp->p);
202 g->gen = mpmont_mul(&g->mm, MP_NEW, gp->g, g->mm.r2);
204 g->g.r = MP_COPY(gp->q);
205 g->g.h = MP_NEW; mp_div(&g->g.h, 0, gp->p, gp->q);
209 /*----- That's all, folks -------------------------------------------------*/