/src/botan/src/lib/math/numbertheory/nistp_redc.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * NIST prime reductions |
3 | | * (C) 2014,2015,2018 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/internal/curve_nistp.h> |
9 | | |
10 | | #include <botan/internal/ct_utils.h> |
11 | | #include <botan/internal/mp_core.h> |
12 | | |
13 | | namespace Botan { |
14 | | |
15 | 0 | const BigInt& prime_p521() { |
16 | 0 | static const BigInt p521( |
17 | 0 | "0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" |
18 | 0 | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"); |
19 | |
|
20 | 0 | return p521; |
21 | 0 | } |
22 | | |
23 | 0 | void redc_p521(BigInt& x, secure_vector<word>& ws) { |
24 | 0 | BOTAN_DEBUG_ASSERT(x.is_positive()); |
25 | |
|
26 | 0 | const size_t p_full_words = 521 / BOTAN_MP_WORD_BITS; |
27 | 0 | const size_t p_top_bits = 521 % BOTAN_MP_WORD_BITS; |
28 | 0 | const size_t p_words = p_full_words + 1; |
29 | |
|
30 | 0 | #if(BOTAN_MP_WORD_BITS == 64) |
31 | 0 | static const word p521_words[p_words] = {0xFFFFFFFFFFFFFFFF, |
32 | 0 | 0xFFFFFFFFFFFFFFFF, |
33 | 0 | 0xFFFFFFFFFFFFFFFF, |
34 | 0 | 0xFFFFFFFFFFFFFFFF, |
35 | 0 | 0xFFFFFFFFFFFFFFFF, |
36 | 0 | 0xFFFFFFFFFFFFFFFF, |
37 | 0 | 0xFFFFFFFFFFFFFFFF, |
38 | 0 | 0xFFFFFFFFFFFFFFFF, |
39 | 0 | 0x1FF}; |
40 | | #else |
41 | | static const word p521_words[p_words] = {0xFFFFFFFF, |
42 | | 0xFFFFFFFF, |
43 | | 0xFFFFFFFF, |
44 | | 0xFFFFFFFF, |
45 | | 0xFFFFFFFF, |
46 | | 0xFFFFFFFF, |
47 | | 0xFFFFFFFF, |
48 | | 0xFFFFFFFF, |
49 | | 0xFFFFFFFF, |
50 | | 0xFFFFFFFF, |
51 | | 0xFFFFFFFF, |
52 | | 0xFFFFFFFF, |
53 | | 0xFFFFFFFF, |
54 | | 0xFFFFFFFF, |
55 | | 0xFFFFFFFF, |
56 | | 0xFFFFFFFF, |
57 | | 0x1FF}; |
58 | | #endif |
59 | |
|
60 | 0 | if(ws.size() < p_words + 1) { |
61 | 0 | ws.resize(p_words + 1); |
62 | 0 | } |
63 | |
|
64 | 0 | clear_mem(ws.data(), ws.size()); |
65 | 0 | bigint_shr2(ws.data(), x.data(), std::min(x.size(), 2 * p_words), p_full_words, p_top_bits); |
66 | |
|
67 | 0 | x.mask_bits(521); |
68 | 0 | x.grow_to(p_words); |
69 | | |
70 | | // Word-level carry will be zero |
71 | 0 | word carry = bigint_add3_nc(x.mutable_data(), x.data(), p_words, ws.data(), p_words); |
72 | 0 | BOTAN_ASSERT_EQUAL(carry, 0, "Final carry in P-521 reduction"); |
73 | |
|
74 | 0 | const word top_word = x.word_at(p_full_words); |
75 | | |
76 | | /* |
77 | | * Check if we need to reduce modulo P |
78 | | * There are two possible cases: |
79 | | * - The result overflowed past 521 bits, in which case bit 522 will be set |
80 | | * - The result is exactly 2**521 - 1 |
81 | | */ |
82 | 0 | const auto bit_522_set = CT::Mask<word>::expand(top_word >> p_top_bits); |
83 | |
|
84 | 0 | word and_512 = MP_WORD_MAX; |
85 | 0 | for(size_t i = 0; i != p_full_words; ++i) { |
86 | 0 | and_512 &= x.word_at(i); |
87 | 0 | } |
88 | 0 | const auto all_512_low_bits_set = CT::Mask<word>::is_equal(and_512, MP_WORD_MAX); |
89 | 0 | const auto has_p521_top_word = CT::Mask<word>::is_equal(top_word, 0x1FF); |
90 | 0 | const auto is_p521 = all_512_low_bits_set & has_p521_top_word; |
91 | |
|
92 | 0 | const auto needs_reduction = is_p521 | bit_522_set; |
93 | |
|
94 | 0 | bigint_cnd_sub(needs_reduction.value(), x.mutable_data(), p521_words, p_words); |
95 | 0 | } |
96 | | |
97 | | namespace { |
98 | | |
99 | | /** |
100 | | * Treating this MPI as a sequence of 32-bit words in big-endian |
101 | | * order, return word i. The array is assumed to be large enough. |
102 | | */ |
103 | 1.57G | inline uint32_t get_uint32(const word xw[], size_t i) { |
104 | | #if(BOTAN_MP_WORD_BITS == 32) |
105 | | return xw[i]; |
106 | | #else |
107 | 1.57G | return static_cast<uint32_t>(xw[i / 2] >> ((i % 2) * 32)); |
108 | 1.57G | #endif |
109 | 1.57G | } |
110 | | |
111 | 394M | inline void set_words(word x[], size_t i, uint32_t R0, uint32_t R1) { |
112 | | #if(BOTAN_MP_WORD_BITS == 32) |
113 | | x[i] = R0; |
114 | | x[i + 1] = R1; |
115 | | #else |
116 | 394M | x[i / 2] = (static_cast<uint64_t>(R1) << 32) | R0; |
117 | 394M | #endif |
118 | 394M | } |
119 | | |
120 | | } // namespace |
121 | | |
122 | 1 | const BigInt& prime_p192() { |
123 | 1 | static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"); |
124 | 1 | return p192; |
125 | 1 | } |
126 | | |
127 | 0 | void redc_p192(BigInt& x, secure_vector<word>& ws) { |
128 | 0 | BOTAN_DEBUG_ASSERT(x.is_positive()); |
129 | |
|
130 | 0 | BOTAN_UNUSED(ws); |
131 | |
|
132 | 0 | static const size_t p192_limbs = 192 / BOTAN_MP_WORD_BITS; |
133 | |
|
134 | 0 | x.grow_to(2 * p192_limbs); |
135 | 0 | word* xw = x.mutable_data(); |
136 | |
|
137 | 0 | const uint64_t X00 = get_uint32(xw, 0); |
138 | 0 | const uint64_t X01 = get_uint32(xw, 1); |
139 | 0 | const uint64_t X02 = get_uint32(xw, 2); |
140 | 0 | const uint64_t X03 = get_uint32(xw, 3); |
141 | 0 | const uint64_t X04 = get_uint32(xw, 4); |
142 | 0 | const uint64_t X05 = get_uint32(xw, 5); |
143 | 0 | const uint64_t X06 = get_uint32(xw, 6); |
144 | 0 | const uint64_t X07 = get_uint32(xw, 7); |
145 | 0 | const uint64_t X08 = get_uint32(xw, 8); |
146 | 0 | const uint64_t X09 = get_uint32(xw, 9); |
147 | 0 | const uint64_t X10 = get_uint32(xw, 10); |
148 | 0 | const uint64_t X11 = get_uint32(xw, 11); |
149 | |
|
150 | 0 | const uint64_t S0 = X00 + X06 + X10; |
151 | 0 | const uint64_t S1 = X01 + X07 + X11; |
152 | 0 | const uint64_t S2 = X02 + X06 + X08 + X10; |
153 | 0 | const uint64_t S3 = X03 + X07 + X09 + X11; |
154 | 0 | const uint64_t S4 = X04 + X08 + X10; |
155 | 0 | const uint64_t S5 = X05 + X09 + X11; |
156 | |
|
157 | 0 | uint64_t S = 0; |
158 | 0 | uint32_t R0 = 0, R1 = 0; |
159 | |
|
160 | 0 | S += S0; |
161 | 0 | R0 = static_cast<uint32_t>(S); |
162 | 0 | S >>= 32; |
163 | |
|
164 | 0 | S += S1; |
165 | 0 | R1 = static_cast<uint32_t>(S); |
166 | 0 | S >>= 32; |
167 | |
|
168 | 0 | set_words(xw, 0, R0, R1); |
169 | |
|
170 | 0 | S += S2; |
171 | 0 | R0 = static_cast<uint32_t>(S); |
172 | 0 | S >>= 32; |
173 | |
|
174 | 0 | S += S3; |
175 | 0 | R1 = static_cast<uint32_t>(S); |
176 | 0 | S >>= 32; |
177 | |
|
178 | 0 | set_words(xw, 2, R0, R1); |
179 | |
|
180 | 0 | S += S4; |
181 | 0 | R0 = static_cast<uint32_t>(S); |
182 | 0 | S >>= 32; |
183 | |
|
184 | 0 | S += S5; |
185 | 0 | R1 = static_cast<uint32_t>(S); |
186 | 0 | S >>= 32; |
187 | |
|
188 | 0 | set_words(xw, 4, R0, R1); |
189 | | |
190 | | // No underflow possible |
191 | | |
192 | | /* |
193 | | This is a table of (i*P-192) % 2**192 for i in 1...3 |
194 | | */ |
195 | 0 | static const word p192_mults[3][p192_limbs] = { |
196 | 0 | #if(BOTAN_MP_WORD_BITS == 64) |
197 | 0 | {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF}, |
198 | 0 | {0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFD, 0xFFFFFFFFFFFFFFFF}, |
199 | 0 | {0xFFFFFFFFFFFFFFFD, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFFF}, |
200 | | #else |
201 | | {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, |
202 | | {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, |
203 | | {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, |
204 | | #endif |
205 | 0 | }; |
206 | |
|
207 | 0 | CT::unpoison(S); |
208 | 0 | BOTAN_ASSERT(S <= 2, "Expected overflow"); |
209 | |
|
210 | 0 | BOTAN_ASSERT_NOMSG(x.size() >= p192_limbs + 1); |
211 | 0 | x.mask_bits(192); |
212 | 0 | word borrow = bigint_sub2(x.mutable_data(), p192_limbs + 1, p192_mults[S], p192_limbs); |
213 | 0 | BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); |
214 | 0 | bigint_cnd_add(borrow, x.mutable_data(), p192_limbs + 1, p192_mults[0], p192_limbs); |
215 | 0 | } |
216 | | |
217 | 1 | const BigInt& prime_p224() { |
218 | 1 | static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"); |
219 | 1 | return p224; |
220 | 1 | } |
221 | | |
222 | 0 | void redc_p224(BigInt& x, secure_vector<word>& ws) { |
223 | 0 | BOTAN_DEBUG_ASSERT(x.is_positive()); |
224 | |
|
225 | 0 | static const size_t p224_limbs = (BOTAN_MP_WORD_BITS == 32) ? 7 : 4; |
226 | |
|
227 | 0 | BOTAN_UNUSED(ws); |
228 | |
|
229 | 0 | x.grow_to(2 * p224_limbs); |
230 | 0 | word* xw = x.mutable_data(); |
231 | |
|
232 | 0 | const int64_t X00 = get_uint32(xw, 0); |
233 | 0 | const int64_t X01 = get_uint32(xw, 1); |
234 | 0 | const int64_t X02 = get_uint32(xw, 2); |
235 | 0 | const int64_t X03 = get_uint32(xw, 3); |
236 | 0 | const int64_t X04 = get_uint32(xw, 4); |
237 | 0 | const int64_t X05 = get_uint32(xw, 5); |
238 | 0 | const int64_t X06 = get_uint32(xw, 6); |
239 | 0 | const int64_t X07 = get_uint32(xw, 7); |
240 | 0 | const int64_t X08 = get_uint32(xw, 8); |
241 | 0 | const int64_t X09 = get_uint32(xw, 9); |
242 | 0 | const int64_t X10 = get_uint32(xw, 10); |
243 | 0 | const int64_t X11 = get_uint32(xw, 11); |
244 | 0 | const int64_t X12 = get_uint32(xw, 12); |
245 | 0 | const int64_t X13 = get_uint32(xw, 13); |
246 | | |
247 | | // One full copy of P224 is added, so the result is always positive |
248 | |
|
249 | 0 | const int64_t S0 = 0x00000001 + X00 - X07 - X11; |
250 | 0 | const int64_t S1 = 0x00000000 + X01 - X08 - X12; |
251 | 0 | const int64_t S2 = 0x00000000 + X02 - X09 - X13; |
252 | 0 | const int64_t S3 = 0xFFFFFFFF + X03 + X07 + X11 - X10; |
253 | 0 | const int64_t S4 = 0xFFFFFFFF + X04 + X08 + X12 - X11; |
254 | 0 | const int64_t S5 = 0xFFFFFFFF + X05 + X09 + X13 - X12; |
255 | 0 | const int64_t S6 = 0xFFFFFFFF + X06 + X10 - X13; |
256 | |
|
257 | 0 | int64_t S = 0; |
258 | 0 | uint32_t R0 = 0, R1 = 0; |
259 | |
|
260 | 0 | S += S0; |
261 | 0 | R0 = static_cast<uint32_t>(S); |
262 | 0 | S >>= 32; |
263 | |
|
264 | 0 | S += S1; |
265 | 0 | R1 = static_cast<uint32_t>(S); |
266 | 0 | S >>= 32; |
267 | |
|
268 | 0 | set_words(xw, 0, R0, R1); |
269 | |
|
270 | 0 | S += S2; |
271 | 0 | R0 = static_cast<uint32_t>(S); |
272 | 0 | S >>= 32; |
273 | |
|
274 | 0 | S += S3; |
275 | 0 | R1 = static_cast<uint32_t>(S); |
276 | 0 | S >>= 32; |
277 | |
|
278 | 0 | set_words(xw, 2, R0, R1); |
279 | |
|
280 | 0 | S += S4; |
281 | 0 | R0 = static_cast<uint32_t>(S); |
282 | 0 | S >>= 32; |
283 | |
|
284 | 0 | S += S5; |
285 | 0 | R1 = static_cast<uint32_t>(S); |
286 | 0 | S >>= 32; |
287 | |
|
288 | 0 | set_words(xw, 4, R0, R1); |
289 | |
|
290 | 0 | S += S6; |
291 | 0 | R0 = static_cast<uint32_t>(S); |
292 | 0 | S >>= 32; |
293 | |
|
294 | 0 | set_words(xw, 6, R0, 0); |
295 | |
|
296 | 0 | static const word p224_mults[3][p224_limbs] = { |
297 | 0 | #if(BOTAN_MP_WORD_BITS == 64) |
298 | 0 | {0x0000000000000001, 0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF}, |
299 | 0 | {0x0000000000000002, 0xFFFFFFFE00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF}, |
300 | 0 | {0x0000000000000003, 0xFFFFFFFD00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF}, |
301 | | #else |
302 | | {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, |
303 | | {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, |
304 | | {0x00000003, 0x00000000, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} |
305 | | #endif |
306 | |
|
307 | 0 | }; |
308 | |
|
309 | 0 | CT::unpoison(S); |
310 | 0 | BOTAN_ASSERT(S >= 0 && S <= 2, "Expected overflow"); |
311 | |
|
312 | 0 | BOTAN_ASSERT_NOMSG(x.size() >= p224_limbs + 1); |
313 | 0 | x.mask_bits(224); |
314 | 0 | word borrow = bigint_sub2(x.mutable_data(), p224_limbs + 1, p224_mults[S], p224_limbs); |
315 | 0 | BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); |
316 | 0 | bigint_cnd_add(borrow, x.mutable_data(), p224_limbs + 1, p224_mults[0], p224_limbs); |
317 | 0 | } |
318 | | |
319 | 1 | const BigInt& prime_p256() { |
320 | 1 | static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"); |
321 | 1 | return p256; |
322 | 1 | } |
323 | | |
324 | 0 | void redc_p256(BigInt& x, secure_vector<word>& ws) { |
325 | 0 | BOTAN_DEBUG_ASSERT(x.is_positive()); |
326 | |
|
327 | 0 | static const size_t p256_limbs = (BOTAN_MP_WORD_BITS == 32) ? 8 : 4; |
328 | |
|
329 | 0 | BOTAN_UNUSED(ws); |
330 | |
|
331 | 0 | x.grow_to(2 * p256_limbs); |
332 | 0 | word* xw = x.mutable_data(); |
333 | |
|
334 | 0 | const int64_t X00 = get_uint32(xw, 0); |
335 | 0 | const int64_t X01 = get_uint32(xw, 1); |
336 | 0 | const int64_t X02 = get_uint32(xw, 2); |
337 | 0 | const int64_t X03 = get_uint32(xw, 3); |
338 | 0 | const int64_t X04 = get_uint32(xw, 4); |
339 | 0 | const int64_t X05 = get_uint32(xw, 5); |
340 | 0 | const int64_t X06 = get_uint32(xw, 6); |
341 | 0 | const int64_t X07 = get_uint32(xw, 7); |
342 | 0 | const int64_t X08 = get_uint32(xw, 8); |
343 | 0 | const int64_t X09 = get_uint32(xw, 9); |
344 | 0 | const int64_t X10 = get_uint32(xw, 10); |
345 | 0 | const int64_t X11 = get_uint32(xw, 11); |
346 | 0 | const int64_t X12 = get_uint32(xw, 12); |
347 | 0 | const int64_t X13 = get_uint32(xw, 13); |
348 | 0 | const int64_t X14 = get_uint32(xw, 14); |
349 | 0 | const int64_t X15 = get_uint32(xw, 15); |
350 | | |
351 | | // Adds 6 * P-256 to prevent underflow |
352 | 0 | const int64_t S0 = 0xFFFFFFFA + X00 + X08 + X09 - (X11 + X12 + X13) - X14; |
353 | 0 | const int64_t S1 = 0xFFFFFFFF + X01 + X09 + X10 - X12 - (X13 + X14 + X15); |
354 | 0 | const int64_t S2 = 0xFFFFFFFF + X02 + X10 + X11 - (X13 + X14 + X15); |
355 | 0 | const int64_t S3 = 0x00000005 + X03 + (X11 + X12) * 2 + X13 - X15 - X08 - X09; |
356 | 0 | const int64_t S4 = 0x00000000 + X04 + (X12 + X13) * 2 + X14 - X09 - X10; |
357 | 0 | const int64_t S5 = 0x00000000 + X05 + (X13 + X14) * 2 + X15 - X10 - X11; |
358 | 0 | const int64_t S6 = 0x00000006 + X06 + X13 + X14 * 3 + X15 * 2 - X08 - X09; |
359 | 0 | const int64_t S7 = 0xFFFFFFFA + X07 + X15 * 3 + X08 - X10 - (X11 + X12 + X13); |
360 | |
|
361 | 0 | int64_t S = 0; |
362 | |
|
363 | 0 | uint32_t R0 = 0, R1 = 0; |
364 | |
|
365 | 0 | S += S0; |
366 | 0 | R0 = static_cast<uint32_t>(S); |
367 | 0 | S >>= 32; |
368 | |
|
369 | 0 | S += S1; |
370 | 0 | R1 = static_cast<uint32_t>(S); |
371 | 0 | S >>= 32; |
372 | |
|
373 | 0 | set_words(xw, 0, R0, R1); |
374 | |
|
375 | 0 | S += S2; |
376 | 0 | R0 = static_cast<uint32_t>(S); |
377 | 0 | S >>= 32; |
378 | |
|
379 | 0 | S += S3; |
380 | 0 | R1 = static_cast<uint32_t>(S); |
381 | 0 | S >>= 32; |
382 | |
|
383 | 0 | set_words(xw, 2, R0, R1); |
384 | |
|
385 | 0 | S += S4; |
386 | 0 | R0 = static_cast<uint32_t>(S); |
387 | 0 | S >>= 32; |
388 | |
|
389 | 0 | S += S5; |
390 | 0 | R1 = static_cast<uint32_t>(S); |
391 | 0 | S >>= 32; |
392 | |
|
393 | 0 | set_words(xw, 4, R0, R1); |
394 | |
|
395 | 0 | S += S6; |
396 | 0 | R0 = static_cast<uint32_t>(S); |
397 | 0 | S >>= 32; |
398 | |
|
399 | 0 | S += S7; |
400 | 0 | R1 = static_cast<uint32_t>(S); |
401 | 0 | S >>= 32; |
402 | 0 | set_words(xw, 6, R0, R1); |
403 | |
|
404 | 0 | S += 5; // the top digits of 6*P-256 |
405 | | |
406 | | /* |
407 | | This is a table of (i*P-256) % 2**256 for i in 1...10 |
408 | | */ |
409 | 0 | static const word p256_mults[11][p256_limbs] = { |
410 | 0 | #if(BOTAN_MP_WORD_BITS == 64) |
411 | 0 | {0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF, 0x0000000000000000, 0xFFFFFFFF00000001}, |
412 | 0 | {0xFFFFFFFFFFFFFFFE, 0x00000001FFFFFFFF, 0x0000000000000000, 0xFFFFFFFE00000002}, |
413 | 0 | {0xFFFFFFFFFFFFFFFD, 0x00000002FFFFFFFF, 0x0000000000000000, 0xFFFFFFFD00000003}, |
414 | 0 | {0xFFFFFFFFFFFFFFFC, 0x00000003FFFFFFFF, 0x0000000000000000, 0xFFFFFFFC00000004}, |
415 | 0 | {0xFFFFFFFFFFFFFFFB, 0x00000004FFFFFFFF, 0x0000000000000000, 0xFFFFFFFB00000005}, |
416 | 0 | {0xFFFFFFFFFFFFFFFA, 0x00000005FFFFFFFF, 0x0000000000000000, 0xFFFFFFFA00000006}, |
417 | 0 | {0xFFFFFFFFFFFFFFF9, 0x00000006FFFFFFFF, 0x0000000000000000, 0xFFFFFFF900000007}, |
418 | 0 | {0xFFFFFFFFFFFFFFF8, 0x00000007FFFFFFFF, 0x0000000000000000, 0xFFFFFFF800000008}, |
419 | 0 | {0xFFFFFFFFFFFFFFF7, 0x00000008FFFFFFFF, 0x0000000000000000, 0xFFFFFFF700000009}, |
420 | 0 | {0xFFFFFFFFFFFFFFF6, 0x00000009FFFFFFFF, 0x0000000000000000, 0xFFFFFFF60000000A}, |
421 | 0 | {0xFFFFFFFFFFFFFFF5, 0x0000000AFFFFFFFF, 0x0000000000000000, 0xFFFFFFF50000000B}, |
422 | | #else |
423 | | {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF}, |
424 | | {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE}, |
425 | | {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002, 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD}, |
426 | | {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003, 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC}, |
427 | | {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004, 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB}, |
428 | | {0xFFFFFFFA, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000005, 0x00000000, 0x00000000, 0x00000006, 0xFFFFFFFA}, |
429 | | {0xFFFFFFF9, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000006, 0x00000000, 0x00000000, 0x00000007, 0xFFFFFFF9}, |
430 | | {0xFFFFFFF8, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000007, 0x00000000, 0x00000000, 0x00000008, 0xFFFFFFF8}, |
431 | | {0xFFFFFFF7, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000008, 0x00000000, 0x00000000, 0x00000009, 0xFFFFFFF7}, |
432 | | {0xFFFFFFF6, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000009, 0x00000000, 0x00000000, 0x0000000A, 0xFFFFFFF6}, |
433 | | {0xFFFFFFF5, 0xFFFFFFFF, 0xFFFFFFFF, 0x0000000A, 0x00000000, 0x00000000, 0x0000000B, 0xFFFFFFF5}, |
434 | | #endif |
435 | 0 | }; |
436 | |
|
437 | 0 | CT::unpoison(S); |
438 | 0 | BOTAN_ASSERT(S >= 0 && S <= 10, "Expected overflow"); |
439 | |
|
440 | 0 | BOTAN_ASSERT_NOMSG(x.size() >= p256_limbs + 1); |
441 | 0 | x.mask_bits(256); |
442 | 0 | word borrow = bigint_sub2(x.mutable_data(), p256_limbs + 1, p256_mults[S], p256_limbs); |
443 | 0 | BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); |
444 | 0 | bigint_cnd_add(borrow, x.mutable_data(), p256_limbs + 1, p256_mults[0], p256_limbs); |
445 | 0 | } |
446 | | |
447 | 4.78M | const BigInt& prime_p384() { |
448 | 4.78M | static const BigInt p384( |
449 | 4.78M | "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"); |
450 | 4.78M | return p384; |
451 | 4.78M | } |
452 | | |
453 | 65.7M | void redc_p384(BigInt& x, secure_vector<word>& ws) { |
454 | 65.7M | BOTAN_DEBUG_ASSERT(x.is_positive()); |
455 | | |
456 | 65.7M | BOTAN_UNUSED(ws); |
457 | | |
458 | 65.7M | static const size_t p384_limbs = (BOTAN_MP_WORD_BITS == 32) ? 12 : 6; |
459 | | |
460 | 65.7M | x.grow_to(2 * p384_limbs); |
461 | 65.7M | word* xw = x.mutable_data(); |
462 | | |
463 | 65.7M | const int64_t X00 = get_uint32(xw, 0); |
464 | 65.7M | const int64_t X01 = get_uint32(xw, 1); |
465 | 65.7M | const int64_t X02 = get_uint32(xw, 2); |
466 | 65.7M | const int64_t X03 = get_uint32(xw, 3); |
467 | 65.7M | const int64_t X04 = get_uint32(xw, 4); |
468 | 65.7M | const int64_t X05 = get_uint32(xw, 5); |
469 | 65.7M | const int64_t X06 = get_uint32(xw, 6); |
470 | 65.7M | const int64_t X07 = get_uint32(xw, 7); |
471 | 65.7M | const int64_t X08 = get_uint32(xw, 8); |
472 | 65.7M | const int64_t X09 = get_uint32(xw, 9); |
473 | 65.7M | const int64_t X10 = get_uint32(xw, 10); |
474 | 65.7M | const int64_t X11 = get_uint32(xw, 11); |
475 | 65.7M | const int64_t X12 = get_uint32(xw, 12); |
476 | 65.7M | const int64_t X13 = get_uint32(xw, 13); |
477 | 65.7M | const int64_t X14 = get_uint32(xw, 14); |
478 | 65.7M | const int64_t X15 = get_uint32(xw, 15); |
479 | 65.7M | const int64_t X16 = get_uint32(xw, 16); |
480 | 65.7M | const int64_t X17 = get_uint32(xw, 17); |
481 | 65.7M | const int64_t X18 = get_uint32(xw, 18); |
482 | 65.7M | const int64_t X19 = get_uint32(xw, 19); |
483 | 65.7M | const int64_t X20 = get_uint32(xw, 20); |
484 | 65.7M | const int64_t X21 = get_uint32(xw, 21); |
485 | 65.7M | const int64_t X22 = get_uint32(xw, 22); |
486 | 65.7M | const int64_t X23 = get_uint32(xw, 23); |
487 | | |
488 | | // One copy of P-384 is added to prevent underflow |
489 | 65.7M | const int64_t S0 = 0xFFFFFFFF + X00 + X12 + X20 + X21 - X23; |
490 | 65.7M | const int64_t S1 = 0x00000000 + X01 + X13 + X22 + X23 - X12 - X20; |
491 | 65.7M | const int64_t S2 = 0x00000000 + X02 + X14 + X23 - X13 - X21; |
492 | 65.7M | const int64_t S3 = 0xFFFFFFFF + X03 + X12 + X15 + X20 + X21 - X14 - X22 - X23; |
493 | 65.7M | const int64_t S4 = 0xFFFFFFFE + X04 + X12 + X13 + X16 + X20 + X21 * 2 + X22 - X15 - X23 * 2; |
494 | 65.7M | const int64_t S5 = 0xFFFFFFFF + X05 + X13 + X14 + X17 + X21 + X22 * 2 + X23 - X16; |
495 | 65.7M | const int64_t S6 = 0xFFFFFFFF + X06 + X14 + X15 + X18 + X22 + X23 * 2 - X17; |
496 | 65.7M | const int64_t S7 = 0xFFFFFFFF + X07 + X15 + X16 + X19 + X23 - X18; |
497 | 65.7M | const int64_t S8 = 0xFFFFFFFF + X08 + X16 + X17 + X20 - X19; |
498 | 65.7M | const int64_t S9 = 0xFFFFFFFF + X09 + X17 + X18 + X21 - X20; |
499 | 65.7M | const int64_t SA = 0xFFFFFFFF + X10 + X18 + X19 + X22 - X21; |
500 | 65.7M | const int64_t SB = 0xFFFFFFFF + X11 + X19 + X20 + X23 - X22; |
501 | | |
502 | 65.7M | int64_t S = 0; |
503 | | |
504 | 65.7M | uint32_t R0 = 0, R1 = 0; |
505 | | |
506 | 65.7M | S += S0; |
507 | 65.7M | R0 = static_cast<uint32_t>(S); |
508 | 65.7M | S >>= 32; |
509 | | |
510 | 65.7M | S += S1; |
511 | 65.7M | R1 = static_cast<uint32_t>(S); |
512 | 65.7M | S >>= 32; |
513 | | |
514 | 65.7M | set_words(xw, 0, R0, R1); |
515 | | |
516 | 65.7M | S += S2; |
517 | 65.7M | R0 = static_cast<uint32_t>(S); |
518 | 65.7M | S >>= 32; |
519 | | |
520 | 65.7M | S += S3; |
521 | 65.7M | R1 = static_cast<uint32_t>(S); |
522 | 65.7M | S >>= 32; |
523 | | |
524 | 65.7M | set_words(xw, 2, R0, R1); |
525 | | |
526 | 65.7M | S += S4; |
527 | 65.7M | R0 = static_cast<uint32_t>(S); |
528 | 65.7M | S >>= 32; |
529 | | |
530 | 65.7M | S += S5; |
531 | 65.7M | R1 = static_cast<uint32_t>(S); |
532 | 65.7M | S >>= 32; |
533 | | |
534 | 65.7M | set_words(xw, 4, R0, R1); |
535 | | |
536 | 65.7M | S += S6; |
537 | 65.7M | R0 = static_cast<uint32_t>(S); |
538 | 65.7M | S >>= 32; |
539 | | |
540 | 65.7M | S += S7; |
541 | 65.7M | R1 = static_cast<uint32_t>(S); |
542 | 65.7M | S >>= 32; |
543 | | |
544 | 65.7M | set_words(xw, 6, R0, R1); |
545 | | |
546 | 65.7M | S += S8; |
547 | 65.7M | R0 = static_cast<uint32_t>(S); |
548 | 65.7M | S >>= 32; |
549 | | |
550 | 65.7M | S += S9; |
551 | 65.7M | R1 = static_cast<uint32_t>(S); |
552 | 65.7M | S >>= 32; |
553 | | |
554 | 65.7M | set_words(xw, 8, R0, R1); |
555 | | |
556 | 65.7M | S += SA; |
557 | 65.7M | R0 = static_cast<uint32_t>(S); |
558 | 65.7M | S >>= 32; |
559 | | |
560 | 65.7M | S += SB; |
561 | 65.7M | R1 = static_cast<uint32_t>(S); |
562 | 65.7M | S >>= 32; |
563 | | |
564 | 65.7M | set_words(xw, 10, R0, R1); |
565 | | |
566 | | /* |
567 | | This is a table of (i*P-384) % 2**384 for i in 1...4 |
568 | | */ |
569 | 65.7M | static const word p384_mults[5][p384_limbs] = { |
570 | 65.7M | #if(BOTAN_MP_WORD_BITS == 64) |
571 | 65.7M | {0x00000000FFFFFFFF, |
572 | 65.7M | 0xFFFFFFFF00000000, |
573 | 65.7M | 0xFFFFFFFFFFFFFFFE, |
574 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
575 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
576 | 65.7M | 0xFFFFFFFFFFFFFFFF}, |
577 | 65.7M | {0x00000001FFFFFFFE, |
578 | 65.7M | 0xFFFFFFFE00000000, |
579 | 65.7M | 0xFFFFFFFFFFFFFFFD, |
580 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
581 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
582 | 65.7M | 0xFFFFFFFFFFFFFFFF}, |
583 | 65.7M | {0x00000002FFFFFFFD, |
584 | 65.7M | 0xFFFFFFFD00000000, |
585 | 65.7M | 0xFFFFFFFFFFFFFFFC, |
586 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
587 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
588 | 65.7M | 0xFFFFFFFFFFFFFFFF}, |
589 | 65.7M | {0x00000003FFFFFFFC, |
590 | 65.7M | 0xFFFFFFFC00000000, |
591 | 65.7M | 0xFFFFFFFFFFFFFFFB, |
592 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
593 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
594 | 65.7M | 0xFFFFFFFFFFFFFFFF}, |
595 | 65.7M | {0x00000004FFFFFFFB, |
596 | 65.7M | 0xFFFFFFFB00000000, |
597 | 65.7M | 0xFFFFFFFFFFFFFFFA, |
598 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
599 | 65.7M | 0xFFFFFFFFFFFFFFFF, |
600 | 65.7M | 0xFFFFFFFFFFFFFFFF}, |
601 | | |
602 | | #else |
603 | | {0xFFFFFFFF, |
604 | | 0x00000000, |
605 | | 0x00000000, |
606 | | 0xFFFFFFFF, |
607 | | 0xFFFFFFFE, |
608 | | 0xFFFFFFFF, |
609 | | 0xFFFFFFFF, |
610 | | 0xFFFFFFFF, |
611 | | 0xFFFFFFFF, |
612 | | 0xFFFFFFFF, |
613 | | 0xFFFFFFFF, |
614 | | 0xFFFFFFFF}, |
615 | | {0xFFFFFFFE, |
616 | | 0x00000001, |
617 | | 0x00000000, |
618 | | 0xFFFFFFFE, |
619 | | 0xFFFFFFFD, |
620 | | 0xFFFFFFFF, |
621 | | 0xFFFFFFFF, |
622 | | 0xFFFFFFFF, |
623 | | 0xFFFFFFFF, |
624 | | 0xFFFFFFFF, |
625 | | 0xFFFFFFFF, |
626 | | 0xFFFFFFFF}, |
627 | | {0xFFFFFFFD, |
628 | | 0x00000002, |
629 | | 0x00000000, |
630 | | 0xFFFFFFFD, |
631 | | 0xFFFFFFFC, |
632 | | 0xFFFFFFFF, |
633 | | 0xFFFFFFFF, |
634 | | 0xFFFFFFFF, |
635 | | 0xFFFFFFFF, |
636 | | 0xFFFFFFFF, |
637 | | 0xFFFFFFFF, |
638 | | 0xFFFFFFFF}, |
639 | | {0xFFFFFFFC, |
640 | | 0x00000003, |
641 | | 0x00000000, |
642 | | 0xFFFFFFFC, |
643 | | 0xFFFFFFFB, |
644 | | 0xFFFFFFFF, |
645 | | 0xFFFFFFFF, |
646 | | 0xFFFFFFFF, |
647 | | 0xFFFFFFFF, |
648 | | 0xFFFFFFFF, |
649 | | 0xFFFFFFFF, |
650 | | 0xFFFFFFFF}, |
651 | | {0xFFFFFFFB, |
652 | | 0x00000004, |
653 | | 0x00000000, |
654 | | 0xFFFFFFFB, |
655 | | 0xFFFFFFFA, |
656 | | 0xFFFFFFFF, |
657 | | 0xFFFFFFFF, |
658 | | 0xFFFFFFFF, |
659 | | 0xFFFFFFFF, |
660 | | 0xFFFFFFFF, |
661 | | 0xFFFFFFFF, |
662 | | 0xFFFFFFFF}, |
663 | | #endif |
664 | 65.7M | }; |
665 | | |
666 | 65.7M | CT::unpoison(S); |
667 | 65.7M | BOTAN_ASSERT(S >= 0 && S <= 4, "Expected overflow"); |
668 | | |
669 | 65.7M | BOTAN_ASSERT_NOMSG(x.size() >= p384_limbs + 1); |
670 | 65.7M | x.mask_bits(384); |
671 | 65.7M | word borrow = bigint_sub2(x.mutable_data(), p384_limbs + 1, p384_mults[S], p384_limbs); |
672 | 65.7M | BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); |
673 | 65.7M | bigint_cnd_add(borrow, x.mutable_data(), p384_limbs + 1, p384_mults[0], p384_limbs); |
674 | 65.7M | } |
675 | | |
676 | | } // namespace Botan |