3 * Abstraction for prime groups
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 /*----- Header files ------------------------------------------------------*/
36 #include "group-guts.h"
38 /*----- Main code ---------------------------------------------------------*/
40 /* --- Group operations --- */
42 static void gdestroygroup(group
*gg
) {
43 gctx_bin
*g
= (gctx_bin
*)gg
;
44 mp_drop(g
->gen
.x
); mp_drop(g
->g
.r
); mp_drop(g
->g
.h
);
45 gfreduce_destroy(&g
->r
);
49 static ge_bin
*gcreate(group
*gg
) {
50 gctx_bin
*g
= (gctx_bin
*)gg
; ge_bin
*x
= CREATE(ge_bin
);
51 x
->x
= MP_COPY(g
->one
.x
); return (x
);
54 static void gcopy(group
*gg
, ge_bin
*d
, ge_bin
*x
)
55 { mp
*t
= MP_COPY(x
->x
); MP_DROP(d
->x
); d
->x
= t
; }
57 static void gburn(group
*gg
, ge_bin
*x
) { x
->x
->f
|= MP_BURN
; }
59 static void gdestroy(group
*gg
, ge_bin
*x
) { MP_DROP(x
->x
); DESTROY(x
); }
61 static int gsamep(group
*gg
, group
*hh
) {
62 gctx_bin
*g
= (gctx_bin
*)gg
, *h
= (gctx_bin
*)hh
;
63 return (MP_EQ(g
->r
.p
, h
->r
.p
));
66 static int geq(group
*gg
, ge_bin
*x
, ge_bin
*y
)
67 { return (MP_EQ(x
->x
, y
->x
)); }
69 static const char *gcheck(group
*gg
, grand
*gr
) {
70 gctx_bin
*g
= (gctx_bin
*)gg
; int rc
; mp
*t
, *tt
;
71 if (!gf_irreduciblep(g
->r
.p
)) return ("p is not irreducible");
72 t
= mp_mul(MP_NEW
, g
->g
.r
, g
->g
.h
); t
= mp_add(t
, t
, MP_ONE
);
73 tt
= mp_lsl(MP_NEW
, MP_ONE
, g
->g
.nbits
);
74 rc
= MP_EQ(t
, tt
); MP_DROP(t
); MP_DROP(tt
);
75 if (!rc
) return ("not a subgroup");
76 return (group_stdcheck(gg
, gr
));
79 static void gmul(group
*gg
, ge_bin
*d
, ge_bin
*x
, ge_bin
*y
) {
80 gctx_bin
*g
= (gctx_bin
*)gg
; mp
*r
= gf_mul(d
->x
, x
->x
, y
->x
);
81 d
->x
= gfreduce_do(&g
->r
, r
, r
);
84 static void gsqr(group
*gg
, ge_bin
*d
, ge_bin
*x
) {
85 gctx_bin
*g
= (gctx_bin
*)gg
; mp
*r
= gf_sqr(d
->x
, x
->x
);
86 d
->x
= gfreduce_do(&g
->r
, r
, r
);
89 static void ginv(group
*gg
, ge_bin
*d
, ge_bin
*x
)
90 { gctx_bin
*g
= (gctx_bin
*)gg
; d
->x
= gf_modinv(d
->x
, x
->x
, g
->r
.p
); }
92 static void gexp(group
*gg
, ge_bin
*d
, ge_bin
*x
, mp
*n
) {
93 gctx_bin
*g
= (gctx_bin
*)gg
;
94 d
->x
= gfreduce_exp(&g
->r
, d
->x
, x
->x
, n
);
97 static int gread(group
*gg
, ge_bin
*d
, const mptext_ops
*ops
, void *p
) {
98 mp
*t
; if ((t
= mp_read(MP_NEW
, 0, ops
, p
)) == 0) return (-1);
99 mp_drop(d
->x
); d
->x
= t
; return (0);
102 static int gwrite(group
*gg
, ge_bin
*x
, const mptext_ops
*ops
, void *p
) {
104 if (!ops
->put("0x", 2, p
) && !mp_write(x
->x
, 16, ops
, p
)) rc
= 0;
108 static mp
*gtoint(group
*gg
, mp
*d
, ge_bin
*x
) { return MP_COPY(x
->x
); }
110 static int gfromint(group
*gg
, ge_bin
*d
, mp
*x
)
111 { d
->x
= MP_COPY(x
); return 0; }
113 static int gtobuf(group
*gg
, buf
*b
, ge_bin
*x
)
114 { int rc
= buf_putmp(b
, x
->x
); return (rc
); }
116 static int gfrombuf(group
*gg
, buf
*b
, ge_bin
*d
) {
117 gctx_bin
*g
= (gctx_bin
*)gg
; mp
*x
;
118 if ((x
= buf_getmp(b
)) == 0) return (-1);
119 MP_DROP(d
->x
); d
->x
= gfreduce_do(&g
->r
, x
, x
);
123 static int gtoraw(group
*gg
, buf
*b
, ge_bin
*x
) {
124 gctx_bin
*g
= (gctx_bin
*)gg
; octet
*q
;
125 if ((q
= buf_get(b
, g
->g
.noctets
)) == 0) return (-1);
126 mp_storeb(x
->x
, q
, g
->g
.noctets
); return (0);
129 static int gfromraw(group
*gg
, buf
*b
, ge_bin
*d
) {
130 gctx_bin
*g
= (gctx_bin
*)gg
; mp
*x
; octet
*q
;
131 if ((q
= buf_get(b
, g
->g
.noctets
)) == 0) return (-1);
132 x
= mp_loadb(MP_NEW
, q
, g
->g
.noctets
);
133 MP_DROP(d
->x
); d
->x
= gfreduce_do(&g
->r
, x
, x
);
137 /* --- @group_binary@ --- *
139 * Arguments: @const gbin_param *gb@ = group parameters
141 * Returns: A pointer to the group, or null.
143 * Use: Constructs an abstract group interface for a subgroup of a
144 * prime field. Group elements are @mp *@ pointers.
147 static const group_ops gops
= {
149 gdestroygroup
, gcreate
, gcopy
, gburn
, gdestroy
,
150 gsamep
, geq
, group_stdidentp
,
152 gmul
, gsqr
, ginv
, group_stddiv
, gexp
, group_stdmexp
,
154 gtoint
, gfromint
, group_stdtoec
, group_stdfromec
, gtobuf
, gfrombuf
,
158 group
*group_binary(const gbin_param
*gb
)
165 g
= CREATE(gctx_bin
);
167 g
->g
.nbits
= mp_bits(gb
->p
) - 1;
168 g
->g
.noctets
= (g
->g
.nbits
+ 7) >> 3;
169 gfreduce_create(&g
->r
, gb
->p
);
172 g
->gen
.x
= MP_COPY(gb
->g
);
174 g
->g
.r
= MP_COPY(gb
->q
);
175 t
= mp_lsl(MP_NEW
, MP_ONE
, g
->g
.nbits
);
176 t
= mp_sub(t
, t
, MP_ONE
);
177 g
->g
.h
= MP_NEW
; mp_div(&g
->g
.h
, 0, t
, gb
->q
);
182 /*----- That's all, folks -------------------------------------------------*/