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 }