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