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