The Tor Browser / file revision

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

security/nss/lib/freebl/ecl/ec2_mont.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 /* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery

    11  * projective coordinates. Uses algorithm Mdouble in appendix of Lopez, J. 

    12  * and Dahab, R.  "Fast multiplication on elliptic curves over GF(2^m)

    13  * without precomputation". modified to not require precomputation of

    14  * c=b^{2^{m-1}}. */

    15 static mp_err

    16 gf2m_Mdouble(mp_int *x, mp_int *z, const ECGroup *group)

    17 {

    18 	mp_err res = MP_OKAY;

    19 	mp_int t1;

    20 

    21 	MP_DIGITS(&t1) = 0;

    22 	MP_CHECKOK(mp_init(&t1));

    23 

    24 	MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));

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

    26 	MP_CHECKOK(group->meth->field_mul(x, &t1, z, group->meth));

    27 	MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));

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

    29 	MP_CHECKOK(group->meth->

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

    31 	MP_CHECKOK(group->meth->field_add(x, &t1, x, group->meth));

    32 

    33   CLEANUP:

    34 	mp_clear(&t1);

    35 	return res;

    36 }

    37 

    38 /* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in

    39  * Montgomery projective coordinates. Uses algorithm Madd in appendix of

    40  * Lopex, J. and Dahab, R.  "Fast multiplication on elliptic curves over

    41  * GF(2^m) without precomputation". */

    42 static mp_err

    43 gf2m_Madd(const mp_int *x, mp_int *x1, mp_int *z1, mp_int *x2, mp_int *z2,

    44 		  const ECGroup *group)

    45 {

    46 	mp_err res = MP_OKAY;

    47 	mp_int t1, t2;

    48 

    49 	MP_DIGITS(&t1) = 0;

    50 	MP_DIGITS(&t2) = 0;

    51 	MP_CHECKOK(mp_init(&t1));

    52 	MP_CHECKOK(mp_init(&t2));

    53 

    54 	MP_CHECKOK(mp_copy(x, &t1));

    55 	MP_CHECKOK(group->meth->field_mul(x1, z2, x1, group->meth));

    56 	MP_CHECKOK(group->meth->field_mul(z1, x2, z1, group->meth));

    57 	MP_CHECKOK(group->meth->field_mul(x1, z1, &t2, group->meth));

    58 	MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));

    59 	MP_CHECKOK(group->meth->field_sqr(z1, z1, group->meth));

    60 	MP_CHECKOK(group->meth->field_mul(z1, &t1, x1, group->meth));

    61 	MP_CHECKOK(group->meth->field_add(x1, &t2, x1, group->meth));

    62 

    63   CLEANUP:

    64 	mp_clear(&t1);

    65 	mp_clear(&t2);

    66 	return res;

    67 }

    68 

    69 /* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)

    70  * using Montgomery point multiplication algorithm Mxy() in appendix of

    71  * Lopex, J. and Dahab, R.  "Fast multiplication on elliptic curves over

    72  * GF(2^m) without precomputation". Returns: 0 on error 1 if return value

    73  * should be the point at infinity 2 otherwise */

    74 static int

    75 gf2m_Mxy(const mp_int *x, const mp_int *y, mp_int *x1, mp_int *z1,

    76 		 mp_int *x2, mp_int *z2, const ECGroup *group)

    77 {

    78 	mp_err res = MP_OKAY;

    79 	int ret = 0;

    80 	mp_int t3, t4, t5;

    81 

    82 	MP_DIGITS(&t3) = 0;

    83 	MP_DIGITS(&t4) = 0;

    84 	MP_DIGITS(&t5) = 0;

    85 	MP_CHECKOK(mp_init(&t3));

    86 	MP_CHECKOK(mp_init(&t4));

    87 	MP_CHECKOK(mp_init(&t5));

    88 

    89 	if (mp_cmp_z(z1) == 0) {

    90 		mp_zero(x2);

    91 		mp_zero(z2);

    92 		ret = 1;

    93 		goto CLEANUP;

    94 	}

    95 

    96 	if (mp_cmp_z(z2) == 0) {

    97 		MP_CHECKOK(mp_copy(x, x2));

    98 		MP_CHECKOK(group->meth->field_add(x, y, z2, group->meth));

    99 		ret = 2;

   100 		goto CLEANUP;

   101 	}

   102 

   103 	MP_CHECKOK(mp_set_int(&t5, 1));

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

   105 		MP_CHECKOK(group->meth->field_enc(&t5, &t5, group->meth));

   106 	}

   107 

   108 	MP_CHECKOK(group->meth->field_mul(z1, z2, &t3, group->meth));

   109 

   110 	MP_CHECKOK(group->meth->field_mul(z1, x, z1, group->meth));

   111 	MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));

   112 	MP_CHECKOK(group->meth->field_mul(z2, x, z2, group->meth));

   113 	MP_CHECKOK(group->meth->field_mul(z2, x1, x1, group->meth));

   114 	MP_CHECKOK(group->meth->field_add(z2, x2, z2, group->meth));

   115 

   116 	MP_CHECKOK(group->meth->field_mul(z2, z1, z2, group->meth));

   117 	MP_CHECKOK(group->meth->field_sqr(x, &t4, group->meth));

   118 	MP_CHECKOK(group->meth->field_add(&t4, y, &t4, group->meth));

   119 	MP_CHECKOK(group->meth->field_mul(&t4, &t3, &t4, group->meth));

   120 	MP_CHECKOK(group->meth->field_add(&t4, z2, &t4, group->meth));

   121 

   122 	MP_CHECKOK(group->meth->field_mul(&t3, x, &t3, group->meth));

   123 	MP_CHECKOK(group->meth->field_div(&t5, &t3, &t3, group->meth));

   124 	MP_CHECKOK(group->meth->field_mul(&t3, &t4, &t4, group->meth));

   125 	MP_CHECKOK(group->meth->field_mul(x1, &t3, x2, group->meth));

   126 	MP_CHECKOK(group->meth->field_add(x2, x, z2, group->meth));

   127 

   128 	MP_CHECKOK(group->meth->field_mul(z2, &t4, z2, group->meth));

   129 	MP_CHECKOK(group->meth->field_add(z2, y, z2, group->meth));

   130 

   131 	ret = 2;

   132 

   133   CLEANUP:

   134 	mp_clear(&t3);

   135 	mp_clear(&t4);

   136 	mp_clear(&t5);

   137 	if (res == MP_OKAY) {

   138 		return ret;

   139 	} else {

   140 		return 0;

   141 	}

   142 }

   143 

   144 /* Computes R = nP based on algorithm 2P of Lopex, J. and Dahab, R.  "Fast 

   145  * multiplication on elliptic curves over GF(2^m) without

   146  * precomputation". Elliptic curve points P and R can be identical. Uses

   147  * Montgomery projective coordinates. */

   148 mp_err

   149 ec_GF2m_pt_mul_mont(const mp_int *n, const mp_int *px, const mp_int *py,

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

   151 {

   152 	mp_err res = MP_OKAY;

   153 	mp_int x1, x2, z1, z2;

   154 	int i, j;

   155 	mp_digit top_bit, mask;

   156 

   157 	MP_DIGITS(&x1) = 0;

   158 	MP_DIGITS(&x2) = 0;

   159 	MP_DIGITS(&z1) = 0;

   160 	MP_DIGITS(&z2) = 0;

   161 	MP_CHECKOK(mp_init(&x1));

   162 	MP_CHECKOK(mp_init(&x2));

   163 	MP_CHECKOK(mp_init(&z1));

   164 	MP_CHECKOK(mp_init(&z2));

   165 

   166 	/* if result should be point at infinity */

   167 	if ((mp_cmp_z(n) == 0) || (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES)) {

   168 		MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));

   169 		goto CLEANUP;

   170 	}

   171 

   172 	MP_CHECKOK(mp_copy(px, &x1));	/* x1 = px */

   173 	MP_CHECKOK(mp_set_int(&z1, 1));	/* z1 = 1 */

   174 	MP_CHECKOK(group->meth->field_sqr(&x1, &z2, group->meth));	/* z2 =

   175 																 * x1^2 =

   176 																 * px^2 */

   177 	MP_CHECKOK(group->meth->field_sqr(&z2, &x2, group->meth));

   178 	MP_CHECKOK(group->meth->field_add(&x2, &group->curveb, &x2, group->meth));	/* x2 

   179 																				 * = 

   180 																				 * px^4 

   181 																				 * + 

   182 																				 * b 

   183 																				 */

   184 

   185 	/* find top-most bit and go one past it */

   186 	i = MP_USED(n) - 1;

   187 	j = MP_DIGIT_BIT - 1;

   188 	top_bit = 1;

   189 	top_bit <<= MP_DIGIT_BIT - 1;

   190 	mask = top_bit;

   191 	while (!(MP_DIGITS(n)[i] & mask)) {

   192 		mask >>= 1;

   193 		j--;

   194 	}

   195 	mask >>= 1;

   196 	j--;

   197 

   198 	/* if top most bit was at word break, go to next word */

   199 	if (!mask) {

   200 		i--;

   201 		j = MP_DIGIT_BIT - 1;

   202 		mask = top_bit;

   203 	}

   204 

   205 	for (; i >= 0; i--) {

   206 		for (; j >= 0; j--) {

   207 			if (MP_DIGITS(n)[i] & mask) {

   208 				MP_CHECKOK(gf2m_Madd(px, &x1, &z1, &x2, &z2, group));

   209 				MP_CHECKOK(gf2m_Mdouble(&x2, &z2, group));

   210 			} else {

   211 				MP_CHECKOK(gf2m_Madd(px, &x2, &z2, &x1, &z1, group));

   212 				MP_CHECKOK(gf2m_Mdouble(&x1, &z1, group));

   213 			}

   214 			mask >>= 1;

   215 		}

   216 		j = MP_DIGIT_BIT - 1;

   217 		mask = top_bit;

   218 	}

   219 

   220 	/* convert out of "projective" coordinates */

   221 	i = gf2m_Mxy(px, py, &x1, &z1, &x2, &z2, group);

   222 	if (i == 0) {

   223 		res = MP_BADARG;

   224 		goto CLEANUP;

   225 	} else if (i == 1) {

   226 		MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));

   227 	} else {

   228 		MP_CHECKOK(mp_copy(&x2, rx));

   229 		MP_CHECKOK(mp_copy(&z2, ry));

   230 	}

   231 

   232   CLEANUP:

   233 	mp_clear(&x1);

   234 	mp_clear(&x2);

   235 	mp_clear(&z1);

   236 	mp_clear(&z2);

   237 	return res;

   238 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial