1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/ecl_gf.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,997 @@
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 "mpi.h"
1.9 +#include "mp_gf2m.h"
1.10 +#include "ecl-priv.h"
1.11 +#include "mpi-priv.h"
1.12 +#include <stdlib.h>
1.13 +
1.14 +/* Allocate memory for a new GFMethod object. */
1.15 +GFMethod *
1.16 +GFMethod_new()
1.17 +{
1.18 + mp_err res = MP_OKAY;
1.19 + GFMethod *meth;
1.20 + meth = (GFMethod *) malloc(sizeof(GFMethod));
1.21 + if (meth == NULL)
1.22 + return NULL;
1.23 + meth->constructed = MP_YES;
1.24 + MP_DIGITS(&meth->irr) = 0;
1.25 + meth->extra_free = NULL;
1.26 + MP_CHECKOK(mp_init(&meth->irr));
1.27 +
1.28 + CLEANUP:
1.29 + if (res != MP_OKAY) {
1.30 + GFMethod_free(meth);
1.31 + return NULL;
1.32 + }
1.33 + return meth;
1.34 +}
1.35 +
1.36 +/* Construct a generic GFMethod for arithmetic over prime fields with
1.37 + * irreducible irr. */
1.38 +GFMethod *
1.39 +GFMethod_consGFp(const mp_int *irr)
1.40 +{
1.41 + mp_err res = MP_OKAY;
1.42 + GFMethod *meth = NULL;
1.43 +
1.44 + meth = GFMethod_new();
1.45 + if (meth == NULL)
1.46 + return NULL;
1.47 +
1.48 + MP_CHECKOK(mp_copy(irr, &meth->irr));
1.49 + meth->irr_arr[0] = mpl_significant_bits(irr);
1.50 + meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
1.51 + meth->irr_arr[4] = 0;
1.52 + switch(MP_USED(&meth->irr)) {
1.53 + /* maybe we need 1 and 2 words here as well?*/
1.54 + case 3:
1.55 + meth->field_add = &ec_GFp_add_3;
1.56 + meth->field_sub = &ec_GFp_sub_3;
1.57 + break;
1.58 + case 4:
1.59 + meth->field_add = &ec_GFp_add_4;
1.60 + meth->field_sub = &ec_GFp_sub_4;
1.61 + break;
1.62 + case 5:
1.63 + meth->field_add = &ec_GFp_add_5;
1.64 + meth->field_sub = &ec_GFp_sub_5;
1.65 + break;
1.66 + case 6:
1.67 + meth->field_add = &ec_GFp_add_6;
1.68 + meth->field_sub = &ec_GFp_sub_6;
1.69 + break;
1.70 + default:
1.71 + meth->field_add = &ec_GFp_add;
1.72 + meth->field_sub = &ec_GFp_sub;
1.73 + }
1.74 + meth->field_neg = &ec_GFp_neg;
1.75 + meth->field_mod = &ec_GFp_mod;
1.76 + meth->field_mul = &ec_GFp_mul;
1.77 + meth->field_sqr = &ec_GFp_sqr;
1.78 + meth->field_div = &ec_GFp_div;
1.79 + meth->field_enc = NULL;
1.80 + meth->field_dec = NULL;
1.81 + meth->extra1 = NULL;
1.82 + meth->extra2 = NULL;
1.83 + meth->extra_free = NULL;
1.84 +
1.85 + CLEANUP:
1.86 + if (res != MP_OKAY) {
1.87 + GFMethod_free(meth);
1.88 + return NULL;
1.89 + }
1.90 + return meth;
1.91 +}
1.92 +
1.93 +/* Construct a generic GFMethod for arithmetic over binary polynomial
1.94 + * fields with irreducible irr that has array representation irr_arr (see
1.95 + * ecl-priv.h for description of the representation). If irr_arr is NULL,
1.96 + * then it is constructed from the bitstring representation. */
1.97 +GFMethod *
1.98 +GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5])
1.99 +{
1.100 + mp_err res = MP_OKAY;
1.101 + int ret;
1.102 + GFMethod *meth = NULL;
1.103 +
1.104 + meth = GFMethod_new();
1.105 + if (meth == NULL)
1.106 + return NULL;
1.107 +
1.108 + MP_CHECKOK(mp_copy(irr, &meth->irr));
1.109 + if (irr_arr != NULL) {
1.110 + /* Irreducible polynomials are either trinomials or pentanomials. */
1.111 + meth->irr_arr[0] = irr_arr[0];
1.112 + meth->irr_arr[1] = irr_arr[1];
1.113 + meth->irr_arr[2] = irr_arr[2];
1.114 + if (irr_arr[2] > 0) {
1.115 + meth->irr_arr[3] = irr_arr[3];
1.116 + meth->irr_arr[4] = irr_arr[4];
1.117 + } else {
1.118 + meth->irr_arr[3] = meth->irr_arr[4] = 0;
1.119 + }
1.120 + } else {
1.121 + ret = mp_bpoly2arr(irr, meth->irr_arr, 5);
1.122 + /* Irreducible polynomials are either trinomials or pentanomials. */
1.123 + if ((ret != 5) && (ret != 3)) {
1.124 + res = MP_UNDEF;
1.125 + goto CLEANUP;
1.126 + }
1.127 + }
1.128 + meth->field_add = &ec_GF2m_add;
1.129 + meth->field_neg = &ec_GF2m_neg;
1.130 + meth->field_sub = &ec_GF2m_add;
1.131 + meth->field_mod = &ec_GF2m_mod;
1.132 + meth->field_mul = &ec_GF2m_mul;
1.133 + meth->field_sqr = &ec_GF2m_sqr;
1.134 + meth->field_div = &ec_GF2m_div;
1.135 + meth->field_enc = NULL;
1.136 + meth->field_dec = NULL;
1.137 + meth->extra1 = NULL;
1.138 + meth->extra2 = NULL;
1.139 + meth->extra_free = NULL;
1.140 +
1.141 + CLEANUP:
1.142 + if (res != MP_OKAY) {
1.143 + GFMethod_free(meth);
1.144 + return NULL;
1.145 + }
1.146 + return meth;
1.147 +}
1.148 +
1.149 +/* Free the memory allocated (if any) to a GFMethod object. */
1.150 +void
1.151 +GFMethod_free(GFMethod *meth)
1.152 +{
1.153 + if (meth == NULL)
1.154 + return;
1.155 + if (meth->constructed == MP_NO)
1.156 + return;
1.157 + mp_clear(&meth->irr);
1.158 + if (meth->extra_free != NULL)
1.159 + meth->extra_free(meth);
1.160 + free(meth);
1.161 +}
1.162 +
1.163 +/* Wrapper functions for generic prime field arithmetic. */
1.164 +
1.165 +/* Add two field elements. Assumes that 0 <= a, b < meth->irr */
1.166 +mp_err
1.167 +ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
1.168 + const GFMethod *meth)
1.169 +{
1.170 + /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
1.171 + mp_err res;
1.172 +
1.173 + if ((res = mp_add(a, b, r)) != MP_OKAY) {
1.174 + return res;
1.175 + }
1.176 + if (mp_cmp(r, &meth->irr) >= 0) {
1.177 + return mp_sub(r, &meth->irr, r);
1.178 + }
1.179 + return res;
1.180 +}
1.181 +
1.182 +/* Negates a field element. Assumes that 0 <= a < meth->irr */
1.183 +mp_err
1.184 +ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
1.185 +{
1.186 + /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
1.187 +
1.188 + if (mp_cmp_z(a) == 0) {
1.189 + mp_zero(r);
1.190 + return MP_OKAY;
1.191 + }
1.192 + return mp_sub(&meth->irr, a, r);
1.193 +}
1.194 +
1.195 +/* Subtracts two field elements. Assumes that 0 <= a, b < meth->irr */
1.196 +mp_err
1.197 +ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
1.198 + const GFMethod *meth)
1.199 +{
1.200 + mp_err res = MP_OKAY;
1.201 +
1.202 + /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
1.203 + res = mp_sub(a, b, r);
1.204 + if (res == MP_RANGE) {
1.205 + MP_CHECKOK(mp_sub(b, a, r));
1.206 + if (mp_cmp_z(r) < 0) {
1.207 + MP_CHECKOK(mp_add(r, &meth->irr, r));
1.208 + }
1.209 + MP_CHECKOK(ec_GFp_neg(r, r, meth));
1.210 + }
1.211 + if (mp_cmp_z(r) < 0) {
1.212 + MP_CHECKOK(mp_add(r, &meth->irr, r));
1.213 + }
1.214 + CLEANUP:
1.215 + return res;
1.216 +}
1.217 +/*
1.218 + * Inline adds for small curve lengths.
1.219 + */
1.220 +/* 3 words */
1.221 +mp_err
1.222 +ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
1.223 + const GFMethod *meth)
1.224 +{
1.225 + mp_err res = MP_OKAY;
1.226 + mp_digit a0 = 0, a1 = 0, a2 = 0;
1.227 + mp_digit r0 = 0, r1 = 0, r2 = 0;
1.228 + mp_digit carry;
1.229 +
1.230 + switch(MP_USED(a)) {
1.231 + case 3:
1.232 + a2 = MP_DIGIT(a,2);
1.233 + case 2:
1.234 + a1 = MP_DIGIT(a,1);
1.235 + case 1:
1.236 + a0 = MP_DIGIT(a,0);
1.237 + }
1.238 + switch(MP_USED(b)) {
1.239 + case 3:
1.240 + r2 = MP_DIGIT(b,2);
1.241 + case 2:
1.242 + r1 = MP_DIGIT(b,1);
1.243 + case 1:
1.244 + r0 = MP_DIGIT(b,0);
1.245 + }
1.246 +
1.247 +#ifndef MPI_AMD64_ADD
1.248 + MP_ADD_CARRY(a0, r0, r0, 0, carry);
1.249 + MP_ADD_CARRY(a1, r1, r1, carry, carry);
1.250 + MP_ADD_CARRY(a2, r2, r2, carry, carry);
1.251 +#else
1.252 + __asm__ (
1.253 + "xorq %3,%3 \n\t"
1.254 + "addq %4,%0 \n\t"
1.255 + "adcq %5,%1 \n\t"
1.256 + "adcq %6,%2 \n\t"
1.257 + "adcq $0,%3 \n\t"
1.258 + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
1.259 + : "r" (a0), "r" (a1), "r" (a2),
1.260 + "0" (r0), "1" (r1), "2" (r2)
1.261 + : "%cc" );
1.262 +#endif
1.263 +
1.264 + MP_CHECKOK(s_mp_pad(r, 3));
1.265 + MP_DIGIT(r, 2) = r2;
1.266 + MP_DIGIT(r, 1) = r1;
1.267 + MP_DIGIT(r, 0) = r0;
1.268 + MP_SIGN(r) = MP_ZPOS;
1.269 + MP_USED(r) = 3;
1.270 +
1.271 + /* Do quick 'subract' if we've gone over
1.272 + * (add the 2's complement of the curve field) */
1.273 + a2 = MP_DIGIT(&meth->irr,2);
1.274 + if (carry || r2 > a2 ||
1.275 + ((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) {
1.276 + a1 = MP_DIGIT(&meth->irr,1);
1.277 + a0 = MP_DIGIT(&meth->irr,0);
1.278 +#ifndef MPI_AMD64_ADD
1.279 + MP_SUB_BORROW(r0, a0, r0, 0, carry);
1.280 + MP_SUB_BORROW(r1, a1, r1, carry, carry);
1.281 + MP_SUB_BORROW(r2, a2, r2, carry, carry);
1.282 +#else
1.283 + __asm__ (
1.284 + "subq %3,%0 \n\t"
1.285 + "sbbq %4,%1 \n\t"
1.286 + "sbbq %5,%2 \n\t"
1.287 + : "=r"(r0), "=r"(r1), "=r"(r2)
1.288 + : "r" (a0), "r" (a1), "r" (a2),
1.289 + "0" (r0), "1" (r1), "2" (r2)
1.290 + : "%cc" );
1.291 +#endif
1.292 + MP_DIGIT(r, 2) = r2;
1.293 + MP_DIGIT(r, 1) = r1;
1.294 + MP_DIGIT(r, 0) = r0;
1.295 + }
1.296 +
1.297 + s_mp_clamp(r);
1.298 +
1.299 + CLEANUP:
1.300 + return res;
1.301 +}
1.302 +
1.303 +/* 4 words */
1.304 +mp_err
1.305 +ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
1.306 + const GFMethod *meth)
1.307 +{
1.308 + mp_err res = MP_OKAY;
1.309 + mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
1.310 + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
1.311 + mp_digit carry;
1.312 +
1.313 + switch(MP_USED(a)) {
1.314 + case 4:
1.315 + a3 = MP_DIGIT(a,3);
1.316 + case 3:
1.317 + a2 = MP_DIGIT(a,2);
1.318 + case 2:
1.319 + a1 = MP_DIGIT(a,1);
1.320 + case 1:
1.321 + a0 = MP_DIGIT(a,0);
1.322 + }
1.323 + switch(MP_USED(b)) {
1.324 + case 4:
1.325 + r3 = MP_DIGIT(b,3);
1.326 + case 3:
1.327 + r2 = MP_DIGIT(b,2);
1.328 + case 2:
1.329 + r1 = MP_DIGIT(b,1);
1.330 + case 1:
1.331 + r0 = MP_DIGIT(b,0);
1.332 + }
1.333 +
1.334 +#ifndef MPI_AMD64_ADD
1.335 + MP_ADD_CARRY(a0, r0, r0, 0, carry);
1.336 + MP_ADD_CARRY(a1, r1, r1, carry, carry);
1.337 + MP_ADD_CARRY(a2, r2, r2, carry, carry);
1.338 + MP_ADD_CARRY(a3, r3, r3, carry, carry);
1.339 +#else
1.340 + __asm__ (
1.341 + "xorq %4,%4 \n\t"
1.342 + "addq %5,%0 \n\t"
1.343 + "adcq %6,%1 \n\t"
1.344 + "adcq %7,%2 \n\t"
1.345 + "adcq %8,%3 \n\t"
1.346 + "adcq $0,%4 \n\t"
1.347 + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
1.348 + : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
1.349 + "0" (r0), "1" (r1), "2" (r2), "3" (r3)
1.350 + : "%cc" );
1.351 +#endif
1.352 +
1.353 + MP_CHECKOK(s_mp_pad(r, 4));
1.354 + MP_DIGIT(r, 3) = r3;
1.355 + MP_DIGIT(r, 2) = r2;
1.356 + MP_DIGIT(r, 1) = r1;
1.357 + MP_DIGIT(r, 0) = r0;
1.358 + MP_SIGN(r) = MP_ZPOS;
1.359 + MP_USED(r) = 4;
1.360 +
1.361 + /* Do quick 'subract' if we've gone over
1.362 + * (add the 2's complement of the curve field) */
1.363 + a3 = MP_DIGIT(&meth->irr,3);
1.364 + if (carry || r3 > a3 ||
1.365 + ((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) {
1.366 + a2 = MP_DIGIT(&meth->irr,2);
1.367 + a1 = MP_DIGIT(&meth->irr,1);
1.368 + a0 = MP_DIGIT(&meth->irr,0);
1.369 +#ifndef MPI_AMD64_ADD
1.370 + MP_SUB_BORROW(r0, a0, r0, 0, carry);
1.371 + MP_SUB_BORROW(r1, a1, r1, carry, carry);
1.372 + MP_SUB_BORROW(r2, a2, r2, carry, carry);
1.373 + MP_SUB_BORROW(r3, a3, r3, carry, carry);
1.374 +#else
1.375 + __asm__ (
1.376 + "subq %4,%0 \n\t"
1.377 + "sbbq %5,%1 \n\t"
1.378 + "sbbq %6,%2 \n\t"
1.379 + "sbbq %7,%3 \n\t"
1.380 + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
1.381 + : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
1.382 + "0" (r0), "1" (r1), "2" (r2), "3" (r3)
1.383 + : "%cc" );
1.384 +#endif
1.385 + MP_DIGIT(r, 3) = r3;
1.386 + MP_DIGIT(r, 2) = r2;
1.387 + MP_DIGIT(r, 1) = r1;
1.388 + MP_DIGIT(r, 0) = r0;
1.389 + }
1.390 +
1.391 + s_mp_clamp(r);
1.392 +
1.393 + CLEANUP:
1.394 + return res;
1.395 +}
1.396 +
1.397 +/* 5 words */
1.398 +mp_err
1.399 +ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
1.400 + const GFMethod *meth)
1.401 +{
1.402 + mp_err res = MP_OKAY;
1.403 + mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
1.404 + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
1.405 + mp_digit carry;
1.406 +
1.407 + switch(MP_USED(a)) {
1.408 + case 5:
1.409 + a4 = MP_DIGIT(a,4);
1.410 + case 4:
1.411 + a3 = MP_DIGIT(a,3);
1.412 + case 3:
1.413 + a2 = MP_DIGIT(a,2);
1.414 + case 2:
1.415 + a1 = MP_DIGIT(a,1);
1.416 + case 1:
1.417 + a0 = MP_DIGIT(a,0);
1.418 + }
1.419 + switch(MP_USED(b)) {
1.420 + case 5:
1.421 + r4 = MP_DIGIT(b,4);
1.422 + case 4:
1.423 + r3 = MP_DIGIT(b,3);
1.424 + case 3:
1.425 + r2 = MP_DIGIT(b,2);
1.426 + case 2:
1.427 + r1 = MP_DIGIT(b,1);
1.428 + case 1:
1.429 + r0 = MP_DIGIT(b,0);
1.430 + }
1.431 +
1.432 + MP_ADD_CARRY(a0, r0, r0, 0, carry);
1.433 + MP_ADD_CARRY(a1, r1, r1, carry, carry);
1.434 + MP_ADD_CARRY(a2, r2, r2, carry, carry);
1.435 + MP_ADD_CARRY(a3, r3, r3, carry, carry);
1.436 + MP_ADD_CARRY(a4, r4, r4, carry, carry);
1.437 +
1.438 + MP_CHECKOK(s_mp_pad(r, 5));
1.439 + MP_DIGIT(r, 4) = r4;
1.440 + MP_DIGIT(r, 3) = r3;
1.441 + MP_DIGIT(r, 2) = r2;
1.442 + MP_DIGIT(r, 1) = r1;
1.443 + MP_DIGIT(r, 0) = r0;
1.444 + MP_SIGN(r) = MP_ZPOS;
1.445 + MP_USED(r) = 5;
1.446 +
1.447 + /* Do quick 'subract' if we've gone over
1.448 + * (add the 2's complement of the curve field) */
1.449 + a4 = MP_DIGIT(&meth->irr,4);
1.450 + if (carry || r4 > a4 ||
1.451 + ((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) {
1.452 + a3 = MP_DIGIT(&meth->irr,3);
1.453 + a2 = MP_DIGIT(&meth->irr,2);
1.454 + a1 = MP_DIGIT(&meth->irr,1);
1.455 + a0 = MP_DIGIT(&meth->irr,0);
1.456 + MP_SUB_BORROW(r0, a0, r0, 0, carry);
1.457 + MP_SUB_BORROW(r1, a1, r1, carry, carry);
1.458 + MP_SUB_BORROW(r2, a2, r2, carry, carry);
1.459 + MP_SUB_BORROW(r3, a3, r3, carry, carry);
1.460 + MP_SUB_BORROW(r4, a4, r4, carry, carry);
1.461 + MP_DIGIT(r, 4) = r4;
1.462 + MP_DIGIT(r, 3) = r3;
1.463 + MP_DIGIT(r, 2) = r2;
1.464 + MP_DIGIT(r, 1) = r1;
1.465 + MP_DIGIT(r, 0) = r0;
1.466 + }
1.467 +
1.468 + s_mp_clamp(r);
1.469 +
1.470 + CLEANUP:
1.471 + return res;
1.472 +}
1.473 +
1.474 +/* 6 words */
1.475 +mp_err
1.476 +ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
1.477 + const GFMethod *meth)
1.478 +{
1.479 + mp_err res = MP_OKAY;
1.480 + mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
1.481 + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
1.482 + mp_digit carry;
1.483 +
1.484 + switch(MP_USED(a)) {
1.485 + case 6:
1.486 + a5 = MP_DIGIT(a,5);
1.487 + case 5:
1.488 + a4 = MP_DIGIT(a,4);
1.489 + case 4:
1.490 + a3 = MP_DIGIT(a,3);
1.491 + case 3:
1.492 + a2 = MP_DIGIT(a,2);
1.493 + case 2:
1.494 + a1 = MP_DIGIT(a,1);
1.495 + case 1:
1.496 + a0 = MP_DIGIT(a,0);
1.497 + }
1.498 + switch(MP_USED(b)) {
1.499 + case 6:
1.500 + r5 = MP_DIGIT(b,5);
1.501 + case 5:
1.502 + r4 = MP_DIGIT(b,4);
1.503 + case 4:
1.504 + r3 = MP_DIGIT(b,3);
1.505 + case 3:
1.506 + r2 = MP_DIGIT(b,2);
1.507 + case 2:
1.508 + r1 = MP_DIGIT(b,1);
1.509 + case 1:
1.510 + r0 = MP_DIGIT(b,0);
1.511 + }
1.512 +
1.513 + MP_ADD_CARRY(a0, r0, r0, 0, carry);
1.514 + MP_ADD_CARRY(a1, r1, r1, carry, carry);
1.515 + MP_ADD_CARRY(a2, r2, r2, carry, carry);
1.516 + MP_ADD_CARRY(a3, r3, r3, carry, carry);
1.517 + MP_ADD_CARRY(a4, r4, r4, carry, carry);
1.518 + MP_ADD_CARRY(a5, r5, r5, carry, carry);
1.519 +
1.520 + MP_CHECKOK(s_mp_pad(r, 6));
1.521 + MP_DIGIT(r, 5) = r5;
1.522 + MP_DIGIT(r, 4) = r4;
1.523 + MP_DIGIT(r, 3) = r3;
1.524 + MP_DIGIT(r, 2) = r2;
1.525 + MP_DIGIT(r, 1) = r1;
1.526 + MP_DIGIT(r, 0) = r0;
1.527 + MP_SIGN(r) = MP_ZPOS;
1.528 + MP_USED(r) = 6;
1.529 +
1.530 + /* Do quick 'subract' if we've gone over
1.531 + * (add the 2's complement of the curve field) */
1.532 + a5 = MP_DIGIT(&meth->irr,5);
1.533 + if (carry || r5 > a5 ||
1.534 + ((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) {
1.535 + a4 = MP_DIGIT(&meth->irr,4);
1.536 + a3 = MP_DIGIT(&meth->irr,3);
1.537 + a2 = MP_DIGIT(&meth->irr,2);
1.538 + a1 = MP_DIGIT(&meth->irr,1);
1.539 + a0 = MP_DIGIT(&meth->irr,0);
1.540 + MP_SUB_BORROW(r0, a0, r0, 0, carry);
1.541 + MP_SUB_BORROW(r1, a1, r1, carry, carry);
1.542 + MP_SUB_BORROW(r2, a2, r2, carry, carry);
1.543 + MP_SUB_BORROW(r3, a3, r3, carry, carry);
1.544 + MP_SUB_BORROW(r4, a4, r4, carry, carry);
1.545 + MP_SUB_BORROW(r5, a5, r5, carry, carry);
1.546 + MP_DIGIT(r, 5) = r5;
1.547 + MP_DIGIT(r, 4) = r4;
1.548 + MP_DIGIT(r, 3) = r3;
1.549 + MP_DIGIT(r, 2) = r2;
1.550 + MP_DIGIT(r, 1) = r1;
1.551 + MP_DIGIT(r, 0) = r0;
1.552 + }
1.553 +
1.554 + s_mp_clamp(r);
1.555 +
1.556 + CLEANUP:
1.557 + return res;
1.558 +}
1.559 +
1.560 +/*
1.561 + * The following subraction functions do in-line subractions based
1.562 + * on our curve size.
1.563 + *
1.564 + * ... 3 words
1.565 + */
1.566 +mp_err
1.567 +ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
1.568 + const GFMethod *meth)
1.569 +{
1.570 + mp_err res = MP_OKAY;
1.571 + mp_digit b0 = 0, b1 = 0, b2 = 0;
1.572 + mp_digit r0 = 0, r1 = 0, r2 = 0;
1.573 + mp_digit borrow;
1.574 +
1.575 + switch(MP_USED(a)) {
1.576 + case 3:
1.577 + r2 = MP_DIGIT(a,2);
1.578 + case 2:
1.579 + r1 = MP_DIGIT(a,1);
1.580 + case 1:
1.581 + r0 = MP_DIGIT(a,0);
1.582 + }
1.583 + switch(MP_USED(b)) {
1.584 + case 3:
1.585 + b2 = MP_DIGIT(b,2);
1.586 + case 2:
1.587 + b1 = MP_DIGIT(b,1);
1.588 + case 1:
1.589 + b0 = MP_DIGIT(b,0);
1.590 + }
1.591 +
1.592 +#ifndef MPI_AMD64_ADD
1.593 + MP_SUB_BORROW(r0, b0, r0, 0, borrow);
1.594 + MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
1.595 + MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
1.596 +#else
1.597 + __asm__ (
1.598 + "xorq %3,%3 \n\t"
1.599 + "subq %4,%0 \n\t"
1.600 + "sbbq %5,%1 \n\t"
1.601 + "sbbq %6,%2 \n\t"
1.602 + "adcq $0,%3 \n\t"
1.603 + : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow)
1.604 + : "r" (b0), "r" (b1), "r" (b2),
1.605 + "0" (r0), "1" (r1), "2" (r2)
1.606 + : "%cc" );
1.607 +#endif
1.608 +
1.609 + /* Do quick 'add' if we've gone under 0
1.610 + * (subtract the 2's complement of the curve field) */
1.611 + if (borrow) {
1.612 + b2 = MP_DIGIT(&meth->irr,2);
1.613 + b1 = MP_DIGIT(&meth->irr,1);
1.614 + b0 = MP_DIGIT(&meth->irr,0);
1.615 +#ifndef MPI_AMD64_ADD
1.616 + MP_ADD_CARRY(b0, r0, r0, 0, borrow);
1.617 + MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
1.618 + MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
1.619 +#else
1.620 + __asm__ (
1.621 + "addq %3,%0 \n\t"
1.622 + "adcq %4,%1 \n\t"
1.623 + "adcq %5,%2 \n\t"
1.624 + : "=r"(r0), "=r"(r1), "=r"(r2)
1.625 + : "r" (b0), "r" (b1), "r" (b2),
1.626 + "0" (r0), "1" (r1), "2" (r2)
1.627 + : "%cc" );
1.628 +#endif
1.629 + }
1.630 +
1.631 +#ifdef MPI_AMD64_ADD
1.632 + /* compiler fakeout? */
1.633 + if ((r2 == b0) && (r1 == b0) && (r0 == b0)) {
1.634 + MP_CHECKOK(s_mp_pad(r, 4));
1.635 + }
1.636 +#endif
1.637 + MP_CHECKOK(s_mp_pad(r, 3));
1.638 + MP_DIGIT(r, 2) = r2;
1.639 + MP_DIGIT(r, 1) = r1;
1.640 + MP_DIGIT(r, 0) = r0;
1.641 + MP_SIGN(r) = MP_ZPOS;
1.642 + MP_USED(r) = 3;
1.643 + s_mp_clamp(r);
1.644 +
1.645 + CLEANUP:
1.646 + return res;
1.647 +}
1.648 +
1.649 +/* 4 words */
1.650 +mp_err
1.651 +ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
1.652 + const GFMethod *meth)
1.653 +{
1.654 + mp_err res = MP_OKAY;
1.655 + mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
1.656 + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
1.657 + mp_digit borrow;
1.658 +
1.659 + switch(MP_USED(a)) {
1.660 + case 4:
1.661 + r3 = MP_DIGIT(a,3);
1.662 + case 3:
1.663 + r2 = MP_DIGIT(a,2);
1.664 + case 2:
1.665 + r1 = MP_DIGIT(a,1);
1.666 + case 1:
1.667 + r0 = MP_DIGIT(a,0);
1.668 + }
1.669 + switch(MP_USED(b)) {
1.670 + case 4:
1.671 + b3 = MP_DIGIT(b,3);
1.672 + case 3:
1.673 + b2 = MP_DIGIT(b,2);
1.674 + case 2:
1.675 + b1 = MP_DIGIT(b,1);
1.676 + case 1:
1.677 + b0 = MP_DIGIT(b,0);
1.678 + }
1.679 +
1.680 +#ifndef MPI_AMD64_ADD
1.681 + MP_SUB_BORROW(r0, b0, r0, 0, borrow);
1.682 + MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
1.683 + MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
1.684 + MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
1.685 +#else
1.686 + __asm__ (
1.687 + "xorq %4,%4 \n\t"
1.688 + "subq %5,%0 \n\t"
1.689 + "sbbq %6,%1 \n\t"
1.690 + "sbbq %7,%2 \n\t"
1.691 + "sbbq %8,%3 \n\t"
1.692 + "adcq $0,%4 \n\t"
1.693 + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow)
1.694 + : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
1.695 + "0" (r0), "1" (r1), "2" (r2), "3" (r3)
1.696 + : "%cc" );
1.697 +#endif
1.698 +
1.699 + /* Do quick 'add' if we've gone under 0
1.700 + * (subtract the 2's complement of the curve field) */
1.701 + if (borrow) {
1.702 + b3 = MP_DIGIT(&meth->irr,3);
1.703 + b2 = MP_DIGIT(&meth->irr,2);
1.704 + b1 = MP_DIGIT(&meth->irr,1);
1.705 + b0 = MP_DIGIT(&meth->irr,0);
1.706 +#ifndef MPI_AMD64_ADD
1.707 + MP_ADD_CARRY(b0, r0, r0, 0, borrow);
1.708 + MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
1.709 + MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
1.710 + MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
1.711 +#else
1.712 + __asm__ (
1.713 + "addq %4,%0 \n\t"
1.714 + "adcq %5,%1 \n\t"
1.715 + "adcq %6,%2 \n\t"
1.716 + "adcq %7,%3 \n\t"
1.717 + : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
1.718 + : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
1.719 + "0" (r0), "1" (r1), "2" (r2), "3" (r3)
1.720 + : "%cc" );
1.721 +#endif
1.722 + }
1.723 +#ifdef MPI_AMD64_ADD
1.724 + /* compiler fakeout? */
1.725 + if ((r3 == b0) && (r1 == b0) && (r0 == b0)) {
1.726 + MP_CHECKOK(s_mp_pad(r, 4));
1.727 + }
1.728 +#endif
1.729 + MP_CHECKOK(s_mp_pad(r, 4));
1.730 + MP_DIGIT(r, 3) = r3;
1.731 + MP_DIGIT(r, 2) = r2;
1.732 + MP_DIGIT(r, 1) = r1;
1.733 + MP_DIGIT(r, 0) = r0;
1.734 + MP_SIGN(r) = MP_ZPOS;
1.735 + MP_USED(r) = 4;
1.736 + s_mp_clamp(r);
1.737 +
1.738 + CLEANUP:
1.739 + return res;
1.740 +}
1.741 +
1.742 +/* 5 words */
1.743 +mp_err
1.744 +ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
1.745 + const GFMethod *meth)
1.746 +{
1.747 + mp_err res = MP_OKAY;
1.748 + mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
1.749 + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
1.750 + mp_digit borrow;
1.751 +
1.752 + switch(MP_USED(a)) {
1.753 + case 5:
1.754 + r4 = MP_DIGIT(a,4);
1.755 + case 4:
1.756 + r3 = MP_DIGIT(a,3);
1.757 + case 3:
1.758 + r2 = MP_DIGIT(a,2);
1.759 + case 2:
1.760 + r1 = MP_DIGIT(a,1);
1.761 + case 1:
1.762 + r0 = MP_DIGIT(a,0);
1.763 + }
1.764 + switch(MP_USED(b)) {
1.765 + case 5:
1.766 + b4 = MP_DIGIT(b,4);
1.767 + case 4:
1.768 + b3 = MP_DIGIT(b,3);
1.769 + case 3:
1.770 + b2 = MP_DIGIT(b,2);
1.771 + case 2:
1.772 + b1 = MP_DIGIT(b,1);
1.773 + case 1:
1.774 + b0 = MP_DIGIT(b,0);
1.775 + }
1.776 +
1.777 + MP_SUB_BORROW(r0, b0, r0, 0, borrow);
1.778 + MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
1.779 + MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
1.780 + MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
1.781 + MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
1.782 +
1.783 + /* Do quick 'add' if we've gone under 0
1.784 + * (subtract the 2's complement of the curve field) */
1.785 + if (borrow) {
1.786 + b4 = MP_DIGIT(&meth->irr,4);
1.787 + b3 = MP_DIGIT(&meth->irr,3);
1.788 + b2 = MP_DIGIT(&meth->irr,2);
1.789 + b1 = MP_DIGIT(&meth->irr,1);
1.790 + b0 = MP_DIGIT(&meth->irr,0);
1.791 + MP_ADD_CARRY(b0, r0, r0, 0, borrow);
1.792 + MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
1.793 + MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
1.794 + MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
1.795 + }
1.796 + MP_CHECKOK(s_mp_pad(r, 5));
1.797 + MP_DIGIT(r, 4) = r4;
1.798 + MP_DIGIT(r, 3) = r3;
1.799 + MP_DIGIT(r, 2) = r2;
1.800 + MP_DIGIT(r, 1) = r1;
1.801 + MP_DIGIT(r, 0) = r0;
1.802 + MP_SIGN(r) = MP_ZPOS;
1.803 + MP_USED(r) = 5;
1.804 + s_mp_clamp(r);
1.805 +
1.806 + CLEANUP:
1.807 + return res;
1.808 +}
1.809 +
1.810 +/* 6 words */
1.811 +mp_err
1.812 +ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
1.813 + const GFMethod *meth)
1.814 +{
1.815 + mp_err res = MP_OKAY;
1.816 + mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
1.817 + mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
1.818 + mp_digit borrow;
1.819 +
1.820 + switch(MP_USED(a)) {
1.821 + case 6:
1.822 + r5 = MP_DIGIT(a,5);
1.823 + case 5:
1.824 + r4 = MP_DIGIT(a,4);
1.825 + case 4:
1.826 + r3 = MP_DIGIT(a,3);
1.827 + case 3:
1.828 + r2 = MP_DIGIT(a,2);
1.829 + case 2:
1.830 + r1 = MP_DIGIT(a,1);
1.831 + case 1:
1.832 + r0 = MP_DIGIT(a,0);
1.833 + }
1.834 + switch(MP_USED(b)) {
1.835 + case 6:
1.836 + b5 = MP_DIGIT(b,5);
1.837 + case 5:
1.838 + b4 = MP_DIGIT(b,4);
1.839 + case 4:
1.840 + b3 = MP_DIGIT(b,3);
1.841 + case 3:
1.842 + b2 = MP_DIGIT(b,2);
1.843 + case 2:
1.844 + b1 = MP_DIGIT(b,1);
1.845 + case 1:
1.846 + b0 = MP_DIGIT(b,0);
1.847 + }
1.848 +
1.849 + MP_SUB_BORROW(r0, b0, r0, 0, borrow);
1.850 + MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
1.851 + MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
1.852 + MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
1.853 + MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
1.854 + MP_SUB_BORROW(r5, b5, r5, borrow, borrow);
1.855 +
1.856 + /* Do quick 'add' if we've gone under 0
1.857 + * (subtract the 2's complement of the curve field) */
1.858 + if (borrow) {
1.859 + b5 = MP_DIGIT(&meth->irr,5);
1.860 + b4 = MP_DIGIT(&meth->irr,4);
1.861 + b3 = MP_DIGIT(&meth->irr,3);
1.862 + b2 = MP_DIGIT(&meth->irr,2);
1.863 + b1 = MP_DIGIT(&meth->irr,1);
1.864 + b0 = MP_DIGIT(&meth->irr,0);
1.865 + MP_ADD_CARRY(b0, r0, r0, 0, borrow);
1.866 + MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
1.867 + MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
1.868 + MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
1.869 + MP_ADD_CARRY(b4, r4, r4, borrow, borrow);
1.870 + }
1.871 +
1.872 + MP_CHECKOK(s_mp_pad(r, 6));
1.873 + MP_DIGIT(r, 5) = r5;
1.874 + MP_DIGIT(r, 4) = r4;
1.875 + MP_DIGIT(r, 3) = r3;
1.876 + MP_DIGIT(r, 2) = r2;
1.877 + MP_DIGIT(r, 1) = r1;
1.878 + MP_DIGIT(r, 0) = r0;
1.879 + MP_SIGN(r) = MP_ZPOS;
1.880 + MP_USED(r) = 6;
1.881 + s_mp_clamp(r);
1.882 +
1.883 + CLEANUP:
1.884 + return res;
1.885 +}
1.886 +
1.887 +
1.888 +/* Reduces an integer to a field element. */
1.889 +mp_err
1.890 +ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
1.891 +{
1.892 + return mp_mod(a, &meth->irr, r);
1.893 +}
1.894 +
1.895 +/* Multiplies two field elements. */
1.896 +mp_err
1.897 +ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
1.898 + const GFMethod *meth)
1.899 +{
1.900 + return mp_mulmod(a, b, &meth->irr, r);
1.901 +}
1.902 +
1.903 +/* Squares a field element. */
1.904 +mp_err
1.905 +ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1.906 +{
1.907 + return mp_sqrmod(a, &meth->irr, r);
1.908 +}
1.909 +
1.910 +/* Divides two field elements. If a is NULL, then returns the inverse of
1.911 + * b. */
1.912 +mp_err
1.913 +ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
1.914 + const GFMethod *meth)
1.915 +{
1.916 + mp_err res = MP_OKAY;
1.917 + mp_int t;
1.918 +
1.919 + /* If a is NULL, then return the inverse of b, otherwise return a/b. */
1.920 + if (a == NULL) {
1.921 + return mp_invmod(b, &meth->irr, r);
1.922 + } else {
1.923 + /* MPI doesn't support divmod, so we implement it using invmod and
1.924 + * mulmod. */
1.925 + MP_CHECKOK(mp_init(&t));
1.926 + MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
1.927 + MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
1.928 + CLEANUP:
1.929 + mp_clear(&t);
1.930 + return res;
1.931 + }
1.932 +}
1.933 +
1.934 +/* Wrapper functions for generic binary polynomial field arithmetic. */
1.935 +
1.936 +/* Adds two field elements. */
1.937 +mp_err
1.938 +ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
1.939 + const GFMethod *meth)
1.940 +{
1.941 + return mp_badd(a, b, r);
1.942 +}
1.943 +
1.944 +/* Negates a field element. Note that for binary polynomial fields, the
1.945 + * negation of a field element is the field element itself. */
1.946 +mp_err
1.947 +ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
1.948 +{
1.949 + if (a == r) {
1.950 + return MP_OKAY;
1.951 + } else {
1.952 + return mp_copy(a, r);
1.953 + }
1.954 +}
1.955 +
1.956 +/* Reduces a binary polynomial to a field element. */
1.957 +mp_err
1.958 +ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
1.959 +{
1.960 + return mp_bmod(a, meth->irr_arr, r);
1.961 +}
1.962 +
1.963 +/* Multiplies two field elements. */
1.964 +mp_err
1.965 +ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
1.966 + const GFMethod *meth)
1.967 +{
1.968 + return mp_bmulmod(a, b, meth->irr_arr, r);
1.969 +}
1.970 +
1.971 +/* Squares a field element. */
1.972 +mp_err
1.973 +ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1.974 +{
1.975 + return mp_bsqrmod(a, meth->irr_arr, r);
1.976 +}
1.977 +
1.978 +/* Divides two field elements. If a is NULL, then returns the inverse of
1.979 + * b. */
1.980 +mp_err
1.981 +ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
1.982 + const GFMethod *meth)
1.983 +{
1.984 + mp_err res = MP_OKAY;
1.985 + mp_int t;
1.986 +
1.987 + /* If a is NULL, then return the inverse of b, otherwise return a/b. */
1.988 + if (a == NULL) {
1.989 + /* The GF(2^m) portion of MPI doesn't support invmod, so we
1.990 + * compute 1/b. */
1.991 + MP_CHECKOK(mp_init(&t));
1.992 + MP_CHECKOK(mp_set_int(&t, 1));
1.993 + MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
1.994 + CLEANUP:
1.995 + mp_clear(&t);
1.996 + return res;
1.997 + } else {
1.998 + return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
1.999 + }
1.1000 +}
