usr/src/common/crypto/ecc/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  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
  40  * Use is subject to license terms.
  41  *
  42  * Sun elects to use this software under the MPL license.
  43  */
  44
  45 #pragma ident   "%Z%%M% %I%     %E% SMI"
  46
  47 /* Uses Montgomery reduction for field arithmetic.  See mpi/mpmontg.c for
  48  * code implementation. */
  49
  50 #include "mpi.h"
  51 #include "mplogic.h"
  52 #include "mpi-priv.h"
  53 #include "ecl-priv.h"
  54 #include "ecp.h"
  55 #ifndef _KERNEL
  56 #include <stdlib.h>
  57 #include <stdio.h>
  58 #endif
  59
  60 /* Construct a generic GFMethod for arithmetic over prime fields with
  61  * irreducible irr. */
  62 GFMethod *
  63 GFMethod_consGFp_mont(const mp_int *irr)
  64 {
  65         mp_err res = MP_OKAY;
  66         int i;
  67         GFMethod *meth = NULL;
  68         mp_mont_modulus *mmm;
  69
  70         meth = GFMethod_consGFp(irr);
  71         if (meth == NULL)
  72                 return NULL;
  73
  74 #ifdef _KERNEL
  75         mmm = (mp_mont_modulus *) kmem_alloc(sizeof(mp_mont_modulus),
  76             FLAG(irr));
  77 #else
  78         mmm = (mp_mont_modulus *) malloc(sizeof(mp_mont_modulus));
  79 #endif
  80         if (mmm == NULL) {
  81                 res = MP_MEM;
  82                 goto CLEANUP;
  83         }
  84
  85         meth->field_mul = &ec_GFp_mul_mont;
  86         meth->field_sqr = &ec_GFp_sqr_mont;
  87         meth->field_div = &ec_GFp_div_mont;
  88         meth->field_enc = &ec_GFp_enc_mont;
  89         meth->field_dec = &ec_GFp_dec_mont;
  90         meth->extra1 = mmm;
  91         meth->extra2 = NULL;
  92         meth->extra_free = &ec_GFp_extra_free_mont;
  93
  94         mmm->N = meth->irr;
  95         i = mpl_significant_bits(&meth->irr);
  96         i += MP_DIGIT_BIT - 1;
  97         mmm->b = i - i % MP_DIGIT_BIT;
  98         mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0));
  99
 100   CLEANUP:
 101         if (res != MP_OKAY) {
 102                 GFMethod_free(meth);
 103                 return NULL;
 104         }
 105         return meth;
 106 }
 107
 108 /* Wrapper functions for generic prime field arithmetic. */
 109
 110 /* Field multiplication using Montgomery reduction. */
 111 mp_err
 112 ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
 113                                 const GFMethod *meth)
 114 {
 115         mp_err res = MP_OKAY;
 116
 117 #ifdef MP_MONT_USE_MP_MUL
 118         /* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont
 119          * is not implemented and we have to use mp_mul and s_mp_redc directly
 120          */
 121         MP_CHECKOK(mp_mul(a, b, r));
 122         MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
 123 #else
 124         mp_int s;
 125
 126         MP_DIGITS(&s) = 0;
 127         /* s_mp_mul_mont doesn't allow source and destination to be the same */
 128         if ((a == r) || (b == r)) {
 129                 MP_CHECKOK(mp_init(&s, FLAG(a)));
 130                 MP_CHECKOK(s_mp_mul_mont
 131                                    (a, b, &s, (mp_mont_modulus *) meth->extra1));
 132                 MP_CHECKOK(mp_copy(&s, r));
 133                 mp_clear(&s);
 134         } else {
 135                 return s_mp_mul_mont(a, b, r, (mp_mont_modulus *) meth->extra1);
 136         }
 137 #endif
 138   CLEANUP:
 139         return res;
 140 }
 141
 142 /* Field squaring using Montgomery reduction. */
 143 mp_err
 144 ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
 145 {
 146         return ec_GFp_mul_mont(a, a, r, meth);
 147 }
 148
 149 /* Field division using Montgomery reduction. */
 150 mp_err
 151 ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
 152                                 const GFMethod *meth)
 153 {
 154         mp_err res = MP_OKAY;
 155
 156         /* if A=aZ represents a encoded in montgomery coordinates with Z and #
 157          * and \ respectively represent multiplication and division in
 158          * montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv =
 159          * (1/b)Z = (1/B)(Z^2) where B # Binv = Z */
 160         MP_CHECKOK(ec_GFp_div(a, b, r, meth));
 161         MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
 162         if (a == NULL) {
 163                 MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
 164         }
 165   CLEANUP:
 166         return res;
 167 }
 168
 169 /* Encode a field element in Montgomery form. See s_mp_to_mont in
 170  * mpi/mpmontg.c */
 171 mp_err
 172 ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
 173 {
 174         mp_mont_modulus *mmm;
 175         mp_err res = MP_OKAY;
 176
 177         mmm = (mp_mont_modulus *) meth->extra1;
 178         MP_CHECKOK(mpl_lsh(a, r, mmm->b));
 179         MP_CHECKOK(mp_mod(r, &mmm->N, r));
 180   CLEANUP:
 181         return res;
 182 }
 183
 184 /* Decode a field element from Montgomery form. */
 185 mp_err
 186 ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
 187 {
 188         mp_err res = MP_OKAY;
 189
 190         if (a != r) {
 191                 MP_CHECKOK(mp_copy(a, r));
 192         }
 193         MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
 194   CLEANUP:
 195         return res;
 196 }
 197
 198 /* Free the memory allocated to the extra fields of Montgomery GFMethod
 199  * object. */
 200 void
 201 ec_GFp_extra_free_mont(GFMethod *meth)
 202 {
 203         if (meth->extra1 != NULL) {
 204 #ifdef _KERNEL
 205                 kmem_free(meth->extra1, sizeof(mp_mont_modulus));
 206 #else
 207                 free(meth->extra1);
 208 #endif
 209                 meth->extra1 = NULL;
 210         }
 211 }