diff options
author | nelsonb%netscape.com <devnull@localhost> | 2003-03-26 05:03:11 +0000 |
---|---|---|
committer | nelsonb%netscape.com <devnull@localhost> | 2003-03-26 05:03:11 +0000 |
commit | fd6e4219453a1def1d699a3058be3314a651b0b4 (patch) | |
tree | 87bf37355f6ec96ae88d5b6a13f3d88f32ecb783 | |
parent | e173c4d2d1aa382b60e27ca9120a77eea7a2a876 (diff) | |
download | nss-hg-fd6e4219453a1def1d699a3058be3314a651b0b4.tar.gz |
Add support for Elliptic Curve Cryptography. Bug 195135.
Contributor(s):
* Sheueling Chang Shantz <sheueling.chang@sun.com> and
* Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
Added Files:
GF2m_ecl.c GF2m_ecl.h mpi/mp_gf2m.c mpi/mp_gf2m.h
mpi/tests/mptest-b.c
-rw-r--r-- | security/nss/lib/freebl/GF2m_ecl.c | 539 | ||||
-rw-r--r-- | security/nss/lib/freebl/GF2m_ecl.h | 96 | ||||
-rw-r--r-- | security/nss/lib/freebl/mpi/mp_gf2m.c | 570 | ||||
-rw-r--r-- | security/nss/lib/freebl/mpi/mp_gf2m.h | 62 | ||||
-rw-r--r-- | security/nss/lib/freebl/mpi/tests/mptest-b.c | 211 |
5 files changed, 1478 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/GF2m_ecl.c b/security/nss/lib/freebl/GF2m_ecl.c new file mode 100644 index 000000000..09fbf7979 --- /dev/null +++ b/security/nss/lib/freebl/GF2m_ecl.c @@ -0,0 +1,539 @@ +/* + * 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 binary polynomial + * field curves. + * + * The Initial Developer of the Original Code is Sun Microsystems, Inc. + * Portions created by Sun Microsystems, Inc. are Copyright (C) 2003 + * Sun Microsystems, Inc. All Rights Reserved. + * + * Contributor(s): + * Douglas Stebila <douglas@stebila.ca> + * + * 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. + * + */ + +#ifdef NSS_ENABLE_ECC +/* + * GF2m_ecl.c: Contains an implementation of elliptic curve math library + * for curves over GF2m. + * + * XXX Can be moved to a separate subdirectory later. + * + */ + +#include "GF2m_ecl.h" +#include "mpi/mplogic.h" +#include "mpi/mp_gf2m.h" +#include <stdlib.h> + +/* Checks if point P(px, py) is at infinity. Uses affine coordinates. */ +mp_err +GF2m_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 +GF2m_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.2. + * Elliptic curve points P, Q, and R can all be identical. + * Uses affine coordinates. + */ +mp_err +GF2m_ec_pt_add_aff(const mp_int *pp, 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, xtemp, ytemp; + unsigned int *p; + int p_size; + + p_size = mp_bpoly2arr(pp, p, 0) + 1; + p = (unsigned int *) (malloc(sizeof(unsigned int) * p_size)); + if (p == NULL) goto cleanup; + mp_bpoly2arr(pp, p, p_size); + + CHECK_MPI_OK( mp_init(&lambda) ); + CHECK_MPI_OK( mp_init(&xtemp) ); + CHECK_MPI_OK( mp_init(&ytemp) ); + /* if P = inf, then R = Q */ + if (GF2m_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 (GF2m_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), + * xtemp = a + lambda^2 + lambda + px + qx + */ + if (mp_cmp(px, qx) != 0) { + CHECK_MPI_OK( mp_badd(py, qy, &ytemp) ); + CHECK_MPI_OK( mp_badd(px, qx, &xtemp) ); + CHECK_MPI_OK( mp_bdivmod(&ytemp, &xtemp, pp, p, &lambda) ); + CHECK_MPI_OK( mp_bsqrmod(&lambda, p, &xtemp) ); + CHECK_MPI_OK( mp_badd(&xtemp, &lambda, &xtemp) ); + CHECK_MPI_OK( mp_badd(&xtemp, a, &xtemp) ); + CHECK_MPI_OK( mp_badd(&xtemp, px, &xtemp) ); + CHECK_MPI_OK( mp_badd(&xtemp, qx, &xtemp) ); + } else { + /* if py != qy or qx = 0, then R = inf */ + if (((mp_cmp(py, qy) != 0)) || (mp_cmp_z(qx) == 0)) { + mp_zero(rx); + mp_zero(ry); + err = MP_OKAY; + goto cleanup; + } + /* lambda = qx + qy / qx */ + CHECK_MPI_OK( mp_bdivmod(qy, qx, pp, p, &lambda) ); + CHECK_MPI_OK( mp_badd(&lambda, qx, &lambda) ); + /* xtemp = a + lambda^2 + lambda */ + CHECK_MPI_OK( mp_bsqrmod(&lambda, p, &xtemp) ); + CHECK_MPI_OK( mp_badd(&xtemp, &lambda, &xtemp) ); + CHECK_MPI_OK( mp_badd(&xtemp, a, &xtemp) ); + } + /* ry = (qx + xtemp) * lambda + xtemp + qy */ + CHECK_MPI_OK( mp_badd(qx, &xtemp, &ytemp) ); + CHECK_MPI_OK( mp_bmulmod(&ytemp, &lambda, p, &ytemp) ); + CHECK_MPI_OK( mp_badd(&ytemp, &xtemp, &ytemp) ); + CHECK_MPI_OK( mp_badd(&ytemp, qy, ry) ); + /* rx = xtemp */ + CHECK_MPI_OK( mp_copy(&xtemp, rx) ); + +cleanup: + mp_clear(&lambda); + mp_clear(&xtemp); + mp_clear(&ytemp); + free(p); + return err; +} + +/* Computes R = P - Q. + * Elliptic curve points P, Q, and R can all be identical. + * Uses affine coordinates. + */ +mp_err +GF2m_ec_pt_sub_aff(const mp_int *pp, 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 = qx+qy */ + CHECK_MPI_OK( mp_badd(qx, qy, &nqy) ); + err = GF2m_ec_pt_add_aff(pp, 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 +GF2m_ec_pt_dbl_aff(const mp_int *pp, const mp_int *a, const mp_int *px, + const mp_int *py, mp_int *rx, mp_int *ry) +{ + return GF2m_ec_pt_add_aff(pp, 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 +GF2m_ec_pt_mul_aff(const mp_int *pp, 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; + unsigned int *p; + int p_size; + + 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) ); + + p_size = mp_bpoly2arr(pp, p, 0) + 1; + p = (unsigned int *) (malloc(sizeof(unsigned int) * p_size)); + if (p == NULL) goto cleanup; + mp_bpoly2arr(pp, p, p_size); + + /* 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 then Q = -Q, k = -k */ + if (mp_cmp_z(n) < 0) { + CHECK_MPI_OK( mp_badd(&qx, &qy, &qy) ); + CHECK_MPI_OK( mp_neg(&k, &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( GF2m_ec_pt_add_aff(pp, a, &sx, &sy, &qx, &qy, &sx, &sy) ); + } + if (i > 0) { + /* S = 2S */ + CHECK_MPI_OK( GF2m_ec_pt_dbl_aff(pp, 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( GF2m_ec_pt_dbl_aff(pp, 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( GF2m_ec_pt_add_aff(pp, 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( GF2m_ec_pt_sub_aff(pp, 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); + free(p); + return err; +} + +/* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective + * coordinates. + * Uses algorithm Mdouble in appendix of + * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over + * GF(2^m) without precomputation". + * modified to not require precomputation of c=b^{2^{m-1}}. + */ +static mp_err +gf2m_Mdouble(const mp_int *pp, const unsigned int p[], const mp_int *a, + const mp_int *b, mp_int *x, mp_int *z) +{ + mp_err err = MP_OKAY; + mp_int t1; + + MP_DIGITS(&t1) = 0; + CHECK_MPI_OK( mp_init(&t1) ); + + CHECK_MPI_OK( mp_bsqrmod(x, p, x) ); + CHECK_MPI_OK( mp_bsqrmod(z, p, &t1) ); + CHECK_MPI_OK( mp_bmulmod(x, &t1, p, z) ); + CHECK_MPI_OK( mp_bsqrmod(x, p, x) ); + CHECK_MPI_OK( mp_bsqrmod(&t1, p, &t1) ); + CHECK_MPI_OK( mp_bmulmod(b, &t1, p, &t1) ); + CHECK_MPI_OK( mp_badd(x, &t1, x) ); + +cleanup: + mp_clear(&t1); + return err; +} + +/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery + * projective coordinates. + * Uses algorithm Madd in appendix of + * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over + * GF(2^m) without precomputation". + */ +static mp_err +gf2m_Madd(const mp_int *pp, const unsigned int p[], const mp_int *a, + const mp_int *b, const mp_int *x, mp_int *x1, mp_int *z1, mp_int *x2, + mp_int *z2) +{ + mp_err err = MP_OKAY; + mp_int t1, t2; + + MP_DIGITS(&t1) = 0; + MP_DIGITS(&t2) = 0; + CHECK_MPI_OK( mp_init(&t1) ); + CHECK_MPI_OK( mp_init(&t2) ); + + CHECK_MPI_OK( mp_copy(x, &t1) ); + CHECK_MPI_OK( mp_bmulmod(x1, z2, p, x1) ); + CHECK_MPI_OK( mp_bmulmod(z1, x2, p, z1) ); + CHECK_MPI_OK( mp_bmulmod(x1, z1, p, &t2) ); + CHECK_MPI_OK( mp_badd(z1, x1, z1) ); + CHECK_MPI_OK( mp_bsqrmod(z1, p, z1) ); + CHECK_MPI_OK( mp_bmulmod(z1, &t1, p, x1) ); + CHECK_MPI_OK( mp_badd(x1, &t2, x1) ); + +cleanup: + mp_clear(&t1); + mp_clear(&t2); + return err; +} + +/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) + * using Montgomery point multiplication algorithm Mxy() in appendix of + * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over + * GF(2^m) without precomputation". + * Returns: + * 0 on error + * 1 if return value should be the point at infinity + * 2 otherwise + */ +static int +gf2m_Mxy(const mp_int *pp, const unsigned int p[], const mp_int *a, + const mp_int *b, const mp_int *x, const mp_int *y, mp_int *x1, mp_int *z1, + mp_int *x2, mp_int *z2) +{ + mp_err err = MP_OKAY; + int ret; + mp_int t3, t4, t5; + + MP_DIGITS(&t3) = 0; + MP_DIGITS(&t4) = 0; + MP_DIGITS(&t5) = 0; + CHECK_MPI_OK( mp_init(&t3) ); + CHECK_MPI_OK( mp_init(&t4) ); + CHECK_MPI_OK( mp_init(&t5) ); + + if (mp_cmp_z(z1) == 0) { + mp_zero(x2); + mp_zero(z2); + ret = 1; + goto cleanup; + } + + if (mp_cmp_z(z2) == 0) { + CHECK_MPI_OK( mp_copy(x, x2) ); + CHECK_MPI_OK( mp_badd(x, y, z2) ); + ret = 2; + goto cleanup; + } + + mp_set(&t5, 0x1); + + CHECK_MPI_OK( mp_bmulmod(z1, z2, p, &t3) ); + + CHECK_MPI_OK( mp_bmulmod(z1, x, p, z1) ); + CHECK_MPI_OK( mp_badd(z1, x1, z1) ); + CHECK_MPI_OK( mp_bmulmod(z2, x, p, z2) ); + CHECK_MPI_OK( mp_bmulmod(z2, x1, p, x1) ); + CHECK_MPI_OK( mp_badd(z2, x2, z2) ); + + CHECK_MPI_OK( mp_bmulmod(z2, z1, p, z2) ); + CHECK_MPI_OK( mp_bsqrmod(x, p, &t4) ); + CHECK_MPI_OK( mp_badd(&t4, y, &t4) ); + CHECK_MPI_OK( mp_bmulmod(&t4, &t3, p, &t4) ); + CHECK_MPI_OK( mp_badd(&t4, z2, &t4) ); + + CHECK_MPI_OK( mp_bmulmod(&t3, x, p, &t3) ); + CHECK_MPI_OK( mp_bdivmod(&t5, &t3, pp, p, &t3) ); + CHECK_MPI_OK( mp_bmulmod(&t3, &t4, p, &t4) ); + CHECK_MPI_OK( mp_bmulmod(x1, &t3, p, x2) ); + CHECK_MPI_OK( mp_badd(x2, x, z2) ); + + CHECK_MPI_OK( mp_bmulmod(z2, &t4, p, z2) ); + CHECK_MPI_OK( mp_badd(z2, y, z2) ); + + ret = 2; + +cleanup: + mp_clear(&t3); + mp_clear(&t4); + mp_clear(&t5); + if (err == MP_OKAY) { + return ret; + } else { + return 0; + } +} + +/* Computes R = nP based on algorithm 2P of + * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over + * GF(2^m) without precomputation". + * Elliptic curve points P and R can be identical. + * Uses Montgomery projective coordinates. + */ +mp_err +GF2m_ec_pt_mul_mont(const mp_int *pp, 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 x1, x2, z1, z2; + int i, j; + mp_digit top_bit, mask; + unsigned int *p; + int p_size; + + MP_DIGITS(&x1) = 0; + MP_DIGITS(&x2) = 0; + MP_DIGITS(&z1) = 0; + MP_DIGITS(&z2) = 0; + CHECK_MPI_OK( mp_init(&x1) ); + CHECK_MPI_OK( mp_init(&x2) ); + CHECK_MPI_OK( mp_init(&z1) ); + CHECK_MPI_OK( mp_init(&z2) ); + + p_size = mp_bpoly2arr(pp, p, 0) + 1; + p = (unsigned int *) (malloc(sizeof(unsigned int) * p_size)); + if (p == NULL) goto cleanup; + mp_bpoly2arr(pp, p, p_size); + + /* if result should be point at infinity */ + if ((mp_cmp_z(n) == 0) || (GF2m_ec_pt_is_inf_aff(px, py) == MP_YES)) { + CHECK_MPI_OK( GF2m_ec_pt_set_inf_aff(rx, ry) ); + goto cleanup; + } + + CHECK_MPI_OK( mp_copy(rx, &x2) ); /* x2 = rx */ + CHECK_MPI_OK( mp_copy(ry, &z2) ); /* z2 = ry */ + + CHECK_MPI_OK( mp_copy(px, &x1) ); /* x1 = px */ + mp_set(&z1, 0x1); /* z1 = 1 */ + CHECK_MPI_OK( mp_bsqrmod(&x1, p, &z2) ); /* z2 = x1^2 = x2^2 */ + CHECK_MPI_OK( mp_bsqrmod(&z2, p, &x2) ); + CHECK_MPI_OK( mp_badd(&x2, b, &x2) ); /* x2 = px^4 + b */ + + /* find top-most bit and go one past it */ + i = MP_USED(n) - 1; + j = MP_DIGIT_BIT - 1; + top_bit = 1; + top_bit <<= MP_DIGIT_BIT - 1; + mask = top_bit; + while (!(MP_DIGITS(n)[i] & mask)) { + mask >>= 1; + j--; + } + mask >>= 1; j--; + + /* if top most bit was at word break, go to next word */ + if (!mask) { + i--; + j = MP_DIGIT_BIT - 1; + mask = top_bit; + } + + for (; i >= 0; i--) { + for (; j >= 0; j--) { + if (MP_DIGITS(n)[i] & mask) { + CHECK_MPI_OK( gf2m_Madd(pp, p, a, b, px, &x1, &z1, &x2, &z2) ); + CHECK_MPI_OK( gf2m_Mdouble(pp, p, a, b, &x2, &z2) ); + } else { + CHECK_MPI_OK( gf2m_Madd(pp, p, a, b, px, &x2, &z2, &x1, &z1) ); + CHECK_MPI_OK( gf2m_Mdouble(pp, p, a, b, &x1, &z1) ); + } + mask >>= 1; + } + j = MP_DIGIT_BIT - 1; + mask = top_bit; + } + + /* convert out of "projective" coordinates */ + i = gf2m_Mxy(pp, p, a, b, px, py, &x1, &z1, &x2, &z2); + if (i == 0) { + err = MP_BADARG; + goto cleanup; + } else if (i == 1) { + CHECK_MPI_OK( GF2m_ec_pt_set_inf_aff(rx, ry) ); + } else { + CHECK_MPI_OK( mp_copy(&x2, rx) ); + CHECK_MPI_OK( mp_copy(&z2, ry) ); + } + +cleanup: + mp_clear(&x1); + mp_clear(&x2); + mp_clear(&z1); + mp_clear(&z2); + free(p); + return err; +} + +#endif /* NSS_ENABLE_ECC */ diff --git a/security/nss/lib/freebl/GF2m_ecl.h b/security/nss/lib/freebl/GF2m_ecl.h new file mode 100644 index 000000000..e562c2fc0 --- /dev/null +++ b/security/nss/lib/freebl/GF2m_ecl.h @@ -0,0 +1,96 @@ +/* + * 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 binary polynomial + * field curves. + * + * The Initial Developer of the Original Code is Sun Microsystems, Inc. + * Portions created by Sun Microsystems, Inc. are Copyright (C) 2003 + * Sun Microsystems, Inc. All Rights Reserved. + * + * Contributor(s): + * Douglas Stebila <douglas@stebila.ca> + * + * 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. + * + */ + +#ifndef __gf2m_ecl_h_ +#define __gf2m_ecl_h_ +#ifdef NSS_ENABLE_ECC + +#include "secmpi.h" + +/* Checks if point P(px, py) is at infinity. Uses affine coordinates. */ +mp_err GF2m_ec_pt_is_inf_aff(const mp_int *px, const mp_int *py); + +/* Sets P(px, py) to be the point at infinity. Uses affine coordinates. */ +mp_err GF2m_ec_pt_set_inf_aff(mp_int *px, mp_int *py); + +/* Computes R = P + Q where R is (rx, ry), P is (px, py) and Q is (qx, qy). + * Uses affine coordinates. + */ +mp_err GF2m_ec_pt_add_aff(const mp_int *pp, 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); + +/* Computes R = P - Q. Uses affine coordinates. */ +mp_err GF2m_ec_pt_sub_aff(const mp_int *pp, 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); + +/* Computes R = 2P. Uses affine coordinates. */ +mp_err GF2m_ec_pt_dbl_aff(const mp_int *pp, const mp_int *a, + const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry); + +/* 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 irreducible that + * determines the field GF2m. Uses affine coordinates. + */ +mp_err GF2m_ec_pt_mul_aff(const mp_int *pp, 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); + +/* 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 irreducible that + * determines the field GF2m. Uses Montgomery projective coordinates. + */ +mp_err GF2m_ec_pt_mul_mont(const mp_int *pp, 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); + +#define GF2m_ec_pt_is_inf(px, py) GF2m_ec_pt_is_inf_aff((px), (py)) +#define GF2m_ec_pt_add(p, a, px, py, qx, qy, rx, ry) \ + GF2m_ec_pt_add_aff((p), (a), (px), (py), (qx), (qy), (rx), (ry)) + +#define GF2m_ECL_MONTGOMERY +#ifdef GF2m_ECL_AFFINE +#define GF2m_ec_pt_mul(pp, a, b, px, py, n, rx, ry) \ + GF2m_ec_pt_mul_aff((pp), (a), (b), (px), (py), (n), (rx), (ry)) +#elif defined(GF2m_ECL_MONTGOMERY) +#define GF2m_ec_pt_mul(pp, a, b, px, py, n, rx, ry) \ + GF2m_ec_pt_mul_mont((pp), (a), (b), (px), (py), (n), (rx), (ry)) +#endif /* GF2m_ECL_AFFINE or GF2m_ECL_MONTGOMERY */ + +#endif /* NSS_ENABLE_ECC */ +#endif /* __gf2m_ecl_h_ */ diff --git a/security/nss/lib/freebl/mpi/mp_gf2m.c b/security/nss/lib/freebl/mpi/mp_gf2m.c new file mode 100644 index 000000000..93d419611 --- /dev/null +++ b/security/nss/lib/freebl/mpi/mp_gf2m.c @@ -0,0 +1,570 @@ +/* + * 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 Multi-precision Binary Polynomial Arithmetic + * Library. + * + * The Initial Developer of the Original Code is Sun Microsystems, Inc. + * Portions created by Sun Microsystems, Inc. are Copyright (C) 2003 + * Sun Microsystems, Inc. All Rights Reserved. + * + * Contributor(s): + * Sheueling Chang Shantz <sheueling.chang@sun.com> and + * Douglas Stebila <douglas@stebila.ca> of Sun Laboratories. + * + * 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. + * + */ + +#include "mp_gf2m.h" +#include "mplogic.h" +#include "mpi-priv.h" + +static const mp_digit SQR_tb[16] = +{ + 0, 1, 4, 5, 16, 17, 20, 21, + 64, 65, 68, 69, 80, 81, 84, 85 +}; + +#if defined(MP_USE_UINT_DIGIT) +#define MP_DIGIT_BITS 32 + +/* Platform-specific macros for fast binary polynomial squaring. */ + +#define gf2m_SQR1(w) \ + SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \ + SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF] +#define gf2m_SQR0(w) \ + SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ + SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] + +/* Multiply two binary polynomials mp_digits a, b. + * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1. + * Output in two mp_digits rh, rl. + */ +static void +s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b) +{ + register mp_digit h, l, s; + mp_digit tab[8], top2b = a >> 30; + register mp_digit a1, a2, a4; + + a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1; + + tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; + tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4; + + s = tab[b & 0x7]; l = s; + s = tab[b >> 3 & 0x7]; l ^= s << 3; h = s >> 29; + s = tab[b >> 6 & 0x7]; l ^= s << 6; h ^= s >> 26; + s = tab[b >> 9 & 0x7]; l ^= s << 9; h ^= s >> 23; + s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20; + s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17; + s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14; + s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11; + s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >> 8; + s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >> 5; + s = tab[b >> 30 ]; l ^= s << 30; h ^= s >> 2; + + /* compensate for the top two bits of a */ + + if (top2b & 01) { l ^= b << 30; h ^= b >> 2; } + if (top2b & 02) { l ^= b << 31; h ^= b >> 1; } + + *rh = h; *rl = l; +} +#endif + +#if defined(MP_USE_LONG_DIGIT) || defined(MP_USE_LONG_LONG_DIGIT) +#define MP_DIGIT_BITS 64 +#define MP_TOP_BIT + +/* Platform-specific fast binary polynomial squaring. */ +#define gf2m_SQR1(w) \ + SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \ + SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \ + SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \ + SQR_tb[(w) >> 36 & 0xF] << 8 | SQR_tb[(w) >> 32 & 0xF] +#define gf2m_SQR0(w) \ + SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \ + SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \ + SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ + SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] + +/* Multiply two binary polynomials mp_digits a, b, output in rh, rl */ +static void +s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b) +{ + register mp_digit h, l, s; + mp_digit tab[16], top3b = a >> 61; + register mp_digit a1, a2, a4, a8; + + a1 = a & (0x1FFFFFFFFFFFFFFF); a2 = a1 << 1; + a4 = a2 << 1; a8 = a4 << 1; + tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2; + tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4; + tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8; + tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8; + + s = tab[b & 0xF]; l = s; + s = tab[b >> 4 & 0xF]; l ^= s << 4; h = s >> 60; + s = tab[b >> 8 & 0xF]; l ^= s << 8; h ^= s >> 56; + s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52; + s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48; + s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44; + s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40; + s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36; + s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32; + s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28; + s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24; + s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20; + s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16; + s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12; + s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >> 8; + s = tab[b >> 60 ]; l ^= s << 60; h ^= s >> 4; + + /* compensate for the top three bits of a */ + + if (top3b & 01) { l ^= b << 61; h ^= b >> 3; } + if (top3b & 02) { l ^= b << 62; h ^= b >> 2; } + if (top3b & 04) { l ^= b << 63; h ^= b >> 1; } + + *rh = h; *rl = l; +} +#endif + +#if 0 /* to be used later */ +/* Compute xor-multiply of two binary polynomials (a1, a0) x (b1, b0) + * result is a binary polynomial in 4 mp_digits r[4]. + * The caller MUST ensure that r has the right amount of space allocated. + */ +static void +s_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1, + const mp_digit b0) +{ + mp_digit m1, m0; + /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */ + s_bmul_1x1(r+3, r+2, a1, b1); + s_bmul_1x1(r+1, r, a0, b0); + s_bmul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1); + /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */ + r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */ + r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */ +} +#endif /* 0 */ + +/* Compute addition of two binary polynomials a and b, + * store result in c; c could be a or b, a and b could be equal; + * c is the bitwise XOR of a and b. + */ +mp_err +mp_badd(const mp_int *a, const mp_int *b, mp_int *c) +{ + mp_digit *pa, *pb, *pc; + mp_size ix; + mp_size used_pa, used_pb; + mp_err res = MP_OKAY; + + /* Add all digits up to the precision of b. If b had more + * precision than a initially, swap a, b first + */ + if (MP_USED(a) >= MP_USED(b)) { + pa = MP_DIGITS(a); + pb = MP_DIGITS(b); + used_pa = MP_USED(a); + used_pb = MP_USED(b); + } else { + pa = MP_DIGITS(b); + pb = MP_DIGITS(a); + used_pa = MP_USED(b); + used_pb = MP_USED(a); + } + + /* Make sure c has enough precision for the output value */ + MP_CHECKOK( s_mp_pad(c, used_pa) ); + + /* Do word-by-word xor */ + pc = MP_DIGITS(c); + for (ix = 0; ix < used_pb; ix++) { + (*pc++) = (*pa++) ^ (*pb++); + } + + /* Finish the rest of digits until we're actually done */ + for (; ix < used_pa; ++ix) { + *pc++ = *pa++; + } + + MP_USED(c) = used_pa; + MP_SIGN(c) = ZPOS; + s_mp_clamp(c); + +CLEANUP: + return res; +} + +#define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) ); + +/* Compute binary polynomial multiply d = a * b */ +static void +s_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d) +{ + mp_digit a_i, a0b0, a1b1, carry = 0; + while (a_len--) { + a_i = *a++; + s_bmul_1x1(&a1b1, &a0b0, a_i, b); + *d++ = a0b0 ^ carry; + carry = a1b1; + } + *d = carry; +} + +/* Compute binary polynomial xor multiply accumulate d ^= a * b */ +static void +s_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d) +{ + mp_digit a_i, a0b0, a1b1, carry = 0; + while (a_len--) { + a_i = *a++; + s_bmul_1x1(&a1b1, &a0b0, a_i, b); + *d++ ^= a0b0 ^ carry; + carry = a1b1; + } + *d ^= carry; +} + +/* Compute binary polynomial xor multiply c = a * b. + * All parameters may be identical. + */ +mp_err +mp_bmul(const mp_int *a, const mp_int *b, mp_int *c) +{ + mp_digit *pb, b_i; + mp_int tmp; + mp_size ib, a_used, b_used; + mp_err res = MP_OKAY; + + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG); + + if (a == c) { + MP_CHECKOK( mp_init_copy(&tmp, a) ); + if (a == b) + b = &tmp; + a = &tmp; + } else if (b == c) { + MP_CHECKOK( mp_init_copy(&tmp, b) ); + b = &tmp; + } else MP_DIGITS(&tmp) = 0; + + if (MP_USED(a) < MP_USED(b)) { + const mp_int *xch = b; /* switch a and b if b longer */ + b = a; + a = xch; + } + + MP_USED(c) = 1; MP_DIGIT(c, 0) = 0; + MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) ); + + pb = MP_DIGITS(b); + s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c)); + + /* Outer loop: Digits of b */ + a_used = MP_USED(a); + b_used = MP_USED(b); + for (ib = 1; ib < b_used; ib++) { + b_i = *pb++; + + /* Inner product: Digits of a */ + if (b_i) + s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib); + else + MP_DIGIT(c, ib + a_used) = b_i; + } + + s_mp_clamp(c); + + SIGN(c) = ZPOS; + +CLEANUP: + mp_clear(&tmp); + return res; +} + + +/* Compute modular reduction of a and store result in r. + * r could be a. + * For modular arithmetic, the irreducible polynomial f(t) is represented + * as an array of int[], where f(t) is of the form: + * f(t) = t^p[0] + t^p[1] + ... + t^p[k] + * where m = p[0] > p[1] > ... > p[k] = 0. + */ +int +mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r) +{ + int j, k; + int n, dN, d0, d1; + mp_digit zz, *z, tmp; + mp_size used; + mp_err res = MP_OKAY; + + /* The algorithm does the reduction in place in r, + * if a != r, copy a into r first so reduction can be done in r + */ + if (a != r) { + MP_CHECKOK( mp_copy(a, r) ); + } + z = MP_DIGITS(r); + + /* start reduction */ + dN = p[0] / MP_DIGIT_BITS; + used = MP_USED(r); + + for (j = used - 1; j > dN;) { + + zz = z[j]; + if (zz == 0) { + j--; continue; + } + z[j] = 0; + + for (k = 1; p[k] > 0; k++) { + /* reducing component t^p[k] */ + n = p[0] - p[k]; + d0 = n % MP_DIGIT_BITS; + d1 = MP_DIGIT_BITS - d0; + n /= MP_DIGIT_BITS; + z[j-n] ^= (zz>>d0); + if (d0) + z[j-n-1] ^= (zz<<d1); + } + + /* reducing component t^0 */ + n = dN; + d0 = p[0] % MP_DIGIT_BITS; + d1 = MP_DIGIT_BITS - d0; + z[j-n] ^= (zz >> d0); + if (d0) + z[j-n-1] ^= (zz << d1); + + } + + /* final round of reduction */ + while (j == dN) { + + d0 = p[0] % MP_DIGIT_BITS; + zz = z[dN] >> d0; + if (zz == 0) break; + d1 = MP_DIGIT_BITS - d0; + + /* clear up the top d1 bits */ + if (d0) z[dN] = (z[dN] << d1) >> d1; + *z ^= zz; /* reduction t^0 component */ + + for (k = 1; p[k] > 0; k++) { + /* reducing component t^p[k]*/ + n = p[k] / MP_DIGIT_BITS; + d0 = p[k] % MP_DIGIT_BITS; + d1 = MP_DIGIT_BITS - d0; + z[n] ^= (zz << d0); + tmp = zz >> d1; + if (d0 && tmp) + z[n+1] ^= tmp; + } + } + + s_mp_clamp(r); +CLEANUP: + return res; +} + +/* Compute the product of two polynomials a and b, reduce modulo p, + * Store the result in r. r could be a or b; a could be b. + */ +mp_err +mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r) +{ + mp_err res; + + if (a == b) return mp_bsqrmod(a, p, r); + if ((res = mp_bmul(a, b, r) ) != MP_OKAY) + return res; + return mp_bmod(r, p, r); +} + +/* Compute binary polynomial squaring c = a*a mod p . + * Parameter r and a can be identical. + */ + +mp_err +mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r) +{ + mp_digit *pa, *pr, a_i; + mp_int tmp; + mp_size ia, a_used; + mp_err res; + + ARGCHK(a != NULL && r != NULL, MP_BADARG); + + if (a == r) { + MP_CHECKOK( mp_init_copy(&tmp, a) ); + a = &tmp; + } else MP_DIGITS(&tmp) = 0; + + MP_USED(r) = 1; MP_DIGIT(r, 0) = 0; + MP_CHECKOK( s_mp_pad(r, 2*USED(a)) ); + + pa = MP_DIGITS(a); + pr = MP_DIGITS(r); + a_used = MP_USED(a); + + for (ia = 0; ia < a_used; ia++) { + a_i = *pa++; + *pr++ = gf2m_SQR0(a_i); + *pr++ = gf2m_SQR1(a_i); + } + + MP_CHECKOK( mp_bmod(r, p, r) ); + s_mp_clamp(r); + SIGN(r) = ZPOS; + +CLEANUP: + mp_clear(&tmp); + return res; +} + +/* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p. + * Store the result in r. r could be x or y, and x could equal y. + * Uses algorithm Modular_Division_GF(2^m) from + * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to + * the Great Divide". + */ +int +mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp, + const unsigned int p[], mp_int *r) +{ + mp_int aa, bb, uu; + mp_int *a, *b, *u, *v; + mp_err res = MP_OKAY; + + MP_CHECKOK( mp_init_copy(&aa, x) ); + MP_CHECKOK( mp_init_copy(&uu, y) ); + MP_CHECKOK( mp_init_copy(&bb, pp) ); + MP_CHECKOK( s_mp_pad(r, USED(pp)) ); + MP_USED(r) = 1; MP_DIGIT(r, 0) = 0; + + a = &aa; b= &bb; u=&uu; v=r; + /* reduce x and y mod p */ + MP_CHECKOK( mp_bmod(a, p, a) ); + MP_CHECKOK( mp_bmod(u, p, u) ); + + while (!mp_isodd(a)) { + s_mp_div2(a); + if (mp_isodd(u)) { + MP_CHECKOK( mp_badd(u, pp, u) ); + } + s_mp_div_2(u); + } + + do { + if (mp_cmp_mag(b, a) > 0) { + MP_CHECKOK( mp_badd(b, a, b) ); + MP_CHECKOK( mp_badd(v, u, v) ); + do { + s_mp_div2(b); + if (mp_isodd(v)) { + MP_CHECKOK( mp_badd(v, pp, v) ); + } + s_mp_div2(v); + } while (!mp_isodd(b)); + } + else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1)) + break; + else { + MP_CHECKOK( mp_badd(a, b, a) ); + MP_CHECKOK( mp_badd(u, v, u) ); + do { + s_mp_div2(a); + if (mp_isodd(u)) { + MP_CHECKOK( mp_badd(u, pp, u) ); + } + s_mp_div2(u); + } while (!mp_isodd(a)); + } + } while (1); + + MP_CHECKOK( mp_copy(u, r) ); + +CLEANUP: + return res; + +} + +/* Convert the bit-string representation of a polynomial a into an array + * of integers corresponding to the bits with non-zero coefficient. + * Up to max elements of the array will be filled. Return value is total + * number of coefficients that would be extracted if array was large enough. + */ +int +mp_bpoly2arr(const mp_int *a, unsigned int p[], int max) +{ + int i, j, k; + mp_digit top_bit, mask; + + top_bit = 1; + top_bit <<= MP_DIGIT_BIT - 1; + + for (k = 0; k < max; k++) p[k] = 0; + k = 0; + + for (i = MP_USED(a) - 1; i >= 0; i--) { + mask = top_bit; + for (j = MP_DIGIT_BIT - 1; j >= 0; j--) { + if (MP_DIGITS(a)[i] & mask) { + if (k < max) p[k] = MP_DIGIT_BIT * i + j; + k++; + } + mask >>= 1; + } + } + + return k; +} + +/* Convert the coefficient array representation of a polynomial to a + * bit-string. The array must be terminated by 0. + */ +mp_err +mp_barr2poly(const unsigned int p[], mp_int *a) +{ + + mp_err res = MP_OKAY; + int i; + + mp_zero(a); + for (i = 0; p[i] > 0; i++) { + MP_CHECKOK( mpl_set_bit(a, p[i], 1) ); + } + MP_CHECKOK( mpl_set_bit(a, 0, 1) ); + +CLEANUP: + return MP_OKAY; +} diff --git a/security/nss/lib/freebl/mpi/mp_gf2m.h b/security/nss/lib/freebl/mpi/mp_gf2m.h new file mode 100644 index 000000000..c4268f142 --- /dev/null +++ b/security/nss/lib/freebl/mpi/mp_gf2m.h @@ -0,0 +1,62 @@ +/* + * 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 Multi-precision Binary Polynomial Arithmetic + * Library. + * + * The Initial Developer of the Original Code is Sun Microsystems, Inc. + * Portions created by Sun Microsystems, Inc. are Copyright (C) 2003 + * Sun Microsystems, Inc. All Rights Reserved. + * + * Contributor(s): + * Sheueling Chang Shantz <sheueling.chang@sun.com> and + * Douglas Stebila <douglas@stebila.ca> of Sun Laboratories. + * + * 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. + * + */ + +#ifndef _MP_GF2M_H_ +#define _MP_GF2M_H_ + +#include "mpi.h" + +mp_err mp_badd(const mp_int *a, const mp_int *b, mp_int *c); +mp_err mp_bmul(const mp_int *a, const mp_int *b, mp_int *c); + +/* For modular arithmetic, the irreducible polynomial f(t) is represented + * as an array of int[], where f(t) is of the form: + * f(t) = t^p[0] + t^p[1] + ... + t^p[k] + * where m = p[0] > p[1] > ... > p[k] = 0. + */ +mp_err mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r); +mp_err mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], + mp_int *r); +mp_err mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r); +mp_err mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp, + const unsigned int p[], mp_int *r); + +int mp_bpoly2arr(const mp_int *a, unsigned int p[], int max); +mp_err mp_barr2poly(const unsigned int p[], mp_int *a); + +#endif /* _MP_GF2M_H_ */ diff --git a/security/nss/lib/freebl/mpi/tests/mptest-b.c b/security/nss/lib/freebl/mpi/tests/mptest-b.c new file mode 100644 index 000000000..da89cb3e0 --- /dev/null +++ b/security/nss/lib/freebl/mpi/tests/mptest-b.c @@ -0,0 +1,211 @@ +/* + * Simple test driver for MPI library + * + * Test GF2m: Binary Polynomial Arithmetic + * + * 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 Multi-precision Binary Polynomial Arithmetic + * Library. + * + * Contributor(s): + * Sheueling Chang Shantz <sheueling.chang@sun.com> and + * Douglas Stebila <douglas@stebila.ca> of Sun Laboratories. + * + * Alternatively, the contents of this file may be used under the + * terms of the GNU General Public License Version 2 or later (the + * "GPL"), in which case the provisions of the GPL are applicable + * instead of those above. If you wish to allow use of your + * version of this file only under the terms of the GPL and not to + * allow others to use your version of this file under the MPL, + * indicate your decision by deleting the provisions above and + * replace them with the notice and other provisions required by + * the GPL. If you do not delete the provisions above, a recipient + * may use your version of this file under either the MPL or the GPL. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <ctype.h> +#include <limits.h> + +#include "mp_gf2m.h" + +int main(int argc, char *argv[]) +{ + int ix; + mp_int pp, a, b, x, y, order; + mp_int c, d, e; + mp_digit r; + mp_err res; + unsigned int p[] = {163,7,6,3,0}; + unsigned int ptemp[10]; + + printf("Test b: Binary Polynomial Arithmetic\n\n"); + + mp_init(&pp); + mp_init(&a); + mp_init(&b); + mp_init(&x); + mp_init(&y); + mp_init(&order); + + mp_read_radix(&pp, "0800000000000000000000000000000000000000C9", 16); + mp_read_radix(&a, "1", 16); + mp_read_radix(&b, "020A601907B8C953CA1481EB10512F78744A3205FD", 16); + mp_read_radix(&x, "03F0EBA16286A2D57EA0991168D4994637E8343E36", 16); + mp_read_radix(&y, "00D51FBC6C71A0094FA2CDD545B11C5C0C797324F1", 16); + mp_read_radix(&order, "040000000000000000000292FE77E70C12A4234C33", 16); + printf("pp = "); mp_print(&pp, stdout); fputc('\n', stdout); + printf("a = "); mp_print(&a, stdout); fputc('\n', stdout); + printf("b = "); mp_print(&b, stdout); fputc('\n', stdout); + printf("x = "); mp_print(&x, stdout); fputc('\n', stdout); + printf("y = "); mp_print(&y, stdout); fputc('\n', stdout); + printf("order = "); mp_print(&order, stdout); fputc('\n', stdout); + + mp_init(&c); + mp_init(&d); + mp_init(&e); + + /* Test polynomial conversion */ + ix = mp_bpoly2arr(&pp, ptemp, 10); + if ( + (ix != 5) || + (ptemp[0] != p[0]) || + (ptemp[1] != p[1]) || + (ptemp[2] != p[2]) || + (ptemp[3] != p[3]) || + (ptemp[4] != p[4]) + ) { + printf("Polynomial to array conversion not correct\n"); + return -1; + } + + printf("Polynomial conversion test #1 successful.\n"); + MP_CHECKOK( mp_barr2poly(p, &c) ); + if (mp_cmp(&pp, &c) != 0) { + printf("Array to polynomial conversion not correct\n"); + return -1; + } + printf("Polynomial conversion test #2 successful.\n"); + + /* Test addition */ + MP_CHECKOK( mp_badd(&a, &a, &c) ); + if (mp_cmp_z(&c) != 0) { + printf("a+a should equal zero\n"); + return -1; + } + printf("Addition test #1 successful.\n"); + MP_CHECKOK( mp_badd(&a, &b, &c) ); + MP_CHECKOK( mp_badd(&b, &c, &c) ); + if (mp_cmp(&c, &a) != 0) { + printf("c = (a + b) + b should equal a\n"); + printf("a = "); mp_print(&a, stdout); fputc('\n', stdout); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Addition test #2 successful.\n"); + + /* Test multiplication */ + mp_set(&c, 2); + MP_CHECKOK( mp_bmul(&b, &c, &c) ); + MP_CHECKOK( mp_badd(&b, &c, &c) ); + mp_set(&d, 3); + MP_CHECKOK( mp_bmul(&b, &d, &d) ); + if (mp_cmp(&c, &d) != 0) { + printf("c = (2 * b) + b should equal c = 3 * b\n"); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + printf("d = "); mp_print(&d, stdout); fputc('\n', stdout); + return -1; + } + printf("Multiplication test #1 successful.\n"); + + /* Test modular reduction */ + MP_CHECKOK( mp_bmod(&b, p, &c) ); + if (mp_cmp(&b, &c) != 0) { + printf("c = b mod p should equal b\n"); + printf("b = "); mp_print(&b, stdout); fputc('\n', stdout); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular reduction test #1 successful.\n"); + MP_CHECKOK( mp_badd(&b, &pp, &c) ); + MP_CHECKOK( mp_bmod(&c, p, &c) ); + if (mp_cmp(&b, &c) != 0) { + printf("c = (b + p) mod p should equal b\n"); + printf("b = "); mp_print(&b, stdout); fputc('\n', stdout); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular reduction test #2 successful.\n"); + MP_CHECKOK( mp_bmul(&b, &pp, &c) ); + MP_CHECKOK( mp_bmod(&c, p, &c) ); + if (mp_cmp_z(&c) != 0) { + printf("c = (b * p) mod p should equal 0\n"); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular reduction test #3 successful.\n"); + + /* Test modular multiplication */ + MP_CHECKOK( mp_bmulmod(&b, &pp, p, &c) ); + if (mp_cmp_z(&c) != 0) { + printf("c = (b * p) mod p should equal 0\n"); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular multiplication test #1 successful.\n"); + mp_set(&c, 1); + MP_CHECKOK( mp_badd(&pp, &c, &c) ); + MP_CHECKOK( mp_bmulmod(&b, &c, p, &c) ); + if (mp_cmp(&b, &c) != 0) { + printf("c = (b * (p + 1)) mod p should equal b\n"); + printf("b = "); mp_print(&b, stdout); fputc('\n', stdout); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular multiplication test #2 successful.\n"); + + /* Test modular squaring */ + MP_CHECKOK( mp_copy(&b, &c) ); + MP_CHECKOK( mp_bmulmod(&b, &c, p, &c) ); + MP_CHECKOK( mp_bsqrmod(&b, p, &d) ); + if (mp_cmp(&c, &d) != 0) { + printf("c = (b * b) mod p should equal d = b^2 mod p\n"); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + printf("d = "); mp_print(&d, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular squaring test #1 successful.\n"); + + /* Test modular division */ + MP_CHECKOK( mp_bdivmod(&b, &x, &pp, p, &c) ); + MP_CHECKOK( mp_bmulmod(&c, &x, p, &c) ); + if (mp_cmp(&b, &c) != 0) { + printf("c = (b / x) * x mod p should equal b\n"); + printf("b = "); mp_print(&b, stdout); fputc('\n', stdout); + printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); + return -1; + } + printf("Modular division test #1 successful.\n"); + +CLEANUP: + + mp_clear(&order); + mp_clear(&y); + mp_clear(&x); + mp_clear(&b); + mp_clear(&a); + mp_clear(&pp); + + return 0; +} |