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

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
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