1 /* 2 * Copyright 2017-2021 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright 2015-2016 Cryptography Research, Inc. 4 * 5 * Licensed under the Apache License 2.0 (the "License"). You may not use 6 * this file except in compliance with the License. You can obtain a copy 7 * in the file LICENSE in the source distribution or at 8 * https://www.openssl.org/source/license.html 9 * 10 * Originally written by Mike Hamburg 11 */ 12 #include <openssl/crypto.h> 13 14 #include "word.h" 15 #include "point_448.h" 16 17 static const c448_word_t MONTGOMERY_FACTOR = (c448_word_t) 0x3bd440fae918bc5ULL; 18 static const curve448_scalar_t sc_p = { 19 { 20 { 21 SC_LIMB(0x2378c292ab5844f3ULL), SC_LIMB(0x216cc2728dc58f55ULL), 22 SC_LIMB(0xc44edb49aed63690ULL), SC_LIMB(0xffffffff7cca23e9ULL), 23 SC_LIMB(0xffffffffffffffffULL), SC_LIMB(0xffffffffffffffffULL), 24 SC_LIMB(0x3fffffffffffffffULL) 25 } 26 } 27 }, sc_r2 = { 28 { 29 { 30 31 SC_LIMB(0xe3539257049b9b60ULL), SC_LIMB(0x7af32c4bc1b195d9ULL), 32 SC_LIMB(0x0d66de2388ea1859ULL), SC_LIMB(0xae17cf725ee4d838ULL), 33 SC_LIMB(0x1a9cc14ba3c47c44ULL), SC_LIMB(0x2052bcb7e4d070afULL), 34 SC_LIMB(0x3402a939f823b729ULL) 35 } 36 } 37 }; 38 39 #define WBITS C448_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */ 40 41 const curve448_scalar_t ossl_curve448_scalar_one = {{{1}}}; 42 const curve448_scalar_t ossl_curve448_scalar_zero = {{{0}}}; 43 44 /* 45 * {extra,accum} - sub +? p 46 * Must have extra <= 1 47 */ 48 static void sc_subx(curve448_scalar_t out, 49 const c448_word_t accum[C448_SCALAR_LIMBS], 50 const curve448_scalar_t sub, 51 const curve448_scalar_t p, c448_word_t extra) 52 { 53 c448_dsword_t chain = 0; 54 unsigned int i; 55 c448_word_t borrow; 56 57 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 58 chain = (chain + accum[i]) - sub->limb[i]; 59 out->limb[i] = (c448_word_t)chain; 60 chain >>= WBITS; 61 } 62 borrow = (c448_word_t)chain + extra; /* = 0 or -1 */ 63 64 chain = 0; 65 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 66 chain = (chain + out->limb[i]) + (p->limb[i] & borrow); 67 out->limb[i] = (c448_word_t)chain; 68 chain >>= WBITS; 69 } 70 } 71 72 static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a, 73 const curve448_scalar_t b) 74 { 75 unsigned int i, j; 76 c448_word_t accum[C448_SCALAR_LIMBS + 1] = { 0 }; 77 c448_word_t hi_carry = 0; 78 79 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 80 c448_word_t mand = a->limb[i]; 81 const c448_word_t *mier = b->limb; 82 83 c448_dword_t chain = 0; 84 for (j = 0; j < C448_SCALAR_LIMBS; j++) { 85 chain += ((c448_dword_t) mand) * mier[j] + accum[j]; 86 accum[j] = (c448_word_t)chain; 87 chain >>= WBITS; 88 } 89 accum[j] = (c448_word_t)chain; 90 91 mand = accum[0] * MONTGOMERY_FACTOR; 92 chain = 0; 93 mier = sc_p->limb; 94 for (j = 0; j < C448_SCALAR_LIMBS; j++) { 95 chain += (c448_dword_t) mand *mier[j] + accum[j]; 96 if (j) 97 accum[j - 1] = (c448_word_t)chain; 98 chain >>= WBITS; 99 } 100 chain += accum[j]; 101 chain += hi_carry; 102 accum[j - 1] = (c448_word_t)chain; 103 hi_carry = chain >> WBITS; 104 } 105 106 sc_subx(out, accum, sc_p, sc_p, hi_carry); 107 } 108 109 void ossl_curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a, 110 const curve448_scalar_t b) 111 { 112 sc_montmul(out, a, b); 113 sc_montmul(out, out, sc_r2); 114 } 115 116 void 117 ossl_curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a, 118 const curve448_scalar_t b) 119 { 120 sc_subx(out, a->limb, b, sc_p, 0); 121 } 122 123 void 124 ossl_curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a, 125 const curve448_scalar_t b) 126 { 127 c448_dword_t chain = 0; 128 unsigned int i; 129 130 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 131 chain = (chain + a->limb[i]) + b->limb[i]; 132 out->limb[i] = (c448_word_t)chain; 133 chain >>= WBITS; 134 } 135 sc_subx(out, out->limb, sc_p, sc_p, (c448_word_t)chain); 136 } 137 138 static ossl_inline void scalar_decode_short(curve448_scalar_t s, 139 const unsigned char *ser, 140 size_t nbytes) 141 { 142 size_t i, j, k = 0; 143 144 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 145 c448_word_t out = 0; 146 147 for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++) 148 out |= ((c448_word_t) ser[k]) << (8 * j); 149 s->limb[i] = out; 150 } 151 } 152 153 c448_error_t 154 ossl_curve448_scalar_decode(curve448_scalar_t s, 155 const unsigned char ser[C448_SCALAR_BYTES]) 156 { 157 unsigned int i; 158 c448_dsword_t accum = 0; 159 160 scalar_decode_short(s, ser, C448_SCALAR_BYTES); 161 for (i = 0; i < C448_SCALAR_LIMBS; i++) 162 accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS; 163 /* Here accum == 0 or -1 */ 164 165 ossl_curve448_scalar_mul(s, s, ossl_curve448_scalar_one); /* ham-handed reduce */ 166 167 return c448_succeed_if(~word_is_zero((uint32_t)accum)); 168 } 169 170 void ossl_curve448_scalar_destroy(curve448_scalar_t scalar) 171 { 172 OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t)); 173 } 174 175 void 176 ossl_curve448_scalar_decode_long(curve448_scalar_t s, 177 const unsigned char *ser, size_t ser_len) 178 { 179 size_t i; 180 curve448_scalar_t t1, t2; 181 182 if (ser_len == 0) { 183 curve448_scalar_copy(s, ossl_curve448_scalar_zero); 184 return; 185 } 186 187 i = ser_len - (ser_len % C448_SCALAR_BYTES); 188 if (i == ser_len) 189 i -= C448_SCALAR_BYTES; 190 191 scalar_decode_short(t1, &ser[i], ser_len - i); 192 193 if (ser_len == sizeof(curve448_scalar_t)) { 194 assert(i == 0); 195 /* ham-handed reduce */ 196 ossl_curve448_scalar_mul(s, t1, ossl_curve448_scalar_one); 197 ossl_curve448_scalar_destroy(t1); 198 return; 199 } 200 201 while (i) { 202 i -= C448_SCALAR_BYTES; 203 sc_montmul(t1, t1, sc_r2); 204 (void)ossl_curve448_scalar_decode(t2, ser + i); 205 ossl_curve448_scalar_add(t1, t1, t2); 206 } 207 208 curve448_scalar_copy(s, t1); 209 ossl_curve448_scalar_destroy(t1); 210 ossl_curve448_scalar_destroy(t2); 211 } 212 213 void 214 ossl_curve448_scalar_encode(unsigned char ser[C448_SCALAR_BYTES], 215 const curve448_scalar_t s) 216 { 217 unsigned int i, j, k = 0; 218 219 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 220 for (j = 0; j < sizeof(c448_word_t); j++, k++) 221 ser[k] = s->limb[i] >> (8 * j); 222 } 223 } 224 225 void 226 ossl_curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a) 227 { 228 c448_word_t mask = 0 - (a->limb[0] & 1); 229 c448_dword_t chain = 0; 230 unsigned int i; 231 232 for (i = 0; i < C448_SCALAR_LIMBS; i++) { 233 chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask); 234 out->limb[i] = (c448_word_t)chain; 235 chain >>= C448_WORD_BITS; 236 } 237 for (i = 0; i < C448_SCALAR_LIMBS - 1; i++) 238 out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1); 239 out->limb[i] = out->limb[i] >> 1 | (c448_word_t)(chain << (WBITS - 1)); 240 } 241