Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(112)

Side by Side Diff: nss/lib/freebl/ec.c

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

Powered by Google App Engine
This is Rietveld 408576698