1/* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* ********************************************************************* 25 * 26 * The Original Code is the elliptic curve math library for prime field curves. 27 * 28 * The Initial Developer of the Original Code is 29 * Sun Microsystems, Inc. 30 * Portions created by the Initial Developer are Copyright (C) 2003 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Douglas Stebila <douglas@stebila.ca> 35 * 36 *********************************************************************** */ 37 38#include "ecp.h" 39#include "mpi.h" 40#include "mplogic.h" 41#include "mpi-priv.h" 42#ifndef _KERNEL 43#include <stdlib.h> 44#endif 45 46/* Fast modular reduction for p384 = 2^384 - 2^128 - 2^96 + 2^32 - 1. a can be r. 47 * Uses algorithm 2.30 from Hankerson, Menezes, Vanstone. Guide to 48 * Elliptic Curve Cryptography. */ 49mp_err 50ec_GFp_nistp384_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 51{ 52 mp_err res = MP_OKAY; 53 int a_bits = mpl_significant_bits(a); 54 int i; 55 56 /* m1, m2 are statically-allocated mp_int of exactly the size we need */ 57 mp_int m[10]; 58 59#ifdef ECL_THIRTY_TWO_BIT 60 mp_digit s[10][12]; 61 for (i = 0; i < 10; i++) { 62 MP_SIGN(&m[i]) = MP_ZPOS; 63 MP_ALLOC(&m[i]) = 12; 64 MP_USED(&m[i]) = 12; 65 MP_DIGITS(&m[i]) = s[i]; 66 } 67#else 68 mp_digit s[10][6]; 69 for (i = 0; i < 10; i++) { 70 MP_SIGN(&m[i]) = MP_ZPOS; 71 MP_ALLOC(&m[i]) = 6; 72 MP_USED(&m[i]) = 6; 73 MP_DIGITS(&m[i]) = s[i]; 74 } 75#endif 76 77#ifdef ECL_THIRTY_TWO_BIT 78 /* for polynomials larger than twice the field size or polynomials 79 * not using all words, use regular reduction */ 80 if ((a_bits > 768) || (a_bits <= 736)) { 81 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 82 } else { 83 for (i = 0; i < 12; i++) { 84 s[0][i] = MP_DIGIT(a, i); 85 } 86 s[1][0] = 0; 87 s[1][1] = 0; 88 s[1][2] = 0; 89 s[1][3] = 0; 90 s[1][4] = MP_DIGIT(a, 21); 91 s[1][5] = MP_DIGIT(a, 22); 92 s[1][6] = MP_DIGIT(a, 23); 93 s[1][7] = 0; 94 s[1][8] = 0; 95 s[1][9] = 0; 96 s[1][10] = 0; 97 s[1][11] = 0; 98 for (i = 0; i < 12; i++) { 99 s[2][i] = MP_DIGIT(a, i+12); 100 } 101 s[3][0] = MP_DIGIT(a, 21); 102 s[3][1] = MP_DIGIT(a, 22); 103 s[3][2] = MP_DIGIT(a, 23); 104 for (i = 3; i < 12; i++) { 105 s[3][i] = MP_DIGIT(a, i+9); 106 } 107 s[4][0] = 0; 108 s[4][1] = MP_DIGIT(a, 23); 109 s[4][2] = 0; 110 s[4][3] = MP_DIGIT(a, 20); 111 for (i = 4; i < 12; i++) { 112 s[4][i] = MP_DIGIT(a, i+8); 113 } 114 s[5][0] = 0; 115 s[5][1] = 0; 116 s[5][2] = 0; 117 s[5][3] = 0; 118 s[5][4] = MP_DIGIT(a, 20); 119 s[5][5] = MP_DIGIT(a, 21); 120 s[5][6] = MP_DIGIT(a, 22); 121 s[5][7] = MP_DIGIT(a, 23); 122 s[5][8] = 0; 123 s[5][9] = 0; 124 s[5][10] = 0; 125 s[5][11] = 0; 126 s[6][0] = MP_DIGIT(a, 20); 127 s[6][1] = 0; 128 s[6][2] = 0; 129 s[6][3] = MP_DIGIT(a, 21); 130 s[6][4] = MP_DIGIT(a, 22); 131 s[6][5] = MP_DIGIT(a, 23); 132 s[6][6] = 0; 133 s[6][7] = 0; 134 s[6][8] = 0; 135 s[6][9] = 0; 136 s[6][10] = 0; 137 s[6][11] = 0; 138 s[7][0] = MP_DIGIT(a, 23); 139 for (i = 1; i < 12; i++) { 140 s[7][i] = MP_DIGIT(a, i+11); 141 } 142 s[8][0] = 0; 143 s[8][1] = MP_DIGIT(a, 20); 144 s[8][2] = MP_DIGIT(a, 21); 145 s[8][3] = MP_DIGIT(a, 22); 146 s[8][4] = MP_DIGIT(a, 23); 147 s[8][5] = 0; 148 s[8][6] = 0; 149 s[8][7] = 0; 150 s[8][8] = 0; 151 s[8][9] = 0; 152 s[8][10] = 0; 153 s[8][11] = 0; 154 s[9][0] = 0; 155 s[9][1] = 0; 156 s[9][2] = 0; 157 s[9][3] = MP_DIGIT(a, 23); 158 s[9][4] = MP_DIGIT(a, 23); 159 s[9][5] = 0; 160 s[9][6] = 0; 161 s[9][7] = 0; 162 s[9][8] = 0; 163 s[9][9] = 0; 164 s[9][10] = 0; 165 s[9][11] = 0; 166 167 MP_CHECKOK(mp_add(&m[0], &m[1], r)); 168 MP_CHECKOK(mp_add(r, &m[1], r)); 169 MP_CHECKOK(mp_add(r, &m[2], r)); 170 MP_CHECKOK(mp_add(r, &m[3], r)); 171 MP_CHECKOK(mp_add(r, &m[4], r)); 172 MP_CHECKOK(mp_add(r, &m[5], r)); 173 MP_CHECKOK(mp_add(r, &m[6], r)); 174 MP_CHECKOK(mp_sub(r, &m[7], r)); 175 MP_CHECKOK(mp_sub(r, &m[8], r)); 176 MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r)); 177 s_mp_clamp(r); 178 } 179#else 180 /* for polynomials larger than twice the field size or polynomials 181 * not using all words, use regular reduction */ 182 if ((a_bits > 768) || (a_bits <= 736)) { 183 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 184 } else { 185 for (i = 0; i < 6; i++) { 186 s[0][i] = MP_DIGIT(a, i); 187 } 188 s[1][0] = 0; 189 s[1][1] = 0; 190 s[1][2] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 191 s[1][3] = MP_DIGIT(a, 11) >> 32; 192 s[1][4] = 0; 193 s[1][5] = 0; 194 for (i = 0; i < 6; i++) { 195 s[2][i] = MP_DIGIT(a, i+6); 196 } 197 s[3][0] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 198 s[3][1] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32); 199 for (i = 2; i < 6; i++) { 200 s[3][i] = (MP_DIGIT(a, i+4) >> 32) | (MP_DIGIT(a, i+5) << 32); 201 } 202 s[4][0] = (MP_DIGIT(a, 11) >> 32) << 32; 203 s[4][1] = MP_DIGIT(a, 10) << 32; 204 for (i = 2; i < 6; i++) { 205 s[4][i] = MP_DIGIT(a, i+4); 206 } 207 s[5][0] = 0; 208 s[5][1] = 0; 209 s[5][2] = MP_DIGIT(a, 10); 210 s[5][3] = MP_DIGIT(a, 11); 211 s[5][4] = 0; 212 s[5][5] = 0; 213 s[6][0] = (MP_DIGIT(a, 10) << 32) >> 32; 214 s[6][1] = (MP_DIGIT(a, 10) >> 32) << 32; 215 s[6][2] = MP_DIGIT(a, 11); 216 s[6][3] = 0; 217 s[6][4] = 0; 218 s[6][5] = 0; 219 s[7][0] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32); 220 for (i = 1; i < 6; i++) { 221 s[7][i] = (MP_DIGIT(a, i+5) >> 32) | (MP_DIGIT(a, i+6) << 32); 222 } 223 s[8][0] = MP_DIGIT(a, 10) << 32; 224 s[8][1] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32); 225 s[8][2] = MP_DIGIT(a, 11) >> 32; 226 s[8][3] = 0; 227 s[8][4] = 0; 228 s[8][5] = 0; 229 s[9][0] = 0; 230 s[9][1] = (MP_DIGIT(a, 11) >> 32) << 32; 231 s[9][2] = MP_DIGIT(a, 11) >> 32; 232 s[9][3] = 0; 233 s[9][4] = 0; 234 s[9][5] = 0; 235 236 MP_CHECKOK(mp_add(&m[0], &m[1], r)); 237 MP_CHECKOK(mp_add(r, &m[1], r)); 238 MP_CHECKOK(mp_add(r, &m[2], r)); 239 MP_CHECKOK(mp_add(r, &m[3], r)); 240 MP_CHECKOK(mp_add(r, &m[4], r)); 241 MP_CHECKOK(mp_add(r, &m[5], r)); 242 MP_CHECKOK(mp_add(r, &m[6], r)); 243 MP_CHECKOK(mp_sub(r, &m[7], r)); 244 MP_CHECKOK(mp_sub(r, &m[8], r)); 245 MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r)); 246 s_mp_clamp(r); 247 } 248#endif 249 250 CLEANUP: 251 return res; 252} 253 254/* Compute the square of polynomial a, reduce modulo p384. Store the 255 * result in r. r could be a. Uses optimized modular reduction for p384. 256 */ 257mp_err 258ec_GFp_nistp384_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 259{ 260 mp_err res = MP_OKAY; 261 262 MP_CHECKOK(mp_sqr(a, r)); 263 MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth)); 264 CLEANUP: 265 return res; 266} 267 268/* Compute the product of two polynomials a and b, reduce modulo p384. 269 * Store the result in r. r could be a or b; a could be b. Uses 270 * optimized modular reduction for p384. */ 271mp_err 272ec_GFp_nistp384_mul(const mp_int *a, const mp_int *b, mp_int *r, 273 const GFMethod *meth) 274{ 275 mp_err res = MP_OKAY; 276 277 MP_CHECKOK(mp_mul(a, b, r)); 278 MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth)); 279 CLEANUP: 280 return res; 281} 282 283/* Wire in fast field arithmetic and precomputation of base point for 284 * named curves. */ 285mp_err 286ec_group_set_gfp384(ECGroup *group, ECCurveName name) 287{ 288 if (name == ECCurve_NIST_P384) { 289 group->meth->field_mod = &ec_GFp_nistp384_mod; 290 group->meth->field_mul = &ec_GFp_nistp384_mul; 291 group->meth->field_sqr = &ec_GFp_nistp384_sqr; 292 } 293 return MP_OKAY; 294} 295