The Tor Browser / file comparison
comparison: security/nss/lib/freebl/ecl/ec2_proj.c
security/nss/lib/freebl/ecl/ec2_proj.c
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:bef586c39cb9 |
|---|---|
| 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 |
