Mercurial > dropbear

comparison libtomcrypt/src/pk/dh/dh.c @ 285:1b9e69c058d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3) to branch 'au.asn.ucc.matt.dropbear' (head fdf4a7a3b97ae5046139915de7e40399cceb2c01)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 08 Mar 2006 13:23:58 +0000
parents
children
comparison
equal deleted inserted replaced
281:997e6f7dc01e 285:1b9e69c058d2
1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
2 *
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
5 *
6 * The library is free for all purposes without any express
7 * guarantee it works.
8 *
9 * Tom St Denis, [email protected], http://libtomcrypt.org
10 */
11 #include "tomcrypt.h"
12
13 /**
14 @file dh.c
15 DH crypto, Tom St Denis
16 */
17
18 #ifdef MDH
19
20 /* max export size we'll encounter (smaller than this but lets round up a bit) */
21 #define DH_BUF_SIZE 1200
22
23 /* This holds the key settings. ***MUST*** be organized by size from smallest to largest. */
24 static const struct {
25 int size;
26 char *name, *base, *prime;
27 } sets[] = {
28 #ifdef DH768
29 {
30 96,
31 "DH-768",
32 "4",
33 "F///////////////////////////////////////////////////////////"
34 "////////////////////////////////////////////////////////////"
35 "//////m3wvV"
36 },
37 #endif
38 #ifdef DH1024
39 {
40 128,
41 "DH-1024",
42 "4",
43 "F///////////////////////////////////////////////////////////"
44 "////////////////////////////////////////////////////////////"
45 "////////////////////////////////////////////////m3C47"
46 },
47 #endif
48 #ifdef DH1280
49 {
50 160,
51 "DH-1280",
52 "4",
53 "F///////////////////////////////////////////////////////////"
54 "////////////////////////////////////////////////////////////"
55 "////////////////////////////////////////////////////////////"
56 "//////////////////////////////m4kSN"
57 },
58 #endif
59 #ifdef DH1536
60 {
61 192,
62 "DH-1536",
63 "4",
64 "F///////////////////////////////////////////////////////////"
65 "////////////////////////////////////////////////////////////"
66 "////////////////////////////////////////////////////////////"
67 "////////////////////////////////////////////////////////////"
68 "////////////m5uqd"
69 },
70 #endif
71 #ifdef DH1792
72 {
73 224,
74 "DH-1792",
75 "4",
76 "F///////////////////////////////////////////////////////////"
77 "////////////////////////////////////////////////////////////"
78 "////////////////////////////////////////////////////////////"
79 "////////////////////////////////////////////////////////////"
80 "//////////////////////////////////////////////////////mT/sd"
81 },
82 #endif
83 #ifdef DH2048
84 {
85 256,
86 "DH-2048",
87 "4",
88 "3///////////////////////////////////////////////////////////"
89 "////////////////////////////////////////////////////////////"
90 "////////////////////////////////////////////////////////////"
91 "////////////////////////////////////////////////////////////"
92 "////////////////////////////////////////////////////////////"
93 "/////////////////////////////////////////m8MPh"
94 },
95 #endif
96 #ifdef DH2560
97 {
98 320,
99 "DH-2560",
100 "4",
101 "3///////////////////////////////////////////////////////////"
102 "////////////////////////////////////////////////////////////"
103 "////////////////////////////////////////////////////////////"
104 "////////////////////////////////////////////////////////////"
105 "////////////////////////////////////////////////////////////"
106 "////////////////////////////////////////////////////////////"
107 "////////////////////////////////////////////////////////////"
108 "/////mKFpF"
109 },
110 #endif
111 #ifdef DH3072
112 {
113 384,
114 "DH-3072",
115 "4",
116 "3///////////////////////////////////////////////////////////"
117 "////////////////////////////////////////////////////////////"
118 "////////////////////////////////////////////////////////////"
119 "////////////////////////////////////////////////////////////"
120 "////////////////////////////////////////////////////////////"
121 "////////////////////////////////////////////////////////////"
122 "////////////////////////////////////////////////////////////"
123 "////////////////////////////////////////////////////////////"
124 "/////////////////////////////m32nN"
125 },
126 #endif
127 #ifdef DH4096
128 {
129 512,
130 "DH-4096",
131 "4",
132 "////////////////////////////////////////////////////////////"
133 "////////////////////////////////////////////////////////////"
134 "////////////////////////////////////////////////////////////"
135 "////////////////////////////////////////////////////////////"
136 "////////////////////////////////////////////////////////////"
137 "////////////////////////////////////////////////////////////"
138 "////////////////////////////////////////////////////////////"
139 "////////////////////////////////////////////////////////////"
140 "////////////////////////////////////////////////////////////"
141 "////////////////////////////////////////////////////////////"
142 "////////////////////////////////////////////////////////////"
143 "/////////////////////m8pOF"
144 },
145 #endif
146 {
147 0,
148 NULL,
149 NULL,
150 NULL
151 }
152 };
153
154 static int is_valid_idx(int n)
155 {
156 int x;
157
158 for (x = 0; sets[x].size; x++);
159 if ((n < 0) || (n >= x)) {
160 return 0;
161 }
162 return 1;
163 }
164
165 /**
166 Test the DH sub-system (can take a while)
167 @return CRYPT_OK if successful
168 */
169 int dh_test(void)
170 {
171 mp_int p, g, tmp;
172 int x, err, primality;
173
174 if ((err = mp_init_multi(&p, &g, &tmp, NULL)) != MP_OKAY) { goto error; }
175
176 for (x = 0; sets[x].size != 0; x++) {
177 #if 0
178 printf("dh_test():testing size %d-bits\n", sets[x].size * 8);
179 #endif
180 if ((err = mp_read_radix(&g,(char *)sets[x].base, 64)) != MP_OKAY) { goto error; }
181 if ((err = mp_read_radix(&p,(char *)sets[x].prime, 64)) != MP_OKAY) { goto error; }
182
183 /* ensure p is prime */
184 if ((err = is_prime(&p, &primality)) != CRYPT_OK) { goto done; }
185 if (primality == 0) {
186 err = CRYPT_FAIL_TESTVECTOR;
187 goto done;
188 }
189
190 if ((err = mp_sub_d(&p, 1, &tmp)) != MP_OKAY) { goto error; }
191 if ((err = mp_div_2(&tmp, &tmp)) != MP_OKAY) { goto error; }
192
193 /* ensure (p-1)/2 is prime */
194 if ((err = is_prime(&tmp, &primality)) != CRYPT_OK) { goto done; }
195 if (primality == 0) {
196 err = CRYPT_FAIL_TESTVECTOR;
197 goto done;
198 }
199
200 /* now see if g^((p-1)/2) mod p is in fact 1 */
201 if ((err = mp_exptmod(&g, &tmp, &p, &tmp)) != MP_OKAY) { goto error; }
202 if (mp_cmp_d(&tmp, 1)) {
203 err = CRYPT_FAIL_TESTVECTOR;
204 goto done;
205 }
206 }
207 err = CRYPT_OK;
208 goto done;
209 error:
210 err = mpi_to_ltc_error(err);
211 done:
212 mp_clear_multi(&tmp, &g, &p, NULL);
213 return err;
214 }
215
216 /**
217 Get the min and max DH key sizes (octets)
218 @param low [out] The smallest key size supported
219 @param high [out] The largest key size supported
220 */
221 void dh_sizes(int *low, int *high)
222 {
223 int x;
224 LTC_ARGCHK(low != NULL);
225 LTC_ARGCHK(high != NULL);
226 *low = INT_MAX;
227 *high = 0;
228 for (x = 0; sets[x].size != 0; x++) {
229 if (*low > sets[x].size) *low = sets[x].size;
230 if (*high < sets[x].size) *high = sets[x].size;
231 }
232 }
233
234 /**
235 Returns the key size of a given DH key (octets)
236 @param key The DH key to get the size of
237 @return The size if valid or INT_MAX if not
238 */
239 int dh_get_size(dh_key *key)
240 {
241 LTC_ARGCHK(key != NULL);
242 if (is_valid_idx(key->idx) == 1) {
243 return sets[key->idx].size;
244 } else {
245 return INT_MAX; /* large value that would cause dh_make_key() to fail */
246 }
247 }
248
249 /**
250 Make a DH key [private key pair]
251 @param prng An active PRNG state
252 @param wprng The index for the PRNG you desire to use
253 @param keysize The key size (octets) desired
254 @param key [out] Where the newly created DH key will be stored
255 @return CRYPT_OK if successful, note: on error all allocated memory will be freed automatically.
256 */
257 int dh_make_key(prng_state *prng, int wprng, int keysize, dh_key *key)
258 {
259 unsigned char *buf;
260 unsigned long x;
261 mp_int p, g;
262 int err;
263
264 LTC_ARGCHK(key != NULL);
265
266 /* good prng? */
267 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
268 return err;
269 }
270
271 /* find key size */
272 for (x = 0; (keysize > sets[x].size) && (sets[x].size != 0); x++);
273 #ifdef FAST_PK
274 keysize = MIN(sets[x].size, 32);
275 #else
276 keysize = sets[x].size;
277 #endif
278
279 if (sets[x].size == 0) {
280 return CRYPT_INVALID_KEYSIZE;
281 }
282 key->idx = x;
283
284 /* allocate buffer */
285 buf = XMALLOC(keysize);
286 if (buf == NULL) {
287 return CRYPT_MEM;
288 }
289
290 /* make up random string */
291 if (prng_descriptor[wprng].read(buf, keysize, prng) != (unsigned long)keysize) {
292 err = CRYPT_ERROR_READPRNG;
293 goto error2;
294 }
295
296 /* init parameters */
297 if ((err = mp_init_multi(&g, &p, &key->x, &key->y, NULL)) != MP_OKAY) {
298 goto error;
299 }
300 if ((err = mp_read_radix(&g, sets[key->idx].base, 64)) != MP_OKAY) { goto error; }
301 if ((err = mp_read_radix(&p, sets[key->idx].prime, 64)) != MP_OKAY) { goto error; }
302
303 /* load the x value */
304 if ((err = mp_read_unsigned_bin(&key->x, buf, keysize)) != MP_OKAY) { goto error; }
305 if ((err = mp_exptmod(&g, &key->x, &p, &key->y)) != MP_OKAY) { goto error; }
306 key->type = PK_PRIVATE;
307
308 if ((err = mp_shrink(&key->x)) != MP_OKAY) { goto error; }
309 if ((err = mp_shrink(&key->y)) != MP_OKAY) { goto error; }
310
311 /* free up ram */
312 err = CRYPT_OK;
313 goto done;
314 error:
315 err = mpi_to_ltc_error(err);
316 error2:
317 mp_clear_multi(&key->x, &key->y, NULL);
318 done:
319 #ifdef LTC_CLEAN_STACK
320 zeromem(buf, keysize);
321 #endif
322 mp_clear_multi(&p, &g, NULL);
323 XFREE(buf);
324 return err;
325 }
326
327 /**
328 Free the allocated ram for a DH key
329 @param key The key which you wish to free
330 */
331 void dh_free(dh_key *key)
332 {
333 LTC_ARGCHK(key != NULL);
334 mp_clear_multi(&key->x, &key->y, NULL);
335 }
336
337 /**
338 Export a DH key to a binary packet
339 @param out [out] The destination for the key
340 @param outlen [in/out] The max size and resulting size of the DH key
341 @param type Which type of key (PK_PRIVATE or PK_PUBLIC)
342 @param key The key you wish to export
343 @return CRYPT_OK if successful
344 */
345 int dh_export(unsigned char *out, unsigned long *outlen, int type, dh_key *key)
346 {
347 unsigned long y, z;
348 int err;
349
350 LTC_ARGCHK(out != NULL);
351 LTC_ARGCHK(outlen != NULL);
352 LTC_ARGCHK(key != NULL);
353
354 /* can we store the static header? */
355 if (*outlen < (PACKET_SIZE + 2)) {
356 return CRYPT_BUFFER_OVERFLOW;
357 }
358
359 if (type == PK_PRIVATE && key->type != PK_PRIVATE) {
360 return CRYPT_PK_NOT_PRIVATE;
361 }
362
363 /* header */
364 y = PACKET_SIZE;
365
366 /* header */
367 out[y++] = type;
368 out[y++] = (unsigned char)(sets[key->idx].size / 8);
369
370 /* export y */
371 OUTPUT_BIGNUM(&key->y, out, y, z);
372
373 if (type == PK_PRIVATE) {
374 /* export x */
375 OUTPUT_BIGNUM(&key->x, out, y, z);
376 }
377
378 /* store header */
379 packet_store_header(out, PACKET_SECT_DH, PACKET_SUB_KEY);
380
381 /* store len */
382 *outlen = y;
383 return CRYPT_OK;
384 }
385
386 /**
387 Import a DH key from a binary packet
388 @param in The packet to read
389 @param inlen The length of the input packet
390 @param key [out] Where to import the key to
391 @return CRYPT_OK if successful, on error all allocated memory is freed automatically
392 */
393 int dh_import(const unsigned char *in, unsigned long inlen, dh_key *key)
394 {
395 unsigned long x, y, s;
396 int err;
397
398 LTC_ARGCHK(in != NULL);
399 LTC_ARGCHK(key != NULL);
400
401 /* make sure valid length */
402 if ((2+PACKET_SIZE) > inlen) {
403 return CRYPT_INVALID_PACKET;
404 }
405
406 /* check type byte */
407 if ((err = packet_valid_header((unsigned char *)in, PACKET_SECT_DH, PACKET_SUB_KEY)) != CRYPT_OK) {
408 return err;
409 }
410
411 /* init */
412 if ((err = mp_init_multi(&key->x, &key->y, NULL)) != MP_OKAY) {
413 return mpi_to_ltc_error(err);
414 }
415
416 /* advance past packet header */
417 y = PACKET_SIZE;
418
419 /* key type, e.g. private, public */
420 key->type = (int)in[y++];
421
422 /* key size in bytes */
423 s = (unsigned long)in[y++] * 8;
424
425 for (x = 0; (s > (unsigned long)sets[x].size) && (sets[x].size != 0); x++);
426 if (sets[x].size == 0) {
427 err = CRYPT_INVALID_KEYSIZE;
428 goto error;
429 }
430 key->idx = (int)x;
431
432 /* type check both values */
433 if ((key->type != PK_PUBLIC) && (key->type != PK_PRIVATE)) {
434 err = CRYPT_PK_TYPE_MISMATCH;
435 goto error;
436 }
437
438 /* is the key idx valid? */
439 if (is_valid_idx(key->idx) != 1) {
440 err = CRYPT_PK_TYPE_MISMATCH;
441 goto error;
442 }
443
444 /* load public value g^x mod p*/
445 INPUT_BIGNUM(&key->y, in, x, y, inlen);
446
447 if (key->type == PK_PRIVATE) {
448 INPUT_BIGNUM(&key->x, in, x, y, inlen);
449 }
450
451 /* eliminate private key if public */
452 if (key->type == PK_PUBLIC) {
453 mp_clear(&key->x);
454 }
455
456 return CRYPT_OK;
457 error:
458 mp_clear_multi(&key->y, &key->x, NULL);
459 return err;
460 }
461
462 /**
463 Create a DH shared secret.
464 @param private_key The private DH key in the pair
465 @param public_key The public DH key in the pair
466 @param out [out] The destination of the shared data
467 @param outlen [in/out] The max size and resulting size of the shared data.
468 @return CRYPT_OK if successful
469 */
470 int dh_shared_secret(dh_key *private_key, dh_key *public_key,
471 unsigned char *out, unsigned long *outlen)
472 {
473 mp_int tmp, p;
474 unsigned long x;
475 int err;
476
477 LTC_ARGCHK(private_key != NULL);
478 LTC_ARGCHK(public_key != NULL);
479 LTC_ARGCHK(out != NULL);
480 LTC_ARGCHK(outlen != NULL);
481
482 /* types valid? */
483 if (private_key->type != PK_PRIVATE) {
484 return CRYPT_PK_NOT_PRIVATE;
485 }
486
487 /* same idx? */
488 if (private_key->idx != public_key->idx) {
489 return CRYPT_PK_TYPE_MISMATCH;
490 }
491
492 /* compute y^x mod p */
493 if ((err = mp_init_multi(&tmp, &p, NULL)) != MP_OKAY) {
494 return mpi_to_ltc_error(err);
495 }
496
497 if ((err = mp_read_radix(&p, (char *)sets[private_key->idx].prime, 64)) != MP_OKAY) { goto error; }
498 if ((err = mp_exptmod(&public_key->y, &private_key->x, &p, &tmp)) != MP_OKAY) { goto error; }
499
500 /* enough space for output? */
501 x = (unsigned long)mp_unsigned_bin_size(&tmp);
502 if (*outlen < x) {
503 err = CRYPT_BUFFER_OVERFLOW;
504 goto done;
505 }
506 if ((err = mp_to_unsigned_bin(&tmp, out)) != MP_OKAY) { goto error; }
507 *outlen = x;
508 err = CRYPT_OK;
509 goto done;
510 error:
511 err = mpi_to_ltc_error(err);
512 done:
513 mp_clear_multi(&p, &tmp, NULL);
514 return err;
515 }
516
517 #include "dh_sys.c"
518
519 #endif
520
521
522 /* $Source: /cvs/libtom/libtomcrypt/src/pk/dh/dh.c,v $ */
523 /* $Revision: 1.3 $ */
524 /* $Date: 2005/05/05 14:35:59 $ */