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