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 } 270