1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/ec2_mont.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,238 @@
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 +/* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery
1.14 + * projective coordinates. Uses algorithm Mdouble in appendix of Lopez, J.
1.15 + * and Dahab, R. "Fast multiplication on elliptic curves over GF(2^m)
1.16 + * without precomputation". modified to not require precomputation of
1.17 + * c=b^{2^{m-1}}. */
1.18 +static mp_err
1.19 +gf2m_Mdouble(mp_int *x, mp_int *z, const ECGroup *group)
1.20 +{
1.21 + mp_err res = MP_OKAY;
1.22 + mp_int t1;
1.23 +
1.24 + MP_DIGITS(&t1) = 0;
1.25 + MP_CHECKOK(mp_init(&t1));
1.26 +
1.27 + MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
1.28 + MP_CHECKOK(group->meth->field_sqr(z, &t1, group->meth));
1.29 + MP_CHECKOK(group->meth->field_mul(x, &t1, z, group->meth));
1.30 + MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
1.31 + MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));
1.32 + MP_CHECKOK(group->meth->
1.33 + field_mul(&group->curveb, &t1, &t1, group->meth));
1.34 + MP_CHECKOK(group->meth->field_add(x, &t1, x, group->meth));
1.35 +
1.36 + CLEANUP:
1.37 + mp_clear(&t1);
1.38 + return res;
1.39 +}
1.40 +
1.41 +/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in
1.42 + * Montgomery projective coordinates. Uses algorithm Madd in appendix of
1.43 + * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
1.44 + * GF(2^m) without precomputation". */
1.45 +static mp_err
1.46 +gf2m_Madd(const mp_int *x, mp_int *x1, mp_int *z1, mp_int *x2, mp_int *z2,
1.47 + const ECGroup *group)
1.48 +{
1.49 + mp_err res = MP_OKAY;
1.50 + mp_int t1, t2;
1.51 +
1.52 + MP_DIGITS(&t1) = 0;
1.53 + MP_DIGITS(&t2) = 0;
1.54 + MP_CHECKOK(mp_init(&t1));
1.55 + MP_CHECKOK(mp_init(&t2));
1.56 +
1.57 + MP_CHECKOK(mp_copy(x, &t1));
1.58 + MP_CHECKOK(group->meth->field_mul(x1, z2, x1, group->meth));
1.59 + MP_CHECKOK(group->meth->field_mul(z1, x2, z1, group->meth));
1.60 + MP_CHECKOK(group->meth->field_mul(x1, z1, &t2, group->meth));
1.61 + MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
1.62 + MP_CHECKOK(group->meth->field_sqr(z1, z1, group->meth));
1.63 + MP_CHECKOK(group->meth->field_mul(z1, &t1, x1, group->meth));
1.64 + MP_CHECKOK(group->meth->field_add(x1, &t2, x1, group->meth));
1.65 +
1.66 + CLEANUP:
1.67 + mp_clear(&t1);
1.68 + mp_clear(&t2);
1.69 + return res;
1.70 +}
1.71 +
1.72 +/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
1.73 + * using Montgomery point multiplication algorithm Mxy() in appendix of
1.74 + * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
1.75 + * GF(2^m) without precomputation". Returns: 0 on error 1 if return value
1.76 + * should be the point at infinity 2 otherwise */
1.77 +static int
1.78 +gf2m_Mxy(const mp_int *x, const mp_int *y, mp_int *x1, mp_int *z1,
1.79 + mp_int *x2, mp_int *z2, const ECGroup *group)
1.80 +{
1.81 + mp_err res = MP_OKAY;
1.82 + int ret = 0;
1.83 + mp_int t3, t4, t5;
1.84 +
1.85 + MP_DIGITS(&t3) = 0;
1.86 + MP_DIGITS(&t4) = 0;
1.87 + MP_DIGITS(&t5) = 0;
1.88 + MP_CHECKOK(mp_init(&t3));
1.89 + MP_CHECKOK(mp_init(&t4));
1.90 + MP_CHECKOK(mp_init(&t5));
1.91 +
1.92 + if (mp_cmp_z(z1) == 0) {
1.93 + mp_zero(x2);
1.94 + mp_zero(z2);
1.95 + ret = 1;
1.96 + goto CLEANUP;
1.97 + }
1.98 +
1.99 + if (mp_cmp_z(z2) == 0) {
1.100 + MP_CHECKOK(mp_copy(x, x2));
1.101 + MP_CHECKOK(group->meth->field_add(x, y, z2, group->meth));
1.102 + ret = 2;
1.103 + goto CLEANUP;
1.104 + }
1.105 +
1.106 + MP_CHECKOK(mp_set_int(&t5, 1));
1.107 + if (group->meth->field_enc) {
1.108 + MP_CHECKOK(group->meth->field_enc(&t5, &t5, group->meth));
1.109 + }
1.110 +
1.111 + MP_CHECKOK(group->meth->field_mul(z1, z2, &t3, group->meth));
1.112 +
1.113 + MP_CHECKOK(group->meth->field_mul(z1, x, z1, group->meth));
1.114 + MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
1.115 + MP_CHECKOK(group->meth->field_mul(z2, x, z2, group->meth));
1.116 + MP_CHECKOK(group->meth->field_mul(z2, x1, x1, group->meth));
1.117 + MP_CHECKOK(group->meth->field_add(z2, x2, z2, group->meth));
1.118 +
1.119 + MP_CHECKOK(group->meth->field_mul(z2, z1, z2, group->meth));
1.120 + MP_CHECKOK(group->meth->field_sqr(x, &t4, group->meth));
1.121 + MP_CHECKOK(group->meth->field_add(&t4, y, &t4, group->meth));
1.122 + MP_CHECKOK(group->meth->field_mul(&t4, &t3, &t4, group->meth));
1.123 + MP_CHECKOK(group->meth->field_add(&t4, z2, &t4, group->meth));
1.124 +
1.125 + MP_CHECKOK(group->meth->field_mul(&t3, x, &t3, group->meth));
1.126 + MP_CHECKOK(group->meth->field_div(&t5, &t3, &t3, group->meth));
1.127 + MP_CHECKOK(group->meth->field_mul(&t3, &t4, &t4, group->meth));
1.128 + MP_CHECKOK(group->meth->field_mul(x1, &t3, x2, group->meth));
1.129 + MP_CHECKOK(group->meth->field_add(x2, x, z2, group->meth));
1.130 +
1.131 + MP_CHECKOK(group->meth->field_mul(z2, &t4, z2, group->meth));
1.132 + MP_CHECKOK(group->meth->field_add(z2, y, z2, group->meth));
1.133 +
1.134 + ret = 2;
1.135 +
1.136 + CLEANUP:
1.137 + mp_clear(&t3);
1.138 + mp_clear(&t4);
1.139 + mp_clear(&t5);
1.140 + if (res == MP_OKAY) {
1.141 + return ret;
1.142 + } else {
1.143 + return 0;
1.144 + }
1.145 +}
1.146 +
1.147 +/* Computes R = nP based on algorithm 2P of Lopex, J. and Dahab, R. "Fast
1.148 + * multiplication on elliptic curves over GF(2^m) without
1.149 + * precomputation". Elliptic curve points P and R can be identical. Uses
1.150 + * Montgomery projective coordinates. */
1.151 +mp_err
1.152 +ec_GF2m_pt_mul_mont(const mp_int *n, const mp_int *px, const mp_int *py,
1.153 + mp_int *rx, mp_int *ry, const ECGroup *group)
1.154 +{
1.155 + mp_err res = MP_OKAY;
1.156 + mp_int x1, x2, z1, z2;
1.157 + int i, j;
1.158 + mp_digit top_bit, mask;
1.159 +
1.160 + MP_DIGITS(&x1) = 0;
1.161 + MP_DIGITS(&x2) = 0;
1.162 + MP_DIGITS(&z1) = 0;
1.163 + MP_DIGITS(&z2) = 0;
1.164 + MP_CHECKOK(mp_init(&x1));
1.165 + MP_CHECKOK(mp_init(&x2));
1.166 + MP_CHECKOK(mp_init(&z1));
1.167 + MP_CHECKOK(mp_init(&z2));
1.168 +
1.169 + /* if result should be point at infinity */
1.170 + if ((mp_cmp_z(n) == 0) || (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES)) {
1.171 + MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
1.172 + goto CLEANUP;
1.173 + }
1.174 +
1.175 + MP_CHECKOK(mp_copy(px, &x1)); /* x1 = px */
1.176 + MP_CHECKOK(mp_set_int(&z1, 1)); /* z1 = 1 */
1.177 + MP_CHECKOK(group->meth->field_sqr(&x1, &z2, group->meth)); /* z2 =
1.178 + * x1^2 =
1.179 + * px^2 */
1.180 + MP_CHECKOK(group->meth->field_sqr(&z2, &x2, group->meth));
1.181 + MP_CHECKOK(group->meth->field_add(&x2, &group->curveb, &x2, group->meth)); /* x2
1.182 + * =
1.183 + * px^4
1.184 + * +
1.185 + * b
1.186 + */
1.187 +
1.188 + /* find top-most bit and go one past it */
1.189 + i = MP_USED(n) - 1;
1.190 + j = MP_DIGIT_BIT - 1;
1.191 + top_bit = 1;
1.192 + top_bit <<= MP_DIGIT_BIT - 1;
1.193 + mask = top_bit;
1.194 + while (!(MP_DIGITS(n)[i] & mask)) {
1.195 + mask >>= 1;
1.196 + j--;
1.197 + }
1.198 + mask >>= 1;
1.199 + j--;
1.200 +
1.201 + /* if top most bit was at word break, go to next word */
1.202 + if (!mask) {
1.203 + i--;
1.204 + j = MP_DIGIT_BIT - 1;
1.205 + mask = top_bit;
1.206 + }
1.207 +
1.208 + for (; i >= 0; i--) {
1.209 + for (; j >= 0; j--) {
1.210 + if (MP_DIGITS(n)[i] & mask) {
1.211 + MP_CHECKOK(gf2m_Madd(px, &x1, &z1, &x2, &z2, group));
1.212 + MP_CHECKOK(gf2m_Mdouble(&x2, &z2, group));
1.213 + } else {
1.214 + MP_CHECKOK(gf2m_Madd(px, &x2, &z2, &x1, &z1, group));
1.215 + MP_CHECKOK(gf2m_Mdouble(&x1, &z1, group));
1.216 + }
1.217 + mask >>= 1;
1.218 + }
1.219 + j = MP_DIGIT_BIT - 1;
1.220 + mask = top_bit;
1.221 + }
1.222 +
1.223 + /* convert out of "projective" coordinates */
1.224 + i = gf2m_Mxy(px, py, &x1, &z1, &x2, &z2, group);
1.225 + if (i == 0) {
1.226 + res = MP_BADARG;
1.227 + goto CLEANUP;
1.228 + } else if (i == 1) {
1.229 + MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
1.230 + } else {
1.231 + MP_CHECKOK(mp_copy(&x2, rx));
1.232 + MP_CHECKOK(mp_copy(&z2, ry));
1.233 + }
1.234 +
1.235 + CLEANUP:
1.236 + mp_clear(&x1);
1.237 + mp_clear(&x2);
1.238 + mp_clear(&z1);
1.239 + mp_clear(&z2);
1.240 + return res;
1.241 +}
