Coverage Report

Created: 2021-05-04 09:02

/src/botan/build/include/botan/internal/monty.h
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
#ifndef BOTAN_MONTY_INT_H_
8
#define BOTAN_MONTY_INT_H_
9
10
#include <botan/bigint.h>
11
12
namespace Botan {
13
14
class Modular_Reducer;
15
16
class Montgomery_Params;
17
18
/*
19
* Compute -input^-1 mod 2^MP_WORD_BITS. Throws an exception if input
20
* is even. If input is odd, then input and 2^n are relatively prime
21
* and an inverse exists.
22
*/
23
word monty_inverse(word input);
24
25
/**
26
* The Montgomery representation of an integer
27
*/
28
class BOTAN_TEST_API Montgomery_Int final
29
   {
30
   public:
31
      /**
32
      * Create a zero-initialized Montgomery_Int
33
      */
34
0
      Montgomery_Int(std::shared_ptr<const Montgomery_Params> params) : m_params(params) {}
35
36
      /**
37
      * Create a Montgomery_Int
38
      */
39
      Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
40
                     const BigInt& v,
41
                     bool redc_needed = true);
42
43
      /**
44
      * Create a Montgomery_Int
45
      */
46
      Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
47
                     const uint8_t bits[], size_t len,
48
                     bool redc_needed = true);
49
50
      /**
51
      * Create a Montgomery_Int
52
      */
53
      Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
54
                     const word words[], size_t len,
55
                     bool redc_needed = true);
56
57
      bool operator==(const Montgomery_Int& other) const;
58
0
      bool operator!=(const Montgomery_Int& other) const { return (m_v != other.m_v); }
59
60
      std::vector<uint8_t> serialize() const;
61
62
      size_t size() const;
63
      bool is_one() const;
64
      bool is_zero() const;
65
66
      void fix_size();
67
68
      /**
69
      * Return the value to normal mod-p space
70
      */
71
      BigInt value() const;
72
73
      /**
74
      * Return the Montgomery representation
75
      */
76
2.08M
      const BigInt& repr() const { return m_v; }
77
78
      Montgomery_Int operator+(const Montgomery_Int& other) const;
79
80
      Montgomery_Int operator-(const Montgomery_Int& other) const;
81
82
      Montgomery_Int& operator+=(const Montgomery_Int& other);
83
84
      Montgomery_Int& operator-=(const Montgomery_Int& other);
85
86
      Montgomery_Int operator*(const Montgomery_Int& other) const;
87
88
      Montgomery_Int& operator*=(const Montgomery_Int& other);
89
90
      Montgomery_Int& operator*=(const secure_vector<word>& other);
91
92
      Montgomery_Int& add(const Montgomery_Int& other,
93
                          secure_vector<word>& ws);
94
95
      Montgomery_Int& sub(const Montgomery_Int& other,
96
                          secure_vector<word>& ws);
97
98
      Montgomery_Int mul(const Montgomery_Int& other,
99
                         secure_vector<word>& ws) const;
100
101
      Montgomery_Int& mul_by(const Montgomery_Int& other,
102
                             secure_vector<word>& ws);
103
104
      Montgomery_Int& mul_by(const secure_vector<word>& other,
105
                             secure_vector<word>& ws);
106
107
      Montgomery_Int square(secure_vector<word>& ws) const;
108
109
      Montgomery_Int cube(secure_vector<word>& ws) const;
110
111
      Montgomery_Int& square_this(secure_vector<word>& ws);
112
113
      Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
114
115
      Montgomery_Int multiplicative_inverse() const;
116
117
      Montgomery_Int additive_inverse() const;
118
119
      Montgomery_Int& mul_by_2(secure_vector<word>& ws);
120
121
      Montgomery_Int& mul_by_3(secure_vector<word>& ws);
122
123
      Montgomery_Int& mul_by_4(secure_vector<word>& ws);
124
125
      Montgomery_Int& mul_by_8(secure_vector<word>& ws);
126
127
28.9k
      void const_time_poison() const { m_v.const_time_poison(); }
128
72.2k
      void const_time_unpoison() const { return m_v.const_time_unpoison(); }
129
130
   private:
131
      std::shared_ptr<const Montgomery_Params> m_params;
132
      BigInt m_v;
133
   };
134
135
/**
136
* Parameters for Montgomery Reduction
137
*/
138
class BOTAN_TEST_API Montgomery_Params final
139
   {
140
   public:
141
      /**
142
      * Initialize a set of Montgomery reduction parameters. These values
143
      * can be shared by all values in a specific Montgomery domain.
144
      */
145
      Montgomery_Params(const BigInt& p, const Modular_Reducer& mod_p);
146
147
      /**
148
      * Initialize a set of Montgomery reduction parameters. These values
149
      * can be shared by all values in a specific Montgomery domain.
150
      */
151
      Montgomery_Params(const BigInt& p);
152
153
145k
      const BigInt& p() const { return m_p; }
154
72.5k
      const BigInt& R1() const { return m_r1; }
155
72.6k
      const BigInt& R2() const { return m_r2; }
156
0
      const BigInt& R3() const { return m_r3; }
157
158
0
      word p_dash() const { return m_p_dash; }
159
160
1.07M
      size_t p_words() const { return m_p_words; }
161
162
      BigInt redc(const BigInt& x,
163
                  secure_vector<word>& ws) const;
164
165
      BigInt mul(const BigInt& x,
166
                 const BigInt& y,
167
                 secure_vector<word>& ws) const;
168
169
      BigInt mul(const BigInt& x,
170
                 const secure_vector<word>& y,
171
                 secure_vector<word>& ws) const;
172
173
      void mul_by(BigInt& x,
174
                  const secure_vector<word>& y,
175
                  secure_vector<word>& ws) const;
176
177
      void mul_by(BigInt& x, const BigInt& y,
178
                  secure_vector<word>& ws) const;
179
180
      BigInt sqr(const BigInt& x,
181
                 secure_vector<word>& ws) const;
182
183
      void square_this(BigInt& x,
184
                       secure_vector<word>& ws) const;
185
186
      BigInt inv_mod_p(const BigInt& x) const;
187
188
   private:
189
      BigInt m_p;
190
      BigInt m_r1;
191
      BigInt m_r2;
192
      BigInt m_r3;
193
      word m_p_dash;
194
      size_t m_p_words;
195
   };
196
197
}
198
199
#endif