11972552403

Committed 22 Nov 2024 12:26PM UTC coverage: 91.244% (+0.004%) from 91.24%

Build # 11972552403

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4436 from randombit/jack/cleanup-curvegfp

Cleanups relating to CurveGFp

Run Details

93250 of 102198 relevant lines covered (91.24%)

11237819.31 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

67.3

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

/*
* (C) 2018,2024 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/monty.h>

#include <botan/reducer.h>
#include <botan/internal/mp_core.h>

#include <utility>

namespace Botan {

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, secure_vector<word>& ws) const {
   // TODO use Montgomery inverse here?
   return this->mul(inverse_mod(x, p()), this->R3(), ws);
}

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

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

   BigInt z = x;
   z.grow_to(2 * m_p_words);

   bigint_monty_redc(z.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());

   return z;
}

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

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

   x.grow_to(output_size);

   bigint_monty_redc(x.mutable_data(), m_p._data(), m_p_words, m_p_dash, ws.data(), ws.size());
}

BigInt Montgomery_Params::mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const {
   BigInt z = BigInt::with_capacity(2 * m_p_words);
   this->mul(z, x, y, ws);
   return z;
}

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

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

   if(z.size() < output_size) {
      z.grow_to(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());
}

BigInt Montgomery_Params::mul(const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const {
   BigInt z = BigInt::with_capacity(2 * m_p_words);
   this->mul(z, x, y, ws);
   return z;
}

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

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

   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;

   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 {
   BOTAN_DEBUG_ASSERT(x.sig_words() <= m_p_words);
   return this->sqr(std::span{x._data(), x.size()}, ws);
}

BigInt Montgomery_Params::sqr(std::span<const word> x, secure_vector<word>& ws) const {
   BigInt z = BigInt::with_capacity(2 * m_p_words);
   this->sqr(z, x, ws);
   return z;
}

void Montgomery_Params::sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const {
   this->sqr(z, std::span{x._data(), x.size()}, ws);
}

void Montgomery_Params::sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const {
   const size_t output_size = 2 * m_p_words;

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

   if(z.size() < output_size) {
      z.grow_to(output_size);
   }

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

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

   if(ws.size() < 2 * output_size) {
      ws.resize(2 * output_size);
   }

   word* z_data = &ws[0];
   word* ws_data = &ws[output_size];

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

   bigint_sqr(z_data, output_size, x._data(), x.size(), std::min(m_p_words, x.size()), ws_data, output_size);

   bigint_monty_redc(z_data, m_p._data(), m_p_words, m_p_dash, ws_data, output_size);

   if(x.size() < output_size) {
      x.grow_to(output_size);
   }
   copy_mem(x.mutable_data(), z_data, output_size);
}

Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
                               const BigInt& v,
                               bool redc_needed) :
      m_params(params) {
   if(redc_needed == false) {
      m_v = v;
   } else {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(v, m_params->R2(), ws);
   }
}

Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
                               const uint8_t bits[],
                               size_t len,
                               bool redc_needed) :
      m_params(params), m_v(bits, len) {
   if(redc_needed) {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(m_v, m_params->R2(), ws);
   }
}

Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
                               const word words[],
                               size_t len,
                               bool redc_needed) :
      m_params(std::move(params)) {
   m_v.set_words(words, len);

   if(redc_needed) {
      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
      secure_vector<word> ws;
      m_v = m_params->mul(m_v, m_params->R2(), ws);
   }
}

void Montgomery_Int::fix_size() {
   const size_t p_words = m_params->p_words();

   if(m_v.sig_words() > p_words) {
      throw Internal_Error("Montgomery_Int::fix_size v too large");
   }

   m_v.grow_to(p_words);
}

bool Montgomery_Int::operator==(const Montgomery_Int& other) const {
   return m_v == other.m_v && m_params->p() == other.m_params->p();
}

std::vector<uint8_t> Montgomery_Int::serialize() const {
   return value().serialize();
}

size_t Montgomery_Int::size() const {
   return m_params->p().bytes();
}

bool Montgomery_Int::is_one() const {
   return m_v == m_params->R1();
}

bool Montgomery_Int::is_zero() const {
   return m_v.is_zero();
}

BigInt Montgomery_Int::value() const {
   secure_vector<word> ws;
   return m_params->redc(m_v, ws);
}

Montgomery_Int Montgomery_Int::operator+(const Montgomery_Int& other) const {
   secure_vector<word> ws;
   BigInt z = m_v;
   z.mod_add(other.m_v, m_params->p(), ws);
   return Montgomery_Int(m_params, z, false);
}

Montgomery_Int Montgomery_Int::operator-(const Montgomery_Int& other) const {
   secure_vector<word> ws;
   BigInt z = m_v;
   z.mod_sub(other.m_v, m_params->p(), ws);
   return Montgomery_Int(m_params, z, false);
}

Montgomery_Int& Montgomery_Int::operator+=(const Montgomery_Int& other) {
   secure_vector<word> ws;
   return this->add(other, ws);
}

Montgomery_Int& Montgomery_Int::add(const Montgomery_Int& other, secure_vector<word>& ws) {
   m_v.mod_add(other.m_v, m_params->p(), ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::operator-=(const Montgomery_Int& other) {
   secure_vector<word> ws;
   return this->sub(other, ws);
}

Montgomery_Int& Montgomery_Int::sub(const Montgomery_Int& other, secure_vector<word>& ws) {
   m_v.mod_sub(other.m_v, m_params->p(), ws);
   return (*this);
}

Montgomery_Int Montgomery_Int::operator*(const Montgomery_Int& other) const {
   secure_vector<word> ws;
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
}

Montgomery_Int Montgomery_Int::mul(const Montgomery_Int& other, secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->mul(m_v, other.m_v, ws), false);
}

Montgomery_Int& Montgomery_Int::mul_by(const Montgomery_Int& other, secure_vector<word>& ws) {
   m_params->mul_by(m_v, other.m_v, ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::mul_by(const secure_vector<word>& other, secure_vector<word>& ws) {
   m_params->mul_by(m_v, other, ws);
   return (*this);
}

Montgomery_Int& Montgomery_Int::operator*=(const Montgomery_Int& other) {
   secure_vector<word> ws;
   return mul_by(other, ws);
}

Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other) {
   secure_vector<word> ws;
   return mul_by(other, ws);
}

Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n) {
   for(size_t i = 0; i != n; ++i) {
      m_params->square_this(m_v, ws);
   }
   return (*this);
}

Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws) {
   m_params->square_this(m_v, ws);
   return (*this);
}

Montgomery_Int Montgomery_Int::square(secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
}

Montgomery_Int Montgomery_Int::cube(secure_vector<word>& ws) const {
   return Montgomery_Int(m_params, m_params->sqr(m_v, ws), false);
}

Montgomery_Int Montgomery_Int::multiplicative_inverse() const {
   secure_vector<word> ws;
   return Montgomery_Int(m_params, m_params->inv_mod_p(m_v, ws), 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);
}

}  // namespace Botan

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

randombit / botan / 11972552403

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous