security/nss/lib/freebl/ecl/ecp_mont.c

   1 /*
   2  * ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is the elliptic curve math library.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Sun Microsystems, Inc.
  19  * Portions created by the Initial Developer are Copyright (C) 2003
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 /* Uses Montgomery reduction for field arithmetic.  See mpi/mpmontg.c for
  40  * code implementation. */
  41
  42 #include "mpi.h"
  43 #include "mplogic.h"
  44 #include "mpi-priv.h"
  45 #include "ecl-priv.h"
  46 #include "ecp.h"
  47 #include <stdlib.h>
  48 #include <stdio.h>
  49
  50 /* Construct a generic GFMethod for arithmetic over prime fields with
  51  * irreducible irr. */
  52 GFMethod *
  53 GFMethod_consGFp_mont(const mp_int *irr)
  54 {
  55         mp_err res = MP_OKAY;
  56         int i;
  57         GFMethod *meth = NULL;
  58         mp_mont_modulus *mmm;
  59
  60         meth = GFMethod_consGFp(irr);
  61         if (meth == NULL)
  62                 return NULL;
  63
  64         mmm = (mp_mont_modulus *) malloc(sizeof(mp_mont_modulus));
  65         if (mmm == NULL) {
  66                 res = MP_MEM;
  67                 goto CLEANUP;
  68         }
  69
  70         meth->field_mul = &ec_GFp_mul_mont;
  71         meth->field_sqr = &ec_GFp_sqr_mont;
  72         meth->field_div = &ec_GFp_div_mont;
  73         meth->field_enc = &ec_GFp_enc_mont;
  74         meth->field_dec = &ec_GFp_dec_mont;
  75         meth->extra1 = mmm;
  76         meth->extra2 = NULL;
  77         meth->extra_free = &ec_GFp_extra_free_mont;
  78
  79         mmm->N = meth->irr;
  80         i = mpl_significant_bits(&meth->irr);
  81         i += MP_DIGIT_BIT - 1;
  82         mmm->b = i - i % MP_DIGIT_BIT;
  83         mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0));
  84
  85   CLEANUP:
  86         if (res != MP_OKAY) {
  87                 GFMethod_free(meth);
  88                 return NULL;
  89         }
  90         return meth;
  91 }
  92
  93 /* Wrapper functions for generic prime field arithmetic. */
  94
  95 /* Field multiplication using Montgomery reduction. */
  96 mp_err
  97 ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
  98                                 const GFMethod *meth)
  99 {
 100         mp_err res = MP_OKAY;
 101
 102 #ifdef MP_MONT_USE_MP_MUL
 103         /* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont
 104          * is not implemented and we have to use mp_mul and s_mp_redc directly
 105          */
 106         MP_CHECKOK(mp_mul(a, b, r));
 107         MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
 108 #else
 109         mp_int s;
 110
 111         MP_DIGITS(&s) = 0;
 112         /* s_mp_mul_mont doesn't allow source and destination to be the same */
 113         if ((a == r) || (b == r)) {
 114                 MP_CHECKOK(mp_init(&s));
 115                 MP_CHECKOK(s_mp_mul_mont
 116                                    (a, b, &s, (mp_mont_modulus *) meth->extra1));
 117                 MP_CHECKOK(mp_copy(&s, r));
 118                 mp_clear(&s);
 119         } else {
 120                 return s_mp_mul_mont(a, b, r, (mp_mont_modulus *) meth->extra1);
 121         }
 122 #endif
 123   CLEANUP:
 124         return res;
 125 }
 126
 127 /* Field squaring using Montgomery reduction. */
 128 mp_err
 129 ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
 130 {
 131         return ec_GFp_mul_mont(a, a, r, meth);
 132 }
 133
 134 /* Field division using Montgomery reduction. */
 135 mp_err
 136 ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
 137                                 const GFMethod *meth)
 138 {
 139         mp_err res = MP_OKAY;
 140
 141         /* if A=aZ represents a encoded in montgomery coordinates with Z and #
 142          * and \ respectively represent multiplication and division in
 143          * montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv =
 144          * (1/b)Z = (1/B)(Z^2) where B # Binv = Z */
 145         MP_CHECKOK(ec_GFp_div(a, b, r, meth));
 146         MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
 147         if (a == NULL) {
 148                 MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
 149         }
 150   CLEANUP:
 151         return res;
 152 }
 153
 154 /* Encode a field element in Montgomery form. See s_mp_to_mont in
 155  * mpi/mpmontg.c */
 156 mp_err
 157 ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
 158 {
 159         mp_mont_modulus *mmm;
 160         mp_err res = MP_OKAY;
 161
 162         mmm = (mp_mont_modulus *) meth->extra1;
 163         MP_CHECKOK(mpl_lsh(a, r, mmm->b));
 164         MP_CHECKOK(mp_mod(r, &mmm->N, r));
 165   CLEANUP:
 166         return res;
 167 }
 168
 169 /* Decode a field element from Montgomery form. */
 170 mp_err
 171 ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
 172 {
 173         mp_err res = MP_OKAY;
 174
 175         if (a != r) {
 176                 MP_CHECKOK(mp_copy(a, r));
 177         }
 178         MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
 179   CLEANUP:
 180         return res;
 181 }
 182
 183 /* Free the memory allocated to the extra fields of Montgomery GFMethod
 184  * object. */
 185 void
 186 ec_GFp_extra_free_mont(GFMethod *meth)
 187 {
 188         if (meth->extra1 != NULL) {
 189                 free(meth->extra1);
 190                 meth->extra1 = NULL;
 191         }
 192 }