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