/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
   {
   // 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: 2020-05-23 13:54

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