diff options
Diffstat (limited to 'security/nss/lib/freebl/GFp_ecl.c')
| -rw-r--r-- | security/nss/lib/freebl/GFp_ecl.c | 648 |
1 files changed, 0 insertions, 648 deletions
diff --git a/security/nss/lib/freebl/GFp_ecl.c b/security/nss/lib/freebl/GFp_ecl.c deleted file mode 100644 index 7b460cc58..000000000 --- a/security/nss/lib/freebl/GFp_ecl.c +++ /dev/null @@ -1,648 +0,0 @@ -/* - * ***** BEGIN LICENSE BLOCK ***** - * Version: MPL 1.1/GPL 2.0/LGPL 2.1 - * - * The contents of this file are subject to the Mozilla Public License Version - * 1.1 (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * http://www.mozilla.org/MPL/ - * - * Software distributed under the License is distributed on an "AS IS" basis, - * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License - * for the specific language governing rights and limitations under the - * License. - * - * The Original Code is the elliptic curve math library for prime field curves. - * - * The Initial Developer of the Original Code is - * Sun Microsystems, Inc. - * Portions created by the Initial Developer are Copyright (C) 2003 - * the Initial Developer. All Rights Reserved. - * - * Contributor(s): - * Sheueling Chang Shantz <sheueling.chang@sun.com> and - * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories - * Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>, - * Nils Larsch <nla@trustcenter.de>, and - * Lenka Fibikova <fibikova@exp-math.uni-essen.de>, the OpenSSL Project - * - * Alternatively, the contents of this file may be used under the terms of - * either the GNU General Public License Version 2 or later (the "GPL"), or - * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), - * in which case the provisions of the GPL or the LGPL are applicable instead - * of those above. If you wish to allow use of your version of this file only - * under the terms of either the GPL or the LGPL, and not to allow others to - * use your version of this file under the terms of the MPL, indicate your - * decision by deleting the provisions above and replace them with the notice - * and other provisions required by the GPL or the LGPL. If you do not delete - * the provisions above, a recipient may use your version of this file under - * the terms of any one of the MPL, the GPL or the LGPL. - * - * ***** END LICENSE BLOCK ***** */ - -#ifdef NSS_ENABLE_ECC -/* - * GFp_ecl.c: Contains an implementation of elliptic curve math library - * for curves over GFp. - * - * XXX Can be moved to a separate subdirectory later. - * - */ - -#include "GFp_ecl.h" -#include "mpi/mplogic.h" - -/* Checks if point P(px, py) is at infinity. Uses affine coordinates. */ -mp_err -GFp_ec_pt_is_inf_aff(const mp_int *px, const mp_int *py) -{ - - if ((mp_cmp_z(px) == 0) && (mp_cmp_z(py) == 0)) { - return MP_YES; - } else { - return MP_NO; - } - -} - -/* Sets P(px, py) to be the point at infinity. Uses affine coordinates. */ -mp_err -GFp_ec_pt_set_inf_aff(mp_int *px, mp_int *py) -{ - mp_zero(px); - mp_zero(py); - return MP_OKAY; -} - -/* Computes R = P + Q based on IEEE P1363 A.10.1. - * Elliptic curve points P, Q, and R can all be identical. - * Uses affine coordinates. - */ -mp_err -GFp_ec_pt_add_aff(const mp_int *p, const mp_int *a, const mp_int *px, - const mp_int *py, const mp_int *qx, const mp_int *qy, - mp_int *rx, mp_int *ry) -{ - mp_err err = MP_OKAY; - mp_int lambda, temp, xtemp, ytemp; - - CHECK_MPI_OK( mp_init(&lambda) ); - CHECK_MPI_OK( mp_init(&temp) ); - CHECK_MPI_OK( mp_init(&xtemp) ); - CHECK_MPI_OK( mp_init(&ytemp) ); - /* if P = inf, then R = Q */ - if (GFp_ec_pt_is_inf_aff(px, py) == 0) { - CHECK_MPI_OK( mp_copy(qx, rx) ); - CHECK_MPI_OK( mp_copy(qy, ry) ); - err = MP_OKAY; - goto cleanup; - } - /* if Q = inf, then R = P */ - if (GFp_ec_pt_is_inf_aff(qx, qy) == 0) { - CHECK_MPI_OK( mp_copy(px, rx) ); - CHECK_MPI_OK( mp_copy(py, ry) ); - err = MP_OKAY; - goto cleanup; - } - /* if px != qx, then lambda = (py-qy) / (px-qx) */ - if (mp_cmp(px, qx) != 0) { - CHECK_MPI_OK( mp_submod(py, qy, p, &ytemp) ); - CHECK_MPI_OK( mp_submod(px, qx, p, &xtemp) ); - CHECK_MPI_OK( mp_invmod(&xtemp, p, &xtemp) ); - CHECK_MPI_OK( mp_mulmod(&ytemp, &xtemp, p, &lambda) ); - } else { - /* if py != qy or qy = 0, then R = inf */ - if (((mp_cmp(py, qy) != 0)) || (mp_cmp_z(qy) == 0)) { - mp_zero(rx); - mp_zero(ry); - err = MP_OKAY; - goto cleanup; - } - /* lambda = (3qx^2+a) / (2qy) */ - CHECK_MPI_OK( mp_sqrmod(qx, p, &xtemp) ); - mp_set(&temp, 0x3); - CHECK_MPI_OK( mp_mulmod(&xtemp, &temp, p, &xtemp) ); - CHECK_MPI_OK( mp_addmod(&xtemp, a, p, &xtemp) ); - mp_set(&temp, 0x2); - CHECK_MPI_OK( mp_mulmod(qy, &temp, p, &ytemp) ); - CHECK_MPI_OK( mp_invmod(&ytemp, p, &ytemp) ); - CHECK_MPI_OK( mp_mulmod(&xtemp, &ytemp, p, &lambda) ); - } - /* rx = lambda^2 - px - qx */ - CHECK_MPI_OK( mp_sqrmod(&lambda, p, &xtemp) ); - CHECK_MPI_OK( mp_submod(&xtemp, px, p, &xtemp) ); - CHECK_MPI_OK( mp_submod(&xtemp, qx, p, &xtemp) ); - /* ry = (x1-x2) * lambda - y1 */ - CHECK_MPI_OK( mp_submod(qx, &xtemp, p, &ytemp) ); - CHECK_MPI_OK( mp_mulmod(&ytemp, &lambda, p, &ytemp) ); - CHECK_MPI_OK( mp_submod(&ytemp, qy, p, &ytemp) ); - CHECK_MPI_OK( mp_copy(&xtemp, rx) ); - CHECK_MPI_OK( mp_copy(&ytemp, ry) ); - -cleanup: - mp_clear(&lambda); - mp_clear(&temp); - mp_clear(&xtemp); - mp_clear(&ytemp); - return err; -} - -/* Computes R = P - Q. - * Elliptic curve points P, Q, and R can all be identical. - * Uses affine coordinates. - */ -mp_err -GFp_ec_pt_sub_aff(const mp_int *p, const mp_int *a, const mp_int *px, - const mp_int *py, const mp_int *qx, const mp_int *qy, - mp_int *rx, mp_int *ry) -{ - mp_err err = MP_OKAY; - mp_int nqy; - MP_DIGITS(&nqy) = 0; - CHECK_MPI_OK( mp_init(&nqy) ); - /* nqy = -qy */ - CHECK_MPI_OK( mp_neg(qy, &nqy) ); - err = GFp_ec_pt_add_aff(p, a, px, py, qx, &nqy, rx, ry); -cleanup: - mp_clear(&nqy); - return err; -} - -/* Computes R = 2P. - * Elliptic curve points P and R can be identical. - * Uses affine coordinates. - */ -mp_err -GFp_ec_pt_dbl_aff(const mp_int *p, const mp_int *a, const mp_int *px, - const mp_int *py, mp_int *rx, mp_int *ry) -{ - return GFp_ec_pt_add_aff(p, a, px, py, px, py, rx, ry); -} - -/* Gets the i'th bit in the binary representation of a. - * If i >= length(a), then return 0. - * (The above behaviour differs from mpl_get_bit, which - * causes an error if i >= length(a).) - */ -#define MP_GET_BIT(a, i) \ - ((i) >= mpl_significant_bits((a))) ? 0 : mpl_get_bit((a), (i)) - -/* Computes R = nP based on IEEE P1363 A.10.3. - * Elliptic curve points P and R can be identical. - * Uses affine coordinates. - */ -mp_err -GFp_ec_pt_mul_aff(const mp_int *p, const mp_int *a, const mp_int *b, - const mp_int *px, const mp_int *py, const mp_int *n, mp_int *rx, - mp_int *ry) -{ - mp_err err = MP_OKAY; - mp_int k, k3, qx, qy, sx, sy; - int b1, b3, i, l; - - MP_DIGITS(&k) = 0; - MP_DIGITS(&k3) = 0; - MP_DIGITS(&qx) = 0; - MP_DIGITS(&qy) = 0; - MP_DIGITS(&sx) = 0; - MP_DIGITS(&sy) = 0; - CHECK_MPI_OK( mp_init(&k) ); - CHECK_MPI_OK( mp_init(&k3) ); - CHECK_MPI_OK( mp_init(&qx) ); - CHECK_MPI_OK( mp_init(&qy) ); - CHECK_MPI_OK( mp_init(&sx) ); - CHECK_MPI_OK( mp_init(&sy) ); - - /* if n = 0 then r = inf */ - if (mp_cmp_z(n) == 0) { - mp_zero(rx); - mp_zero(ry); - err = MP_OKAY; - goto cleanup; - } - /* Q = P, k = n */ - CHECK_MPI_OK( mp_copy(px, &qx) ); - CHECK_MPI_OK( mp_copy(py, &qy) ); - CHECK_MPI_OK( mp_copy(n, &k) ); - /* if n < 0 Q = -Q, k = -k */ - if (mp_cmp_z(n) < 0) { - CHECK_MPI_OK( mp_neg(&qy, &qy) ); - CHECK_MPI_OK( mp_mod(&qy, p, &qy) ); - CHECK_MPI_OK( mp_neg(&k, &k) ); - CHECK_MPI_OK( mp_mod(&k, p, &k) ); - } -#ifdef EC_DEBUG /* basic double and add method */ - l = mpl_significant_bits(&k) - 1; - mp_zero(&sx); - mp_zero(&sy); - for (i = l; i >= 0; i--) { - /* if k_i = 1, then S = S + Q */ - if (mpl_get_bit(&k, i) != 0) { - CHECK_MPI_OK( GFp_ec_pt_add_aff(p, a, &sx, &sy, - &qx, &qy, &sx, &sy) ); - } - if (i > 0) { - /* S = 2S */ - CHECK_MPI_OK( GFp_ec_pt_dbl_aff(p, a, &sx, &sy, &sx, &sy) ); - } - } -#else /* double and add/subtract method from standard */ - /* k3 = 3 * k */ - mp_set(&k3, 0x3); - CHECK_MPI_OK( mp_mul(&k, &k3, &k3) ); - /* S = Q */ - CHECK_MPI_OK( mp_copy(&qx, &sx) ); - CHECK_MPI_OK( mp_copy(&qy, &sy) ); - /* l = index of high order bit in binary representation of 3*k */ - l = mpl_significant_bits(&k3) - 1; - /* for i = l-1 downto 1 */ - for (i = l - 1; i >= 1; i--) { - /* S = 2S */ - CHECK_MPI_OK( GFp_ec_pt_dbl_aff(p, a, &sx, &sy, &sx, &sy) ); - b3 = MP_GET_BIT(&k3, i); - b1 = MP_GET_BIT(&k, i); - /* if k3_i = 1 and k_i = 0, then S = S + Q */ - if ((b3 == 1) && (b1 == 0)) { - CHECK_MPI_OK( GFp_ec_pt_add_aff(p, a, &sx, &sy, - &qx, &qy, &sx, &sy) ); - /* if k3_i = 0 and k_i = 1, then S = S - Q */ - } else if ((b3 == 0) && (b1 == 1)) { - CHECK_MPI_OK( GFp_ec_pt_sub_aff(p, a, &sx, &sy, - &qx, &qy, &sx, &sy) ); - } - } -#endif - /* output S */ - CHECK_MPI_OK( mp_copy(&sx, rx) ); - CHECK_MPI_OK( mp_copy(&sy, ry) ); - -cleanup: - mp_clear(&k); - mp_clear(&k3); - mp_clear(&qx); - mp_clear(&qy); - mp_clear(&sx); - mp_clear(&sy); - return err; -} - -/* Converts a point P(px, py, pz) from Jacobian projective coordinates to - * affine coordinates R(rx, ry). P and R can share x and y coordinates. - */ -mp_err -GFp_ec_pt_jac2aff(const mp_int *px, const mp_int *py, const mp_int *pz, - const mp_int *p, mp_int *rx, mp_int *ry) -{ - mp_err err = MP_OKAY; - mp_int z1, z2, z3; - MP_DIGITS(&z1) = 0; - MP_DIGITS(&z2) = 0; - MP_DIGITS(&z3) = 0; - CHECK_MPI_OK( mp_init(&z1) ); - CHECK_MPI_OK( mp_init(&z2) ); - CHECK_MPI_OK( mp_init(&z3) ); - - /* if point at infinity, then set point at infinity and exit */ - if (GFp_ec_pt_is_inf_jac(px, py, pz) == MP_YES) { - CHECK_MPI_OK( GFp_ec_pt_set_inf_aff(rx, ry) ); - goto cleanup; - } - - /* transform (px, py, pz) into (px / pz^2, py / pz^3) */ - if (mp_cmp_d(pz, 1) == 0) { - CHECK_MPI_OK( mp_copy(px, rx) ); - CHECK_MPI_OK( mp_copy(py, ry) ); - } else { - CHECK_MPI_OK( mp_invmod(pz, p, &z1) ); - CHECK_MPI_OK( mp_sqrmod(&z1, p, &z2) ); - CHECK_MPI_OK( mp_mulmod(&z1, &z2, p, &z3) ); - CHECK_MPI_OK( mp_mulmod(px, &z2, p, rx) ); - CHECK_MPI_OK( mp_mulmod(py, &z3, p, ry) ); - } - -cleanup: - mp_clear(&z1); - mp_clear(&z2); - mp_clear(&z3); - return err; -} - -/* Checks if point P(px, py, pz) is at infinity. - * Uses Jacobian coordinates. - */ -mp_err -GFp_ec_pt_is_inf_jac(const mp_int *px, const mp_int *py, const mp_int *pz) -{ - return mp_cmp_z(pz); -} - -/* Sets P(px, py, pz) to be the point at infinity. Uses Jacobian - * coordinates. - */ -mp_err -GFp_ec_pt_set_inf_jac(mp_int *px, mp_int *py, mp_int *pz) -{ - mp_zero(pz); - return MP_OKAY; -} - -/* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and - * Q is (qx, qy, qz). Elliptic curve points P, Q, and R can all be - * identical. Uses Jacobian coordinates. - * - * This routine implements Point Addition in the Jacobian Projective - * space as described in the paper "Efficient elliptic curve exponentiation - * using mixed coordinates", by H. Cohen, A Miyaji, T. Ono. - */ -mp_err -GFp_ec_pt_add_jac(const mp_int *p, const mp_int *a, const mp_int *px, - const mp_int *py, const mp_int *pz, const mp_int *qx, - const mp_int *qy, const mp_int *qz, mp_int *rx, mp_int *ry, mp_int *rz) -{ - mp_err err = MP_OKAY; - mp_int n0, u1, u2, s1, s2, H, G; - MP_DIGITS(&n0) = 0; - MP_DIGITS(&u1) = 0; - MP_DIGITS(&u2) = 0; - MP_DIGITS(&s1) = 0; - MP_DIGITS(&s2) = 0; - MP_DIGITS(&H) = 0; - MP_DIGITS(&G) = 0; - CHECK_MPI_OK( mp_init(&n0) ); - CHECK_MPI_OK( mp_init(&u1) ); - CHECK_MPI_OK( mp_init(&u2) ); - CHECK_MPI_OK( mp_init(&s1) ); - CHECK_MPI_OK( mp_init(&s2) ); - CHECK_MPI_OK( mp_init(&H) ); - CHECK_MPI_OK( mp_init(&G) ); - - /* Use point double if pointers are equal. */ - if ((px == qx) && (py == qy) && (pz == qz)) { - err = GFp_ec_pt_dbl_jac(p, a, px, py, pz, rx, ry, rz); - goto cleanup; - } - - /* If either P or Q is the point at infinity, then return - * the other point - */ - if (GFp_ec_pt_is_inf_jac(px, py, pz) == MP_YES) { - CHECK_MPI_OK( mp_copy(qx, rx) ); - CHECK_MPI_OK( mp_copy(qy, ry) ); - CHECK_MPI_OK( mp_copy(qz, rz) ); - goto cleanup; - } - if (GFp_ec_pt_is_inf_jac(qx, qy, qz) == MP_YES) { - CHECK_MPI_OK( mp_copy(px, rx) ); - CHECK_MPI_OK( mp_copy(py, ry) ); - CHECK_MPI_OK( mp_copy(pz, rz) ); - goto cleanup; - } - - /* Compute u1 = px * qz^2, s1 = py * qz^3 */ - if (mp_cmp_d(qz, 1) == 0) { - CHECK_MPI_OK( mp_copy(px, &u1) ); - CHECK_MPI_OK( mp_copy(py, &s1) ); - } else { - CHECK_MPI_OK( mp_sqrmod(qz, p, &n0) ); - CHECK_MPI_OK( mp_mulmod(px, &n0, p, &u1) ); - CHECK_MPI_OK( mp_mulmod(&n0, qz, p, &n0) ); - CHECK_MPI_OK( mp_mulmod(py, &n0, p, &s1) ); - } - - /* Compute u2 = qx * pz^2, s2 = qy * pz^3 */ - if (mp_cmp_d(pz, 1) == 0) { - CHECK_MPI_OK( mp_copy(qx, &u2) ); - CHECK_MPI_OK( mp_copy(qy, &s2) ); - } else { - CHECK_MPI_OK( mp_sqrmod(pz, p, &n0) ); - CHECK_MPI_OK( mp_mulmod(qx, &n0, p, &u2) ); - CHECK_MPI_OK( mp_mulmod(&n0, pz, p, &n0) ); - CHECK_MPI_OK( mp_mulmod(qy, &n0, p, &s2) ); - } - - /* Compute H = u2 - u1 ; G = s2 - s1 */ - CHECK_MPI_OK( mp_submod(&u2, &u1, p, &H) ); - CHECK_MPI_OK( mp_submod(&s2, &s1, p, &G) ); - - if (mp_cmp_z(&H) == 0) { - if (mp_cmp_z(&G) == 0) { - /* P = Q; double */ - err = GFp_ec_pt_dbl_jac(p, a, px, py, pz, - rx, ry, rz); - goto cleanup; - } else { - /* P = -Q; return point at infinity */ - CHECK_MPI_OK( GFp_ec_pt_set_inf_jac(rx, ry, rz) ); - goto cleanup; - } - } - - /* rz = pz * qz * H */ - if (mp_cmp_d(pz, 1) == 0) { - if (mp_cmp_d(qz, 1) == 0) { - /* if pz == qz == 1, then rz = H */ - CHECK_MPI_OK( mp_copy(&H, rz) ); - } else { - CHECK_MPI_OK( mp_mulmod(qz, &H, p, rz) ); - } - } else { - if (mp_cmp_d(qz, 1) == 0) { - CHECK_MPI_OK( mp_mulmod(pz, &H, p, rz) ); - } else { - CHECK_MPI_OK( mp_mulmod(pz, qz, p, &n0) ); - CHECK_MPI_OK( mp_mulmod(&n0, &H, p, rz) ); - } - } - - /* rx = G^2 - H^3 - 2 * u1 * H^2 */ - CHECK_MPI_OK( mp_sqrmod(&G, p, rx) ); - CHECK_MPI_OK( mp_sqrmod(&H, p, &n0) ); - CHECK_MPI_OK( mp_mulmod(&n0, &u1, p, &u1) ); - CHECK_MPI_OK( mp_addmod(&u1, &u1, p, &u2) ); - CHECK_MPI_OK( mp_mulmod(&H, &n0, p, &H) ); - CHECK_MPI_OK( mp_submod(rx, &H, p, rx) ); - CHECK_MPI_OK( mp_submod(rx, &u2, p, rx) ); - - /* ry = - s1 * H^3 + G * (u1 * H^2 - rx) */ - /* (formula based on values of variables before block above) */ - CHECK_MPI_OK( mp_submod(&u1, rx, p, &u1) ); - CHECK_MPI_OK( mp_mulmod(&G, &u1, p, ry) ); - CHECK_MPI_OK( mp_mulmod(&s1, &H, p, &s1) ); - CHECK_MPI_OK( mp_submod(ry, &s1, p, ry) ); - -cleanup: - mp_clear(&n0); - mp_clear(&u1); - mp_clear(&u2); - mp_clear(&s1); - mp_clear(&s2); - mp_clear(&H); - mp_clear(&G); - return err; -} - -/* Computes R = 2P. Elliptic curve points P and R can be identical. Uses - * Jacobian coordinates. - * - * This routine implements Point Doubling in the Jacobian Projective - * space as described in the paper "Efficient elliptic curve exponentiation - * using mixed coordinates", by H. Cohen, A Miyaji, T. Ono. - */ -mp_err -GFp_ec_pt_dbl_jac(const mp_int *p, const mp_int *a, const mp_int *px, - const mp_int *py, const mp_int *pz, mp_int *rx, mp_int *ry, mp_int *rz) -{ - mp_err err = MP_OKAY; - mp_int t0, t1, M, S; - MP_DIGITS(&t0) = 0; - MP_DIGITS(&t1) = 0; - MP_DIGITS(&M) = 0; - MP_DIGITS(&S) = 0; - CHECK_MPI_OK( mp_init(&t0) ); - CHECK_MPI_OK( mp_init(&t1) ); - CHECK_MPI_OK( mp_init(&M) ); - CHECK_MPI_OK( mp_init(&S) ); - - if (GFp_ec_pt_is_inf_jac(px, py, pz) == MP_YES) { - CHECK_MPI_OK( GFp_ec_pt_set_inf_jac(rx, ry, rz) ); - goto cleanup; - } - - if (mp_cmp_d(pz, 1) == 0) { - /* M = 3 * px^2 + a */ - CHECK_MPI_OK( mp_sqrmod(px, p, &t0) ); - CHECK_MPI_OK( mp_addmod(&t0, &t0, p, &M) ); - CHECK_MPI_OK( mp_addmod(&t0, &M, p, &t0) ); - CHECK_MPI_OK( mp_addmod(&t0, a, p, &M) ); - } else if (mp_cmp_int(a, -3) == 0) { - /* M = 3 * (px + pz^2) * (px - pz) */ - CHECK_MPI_OK( mp_sqrmod(pz, p, &M) ); - CHECK_MPI_OK( mp_addmod(px, &M, p, &t0) ); - CHECK_MPI_OK( mp_submod(px, &M, p, &t1) ); - CHECK_MPI_OK( mp_mulmod(&t0, &t1, p, &M) ); - CHECK_MPI_OK( mp_addmod(&M, &M, p, &t0) ); - CHECK_MPI_OK( mp_addmod(&t0, &M, p, &M) ); - } else { - CHECK_MPI_OK( mp_sqrmod(px, p, &t0) ); - CHECK_MPI_OK( mp_addmod(&t0, &t0, p, &M) ); - CHECK_MPI_OK( mp_addmod(&t0, &M, p, &t0) ); - CHECK_MPI_OK( mp_sqrmod(pz, p, &M) ); - CHECK_MPI_OK( mp_sqrmod(&M, p, &M) ); - CHECK_MPI_OK( mp_mulmod(&M, a, p, &M) ); - CHECK_MPI_OK( mp_addmod(&M, &t0, p, &M) ); - } - - /* rz = 2 * py * pz */ - if (mp_cmp_d(pz, 1) == 0) { - CHECK_MPI_OK( mp_addmod(py, py, p, rz) ); - CHECK_MPI_OK( mp_sqrmod(rz, p, &t0) ); - } else { - CHECK_MPI_OK( mp_addmod(py, py, p, &t0) ); - CHECK_MPI_OK( mp_mulmod(&t0, pz, p, rz) ); - CHECK_MPI_OK( mp_sqrmod(&t0, p, &t0) ); - } - - /* S = 4 * px * py^2 = pz * (2 * py)^2 */ - CHECK_MPI_OK( mp_mulmod(px, &t0, p, &S) ); - - /* rx = M^2 - 2 * S */ - CHECK_MPI_OK( mp_addmod(&S, &S, p, &t1) ); - CHECK_MPI_OK( mp_sqrmod(&M, p, rx) ); - CHECK_MPI_OK( mp_submod(rx, &t1, p, rx) ); - - /* ry = M * (S - rx) - 8 * py^4 */ - CHECK_MPI_OK( mp_sqrmod(&t0, p, &t1) ); - if (mp_isodd(&t1)) { - CHECK_MPI_OK( mp_add(&t1, p, &t1) ); - } - CHECK_MPI_OK( mp_div_2(&t1, &t1) ); - CHECK_MPI_OK( mp_submod(&S, rx, p, &S) ); - CHECK_MPI_OK( mp_mulmod(&M, &S, p, &M) ); - CHECK_MPI_OK( mp_submod(&M, &t1, p, ry) ); - -cleanup: - mp_clear(&t0); - mp_clear(&t1); - mp_clear(&M); - mp_clear(&S); - return err; -} - -/* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters - * a, b and p are the elliptic curve coefficients and the prime that - * determines the field GFp. Elliptic curve points P and R can be - * identical. Uses Jacobian coordinates. - */ -mp_err -GFp_ec_pt_mul_jac(const mp_int *p, const mp_int *a, const mp_int *b, - const mp_int *px, const mp_int *py, const mp_int *n, - mp_int *rx, mp_int *ry) -{ - mp_err err = MP_OKAY; - mp_int k, qx, qy, qz, sx, sy, sz; - int i, l; - - MP_DIGITS(&k) = 0; - MP_DIGITS(&qx) = 0; - MP_DIGITS(&qy) = 0; - MP_DIGITS(&qz) = 0; - MP_DIGITS(&sx) = 0; - MP_DIGITS(&sy) = 0; - MP_DIGITS(&sz) = 0; - CHECK_MPI_OK( mp_init(&k) ); - CHECK_MPI_OK( mp_init(&qx) ); - CHECK_MPI_OK( mp_init(&qy) ); - CHECK_MPI_OK( mp_init(&qz) ); - CHECK_MPI_OK( mp_init(&sx) ); - CHECK_MPI_OK( mp_init(&sy) ); - CHECK_MPI_OK( mp_init(&sz) ); - - /* if n = 0 then r = inf */ - if (mp_cmp_z(n) == 0) { - mp_zero(rx); - mp_zero(ry); - err = MP_OKAY; - goto cleanup; - /* if n < 0 then out of range error */ - } else if (mp_cmp_z(n) < 0) { - err = MP_RANGE; - goto cleanup; - } - /* Q = P, k = n */ - CHECK_MPI_OK( mp_copy(px, &qx) ); - CHECK_MPI_OK( mp_copy(py, &qy) ); - CHECK_MPI_OK( mp_set_int(&qz, 1) ); - CHECK_MPI_OK( mp_copy(n, &k) ); - - /* double and add method */ - l = mpl_significant_bits(&k) - 1; - mp_zero(&sx); - mp_zero(&sy); - mp_zero(&sz); - for (i = l; i >= 0; i--) { - /* if k_i = 1, then S = S + Q */ - if (MP_GET_BIT(&k, i) != 0) { - CHECK_MPI_OK( GFp_ec_pt_add_jac(p, a, &sx, &sy, &sz, - &qx, &qy, &qz, &sx, &sy, &sz) ); - } - if (i > 0) { - /* S = 2S */ - CHECK_MPI_OK( GFp_ec_pt_dbl_jac(p, a, &sx, &sy, &sz, - &sx, &sy, &sz) ); - } - } - - /* convert result S to affine coordinates */ - CHECK_MPI_OK( GFp_ec_pt_jac2aff(&sx, &sy, &sz, p, rx, ry) ); - -cleanup: - mp_clear(&k); - mp_clear(&qx); - mp_clear(&qy); - mp_clear(&qz); - mp_clear(&sx); - mp_clear(&sy); - mp_clear(&sz); - return err; -} -#endif /* NSS_ENABLE_ECC */ |