/src/openssl/crypto/ec/curve448/scalar.c
Line | Count | Source (jump to first uncovered line) |
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 | 819 | #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 | 9 | { |
53 | 9 | c448_dsword_t chain = 0; |
54 | 9 | unsigned int i; |
55 | 9 | c448_word_t borrow; |
56 | | |
57 | 72 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
58 | 63 | chain = (chain + accum[i]) - sub->limb[i]; |
59 | 63 | out->limb[i] = (c448_word_t)chain; |
60 | 63 | chain >>= WBITS; |
61 | 63 | } |
62 | 9 | borrow = (c448_word_t)chain + extra; /* = 0 or -1 */ |
63 | | |
64 | 9 | chain = 0; |
65 | 72 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
66 | 63 | chain = (chain + out->limb[i]) + (p->limb[i] & borrow); |
67 | 63 | out->limb[i] = (c448_word_t)chain; |
68 | 63 | chain >>= WBITS; |
69 | 63 | } |
70 | 9 | } |
71 | | |
72 | | static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a, |
73 | | const curve448_scalar_t b) |
74 | 6 | { |
75 | 6 | unsigned int i, j; |
76 | 6 | c448_word_t accum[C448_SCALAR_LIMBS + 1] = { 0 }; |
77 | 6 | c448_word_t hi_carry = 0; |
78 | | |
79 | 48 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
80 | 42 | c448_word_t mand = a->limb[i]; |
81 | 42 | const c448_word_t *mier = b->limb; |
82 | | |
83 | 42 | c448_dword_t chain = 0; |
84 | 336 | for (j = 0; j < C448_SCALAR_LIMBS; j++) { |
85 | 294 | chain += ((c448_dword_t) mand) * mier[j] + accum[j]; |
86 | 294 | accum[j] = (c448_word_t)chain; |
87 | 294 | chain >>= WBITS; |
88 | 294 | } |
89 | 42 | accum[j] = (c448_word_t)chain; |
90 | | |
91 | 42 | mand = accum[0] * MONTGOMERY_FACTOR; |
92 | 42 | chain = 0; |
93 | 42 | mier = sc_p->limb; |
94 | 336 | for (j = 0; j < C448_SCALAR_LIMBS; j++) { |
95 | 294 | chain += (c448_dword_t) mand *mier[j] + accum[j]; |
96 | 294 | if (j) |
97 | 252 | accum[j - 1] = (c448_word_t)chain; |
98 | 294 | chain >>= WBITS; |
99 | 294 | } |
100 | 42 | chain += accum[j]; |
101 | 42 | chain += hi_carry; |
102 | 42 | accum[j - 1] = (c448_word_t)chain; |
103 | 42 | hi_carry = chain >> WBITS; |
104 | 42 | } |
105 | | |
106 | 6 | sc_subx(out, accum, sc_p, sc_p, hi_carry); |
107 | 6 | } |
108 | | |
109 | | void ossl_curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a, |
110 | | const curve448_scalar_t b) |
111 | 3 | { |
112 | 3 | sc_montmul(out, a, b); |
113 | 3 | sc_montmul(out, out, sc_r2); |
114 | 3 | } |
115 | | |
116 | | void |
117 | | ossl_curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a, |
118 | | const curve448_scalar_t b) |
119 | 0 | { |
120 | 0 | sc_subx(out, a->limb, b, sc_p, 0); |
121 | 0 | } |
122 | | |
123 | | void |
124 | | ossl_curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a, |
125 | | const curve448_scalar_t b) |
126 | 3 | { |
127 | 3 | c448_dword_t chain = 0; |
128 | 3 | unsigned int i; |
129 | | |
130 | 24 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
131 | 21 | chain = (chain + a->limb[i]) + b->limb[i]; |
132 | 21 | out->limb[i] = (c448_word_t)chain; |
133 | 21 | chain >>= WBITS; |
134 | 21 | } |
135 | 3 | sc_subx(out, out->limb, sc_p, sc_p, (c448_word_t)chain); |
136 | 3 | } |
137 | | |
138 | | static ossl_inline void scalar_decode_short(curve448_scalar_t s, |
139 | | const unsigned char *ser, |
140 | | size_t nbytes) |
141 | 3 | { |
142 | 3 | size_t i, j, k = 0; |
143 | | |
144 | 24 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
145 | 21 | c448_word_t out = 0; |
146 | | |
147 | 189 | for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++) |
148 | 168 | out |= ((c448_word_t) ser[k]) << (8 * j); |
149 | 21 | s->limb[i] = out; |
150 | 21 | } |
151 | 3 | } |
152 | | |
153 | | c448_error_t |
154 | | ossl_curve448_scalar_decode(curve448_scalar_t s, |
155 | | const unsigned char ser[C448_SCALAR_BYTES]) |
156 | 0 | { |
157 | 0 | unsigned int i; |
158 | 0 | c448_dsword_t accum = 0; |
159 | |
|
160 | 0 | scalar_decode_short(s, ser, C448_SCALAR_BYTES); |
161 | 0 | for (i = 0; i < C448_SCALAR_LIMBS; i++) |
162 | 0 | accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS; |
163 | | /* Here accum == 0 or -1 */ |
164 | |
|
165 | 0 | ossl_curve448_scalar_mul(s, s, ossl_curve448_scalar_one); /* ham-handed reduce */ |
166 | |
|
167 | 0 | return c448_succeed_if(~word_is_zero((uint32_t)accum)); |
168 | 0 | } |
169 | | |
170 | | void ossl_curve448_scalar_destroy(curve448_scalar_t scalar) |
171 | 3 | { |
172 | 3 | OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t)); |
173 | 3 | } |
174 | | |
175 | | void |
176 | | ossl_curve448_scalar_decode_long(curve448_scalar_t s, |
177 | | const unsigned char *ser, size_t ser_len) |
178 | 3 | { |
179 | 3 | size_t i; |
180 | 3 | curve448_scalar_t t1, t2; |
181 | | |
182 | 3 | if (ser_len == 0) { |
183 | 0 | curve448_scalar_copy(s, ossl_curve448_scalar_zero); |
184 | 0 | return; |
185 | 0 | } |
186 | | |
187 | 3 | i = ser_len - (ser_len % C448_SCALAR_BYTES); |
188 | 3 | if (i == ser_len) |
189 | 3 | i -= C448_SCALAR_BYTES; |
190 | | |
191 | 3 | scalar_decode_short(t1, &ser[i], ser_len - i); |
192 | | |
193 | 3 | if (ser_len == sizeof(curve448_scalar_t)) { |
194 | 3 | assert(i == 0); |
195 | | /* ham-handed reduce */ |
196 | 3 | ossl_curve448_scalar_mul(s, t1, ossl_curve448_scalar_one); |
197 | 3 | ossl_curve448_scalar_destroy(t1); |
198 | 3 | return; |
199 | 3 | } |
200 | | |
201 | 0 | while (i) { |
202 | 0 | i -= C448_SCALAR_BYTES; |
203 | 0 | sc_montmul(t1, t1, sc_r2); |
204 | 0 | (void)ossl_curve448_scalar_decode(t2, ser + i); |
205 | 0 | ossl_curve448_scalar_add(t1, t1, t2); |
206 | 0 | } |
207 | |
|
208 | 0 | curve448_scalar_copy(s, t1); |
209 | 0 | ossl_curve448_scalar_destroy(t1); |
210 | 0 | ossl_curve448_scalar_destroy(t2); |
211 | 0 | } |
212 | | |
213 | | void |
214 | | ossl_curve448_scalar_encode(unsigned char ser[C448_SCALAR_BYTES], |
215 | | const curve448_scalar_t s) |
216 | 0 | { |
217 | 0 | unsigned int i, j, k = 0; |
218 | |
|
219 | 0 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
220 | 0 | for (j = 0; j < sizeof(c448_word_t); j++, k++) |
221 | 0 | ser[k] = s->limb[i] >> (8 * j); |
222 | 0 | } |
223 | 0 | } |
224 | | |
225 | | void |
226 | | ossl_curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a) |
227 | 6 | { |
228 | 6 | c448_word_t mask = 0 - (a->limb[0] & 1); |
229 | 6 | c448_dword_t chain = 0; |
230 | 6 | unsigned int i; |
231 | | |
232 | 48 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
233 | 42 | chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask); |
234 | 42 | out->limb[i] = (c448_word_t)chain; |
235 | 42 | chain >>= C448_WORD_BITS; |
236 | 42 | } |
237 | 42 | for (i = 0; i < C448_SCALAR_LIMBS - 1; i++) |
238 | 36 | out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1); |
239 | 6 | out->limb[i] = out->limb[i] >> 1 | (c448_word_t)(chain << (WBITS - 1)); |
240 | 6 | } |