1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/ecl/ecp_521.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,137 @@
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 "mpi.h"
1.10 +#include "mplogic.h"
1.11 +#include "mpi-priv.h"
1.12 +
1.13 +#define ECP521_DIGITS ECL_CURVE_DIGITS(521)
1.14 +
1.15 +/* Fast modular reduction for p521 = 2^521 - 1. a can be r. Uses
1.16 + * algorithm 2.31 from Hankerson, Menezes, Vanstone. Guide to
1.17 + * Elliptic Curve Cryptography. */
1.18 +static mp_err
1.19 +ec_GFp_nistp521_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
1.20 +{
1.21 + mp_err res = MP_OKAY;
1.22 + int a_bits = mpl_significant_bits(a);
1.23 + int i;
1.24 +
1.25 + /* m1, m2 are statically-allocated mp_int of exactly the size we need */
1.26 + mp_int m1;
1.27 +
1.28 + mp_digit s1[ECP521_DIGITS] = { 0 };
1.29 +
1.30 + MP_SIGN(&m1) = MP_ZPOS;
1.31 + MP_ALLOC(&m1) = ECP521_DIGITS;
1.32 + MP_USED(&m1) = ECP521_DIGITS;
1.33 + MP_DIGITS(&m1) = s1;
1.34 +
1.35 + if (a_bits < 521) {
1.36 + if (a==r) return MP_OKAY;
1.37 + return mp_copy(a, r);
1.38 + }
1.39 + /* for polynomials larger than twice the field size or polynomials
1.40 + * not using all words, use regular reduction */
1.41 + if (a_bits > (521*2)) {
1.42 + MP_CHECKOK(mp_mod(a, &meth->irr, r));
1.43 + } else {
1.44 +#define FIRST_DIGIT (ECP521_DIGITS-1)
1.45 + for (i = FIRST_DIGIT; i < MP_USED(a)-1; i++) {
1.46 + s1[i-FIRST_DIGIT] = (MP_DIGIT(a, i) >> 9)
1.47 + | (MP_DIGIT(a, 1+i) << (MP_DIGIT_BIT-9));
1.48 + }
1.49 + s1[i-FIRST_DIGIT] = MP_DIGIT(a, i) >> 9;
1.50 +
1.51 + if ( a != r ) {
1.52 + MP_CHECKOK(s_mp_pad(r,ECP521_DIGITS));
1.53 + for (i = 0; i < ECP521_DIGITS; i++) {
1.54 + MP_DIGIT(r,i) = MP_DIGIT(a, i);
1.55 + }
1.56 + }
1.57 + MP_USED(r) = ECP521_DIGITS;
1.58 + MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF;
1.59 +
1.60 + MP_CHECKOK(s_mp_add(r, &m1));
1.61 + if (MP_DIGIT(r, FIRST_DIGIT) & 0x200) {
1.62 + MP_CHECKOK(s_mp_add_d(r,1));
1.63 + MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF;
1.64 + } else if (s_mp_cmp(r, &meth->irr) == 0) {
1.65 + mp_zero(r);
1.66 + }
1.67 + s_mp_clamp(r);
1.68 + }
1.69 +
1.70 + CLEANUP:
1.71 + return res;
1.72 +}
1.73 +
1.74 +/* Compute the square of polynomial a, reduce modulo p521. Store the
1.75 + * result in r. r could be a. Uses optimized modular reduction for p521.
1.76 + */
1.77 +static mp_err
1.78 +ec_GFp_nistp521_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1.79 +{
1.80 + mp_err res = MP_OKAY;
1.81 +
1.82 + MP_CHECKOK(mp_sqr(a, r));
1.83 + MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
1.84 + CLEANUP:
1.85 + return res;
1.86 +}
1.87 +
1.88 +/* Compute the product of two polynomials a and b, reduce modulo p521.
1.89 + * Store the result in r. r could be a or b; a could be b. Uses
1.90 + * optimized modular reduction for p521. */
1.91 +static mp_err
1.92 +ec_GFp_nistp521_mul(const mp_int *a, const mp_int *b, mp_int *r,
1.93 + const GFMethod *meth)
1.94 +{
1.95 + mp_err res = MP_OKAY;
1.96 +
1.97 + MP_CHECKOK(mp_mul(a, b, r));
1.98 + MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
1.99 + CLEANUP:
1.100 + return res;
1.101 +}
1.102 +
1.103 +/* Divides two field elements. If a is NULL, then returns the inverse of
1.104 + * b. */
1.105 +static mp_err
1.106 +ec_GFp_nistp521_div(const mp_int *a, const mp_int *b, mp_int *r,
1.107 + const GFMethod *meth)
1.108 +{
1.109 + mp_err res = MP_OKAY;
1.110 + mp_int t;
1.111 +
1.112 + /* If a is NULL, then return the inverse of b, otherwise return a/b. */
1.113 + if (a == NULL) {
1.114 + return mp_invmod(b, &meth->irr, r);
1.115 + } else {
1.116 + /* MPI doesn't support divmod, so we implement it using invmod and
1.117 + * mulmod. */
1.118 + MP_CHECKOK(mp_init(&t));
1.119 + MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
1.120 + MP_CHECKOK(mp_mul(a, &t, r));
1.121 + MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
1.122 + CLEANUP:
1.123 + mp_clear(&t);
1.124 + return res;
1.125 + }
1.126 +}
1.127 +
1.128 +/* Wire in fast field arithmetic and precomputation of base point for
1.129 + * named curves. */
1.130 +mp_err
1.131 +ec_group_set_gfp521(ECGroup *group, ECCurveName name)
1.132 +{
1.133 + if (name == ECCurve_NIST_P521) {
1.134 + group->meth->field_mod = &ec_GFp_nistp521_mod;
1.135 + group->meth->field_mul = &ec_GFp_nistp521_mul;
1.136 + group->meth->field_sqr = &ec_GFp_nistp521_sqr;
1.137 + group->meth->field_div = &ec_GFp_nistp521_div;
1.138 + }
1.139 + return MP_OKAY;
1.140 +}
