Coverage Report

Created: 2022-06-23 06:44

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