Botan 2.19.1
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 BigIntp () const
 
word p_dash () const
 
size_t p_words () const
 
const BigIntR1 () const
 
const BigIntR2 () const
 
const BigIntR3 () 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 130 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 13 of file monty.cpp.

15 {
16 if(p.is_even() || p < 3)
17 throw Invalid_Argument("Montgomery_Params invalid modulus");
18
19 m_p = p;
20 m_p_words = m_p.sig_words();
21 m_p_dash = monty_inverse(m_p.word_at(0));
22
23 const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
24
25 m_r1 = mod_p.reduce(r);
26 m_r2 = mod_p.square(m_r1);
27 m_r3 = mod_p.multiply(m_r1, m_r2);
28 }
size_t sig_words() const
Definition: bigint.h:586
word word_at(size_t n) const
Definition: bigint.h:508
bool is_even() const
Definition: bigint.h:403
static BigInt power_of_2(size_t n)
Definition: bigint.h:758
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:197
const BigInt & p() const
Definition: monty.h:145
word monty_inverse(word a)
Definition: mod_inv.cpp:327

References 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 30 of file monty.cpp.

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

References Botan::BigInt::is_even(), Botan::BigInt::is_negative(), 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 50 of file monty.cpp.

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

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 73 of file monty.cpp.

75 {
76 const size_t output_size = 2*m_p_words + 2;
77
78 if(ws.size() < output_size)
79 ws.resize(output_size);
80
81 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
82 BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
83
84 BigInt z(BigInt::Positive, output_size);
85 bigint_mul(z.mutable_data(), z.size(),
86 x.data(), x.size(), std::min(m_p_words, x.size()),
87 y.data(), y.size(), std::min(m_p_words, y.size()),
88 ws.data(), ws.size());
89
90 bigint_monty_redc(z.mutable_data(),
91 m_p.data(), m_p_words, m_p_dash,
92 ws.data(), ws.size());
93
94 return z;
95 }
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
const word * data() const
Definition: bigint.h:620
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:298
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109

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

◆ mul() [2/2]

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

Definition at line 97 of file monty.cpp.

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

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

◆ mul_by() [1/2]

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

Definition at line 148 of file monty.cpp.

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

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 120 of file monty.cpp.

123 {
124 const size_t output_size = 2*m_p_words + 2;
125
126 if(ws.size() < 2*output_size)
127 ws.resize(2*output_size);
128
129 word* z_data = &ws[0];
130 word* ws_data = &ws[output_size];
131
132 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
133
134 bigint_mul(z_data, output_size,
135 x.data(), x.size(), std::min(m_p_words, x.size()),
136 y.data(), y.size(), std::min(m_p_words, y.size()),
137 ws_data, output_size);
138
139 bigint_monty_redc(z_data,
140 m_p.data(), m_p_words, m_p_dash,
141 ws_data, output_size);
142
143 if(x.size() < output_size)
144 x.grow_to(output_size);
145 copy_mem(x.mutable_data(), z_data, output_size);
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().

◆ p()

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

Definition at line 145 of file monty.h.

145{ return m_p; }

Referenced by inv_mod_p(), and Montgomery_Params().

◆ p_dash()

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

Definition at line 150 of file monty.h.

150{ return m_p_dash; }

◆ p_words()

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

Definition at line 152 of file monty.h.

152{ return m_p_words; }

◆ R1()

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

Definition at line 146 of file monty.h.

146{ return m_r1; }

◆ R2()

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

Definition at line 147 of file monty.h.

147{ return m_r2; }

◆ R3()

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

Definition at line 148 of file monty.h.

148{ 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.

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

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 176 of file monty.cpp.

177 {
178 const size_t output_size = 2*m_p_words + 2;
179
180 if(ws.size() < output_size)
181 ws.resize(output_size);
182
183 BigInt z(BigInt::Positive, output_size);
184
185 BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
186
187 bigint_sqr(z.mutable_data(), z.size(),
188 x.data(), x.size(), std::min(m_p_words, x.size()),
189 ws.data(), ws.size());
190
191 bigint_monty_redc(z.mutable_data(),
192 m_p.data(), m_p_words, m_p_dash,
193 ws.data(), ws.size());
194
195 return z;
196 }
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:357

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

◆ square_this()

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

Definition at line 198 of file monty.cpp.

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

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: