Botan 3.14.1
Crypto and TLS for C&
monty.h
Go to the documentation of this file.
1/*
2* (C) 2018,2024 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_MONTY_INT_H_
8#define BOTAN_MONTY_INT_H_
9
10#include <botan/bigint.h>
11
12#include <botan/internal/ct_utils.h>
13#include <memory>
14#include <span>
15
16namespace Botan {
17
19
20/**
21* Parameters for Montgomery Reduction
22*/
24 public:
25 /**
26 * Initialize a set of Montgomery reduction parameters. These values
27 * can be shared by all values in a specific Montgomery domain.
28 */
29 Montgomery_Params(const BigInt& p, const Barrett_Reduction& mod_p);
30
31 /**
32 * Initialize a set of Montgomery reduction parameters. These values
33 * can be shared by all values in a specific Montgomery domain.
34 */
35 explicit Montgomery_Params(const BigInt& p);
36
37 bool operator==(const Montgomery_Params& other) const;
38
39 bool operator!=(const Montgomery_Params& other) const { return !((*this) == other); }
40
41 const BigInt& p() const { return m_data->p(); }
42
43 const BigInt& R1() const { return m_data->r1(); }
44
45 const BigInt& R2() const { return m_data->r2(); }
46
47 const BigInt& R3() const { return m_data->r3(); }
48
49 word p_dash() const { return m_data->p_dash(); }
50
51 /**
52 * Return floor(2^(bits(p) - 1 + WB) / p) where WB is the word size in bits
53 */
54 word p_top_mu() const { return m_data->p_top_mu(); }
55
56 size_t p_bits() const { return m_data->p_bits(); }
57
58 size_t p_words() const { return m_data->p_size(); }
59
60 void _const_time_poison() const { m_data->_const_time_poison(); }
61
62 void _const_time_unpoison() const { m_data->_const_time_unpoison(); }
63
64 BigInt redc(const BigInt& x, secure_vector<word>& ws) const;
65
66 void mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
67
68 void mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const;
69
70 BigInt mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
71
72 void mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
73
74 BigInt sqr(const BigInt& x, secure_vector<word>& ws) const;
75
76 void sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const;
77
78 void sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const;
79
80 private:
81 BigInt sqr(std::span<const word> x, secure_vector<word>& ws) const;
82
83 class Data final {
84 public:
85 Data(const BigInt& p, const Barrett_Reduction& mod_p);
86
87 const BigInt& p() const { return m_p; }
88
89 const BigInt& r1() const { return m_r1; }
90
91 const BigInt& r2() const { return m_r2; }
92
93 const BigInt& r3() const { return m_r3; }
94
95 word p_dash() const { return m_p_dash; }
96
97 word p_top_mu() const { return m_p_top_mu; }
98
99 size_t p_bits() const { return m_p_bits; }
100
101 size_t p_size() const { return m_p_words; }
102
103 void _const_time_poison() const { CT::poison_all(m_p, m_r1, m_r2, m_r3, m_p_dash, m_p_top_mu); }
104
105 void _const_time_unpoison() const { CT::unpoison_all(m_p, m_r1, m_r2, m_r3, m_p_dash, m_p_top_mu); }
106
107 private:
108 BigInt m_p;
109 BigInt m_r1;
110 BigInt m_r2;
111 BigInt m_r3;
112 word m_p_dash;
113 word m_p_top_mu;
114 size_t m_p_bits;
115 size_t m_p_words;
116 };
117
118 std::shared_ptr<const Data> m_data;
119};
120
121/**
122* The Montgomery representation of an integer
123*/
125 public:
126 /**
127 * Create a zero-initialized Montgomery_Int
128 */
129 explicit Montgomery_Int(const Montgomery_Params& params);
130
131 /**
132 * Create a Montgomery_Int from a BigInt
133 */
134 Montgomery_Int(const Montgomery_Params& params, const BigInt& v, bool redc_needed = true);
135
136 /**
137 * Create a Montgomery_Int
138 *
139 * The span must be exactly p_words long and encoding a value less than p already
140 * in Montgomery form
141 */
142 Montgomery_Int(const Montgomery_Params& params, std::span<const word> words);
143
144 /**
145 * Return the value 1 in Montgomery form
146 */
147 static Montgomery_Int one(const Montgomery_Params& params);
148
149 /**
150 * Wide reduction - input can be at most 2*bytes long
151 */
152 static Montgomery_Int from_wide_int(const Montgomery_Params& params, const BigInt& x);
153
154 std::vector<uint8_t> serialize() const;
155
156 /**
157 * Return the value to normal mod-p space
158 */
159 BigInt value() const;
160
161 /**
162 * Return the Montgomery representation
163 */
164 const secure_vector<word>& repr() const { return m_v; }
165
166 Montgomery_Int operator+(const Montgomery_Int& other) const;
167
168 Montgomery_Int operator-(const Montgomery_Int& other) const;
169
170 Montgomery_Int mul(const Montgomery_Int& other, secure_vector<word>& ws) const;
171
172 Montgomery_Int& mul_by(const Montgomery_Int& other, secure_vector<word>& ws);
173
174 Montgomery_Int& mul_by(std::span<const word> other, secure_vector<word>& ws);
175
177
178 Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
179
181
183
184 /**
185 * Multiply by an integer d (which is not in Montgomery form)
186 *
187 * Requires 0 <= d < 2^(WB-2), where WB is the word size in bits (so
188 * d < 2^62 with 64-bit words, or d < 2^30 with 32-bit words). Larger
189 * values throw Invalid_Argument.
190 *
191 * This is constant time with respect to the values of this, d, and p
192 */
193 Montgomery_Int& mul_by_word(word d);
194
195 /**
196 * Divide by 2 modulo p
197 */
198 Montgomery_Int& div2();
199
200 /**
201 * If predicate is true assign other to this, in constant time
202 */
203 void ct_cond_assign(bool predicate, const Montgomery_Int& other);
204
205 /**
206 * If predicate is true negate this modulo p, in constant time
207 */
208 void ct_cond_negate(bool predicate);
209
210 bool is_zero() const;
211
212 void _const_time_poison() const { CT::poison(m_v); }
213
214 void _const_time_unpoison() const { CT::unpoison(m_v); }
215
216 const Montgomery_Params& _params() const { return m_params; }
217
218 private:
220
221 // this = this + other mod p; other may alias this
222 void add_mod_p(std::span<const word> other);
223
224 Montgomery_Params m_params;
226};
227
228} // namespace Botan
229
230#endif
#define BOTAN_TEST_API
Definition api.h:41
void _const_time_unpoison() const
Definition monty.h:214
static Montgomery_Int from_wide_int(const Montgomery_Params &params, const BigInt &x)
Definition monty.cpp:241
const secure_vector< word > & repr() const
Definition monty.h:164
static Montgomery_Int one(const Montgomery_Params &params)
Definition monty.cpp:237
Montgomery_Int(const Montgomery_Params &params)
Definition monty.cpp:230
BigInt value() const
Definition monty.cpp:279
void _const_time_poison() const
Definition monty.h:212
const Montgomery_Params & _params() const
Definition monty.h:216
std::vector< uint8_t > serialize() const
Definition monty.cpp:275
word p_top_mu() const
Definition monty.h:54
void _const_time_unpoison() const
Definition monty.h:62
size_t p_bits() const
Definition monty.h:56
bool operator!=(const Montgomery_Params &other) const
Definition monty.h:39
size_t p_words() const
Definition monty.h:58
bool operator==(const Montgomery_Params &other) const
Definition monty.cpp:73
Montgomery_Params(const BigInt &p, const Barrett_Reduction &mod_p)
Definition monty.cpp:67
const BigInt & R3() const
Definition monty.h:47
const BigInt & R2() const
Definition monty.h:45
const BigInt & R1() const
Definition monty.h:43
word p_dash() const
Definition monty.h:49
void _const_time_poison() const
Definition monty.h:60
const BigInt & p() const
Definition monty.h:41
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
BigInt square(const BigInt &x)
Definition numthry.cpp:184
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:1216
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition secmem.h:168
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
constexpr auto operator-=(Strong< T1, Tags... > &a, T2 b)