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 }