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