The Tor Browser / file revision

security/nss/lib/freebl/ecl/ec2_aff.c@b8a032363ba2

security/nss/lib/freebl/ecl/ec2_aff.c

Thu, 22 Jan 2015 13:21:57 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Thu, 22 Jan 2015 13:21:57 +0100
branch
TOR_BUG_9701
changeset 15
b8a032363ba2
permissions
-rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     1 /* This Source Code Form is subject to the terms of the Mozilla Public

     2  * License, v. 2.0. If a copy of the MPL was not distributed with this

     3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     4 

     5 #include "ec2.h"

     6 #include "mplogic.h"

     7 #include "mp_gf2m.h"

     8 #include <stdlib.h>

     9 

    10 /* Checks if point P(px, py) is at infinity.  Uses affine coordinates. */

    11 mp_err

    12 ec_GF2m_pt_is_inf_aff(const mp_int *px, const mp_int *py)

    13 {

    14 

    15 	if ((mp_cmp_z(px) == 0) && (mp_cmp_z(py) == 0)) {

    16 		return MP_YES;

    17 	} else {

    18 		return MP_NO;

    19 	}

    20 

    21 }

    22 

    23 /* Sets P(px, py) to be the point at infinity.  Uses affine coordinates. */

    24 mp_err

    25 ec_GF2m_pt_set_inf_aff(mp_int *px, mp_int *py)

    26 {

    27 	mp_zero(px);

    28 	mp_zero(py);

    29 	return MP_OKAY;

    30 }

    31 

    32 /* Computes R = P + Q based on IEEE P1363 A.10.2. Elliptic curve points P, 

    33  * Q, and R can all be identical. Uses affine coordinates. */

    34 mp_err

    35 ec_GF2m_pt_add_aff(const mp_int *px, const mp_int *py, const mp_int *qx,

    36 				   const mp_int *qy, mp_int *rx, mp_int *ry,

    37 				   const ECGroup *group)

    38 {

    39 	mp_err res = MP_OKAY;

    40 	mp_int lambda, tempx, tempy;

    41 

    42 	MP_DIGITS(&lambda) = 0;

    43 	MP_DIGITS(&tempx) = 0;

    44 	MP_DIGITS(&tempy) = 0;

    45 	MP_CHECKOK(mp_init(&lambda));

    46 	MP_CHECKOK(mp_init(&tempx));

    47 	MP_CHECKOK(mp_init(&tempy));

    48 	/* if P = inf, then R = Q */

    49 	if (ec_GF2m_pt_is_inf_aff(px, py) == 0) {

    50 		MP_CHECKOK(mp_copy(qx, rx));

    51 		MP_CHECKOK(mp_copy(qy, ry));

    52 		res = MP_OKAY;

    53 		goto CLEANUP;

    54 	}

    55 	/* if Q = inf, then R = P */

    56 	if (ec_GF2m_pt_is_inf_aff(qx, qy) == 0) {

    57 		MP_CHECKOK(mp_copy(px, rx));

    58 		MP_CHECKOK(mp_copy(py, ry));

    59 		res = MP_OKAY;

    60 		goto CLEANUP;

    61 	}

    62 	/* if px != qx, then lambda = (py+qy) / (px+qx), tempx = a + lambda^2

    63 	 * + lambda + px + qx */

    64 	if (mp_cmp(px, qx) != 0) {

    65 		MP_CHECKOK(group->meth->field_add(py, qy, &tempy, group->meth));

    66 		MP_CHECKOK(group->meth->field_add(px, qx, &tempx, group->meth));

    67 		MP_CHECKOK(group->meth->

    68 				   field_div(&tempy, &tempx, &lambda, group->meth));

    69 		MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth));

    70 		MP_CHECKOK(group->meth->

    71 				   field_add(&tempx, &lambda, &tempx, group->meth));

    72 		MP_CHECKOK(group->meth->

    73 				   field_add(&tempx, &group->curvea, &tempx, group->meth));

    74 		MP_CHECKOK(group->meth->

    75 				   field_add(&tempx, px, &tempx, group->meth));

    76 		MP_CHECKOK(group->meth->

    77 				   field_add(&tempx, qx, &tempx, group->meth));

    78 	} else {

    79 		/* if py != qy or qx = 0, then R = inf */

    80 		if (((mp_cmp(py, qy) != 0)) || (mp_cmp_z(qx) == 0)) {

    81 			mp_zero(rx);

    82 			mp_zero(ry);

    83 			res = MP_OKAY;

    84 			goto CLEANUP;

    85 		}

    86 		/* lambda = qx + qy / qx */

    87 		MP_CHECKOK(group->meth->field_div(qy, qx, &lambda, group->meth));

    88 		MP_CHECKOK(group->meth->

    89 				   field_add(&lambda, qx, &lambda, group->meth));

    90 		/* tempx = a + lambda^2 + lambda */

    91 		MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth));

    92 		MP_CHECKOK(group->meth->

    93 				   field_add(&tempx, &lambda, &tempx, group->meth));

    94 		MP_CHECKOK(group->meth->

    95 				   field_add(&tempx, &group->curvea, &tempx, group->meth));

    96 	}

    97 	/* ry = (qx + tempx) * lambda + tempx + qy */

    98 	MP_CHECKOK(group->meth->field_add(qx, &tempx, &tempy, group->meth));

    99 	MP_CHECKOK(group->meth->

   100 			   field_mul(&tempy, &lambda, &tempy, group->meth));

   101 	MP_CHECKOK(group->meth->

   102 			   field_add(&tempy, &tempx, &tempy, group->meth));

   103 	MP_CHECKOK(group->meth->field_add(&tempy, qy, ry, group->meth));

   104 	/* rx = tempx */

   105 	MP_CHECKOK(mp_copy(&tempx, rx));

   106 

   107   CLEANUP:

   108 	mp_clear(&lambda);

   109 	mp_clear(&tempx);

   110 	mp_clear(&tempy);

   111 	return res;

   112 }

   113 

   114 /* Computes R = P - Q. Elliptic curve points P, Q, and R can all be

   115  * identical. Uses affine coordinates. */

   116 mp_err

   117 ec_GF2m_pt_sub_aff(const mp_int *px, const mp_int *py, const mp_int *qx,

   118 				   const mp_int *qy, mp_int *rx, mp_int *ry,

   119 				   const ECGroup *group)

   120 {

   121 	mp_err res = MP_OKAY;

   122 	mp_int nqy;

   123 

   124 	MP_DIGITS(&nqy) = 0;

   125 	MP_CHECKOK(mp_init(&nqy));

   126 	/* nqy = qx+qy */

   127 	MP_CHECKOK(group->meth->field_add(qx, qy, &nqy, group->meth));

   128 	MP_CHECKOK(group->point_add(px, py, qx, &nqy, rx, ry, group));

   129   CLEANUP:

   130 	mp_clear(&nqy);

   131 	return res;

   132 }

   133 

   134 /* Computes R = 2P. Elliptic curve points P and R can be identical. Uses

   135  * affine coordinates. */

   136 mp_err

   137 ec_GF2m_pt_dbl_aff(const mp_int *px, const mp_int *py, mp_int *rx,

   138 				   mp_int *ry, const ECGroup *group)

   139 {

   140 	return group->point_add(px, py, px, py, rx, ry, group);

   141 }

   142 

   143 /* by default, this routine is unused and thus doesn't need to be compiled */

   144 #ifdef ECL_ENABLE_GF2M_PT_MUL_AFF

   145 /* Computes R = nP based on IEEE P1363 A.10.3. Elliptic curve points P and 

   146  * R can be identical. Uses affine coordinates. */

   147 mp_err

   148 ec_GF2m_pt_mul_aff(const mp_int *n, const mp_int *px, const mp_int *py,

   149 				   mp_int *rx, mp_int *ry, const ECGroup *group)

   150 {

   151 	mp_err res = MP_OKAY;

   152 	mp_int k, k3, qx, qy, sx, sy;

   153 	int b1, b3, i, l;

   154 

   155 	MP_DIGITS(&k) = 0;

   156 	MP_DIGITS(&k3) = 0;

   157 	MP_DIGITS(&qx) = 0;

   158 	MP_DIGITS(&qy) = 0;

   159 	MP_DIGITS(&sx) = 0;

   160 	MP_DIGITS(&sy) = 0;

   161 	MP_CHECKOK(mp_init(&k));

   162 	MP_CHECKOK(mp_init(&k3));

   163 	MP_CHECKOK(mp_init(&qx));

   164 	MP_CHECKOK(mp_init(&qy));

   165 	MP_CHECKOK(mp_init(&sx));

   166 	MP_CHECKOK(mp_init(&sy));

   167 

   168 	/* if n = 0 then r = inf */

   169 	if (mp_cmp_z(n) == 0) {

   170 		mp_zero(rx);

   171 		mp_zero(ry);

   172 		res = MP_OKAY;

   173 		goto CLEANUP;

   174 	}

   175 	/* Q = P, k = n */

   176 	MP_CHECKOK(mp_copy(px, &qx));

   177 	MP_CHECKOK(mp_copy(py, &qy));

   178 	MP_CHECKOK(mp_copy(n, &k));

   179 	/* if n < 0 then Q = -Q, k = -k */

   180 	if (mp_cmp_z(n) < 0) {

   181 		MP_CHECKOK(group->meth->field_add(&qx, &qy, &qy, group->meth));

   182 		MP_CHECKOK(mp_neg(&k, &k));

   183 	}

   184 #ifdef ECL_DEBUG				/* basic double and add method */

   185 	l = mpl_significant_bits(&k) - 1;

   186 	MP_CHECKOK(mp_copy(&qx, &sx));

   187 	MP_CHECKOK(mp_copy(&qy, &sy));

   188 	for (i = l - 1; i >= 0; i--) {

   189 		/* S = 2S */

   190 		MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group));

   191 		/* if k_i = 1, then S = S + Q */

   192 		if (mpl_get_bit(&k, i) != 0) {

   193 			MP_CHECKOK(group->

   194 					   point_add(&sx, &sy, &qx, &qy, &sx, &sy, group));

   195 		}

   196 	}

   197 #else							/* double and add/subtract method from

   198 								 * standard */

   199 	/* k3 = 3 * k */

   200 	MP_CHECKOK(mp_set_int(&k3, 3));

   201 	MP_CHECKOK(mp_mul(&k, &k3, &k3));

   202 	/* S = Q */

   203 	MP_CHECKOK(mp_copy(&qx, &sx));

   204 	MP_CHECKOK(mp_copy(&qy, &sy));

   205 	/* l = index of high order bit in binary representation of 3*k */

   206 	l = mpl_significant_bits(&k3) - 1;

   207 	/* for i = l-1 downto 1 */

   208 	for (i = l - 1; i >= 1; i--) {

   209 		/* S = 2S */

   210 		MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group));

   211 		b3 = MP_GET_BIT(&k3, i);

   212 		b1 = MP_GET_BIT(&k, i);

   213 		/* if k3_i = 1 and k_i = 0, then S = S + Q */

   214 		if ((b3 == 1) && (b1 == 0)) {

   215 			MP_CHECKOK(group->

   216 					   point_add(&sx, &sy, &qx, &qy, &sx, &sy, group));

   217 			/* if k3_i = 0 and k_i = 1, then S = S - Q */

   218 		} else if ((b3 == 0) && (b1 == 1)) {

   219 			MP_CHECKOK(group->

   220 					   point_sub(&sx, &sy, &qx, &qy, &sx, &sy, group));

   221 		}

   222 	}

   223 #endif

   224 	/* output S */

   225 	MP_CHECKOK(mp_copy(&sx, rx));

   226 	MP_CHECKOK(mp_copy(&sy, ry));

   227 

   228   CLEANUP:

   229 	mp_clear(&k);

   230 	mp_clear(&k3);

   231 	mp_clear(&qx);

   232 	mp_clear(&qy);

   233 	mp_clear(&sx);

   234 	mp_clear(&sy);

   235 	return res;

   236 }

   237 #endif

   238 

   239 /* Validates a point on a GF2m curve. */

   240 mp_err 

   241 ec_GF2m_validate_point(const mp_int *px, const mp_int *py, const ECGroup *group)

   242 {

   243 	mp_err res = MP_NO;

   244 	mp_int accl, accr, tmp, pxt, pyt;

   245 

   246 	MP_DIGITS(&accl) = 0;

   247 	MP_DIGITS(&accr) = 0;

   248 	MP_DIGITS(&tmp) = 0;

   249 	MP_DIGITS(&pxt) = 0;

   250 	MP_DIGITS(&pyt) = 0;

   251 	MP_CHECKOK(mp_init(&accl));

   252 	MP_CHECKOK(mp_init(&accr));

   253 	MP_CHECKOK(mp_init(&tmp));

   254 	MP_CHECKOK(mp_init(&pxt));

   255 	MP_CHECKOK(mp_init(&pyt));

   256 

   257     /* 1: Verify that publicValue is not the point at infinity */

   258 	if (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES) {

   259 		res = MP_NO;

   260 		goto CLEANUP;

   261 	}

   262     /* 2: Verify that the coordinates of publicValue are elements 

   263      *    of the field.

   264      */

   265 	if ((MP_SIGN(px) == MP_NEG) || (mp_cmp(px, &group->meth->irr) >= 0) || 

   266 		(MP_SIGN(py) == MP_NEG) || (mp_cmp(py, &group->meth->irr) >= 0)) {

   267 		res = MP_NO;

   268 		goto CLEANUP;

   269 	}

   270     /* 3: Verify that publicValue is on the curve. */

   271 	if (group->meth->field_enc) {

   272 		group->meth->field_enc(px, &pxt, group->meth);

   273 		group->meth->field_enc(py, &pyt, group->meth);

   274 	} else {

   275 		mp_copy(px, &pxt);

   276 		mp_copy(py, &pyt);

   277 	}

   278 	/* left-hand side: y^2 + x*y  */

   279 	MP_CHECKOK( group->meth->field_sqr(&pyt, &accl, group->meth) );

   280 	MP_CHECKOK( group->meth->field_mul(&pxt, &pyt, &tmp, group->meth) );

   281 	MP_CHECKOK( group->meth->field_add(&accl, &tmp, &accl, group->meth) );

   282 	/* right-hand side: x^3 + a*x^2 + b */

   283 	MP_CHECKOK( group->meth->field_sqr(&pxt, &tmp, group->meth) );

   284 	MP_CHECKOK( group->meth->field_mul(&pxt, &tmp, &accr, group->meth) );

   285 	MP_CHECKOK( group->meth->field_mul(&group->curvea, &tmp, &tmp, group->meth) );

   286 	MP_CHECKOK( group->meth->field_add(&tmp, &accr, &accr, group->meth) );

   287 	MP_CHECKOK( group->meth->field_add(&accr, &group->curveb, &accr, group->meth) );

   288 	/* check LHS - RHS == 0 */

   289 	MP_CHECKOK( group->meth->field_add(&accl, &accr, &accr, group->meth) );

   290 	if (mp_cmp_z(&accr) != 0) {

   291 		res = MP_NO;

   292 		goto CLEANUP;

   293 	}

   294     /* 4: Verify that the order of the curve times the publicValue

   295      *    is the point at infinity.

   296      */

   297 	MP_CHECKOK( ECPoint_mul(group, &group->order, px, py, &pxt, &pyt) );

   298 	if (ec_GF2m_pt_is_inf_aff(&pxt, &pyt) != MP_YES) {

   299 		res = MP_NO;

   300 		goto CLEANUP;

   301 	}

   302 

   303 	res = MP_YES;

   304 

   305 CLEANUP:

   306 	mp_clear(&accl);

   307 	mp_clear(&accr);

   308 	mp_clear(&tmp);

   309 	mp_clear(&pxt);

   310 	mp_clear(&pyt);

   311 	return res;

   312 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial