usr/src/common/crypto/ecc/ecp_384.c

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