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