The Tor Browser / file comparison
comparison: security/nss/lib/freebl/ecl/ec2_mont.c
security/nss/lib/freebl/ecl/ec2_mont.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:9944c30d28aa |
|---|---|
| 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 } |
