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