Mercurial > dropbear

comparison src/pk/ecc/ecc_sys.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
12 /**
13 @file ecc_sys.c
14 ECC Crypto, Tom St Denis
15 */
16
17 /**
18 Encrypt a symmetric key with ECC
19 @param in The symmetric key you want to encrypt
20 @param inlen The length of the key to encrypt (octets)
21 @param out [out] The destination for 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 you wish to use
25 @param hash The index of the hash you want to use
26 @param key The ECC key you want to encrypt to
27 @return CRYPT_OK if successful
28 */
29 int ecc_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 ecc_key *key)
33 {
34 unsigned char *pub_expt, *ecc_shared, *skey;
35 ecc_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/cipher/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 /* make a random key and export the public copy */
58 if ((err = ecc_make_key(prng, wprng, ecc_get_size(key), &pubkey)) != CRYPT_OK) {
59 return err;
60 }
61
62 pub_expt = XMALLOC(ECC_BUF_SIZE);
63 ecc_shared = XMALLOC(ECC_BUF_SIZE);
64 skey = XMALLOC(MAXBLOCKSIZE);
65 if (pub_expt == NULL || ecc_shared == NULL || skey == NULL) {
66 if (pub_expt != NULL) {
67 XFREE(pub_expt);
68 }
69 if (ecc_shared != NULL) {
70 XFREE(ecc_shared);
71 }
72 if (skey != NULL) {
73 XFREE(skey);
74 }
75 ecc_free(&pubkey);
76 return CRYPT_MEM;
77 }
78
79 pubkeysize = ECC_BUF_SIZE;
80 if ((err = ecc_export(pub_expt, &pubkeysize, PK_PUBLIC, &pubkey)) != CRYPT_OK) {
81 ecc_free(&pubkey);
82 goto LBL_ERR;
83 }
84
85 /* now check if the out buffer is big enough */
86 if (*outlen < (9 + PACKET_SIZE + pubkeysize + hash_descriptor[hash].hashsize)) {
87 ecc_free(&pubkey);
88 err = CRYPT_BUFFER_OVERFLOW;
89 goto LBL_ERR;
90 }
91
92 /* make random key */
93 hashsize = hash_descriptor[hash].hashsize;
94 x = ECC_BUF_SIZE;
95 if ((err = ecc_shared_secret(&pubkey, key, ecc_shared, &x)) != CRYPT_OK) {
96 ecc_free(&pubkey);
97 goto LBL_ERR;
98 }
99 ecc_free(&pubkey);
100 z = MAXBLOCKSIZE;
101 if ((err = hash_memory(hash, ecc_shared, x, skey, &z)) != CRYPT_OK) {
102 goto LBL_ERR;
103 }
104
105 /* store header */
106 packet_store_header(out, PACKET_SECT_ECC, PACKET_SUB_ENC_KEY);
107
108 /* output header */
109 y = PACKET_SIZE;
110
111 /* size of hash name and the name itself */
112 out[y++] = hash_descriptor[hash].ID;
113
114 /* length of ECC pubkey and the key itself */
115 STORE32L(pubkeysize, out+y);
116 y += 4;
117
118 for (x = 0; x < pubkeysize; x++, y++) {
119 out[y] = pub_expt[x];
120 }
121
122 STORE32L(inlen, out+y);
123 y += 4;
124
125 /* Encrypt/Store the encrypted key */
126 for (x = 0; x < inlen; x++, y++) {
127 out[y] = skey[x] ^ in[x];
128 }
129 *outlen = y;
130
131 err = CRYPT_OK;
132 LBL_ERR:
133 #ifdef LTC_CLEAN_STACK
134 /* clean up */
135 zeromem(pub_expt, ECC_BUF_SIZE);
136 zeromem(ecc_shared, ECC_BUF_SIZE);
137 zeromem(skey, MAXBLOCKSIZE);
138 #endif
139
140 XFREE(skey);
141 XFREE(ecc_shared);
142 XFREE(pub_expt);
143
144 return err;
145 }
146
147 /**
148 Decrypt an ECC encrypted key
149 @param in The ciphertext
150 @param inlen The length of the ciphertext (octets)
151 @param out [out] The plaintext
152 @param outlen [in/out] The max size and resulting size of the plaintext
153 @param key The corresponding private ECC key
154 @return CRYPT_OK if successful
155 */
156 int ecc_decrypt_key(const unsigned char *in, unsigned long inlen,
157 unsigned char *out, unsigned long *outlen,
158 ecc_key *key)
159 {
160 unsigned char *shared_secret, *skey;
161 unsigned long x, y, z, hashsize, keysize;
162 int hash, err;
163 ecc_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 /* correct length ? */
176 if (inlen < PACKET_SIZE+1+4+4) {
177 return CRYPT_INVALID_PACKET;
178 } else {
179 inlen -= PACKET_SIZE+1+4+4;
180 }
181
182 /* is header correct? */
183 if ((err = packet_valid_header((unsigned char *)in, PACKET_SECT_ECC, PACKET_SUB_ENC_KEY)) != CRYPT_OK) {
184 return err;
185 }
186
187 /* now lets get the hash name */
188 y = PACKET_SIZE;
189 hash = find_hash_id(in[y++]);
190 if (hash == -1) {
191 return CRYPT_INVALID_HASH;
192 }
193
194 /* common values */
195 hashsize = hash_descriptor[hash].hashsize;
196
197 /* get public key */
198 LOAD32L(x, in+y);
199 if (inlen < x) {
200 return CRYPT_INVALID_PACKET;
201 } else {
202 inlen -= x;
203 }
204 y += 4;
205 if ((err = ecc_import(in+y, x, &pubkey)) != CRYPT_OK) {
206 return err;
207 }
208 y += x;
209
210 /* allocate memory */
211 shared_secret = XMALLOC(ECC_BUF_SIZE);
212 skey = XMALLOC(MAXBLOCKSIZE);
213 if (shared_secret == NULL || skey == NULL) {
214 if (shared_secret != NULL) {
215 XFREE(shared_secret);
216 }
217 if (skey != NULL) {
218 XFREE(skey);
219 }
220 ecc_free(&pubkey);
221 return CRYPT_MEM;
222 }
223
224 /* make shared key */
225 x = ECC_BUF_SIZE;
226 if ((err = ecc_shared_secret(key, &pubkey, shared_secret, &x)) != CRYPT_OK) {
227 ecc_free(&pubkey);
228 goto LBL_ERR;
229 }
230 ecc_free(&pubkey);
231
232 z = MAXBLOCKSIZE;
233 if ((err = hash_memory(hash, shared_secret, x, skey, &z)) != CRYPT_OK) {
234 goto LBL_ERR;
235 }
236
237 LOAD32L(keysize, in+y);
238 if (inlen < keysize) {
239 err = CRYPT_INVALID_PACKET;
240 goto LBL_ERR;
241 } else {
242 inlen -= keysize;
243 }
244 y += 4;
245
246 if (*outlen < keysize) {
247 err = CRYPT_BUFFER_OVERFLOW;
248 goto LBL_ERR;
249 }
250
251 /* Decrypt the key */
252 for (x = 0; x < keysize; x++, y++) {
253 out[x] = skey[x] ^ in[y];
254 }
255
256 *outlen = keysize;
257
258 err = CRYPT_OK;
259 LBL_ERR:
260 #ifdef LTC_CLEAN_STACK
261 zeromem(shared_secret, ECC_BUF_SIZE);
262 zeromem(skey, MAXBLOCKSIZE);
263 #endif
264
265 XFREE(skey);
266 XFREE(shared_secret);
267
268 return err;
269 }
270
271 /**
272 Sign a message digest
273 @param in The message digest to sign
274 @param inlen The length of the digest
275 @param out [out] The destination for the signature
276 @param outlen [in/out] The max size and resulting size of the signature
277 @param prng An active PRNG state
278 @param wprng The index of the PRNG you wish to use
279 @param key A private ECC key
280 @return CRYPT_OK if successful
281 */
282 int ecc_sign_hash(const unsigned char *in, unsigned long inlen,
283 unsigned char *out, unsigned long *outlen,
284 prng_state *prng, int wprng, ecc_key *key)
285 {
286 ecc_key pubkey;
287 mp_int b, p;
288 unsigned char *epubkey, *er;
289 unsigned long x, y, pubkeysize, rsize;
290 int err;
291
292 LTC_ARGCHK(in != NULL);
293 LTC_ARGCHK(out != NULL);
294 LTC_ARGCHK(outlen != NULL);
295 LTC_ARGCHK(key != NULL);
296
297 /* is this a private key? */
298 if (key->type != PK_PRIVATE) {
299 return CRYPT_PK_NOT_PRIVATE;
300 }
301
302 /* is the IDX valid ? */
303 if (is_valid_idx(key->idx) != 1) {
304 return CRYPT_PK_INVALID_TYPE;
305 }
306
307 if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
308 return err;
309 }
310
311 /* make up a key and export the public copy */
312 if ((err = ecc_make_key(prng, wprng, ecc_get_size(key), &pubkey)) != CRYPT_OK) {
313 return err;
314 }
315
316 /* allocate ram */
317 epubkey = XMALLOC(ECC_BUF_SIZE);
318 er = XMALLOC(ECC_BUF_SIZE);
319 if (epubkey == NULL || er == NULL) {
320 if (epubkey != NULL) {
321 XFREE(epubkey);
322 }
323 if (er != NULL) {
324 XFREE(er);
325 }
326 ecc_free(&pubkey);
327 return CRYPT_MEM;
328 }
329
330 pubkeysize = ECC_BUF_SIZE;
331 if ((err = ecc_export(epubkey, &pubkeysize, PK_PUBLIC, &pubkey)) != CRYPT_OK) {
332 ecc_free(&pubkey);
333 goto LBL_ERR;
334 }
335
336 /* get the hash and load it as a bignum into 'b' */
337 /* init the bignums */
338 if ((err = mp_init_multi(&b, &p, NULL)) != MP_OKAY) {
339 ecc_free(&pubkey);
340 err = mpi_to_ltc_error(err);
341 goto LBL_ERR;
342 }
343 if ((err = mp_read_radix(&p, (char *)sets[key->idx].order, 64)) != MP_OKAY) { goto error; }
344 if ((err = mp_read_unsigned_bin(&b, (unsigned char *)in, (int)inlen)) != MP_OKAY) { goto error; }
345
346 /* find b = (m - x)/k */
347 if ((err = mp_invmod(&pubkey.k, &p, &pubkey.k)) != MP_OKAY) { goto error; } /* k = 1/k */
348 if ((err = mp_submod(&b, &key->k, &p, &b)) != MP_OKAY) { goto error; } /* b = m - x */
349 if ((err = mp_mulmod(&b, &pubkey.k, &p, &b)) != MP_OKAY) { goto error; } /* b = (m - x)/k */
350
351 /* export it */
352 rsize = (unsigned long)mp_unsigned_bin_size(&b);
353 if (rsize > ECC_BUF_SIZE) {
354 err = CRYPT_BUFFER_OVERFLOW;
355 goto error;
356 }
357 if ((err = mp_to_unsigned_bin(&b, er)) != MP_OKAY) { goto error; }
358
359 /* now lets check the outlen before we write */
360 if (*outlen < (12 + rsize + pubkeysize)) {
361 err = CRYPT_BUFFER_OVERFLOW;
362 goto LBL_ERR;
363 }
364
365 /* lets output */
366 y = PACKET_SIZE;
367
368 /* size of public key */
369 STORE32L(pubkeysize, out+y);
370 y += 4;
371
372 /* copy the public key */
373 for (x = 0; x < pubkeysize; x++, y++) {
374 out[y] = epubkey[x];
375 }
376
377 /* size of 'r' */
378 STORE32L(rsize, out+y);
379 y += 4;
380
381 /* copy r */
382 for (x = 0; x < rsize; x++, y++) {
383 out[y] = er[x];
384 }
385
386 /* store header */
387 packet_store_header(out, PACKET_SECT_ECC, PACKET_SUB_SIGNED);
388 *outlen = y;
389
390 /* all ok */
391 err = CRYPT_OK;
392 goto LBL_ERR;
393 error:
394 err = mpi_to_ltc_error(err);
395 LBL_ERR:
396 mp_clear_multi(&b, &p, NULL);
397 ecc_free(&pubkey);
398 #ifdef LTC_CLEAN_STACK
399 zeromem(er, ECC_BUF_SIZE);
400 zeromem(epubkey, ECC_BUF_SIZE);
401 #endif
402
403 XFREE(epubkey);
404 XFREE(er);
405
406 return err;
407 }
408
409 /* verify that mG = (bA + Y)
410 *
411 * The signatures work by making up a fresh key "a" with a public key "A". Now we want to sign so the
412 * public key Y = xG can verify it.
413 *
414 * b = (m - x)/k, A is the public key embedded and Y is the users public key [who signed it]
415 * A = kG therefore bA == ((m-x)/k)kG == (m-x)G
416 *
417 * Adding Y = xG to the bA gives us (m-x)G + xG == mG
418 *
419 * The user given only xG, kG and b cannot determine k or x which means they can't find the private key.
420 *
421 */
422
423 /**
424 Verify an ECC signature
425 @param sig The signature to verify
426 @param siglen The length of the signature (octets)
427 @param hash The hash (message digest) that was signed
428 @param hashlen The length of the hash (octets)
429 @param stat Result of signature, 1==valid, 0==invalid
430 @param key The corresponding public ECC key
431 @return CRYPT_OK if successful (even if the signature is not valid)
432 */
433 int ecc_verify_hash(const unsigned char *sig, unsigned long siglen,
434 const unsigned char *hash, unsigned long hashlen,
435 int *stat, ecc_key *key)
436 {
437 ecc_point *mG;
438 ecc_key pubkey;
439 mp_int b, p, m, mu;
440 unsigned long x, y;
441 int err;
442
443 LTC_ARGCHK(sig != NULL);
444 LTC_ARGCHK(hash != NULL);
445 LTC_ARGCHK(stat != NULL);
446 LTC_ARGCHK(key != NULL);
447
448 /* default to invalid signature */
449 *stat = 0;
450
451 if (siglen < PACKET_SIZE+4+4) {
452 return CRYPT_INVALID_PACKET;
453 } else {
454 siglen -= PACKET_SIZE+4+4;
455 }
456
457 /* is the message format correct? */
458 if ((err = packet_valid_header((unsigned char *)sig, PACKET_SECT_ECC, PACKET_SUB_SIGNED)) != CRYPT_OK) {
459 return err;
460 }
461
462 /* get hash name */
463 y = PACKET_SIZE;
464
465 /* get size of public key */
466 LOAD32L(x, sig+y);
467 if (siglen < x) {
468 return CRYPT_INVALID_PACKET;
469 } else {
470 siglen -= x;
471 }
472 y += 4;
473
474 /* load the public key */
475 if ((err = ecc_import((unsigned char*)sig+y, x, &pubkey)) != CRYPT_OK) {
476 return err;
477 }
478 y += x;
479
480 /* load size of 'b' */
481 LOAD32L(x, sig+y);
482 if (siglen < x) {
483 return CRYPT_INVALID_PACKET;
484 } else {
485 siglen -= x;
486 }
487 y += 4;
488
489 /* init values */
490 if ((err = mp_init_multi(&b, &m, &p, &mu, NULL)) != MP_OKAY) {
491 ecc_free(&pubkey);
492 return mpi_to_ltc_error(err);
493 }
494
495 mG = new_point();
496 if (mG == NULL) {
497 mp_clear_multi(&b, &m, &p, &mu, NULL);
498 ecc_free(&pubkey);
499 return CRYPT_MEM;
500 }
501
502 /* load b */
503 if ((err = mp_read_unsigned_bin(&b, (unsigned char *)sig+y, (int)x)) != MP_OKAY) { goto error; }
504 y += x;
505
506 /* get m in binary a bignum */
507 if ((err = mp_read_unsigned_bin(&m, (unsigned char *)hash, (int)hashlen)) != MP_OKAY) { goto error; }
508
509 /* load prime */
510 if ((err = mp_read_radix(&p, (char *)sets[key->idx].prime, 64)) != MP_OKAY) { goto error; }
511
512 /* calculate barrett stuff */
513 mp_set(&mu, 1);
514 mp_lshd(&mu, 2 * USED(&p));
515 if ((err = mp_div(&mu, &p, &mu, NULL)) != MP_OKAY) { goto error; }
516
517 /* get bA */
518 if ((err = ecc_mulmod(&b, &pubkey.pubkey, &pubkey.pubkey, &p)) != CRYPT_OK) { goto done; }
519
520 /* get bA + Y */
521 if ((err = add_point(&pubkey.pubkey, &key->pubkey, &pubkey.pubkey, &p, &mu)) != CRYPT_OK) { goto done; }
522
523 /* we have to transform it */
524 if ((err = ecc_map(&pubkey.pubkey, &p, &mu)) != CRYPT_OK) { goto done; }
525
526 /* get mG */
527 if ((err = mp_read_radix(&mG->x, (char *)sets[key->idx].Gx, 64)) != MP_OKAY) { goto error; }
528 if ((err = mp_read_radix(&mG->y, (char *)sets[key->idx].Gy, 64)) != MP_OKAY) { goto error; }
529 mp_set(&mG->z, 1);
530 if ((err = ecc_mulmod(&m, mG, mG, &p)) != CRYPT_OK) { goto done; }
531
532 /* compare mG to bA + Y */
533 if (mp_cmp(&mG->x, &pubkey.pubkey.x) == MP_EQ && mp_cmp(&mG->y, &pubkey.pubkey.y) == MP_EQ) {
534 *stat = 1;
535 }
536
537 /* clear up and return */
538 err = CRYPT_OK;
539 goto done;
540 error:
541 err = mpi_to_ltc_error(err);
542 done:
543 del_point(mG);
544 ecc_free(&pubkey);
545 mp_clear_multi(&p, &m, &b, &mu, NULL);
546 return err;
547 }
548