wolf SSL / wolfSSL

wolfSSL SSL/TLS library, support up to TLS1.3

Dependents:   CyaSSL-Twitter-OAuth4Tw Example-client-tls-cert TwitterReader TweetTest ... more

wolfcrypt/src/fe_operations.c@4:1b0d80432c79, 2016-04-28 (annotated)

Committer:
wolfSSL
Date:
Thu Apr 28 00:57:21 2016 +0000
Revision:
4:1b0d80432c79
wolfSSL 3.9.0

Who changed what in which revision?

UserRevisionLine numberNew contents of line
wolfSSL 4:1b0d80432c79 1 /* fe_operations.c
wolfSSL 4:1b0d80432c79 2 *
wolfSSL 4:1b0d80432c79 3 * Copyright (C) 2006-2016 wolfSSL Inc.
wolfSSL 4:1b0d80432c79 4 *
wolfSSL 4:1b0d80432c79 5 * This file is part of wolfSSL.
wolfSSL 4:1b0d80432c79 6 *
wolfSSL 4:1b0d80432c79 7 * wolfSSL is free software; you can redistribute it and/or modify
wolfSSL 4:1b0d80432c79 8 * it under the terms of the GNU General Public License as published by
wolfSSL 4:1b0d80432c79 9 * the Free Software Foundation; either version 2 of the License, or
wolfSSL 4:1b0d80432c79 10 * (at your option) any later version.
wolfSSL 4:1b0d80432c79 11 *
wolfSSL 4:1b0d80432c79 12 * wolfSSL is distributed in the hope that it will be useful,
wolfSSL 4:1b0d80432c79 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
wolfSSL 4:1b0d80432c79 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
wolfSSL 4:1b0d80432c79 15 * GNU General Public License for more details.
wolfSSL 4:1b0d80432c79 16 *
wolfSSL 4:1b0d80432c79 17 * You should have received a copy of the GNU General Public License
wolfSSL 4:1b0d80432c79 18 * along with this program; if not, write to the Free Software
wolfSSL 4:1b0d80432c79 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
wolfSSL 4:1b0d80432c79 20 */
wolfSSL 4:1b0d80432c79 21
wolfSSL 4:1b0d80432c79 22
wolfSSL 4:1b0d80432c79 23 /* Based On Daniel J Bernstein's curve25519 Public Domain ref10 work. */
wolfSSL 4:1b0d80432c79 24
wolfSSL 4:1b0d80432c79 25 #ifdef HAVE_CONFIG_H
wolfSSL 4:1b0d80432c79 26 #include <config.h>
wolfSSL 4:1b0d80432c79 27 #endif
wolfSSL 4:1b0d80432c79 28
wolfSSL 4:1b0d80432c79 29 #include <wolfssl/wolfcrypt/settings.h>
wolfSSL 4:1b0d80432c79 30
wolfSSL 4:1b0d80432c79 31 #ifndef CURVED25519_SMALL /* run when not defined to use small memory math */
wolfSSL 4:1b0d80432c79 32 #if defined(HAVE_ED25519) || defined(HAVE_CURVE25519)
wolfSSL 4:1b0d80432c79 33
wolfSSL 4:1b0d80432c79 34 #include <wolfssl/wolfcrypt/fe_operations.h>
wolfSSL 4:1b0d80432c79 35 #include <stdint.h>
wolfSSL 4:1b0d80432c79 36
wolfSSL 4:1b0d80432c79 37 #ifdef NO_INLINE
wolfSSL 4:1b0d80432c79 38 #include <wolfssl/wolfcrypt/misc.h>
wolfSSL 4:1b0d80432c79 39 #else
wolfSSL 4:1b0d80432c79 40 #include <wolfcrypt/src/misc.c>
wolfSSL 4:1b0d80432c79 41 #endif
wolfSSL 4:1b0d80432c79 42
wolfSSL 4:1b0d80432c79 43 /*
wolfSSL 4:1b0d80432c79 44 fe means field element.
wolfSSL 4:1b0d80432c79 45 Here the field is \Z/(2^255-19).
wolfSSL 4:1b0d80432c79 46 An element t, entries t[0]...t[9], represents the integer
wolfSSL 4:1b0d80432c79 47 t[0]+2^26 t[1]+2^51 t[2]+2^77 t[3]+2^102 t[4]+...+2^230 t[9].
wolfSSL 4:1b0d80432c79 48 Bounds on each t[i] vary depending on context.
wolfSSL 4:1b0d80432c79 49 */
wolfSSL 4:1b0d80432c79 50
wolfSSL 4:1b0d80432c79 51 uint64_t load_3(const unsigned char *in)
wolfSSL 4:1b0d80432c79 52 {
wolfSSL 4:1b0d80432c79 53 uint64_t result;
wolfSSL 4:1b0d80432c79 54 result = (uint64_t) in[0];
wolfSSL 4:1b0d80432c79 55 result |= ((uint64_t) in[1]) << 8;
wolfSSL 4:1b0d80432c79 56 result |= ((uint64_t) in[2]) << 16;
wolfSSL 4:1b0d80432c79 57 return result;
wolfSSL 4:1b0d80432c79 58 }
wolfSSL 4:1b0d80432c79 59
wolfSSL 4:1b0d80432c79 60
wolfSSL 4:1b0d80432c79 61 uint64_t load_4(const unsigned char *in)
wolfSSL 4:1b0d80432c79 62 {
wolfSSL 4:1b0d80432c79 63 uint64_t result;
wolfSSL 4:1b0d80432c79 64 result = (uint64_t) in[0];
wolfSSL 4:1b0d80432c79 65 result |= ((uint64_t) in[1]) << 8;
wolfSSL 4:1b0d80432c79 66 result |= ((uint64_t) in[2]) << 16;
wolfSSL 4:1b0d80432c79 67 result |= ((uint64_t) in[3]) << 24;
wolfSSL 4:1b0d80432c79 68 return result;
wolfSSL 4:1b0d80432c79 69 }
wolfSSL 4:1b0d80432c79 70
wolfSSL 4:1b0d80432c79 71
wolfSSL 4:1b0d80432c79 72 /*
wolfSSL 4:1b0d80432c79 73 h = 1
wolfSSL 4:1b0d80432c79 74 */
wolfSSL 4:1b0d80432c79 75
wolfSSL 4:1b0d80432c79 76 void fe_1(fe h)
wolfSSL 4:1b0d80432c79 77 {
wolfSSL 4:1b0d80432c79 78 h[0] = 1;
wolfSSL 4:1b0d80432c79 79 h[1] = 0;
wolfSSL 4:1b0d80432c79 80 h[2] = 0;
wolfSSL 4:1b0d80432c79 81 h[3] = 0;
wolfSSL 4:1b0d80432c79 82 h[4] = 0;
wolfSSL 4:1b0d80432c79 83 h[5] = 0;
wolfSSL 4:1b0d80432c79 84 h[6] = 0;
wolfSSL 4:1b0d80432c79 85 h[7] = 0;
wolfSSL 4:1b0d80432c79 86 h[8] = 0;
wolfSSL 4:1b0d80432c79 87 h[9] = 0;
wolfSSL 4:1b0d80432c79 88 }
wolfSSL 4:1b0d80432c79 89
wolfSSL 4:1b0d80432c79 90
wolfSSL 4:1b0d80432c79 91 /*
wolfSSL 4:1b0d80432c79 92 h = 0
wolfSSL 4:1b0d80432c79 93 */
wolfSSL 4:1b0d80432c79 94
wolfSSL 4:1b0d80432c79 95 void fe_0(fe h)
wolfSSL 4:1b0d80432c79 96 {
wolfSSL 4:1b0d80432c79 97 h[0] = 0;
wolfSSL 4:1b0d80432c79 98 h[1] = 0;
wolfSSL 4:1b0d80432c79 99 h[2] = 0;
wolfSSL 4:1b0d80432c79 100 h[3] = 0;
wolfSSL 4:1b0d80432c79 101 h[4] = 0;
wolfSSL 4:1b0d80432c79 102 h[5] = 0;
wolfSSL 4:1b0d80432c79 103 h[6] = 0;
wolfSSL 4:1b0d80432c79 104 h[7] = 0;
wolfSSL 4:1b0d80432c79 105 h[8] = 0;
wolfSSL 4:1b0d80432c79 106 h[9] = 0;
wolfSSL 4:1b0d80432c79 107 }
wolfSSL 4:1b0d80432c79 108
wolfSSL 4:1b0d80432c79 109
wolfSSL 4:1b0d80432c79 110 int curve25519(byte* q, byte* n, byte* p)
wolfSSL 4:1b0d80432c79 111 {
wolfSSL 4:1b0d80432c79 112 #if 0
wolfSSL 4:1b0d80432c79 113 unsigned char e[32];
wolfSSL 4:1b0d80432c79 114 #endif
wolfSSL 4:1b0d80432c79 115 fe x1;
wolfSSL 4:1b0d80432c79 116 fe x2;
wolfSSL 4:1b0d80432c79 117 fe z2;
wolfSSL 4:1b0d80432c79 118 fe x3;
wolfSSL 4:1b0d80432c79 119 fe z3;
wolfSSL 4:1b0d80432c79 120 fe tmp0;
wolfSSL 4:1b0d80432c79 121 fe tmp1;
wolfSSL 4:1b0d80432c79 122 int pos;
wolfSSL 4:1b0d80432c79 123 unsigned int swap;
wolfSSL 4:1b0d80432c79 124 unsigned int b;
wolfSSL 4:1b0d80432c79 125
wolfSSL 4:1b0d80432c79 126 /* Clamp already done during key generation and import */
wolfSSL 4:1b0d80432c79 127 #if 0
wolfSSL 4:1b0d80432c79 128 {
wolfSSL 4:1b0d80432c79 129 unsigned int i;
wolfSSL 4:1b0d80432c79 130 for (i = 0;i < 32;++i) e[i] = n[i];
wolfSSL 4:1b0d80432c79 131 e[0] &= 248;
wolfSSL 4:1b0d80432c79 132 e[31] &= 127;
wolfSSL 4:1b0d80432c79 133 e[31] |= 64;
wolfSSL 4:1b0d80432c79 134 }
wolfSSL 4:1b0d80432c79 135 #endif
wolfSSL 4:1b0d80432c79 136
wolfSSL 4:1b0d80432c79 137 fe_frombytes(x1,p);
wolfSSL 4:1b0d80432c79 138 fe_1(x2);
wolfSSL 4:1b0d80432c79 139 fe_0(z2);
wolfSSL 4:1b0d80432c79 140 fe_copy(x3,x1);
wolfSSL 4:1b0d80432c79 141 fe_1(z3);
wolfSSL 4:1b0d80432c79 142
wolfSSL 4:1b0d80432c79 143 swap = 0;
wolfSSL 4:1b0d80432c79 144 for (pos = 254;pos >= 0;--pos) {
wolfSSL 4:1b0d80432c79 145 #if 0
wolfSSL 4:1b0d80432c79 146 b = e[pos / 8] >> (pos & 7);
wolfSSL 4:1b0d80432c79 147 #else
wolfSSL 4:1b0d80432c79 148 b = n[pos / 8] >> (pos & 7);
wolfSSL 4:1b0d80432c79 149 #endif
wolfSSL 4:1b0d80432c79 150 b &= 1;
wolfSSL 4:1b0d80432c79 151 swap ^= b;
wolfSSL 4:1b0d80432c79 152 fe_cswap(x2,x3,swap);
wolfSSL 4:1b0d80432c79 153 fe_cswap(z2,z3,swap);
wolfSSL 4:1b0d80432c79 154 swap = b;
wolfSSL 4:1b0d80432c79 155
wolfSSL 4:1b0d80432c79 156 /* montgomery */
wolfSSL 4:1b0d80432c79 157 fe_sub(tmp0,x3,z3);
wolfSSL 4:1b0d80432c79 158 fe_sub(tmp1,x2,z2);
wolfSSL 4:1b0d80432c79 159 fe_add(x2,x2,z2);
wolfSSL 4:1b0d80432c79 160 fe_add(z2,x3,z3);
wolfSSL 4:1b0d80432c79 161 fe_mul(z3,tmp0,x2);
wolfSSL 4:1b0d80432c79 162 fe_mul(z2,z2,tmp1);
wolfSSL 4:1b0d80432c79 163 fe_sq(tmp0,tmp1);
wolfSSL 4:1b0d80432c79 164 fe_sq(tmp1,x2);
wolfSSL 4:1b0d80432c79 165 fe_add(x3,z3,z2);
wolfSSL 4:1b0d80432c79 166 fe_sub(z2,z3,z2);
wolfSSL 4:1b0d80432c79 167 fe_mul(x2,tmp1,tmp0);
wolfSSL 4:1b0d80432c79 168 fe_sub(tmp1,tmp1,tmp0);
wolfSSL 4:1b0d80432c79 169 fe_sq(z2,z2);
wolfSSL 4:1b0d80432c79 170 fe_mul121666(z3,tmp1);
wolfSSL 4:1b0d80432c79 171 fe_sq(x3,x3);
wolfSSL 4:1b0d80432c79 172 fe_add(tmp0,tmp0,z3);
wolfSSL 4:1b0d80432c79 173 fe_mul(z3,x1,z2);
wolfSSL 4:1b0d80432c79 174 fe_mul(z2,tmp1,tmp0);
wolfSSL 4:1b0d80432c79 175 }
wolfSSL 4:1b0d80432c79 176 fe_cswap(x2,x3,swap);
wolfSSL 4:1b0d80432c79 177 fe_cswap(z2,z3,swap);
wolfSSL 4:1b0d80432c79 178
wolfSSL 4:1b0d80432c79 179 fe_invert(z2,z2);
wolfSSL 4:1b0d80432c79 180 fe_mul(x2,x2,z2);
wolfSSL 4:1b0d80432c79 181 fe_tobytes(q,x2);
wolfSSL 4:1b0d80432c79 182
wolfSSL 4:1b0d80432c79 183 return 0;
wolfSSL 4:1b0d80432c79 184 }
wolfSSL 4:1b0d80432c79 185
wolfSSL 4:1b0d80432c79 186
wolfSSL 4:1b0d80432c79 187 /*
wolfSSL 4:1b0d80432c79 188 h = f * f
wolfSSL 4:1b0d80432c79 189 Can overlap h with f.
wolfSSL 4:1b0d80432c79 190
wolfSSL 4:1b0d80432c79 191 Preconditions:
wolfSSL 4:1b0d80432c79 192 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
wolfSSL 4:1b0d80432c79 193
wolfSSL 4:1b0d80432c79 194 Postconditions:
wolfSSL 4:1b0d80432c79 195 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
wolfSSL 4:1b0d80432c79 196 */
wolfSSL 4:1b0d80432c79 197
wolfSSL 4:1b0d80432c79 198 /*
wolfSSL 4:1b0d80432c79 199 See fe_mul.c for discussion of implementation strategy.
wolfSSL 4:1b0d80432c79 200 */
wolfSSL 4:1b0d80432c79 201
wolfSSL 4:1b0d80432c79 202 void fe_sq(fe h,const fe f)
wolfSSL 4:1b0d80432c79 203 {
wolfSSL 4:1b0d80432c79 204 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 205 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 206 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 207 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 208 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 209 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 210 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 211 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 212 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 213 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 214 int32_t f0_2 = 2 * f0;
wolfSSL 4:1b0d80432c79 215 int32_t f1_2 = 2 * f1;
wolfSSL 4:1b0d80432c79 216 int32_t f2_2 = 2 * f2;
wolfSSL 4:1b0d80432c79 217 int32_t f3_2 = 2 * f3;
wolfSSL 4:1b0d80432c79 218 int32_t f4_2 = 2 * f4;
wolfSSL 4:1b0d80432c79 219 int32_t f5_2 = 2 * f5;
wolfSSL 4:1b0d80432c79 220 int32_t f6_2 = 2 * f6;
wolfSSL 4:1b0d80432c79 221 int32_t f7_2 = 2 * f7;
wolfSSL 4:1b0d80432c79 222 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 223 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 224 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 225 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 226 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 227 int64_t f0f0 = f0 * (int64_t) f0;
wolfSSL 4:1b0d80432c79 228 int64_t f0f1_2 = f0_2 * (int64_t) f1;
wolfSSL 4:1b0d80432c79 229 int64_t f0f2_2 = f0_2 * (int64_t) f2;
wolfSSL 4:1b0d80432c79 230 int64_t f0f3_2 = f0_2 * (int64_t) f3;
wolfSSL 4:1b0d80432c79 231 int64_t f0f4_2 = f0_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 232 int64_t f0f5_2 = f0_2 * (int64_t) f5;
wolfSSL 4:1b0d80432c79 233 int64_t f0f6_2 = f0_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 234 int64_t f0f7_2 = f0_2 * (int64_t) f7;
wolfSSL 4:1b0d80432c79 235 int64_t f0f8_2 = f0_2 * (int64_t) f8;
wolfSSL 4:1b0d80432c79 236 int64_t f0f9_2 = f0_2 * (int64_t) f9;
wolfSSL 4:1b0d80432c79 237 int64_t f1f1_2 = f1_2 * (int64_t) f1;
wolfSSL 4:1b0d80432c79 238 int64_t f1f2_2 = f1_2 * (int64_t) f2;
wolfSSL 4:1b0d80432c79 239 int64_t f1f3_4 = f1_2 * (int64_t) f3_2;
wolfSSL 4:1b0d80432c79 240 int64_t f1f4_2 = f1_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 241 int64_t f1f5_4 = f1_2 * (int64_t) f5_2;
wolfSSL 4:1b0d80432c79 242 int64_t f1f6_2 = f1_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 243 int64_t f1f7_4 = f1_2 * (int64_t) f7_2;
wolfSSL 4:1b0d80432c79 244 int64_t f1f8_2 = f1_2 * (int64_t) f8;
wolfSSL 4:1b0d80432c79 245 int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 246 int64_t f2f2 = f2 * (int64_t) f2;
wolfSSL 4:1b0d80432c79 247 int64_t f2f3_2 = f2_2 * (int64_t) f3;
wolfSSL 4:1b0d80432c79 248 int64_t f2f4_2 = f2_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 249 int64_t f2f5_2 = f2_2 * (int64_t) f5;
wolfSSL 4:1b0d80432c79 250 int64_t f2f6_2 = f2_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 251 int64_t f2f7_2 = f2_2 * (int64_t) f7;
wolfSSL 4:1b0d80432c79 252 int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 253 int64_t f2f9_38 = f2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 254 int64_t f3f3_2 = f3_2 * (int64_t) f3;
wolfSSL 4:1b0d80432c79 255 int64_t f3f4_2 = f3_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 256 int64_t f3f5_4 = f3_2 * (int64_t) f5_2;
wolfSSL 4:1b0d80432c79 257 int64_t f3f6_2 = f3_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 258 int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 259 int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 260 int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 261 int64_t f4f4 = f4 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 262 int64_t f4f5_2 = f4_2 * (int64_t) f5;
wolfSSL 4:1b0d80432c79 263 int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
wolfSSL 4:1b0d80432c79 264 int64_t f4f7_38 = f4 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 265 int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 266 int64_t f4f9_38 = f4 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 267 int64_t f5f5_38 = f5 * (int64_t) f5_38;
wolfSSL 4:1b0d80432c79 268 int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
wolfSSL 4:1b0d80432c79 269 int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 270 int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 271 int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 272 int64_t f6f6_19 = f6 * (int64_t) f6_19;
wolfSSL 4:1b0d80432c79 273 int64_t f6f7_38 = f6 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 274 int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 275 int64_t f6f9_38 = f6 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 276 int64_t f7f7_38 = f7 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 277 int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 278 int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 279 int64_t f8f8_19 = f8 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 280 int64_t f8f9_38 = f8 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 281 int64_t f9f9_38 = f9 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 282 int64_t h0 = f0f0 +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;
wolfSSL 4:1b0d80432c79 283 int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;
wolfSSL 4:1b0d80432c79 284 int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;
wolfSSL 4:1b0d80432c79 285 int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;
wolfSSL 4:1b0d80432c79 286 int64_t h4 = f0f4_2+f1f3_4 +f2f2 +f5f9_76+f6f8_38+f7f7_38;
wolfSSL 4:1b0d80432c79 287 int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;
wolfSSL 4:1b0d80432c79 288 int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;
wolfSSL 4:1b0d80432c79 289 int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;
wolfSSL 4:1b0d80432c79 290 int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4 +f9f9_38;
wolfSSL 4:1b0d80432c79 291 int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;
wolfSSL 4:1b0d80432c79 292 int64_t carry0;
wolfSSL 4:1b0d80432c79 293 int64_t carry1;
wolfSSL 4:1b0d80432c79 294 int64_t carry2;
wolfSSL 4:1b0d80432c79 295 int64_t carry3;
wolfSSL 4:1b0d80432c79 296 int64_t carry4;
wolfSSL 4:1b0d80432c79 297 int64_t carry5;
wolfSSL 4:1b0d80432c79 298 int64_t carry6;
wolfSSL 4:1b0d80432c79 299 int64_t carry7;
wolfSSL 4:1b0d80432c79 300 int64_t carry8;
wolfSSL 4:1b0d80432c79 301 int64_t carry9;
wolfSSL 4:1b0d80432c79 302
wolfSSL 4:1b0d80432c79 303 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 304 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 305
wolfSSL 4:1b0d80432c79 306 carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
wolfSSL 4:1b0d80432c79 307 carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
wolfSSL 4:1b0d80432c79 308
wolfSSL 4:1b0d80432c79 309 carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
wolfSSL 4:1b0d80432c79 310 carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
wolfSSL 4:1b0d80432c79 311
wolfSSL 4:1b0d80432c79 312 carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
wolfSSL 4:1b0d80432c79 313 carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
wolfSSL 4:1b0d80432c79 314
wolfSSL 4:1b0d80432c79 315 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 316 carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
wolfSSL 4:1b0d80432c79 317
wolfSSL 4:1b0d80432c79 318 carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
wolfSSL 4:1b0d80432c79 319
wolfSSL 4:1b0d80432c79 320 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 321
wolfSSL 4:1b0d80432c79 322 h[0] = (int32_t)h0;
wolfSSL 4:1b0d80432c79 323 h[1] = (int32_t)h1;
wolfSSL 4:1b0d80432c79 324 h[2] = (int32_t)h2;
wolfSSL 4:1b0d80432c79 325 h[3] = (int32_t)h3;
wolfSSL 4:1b0d80432c79 326 h[4] = (int32_t)h4;
wolfSSL 4:1b0d80432c79 327 h[5] = (int32_t)h5;
wolfSSL 4:1b0d80432c79 328 h[6] = (int32_t)h6;
wolfSSL 4:1b0d80432c79 329 h[7] = (int32_t)h7;
wolfSSL 4:1b0d80432c79 330 h[8] = (int32_t)h8;
wolfSSL 4:1b0d80432c79 331 h[9] = (int32_t)h9;
wolfSSL 4:1b0d80432c79 332 }
wolfSSL 4:1b0d80432c79 333
wolfSSL 4:1b0d80432c79 334
wolfSSL 4:1b0d80432c79 335 /*
wolfSSL 4:1b0d80432c79 336 h = f + g
wolfSSL 4:1b0d80432c79 337 Can overlap h with f or g.
wolfSSL 4:1b0d80432c79 338
wolfSSL 4:1b0d80432c79 339 Preconditions:
wolfSSL 4:1b0d80432c79 340 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 341 |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 342
wolfSSL 4:1b0d80432c79 343 Postconditions:
wolfSSL 4:1b0d80432c79 344 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
wolfSSL 4:1b0d80432c79 345 */
wolfSSL 4:1b0d80432c79 346
wolfSSL 4:1b0d80432c79 347 void fe_add(fe h,const fe f,const fe g)
wolfSSL 4:1b0d80432c79 348 {
wolfSSL 4:1b0d80432c79 349 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 350 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 351 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 352 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 353 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 354 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 355 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 356 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 357 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 358 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 359 int32_t g0 = g[0];
wolfSSL 4:1b0d80432c79 360 int32_t g1 = g[1];
wolfSSL 4:1b0d80432c79 361 int32_t g2 = g[2];
wolfSSL 4:1b0d80432c79 362 int32_t g3 = g[3];
wolfSSL 4:1b0d80432c79 363 int32_t g4 = g[4];
wolfSSL 4:1b0d80432c79 364 int32_t g5 = g[5];
wolfSSL 4:1b0d80432c79 365 int32_t g6 = g[6];
wolfSSL 4:1b0d80432c79 366 int32_t g7 = g[7];
wolfSSL 4:1b0d80432c79 367 int32_t g8 = g[8];
wolfSSL 4:1b0d80432c79 368 int32_t g9 = g[9];
wolfSSL 4:1b0d80432c79 369 int32_t h0 = f0 + g0;
wolfSSL 4:1b0d80432c79 370 int32_t h1 = f1 + g1;
wolfSSL 4:1b0d80432c79 371 int32_t h2 = f2 + g2;
wolfSSL 4:1b0d80432c79 372 int32_t h3 = f3 + g3;
wolfSSL 4:1b0d80432c79 373 int32_t h4 = f4 + g4;
wolfSSL 4:1b0d80432c79 374 int32_t h5 = f5 + g5;
wolfSSL 4:1b0d80432c79 375 int32_t h6 = f6 + g6;
wolfSSL 4:1b0d80432c79 376 int32_t h7 = f7 + g7;
wolfSSL 4:1b0d80432c79 377 int32_t h8 = f8 + g8;
wolfSSL 4:1b0d80432c79 378 int32_t h9 = f9 + g9;
wolfSSL 4:1b0d80432c79 379 h[0] = h0;
wolfSSL 4:1b0d80432c79 380 h[1] = h1;
wolfSSL 4:1b0d80432c79 381 h[2] = h2;
wolfSSL 4:1b0d80432c79 382 h[3] = h3;
wolfSSL 4:1b0d80432c79 383 h[4] = h4;
wolfSSL 4:1b0d80432c79 384 h[5] = h5;
wolfSSL 4:1b0d80432c79 385 h[6] = h6;
wolfSSL 4:1b0d80432c79 386 h[7] = h7;
wolfSSL 4:1b0d80432c79 387 h[8] = h8;
wolfSSL 4:1b0d80432c79 388 h[9] = h9;
wolfSSL 4:1b0d80432c79 389 }
wolfSSL 4:1b0d80432c79 390
wolfSSL 4:1b0d80432c79 391
wolfSSL 4:1b0d80432c79 392 /*
wolfSSL 4:1b0d80432c79 393 Preconditions:
wolfSSL 4:1b0d80432c79 394 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
wolfSSL 4:1b0d80432c79 395
wolfSSL 4:1b0d80432c79 396 Write p=2^255-19; q=floor(h/p).
wolfSSL 4:1b0d80432c79 397 Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
wolfSSL 4:1b0d80432c79 398
wolfSSL 4:1b0d80432c79 399 Proof:
wolfSSL 4:1b0d80432c79 400 Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
wolfSSL 4:1b0d80432c79 401 Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
wolfSSL 4:1b0d80432c79 402
wolfSSL 4:1b0d80432c79 403 Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
wolfSSL 4:1b0d80432c79 404 Then 0<y<1.
wolfSSL 4:1b0d80432c79 405
wolfSSL 4:1b0d80432c79 406 Write r=h-pq.
wolfSSL 4:1b0d80432c79 407 Have 0<=r<=p-1=2^255-20.
wolfSSL 4:1b0d80432c79 408 Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
wolfSSL 4:1b0d80432c79 409
wolfSSL 4:1b0d80432c79 410 Write x=r+19(2^-255)r+y.
wolfSSL 4:1b0d80432c79 411 Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
wolfSSL 4:1b0d80432c79 412
wolfSSL 4:1b0d80432c79 413 Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
wolfSSL 4:1b0d80432c79 414 so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
wolfSSL 4:1b0d80432c79 415 */
wolfSSL 4:1b0d80432c79 416
wolfSSL 4:1b0d80432c79 417 void fe_tobytes(unsigned char *s,const fe h)
wolfSSL 4:1b0d80432c79 418 {
wolfSSL 4:1b0d80432c79 419 int32_t h0 = h[0];
wolfSSL 4:1b0d80432c79 420 int32_t h1 = h[1];
wolfSSL 4:1b0d80432c79 421 int32_t h2 = h[2];
wolfSSL 4:1b0d80432c79 422 int32_t h3 = h[3];
wolfSSL 4:1b0d80432c79 423 int32_t h4 = h[4];
wolfSSL 4:1b0d80432c79 424 int32_t h5 = h[5];
wolfSSL 4:1b0d80432c79 425 int32_t h6 = h[6];
wolfSSL 4:1b0d80432c79 426 int32_t h7 = h[7];
wolfSSL 4:1b0d80432c79 427 int32_t h8 = h[8];
wolfSSL 4:1b0d80432c79 428 int32_t h9 = h[9];
wolfSSL 4:1b0d80432c79 429 int32_t q;
wolfSSL 4:1b0d80432c79 430 int32_t carry0;
wolfSSL 4:1b0d80432c79 431 int32_t carry1;
wolfSSL 4:1b0d80432c79 432 int32_t carry2;
wolfSSL 4:1b0d80432c79 433 int32_t carry3;
wolfSSL 4:1b0d80432c79 434 int32_t carry4;
wolfSSL 4:1b0d80432c79 435 int32_t carry5;
wolfSSL 4:1b0d80432c79 436 int32_t carry6;
wolfSSL 4:1b0d80432c79 437 int32_t carry7;
wolfSSL 4:1b0d80432c79 438 int32_t carry8;
wolfSSL 4:1b0d80432c79 439 int32_t carry9;
wolfSSL 4:1b0d80432c79 440
wolfSSL 4:1b0d80432c79 441 q = (19 * h9 + (((int32_t) 1) << 24)) >> 25;
wolfSSL 4:1b0d80432c79 442 q = (h0 + q) >> 26;
wolfSSL 4:1b0d80432c79 443 q = (h1 + q) >> 25;
wolfSSL 4:1b0d80432c79 444 q = (h2 + q) >> 26;
wolfSSL 4:1b0d80432c79 445 q = (h3 + q) >> 25;
wolfSSL 4:1b0d80432c79 446 q = (h4 + q) >> 26;
wolfSSL 4:1b0d80432c79 447 q = (h5 + q) >> 25;
wolfSSL 4:1b0d80432c79 448 q = (h6 + q) >> 26;
wolfSSL 4:1b0d80432c79 449 q = (h7 + q) >> 25;
wolfSSL 4:1b0d80432c79 450 q = (h8 + q) >> 26;
wolfSSL 4:1b0d80432c79 451 q = (h9 + q) >> 25;
wolfSSL 4:1b0d80432c79 452
wolfSSL 4:1b0d80432c79 453 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
wolfSSL 4:1b0d80432c79 454 h0 += 19 * q;
wolfSSL 4:1b0d80432c79 455 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
wolfSSL 4:1b0d80432c79 456
wolfSSL 4:1b0d80432c79 457 carry0 = h0 >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 458 carry1 = h1 >> 25; h2 += carry1; h1 -= carry1 << 25;
wolfSSL 4:1b0d80432c79 459 carry2 = h2 >> 26; h3 += carry2; h2 -= carry2 << 26;
wolfSSL 4:1b0d80432c79 460 carry3 = h3 >> 25; h4 += carry3; h3 -= carry3 << 25;
wolfSSL 4:1b0d80432c79 461 carry4 = h4 >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 462 carry5 = h5 >> 25; h6 += carry5; h5 -= carry5 << 25;
wolfSSL 4:1b0d80432c79 463 carry6 = h6 >> 26; h7 += carry6; h6 -= carry6 << 26;
wolfSSL 4:1b0d80432c79 464 carry7 = h7 >> 25; h8 += carry7; h7 -= carry7 << 25;
wolfSSL 4:1b0d80432c79 465 carry8 = h8 >> 26; h9 += carry8; h8 -= carry8 << 26;
wolfSSL 4:1b0d80432c79 466 carry9 = h9 >> 25; h9 -= carry9 << 25;
wolfSSL 4:1b0d80432c79 467 /* h10 = carry9 */
wolfSSL 4:1b0d80432c79 468
wolfSSL 4:1b0d80432c79 469 /*
wolfSSL 4:1b0d80432c79 470 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
wolfSSL 4:1b0d80432c79 471 Have h0+...+2^230 h9 between 0 and 2^255-1;
wolfSSL 4:1b0d80432c79 472 evidently 2^255 h10-2^255 q = 0.
wolfSSL 4:1b0d80432c79 473 Goal: Output h0+...+2^230 h9.
wolfSSL 4:1b0d80432c79 474 */
wolfSSL 4:1b0d80432c79 475
wolfSSL 4:1b0d80432c79 476 s[0] = h0 >> 0;
wolfSSL 4:1b0d80432c79 477 s[1] = h0 >> 8;
wolfSSL 4:1b0d80432c79 478 s[2] = h0 >> 16;
wolfSSL 4:1b0d80432c79 479 s[3] = (h0 >> 24) | (h1 << 2);
wolfSSL 4:1b0d80432c79 480 s[4] = h1 >> 6;
wolfSSL 4:1b0d80432c79 481 s[5] = h1 >> 14;
wolfSSL 4:1b0d80432c79 482 s[6] = (h1 >> 22) | (h2 << 3);
wolfSSL 4:1b0d80432c79 483 s[7] = h2 >> 5;
wolfSSL 4:1b0d80432c79 484 s[8] = h2 >> 13;
wolfSSL 4:1b0d80432c79 485 s[9] = (h2 >> 21) | (h3 << 5);
wolfSSL 4:1b0d80432c79 486 s[10] = h3 >> 3;
wolfSSL 4:1b0d80432c79 487 s[11] = h3 >> 11;
wolfSSL 4:1b0d80432c79 488 s[12] = (h3 >> 19) | (h4 << 6);
wolfSSL 4:1b0d80432c79 489 s[13] = h4 >> 2;
wolfSSL 4:1b0d80432c79 490 s[14] = h4 >> 10;
wolfSSL 4:1b0d80432c79 491 s[15] = h4 >> 18;
wolfSSL 4:1b0d80432c79 492 s[16] = h5 >> 0;
wolfSSL 4:1b0d80432c79 493 s[17] = h5 >> 8;
wolfSSL 4:1b0d80432c79 494 s[18] = h5 >> 16;
wolfSSL 4:1b0d80432c79 495 s[19] = (h5 >> 24) | (h6 << 1);
wolfSSL 4:1b0d80432c79 496 s[20] = h6 >> 7;
wolfSSL 4:1b0d80432c79 497 s[21] = h6 >> 15;
wolfSSL 4:1b0d80432c79 498 s[22] = (h6 >> 23) | (h7 << 3);
wolfSSL 4:1b0d80432c79 499 s[23] = h7 >> 5;
wolfSSL 4:1b0d80432c79 500 s[24] = h7 >> 13;
wolfSSL 4:1b0d80432c79 501 s[25] = (h7 >> 21) | (h8 << 4);
wolfSSL 4:1b0d80432c79 502 s[26] = h8 >> 4;
wolfSSL 4:1b0d80432c79 503 s[27] = h8 >> 12;
wolfSSL 4:1b0d80432c79 504 s[28] = (h8 >> 20) | (h9 << 6);
wolfSSL 4:1b0d80432c79 505 s[29] = h9 >> 2;
wolfSSL 4:1b0d80432c79 506 s[30] = h9 >> 10;
wolfSSL 4:1b0d80432c79 507 s[31] = h9 >> 18;
wolfSSL 4:1b0d80432c79 508 }
wolfSSL 4:1b0d80432c79 509
wolfSSL 4:1b0d80432c79 510
wolfSSL 4:1b0d80432c79 511 /*
wolfSSL 4:1b0d80432c79 512 h = f - g
wolfSSL 4:1b0d80432c79 513 Can overlap h with f or g.
wolfSSL 4:1b0d80432c79 514
wolfSSL 4:1b0d80432c79 515 Preconditions:
wolfSSL 4:1b0d80432c79 516 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 517 |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 518
wolfSSL 4:1b0d80432c79 519 Postconditions:
wolfSSL 4:1b0d80432c79 520 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
wolfSSL 4:1b0d80432c79 521 */
wolfSSL 4:1b0d80432c79 522
wolfSSL 4:1b0d80432c79 523 void fe_sub(fe h,const fe f,const fe g)
wolfSSL 4:1b0d80432c79 524 {
wolfSSL 4:1b0d80432c79 525 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 526 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 527 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 528 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 529 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 530 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 531 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 532 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 533 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 534 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 535 int32_t g0 = g[0];
wolfSSL 4:1b0d80432c79 536 int32_t g1 = g[1];
wolfSSL 4:1b0d80432c79 537 int32_t g2 = g[2];
wolfSSL 4:1b0d80432c79 538 int32_t g3 = g[3];
wolfSSL 4:1b0d80432c79 539 int32_t g4 = g[4];
wolfSSL 4:1b0d80432c79 540 int32_t g5 = g[5];
wolfSSL 4:1b0d80432c79 541 int32_t g6 = g[6];
wolfSSL 4:1b0d80432c79 542 int32_t g7 = g[7];
wolfSSL 4:1b0d80432c79 543 int32_t g8 = g[8];
wolfSSL 4:1b0d80432c79 544 int32_t g9 = g[9];
wolfSSL 4:1b0d80432c79 545 int32_t h0 = f0 - g0;
wolfSSL 4:1b0d80432c79 546 int32_t h1 = f1 - g1;
wolfSSL 4:1b0d80432c79 547 int32_t h2 = f2 - g2;
wolfSSL 4:1b0d80432c79 548 int32_t h3 = f3 - g3;
wolfSSL 4:1b0d80432c79 549 int32_t h4 = f4 - g4;
wolfSSL 4:1b0d80432c79 550 int32_t h5 = f5 - g5;
wolfSSL 4:1b0d80432c79 551 int32_t h6 = f6 - g6;
wolfSSL 4:1b0d80432c79 552 int32_t h7 = f7 - g7;
wolfSSL 4:1b0d80432c79 553 int32_t h8 = f8 - g8;
wolfSSL 4:1b0d80432c79 554 int32_t h9 = f9 - g9;
wolfSSL 4:1b0d80432c79 555 h[0] = h0;
wolfSSL 4:1b0d80432c79 556 h[1] = h1;
wolfSSL 4:1b0d80432c79 557 h[2] = h2;
wolfSSL 4:1b0d80432c79 558 h[3] = h3;
wolfSSL 4:1b0d80432c79 559 h[4] = h4;
wolfSSL 4:1b0d80432c79 560 h[5] = h5;
wolfSSL 4:1b0d80432c79 561 h[6] = h6;
wolfSSL 4:1b0d80432c79 562 h[7] = h7;
wolfSSL 4:1b0d80432c79 563 h[8] = h8;
wolfSSL 4:1b0d80432c79 564 h[9] = h9;
wolfSSL 4:1b0d80432c79 565 }
wolfSSL 4:1b0d80432c79 566
wolfSSL 4:1b0d80432c79 567
wolfSSL 4:1b0d80432c79 568 /*
wolfSSL 4:1b0d80432c79 569 Ignores top bit of h.
wolfSSL 4:1b0d80432c79 570 */
wolfSSL 4:1b0d80432c79 571
wolfSSL 4:1b0d80432c79 572 void fe_frombytes(fe h,const unsigned char *s)
wolfSSL 4:1b0d80432c79 573 {
wolfSSL 4:1b0d80432c79 574 int64_t h0 = load_4(s);
wolfSSL 4:1b0d80432c79 575 int64_t h1 = load_3(s + 4) << 6;
wolfSSL 4:1b0d80432c79 576 int64_t h2 = load_3(s + 7) << 5;
wolfSSL 4:1b0d80432c79 577 int64_t h3 = load_3(s + 10) << 3;
wolfSSL 4:1b0d80432c79 578 int64_t h4 = load_3(s + 13) << 2;
wolfSSL 4:1b0d80432c79 579 int64_t h5 = load_4(s + 16);
wolfSSL 4:1b0d80432c79 580 int64_t h6 = load_3(s + 20) << 7;
wolfSSL 4:1b0d80432c79 581 int64_t h7 = load_3(s + 23) << 5;
wolfSSL 4:1b0d80432c79 582 int64_t h8 = load_3(s + 26) << 4;
wolfSSL 4:1b0d80432c79 583 int64_t h9 = (load_3(s + 29) & 8388607) << 2;
wolfSSL 4:1b0d80432c79 584 int64_t carry0;
wolfSSL 4:1b0d80432c79 585 int64_t carry1;
wolfSSL 4:1b0d80432c79 586 int64_t carry2;
wolfSSL 4:1b0d80432c79 587 int64_t carry3;
wolfSSL 4:1b0d80432c79 588 int64_t carry4;
wolfSSL 4:1b0d80432c79 589 int64_t carry5;
wolfSSL 4:1b0d80432c79 590 int64_t carry6;
wolfSSL 4:1b0d80432c79 591 int64_t carry7;
wolfSSL 4:1b0d80432c79 592 int64_t carry8;
wolfSSL 4:1b0d80432c79 593 int64_t carry9;
wolfSSL 4:1b0d80432c79 594
wolfSSL 4:1b0d80432c79 595 carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
wolfSSL 4:1b0d80432c79 596 carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
wolfSSL 4:1b0d80432c79 597 carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
wolfSSL 4:1b0d80432c79 598 carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
wolfSSL 4:1b0d80432c79 599 carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
wolfSSL 4:1b0d80432c79 600
wolfSSL 4:1b0d80432c79 601 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 602 carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
wolfSSL 4:1b0d80432c79 603 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 604 carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
wolfSSL 4:1b0d80432c79 605 carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
wolfSSL 4:1b0d80432c79 606
wolfSSL 4:1b0d80432c79 607 h[0] = (int32_t)h0;
wolfSSL 4:1b0d80432c79 608 h[1] = (int32_t)h1;
wolfSSL 4:1b0d80432c79 609 h[2] = (int32_t)h2;
wolfSSL 4:1b0d80432c79 610 h[3] = (int32_t)h3;
wolfSSL 4:1b0d80432c79 611 h[4] = (int32_t)h4;
wolfSSL 4:1b0d80432c79 612 h[5] = (int32_t)h5;
wolfSSL 4:1b0d80432c79 613 h[6] = (int32_t)h6;
wolfSSL 4:1b0d80432c79 614 h[7] = (int32_t)h7;
wolfSSL 4:1b0d80432c79 615 h[8] = (int32_t)h8;
wolfSSL 4:1b0d80432c79 616 h[9] = (int32_t)h9;
wolfSSL 4:1b0d80432c79 617 }
wolfSSL 4:1b0d80432c79 618
wolfSSL 4:1b0d80432c79 619
wolfSSL 4:1b0d80432c79 620 void fe_invert(fe out,const fe z)
wolfSSL 4:1b0d80432c79 621 {
wolfSSL 4:1b0d80432c79 622 fe t0;
wolfSSL 4:1b0d80432c79 623 fe t1;
wolfSSL 4:1b0d80432c79 624 fe t2;
wolfSSL 4:1b0d80432c79 625 fe t3;
wolfSSL 4:1b0d80432c79 626 int i;
wolfSSL 4:1b0d80432c79 627
wolfSSL 4:1b0d80432c79 628 /* pow225521 */
wolfSSL 4:1b0d80432c79 629 fe_sq(t0,z); for (i = 1;i < 1;++i) fe_sq(t0,t0);
wolfSSL 4:1b0d80432c79 630 fe_sq(t1,t0); for (i = 1;i < 2;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 631 fe_mul(t1,z,t1);
wolfSSL 4:1b0d80432c79 632 fe_mul(t0,t0,t1);
wolfSSL 4:1b0d80432c79 633 fe_sq(t2,t0); for (i = 1;i < 1;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 634 fe_mul(t1,t1,t2);
wolfSSL 4:1b0d80432c79 635 fe_sq(t2,t1); for (i = 1;i < 5;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 636 fe_mul(t1,t2,t1);
wolfSSL 4:1b0d80432c79 637 fe_sq(t2,t1); for (i = 1;i < 10;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 638 fe_mul(t2,t2,t1);
wolfSSL 4:1b0d80432c79 639 fe_sq(t3,t2); for (i = 1;i < 20;++i) fe_sq(t3,t3);
wolfSSL 4:1b0d80432c79 640 fe_mul(t2,t3,t2);
wolfSSL 4:1b0d80432c79 641 fe_sq(t2,t2); for (i = 1;i < 10;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 642 fe_mul(t1,t2,t1);
wolfSSL 4:1b0d80432c79 643 fe_sq(t2,t1); for (i = 1;i < 50;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 644 fe_mul(t2,t2,t1);
wolfSSL 4:1b0d80432c79 645 fe_sq(t3,t2); for (i = 1;i < 100;++i) fe_sq(t3,t3);
wolfSSL 4:1b0d80432c79 646 fe_mul(t2,t3,t2);
wolfSSL 4:1b0d80432c79 647 fe_sq(t2,t2); for (i = 1;i < 50;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 648 fe_mul(t1,t2,t1);
wolfSSL 4:1b0d80432c79 649 fe_sq(t1,t1); for (i = 1;i < 5;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 650 fe_mul(out,t1,t0);
wolfSSL 4:1b0d80432c79 651
wolfSSL 4:1b0d80432c79 652 return;
wolfSSL 4:1b0d80432c79 653 }
wolfSSL 4:1b0d80432c79 654
wolfSSL 4:1b0d80432c79 655
wolfSSL 4:1b0d80432c79 656 /*
wolfSSL 4:1b0d80432c79 657 h = f
wolfSSL 4:1b0d80432c79 658 */
wolfSSL 4:1b0d80432c79 659
wolfSSL 4:1b0d80432c79 660 void fe_copy(fe h,const fe f)
wolfSSL 4:1b0d80432c79 661 {
wolfSSL 4:1b0d80432c79 662 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 663 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 664 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 665 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 666 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 667 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 668 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 669 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 670 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 671 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 672 h[0] = f0;
wolfSSL 4:1b0d80432c79 673 h[1] = f1;
wolfSSL 4:1b0d80432c79 674 h[2] = f2;
wolfSSL 4:1b0d80432c79 675 h[3] = f3;
wolfSSL 4:1b0d80432c79 676 h[4] = f4;
wolfSSL 4:1b0d80432c79 677 h[5] = f5;
wolfSSL 4:1b0d80432c79 678 h[6] = f6;
wolfSSL 4:1b0d80432c79 679 h[7] = f7;
wolfSSL 4:1b0d80432c79 680 h[8] = f8;
wolfSSL 4:1b0d80432c79 681 h[9] = f9;
wolfSSL 4:1b0d80432c79 682 }
wolfSSL 4:1b0d80432c79 683
wolfSSL 4:1b0d80432c79 684
wolfSSL 4:1b0d80432c79 685 /*
wolfSSL 4:1b0d80432c79 686 h = f * g
wolfSSL 4:1b0d80432c79 687 Can overlap h with f or g.
wolfSSL 4:1b0d80432c79 688
wolfSSL 4:1b0d80432c79 689 Preconditions:
wolfSSL 4:1b0d80432c79 690 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
wolfSSL 4:1b0d80432c79 691 |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
wolfSSL 4:1b0d80432c79 692
wolfSSL 4:1b0d80432c79 693 Postconditions:
wolfSSL 4:1b0d80432c79 694 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
wolfSSL 4:1b0d80432c79 695 */
wolfSSL 4:1b0d80432c79 696
wolfSSL 4:1b0d80432c79 697 /*
wolfSSL 4:1b0d80432c79 698 Notes on implementation strategy:
wolfSSL 4:1b0d80432c79 699
wolfSSL 4:1b0d80432c79 700 Using schoolbook multiplication.
wolfSSL 4:1b0d80432c79 701 Karatsuba would save a little in some cost models.
wolfSSL 4:1b0d80432c79 702
wolfSSL 4:1b0d80432c79 703 Most multiplications by 2 and 19 are 32-bit precomputations;
wolfSSL 4:1b0d80432c79 704 cheaper than 64-bit postcomputations.
wolfSSL 4:1b0d80432c79 705
wolfSSL 4:1b0d80432c79 706 There is one remaining multiplication by 19 in the carry chain;
wolfSSL 4:1b0d80432c79 707 one *19 precomputation can be merged into this,
wolfSSL 4:1b0d80432c79 708 but the resulting data flow is considerably less clean.
wolfSSL 4:1b0d80432c79 709
wolfSSL 4:1b0d80432c79 710 There are 12 carries below.
wolfSSL 4:1b0d80432c79 711 10 of them are 2-way parallelizable and vectorizable.
wolfSSL 4:1b0d80432c79 712 Can get away with 11 carries, but then data flow is much deeper.
wolfSSL 4:1b0d80432c79 713
wolfSSL 4:1b0d80432c79 714 With tighter constraints on inputs can squeeze carries into int32.
wolfSSL 4:1b0d80432c79 715 */
wolfSSL 4:1b0d80432c79 716
wolfSSL 4:1b0d80432c79 717 void fe_mul(fe h,const fe f,const fe g)
wolfSSL 4:1b0d80432c79 718 {
wolfSSL 4:1b0d80432c79 719 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 720 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 721 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 722 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 723 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 724 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 725 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 726 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 727 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 728 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 729 int32_t g0 = g[0];
wolfSSL 4:1b0d80432c79 730 int32_t g1 = g[1];
wolfSSL 4:1b0d80432c79 731 int32_t g2 = g[2];
wolfSSL 4:1b0d80432c79 732 int32_t g3 = g[3];
wolfSSL 4:1b0d80432c79 733 int32_t g4 = g[4];
wolfSSL 4:1b0d80432c79 734 int32_t g5 = g[5];
wolfSSL 4:1b0d80432c79 735 int32_t g6 = g[6];
wolfSSL 4:1b0d80432c79 736 int32_t g7 = g[7];
wolfSSL 4:1b0d80432c79 737 int32_t g8 = g[8];
wolfSSL 4:1b0d80432c79 738 int32_t g9 = g[9];
wolfSSL 4:1b0d80432c79 739 int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */
wolfSSL 4:1b0d80432c79 740 int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */
wolfSSL 4:1b0d80432c79 741 int32_t g3_19 = 19 * g3;
wolfSSL 4:1b0d80432c79 742 int32_t g4_19 = 19 * g4;
wolfSSL 4:1b0d80432c79 743 int32_t g5_19 = 19 * g5;
wolfSSL 4:1b0d80432c79 744 int32_t g6_19 = 19 * g6;
wolfSSL 4:1b0d80432c79 745 int32_t g7_19 = 19 * g7;
wolfSSL 4:1b0d80432c79 746 int32_t g8_19 = 19 * g8;
wolfSSL 4:1b0d80432c79 747 int32_t g9_19 = 19 * g9;
wolfSSL 4:1b0d80432c79 748 int32_t f1_2 = 2 * f1;
wolfSSL 4:1b0d80432c79 749 int32_t f3_2 = 2 * f3;
wolfSSL 4:1b0d80432c79 750 int32_t f5_2 = 2 * f5;
wolfSSL 4:1b0d80432c79 751 int32_t f7_2 = 2 * f7;
wolfSSL 4:1b0d80432c79 752 int32_t f9_2 = 2 * f9;
wolfSSL 4:1b0d80432c79 753 int64_t f0g0 = f0 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 754 int64_t f0g1 = f0 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 755 int64_t f0g2 = f0 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 756 int64_t f0g3 = f0 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 757 int64_t f0g4 = f0 * (int64_t) g4;
wolfSSL 4:1b0d80432c79 758 int64_t f0g5 = f0 * (int64_t) g5;
wolfSSL 4:1b0d80432c79 759 int64_t f0g6 = f0 * (int64_t) g6;
wolfSSL 4:1b0d80432c79 760 int64_t f0g7 = f0 * (int64_t) g7;
wolfSSL 4:1b0d80432c79 761 int64_t f0g8 = f0 * (int64_t) g8;
wolfSSL 4:1b0d80432c79 762 int64_t f0g9 = f0 * (int64_t) g9;
wolfSSL 4:1b0d80432c79 763 int64_t f1g0 = f1 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 764 int64_t f1g1_2 = f1_2 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 765 int64_t f1g2 = f1 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 766 int64_t f1g3_2 = f1_2 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 767 int64_t f1g4 = f1 * (int64_t) g4;
wolfSSL 4:1b0d80432c79 768 int64_t f1g5_2 = f1_2 * (int64_t) g5;
wolfSSL 4:1b0d80432c79 769 int64_t f1g6 = f1 * (int64_t) g6;
wolfSSL 4:1b0d80432c79 770 int64_t f1g7_2 = f1_2 * (int64_t) g7;
wolfSSL 4:1b0d80432c79 771 int64_t f1g8 = f1 * (int64_t) g8;
wolfSSL 4:1b0d80432c79 772 int64_t f1g9_38 = f1_2 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 773 int64_t f2g0 = f2 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 774 int64_t f2g1 = f2 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 775 int64_t f2g2 = f2 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 776 int64_t f2g3 = f2 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 777 int64_t f2g4 = f2 * (int64_t) g4;
wolfSSL 4:1b0d80432c79 778 int64_t f2g5 = f2 * (int64_t) g5;
wolfSSL 4:1b0d80432c79 779 int64_t f2g6 = f2 * (int64_t) g6;
wolfSSL 4:1b0d80432c79 780 int64_t f2g7 = f2 * (int64_t) g7;
wolfSSL 4:1b0d80432c79 781 int64_t f2g8_19 = f2 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 782 int64_t f2g9_19 = f2 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 783 int64_t f3g0 = f3 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 784 int64_t f3g1_2 = f3_2 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 785 int64_t f3g2 = f3 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 786 int64_t f3g3_2 = f3_2 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 787 int64_t f3g4 = f3 * (int64_t) g4;
wolfSSL 4:1b0d80432c79 788 int64_t f3g5_2 = f3_2 * (int64_t) g5;
wolfSSL 4:1b0d80432c79 789 int64_t f3g6 = f3 * (int64_t) g6;
wolfSSL 4:1b0d80432c79 790 int64_t f3g7_38 = f3_2 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 791 int64_t f3g8_19 = f3 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 792 int64_t f3g9_38 = f3_2 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 793 int64_t f4g0 = f4 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 794 int64_t f4g1 = f4 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 795 int64_t f4g2 = f4 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 796 int64_t f4g3 = f4 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 797 int64_t f4g4 = f4 * (int64_t) g4;
wolfSSL 4:1b0d80432c79 798 int64_t f4g5 = f4 * (int64_t) g5;
wolfSSL 4:1b0d80432c79 799 int64_t f4g6_19 = f4 * (int64_t) g6_19;
wolfSSL 4:1b0d80432c79 800 int64_t f4g7_19 = f4 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 801 int64_t f4g8_19 = f4 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 802 int64_t f4g9_19 = f4 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 803 int64_t f5g0 = f5 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 804 int64_t f5g1_2 = f5_2 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 805 int64_t f5g2 = f5 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 806 int64_t f5g3_2 = f5_2 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 807 int64_t f5g4 = f5 * (int64_t) g4;
wolfSSL 4:1b0d80432c79 808 int64_t f5g5_38 = f5_2 * (int64_t) g5_19;
wolfSSL 4:1b0d80432c79 809 int64_t f5g6_19 = f5 * (int64_t) g6_19;
wolfSSL 4:1b0d80432c79 810 int64_t f5g7_38 = f5_2 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 811 int64_t f5g8_19 = f5 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 812 int64_t f5g9_38 = f5_2 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 813 int64_t f6g0 = f6 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 814 int64_t f6g1 = f6 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 815 int64_t f6g2 = f6 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 816 int64_t f6g3 = f6 * (int64_t) g3;
wolfSSL 4:1b0d80432c79 817 int64_t f6g4_19 = f6 * (int64_t) g4_19;
wolfSSL 4:1b0d80432c79 818 int64_t f6g5_19 = f6 * (int64_t) g5_19;
wolfSSL 4:1b0d80432c79 819 int64_t f6g6_19 = f6 * (int64_t) g6_19;
wolfSSL 4:1b0d80432c79 820 int64_t f6g7_19 = f6 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 821 int64_t f6g8_19 = f6 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 822 int64_t f6g9_19 = f6 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 823 int64_t f7g0 = f7 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 824 int64_t f7g1_2 = f7_2 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 825 int64_t f7g2 = f7 * (int64_t) g2;
wolfSSL 4:1b0d80432c79 826 int64_t f7g3_38 = f7_2 * (int64_t) g3_19;
wolfSSL 4:1b0d80432c79 827 int64_t f7g4_19 = f7 * (int64_t) g4_19;
wolfSSL 4:1b0d80432c79 828 int64_t f7g5_38 = f7_2 * (int64_t) g5_19;
wolfSSL 4:1b0d80432c79 829 int64_t f7g6_19 = f7 * (int64_t) g6_19;
wolfSSL 4:1b0d80432c79 830 int64_t f7g7_38 = f7_2 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 831 int64_t f7g8_19 = f7 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 832 int64_t f7g9_38 = f7_2 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 833 int64_t f8g0 = f8 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 834 int64_t f8g1 = f8 * (int64_t) g1;
wolfSSL 4:1b0d80432c79 835 int64_t f8g2_19 = f8 * (int64_t) g2_19;
wolfSSL 4:1b0d80432c79 836 int64_t f8g3_19 = f8 * (int64_t) g3_19;
wolfSSL 4:1b0d80432c79 837 int64_t f8g4_19 = f8 * (int64_t) g4_19;
wolfSSL 4:1b0d80432c79 838 int64_t f8g5_19 = f8 * (int64_t) g5_19;
wolfSSL 4:1b0d80432c79 839 int64_t f8g6_19 = f8 * (int64_t) g6_19;
wolfSSL 4:1b0d80432c79 840 int64_t f8g7_19 = f8 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 841 int64_t f8g8_19 = f8 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 842 int64_t f8g9_19 = f8 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 843 int64_t f9g0 = f9 * (int64_t) g0;
wolfSSL 4:1b0d80432c79 844 int64_t f9g1_38 = f9_2 * (int64_t) g1_19;
wolfSSL 4:1b0d80432c79 845 int64_t f9g2_19 = f9 * (int64_t) g2_19;
wolfSSL 4:1b0d80432c79 846 int64_t f9g3_38 = f9_2 * (int64_t) g3_19;
wolfSSL 4:1b0d80432c79 847 int64_t f9g4_19 = f9 * (int64_t) g4_19;
wolfSSL 4:1b0d80432c79 848 int64_t f9g5_38 = f9_2 * (int64_t) g5_19;
wolfSSL 4:1b0d80432c79 849 int64_t f9g6_19 = f9 * (int64_t) g6_19;
wolfSSL 4:1b0d80432c79 850 int64_t f9g7_38 = f9_2 * (int64_t) g7_19;
wolfSSL 4:1b0d80432c79 851 int64_t f9g8_19 = f9 * (int64_t) g8_19;
wolfSSL 4:1b0d80432c79 852 int64_t f9g9_38 = f9_2 * (int64_t) g9_19;
wolfSSL 4:1b0d80432c79 853 int64_t h0 = f0g0+f1g9_38+f2g8_19+f3g7_38+f4g6_19+f5g5_38+f6g4_19+f7g3_38+f8g2_19+f9g1_38;
wolfSSL 4:1b0d80432c79 854 int64_t h1 = f0g1+f1g0 +f2g9_19+f3g8_19+f4g7_19+f5g6_19+f6g5_19+f7g4_19+f8g3_19+f9g2_19;
wolfSSL 4:1b0d80432c79 855 int64_t h2 = f0g2+f1g1_2 +f2g0 +f3g9_38+f4g8_19+f5g7_38+f6g6_19+f7g5_38+f8g4_19+f9g3_38;
wolfSSL 4:1b0d80432c79 856 int64_t h3 = f0g3+f1g2 +f2g1 +f3g0 +f4g9_19+f5g8_19+f6g7_19+f7g6_19+f8g5_19+f9g4_19;
wolfSSL 4:1b0d80432c79 857 int64_t h4 = f0g4+f1g3_2 +f2g2 +f3g1_2 +f4g0 +f5g9_38+f6g8_19+f7g7_38+f8g6_19+f9g5_38;
wolfSSL 4:1b0d80432c79 858 int64_t h5 = f0g5+f1g4 +f2g3 +f3g2 +f4g1 +f5g0 +f6g9_19+f7g8_19+f8g7_19+f9g6_19;
wolfSSL 4:1b0d80432c79 859 int64_t h6 = f0g6+f1g5_2 +f2g4 +f3g3_2 +f4g2 +f5g1_2 +f6g0 +f7g9_38+f8g8_19+f9g7_38;
wolfSSL 4:1b0d80432c79 860 int64_t h7 = f0g7+f1g6 +f2g5 +f3g4 +f4g3 +f5g2 +f6g1 +f7g0 +f8g9_19+f9g8_19;
wolfSSL 4:1b0d80432c79 861 int64_t h8 = f0g8+f1g7_2 +f2g6 +f3g5_2 +f4g4 +f5g3_2 +f6g2 +f7g1_2 +f8g0 +f9g9_38;
wolfSSL 4:1b0d80432c79 862 int64_t h9 = f0g9+f1g8 +f2g7 +f3g6 +f4g5 +f5g4 +f6g3 +f7g2 +f8g1 +f9g0 ;
wolfSSL 4:1b0d80432c79 863 int64_t carry0;
wolfSSL 4:1b0d80432c79 864 int64_t carry1;
wolfSSL 4:1b0d80432c79 865 int64_t carry2;
wolfSSL 4:1b0d80432c79 866 int64_t carry3;
wolfSSL 4:1b0d80432c79 867 int64_t carry4;
wolfSSL 4:1b0d80432c79 868 int64_t carry5;
wolfSSL 4:1b0d80432c79 869 int64_t carry6;
wolfSSL 4:1b0d80432c79 870 int64_t carry7;
wolfSSL 4:1b0d80432c79 871 int64_t carry8;
wolfSSL 4:1b0d80432c79 872 int64_t carry9;
wolfSSL 4:1b0d80432c79 873
wolfSSL 4:1b0d80432c79 874 /*
wolfSSL 4:1b0d80432c79 875 |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38))
wolfSSL 4:1b0d80432c79 876 i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8
wolfSSL 4:1b0d80432c79 877 |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19))
wolfSSL 4:1b0d80432c79 878 i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9
wolfSSL 4:1b0d80432c79 879 */
wolfSSL 4:1b0d80432c79 880
wolfSSL 4:1b0d80432c79 881 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 882 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 883 /* |h0| <= 2^25 */
wolfSSL 4:1b0d80432c79 884 /* |h4| <= 2^25 */
wolfSSL 4:1b0d80432c79 885 /* |h1| <= 1.71*2^59 */
wolfSSL 4:1b0d80432c79 886 /* |h5| <= 1.71*2^59 */
wolfSSL 4:1b0d80432c79 887
wolfSSL 4:1b0d80432c79 888 carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
wolfSSL 4:1b0d80432c79 889 carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
wolfSSL 4:1b0d80432c79 890 /* |h1| <= 2^24; from now on fits into int32 */
wolfSSL 4:1b0d80432c79 891 /* |h5| <= 2^24; from now on fits into int32 */
wolfSSL 4:1b0d80432c79 892 /* |h2| <= 1.41*2^60 */
wolfSSL 4:1b0d80432c79 893 /* |h6| <= 1.41*2^60 */
wolfSSL 4:1b0d80432c79 894
wolfSSL 4:1b0d80432c79 895 carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
wolfSSL 4:1b0d80432c79 896 carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
wolfSSL 4:1b0d80432c79 897 /* |h2| <= 2^25; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 898 /* |h6| <= 2^25; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 899 /* |h3| <= 1.71*2^59 */
wolfSSL 4:1b0d80432c79 900 /* |h7| <= 1.71*2^59 */
wolfSSL 4:1b0d80432c79 901
wolfSSL 4:1b0d80432c79 902 carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
wolfSSL 4:1b0d80432c79 903 carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
wolfSSL 4:1b0d80432c79 904 /* |h3| <= 2^24; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 905 /* |h7| <= 2^24; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 906 /* |h4| <= 1.72*2^34 */
wolfSSL 4:1b0d80432c79 907 /* |h8| <= 1.41*2^60 */
wolfSSL 4:1b0d80432c79 908
wolfSSL 4:1b0d80432c79 909 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 910 carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
wolfSSL 4:1b0d80432c79 911 /* |h4| <= 2^25; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 912 /* |h8| <= 2^25; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 913 /* |h5| <= 1.01*2^24 */
wolfSSL 4:1b0d80432c79 914 /* |h9| <= 1.71*2^59 */
wolfSSL 4:1b0d80432c79 915
wolfSSL 4:1b0d80432c79 916 carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
wolfSSL 4:1b0d80432c79 917 /* |h9| <= 2^24; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 918 /* |h0| <= 1.1*2^39 */
wolfSSL 4:1b0d80432c79 919
wolfSSL 4:1b0d80432c79 920 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 921 /* |h0| <= 2^25; from now on fits into int32 unchanged */
wolfSSL 4:1b0d80432c79 922 /* |h1| <= 1.01*2^24 */
wolfSSL 4:1b0d80432c79 923
wolfSSL 4:1b0d80432c79 924 h[0] = (int32_t)h0;
wolfSSL 4:1b0d80432c79 925 h[1] = (int32_t)h1;
wolfSSL 4:1b0d80432c79 926 h[2] = (int32_t)h2;
wolfSSL 4:1b0d80432c79 927 h[3] = (int32_t)h3;
wolfSSL 4:1b0d80432c79 928 h[4] = (int32_t)h4;
wolfSSL 4:1b0d80432c79 929 h[5] = (int32_t)h5;
wolfSSL 4:1b0d80432c79 930 h[6] = (int32_t)h6;
wolfSSL 4:1b0d80432c79 931 h[7] = (int32_t)h7;
wolfSSL 4:1b0d80432c79 932 h[8] = (int32_t)h8;
wolfSSL 4:1b0d80432c79 933 h[9] = (int32_t)h9;
wolfSSL 4:1b0d80432c79 934 }
wolfSSL 4:1b0d80432c79 935
wolfSSL 4:1b0d80432c79 936
wolfSSL 4:1b0d80432c79 937 /*
wolfSSL 4:1b0d80432c79 938 Replace (f,g) with (g,f) if b == 1;
wolfSSL 4:1b0d80432c79 939 replace (f,g) with (f,g) if b == 0.
wolfSSL 4:1b0d80432c79 940
wolfSSL 4:1b0d80432c79 941 Preconditions: b in {0,1}.
wolfSSL 4:1b0d80432c79 942 */
wolfSSL 4:1b0d80432c79 943
wolfSSL 4:1b0d80432c79 944 void fe_cswap(fe f,fe g,unsigned int b)
wolfSSL 4:1b0d80432c79 945 {
wolfSSL 4:1b0d80432c79 946 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 947 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 948 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 949 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 950 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 951 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 952 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 953 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 954 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 955 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 956 int32_t g0 = g[0];
wolfSSL 4:1b0d80432c79 957 int32_t g1 = g[1];
wolfSSL 4:1b0d80432c79 958 int32_t g2 = g[2];
wolfSSL 4:1b0d80432c79 959 int32_t g3 = g[3];
wolfSSL 4:1b0d80432c79 960 int32_t g4 = g[4];
wolfSSL 4:1b0d80432c79 961 int32_t g5 = g[5];
wolfSSL 4:1b0d80432c79 962 int32_t g6 = g[6];
wolfSSL 4:1b0d80432c79 963 int32_t g7 = g[7];
wolfSSL 4:1b0d80432c79 964 int32_t g8 = g[8];
wolfSSL 4:1b0d80432c79 965 int32_t g9 = g[9];
wolfSSL 4:1b0d80432c79 966 int32_t x0 = f0 ^ g0;
wolfSSL 4:1b0d80432c79 967 int32_t x1 = f1 ^ g1;
wolfSSL 4:1b0d80432c79 968 int32_t x2 = f2 ^ g2;
wolfSSL 4:1b0d80432c79 969 int32_t x3 = f3 ^ g3;
wolfSSL 4:1b0d80432c79 970 int32_t x4 = f4 ^ g4;
wolfSSL 4:1b0d80432c79 971 int32_t x5 = f5 ^ g5;
wolfSSL 4:1b0d80432c79 972 int32_t x6 = f6 ^ g6;
wolfSSL 4:1b0d80432c79 973 int32_t x7 = f7 ^ g7;
wolfSSL 4:1b0d80432c79 974 int32_t x8 = f8 ^ g8;
wolfSSL 4:1b0d80432c79 975 int32_t x9 = f9 ^ g9;
wolfSSL 4:1b0d80432c79 976 b = -b;
wolfSSL 4:1b0d80432c79 977 x0 &= b;
wolfSSL 4:1b0d80432c79 978 x1 &= b;
wolfSSL 4:1b0d80432c79 979 x2 &= b;
wolfSSL 4:1b0d80432c79 980 x3 &= b;
wolfSSL 4:1b0d80432c79 981 x4 &= b;
wolfSSL 4:1b0d80432c79 982 x5 &= b;
wolfSSL 4:1b0d80432c79 983 x6 &= b;
wolfSSL 4:1b0d80432c79 984 x7 &= b;
wolfSSL 4:1b0d80432c79 985 x8 &= b;
wolfSSL 4:1b0d80432c79 986 x9 &= b;
wolfSSL 4:1b0d80432c79 987 f[0] = f0 ^ x0;
wolfSSL 4:1b0d80432c79 988 f[1] = f1 ^ x1;
wolfSSL 4:1b0d80432c79 989 f[2] = f2 ^ x2;
wolfSSL 4:1b0d80432c79 990 f[3] = f3 ^ x3;
wolfSSL 4:1b0d80432c79 991 f[4] = f4 ^ x4;
wolfSSL 4:1b0d80432c79 992 f[5] = f5 ^ x5;
wolfSSL 4:1b0d80432c79 993 f[6] = f6 ^ x6;
wolfSSL 4:1b0d80432c79 994 f[7] = f7 ^ x7;
wolfSSL 4:1b0d80432c79 995 f[8] = f8 ^ x8;
wolfSSL 4:1b0d80432c79 996 f[9] = f9 ^ x9;
wolfSSL 4:1b0d80432c79 997 g[0] = g0 ^ x0;
wolfSSL 4:1b0d80432c79 998 g[1] = g1 ^ x1;
wolfSSL 4:1b0d80432c79 999 g[2] = g2 ^ x2;
wolfSSL 4:1b0d80432c79 1000 g[3] = g3 ^ x3;
wolfSSL 4:1b0d80432c79 1001 g[4] = g4 ^ x4;
wolfSSL 4:1b0d80432c79 1002 g[5] = g5 ^ x5;
wolfSSL 4:1b0d80432c79 1003 g[6] = g6 ^ x6;
wolfSSL 4:1b0d80432c79 1004 g[7] = g7 ^ x7;
wolfSSL 4:1b0d80432c79 1005 g[8] = g8 ^ x8;
wolfSSL 4:1b0d80432c79 1006 g[9] = g9 ^ x9;
wolfSSL 4:1b0d80432c79 1007 }
wolfSSL 4:1b0d80432c79 1008
wolfSSL 4:1b0d80432c79 1009
wolfSSL 4:1b0d80432c79 1010 /*
wolfSSL 4:1b0d80432c79 1011 h = f * 121666
wolfSSL 4:1b0d80432c79 1012 Can overlap h with f.
wolfSSL 4:1b0d80432c79 1013
wolfSSL 4:1b0d80432c79 1014 Preconditions:
wolfSSL 4:1b0d80432c79 1015 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
wolfSSL 4:1b0d80432c79 1016
wolfSSL 4:1b0d80432c79 1017 Postconditions:
wolfSSL 4:1b0d80432c79 1018 |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 1019 */
wolfSSL 4:1b0d80432c79 1020
wolfSSL 4:1b0d80432c79 1021 void fe_mul121666(fe h,fe f)
wolfSSL 4:1b0d80432c79 1022 {
wolfSSL 4:1b0d80432c79 1023 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 1024 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 1025 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 1026 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 1027 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 1028 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 1029 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 1030 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 1031 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 1032 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 1033 int64_t h0 = f0 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1034 int64_t h1 = f1 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1035 int64_t h2 = f2 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1036 int64_t h3 = f3 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1037 int64_t h4 = f4 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1038 int64_t h5 = f5 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1039 int64_t h6 = f6 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1040 int64_t h7 = f7 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1041 int64_t h8 = f8 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1042 int64_t h9 = f9 * (int64_t) 121666;
wolfSSL 4:1b0d80432c79 1043 int64_t carry0;
wolfSSL 4:1b0d80432c79 1044 int64_t carry1;
wolfSSL 4:1b0d80432c79 1045 int64_t carry2;
wolfSSL 4:1b0d80432c79 1046 int64_t carry3;
wolfSSL 4:1b0d80432c79 1047 int64_t carry4;
wolfSSL 4:1b0d80432c79 1048 int64_t carry5;
wolfSSL 4:1b0d80432c79 1049 int64_t carry6;
wolfSSL 4:1b0d80432c79 1050 int64_t carry7;
wolfSSL 4:1b0d80432c79 1051 int64_t carry8;
wolfSSL 4:1b0d80432c79 1052 int64_t carry9;
wolfSSL 4:1b0d80432c79 1053
wolfSSL 4:1b0d80432c79 1054 carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
wolfSSL 4:1b0d80432c79 1055 carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
wolfSSL 4:1b0d80432c79 1056 carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
wolfSSL 4:1b0d80432c79 1057 carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
wolfSSL 4:1b0d80432c79 1058 carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
wolfSSL 4:1b0d80432c79 1059
wolfSSL 4:1b0d80432c79 1060 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 1061 carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
wolfSSL 4:1b0d80432c79 1062 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 1063 carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
wolfSSL 4:1b0d80432c79 1064 carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
wolfSSL 4:1b0d80432c79 1065
wolfSSL 4:1b0d80432c79 1066 h[0] = (int32_t)h0;
wolfSSL 4:1b0d80432c79 1067 h[1] = (int32_t)h1;
wolfSSL 4:1b0d80432c79 1068 h[2] = (int32_t)h2;
wolfSSL 4:1b0d80432c79 1069 h[3] = (int32_t)h3;
wolfSSL 4:1b0d80432c79 1070 h[4] = (int32_t)h4;
wolfSSL 4:1b0d80432c79 1071 h[5] = (int32_t)h5;
wolfSSL 4:1b0d80432c79 1072 h[6] = (int32_t)h6;
wolfSSL 4:1b0d80432c79 1073 h[7] = (int32_t)h7;
wolfSSL 4:1b0d80432c79 1074 h[8] = (int32_t)h8;
wolfSSL 4:1b0d80432c79 1075 h[9] = (int32_t)h9;
wolfSSL 4:1b0d80432c79 1076 }
wolfSSL 4:1b0d80432c79 1077
wolfSSL 4:1b0d80432c79 1078
wolfSSL 4:1b0d80432c79 1079 /*
wolfSSL 4:1b0d80432c79 1080 h = 2 * f * f
wolfSSL 4:1b0d80432c79 1081 Can overlap h with f.
wolfSSL 4:1b0d80432c79 1082
wolfSSL 4:1b0d80432c79 1083 Preconditions:
wolfSSL 4:1b0d80432c79 1084 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
wolfSSL 4:1b0d80432c79 1085
wolfSSL 4:1b0d80432c79 1086 Postconditions:
wolfSSL 4:1b0d80432c79 1087 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
wolfSSL 4:1b0d80432c79 1088 */
wolfSSL 4:1b0d80432c79 1089
wolfSSL 4:1b0d80432c79 1090 /*
wolfSSL 4:1b0d80432c79 1091 See fe_mul.c for discussion of implementation strategy.
wolfSSL 4:1b0d80432c79 1092 */
wolfSSL 4:1b0d80432c79 1093
wolfSSL 4:1b0d80432c79 1094 void fe_sq2(fe h,const fe f)
wolfSSL 4:1b0d80432c79 1095 {
wolfSSL 4:1b0d80432c79 1096 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 1097 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 1098 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 1099 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 1100 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 1101 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 1102 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 1103 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 1104 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 1105 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 1106 int32_t f0_2 = 2 * f0;
wolfSSL 4:1b0d80432c79 1107 int32_t f1_2 = 2 * f1;
wolfSSL 4:1b0d80432c79 1108 int32_t f2_2 = 2 * f2;
wolfSSL 4:1b0d80432c79 1109 int32_t f3_2 = 2 * f3;
wolfSSL 4:1b0d80432c79 1110 int32_t f4_2 = 2 * f4;
wolfSSL 4:1b0d80432c79 1111 int32_t f5_2 = 2 * f5;
wolfSSL 4:1b0d80432c79 1112 int32_t f6_2 = 2 * f6;
wolfSSL 4:1b0d80432c79 1113 int32_t f7_2 = 2 * f7;
wolfSSL 4:1b0d80432c79 1114 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 1115 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 1116 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 1117 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 1118 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
wolfSSL 4:1b0d80432c79 1119 int64_t f0f0 = f0 * (int64_t) f0;
wolfSSL 4:1b0d80432c79 1120 int64_t f0f1_2 = f0_2 * (int64_t) f1;
wolfSSL 4:1b0d80432c79 1121 int64_t f0f2_2 = f0_2 * (int64_t) f2;
wolfSSL 4:1b0d80432c79 1122 int64_t f0f3_2 = f0_2 * (int64_t) f3;
wolfSSL 4:1b0d80432c79 1123 int64_t f0f4_2 = f0_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 1124 int64_t f0f5_2 = f0_2 * (int64_t) f5;
wolfSSL 4:1b0d80432c79 1125 int64_t f0f6_2 = f0_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 1126 int64_t f0f7_2 = f0_2 * (int64_t) f7;
wolfSSL 4:1b0d80432c79 1127 int64_t f0f8_2 = f0_2 * (int64_t) f8;
wolfSSL 4:1b0d80432c79 1128 int64_t f0f9_2 = f0_2 * (int64_t) f9;
wolfSSL 4:1b0d80432c79 1129 int64_t f1f1_2 = f1_2 * (int64_t) f1;
wolfSSL 4:1b0d80432c79 1130 int64_t f1f2_2 = f1_2 * (int64_t) f2;
wolfSSL 4:1b0d80432c79 1131 int64_t f1f3_4 = f1_2 * (int64_t) f3_2;
wolfSSL 4:1b0d80432c79 1132 int64_t f1f4_2 = f1_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 1133 int64_t f1f5_4 = f1_2 * (int64_t) f5_2;
wolfSSL 4:1b0d80432c79 1134 int64_t f1f6_2 = f1_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 1135 int64_t f1f7_4 = f1_2 * (int64_t) f7_2;
wolfSSL 4:1b0d80432c79 1136 int64_t f1f8_2 = f1_2 * (int64_t) f8;
wolfSSL 4:1b0d80432c79 1137 int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1138 int64_t f2f2 = f2 * (int64_t) f2;
wolfSSL 4:1b0d80432c79 1139 int64_t f2f3_2 = f2_2 * (int64_t) f3;
wolfSSL 4:1b0d80432c79 1140 int64_t f2f4_2 = f2_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 1141 int64_t f2f5_2 = f2_2 * (int64_t) f5;
wolfSSL 4:1b0d80432c79 1142 int64_t f2f6_2 = f2_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 1143 int64_t f2f7_2 = f2_2 * (int64_t) f7;
wolfSSL 4:1b0d80432c79 1144 int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1145 int64_t f2f9_38 = f2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1146 int64_t f3f3_2 = f3_2 * (int64_t) f3;
wolfSSL 4:1b0d80432c79 1147 int64_t f3f4_2 = f3_2 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 1148 int64_t f3f5_4 = f3_2 * (int64_t) f5_2;
wolfSSL 4:1b0d80432c79 1149 int64_t f3f6_2 = f3_2 * (int64_t) f6;
wolfSSL 4:1b0d80432c79 1150 int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 1151 int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1152 int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1153 int64_t f4f4 = f4 * (int64_t) f4;
wolfSSL 4:1b0d80432c79 1154 int64_t f4f5_2 = f4_2 * (int64_t) f5;
wolfSSL 4:1b0d80432c79 1155 int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
wolfSSL 4:1b0d80432c79 1156 int64_t f4f7_38 = f4 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 1157 int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1158 int64_t f4f9_38 = f4 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1159 int64_t f5f5_38 = f5 * (int64_t) f5_38;
wolfSSL 4:1b0d80432c79 1160 int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
wolfSSL 4:1b0d80432c79 1161 int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 1162 int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1163 int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1164 int64_t f6f6_19 = f6 * (int64_t) f6_19;
wolfSSL 4:1b0d80432c79 1165 int64_t f6f7_38 = f6 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 1166 int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1167 int64_t f6f9_38 = f6 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1168 int64_t f7f7_38 = f7 * (int64_t) f7_38;
wolfSSL 4:1b0d80432c79 1169 int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1170 int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1171 int64_t f8f8_19 = f8 * (int64_t) f8_19;
wolfSSL 4:1b0d80432c79 1172 int64_t f8f9_38 = f8 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1173 int64_t f9f9_38 = f9 * (int64_t) f9_38;
wolfSSL 4:1b0d80432c79 1174 int64_t h0 = f0f0 +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;
wolfSSL 4:1b0d80432c79 1175 int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;
wolfSSL 4:1b0d80432c79 1176 int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;
wolfSSL 4:1b0d80432c79 1177 int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;
wolfSSL 4:1b0d80432c79 1178 int64_t h4 = f0f4_2+f1f3_4 +f2f2 +f5f9_76+f6f8_38+f7f7_38;
wolfSSL 4:1b0d80432c79 1179 int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;
wolfSSL 4:1b0d80432c79 1180 int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;
wolfSSL 4:1b0d80432c79 1181 int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;
wolfSSL 4:1b0d80432c79 1182 int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4 +f9f9_38;
wolfSSL 4:1b0d80432c79 1183 int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;
wolfSSL 4:1b0d80432c79 1184 int64_t carry0;
wolfSSL 4:1b0d80432c79 1185 int64_t carry1;
wolfSSL 4:1b0d80432c79 1186 int64_t carry2;
wolfSSL 4:1b0d80432c79 1187 int64_t carry3;
wolfSSL 4:1b0d80432c79 1188 int64_t carry4;
wolfSSL 4:1b0d80432c79 1189 int64_t carry5;
wolfSSL 4:1b0d80432c79 1190 int64_t carry6;
wolfSSL 4:1b0d80432c79 1191 int64_t carry7;
wolfSSL 4:1b0d80432c79 1192 int64_t carry8;
wolfSSL 4:1b0d80432c79 1193 int64_t carry9;
wolfSSL 4:1b0d80432c79 1194
wolfSSL 4:1b0d80432c79 1195 h0 += h0;
wolfSSL 4:1b0d80432c79 1196 h1 += h1;
wolfSSL 4:1b0d80432c79 1197 h2 += h2;
wolfSSL 4:1b0d80432c79 1198 h3 += h3;
wolfSSL 4:1b0d80432c79 1199 h4 += h4;
wolfSSL 4:1b0d80432c79 1200 h5 += h5;
wolfSSL 4:1b0d80432c79 1201 h6 += h6;
wolfSSL 4:1b0d80432c79 1202 h7 += h7;
wolfSSL 4:1b0d80432c79 1203 h8 += h8;
wolfSSL 4:1b0d80432c79 1204 h9 += h9;
wolfSSL 4:1b0d80432c79 1205
wolfSSL 4:1b0d80432c79 1206 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 1207 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 1208
wolfSSL 4:1b0d80432c79 1209 carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
wolfSSL 4:1b0d80432c79 1210 carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
wolfSSL 4:1b0d80432c79 1211
wolfSSL 4:1b0d80432c79 1212 carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
wolfSSL 4:1b0d80432c79 1213 carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
wolfSSL 4:1b0d80432c79 1214
wolfSSL 4:1b0d80432c79 1215 carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
wolfSSL 4:1b0d80432c79 1216 carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
wolfSSL 4:1b0d80432c79 1217
wolfSSL 4:1b0d80432c79 1218 carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
wolfSSL 4:1b0d80432c79 1219 carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
wolfSSL 4:1b0d80432c79 1220
wolfSSL 4:1b0d80432c79 1221 carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
wolfSSL 4:1b0d80432c79 1222
wolfSSL 4:1b0d80432c79 1223 carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
wolfSSL 4:1b0d80432c79 1224
wolfSSL 4:1b0d80432c79 1225 h[0] = (int32_t)h0;
wolfSSL 4:1b0d80432c79 1226 h[1] = (int32_t)h1;
wolfSSL 4:1b0d80432c79 1227 h[2] = (int32_t)h2;
wolfSSL 4:1b0d80432c79 1228 h[3] = (int32_t)h3;
wolfSSL 4:1b0d80432c79 1229 h[4] = (int32_t)h4;
wolfSSL 4:1b0d80432c79 1230 h[5] = (int32_t)h5;
wolfSSL 4:1b0d80432c79 1231 h[6] = (int32_t)h6;
wolfSSL 4:1b0d80432c79 1232 h[7] = (int32_t)h7;
wolfSSL 4:1b0d80432c79 1233 h[8] = (int32_t)h8;
wolfSSL 4:1b0d80432c79 1234 h[9] = (int32_t)h9;
wolfSSL 4:1b0d80432c79 1235 }
wolfSSL 4:1b0d80432c79 1236
wolfSSL 4:1b0d80432c79 1237
wolfSSL 4:1b0d80432c79 1238 void fe_pow22523(fe out,const fe z)
wolfSSL 4:1b0d80432c79 1239 {
wolfSSL 4:1b0d80432c79 1240 fe t0;
wolfSSL 4:1b0d80432c79 1241 fe t1;
wolfSSL 4:1b0d80432c79 1242 fe t2;
wolfSSL 4:1b0d80432c79 1243 int i;
wolfSSL 4:1b0d80432c79 1244
wolfSSL 4:1b0d80432c79 1245 fe_sq(t0,z); for (i = 1;i < 1;++i) fe_sq(t0,t0);
wolfSSL 4:1b0d80432c79 1246 fe_sq(t1,t0); for (i = 1;i < 2;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 1247 fe_mul(t1,z,t1);
wolfSSL 4:1b0d80432c79 1248 fe_mul(t0,t0,t1);
wolfSSL 4:1b0d80432c79 1249 fe_sq(t0,t0); for (i = 1;i < 1;++i) fe_sq(t0,t0);
wolfSSL 4:1b0d80432c79 1250 fe_mul(t0,t1,t0);
wolfSSL 4:1b0d80432c79 1251 fe_sq(t1,t0); for (i = 1;i < 5;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 1252 fe_mul(t0,t1,t0);
wolfSSL 4:1b0d80432c79 1253 fe_sq(t1,t0); for (i = 1;i < 10;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 1254 fe_mul(t1,t1,t0);
wolfSSL 4:1b0d80432c79 1255 fe_sq(t2,t1); for (i = 1;i < 20;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 1256 fe_mul(t1,t2,t1);
wolfSSL 4:1b0d80432c79 1257 fe_sq(t1,t1); for (i = 1;i < 10;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 1258 fe_mul(t0,t1,t0);
wolfSSL 4:1b0d80432c79 1259 fe_sq(t1,t0); for (i = 1;i < 50;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 1260 fe_mul(t1,t1,t0);
wolfSSL 4:1b0d80432c79 1261 fe_sq(t2,t1); for (i = 1;i < 100;++i) fe_sq(t2,t2);
wolfSSL 4:1b0d80432c79 1262 fe_mul(t1,t2,t1);
wolfSSL 4:1b0d80432c79 1263 fe_sq(t1,t1); for (i = 1;i < 50;++i) fe_sq(t1,t1);
wolfSSL 4:1b0d80432c79 1264 fe_mul(t0,t1,t0);
wolfSSL 4:1b0d80432c79 1265 fe_sq(t0,t0); for (i = 1;i < 2;++i) fe_sq(t0,t0);
wolfSSL 4:1b0d80432c79 1266 fe_mul(out,t0,z);
wolfSSL 4:1b0d80432c79 1267
wolfSSL 4:1b0d80432c79 1268 return;
wolfSSL 4:1b0d80432c79 1269 }
wolfSSL 4:1b0d80432c79 1270
wolfSSL 4:1b0d80432c79 1271
wolfSSL 4:1b0d80432c79 1272 /*
wolfSSL 4:1b0d80432c79 1273 h = -f
wolfSSL 4:1b0d80432c79 1274
wolfSSL 4:1b0d80432c79 1275 Preconditions:
wolfSSL 4:1b0d80432c79 1276 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 1277
wolfSSL 4:1b0d80432c79 1278 Postconditions:
wolfSSL 4:1b0d80432c79 1279 |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
wolfSSL 4:1b0d80432c79 1280 */
wolfSSL 4:1b0d80432c79 1281
wolfSSL 4:1b0d80432c79 1282 void fe_neg(fe h,const fe f)
wolfSSL 4:1b0d80432c79 1283 {
wolfSSL 4:1b0d80432c79 1284 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 1285 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 1286 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 1287 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 1288 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 1289 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 1290 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 1291 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 1292 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 1293 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 1294 int32_t h0 = -f0;
wolfSSL 4:1b0d80432c79 1295 int32_t h1 = -f1;
wolfSSL 4:1b0d80432c79 1296 int32_t h2 = -f2;
wolfSSL 4:1b0d80432c79 1297 int32_t h3 = -f3;
wolfSSL 4:1b0d80432c79 1298 int32_t h4 = -f4;
wolfSSL 4:1b0d80432c79 1299 int32_t h5 = -f5;
wolfSSL 4:1b0d80432c79 1300 int32_t h6 = -f6;
wolfSSL 4:1b0d80432c79 1301 int32_t h7 = -f7;
wolfSSL 4:1b0d80432c79 1302 int32_t h8 = -f8;
wolfSSL 4:1b0d80432c79 1303 int32_t h9 = -f9;
wolfSSL 4:1b0d80432c79 1304 h[0] = h0;
wolfSSL 4:1b0d80432c79 1305 h[1] = h1;
wolfSSL 4:1b0d80432c79 1306 h[2] = h2;
wolfSSL 4:1b0d80432c79 1307 h[3] = h3;
wolfSSL 4:1b0d80432c79 1308 h[4] = h4;
wolfSSL 4:1b0d80432c79 1309 h[5] = h5;
wolfSSL 4:1b0d80432c79 1310 h[6] = h6;
wolfSSL 4:1b0d80432c79 1311 h[7] = h7;
wolfSSL 4:1b0d80432c79 1312 h[8] = h8;
wolfSSL 4:1b0d80432c79 1313 h[9] = h9;
wolfSSL 4:1b0d80432c79 1314 }
wolfSSL 4:1b0d80432c79 1315
wolfSSL 4:1b0d80432c79 1316
wolfSSL 4:1b0d80432c79 1317 /*
wolfSSL 4:1b0d80432c79 1318 Preconditions:
wolfSSL 4:1b0d80432c79 1319 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
wolfSSL 4:1b0d80432c79 1320 */
wolfSSL 4:1b0d80432c79 1321
wolfSSL 4:1b0d80432c79 1322 static const unsigned char zero[32] = {0};
wolfSSL 4:1b0d80432c79 1323
wolfSSL 4:1b0d80432c79 1324 int fe_isnonzero(const fe f)
wolfSSL 4:1b0d80432c79 1325 {
wolfSSL 4:1b0d80432c79 1326 unsigned char s[32];
wolfSSL 4:1b0d80432c79 1327 fe_tobytes(s,f);
wolfSSL 4:1b0d80432c79 1328 return ConstantCompare(s,zero,32);
wolfSSL 4:1b0d80432c79 1329 }
wolfSSL 4:1b0d80432c79 1330
wolfSSL 4:1b0d80432c79 1331
wolfSSL 4:1b0d80432c79 1332 /*
wolfSSL 4:1b0d80432c79 1333 return 1 if f is in {1,3,5,...,q-2}
wolfSSL 4:1b0d80432c79 1334 return 0 if f is in {0,2,4,...,q-1}
wolfSSL 4:1b0d80432c79 1335
wolfSSL 4:1b0d80432c79 1336 Preconditions:
wolfSSL 4:1b0d80432c79 1337 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
wolfSSL 4:1b0d80432c79 1338 */
wolfSSL 4:1b0d80432c79 1339
wolfSSL 4:1b0d80432c79 1340 int fe_isnegative(const fe f)
wolfSSL 4:1b0d80432c79 1341 {
wolfSSL 4:1b0d80432c79 1342 unsigned char s[32];
wolfSSL 4:1b0d80432c79 1343 fe_tobytes(s,f);
wolfSSL 4:1b0d80432c79 1344 return s[0] & 1;
wolfSSL 4:1b0d80432c79 1345 }
wolfSSL 4:1b0d80432c79 1346
wolfSSL 4:1b0d80432c79 1347
wolfSSL 4:1b0d80432c79 1348 /*
wolfSSL 4:1b0d80432c79 1349 Replace (f,g) with (g,g) if b == 1;
wolfSSL 4:1b0d80432c79 1350 replace (f,g) with (f,g) if b == 0.
wolfSSL 4:1b0d80432c79 1351
wolfSSL 4:1b0d80432c79 1352 Preconditions: b in {0,1}.
wolfSSL 4:1b0d80432c79 1353 */
wolfSSL 4:1b0d80432c79 1354
wolfSSL 4:1b0d80432c79 1355 void fe_cmov(fe f,const fe g,unsigned int b)
wolfSSL 4:1b0d80432c79 1356 {
wolfSSL 4:1b0d80432c79 1357 int32_t f0 = f[0];
wolfSSL 4:1b0d80432c79 1358 int32_t f1 = f[1];
wolfSSL 4:1b0d80432c79 1359 int32_t f2 = f[2];
wolfSSL 4:1b0d80432c79 1360 int32_t f3 = f[3];
wolfSSL 4:1b0d80432c79 1361 int32_t f4 = f[4];
wolfSSL 4:1b0d80432c79 1362 int32_t f5 = f[5];
wolfSSL 4:1b0d80432c79 1363 int32_t f6 = f[6];
wolfSSL 4:1b0d80432c79 1364 int32_t f7 = f[7];
wolfSSL 4:1b0d80432c79 1365 int32_t f8 = f[8];
wolfSSL 4:1b0d80432c79 1366 int32_t f9 = f[9];
wolfSSL 4:1b0d80432c79 1367 int32_t g0 = g[0];
wolfSSL 4:1b0d80432c79 1368 int32_t g1 = g[1];
wolfSSL 4:1b0d80432c79 1369 int32_t g2 = g[2];
wolfSSL 4:1b0d80432c79 1370 int32_t g3 = g[3];
wolfSSL 4:1b0d80432c79 1371 int32_t g4 = g[4];
wolfSSL 4:1b0d80432c79 1372 int32_t g5 = g[5];
wolfSSL 4:1b0d80432c79 1373 int32_t g6 = g[6];
wolfSSL 4:1b0d80432c79 1374 int32_t g7 = g[7];
wolfSSL 4:1b0d80432c79 1375 int32_t g8 = g[8];
wolfSSL 4:1b0d80432c79 1376 int32_t g9 = g[9];
wolfSSL 4:1b0d80432c79 1377 int32_t x0 = f0 ^ g0;
wolfSSL 4:1b0d80432c79 1378 int32_t x1 = f1 ^ g1;
wolfSSL 4:1b0d80432c79 1379 int32_t x2 = f2 ^ g2;
wolfSSL 4:1b0d80432c79 1380 int32_t x3 = f3 ^ g3;
wolfSSL 4:1b0d80432c79 1381 int32_t x4 = f4 ^ g4;
wolfSSL 4:1b0d80432c79 1382 int32_t x5 = f5 ^ g5;
wolfSSL 4:1b0d80432c79 1383 int32_t x6 = f6 ^ g6;
wolfSSL 4:1b0d80432c79 1384 int32_t x7 = f7 ^ g7;
wolfSSL 4:1b0d80432c79 1385 int32_t x8 = f8 ^ g8;
wolfSSL 4:1b0d80432c79 1386 int32_t x9 = f9 ^ g9;
wolfSSL 4:1b0d80432c79 1387 b = -b;
wolfSSL 4:1b0d80432c79 1388 x0 &= b;
wolfSSL 4:1b0d80432c79 1389 x1 &= b;
wolfSSL 4:1b0d80432c79 1390 x2 &= b;
wolfSSL 4:1b0d80432c79 1391 x3 &= b;
wolfSSL 4:1b0d80432c79 1392 x4 &= b;
wolfSSL 4:1b0d80432c79 1393 x5 &= b;
wolfSSL 4:1b0d80432c79 1394 x6 &= b;
wolfSSL 4:1b0d80432c79 1395 x7 &= b;
wolfSSL 4:1b0d80432c79 1396 x8 &= b;
wolfSSL 4:1b0d80432c79 1397 x9 &= b;
wolfSSL 4:1b0d80432c79 1398 f[0] = f0 ^ x0;
wolfSSL 4:1b0d80432c79 1399 f[1] = f1 ^ x1;
wolfSSL 4:1b0d80432c79 1400 f[2] = f2 ^ x2;
wolfSSL 4:1b0d80432c79 1401 f[3] = f3 ^ x3;
wolfSSL 4:1b0d80432c79 1402 f[4] = f4 ^ x4;
wolfSSL 4:1b0d80432c79 1403 f[5] = f5 ^ x5;
wolfSSL 4:1b0d80432c79 1404 f[6] = f6 ^ x6;
wolfSSL 4:1b0d80432c79 1405 f[7] = f7 ^ x7;
wolfSSL 4:1b0d80432c79 1406 f[8] = f8 ^ x8;
wolfSSL 4:1b0d80432c79 1407 f[9] = f9 ^ x9;
wolfSSL 4:1b0d80432c79 1408 }
wolfSSL 4:1b0d80432c79 1409 #endif /* HAVE ED25519 or CURVE25519 */
wolfSSL 4:1b0d80432c79 1410 #endif /* not defined CURVED25519_SMALL */
wolfSSL 4:1b0d80432c79 1411
wolfSSL 4:1b0d80432c79 1412