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 /* Fast modular reduction for p384 = 2^384 - 2^128 - 2^96 + 2^32 - 1. a can be r. 56 * Uses algorithm 2.30 from Hankerson, Menezes, Vanstone. Guide to 57 * Elliptic Curve Cryptography. */ 58 mp_err 59 ec_GFp_nistp384_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 m[10]; 67 68 #ifdef ECL_THIRTY_TWO_BIT 69 mp_digit s[10][12]; 70 for (i = 0; i < 10; i++) { 71 MP_SIGN(&m[i]) = MP_ZPOS; 72 MP_ALLOC(&m[i]) = 12; 73 MP_USED(&m[i]) = 12; 74 MP_DIGITS(&m[i]) = s[i]; 75 } 76 #else 77 mp_digit s[10][6]; 78 for (i = 0; i < 10; i++) { 79 MP_SIGN(&m[i]) = MP_ZPOS; 80 MP_ALLOC(&m[i]) = 6; 81 MP_USED(&m[i]) = 6; 82 MP_DIGITS(&m[i]) = s[i]; 83 } 84 #endif 85 86 #ifdef ECL_THIRTY_TWO_BIT 87 /* for polynomials larger than twice the field size or polynomials 88 * not using all words, use regular reduction */ 89 if ((a_bits > 768) || (a_bits <= 736)) { 90 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 91 } else { 92 for (i = 0; i < 12; i++) { 93 s[0][i] = MP_DIGIT(a, i); 94 } 95 s[1][0] = 0; 96 s[1][1] = 0; 97 s[1][2] = 0; 98 s[1][3] = 0; 99 s[1][4] = MP_DIGIT(a, 21); 100 s[1][5] = MP_DIGIT(a, 22); 101 s[1][6] = MP_DIGIT(a, 23); 102 s[1][7] = 0; 103 s[1][8] = 0; 104 s[1][9] = 0; 105 s[1][10] = 0; 106 s[1][11] = 0; 107 for (i = 0; i < 12; i++) { 108 s[2][i] = MP_DIGIT(a, i+12); 109 } 110 s[3][0] = MP_DIGIT(a, 21); 111 s[3][1] = MP_DIGIT(a, 22); 112 s[3][2] = MP_DIGIT(a, 23); 113 for (i = 3; i < 12; i++) { 114 s[3][i] = MP_DIGIT(a, i+9); 115 } 116 s[4][0] = 0; 117 s[4][1] = MP_DIGIT(a, 23); 118 s[4][2] = 0; 119 s[4][3] = MP_DIGIT(a, 20); 120 for (i = 4; i < 12; i++) { 121 s[4][i] = MP_DIGIT(a, i+8); 122 } 123 s[5][0] = 0; 124 s[5][1] = 0; 125 s[5][2] = 0; 126 s[5][3] = 0; 127 s[5][4] = MP_DIGIT(a, 20); 128 s[5][5] = MP_DIGIT(a, 21); 129 s[5][6] = MP_DIGIT(a, 22); 130 s[5][7] = MP_DIGIT(a, 23); 131 s[5][8] = 0; 132 s[5][9] = 0; 133 s[5][10] = 0; 134 s[5][11] = 0; 135 s[6][0] = MP_DIGIT(a, 20); 136 s[6][1] = 0; 137 s[6][2] = 0; 138 s[6][3] = MP_DIGIT(a, 21); 139 s[6][4] = MP_DIGIT(a, 22); 140 s[6][5] = MP_DIGIT(a, 23); 141 s[6][6] = 0; 142 s[6][7] = 0; 143 s[6][8] = 0; 144 s[6][9] = 0; 145 s[6][10] = 0; 146 s[6][11] = 0; 147 s[7][0] = MP_DIGIT(a, 23); 148 for (i = 1; i < 12; i++) { 149 s[7][i] = MP_DIGIT(a, i+11); 150 } 151 s[8][0] = 0; 152 s[8][1] = MP_DIGIT(a, 20); 153 s[8][2] = MP_DIGIT(a, 21); 154 s[8][3] = MP_DIGIT(a, 22); 155 s[8][4] = MP_DIGIT(a, 23); 156 s[8][5] = 0; 157 s[8][6] = 0; 158 s[8][7] = 0; 159 s[8][8] = 0; 160 s[8][9] = 0; 161 s[8][10] = 0; 162 s[8][11] = 0; 163 s[9][0] = 0; 164 s[9][1] = 0; 165 s[9][2] = 0; 166 s[9][3] = MP_DIGIT(a, 23); 167 s[9][4] = MP_DIGIT(a, 23); 168 s[9][5] = 0; 169 s[9][6] = 0; 170 s[9][7] = 0; 171 s[9][8] = 0; 172 s[9][9] = 0; 173 s[9][10] = 0; 174 s[9][11] = 0; 175 176 MP_CHECKOK(mp_add(&m[0], &m[1], r)); 177 MP_CHECKOK(mp_add(r, &m[1], r)); 178 MP_CHECKOK(mp_add(r, &m[2], r)); 179 MP_CHECKOK(mp_add(r, &m[3], r)); 180 MP_CHECKOK(mp_add(r, &m[4], r)); 181 MP_CHECKOK(mp_add(r, &m[5], r)); 182 MP_CHECKOK(mp_add(r, &m[6], r)); 183 MP_CHECKOK(mp_sub(r, &m[7], r)); 184 MP_CHECKOK(mp_sub(r, &m[8], r)); 185 MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r)); 186 s_mp_clamp(r); 187 } 188 #else 189 /* for polynomials larger than twice the field size or polynomials 190 * not using all words, use regular reduction */ 191 if ((a_bits > 768) || (a_bits <= 736)) { 192 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 193 } else { 194 for (i = 0; i < 6; i++) { 195 s[0][i] = MP_DIGIT(a, i); 196 } 197 s[1][0] = 0; 198 s[1][1] = 0; 199 s[1][2] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 200 s[1][3] = MP_DIGIT(a, 11) >> 32; 201 s[1][4] = 0; 202 s[1][5] = 0; 203 for (i = 0; i < 6; i++) { 204 s[2][i] = MP_DIGIT(a, i+6); 205 } 206 s[3][0] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 207 s[3][1] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32); 208 for (i = 2; i < 6; i++) { 209 s[3][i] = (MP_DIGIT(a, i+4) >> 32) | (MP_DIGIT(a, i+5) << 32); 210 } 211 s[4][0] = (MP_DIGIT(a, 11) >> 32) << 32; 212 s[4][1] = MP_DIGIT(a, 10) << 32; 213 for (i = 2; i < 6; i++) { 214 s[4][i] = MP_DIGIT(a, i+4); 215 } 216 s[5][0] = 0; 217 s[5][1] = 0; 218 s[5][2] = MP_DIGIT(a, 10); 219 s[5][3] = MP_DIGIT(a, 11); 220 s[5][4] = 0; 221 s[5][5] = 0; 222 s[6][0] = (MP_DIGIT(a, 10) << 32) >> 32; 223 s[6][1] = (MP_DIGIT(a, 10) >> 32) << 32; 224 s[6][2] = MP_DIGIT(a, 11); 225 s[6][3] = 0; 226 s[6][4] = 0; 227 s[6][5] = 0; 228 s[7][0] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32); 229 for (i = 1; i < 6; i++) { 230 s[7][i] = (MP_DIGIT(a, i+5) >> 32) | (MP_DIGIT(a, i+6) << 32); 231 } 232 s[8][0] = MP_DIGIT(a, 10) << 32; 233 s[8][1] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 234 s[8][2] = MP_DIGIT(a, 11) >> 32; 235 s[8][3] = 0; 236 s[8][4] = 0; 237 s[8][5] = 0; 238 s[9][0] = 0; 239 s[9][1] = (MP_DIGIT(a, 11) >> 32) << 32; 240 s[9][2] = MP_DIGIT(a, 11) >> 32; 241 s[9][3] = 0; 242 s[9][4] = 0; 243 s[9][5] = 0; 244 245 MP_CHECKOK(mp_add(&m[0], &m[1], r)); 246 MP_CHECKOK(mp_add(r, &m[1], r)); 247 MP_CHECKOK(mp_add(r, &m[2], r)); 248 MP_CHECKOK(mp_add(r, &m[3], r)); 249 MP_CHECKOK(mp_add(r, &m[4], r)); 250 MP_CHECKOK(mp_add(r, &m[5], r)); 251 MP_CHECKOK(mp_add(r, &m[6], r)); 252 MP_CHECKOK(mp_sub(r, &m[7], r)); 253 MP_CHECKOK(mp_sub(r, &m[8], r)); 254 MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r)); 255 s_mp_clamp(r); 256 } 257 #endif 258 259 CLEANUP: 260 return res; 261 } 262 263 /* Compute the square of polynomial a, reduce modulo p384. Store the 264 * result in r. r could be a. Uses optimized modular reduction for p384. 265 */ 266 mp_err 267 ec_GFp_nistp384_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 268 { 269 mp_err res = MP_OKAY; 270 271 MP_CHECKOK(mp_sqr(a, r)); 272 MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth)); 273 CLEANUP: 274 return res; 275 } 276 277 /* Compute the product of two polynomials a and b, reduce modulo p384. 278 * Store the result in r. r could be a or b; a could be b. Uses 279 * optimized modular reduction for p384. */ 280 mp_err 281 ec_GFp_nistp384_mul(const mp_int *a, const mp_int *b, mp_int *r, 282 const GFMethod *meth) 283 { 284 mp_err res = MP_OKAY; 285 286 MP_CHECKOK(mp_mul(a, b, r)); 287 MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth)); 288 CLEANUP: 289 return res; 290 } 291 292 /* Wire in fast field arithmetic and precomputation of base point for 293 * named curves. */ 294 mp_err 295 ec_group_set_gfp384(ECGroup *group, ECCurveName name) 296 { 297 if (name == ECCurve_NIST_P384) { 298 group->meth->field_mod = &ec_GFp_nistp384_mod; 299 group->meth->field_mul = &ec_GFp_nistp384_mul; 300 group->meth->field_sqr = &ec_GFp_nistp384_sqr; 301 } 302 return MP_OKAY; 303 } 304