Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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
51 const BigInt& prime_p521()
52 {
53 static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
54 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
55
56 return p521;
57 }
58
59 void redc_p521(BigInt& x, secure_vector<word>& ws)
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 }
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:393
Botan::BigInt
Definition: bigint.h:23
Botan::bigint_shr2
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
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:57
Botan::bigint_add3_nc
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
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:419
Botan::BigInt::mask_bits
void mask_bits(size_t n)
Definition: bigint.h:276
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
BOTAN_ASSERT_EQUAL
#define BOTAN_ASSERT_EQUAL(expr1, expr2, assertion_made)
Definition: assert.h:53
Botan::redc_p521
void redc_p521(BigInt &x, secure_vector< word > &ws)
Definition: curve_nistp.cpp:59
Botan::BigInt::data
const word * data() const
Definition: bigint.h:425
Botan
Definition: alg_id.cpp:13
Botan::prime_p521
const BigInt & prime_p521()
Definition: curve_nistp.cpp:51
Botan::word_sub
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
Botan::MP_WORD_BITS
const size_t MP_WORD_BITS
Definition: mp_core.h:21