Coverage Report

Created: 2020-11-21 08:34

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