1 /* ********************************************************************* 2 * 3 * Sun elects to have this file available under and governed by the 4 * Mozilla Public License Version 1.1 ("MPL") (see 5 * http://www.mozilla.org/MPL/ for full license text). For the avoidance 6 * of doubt and subject to the following, Sun also elects to allow 7 * licensees to use this file under the MPL, the GNU General Public 8 * License version 2 only or the Lesser General Public License version 9 * 2.1 only. Any references to the "GNU General Public License version 2 10 * or later" or "GPL" in the following shall be construed to mean the 11 * GNU General Public License version 2 only. Any references to the "GNU 12 * Lesser General Public License version 2.1 or later" or "LGPL" in the 13 * following shall be construed to mean the GNU Lesser General Public 14 * License version 2.1 only. However, the following notice accompanied 15 * the original version of this file: 16 * 17 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 18 * 19 * The contents of this file are subject to the Mozilla Public License Version 20 * 1.1 (the "License"); you may not use this file except in compliance with 21 * the License. You may obtain a copy of the License at 22 * http://www.mozilla.org/MPL/ 23 * 24 * Software distributed under the License is distributed on an "AS IS" basis, 25 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 26 * for the specific language governing rights and limitations under the 27 * License. 28 * 29 * The Original Code is the elliptic curve math library for prime field curves. 30 * 31 * The Initial Developer of the Original Code is 32 * Sun Microsystems, Inc. 33 * Portions created by the Initial Developer are Copyright (C) 2003 34 * the Initial Developer. All Rights Reserved. 35 * 36 * Contributor(s): 37 * Douglas Stebila <douglas@stebila.ca> 38 * 39 * Alternatively, the contents of this file may be used under the terms of 40 * either the GNU General Public License Version 2 or later (the "GPL"), or 41 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 42 * in which case the provisions of the GPL or the LGPL are applicable instead 43 * of those above. If you wish to allow use of your version of this file only 44 * under the terms of either the GPL or the LGPL, and not to allow others to 45 * use your version of this file under the terms of the MPL, indicate your 46 * decision by deleting the provisions above and replace them with the notice 47 * and other provisions required by the GPL or the LGPL. If you do not delete 48 * the provisions above, a recipient may use your version of this file under 49 * the terms of any one of the MPL, the GPL or the LGPL. 50 * 51 *********************************************************************** */ 52 /* 53 * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved. 54 * Use is subject to license terms. 55 */ 56 57 #include "ecp.h" 58 #include "mpi.h" 59 #include "mplogic.h" 60 #include "mpi-priv.h" 61 #ifndef _KERNEL 62 #include <stdlib.h> 63 #endif 64 65 /* Fast modular reduction for p384 = 2^384 - 2^128 - 2^96 + 2^32 - 1. a can be r. 66 * Uses algorithm 2.30 from Hankerson, Menezes, Vanstone. Guide to 67 * Elliptic Curve Cryptography. */ 68 mp_err 69 ec_GFp_nistp384_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 70 { 71 mp_err res = MP_OKAY; 72 int a_bits = mpl_significant_bits(a); 73 int i; 74 75 /* m1, m2 are statically-allocated mp_int of exactly the size we need */ 76 mp_int m[10]; 77 78 #ifdef ECL_THIRTY_TWO_BIT 79 mp_digit s[10][12]; 80 for (i = 0; i < 10; i++) { 81 MP_SIGN(&m[i]) = MP_ZPOS; 82 MP_ALLOC(&m[i]) = 12; 83 MP_USED(&m[i]) = 12; 84 MP_DIGITS(&m[i]) = s[i]; 85 } 86 #else 87 mp_digit s[10][6]; 88 for (i = 0; i < 10; i++) { 89 MP_SIGN(&m[i]) = MP_ZPOS; 90 MP_ALLOC(&m[i]) = 6; 91 MP_USED(&m[i]) = 6; 92 MP_DIGITS(&m[i]) = s[i]; 93 } 94 #endif 95 96 #ifdef ECL_THIRTY_TWO_BIT 97 /* for polynomials larger than twice the field size or polynomials 98 * not using all words, use regular reduction */ 99 if ((a_bits > 768) || (a_bits <= 736)) { 100 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 101 } else { 102 for (i = 0; i < 12; i++) { 103 s[0][i] = MP_DIGIT(a, i); 104 } 105 s[1][0] = 0; 106 s[1][1] = 0; 107 s[1][2] = 0; 108 s[1][3] = 0; 109 s[1][4] = MP_DIGIT(a, 21); 110 s[1][5] = MP_DIGIT(a, 22); 111 s[1][6] = MP_DIGIT(a, 23); 112 s[1][7] = 0; 113 s[1][8] = 0; 114 s[1][9] = 0; 115 s[1][10] = 0; 116 s[1][11] = 0; 117 for (i = 0; i < 12; i++) { 118 s[2][i] = MP_DIGIT(a, i+12); 119 } 120 s[3][0] = MP_DIGIT(a, 21); 121 s[3][1] = MP_DIGIT(a, 22); 122 s[3][2] = MP_DIGIT(a, 23); 123 for (i = 3; i < 12; i++) { 124 s[3][i] = MP_DIGIT(a, i+9); 125 } 126 s[4][0] = 0; 127 s[4][1] = MP_DIGIT(a, 23); 128 s[4][2] = 0; 129 s[4][3] = MP_DIGIT(a, 20); 130 for (i = 4; i < 12; i++) { 131 s[4][i] = MP_DIGIT(a, i+8); 132 } 133 s[5][0] = 0; 134 s[5][1] = 0; 135 s[5][2] = 0; 136 s[5][3] = 0; 137 s[5][4] = MP_DIGIT(a, 20); 138 s[5][5] = MP_DIGIT(a, 21); 139 s[5][6] = MP_DIGIT(a, 22); 140 s[5][7] = MP_DIGIT(a, 23); 141 s[5][8] = 0; 142 s[5][9] = 0; 143 s[5][10] = 0; 144 s[5][11] = 0; 145 s[6][0] = MP_DIGIT(a, 20); 146 s[6][1] = 0; 147 s[6][2] = 0; 148 s[6][3] = MP_DIGIT(a, 21); 149 s[6][4] = MP_DIGIT(a, 22); 150 s[6][5] = MP_DIGIT(a, 23); 151 s[6][6] = 0; 152 s[6][7] = 0; 153 s[6][8] = 0; 154 s[6][9] = 0; 155 s[6][10] = 0; 156 s[6][11] = 0; 157 s[7][0] = MP_DIGIT(a, 23); 158 for (i = 1; i < 12; i++) { 159 s[7][i] = MP_DIGIT(a, i+11); 160 } 161 s[8][0] = 0; 162 s[8][1] = MP_DIGIT(a, 20); 163 s[8][2] = MP_DIGIT(a, 21); 164 s[8][3] = MP_DIGIT(a, 22); 165 s[8][4] = MP_DIGIT(a, 23); 166 s[8][5] = 0; 167 s[8][6] = 0; 168 s[8][7] = 0; 169 s[8][8] = 0; 170 s[8][9] = 0; 171 s[8][10] = 0; 172 s[8][11] = 0; 173 s[9][0] = 0; 174 s[9][1] = 0; 175 s[9][2] = 0; 176 s[9][3] = MP_DIGIT(a, 23); 177 s[9][4] = MP_DIGIT(a, 23); 178 s[9][5] = 0; 179 s[9][6] = 0; 180 s[9][7] = 0; 181 s[9][8] = 0; 182 s[9][9] = 0; 183 s[9][10] = 0; 184 s[9][11] = 0; 185 186 MP_CHECKOK(mp_add(&m[0], &m[1], r)); 187 MP_CHECKOK(mp_add(r, &m[1], r)); 188 MP_CHECKOK(mp_add(r, &m[2], r)); 189 MP_CHECKOK(mp_add(r, &m[3], r)); 190 MP_CHECKOK(mp_add(r, &m[4], r)); 191 MP_CHECKOK(mp_add(r, &m[5], r)); 192 MP_CHECKOK(mp_add(r, &m[6], r)); 193 MP_CHECKOK(mp_sub(r, &m[7], r)); 194 MP_CHECKOK(mp_sub(r, &m[8], r)); 195 MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r)); 196 s_mp_clamp(r); 197 } 198 #else 199 /* for polynomials larger than twice the field size or polynomials 200 * not using all words, use regular reduction */ 201 if ((a_bits > 768) || (a_bits <= 736)) { 202 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 203 } else { 204 for (i = 0; i < 6; i++) { 205 s[0][i] = MP_DIGIT(a, i); 206 } 207 s[1][0] = 0; 208 s[1][1] = 0; 209 s[1][2] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 210 s[1][3] = MP_DIGIT(a, 11) >> 32; 211 s[1][4] = 0; 212 s[1][5] = 0; 213 for (i = 0; i < 6; i++) { 214 s[2][i] = MP_DIGIT(a, i+6); 215 } 216 s[3][0] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 217 s[3][1] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32); 218 for (i = 2; i < 6; i++) { 219 s[3][i] = (MP_DIGIT(a, i+4) >> 32) | (MP_DIGIT(a, i+5) << 32); 220 } 221 s[4][0] = (MP_DIGIT(a, 11) >> 32) << 32; 222 s[4][1] = MP_DIGIT(a, 10) << 32; 223 for (i = 2; i < 6; i++) { 224 s[4][i] = MP_DIGIT(a, i+4); 225 } 226 s[5][0] = 0; 227 s[5][1] = 0; 228 s[5][2] = MP_DIGIT(a, 10); 229 s[5][3] = MP_DIGIT(a, 11); 230 s[5][4] = 0; 231 s[5][5] = 0; 232 s[6][0] = (MP_DIGIT(a, 10) << 32) >> 32; 233 s[6][1] = (MP_DIGIT(a, 10) >> 32) << 32; 234 s[6][2] = MP_DIGIT(a, 11); 235 s[6][3] = 0; 236 s[6][4] = 0; 237 s[6][5] = 0; 238 s[7][0] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32); 239 for (i = 1; i < 6; i++) { 240 s[7][i] = (MP_DIGIT(a, i+5) >> 32) | (MP_DIGIT(a, i+6) << 32); 241 } 242 s[8][0] = MP_DIGIT(a, 10) << 32; 243 s[8][1] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 244 s[8][2] = MP_DIGIT(a, 11) >> 32; 245 s[8][3] = 0; 246 s[8][4] = 0; 247 s[8][5] = 0; 248 s[9][0] = 0; 249 s[9][1] = (MP_DIGIT(a, 11) >> 32) << 32; 250 s[9][2] = MP_DIGIT(a, 11) >> 32; 251 s[9][3] = 0; 252 s[9][4] = 0; 253 s[9][5] = 0; 254 255 MP_CHECKOK(mp_add(&m[0], &m[1], r)); 256 MP_CHECKOK(mp_add(r, &m[1], r)); 257 MP_CHECKOK(mp_add(r, &m[2], r)); 258 MP_CHECKOK(mp_add(r, &m[3], r)); 259 MP_CHECKOK(mp_add(r, &m[4], r)); 260 MP_CHECKOK(mp_add(r, &m[5], r)); 261 MP_CHECKOK(mp_add(r, &m[6], r)); 262 MP_CHECKOK(mp_sub(r, &m[7], r)); 263 MP_CHECKOK(mp_sub(r, &m[8], r)); 264 MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r)); 265 s_mp_clamp(r); 266 } 267 #endif 268 269 CLEANUP: 270 return res; 271 } 272 273 /* Compute the square of polynomial a, reduce modulo p384. Store the 274 * result in r. r could be a. Uses optimized modular reduction for p384. 275 */ 276 mp_err 277 ec_GFp_nistp384_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 278 { 279 mp_err res = MP_OKAY; 280 281 MP_CHECKOK(mp_sqr(a, r)); 282 MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth)); 283 CLEANUP: 284 return res; 285 } 286 287 /* Compute the product of two polynomials a and b, reduce modulo p384. 288 * Store the result in r. r could be a or b; a could be b. Uses 289 * optimized modular reduction for p384. */ 290 mp_err 291 ec_GFp_nistp384_mul(const mp_int *a, const mp_int *b, mp_int *r, 292 const GFMethod *meth) 293 { 294 mp_err res = MP_OKAY; 295 296 MP_CHECKOK(mp_mul(a, b, r)); 297 MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth)); 298 CLEANUP: 299 return res; 300 } 301 302 /* Wire in fast field arithmetic and precomputation of base point for 303 * named curves. */ 304 mp_err 305 ec_group_set_gfp384(ECGroup *group, ECCurveName name) 306 { 307 if (name == ECCurve_NIST_P384) { 308 group->meth->field_mod = &ec_GFp_nistp384_mod; 309 group->meth->field_mul = &ec_GFp_nistp384_mul; 310 group->meth->field_sqr = &ec_GFp_nistp384_sqr; 311 } 312 return MP_OKAY; 313 }