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