/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/monty.h>
#include <botan/reducer.h>
#include <botan/internal/mp_core.h>

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_negative() || p.is_even())
      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
   {
   return ct_inverse_mod_odd_modulus(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");

   secure_vector<word>& w = m_v.get_word_vector();

   if(w.size() != p_words)
      {
      w.resize(p_words);
      w.shrink_to_fit();
      }
   }

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: 2020-02-14 15:38

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