1/* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* ********************************************************************* 25 * 26 * The Original Code is the elliptic curve math library. 27 * 28 * The Initial Developer of the Original Code is 29 * Sun Microsystems, Inc. 30 * Portions created by the Initial Developer are Copyright (C) 2003 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories 35 * 36 *********************************************************************** */ 37 38/* Uses Montgomery reduction for field arithmetic. See mpi/mpmontg.c for 39 * code implementation. */ 40 41#include "mpi.h" 42#include "mplogic.h" 43#include "mpi-priv.h" 44#include "ecl-priv.h" 45#include "ecp.h" 46#ifndef _KERNEL 47#include <stdlib.h> 48#include <stdio.h> 49#endif 50 51/* Construct a generic GFMethod for arithmetic over prime fields with 52 * irreducible irr. */ 53GFMethod * 54GFMethod_consGFp_mont(const mp_int *irr) 55{ 56 mp_err res = MP_OKAY; 57 int i; 58 GFMethod *meth = NULL; 59 mp_mont_modulus *mmm; 60 61 meth = GFMethod_consGFp(irr); 62 if (meth == NULL) 63 return NULL; 64 65#ifdef _KERNEL 66 mmm = (mp_mont_modulus *) kmem_alloc(sizeof(mp_mont_modulus), 67 FLAG(irr)); 68#else 69 mmm = (mp_mont_modulus *) malloc(sizeof(mp_mont_modulus)); 70#endif 71 if (mmm == NULL) { 72 res = MP_MEM; 73 goto CLEANUP; 74 } 75 76 meth->field_mul = &ec_GFp_mul_mont; 77 meth->field_sqr = &ec_GFp_sqr_mont; 78 meth->field_div = &ec_GFp_div_mont; 79 meth->field_enc = &ec_GFp_enc_mont; 80 meth->field_dec = &ec_GFp_dec_mont; 81 meth->extra1 = mmm; 82 meth->extra2 = NULL; 83 meth->extra_free = &ec_GFp_extra_free_mont; 84 85 mmm->N = meth->irr; 86 i = mpl_significant_bits(&meth->irr); 87 i += MP_DIGIT_BIT - 1; 88 mmm->b = i - i % MP_DIGIT_BIT; 89 mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0)); 90 91 CLEANUP: 92 if (res != MP_OKAY) { 93 GFMethod_free(meth); 94 return NULL; 95 } 96 return meth; 97} 98 99/* Wrapper functions for generic prime field arithmetic. */ 100 101/* Field multiplication using Montgomery reduction. */ 102mp_err 103ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r, 104 const GFMethod *meth) 105{ 106 mp_err res = MP_OKAY; 107 108#ifdef MP_MONT_USE_MP_MUL 109 /* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont 110 * is not implemented and we have to use mp_mul and s_mp_redc directly 111 */ 112 MP_CHECKOK(mp_mul(a, b, r)); 113 MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1)); 114#else 115 mp_int s; 116 117 MP_DIGITS(&s) = 0; 118 /* s_mp_mul_mont doesn't allow source and destination to be the same */ 119 if ((a == r) || (b == r)) { 120 MP_CHECKOK(mp_init(&s, FLAG(a))); 121 MP_CHECKOK(s_mp_mul_mont 122 (a, b, &s, (mp_mont_modulus *) meth->extra1)); 123 MP_CHECKOK(mp_copy(&s, r)); 124 mp_clear(&s); 125 } else { 126 return s_mp_mul_mont(a, b, r, (mp_mont_modulus *) meth->extra1); 127 } 128#endif 129 CLEANUP: 130 return res; 131} 132 133/* Field squaring using Montgomery reduction. */ 134mp_err 135ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth) 136{ 137 return ec_GFp_mul_mont(a, a, r, meth); 138} 139 140/* Field division using Montgomery reduction. */ 141mp_err 142ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r, 143 const GFMethod *meth) 144{ 145 mp_err res = MP_OKAY; 146 147 /* if A=aZ represents a encoded in montgomery coordinates with Z and # 148 * and \ respectively represent multiplication and division in 149 * montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv = 150 * (1/b)Z = (1/B)(Z^2) where B # Binv = Z */ 151 MP_CHECKOK(ec_GFp_div(a, b, r, meth)); 152 MP_CHECKOK(ec_GFp_enc_mont(r, r, meth)); 153 if (a == NULL) { 154 MP_CHECKOK(ec_GFp_enc_mont(r, r, meth)); 155 } 156 CLEANUP: 157 return res; 158} 159 160/* Encode a field element in Montgomery form. See s_mp_to_mont in 161 * mpi/mpmontg.c */ 162mp_err 163ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth) 164{ 165 mp_mont_modulus *mmm; 166 mp_err res = MP_OKAY; 167 168 mmm = (mp_mont_modulus *) meth->extra1; 169 MP_CHECKOK(mpl_lsh(a, r, mmm->b)); 170 MP_CHECKOK(mp_mod(r, &mmm->N, r)); 171 CLEANUP: 172 return res; 173} 174 175/* Decode a field element from Montgomery form. */ 176mp_err 177ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth) 178{ 179 mp_err res = MP_OKAY; 180 181 if (a != r) { 182 MP_CHECKOK(mp_copy(a, r)); 183 } 184 MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1)); 185 CLEANUP: 186 return res; 187} 188 189/* Free the memory allocated to the extra fields of Montgomery GFMethod 190 * object. */ 191void 192ec_GFp_extra_free_mont(GFMethod *meth) 193{ 194 if (meth->extra1 != NULL) { 195#ifdef _KERNEL 196 kmem_free(meth->extra1, sizeof(mp_mont_modulus)); 197#else 198 free(meth->extra1); 199#endif 200 meth->extra1 = NULL; 201 } 202} 203