Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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