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