97f455fa3d64664737794edc94849f363f101618
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 -------------------------------------------------*/