/src/botan/src/lib/math/numbertheory/monty.cpp

Source
/*
* (C) 2018,2024 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/monty.h>

#include <botan/numthry.h>
#include <botan/internal/barrett.h>
#include <botan/internal/mp_core.h>

#include <utility>

namespace Botan {

Montgomery_Params::Montgomery_Params(const BigInt& p, const Barrett_Reduction& mod_p) {
   if(p.is_even() || p < 3) {
      throw Invalid_Argument("Montgomery_Params invalid modulus");
   }

   m_p = p;
   m_p_words = m_p.sig_words();
   m_p_dash = monty_inverse(m_p.word_at(0));

   const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);

   m_r1 = mod_p.reduce(r);
   m_r2 = mod_p.square(m_r1);
   m_r3 = mod_p.multiply(m_r1, m_r2);
}

Montgomery_Params::Montgomery_Params(const BigInt& p) {
   if(p.is_even() || p < 3) {
      throw Invalid_Argument("Montgomery_Params invalid modulus");
   }

   m_p = p;
   m_p_words = m_p.sig_words();
   m_p_dash = monty_inverse(m_p.word_at(0));

   const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);

   auto mod_p = Barrett_Reduction::for_secret_modulus(p);

   m_r1 = mod_p.reduce(r);
   m_r2 = mod_p.square(m_r1);
   m_r3 = mod_p.multiply(m_r1, m_r2);
}

BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const {
   const size_t output_size = m_p_words + 1;

   if(ws.size() < output_size) {
      ws.resize(output_size);
   }

   BigInt z = x;
   z.grow_to(2 * m_p_words);

   bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());

   return z;
}

BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   BigInt z = BigInt::with_capacity(2 * m_p_words);
   this->mul(z, x, y, ws);
   return z;
}

void Montgomery_Params::mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

   if(ws.size() < output_size) {
      ws.resize(output_size);
   }

   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
   BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);

   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_mul(z.mutable_data(),
              z.size(),
              x._data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y._data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws.data(),
              ws.size());

   bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

BigInt Montgomery_Params::mul(const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
   BigInt z = BigInt::with_capacity(2 * m_p_words);
   this->mul(z, x, y, ws);
   return z;
}

void Montgomery_Params::mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;
   if(ws.size() < output_size) {
      ws.resize(output_size);
   }
   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);

   bigint_mul(z.mutable_data(),
              z.size(),
              x._data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws.data(),
              ws.size());

   bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

void Montgomery_Params::mul_by(BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

   if(ws.size() < 2 * output_size) {
      ws.resize(2 * output_size);
   }

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);

   bigint_mul(z_data,
              output_size,
              x._data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y.data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws_data,
              output_size);

   bigint_monty_redc_inplace(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

void Montgomery_Params::mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

   if(ws.size() < 2 * output_size) {
      ws.resize(2 * output_size);
   }

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);

   bigint_mul(z_data,
              output_size,
              x._data(),
              x.size(),
              std::min(m_p_words, x.size()),
              y._data(),
              y.size(),
              std::min(m_p_words, y.size()),
              ws_data,
              output_size);

   bigint_monty_redc_inplace(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const {
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
   return this->sqr(std::span{x._data(), x.size()}, ws);
}

BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
   BigInt z = BigInt::with_capacity(2 * m_p_words);
   this->sqr(z, x, ws);
   return z;
}

void Montgomery_Params::sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const {
   this->sqr(z, std::span{x._data(), x.size()}, ws);
}

void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

   if(ws.size() < output_size) {
      ws.resize(output_size);
   }

   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

   bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(m_p_words, x.size()), ws.data(), ws.size());

   bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

void Montgomery_Params::square_this(BigInt& x, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

   if(ws.size() < 2 * output_size) {
      ws.resize(2 * output_size);
   }

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);

   bigint_sqr(z_data, output_size, x._data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);

   bigint_monty_redc_inplace(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

Montgomery_Int Montgomery_Int::one(const std::shared_ptr<const Montgomery_Params>& params) {
   return Montgomery_Int(params, params->R1(), false);
}

Montgomery_Int Montgomery_Int::from_wide_int(const std::shared_ptr<const Montgomery_Params>& params, const BigInt& x) {
   //BOTAN_ARG_CHECK(x < params->p() * params->p(), "Input too large");

   secure_vector<word> ws;
   auto redc_x = params->mul(params->redc(x, ws), params->R3(), ws);
   return Montgomery_Int(params, redc_x, false);
}

Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
                               const BigInt& v,
                               bool redc_needed) :
      m_params(params) {
   if(redc_needed == false) {
      m_v = v;
   } else {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(v, m_params->R2(), ws);
   }
}

Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
                               const uint8_t bits[],
                               size_t len,
                               bool redc_needed) :
      m_params(params), m_v(bits, len) {
   if(redc_needed) {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(m_v, m_params->R2(), ws);
   }
}

Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
                               const word words[],
                               size_t len,
                               bool redc_needed) :
      m_params(std::move(params)) {
   m_v.set_words(words, len);

   if(redc_needed) {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(m_v, m_params->R2(), ws);
   }
}

void Montgomery_Int::fix_size() {
   const size_t p_words = m_params->p_words();
   BOTAN_DEBUG_ASSERT(m_v.sig_words() <= p_words);
   m_v.grow_to(p_words);
}

bool Montgomery_Int::operator==(const Montgomery_Int& other) const {
   return m_v == other.m_v && m_params->p() == other.m_params->p();
}

std::vector<uint8_t> Montgomery_Int::serialize() const {
   return value().serialize();
}

size_t Montgomery_Int::size() const {
   return m_params->p().bytes();
}

bool Montgomery_Int::is_one() const {
   return m_v == m_params->R1();
}

bool Montgomery_Int::is_zero() const {
   return m_v.is_zero();
}

BigInt Montgomery_Int::value() const {
   secure_vector<word> ws;
   return m_params->redc(m_v, ws);
}

Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   secure_vector<word> ws;
   BigInt z = m_v;
   z.mod_add(other.m_v, m_params->p(), ws);
   return Montgomery_Int(m_params, z, false);
}

Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   secure_vector<word> ws;
   BigInt z = m_v;
   z.mod_sub(other.m_v, m_params->p(), ws);
   return Montgomery_Int(m_params, z, false);
}

Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   secure_vector<word> ws;
   return this->add(other, ws);
}

Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   m_v.mod_add(other.m_v, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   secure_vector<word> ws;
   return this->sub(other, ws);
}

Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   m_v.mod_sub(other.m_v, m_params->p(), ws);
   return (*this);
}

Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   secure_vector<word> ws;
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
}

Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
}

Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   m_params->mul_by(m_v, other.m_v, ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, secure_vector<word>& ws) {
   m_params->mul_by(m_v, other, ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other) {
   BOTAN_STATE_CHECK(other.m_params == m_params);
   secure_vector<word> ws;
   return mul_by(other, ws);
}

Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other) {
   secure_vector<word> ws;
   return mul_by(other, ws);
}

Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
   for(size_t i = 0; i != n; ++i) {
      m_params->square_this(m_v, ws);
   }
   return (*this);
}

Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws) {
   m_params->square_this(m_v, ws);
   return (*this);
}

Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
}

Montgomery_Int Montgomery_Int::cube(secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
}

Montgomery_Int Montgomery_Int::additive_inverse() const {
   return Montgomery_Int(m_params, m_params->p()) - (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws) {
   m_v.mod_mul(2, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws) {
   m_v.mod_mul(3, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws) {
   m_v.mod_mul(4, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws) {
   m_v.mod_mul(8, m_params->p(), ws);
   return (*this);
}

}  // namespace Botan

Coverage Report

Created: 2026-10-13 06:31

Line	Count	Source
1		/*
2		* (C) 2018,2024 Jack Lloyd
3		*
4		* Botan is released under the Simplified BSD License (see license.txt)
5		*/
6
7		#include <botan/internal/monty.h>
8
9		#include <botan/numthry.h>
10		#include <botan/internal/barrett.h>
11		#include <botan/internal/mp_core.h>
12
13		#include <utility>
14
15		namespace Botan {
16
17	672	Montgomery_Params::Montgomery_Params(const BigInt& p, const Barrett_Reduction& mod_p) {
18	672	if(p.is_even() \|\| p < 3) {
19	0	throw Invalid_Argument("Montgomery_Params invalid modulus");
20	0	}
21
22	672	m_p = p;
23	672	m_p_words = m_p.sig_words();
24	672	m_p_dash = monty_inverse(m_p.word_at(0));
25
26	672	const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);
27
28	672	m_r1 = mod_p.reduce(r);
29	672	m_r2 = mod_p.square(m_r1);
30	672	m_r3 = mod_p.multiply(m_r1, m_r2);
31	672	}
32
33	4	Montgomery_Params::Montgomery_Params(const BigInt& p) {
34	4	if(p.is_even() \|\| p < 3) {
35	0	throw Invalid_Argument("Montgomery_Params invalid modulus");
36	0	}
37
38	4	m_p = p;
39	4	m_p_words = m_p.sig_words();
40	4	m_p_dash = monty_inverse(m_p.word_at(0));
41
42	4	const BigInt r = BigInt::power_of_2(m_p_words * WordInfo<word>::bits);
43
44	4	auto mod_p = Barrett_Reduction::for_secret_modulus(p);
45
46	4	m_r1 = mod_p.reduce(r);
47	4	m_r2 = mod_p.square(m_r1);
48	4	m_r3 = mod_p.multiply(m_r1, m_r2);
49	4	}
50
51	662	BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const {
52	662	const size_t output_size = m_p_words + 1;
53
54	662	if(ws.size() < output_size) {
55	662	ws.resize(output_size);
56	662	}
57
58	662	BigInt z = x;
59	662	z.grow_to(2 * m_p_words);
60
61	662	bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
62
63	662	return z;
64	662	}
65
66	17.2k	BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
67	17.2k	BigInt z = BigInt::with_capacity(2 * m_p_words);
68	17.2k	this->mul(z, x, y, ws);
69	17.2k	return z;
70	17.2k	}
71
72	39.8k	void Montgomery_Params::mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
73	39.8k	const size_t output_size = 2 * m_p_words;
74
75	39.8k	if(ws.size() < output_size) {
76	9.94k	ws.resize(output_size);
77	9.94k	}
78
79	39.8k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
80	39.8k	BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
81
82	39.8k	if(z.size() < output_size) {
83	2.44k	z.grow_to(output_size);
84	2.44k	}
85
86	39.8k	bigint_mul(z.mutable_data(),
87	39.8k	z.size(),
88	39.8k	x._data(),
89	39.8k	x.size(),
90	39.8k	std::min(m_p_words, x.size()),
91	39.8k	y._data(),
92	39.8k	y.size(),
93	39.8k	std::min(m_p_words, y.size()),
94	39.8k	ws.data(),
95	39.8k	ws.size());
96
97	39.8k	bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
98	39.8k	}
99
100	0	BigInt Montgomery_Params::mul(const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
101	0	BigInt z = BigInt::with_capacity(2 * m_p_words);
102	0	this->mul(z, x, y, ws);
103	0	return z;
104	0	}
105
106	5.56k	void Montgomery_Params::mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
107	5.56k	const size_t output_size = 2 * m_p_words;
108	5.56k	if(ws.size() < output_size) {
109	0	ws.resize(output_size);
110	0	}
111	5.56k	if(z.size() < output_size) {
112	0	z.grow_to(output_size);
113	0	}
114
115	5.56k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
116
117	5.56k	bigint_mul(z.mutable_data(),
118	5.56k	z.size(),
119	5.56k	x._data(),
120	5.56k	x.size(),
121	5.56k	std::min(m_p_words, x.size()),
122	5.56k	y.data(),
123	5.56k	y.size(),
124	5.56k	std::min(m_p_words, y.size()),
125	5.56k	ws.data(),
126	5.56k	ws.size());
127
128	5.56k	bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
129	5.56k	}
130
131	15.5k	void Montgomery_Params::mul_by(BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
132	15.5k	const size_t output_size = 2 * m_p_words;
133
134	15.5k	if(ws.size() < 2 * output_size) {
135	0	ws.resize(2 * output_size);
136	0	}
137
138	15.5k	word* z_data = &ws[0];
139	15.5k	word* ws_data = &ws[output_size];
140
141	15.5k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
142
143	15.5k	bigint_mul(z_data,
144	15.5k	output_size,
145	15.5k	x._data(),
146	15.5k	x.size(),
147	15.5k	std::min(m_p_words, x.size()),
148	15.5k	y.data(),
149	15.5k	y.size(),
150	15.5k	std::min(m_p_words, y.size()),
151	15.5k	ws_data,
152	15.5k	output_size);
153
154	15.5k	bigint_monty_redc_inplace(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);
155
156	15.5k	if(x.size() < output_size) {
157	0	x.grow_to(output_size);
158	0	}
159	15.5k	copy_mem(x.mutable_data(), z_data, output_size);
160	15.5k	}
161
162	4.65k	void Montgomery_Params::mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
163	4.65k	const size_t output_size = 2 * m_p_words;
164
165	4.65k	if(ws.size() < 2 * output_size) {
166	2.32k	ws.resize(2 * output_size);
167	2.32k	}
168
169	4.65k	word* z_data = &ws[0];
170	4.65k	word* ws_data = &ws[output_size];
171
172	4.65k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
173
174	4.65k	bigint_mul(z_data,
175	4.65k	output_size,
176	4.65k	x._data(),
177	4.65k	x.size(),
178	4.65k	std::min(m_p_words, x.size()),
179	4.65k	y._data(),
180	4.65k	y.size(),
181	4.65k	std::min(m_p_words, y.size()),
182	4.65k	ws_data,
183	4.65k	output_size);
184
185	4.65k	bigint_monty_redc_inplace(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);
186
187	4.65k	if(x.size() < output_size) {
188	0	x.grow_to(output_size);
189	0	}
190	4.65k	copy_mem(x.mutable_data(), z_data, output_size);
191	4.65k	}
192
193	0	BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const {
194	0	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
195	0	return this->sqr(std::span{x._data(), x.size()}, ws);
196	0	}
197
198	0	BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
199	0	BigInt z = BigInt::with_capacity(2 * m_p_words);
200	0	this->sqr(z, x, ws);
201	0	return z;
202	0	}
203
204	12.2k	void Montgomery_Params::sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const {
205	12.2k	this->sqr(z, std::span{x._data(), x.size()}, ws);
206	12.2k	}
207
208	13.5k	void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
209	13.5k	const size_t output_size = 2 * m_p_words;
210
211	13.5k	if(ws.size() < output_size) {
212	0	ws.resize(output_size);
213	0	}
214
215	13.5k	if(z.size() < output_size) {
216	342	z.grow_to(output_size);
217	342	}
218
219	13.5k	bigint_sqr(z.mutable_data(), z.size(), x.data(), x.size(), std::min(m_p_words, x.size()), ws.data(), ws.size());
220
221	13.5k	bigint_monty_redc_inplace(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
222	13.5k	}
223
224	62.3k	void Montgomery_Params::square_this(BigInt& x, secure_vector<word>& ws) const {
225	62.3k	const size_t output_size = 2 * m_p_words;
226
227	62.3k	if(ws.size() < 2 * output_size) {
228	502	ws.resize(2 * output_size);
229	502	}
230
231	62.3k	word* z_data = &ws[0];
232	62.3k	word* ws_data = &ws[output_size];
233
234	62.3k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
235
236	62.3k	bigint_sqr(z_data, output_size, x._data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);
237
238	62.3k	bigint_monty_redc_inplace(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);
239
240	62.3k	if(x.size() < output_size) {
241	502	x.grow_to(output_size);
242	502	}
243	62.3k	copy_mem(x.mutable_data(), z_data, output_size);
244	62.3k	}
245
246	679	Montgomery_Int Montgomery_Int::one(const std::shared_ptr<const Montgomery_Params>& params) {
247	679	return Montgomery_Int(params, params->R1(), false);
248	679	}
249
250	0	Montgomery_Int Montgomery_Int::from_wide_int(const std::shared_ptr<const Montgomery_Params>& params, const BigInt& x) {
251		//BOTAN_ARG_CHECK(x < params->p() * params->p(), "Input too large");
252
253	0	secure_vector<word> ws;
254	0	auto redc_x = params->mul(params->redc(x, ws), params->R3(), ws);
255	0	return Montgomery_Int(params, redc_x, false);
256	0	}
257
258		Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
259		const BigInt& v,
260		bool redc_needed) :
261	10.6k	m_params(params) {
262	10.6k	if(redc_needed == false) {
263	9.94k	m_v = v;
264	9.94k	} else {
265	662	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
266	662	secure_vector<word> ws;
267	662	m_v = m_params->mul(v, m_params->R2(), ws);
268	662	}
269	10.6k	}
270
271		Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
272		const uint8_t bits[],
273		size_t len,
274		bool redc_needed) :
275	0	m_params(params), m_v(bits, len) {
276	0	if(redc_needed) {
277	0	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
278	0	secure_vector<word> ws;
279	0	m_v = m_params->mul(m_v, m_params->R2(), ws);
280	0	}
281	0	}
282
283		Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
284		const word words[],
285		size_t len,
286		bool redc_needed) :
287	645	m_params(std::move(params)) {
288	645	m_v.set_words(words, len);
289
290	645	if(redc_needed) {
291	0	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
292	0	secure_vector<word> ws;
293	0	m_v = m_params->mul(m_v, m_params->R2(), ws);
294	0	}
295	645	}
296
297	10.5k	void Montgomery_Int::fix_size() {
298	10.5k	const size_t p_words = m_params->p_words();
299	10.5k	BOTAN_DEBUG_ASSERT(m_v.sig_words() <= p_words);
300	10.5k	m_v.grow_to(p_words);
301	10.5k	}
302
303	0	bool Montgomery_Int::operator==(const Montgomery_Int& other) const {
304	0	return m_v == other.m_v && m_params->p() == other.m_params->p();
305	0	}
306
307	0	std::vector<uint8_t> Montgomery_Int::serialize() const {
308	0	return value().serialize();
309	0	}
310
311	0	size_t Montgomery_Int::size() const {
312	0	return m_params->p().bytes();
313	0	}
314
315	0	bool Montgomery_Int::is_one() const {
316	0	return m_v == m_params->R1();
317	0	}
318
319	0	bool Montgomery_Int::is_zero() const {
320	0	return m_v.is_zero();
321	0	}
322
323	662	BigInt Montgomery_Int::value() const {
324	662	secure_vector<word> ws;
325	662	return m_params->redc(m_v, ws);
326	662	}
327
328	0	Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
329	0	BOTAN_STATE_CHECK(other.m_params == m_params);
330	0	secure_vector<word> ws;
331	0	BigInt z = m_v;
332	0	z.mod_add(other.m_v, m_params->p(), ws);
333	0	return Montgomery_Int(m_params, z, false);
334	0	}
335
336	0	Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
337	0	BOTAN_STATE_CHECK(other.m_params == m_params);
338	0	secure_vector<word> ws;
339	0	BigInt z = m_v;
340	0	z.mod_sub(other.m_v, m_params->p(), ws);
341	0	return Montgomery_Int(m_params, z, false);
342	0	}
343
344	0	Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) {
345	0	BOTAN_STATE_CHECK(other.m_params == m_params);
346	0	secure_vector<word> ws;
347	0	return this->add(other, ws);
348	0	}
349
350	0	Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) {
351	0	BOTAN_STATE_CHECK(other.m_params == m_params);
352	0	m_v.mod_add(other.m_v, m_params->p(), ws);
353	0	return (*this);
354	0	}
355
356	0	Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) {
357	0	BOTAN_STATE_CHECK(other.m_params == m_params);
358	0	secure_vector<word> ws;
359	0	return this->sub(other, ws);
360	0	}
361
362	0	Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) {
363	0	BOTAN_STATE_CHECK(other.m_params == m_params);
364	0	m_v.mod_sub(other.m_v, m_params->p(), ws);
365	0	return (*this);
366	0	}
367
368	9.26k	Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const {
369	9.26k	BOTAN_STATE_CHECK(other.m_params == m_params);
370	9.26k	secure_vector<word> ws;
371	9.26k	return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
372	9.26k	}
373
374	0	Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
375	0	BOTAN_STATE_CHECK(other.m_params == m_params);
376	0	return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
377	0	}
378
379	0	Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) {
380	0	BOTAN_STATE_CHECK(other.m_params == m_params);
381	0	m_params->mul_by(m_v, other.m_v, ws);
382	0	return (*this);
383	0	}
384
385	15.5k	Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, secure_vector<word>& ws) {
386	15.5k	m_params->mul_by(m_v, other, ws);
387	15.5k	return (*this);
388	15.5k	}
389
390	0	Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other) {
391	0	BOTAN_STATE_CHECK(other.m_params == m_params);
392	0	secure_vector<word> ws;
393	0	return mul_by(other, ws);
394	0	}
395
396	0	Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other) {
397	0	secure_vector<word> ws;
398	0	return mul_by(other, ws);
399	0	}
400
401	15.5k	Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
402	77.9k	for(size_t i = 0; i != n; ++i) {
403	62.3k	m_params->square_this(m_v, ws);
404	62.3k	}
405	15.5k	return (*this);
406	15.5k	}
407
408	0	Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws) {
409	0	m_params->square_this(m_v, ws);
410	0	return (*this);
411	0	}
412
413	0	Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
414	0	return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
415	0	}
416
417	0	Montgomery_Int Montgomery_Int::cube(secure_vector<word>& ws) const {
418	0	return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
419	0	}
420
421	0	Montgomery_Int Montgomery_Int::additive_inverse() const {
422	0	return Montgomery_Int(m_params, m_params->p()) - (*this);
423	0	}
424
425	0	Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws) {
426	0	m_v.mod_mul(2, m_params->p(), ws);
427	0	return (*this);
428	0	}
429
430	0	Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws) {
431	0	m_v.mod_mul(3, m_params->p(), ws);
432	0	return (*this);
433	0	}
434
435	0	Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws) {
436	0	m_v.mod_mul(4, m_params->p(), ws);
437	0	return (*this);
438	0	}
439
440	0	Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws) {
441	0	m_v.mod_mul(8, m_params->p(), ws);
442	0	return (*this);
443	0	}
444
445		} // namespace Botan