Mercurial > dropbear

comparison src/pk/dh/dh.c @ 191:1c15b283127b libtomcrypt-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import of libtomcrypt 1.02 with manual path rename rearrangement etc
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 13:23:02 +0000
parents
children 39d5d58461d6
comparison
equal deleted inserted replaced
143:5d99163f7e32 191:1c15b283127b
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