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 for prime field curves. 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> 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 #include "ecp.h" 48 #include "mpi.h" 49 #include "mplogic.h" 50 #include "mpi-priv.h" 51 #ifndef _KERNEL 52 #include <stdlib.h> 53 #endif 54 55 #define ECP521_DIGITS ECL_CURVE_DIGITS(521) 56 57 /* Fast modular reduction for p521 = 2^521 - 1. a can be r. Uses 58 * algorithm 2.31 from Hankerson, Menezes, Vanstone. Guide to 59 * Elliptic Curve Cryptography. */ 60 mp_err 61 ec_GFp_nistp521_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 62 { 63 mp_err res = MP_OKAY; 64 int a_bits = mpl_significant_bits(a); 65 int i; 66 67 /* m1, m2 are statically-allocated mp_int of exactly the size we need */ 68 mp_int m1; 69 70 mp_digit s1[ECP521_DIGITS] = { 0 }; 71 72 MP_SIGN(&m1) = MP_ZPOS; 73 MP_ALLOC(&m1) = ECP521_DIGITS; 74 MP_USED(&m1) = ECP521_DIGITS; 75 MP_DIGITS(&m1) = s1; 76 77 if (a_bits < 521) { 78 if (a==r) return MP_OKAY; 79 return mp_copy(a, r); 80 } 81 /* for polynomials larger than twice the field size or polynomials 82 * not using all words, use regular reduction */ 83 if (a_bits > (521*2)) { 84 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 85 } else { 86 #define FIRST_DIGIT (ECP521_DIGITS-1) 87 for (i = FIRST_DIGIT; i < MP_USED(a)-1; i++) { 88 s1[i-FIRST_DIGIT] = (MP_DIGIT(a, i) >> 9) 89 | (MP_DIGIT(a, 1+i) << (MP_DIGIT_BIT-9)); 90 } 91 s1[i-FIRST_DIGIT] = MP_DIGIT(a, i) >> 9; 92 93 if ( a != r ) { 94 MP_CHECKOK(s_mp_pad(r,ECP521_DIGITS)); 95 for (i = 0; i < ECP521_DIGITS; i++) { 96 MP_DIGIT(r,i) = MP_DIGIT(a, i); 97 } 98 } 99 MP_USED(r) = ECP521_DIGITS; 100 MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF; 101 102 MP_CHECKOK(s_mp_add(r, &m1)); 103 if (MP_DIGIT(r, FIRST_DIGIT) & 0x200) { 104 MP_CHECKOK(s_mp_add_d(r,1)); 105 MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF; 106 } 107 s_mp_clamp(r); 108 } 109 110 CLEANUP: 111 return res; 112 } 113 114 /* Compute the square of polynomial a, reduce modulo p521. Store the 115 * result in r. r could be a. Uses optimized modular reduction for p521. 116 */ 117 mp_err 118 ec_GFp_nistp521_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 119 { 120 mp_err res = MP_OKAY; 121 122 MP_CHECKOK(mp_sqr(a, r)); 123 MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth)); 124 CLEANUP: 125 return res; 126 } 127 128 /* Compute the product of two polynomials a and b, reduce modulo p521. 129 * Store the result in r. r could be a or b; a could be b. Uses 130 * optimized modular reduction for p521. */ 131 mp_err 132 ec_GFp_nistp521_mul(const mp_int *a, const mp_int *b, mp_int *r, 133 const GFMethod *meth) 134 { 135 mp_err res = MP_OKAY; 136 137 MP_CHECKOK(mp_mul(a, b, r)); 138 MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth)); 139 CLEANUP: 140 return res; 141 } 142 143 /* Divides two field elements. If a is NULL, then returns the inverse of 144 * b. */ 145 mp_err 146 ec_GFp_nistp521_div(const mp_int *a, const mp_int *b, mp_int *r, 147 const GFMethod *meth) 148 { 149 mp_err res = MP_OKAY; 150 mp_int t; 151 152 /* If a is NULL, then return the inverse of b, otherwise return a/b. */ 153 if (a == NULL) { 154 return mp_invmod(b, &meth->irr, r); 155 } else { 156 /* MPI doesn't support divmod, so we implement it using invmod and 157 * mulmod. */ 158 MP_CHECKOK(mp_init(&t, FLAG(b))); 159 MP_CHECKOK(mp_invmod(b, &meth->irr, &t)); 160 MP_CHECKOK(mp_mul(a, &t, r)); 161 MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth)); 162 CLEANUP: 163 mp_clear(&t); 164 return res; 165 } 166 } 167 168 /* Wire in fast field arithmetic and precomputation of base point for 169 * named curves. */ 170 mp_err 171 ec_group_set_gfp521(ECGroup *group, ECCurveName name) 172 { 173 if (name == ECCurve_NIST_P521) { 174 group->meth->field_mod = &ec_GFp_nistp521_mod; 175 group->meth->field_mul = &ec_GFp_nistp521_mul; 176 group->meth->field_sqr = &ec_GFp_nistp521_sqr; 177 group->meth->field_div = &ec_GFp_nistp521_div; 178 } 179 return MP_OKAY; 180 } 181