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, 2011, 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 p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r. 66 * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to 67 * Elliptic Curve Cryptography. */ 68 mp_err 69 ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 70 { 71 mp_err res = MP_OKAY; 72 mp_size a_used = MP_USED(a); 73 int a_bits = mpl_significant_bits(a); 74 mp_digit carry; 75 76 #ifdef ECL_THIRTY_TWO_BIT 77 mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0; 78 mp_digit r0, r1, r2, r3, r4, r5, r6, r7; 79 int r8; /* must be a signed value ! */ 80 #else 81 mp_digit a4=0, a5=0, a6=0, a7=0; 82 mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l; 83 mp_digit r0, r1, r2, r3; 84 int r4; /* must be a signed value ! */ 85 #endif 86 /* for polynomials larger than twice the field size 87 * use regular reduction */ 88 if (a_bits < 256) { 89 if (a == r) return MP_OKAY; 90 return mp_copy(a,r); 91 } 92 if (a_bits > 512) { 93 MP_CHECKOK(mp_mod(a, &meth->irr, r)); 94 } else { 95 96 #ifdef ECL_THIRTY_TWO_BIT 97 switch (a_used) { 98 case 16: 99 a15 = MP_DIGIT(a,15); 100 case 15: 101 a14 = MP_DIGIT(a,14); 102 case 14: 103 a13 = MP_DIGIT(a,13); 104 case 13: 105 a12 = MP_DIGIT(a,12); 106 case 12: 107 a11 = MP_DIGIT(a,11); 108 case 11: 109 a10 = MP_DIGIT(a,10); 110 case 10: 111 a9 = MP_DIGIT(a,9); 112 case 9: 113 a8 = MP_DIGIT(a,8); 114 } 115 116 r0 = MP_DIGIT(a,0); 117 r1 = MP_DIGIT(a,1); 118 r2 = MP_DIGIT(a,2); 119 r3 = MP_DIGIT(a,3); 120 r4 = MP_DIGIT(a,4); 121 r5 = MP_DIGIT(a,5); 122 r6 = MP_DIGIT(a,6); 123 r7 = MP_DIGIT(a,7); 124 125 /* sum 1 */ 126 MP_ADD_CARRY(r3, a11, r3, 0, carry); 127 MP_ADD_CARRY(r4, a12, r4, carry, carry); 128 MP_ADD_CARRY(r5, a13, r5, carry, carry); 129 MP_ADD_CARRY(r6, a14, r6, carry, carry); 130 MP_ADD_CARRY(r7, a15, r7, carry, carry); 131 r8 = carry; 132 MP_ADD_CARRY(r3, a11, r3, 0, carry); 133 MP_ADD_CARRY(r4, a12, r4, carry, carry); 134 MP_ADD_CARRY(r5, a13, r5, carry, carry); 135 MP_ADD_CARRY(r6, a14, r6, carry, carry); 136 MP_ADD_CARRY(r7, a15, r7, carry, carry); 137 r8 += carry; 138 /* sum 2 */ 139 MP_ADD_CARRY(r3, a12, r3, 0, carry); 140 MP_ADD_CARRY(r4, a13, r4, carry, carry); 141 MP_ADD_CARRY(r5, a14, r5, carry, carry); 142 MP_ADD_CARRY(r6, a15, r6, carry, carry); 143 MP_ADD_CARRY(r7, 0, r7, carry, carry); 144 r8 += carry; 145 /* combine last bottom of sum 3 with second sum 2 */ 146 MP_ADD_CARRY(r0, a8, r0, 0, carry); 147 MP_ADD_CARRY(r1, a9, r1, carry, carry); 148 MP_ADD_CARRY(r2, a10, r2, carry, carry); 149 MP_ADD_CARRY(r3, a12, r3, carry, carry); 150 MP_ADD_CARRY(r4, a13, r4, carry, carry); 151 MP_ADD_CARRY(r5, a14, r5, carry, carry); 152 MP_ADD_CARRY(r6, a15, r6, carry, carry); 153 MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */ 154 r8 += carry; 155 /* sum 3 (rest of it)*/ 156 MP_ADD_CARRY(r6, a14, r6, 0, carry); 157 MP_ADD_CARRY(r7, 0, r7, carry, carry); 158 r8 += carry; 159 /* sum 4 (rest of it)*/ 160 MP_ADD_CARRY(r0, a9, r0, 0, carry); 161 MP_ADD_CARRY(r1, a10, r1, carry, carry); 162 MP_ADD_CARRY(r2, a11, r2, carry, carry); 163 MP_ADD_CARRY(r3, a13, r3, carry, carry); 164 MP_ADD_CARRY(r4, a14, r4, carry, carry); 165 MP_ADD_CARRY(r5, a15, r5, carry, carry); 166 MP_ADD_CARRY(r6, a13, r6, carry, carry); 167 MP_ADD_CARRY(r7, a8, r7, carry, carry); 168 r8 += carry; 169 /* diff 5 */ 170 MP_SUB_BORROW(r0, a11, r0, 0, carry); 171 MP_SUB_BORROW(r1, a12, r1, carry, carry); 172 MP_SUB_BORROW(r2, a13, r2, carry, carry); 173 MP_SUB_BORROW(r3, 0, r3, carry, carry); 174 MP_SUB_BORROW(r4, 0, r4, carry, carry); 175 MP_SUB_BORROW(r5, 0, r5, carry, carry); 176 MP_SUB_BORROW(r6, a8, r6, carry, carry); 177 MP_SUB_BORROW(r7, a10, r7, carry, carry); 178 r8 -= carry; 179 /* diff 6 */ 180 MP_SUB_BORROW(r0, a12, r0, 0, carry); 181 MP_SUB_BORROW(r1, a13, r1, carry, carry); 182 MP_SUB_BORROW(r2, a14, r2, carry, carry); 183 MP_SUB_BORROW(r3, a15, r3, carry, carry); 184 MP_SUB_BORROW(r4, 0, r4, carry, carry); 185 MP_SUB_BORROW(r5, 0, r5, carry, carry); 186 MP_SUB_BORROW(r6, a9, r6, carry, carry); 187 MP_SUB_BORROW(r7, a11, r7, carry, carry); 188 r8 -= carry; 189 /* diff 7 */ 190 MP_SUB_BORROW(r0, a13, r0, 0, carry); 191 MP_SUB_BORROW(r1, a14, r1, carry, carry); 192 MP_SUB_BORROW(r2, a15, r2, carry, carry); 193 MP_SUB_BORROW(r3, a8, r3, carry, carry); 194 MP_SUB_BORROW(r4, a9, r4, carry, carry); 195 MP_SUB_BORROW(r5, a10, r5, carry, carry); 196 MP_SUB_BORROW(r6, 0, r6, carry, carry); 197 MP_SUB_BORROW(r7, a12, r7, carry, carry); 198 r8 -= carry; 199 /* diff 8 */ 200 MP_SUB_BORROW(r0, a14, r0, 0, carry); 201 MP_SUB_BORROW(r1, a15, r1, carry, carry); 202 MP_SUB_BORROW(r2, 0, r2, carry, carry); 203 MP_SUB_BORROW(r3, a9, r3, carry, carry); 204 MP_SUB_BORROW(r4, a10, r4, carry, carry); 205 MP_SUB_BORROW(r5, a11, r5, carry, carry); 206 MP_SUB_BORROW(r6, 0, r6, carry, carry); 207 MP_SUB_BORROW(r7, a13, r7, carry, carry); 208 r8 -= carry; 209 210 /* reduce the overflows */ 211 while (r8 > 0) { 212 mp_digit r8_d = r8; 213 MP_ADD_CARRY(r0, r8_d, r0, 0, carry); 214 MP_ADD_CARRY(r1, 0, r1, carry, carry); 215 MP_ADD_CARRY(r2, 0, r2, carry, carry); 216 MP_ADD_CARRY(r3, -r8_d, r3, carry, carry); 217 MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry); 218 MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry); 219 MP_ADD_CARRY(r6, -(r8_d+1), r6, carry, carry); 220 MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry); 221 r8 = carry; 222 } 223 224 /* reduce the underflows */ 225 while (r8 < 0) { 226 mp_digit r8_d = -r8; 227 MP_SUB_BORROW(r0, r8_d, r0, 0, carry); 228 MP_SUB_BORROW(r1, 0, r1, carry, carry); 229 MP_SUB_BORROW(r2, 0, r2, carry, carry); 230 MP_SUB_BORROW(r3, -r8_d, r3, carry, carry); 231 MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry); 232 MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry); 233 MP_SUB_BORROW(r6, -(r8_d+1), r6, carry, carry); 234 MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry); 235 r8 = -carry; 236 } 237 if (a != r) { 238 MP_CHECKOK(s_mp_pad(r,8)); 239 } 240 MP_SIGN(r) = MP_ZPOS; 241 MP_USED(r) = 8; 242 243 MP_DIGIT(r,7) = r7; 244 MP_DIGIT(r,6) = r6; 245 MP_DIGIT(r,5) = r5; 246 MP_DIGIT(r,4) = r4; 247 MP_DIGIT(r,3) = r3; 248 MP_DIGIT(r,2) = r2; 249 MP_DIGIT(r,1) = r1; 250 MP_DIGIT(r,0) = r0; 251 252 /* final reduction if necessary */ 253 if ((r7 == MP_DIGIT_MAX) && 254 ((r6 > 1) || ((r6 == 1) && 255 (r5 || r4 || r3 || 256 ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX) 257 && (r0 == MP_DIGIT_MAX)))))) { 258 MP_CHECKOK(mp_sub(r, &meth->irr, r)); 259 } 260 #ifdef notdef 261 262 263 /* smooth the negatives */ 264 while (MP_SIGN(r) != MP_ZPOS) { 265 MP_CHECKOK(mp_add(r, &meth->irr, r)); 266 } 267 while (MP_USED(r) > 8) { 268 MP_CHECKOK(mp_sub(r, &meth->irr, r)); 269 } 270 271 /* final reduction if necessary */ 272 if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) { 273 if (mp_cmp(r,&meth->irr) != MP_LT) { 274 MP_CHECKOK(mp_sub(r, &meth->irr, r)); 275 } 276 } 277 #endif 278 s_mp_clamp(r); 279 #else 280 switch (a_used) { 281 case 8: 282 a7 = MP_DIGIT(a,7); 283 case 7: 284 a6 = MP_DIGIT(a,6); 285 case 6: 286 a5 = MP_DIGIT(a,5); 287 case 5: 288 a4 = MP_DIGIT(a,4); 289 } 290 a7l = a7 << 32; 291 a7h = a7 >> 32; 292 a6l = a6 << 32; 293 a6h = a6 >> 32; 294 a5l = a5 << 32; 295 a5h = a5 >> 32; 296 a4l = a4 << 32; 297 a4h = a4 >> 32; 298 r3 = MP_DIGIT(a,3); 299 r2 = MP_DIGIT(a,2); 300 r1 = MP_DIGIT(a,1); 301 r0 = MP_DIGIT(a,0); 302 303 /* sum 1 */ 304 MP_ADD_CARRY_ZERO(r1, a5h << 32, r1, carry); 305 MP_ADD_CARRY(r2, a6, r2, carry, carry); 306 MP_ADD_CARRY(r3, a7, r3, carry, carry); 307 r4 = carry; 308 MP_ADD_CARRY_ZERO(r1, a5h << 32, r1, carry); 309 MP_ADD_CARRY(r2, a6, r2, carry, carry); 310 MP_ADD_CARRY(r3, a7, r3, carry, carry); 311 r4 += carry; 312 /* sum 2 */ 313 MP_ADD_CARRY_ZERO(r1, a6l, r1, carry); 314 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry); 315 MP_ADD_CARRY(r3, a7h, r3, carry, carry); 316 r4 += carry; 317 MP_ADD_CARRY_ZERO(r1, a6l, r1, carry); 318 MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry); 319 MP_ADD_CARRY(r3, a7h, r3, carry, carry); 320 r4 += carry; 321 322 /* sum 3 */ 323 MP_ADD_CARRY_ZERO(r0, a4, r0, carry); 324 MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry); 325 MP_ADD_CARRY(r2, 0, r2, carry, carry); 326 MP_ADD_CARRY(r3, a7, r3, carry, carry); 327 r4 += carry; 328 /* sum 4 */ 329 MP_ADD_CARRY_ZERO(r0, a4h | a5l, r0, carry); 330 MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry); 331 MP_ADD_CARRY(r2, a7, r2, carry, carry); 332 MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry); 333 r4 += carry; 334 /* diff 5 */ 335 MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry); 336 MP_SUB_BORROW(r1, a6h, r1, carry, carry); 337 MP_SUB_BORROW(r2, 0, r2, carry, carry); 338 MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry); 339 r4 -= carry; 340 /* diff 6 */ 341 MP_SUB_BORROW(r0, a6, r0, 0, carry); 342 MP_SUB_BORROW(r1, a7, r1, carry, carry); 343 MP_SUB_BORROW(r2, 0, r2, carry, carry); 344 MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry); 345 r4 -= carry; 346 /* diff 7 */ 347 MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry); 348 MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry); 349 MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry); 350 MP_SUB_BORROW(r3, a6l, r3, carry, carry); 351 r4 -= carry; 352 /* diff 8 */ 353 MP_SUB_BORROW(r0, a7, r0, 0, carry); 354 MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry); 355 MP_SUB_BORROW(r2, a5, r2, carry, carry); 356 MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry); 357 r4 -= carry; 358 359 /* reduce the overflows */ 360 while (r4 > 0) { 361 mp_digit r4_long = r4; 362 mp_digit r4l = (r4_long << 32); 363 MP_ADD_CARRY_ZERO(r0, r4_long, r0, carry); 364 MP_ADD_CARRY(r1, -r4l, r1, carry, carry); 365 MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry); 366 MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry); 367 r4 = carry; 368 } 369 370 /* reduce the underflows */ 371 while (r4 < 0) { 372 mp_digit r4_long = -r4; 373 mp_digit r4l = (r4_long << 32); 374 MP_SUB_BORROW(r0, r4_long, r0, 0, carry); 375 MP_SUB_BORROW(r1, -r4l, r1, carry, carry); 376 MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry); 377 MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry); 378 r4 = -carry; 379 } 380 381 if (a != r) { 382 MP_CHECKOK(s_mp_pad(r,4)); 383 } 384 MP_SIGN(r) = MP_ZPOS; 385 MP_USED(r) = 4; 386 387 MP_DIGIT(r,3) = r3; 388 MP_DIGIT(r,2) = r2; 389 MP_DIGIT(r,1) = r1; 390 MP_DIGIT(r,0) = r0; 391 392 /* final reduction if necessary */ 393 if ((r3 > 0xFFFFFFFF00000001ULL) || 394 ((r3 == 0xFFFFFFFF00000001ULL) && 395 (r2 || (r1 >> 32)|| 396 (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) { 397 /* very rare, just use mp_sub */ 398 MP_CHECKOK(mp_sub(r, &meth->irr, r)); 399 } 400 401 s_mp_clamp(r); 402 #endif 403 } 404 405 CLEANUP: 406 return res; 407 } 408 409 /* Compute the square of polynomial a, reduce modulo p256. Store the 410 * result in r. r could be a. Uses optimized modular reduction for p256. 411 */ 412 mp_err 413 ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 414 { 415 mp_err res = MP_OKAY; 416 417 MP_CHECKOK(mp_sqr(a, r)); 418 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); 419 CLEANUP: 420 return res; 421 } 422 423 /* Compute the product of two polynomials a and b, reduce modulo p256. 424 * Store the result in r. r could be a or b; a could be b. Uses 425 * optimized modular reduction for p256. */ 426 mp_err 427 ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r, 428 const GFMethod *meth) 429 { 430 mp_err res = MP_OKAY; 431 432 MP_CHECKOK(mp_mul(a, b, r)); 433 MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); 434 CLEANUP: 435 return res; 436 } 437 438 /* Wire in fast field arithmetic and precomputation of base point for 439 * named curves. */ 440 mp_err 441 ec_group_set_gfp256(ECGroup *group, ECCurveName name) 442 { 443 if (name == ECCurve_NIST_P256) { 444 group->meth->field_mod = &ec_GFp_nistp256_mod; 445 group->meth->field_mul = &ec_GFp_nistp256_mul; 446 group->meth->field_sqr = &ec_GFp_nistp256_sqr; 447 } 448 return MP_OKAY; 449 }