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

Source (jump to first uncovered line)
/*
* (C) 2018 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 {

word monty_inverse(word a)
   {
   if(a % 2 == 0)
      throw Invalid_Argument("monty_inverse only valid for odd integers");

   /*
   * From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
   * https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
   */

   word b = 1;
   word r = 0;

   for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
      {
      const word bi = b % 2;
      r >>= 1;
      r += bi << (BOTAN_MP_WORD_BITS - 1);

      b -= a * bi;
      b >>= 1;
      }

   // Now invert in addition space
   r = (MP_WORD_MAX - r) + 1;

   return r;
   }

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) const
   {
   // TODO use Montgomery inverse here?
   return inverse_mod(x, p());
   }

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

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

   BigInt z = x;
   z.grow_to(output_size);

   bigint_monty_redc(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
   {
   const size_t output_size = 2*m_p_words + 2;

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

   BigInt z = BigInt::with_capacity(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());

   return z;
   }

BigInt Montgomery_Params::mul(const BigInt& x,
                              const secure_vector<word>& y,
                              secure_vector<word>& ws) const
   {
   const size_t output_size = 2*m_p_words + 2;
   if(ws.size() < output_size)
      ws.resize(output_size);
   BigInt z = BigInt::with_capacity(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());

   return z;
   }

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

   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 + 2;

   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
   {
   const size_t output_size = 2*m_p_words + 2;

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

   BigInt z = BigInt::with_capacity(output_size);

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

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

   return z;
   }

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

   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
   {
   std::vector<uint8_t> v(size());
   BigInt::encode_1363(v.data(), v.size(), value());
   return v;
   }

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;
   const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
   return Montgomery_Int(m_params, iv, 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);
   }

}

Coverage Report

Created: 2022-06-23 06:44

Line	Count	Source (jump to first uncovered line)
1		/*
2		* (C) 2018 Jack Lloyd
3		*
4		* Botan is released under the Simplified BSD License (see license.txt)
5		*/
6
7		#include <botan/internal/monty.h>
8		#include <botan/reducer.h>
9		#include <botan/internal/mp_core.h>
10
11		#include <utility>
12
13		namespace Botan {
14
15		word monty_inverse(word a)
16	29.3k	{
17	29.3k	if(a % 2 == 0)
18	0	throw Invalid_Argument("monty_inverse only valid for odd integers");
19
20		/*
21		* From "A New Algorithm for Inversion mod p^k" by Çetin Kaya Koç
22		* https://eprint.iacr.org/2017/411.pdf sections 5 and 7.
23		*/
24
25	29.3k	word b = 1;
26	29.3k	word r = 0;
27
28	1.90M	for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
29	1.87M	{
30	1.87M	const word bi = b % 2;
31	1.87M	r >>= 1;
32	1.87M	r += bi << (BOTAN_MP_WORD_BITS - 1);
33
34	1.87M	b -= a * bi;
35	1.87M	b >>= 1;
36	1.87M	}
37
38		// Now invert in addition space
39	29.3k	r = (MP_WORD_MAX - r) + 1;
40
41	29.3k	return r;
42	29.3k	}
43
44		Montgomery_Params::Montgomery_Params(const BigInt& p,
45		const Modular_Reducer& mod_p)
46	21.6k	{
47	21.6k	if(p.is_even() \|\| p < 3)
48	99	throw Invalid_Argument("Montgomery_Params invalid modulus");
49
50	21.5k	m_p = p;
51	21.5k	m_p_words = m_p.sig_words();
52	21.5k	m_p_dash = monty_inverse(m_p.word_at(0));
53
54	21.5k	const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
55
56	21.5k	m_r1 = mod_p.reduce(r);
57	21.5k	m_r2 = mod_p.square(m_r1);
58	21.5k	m_r3 = mod_p.multiply(m_r1, m_r2);
59	21.5k	}
60
61		Montgomery_Params::Montgomery_Params(const BigInt& p)
62	6.57k	{
63	6.57k	if(p.is_even() \|\| p < 3)
64	12	throw Invalid_Argument("Montgomery_Params invalid modulus");
65
66	6.56k	m_p = p;
67	6.56k	m_p_words = m_p.sig_words();
68	6.56k	m_p_dash = monty_inverse(m_p.word_at(0));
69
70	6.56k	const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
71
72		// It might be faster to use ct_modulo here vs setting up Barrett reduction?
73	6.56k	Modular_Reducer mod_p(p);
74
75	6.56k	m_r1 = mod_p.reduce(r);
76	6.56k	m_r2 = mod_p.square(m_r1);
77	6.56k	m_r3 = mod_p.multiply(m_r1, m_r2);
78	6.56k	}
79
80		BigInt Montgomery_Params::inv_mod_p(const BigInt& x) const
81	0	{
82		// TODO use Montgomery inverse here?
83	0	return inverse_mod(x, p());
84	0	}
85
86		BigInt Montgomery_Params::redc(const BigInt& x, secure_vector<word>& ws) const
87	82.9k	{
88	82.9k	const size_t output_size = 2*m_p_words + 2;
89
90	82.9k	if(ws.size() < output_size)
91	82.9k	ws.resize(output_size);
92
93	82.9k	BigInt z = x;
94	82.9k	z.grow_to(output_size);
95
96	82.9k	bigint_monty_redc(z.mutable_data(),
97	82.9k	m_p.data(), m_p_words, m_p_dash,
98	82.9k	ws.data(), ws.size());
99
100	82.9k	return z;
101	82.9k	}
102
103		BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y,
104		secure_vector<word>& ws) const
105	1.16M	{
106	1.16M	const size_t output_size = 2*m_p_words + 2;
107
108	1.16M	if(ws.size() < output_size)
109	1.16M	ws.resize(output_size);
110
111	1.16M	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
112	1.16M	BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
113
114	1.16M	BigInt z = BigInt::with_capacity(output_size);
115	1.16M	bigint_mul(z.mutable_data(), z.size(),
116	1.16M	x.data(), x.size(), std::min(m_p_words, x.size()),
117	1.16M	y.data(), y.size(), std::min(m_p_words, y.size()),
118	1.16M	ws.data(), ws.size());
119
120	1.16M	bigint_monty_redc(z.mutable_data(),
121	1.16M	m_p.data(), m_p_words, m_p_dash,
122	1.16M	ws.data(), ws.size());
123
124	1.16M	return z;
125	1.16M	}
126
127		BigInt Montgomery_Params::mul(const BigInt& x,
128		const secure_vector<word>& y,
129		secure_vector<word>& ws) const
130	0	{
131	0	const size_t output_size = 2*m_p_words + 2;
132	0	if(ws.size() < output_size)
133	0	ws.resize(output_size);
134	0	BigInt z = BigInt::with_capacity(output_size);
135
136	0	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
137
138	0	bigint_mul(z.mutable_data(), z.size(),
139	0	x.data(), x.size(), std::min(m_p_words, x.size()),
140	0	y.data(), y.size(), std::min(m_p_words, y.size()),
141	0	ws.data(), ws.size());
142
143	0	bigint_monty_redc(z.mutable_data(),
144	0	m_p.data(), m_p_words, m_p_dash,
145	0	ws.data(), ws.size());
146
147	0	return z;
148	0	}
149
150		void Montgomery_Params::mul_by(BigInt& x,
151		const secure_vector<word>& y,
152		secure_vector<word>& ws) const
153	194k	{
154	194k	const size_t output_size = 2*m_p_words + 2;
155
156	194k	if(ws.size() < 2*output_size)
157	0	ws.resize(2*output_size);
158
159	194k	word* z_data = &ws[0];
160	194k	word* ws_data = &ws[output_size];
161
162	194k	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
163
164	194k	bigint_mul(z_data, output_size,
165	194k	x.data(), x.size(), std::min(m_p_words, x.size()),
166	194k	y.data(), y.size(), std::min(m_p_words, y.size()),
167	194k	ws_data, output_size);
168
169	194k	bigint_monty_redc(z_data,
170	194k	m_p.data(), m_p_words, m_p_dash,
171	194k	ws_data, output_size);
172
173	194k	if(x.size() < output_size)
174	0	x.grow_to(output_size);
175	194k	copy_mem(x.mutable_data(), z_data, output_size);
176	194k	}
177
178		void Montgomery_Params::mul_by(BigInt& x,
179		const BigInt& y,
180		secure_vector<word>& ws) const
181	1.19M	{
182	1.19M	const size_t output_size = 2*m_p_words + 2;
183
184	1.19M	if(ws.size() < 2*output_size)
185	77	ws.resize(2*output_size);
186
187	1.19M	word* z_data = &ws[0];
188	1.19M	word* ws_data = &ws[output_size];
189
190	1.19M	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
191
192	1.19M	bigint_mul(z_data, output_size,
193	1.19M	x.data(), x.size(), std::min(m_p_words, x.size()),
194	1.19M	y.data(), y.size(), std::min(m_p_words, y.size()),
195	1.19M	ws_data, output_size);
196
197	1.19M	bigint_monty_redc(z_data,
198	1.19M	m_p.data(), m_p_words, m_p_dash,
199	1.19M	ws_data, output_size);
200
201	1.19M	if(x.size() < output_size)
202	14	x.grow_to(output_size);
203	1.19M	copy_mem(x.mutable_data(), z_data, output_size);
204	1.19M	}
205
206		BigInt Montgomery_Params::sqr(const BigInt& x, secure_vector<word>& ws) const
207	172	{
208	172	const size_t output_size = 2*m_p_words + 2;
209
210	172	if(ws.size() < output_size)
211	86	ws.resize(output_size);
212
213	172	BigInt z = BigInt::with_capacity(output_size);
214
215	172	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
216
217	172	bigint_sqr(z.mutable_data(), z.size(),
218	172	x.data(), x.size(), std::min(m_p_words, x.size()),
219	172	ws.data(), ws.size());
220
221	172	bigint_monty_redc(z.mutable_data(),
222	172	m_p.data(), m_p_words, m_p_dash,
223	172	ws.data(), ws.size());
224
225	172	return z;
226	172	}
227
228		void Montgomery_Params::square_this(BigInt& x,
229		secure_vector<word>& ws) const
230	8.79M	{
231	8.79M	const size_t output_size = 2*m_p_words + 2;
232
233	8.79M	if(ws.size() < 2*output_size)
234	31.5k	ws.resize(2*output_size);
235
236	8.79M	word* z_data = &ws[0];
237	8.79M	word* ws_data = &ws[output_size];
238
239	8.79M	BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
240
241	8.79M	bigint_sqr(z_data, output_size,
242	8.79M	x.data(), x.size(), std::min(m_p_words, x.size()),
243	8.79M	ws_data, output_size);
244
245	8.79M	bigint_monty_redc(z_data,
246	8.79M	m_p.data(), m_p_words, m_p_dash,
247	8.79M	ws_data, output_size);
248
249	8.79M	if(x.size() < output_size)
250	2.20k	x.grow_to(output_size);
251	8.79M	copy_mem(x.mutable_data(), z_data, output_size);
252	8.79M	}
253
254		Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
255		const BigInt& v,
256		bool redc_needed) :
257		m_params(params)
258	1.25M	{
259	1.25M	if(redc_needed == false)
260	1.16M	{
261	1.16M	m_v = v;
262	1.16M	}
263	83.5k	else
264	83.5k	{
265	83.5k	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
266	83.5k	secure_vector<word> ws;
267	83.5k	m_v = m_params->mul(v, m_params->R2(), ws);
268	83.5k	}
269	1.25M	}
270
271		Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
272		const uint8_t bits[], size_t len,
273		bool redc_needed) :
274		m_params(params),
275		m_v(bits, len)
276	0	{
277	0	if(redc_needed)
278	0	{
279	0	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
280	0	secure_vector<word> ws;
281	0	m_v = m_params->mul(m_v, m_params->R2(), ws);
282	0	}
283	0	}
284
285		Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
286		const word words[], size_t len,
287		bool redc_needed) :
288		m_params(std::move(params))
289	2.24k	{
290	2.24k	m_v.set_words(words, len);
291
292	2.24k	if(redc_needed)
293	0	{
294	0	BOTAN_ASSERT_NOMSG(m_v < m_params->p());
295	0	secure_vector<word> ws;
296	0	m_v = m_params->mul(m_v, m_params->R2(), ws);
297	0	}
298	2.24k	}
299
300		void Montgomery_Int::fix_size()
301	1.24M	{
302	1.24M	const size_t p_words = m_params->p_words();
303
304	1.24M	if(m_v.sig_words() > p_words)
305	2	throw Internal_Error("Montgomery_Int::fix_size v too large");
306
307	1.24M	m_v.grow_to(p_words);
308	1.24M	}
309
310		bool Montgomery_Int::operator==(const Montgomery_Int& other) const
311	0	{
312	0	return m_v == other.m_v && m_params->p() == other.m_params->p();
313	0	}
314
315		std::vector<uint8_t> Montgomery_Int::serialize() const
316	0	{
317	0	std::vector<uint8_t> v(size());
318	0	BigInt::encode_1363(v.data(), v.size(), value());
319	0	return v;
320	0	}
321
322		size_t Montgomery_Int::size() const
323	0	{
324	0	return m_params->p().bytes();
325	0	}
326
327		bool Montgomery_Int::is_one() const
328	0	{
329	0	return m_v == m_params->R1();
330	0	}
331
332		bool Montgomery_Int::is_zero() const
333	0	{
334	0	return m_v.is_zero();
335	0	}
336
337		BigInt Montgomery_Int::value() const
338	82.9k	{
339	82.9k	secure_vector<word> ws;
340	82.9k	return m_params->redc(m_v, ws);
341	82.9k	}
342
343		Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const
344	0	{
345	0	secure_vector<word> ws;
346	0	BigInt z = m_v;
347	0	z.mod_add(other.m_v, m_params->p(), ws);
348	0	return Montgomery_Int(m_params, z, false);
349	0	}
350
351		Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const
352	0	{
353	0	secure_vector<word> ws;
354	0	BigInt z = m_v;
355	0	z.mod_sub(other.m_v, m_params->p(), ws);
356	0	return Montgomery_Int(m_params, z, false);
357	0	}
358
359		Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other)
360	0	{
361	0	secure_vector<word> ws;
362	0	return this->add(other, ws);
363	0	}
364
365		Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws)
366	0	{
367	0	m_v.mod_add(other.m_v, m_params->p(), ws);
368	0	return (*this);
369	0	}
370
371		Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other)
372	0	{
373	0	secure_vector<word> ws;
374	0	return this->sub(other, ws);
375	0	}
376
377		Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws)
378	0	{
379	0	m_v.mod_sub(other.m_v, m_params->p(), ws);
380	0	return (*this);
381	0	}
382
383		Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const
384	1.08M	{
385	1.08M	secure_vector<word> ws;
386	1.08M	return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
387	1.08M	}
388
389		Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other,
390		secure_vector<word>& ws) const
391	946	{
392	946	return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
393	946	}
394
395		Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other,
396		secure_vector<word>& ws)
397	1.19M	{
398	1.19M	m_params->mul_by(m_v, other.m_v, ws);
399	1.19M	return (*this);
400	1.19M	}
401
402		Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other,
403		secure_vector<word>& ws)
404	194k	{
405	194k	m_params->mul_by(m_v, other, ws);
406	194k	return (*this);
407	194k	}
408
409		Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other)
410	0	{
411	0	secure_vector<word> ws;
412	0	return mul_by(other, ws);
413	0	}
414
415		Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other)
416	0	{
417	0	secure_vector<word> ws;
418	0	return mul_by(other, ws);
419	0	}
420
421		Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n)
422	2.77M	{
423	11.4M	for(size_t i = 0; i != n; ++i)
424	8.70M	m_params->square_this(m_v, ws);
425	2.77M	return (*this);
426	2.77M	}
427
428		Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws)
429	83.6k	{
430	83.6k	m_params->square_this(m_v, ws);
431	83.6k	return (*this);
432	83.6k	}
433
434		Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const
435	172	{
436	172	return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
437	172	}
438
439		Montgomery_Int Montgomery_Int::cube(secure_vector<word>& ws) const
440	0	{
441	0	return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
442	0	}
443
444		Montgomery_Int Montgomery_Int::multiplicative_inverse() const
445	0	{
446	0	secure_vector<word> ws;
447	0	const BigInt iv = m_params->mul(m_params->inv_mod_p(m_v), m_params->R3(), ws);
448	0	return Montgomery_Int(m_params, iv, false);
449	0	}
450
451		Montgomery_Int Montgomery_Int::additive_inverse() const
452	0	{
453	0	return Montgomery_Int(m_params, m_params->p()) - (*this);
454	0	}
455
456		Montgomery_Int& Montgomery_Int::mul_by_2(secure_vector<word>& ws)
457	0	{
458	0	m_v.mod_mul(2, m_params->p(), ws);
459	0	return (*this);
460	0	}
461
462		Montgomery_Int& Montgomery_Int::mul_by_3(secure_vector<word>& ws)
463	0	{
464	0	m_v.mod_mul(3, m_params->p(), ws);
465	0	return (*this);
466	0	}
467
468		Montgomery_Int& Montgomery_Int::mul_by_4(secure_vector<word>& ws)
469	0	{
470	0	m_v.mod_mul(4, m_params->p(), ws);
471	0	return (*this);
472	0	}
473
474		Montgomery_Int& Montgomery_Int::mul_by_8(secure_vector<word>& ws)
475	0	{
476	0	m_v.mod_mul(8, m_params->p(), ws);
477	0	return (*this);
478	0	}
479
480		}