Mercurial > dropbear

comparison libtomcrypt/src/pk/dh/dh_sys.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
12 /**
13 @file dh_sys.c
14 DH Crypto, Tom St Denis
15 */
16
17 /**
18 Encrypt a short symmetric key with a public DH key
19 @param in The symmetric key to encrypt
20 @param inlen The length of the key (octets)
21 @param out [out] The ciphertext
22 @param outlen [in/out] The max size and resulting size of the ciphertext
23 @param prng An active PRNG state
24 @param wprng The index of the PRNG desired
25 @param hash The index of the hash desired (must produce a digest of size >= the size of the plaintext)
26 @param key The public key you wish to encrypt with.
27 @return CRYPT_OK if successful
28 */
29 int dh_encrypt_key(const unsigned char *in, unsigned long inlen,
30 unsigned char *out, unsigned long *outlen,
31 prng_state *prng, int wprng, int hash,
32 dh_key *key)
33 {
34 unsigned char *pub_expt, *dh_shared, *skey;
35 dh_key pubkey;
36 unsigned long x, y, z, hashsize, pubkeysize;
37 int err;
38
39 LTC_ARGCHK(in != NULL);
40 LTC_ARGCHK(out != NULL);
41 LTC_ARGCHK(outlen != NULL);
42 LTC_ARGCHK(key != NULL);
43
44 /* check that wprng/hash are not invalid */
45 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
46 return err;
47 }
48
49 if ((err = hash_is_valid(hash)) != CRYPT_OK) {
50 return err;
51 }
52
53 if (inlen > hash_descriptor[hash].hashsize) {
54 return CRYPT_INVALID_HASH;
55 }
56
57 /* allocate memory */
58 pub_expt = XMALLOC(DH_BUF_SIZE);
59 dh_shared = XMALLOC(DH_BUF_SIZE);
60 skey = XMALLOC(MAXBLOCKSIZE);
61 if (pub_expt == NULL || dh_shared == NULL || skey == NULL) {
62 if (pub_expt != NULL) {
63 XFREE(pub_expt);
64 }
65 if (dh_shared != NULL) {
66 XFREE(dh_shared);
67 }
68 if (skey != NULL) {
69 XFREE(skey);
70 }
71 return CRYPT_MEM;
72 }
73
74 /* make a random key and export the public copy */
75 if ((err = dh_make_key(prng, wprng, dh_get_size(key), &pubkey)) != CRYPT_OK) {
76 goto LBL_ERR;
77 }
78
79 pubkeysize = DH_BUF_SIZE;
80 if ((err = dh_export(pub_expt, &pubkeysize, PK_PUBLIC, &pubkey)) != CRYPT_OK) {
81 dh_free(&pubkey);
82 goto LBL_ERR;
83 }
84
85 /* now check if the out buffer is big enough */
86 if (*outlen < (1 + 4 + 4 + PACKET_SIZE + pubkeysize + inlen)) {
87 dh_free(&pubkey);
88 err = CRYPT_BUFFER_OVERFLOW;
89 goto LBL_ERR;
90 }
91
92 /* make random key */
93 hashsize = hash_descriptor[hash].hashsize;
94
95 x = DH_BUF_SIZE;
96 if ((err = dh_shared_secret(&pubkey, key, dh_shared, &x)) != CRYPT_OK) {
97 dh_free(&pubkey);
98 goto LBL_ERR;
99 }
100 dh_free(&pubkey);
101
102 z = MAXBLOCKSIZE;
103 if ((err = hash_memory(hash, dh_shared, x, skey, &z)) != CRYPT_OK) {
104 goto LBL_ERR;
105 }
106
107 /* store header */
108 packet_store_header(out, PACKET_SECT_DH, PACKET_SUB_ENC_KEY);
109
110 /* output header */
111 y = PACKET_SIZE;
112
113 /* size of hash name and the name itself */
114 out[y++] = hash_descriptor[hash].ID;
115
116 /* length of DH pubkey and the key itself */
117 STORE32L(pubkeysize, out+y);
118 y += 4;
119 for (x = 0; x < pubkeysize; x++, y++) {
120 out[y] = pub_expt[x];
121 }
122
123 /* Store the encrypted key */
124 STORE32L(inlen, out+y);
125 y += 4;
126
127 for (x = 0; x < inlen; x++, y++) {
128 out[y] = skey[x] ^ in[x];
129 }
130 *outlen = y;
131
132 err = CRYPT_OK;
133 LBL_ERR:
134 #ifdef LTC_CLEAN_STACK
135 /* clean up */
136 zeromem(pub_expt, DH_BUF_SIZE);
137 zeromem(dh_shared, DH_BUF_SIZE);
138 zeromem(skey, MAXBLOCKSIZE);
139 #endif
140 XFREE(skey);
141 XFREE(dh_shared);
142 XFREE(pub_expt);
143
144 return err;
145 }
146
147 /**
148 Decrypt a DH encrypted symmetric key
149 @param in The DH encrypted packet
150 @param inlen The length of the DH encrypted packet
151 @param out The plaintext
152 @param outlen [in/out] The max size and resulting size of the plaintext
153 @param key The private DH key corresponding to the public key that encrypted the plaintext
154 @return CRYPT_OK if successful
155 */
156 int dh_decrypt_key(const unsigned char *in, unsigned long inlen,
157 unsigned char *out, unsigned long *outlen,
158 dh_key *key)
159 {
160 unsigned char *shared_secret, *skey;
161 unsigned long x, y, z, hashsize, keysize;
162 int hash, err;
163 dh_key pubkey;
164
165 LTC_ARGCHK(in != NULL);
166 LTC_ARGCHK(out != NULL);
167 LTC_ARGCHK(outlen != NULL);
168 LTC_ARGCHK(key != NULL);
169
170 /* right key type? */
171 if (key->type != PK_PRIVATE) {
172 return CRYPT_PK_NOT_PRIVATE;
173 }
174
175 /* allocate ram */
176 shared_secret = XMALLOC(DH_BUF_SIZE);
177 skey = XMALLOC(MAXBLOCKSIZE);
178 if (shared_secret == NULL || skey == NULL) {
179 if (shared_secret != NULL) {
180 XFREE(shared_secret);
181 }
182 if (skey != NULL) {
183 XFREE(skey);
184 }
185 return CRYPT_MEM;
186 }
187
188 /* check if initial header should fit */
189 if (inlen < PACKET_SIZE+1+4+4) {
190 err = CRYPT_INVALID_PACKET;
191 goto LBL_ERR;
192 } else {
193 inlen -= PACKET_SIZE+1+4+4;
194 }
195
196 /* is header correct? */
197 if ((err = packet_valid_header((unsigned char *)in, PACKET_SECT_DH, PACKET_SUB_ENC_KEY)) != CRYPT_OK) {
198 goto LBL_ERR;
199 }
200
201 /* now lets get the hash name */
202 y = PACKET_SIZE;
203 hash = find_hash_id(in[y++]);
204 if (hash == -1) {
205 err = CRYPT_INVALID_HASH;
206 goto LBL_ERR;
207 }
208
209 /* common values */
210 hashsize = hash_descriptor[hash].hashsize;
211
212 /* get public key */
213 LOAD32L(x, in+y);
214
215 /* now check if the imported key will fit */
216 if (inlen < x) {
217 err = CRYPT_INVALID_PACKET;
218 goto LBL_ERR;
219 } else {
220 inlen -= x;
221 }
222
223 y += 4;
224 if ((err = dh_import(in+y, x, &pubkey)) != CRYPT_OK) {
225 goto LBL_ERR;
226 }
227 y += x;
228
229 /* make shared key */
230 x = DH_BUF_SIZE;
231 if ((err = dh_shared_secret(key, &pubkey, shared_secret, &x)) != CRYPT_OK) {
232 dh_free(&pubkey);
233 goto LBL_ERR;
234 }
235 dh_free(&pubkey);
236
237 z = MAXBLOCKSIZE;
238 if ((err = hash_memory(hash, shared_secret, x, skey, &z)) != CRYPT_OK) {
239 goto LBL_ERR;
240 }
241
242 /* load in the encrypted key */
243 LOAD32L(keysize, in+y);
244
245 /* will the out fit as part of the input */
246 if (inlen < keysize) {
247 err = CRYPT_INVALID_PACKET;
248 goto LBL_ERR;
249 } else {
250 inlen -= keysize;
251 }
252
253 if (keysize > *outlen) {
254 err = CRYPT_BUFFER_OVERFLOW;
255 goto LBL_ERR;
256 }
257 y += 4;
258
259 *outlen = keysize;
260
261 for (x = 0; x < keysize; x++, y++) {
262 out[x] = skey[x] ^ in[y];
263 }
264
265 err = CRYPT_OK;
266 LBL_ERR:
267 #ifdef LTC_CLEAN_STACK
268 zeromem(shared_secret, DH_BUF_SIZE);
269 zeromem(skey, MAXBLOCKSIZE);
270 #endif
271
272 XFREE(skey);
273 XFREE(shared_secret);
274
275 return err;
276 }
277
278 /* perform an ElGamal Signature of a hash
279 *
280 * The math works as follows. x is the private key, M is the message to sign
281
282 1. pick a random k
283 2. compute a = g^k mod p
284 3. compute b = (M - xa)/k mod p
285 4. Send (a,b)
286
287 Now to verify with y=g^x mod p, a and b
288
289 1. compute y^a * a^b = g^(xa) * g^(k*(M-xa)/k)
290 = g^(xa + (M - xa))
291 = g^M [all mod p]
292
293 2. Compare against g^M mod p [based on input hash].
294 3. If result of #2 == result of #1 then signature valid
295 */
296
297 /**
298 Sign a message digest using a DH private key
299 @param in The data to sign
300 @param inlen The length of the input (octets)
301 @param out [out] The destination of the signature
302 @param outlen [in/out] The max size and resulting size of the output
303 @param prng An active PRNG state
304 @param wprng The index of the PRNG desired
305 @param key A private DH key
306 @return CRYPT_OK if successful
307 */
308 int dh_sign_hash(const unsigned char *in, unsigned long inlen,
309 unsigned char *out, unsigned long *outlen,
310 prng_state *prng, int wprng, dh_key *key)
311 {
312 mp_int a, b, k, m, g, p, p1, tmp;
313 unsigned char *buf;
314 unsigned long x, y;
315 int err;
316
317 LTC_ARGCHK(in != NULL);
318 LTC_ARGCHK(out != NULL);
319 LTC_ARGCHK(outlen != NULL);
320 LTC_ARGCHK(key != NULL);
321
322 /* check parameters */
323 if (key->type != PK_PRIVATE) {
324 return CRYPT_PK_NOT_PRIVATE;
325 }
326
327 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
328 return err;
329 }
330
331 /* is the IDX valid ? */
332 if (is_valid_idx(key->idx) != 1) {
333 return CRYPT_PK_INVALID_TYPE;
334 }
335
336 /* allocate ram for buf */
337 buf = XMALLOC(520);
338
339 /* make up a random value k,
340 * since the order of the group is prime
341 * we need not check if gcd(k, r) is 1
342 */
343 if (prng_descriptor[wprng].read(buf, sets[key->idx].size, prng) !=
344 (unsigned long)(sets[key->idx].size)) {
345 err = CRYPT_ERROR_READPRNG;
346 goto LBL_ERR;
347 }
348
349 /* init bignums */
350 if ((err = mp_init_multi(&a, &b, &k, &m, &p, &g, &p1, &tmp, NULL)) != MP_OKAY) {
351 err = mpi_to_ltc_error(err);
352 goto LBL_ERR;
353 }
354
355 /* load k and m */
356 if ((err = mp_read_unsigned_bin(&m, (unsigned char *)in, inlen)) != MP_OKAY) { goto error; }
357 if ((err = mp_read_unsigned_bin(&k, buf, sets[key->idx].size)) != MP_OKAY) { goto error; }
358
359 /* load g, p and p1 */
360 if ((err = mp_read_radix(&g, sets[key->idx].base, 64)) != MP_OKAY) { goto error; }
361 if ((err = mp_read_radix(&p, sets[key->idx].prime, 64)) != MP_OKAY) { goto error; }
362 if ((err = mp_sub_d(&p, 1, &p1)) != MP_OKAY) { goto error; }
363 if ((err = mp_div_2(&p1, &p1)) != MP_OKAY) { goto error; } /* p1 = (p-1)/2 */
364
365 /* now get a = g^k mod p */
366 if ((err = mp_exptmod(&g, &k, &p, &a)) != MP_OKAY) { goto error; }
367
368 /* now find M = xa + kb mod p1 or just b = (M - xa)/k mod p1 */
369 if ((err = mp_invmod(&k, &p1, &k)) != MP_OKAY) { goto error; } /* k = 1/k mod p1 */
370 if ((err = mp_mulmod(&a, &key->x, &p1, &tmp)) != MP_OKAY) { goto error; } /* tmp = xa */
371 if ((err = mp_submod(&m, &tmp, &p1, &tmp)) != MP_OKAY) { goto error; } /* tmp = M - xa */
372 if ((err = mp_mulmod(&k, &tmp, &p1, &b)) != MP_OKAY) { goto error; } /* b = (M - xa)/k */
373
374 /* check for overflow */
375 if ((unsigned long)(PACKET_SIZE + 4 + 4 + mp_unsigned_bin_size(&a) + mp_unsigned_bin_size(&b)) > *outlen) {
376 err = CRYPT_BUFFER_OVERFLOW;
377 goto LBL_ERR;
378 }
379
380 /* store header */
381 y = PACKET_SIZE;
382
383 /* now store them both (a,b) */
384 x = (unsigned long)mp_unsigned_bin_size(&a);
385 STORE32L(x, out+y); y += 4;
386 if ((err = mp_to_unsigned_bin(&a, out+y)) != MP_OKAY) { goto error; }
387 y += x;
388
389 x = (unsigned long)mp_unsigned_bin_size(&b);
390 STORE32L(x, out+y); y += 4;
391 if ((err = mp_to_unsigned_bin(&b, out+y)) != MP_OKAY) { goto error; }
392 y += x;
393
394 /* check if size too big */
395 if (*outlen < y) {
396 err = CRYPT_BUFFER_OVERFLOW;
397 goto LBL_ERR;
398 }
399
400 /* store header */
401 packet_store_header(out, PACKET_SECT_DH, PACKET_SUB_SIGNED);
402 *outlen = y;
403
404 err = CRYPT_OK;
405 goto LBL_ERR;
406 error:
407 err = mpi_to_ltc_error(err);
408 LBL_ERR:
409 mp_clear_multi(&tmp, &p1, &g, &p, &m, &k, &b, &a, NULL);
410
411 XFREE(buf);
412
413 return err;
414 }
415
416
417 /**
418 Verify the signature given
419 @param sig The signature
420 @param siglen The length of the signature (octets)
421 @param hash The hash that was signed
422 @param hashlen The length of the hash (octets)
423 @param stat [out] Result of signature comparison, 1==valid, 0==invalid
424 @param key The public DH key that signed the hash
425 @return CRYPT_OK if succsessful (even if signature is invalid)
426 */
427 int dh_verify_hash(const unsigned char *sig, unsigned long siglen,
428 const unsigned char *hash, unsigned long hashlen,
429 int *stat, dh_key *key)
430 {
431 mp_int a, b, p, g, m, tmp;
432 unsigned long x, y;
433 int err;
434
435 LTC_ARGCHK(sig != NULL);
436 LTC_ARGCHK(hash != NULL);
437 LTC_ARGCHK(stat != NULL);
438 LTC_ARGCHK(key != NULL);
439
440 /* default to invalid */
441 *stat = 0;
442
443 /* check initial input length */
444 if (siglen < PACKET_SIZE+4+4) {
445 return CRYPT_INVALID_PACKET;
446 }
447
448 /* header ok? */
449 if ((err = packet_valid_header((unsigned char *)sig, PACKET_SECT_DH, PACKET_SUB_SIGNED)) != CRYPT_OK) {
450 return err;
451 }
452
453 /* get hash out of packet */
454 y = PACKET_SIZE;
455
456 /* init all bignums */
457 if ((err = mp_init_multi(&a, &p, &b, &g, &m, &tmp, NULL)) != MP_OKAY) {
458 return mpi_to_ltc_error(err);
459 }
460
461 /* load a and b */
462 INPUT_BIGNUM(&a, sig, x, y, siglen);
463 INPUT_BIGNUM(&b, sig, x, y, siglen);
464
465 /* load p and g */
466 if ((err = mp_read_radix(&p, sets[key->idx].prime, 64)) != MP_OKAY) { goto error1; }
467 if ((err = mp_read_radix(&g, sets[key->idx].base, 64)) != MP_OKAY) { goto error1; }
468
469 /* load m */
470 if ((err = mp_read_unsigned_bin(&m, (unsigned char *)hash, hashlen)) != MP_OKAY) { goto error1; }
471
472 /* find g^m mod p */
473 if ((err = mp_exptmod(&g, &m, &p, &m)) != MP_OKAY) { goto error1; } /* m = g^m mod p */
474
475 /* find y^a * a^b */
476 if ((err = mp_exptmod(&key->y, &a, &p, &tmp)) != MP_OKAY) { goto error1; } /* tmp = y^a mod p */
477 if ((err = mp_exptmod(&a, &b, &p, &a)) != MP_OKAY) { goto error1; } /* a = a^b mod p */
478 if ((err = mp_mulmod(&a, &tmp, &p, &a)) != MP_OKAY) { goto error1; } /* a = y^a * a^b mod p */
479
480 /* y^a * a^b == g^m ??? */
481 if (mp_cmp(&a, &m) == 0) {
482 *stat = 1;
483 }
484
485 /* clean up */
486 err = CRYPT_OK;
487 goto done;
488 error1:
489 err = mpi_to_ltc_error(err);
490 error:
491 done:
492 mp_clear_multi(&tmp, &m, &g, &p, &b, &a, NULL);
493 return err;
494 }
495
496
497 /* $Source: /cvs/libtom/libtomcrypt/src/pk/dh/dh_sys.c,v $ */
498 /* $Revision: 1.3 $ */
499 /* $Date: 2005/05/05 14:35:59 $ */