Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2021 Denys Vlasenko |
| 3 | * |
| 4 | * Licensed under GPLv2, see file LICENSE in this source tree. |
| 5 | */ |
| 6 | #include "tls.h" |
| 7 | |
| 8 | #define SP_DEBUG 0 |
| 9 | #define FIXED_SECRET 0 |
| 10 | #define FIXED_PEER_PUBKEY 0 |
| 11 | |
| 12 | #if SP_DEBUG |
| 13 | # define dbg(...) fprintf(stderr, __VA_ARGS__) |
| 14 | static void dump_hex(const char *fmt, const void *vp, int len) |
| 15 | { |
| 16 | char hexbuf[32 * 1024 + 4]; |
| 17 | const uint8_t *p = vp; |
| 18 | |
| 19 | bin2hex(hexbuf, (void*)p, len)[0] = '\0'; |
| 20 | dbg(fmt, hexbuf); |
| 21 | } |
| 22 | #else |
| 23 | # define dbg(...) ((void)0) |
| 24 | # define dump_hex(...) ((void)0) |
| 25 | #endif |
| 26 | |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 27 | typedef int32_t sp_digit; |
| 28 | |
| 29 | /* The code below is taken from parts of |
| 30 | * wolfssl-3.15.3/wolfcrypt/src/sp_c32.c |
| 31 | * and heavily modified. |
| 32 | * Header comment is kept intact: |
| 33 | */ |
| 34 | |
| 35 | /* sp.c |
| 36 | * |
| 37 | * Copyright (C) 2006-2018 wolfSSL Inc. |
| 38 | * |
| 39 | * This file is part of wolfSSL. |
| 40 | * |
| 41 | * wolfSSL is free software; you can redistribute it and/or modify |
| 42 | * it under the terms of the GNU General Public License as published by |
| 43 | * the Free Software Foundation; either version 2 of the License, or |
| 44 | * (at your option) any later version. |
| 45 | * |
| 46 | * wolfSSL is distributed in the hope that it will be useful, |
| 47 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 48 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 49 | * GNU General Public License for more details. |
| 50 | * |
| 51 | * You should have received a copy of the GNU General Public License |
| 52 | * along with this program; if not, write to the Free Software |
| 53 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA |
| 54 | */ |
| 55 | |
| 56 | /* Implementation by Sean Parkinson. */ |
| 57 | |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 58 | typedef struct sp_point { |
| 59 | sp_digit x[2 * 10]; |
| 60 | sp_digit y[2 * 10]; |
| 61 | sp_digit z[2 * 10]; |
| 62 | int infinity; |
| 63 | } sp_point; |
| 64 | |
| 65 | /* The modulus (prime) of the curve P256. */ |
| 66 | static const sp_digit p256_mod[10] = { |
| 67 | 0x3ffffff,0x3ffffff,0x3ffffff,0x003ffff,0x0000000, |
| 68 | 0x0000000,0x0000000,0x0000400,0x3ff0000,0x03fffff, |
| 69 | }; |
| 70 | |
| 71 | #define p256_mp_mod ((sp_digit)0x000001) |
| 72 | |
Denys Vlasenko | 7714518 | 2021-10-01 13:51:39 +0200 | [diff] [blame^] | 73 | /* Normalize the values in each word to 26 bits. */ |
| 74 | static void sp_256_norm_10(sp_digit* a) |
| 75 | { |
| 76 | int i; |
| 77 | for (i = 0; i < 9; i++) { |
| 78 | a[i+1] += a[i] >> 26; |
| 79 | a[i] &= 0x3ffffff; |
| 80 | } |
| 81 | } |
| 82 | |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 83 | /* Write r as big endian to byte aray. |
| 84 | * Fixed length number of bytes written: 32 |
| 85 | * |
| 86 | * r A single precision integer. |
| 87 | * a Byte array. |
| 88 | */ |
| 89 | static void sp_256_to_bin(sp_digit* r, uint8_t* a) |
| 90 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 91 | int i, j, s = 0, b; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 92 | |
Denys Vlasenko | 7714518 | 2021-10-01 13:51:39 +0200 | [diff] [blame^] | 93 | sp_256_norm_10(r); |
| 94 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 95 | j = 256 / 8 - 1; |
| 96 | a[j] = 0; |
| 97 | for (i = 0; i < 10 && j >= 0; i++) { |
| 98 | b = 0; |
| 99 | a[j--] |= r[i] << s; b += 8 - s; |
| 100 | if (j < 0) |
| 101 | break; |
| 102 | while (b < 26) { |
| 103 | a[j--] = r[i] >> b; b += 8; |
| 104 | if (j < 0) |
| 105 | break; |
| 106 | } |
| 107 | s = 8 - (b - 26); |
| 108 | if (j >= 0) |
| 109 | a[j] = 0; |
| 110 | if (s != 0) |
| 111 | j++; |
| 112 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 113 | } |
| 114 | |
| 115 | /* Read big endian unsigned byte aray into r. |
| 116 | * |
| 117 | * r A single precision integer. |
| 118 | * a Byte array. |
| 119 | * n Number of bytes in array to read. |
| 120 | */ |
| 121 | static void sp_256_from_bin(sp_digit* r, int max, const uint8_t* a, int n) |
| 122 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 123 | int i, j = 0, s = 0; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 124 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 125 | r[0] = 0; |
| 126 | for (i = n-1; i >= 0; i--) { |
| 127 | r[j] |= ((sp_digit)a[i]) << s; |
| 128 | if (s >= 18) { |
| 129 | r[j] &= 0x3ffffff; |
| 130 | s = 26 - s; |
| 131 | if (j + 1 >= max) |
| 132 | break; |
| 133 | r[++j] = a[i] >> s; |
| 134 | s = 8 - s; |
| 135 | } |
| 136 | else |
| 137 | s += 8; |
| 138 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 139 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 140 | for (j++; j < max; j++) |
| 141 | r[j] = 0; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 142 | } |
| 143 | |
| 144 | /* Convert a point of big-endian 32-byte x,y pair to type sp_point. */ |
| 145 | static void sp_256_point_from_bin2x32(sp_point* p, const uint8_t *bin2x32) |
| 146 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 147 | memset(p, 0, sizeof(*p)); |
| 148 | /*p->infinity = 0;*/ |
| 149 | sp_256_from_bin(p->x, 2 * 10, bin2x32, 32); |
| 150 | sp_256_from_bin(p->y, 2 * 10, bin2x32 + 32, 32); |
| 151 | //static const uint8_t one[1] = { 1 }; |
| 152 | //sp_256_from_bin(p->z, 2 * 10, one, 1); |
| 153 | p->z[0] = 1; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 154 | } |
| 155 | |
Denys Vlasenko | b3b1713 | 2021-04-26 16:53:53 +0200 | [diff] [blame] | 156 | /* Compare a with b. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 157 | * |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 158 | * return -ve, 0 or +ve if a is less than, equal to or greater than b |
| 159 | * respectively. |
| 160 | */ |
| 161 | static sp_digit sp_256_cmp_10(const sp_digit* a, const sp_digit* b) |
| 162 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 163 | sp_digit r; |
| 164 | int i; |
| 165 | for (i = 9; i >= 0; i--) { |
| 166 | r = a[i] - b[i]; |
| 167 | if (r != 0) |
| 168 | break; |
| 169 | } |
| 170 | return r; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 171 | } |
| 172 | |
| 173 | /* Compare two numbers to determine if they are equal. |
| 174 | * |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 175 | * return 1 when equal and 0 otherwise. |
| 176 | */ |
| 177 | static int sp_256_cmp_equal_10(const sp_digit* a, const sp_digit* b) |
| 178 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 179 | return sp_256_cmp_10(a, b) == 0; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 180 | } |
| 181 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 182 | /* Add b to a into r. (r = a + b) */ |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 183 | static void sp_256_add_10(sp_digit* r, const sp_digit* a, const sp_digit* b) |
| 184 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 185 | int i; |
| 186 | for (i = 0; i < 10; i++) |
| 187 | r[i] = a[i] + b[i]; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 188 | } |
| 189 | |
Denys Vlasenko | 9a40be4 | 2021-04-26 21:58:04 +0200 | [diff] [blame] | 190 | /* Sub b from a into r. (r = a - b) */ |
| 191 | static void sp_256_sub_10(sp_digit* r, const sp_digit* a, const sp_digit* b) |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 192 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 193 | int i; |
| 194 | for (i = 0; i < 10; i++) |
Denys Vlasenko | 9a40be4 | 2021-04-26 21:58:04 +0200 | [diff] [blame] | 195 | r[i] = a[i] - b[i]; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 196 | } |
| 197 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 198 | /* Shift number left one bit. Bottom bit is lost. */ |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 199 | static void sp_256_rshift1_10(sp_digit* r, sp_digit* a) |
| 200 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 201 | int i; |
| 202 | for (i = 0; i < 9; i++) |
| 203 | r[i] = ((a[i] >> 1) | (a[i + 1] << 25)) & 0x3ffffff; |
| 204 | r[9] = a[9] >> 1; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 205 | } |
| 206 | |
Denys Vlasenko | a2bc52d | 2021-04-27 01:21:26 +0200 | [diff] [blame] | 207 | /* Mul a by scalar b and add into r. (r += a * b) */ |
| 208 | static void sp_256_mul_add_10(sp_digit* r, const sp_digit* a, sp_digit b) |
| 209 | { |
| 210 | int64_t tb = b; |
| 211 | int64_t t = 0; |
| 212 | int i; |
| 213 | |
| 214 | for (i = 0; i < 10; i++) { |
| 215 | t += (tb * a[i]) + r[i]; |
| 216 | r[i] = t & 0x3ffffff; |
| 217 | t >>= 26; |
| 218 | } |
| 219 | r[10] += t; |
| 220 | } |
| 221 | |
| 222 | /* Multiply a and b into r. (r = a * b) */ |
| 223 | static void sp_256_mul_10(sp_digit* r, const sp_digit* a, const sp_digit* b) |
| 224 | { |
| 225 | int i, j, k; |
| 226 | int64_t c; |
| 227 | |
| 228 | c = ((int64_t)a[9]) * b[9]; |
| 229 | r[19] = (sp_digit)(c >> 26); |
| 230 | c = (c & 0x3ffffff) << 26; |
| 231 | for (k = 17; k >= 0; k--) { |
| 232 | for (i = 9; i >= 0; i--) { |
| 233 | j = k - i; |
| 234 | if (j >= 10) |
| 235 | break; |
| 236 | if (j < 0) |
| 237 | continue; |
| 238 | c += ((int64_t)a[i]) * b[j]; |
| 239 | } |
| 240 | r[k + 2] += c >> 52; |
| 241 | r[k + 1] = (c >> 26) & 0x3ffffff; |
| 242 | c = (c & 0x3ffffff) << 26; |
| 243 | } |
| 244 | r[0] = (sp_digit)(c >> 26); |
| 245 | } |
| 246 | |
| 247 | /* Square a and put result in r. (r = a * a) */ |
| 248 | static void sp_256_sqr_10(sp_digit* r, const sp_digit* a) |
| 249 | { |
| 250 | int i, j, k; |
| 251 | int64_t c; |
| 252 | |
| 253 | c = ((int64_t)a[9]) * a[9]; |
| 254 | r[19] = (sp_digit)(c >> 26); |
| 255 | c = (c & 0x3ffffff) << 26; |
| 256 | for (k = 17; k >= 0; k--) { |
| 257 | for (i = 9; i >= 0; i--) { |
| 258 | j = k - i; |
| 259 | if (j >= 10 || i <= j) |
| 260 | break; |
| 261 | if (j < 0) |
| 262 | continue; |
| 263 | c += ((int64_t)a[i]) * a[j] * 2; |
| 264 | } |
| 265 | if (i == j) |
| 266 | c += ((int64_t)a[i]) * a[i]; |
| 267 | r[k + 2] += c >> 52; |
| 268 | r[k + 1] = (c >> 26) & 0x3ffffff; |
| 269 | c = (c & 0x3ffffff) << 26; |
| 270 | } |
| 271 | r[0] = (sp_digit)(c >> 26); |
| 272 | } |
| 273 | |
| 274 | /* Divide the number by 2 mod the modulus (prime). (r = a / 2 % m) */ |
| 275 | static void sp_256_div2_10(sp_digit* r, const sp_digit* a, const sp_digit* m) |
| 276 | { |
| 277 | if (a[0] & 1) |
| 278 | sp_256_add_10(r, a, m); |
| 279 | sp_256_norm_10(r); |
| 280 | sp_256_rshift1_10(r, r); |
| 281 | } |
| 282 | |
| 283 | /* Add two Montgomery form numbers (r = a + b % m) */ |
| 284 | static void sp_256_mont_add_10(sp_digit* r, const sp_digit* a, const sp_digit* b, |
| 285 | const sp_digit* m) |
| 286 | { |
| 287 | sp_256_add_10(r, a, b); |
| 288 | sp_256_norm_10(r); |
| 289 | if ((r[9] >> 22) > 0) |
| 290 | sp_256_sub_10(r, r, m); |
| 291 | sp_256_norm_10(r); |
| 292 | } |
| 293 | |
| 294 | /* Subtract two Montgomery form numbers (r = a - b % m) */ |
| 295 | static void sp_256_mont_sub_10(sp_digit* r, const sp_digit* a, const sp_digit* b, |
| 296 | const sp_digit* m) |
| 297 | { |
| 298 | sp_256_sub_10(r, a, b); |
| 299 | if (r[9] >> 22) |
| 300 | sp_256_add_10(r, r, m); |
| 301 | sp_256_norm_10(r); |
| 302 | } |
| 303 | |
| 304 | /* Double a Montgomery form number (r = a + a % m) */ |
| 305 | static void sp_256_mont_dbl_10(sp_digit* r, const sp_digit* a, const sp_digit* m) |
| 306 | { |
| 307 | sp_256_add_10(r, a, a); |
| 308 | sp_256_norm_10(r); |
| 309 | if ((r[9] >> 22) > 0) |
| 310 | sp_256_sub_10(r, r, m); |
| 311 | sp_256_norm_10(r); |
| 312 | } |
| 313 | |
| 314 | /* Triple a Montgomery form number (r = a + a + a % m) */ |
| 315 | static void sp_256_mont_tpl_10(sp_digit* r, const sp_digit* a, const sp_digit* m) |
| 316 | { |
| 317 | sp_256_add_10(r, a, a); |
| 318 | sp_256_norm_10(r); |
| 319 | if ((r[9] >> 22) > 0) |
| 320 | sp_256_sub_10(r, r, m); |
| 321 | sp_256_norm_10(r); |
| 322 | sp_256_add_10(r, r, a); |
| 323 | sp_256_norm_10(r); |
| 324 | if ((r[9] >> 22) > 0) |
| 325 | sp_256_sub_10(r, r, m); |
| 326 | sp_256_norm_10(r); |
| 327 | } |
| 328 | |
| 329 | /* Shift the result in the high 256 bits down to the bottom. */ |
| 330 | static void sp_256_mont_shift_10(sp_digit* r, const sp_digit* a) |
| 331 | { |
| 332 | int i; |
| 333 | sp_digit n, s; |
| 334 | |
| 335 | s = a[10]; |
| 336 | n = a[9] >> 22; |
| 337 | for (i = 0; i < 9; i++) { |
| 338 | n += (s & 0x3ffffff) << 4; |
| 339 | r[i] = n & 0x3ffffff; |
| 340 | n >>= 26; |
| 341 | s = a[11 + i] + (s >> 26); |
| 342 | } |
| 343 | n += s << 4; |
| 344 | r[9] = n; |
| 345 | memset(&r[10], 0, sizeof(*r) * 10); |
| 346 | } |
| 347 | |
| 348 | /* Reduce the number back to 256 bits using Montgomery reduction. |
| 349 | * |
| 350 | * a A single precision number to reduce in place. |
| 351 | * m The single precision number representing the modulus. |
| 352 | * mp The digit representing the negative inverse of m mod 2^n. |
| 353 | */ |
| 354 | static void sp_256_mont_reduce_10(sp_digit* a, const sp_digit* m, sp_digit mp) |
| 355 | { |
| 356 | int i; |
| 357 | sp_digit mu; |
| 358 | |
| 359 | if (mp != 1) { |
| 360 | for (i = 0; i < 9; i++) { |
| 361 | mu = (a[i] * mp) & 0x3ffffff; |
| 362 | sp_256_mul_add_10(a+i, m, mu); |
| 363 | a[i+1] += a[i] >> 26; |
| 364 | } |
| 365 | mu = (a[i] * mp) & 0x3fffffl; |
| 366 | sp_256_mul_add_10(a+i, m, mu); |
| 367 | a[i+1] += a[i] >> 26; |
| 368 | a[i] &= 0x3ffffff; |
| 369 | } |
| 370 | else { |
| 371 | for (i = 0; i < 9; i++) { |
| 372 | mu = a[i] & 0x3ffffff; |
| 373 | sp_256_mul_add_10(a+i, p256_mod, mu); |
| 374 | a[i+1] += a[i] >> 26; |
| 375 | } |
| 376 | mu = a[i] & 0x3fffffl; |
| 377 | sp_256_mul_add_10(a+i, p256_mod, mu); |
| 378 | a[i+1] += a[i] >> 26; |
| 379 | a[i] &= 0x3ffffff; |
| 380 | } |
| 381 | |
| 382 | sp_256_mont_shift_10(a, a); |
| 383 | if ((a[9] >> 22) > 0) |
| 384 | sp_256_sub_10(a, a, m); |
| 385 | sp_256_norm_10(a); |
| 386 | } |
| 387 | |
| 388 | /* Multiply two Montogmery form numbers mod the modulus (prime). |
| 389 | * (r = a * b mod m) |
| 390 | * |
| 391 | * r Result of multiplication. |
| 392 | * a First number to multiply in Montogmery form. |
| 393 | * b Second number to multiply in Montogmery form. |
| 394 | * m Modulus (prime). |
| 395 | * mp Montogmery mulitplier. |
| 396 | */ |
| 397 | static void sp_256_mont_mul_10(sp_digit* r, const sp_digit* a, const sp_digit* b, |
| 398 | const sp_digit* m, sp_digit mp) |
| 399 | { |
| 400 | sp_256_mul_10(r, a, b); |
| 401 | sp_256_mont_reduce_10(r, m, mp); |
| 402 | } |
| 403 | |
| 404 | /* Square the Montgomery form number. (r = a * a mod m) |
| 405 | * |
| 406 | * r Result of squaring. |
| 407 | * a Number to square in Montogmery form. |
| 408 | * m Modulus (prime). |
| 409 | * mp Montogmery mulitplier. |
| 410 | */ |
| 411 | static void sp_256_mont_sqr_10(sp_digit* r, const sp_digit* a, const sp_digit* m, |
| 412 | sp_digit mp) |
| 413 | { |
| 414 | sp_256_sqr_10(r, a); |
| 415 | sp_256_mont_reduce_10(r, m, mp); |
| 416 | } |
| 417 | |
| 418 | /* Invert the number, in Montgomery form, modulo the modulus (prime) of the |
| 419 | * P256 curve. (r = 1 / a mod m) |
| 420 | * |
| 421 | * r Inverse result. |
| 422 | * a Number to invert. |
| 423 | */ |
| 424 | #if 0 |
| 425 | /* Mod-2 for the P256 curve. */ |
| 426 | static const uint32_t p256_mod_2[8] = { |
| 427 | 0xfffffffd,0xffffffff,0xffffffff,0x00000000, |
| 428 | 0x00000000,0x00000000,0x00000001,0xffffffff, |
| 429 | }; |
| 430 | //Bit pattern: |
| 431 | //2 2 2 2 2 2 2 1...1 |
| 432 | //5 5 4 3 2 1 0 9...0 9...1 |
| 433 | //543210987654321098765432109876543210987654321098765432109876543210...09876543210...09876543210 |
| 434 | //111111111111111111111111111111110000000000000000000000000000000100...00000111111...11111111101 |
| 435 | #endif |
| 436 | static void sp_256_mont_inv_10(sp_digit* r, sp_digit* a) |
| 437 | { |
| 438 | sp_digit t[2*10]; //can be just [10]? |
| 439 | int i; |
| 440 | |
| 441 | memcpy(t, a, sizeof(sp_digit) * 10); |
| 442 | for (i = 254; i >= 0; i--) { |
| 443 | sp_256_mont_sqr_10(t, t, p256_mod, p256_mp_mod); |
| 444 | /*if (p256_mod_2[i / 32] & ((sp_digit)1 << (i % 32)))*/ |
| 445 | if (i >= 224 || i == 192 || (i <= 95 && i != 1)) |
| 446 | sp_256_mont_mul_10(t, t, a, p256_mod, p256_mp_mod); |
| 447 | } |
| 448 | memcpy(r, t, sizeof(sp_digit) * 10); |
| 449 | } |
| 450 | |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 451 | /* Multiply a number by Montogmery normalizer mod modulus (prime). |
| 452 | * |
| 453 | * r The resulting Montgomery form number. |
| 454 | * a The number to convert. |
| 455 | */ |
| 456 | static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a) |
| 457 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 458 | int64_t t[8]; |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 459 | int64_t o; |
Denys Vlasenko | 646e856 | 2021-04-27 13:09:44 +0200 | [diff] [blame] | 460 | uint32_t a32; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 461 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 462 | /* 1 1 0 -1 -1 -1 -1 0 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 463 | /* 0 1 1 0 -1 -1 -1 -1 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 464 | /* 0 0 1 1 0 -1 -1 -1 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 465 | /* -1 -1 0 2 2 1 0 -1 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 466 | /* 0 -1 -1 0 2 2 1 0 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 467 | /* 0 0 -1 -1 0 2 2 1 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 468 | /* -1 -1 0 0 0 1 3 2 */ |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 469 | /* 1 0 -1 -1 -1 -1 0 3 */ |
Denys Vlasenko | 646e856 | 2021-04-27 13:09:44 +0200 | [diff] [blame] | 470 | // t[] should be calculated from "a" (converted from 26-bit to 32-bit vector a32[8]) |
| 471 | // according to the above matrix: |
| 472 | //t[0] = 0 + a32[0] + a32[1] - a32[3] - a32[4] - a32[5] - a32[6] ; |
| 473 | //t[1] = 0 + a32[1] + a32[2] - a32[4] - a32[5] - a32[6] - a32[7] ; |
| 474 | //t[2] = 0 + a32[2] + a32[3] - a32[5] - a32[6] - a32[7] ; |
| 475 | //t[3] = 0 - a32[0] - a32[1] + 2*a32[3] + 2*a32[4] + a32[5] - a32[7] ; |
| 476 | //t[4] = 0 - a32[1] - a32[2] + 2*a32[4] + 2*a32[5] + a32[6] ; |
| 477 | //t[5] = 0 - a32[2] - a32[3] + 2*a32[5] + 2*a32[6] + a32[7] ; |
| 478 | //t[6] = 0 - a32[0] - a32[1] + a32[5] + 3*a32[6] + 2*a32[7]; |
| 479 | //t[7] = 0 + a32[0] - a32[2] - a32[3] - a32[4] - a32[5] + 3*a32[7]; |
| 480 | // We can do it "piecemeal" after each a32[i] is known, no need to store entire a32[8] vector: |
| 481 | |
| 482 | #define A32 (int64_t)a32 |
| 483 | a32 = a[0] | (a[1] << 26); |
| 484 | t[0] = 0 + A32; |
| 485 | t[3] = 0 - A32; |
| 486 | t[6] = 0 - A32; |
| 487 | t[7] = 0 + A32; |
| 488 | |
| 489 | a32 = (a[1] >> 6) | (a[2] << 20); |
| 490 | t[0] += A32 ; |
| 491 | t[1] = 0 + A32; |
| 492 | t[3] -= A32 ; |
| 493 | t[4] = 0 - A32; |
| 494 | t[6] -= A32 ; |
| 495 | |
| 496 | a32 = (a[2] >> 12) | (a[3] << 14); |
| 497 | t[1] += A32 ; |
| 498 | t[2] = 0 + A32; |
| 499 | t[4] -= A32 ; |
| 500 | t[5] = 0 - A32; |
| 501 | t[7] -= A32 ; |
| 502 | |
| 503 | a32 = (a[3] >> 18) | (a[4] << 8); |
| 504 | t[0] -= A32 ; |
| 505 | t[2] += A32 ; |
| 506 | t[3] += 2*A32; |
| 507 | t[5] -= A32 ; |
| 508 | t[7] -= A32 ; |
| 509 | |
| 510 | a32 = (a[4] >> 24) | (a[5] << 2) | (a[6] << 28); |
| 511 | t[0] -= A32 ; |
| 512 | t[1] -= A32 ; |
| 513 | t[3] += 2*A32; |
| 514 | t[4] += 2*A32; |
| 515 | t[7] -= A32 ; |
| 516 | |
| 517 | a32 = (a[6] >> 4) | (a[7] << 22); |
| 518 | t[0] -= A32 ; |
| 519 | t[1] -= A32 ; |
| 520 | t[2] -= A32 ; |
| 521 | t[3] += A32 ; |
| 522 | t[4] += 2*A32; |
| 523 | t[5] += 2*A32; |
| 524 | t[6] += A32 ; |
| 525 | t[7] -= A32 ; |
| 526 | |
| 527 | a32 = (a[7] >> 10) | (a[8] << 16); |
| 528 | t[0] -= A32 ; |
| 529 | t[1] -= A32 ; |
| 530 | t[2] -= A32 ; |
| 531 | t[4] += A32 ; |
| 532 | t[5] += 2*A32; |
| 533 | t[6] += 3*A32; |
| 534 | |
| 535 | a32 = (a[8] >> 16) | (a[9] << 10); |
| 536 | t[1] -= A32 ; |
| 537 | t[2] -= A32 ; |
| 538 | t[3] -= A32 ; |
| 539 | t[5] += A32 ; |
| 540 | t[6] += 2*A32; |
| 541 | t[7] += 3*A32; |
| 542 | #undef A32 |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 543 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 544 | t[1] += t[0] >> 32; t[0] &= 0xffffffff; |
| 545 | t[2] += t[1] >> 32; t[1] &= 0xffffffff; |
| 546 | t[3] += t[2] >> 32; t[2] &= 0xffffffff; |
| 547 | t[4] += t[3] >> 32; t[3] &= 0xffffffff; |
| 548 | t[5] += t[4] >> 32; t[4] &= 0xffffffff; |
| 549 | t[6] += t[5] >> 32; t[5] &= 0xffffffff; |
| 550 | t[7] += t[6] >> 32; t[6] &= 0xffffffff; |
| 551 | o = t[7] >> 32; t[7] &= 0xffffffff; |
| 552 | t[0] += o; |
| 553 | t[3] -= o; |
| 554 | t[6] -= o; |
| 555 | t[7] += o; |
Denys Vlasenko | 840ae69 | 2021-04-27 13:31:26 +0200 | [diff] [blame] | 556 | t[1] += t[0] >> 32; //t[0] &= 0xffffffff; |
| 557 | t[2] += t[1] >> 32; //t[1] &= 0xffffffff; |
| 558 | t[3] += t[2] >> 32; //t[2] &= 0xffffffff; |
| 559 | t[4] += t[3] >> 32; //t[3] &= 0xffffffff; |
| 560 | t[5] += t[4] >> 32; //t[4] &= 0xffffffff; |
| 561 | t[6] += t[5] >> 32; //t[5] &= 0xffffffff; |
| 562 | t[7] += t[6] >> 32; //t[6] &= 0xffffffff; - (uint32_t)t[i] casts below accomplish masking |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 563 | |
Denys Vlasenko | 840ae69 | 2021-04-27 13:31:26 +0200 | [diff] [blame] | 564 | r[0] = 0x3ffffff & ((sp_digit)((uint32_t)t[0])); |
| 565 | r[1] = 0x3ffffff & ((sp_digit)((uint32_t)t[0] >> 26) | ((sp_digit)t[1] << 6)); |
| 566 | r[2] = 0x3ffffff & ((sp_digit)((uint32_t)t[1] >> 20) | ((sp_digit)t[2] << 12)); |
| 567 | r[3] = 0x3ffffff & ((sp_digit)((uint32_t)t[2] >> 14) | ((sp_digit)t[3] << 18)); |
| 568 | r[4] = 0x3ffffff & ((sp_digit)((uint32_t)t[3] >> 8) | ((sp_digit)t[4] << 24)); |
| 569 | r[5] = 0x3ffffff & ((sp_digit)((uint32_t)t[4] >> 2)); |
| 570 | r[6] = 0x3ffffff & ((sp_digit)((uint32_t)t[4] >> 28) | ((sp_digit)t[5] << 4)); |
| 571 | r[7] = 0x3ffffff & ((sp_digit)((uint32_t)t[5] >> 22) | ((sp_digit)t[6] << 10)); |
| 572 | r[8] = 0x3ffffff & ((sp_digit)((uint32_t)t[6] >> 16) | ((sp_digit)t[7] << 16)); |
| 573 | r[9] = ((sp_digit)((uint32_t)t[7] >> 10)); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 574 | } |
| 575 | |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 576 | /* Map the Montgomery form projective co-ordinate point to an affine point. |
| 577 | * |
| 578 | * r Resulting affine co-ordinate point. |
| 579 | * p Montgomery form projective co-ordinate point. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 580 | */ |
Denys Vlasenko | 6381f3d | 2021-04-26 17:41:43 +0200 | [diff] [blame] | 581 | static void sp_256_map_10(sp_point* r, sp_point* p) |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 582 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 583 | sp_digit t1[2*10]; |
| 584 | sp_digit t2[2*10]; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 585 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 586 | sp_256_mont_inv_10(t1, p->z); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 587 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 588 | sp_256_mont_sqr_10(t2, t1, p256_mod, p256_mp_mod); |
| 589 | sp_256_mont_mul_10(t1, t2, t1, p256_mod, p256_mp_mod); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 590 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 591 | /* x /= z^2 */ |
| 592 | sp_256_mont_mul_10(r->x, p->x, t2, p256_mod, p256_mp_mod); |
| 593 | memset(r->x + 10, 0, sizeof(r->x) / 2); |
| 594 | sp_256_mont_reduce_10(r->x, p256_mod, p256_mp_mod); |
| 595 | /* Reduce x to less than modulus */ |
Denys Vlasenko | 9a40be4 | 2021-04-26 21:58:04 +0200 | [diff] [blame] | 596 | if (sp_256_cmp_10(r->x, p256_mod) >= 0) |
| 597 | sp_256_sub_10(r->x, r->x, p256_mod); |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 598 | sp_256_norm_10(r->x); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 599 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 600 | /* y /= z^3 */ |
| 601 | sp_256_mont_mul_10(r->y, p->y, t1, p256_mod, p256_mp_mod); |
| 602 | memset(r->y + 10, 0, sizeof(r->y) / 2); |
| 603 | sp_256_mont_reduce_10(r->y, p256_mod, p256_mp_mod); |
| 604 | /* Reduce y to less than modulus */ |
Denys Vlasenko | 9a40be4 | 2021-04-26 21:58:04 +0200 | [diff] [blame] | 605 | if (sp_256_cmp_10(r->y, p256_mod) >= 0) |
| 606 | sp_256_sub_10(r->y, r->y, p256_mod); |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 607 | sp_256_norm_10(r->y); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 608 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 609 | memset(r->z, 0, sizeof(r->z)); |
| 610 | r->z[0] = 1; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 611 | } |
| 612 | |
| 613 | /* Double the Montgomery form projective point p. |
| 614 | * |
| 615 | * r Result of doubling point. |
| 616 | * p Point to double. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 617 | */ |
Denys Vlasenko | 6381f3d | 2021-04-26 17:41:43 +0200 | [diff] [blame] | 618 | static void sp_256_proj_point_dbl_10(sp_point* r, sp_point* p) |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 619 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 620 | sp_point tp; |
| 621 | sp_digit t1[2*10]; |
| 622 | sp_digit t2[2*10]; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 623 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 624 | /* Put point to double into result */ |
| 625 | if (r != p) |
| 626 | *r = *p; /* struct copy */ |
Denys Vlasenko | 4d3a5c1 | 2021-04-26 15:21:38 +0200 | [diff] [blame] | 627 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 628 | if (r->infinity) { |
| 629 | /* If infinity, don't double (work on dummy value) */ |
| 630 | r = &tp; |
| 631 | } |
| 632 | /* T1 = Z * Z */ |
| 633 | sp_256_mont_sqr_10(t1, r->z, p256_mod, p256_mp_mod); |
| 634 | /* Z = Y * Z */ |
| 635 | sp_256_mont_mul_10(r->z, r->y, r->z, p256_mod, p256_mp_mod); |
| 636 | /* Z = 2Z */ |
| 637 | sp_256_mont_dbl_10(r->z, r->z, p256_mod); |
| 638 | /* T2 = X - T1 */ |
| 639 | sp_256_mont_sub_10(t2, r->x, t1, p256_mod); |
| 640 | /* T1 = X + T1 */ |
| 641 | sp_256_mont_add_10(t1, r->x, t1, p256_mod); |
| 642 | /* T2 = T1 * T2 */ |
| 643 | sp_256_mont_mul_10(t2, t1, t2, p256_mod, p256_mp_mod); |
| 644 | /* T1 = 3T2 */ |
| 645 | sp_256_mont_tpl_10(t1, t2, p256_mod); |
| 646 | /* Y = 2Y */ |
| 647 | sp_256_mont_dbl_10(r->y, r->y, p256_mod); |
| 648 | /* Y = Y * Y */ |
| 649 | sp_256_mont_sqr_10(r->y, r->y, p256_mod, p256_mp_mod); |
| 650 | /* T2 = Y * Y */ |
| 651 | sp_256_mont_sqr_10(t2, r->y, p256_mod, p256_mp_mod); |
| 652 | /* T2 = T2/2 */ |
| 653 | sp_256_div2_10(t2, t2, p256_mod); |
| 654 | /* Y = Y * X */ |
| 655 | sp_256_mont_mul_10(r->y, r->y, r->x, p256_mod, p256_mp_mod); |
| 656 | /* X = T1 * T1 */ |
| 657 | sp_256_mont_mul_10(r->x, t1, t1, p256_mod, p256_mp_mod); |
| 658 | /* X = X - Y */ |
| 659 | sp_256_mont_sub_10(r->x, r->x, r->y, p256_mod); |
| 660 | /* X = X - Y */ |
| 661 | sp_256_mont_sub_10(r->x, r->x, r->y, p256_mod); |
| 662 | /* Y = Y - X */ |
| 663 | sp_256_mont_sub_10(r->y, r->y, r->x, p256_mod); |
| 664 | /* Y = Y * T1 */ |
| 665 | sp_256_mont_mul_10(r->y, r->y, t1, p256_mod, p256_mp_mod); |
| 666 | /* Y = Y - T2 */ |
| 667 | sp_256_mont_sub_10(r->y, r->y, t2, p256_mod); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 668 | } |
| 669 | |
| 670 | /* Add two Montgomery form projective points. |
| 671 | * |
| 672 | * r Result of addition. |
| 673 | * p Frist point to add. |
| 674 | * q Second point to add. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 675 | */ |
Denys Vlasenko | 6381f3d | 2021-04-26 17:41:43 +0200 | [diff] [blame] | 676 | static void sp_256_proj_point_add_10(sp_point* r, sp_point* p, sp_point* q) |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 677 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 678 | sp_digit t1[2*10]; |
| 679 | sp_digit t2[2*10]; |
| 680 | sp_digit t3[2*10]; |
| 681 | sp_digit t4[2*10]; |
| 682 | sp_digit t5[2*10]; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 683 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 684 | /* Ensure only the first point is the same as the result. */ |
| 685 | if (q == r) { |
| 686 | sp_point* a = p; |
| 687 | p = q; |
| 688 | q = a; |
| 689 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 690 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 691 | /* Check double */ |
| 692 | sp_256_sub_10(t1, p256_mod, q->y); |
| 693 | sp_256_norm_10(t1); |
| 694 | if (sp_256_cmp_equal_10(p->x, q->x) |
| 695 | && sp_256_cmp_equal_10(p->z, q->z) |
| 696 | && (sp_256_cmp_equal_10(p->y, q->y) || sp_256_cmp_equal_10(p->y, t1)) |
| 697 | ) { |
| 698 | sp_256_proj_point_dbl_10(r, p); |
| 699 | } |
| 700 | else { |
| 701 | sp_point tp; |
| 702 | sp_point *v; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 703 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 704 | v = r; |
| 705 | if (p->infinity | q->infinity) { |
| 706 | memset(&tp, 0, sizeof(tp)); |
| 707 | v = &tp; |
| 708 | } |
Denys Vlasenko | 772e187 | 2021-04-26 17:25:27 +0200 | [diff] [blame] | 709 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 710 | *r = p->infinity ? *q : *p; /* struct copy */ |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 711 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 712 | /* U1 = X1*Z2^2 */ |
| 713 | sp_256_mont_sqr_10(t1, q->z, p256_mod, p256_mp_mod); |
| 714 | sp_256_mont_mul_10(t3, t1, q->z, p256_mod, p256_mp_mod); |
| 715 | sp_256_mont_mul_10(t1, t1, v->x, p256_mod, p256_mp_mod); |
| 716 | /* U2 = X2*Z1^2 */ |
| 717 | sp_256_mont_sqr_10(t2, v->z, p256_mod, p256_mp_mod); |
| 718 | sp_256_mont_mul_10(t4, t2, v->z, p256_mod, p256_mp_mod); |
| 719 | sp_256_mont_mul_10(t2, t2, q->x, p256_mod, p256_mp_mod); |
| 720 | /* S1 = Y1*Z2^3 */ |
| 721 | sp_256_mont_mul_10(t3, t3, v->y, p256_mod, p256_mp_mod); |
| 722 | /* S2 = Y2*Z1^3 */ |
| 723 | sp_256_mont_mul_10(t4, t4, q->y, p256_mod, p256_mp_mod); |
| 724 | /* H = U2 - U1 */ |
| 725 | sp_256_mont_sub_10(t2, t2, t1, p256_mod); |
| 726 | /* R = S2 - S1 */ |
| 727 | sp_256_mont_sub_10(t4, t4, t3, p256_mod); |
| 728 | /* Z3 = H*Z1*Z2 */ |
| 729 | sp_256_mont_mul_10(v->z, v->z, q->z, p256_mod, p256_mp_mod); |
| 730 | sp_256_mont_mul_10(v->z, v->z, t2, p256_mod, p256_mp_mod); |
| 731 | /* X3 = R^2 - H^3 - 2*U1*H^2 */ |
| 732 | sp_256_mont_sqr_10(v->x, t4, p256_mod, p256_mp_mod); |
| 733 | sp_256_mont_sqr_10(t5, t2, p256_mod, p256_mp_mod); |
| 734 | sp_256_mont_mul_10(v->y, t1, t5, p256_mod, p256_mp_mod); |
| 735 | sp_256_mont_mul_10(t5, t5, t2, p256_mod, p256_mp_mod); |
| 736 | sp_256_mont_sub_10(v->x, v->x, t5, p256_mod); |
| 737 | sp_256_mont_dbl_10(t1, v->y, p256_mod); |
| 738 | sp_256_mont_sub_10(v->x, v->x, t1, p256_mod); |
| 739 | /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */ |
| 740 | sp_256_mont_sub_10(v->y, v->y, v->x, p256_mod); |
| 741 | sp_256_mont_mul_10(v->y, v->y, t4, p256_mod, p256_mp_mod); |
| 742 | sp_256_mont_mul_10(t5, t5, t3, p256_mod, p256_mp_mod); |
| 743 | sp_256_mont_sub_10(v->y, v->y, t5, p256_mod); |
| 744 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 745 | } |
| 746 | |
| 747 | /* Multiply the point by the scalar and return the result. |
| 748 | * If map is true then convert result to affine co-ordinates. |
| 749 | * |
| 750 | * r Resulting point. |
| 751 | * g Point to multiply. |
| 752 | * k Scalar to multiply by. |
Denys Vlasenko | 03ab2a9 | 2021-04-26 14:55:46 +0200 | [diff] [blame] | 753 | * map Indicates whether to convert result to affine. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 754 | */ |
| 755 | static void sp_256_ecc_mulmod_10(sp_point* r, const sp_point* g, const sp_digit* k /*, int map*/) |
| 756 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 757 | enum { map = 1 }; /* we always convert result to affine coordinates */ |
| 758 | sp_point t[3]; |
| 759 | sp_digit n; |
| 760 | int i; |
| 761 | int c, y; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 762 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 763 | memset(t, 0, sizeof(t)); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 764 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 765 | /* t[0] = {0, 0, 1} * norm */ |
| 766 | t[0].infinity = 1; |
| 767 | /* t[1] = {g->x, g->y, g->z} * norm */ |
| 768 | sp_256_mod_mul_norm_10(t[1].x, g->x); |
| 769 | sp_256_mod_mul_norm_10(t[1].y, g->y); |
| 770 | sp_256_mod_mul_norm_10(t[1].z, g->z); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 771 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 772 | i = 9; |
| 773 | c = 22; |
| 774 | n = k[i--] << (26 - c); |
| 775 | for (; ; c--) { |
| 776 | if (c == 0) { |
| 777 | if (i == -1) |
| 778 | break; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 779 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 780 | n = k[i--]; |
| 781 | c = 26; |
| 782 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 783 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 784 | y = (n >> 25) & 1; |
| 785 | n <<= 1; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 786 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 787 | sp_256_proj_point_add_10(&t[y^1], &t[0], &t[1]); |
| 788 | memcpy(&t[2], &t[y], sizeof(sp_point)); |
| 789 | sp_256_proj_point_dbl_10(&t[2], &t[2]); |
| 790 | memcpy(&t[y], &t[2], sizeof(sp_point)); |
| 791 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 792 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 793 | if (map) |
| 794 | sp_256_map_10(r, &t[0]); |
| 795 | else |
| 796 | memcpy(r, &t[0], sizeof(sp_point)); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 797 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 798 | memset(t, 0, sizeof(t)); //paranoia |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 799 | } |
| 800 | |
| 801 | /* Multiply the base point of P256 by the scalar and return the result. |
| 802 | * If map is true then convert result to affine co-ordinates. |
| 803 | * |
| 804 | * r Resulting point. |
| 805 | * k Scalar to multiply by. |
Denys Vlasenko | 03ab2a9 | 2021-04-26 14:55:46 +0200 | [diff] [blame] | 806 | * map Indicates whether to convert result to affine. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 807 | */ |
| 808 | static void sp_256_ecc_mulmod_base_10(sp_point* r, sp_digit* k /*, int map*/) |
| 809 | { |
Denys Vlasenko | 39a3ef5 | 2021-04-27 01:31:51 +0200 | [diff] [blame] | 810 | /* Since this function is called only once, save space: |
| 811 | * don't have "static const sp_point p256_base = {...}", |
| 812 | * it would have more zeros than data. |
| 813 | */ |
Denys Vlasenko | 48a18d1 | 2021-04-27 12:24:21 +0200 | [diff] [blame] | 814 | static const uint8_t p256_base_bin[] = { |
| 815 | /* x (big-endian) */ |
| 816 | 0x6b,0x17,0xd1,0xf2,0xe1,0x2c,0x42,0x47,0xf8,0xbc,0xe6,0xe5,0x63,0xa4,0x40,0xf2,0x77,0x03,0x7d,0x81,0x2d,0xeb,0x33,0xa0,0xf4,0xa1,0x39,0x45,0xd8,0x98,0xc2,0x96, |
| 817 | /* y */ |
| 818 | 0x4f,0xe3,0x42,0xe2,0xfe,0x1a,0x7f,0x9b,0x8e,0xe7,0xeb,0x4a,0x7c,0x0f,0x9e,0x16,0x2b,0xce,0x33,0x57,0x6b,0x31,0x5e,0xce,0xcb,0xb6,0x40,0x68,0x37,0xbf,0x51,0xf5, |
Denys Vlasenko | 646e856 | 2021-04-27 13:09:44 +0200 | [diff] [blame] | 819 | /* z will be set to 1, infinity flag to "false" */ |
Denys Vlasenko | 39a3ef5 | 2021-04-27 01:31:51 +0200 | [diff] [blame] | 820 | }; |
| 821 | sp_point p256_base; |
| 822 | |
Denys Vlasenko | 48a18d1 | 2021-04-27 12:24:21 +0200 | [diff] [blame] | 823 | sp_256_point_from_bin2x32(&p256_base, p256_base_bin); |
Denys Vlasenko | 39a3ef5 | 2021-04-27 01:31:51 +0200 | [diff] [blame] | 824 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 825 | sp_256_ecc_mulmod_10(r, &p256_base, k /*, map*/); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 826 | } |
| 827 | |
| 828 | /* Multiply the point by the scalar and serialize the X ordinate. |
| 829 | * The number is 0 padded to maximum size on output. |
| 830 | * |
| 831 | * priv Scalar to multiply the point by. |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 832 | * pub2x32 Point to multiply. |
| 833 | * out32 Buffer to hold X ordinate. |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 834 | */ |
Denys Vlasenko | a2bc52d | 2021-04-27 01:21:26 +0200 | [diff] [blame] | 835 | static void sp_ecc_secret_gen_256(const sp_digit priv[10], const uint8_t *pub2x32, uint8_t* out32) |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 836 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 837 | sp_point point[1]; |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 838 | |
| 839 | #if FIXED_PEER_PUBKEY |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 840 | memset((void*)pub2x32, 0x55, 64); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 841 | #endif |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 842 | dump_hex("peerkey %s\n", pub2x32, 32); /* in TLS, this is peer's public key */ |
| 843 | dump_hex(" %s\n", pub2x32 + 32, 32); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 844 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 845 | sp_256_point_from_bin2x32(point, pub2x32); |
| 846 | dump_hex("point->x %s\n", point->x, sizeof(point->x)); |
| 847 | dump_hex("point->y %s\n", point->y, sizeof(point->y)); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 848 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 849 | sp_256_ecc_mulmod_10(point, point, priv); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 850 | |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 851 | sp_256_to_bin(point->x, out32); |
| 852 | dump_hex("out32: %s\n", out32, 32); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 853 | } |
| 854 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 855 | /* Generates a scalar that is in the range 1..order-1. */ |
| 856 | #define SIMPLIFY 1 |
| 857 | /* Add 1 to a. (a = a + 1) */ |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 858 | static void sp_256_add_one_10(sp_digit* a) |
| 859 | { |
Denys Vlasenko | 1204012 | 2021-04-26 20:24:34 +0200 | [diff] [blame] | 860 | a[0]++; |
| 861 | sp_256_norm_10(a); |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 862 | } |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 863 | static void sp_256_ecc_gen_k_10(sp_digit k[10]) |
| 864 | { |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 865 | #if !SIMPLIFY |
| 866 | /* The order of the curve P256 minus 2. */ |
| 867 | static const sp_digit p256_order2[10] = { |
| 868 | 0x063254f,0x272b0bf,0x1e84f3b,0x2b69c5e,0x3bce6fa, |
| 869 | 0x3ffffff,0x3ffffff,0x00003ff,0x3ff0000,0x03fffff, |
| 870 | }; |
| 871 | #endif |
| 872 | uint8_t buf[32]; |
| 873 | |
| 874 | for (;;) { |
| 875 | tls_get_random(buf, sizeof(buf)); |
| 876 | #if FIXED_SECRET |
| 877 | memset(buf, 0x77, sizeof(buf)); |
| 878 | #endif |
| 879 | sp_256_from_bin(k, 10, buf, sizeof(buf)); |
| 880 | #if !SIMPLIFY |
| 881 | if (sp_256_cmp_10(k, p256_order2) < 0) |
| 882 | break; |
| 883 | #else |
| 884 | /* non-loopy version (and not needing p256_order2[]): |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 885 | * if most-significant word seems that k can be larger |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 886 | * than p256_order2, fix it up: |
| 887 | */ |
| 888 | if (k[9] >= 0x03fffff) |
| 889 | k[9] = 0x03ffffe; |
| 890 | break; |
| 891 | #endif |
| 892 | } |
| 893 | sp_256_add_one_10(k); |
| 894 | #undef SIMPLIFY |
| 895 | } |
| 896 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 897 | /* Makes a random EC key pair. */ |
| 898 | static void sp_ecc_make_key_256(sp_digit privkey[10], uint8_t *pubkey) |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 899 | { |
| 900 | sp_point point[1]; |
| 901 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 902 | sp_256_ecc_gen_k_10(privkey); |
| 903 | sp_256_ecc_mulmod_base_10(point, privkey); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 904 | sp_256_to_bin(point->x, pubkey); |
| 905 | sp_256_to_bin(point->y, pubkey + 32); |
| 906 | |
| 907 | memset(point, 0, sizeof(point)); //paranoia |
| 908 | } |
| 909 | |
| 910 | void FAST_FUNC curve_P256_compute_pubkey_and_premaster( |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 911 | uint8_t *pubkey2x32, uint8_t *premaster32, |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 912 | const uint8_t *peerkey2x32) |
| 913 | { |
| 914 | sp_digit privkey[10]; |
| 915 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 916 | sp_ecc_make_key_256(privkey, pubkey2x32); |
| 917 | dump_hex("pubkey: %s\n", pubkey2x32, 32); |
| 918 | dump_hex(" %s\n", pubkey2x32 + 32, 32); |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 919 | |
Denys Vlasenko | 074b33b | 2021-04-26 14:33:38 +0200 | [diff] [blame] | 920 | /* Combine our privkey and peer's public key to generate premaster */ |
Denys Vlasenko | f18a1fd | 2021-04-26 13:25:56 +0200 | [diff] [blame] | 921 | sp_ecc_secret_gen_256(privkey, /*x,y:*/peerkey2x32, premaster32); |
| 922 | dump_hex("premaster: %s\n", premaster32, 32); |
| 923 | } |