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