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