OLD | NEW |
---|---|
1 /* This Source Code Form is subject to the terms of the Mozilla Public | 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 | 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/. */ | 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
4 | 4 |
5 #include "ecp.h" | 5 #include "ecp.h" |
6 #include "mplogic.h" | 6 #include "mplogic.h" |
7 #include <stdlib.h> | 7 #include <stdlib.h> |
8 #ifdef ECL_DEBUG | 8 #ifdef ECL_DEBUG |
9 #include <assert.h> | 9 #include <assert.h> |
10 #endif | 10 #endif |
(...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
137 /* A = qx * pz^2, B = qy * pz^3 */ | 137 /* A = qx * pz^2, B = qy * pz^3 */ |
138 MP_CHECKOK(group->meth->field_sqr(pz, &A, group->meth)); | 138 MP_CHECKOK(group->meth->field_sqr(pz, &A, group->meth)); |
139 MP_CHECKOK(group->meth->field_mul(&A, pz, &B, group->meth)); | 139 MP_CHECKOK(group->meth->field_mul(&A, pz, &B, group->meth)); |
140 MP_CHECKOK(group->meth->field_mul(&A, qx, &A, group->meth)); | 140 MP_CHECKOK(group->meth->field_mul(&A, qx, &A, group->meth)); |
141 MP_CHECKOK(group->meth->field_mul(&B, qy, &B, group->meth)); | 141 MP_CHECKOK(group->meth->field_mul(&B, qy, &B, group->meth)); |
142 | 142 |
143 /* C = A - px, D = B - py */ | 143 /* C = A - px, D = B - py */ |
144 MP_CHECKOK(group->meth->field_sub(&A, px, &C, group->meth)); | 144 MP_CHECKOK(group->meth->field_sub(&A, px, &C, group->meth)); |
145 MP_CHECKOK(group->meth->field_sub(&B, py, &D, group->meth)); | 145 MP_CHECKOK(group->meth->field_sub(&B, py, &D, group->meth)); |
146 | 146 |
147 if (mp_cmp_z(&C) == 0) { | |
148 /* P == Q or P == -Q */ | |
Ryan Sleevi
2015/12/11 01:26:14
Of interest; correctness fix
davidben
2015/12/11 22:10:58
I don't really know this math well enough to be ab
| |
149 if (mp_cmp_z(&D) == 0) { | |
150 /* P == Q */ | |
151 /* It is cheaper to double (qx, qy, 1) than (px, py, pz) . */ | |
152 MP_DIGIT(&D, 0) = 1; /* Set D to 1. */ | |
153 MP_CHECKOK(ec_GFp_pt_dbl_jac(qx, qy, &D, rx, ry, rz, gro up)); | |
154 } else { | |
155 /* P == -Q */ | |
156 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz)); | |
157 } | |
158 goto CLEANUP; | |
159 } | |
160 | |
147 /* C2 = C^2, C3 = C^3 */ | 161 /* C2 = C^2, C3 = C^3 */ |
148 MP_CHECKOK(group->meth->field_sqr(&C, &C2, group->meth)); | 162 MP_CHECKOK(group->meth->field_sqr(&C, &C2, group->meth)); |
149 MP_CHECKOK(group->meth->field_mul(&C, &C2, &C3, group->meth)); | 163 MP_CHECKOK(group->meth->field_mul(&C, &C2, &C3, group->meth)); |
150 | 164 |
151 /* rz = pz * C */ | 165 /* rz = pz * C */ |
152 MP_CHECKOK(group->meth->field_mul(pz, &C, rz, group->meth)); | 166 MP_CHECKOK(group->meth->field_mul(pz, &C, rz, group->meth)); |
153 | 167 |
154 /* C = px * C^2 */ | 168 /* C = px * C^2 */ |
155 MP_CHECKOK(group->meth->field_mul(px, &C2, &C, group->meth)); | 169 MP_CHECKOK(group->meth->field_mul(px, &C2, &C, group->meth)); |
156 /* A = D^2 */ | 170 /* A = D^2 */ |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
198 | 212 |
199 MP_DIGITS(&t0) = 0; | 213 MP_DIGITS(&t0) = 0; |
200 MP_DIGITS(&t1) = 0; | 214 MP_DIGITS(&t1) = 0; |
201 MP_DIGITS(&M) = 0; | 215 MP_DIGITS(&M) = 0; |
202 MP_DIGITS(&S) = 0; | 216 MP_DIGITS(&S) = 0; |
203 MP_CHECKOK(mp_init(&t0)); | 217 MP_CHECKOK(mp_init(&t0)); |
204 MP_CHECKOK(mp_init(&t1)); | 218 MP_CHECKOK(mp_init(&t1)); |
205 MP_CHECKOK(mp_init(&M)); | 219 MP_CHECKOK(mp_init(&M)); |
206 MP_CHECKOK(mp_init(&S)); | 220 MP_CHECKOK(mp_init(&S)); |
207 | 221 |
208 » if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { | 222 » /* P == inf or P == -P */ |
Ryan Sleevi
2015/12/11 01:26:14
Another correctness fix
davidben
2015/12/11 22:10:58
Ditto.
| |
223 » if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES || mp_cmp_z(py) == 0) { | |
209 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz)); | 224 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz)); |
210 goto CLEANUP; | 225 goto CLEANUP; |
211 } | 226 } |
212 | 227 |
213 if (mp_cmp_d(pz, 1) == 0) { | 228 if (mp_cmp_d(pz, 1) == 0) { |
214 /* M = 3 * px^2 + a */ | 229 /* M = 3 * px^2 + a */ |
215 MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth)); | 230 MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth)); |
216 MP_CHECKOK(group->meth->field_add(&t0, &t0, &M, group->meth)); | 231 MP_CHECKOK(group->meth->field_add(&t0, &t0, &M, group->meth)); |
217 MP_CHECKOK(group->meth->field_add(&t0, &M, &t0, group->meth)); | 232 MP_CHECKOK(group->meth->field_add(&t0, &M, &t0, group->meth)); |
218 MP_CHECKOK(group->meth-> | 233 MP_CHECKOK(group->meth-> |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
365 * Software Implementation of the NIST Elliptic Curves over Prime Fields. */ | 380 * Software Implementation of the NIST Elliptic Curves over Prime Fields. */ |
366 mp_err | 381 mp_err |
367 ec_GFp_pts_mul_jac(const mp_int *k1, const mp_int *k2, const mp_int *px, | 382 ec_GFp_pts_mul_jac(const mp_int *k1, const mp_int *k2, const mp_int *px, |
368 const mp_int *py, mp_int *rx, mp_int *ry, | 383 const mp_int *py, mp_int *rx, mp_int *ry, |
369 const ECGroup *group) | 384 const ECGroup *group) |
370 { | 385 { |
371 mp_err res = MP_OKAY; | 386 mp_err res = MP_OKAY; |
372 mp_int precomp[4][4][2]; | 387 mp_int precomp[4][4][2]; |
373 mp_int rz; | 388 mp_int rz; |
374 const mp_int *a, *b; | 389 const mp_int *a, *b; |
375 » int i, j; | 390 » unsigned int i, j; |
376 int ai, bi, d; | 391 int ai, bi, d; |
377 | 392 |
378 for (i = 0; i < 4; i++) { | 393 for (i = 0; i < 4; i++) { |
379 for (j = 0; j < 4; j++) { | 394 for (j = 0; j < 4; j++) { |
380 MP_DIGITS(&precomp[i][j][0]) = 0; | 395 MP_DIGITS(&precomp[i][j][0]) = 0; |
381 MP_DIGITS(&precomp[i][j][1]) = 0; | 396 MP_DIGITS(&precomp[i][j][1]) = 0; |
382 } | 397 } |
383 } | 398 } |
384 MP_DIGITS(&rz) = 0; | 399 MP_DIGITS(&rz) = 0; |
385 | 400 |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
472 &precomp[i][0][0], &pre comp[i][0][1], | 487 &precomp[i][0][0], &pre comp[i][0][1], |
473 &precomp[i][3][0], &pre comp[i][3][1], group)); | 488 &precomp[i][3][0], &pre comp[i][3][1], group)); |
474 } | 489 } |
475 | 490 |
476 d = (mpl_significant_bits(a) + 1) / 2; | 491 d = (mpl_significant_bits(a) + 1) / 2; |
477 | 492 |
478 /* R = inf */ | 493 /* R = inf */ |
479 MP_CHECKOK(mp_init(&rz)); | 494 MP_CHECKOK(mp_init(&rz)); |
480 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz)); | 495 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz)); |
481 | 496 |
482 » for (i = d - 1; i >= 0; i--) { | 497 for (i = d; i-- > 0;) { |
483 ai = MP_GET_BIT(a, 2 * i + 1); | 498 ai = MP_GET_BIT(a, 2 * i + 1); |
484 ai <<= 1; | 499 ai <<= 1; |
485 ai |= MP_GET_BIT(a, 2 * i); | 500 ai |= MP_GET_BIT(a, 2 * i); |
486 bi = MP_GET_BIT(b, 2 * i + 1); | 501 bi = MP_GET_BIT(b, 2 * i + 1); |
487 bi <<= 1; | 502 bi <<= 1; |
488 bi |= MP_GET_BIT(b, 2 * i); | 503 bi |= MP_GET_BIT(b, 2 * i); |
489 /* R = 2^2 * R */ | 504 /* R = 2^2 * R */ |
490 MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group)); | 505 MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group)); |
491 MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group)); | 506 MP_CHECKOK(ec_GFp_pt_dbl_jac(rx, ry, &rz, rx, ry, &rz, group)); |
492 /* R = R + (ai * A + bi * B) */ | 507 /* R = R + (ai * A + bi * B) */ |
(...skipping 12 matching lines...) Expand all Loading... | |
505 CLEANUP: | 520 CLEANUP: |
506 mp_clear(&rz); | 521 mp_clear(&rz); |
507 for (i = 0; i < 4; i++) { | 522 for (i = 0; i < 4; i++) { |
508 for (j = 0; j < 4; j++) { | 523 for (j = 0; j < 4; j++) { |
509 mp_clear(&precomp[i][j][0]); | 524 mp_clear(&precomp[i][j][0]); |
510 mp_clear(&precomp[i][j][1]); | 525 mp_clear(&precomp[i][j][1]); |
511 } | 526 } |
512 } | 527 } |
513 return res; | 528 return res; |
514 } | 529 } |
OLD | NEW |