/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_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-11-21 08:34

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