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

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;
+}