1 /* borrowed from isakmpd-20030718 (-; */
2
3 /* $OpenBSD: math_group.c,v 1.18 2003/06/03 14:28:16 ho Exp $ */
4 /* $EOM: math_group.c,v 1.25 2000/04/07 19:53:26 niklas Exp $ */
5
6 /*
7 * Copyright (c) 1998 Niels Provos. All rights reserved.
8 * Copyright (c) 1999, 2000 Niklas Hallqvist. All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 /*
32 * This code was written under funding by Ericsson Radio Systems.
33 */
34
35 #include <assert.h>
36 #include <sys/param.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <netinet/in.h>
40
41 #include <gcrypt.h>
42
43 #include "math_group.h"
44
45 /* We do not want to export these definitions. */
46 static void modp_free(struct group *);
47 static struct group *modp_clone(struct group *, struct group *);
48 static void modp_init(struct group *);
49
50 static int modp_getlen(struct group *);
51 static void modp_getraw(struct group *, gcry_mpi_t, unsigned char *);
52 static int modp_setraw(struct group *, gcry_mpi_t, unsigned char *, int);
53 static int modp_setrandom(struct group *, gcry_mpi_t);
54 static int modp_operation(struct group *, gcry_mpi_t, gcry_mpi_t, gcry_mpi_t);
55
56 /*
57 * This module provides access to the operations on the specified group
58 * and is absolutly free of any cryptographic devices. This is math :-).
59 */
60
61 /* Describe preconfigured MODP groups */
62
63 /*
64 * The Generalized Number Field Sieve has an asymptotic running time
65 * of: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))), where q is the
66 * group order, e.g. q = 2**768.
67 */
68
69 static const struct modp_dscr oakley_modp[] = {
70 {
71 OAKLEY_GRP_1, 72, /* This group is insecure, only sufficient for DES */
72 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
73 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
74 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
75 "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
76 "2"
77 },
78 {
79 OAKLEY_GRP_2, 82, /* This group is a bit better */
80 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
81 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
82 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
83 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
84 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
85 "FFFFFFFFFFFFFFFF",
86 "2"
87 },
88 {
89 OAKLEY_GRP_5, 102, /* This group is yet a bit better, but non-standard */
90 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
91 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
92 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
93 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
94 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
95 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
96 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
97 "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
98 "2"
99 },
100 };
101
102 /* XXX I want to get rid of the casting here. */
103 static struct group groups[] = {
104 {
105 MODP, OAKLEY_GRP_1, 0, NULL, &oakley_modp[0], NULL, NULL, NULL, NULL, NULL,
106 (int (*)(struct group *))modp_getlen,
107 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
108 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
109 (int (*)(struct group *, void *))modp_setrandom,
110 (int (*)(struct group *, void *, void *, void *))modp_operation
111 },
112 {
113 MODP, OAKLEY_GRP_2, 0, NULL, &oakley_modp[1], NULL, NULL, NULL, NULL, NULL,
114 (int (*)(struct group *))modp_getlen,
115 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
116 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
117 (int (*)(struct group *, void *))modp_setrandom,
118 (int (*)(struct group *, void *, void *, void *))modp_operation
119 },
120 {
121 MODP, OAKLEY_GRP_5, 0, NULL, &oakley_modp[2], NULL, NULL, NULL, NULL, NULL,
122 (int (*)(struct group *))modp_getlen,
123 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
124 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
125 (int (*)(struct group *, void *))modp_setrandom,
126 (int (*)(struct group *, void *, void *, void *))modp_operation
127 },
128 };
129
130 /*
131 * Initialize the group structure for later use,
132 * this is done by converting the values given in the describtion
133 * and converting them to their native representation.
134 */
group_init(void)135 void group_init(void)
136 {
137 int i;
138
139 for (i = sizeof(groups) / sizeof(groups[0]) - 1; i >= 0; i--) {
140 assert(groups[i].type == MODP);
141 modp_init(&groups[i]); /* Initialize an over GF(p) */
142 }
143 }
144
group_get(int id)145 struct group *group_get(int id)
146 {
147 struct group *new, *clone;
148
149 assert(id >= 1);
150 assert(id <= (int)(sizeof(groups) / sizeof(groups[0])));
151
152 clone = &groups[id - 1];
153
154 new = malloc(sizeof *new);
155 assert(new);
156
157 assert(clone->type == MODP);
158 new = modp_clone(new, clone);
159 return new;
160 }
161
group_free(struct group * grp)162 void group_free(struct group *grp)
163 {
164 assert(grp->type == MODP);
165 modp_free(grp);
166 free(grp);
167 }
168
modp_clone(struct group * new,struct group * clone)169 static struct group *modp_clone(struct group *new, struct group *clone)
170 {
171 struct modp_group *new_grp, *clone_grp = clone->group;
172
173 new_grp = malloc(sizeof *new_grp);
174 assert(new_grp);
175
176 memcpy(new, clone, sizeof(struct group));
177
178 new->group = new_grp;
179 new_grp->p = gcry_mpi_copy(clone_grp->p);
180 new_grp->gen = gcry_mpi_copy(clone_grp->gen);
181
182 new_grp->a = gcry_mpi_new(clone->bits);
183 new_grp->b = gcry_mpi_new(clone->bits);
184 new_grp->c = gcry_mpi_new(clone->bits);
185
186 new->gen = new_grp->gen;
187 new->a = new_grp->a;
188 new->b = new_grp->b;
189 new->c = new_grp->c;
190
191 return new;
192 }
193
modp_free(struct group * old)194 static void modp_free(struct group *old)
195 {
196 struct modp_group *grp = old->group;
197
198 gcry_mpi_release(grp->p);
199 gcry_mpi_release(grp->gen);
200 gcry_mpi_release(grp->a);
201 gcry_mpi_release(grp->b);
202 gcry_mpi_release(grp->c);
203
204 free(grp);
205 }
206
modp_init(struct group * group)207 static void modp_init(struct group *group)
208 {
209 const struct modp_dscr *dscr = group->group_dscr;
210 struct modp_group *grp;
211
212 grp = malloc(sizeof *grp);
213 assert(grp);
214
215 group->bits = dscr->bits;
216
217 gcry_mpi_scan(&grp->p, GCRYMPI_FMT_HEX, (const unsigned char*)dscr->prime, 0, NULL);
218 gcry_mpi_scan(&grp->gen, GCRYMPI_FMT_HEX, (const unsigned char *)dscr->gen, 0, NULL);
219
220 grp->a = gcry_mpi_new(group->bits);
221 grp->b = gcry_mpi_new(group->bits);
222 grp->c = gcry_mpi_new(group->bits);
223
224 group->gen = grp->gen;
225 group->a = grp->a;
226 group->b = grp->b;
227 group->c = grp->c;
228
229 group->group = grp;
230 }
231
modp_getlen(struct group * group)232 static int modp_getlen(struct group *group)
233 {
234 struct modp_group *grp = (struct modp_group *)group->group;
235
236 return (gcry_mpi_get_nbits(grp->p) + 7) / 8;
237 }
238
modp_getraw(struct group * grp,gcry_mpi_t v,unsigned char * d)239 static void modp_getraw(struct group *grp, gcry_mpi_t v, unsigned char *d)
240 {
241 size_t l, l2;
242 unsigned char *tmp;
243 int ret;
244
245 l = grp->getlen(grp);
246 ret = gcry_mpi_aprint(GCRYMPI_FMT_STD, &tmp, &l2, v);
247 memcpy(d, tmp + (l2 - l), l);
248 gcry_free(tmp);
249 #if 0
250 {
251 char *p;
252 gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, v);
253 printf("export %d - %d(%d):\n%s\n", l, l2, ret, p);
254 gcry_free(p);
255 }
256 #endif
257 }
258
modp_setraw(struct group * grp,gcry_mpi_t d,unsigned char * s,int l)259 static int modp_setraw(struct group *grp, gcry_mpi_t d, unsigned char *s, int l)
260 {
261 int i;
262
263 grp = NULL; /* unused */
264
265 gcry_mpi_set_ui(d, 0);
266 for (i = 0; i < l; i++) {
267 gcry_mpi_mul_2exp(d, d, 8);
268 gcry_mpi_add_ui(d, d, s[i]);
269 }
270 #if 0
271 {
272 char *p;
273 gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, d);
274 printf("import %d:\n%s\n", l, p);
275 gcry_free(p);
276 }
277 #endif
278 return 0;
279 }
280
modp_setrandom(struct group * grp,gcry_mpi_t d)281 static int modp_setrandom(struct group *grp, gcry_mpi_t d)
282 {
283 int i, l = grp->getlen(grp);
284 uint32_t tmp = 0;
285
286 gcry_mpi_set_ui(d, 0);
287
288 for (i = 0; i < l; i++) {
289 if (i % 4)
290 gcry_randomize((unsigned char *)&tmp, sizeof(tmp), GCRY_STRONG_RANDOM);
291
292 gcry_mpi_mul_2exp(d, d, 8);
293 gcry_mpi_add_ui(d, d, tmp & 0xFF);
294 tmp >>= 8;
295 }
296 return 0;
297 }
298
modp_operation(struct group * group,gcry_mpi_t d,gcry_mpi_t a,gcry_mpi_t e)299 static int modp_operation(struct group *group, gcry_mpi_t d, gcry_mpi_t a, gcry_mpi_t e)
300 {
301 struct modp_group *grp = (struct modp_group *)group->group;
302
303 gcry_mpi_powm(d, a, e, grp->p);
304 return 0;
305 }
306