?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
adden new isakmpd
[anytun.git] / keyexchange / isakmpd-20041012 / math_group.c
blob55f340f58cfba257d2032e753e1bfb3f50956520
1 /* $OpenBSD: math_group.c,v 1.23 2004/06/14 09:55:41 ho Exp $ */
2 /* $EOM: math_group.c,v 1.25 2000/04/07 19:53:26 niklas Exp $ */
3
4 /*
5 * Copyright (c) 1998 Niels Provos. All rights reserved.
6 * Copyright (c) 1999, 2000 Niklas Hallqvist. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /*
30 * This code was written under funding by Ericsson Radio Systems.
31 */
32
33 #include <sys/param.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "sysdep.h"
38
39 #include "gmp_util.h"
40 #include "log.h"
41 #include "math_2n.h"
42 #include "math_ec2n.h"
43 #include "math_group.h"
44 #include "math_mp.h"
45
46 /* We do not want to export these definitions. */
47 int modp_getlen(struct group *);
48 void modp_getraw(struct group *, math_mp_t, u_int8_t *);
49 int modp_setraw(struct group *, math_mp_t, u_int8_t *, int);
50 int modp_setrandom(struct group *, math_mp_t);
51 int modp_operation(struct group *, math_mp_t, math_mp_t, math_mp_t);
52
53 int ec2n_getlen(struct group *);
54 void ec2n_getraw(struct group *, ec2np_ptr, u_int8_t *);
55 int ec2n_setraw(struct group *, ec2np_ptr, u_int8_t *, int);
56 int ec2n_setrandom(struct group *, ec2np_ptr);
57 int ec2n_operation(struct group *, ec2np_ptr, ec2np_ptr, ec2np_ptr);
58
59 struct ec2n_group {
60 ec2np_t gen; /* Generator */
61 ec2ng_t grp;
62 ec2np_t a, b, c, d;
63 };
64
65 struct modp_group {
66 math_mp_t gen; /* Generator */
67 math_mp_t p; /* Prime */
68 math_mp_t a, b, c, d;
69 };
70
71 /*
72 * This module provides access to the operations on the specified group
73 * and is absolutly free of any cryptographic devices. This is math :-).
74 */
75
76 #define OAKLEY_GRP_1 1
77 #define OAKLEY_GRP_2 2
78 #define OAKLEY_GRP_3 3
79 #define OAKLEY_GRP_4 4
80 #define OAKLEY_GRP_5 5
81 #define OAKLEY_GRP_6 6
82 #define OAKLEY_GRP_7 7
83 #define OAKLEY_GRP_8 8
84 #define OAKLEY_GRP_9 9
85 #define OAKLEY_GRP_10 10
86 #define OAKLEY_GRP_11 11
87 #define OAKLEY_GRP_12 12
88 #define OAKLEY_GRP_13 13
89 #define OAKLEY_GRP_14 14
90 #define OAKLEY_GRP_15 15
91 #define OAKLEY_GRP_16 16
92 #define OAKLEY_GRP_17 17
93 #define OAKLEY_GRP_18 18
94
95 /* Describe preconfigured MODP groups */
96
97 /*
98 * The Generalized Number Field Sieve has an asymptotic running time
99 * of: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))), where q is the
100 * group order, e.g. q = 2**768.
101 */
102
103 struct modp_dscr oakley_modp[] =
104 {
105 {OAKLEY_GRP_1, 72, /* This group is insecure, only sufficient
106 * for DES */
107 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
108 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
109 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
110 "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
111 "0x02"
112 },
113 {OAKLEY_GRP_2, 82, /* This group is a bit better */
114 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
115 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
116 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
117 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
118 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
119 "FFFFFFFFFFFFFFFF",
120 "0x02"
121 },
122 {OAKLEY_GRP_5, 102,
123 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
124 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
125 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
126 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
127 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
128 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
129 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
130 "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
131 "0x02"
132 },
133 {OAKLEY_GRP_14, 135, /* 2048 bit */
134 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
135 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
136 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
137 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
138 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
139 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
140 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
141 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
142 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
143 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
144 "15728E5A8AACAA68FFFFFFFFFFFFFFFF",
145 "0x02"
146 },
147 {OAKLEY_GRP_15, 170, /* 3072 bit */
148 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
149 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
150 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
151 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
152 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
153 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
154 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
155 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
156 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
157 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
158 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
159 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
160 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
161 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
162 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
163 "43DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF",
164 "0x02"
165 },
166 {OAKLEY_GRP_16, 195, /* 4096 bit */
167 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
168 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
169 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
170 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
171 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
172 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
173 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
174 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
175 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
176 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
177 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
178 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
179 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
180 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
181 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
182 "43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7"
183 "88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA"
184 "2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6"
185 "287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED"
186 "1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9"
187 "93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199"
188 "FFFFFFFFFFFFFFFF",
189 "0x02"
190 },
191 {OAKLEY_GRP_17, 220, /* 6144 bit */
192 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
193 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
194 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
195 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
196 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
197 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
198 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
199 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
200 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
201 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
202 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
203 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
204 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
205 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
206 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
207 "43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7"
208 "88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA"
209 "2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6"
210 "287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED"
211 "1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9"
212 "93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934028492"
213 "36C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BD"
214 "F8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831"
215 "179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1B"
216 "DB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF"
217 "5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6"
218 "D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F3"
219 "23A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AA"
220 "CC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE328"
221 "06A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55C"
222 "DA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE"
223 "12BF2D5B0B7474D6E694F91E6DCC4024FFFFFFFFFFFFFFFF",
224 "0x02"
225 },
226 {OAKLEY_GRP_18, 250, /* 8192 bit */
227 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
228 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
229 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
230 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
231 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
232 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
233 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
234 "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
235 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9"
236 "DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
237 "15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64"
238 "ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7"
239 "ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B"
240 "F12FFA06D98A0864D87602733EC86A64521F2B18177B200C"
241 "BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31"
242 "43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7"
243 "88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA"
244 "2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6"
245 "287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED"
246 "1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9"
247 "93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934028492"
248 "36C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BD"
249 "F8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831"
250 "179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1B"
251 "DB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF"
252 "5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6"
253 "D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F3"
254 "23A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AA"
255 "CC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE328"
256 "06A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55C"
257 "DA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE"
258 "12BF2D5B0B7474D6E694F91E6DBE115974A3926F12FEE5E4"
259 "38777CB6A932DF8CD8BEC4D073B931BA3BC832B68D9DD300"
260 "741FA7BF8AFC47ED2576F6936BA424663AAB639C5AE4F568"
261 "3423B4742BF1C978238F16CBE39D652DE3FDB8BEFC848AD9"
262 "22222E04A4037C0713EB57A81A23F0C73473FC646CEA306B"
263 "4BCBC8862F8385DDFA9D4B7FA2C087E879683303ED5BDD3A"
264 "062B3CF5B3A278A66D2A13F83F44F82DDF310EE074AB6A36"
265 "4597E899A0255DC164F31CC50846851DF9AB48195DED7EA1"
266 "B1D510BD7EE74D73FAF36BC31ECFA268359046F4EB879F92"
267 "4009438B481C6CD7889A002ED5EE382BC9190DA6FC026E47"
268 "9558E4475677E9AA9E3050E2765694DFC81F56E880B96E71"
269 "60C980DD98EDD3DFFFFFFFFFFFFFFFFF",
270 "0x02"
271 },
272 };
273
274 #ifdef USE_EC
275 /* Describe preconfigured EC2N groups */
276
277 /*
278 * Related collision-search methods can compute discrete logarithmns
279 * in O(sqrt(r)), r being the subgroup order.
280 */
281
282 struct ec2n_dscr oakley_ec2n[] = {
283 { OAKLEY_GRP_3, 76, /* This group is also considered insecure
284 * (P1363) */
285 "0x0800000000000000000000004000000000000001",
286 "0x7b",
287 "0x00",
288 "0x7338f" },
289 { OAKLEY_GRP_4, 91,
290 "0x020000000000000000000000000000200000000000000001",
291 "0x18",
292 "0x00",
293 "0x1ee9" },
294 };
295 #endif /* USE_EC */
296
297 /* XXX I want to get rid of the casting here. */
298 struct group groups[] = {
299 {
300 MODP, OAKLEY_GRP_1, 0, &oakley_modp[0], 0, 0, 0, 0, 0,
301 (int (*) (struct group *)) modp_getlen,
302 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
303 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
304 (int (*) (struct group *, void *)) modp_setrandom,
305 (int (*) (struct group *, void *, void *, void *)) modp_operation
306 },
307 {
308 MODP, OAKLEY_GRP_2, 0, &oakley_modp[1], 0, 0, 0, 0, 0,
309 (int (*) (struct group *)) modp_getlen,
310 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
311 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
312 (int (*) (struct group *, void *)) modp_setrandom,
313 (int (*) (struct group *, void *, void *, void *)) modp_operation
314 },
315 #ifdef USE_EC
316 {
317 EC2N, OAKLEY_GRP_3, 0, &oakley_ec2n[0], 0, 0, 0, 0, 0,
318 (int (*) (struct group *)) ec2n_getlen,
319 (void (*) (struct group *, void *, u_int8_t *)) ec2n_getraw,
320 (int (*) (struct group *, void *, u_int8_t *, int)) ec2n_setraw,
321 (int (*) (struct group *, void *)) ec2n_setrandom,
322 (int (*) (struct group *, void *, void *, void *)) ec2n_operation
323 },
324 {
325 EC2N, OAKLEY_GRP_4, 0, &oakley_ec2n[1], 0, 0, 0, 0, 0,
326 (int (*) (struct group *)) ec2n_getlen,
327 (void (*) (struct group *, void *, u_int8_t *)) ec2n_getraw,
328 (int (*) (struct group *, void *, u_int8_t *, int)) ec2n_setraw,
329 (int (*) (struct group *, void *)) ec2n_setrandom,
330 (int (*) (struct group *, void *, void *, void *)) ec2n_operation
331 },
332 #endif /* USE_EC */
333 {
334 MODP, OAKLEY_GRP_5, 0, &oakley_modp[2], 0, 0, 0, 0, 0,
335 (int (*) (struct group *)) modp_getlen,
336 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
337 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
338 (int (*) (struct group *, void *)) modp_setrandom,
339 (int (*) (struct group *, void *, void *, void *)) modp_operation
340 },
341 #ifdef USE_EC
342 /* XXX Higher EC2N group go here... */
343 #endif /* USE_EC */
344 /* XXX group 6 to 13 are not yet defined (draft-ike-ecc) */
345 {
346 NOTYET, OAKLEY_GRP_6, 0, NULL, 0, 0, 0, 0, 0,
347 NULL, NULL, NULL, NULL, NULL
348 },
349 {
350 NOTYET, OAKLEY_GRP_7, 0, NULL, 0, 0, 0, 0, 0,
351 NULL, NULL, NULL, NULL, NULL
352 },
353 {
354 NOTYET, OAKLEY_GRP_8, 0, NULL, 0, 0, 0, 0, 0,
355 NULL, NULL, NULL, NULL, NULL
356 },
357 {
358 NOTYET, OAKLEY_GRP_9, 0, NULL, 0, 0, 0, 0, 0,
359 NULL, NULL, NULL, NULL, NULL
360 },
361 {
362 NOTYET, OAKLEY_GRP_10, 0, NULL, 0, 0, 0, 0, 0,
363 NULL, NULL, NULL, NULL, NULL
364 },
365 {
366 NOTYET, OAKLEY_GRP_11, 0, NULL, 0, 0, 0, 0, 0,
367 NULL, NULL, NULL, NULL, NULL
368 },
369 {
370 NOTYET, OAKLEY_GRP_12, 0, NULL, 0, 0, 0, 0, 0,
371 NULL, NULL, NULL, NULL, NULL
372 },
373 {
374 NOTYET, OAKLEY_GRP_13, 0, NULL, 0, 0, 0, 0, 0,
375 NULL, NULL, NULL, NULL, NULL
376 },
377 {
378 MODP, OAKLEY_GRP_14, 0, &oakley_modp[3], 0, 0, 0, 0, 0,
379 (int (*) (struct group *)) modp_getlen,
380 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
381 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
382 (int (*) (struct group *, void *)) modp_setrandom,
383 (int (*) (struct group *, void *, void *, void *)) modp_operation
384 },
385 {
386 MODP, OAKLEY_GRP_15, 0, &oakley_modp[4], 0, 0, 0, 0, 0,
387 (int (*) (struct group *)) modp_getlen,
388 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
389 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
390 (int (*) (struct group *, void *)) modp_setrandom,
391 (int (*) (struct group *, void *, void *, void *)) modp_operation
392 },
393 {
394 MODP, OAKLEY_GRP_16, 0, &oakley_modp[5], 0, 0, 0, 0, 0,
395 (int (*) (struct group *)) modp_getlen,
396 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
397 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
398 (int (*) (struct group *, void *)) modp_setrandom,
399 (int (*) (struct group *, void *, void *, void *)) modp_operation
400 },
401 {
402 MODP, OAKLEY_GRP_17, 0, &oakley_modp[6], 0, 0, 0, 0, 0,
403 (int (*) (struct group *)) modp_getlen,
404 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
405 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
406 (int (*) (struct group *, void *)) modp_setrandom,
407 (int (*) (struct group *, void *, void *, void *)) modp_operation
408 },
409 {
410 MODP, OAKLEY_GRP_18, 0, &oakley_modp[7], 0, 0, 0, 0, 0,
411 (int (*) (struct group *)) modp_getlen,
412 (void (*) (struct group *, void *, u_int8_t *)) modp_getraw,
413 (int (*) (struct group *, void *, u_int8_t *, int)) modp_setraw,
414 (int (*) (struct group *, void *)) modp_setrandom,
415 (int (*) (struct group *, void *, void *, void *)) modp_operation
416 },
417 };
418
419 /*
420 * Initialize the group structure for later use,
421 * this is done by converting the values given in the describtion
422 * and converting them to their native representation.
423 */
424 void
425 group_init(void)
426 {
427 int i;
428
429 for (i = sizeof(groups) / sizeof(groups[0]) - 1; i >= 0; i--)
430 switch (groups[i].type) {
431 #ifdef USE_EC
432 case EC2N: /* Initialize an Elliptic Curve over GF(2**n) */
433 ec2n_init(&groups[i]);
434 break;
435 #endif
436
437 case MODP: /* Initialize an over GF(p) */
438 modp_init(&groups[i]);
439 break;
440
441 case NOTYET: /* Not yet assigned, drop silently */
442 break;
443
444 default:
445 log_print("Unknown group type %d at index %d in "
446 "group_init().", groups[i].type, i);
447 break;
448 }
449 }
450
451 struct group *
452 group_get(u_int32_t id)
453 {
454 struct group *new, *clone;
455
456 if (id < 1 || id > (sizeof(groups) / sizeof(groups[0]))) {
457 log_print("group_get: group ID (%u) out of range", id);
458 return 0;
459 }
460 clone = &groups[id - 1];
461
462 new = malloc(sizeof *new);
463 if (!new) {
464 log_error("group_get: malloc (%lu) failed",
465 (unsigned long)sizeof *new);
466 return 0;
467 }
468 switch (clone->type) {
469 #ifdef USE_EC
470 case EC2N:
471 new = ec2n_clone(new, clone);
472 break;
473 #endif
474 case MODP:
475 new = modp_clone(new, clone);
476 break;
477 default:
478 log_print("group_get: unknown group type %d", clone->type);
479 free(new);
480 return 0;
481 }
482 LOG_DBG((LOG_MISC, 70, "group_get: returning %p of group %d", new,
483 new->id));
484 return new;
485 }
486
487 void
488 group_free(struct group *grp)
489 {
490 switch (grp->type) {
491 #ifdef USE_EC
492 case EC2N:
493 ec2n_free(grp);
494 break;
495 #endif
496 case MODP:
497 modp_free(grp);
498 break;
499 default:
500 log_print("group_free: unknown group type %d", grp->type);
501 break;
502 }
503 free(grp);
504 }
505
506 struct group *
507 modp_clone(struct group *new, struct group *clone)
508 {
509 struct modp_group *new_grp, *clone_grp = clone->group;
510
511 new_grp = malloc(sizeof *new_grp);
512 if (!new_grp) {
513 log_print("modp_clone: malloc (%lu) failed",
514 (unsigned long)sizeof *new_grp);
515 free(new);
516 return 0;
517 }
518 memcpy(new, clone, sizeof(struct group));
519
520 new->group = new_grp;
521 #if MP_FLAVOUR == MP_FLAVOUR_GMP
522 mpz_init_set(new_grp->p, clone_grp->p);
523 mpz_init_set(new_grp->gen, clone_grp->gen);
524
525 mpz_init(new_grp->a);
526 mpz_init(new_grp->b);
527 mpz_init(new_grp->c);
528 #elif MP_FLAVOUR == MP_FLAVOUR_OPENSSL
529 new_grp->p = BN_dup(clone_grp->p);
530 new_grp->gen = BN_dup(clone_grp->gen);
531
532 new_grp->a = BN_new();
533 new_grp->b = BN_new();
534 new_grp->c = BN_new();
535 #endif
536
537 new->gen = new_grp->gen;
538 new->a = new_grp->a;
539 new->b = new_grp->b;
540 new->c = new_grp->c;
541
542 return new;
543 }
544
545 void
546 modp_free(struct group *old)
547 {
548 struct modp_group *grp = old->group;
549
550 #if MP_FLAVOUR == MP_FLAVOUR_GMP
551 mpz_clear(grp->p);
552 mpz_clear(grp->gen);
553 mpz_clear(grp->a);
554 mpz_clear(grp->b);
555 mpz_clear(grp->c);
556 #elif MP_FLAVOUR == MP_FLAVOUR_OPENSSL
557 BN_clear_free(grp->p);
558 BN_clear_free(grp->gen);
559 BN_clear_free(grp->a);
560 BN_clear_free(grp->b);
561 BN_clear_free(grp->c);
562 #endif
563
564 free(grp);
565 }
566
567 void
568 modp_init(struct group *group)
569 {
570 struct modp_dscr *dscr = (struct modp_dscr *)group->group;
571 struct modp_group *grp;
572
573 grp = malloc(sizeof *grp);
574 if (!grp)
575 log_fatal("modp_init: malloc (%lu) failed",
576 (unsigned long)sizeof *grp);
577
578 group->bits = dscr->bits;
579
580 #if MP_FLAVOUR == MP_FLAVOUR_GMP
581 mpz_init_set_str(grp->p, dscr->prime, 0);
582 mpz_init_set_str(grp->gen, dscr->gen, 0);
583
584 mpz_init(grp->a);
585 mpz_init(grp->b);
586 mpz_init(grp->c);
587 #elif MP_FLAVOUR == MP_FLAVOUR_OPENSSL
588 grp->p = BN_new();
589 BN_hex2bn(&grp->p, dscr->prime + 2);
590 grp->gen = BN_new();
591 BN_hex2bn(&grp->gen, dscr->gen + 2);
592
593 grp->a = BN_new();
594 grp->b = BN_new();
595 grp->c = BN_new();
596 #endif
597
598 group->gen = grp->gen;
599 group->a = grp->a;
600 group->b = grp->b;
601 group->c = grp->c;
602
603 group->group = grp;
604 }
605
606 #ifdef USE_EC
607 struct group *
608 ec2n_clone(struct group *new, struct group *clone)
609 {
610 struct ec2n_group *new_grp, *clone_grp = clone->group;
611
612 new_grp = malloc(sizeof *new_grp);
613 if (!new_grp) {
614 log_error("ec2n_clone: malloc (%lu) failed",
615 (unsigned long)sizeof *new_grp);
616 free(new);
617 return 0;
618 }
619 memcpy(new, clone, sizeof(struct group));
620
621 new->group = new_grp;
622 ec2ng_init(new_grp->grp);
623 ec2np_init(new_grp->gen);
624 ec2np_init(new_grp->a);
625 ec2np_init(new_grp->b);
626 ec2np_init(new_grp->c);
627
628 if (ec2ng_set(new_grp->grp, clone_grp->grp))
629 goto fail;
630 if (ec2np_set(new_grp->gen, clone_grp->gen))
631 goto fail;
632
633 new->gen = new_grp->gen;
634 new->a = new_grp->a;
635 new->b = new_grp->b;
636 new->c = new_grp->c;
637 new->d = ((ec2np_ptr) new->a)->x;
638
639 return new;
640
641 fail:
642 ec2ng_clear(new_grp->grp);
643 ec2np_clear(new_grp->gen);
644 ec2np_clear(new_grp->a);
645 ec2np_clear(new_grp->b);
646 ec2np_clear(new_grp->c);
647 free(new_grp);
648 free(new);
649 return 0;
650 }
651
652 void
653 ec2n_free(struct group *old)
654 {
655 struct ec2n_group *grp = old->group;
656
657 ec2ng_clear(grp->grp);
658 ec2np_clear(grp->gen);
659 ec2np_clear(grp->a);
660 ec2np_clear(grp->b);
661 ec2np_clear(grp->c);
662
663 free(grp);
664 }
665
666 void
667 ec2n_init(struct group *group)
668 {
669 struct ec2n_dscr *dscr = (struct ec2n_dscr *)group->group;
670 struct ec2n_group *grp;
671
672 grp = malloc(sizeof *grp);
673 if (!grp)
674 log_fatal("ec2n_init: malloc (%lu) failed",
675 (unsigned long)sizeof *grp);
676
677 group->bits = dscr->bits;
678
679 ec2ng_init(grp->grp);
680 ec2np_init(grp->gen);
681 ec2np_init(grp->a);
682 ec2np_init(grp->b);
683 ec2np_init(grp->c);
684
685 if (ec2ng_set_p_str(grp->grp, dscr->polynomial))
686 goto fail;
687 grp->grp->p->bits = b2n_sigbit(grp->grp->p);
688 if (ec2ng_set_a_str(grp->grp, dscr->a))
689 goto fail;
690 if (ec2ng_set_b_str(grp->grp, dscr->b))
691 goto fail;
692
693 if (ec2np_set_x_str(grp->gen, dscr->gen_x))
694 goto fail;
695 if (ec2np_find_y(grp->gen, grp->grp))
696 goto fail;
697
698 /* Sanity check */
699 if (!ec2np_ison(grp->gen, grp->grp))
700 log_fatal("ec2n_init: generator is not on curve");
701
702 group->gen = grp->gen;
703 group->a = grp->a;
704 group->b = grp->b;
705 group->c = grp->c;
706 group->d = ((ec2np_ptr) group->a)->x;
707
708 group->group = grp;
709 return;
710
711 fail:
712 log_fatal("ec2n_init: general failure");
713 }
714 #endif /* USE_EC */
715
716 int
717 modp_getlen(struct group *group)
718 {
719 struct modp_group *grp = (struct modp_group *)group->group;
720
721 return mpz_sizeinoctets(grp->p);
722 }
723
724 void
725 modp_getraw(struct group *grp, math_mp_t v, u_int8_t *d)
726 {
727 mpz_getraw(d, v, grp->getlen(grp));
728 }
729
730 int
731 modp_setraw(struct group *grp, math_mp_t d, u_int8_t *s, int l)
732 {
733 mpz_setraw(d, s, l);
734 return 0;
735 }
736
737 int
738 modp_setrandom(struct group *grp, math_mp_t d)
739 {
740 int i, l = grp->getlen(grp);
741 u_int32_t tmp = 0;
742
743 #if MP_FLAVOUR == MP_FLAVOUR_GMP
744 mpz_set_ui(d, 0);
745 #elif MP_FLAVOUR == MP_FLAVOUR_OPENSSL
746 BN_set_word(d, 0);
747 #endif
748
749 for (i = 0; i < l; i++) {
750 if (i % 4)
751 tmp = sysdep_random();
752
753 #if MP_FLAVOUR == MP_FLAVOUR_GMP
754 mpz_mul_2exp(d, d, 8);
755 mpz_add_ui(d, d, tmp & 0xFF);
756 #elif MP_FLAVOUR == MP_FLAVOUR_OPENSSL
757 BN_lshift(d, d, 8);
758 BN_add_word(d, tmp & 0xFF);
759 #endif
760 tmp >>= 8;
761 }
762 return 0;
763 }
764
765 int
766 modp_operation(struct group *group, math_mp_t d, math_mp_t a, math_mp_t e)
767 {
768 struct modp_group *grp = (struct modp_group *)group->group;
769
770 #if MP_FLAVOUR == MP_FLAVOUR_GMP
771 mpz_powm(d, a, e, grp->p);
772 #elif MP_FLAVOUR == MP_FLAVOUR_OPENSSL
773 BN_CTX *ctx = BN_CTX_new();
774 BN_mod_exp(d, a, e, grp->p, ctx);
775 BN_CTX_free(ctx);
776 #endif
777 return 0;
778 }
779
780 #ifdef USE_EC
781 int
782 ec2n_getlen(struct group *group)
783 {
784 struct ec2n_group *grp = (struct ec2n_group *)group->group;
785 int bits = b2n_sigbit(grp->grp->p) - 1;
786
787 return (7 + bits) >> 3;
788 }
789
790 void
791 ec2n_getraw(struct group *group, ec2np_ptr xo, u_int8_t *e)
792 {
793 struct ec2n_group *grp = (struct ec2n_group *) group->group;
794 int chunks, bytes, i, j;
795 b2n_ptr x = xo->x;
796 CHUNK_TYPE tmp;
797
798 bytes = b2n_sigbit(grp->grp->p) - 1;
799 chunks = (CHUNK_MASK + bytes) >> CHUNK_SHIFTS;
800 bytes = ((7 + (bytes & CHUNK_MASK)) >> 3);
801
802 for (i = chunks - 1; i >= 0; i--) {
803 tmp = (i >= x->chunks ? 0 : x->limp[i]);
804 for (j = (i == chunks - 1 ? bytes : CHUNK_BYTES) - 1; j >= 0;
805 j--) {
806 e[j] = tmp & 0xff;
807 tmp >>= 8;
808 }
809 e += (i == chunks - 1 ? bytes : CHUNK_BYTES);
810 }
811 }
812
813 int
814 ec2n_setraw(struct group *grp, ec2np_ptr out, u_int8_t *s, int l)
815 {
816 int len, bytes, i, j;
817 b2n_ptr outx = out->x;
818 CHUNK_TYPE tmp;
819
820 len = (CHUNK_BYTES - 1 + l) / CHUNK_BYTES;
821 if (b2n_resize(outx, len))
822 return -1;
823
824 bytes = ((l - 1) % CHUNK_BYTES) + 1;
825
826 for (i = len - 1; i >= 0; i--) {
827 tmp = 0;
828 for (j = (i == len - 1 ? bytes : CHUNK_BYTES); j > 0; j--) {
829 tmp <<= 8;
830 tmp |= *s++;
831 }
832 outx->limp[i] = tmp;
833 }
834 return 0;
835 }
836
837 int
838 ec2n_setrandom(struct group *group, ec2np_ptr x)
839 {
840 b2n_ptr d = x->x;
841 struct ec2n_group *grp = (struct ec2n_group *) group->group;
842
843 return b2n_random(d, b2n_sigbit(grp->grp->p) - 1);
844 }
845
846 /*
847 * This is an attempt at operation abstraction. It can happen
848 * that we need to initialize the y variable for the operation
849 * to proceed correctly. When this is the case operation has
850 * to supply the variable 'a' with the chunks of the Y cooridnate
851 * set to zero.
852 */
853 int
854 ec2n_operation(struct group *grp, ec2np_ptr d, ec2np_ptr a, ec2np_ptr e)
855 {
856 b2n_ptr ex = e->x;
857 struct ec2n_group *group = (struct ec2n_group *)grp->group;
858
859 if (a->y->chunks == 0)
860 if (ec2np_find_y(a, group->grp))
861 return -1;
862
863 return ec2np_mul(d, a, ex, group->grp);
864 }
865 #endif /* USE_EC */
Implementation of SATP