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 } 212