1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/ec2_proj.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,333 @@
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 +#ifdef ECL_DEBUG
1.13 +#include <assert.h>
1.14 +#endif
1.15 +
1.16 +/* by default, these routines are unused and thus don't need to be compiled */
1.17 +#ifdef ECL_ENABLE_GF2M_PROJ
1.18 +/* Converts a point P(px, py) from affine coordinates to projective
1.19 + * coordinates R(rx, ry, rz). Assumes input is already field-encoded using
1.20 + * field_enc, and returns output that is still field-encoded. */
1.21 +mp_err
1.22 +ec_GF2m_pt_aff2proj(const mp_int *px, const mp_int *py, mp_int *rx,
1.23 + mp_int *ry, mp_int *rz, const ECGroup *group)
1.24 +{
1.25 + mp_err res = MP_OKAY;
1.26 +
1.27 + MP_CHECKOK(mp_copy(px, rx));
1.28 + MP_CHECKOK(mp_copy(py, ry));
1.29 + MP_CHECKOK(mp_set_int(rz, 1));
1.30 + if (group->meth->field_enc) {
1.31 + MP_CHECKOK(group->meth->field_enc(rz, rz, group->meth));
1.32 + }
1.33 + CLEANUP:
1.34 + return res;
1.35 +}
1.36 +
1.37 +/* Converts a point P(px, py, pz) from projective coordinates to affine
1.38 + * coordinates R(rx, ry). P and R can share x and y coordinates. Assumes
1.39 + * input is already field-encoded using field_enc, and returns output that
1.40 + * is still field-encoded. */
1.41 +mp_err
1.42 +ec_GF2m_pt_proj2aff(const mp_int *px, const mp_int *py, const mp_int *pz,
1.43 + mp_int *rx, mp_int *ry, const ECGroup *group)
1.44 +{
1.45 + mp_err res = MP_OKAY;
1.46 + mp_int z1, z2;
1.47 +
1.48 + MP_DIGITS(&z1) = 0;
1.49 + MP_DIGITS(&z2) = 0;
1.50 + MP_CHECKOK(mp_init(&z1));
1.51 + MP_CHECKOK(mp_init(&z2));
1.52 +
1.53 + /* if point at infinity, then set point at infinity and exit */
1.54 + if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {
1.55 + MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
1.56 + goto CLEANUP;
1.57 + }
1.58 +
1.59 + /* transform (px, py, pz) into (px / pz, py / pz^2) */
1.60 + if (mp_cmp_d(pz, 1) == 0) {
1.61 + MP_CHECKOK(mp_copy(px, rx));
1.62 + MP_CHECKOK(mp_copy(py, ry));
1.63 + } else {
1.64 + MP_CHECKOK(group->meth->field_div(NULL, pz, &z1, group->meth));
1.65 + MP_CHECKOK(group->meth->field_sqr(&z1, &z2, group->meth));
1.66 + MP_CHECKOK(group->meth->field_mul(px, &z1, rx, group->meth));
1.67 + MP_CHECKOK(group->meth->field_mul(py, &z2, ry, group->meth));
1.68 + }
1.69 +
1.70 + CLEANUP:
1.71 + mp_clear(&z1);
1.72 + mp_clear(&z2);
1.73 + return res;
1.74 +}
1.75 +
1.76 +/* Checks if point P(px, py, pz) is at infinity. Uses projective
1.77 + * coordinates. */
1.78 +mp_err
1.79 +ec_GF2m_pt_is_inf_proj(const mp_int *px, const mp_int *py,
1.80 + const mp_int *pz)
1.81 +{
1.82 + return mp_cmp_z(pz);
1.83 +}
1.84 +
1.85 +/* Sets P(px, py, pz) to be the point at infinity. Uses projective
1.86 + * coordinates. */
1.87 +mp_err
1.88 +ec_GF2m_pt_set_inf_proj(mp_int *px, mp_int *py, mp_int *pz)
1.89 +{
1.90 + mp_zero(pz);
1.91 + return MP_OKAY;
1.92 +}
1.93 +
1.94 +/* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is
1.95 + * (qx, qy, 1). Elliptic curve points P, Q, and R can all be identical.
1.96 + * Uses mixed projective-affine coordinates. Assumes input is already
1.97 + * field-encoded using field_enc, and returns output that is still
1.98 + * field-encoded. Uses equation (3) from Hankerson, Hernandez, Menezes.
1.99 + * Software Implementation of Elliptic Curve Cryptography Over Binary
1.100 + * Fields. */
1.101 +mp_err
1.102 +ec_GF2m_pt_add_proj(const mp_int *px, const mp_int *py, const mp_int *pz,
1.103 + const mp_int *qx, const mp_int *qy, mp_int *rx,
1.104 + mp_int *ry, mp_int *rz, const ECGroup *group)
1.105 +{
1.106 + mp_err res = MP_OKAY;
1.107 + mp_int A, B, C, D, E, F, G;
1.108 +
1.109 + /* If either P or Q is the point at infinity, then return the other
1.110 + * point */
1.111 + if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {
1.112 + return ec_GF2m_pt_aff2proj(qx, qy, rx, ry, rz, group);
1.113 + }
1.114 + if (ec_GF2m_pt_is_inf_aff(qx, qy) == MP_YES) {
1.115 + MP_CHECKOK(mp_copy(px, rx));
1.116 + MP_CHECKOK(mp_copy(py, ry));
1.117 + return mp_copy(pz, rz);
1.118 + }
1.119 +
1.120 + MP_DIGITS(&A) = 0;
1.121 + MP_DIGITS(&B) = 0;
1.122 + MP_DIGITS(&C) = 0;
1.123 + MP_DIGITS(&D) = 0;
1.124 + MP_DIGITS(&E) = 0;
1.125 + MP_DIGITS(&F) = 0;
1.126 + MP_DIGITS(&G) = 0;
1.127 + MP_CHECKOK(mp_init(&A));
1.128 + MP_CHECKOK(mp_init(&B));
1.129 + MP_CHECKOK(mp_init(&C));
1.130 + MP_CHECKOK(mp_init(&D));
1.131 + MP_CHECKOK(mp_init(&E));
1.132 + MP_CHECKOK(mp_init(&F));
1.133 + MP_CHECKOK(mp_init(&G));
1.134 +
1.135 + /* D = pz^2 */
1.136 + MP_CHECKOK(group->meth->field_sqr(pz, &D, group->meth));
1.137 +
1.138 + /* A = qy * pz^2 + py */
1.139 + MP_CHECKOK(group->meth->field_mul(qy, &D, &A, group->meth));
1.140 + MP_CHECKOK(group->meth->field_add(&A, py, &A, group->meth));
1.141 +
1.142 + /* B = qx * pz + px */
1.143 + MP_CHECKOK(group->meth->field_mul(qx, pz, &B, group->meth));
1.144 + MP_CHECKOK(group->meth->field_add(&B, px, &B, group->meth));
1.145 +
1.146 + /* C = pz * B */
1.147 + MP_CHECKOK(group->meth->field_mul(pz, &B, &C, group->meth));
1.148 +
1.149 + /* D = B^2 * (C + a * pz^2) (using E as a temporary variable) */
1.150 + MP_CHECKOK(group->meth->
1.151 + field_mul(&group->curvea, &D, &D, group->meth));
1.152 + MP_CHECKOK(group->meth->field_add(&C, &D, &D, group->meth));
1.153 + MP_CHECKOK(group->meth->field_sqr(&B, &E, group->meth));
1.154 + MP_CHECKOK(group->meth->field_mul(&E, &D, &D, group->meth));
1.155 +
1.156 + /* rz = C^2 */
1.157 + MP_CHECKOK(group->meth->field_sqr(&C, rz, group->meth));
1.158 +
1.159 + /* E = A * C */
1.160 + MP_CHECKOK(group->meth->field_mul(&A, &C, &E, group->meth));
1.161 +
1.162 + /* rx = A^2 + D + E */
1.163 + MP_CHECKOK(group->meth->field_sqr(&A, rx, group->meth));
1.164 + MP_CHECKOK(group->meth->field_add(rx, &D, rx, group->meth));
1.165 + MP_CHECKOK(group->meth->field_add(rx, &E, rx, group->meth));
1.166 +
1.167 + /* F = rx + qx * rz */
1.168 + MP_CHECKOK(group->meth->field_mul(qx, rz, &F, group->meth));
1.169 + MP_CHECKOK(group->meth->field_add(rx, &F, &F, group->meth));
1.170 +
1.171 + /* G = rx + qy * rz */
1.172 + MP_CHECKOK(group->meth->field_mul(qy, rz, &G, group->meth));
1.173 + MP_CHECKOK(group->meth->field_add(rx, &G, &G, group->meth));
1.174 +
1.175 + /* ry = E * F + rz * G (using G as a temporary variable) */
1.176 + MP_CHECKOK(group->meth->field_mul(rz, &G, &G, group->meth));
1.177 + MP_CHECKOK(group->meth->field_mul(&E, &F, ry, group->meth));
1.178 + MP_CHECKOK(group->meth->field_add(ry, &G, ry, group->meth));
1.179 +
1.180 + CLEANUP:
1.181 + mp_clear(&A);
1.182 + mp_clear(&B);
1.183 + mp_clear(&C);
1.184 + mp_clear(&D);
1.185 + mp_clear(&E);
1.186 + mp_clear(&F);
1.187 + mp_clear(&G);
1.188 + return res;
1.189 +}
1.190 +
1.191 +/* Computes R = 2P. Elliptic curve points P and R can be identical. Uses
1.192 + * projective coordinates.
1.193 + *
1.194 + * Assumes input is already field-encoded using field_enc, and returns
1.195 + * output that is still field-encoded.
1.196 + *
1.197 + * Uses equation (3) from Hankerson, Hernandez, Menezes. Software
1.198 + * Implementation of Elliptic Curve Cryptography Over Binary Fields.
1.199 + */
1.200 +mp_err
1.201 +ec_GF2m_pt_dbl_proj(const mp_int *px, const mp_int *py, const mp_int *pz,
1.202 + mp_int *rx, mp_int *ry, mp_int *rz,
1.203 + const ECGroup *group)
1.204 +{
1.205 + mp_err res = MP_OKAY;
1.206 + mp_int t0, t1;
1.207 +
1.208 + if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {
1.209 + return ec_GF2m_pt_set_inf_proj(rx, ry, rz);
1.210 + }
1.211 +
1.212 + MP_DIGITS(&t0) = 0;
1.213 + MP_DIGITS(&t1) = 0;
1.214 + MP_CHECKOK(mp_init(&t0));
1.215 + MP_CHECKOK(mp_init(&t1));
1.216 +
1.217 + /* t0 = px^2 */
1.218 + /* t1 = pz^2 */
1.219 + MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth));
1.220 + MP_CHECKOK(group->meth->field_sqr(pz, &t1, group->meth));
1.221 +
1.222 + /* rz = px^2 * pz^2 */
1.223 + MP_CHECKOK(group->meth->field_mul(&t0, &t1, rz, group->meth));
1.224 +
1.225 + /* t0 = px^4 */
1.226 + /* t1 = b * pz^4 */
1.227 + MP_CHECKOK(group->meth->field_sqr(&t0, &t0, group->meth));
1.228 + MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));
1.229 + MP_CHECKOK(group->meth->
1.230 + field_mul(&group->curveb, &t1, &t1, group->meth));
1.231 +
1.232 + /* rx = px^4 + b * pz^4 */
1.233 + MP_CHECKOK(group->meth->field_add(&t0, &t1, rx, group->meth));
1.234 +
1.235 + /* ry = b * pz^4 * rz + rx * (a * rz + py^2 + b * pz^4) */
1.236 + MP_CHECKOK(group->meth->field_sqr(py, ry, group->meth));
1.237 + MP_CHECKOK(group->meth->field_add(ry, &t1, ry, group->meth));
1.238 + /* t0 = a * rz */
1.239 + MP_CHECKOK(group->meth->
1.240 + field_mul(&group->curvea, rz, &t0, group->meth));
1.241 + MP_CHECKOK(group->meth->field_add(&t0, ry, ry, group->meth));
1.242 + MP_CHECKOK(group->meth->field_mul(rx, ry, ry, group->meth));
1.243 + /* t1 = b * pz^4 * rz */
1.244 + MP_CHECKOK(group->meth->field_mul(&t1, rz, &t1, group->meth));
1.245 + MP_CHECKOK(group->meth->field_add(&t1, ry, ry, group->meth));
1.246 +
1.247 + CLEANUP:
1.248 + mp_clear(&t0);
1.249 + mp_clear(&t1);
1.250 + return res;
1.251 +}
1.252 +
1.253 +/* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters
1.254 + * a, b and p are the elliptic curve coefficients and the prime that
1.255 + * determines the field GF2m. Elliptic curve points P and R can be
1.256 + * identical. Uses mixed projective-affine coordinates. Assumes input is
1.257 + * already field-encoded using field_enc, and returns output that is still
1.258 + * field-encoded. Uses 4-bit window method. */
1.259 +mp_err
1.260 +ec_GF2m_pt_mul_proj(const mp_int *n, const mp_int *px, const mp_int *py,
1.261 + mp_int *rx, mp_int *ry, const ECGroup *group)
1.262 +{
1.263 + mp_err res = MP_OKAY;
1.264 + mp_int precomp[16][2], rz;
1.265 + mp_digit precomp_arr[ECL_MAX_FIELD_SIZE_DIGITS * 16 * 2], *t;
1.266 + int i, ni, d;
1.267 +
1.268 + ARGCHK(group != NULL, MP_BADARG);
1.269 + ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG);
1.270 +
1.271 + /* initialize precomputation table */
1.272 + t = precomp_arr;
1.273 + for (i = 0; i < 16; i++) {
1.274 + /* x co-ord */
1.275 + MP_SIGN(&precomp[i][0]) = MP_ZPOS;
1.276 + MP_ALLOC(&precomp[i][0]) = ECL_MAX_FIELD_SIZE_DIGITS;
1.277 + MP_USED(&precomp[i][0]) = 1;
1.278 + *t = 0;
1.279 + MP_DIGITS(&precomp[i][0]) = t;
1.280 + t += ECL_MAX_FIELD_SIZE_DIGITS;
1.281 + /* y co-ord */
1.282 + MP_SIGN(&precomp[i][1]) = MP_ZPOS;
1.283 + MP_ALLOC(&precomp[i][1]) = ECL_MAX_FIELD_SIZE_DIGITS;
1.284 + MP_USED(&precomp[i][1]) = 1;
1.285 + *t = 0;
1.286 + MP_DIGITS(&precomp[i][1]) = t;
1.287 + t += ECL_MAX_FIELD_SIZE_DIGITS;
1.288 + }
1.289 +
1.290 + /* fill precomputation table */
1.291 + mp_zero(&precomp[0][0]);
1.292 + mp_zero(&precomp[0][1]);
1.293 + MP_CHECKOK(mp_copy(px, &precomp[1][0]));
1.294 + MP_CHECKOK(mp_copy(py, &precomp[1][1]));
1.295 + for (i = 2; i < 16; i++) {
1.296 + MP_CHECKOK(group->
1.297 + point_add(&precomp[1][0], &precomp[1][1],
1.298 + &precomp[i - 1][0], &precomp[i - 1][1],
1.299 + &precomp[i][0], &precomp[i][1], group));
1.300 + }
1.301 +
1.302 + d = (mpl_significant_bits(n) + 3) / 4;
1.303 +
1.304 + /* R = inf */
1.305 + MP_DIGITS(&rz) = 0;
1.306 + MP_CHECKOK(mp_init(&rz));
1.307 + MP_CHECKOK(ec_GF2m_pt_set_inf_proj(rx, ry, &rz));
1.308 +
1.309 + for (i = d - 1; i >= 0; i--) {
1.310 + /* compute window ni */
1.311 + ni = MP_GET_BIT(n, 4 * i + 3);
1.312 + ni <<= 1;
1.313 + ni |= MP_GET_BIT(n, 4 * i + 2);
1.314 + ni <<= 1;
1.315 + ni |= MP_GET_BIT(n, 4 * i + 1);
1.316 + ni <<= 1;
1.317 + ni |= MP_GET_BIT(n, 4 * i);
1.318 + /* R = 2^4 * R */
1.319 + MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
1.320 + MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
1.321 + MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
1.322 + MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
1.323 + /* R = R + (ni * P) */
1.324 + MP_CHECKOK(ec_GF2m_pt_add_proj
1.325 + (rx, ry, &rz, &precomp[ni][0], &precomp[ni][1], rx, ry,
1.326 + &rz, group));
1.327 + }
1.328 +
1.329 + /* convert result S to affine coordinates */
1.330 + MP_CHECKOK(ec_GF2m_pt_proj2aff(rx, ry, &rz, rx, ry, group));
1.331 +
1.332 + CLEANUP:
1.333 + mp_clear(&rz);
1.334 + return res;
1.335 +}
1.336 +#endif
