1 /*
2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
3 * Use is subject to license terms.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public License
16 * along with this library; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /* *********************************************************************
25 *
26 * The Original Code is the Elliptic Curve Cryptography library.
27 *
28 * The Initial Developer of the Original Code is
29 * Sun Microsystems, Inc.
30 * Portions created by the Initial Developer are Copyright (C) 2003
31 * the Initial Developer. All Rights Reserved.
32 *
33 * Contributor(s):
34 * Dr Vipul Gupta <vipul.gupta@sun.com> and
35 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
36 *
37 *********************************************************************** */
38
39 #include "mplogic.h"
40 #include "ec.h"
41 #include "ecl.h"
42
43 #include <sys/types.h>
44 #ifndef _KERNEL
45 #include <stdlib.h>
46 #include <string.h>
47
48 #ifndef _WIN32
49 #include <stdio.h>
50 #include <strings.h>
51 #endif /* _WIN32 */
52
53 #endif
54 #include "ecl-exp.h"
55 #include "mpi.h"
56 #include "ecc_impl.h"
57
58 /*
59 * Returns true if pointP is the point at infinity, false otherwise
60 */
61 PRBool
62 ec_point_at_infinity(SECItem *pointP)
63 {
64 unsigned int i;
65
66 for (i = 1; i < pointP->len; i++) {
67 if (pointP->data[i] != 0x00) return PR_FALSE;
68 }
69
70 return PR_TRUE;
71 }
72
73 /*
74 * Computes scalar point multiplication pointQ = k1 * G + k2 * pointP for
75 * the curve whose parameters are encoded in params with base point G.
76 */
77 SECStatus
78 ec_points_mul(const ECParams *params, const mp_int *k1, const mp_int *k2,
79 const SECItem *pointP, SECItem *pointQ, int kmflag)
80 {
81 mp_int Px, Py, Qx, Qy;
82 mp_int Gx, Gy, order, irreducible, a, b;
83 #if 0 /* currently don't support non-named curves */
84 unsigned int irr_arr[5];
85 #endif
86 ECGroup *group = NULL;
87 SECStatus rv = SECFailure;
88 mp_err err = MP_OKAY;
89 unsigned int len;
90
91 #if EC_DEBUG
92 int i;
93 char mpstr[256];
94
95 printf("ec_points_mul: params [len=%d]:", params->DEREncoding.len);
96 for (i = 0; i < params->DEREncoding.len; i++)
97 printf("%02x:", params->DEREncoding.data[i]);
98 printf("\n");
99
100 if (k1 != NULL) {
101 mp_tohex(k1, mpstr);
102 printf("ec_points_mul: scalar k1: %s\n", mpstr);
103 mp_todecimal(k1, mpstr);
104 printf("ec_points_mul: scalar k1: %s (dec)\n", mpstr);
105 }
106
107 if (k2 != NULL) {
108 mp_tohex(k2, mpstr);
109 printf("ec_points_mul: scalar k2: %s\n", mpstr);
110 mp_todecimal(k2, mpstr);
111 printf("ec_points_mul: scalar k2: %s (dec)\n", mpstr);
112 }
113
114 if (pointP != NULL) {
115 printf("ec_points_mul: pointP [len=%d]:", pointP->len);
116 for (i = 0; i < pointP->len; i++)
117 printf("%02x:", pointP->data[i]);
118 printf("\n");
119 }
120 #endif
121
122 /* NOTE: We only support uncompressed points for now */
123 len = (params->fieldID.size + 7) >> 3;
124 if (pointP != NULL) {
125 if ((pointP->data[0] != EC_POINT_FORM_UNCOMPRESSED) ||
126 (pointP->len != (2 * len + 1))) {
127 return SECFailure;
128 };
129 }
130
131 MP_DIGITS(&Px) = 0;
132 MP_DIGITS(&Py) = 0;
133 MP_DIGITS(&Qx) = 0;
134 MP_DIGITS(&Qy) = 0;
135 MP_DIGITS(&Gx) = 0;
136 MP_DIGITS(&Gy) = 0;
137 MP_DIGITS(&order) = 0;
138 MP_DIGITS(&irreducible) = 0;
139 MP_DIGITS(&a) = 0;
140 MP_DIGITS(&b) = 0;
141 CHECK_MPI_OK( mp_init(&Px, kmflag) );
142 CHECK_MPI_OK( mp_init(&Py, kmflag) );
143 CHECK_MPI_OK( mp_init(&Qx, kmflag) );
144 CHECK_MPI_OK( mp_init(&Qy, kmflag) );
145 CHECK_MPI_OK( mp_init(&Gx, kmflag) );
146 CHECK_MPI_OK( mp_init(&Gy, kmflag) );
147 CHECK_MPI_OK( mp_init(&order, kmflag) );
148 CHECK_MPI_OK( mp_init(&irreducible, kmflag) );
149 CHECK_MPI_OK( mp_init(&a, kmflag) );
150 CHECK_MPI_OK( mp_init(&b, kmflag) );
151
152 if ((k2 != NULL) && (pointP != NULL)) {
153 /* Initialize Px and Py */
154 CHECK_MPI_OK( mp_read_unsigned_octets(&Px, pointP->data + 1, (mp_size) len) );
155 CHECK_MPI_OK( mp_read_unsigned_octets(&Py, pointP->data + 1 + len, (mp_size) len) );
156 }
157
158 /* construct from named params, if possible */
159 if (params->name != ECCurve_noName) {
160 group = ECGroup_fromName(params->name, kmflag);
161 }
162
163 #if 0 /* currently don't support non-named curves */
164 if (group == NULL) {
165 /* Set up mp_ints containing the curve coefficients */
166 CHECK_MPI_OK( mp_read_unsigned_octets(&Gx, params->base.data + 1,
167 (mp_size) len) );
168 CHECK_MPI_OK( mp_read_unsigned_octets(&Gy, params->base.data + 1 + len,
169 (mp_size) len) );
170 SECITEM_TO_MPINT( params->order, &order );
171 SECITEM_TO_MPINT( params->curve.a, &a );
172 SECITEM_TO_MPINT( params->curve.b, &b );
173 if (params->fieldID.type == ec_field_GFp) {
174 SECITEM_TO_MPINT( params->fieldID.u.prime, &irreducible );
175 group = ECGroup_consGFp(&irreducible, &a, &b, &Gx, &Gy, &order, params->cofactor);
176 } else {
177 SECITEM_TO_MPINT( params->fieldID.u.poly, &irreducible );
178 irr_arr[0] = params->fieldID.size;
179 irr_arr[1] = params->fieldID.k1;
180 irr_arr[2] = params->fieldID.k2;
181 irr_arr[3] = params->fieldID.k3;
182 irr_arr[4] = 0;
183 group = ECGroup_consGF2m(&irreducible, irr_arr, &a, &b, &Gx, &Gy, &order, params->cofactor);
184 }
185 }
186 #endif
187 if (group == NULL)
188 goto cleanup;
189
190 if ((k2 != NULL) && (pointP != NULL)) {
191 CHECK_MPI_OK( ECPoints_mul(group, k1, k2, &Px, &Py, &Qx, &Qy) );
192 } else {
193 CHECK_MPI_OK( ECPoints_mul(group, k1, NULL, NULL, NULL, &Qx, &Qy) );
194 }
195
196 /* Construct the SECItem representation of point Q */
197 pointQ->data[0] = EC_POINT_FORM_UNCOMPRESSED;
198 CHECK_MPI_OK( mp_to_fixlen_octets(&Qx, pointQ->data + 1,
199 (mp_size) len) );
200 CHECK_MPI_OK( mp_to_fixlen_octets(&Qy, pointQ->data + 1 + len,
201 (mp_size) len) );
202
203 rv = SECSuccess;
204
205 #if EC_DEBUG
206 printf("ec_points_mul: pointQ [len=%d]:", pointQ->len);
207 for (i = 0; i < pointQ->len; i++)
208 printf("%02x:", pointQ->data[i]);
209 printf("\n");
210 #endif
211
212 cleanup:
213 ECGroup_free(group);
214 mp_clear(&Px);
215 mp_clear(&Py);
216 mp_clear(&Qx);
217 mp_clear(&Qy);
218 mp_clear(&Gx);
219 mp_clear(&Gy);
220 mp_clear(&order);
221 mp_clear(&irreducible);
222 mp_clear(&a);
223 mp_clear(&b);
224 if (err) {
225 MP_TO_SEC_ERROR(err);
226 rv = SECFailure;
227 }
228
229 return rv;
230 }
231
232 /* Generates a new EC key pair. The private key is a supplied
233 * value and the public key is the result of performing a scalar
234 * point multiplication of that value with the curve's base point.
235 */
236 SECStatus
237 ec_NewKey(ECParams *ecParams, ECPrivateKey **privKey,
238 const unsigned char *privKeyBytes, int privKeyLen, int kmflag)
239 {
240 SECStatus rv = SECFailure;
241 PRArenaPool *arena;
242 ECPrivateKey *key;
243 mp_int k;
244 mp_err err = MP_OKAY;
245 int len;
246
247 #if EC_DEBUG
248 printf("ec_NewKey called\n");
249 #endif
250
251 if (!ecParams || !privKey || !privKeyBytes || (privKeyLen < 0)) {
252 PORT_SetError(SEC_ERROR_INVALID_ARGS);
253 return SECFailure;
254 }
255
256 /* Initialize an arena for the EC key. */
257 if (!(arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE)))
258 return SECFailure;
259
260 key = (ECPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(ECPrivateKey),
261 kmflag);
262 if (!key) {
263 PORT_FreeArena(arena, PR_TRUE);
264 return SECFailure;
265 }
266
267 /* Set the version number (SEC 1 section C.4 says it should be 1) */
268 SECITEM_AllocItem(arena, &key->version, 1, kmflag);
269 key->version.data[0] = 1;
270
271 /* Copy all of the fields from the ECParams argument to the
272 * ECParams structure within the private key.
273 */
274 key->ecParams.arena = arena;
275 key->ecParams.type = ecParams->type;
276 key->ecParams.fieldID.size = ecParams->fieldID.size;
277 key->ecParams.fieldID.type = ecParams->fieldID.type;
278 if (ecParams->fieldID.type == ec_field_GFp) {
279 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.prime,
280 &ecParams->fieldID.u.prime, kmflag));
281 } else {
282 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.poly,
283 &ecParams->fieldID.u.poly, kmflag));
284 }
285 key->ecParams.fieldID.k1 = ecParams->fieldID.k1;
286 key->ecParams.fieldID.k2 = ecParams->fieldID.k2;
287 key->ecParams.fieldID.k3 = ecParams->fieldID.k3;
288 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.a,
289 &ecParams->curve.a, kmflag));
290 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.b,
291 &ecParams->curve.b, kmflag));
292 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.seed,
293 &ecParams->curve.seed, kmflag));
294 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.base,
295 &ecParams->base, kmflag));
296 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.order,
297 &ecParams->order, kmflag));
298 key->ecParams.cofactor = ecParams->cofactor;
299 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.DEREncoding,
300 &ecParams->DEREncoding, kmflag));
301 key->ecParams.name = ecParams->name;
302 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curveOID,
303 &ecParams->curveOID, kmflag));
304
305 len = (ecParams->fieldID.size + 7) >> 3;
306 SECITEM_AllocItem(arena, &key->publicValue, 2*len + 1, kmflag);
307 len = ecParams->order.len;
308 SECITEM_AllocItem(arena, &key->privateValue, len, kmflag);
309
310 /* Copy private key */
311 if (privKeyLen >= len) {
312 memcpy(key->privateValue.data, privKeyBytes, len);
313 } else {
314 memset(key->privateValue.data, 0, (len - privKeyLen));
315 memcpy(key->privateValue.data + (len - privKeyLen), privKeyBytes, privKeyLen);
316 }
317
318 /* Compute corresponding public key */
319 MP_DIGITS(&k) = 0;
320 CHECK_MPI_OK( mp_init(&k, kmflag) );
321 CHECK_MPI_OK( mp_read_unsigned_octets(&k, key->privateValue.data,
322 (mp_size) len) );
323
324 rv = ec_points_mul(ecParams, &k, NULL, NULL, &(key->publicValue), kmflag);
325 if (rv != SECSuccess) goto cleanup;
326 *privKey = key;
327
328 cleanup:
329 mp_clear(&k);
330 if (rv) {
331 PORT_FreeArena(arena, PR_TRUE);
332 }
333
334 #if EC_DEBUG
335 printf("ec_NewKey returning %s\n",
336 (rv == SECSuccess) ? "success" : "failure");
337 #endif
338
339 return rv;
340
341 }
342
343 /* Generates a new EC key pair. The private key is a supplied
344 * random value (in seed) and the public key is the result of
345 * performing a scalar point multiplication of that value with
346 * the curve's base point.
347 */
348 SECStatus
349 EC_NewKeyFromSeed(ECParams *ecParams, ECPrivateKey **privKey,
350 const unsigned char *seed, int seedlen, int kmflag)
351 {
352 SECStatus rv = SECFailure;
353 rv = ec_NewKey(ecParams, privKey, seed, seedlen, kmflag);
354 return rv;
355 }
356
357 /* Generate a random private key using the algorithm A.4.1 of ANSI X9.62,
358 * modified a la FIPS 186-2 Change Notice 1 to eliminate the bias in the
359 * random number generator.
360 *
361 * Parameters
362 * - order: a buffer that holds the curve's group order
363 * - len: the length in octets of the order buffer
364 * - random: a buffer of 2 * len random bytes
365 * - randomlen: the length in octets of the random buffer
366 *
367 * Return Value
368 * Returns a buffer of len octets that holds the private key. The caller
369 * is responsible for freeing the buffer with PORT_ZFree.
370 */
371 static unsigned char *
372 ec_GenerateRandomPrivateKey(const unsigned char *order, int len,
373 const unsigned char *random, int randomlen, int kmflag)
374 {
375 SECStatus rv = SECSuccess;
376 mp_err err;
377 unsigned char *privKeyBytes = NULL;
378 mp_int privKeyVal, order_1, one;
379
380 MP_DIGITS(&privKeyVal) = 0;
381 MP_DIGITS(&order_1) = 0;
382 MP_DIGITS(&one) = 0;
383 CHECK_MPI_OK( mp_init(&privKeyVal, kmflag) );
384 CHECK_MPI_OK( mp_init(&order_1, kmflag) );
385 CHECK_MPI_OK( mp_init(&one, kmflag) );
386
387 /*
388 * Reduces the 2*len buffer of random bytes modulo the group order.
389 */
390 if ((privKeyBytes = PORT_Alloc(2*len, kmflag)) == NULL) goto cleanup;
391 if (randomlen != 2 * len) {
392 randomlen = 2 * len;
393 }
394 /* No need to generate - random bytes are now supplied */
395 /* CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(privKeyBytes, 2*len) );*/
396 memcpy(privKeyBytes, random, randomlen);
397
398 CHECK_MPI_OK( mp_read_unsigned_octets(&privKeyVal, privKeyBytes, 2*len) );
399 CHECK_MPI_OK( mp_read_unsigned_octets(&order_1, order, len) );
400 CHECK_MPI_OK( mp_set_int(&one, 1) );
401 CHECK_MPI_OK( mp_sub(&order_1, &one, &order_1) );
402 CHECK_MPI_OK( mp_mod(&privKeyVal, &order_1, &privKeyVal) );
403 CHECK_MPI_OK( mp_add(&privKeyVal, &one, &privKeyVal) );
404 CHECK_MPI_OK( mp_to_fixlen_octets(&privKeyVal, privKeyBytes, len) );
405 memset(privKeyBytes+len, 0, len);
406 cleanup:
407 mp_clear(&privKeyVal);
408 mp_clear(&order_1);
409 mp_clear(&one);
410 if (err < MP_OKAY) {
411 MP_TO_SEC_ERROR(err);
412 rv = SECFailure;
413 }
414 if (rv != SECSuccess && privKeyBytes) {
415 PORT_ZFree(privKeyBytes, 2*len);
416 privKeyBytes = NULL;
417 }
418 return privKeyBytes;
419 }
420
421 /* Generates a new EC key pair. The private key is a random value and
422 * the public key is the result of performing a scalar point multiplication
423 * of that value with the curve's base point.
424 */
425 SECStatus
426 EC_NewKey(ECParams *ecParams, ECPrivateKey **privKey,
427 const unsigned char* random, int randomlen, int kmflag)
428 {
429 SECStatus rv = SECFailure;
430 int len;
431 unsigned char *privKeyBytes = NULL;
432
433 if (!ecParams) {
434 PORT_SetError(SEC_ERROR_INVALID_ARGS);
435 return SECFailure;
436 }
437
438 len = ecParams->order.len;
439 privKeyBytes = ec_GenerateRandomPrivateKey(ecParams->order.data, len,
440 random, randomlen, kmflag);
441 if (privKeyBytes == NULL) goto cleanup;
442 /* generate public key */
443 CHECK_SEC_OK( ec_NewKey(ecParams, privKey, privKeyBytes, len, kmflag) );
444
445 cleanup:
446 if (privKeyBytes) {
447 PORT_ZFree(privKeyBytes, len * 2);
448 }
449 #if EC_DEBUG
450 printf("EC_NewKey returning %s\n",
451 (rv == SECSuccess) ? "success" : "failure");
452 #endif
453
454 return rv;
455 }
456
457 /* Validates an EC public key as described in Section 5.2.2 of
458 * X9.62. The ECDH primitive when used without the cofactor does
459 * not address small subgroup attacks, which may occur when the
460 * public key is not valid. These attacks can be prevented by
461 * validating the public key before using ECDH.
462 */
463 SECStatus
464 EC_ValidatePublicKey(ECParams *ecParams, SECItem *publicValue, int kmflag)
465 {
466 mp_int Px, Py;
467 ECGroup *group = NULL;
468 SECStatus rv = SECFailure;
469 mp_err err = MP_OKAY;
470 unsigned int len;
471
472 if (!ecParams || !publicValue) {
473 PORT_SetError(SEC_ERROR_INVALID_ARGS);
474 return SECFailure;
475 }
476
477 /* NOTE: We only support uncompressed points for now */
478 len = (ecParams->fieldID.size + 7) >> 3;
479 if (publicValue->data[0] != EC_POINT_FORM_UNCOMPRESSED) {
480 PORT_SetError(SEC_ERROR_UNSUPPORTED_EC_POINT_FORM);
481 return SECFailure;
482 } else if (publicValue->len != (2 * len + 1)) {
483 PORT_SetError(SEC_ERROR_BAD_KEY);
484 return SECFailure;
485 }
486
487 MP_DIGITS(&Px) = 0;
488 MP_DIGITS(&Py) = 0;
489 CHECK_MPI_OK( mp_init(&Px, kmflag) );
490 CHECK_MPI_OK( mp_init(&Py, kmflag) );
491
492 /* Initialize Px and Py */
493 CHECK_MPI_OK( mp_read_unsigned_octets(&Px, publicValue->data + 1, (mp_size) len) );
494 CHECK_MPI_OK( mp_read_unsigned_octets(&Py, publicValue->data + 1 + len, (mp_size) len) );
495
496 /* construct from named params */
497 group = ECGroup_fromName(ecParams->name, kmflag);
498 if (group == NULL) {
499 /*
500 * ECGroup_fromName fails if ecParams->name is not a valid
501 * ECCurveName value, or if we run out of memory, or perhaps
502 * for other reasons. Unfortunately if ecParams->name is a
503 * valid ECCurveName value, we don't know what the right error
504 * code should be because ECGroup_fromName doesn't return an
505 * error code to the caller. Set err to MP_UNDEF because
506 * that's what ECGroup_fromName uses internally.
507 */
508 if ((ecParams->name <= ECCurve_noName) ||
509 (ecParams->name >= ECCurve_pastLastCurve)) {
510 err = MP_BADARG;
511 } else {
512 err = MP_UNDEF;
513 }
514 goto cleanup;
515 }
516
517 /* validate public point */
518 if ((err = ECPoint_validate(group, &Px, &Py)) < MP_YES) {
519 if (err == MP_NO) {
520 PORT_SetError(SEC_ERROR_BAD_KEY);
521 rv = SECFailure;
522 err = MP_OKAY; /* don't change the error code */
523 }
524 goto cleanup;
525 }
526
527 rv = SECSuccess;
528
529 cleanup:
530 ECGroup_free(group);
531 mp_clear(&Px);
532 mp_clear(&Py);
533 if (err) {
534 MP_TO_SEC_ERROR(err);
535 rv = SECFailure;
536 }
537 return rv;
538 }
539
540 /*
541 ** Performs an ECDH key derivation by computing the scalar point
542 ** multiplication of privateValue and publicValue (with or without the
543 ** cofactor) and returns the x-coordinate of the resulting elliptic
544 ** curve point in derived secret. If successful, derivedSecret->data
545 ** is set to the address of the newly allocated buffer containing the
546 ** derived secret, and derivedSecret->len is the size of the secret
547 ** produced. It is the caller's responsibility to free the allocated
548 ** buffer containing the derived secret.
549 */
550 SECStatus
551 ECDH_Derive(SECItem *publicValue,
552 ECParams *ecParams,
553 SECItem *privateValue,
554 PRBool withCofactor,
555 SECItem *derivedSecret,
556 int kmflag)
557 {
558 SECStatus rv = SECFailure;
559 unsigned int len = 0;
560 SECItem pointQ = {siBuffer, NULL, 0};
561 mp_int k; /* to hold the private value */
562 mp_int cofactor;
563 mp_err err = MP_OKAY;
564 #if EC_DEBUG
565 int i;
566 #endif
567
568 if (!publicValue || !ecParams || !privateValue ||
569 !derivedSecret) {
570 PORT_SetError(SEC_ERROR_INVALID_ARGS);
571 return SECFailure;
572 }
573
574 memset(derivedSecret, 0, sizeof *derivedSecret);
575 len = (ecParams->fieldID.size + 7) >> 3;
576 pointQ.len = 2*len + 1;
577 if ((pointQ.data = PORT_Alloc(2*len + 1, kmflag)) == NULL) goto cleanup;
578
579 MP_DIGITS(&k) = 0;
580 CHECK_MPI_OK( mp_init(&k, kmflag) );
581 CHECK_MPI_OK( mp_read_unsigned_octets(&k, privateValue->data,
582 (mp_size) privateValue->len) );
583
584 if (withCofactor && (ecParams->cofactor != 1)) {
585 /* multiply k with the cofactor */
586 MP_DIGITS(&cofactor) = 0;
587 CHECK_MPI_OK( mp_init(&cofactor, kmflag) );
588 mp_set(&cofactor, ecParams->cofactor);
589 CHECK_MPI_OK( mp_mul(&k, &cofactor, &k) );
590 }
591
592 /* Multiply our private key and peer's public point */
593 if ((ec_points_mul(ecParams, NULL, &k, publicValue, &pointQ, kmflag) != SECSuccess) ||
594 ec_point_at_infinity(&pointQ))
595 goto cleanup;
596
597 /* Allocate memory for the derived secret and copy
598 * the x co-ordinate of pointQ into it.
599 */
600 SECITEM_AllocItem(NULL, derivedSecret, len, kmflag);
601 memcpy(derivedSecret->data, pointQ.data + 1, len);
602
603 rv = SECSuccess;
604
605 #if EC_DEBUG
606 printf("derived_secret:\n");
607 for (i = 0; i < derivedSecret->len; i++)
608 printf("%02x:", derivedSecret->data[i]);
609 printf("\n");
610 #endif
611
612 cleanup:
613 mp_clear(&k);
614
615 if (pointQ.data) {
616 PORT_ZFree(pointQ.data, 2*len + 1);
617 }
618
619 return rv;
620 }
621
622 /* Computes the ECDSA signature (a concatenation of two values r and s)
623 * on the digest using the given key and the random value kb (used in
624 * computing s).
625 */
626 SECStatus
627 ECDSA_SignDigestWithSeed(ECPrivateKey *key, SECItem *signature,
628 const SECItem *digest, const unsigned char *kb, const int kblen, int kmflag)
629 {
630 SECStatus rv = SECFailure;
631 mp_int x1;
632 mp_int d, k; /* private key, random integer */
633 mp_int r, s; /* tuple (r, s) is the signature */
634 mp_int n;
635 mp_err err = MP_OKAY;
636 ECParams *ecParams = NULL;
637 SECItem kGpoint = { siBuffer, NULL, 0};
638 int flen = 0; /* length in bytes of the field size */
639 unsigned olen; /* length in bytes of the base point order */
640
641 #if EC_DEBUG
642 char mpstr[256];
643 #endif
644
645 /* Initialize MPI integers. */
646 /* must happen before the first potential call to cleanup */
647 MP_DIGITS(&x1) = 0;
648 MP_DIGITS(&d) = 0;
649 MP_DIGITS(&k) = 0;
650 MP_DIGITS(&r) = 0;
651 MP_DIGITS(&s) = 0;
652 MP_DIGITS(&n) = 0;
653
654 /* Check args */
655 if (!key || !signature || !digest || !kb || (kblen < 0)) {
656 PORT_SetError(SEC_ERROR_INVALID_ARGS);
657 goto cleanup;
658 }
659
660 ecParams = &(key->ecParams);
661 flen = (ecParams->fieldID.size + 7) >> 3;
662 olen = ecParams->order.len;
663 if (signature->data == NULL) {
664 /* a call to get the signature length only */
665 goto finish;
666 }
667 if (signature->len < 2*olen) {
668 PORT_SetError(SEC_ERROR_OUTPUT_LEN);
669 rv = SECBufferTooSmall;
670 goto cleanup;
671 }
672
673
674 CHECK_MPI_OK( mp_init(&x1, kmflag) );
675 CHECK_MPI_OK( mp_init(&d, kmflag) );
676 CHECK_MPI_OK( mp_init(&k, kmflag) );
677 CHECK_MPI_OK( mp_init(&r, kmflag) );
678 CHECK_MPI_OK( mp_init(&s, kmflag) );
679 CHECK_MPI_OK( mp_init(&n, kmflag) );
680
681 SECITEM_TO_MPINT( ecParams->order, &n );
682 SECITEM_TO_MPINT( key->privateValue, &d );
683 CHECK_MPI_OK( mp_read_unsigned_octets(&k, kb, kblen) );
684 /* Make sure k is in the interval [1, n-1] */
685 if ((mp_cmp_z(&k) <= 0) || (mp_cmp(&k, &n) >= 0)) {
686 #if EC_DEBUG
687 printf("k is outside [1, n-1]\n");
688 mp_tohex(&k, mpstr);
689 printf("k : %s \n", mpstr);
690 mp_tohex(&n, mpstr);
691 printf("n : %s \n", mpstr);
692 #endif
693 PORT_SetError(SEC_ERROR_NEED_RANDOM);
694 goto cleanup;
695 }
696
697 /*
698 ** ANSI X9.62, Section 5.3.2, Step 2
699 **
700 ** Compute kG
701 */
702 kGpoint.len = 2*flen + 1;
703 kGpoint.data = PORT_Alloc(2*flen + 1, kmflag);
704 if ((kGpoint.data == NULL) ||
705 (ec_points_mul(ecParams, &k, NULL, NULL, &kGpoint, kmflag)
706 != SECSuccess))
707 goto cleanup;
708
709 /*
710 ** ANSI X9.62, Section 5.3.3, Step 1
711 **
712 ** Extract the x co-ordinate of kG into x1
713 */
714 CHECK_MPI_OK( mp_read_unsigned_octets(&x1, kGpoint.data + 1,
715 (mp_size) flen) );
716
717 /*
718 ** ANSI X9.62, Section 5.3.3, Step 2
719 **
720 ** r = x1 mod n NOTE: n is the order of the curve
721 */
722 CHECK_MPI_OK( mp_mod(&x1, &n, &r) );
723
724 /*
725 ** ANSI X9.62, Section 5.3.3, Step 3
726 **
727 ** verify r != 0
728 */
729 if (mp_cmp_z(&r) == 0) {
730 PORT_SetError(SEC_ERROR_NEED_RANDOM);
731 goto cleanup;
732 }
733
734 /*
735 ** ANSI X9.62, Section 5.3.3, Step 4
736 **
737 ** s = (k**-1 * (HASH(M) + d*r)) mod n
738 */
739 SECITEM_TO_MPINT(*digest, &s); /* s = HASH(M) */
740
741 /* In the definition of EC signing, digests are truncated
742 * to the length of n in bits.
743 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
744 if (digest->len*8 > (unsigned int)ecParams->fieldID.size) {
745 mpl_rsh(&s,&s,digest->len*8 - ecParams->fieldID.size);
746 }
747
748 #if EC_DEBUG
749 mp_todecimal(&n, mpstr);
750 printf("n : %s (dec)\n", mpstr);
751 mp_todecimal(&d, mpstr);
752 printf("d : %s (dec)\n", mpstr);
753 mp_tohex(&x1, mpstr);
754 printf("x1: %s\n", mpstr);
755 mp_todecimal(&s, mpstr);
756 printf("digest: %s (decimal)\n", mpstr);
757 mp_todecimal(&r, mpstr);
758 printf("r : %s (dec)\n", mpstr);
759 mp_tohex(&r, mpstr);
760 printf("r : %s\n", mpstr);
761 #endif
762
763 CHECK_MPI_OK( mp_invmod(&k, &n, &k) ); /* k = k**-1 mod n */
764 CHECK_MPI_OK( mp_mulmod(&d, &r, &n, &d) ); /* d = d * r mod n */
765 CHECK_MPI_OK( mp_addmod(&s, &d, &n, &s) ); /* s = s + d mod n */
766 CHECK_MPI_OK( mp_mulmod(&s, &k, &n, &s) ); /* s = s * k mod n */
767
768 #if EC_DEBUG
769 mp_todecimal(&s, mpstr);
770 printf("s : %s (dec)\n", mpstr);
771 mp_tohex(&s, mpstr);
772 printf("s : %s\n", mpstr);
773 #endif
774
775 /*
776 ** ANSI X9.62, Section 5.3.3, Step 5
777 **
778 ** verify s != 0
779 */
780 if (mp_cmp_z(&s) == 0) {
781 PORT_SetError(SEC_ERROR_NEED_RANDOM);
782 goto cleanup;
783 }
784
785 /*
786 **
787 ** Signature is tuple (r, s)
788 */
789 CHECK_MPI_OK( mp_to_fixlen_octets(&r, signature->data, olen) );
790 CHECK_MPI_OK( mp_to_fixlen_octets(&s, signature->data + olen, olen) );
791 finish:
792 signature->len = 2*olen;
793
794 rv = SECSuccess;
795 err = MP_OKAY;
796 cleanup:
797 mp_clear(&x1);
798 mp_clear(&d);
799 mp_clear(&k);
800 mp_clear(&r);
801 mp_clear(&s);
802 mp_clear(&n);
803
804 if (kGpoint.data) {
805 PORT_ZFree(kGpoint.data, 2*flen + 1);
806 }
807
808 if (err) {
809 MP_TO_SEC_ERROR(err);
810 rv = SECFailure;
811 }
812
813 #if EC_DEBUG
814 printf("ECDSA signing with seed %s\n",
815 (rv == SECSuccess) ? "succeeded" : "failed");
816 #endif
817
818 return rv;
819 }
820
821 /*
822 ** Computes the ECDSA signature on the digest using the given key
823 ** and a random seed.
824 */
825 SECStatus
826 ECDSA_SignDigest(ECPrivateKey *key, SECItem *signature, const SECItem *digest,
827 const unsigned char* random, int randomLen, int kmflag)
828 {
829 SECStatus rv = SECFailure;
830 int len;
831 unsigned char *kBytes= NULL;
832
833 if (!key) {
834 PORT_SetError(SEC_ERROR_INVALID_ARGS);
835 return SECFailure;
836 }
837
838 /* Generate random value k */
839 len = key->ecParams.order.len;
840 kBytes = ec_GenerateRandomPrivateKey(key->ecParams.order.data, len,
841 random, randomLen, kmflag);
842 if (kBytes == NULL) goto cleanup;
843
844 /* Generate ECDSA signature with the specified k value */
845 rv = ECDSA_SignDigestWithSeed(key, signature, digest, kBytes, len, kmflag);
846
847 cleanup:
848 if (kBytes) {
849 PORT_ZFree(kBytes, len * 2);
850 }
851
852 #if EC_DEBUG
853 printf("ECDSA signing %s\n",
854 (rv == SECSuccess) ? "succeeded" : "failed");
855 #endif
856
857 return rv;
858 }
859
860 /*
861 ** Checks the signature on the given digest using the key provided.
862 */
863 SECStatus
864 ECDSA_VerifyDigest(ECPublicKey *key, const SECItem *signature,
865 const SECItem *digest, int kmflag)
866 {
867 SECStatus rv = SECFailure;
868 mp_int r_, s_; /* tuple (r', s') is received signature) */
869 mp_int c, u1, u2, v; /* intermediate values used in verification */
870 mp_int x1;
871 mp_int n;
872 mp_err err = MP_OKAY;
873 ECParams *ecParams = NULL;
874 SECItem pointC = { siBuffer, NULL, 0 };
875 int slen; /* length in bytes of a half signature (r or s) */
876 int flen; /* length in bytes of the field size */
877 unsigned olen; /* length in bytes of the base point order */
878
879 #if EC_DEBUG
880 char mpstr[256];
881 printf("ECDSA verification called\n");
882 #endif
883
884 /* Initialize MPI integers. */
885 /* must happen before the first potential call to cleanup */
886 MP_DIGITS(&r_) = 0;
887 MP_DIGITS(&s_) = 0;
888 MP_DIGITS(&c) = 0;
889 MP_DIGITS(&u1) = 0;
890 MP_DIGITS(&u2) = 0;
891 MP_DIGITS(&x1) = 0;
892 MP_DIGITS(&v) = 0;
893 MP_DIGITS(&n) = 0;
894
895 /* Check args */
896 if (!key || !signature || !digest) {
897 PORT_SetError(SEC_ERROR_INVALID_ARGS);
898 goto cleanup;
899 }
900
901 ecParams = &(key->ecParams);
902 flen = (ecParams->fieldID.size + 7) >> 3;
903 olen = ecParams->order.len;
904 if (signature->len == 0 || signature->len%2 != 0 ||
905 signature->len > 2*olen) {
906 PORT_SetError(SEC_ERROR_INPUT_LEN);
907 goto cleanup;
908 }
909 slen = signature->len/2;
910
911 SECITEM_AllocItem(NULL, &pointC, 2*flen + 1, kmflag);
912 if (pointC.data == NULL)
913 goto cleanup;
914
915 CHECK_MPI_OK( mp_init(&r_, kmflag) );
916 CHECK_MPI_OK( mp_init(&s_, kmflag) );
917 CHECK_MPI_OK( mp_init(&c, kmflag) );
918 CHECK_MPI_OK( mp_init(&u1, kmflag) );
919 CHECK_MPI_OK( mp_init(&u2, kmflag) );
920 CHECK_MPI_OK( mp_init(&x1, kmflag) );
921 CHECK_MPI_OK( mp_init(&v, kmflag) );
922 CHECK_MPI_OK( mp_init(&n, kmflag) );
923
924 /*
925 ** Convert received signature (r', s') into MPI integers.
926 */
927 CHECK_MPI_OK( mp_read_unsigned_octets(&r_, signature->data, slen) );
928 CHECK_MPI_OK( mp_read_unsigned_octets(&s_, signature->data + slen, slen) );
929
930 /*
931 ** ANSI X9.62, Section 5.4.2, Steps 1 and 2
932 **
933 ** Verify that 0 < r' < n and 0 < s' < n
934 */
935 SECITEM_TO_MPINT(ecParams->order, &n);
936 if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||
937 mp_cmp(&r_, &n) >= 0 || mp_cmp(&s_, &n) >= 0) {
938 PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
939 goto cleanup; /* will return rv == SECFailure */
940 }
941
942 /*
943 ** ANSI X9.62, Section 5.4.2, Step 3
944 **
945 ** c = (s')**-1 mod n
946 */
947 CHECK_MPI_OK( mp_invmod(&s_, &n, &c) ); /* c = (s')**-1 mod n */
948
949 /*
950 ** ANSI X9.62, Section 5.4.2, Step 4
951 **
952 ** u1 = ((HASH(M')) * c) mod n
953 */
954 SECITEM_TO_MPINT(*digest, &u1); /* u1 = HASH(M) */
955
956 /* In the definition of EC signing, digests are truncated
957 * to the length of n in bits.
958 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
959 /* u1 = HASH(M') */
960 if (digest->len*8 > (unsigned int)ecParams->fieldID.size) {
961 mpl_rsh(&u1,&u1,digest->len*8- ecParams->fieldID.size);
962 }
963
964 #if EC_DEBUG
965 mp_todecimal(&r_, mpstr);
966 printf("r_: %s (dec)\n", mpstr);
967 mp_todecimal(&s_, mpstr);
968 printf("s_: %s (dec)\n", mpstr);
969 mp_todecimal(&c, mpstr);
970 printf("c : %s (dec)\n", mpstr);
971 mp_todecimal(&u1, mpstr);
972 printf("digest: %s (dec)\n", mpstr);
973 #endif
974
975 CHECK_MPI_OK( mp_mulmod(&u1, &c, &n, &u1) ); /* u1 = u1 * c mod n */
976
977 /*
978 ** ANSI X9.62, Section 5.4.2, Step 4
979 **
980 ** u2 = ((r') * c) mod n
981 */
982 CHECK_MPI_OK( mp_mulmod(&r_, &c, &n, &u2) );
983
984 /*
985 ** ANSI X9.62, Section 5.4.3, Step 1
986 **
987 ** Compute u1*G + u2*Q
988 ** Here, A = u1.G B = u2.Q and C = A + B
989 ** If the result, C, is the point at infinity, reject the signature
990 */
991 if (ec_points_mul(ecParams, &u1, &u2, &key->publicValue, &pointC, kmflag)
992 != SECSuccess) {
993 rv = SECFailure;
994 goto cleanup;
995 }
996 if (ec_point_at_infinity(&pointC)) {
997 PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
998 rv = SECFailure;
999 goto cleanup;
1000 }
1001
1002 CHECK_MPI_OK( mp_read_unsigned_octets(&x1, pointC.data + 1, flen) );
1003
1004 /*
1005 ** ANSI X9.62, Section 5.4.4, Step 2
1006 **
1007 ** v = x1 mod n
1008 */
1009 CHECK_MPI_OK( mp_mod(&x1, &n, &v) );
1010
1011 #if EC_DEBUG
1012 mp_todecimal(&r_, mpstr);
1013 printf("r_: %s (dec)\n", mpstr);
1014 mp_todecimal(&v, mpstr);
1015 printf("v : %s (dec)\n", mpstr);
1016 #endif
1017
1018 /*
1019 ** ANSI X9.62, Section 5.4.4, Step 3
1020 **
1021 ** Verification: v == r'
1022 */
1023 if (mp_cmp(&v, &r_)) {
1024 PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
1025 rv = SECFailure; /* Signature failed to verify. */
1026 } else {
1027 rv = SECSuccess; /* Signature verified. */
1028 }
1029
1030 #if EC_DEBUG
1031 mp_todecimal(&u1, mpstr);
1032 printf("u1: %s (dec)\n", mpstr);
1033 mp_todecimal(&u2, mpstr);
1034 printf("u2: %s (dec)\n", mpstr);
1035 mp_tohex(&x1, mpstr);
1036 printf("x1: %s\n", mpstr);
1037 mp_todecimal(&v, mpstr);
1038 printf("v : %s (dec)\n", mpstr);
1039 #endif
1040
1041 cleanup:
1042 mp_clear(&r_);
1043 mp_clear(&s_);
1044 mp_clear(&c);
1045 mp_clear(&u1);
1046 mp_clear(&u2);
1047 mp_clear(&x1);
1048 mp_clear(&v);
1049 mp_clear(&n);
1050
1051 if (pointC.data) SECITEM_FreeItem(&pointC, PR_FALSE);
1052 if (err) {
1053 MP_TO_SEC_ERROR(err);
1054 rv = SECFailure;
1055 }
1056
1057 #if EC_DEBUG
1058 printf("ECDSA verification %s\n",
1059 (rv == SECSuccess) ? "succeeded" : "failed");
1060 #endif
1061
1062 return rv;
1063 }