Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

mp_monty.cpp
Go to the documentation of this file.
1 /*
2 * Montgomery Reduction
3 * (C) 1999-2011 Jack Lloyd
4 * 2006 Luca Piccarreta
5 * 2016 Matthias Gierlings
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9
10 #include <botan/bigint.h>
11 #include <botan/internal/mp_core.h>
12 #include <botan/internal/mp_madd.h>
13 #include <botan/internal/mp_asmi.h>
14 #include <botan/internal/ct_utils.h>
15 #include <botan/mem_ops.h>
16
17 namespace Botan {
18
19 /*
20 * Montgomery Reduction Algorithm
21 */
22 void bigint_monty_redc(word z[],
23 const word p[], size_t p_size,
24 word p_dash, word ws[])
25 {
26 const size_t z_size = 2*(p_size+1);
27
28 CT::poison(z, z_size);
29 CT::poison(p, p_size);
30 CT::poison(ws, 2*(p_size+1));
31
32 const size_t blocks_of_8 = p_size - (p_size % 8);
33
34 for(size_t i = 0; i != p_size; ++i)
35 {
36 word* z_i = z + i;
37
38 const word y = z_i[0] * p_dash;
39
40 /*
41 bigint_linmul3(ws, p, p_size, y);
42 bigint_add2(z_i, z_size - i, ws, p_size+1);
43 */
44
45 word carry = 0;
46
47 for(size_t j = 0; j != blocks_of_8; j += 8)
48 carry = word8_madd3(z_i + j, p + j, y, carry);
49
50 for(size_t j = blocks_of_8; j != p_size; ++j)
51 z_i[j] = word_madd3(p[j], y, z_i[j], &carry);
52
53 word z_sum = z_i[p_size] + carry;
54 carry = (z_sum < z_i[p_size]);
55 z_i[p_size] = z_sum;
56
57 for(size_t j = p_size + 1; j < z_size - i; ++j)
58 {
59 z_i[j] += carry;
60 carry = carry & !z_i[j];
61 }
62 }
63
64 /*
65 * The result might need to be reduced mod p. To avoid a timing
66 * channel, always perform the subtraction. If in the compution
67 * of x - p a borrow is required then x was already < p.
68 *
69 * x - p starts at ws[0] and is p_size+1 bytes long
70 * x starts at ws[p_size+1] and is also p_size+1 bytes log
71 * (that's the copy_mem)
72 *
73 * Select which address to copy from indexing off of the final
74 * borrow.
75 */
76
77 word borrow = 0;
78 for(size_t i = 0; i != p_size; ++i)
79 ws[i] = word_sub(z[p_size + i], p[i], &borrow);
80
81 ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
82
83 copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
84
85 CT::conditional_copy_mem(borrow, z, ws + (p_size + 1), ws, (p_size + 1));
86 clear_mem(z + p_size + 1, z_size - p_size - 1);
87
88 CT::unpoison(z, z_size);
89 CT::unpoison(p, p_size);
90 CT::unpoison(ws, 2*(p_size+1));
91
92 // This check comes after we've used it but that's ok here
93 CT::unpoison(&borrow, 1);
94 BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow");
95 }
96
97 void bigint_monty_mul(BigInt& z, const BigInt& x, const BigInt& y,
98 const word p[], size_t p_size, word p_dash,
99 word ws[])
100 {
101 bigint_mul(z, x, y, &ws[0]);
102
103 bigint_monty_redc(z.mutable_data(),
104 &p[0], p_size, p_dash,
105 &ws[0]);
106
107 }
108
109 void bigint_monty_sqr(BigInt& z, const BigInt& x, const word p[],
110 size_t p_size, word p_dash, word ws[])
111 {
112 bigint_sqr(z.mutable_data(), z.size(), &ws[0],
113 x.data(), x.size(), x.sig_words());
114
115 bigint_monty_redc(z.mutable_data(),
116 &p[0], p_size, p_dash,
117 &ws[0]);
118 }
119
120 }
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:393
Botan::BigInt
Definition: bigint.h:23
Botan::CT::conditional_copy_mem
void conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:138
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:57
Botan::word_madd3
word word_madd3(word a, word b, word c, word *d)
Definition: mp_madd.h:105
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:419
Botan::CT::poison
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
Botan::BigInt::size
size_t size() const
Definition: bigint.h:387
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
Botan::bigint_monty_sqr
void bigint_monty_sqr(BigInt &z, const BigInt &x, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:109
Botan::word8_madd3
word word8_madd3(word z[8], const word x[8], word y, word carry)
Definition: mp_asmi.h:681
Botan::bigint_sqr
void bigint_sqr(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw)
Definition: mp_karat.cpp:312
Botan::bigint_monty_mul
void bigint_monty_mul(BigInt &z, const BigInt &x, const BigInt &y, const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:97
Botan::BigInt::data
const word * data() const
Definition: bigint.h:425
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:68
Botan
Definition: alg_id.cpp:13
Botan::word_sub
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
Botan::bigint_mul
void bigint_mul(BigInt &z, const BigInt &x, const BigInt &y, word workspace[])
Definition: mp_karat.cpp:252
Botan::CT::unpoison
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57
Botan::bigint_monty_redc
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[])
Definition: mp_monty.cpp:22