Coverage Report

Created: 2020-02-14 15:38

/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
}