/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>

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::Positive, 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::Positive, 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::Positive, 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(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(params),
   m_v(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::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: 2021-02-21 07:20

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