Botan 3.4.0
Crypto and TLS for C&
Public Member Functions | List of all members
Botan::Montgomery_Params Class Referencefinal

#include <monty.h>

Public Member Functions

BigInt inv_mod_p (const BigInt &x) const
 
 Montgomery_Params (const BigInt &p)
 
 Montgomery_Params (const BigInt &p, const Modular_Reducer &mod_p)
 
BigInt mul (const BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
BigInt mul (const BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, const BigInt &y, secure_vector< word > &ws) const
 
void mul_by (BigInt &x, const secure_vector< word > &y, secure_vector< word > &ws) const
 
const BigInt & p () const
 
word p_dash () const
 
size_t p_words () const
 
const BigInt & R1 () const
 
const BigInt & R2 () const
 
const BigInt & R3 () const
 
BigInt redc (const BigInt &x, secure_vector< word > &ws) const
 
BigInt sqr (const BigInt &x, secure_vector< word > &ws) const
 
void square_this (BigInt &x, secure_vector< word > &ws) const
 

Detailed Description

Parameters for Montgomery Reduction

Definition at line 127 of file monty.h.

Constructor & Destructor Documentation

◆ Montgomery_Params() [1/2]

Botan::Montgomery_Params::Montgomery_Params ( const BigInt & p,
const Modular_Reducer & mod_p )

Initialize a set of Montgomery reduction parameters. These values can be shared by all values in a specific Montgomery domain.

Definition at line 16 of file monty.cpp.

16 {
17 if(p.is_even() || p < 3) {
18 throw Invalid_Argument("Montgomery_Params invalid modulus");
19 }
20
21 m_p = p;
22 m_p_words = m_p.sig_words();
23 m_p_dash = monty_inverse(m_p.word_at(0));
24
25 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
26
27 m_r1 = mod_p.reduce(r);
28 m_r2 = mod_p.square(m_r1);
29 m_r3 = mod_p.multiply(m_r1, m_r2);
30}
Botan::BigInt::sig_words
size_t sig_words() const
Definition bigint.h:584
Botan::BigInt::word_at
word word_at(size_t n) const
Definition bigint.h:518
Botan::BigInt::is_even
bool is_even() const
Definition bigint.h:410
Botan::BigInt::power_of_2
static BigInt power_of_2(size_t n)
Definition bigint.h:739
Botan::BigInt::square
BigInt & square(secure_vector< word > &ws)
Definition big_ops2.cpp:183
Botan::Montgomery_Params::p
const BigInt & p() const
Definition monty.h:141
BOTAN_MP_WORD_BITS
#define BOTAN_MP_WORD_BITS
Definition build.h:50
Botan::monty_inverse
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:821

References BOTAN_MP_WORD_BITS, Botan::BigInt::is_even(), Botan::monty_inverse(), Botan::Modular_Reducer::multiply(), p(), Botan::BigInt::power_of_2(), Botan::Modular_Reducer::reduce(), Botan::BigInt::sig_words(), Botan::Modular_Reducer::square(), and Botan::BigInt::word_at().

◆ Montgomery_Params() [2/2]

Botan::Montgomery_Params::Montgomery_Params ( const BigInt & p)

Initialize a set of Montgomery reduction parameters. These values can be shared by all values in a specific Montgomery domain.

Definition at line 32 of file monty.cpp.

32 {
33 if(p.is_even() || p < 3) {
34 throw Invalid_Argument("Montgomery_Params invalid modulus");
35 }
36
37 m_p = p;
38 m_p_words = m_p.sig_words();
39 m_p_dash = monty_inverse(m_p.word_at(0));
40
41 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
42
43 // It might be faster to use ct_modulo here vs setting up Barrett reduction?
44 Modular_Reducer mod_p(p);
45
46 m_r1 = mod_p.reduce(r);
47 m_r2 = mod_p.square(m_r1);
48 m_r3 = mod_p.multiply(m_r1, m_r2);
49}

References BOTAN_MP_WORD_BITS, Botan::BigInt::is_even(), Botan::monty_inverse(), Botan::Modular_Reducer::multiply(), p(), Botan::BigInt::power_of_2(), Botan::Modular_Reducer::reduce(), Botan::BigInt::sig_words(), Botan::Modular_Reducer::square(), and Botan::BigInt::word_at().

Member Function Documentation

◆ inv_mod_p()

BigInt Botan::Montgomery_Params::inv_mod_p ( const BigInt & x) const

Definition at line 51 of file monty.cpp.

51 {
52 // TODO use Montgomery inverse here?
53 return inverse_mod(x, p());
54}
Botan::inverse_mod
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition mod_inv.cpp:178

References Botan::inverse_mod(), and p().

◆ mul() [1/2]

BigInt Botan::Montgomery_Params::mul ( const BigInt & x,
const BigInt & y,
secure_vector< word > & ws ) const

Definition at line 71 of file monty.cpp.

71 {
72 const size_t output_size = 2 * m_p_words + 2;
73
74 if(ws.size() < output_size) {
75 ws.resize(output_size);
76 }
77
78 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
79 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
80
81 BigInt z = BigInt::with_capacity(output_size);
82 bigint_mul(z.mutable_data(),
83 z.size(),
84 x.data(),
85 x.size(),
86 std::min(m_p_words, x.size()),
87 y.data(),
88 y.size(),
89 std::min(m_p_words, y.size()),
90 ws.data(),
91 ws.size());
92
93 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
94
95 return z;
96}
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:98
Botan::BigInt::data
const word * data() const
Definition bigint.h:615
Botan::BigInt::with_capacity
static BigInt with_capacity(size_t n)
Definition bigint.cpp:58
Botan::bigint_monty_redc
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:983
Botan::bigint_mul
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:282

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), Botan::BigInt::size(), and Botan::BigInt::with_capacity().

◆ mul() [2/2]

BigInt Botan::Montgomery_Params::mul ( const BigInt & x,
const secure_vector< word > & y,
secure_vector< word > & ws ) const

Definition at line 98 of file monty.cpp.

98 {
99 const size_t output_size = 2 * m_p_words + 2;
100 if(ws.size() < output_size) {
101 ws.resize(output_size);
102 }
103 BigInt z = BigInt::with_capacity(output_size);
104
105 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
106
107 bigint_mul(z.mutable_data(),
108 z.size(),
109 x.data(),
110 x.size(),
111 std::min(m_p_words, x.size()),
112 y.data(),
113 y.size(),
114 std::min(m_p_words, y.size()),
115 ws.data(),
116 ws.size());
117
118 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
119
120 return z;
121}

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), Botan::BigInt::size(), and Botan::BigInt::with_capacity().

◆ mul_by() [1/2]

void Botan::Montgomery_Params::mul_by ( BigInt & x,
const BigInt & y,
secure_vector< word > & ws ) const

Definition at line 154 of file monty.cpp.

154 {
155 const size_t output_size = 2 * m_p_words;
156
157 if(ws.size() < 2 * output_size) {
158 ws.resize(2 * output_size);
159 }
160
161 word* z_data = &ws[0];
162 word* ws_data = &ws[output_size];
163
164 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
165
166 bigint_mul(z_data,
167 output_size,
168 x.data(),
169 x.size(),
170 std::min(m_p_words, x.size()),
171 y.data(),
172 y.size(),
173 std::min(m_p_words, y.size()),
174 ws_data,
175 output_size);
176
177 bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
178
179 if(x.size() < output_size) {
180 x.grow_to(output_size);
181 }
182 copy_mem(x.mutable_data(), z_data, output_size);
183}
Botan::copy_mem
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

◆ mul_by() [2/2]

void Botan::Montgomery_Params::mul_by ( BigInt & x,
const secure_vector< word > & y,
secure_vector< word > & ws ) const

Definition at line 123 of file monty.cpp.

123 {
124 const size_t output_size = 2 * m_p_words;
125
126 if(ws.size() < 2 * output_size) {
127 ws.resize(2 * output_size);
128 }
129
130 word* z_data = &ws[0];
131 word* ws_data = &ws[output_size];
132
133 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
134
135 bigint_mul(z_data,
136 output_size,
137 x.data(),
138 x.size(),
139 std::min(m_p_words, x.size()),
140 y.data(),
141 y.size(),
142 std::min(m_p_words, y.size()),
143 ws_data,
144 output_size);
145
146 bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
147
148 if(x.size() < output_size) {
149 x.grow_to(output_size);
150 }
151 copy_mem(x.mutable_data(), z_data, output_size);
152}

References Botan::bigint_monty_redc(), Botan::bigint_mul(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

◆ p()

const BigInt & Botan::Montgomery_Params::p ( ) const
inline

Definition at line 141 of file monty.h.

141{ return m_p; }

Referenced by inv_mod_p(), Montgomery_Params(), and Montgomery_Params().

◆ p_dash()

word Botan::Montgomery_Params::p_dash ( ) const
inline

Definition at line 149 of file monty.h.

149{ return m_p_dash; }

◆ p_words()

size_t Botan::Montgomery_Params::p_words ( ) const
inline

Definition at line 151 of file monty.h.

151{ return m_p_words; }

◆ R1()

const BigInt & Botan::Montgomery_Params::R1 ( ) const
inline

Definition at line 143 of file monty.h.

143{ return m_r1; }

◆ R2()

const BigInt & Botan::Montgomery_Params::R2 ( ) const
inline

Definition at line 145 of file monty.h.

145{ return m_r2; }

◆ R3()

const BigInt & Botan::Montgomery_Params::R3 ( ) const
inline

Definition at line 147 of file monty.h.

147{ return m_r3; }

◆ redc()

BigInt Botan::Montgomery_Params::redc ( const BigInt & x,
secure_vector< word > & ws ) const

Definition at line 56 of file monty.cpp.

56 {
57 const size_t output_size = m_p_words + 1;
58
59 if(ws.size() < output_size) {
60 ws.resize(output_size);
61 }
62
63 BigInt z = x;
64 z.grow_to(2 * m_p_words);
65
66 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
67
68 return z;
69}

References Botan::bigint_monty_redc(), Botan::BigInt::data(), Botan::BigInt::grow_to(), and Botan::BigInt::mutable_data().

◆ sqr()

BigInt Botan::Montgomery_Params::sqr ( const BigInt & x,
secure_vector< word > & ws ) const

Definition at line 185 of file monty.cpp.

185 {
186 const size_t output_size = 2 * m_p_words;
187
188 if(ws.size() < output_size) {
189 ws.resize(output_size);
190 }
191
192 BigInt z = BigInt::with_capacity(output_size);
193
194 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
195
196 bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(m_p_words, x.size()), ws.data(), ws.size());
197
198 bigint_monty_redc(z.mutable_data(), m_p.data(), m_p_words, m_p_dash, ws.data(), ws.size());
199
200 return z;
201}
Botan::bigint_sqr
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:326

References Botan::bigint_monty_redc(), Botan::bigint_sqr(), BOTAN_DEBUG_ASSERT, Botan::BigInt::data(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), Botan::BigInt::size(), and Botan::BigInt::with_capacity().

◆ square_this()

void Botan::Montgomery_Params::square_this ( BigInt & x,
secure_vector< word > & ws ) const

Definition at line 203 of file monty.cpp.

203 {
204 const size_t output_size = 2 * m_p_words;
205
206 if(ws.size() < 2 * output_size) {
207 ws.resize(2 * output_size);
208 }
209
210 word* z_data = &ws[0];
211 word* ws_data = &ws[output_size];
212
213 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
214
215 bigint_sqr(z_data, output_size, x.data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);
216
217 bigint_monty_redc(z_data, m_p.data(), m_p_words, m_p_dash, ws_data, output_size);
218
219 if(x.size() < output_size) {
220 x.grow_to(output_size);
221 }
222 copy_mem(x.mutable_data(), z_data, output_size);
223}

References Botan::bigint_monty_redc(), Botan::bigint_sqr(), BOTAN_DEBUG_ASSERT, Botan::copy_mem(), Botan::BigInt::data(), Botan::BigInt::grow_to(), Botan::BigInt::mutable_data(), Botan::BigInt::sig_words(), and Botan::BigInt::size().

The documentation for this class was generated from the following files:
Generated by doxygen 1.10.0