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 193-bit curve. Assumes reduction 50 * polynomial with terms {193, 15, 0}. */ 51mp_err 52ec_GF2m_193_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) < 7) { 62 MP_CHECKOK(s_mp_pad(r, 7)); 63 } 64 u = MP_DIGITS(r); 65 MP_USED(r) = 7; 66 67 /* u[6] only has 2 significant bits */ 68 z = u[6]; 69 u[3] ^= (z << 14) ^ (z >> 1); 70 u[2] ^= (z << 63); 71 z = u[5]; 72 u[3] ^= (z >> 50); 73 u[2] ^= (z << 14) ^ (z >> 1); 74 u[1] ^= (z << 63); 75 z = u[4]; 76 u[2] ^= (z >> 50); 77 u[1] ^= (z << 14) ^ (z >> 1); 78 u[0] ^= (z << 63); 79 z = u[3] >> 1; /* z only has 63 significant bits */ 80 u[1] ^= (z >> 49); 81 u[0] ^= (z << 15) ^ z; 82 /* clear bits above 193 */ 83 u[6] = u[5] = u[4] = 0; 84 u[3] ^= z << 1; 85#else 86 if (MP_USED(r) < 13) { 87 MP_CHECKOK(s_mp_pad(r, 13)); 88 } 89 u = MP_DIGITS(r); 90 MP_USED(r) = 13; 91 92 /* u[12] only has 2 significant bits */ 93 z = u[12]; 94 u[6] ^= (z << 14) ^ (z >> 1); 95 u[5] ^= (z << 31); 96 z = u[11]; 97 u[6] ^= (z >> 18); 98 u[5] ^= (z << 14) ^ (z >> 1); 99 u[4] ^= (z << 31); 100 z = u[10]; 101 u[5] ^= (z >> 18); 102 u[4] ^= (z << 14) ^ (z >> 1); 103 u[3] ^= (z << 31); 104 z = u[9]; 105 u[4] ^= (z >> 18); 106 u[3] ^= (z << 14) ^ (z >> 1); 107 u[2] ^= (z << 31); 108 z = u[8]; 109 u[3] ^= (z >> 18); 110 u[2] ^= (z << 14) ^ (z >> 1); 111 u[1] ^= (z << 31); 112 z = u[7]; 113 u[2] ^= (z >> 18); 114 u[1] ^= (z << 14) ^ (z >> 1); 115 u[0] ^= (z << 31); 116 z = u[6] >> 1; /* z only has 31 significant bits */ 117 u[1] ^= (z >> 17); 118 u[0] ^= (z << 15) ^ z; 119 /* clear bits above 193 */ 120 u[12] = u[11] = u[10] = u[9] = u[8] = u[7] = 0; 121 u[6] ^= z << 1; 122#endif 123 s_mp_clamp(r); 124 125 CLEANUP: 126 return res; 127} 128 129/* Fast squaring for polynomials over a 193-bit curve. Assumes reduction 130 * polynomial with terms {193, 15, 0}. */ 131mp_err 132ec_GF2m_193_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 133{ 134 mp_err res = MP_OKAY; 135 mp_digit *u, *v; 136 137 v = MP_DIGITS(a); 138 139#ifdef ECL_SIXTY_FOUR_BIT 140 if (MP_USED(a) < 4) { 141 return mp_bsqrmod(a, meth->irr_arr, r); 142 } 143 if (MP_USED(r) < 7) { 144 MP_CHECKOK(s_mp_pad(r, 7)); 145 } 146 MP_USED(r) = 7; 147#else 148 if (MP_USED(a) < 7) { 149 return mp_bsqrmod(a, meth->irr_arr, r); 150 } 151 if (MP_USED(r) < 13) { 152 MP_CHECKOK(s_mp_pad(r, 13)); 153 } 154 MP_USED(r) = 13; 155#endif 156 u = MP_DIGITS(r); 157 158#ifdef ECL_THIRTY_TWO_BIT 159 u[12] = gf2m_SQR0(v[6]); 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#endif 166 u[6] = gf2m_SQR0(v[3]); 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_193_mod(r, r, meth); 174 175 CLEANUP: 176 return res; 177} 178 179/* Fast multiplication for polynomials over a 193-bit curve. Assumes 180 * reduction polynomial with terms {193, 15, 0}. */ 181mp_err 182ec_GF2m_193_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 a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0; 187 188#ifdef ECL_THIRTY_TWO_BIT 189 mp_digit a6 = 0, a5 = 0, a4 = 0, b6 = 0, b5 = 0, b4 = 0; 190 mp_digit rm[8]; 191#endif 192 193 if (a == b) { 194 return ec_GF2m_193_sqr(a, r, meth); 195 } else { 196 switch (MP_USED(a)) { 197#ifdef ECL_THIRTY_TWO_BIT 198 case 7: 199 a6 = MP_DIGIT(a, 6); 200 case 6: 201 a5 = MP_DIGIT(a, 5); 202 case 5: 203 a4 = MP_DIGIT(a, 4); 204#endif 205 case 4: 206 a3 = MP_DIGIT(a, 3); 207 case 3: 208 a2 = MP_DIGIT(a, 2); 209 case 2: 210 a1 = MP_DIGIT(a, 1); 211 default: 212 a0 = MP_DIGIT(a, 0); 213 } 214 switch (MP_USED(b)) { 215#ifdef ECL_THIRTY_TWO_BIT 216 case 7: 217 b6 = MP_DIGIT(b, 6); 218 case 6: 219 b5 = MP_DIGIT(b, 5); 220 case 5: 221 b4 = MP_DIGIT(b, 4); 222#endif 223 case 4: 224 b3 = MP_DIGIT(b, 3); 225 case 3: 226 b2 = MP_DIGIT(b, 2); 227 case 2: 228 b1 = MP_DIGIT(b, 1); 229 default: 230 b0 = MP_DIGIT(b, 0); 231 } 232#ifdef ECL_SIXTY_FOUR_BIT 233 MP_CHECKOK(s_mp_pad(r, 8)); 234 s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); 235 MP_USED(r) = 8; 236 s_mp_clamp(r); 237#else 238 MP_CHECKOK(s_mp_pad(r, 14)); 239 s_bmul_3x3(MP_DIGITS(r) + 8, a6, a5, a4, b6, b5, b4); 240 s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); 241 s_bmul_4x4(rm, a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b3, b6 ^ b2, b5 ^ b1, 242 b4 ^ b0); 243 rm[7] ^= MP_DIGIT(r, 7); 244 rm[6] ^= MP_DIGIT(r, 6); 245 rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13); 246 rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12); 247 rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11); 248 rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10); 249 rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9); 250 rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8); 251 MP_DIGIT(r, 11) ^= rm[7]; 252 MP_DIGIT(r, 10) ^= rm[6]; 253 MP_DIGIT(r, 9) ^= rm[5]; 254 MP_DIGIT(r, 8) ^= rm[4]; 255 MP_DIGIT(r, 7) ^= rm[3]; 256 MP_DIGIT(r, 6) ^= rm[2]; 257 MP_DIGIT(r, 5) ^= rm[1]; 258 MP_DIGIT(r, 4) ^= rm[0]; 259 MP_USED(r) = 14; 260 s_mp_clamp(r); 261#endif 262 return ec_GF2m_193_mod(r, r, meth); 263 } 264 265 CLEANUP: 266 return res; 267} 268 269/* Wire in fast field arithmetic for 193-bit curves. */ 270mp_err 271ec_group_set_gf2m193(ECGroup *group, ECCurveName name) 272{ 273 group->meth->field_mod = &ec_GF2m_193_mod; 274 group->meth->field_mul = &ec_GF2m_193_mul; 275 group->meth->field_sqr = &ec_GF2m_193_sqr; 276 return MP_OKAY; 277} 278