1f9fbec18Smcpowers /* 2f9fbec18Smcpowers * ***** BEGIN LICENSE BLOCK ***** 3f9fbec18Smcpowers * Version: MPL 1.1/GPL 2.0/LGPL 2.1 4f9fbec18Smcpowers * 5f9fbec18Smcpowers * The contents of this file are subject to the Mozilla Public License Version 6f9fbec18Smcpowers * 1.1 (the "License"); you may not use this file except in compliance with 7f9fbec18Smcpowers * the License. You may obtain a copy of the License at 8f9fbec18Smcpowers * http://www.mozilla.org/MPL/ 9f9fbec18Smcpowers * 10f9fbec18Smcpowers * Software distributed under the License is distributed on an "AS IS" basis, 11f9fbec18Smcpowers * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 12f9fbec18Smcpowers * for the specific language governing rights and limitations under the 13f9fbec18Smcpowers * License. 14f9fbec18Smcpowers * 15f9fbec18Smcpowers * The Original Code is the elliptic curve math library for binary polynomial field curves. 16f9fbec18Smcpowers * 17f9fbec18Smcpowers * The Initial Developer of the Original Code is 18f9fbec18Smcpowers * Sun Microsystems, Inc. 19f9fbec18Smcpowers * Portions created by the Initial Developer are Copyright (C) 2003 20f9fbec18Smcpowers * the Initial Developer. All Rights Reserved. 21f9fbec18Smcpowers * 22f9fbec18Smcpowers * Contributor(s): 23f9fbec18Smcpowers * Sheueling Chang-Shantz <sheueling.chang@sun.com>, 24f9fbec18Smcpowers * Stephen Fung <fungstep@hotmail.com>, and 25f9fbec18Smcpowers * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories. 26f9fbec18Smcpowers * 27f9fbec18Smcpowers * Alternatively, the contents of this file may be used under the terms of 28f9fbec18Smcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or 29f9fbec18Smcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 30f9fbec18Smcpowers * in which case the provisions of the GPL or the LGPL are applicable instead 31f9fbec18Smcpowers * of those above. If you wish to allow use of your version of this file only 32f9fbec18Smcpowers * under the terms of either the GPL or the LGPL, and not to allow others to 33f9fbec18Smcpowers * use your version of this file under the terms of the MPL, indicate your 34f9fbec18Smcpowers * decision by deleting the provisions above and replace them with the notice 35f9fbec18Smcpowers * and other provisions required by the GPL or the LGPL. If you do not delete 36f9fbec18Smcpowers * the provisions above, a recipient may use your version of this file under 37f9fbec18Smcpowers * the terms of any one of the MPL, the GPL or the LGPL. 38f9fbec18Smcpowers * 39f9fbec18Smcpowers * ***** END LICENSE BLOCK ***** */ 40f9fbec18Smcpowers /* 41f9fbec18Smcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 42f9fbec18Smcpowers * Use is subject to license terms. 43f9fbec18Smcpowers * 44f9fbec18Smcpowers * Sun elects to use this software under the MPL license. 45f9fbec18Smcpowers */ 46f9fbec18Smcpowers 47f9fbec18Smcpowers #include "ec2.h" 48f9fbec18Smcpowers #include "mp_gf2m.h" 49f9fbec18Smcpowers #include "mp_gf2m-priv.h" 50f9fbec18Smcpowers #include "mpi.h" 51f9fbec18Smcpowers #include "mpi-priv.h" 52f9fbec18Smcpowers #ifndef _KERNEL 53f9fbec18Smcpowers #include <stdlib.h> 54f9fbec18Smcpowers #endif 55f9fbec18Smcpowers 56f9fbec18Smcpowers /* Fast reduction for polynomials over a 233-bit curve. Assumes reduction 57f9fbec18Smcpowers * polynomial with terms {233, 74, 0}. */ 58f9fbec18Smcpowers mp_err 59f9fbec18Smcpowers ec_GF2m_233_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 60f9fbec18Smcpowers { 61f9fbec18Smcpowers mp_err res = MP_OKAY; 62f9fbec18Smcpowers mp_digit *u, z; 63f9fbec18Smcpowers 64f9fbec18Smcpowers if (a != r) { 65f9fbec18Smcpowers MP_CHECKOK(mp_copy(a, r)); 66f9fbec18Smcpowers } 67f9fbec18Smcpowers #ifdef ECL_SIXTY_FOUR_BIT 68f9fbec18Smcpowers if (MP_USED(r) < 8) { 69f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 8)); 70f9fbec18Smcpowers } 71f9fbec18Smcpowers u = MP_DIGITS(r); 72f9fbec18Smcpowers MP_USED(r) = 8; 73f9fbec18Smcpowers 74f9fbec18Smcpowers /* u[7] only has 18 significant bits */ 75f9fbec18Smcpowers z = u[7]; 76f9fbec18Smcpowers u[4] ^= (z << 33) ^ (z >> 41); 77f9fbec18Smcpowers u[3] ^= (z << 23); 78f9fbec18Smcpowers z = u[6]; 79f9fbec18Smcpowers u[4] ^= (z >> 31); 80f9fbec18Smcpowers u[3] ^= (z << 33) ^ (z >> 41); 81f9fbec18Smcpowers u[2] ^= (z << 23); 82f9fbec18Smcpowers z = u[5]; 83f9fbec18Smcpowers u[3] ^= (z >> 31); 84f9fbec18Smcpowers u[2] ^= (z << 33) ^ (z >> 41); 85f9fbec18Smcpowers u[1] ^= (z << 23); 86f9fbec18Smcpowers z = u[4]; 87f9fbec18Smcpowers u[2] ^= (z >> 31); 88f9fbec18Smcpowers u[1] ^= (z << 33) ^ (z >> 41); 89f9fbec18Smcpowers u[0] ^= (z << 23); 90f9fbec18Smcpowers z = u[3] >> 41; /* z only has 23 significant bits */ 91f9fbec18Smcpowers u[1] ^= (z << 10); 92f9fbec18Smcpowers u[0] ^= z; 93f9fbec18Smcpowers /* clear bits above 233 */ 94f9fbec18Smcpowers u[7] = u[6] = u[5] = u[4] = 0; 95f9fbec18Smcpowers u[3] ^= z << 41; 96f9fbec18Smcpowers #else 97f9fbec18Smcpowers if (MP_USED(r) < 15) { 98f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 15)); 99f9fbec18Smcpowers } 100f9fbec18Smcpowers u = MP_DIGITS(r); 101f9fbec18Smcpowers MP_USED(r) = 15; 102f9fbec18Smcpowers 103f9fbec18Smcpowers /* u[14] only has 18 significant bits */ 104f9fbec18Smcpowers z = u[14]; 105f9fbec18Smcpowers u[9] ^= (z << 1); 106f9fbec18Smcpowers u[7] ^= (z >> 9); 107f9fbec18Smcpowers u[6] ^= (z << 23); 108f9fbec18Smcpowers z = u[13]; 109f9fbec18Smcpowers u[9] ^= (z >> 31); 110f9fbec18Smcpowers u[8] ^= (z << 1); 111f9fbec18Smcpowers u[6] ^= (z >> 9); 112f9fbec18Smcpowers u[5] ^= (z << 23); 113f9fbec18Smcpowers z = u[12]; 114f9fbec18Smcpowers u[8] ^= (z >> 31); 115f9fbec18Smcpowers u[7] ^= (z << 1); 116f9fbec18Smcpowers u[5] ^= (z >> 9); 117f9fbec18Smcpowers u[4] ^= (z << 23); 118f9fbec18Smcpowers z = u[11]; 119f9fbec18Smcpowers u[7] ^= (z >> 31); 120f9fbec18Smcpowers u[6] ^= (z << 1); 121f9fbec18Smcpowers u[4] ^= (z >> 9); 122f9fbec18Smcpowers u[3] ^= (z << 23); 123f9fbec18Smcpowers z = u[10]; 124f9fbec18Smcpowers u[6] ^= (z >> 31); 125f9fbec18Smcpowers u[5] ^= (z << 1); 126f9fbec18Smcpowers u[3] ^= (z >> 9); 127f9fbec18Smcpowers u[2] ^= (z << 23); 128f9fbec18Smcpowers z = u[9]; 129f9fbec18Smcpowers u[5] ^= (z >> 31); 130f9fbec18Smcpowers u[4] ^= (z << 1); 131f9fbec18Smcpowers u[2] ^= (z >> 9); 132f9fbec18Smcpowers u[1] ^= (z << 23); 133f9fbec18Smcpowers z = u[8]; 134f9fbec18Smcpowers u[4] ^= (z >> 31); 135f9fbec18Smcpowers u[3] ^= (z << 1); 136f9fbec18Smcpowers u[1] ^= (z >> 9); 137f9fbec18Smcpowers u[0] ^= (z << 23); 138f9fbec18Smcpowers z = u[7] >> 9; /* z only has 23 significant bits */ 139f9fbec18Smcpowers u[3] ^= (z >> 22); 140f9fbec18Smcpowers u[2] ^= (z << 10); 141f9fbec18Smcpowers u[0] ^= z; 142f9fbec18Smcpowers /* clear bits above 233 */ 143f9fbec18Smcpowers u[14] = u[13] = u[12] = u[11] = u[10] = u[9] = u[8] = 0; 144f9fbec18Smcpowers u[7] ^= z << 9; 145f9fbec18Smcpowers #endif 146f9fbec18Smcpowers s_mp_clamp(r); 147f9fbec18Smcpowers 148f9fbec18Smcpowers CLEANUP: 149f9fbec18Smcpowers return res; 150f9fbec18Smcpowers } 151f9fbec18Smcpowers 152f9fbec18Smcpowers /* Fast squaring for polynomials over a 233-bit curve. Assumes reduction 153f9fbec18Smcpowers * polynomial with terms {233, 74, 0}. */ 154f9fbec18Smcpowers mp_err 155f9fbec18Smcpowers ec_GF2m_233_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 156f9fbec18Smcpowers { 157f9fbec18Smcpowers mp_err res = MP_OKAY; 158f9fbec18Smcpowers mp_digit *u, *v; 159f9fbec18Smcpowers 160f9fbec18Smcpowers v = MP_DIGITS(a); 161f9fbec18Smcpowers 162f9fbec18Smcpowers #ifdef ECL_SIXTY_FOUR_BIT 163f9fbec18Smcpowers if (MP_USED(a) < 4) { 164f9fbec18Smcpowers return mp_bsqrmod(a, meth->irr_arr, r); 165f9fbec18Smcpowers } 166f9fbec18Smcpowers if (MP_USED(r) < 8) { 167f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 8)); 168f9fbec18Smcpowers } 169f9fbec18Smcpowers MP_USED(r) = 8; 170f9fbec18Smcpowers #else 171f9fbec18Smcpowers if (MP_USED(a) < 8) { 172f9fbec18Smcpowers return mp_bsqrmod(a, meth->irr_arr, r); 173f9fbec18Smcpowers } 174f9fbec18Smcpowers if (MP_USED(r) < 15) { 175f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 15)); 176f9fbec18Smcpowers } 177f9fbec18Smcpowers MP_USED(r) = 15; 178f9fbec18Smcpowers #endif 179f9fbec18Smcpowers u = MP_DIGITS(r); 180f9fbec18Smcpowers 181f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT 182f9fbec18Smcpowers u[14] = gf2m_SQR0(v[7]); 183f9fbec18Smcpowers u[13] = gf2m_SQR1(v[6]); 184f9fbec18Smcpowers u[12] = gf2m_SQR0(v[6]); 185f9fbec18Smcpowers u[11] = gf2m_SQR1(v[5]); 186f9fbec18Smcpowers u[10] = gf2m_SQR0(v[5]); 187f9fbec18Smcpowers u[9] = gf2m_SQR1(v[4]); 188f9fbec18Smcpowers u[8] = gf2m_SQR0(v[4]); 189f9fbec18Smcpowers #endif 190f9fbec18Smcpowers u[7] = gf2m_SQR1(v[3]); 191f9fbec18Smcpowers u[6] = gf2m_SQR0(v[3]); 192f9fbec18Smcpowers u[5] = gf2m_SQR1(v[2]); 193f9fbec18Smcpowers u[4] = gf2m_SQR0(v[2]); 194f9fbec18Smcpowers u[3] = gf2m_SQR1(v[1]); 195f9fbec18Smcpowers u[2] = gf2m_SQR0(v[1]); 196f9fbec18Smcpowers u[1] = gf2m_SQR1(v[0]); 197f9fbec18Smcpowers u[0] = gf2m_SQR0(v[0]); 198f9fbec18Smcpowers return ec_GF2m_233_mod(r, r, meth); 199f9fbec18Smcpowers 200f9fbec18Smcpowers CLEANUP: 201f9fbec18Smcpowers return res; 202f9fbec18Smcpowers } 203f9fbec18Smcpowers 204f9fbec18Smcpowers /* Fast multiplication for polynomials over a 233-bit curve. Assumes 205f9fbec18Smcpowers * reduction polynomial with terms {233, 74, 0}. */ 206f9fbec18Smcpowers mp_err 207f9fbec18Smcpowers ec_GF2m_233_mul(const mp_int *a, const mp_int *b, mp_int *r, 208f9fbec18Smcpowers const GFMethod *meth) 209f9fbec18Smcpowers { 210f9fbec18Smcpowers mp_err res = MP_OKAY; 211f9fbec18Smcpowers mp_digit a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0; 212f9fbec18Smcpowers 213f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT 214f9fbec18Smcpowers mp_digit a7 = 0, a6 = 0, a5 = 0, a4 = 0, b7 = 0, b6 = 0, b5 = 0, b4 = 215f9fbec18Smcpowers 0; 216f9fbec18Smcpowers mp_digit rm[8]; 217f9fbec18Smcpowers #endif 218f9fbec18Smcpowers 219f9fbec18Smcpowers if (a == b) { 220f9fbec18Smcpowers return ec_GF2m_233_sqr(a, r, meth); 221f9fbec18Smcpowers } else { 222f9fbec18Smcpowers switch (MP_USED(a)) { 223f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT 224f9fbec18Smcpowers case 8: 225f9fbec18Smcpowers a7 = MP_DIGIT(a, 7); 226*38a641c5SToomas Soome /* FALLTHROUGH */ 227f9fbec18Smcpowers case 7: 228f9fbec18Smcpowers a6 = MP_DIGIT(a, 6); 229*38a641c5SToomas Soome /* FALLTHROUGH */ 230f9fbec18Smcpowers case 6: 231f9fbec18Smcpowers a5 = MP_DIGIT(a, 5); 232*38a641c5SToomas Soome /* FALLTHROUGH */ 233f9fbec18Smcpowers case 5: 234f9fbec18Smcpowers a4 = MP_DIGIT(a, 4); 235f9fbec18Smcpowers #endif 236*38a641c5SToomas Soome /* FALLTHROUGH */ 237f9fbec18Smcpowers case 4: 238f9fbec18Smcpowers a3 = MP_DIGIT(a, 3); 239*38a641c5SToomas Soome /* FALLTHROUGH */ 240f9fbec18Smcpowers case 3: 241f9fbec18Smcpowers a2 = MP_DIGIT(a, 2); 242*38a641c5SToomas Soome /* FALLTHROUGH */ 243f9fbec18Smcpowers case 2: 244f9fbec18Smcpowers a1 = MP_DIGIT(a, 1); 245*38a641c5SToomas Soome /* FALLTHROUGH */ 246f9fbec18Smcpowers default: 247f9fbec18Smcpowers a0 = MP_DIGIT(a, 0); 248f9fbec18Smcpowers } 249f9fbec18Smcpowers switch (MP_USED(b)) { 250f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT 251f9fbec18Smcpowers case 8: 252f9fbec18Smcpowers b7 = MP_DIGIT(b, 7); 253*38a641c5SToomas Soome /* FALLTHROUGH */ 254f9fbec18Smcpowers case 7: 255f9fbec18Smcpowers b6 = MP_DIGIT(b, 6); 256*38a641c5SToomas Soome /* FALLTHROUGH */ 257f9fbec18Smcpowers case 6: 258f9fbec18Smcpowers b5 = MP_DIGIT(b, 5); 259*38a641c5SToomas Soome /* FALLTHROUGH */ 260f9fbec18Smcpowers case 5: 261f9fbec18Smcpowers b4 = MP_DIGIT(b, 4); 262f9fbec18Smcpowers #endif 263*38a641c5SToomas Soome /* FALLTHROUGH */ 264f9fbec18Smcpowers case 4: 265f9fbec18Smcpowers b3 = MP_DIGIT(b, 3); 266*38a641c5SToomas Soome /* FALLTHROUGH */ 267f9fbec18Smcpowers case 3: 268f9fbec18Smcpowers b2 = MP_DIGIT(b, 2); 269*38a641c5SToomas Soome /* FALLTHROUGH */ 270f9fbec18Smcpowers case 2: 271f9fbec18Smcpowers b1 = MP_DIGIT(b, 1); 272*38a641c5SToomas Soome /* FALLTHROUGH */ 273f9fbec18Smcpowers default: 274f9fbec18Smcpowers b0 = MP_DIGIT(b, 0); 275f9fbec18Smcpowers } 276f9fbec18Smcpowers #ifdef ECL_SIXTY_FOUR_BIT 277f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 8)); 278f9fbec18Smcpowers s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); 279f9fbec18Smcpowers MP_USED(r) = 8; 280f9fbec18Smcpowers s_mp_clamp(r); 281f9fbec18Smcpowers #else 282f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 16)); 283f9fbec18Smcpowers s_bmul_4x4(MP_DIGITS(r) + 8, a7, a6, a5, a4, b7, b6, b5, b4); 284f9fbec18Smcpowers s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); 285f9fbec18Smcpowers s_bmul_4x4(rm, a7 ^ a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b7 ^ b3, 286f9fbec18Smcpowers b6 ^ b2, b5 ^ b1, b4 ^ b0); 287f9fbec18Smcpowers rm[7] ^= MP_DIGIT(r, 7) ^ MP_DIGIT(r, 15); 288f9fbec18Smcpowers rm[6] ^= MP_DIGIT(r, 6) ^ MP_DIGIT(r, 14); 289f9fbec18Smcpowers rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13); 290f9fbec18Smcpowers rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12); 291f9fbec18Smcpowers rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11); 292f9fbec18Smcpowers rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10); 293f9fbec18Smcpowers rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9); 294f9fbec18Smcpowers rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8); 295f9fbec18Smcpowers MP_DIGIT(r, 11) ^= rm[7]; 296f9fbec18Smcpowers MP_DIGIT(r, 10) ^= rm[6]; 297f9fbec18Smcpowers MP_DIGIT(r, 9) ^= rm[5]; 298f9fbec18Smcpowers MP_DIGIT(r, 8) ^= rm[4]; 299f9fbec18Smcpowers MP_DIGIT(r, 7) ^= rm[3]; 300f9fbec18Smcpowers MP_DIGIT(r, 6) ^= rm[2]; 301f9fbec18Smcpowers MP_DIGIT(r, 5) ^= rm[1]; 302f9fbec18Smcpowers MP_DIGIT(r, 4) ^= rm[0]; 303f9fbec18Smcpowers MP_USED(r) = 16; 304f9fbec18Smcpowers s_mp_clamp(r); 305f9fbec18Smcpowers #endif 306f9fbec18Smcpowers return ec_GF2m_233_mod(r, r, meth); 307f9fbec18Smcpowers } 308f9fbec18Smcpowers 309f9fbec18Smcpowers CLEANUP: 310f9fbec18Smcpowers return res; 311f9fbec18Smcpowers } 312f9fbec18Smcpowers 313f9fbec18Smcpowers /* Wire in fast field arithmetic for 233-bit curves. */ 314f9fbec18Smcpowers mp_err 315f9fbec18Smcpowers ec_group_set_gf2m233(ECGroup *group, ECCurveName name) 316f9fbec18Smcpowers { 317f9fbec18Smcpowers group->meth->field_mod = &ec_GF2m_233_mod; 318f9fbec18Smcpowers group->meth->field_mul = &ec_GF2m_233_mul; 319f9fbec18Smcpowers group->meth->field_sqr = &ec_GF2m_233_sqr; 320f9fbec18Smcpowers return MP_OKAY; 321f9fbec18Smcpowers } 322