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 binary polynomial 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  *   Sheueling Chang-Shantz <sheueling.chang@sun.com>,
  38  *   Stephen Fung <fungstep@hotmail.com>, and
  39  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
  40  *
  41  * Alternatively, the contents of this file may be used under the terms of
  42  * either the GNU General Public License Version 2 or later (the "GPL"), or
  43  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  44  * in which case the provisions of the GPL or the LGPL are applicable instead
  45  * of those above. If you wish to allow use of your version of this file only
  46  * under the terms of either the GPL or the LGPL, and not to allow others to
  47  * use your version of this file under the terms of the MPL, indicate your
  48  * decision by deleting the provisions above and replace them with the notice
  49  * and other provisions required by the GPL or the LGPL. If you do not delete
  50  * the provisions above, a recipient may use your version of this file under
  51  * the terms of any one of the MPL, the GPL or the LGPL.
  52  *
  53  *********************************************************************** */
  54 /*
  55  * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved.
  56  * Use is subject to license terms.
  57  */
  58 
  59 #include "ec2.h"
  60 #include "mp_gf2m.h"
  61 #include "mp_gf2m-priv.h"
  62 #include "mpi.h"
  63 #include "mpi-priv.h"
  64 #ifndef _KERNEL
  65 #include <stdlib.h>
  66 #endif
  67 
  68 /* Fast reduction for polynomials over a 233-bit curve. Assumes reduction
  69  * polynomial with terms {233, 74, 0}. */
  70 mp_err
  71 ec_GF2m_233_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
  72 {
  73         mp_err res = MP_OKAY;
  74         mp_digit *u, z;
  75 
  76         if (a != r) {
  77                 MP_CHECKOK(mp_copy(a, r));
  78         }
  79 #ifdef ECL_SIXTY_FOUR_BIT
  80         if (MP_USED(r) < 8) {
  81                 MP_CHECKOK(s_mp_pad(r, 8));
  82         }
  83         u = MP_DIGITS(r);
  84         MP_USED(r) = 8;
  85 
  86         /* u[7] only has 18 significant bits */
  87         z = u[7];
  88         u[4] ^= (z << 33) ^ (z >> 41);
  89         u[3] ^= (z << 23);
  90         z = u[6];
  91         u[4] ^= (z >> 31);
  92         u[3] ^= (z << 33) ^ (z >> 41);
  93         u[2] ^= (z << 23);
  94         z = u[5];
  95         u[3] ^= (z >> 31);
  96         u[2] ^= (z << 33) ^ (z >> 41);
  97         u[1] ^= (z << 23);
  98         z = u[4];
  99         u[2] ^= (z >> 31);
 100         u[1] ^= (z << 33) ^ (z >> 41);
 101         u[0] ^= (z << 23);
 102         z = u[3] >> 41;                         /* z only has 23 significant bits */
 103         u[1] ^= (z << 10);
 104         u[0] ^= z;
 105         /* clear bits above 233 */
 106         u[7] = u[6] = u[5] = u[4] = 0;
 107         u[3] ^= z << 41;
 108 #else
 109         if (MP_USED(r) < 15) {
 110                 MP_CHECKOK(s_mp_pad(r, 15));
 111         }
 112         u = MP_DIGITS(r);
 113         MP_USED(r) = 15;
 114 
 115         /* u[14] only has 18 significant bits */
 116         z = u[14];
 117         u[9] ^= (z << 1);
 118         u[7] ^= (z >> 9);
 119         u[6] ^= (z << 23);
 120         z = u[13];
 121         u[9] ^= (z >> 31);
 122         u[8] ^= (z << 1);
 123         u[6] ^= (z >> 9);
 124         u[5] ^= (z << 23);
 125         z = u[12];
 126         u[8] ^= (z >> 31);
 127         u[7] ^= (z << 1);
 128         u[5] ^= (z >> 9);
 129         u[4] ^= (z << 23);
 130         z = u[11];
 131         u[7] ^= (z >> 31);
 132         u[6] ^= (z << 1);
 133         u[4] ^= (z >> 9);
 134         u[3] ^= (z << 23);
 135         z = u[10];
 136         u[6] ^= (z >> 31);
 137         u[5] ^= (z << 1);
 138         u[3] ^= (z >> 9);
 139         u[2] ^= (z << 23);
 140         z = u[9];
 141         u[5] ^= (z >> 31);
 142         u[4] ^= (z << 1);
 143         u[2] ^= (z >> 9);
 144         u[1] ^= (z << 23);
 145         z = u[8];
 146         u[4] ^= (z >> 31);
 147         u[3] ^= (z << 1);
 148         u[1] ^= (z >> 9);
 149         u[0] ^= (z << 23);
 150         z = u[7] >> 9;                          /* z only has 23 significant bits */
 151         u[3] ^= (z >> 22);
 152         u[2] ^= (z << 10);
 153         u[0] ^= z;
 154         /* clear bits above 233 */
 155         u[14] = u[13] = u[12] = u[11] = u[10] = u[9] = u[8] = 0;
 156         u[7] ^= z << 9;
 157 #endif
 158         s_mp_clamp(r);
 159 
 160   CLEANUP:
 161         return res;
 162 }
 163 
 164 /* Fast squaring for polynomials over a 233-bit curve. Assumes reduction
 165  * polynomial with terms {233, 74, 0}. */
 166 mp_err
 167 ec_GF2m_233_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
 168 {
 169         mp_err res = MP_OKAY;
 170         mp_digit *u, *v;
 171 
 172         v = MP_DIGITS(a);
 173 
 174 #ifdef ECL_SIXTY_FOUR_BIT
 175         if (MP_USED(a) < 4) {
 176                 return mp_bsqrmod(a, meth->irr_arr, r);
 177         }
 178         if (MP_USED(r) < 8) {
 179                 MP_CHECKOK(s_mp_pad(r, 8));
 180         }
 181         MP_USED(r) = 8;
 182 #else
 183         if (MP_USED(a) < 8) {
 184                 return mp_bsqrmod(a, meth->irr_arr, r);
 185         }
 186         if (MP_USED(r) < 15) {
 187                 MP_CHECKOK(s_mp_pad(r, 15));
 188         }
 189         MP_USED(r) = 15;
 190 #endif
 191         u = MP_DIGITS(r);
 192 
 193 #ifdef ECL_THIRTY_TWO_BIT
 194         u[14] = gf2m_SQR0(v[7]);
 195         u[13] = gf2m_SQR1(v[6]);
 196         u[12] = gf2m_SQR0(v[6]);
 197         u[11] = gf2m_SQR1(v[5]);
 198         u[10] = gf2m_SQR0(v[5]);
 199         u[9] = gf2m_SQR1(v[4]);
 200         u[8] = gf2m_SQR0(v[4]);
 201 #endif
 202         u[7] = gf2m_SQR1(v[3]);
 203         u[6] = gf2m_SQR0(v[3]);
 204         u[5] = gf2m_SQR1(v[2]);
 205         u[4] = gf2m_SQR0(v[2]);
 206         u[3] = gf2m_SQR1(v[1]);
 207         u[2] = gf2m_SQR0(v[1]);
 208         u[1] = gf2m_SQR1(v[0]);
 209         u[0] = gf2m_SQR0(v[0]);
 210         return ec_GF2m_233_mod(r, r, meth);
 211 
 212   CLEANUP:
 213         return res;
 214 }
 215 
 216 /* Fast multiplication for polynomials over a 233-bit curve. Assumes
 217  * reduction polynomial with terms {233, 74, 0}. */
 218 mp_err
 219 ec_GF2m_233_mul(const mp_int *a, const mp_int *b, mp_int *r,
 220                                 const GFMethod *meth)
 221 {
 222         mp_err res = MP_OKAY;
 223         mp_digit a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0;
 224 
 225 #ifdef ECL_THIRTY_TWO_BIT
 226         mp_digit a7 = 0, a6 = 0, a5 = 0, a4 = 0, b7 = 0, b6 = 0, b5 = 0, b4 =
 227                 0;
 228         mp_digit rm[8];
 229 #endif
 230 
 231         if (a == b) {
 232                 return ec_GF2m_233_sqr(a, r, meth);
 233         } else {
 234                 switch (MP_USED(a)) {
 235 #ifdef ECL_THIRTY_TWO_BIT
 236                 case 8:
 237                         a7 = MP_DIGIT(a, 7);
 238                 case 7:
 239                         a6 = MP_DIGIT(a, 6);
 240                 case 6:
 241                         a5 = MP_DIGIT(a, 5);
 242                 case 5:
 243                         a4 = MP_DIGIT(a, 4);
 244 #endif
 245                 case 4:
 246                         a3 = MP_DIGIT(a, 3);
 247                 case 3:
 248                         a2 = MP_DIGIT(a, 2);
 249                 case 2:
 250                         a1 = MP_DIGIT(a, 1);
 251                 default:
 252                         a0 = MP_DIGIT(a, 0);
 253                 }
 254                 switch (MP_USED(b)) {
 255 #ifdef ECL_THIRTY_TWO_BIT
 256                 case 8:
 257                         b7 = MP_DIGIT(b, 7);
 258                 case 7:
 259                         b6 = MP_DIGIT(b, 6);
 260                 case 6:
 261                         b5 = MP_DIGIT(b, 5);
 262                 case 5:
 263                         b4 = MP_DIGIT(b, 4);
 264 #endif
 265                 case 4:
 266                         b3 = MP_DIGIT(b, 3);
 267                 case 3:
 268                         b2 = MP_DIGIT(b, 2);
 269                 case 2:
 270                         b1 = MP_DIGIT(b, 1);
 271                 default:
 272                         b0 = MP_DIGIT(b, 0);
 273                 }
 274 #ifdef ECL_SIXTY_FOUR_BIT
 275                 MP_CHECKOK(s_mp_pad(r, 8));
 276                 s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0);
 277                 MP_USED(r) = 8;
 278                 s_mp_clamp(r);
 279 #else
 280                 MP_CHECKOK(s_mp_pad(r, 16));
 281                 s_bmul_4x4(MP_DIGITS(r) + 8, a7, a6, a5, a4, b7, b6, b5, b4);
 282                 s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0);
 283                 s_bmul_4x4(rm, a7 ^ a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b7 ^ b3,
 284                                    b6 ^ b2, b5 ^ b1, b4 ^ b0);
 285                 rm[7] ^= MP_DIGIT(r, 7) ^ MP_DIGIT(r, 15);
 286                 rm[6] ^= MP_DIGIT(r, 6) ^ MP_DIGIT(r, 14);
 287                 rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13);
 288                 rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12);
 289                 rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11);
 290                 rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10);
 291                 rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9);
 292                 rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8);
 293                 MP_DIGIT(r, 11) ^= rm[7];
 294                 MP_DIGIT(r, 10) ^= rm[6];
 295                 MP_DIGIT(r, 9) ^= rm[5];
 296                 MP_DIGIT(r, 8) ^= rm[4];
 297                 MP_DIGIT(r, 7) ^= rm[3];
 298                 MP_DIGIT(r, 6) ^= rm[2];
 299                 MP_DIGIT(r, 5) ^= rm[1];
 300                 MP_DIGIT(r, 4) ^= rm[0];
 301                 MP_USED(r) = 16;
 302                 s_mp_clamp(r);
 303 #endif
 304                 return ec_GF2m_233_mod(r, r, meth);
 305         }
 306 
 307   CLEANUP:
 308         return res;
 309 }
 310 
 311 /* Wire in fast field arithmetic for 233-bit curves. */
 312 mp_err
 313 ec_group_set_gf2m233(ECGroup *group, ECCurveName name)
 314 {
 315         group->meth->field_mod = &ec_GF2m_233_mod;
 316         group->meth->field_mul = &ec_GF2m_233_mul;
 317         group->meth->field_sqr = &ec_GF2m_233_sqr;
 318         return MP_OKAY;
 319 }