1/* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* ********************************************************************* 25 * 26 * The Original Code is the elliptic curve math library for binary polynomial field curves. 27 * 28 * The Initial Developer of the Original Code is 29 * Sun Microsystems, Inc. 30 * Portions created by the Initial Developer are Copyright (C) 2003 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Sheueling Chang-Shantz <sheueling.chang@sun.com>, 35 * Stephen Fung <fungstep@hotmail.com>, and 36 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories. 37 * 38 *********************************************************************** */ 39 40#include "ec2.h" 41#include "mp_gf2m.h" 42#include "mp_gf2m-priv.h" 43#include "mpi.h" 44#include "mpi-priv.h" 45#ifndef _KERNEL 46#include <stdlib.h> 47#endif 48 49/* Fast reduction for polynomials over a 163-bit curve. Assumes reduction 50 * polynomial with terms {163, 7, 6, 3, 0}. */ 51mp_err 52ec_GF2m_163_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 53{ 54 mp_err res = MP_OKAY; 55 mp_digit *u, z; 56 57 if (a != r) { 58 MP_CHECKOK(mp_copy(a, r)); 59 } 60#ifdef ECL_SIXTY_FOUR_BIT 61 if (MP_USED(r) < 6) { 62 MP_CHECKOK(s_mp_pad(r, 6)); 63 } 64 u = MP_DIGITS(r); 65 MP_USED(r) = 6; 66 67 /* u[5] only has 6 significant bits */ 68 z = u[5]; 69 u[2] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29); 70 z = u[4]; 71 u[2] ^= (z >> 28) ^ (z >> 29) ^ (z >> 32) ^ (z >> 35); 72 u[1] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29); 73 z = u[3]; 74 u[1] ^= (z >> 28) ^ (z >> 29) ^ (z >> 32) ^ (z >> 35); 75 u[0] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29); 76 z = u[2] >> 35; /* z only has 29 significant bits */ 77 u[0] ^= (z << 7) ^ (z << 6) ^ (z << 3) ^ z; 78 /* clear bits above 163 */ 79 u[5] = u[4] = u[3] = 0; 80 u[2] ^= z << 35; 81#else 82 if (MP_USED(r) < 11) { 83 MP_CHECKOK(s_mp_pad(r, 11)); 84 } 85 u = MP_DIGITS(r); 86 MP_USED(r) = 11; 87 88 /* u[11] only has 6 significant bits */ 89 z = u[10]; 90 u[5] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3); 91 u[4] ^= (z << 29); 92 z = u[9]; 93 u[5] ^= (z >> 28) ^ (z >> 29); 94 u[4] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3); 95 u[3] ^= (z << 29); 96 z = u[8]; 97 u[4] ^= (z >> 28) ^ (z >> 29); 98 u[3] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3); 99 u[2] ^= (z << 29); 100 z = u[7]; 101 u[3] ^= (z >> 28) ^ (z >> 29); 102 u[2] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3); 103 u[1] ^= (z << 29); 104 z = u[6]; 105 u[2] ^= (z >> 28) ^ (z >> 29); 106 u[1] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3); 107 u[0] ^= (z << 29); 108 z = u[5] >> 3; /* z only has 29 significant bits */ 109 u[1] ^= (z >> 25) ^ (z >> 26); 110 u[0] ^= (z << 7) ^ (z << 6) ^ (z << 3) ^ z; 111 /* clear bits above 163 */ 112 u[11] = u[10] = u[9] = u[8] = u[7] = u[6] = 0; 113 u[5] ^= z << 3; 114#endif 115 s_mp_clamp(r); 116 117 CLEANUP: 118 return res; 119} 120 121/* Fast squaring for polynomials over a 163-bit curve. Assumes reduction 122 * polynomial with terms {163, 7, 6, 3, 0}. */ 123mp_err 124ec_GF2m_163_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 125{ 126 mp_err res = MP_OKAY; 127 mp_digit *u, *v; 128 129 v = MP_DIGITS(a); 130 131#ifdef ECL_SIXTY_FOUR_BIT 132 if (MP_USED(a) < 3) { 133 return mp_bsqrmod(a, meth->irr_arr, r); 134 } 135 if (MP_USED(r) < 6) { 136 MP_CHECKOK(s_mp_pad(r, 6)); 137 } 138 MP_USED(r) = 6; 139#else 140 if (MP_USED(a) < 6) { 141 return mp_bsqrmod(a, meth->irr_arr, r); 142 } 143 if (MP_USED(r) < 12) { 144 MP_CHECKOK(s_mp_pad(r, 12)); 145 } 146 MP_USED(r) = 12; 147#endif 148 u = MP_DIGITS(r); 149 150#ifdef ECL_THIRTY_TWO_BIT 151 u[11] = gf2m_SQR1(v[5]); 152 u[10] = gf2m_SQR0(v[5]); 153 u[9] = gf2m_SQR1(v[4]); 154 u[8] = gf2m_SQR0(v[4]); 155 u[7] = gf2m_SQR1(v[3]); 156 u[6] = gf2m_SQR0(v[3]); 157#endif 158 u[5] = gf2m_SQR1(v[2]); 159 u[4] = gf2m_SQR0(v[2]); 160 u[3] = gf2m_SQR1(v[1]); 161 u[2] = gf2m_SQR0(v[1]); 162 u[1] = gf2m_SQR1(v[0]); 163 u[0] = gf2m_SQR0(v[0]); 164 return ec_GF2m_163_mod(r, r, meth); 165 166 CLEANUP: 167 return res; 168} 169 170/* Fast multiplication for polynomials over a 163-bit curve. Assumes 171 * reduction polynomial with terms {163, 7, 6, 3, 0}. */ 172mp_err 173ec_GF2m_163_mul(const mp_int *a, const mp_int *b, mp_int *r, 174 const GFMethod *meth) 175{ 176 mp_err res = MP_OKAY; 177 mp_digit a2 = 0, a1 = 0, a0, b2 = 0, b1 = 0, b0; 178 179#ifdef ECL_THIRTY_TWO_BIT 180 mp_digit a5 = 0, a4 = 0, a3 = 0, b5 = 0, b4 = 0, b3 = 0; 181 mp_digit rm[6]; 182#endif 183 184 if (a == b) { 185 return ec_GF2m_163_sqr(a, r, meth); 186 } else { 187 switch (MP_USED(a)) { 188#ifdef ECL_THIRTY_TWO_BIT 189 case 6: 190 a5 = MP_DIGIT(a, 5); 191 case 5: 192 a4 = MP_DIGIT(a, 4); 193 case 4: 194 a3 = MP_DIGIT(a, 3); 195#endif 196 case 3: 197 a2 = MP_DIGIT(a, 2); 198 case 2: 199 a1 = MP_DIGIT(a, 1); 200 default: 201 a0 = MP_DIGIT(a, 0); 202 } 203 switch (MP_USED(b)) { 204#ifdef ECL_THIRTY_TWO_BIT 205 case 6: 206 b5 = MP_DIGIT(b, 5); 207 case 5: 208 b4 = MP_DIGIT(b, 4); 209 case 4: 210 b3 = MP_DIGIT(b, 3); 211#endif 212 case 3: 213 b2 = MP_DIGIT(b, 2); 214 case 2: 215 b1 = MP_DIGIT(b, 1); 216 default: 217 b0 = MP_DIGIT(b, 0); 218 } 219#ifdef ECL_SIXTY_FOUR_BIT 220 MP_CHECKOK(s_mp_pad(r, 6)); 221 s_bmul_3x3(MP_DIGITS(r), a2, a1, a0, b2, b1, b0); 222 MP_USED(r) = 6; 223 s_mp_clamp(r); 224#else 225 MP_CHECKOK(s_mp_pad(r, 12)); 226 s_bmul_3x3(MP_DIGITS(r) + 6, a5, a4, a3, b5, b4, b3); 227 s_bmul_3x3(MP_DIGITS(r), a2, a1, a0, b2, b1, b0); 228 s_bmul_3x3(rm, a5 ^ a2, a4 ^ a1, a3 ^ a0, b5 ^ b2, b4 ^ b1, 229 b3 ^ b0); 230 rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 11); 231 rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 10); 232 rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 9); 233 rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 8); 234 rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 7); 235 rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 6); 236 MP_DIGIT(r, 8) ^= rm[5]; 237 MP_DIGIT(r, 7) ^= rm[4]; 238 MP_DIGIT(r, 6) ^= rm[3]; 239 MP_DIGIT(r, 5) ^= rm[2]; 240 MP_DIGIT(r, 4) ^= rm[1]; 241 MP_DIGIT(r, 3) ^= rm[0]; 242 MP_USED(r) = 12; 243 s_mp_clamp(r); 244#endif 245 return ec_GF2m_163_mod(r, r, meth); 246 } 247 248 CLEANUP: 249 return res; 250} 251 252/* Wire in fast field arithmetic for 163-bit curves. */ 253mp_err 254ec_group_set_gf2m163(ECGroup *group, ECCurveName name) 255{ 256 group->meth->field_mod = &ec_GF2m_163_mod; 257 group->meth->field_mul = &ec_GF2m_163_mul; 258 group->meth->field_sqr = &ec_GF2m_163_sqr; 259 return MP_OKAY; 260} 261