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