The Tor Browser / file revision

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

security/nss/lib/freebl/ecl/ec2_proj.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 #ifdef ECL_DEBUG

    10 #include <assert.h>

    11 #endif

    12 

    13 /* by default, these routines are unused and thus don't need to be compiled */

    14 #ifdef ECL_ENABLE_GF2M_PROJ

    15 /* Converts a point P(px, py) from affine coordinates to projective

    16  * coordinates R(rx, ry, rz). Assumes input is already field-encoded using 

    17  * field_enc, and returns output that is still field-encoded. */

    18 mp_err

    19 ec_GF2m_pt_aff2proj(const mp_int *px, const mp_int *py, mp_int *rx,

    20 					mp_int *ry, mp_int *rz, const ECGroup *group)

    21 {

    22 	mp_err res = MP_OKAY;

    23 

    24 	MP_CHECKOK(mp_copy(px, rx));

    25 	MP_CHECKOK(mp_copy(py, ry));

    26 	MP_CHECKOK(mp_set_int(rz, 1));

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

    28 		MP_CHECKOK(group->meth->field_enc(rz, rz, group->meth));

    29 	}

    30   CLEANUP:

    31 	return res;

    32 }

    33 

    34 /* Converts a point P(px, py, pz) from projective coordinates to affine

    35  * coordinates R(rx, ry).  P and R can share x and y coordinates. Assumes

    36  * input is already field-encoded using field_enc, and returns output that

    37  * is still field-encoded. */

    38 mp_err

    39 ec_GF2m_pt_proj2aff(const mp_int *px, const mp_int *py, const mp_int *pz,

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

    41 {

    42 	mp_err res = MP_OKAY;

    43 	mp_int z1, z2;

    44 

    45 	MP_DIGITS(&z1) = 0;

    46 	MP_DIGITS(&z2) = 0;

    47 	MP_CHECKOK(mp_init(&z1));

    48 	MP_CHECKOK(mp_init(&z2));

    49 

    50 	/* if point at infinity, then set point at infinity and exit */

    51 	if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {

    52 		MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));

    53 		goto CLEANUP;

    54 	}

    55 

    56 	/* transform (px, py, pz) into (px / pz, py / pz^2) */

    57 	if (mp_cmp_d(pz, 1) == 0) {

    58 		MP_CHECKOK(mp_copy(px, rx));

    59 		MP_CHECKOK(mp_copy(py, ry));

    60 	} else {

    61 		MP_CHECKOK(group->meth->field_div(NULL, pz, &z1, group->meth));

    62 		MP_CHECKOK(group->meth->field_sqr(&z1, &z2, group->meth));

    63 		MP_CHECKOK(group->meth->field_mul(px, &z1, rx, group->meth));

    64 		MP_CHECKOK(group->meth->field_mul(py, &z2, ry, group->meth));

    65 	}

    66 

    67   CLEANUP:

    68 	mp_clear(&z1);

    69 	mp_clear(&z2);

    70 	return res;

    71 }

    72 

    73 /* Checks if point P(px, py, pz) is at infinity. Uses projective

    74  * coordinates. */

    75 mp_err

    76 ec_GF2m_pt_is_inf_proj(const mp_int *px, const mp_int *py,

    77 					   const mp_int *pz)

    78 {

    79 	return mp_cmp_z(pz);

    80 }

    81 

    82 /* Sets P(px, py, pz) to be the point at infinity.  Uses projective

    83  * coordinates. */

    84 mp_err

    85 ec_GF2m_pt_set_inf_proj(mp_int *px, mp_int *py, mp_int *pz)

    86 {

    87 	mp_zero(pz);

    88 	return MP_OKAY;

    89 }

    90 

    91 /* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is

    92  * (qx, qy, 1).  Elliptic curve points P, Q, and R can all be identical.

    93  * Uses mixed projective-affine coordinates. Assumes input is already

    94  * field-encoded using field_enc, and returns output that is still

    95  * field-encoded. Uses equation (3) from Hankerson, Hernandez, Menezes.

    96  * Software Implementation of Elliptic Curve Cryptography Over Binary

    97  * Fields. */

    98 mp_err

    99 ec_GF2m_pt_add_proj(const mp_int *px, const mp_int *py, const mp_int *pz,

   100 					const mp_int *qx, const mp_int *qy, mp_int *rx,

   101 					mp_int *ry, mp_int *rz, const ECGroup *group)

   102 {

   103 	mp_err res = MP_OKAY;

   104 	mp_int A, B, C, D, E, F, G;

   105 

   106 	/* If either P or Q is the point at infinity, then return the other

   107 	 * point */

   108 	if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {

   109 		return ec_GF2m_pt_aff2proj(qx, qy, rx, ry, rz, group);

   110 	}

   111 	if (ec_GF2m_pt_is_inf_aff(qx, qy) == MP_YES) {

   112 		MP_CHECKOK(mp_copy(px, rx));

   113 		MP_CHECKOK(mp_copy(py, ry));

   114 		return mp_copy(pz, rz);

   115 	}

   116 

   117 	MP_DIGITS(&A) = 0;

   118 	MP_DIGITS(&B) = 0;

   119 	MP_DIGITS(&C) = 0;

   120 	MP_DIGITS(&D) = 0;

   121 	MP_DIGITS(&E) = 0;

   122 	MP_DIGITS(&F) = 0;

   123 	MP_DIGITS(&G) = 0;

   124 	MP_CHECKOK(mp_init(&A));

   125 	MP_CHECKOK(mp_init(&B));

   126 	MP_CHECKOK(mp_init(&C));

   127 	MP_CHECKOK(mp_init(&D));

   128 	MP_CHECKOK(mp_init(&E));

   129 	MP_CHECKOK(mp_init(&F));

   130 	MP_CHECKOK(mp_init(&G));

   131 

   132 	/* D = pz^2 */

   133 	MP_CHECKOK(group->meth->field_sqr(pz, &D, group->meth));

   134 

   135 	/* A = qy * pz^2 + py */

   136 	MP_CHECKOK(group->meth->field_mul(qy, &D, &A, group->meth));

   137 	MP_CHECKOK(group->meth->field_add(&A, py, &A, group->meth));

   138 

   139 	/* B = qx * pz + px */

   140 	MP_CHECKOK(group->meth->field_mul(qx, pz, &B, group->meth));

   141 	MP_CHECKOK(group->meth->field_add(&B, px, &B, group->meth));

   142 

   143 	/* C = pz * B */

   144 	MP_CHECKOK(group->meth->field_mul(pz, &B, &C, group->meth));

   145 

   146 	/* D = B^2 * (C + a * pz^2) (using E as a temporary variable) */

   147 	MP_CHECKOK(group->meth->

   148 			   field_mul(&group->curvea, &D, &D, group->meth));

   149 	MP_CHECKOK(group->meth->field_add(&C, &D, &D, group->meth));

   150 	MP_CHECKOK(group->meth->field_sqr(&B, &E, group->meth));

   151 	MP_CHECKOK(group->meth->field_mul(&E, &D, &D, group->meth));

   152 

   153 	/* rz = C^2 */

   154 	MP_CHECKOK(group->meth->field_sqr(&C, rz, group->meth));

   155 

   156 	/* E = A * C */

   157 	MP_CHECKOK(group->meth->field_mul(&A, &C, &E, group->meth));

   158 

   159 	/* rx = A^2 + D + E */

   160 	MP_CHECKOK(group->meth->field_sqr(&A, rx, group->meth));

   161 	MP_CHECKOK(group->meth->field_add(rx, &D, rx, group->meth));

   162 	MP_CHECKOK(group->meth->field_add(rx, &E, rx, group->meth));

   163 

   164 	/* F = rx + qx * rz */

   165 	MP_CHECKOK(group->meth->field_mul(qx, rz, &F, group->meth));

   166 	MP_CHECKOK(group->meth->field_add(rx, &F, &F, group->meth));

   167 

   168 	/* G = rx + qy * rz */

   169 	MP_CHECKOK(group->meth->field_mul(qy, rz, &G, group->meth));

   170 	MP_CHECKOK(group->meth->field_add(rx, &G, &G, group->meth));

   171 

   172 	/* ry = E * F + rz * G (using G as a temporary variable) */

   173 	MP_CHECKOK(group->meth->field_mul(rz, &G, &G, group->meth));

   174 	MP_CHECKOK(group->meth->field_mul(&E, &F, ry, group->meth));

   175 	MP_CHECKOK(group->meth->field_add(ry, &G, ry, group->meth));

   176 

   177   CLEANUP:

   178 	mp_clear(&A);

   179 	mp_clear(&B);

   180 	mp_clear(&C);

   181 	mp_clear(&D);

   182 	mp_clear(&E);

   183 	mp_clear(&F);

   184 	mp_clear(&G);

   185 	return res;

   186 }

   187 

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

   189  * projective coordinates.

   190  *

   191  * Assumes input is already field-encoded using field_enc, and returns 

   192  * output that is still field-encoded.

   193  *

   194  * Uses equation (3) from Hankerson, Hernandez, Menezes. Software 

   195  * Implementation of Elliptic Curve Cryptography Over Binary Fields.

   196  */

   197 mp_err

   198 ec_GF2m_pt_dbl_proj(const mp_int *px, const mp_int *py, const mp_int *pz,

   199 					mp_int *rx, mp_int *ry, mp_int *rz,

   200 					const ECGroup *group)

   201 {

   202 	mp_err res = MP_OKAY;

   203 	mp_int t0, t1;

   204 

   205 	if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {

   206 		return ec_GF2m_pt_set_inf_proj(rx, ry, rz);

   207 	}

   208 

   209 	MP_DIGITS(&t0) = 0;

   210 	MP_DIGITS(&t1) = 0;

   211 	MP_CHECKOK(mp_init(&t0));

   212 	MP_CHECKOK(mp_init(&t1));

   213 

   214 	/* t0 = px^2 */

   215 	/* t1 = pz^2 */

   216 	MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth));

   217 	MP_CHECKOK(group->meth->field_sqr(pz, &t1, group->meth));

   218 

   219 	/* rz = px^2 * pz^2 */

   220 	MP_CHECKOK(group->meth->field_mul(&t0, &t1, rz, group->meth));

   221 

   222 	/* t0 = px^4 */

   223 	/* t1 = b * pz^4 */

   224 	MP_CHECKOK(group->meth->field_sqr(&t0, &t0, group->meth));

   225 	MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));

   226 	MP_CHECKOK(group->meth->

   227 			   field_mul(&group->curveb, &t1, &t1, group->meth));

   228 

   229 	/* rx = px^4 + b * pz^4 */

   230 	MP_CHECKOK(group->meth->field_add(&t0, &t1, rx, group->meth));

   231 

   232 	/* ry = b * pz^4 * rz + rx * (a * rz + py^2 + b * pz^4) */

   233 	MP_CHECKOK(group->meth->field_sqr(py, ry, group->meth));

   234 	MP_CHECKOK(group->meth->field_add(ry, &t1, ry, group->meth));

   235 	/* t0 = a * rz */

   236 	MP_CHECKOK(group->meth->

   237 			   field_mul(&group->curvea, rz, &t0, group->meth));

   238 	MP_CHECKOK(group->meth->field_add(&t0, ry, ry, group->meth));

   239 	MP_CHECKOK(group->meth->field_mul(rx, ry, ry, group->meth));

   240 	/* t1 = b * pz^4 * rz */

   241 	MP_CHECKOK(group->meth->field_mul(&t1, rz, &t1, group->meth));

   242 	MP_CHECKOK(group->meth->field_add(&t1, ry, ry, group->meth));

   243 

   244   CLEANUP:

   245 	mp_clear(&t0);

   246 	mp_clear(&t1);

   247 	return res;

   248 }

   249 

   250 /* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters

   251  * a, b and p are the elliptic curve coefficients and the prime that

   252  * determines the field GF2m.  Elliptic curve points P and R can be

   253  * identical.  Uses mixed projective-affine coordinates. Assumes input is

   254  * already field-encoded using field_enc, and returns output that is still

   255  * field-encoded. Uses 4-bit window method. */

   256 mp_err

   257 ec_GF2m_pt_mul_proj(const mp_int *n, const mp_int *px, const mp_int *py,

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

   259 {

   260 	mp_err res = MP_OKAY;

   261 	mp_int precomp[16][2], rz;

   262 	mp_digit precomp_arr[ECL_MAX_FIELD_SIZE_DIGITS * 16 * 2], *t;

   263 	int i, ni, d;

   264 

   265 	ARGCHK(group != NULL, MP_BADARG);

   266 	ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG);

   267 

   268 	/* initialize precomputation table */

   269 	t = precomp_arr;

   270 	for (i = 0; i < 16; i++) {

   271 		/* x co-ord */

   272 		MP_SIGN(&precomp[i][0]) = MP_ZPOS;

   273 		MP_ALLOC(&precomp[i][0]) = ECL_MAX_FIELD_SIZE_DIGITS;

   274 		MP_USED(&precomp[i][0]) = 1;

   275 		*t = 0;

   276 		MP_DIGITS(&precomp[i][0]) = t;

   277 		t += ECL_MAX_FIELD_SIZE_DIGITS;

   278 		/* y co-ord */

   279 		MP_SIGN(&precomp[i][1]) = MP_ZPOS;

   280 		MP_ALLOC(&precomp[i][1]) = ECL_MAX_FIELD_SIZE_DIGITS;

   281 		MP_USED(&precomp[i][1]) = 1;

   282 		*t = 0;

   283 		MP_DIGITS(&precomp[i][1]) = t;

   284 		t += ECL_MAX_FIELD_SIZE_DIGITS;

   285 	}

   286 

   287 	/* fill precomputation table */

   288 	mp_zero(&precomp[0][0]);

   289 	mp_zero(&precomp[0][1]);

   290 	MP_CHECKOK(mp_copy(px, &precomp[1][0]));

   291 	MP_CHECKOK(mp_copy(py, &precomp[1][1]));

   292 	for (i = 2; i < 16; i++) {

   293 		MP_CHECKOK(group->

   294 				   point_add(&precomp[1][0], &precomp[1][1],

   295 							 &precomp[i - 1][0], &precomp[i - 1][1],

   296 							 &precomp[i][0], &precomp[i][1], group));

   297 	}

   298 

   299 	d = (mpl_significant_bits(n) + 3) / 4;

   300 

   301 	/* R = inf */

   302 	MP_DIGITS(&rz) = 0;

   303 	MP_CHECKOK(mp_init(&rz));

   304 	MP_CHECKOK(ec_GF2m_pt_set_inf_proj(rx, ry, &rz));

   305 

   306 	for (i = d - 1; i >= 0; i--) {

   307 		/* compute window ni */

   308 		ni = MP_GET_BIT(n, 4 * i + 3);

   309 		ni <<= 1;

   310 		ni |= MP_GET_BIT(n, 4 * i + 2);

   311 		ni <<= 1;

   312 		ni |= MP_GET_BIT(n, 4 * i + 1);

   313 		ni <<= 1;

   314 		ni |= MP_GET_BIT(n, 4 * i);

   315 		/* R = 2^4 * R */

   316 		MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));

   317 		MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));

   318 		MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));

   319 		MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));

   320 		/* R = R + (ni * P) */

   321 		MP_CHECKOK(ec_GF2m_pt_add_proj

   322 				   (rx, ry, &rz, &precomp[ni][0], &precomp[ni][1], rx, ry,

   323 					&rz, group));

   324 	}

   325 

   326 	/* convert result S to affine coordinates */

   327 	MP_CHECKOK(ec_GF2m_pt_proj2aff(rx, ry, &rz, rx, ry, group));

   328 

   329   CLEANUP:

   330 	mp_clear(&rz);

   331 	return res;

   332 }

   333 #endif

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial