Coverage Report

Created: 2021-05-04 09:02

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