Botan  2.4.0
Crypto and TLS for C++11
curve_nistp.cpp
Go to the documentation of this file.
1 /*
2 * NIST prime reductions
3 * (C) 2014,2015 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 
12 namespace Botan {
13 
14 namespace {
15 
16 void normalize(const BigInt& p, BigInt& x, secure_vector<word>& ws, size_t bound)
17  {
18  const word* prime = p.data();
19  const size_t p_words = p.sig_words();
20 
21  while(x.is_negative())
22  x += p;
23 
24  // TODO: provide a high level function for this compare-and-sub operation
25  x.grow_to(p_words + 1);
26 
27  if(ws.size() < p_words + 1)
28  ws.resize(p_words + 1);
29 
30  for(size_t i = 0; bound == 0 || i < bound; ++i)
31  {
32  const word* xd = x.data();
33  word borrow = 0;
34 
35  for(size_t j = 0; j != p_words; ++j)
36  {
37  ws[j] = word_sub(xd[j], prime[j], &borrow);
38  }
39 
40  ws[p_words] = word_sub(xd[p_words], 0, &borrow);
41 
42  if(borrow)
43  break;
44 
45  x.swap_reg(ws);
46  }
47  }
48 
49 }
50 
52  {
53  static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
54  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
55 
56  return p521;
57  }
58 
60  {
61  const size_t p_full_words = 521 / MP_WORD_BITS;
62  const size_t p_top_bits = 521 % MP_WORD_BITS;
63  const size_t p_words = p_full_words + 1;
64 
65  const size_t x_sw = x.sig_words();
66 
67  if(x_sw < p_words)
68  return; // already smaller
69 
70  if(ws.size() < p_words + 1)
71  ws.resize(p_words + 1);
72 
73  clear_mem(ws.data(), ws.size());
74  bigint_shr2(ws.data(), x.data(), x_sw, p_full_words, p_top_bits);
75 
76  x.mask_bits(521);
77 
78  word carry = bigint_add3_nc(x.mutable_data(), x.data(), p_words, ws.data(), p_words);
79  BOTAN_ASSERT_EQUAL(carry, 0, "Final final carry in P-521 reduction");
80 
81  normalize(prime_p521(), x, ws, 1);
82  }
83 
84 #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
85 
86 namespace {
87 
88 /**
89 * Treating this MPI as a sequence of 32-bit words in big-endian
90 * order, return word i (or 0 if out of range)
91 */
92 inline uint32_t get_uint32_t(const BigInt& x, size_t i)
93  {
94 #if (BOTAN_MP_WORD_BITS == 32)
95  return x.word_at(i);
96 #elif (BOTAN_MP_WORD_BITS == 64)
97  return static_cast<uint32_t>(x.word_at(i/2) >> ((i % 2)*32));
98 #else
99  #error "Not implemented"
100 #endif
101  }
102 
103 /**
104 * Treating this MPI as a sequence of 32-bit words in big-endian
105 * order, set word i to the value x
106 */
107 template<typename T>
108 inline void set_uint32_t(BigInt& x, size_t i, T v_in)
109  {
110  const uint32_t v = static_cast<uint32_t>(v_in);
111 #if (BOTAN_MP_WORD_BITS == 32)
112  x.set_word_at(i, v);
113 #elif (BOTAN_MP_WORD_BITS == 64)
114  const word shift_32 = (i % 2) * 32;
115  const word w = (x.word_at(i/2) & (static_cast<word>(0xFFFFFFFF) << (32-shift_32))) | (static_cast<word>(v) << shift_32);
116  x.set_word_at(i/2, w);
117 #else
118  #error "Not implemented"
119 #endif
120  }
121 
122 }
123 
124 const BigInt& prime_p192()
125  {
126  static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF");
127  return p192;
128  }
129 
130 void redc_p192(BigInt& x, secure_vector<word>& ws)
131  {
132  const uint32_t X6 = get_uint32_t(x, 6);
133  const uint32_t X7 = get_uint32_t(x, 7);
134  const uint32_t X8 = get_uint32_t(x, 8);
135  const uint32_t X9 = get_uint32_t(x, 9);
136  const uint32_t X10 = get_uint32_t(x, 10);
137  const uint32_t X11 = get_uint32_t(x, 11);
138 
139  x.mask_bits(192);
140 
141  uint64_t S = 0;
142 
143  S += get_uint32_t(x, 0);
144  S += X6;
145  S += X10;
146  set_uint32_t(x, 0, S);
147  S >>= 32;
148 
149  S += get_uint32_t(x, 1);
150  S += X7;
151  S += X11;
152  set_uint32_t(x, 1, S);
153  S >>= 32;
154 
155  S += get_uint32_t(x, 2);
156  S += X6;
157  S += X8;
158  S += X10;
159  set_uint32_t(x, 2, S);
160  S >>= 32;
161 
162  S += get_uint32_t(x, 3);
163  S += X7;
164  S += X9;
165  S += X11;
166  set_uint32_t(x, 3, S);
167  S >>= 32;
168 
169  S += get_uint32_t(x, 4);
170  S += X8;
171  S += X10;
172  set_uint32_t(x, 4, S);
173  S >>= 32;
174 
175  S += get_uint32_t(x, 5);
176  S += X9;
177  S += X11;
178  set_uint32_t(x, 5, S);
179  S >>= 32;
180 
181  set_uint32_t(x, 6, S);
182 
183  // No underflow possible
184 
185  normalize(prime_p192(), x, ws, 3);
186  }
187 
188 const BigInt& prime_p224()
189  {
190  static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001");
191  return p224;
192  }
193 
194 void redc_p224(BigInt& x, secure_vector<word>& ws)
195  {
196  const uint32_t X7 = get_uint32_t(x, 7);
197  const uint32_t X8 = get_uint32_t(x, 8);
198  const uint32_t X9 = get_uint32_t(x, 9);
199  const uint32_t X10 = get_uint32_t(x, 10);
200  const uint32_t X11 = get_uint32_t(x, 11);
201  const uint32_t X12 = get_uint32_t(x, 12);
202  const uint32_t X13 = get_uint32_t(x, 13);
203 
204  x.mask_bits(224);
205 
206  // One full copy of P224 is added, so the result is always positive
207 
208  int64_t S = 0;
209 
210  S += get_uint32_t(x, 0);
211  S += 1;
212  S -= X7;
213  S -= X11;
214  set_uint32_t(x, 0, S);
215  S >>= 32;
216 
217  S += get_uint32_t(x, 1);
218  S -= X8;
219  S -= X12;
220  set_uint32_t(x, 1, S);
221  S >>= 32;
222 
223  S += get_uint32_t(x, 2);
224  S -= X9;
225  S -= X13;
226  set_uint32_t(x, 2, S);
227  S >>= 32;
228 
229  S += get_uint32_t(x, 3);
230  S += 0xFFFFFFFF;
231  S += X7;
232  S += X11;
233  S -= X10;
234  set_uint32_t(x, 3, S);
235  S >>= 32;
236 
237  S += get_uint32_t(x, 4);
238  S += 0xFFFFFFFF;
239  S += X8;
240  S += X12;
241  S -= X11;
242  set_uint32_t(x, 4, S);
243  S >>= 32;
244 
245  S += get_uint32_t(x, 5);
246  S += 0xFFFFFFFF;
247  S += X9;
248  S += X13;
249  S -= X12;
250  set_uint32_t(x, 5, S);
251  S >>= 32;
252 
253  S += get_uint32_t(x, 6);
254  S += 0xFFFFFFFF;
255  S += X10;
256  S -= X13;
257  set_uint32_t(x, 6, S);
258  S >>= 32;
259  set_uint32_t(x, 7, S);
260 
261  BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
262 
263  normalize(prime_p224(), x, ws, 3);
264  }
265 
266 const BigInt& prime_p256()
267  {
268  static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF");
269  return p256;
270  }
271 
272 void redc_p256(BigInt& x, secure_vector<word>& ws)
273  {
274  const uint32_t X8 = get_uint32_t(x, 8);
275  const uint32_t X9 = get_uint32_t(x, 9);
276  const uint32_t X10 = get_uint32_t(x, 10);
277  const uint32_t X11 = get_uint32_t(x, 11);
278  const uint32_t X12 = get_uint32_t(x, 12);
279  const uint32_t X13 = get_uint32_t(x, 13);
280  const uint32_t X14 = get_uint32_t(x, 14);
281  const uint32_t X15 = get_uint32_t(x, 15);
282 
283  x.mask_bits(256);
284 
285  int64_t S = 0;
286 
287  // Adds 6 * P-256 to prevent underflow
288 
289  S = get_uint32_t(x, 0);
290  S += 0xFFFFFFFA;
291  S += X8;
292  S += X9;
293  S -= X11;
294  S -= X12;
295  S -= X13;
296  S -= X14;
297  set_uint32_t(x, 0, S);
298  S >>= 32;
299 
300  S += get_uint32_t(x, 1);
301  S += 0xFFFFFFFF;
302  S += X9;
303  S += X10;
304  S -= X12;
305  S -= X13;
306  S -= X14;
307  S -= X15;
308  set_uint32_t(x, 1, S);
309  S >>= 32;
310 
311  S += get_uint32_t(x, 2);
312  S += 0xFFFFFFFF;
313  S += X10;
314  S += X11;
315  S -= X13;
316  S -= X14;
317  S -= X15;
318  set_uint32_t(x, 2, S);
319  S >>= 32;
320 
321  S += get_uint32_t(x, 3);
322  S += 5;
323  S += X11;
324  S += X11;
325  S += X12;
326  S += X12;
327  S += X13;
328  S -= X15;
329  S -= X8;
330  S -= X9;
331  set_uint32_t(x, 3, S);
332  S >>= 32;
333 
334  S += get_uint32_t(x, 4);
335  S += X12;
336  S += X12;
337  S += X13;
338  S += X13;
339  S += X14;
340  S -= X9;
341  S -= X10;
342  set_uint32_t(x, 4, S);
343  S >>= 32;
344 
345  S += get_uint32_t(x, 5);
346  S += X13;
347  S += X13;
348  S += X14;
349  S += X14;
350  S += X15;
351  S -= X10;
352  S -= X11;
353  set_uint32_t(x, 5, S);
354  S >>= 32;
355 
356  S += get_uint32_t(x, 6);
357  S += 6;
358  S += X14;
359  S += X14;
360  S += X15;
361  S += X15;
362  S += X14;
363  S += X13;
364  S -= X8;
365  S -= X9;
366  set_uint32_t(x, 6, S);
367  S >>= 32;
368 
369  S += get_uint32_t(x, 7);
370  S += 0xFFFFFFFA;
371  S += X15;
372  S += X15;
373  S += X15;
374  S += X8;
375  S -= X10;
376  S -= X11;
377  S -= X12;
378  S -= X13;
379  set_uint32_t(x, 7, S);
380  S >>= 32;
381 
382  S += 5;
383  set_uint32_t(x, 8, S);
384 
385  BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
386 
387  #if 0
388  if(S >= 2)
389  {
390  BOTAN_ASSERT(S <= 10, "Expected overflow");
391  static const BigInt P256_mults[9] = {
392  2*CurveGFp_P256::prime(),
393  3*CurveGFp_P256::prime(),
394  4*CurveGFp_P256::prime(),
395  5*CurveGFp_P256::prime(),
396  6*CurveGFp_P256::prime(),
397  7*CurveGFp_P256::prime(),
398  8*CurveGFp_P256::prime(),
399  9*CurveGFp_P256::prime(),
400  10*CurveGFp_P256::prime()
401  };
402  x -= P256_mults[S - 2];
403  }
404  #endif
405 
406  normalize(prime_p256(), x, ws, 10);
407  }
408 
409 const BigInt& prime_p384()
410  {
411  static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF");
412  return p384;
413  }
414 
415 void redc_p384(BigInt& x, secure_vector<word>& ws)
416  {
417  const uint32_t X12 = get_uint32_t(x, 12);
418  const uint32_t X13 = get_uint32_t(x, 13);
419  const uint32_t X14 = get_uint32_t(x, 14);
420  const uint32_t X15 = get_uint32_t(x, 15);
421  const uint32_t X16 = get_uint32_t(x, 16);
422  const uint32_t X17 = get_uint32_t(x, 17);
423  const uint32_t X18 = get_uint32_t(x, 18);
424  const uint32_t X19 = get_uint32_t(x, 19);
425  const uint32_t X20 = get_uint32_t(x, 20);
426  const uint32_t X21 = get_uint32_t(x, 21);
427  const uint32_t X22 = get_uint32_t(x, 22);
428  const uint32_t X23 = get_uint32_t(x, 23);
429 
430  x.mask_bits(384);
431 
432  int64_t S = 0;
433 
434  // One copy of P-384 is added to prevent underflow
435  S = get_uint32_t(x, 0);
436  S += 0xFFFFFFFF;
437  S += X12;
438  S += X21;
439  S += X20;
440  S -= X23;
441  set_uint32_t(x, 0, S);
442  S >>= 32;
443 
444  S += get_uint32_t(x, 1);
445  S += X13;
446  S += X22;
447  S += X23;
448  S -= X12;
449  S -= X20;
450  set_uint32_t(x, 1, S);
451  S >>= 32;
452 
453  S += get_uint32_t(x, 2);
454  S += X14;
455  S += X23;
456  S -= X13;
457  S -= X21;
458  set_uint32_t(x, 2, S);
459  S >>= 32;
460 
461  S += get_uint32_t(x, 3);
462  S += 0xFFFFFFFF;
463  S += X15;
464  S += X12;
465  S += X20;
466  S += X21;
467  S -= X14;
468  S -= X22;
469  S -= X23;
470  set_uint32_t(x, 3, S);
471  S >>= 32;
472 
473  S += get_uint32_t(x, 4);
474  S += 0xFFFFFFFE;
475  S += X21;
476  S += X21;
477  S += X16;
478  S += X13;
479  S += X12;
480  S += X20;
481  S += X22;
482  S -= X15;
483  S -= X23;
484  S -= X23;
485  set_uint32_t(x, 4, S);
486  S >>= 32;
487 
488  S += get_uint32_t(x, 5);
489  S += 0xFFFFFFFF;
490  S += X22;
491  S += X22;
492  S += X17;
493  S += X14;
494  S += X13;
495  S += X21;
496  S += X23;
497  S -= X16;
498  set_uint32_t(x, 5, S);
499  S >>= 32;
500 
501  S += get_uint32_t(x, 6);
502  S += 0xFFFFFFFF;
503  S += X23;
504  S += X23;
505  S += X18;
506  S += X15;
507  S += X14;
508  S += X22;
509  S -= X17;
510  set_uint32_t(x, 6, S);
511  S >>= 32;
512 
513  S += get_uint32_t(x, 7);
514  S += 0xFFFFFFFF;
515  S += X19;
516  S += X16;
517  S += X15;
518  S += X23;
519  S -= X18;
520  set_uint32_t(x, 7, S);
521  S >>= 32;
522 
523  S += get_uint32_t(x, 8);
524  S += 0xFFFFFFFF;
525  S += X20;
526  S += X17;
527  S += X16;
528  S -= X19;
529  set_uint32_t(x, 8, S);
530  S >>= 32;
531 
532  S += get_uint32_t(x, 9);
533  S += 0xFFFFFFFF;
534  S += X21;
535  S += X18;
536  S += X17;
537  S -= X20;
538  set_uint32_t(x, 9, S);
539  S >>= 32;
540 
541  S += get_uint32_t(x, 10);
542  S += 0xFFFFFFFF;
543  S += X22;
544  S += X19;
545  S += X18;
546  S -= X21;
547  set_uint32_t(x, 10, S);
548  S >>= 32;
549 
550  S += get_uint32_t(x, 11);
551  S += 0xFFFFFFFF;
552  S += X23;
553  S += X20;
554  S += X19;
555  S -= X22;
556  set_uint32_t(x, 11, S);
557  S >>= 32;
558  BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
559  set_uint32_t(x, 12, S);
560 
561  #if 0
562  if(S >= 2)
563  {
564  BOTAN_ASSERT(S <= 4, "Expected overflow");
565 
566  static const BigInt P384_mults[3] = {
567  2*CurveGFp_P384::prime(),
568  3*CurveGFp_P384::prime(),
569  4*CurveGFp_P384::prime()
570  };
571 
572  x -= P384_mults[S - 2];
573  }
574  #endif
575 
576  normalize(prime_p384(), x, ws, 4);
577  }
578 
579 #endif
580 
581 
582 }
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:356
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:86
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:113
word * mutable_data()
Definition: bigint.h:424
word word_at(size_t n) const
Definition: bigint.h:340
void mask_bits(size_t n)
Definition: bigint.h:281
const word * data() const
Definition: bigint.h:430
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
#define BOTAN_ASSERT_EQUAL(expr1, expr2, assertion_made)
Definition: assert.h:55
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:398
void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: curve_nistp.cpp:59
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
const BigInt & prime_p521()
Definition: curve_nistp.cpp:51
void set_word_at(size_t i, word w)
Definition: bigint.h:343
fe T
Definition: ge.cpp:37
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
const size_t MP_WORD_BITS
Definition: mp_core.h:22