1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/ec2_aff.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,312 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "ec2.h"
1.9 +#include "mplogic.h"
1.10 +#include "mp_gf2m.h"
1.11 +#include <stdlib.h>
1.12 +
1.13 +/* Checks if point P(px, py) is at infinity. Uses affine coordinates. */
1.14 +mp_err
1.15 +ec_GF2m_pt_is_inf_aff(const mp_int *px, const mp_int *py)
1.16 +{
1.17 +
1.18 + if ((mp_cmp_z(px) == 0) && (mp_cmp_z(py) == 0)) {
1.19 + return MP_YES;
1.20 + } else {
1.21 + return MP_NO;
1.22 + }
1.23 +
1.24 +}
1.25 +
1.26 +/* Sets P(px, py) to be the point at infinity. Uses affine coordinates. */
1.27 +mp_err
1.28 +ec_GF2m_pt_set_inf_aff(mp_int *px, mp_int *py)
1.29 +{
1.30 + mp_zero(px);
1.31 + mp_zero(py);
1.32 + return MP_OKAY;
1.33 +}
1.34 +
1.35 +/* Computes R = P + Q based on IEEE P1363 A.10.2. Elliptic curve points P,
1.36 + * Q, and R can all be identical. Uses affine coordinates. */
1.37 +mp_err
1.38 +ec_GF2m_pt_add_aff(const mp_int *px, const mp_int *py, const mp_int *qx,
1.39 + const mp_int *qy, mp_int *rx, mp_int *ry,
1.40 + const ECGroup *group)
1.41 +{
1.42 + mp_err res = MP_OKAY;
1.43 + mp_int lambda, tempx, tempy;
1.44 +
1.45 + MP_DIGITS(&lambda) = 0;
1.46 + MP_DIGITS(&tempx) = 0;
1.47 + MP_DIGITS(&tempy) = 0;
1.48 + MP_CHECKOK(mp_init(&lambda));
1.49 + MP_CHECKOK(mp_init(&tempx));
1.50 + MP_CHECKOK(mp_init(&tempy));
1.51 + /* if P = inf, then R = Q */
1.52 + if (ec_GF2m_pt_is_inf_aff(px, py) == 0) {
1.53 + MP_CHECKOK(mp_copy(qx, rx));
1.54 + MP_CHECKOK(mp_copy(qy, ry));
1.55 + res = MP_OKAY;
1.56 + goto CLEANUP;
1.57 + }
1.58 + /* if Q = inf, then R = P */
1.59 + if (ec_GF2m_pt_is_inf_aff(qx, qy) == 0) {
1.60 + MP_CHECKOK(mp_copy(px, rx));
1.61 + MP_CHECKOK(mp_copy(py, ry));
1.62 + res = MP_OKAY;
1.63 + goto CLEANUP;
1.64 + }
1.65 + /* if px != qx, then lambda = (py+qy) / (px+qx), tempx = a + lambda^2
1.66 + * + lambda + px + qx */
1.67 + if (mp_cmp(px, qx) != 0) {
1.68 + MP_CHECKOK(group->meth->field_add(py, qy, &tempy, group->meth));
1.69 + MP_CHECKOK(group->meth->field_add(px, qx, &tempx, group->meth));
1.70 + MP_CHECKOK(group->meth->
1.71 + field_div(&tempy, &tempx, &lambda, group->meth));
1.72 + MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth));
1.73 + MP_CHECKOK(group->meth->
1.74 + field_add(&tempx, &lambda, &tempx, group->meth));
1.75 + MP_CHECKOK(group->meth->
1.76 + field_add(&tempx, &group->curvea, &tempx, group->meth));
1.77 + MP_CHECKOK(group->meth->
1.78 + field_add(&tempx, px, &tempx, group->meth));
1.79 + MP_CHECKOK(group->meth->
1.80 + field_add(&tempx, qx, &tempx, group->meth));
1.81 + } else {
1.82 + /* if py != qy or qx = 0, then R = inf */
1.83 + if (((mp_cmp(py, qy) != 0)) || (mp_cmp_z(qx) == 0)) {
1.84 + mp_zero(rx);
1.85 + mp_zero(ry);
1.86 + res = MP_OKAY;
1.87 + goto CLEANUP;
1.88 + }
1.89 + /* lambda = qx + qy / qx */
1.90 + MP_CHECKOK(group->meth->field_div(qy, qx, &lambda, group->meth));
1.91 + MP_CHECKOK(group->meth->
1.92 + field_add(&lambda, qx, &lambda, group->meth));
1.93 + /* tempx = a + lambda^2 + lambda */
1.94 + MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth));
1.95 + MP_CHECKOK(group->meth->
1.96 + field_add(&tempx, &lambda, &tempx, group->meth));
1.97 + MP_CHECKOK(group->meth->
1.98 + field_add(&tempx, &group->curvea, &tempx, group->meth));
1.99 + }
1.100 + /* ry = (qx + tempx) * lambda + tempx + qy */
1.101 + MP_CHECKOK(group->meth->field_add(qx, &tempx, &tempy, group->meth));
1.102 + MP_CHECKOK(group->meth->
1.103 + field_mul(&tempy, &lambda, &tempy, group->meth));
1.104 + MP_CHECKOK(group->meth->
1.105 + field_add(&tempy, &tempx, &tempy, group->meth));
1.106 + MP_CHECKOK(group->meth->field_add(&tempy, qy, ry, group->meth));
1.107 + /* rx = tempx */
1.108 + MP_CHECKOK(mp_copy(&tempx, rx));
1.109 +
1.110 + CLEANUP:
1.111 + mp_clear(&lambda);
1.112 + mp_clear(&tempx);
1.113 + mp_clear(&tempy);
1.114 + return res;
1.115 +}
1.116 +
1.117 +/* Computes R = P - Q. Elliptic curve points P, Q, and R can all be
1.118 + * identical. Uses affine coordinates. */
1.119 +mp_err
1.120 +ec_GF2m_pt_sub_aff(const mp_int *px, const mp_int *py, const mp_int *qx,
1.121 + const mp_int *qy, mp_int *rx, mp_int *ry,
1.122 + const ECGroup *group)
1.123 +{
1.124 + mp_err res = MP_OKAY;
1.125 + mp_int nqy;
1.126 +
1.127 + MP_DIGITS(&nqy) = 0;
1.128 + MP_CHECKOK(mp_init(&nqy));
1.129 + /* nqy = qx+qy */
1.130 + MP_CHECKOK(group->meth->field_add(qx, qy, &nqy, group->meth));
1.131 + MP_CHECKOK(group->point_add(px, py, qx, &nqy, rx, ry, group));
1.132 + CLEANUP:
1.133 + mp_clear(&nqy);
1.134 + return res;
1.135 +}
1.136 +
1.137 +/* Computes R = 2P. Elliptic curve points P and R can be identical. Uses
1.138 + * affine coordinates. */
1.139 +mp_err
1.140 +ec_GF2m_pt_dbl_aff(const mp_int *px, const mp_int *py, mp_int *rx,
1.141 + mp_int *ry, const ECGroup *group)
1.142 +{
1.143 + return group->point_add(px, py, px, py, rx, ry, group);
1.144 +}
1.145 +
1.146 +/* by default, this routine is unused and thus doesn't need to be compiled */
1.147 +#ifdef ECL_ENABLE_GF2M_PT_MUL_AFF
1.148 +/* Computes R = nP based on IEEE P1363 A.10.3. Elliptic curve points P and
1.149 + * R can be identical. Uses affine coordinates. */
1.150 +mp_err
1.151 +ec_GF2m_pt_mul_aff(const mp_int *n, const mp_int *px, const mp_int *py,
1.152 + mp_int *rx, mp_int *ry, const ECGroup *group)
1.153 +{
1.154 + mp_err res = MP_OKAY;
1.155 + mp_int k, k3, qx, qy, sx, sy;
1.156 + int b1, b3, i, l;
1.157 +
1.158 + MP_DIGITS(&k) = 0;
1.159 + MP_DIGITS(&k3) = 0;
1.160 + MP_DIGITS(&qx) = 0;
1.161 + MP_DIGITS(&qy) = 0;
1.162 + MP_DIGITS(&sx) = 0;
1.163 + MP_DIGITS(&sy) = 0;
1.164 + MP_CHECKOK(mp_init(&k));
1.165 + MP_CHECKOK(mp_init(&k3));
1.166 + MP_CHECKOK(mp_init(&qx));
1.167 + MP_CHECKOK(mp_init(&qy));
1.168 + MP_CHECKOK(mp_init(&sx));
1.169 + MP_CHECKOK(mp_init(&sy));
1.170 +
1.171 + /* if n = 0 then r = inf */
1.172 + if (mp_cmp_z(n) == 0) {
1.173 + mp_zero(rx);
1.174 + mp_zero(ry);
1.175 + res = MP_OKAY;
1.176 + goto CLEANUP;
1.177 + }
1.178 + /* Q = P, k = n */
1.179 + MP_CHECKOK(mp_copy(px, &qx));
1.180 + MP_CHECKOK(mp_copy(py, &qy));
1.181 + MP_CHECKOK(mp_copy(n, &k));
1.182 + /* if n < 0 then Q = -Q, k = -k */
1.183 + if (mp_cmp_z(n) < 0) {
1.184 + MP_CHECKOK(group->meth->field_add(&qx, &qy, &qy, group->meth));
1.185 + MP_CHECKOK(mp_neg(&k, &k));
1.186 + }
1.187 +#ifdef ECL_DEBUG /* basic double and add method */
1.188 + l = mpl_significant_bits(&k) - 1;
1.189 + MP_CHECKOK(mp_copy(&qx, &sx));
1.190 + MP_CHECKOK(mp_copy(&qy, &sy));
1.191 + for (i = l - 1; i >= 0; i--) {
1.192 + /* S = 2S */
1.193 + MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group));
1.194 + /* if k_i = 1, then S = S + Q */
1.195 + if (mpl_get_bit(&k, i) != 0) {
1.196 + MP_CHECKOK(group->
1.197 + point_add(&sx, &sy, &qx, &qy, &sx, &sy, group));
1.198 + }
1.199 + }
1.200 +#else /* double and add/subtract method from
1.201 + * standard */
1.202 + /* k3 = 3 * k */
1.203 + MP_CHECKOK(mp_set_int(&k3, 3));
1.204 + MP_CHECKOK(mp_mul(&k, &k3, &k3));
1.205 + /* S = Q */
1.206 + MP_CHECKOK(mp_copy(&qx, &sx));
1.207 + MP_CHECKOK(mp_copy(&qy, &sy));
1.208 + /* l = index of high order bit in binary representation of 3*k */
1.209 + l = mpl_significant_bits(&k3) - 1;
1.210 + /* for i = l-1 downto 1 */
1.211 + for (i = l - 1; i >= 1; i--) {
1.212 + /* S = 2S */
1.213 + MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group));
1.214 + b3 = MP_GET_BIT(&k3, i);
1.215 + b1 = MP_GET_BIT(&k, i);
1.216 + /* if k3_i = 1 and k_i = 0, then S = S + Q */
1.217 + if ((b3 == 1) && (b1 == 0)) {
1.218 + MP_CHECKOK(group->
1.219 + point_add(&sx, &sy, &qx, &qy, &sx, &sy, group));
1.220 + /* if k3_i = 0 and k_i = 1, then S = S - Q */
1.221 + } else if ((b3 == 0) && (b1 == 1)) {
1.222 + MP_CHECKOK(group->
1.223 + point_sub(&sx, &sy, &qx, &qy, &sx, &sy, group));
1.224 + }
1.225 + }
1.226 +#endif
1.227 + /* output S */
1.228 + MP_CHECKOK(mp_copy(&sx, rx));
1.229 + MP_CHECKOK(mp_copy(&sy, ry));
1.230 +
1.231 + CLEANUP:
1.232 + mp_clear(&k);
1.233 + mp_clear(&k3);
1.234 + mp_clear(&qx);
1.235 + mp_clear(&qy);
1.236 + mp_clear(&sx);
1.237 + mp_clear(&sy);
1.238 + return res;
1.239 +}
1.240 +#endif
1.241 +
1.242 +/* Validates a point on a GF2m curve. */
1.243 +mp_err
1.244 +ec_GF2m_validate_point(const mp_int *px, const mp_int *py, const ECGroup *group)
1.245 +{
1.246 + mp_err res = MP_NO;
1.247 + mp_int accl, accr, tmp, pxt, pyt;
1.248 +
1.249 + MP_DIGITS(&accl) = 0;
1.250 + MP_DIGITS(&accr) = 0;
1.251 + MP_DIGITS(&tmp) = 0;
1.252 + MP_DIGITS(&pxt) = 0;
1.253 + MP_DIGITS(&pyt) = 0;
1.254 + MP_CHECKOK(mp_init(&accl));
1.255 + MP_CHECKOK(mp_init(&accr));
1.256 + MP_CHECKOK(mp_init(&tmp));
1.257 + MP_CHECKOK(mp_init(&pxt));
1.258 + MP_CHECKOK(mp_init(&pyt));
1.259 +
1.260 + /* 1: Verify that publicValue is not the point at infinity */
1.261 + if (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES) {
1.262 + res = MP_NO;
1.263 + goto CLEANUP;
1.264 + }
1.265 + /* 2: Verify that the coordinates of publicValue are elements
1.266 + * of the field.
1.267 + */
1.268 + if ((MP_SIGN(px) == MP_NEG) || (mp_cmp(px, &group->meth->irr) >= 0) ||
1.269 + (MP_SIGN(py) == MP_NEG) || (mp_cmp(py, &group->meth->irr) >= 0)) {
1.270 + res = MP_NO;
1.271 + goto CLEANUP;
1.272 + }
1.273 + /* 3: Verify that publicValue is on the curve. */
1.274 + if (group->meth->field_enc) {
1.275 + group->meth->field_enc(px, &pxt, group->meth);
1.276 + group->meth->field_enc(py, &pyt, group->meth);
1.277 + } else {
1.278 + mp_copy(px, &pxt);
1.279 + mp_copy(py, &pyt);
1.280 + }
1.281 + /* left-hand side: y^2 + x*y */
1.282 + MP_CHECKOK( group->meth->field_sqr(&pyt, &accl, group->meth) );
1.283 + MP_CHECKOK( group->meth->field_mul(&pxt, &pyt, &tmp, group->meth) );
1.284 + MP_CHECKOK( group->meth->field_add(&accl, &tmp, &accl, group->meth) );
1.285 + /* right-hand side: x^3 + a*x^2 + b */
1.286 + MP_CHECKOK( group->meth->field_sqr(&pxt, &tmp, group->meth) );
1.287 + MP_CHECKOK( group->meth->field_mul(&pxt, &tmp, &accr, group->meth) );
1.288 + MP_CHECKOK( group->meth->field_mul(&group->curvea, &tmp, &tmp, group->meth) );
1.289 + MP_CHECKOK( group->meth->field_add(&tmp, &accr, &accr, group->meth) );
1.290 + MP_CHECKOK( group->meth->field_add(&accr, &group->curveb, &accr, group->meth) );
1.291 + /* check LHS - RHS == 0 */
1.292 + MP_CHECKOK( group->meth->field_add(&accl, &accr, &accr, group->meth) );
1.293 + if (mp_cmp_z(&accr) != 0) {
1.294 + res = MP_NO;
1.295 + goto CLEANUP;
1.296 + }
1.297 + /* 4: Verify that the order of the curve times the publicValue
1.298 + * is the point at infinity.
1.299 + */
1.300 + MP_CHECKOK( ECPoint_mul(group, &group->order, px, py, &pxt, &pyt) );
1.301 + if (ec_GF2m_pt_is_inf_aff(&pxt, &pyt) != MP_YES) {
1.302 + res = MP_NO;
1.303 + goto CLEANUP;
1.304 + }
1.305 +
1.306 + res = MP_YES;
1.307 +
1.308 +CLEANUP:
1.309 + mp_clear(&accl);
1.310 + mp_clear(&accr);
1.311 + mp_clear(&tmp);
1.312 + mp_clear(&pxt);
1.313 + mp_clear(&pyt);
1.314 + return res;
1.315 +}
