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 prime 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 * Douglas Stebila <douglas@stebila.ca> 24f9fbec18Smcpowers * 25f9fbec18Smcpowers * Alternatively, the contents of this file may be used under the terms of 26f9fbec18Smcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or 27f9fbec18Smcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 28f9fbec18Smcpowers * in which case the provisions of the GPL or the LGPL are applicable instead 29f9fbec18Smcpowers * of those above. If you wish to allow use of your version of this file only 30f9fbec18Smcpowers * under the terms of either the GPL or the LGPL, and not to allow others to 31f9fbec18Smcpowers * use your version of this file under the terms of the MPL, indicate your 32f9fbec18Smcpowers * decision by deleting the provisions above and replace them with the notice 33f9fbec18Smcpowers * and other provisions required by the GPL or the LGPL. If you do not delete 34f9fbec18Smcpowers * the provisions above, a recipient may use your version of this file under 35f9fbec18Smcpowers * the terms of any one of the MPL, the GPL or the LGPL. 36f9fbec18Smcpowers * 37f9fbec18Smcpowers * ***** END LICENSE BLOCK ***** */ 38f9fbec18Smcpowers /* 39f9fbec18Smcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 40f9fbec18Smcpowers * Use is subject to license terms. 41f9fbec18Smcpowers * 42f9fbec18Smcpowers * Sun elects to use this software under the MPL license. 43f9fbec18Smcpowers */ 44f9fbec18Smcpowers 45f9fbec18Smcpowers #include "ecp.h" 46f9fbec18Smcpowers #include "mpi.h" 47f9fbec18Smcpowers #include "mplogic.h" 48f9fbec18Smcpowers #include "mpi-priv.h" 49f9fbec18Smcpowers #ifndef _KERNEL 50f9fbec18Smcpowers #include <stdlib.h> 51f9fbec18Smcpowers #endif 52f9fbec18Smcpowers 53f9fbec18Smcpowers /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r. 54f9fbec18Smcpowers * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to 55f9fbec18Smcpowers * Elliptic Curve Cryptography. */ 56f9fbec18Smcpowers mp_err 57f9fbec18Smcpowers ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth) 58f9fbec18Smcpowers { 59f9fbec18Smcpowers mp_err res = MP_OKAY; 60f9fbec18Smcpowers mp_size a_used = MP_USED(a); 61f9fbec18Smcpowers int a_bits = mpl_significant_bits(a); 62f9fbec18Smcpowers mp_digit carry; 63f9fbec18Smcpowers 64f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT 65f9fbec18Smcpowers mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0; 66f9fbec18Smcpowers mp_digit r0, r1, r2, r3, r4, r5, r6, r7; 67f9fbec18Smcpowers int r8; /* must be a signed value ! */ 68f9fbec18Smcpowers #else 69f9fbec18Smcpowers mp_digit a4=0, a5=0, a6=0, a7=0; 70f9fbec18Smcpowers mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l; 71f9fbec18Smcpowers mp_digit r0, r1, r2, r3; 72f9fbec18Smcpowers int r4; /* must be a signed value ! */ 73f9fbec18Smcpowers #endif 74f9fbec18Smcpowers /* for polynomials larger than twice the field size 75f9fbec18Smcpowers * use regular reduction */ 76f9fbec18Smcpowers if (a_bits < 256) { 77f9fbec18Smcpowers if (a == r) return MP_OKAY; 78f9fbec18Smcpowers return mp_copy(a,r); 79f9fbec18Smcpowers } 80f9fbec18Smcpowers if (a_bits > 512) { 81f9fbec18Smcpowers MP_CHECKOK(mp_mod(a, &meth->irr, r)); 82f9fbec18Smcpowers } else { 83f9fbec18Smcpowers 84f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT 85f9fbec18Smcpowers switch (a_used) { 86f9fbec18Smcpowers case 16: 87f9fbec18Smcpowers a15 = MP_DIGIT(a,15); 88*38a641c5SToomas Soome /* FALLTHROUGH */ 89f9fbec18Smcpowers case 15: 90f9fbec18Smcpowers a14 = MP_DIGIT(a,14); 91*38a641c5SToomas Soome /* FALLTHROUGH */ 92f9fbec18Smcpowers case 14: 93f9fbec18Smcpowers a13 = MP_DIGIT(a,13); 94*38a641c5SToomas Soome /* FALLTHROUGH */ 95f9fbec18Smcpowers case 13: 96f9fbec18Smcpowers a12 = MP_DIGIT(a,12); 97*38a641c5SToomas Soome /* FALLTHROUGH */ 98f9fbec18Smcpowers case 12: 99f9fbec18Smcpowers a11 = MP_DIGIT(a,11); 100*38a641c5SToomas Soome /* FALLTHROUGH */ 101f9fbec18Smcpowers case 11: 102f9fbec18Smcpowers a10 = MP_DIGIT(a,10); 103*38a641c5SToomas Soome /* FALLTHROUGH */ 104f9fbec18Smcpowers case 10: 105f9fbec18Smcpowers a9 = MP_DIGIT(a,9); 106*38a641c5SToomas Soome /* FALLTHROUGH */ 107f9fbec18Smcpowers case 9: 108f9fbec18Smcpowers a8 = MP_DIGIT(a,8); 109f9fbec18Smcpowers } 110f9fbec18Smcpowers 111f9fbec18Smcpowers r0 = MP_DIGIT(a,0); 112f9fbec18Smcpowers r1 = MP_DIGIT(a,1); 113f9fbec18Smcpowers r2 = MP_DIGIT(a,2); 114f9fbec18Smcpowers r3 = MP_DIGIT(a,3); 115f9fbec18Smcpowers r4 = MP_DIGIT(a,4); 116f9fbec18Smcpowers r5 = MP_DIGIT(a,5); 117f9fbec18Smcpowers r6 = MP_DIGIT(a,6); 118f9fbec18Smcpowers r7 = MP_DIGIT(a,7); 119f9fbec18Smcpowers 120f9fbec18Smcpowers /* sum 1 */ 121f9fbec18Smcpowers MP_ADD_CARRY(r3, a11, r3, 0, carry); 122f9fbec18Smcpowers MP_ADD_CARRY(r4, a12, r4, carry, carry); 123f9fbec18Smcpowers MP_ADD_CARRY(r5, a13, r5, carry, carry); 124f9fbec18Smcpowers MP_ADD_CARRY(r6, a14, r6, carry, carry); 125f9fbec18Smcpowers MP_ADD_CARRY(r7, a15, r7, carry, carry); 126f9fbec18Smcpowers r8 = carry; 127f9fbec18Smcpowers MP_ADD_CARRY(r3, a11, r3, 0, carry); 128f9fbec18Smcpowers MP_ADD_CARRY(r4, a12, r4, carry, carry); 129f9fbec18Smcpowers MP_ADD_CARRY(r5, a13, r5, carry, carry); 130f9fbec18Smcpowers MP_ADD_CARRY(r6, a14, r6, carry, carry); 131f9fbec18Smcpowers MP_ADD_CARRY(r7, a15, r7, carry, carry); 132f9fbec18Smcpowers r8 += carry; 133f9fbec18Smcpowers /* sum 2 */ 134f9fbec18Smcpowers MP_ADD_CARRY(r3, a12, r3, 0, carry); 135f9fbec18Smcpowers MP_ADD_CARRY(r4, a13, r4, carry, carry); 136f9fbec18Smcpowers MP_ADD_CARRY(r5, a14, r5, carry, carry); 137f9fbec18Smcpowers MP_ADD_CARRY(r6, a15, r6, carry, carry); 138f9fbec18Smcpowers MP_ADD_CARRY(r7, 0, r7, carry, carry); 139f9fbec18Smcpowers r8 += carry; 140f9fbec18Smcpowers /* combine last bottom of sum 3 with second sum 2 */ 141f9fbec18Smcpowers MP_ADD_CARRY(r0, a8, r0, 0, carry); 142f9fbec18Smcpowers MP_ADD_CARRY(r1, a9, r1, carry, carry); 143f9fbec18Smcpowers MP_ADD_CARRY(r2, a10, r2, carry, carry); 144f9fbec18Smcpowers MP_ADD_CARRY(r3, a12, r3, carry, carry); 145f9fbec18Smcpowers MP_ADD_CARRY(r4, a13, r4, carry, carry); 146f9fbec18Smcpowers MP_ADD_CARRY(r5, a14, r5, carry, carry); 147f9fbec18Smcpowers MP_ADD_CARRY(r6, a15, r6, carry, carry); 148f9fbec18Smcpowers MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */ 149f9fbec18Smcpowers r8 += carry; 150f9fbec18Smcpowers /* sum 3 (rest of it)*/ 151f9fbec18Smcpowers MP_ADD_CARRY(r6, a14, r6, 0, carry); 152f9fbec18Smcpowers MP_ADD_CARRY(r7, 0, r7, carry, carry); 153f9fbec18Smcpowers r8 += carry; 154f9fbec18Smcpowers /* sum 4 (rest of it)*/ 155f9fbec18Smcpowers MP_ADD_CARRY(r0, a9, r0, 0, carry); 156f9fbec18Smcpowers MP_ADD_CARRY(r1, a10, r1, carry, carry); 157f9fbec18Smcpowers MP_ADD_CARRY(r2, a11, r2, carry, carry); 158f9fbec18Smcpowers MP_ADD_CARRY(r3, a13, r3, carry, carry); 159f9fbec18Smcpowers MP_ADD_CARRY(r4, a14, r4, carry, carry); 160f9fbec18Smcpowers MP_ADD_CARRY(r5, a15, r5, carry, carry); 161f9fbec18Smcpowers MP_ADD_CARRY(r6, a13, r6, carry, carry); 162f9fbec18Smcpowers MP_ADD_CARRY(r7, a8, r7, carry, carry); 163f9fbec18Smcpowers r8 += carry; 164f9fbec18Smcpowers /* diff 5 */ 165f9fbec18Smcpowers MP_SUB_BORROW(r0, a11, r0, 0, carry); 166f9fbec18Smcpowers MP_SUB_BORROW(r1, a12, r1, carry, carry); 167f9fbec18Smcpowers MP_SUB_BORROW(r2, a13, r2, carry, carry); 168f9fbec18Smcpowers MP_SUB_BORROW(r3, 0, r3, carry, carry); 169f9fbec18Smcpowers MP_SUB_BORROW(r4, 0, r4, carry, carry); 170f9fbec18Smcpowers MP_SUB_BORROW(r5, 0, r5, carry, carry); 171f9fbec18Smcpowers MP_SUB_BORROW(r6, a8, r6, carry, carry); 172f9fbec18Smcpowers MP_SUB_BORROW(r7, a10, r7, carry, carry); 173f9fbec18Smcpowers r8 -= carry; 174f9fbec18Smcpowers /* diff 6 */ 175f9fbec18Smcpowers MP_SUB_BORROW(r0, a12, r0, 0, carry); 176f9fbec18Smcpowers MP_SUB_BORROW(r1, a13, r1, carry, carry); 177f9fbec18Smcpowers MP_SUB_BORROW(r2, a14, r2, carry, carry); 178f9fbec18Smcpowers MP_SUB_BORROW(r3, a15, r3, carry, carry); 179f9fbec18Smcpowers MP_SUB_BORROW(r4, 0, r4, carry, carry); 180f9fbec18Smcpowers MP_SUB_BORROW(r5, 0, r5, carry, carry); 181f9fbec18Smcpowers MP_SUB_BORROW(r6, a9, r6, carry, carry); 182f9fbec18Smcpowers MP_SUB_BORROW(r7, a11, r7, carry, carry); 183f9fbec18Smcpowers r8 -= carry; 184f9fbec18Smcpowers /* diff 7 */ 185f9fbec18Smcpowers MP_SUB_BORROW(r0, a13, r0, 0, carry); 186f9fbec18Smcpowers MP_SUB_BORROW(r1, a14, r1, carry, carry); 187f9fbec18Smcpowers MP_SUB_BORROW(r2, a15, r2, carry, carry); 188f9fbec18Smcpowers MP_SUB_BORROW(r3, a8, r3, carry, carry); 189f9fbec18Smcpowers MP_SUB_BORROW(r4, a9, r4, carry, carry); 190f9fbec18Smcpowers MP_SUB_BORROW(r5, a10, r5, carry, carry); 191f9fbec18Smcpowers MP_SUB_BORROW(r6, 0, r6, carry, carry); 192f9fbec18Smcpowers MP_SUB_BORROW(r7, a12, r7, carry, carry); 193f9fbec18Smcpowers r8 -= carry; 194f9fbec18Smcpowers /* diff 8 */ 195f9fbec18Smcpowers MP_SUB_BORROW(r0, a14, r0, 0, carry); 196f9fbec18Smcpowers MP_SUB_BORROW(r1, a15, r1, carry, carry); 197f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry); 198f9fbec18Smcpowers MP_SUB_BORROW(r3, a9, r3, carry, carry); 199f9fbec18Smcpowers MP_SUB_BORROW(r4, a10, r4, carry, carry); 200f9fbec18Smcpowers MP_SUB_BORROW(r5, a11, r5, carry, carry); 201f9fbec18Smcpowers MP_SUB_BORROW(r6, 0, r6, carry, carry); 202f9fbec18Smcpowers MP_SUB_BORROW(r7, a13, r7, carry, carry); 203f9fbec18Smcpowers r8 -= carry; 204f9fbec18Smcpowers 205f9fbec18Smcpowers /* reduce the overflows */ 206f9fbec18Smcpowers while (r8 > 0) { 207f9fbec18Smcpowers mp_digit r8_d = r8; 208f9fbec18Smcpowers MP_ADD_CARRY(r0, r8_d, r0, 0, carry); 209f9fbec18Smcpowers MP_ADD_CARRY(r1, 0, r1, carry, carry); 210f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry); 211f9fbec18Smcpowers MP_ADD_CARRY(r3, -r8_d, r3, carry, carry); 212f9fbec18Smcpowers MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry); 213f9fbec18Smcpowers MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry); 214f9fbec18Smcpowers MP_ADD_CARRY(r6, -(r8_d+1), r6, carry, carry); 215f9fbec18Smcpowers MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry); 216f9fbec18Smcpowers r8 = carry; 217f9fbec18Smcpowers } 218f9fbec18Smcpowers 219f9fbec18Smcpowers /* reduce the underflows */ 220f9fbec18Smcpowers while (r8 < 0) { 221f9fbec18Smcpowers mp_digit r8_d = -r8; 222f9fbec18Smcpowers MP_SUB_BORROW(r0, r8_d, r0, 0, carry); 223f9fbec18Smcpowers MP_SUB_BORROW(r1, 0, r1, carry, carry); 224f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry); 225f9fbec18Smcpowers MP_SUB_BORROW(r3, -r8_d, r3, carry, carry); 226f9fbec18Smcpowers MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry); 227f9fbec18Smcpowers MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry); 228f9fbec18Smcpowers MP_SUB_BORROW(r6, -(r8_d+1), r6, carry, carry); 229f9fbec18Smcpowers MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry); 230f9fbec18Smcpowers r8 = -carry; 231f9fbec18Smcpowers } 232f9fbec18Smcpowers if (a != r) { 233f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r,8)); 234f9fbec18Smcpowers } 235f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS; 236f9fbec18Smcpowers MP_USED(r) = 8; 237f9fbec18Smcpowers 238f9fbec18Smcpowers MP_DIGIT(r,7) = r7; 239f9fbec18Smcpowers MP_DIGIT(r,6) = r6; 240f9fbec18Smcpowers MP_DIGIT(r,5) = r5; 241f9fbec18Smcpowers MP_DIGIT(r,4) = r4; 242f9fbec18Smcpowers MP_DIGIT(r,3) = r3; 243f9fbec18Smcpowers MP_DIGIT(r,2) = r2; 244f9fbec18Smcpowers MP_DIGIT(r,1) = r1; 245f9fbec18Smcpowers MP_DIGIT(r,0) = r0; 246f9fbec18Smcpowers 247f9fbec18Smcpowers /* final reduction if necessary */ 248f9fbec18Smcpowers if ((r7 == MP_DIGIT_MAX) && 249f9fbec18Smcpowers ((r6 > 1) || ((r6 == 1) && 250f9fbec18Smcpowers (r5 || r4 || r3 || 251f9fbec18Smcpowers ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX) 252f9fbec18Smcpowers && (r0 == MP_DIGIT_MAX)))))) { 253f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r)); 254f9fbec18Smcpowers } 255f9fbec18Smcpowers #ifdef notdef 256f9fbec18Smcpowers 257f9fbec18Smcpowers 258f9fbec18Smcpowers /* smooth the negatives */ 259f9fbec18Smcpowers while (MP_SIGN(r) != MP_ZPOS) { 260f9fbec18Smcpowers MP_CHECKOK(mp_add(r, &meth->irr, r)); 261f9fbec18Smcpowers } 262f9fbec18Smcpowers while (MP_USED(r) > 8) { 263f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r)); 264f9fbec18Smcpowers } 265f9fbec18Smcpowers 266f9fbec18Smcpowers /* final reduction if necessary */ 267f9fbec18Smcpowers if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) { 268f9fbec18Smcpowers if (mp_cmp(r,&meth->irr) != MP_LT) { 269f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r)); 270f9fbec18Smcpowers } 271f9fbec18Smcpowers } 272f9fbec18Smcpowers #endif 273f9fbec18Smcpowers s_mp_clamp(r); 274f9fbec18Smcpowers #else 275f9fbec18Smcpowers switch (a_used) { 276f9fbec18Smcpowers case 8: 277f9fbec18Smcpowers a7 = MP_DIGIT(a,7); 278*38a641c5SToomas Soome /* FALLTHROUGH */ 279f9fbec18Smcpowers case 7: 280f9fbec18Smcpowers a6 = MP_DIGIT(a,6); 281*38a641c5SToomas Soome /* FALLTHROUGH */ 282f9fbec18Smcpowers case 6: 283f9fbec18Smcpowers a5 = MP_DIGIT(a,5); 284*38a641c5SToomas Soome /* FALLTHROUGH */ 285f9fbec18Smcpowers case 5: 286f9fbec18Smcpowers a4 = MP_DIGIT(a,4); 287f9fbec18Smcpowers } 288f9fbec18Smcpowers a7l = a7 << 32; 289f9fbec18Smcpowers a7h = a7 >> 32; 290f9fbec18Smcpowers a6l = a6 << 32; 291f9fbec18Smcpowers a6h = a6 >> 32; 292f9fbec18Smcpowers a5l = a5 << 32; 293f9fbec18Smcpowers a5h = a5 >> 32; 294f9fbec18Smcpowers a4l = a4 << 32; 295f9fbec18Smcpowers a4h = a4 >> 32; 296f9fbec18Smcpowers r3 = MP_DIGIT(a,3); 297f9fbec18Smcpowers r2 = MP_DIGIT(a,2); 298f9fbec18Smcpowers r1 = MP_DIGIT(a,1); 299f9fbec18Smcpowers r0 = MP_DIGIT(a,0); 300f9fbec18Smcpowers 301f9fbec18Smcpowers /* sum 1 */ 302f9fbec18Smcpowers MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry); 303f9fbec18Smcpowers MP_ADD_CARRY(r2, a6, r2, carry, carry); 304f9fbec18Smcpowers MP_ADD_CARRY(r3, a7, r3, carry, carry); 305f9fbec18Smcpowers r4 = carry; 306f9fbec18Smcpowers MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry); 307f9fbec18Smcpowers MP_ADD_CARRY(r2, a6, r2, carry, carry); 308f9fbec18Smcpowers MP_ADD_CARRY(r3, a7, r3, carry, carry); 309f9fbec18Smcpowers r4 += carry; 310f9fbec18Smcpowers /* sum 2 */ 311f9fbec18Smcpowers MP_ADD_CARRY(r1, a6l, r1, 0, carry); 312f9fbec18Smcpowers MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry); 313f9fbec18Smcpowers MP_ADD_CARRY(r3, a7h, r3, carry, carry); 314f9fbec18Smcpowers r4 += carry; 315f9fbec18Smcpowers MP_ADD_CARRY(r1, a6l, r1, 0, carry); 316f9fbec18Smcpowers MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry); 317f9fbec18Smcpowers MP_ADD_CARRY(r3, a7h, r3, carry, carry); 318f9fbec18Smcpowers r4 += carry; 319f9fbec18Smcpowers 320f9fbec18Smcpowers /* sum 3 */ 321f9fbec18Smcpowers MP_ADD_CARRY(r0, a4, r0, 0, carry); 322f9fbec18Smcpowers MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry); 323f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry); 324f9fbec18Smcpowers MP_ADD_CARRY(r3, a7, r3, carry, carry); 325f9fbec18Smcpowers r4 += carry; 326f9fbec18Smcpowers /* sum 4 */ 327f9fbec18Smcpowers MP_ADD_CARRY(r0, a4h | a5l, r0, 0, carry); 328f9fbec18Smcpowers MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry); 329f9fbec18Smcpowers MP_ADD_CARRY(r2, a7, r2, carry, carry); 330f9fbec18Smcpowers MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry); 331f9fbec18Smcpowers r4 += carry; 332f9fbec18Smcpowers /* diff 5 */ 333f9fbec18Smcpowers MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry); 334f9fbec18Smcpowers MP_SUB_BORROW(r1, a6h, r1, carry, carry); 335f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry); 336f9fbec18Smcpowers MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry); 337f9fbec18Smcpowers r4 -= carry; 338f9fbec18Smcpowers /* diff 6 */ 339f9fbec18Smcpowers MP_SUB_BORROW(r0, a6, r0, 0, carry); 340f9fbec18Smcpowers MP_SUB_BORROW(r1, a7, r1, carry, carry); 341f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry); 342f9fbec18Smcpowers MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry); 343f9fbec18Smcpowers r4 -= carry; 344f9fbec18Smcpowers /* diff 7 */ 345f9fbec18Smcpowers MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry); 346f9fbec18Smcpowers MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry); 347f9fbec18Smcpowers MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry); 348f9fbec18Smcpowers MP_SUB_BORROW(r3, a6l, r3, carry, carry); 349f9fbec18Smcpowers r4 -= carry; 350f9fbec18Smcpowers /* diff 8 */ 351f9fbec18Smcpowers MP_SUB_BORROW(r0, a7, r0, 0, carry); 352f9fbec18Smcpowers MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry); 353f9fbec18Smcpowers MP_SUB_BORROW(r2, a5, r2, carry, carry); 354f9fbec18Smcpowers MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry); 355f9fbec18Smcpowers r4 -= carry; 356f9fbec18Smcpowers 357f9fbec18Smcpowers /* reduce the overflows */ 358f9fbec18Smcpowers while (r4 > 0) { 359f9fbec18Smcpowers mp_digit r4_long = r4; 360f9fbec18Smcpowers mp_digit r4l = (r4_long << 32); 361f9fbec18Smcpowers MP_ADD_CARRY(r0, r4_long, r0, 0, carry); 362f9fbec18Smcpowers MP_ADD_CARRY(r1, -r4l, r1, carry, carry); 363f9fbec18Smcpowers MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry); 364f9fbec18Smcpowers MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry); 365f9fbec18Smcpowers r4 = carry; 366f9fbec18Smcpowers } 367f9fbec18Smcpowers 368f9fbec18Smcpowers /* reduce the underflows */ 369f9fbec18Smcpowers while (r4 < 0) { 370f9fbec18Smcpowers mp_digit r4_long = -r4; 371f9fbec18Smcpowers mp_digit r4l = (r4_long << 32); 372f9fbec18Smcpowers MP_SUB_BORROW(r0, r4_long, r0, 0, carry); 373f9fbec18Smcpowers MP_SUB_BORROW(r1, -r4l, r1, carry, carry); 374f9fbec18Smcpowers MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry); 375f9fbec18Smcpowers MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry); 376f9fbec18Smcpowers r4 = -carry; 377f9fbec18Smcpowers } 378f9fbec18Smcpowers 379f9fbec18Smcpowers if (a != r) { 380f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r,4)); 381f9fbec18Smcpowers } 382f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS; 383f9fbec18Smcpowers MP_USED(r) = 4; 384f9fbec18Smcpowers 385f9fbec18Smcpowers MP_DIGIT(r,3) = r3; 386f9fbec18Smcpowers MP_DIGIT(r,2) = r2; 387f9fbec18Smcpowers MP_DIGIT(r,1) = r1; 388f9fbec18Smcpowers MP_DIGIT(r,0) = r0; 389f9fbec18Smcpowers 390f9fbec18Smcpowers /* final reduction if necessary */ 391f9fbec18Smcpowers if ((r3 > 0xFFFFFFFF00000001ULL) || 392f9fbec18Smcpowers ((r3 == 0xFFFFFFFF00000001ULL) && 393f9fbec18Smcpowers (r2 || (r1 >> 32)|| 394f9fbec18Smcpowers (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) { 395f9fbec18Smcpowers /* very rare, just use mp_sub */ 396f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r)); 397f9fbec18Smcpowers } 398f9fbec18Smcpowers 399f9fbec18Smcpowers s_mp_clamp(r); 400f9fbec18Smcpowers #endif 401f9fbec18Smcpowers } 402f9fbec18Smcpowers 403f9fbec18Smcpowers CLEANUP: 404f9fbec18Smcpowers return res; 405f9fbec18Smcpowers } 406f9fbec18Smcpowers 407f9fbec18Smcpowers /* Compute the square of polynomial a, reduce modulo p256. Store the 408f9fbec18Smcpowers * result in r. r could be a. Uses optimized modular reduction for p256. 409f9fbec18Smcpowers */ 410f9fbec18Smcpowers mp_err 411f9fbec18Smcpowers ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) 412f9fbec18Smcpowers { 413f9fbec18Smcpowers mp_err res = MP_OKAY; 414f9fbec18Smcpowers 415f9fbec18Smcpowers MP_CHECKOK(mp_sqr(a, r)); 416f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); 417f9fbec18Smcpowers CLEANUP: 418f9fbec18Smcpowers return res; 419f9fbec18Smcpowers } 420f9fbec18Smcpowers 421f9fbec18Smcpowers /* Compute the product of two polynomials a and b, reduce modulo p256. 422f9fbec18Smcpowers * Store the result in r. r could be a or b; a could be b. Uses 423f9fbec18Smcpowers * optimized modular reduction for p256. */ 424f9fbec18Smcpowers mp_err 425f9fbec18Smcpowers ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r, 426f9fbec18Smcpowers const GFMethod *meth) 427f9fbec18Smcpowers { 428f9fbec18Smcpowers mp_err res = MP_OKAY; 429f9fbec18Smcpowers 430f9fbec18Smcpowers MP_CHECKOK(mp_mul(a, b, r)); 431f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth)); 432f9fbec18Smcpowers CLEANUP: 433f9fbec18Smcpowers return res; 434f9fbec18Smcpowers } 435f9fbec18Smcpowers 436f9fbec18Smcpowers /* Wire in fast field arithmetic and precomputation of base point for 437f9fbec18Smcpowers * named curves. */ 438f9fbec18Smcpowers mp_err 439f9fbec18Smcpowers ec_group_set_gfp256(ECGroup *group, ECCurveName name) 440f9fbec18Smcpowers { 441f9fbec18Smcpowers if (name == ECCurve_NIST_P256) { 442f9fbec18Smcpowers group->meth->field_mod = &ec_GFp_nistp256_mod; 443f9fbec18Smcpowers group->meth->field_mul = &ec_GFp_nistp256_mul; 444f9fbec18Smcpowers group->meth->field_sqr = &ec_GFp_nistp256_sqr; 445f9fbec18Smcpowers } 446f9fbec18Smcpowers return MP_OKAY; 447f9fbec18Smcpowers } 448