Botan 3.9.0
Crypto and TLS for C&
Botan::Montgomery_Int Class Referencefinal

#include <monty.h>

Public Member Functions

void _const_time_poison () const
void _const_time_unpoison () const
const Montgomery_Params_params () const
 Montgomery_Int (const Montgomery_Params &params)
 Montgomery_Int (const Montgomery_Params &params, const BigInt &v, bool redc_needed=true)
 Montgomery_Int (const Montgomery_Params &params, std::span< const word > words)
Montgomery_Int mul (const Montgomery_Int &other, secure_vector< word > &ws) const
Montgomery_Intmul_by (const Montgomery_Int &other, secure_vector< word > &ws)
Montgomery_Intmul_by (std::span< const word > other, secure_vector< word > &ws)
Montgomery_Int operator+ (const Montgomery_Int &other) const
Montgomery_Int operator- (const Montgomery_Int &other) const
const secure_vector< word > & repr () const
std::vector< uint8_t > serialize () const
Montgomery_Int square (secure_vector< word > &ws) const
Montgomery_Intsquare_this_n_times (secure_vector< word > &ws, size_t n)
BigInt value () const

Static Public Member Functions

static Montgomery_Int from_wide_int (const Montgomery_Params &params, const BigInt &x)
static Montgomery_Int one (const Montgomery_Params &params)

Detailed Description

The Montgomery representation of an integer

Definition at line 103 of file monty.h.

Constructor & Destructor Documentation

◆ Montgomery_Int() [1/3]

Botan::Montgomery_Int::Montgomery_Int ( const Montgomery_Params & params)
inlineexplicit

Create a zero-initialized Montgomery_Int

Definition at line 108 of file monty.h.

108: m_params(params) {}

Referenced by from_wide_int(), mul(), mul_by(), mul_by(), one(), operator+(), operator-(), square(), and square_this_n_times().

◆ Montgomery_Int() [2/3]

Botan::Montgomery_Int::Montgomery_Int ( const Montgomery_Params & params,
const BigInt & v,
bool redc_needed = true )

Create a Montgomery_Int from a BigInt

Definition at line 213 of file monty.cpp.

213 :
214 m_params(params), m_v(m_params.p_words()) {
215 BOTAN_ASSERT_NOMSG(v < m_params.p());
216
217 const size_t p_size = m_params.p_words();
218
219 auto v_span = v._as_span();
220
221 if(v_span.size() > p_size) {
222 // Safe to truncate the span since we already checked v < p
223 v_span = v_span.first(p_size);
224 }
225
226 BOTAN_ASSERT_NOMSG(m_v.size() >= v_span.size());
227
228 copy_mem(std::span{m_v}.first(v_span.size()), v_span);
229
230 if(redc_needed) {
232 this->mul_by(m_params.R2()._as_span().first(p_size), ws);
233 }
234}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:312
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:145
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69

References Botan::BigInt::_as_span(), BOTAN_ASSERT_NOMSG, Botan::copy_mem(), and mul_by().

◆ Montgomery_Int() [3/3]

Botan::Montgomery_Int::Montgomery_Int ( const Montgomery_Params & params,
std::span< const word > words )

Create a Montgomery_Int

The span must be exactly p_words long and encoding a value less than p already in Montgomery form

Definition at line 236 of file monty.cpp.

236 :
237 m_params(params), m_v(words.begin(), words.end()) {
238 BOTAN_ARG_CHECK(m_v.size() == m_params.p_words(), "Invalid input span");
239}
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33

References BOTAN_ARG_CHECK.

Member Function Documentation

◆ _const_time_poison()

void Botan::Montgomery_Int::_const_time_poison ( ) const
inline

Definition at line 159 of file monty.h.

159{ CT::poison(m_v); }
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:54

References Botan::CT::poison().

◆ _const_time_unpoison()

void Botan::Montgomery_Int::_const_time_unpoison ( ) const
inline

Definition at line 161 of file monty.h.

161{ CT::unpoison(m_v); }
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:65

References Botan::CT::unpoison().

◆ _params()

const Montgomery_Params & Botan::Montgomery_Int::_params ( ) const
inline

Definition at line 163 of file monty.h.

163{ return m_params; }

◆ from_wide_int()

Montgomery_Int Botan::Montgomery_Int::from_wide_int ( const Montgomery_Params & params,
const BigInt & x )
static

Wide reduction - input can be at most 2*bytes long

Definition at line 207 of file monty.cpp.

207 {
209 auto redc_x = params.mul(params.redc(x, ws), params.R3(), ws);
210 return Montgomery_Int(params, redc_x, false);
211}
Montgomery_Int(const Montgomery_Params &params)
Definition monty.h:108

References Montgomery_Int(), Botan::Montgomery_Params::mul(), Botan::Montgomery_Params::R3(), and Botan::Montgomery_Params::redc().

◆ mul()

Montgomery_Int Botan::Montgomery_Int::mul ( const Montgomery_Int & other,
secure_vector< word > & ws ) const

Definition at line 292 of file monty.cpp.

292 {
293 BOTAN_STATE_CHECK(other.m_params == m_params);
294
295 const size_t p_size = m_params.p_words();
296 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
297
298 if(ws.size() < 2 * p_size) {
299 ws.resize(2 * p_size);
300 }
301
302 secure_vector<word> z(2 * p_size);
303
304 bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.m_v.data(), p_size, p_size, ws.data(), ws.size());
305
306 bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
307 z.resize(p_size); // truncate off high zero words
308
309 return Montgomery_Int(m_params, std::move(z));
310}
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:49
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:283
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:829

References Botan::bigint_monty_redc_inplace(), Botan::bigint_mul(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, and Montgomery_Int().

Referenced by Botan::monty_multi_exp().

◆ mul_by() [1/2]

Montgomery_Int & Botan::Montgomery_Int::mul_by ( const Montgomery_Int & other,
secure_vector< word > & ws )

Definition at line 312 of file monty.cpp.

312 {
313 BOTAN_STATE_CHECK(other.m_params == m_params);
314 return this->mul_by(std::span{other.m_v}, ws);
315}

References BOTAN_STATE_CHECK, Montgomery_Int(), and mul_by().

Referenced by Montgomery_Int(), Botan::monty_multi_exp(), and mul_by().

◆ mul_by() [2/2]

Montgomery_Int & Botan::Montgomery_Int::mul_by ( std::span< const word > other,
secure_vector< word > & ws )

Definition at line 317 of file monty.cpp.

317 {
318 const size_t p_size = m_params.p_words();
319 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.size() == p_size);
320
321 if(ws.size() < 2 * p_size) {
322 ws.resize(2 * p_size);
323 }
324
325 auto do_mul_by = [&](std::span<word> z) {
326 bigint_mul(z.data(), z.size(), m_v.data(), p_size, p_size, other.data(), p_size, p_size, ws.data(), ws.size());
327
328 bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
329
330 copy_mem(m_v, z.first(p_size));
331 };
332
333 if(p_size <= MontgomeryUseStackLimit) {
334 std::array<word, 2 * MontgomeryUseStackLimit> z{};
335 do_mul_by(z);
336 } else {
337 secure_vector<word> z(2 * p_size);
338 do_mul_by(z);
339 }
340
341 return (*this);
342}

References Botan::bigint_monty_redc_inplace(), Botan::bigint_mul(), BOTAN_ASSERT_NOMSG, Botan::copy_mem(), and Montgomery_Int().

◆ one()

Montgomery_Int Botan::Montgomery_Int::one ( const Montgomery_Params & params)
static

Return the value 1 in Montgomery form

Definition at line 203 of file monty.cpp.

203 {
204 return Montgomery_Int(params, params.R1(), false);
205}

References Montgomery_Int(), and Botan::Montgomery_Params::R1().

Referenced by Botan::monty_multi_exp().

◆ operator+()

Montgomery_Int Botan::Montgomery_Int::operator+ ( const Montgomery_Int & other) const

Definition at line 257 of file monty.cpp.

257 {
258 BOTAN_STATE_CHECK(other.m_params == m_params);
259
260 const size_t p_size = m_params.p_words();
261 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
262
263 secure_vector<word> z(2 * p_size);
264
265 word* r = std::span{z}.first(p_size).data();
266 word* t = std::span{z}.last(p_size).data();
267
268 // t = this + other
269 const word carry = bigint_add3(t, m_v.data(), p_size, other.m_v.data(), p_size);
270
271 // Conditionally subtract r = t - p
272 bigint_monty_maybe_sub(p_size, r, carry, t, m_params.p()._data());
273
274 z.resize(p_size); // truncate leaving only r
275 return Montgomery_Int(m_params, std::move(z));
276}
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:122
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:227
void carry(int64_t &h0, int64_t &h1)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119

References Botan::bigint_add3(), Botan::bigint_monty_maybe_sub(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, Botan::carry(), and Montgomery_Int().

◆ operator-()

Montgomery_Int Botan::Montgomery_Int::operator- ( const Montgomery_Int & other) const

Definition at line 278 of file monty.cpp.

278 {
279 BOTAN_STATE_CHECK(other.m_params == m_params);
280
281 const size_t p_size = m_params.p_words();
282 BOTAN_ASSERT_NOMSG(m_v.size() == p_size && other.m_v.size() == p_size);
283
284 secure_vector<word> t(p_size);
285 const word borrow = bigint_sub3(t.data(), m_v.data(), p_size, other.m_v.data(), p_size);
286
287 bigint_cnd_add(borrow, t.data(), m_params.p()._data(), p_size);
288
289 return Montgomery_Int(m_params, std::move(t));
290}
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:194
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:47

References Botan::bigint_cnd_add(), Botan::bigint_sub3(), BOTAN_ASSERT_NOMSG, BOTAN_STATE_CHECK, and Montgomery_Int().

◆ repr()

const secure_vector< word > & Botan::Montgomery_Int::repr ( ) const
inline

Return the Montgomery representation

Definition at line 143 of file monty.h.

143{ return m_v; }

◆ serialize()

std::vector< uint8_t > Botan::Montgomery_Int::serialize ( ) const

Definition at line 241 of file monty.cpp.

241 {
242 return value().serialize();
243}
T serialize(size_t len) const
Definition bigint.h:711
BigInt value() const
Definition monty.cpp:245

References Botan::BigInt::serialize(), and value().

◆ square()

Montgomery_Int Botan::Montgomery_Int::square ( secure_vector< word > & ws) const

Definition at line 373 of file monty.cpp.

373 {
374 auto z = (*this);
375 z.square_this_n_times(ws, 1);
376 return z;
377}

References Montgomery_Int(), and square_this_n_times().

Referenced by Botan::monty_multi_exp().

◆ square_this_n_times()

Montgomery_Int & Botan::Montgomery_Int::square_this_n_times ( secure_vector< word > & ws,
size_t n )

Definition at line 344 of file monty.cpp.

344 {
345 const size_t p_size = m_params.p_words();
346 BOTAN_ASSERT_NOMSG(m_v.size() == p_size);
347
348 if(ws.size() < 2 * p_size) {
349 ws.resize(2 * p_size);
350 }
351
352 auto do_sqr_n = [&](std::span<word> z) {
353 for(size_t i = 0; i != n; ++i) {
354 bigint_sqr(z.data(), 2 * p_size, m_v.data(), p_size, p_size, ws.data(), ws.size());
355
356 bigint_monty_redc_inplace(z.data(), m_params.p()._data(), p_size, m_params.p_dash(), ws.data(), ws.size());
357
358 copy_mem(m_v, std::span{z}.first(p_size));
359 }
360 };
361
362 if(p_size <= MontgomeryUseStackLimit) {
363 std::array<word, 2 * MontgomeryUseStackLimit> z{};
364 do_sqr_n(z);
365 } else {
366 secure_vector<word> z(2 * p_size);
367 do_sqr_n(z);
368 }
369
370 return (*this);
371}
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:327

References Botan::bigint_monty_redc_inplace(), Botan::bigint_sqr(), BOTAN_ASSERT_NOMSG, Botan::copy_mem(), and Montgomery_Int().

Referenced by Botan::monty_multi_exp(), and square().

◆ value()

BigInt Botan::Montgomery_Int::value ( ) const

Return the value to normal mod-p space

Definition at line 245 of file monty.cpp.

245 {
246 secure_vector<word> ws(m_params.p_words());
247
248 secure_vector<word> z = m_v;
249 z.resize(2 * m_params.p_words()); // zero extend
250
252 z.data(), m_params.p()._data(), m_params.p_words(), m_params.p_dash(), ws.data(), ws.size());
253
254 return BigInt::_from_words(z);
255}
static BigInt _from_words(secure_vector< word > &words)
Definition bigint.h:955

References Botan::BigInt::_from_words(), and Botan::bigint_monty_redc_inplace().

Referenced by Botan::DL_Group::multi_exponentiate(), Botan::passes_miller_rabin_test(), Botan::power_mod(), serialize(), and Botan::sqrt_modulo_prime().


The documentation for this class was generated from the following files: