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