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