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