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

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

#include <botan/internal/monty.h>

#include <botan/reducer.h>
#include <botan/internal/mp_core.h>

#include <utility>

namespace Botan {

Montgomery_Params::Montgomery_Params(const BigInt& p, const Modular_Reducer& 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 * BOTAN_MP_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 * BOTAN_MP_WORD_BITS);

   // It might be faster to use ct_modulo here vs setting up Barrett reduction?
   Modular_Reducer mod_p(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::inv_mod_p(const BigInt& x, secure_vector<word>& ws) const {
   // TODO use Montgomery inverse here?
   return this->mul(inverse_mod(x, p()), this->R3(), ws);
}

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(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());

   return z;
}

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

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

   x.grow_to(output_size);

   bigint_monty_redc(x.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

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(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(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(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(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(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(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(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();

   if(m_v.sig_words() > p_words) {
      throw Internal_Error("Montgomery_Int::fix_size v too large");
   }

   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 {
   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 {
   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) {
   secure_vector<word> ws;
   return this->add(other, ws);
}

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

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

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

Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const {
   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 {
   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) {
   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) {
   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::multiplicative_inverse() const {
   secure_vector<word> ws;
   return Montgomery_Int(m_params, m_params->inv_mod_p(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: 2024-11-29 06:10

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