/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 | | public: |
30 | | /** |
31 | | * Create a zero-initialized Montgomery_Int |
32 | | */ |
33 | 0 | Montgomery_Int(std::shared_ptr<const Montgomery_Params> params) : m_params(params) {} |
34 | | |
35 | | /** |
36 | | * Create a Montgomery_Int |
37 | | */ |
38 | | Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params, const BigInt& v, bool redc_needed = true); |
39 | | |
40 | | /** |
41 | | * Create a Montgomery_Int |
42 | | */ |
43 | | Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params, |
44 | | const uint8_t bits[], |
45 | | size_t len, |
46 | | bool redc_needed = true); |
47 | | |
48 | | /** |
49 | | * Create a Montgomery_Int |
50 | | */ |
51 | | Montgomery_Int(std::shared_ptr<const Montgomery_Params> params, |
52 | | const word words[], |
53 | | size_t len, |
54 | | bool redc_needed = true); |
55 | | |
56 | | bool operator==(const Montgomery_Int& other) const; |
57 | | |
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 | 0 | 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, secure_vector<word>& ws); |
93 | | |
94 | | Montgomery_Int& sub(const Montgomery_Int& other, secure_vector<word>& ws); |
95 | | |
96 | | Montgomery_Int mul(const Montgomery_Int& other, secure_vector<word>& ws) const; |
97 | | |
98 | | Montgomery_Int& mul_by(const Montgomery_Int& other, secure_vector<word>& ws); |
99 | | |
100 | | Montgomery_Int& mul_by(const secure_vector<word>& other, secure_vector<word>& ws); |
101 | | |
102 | | Montgomery_Int square(secure_vector<word>& ws) const; |
103 | | |
104 | | Montgomery_Int cube(secure_vector<word>& ws) const; |
105 | | |
106 | | Montgomery_Int& square_this(secure_vector<word>& ws); |
107 | | |
108 | | Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n); |
109 | | |
110 | | Montgomery_Int multiplicative_inverse() const; |
111 | | |
112 | | Montgomery_Int additive_inverse() const; |
113 | | |
114 | | Montgomery_Int& mul_by_2(secure_vector<word>& ws); |
115 | | |
116 | | Montgomery_Int& mul_by_3(secure_vector<word>& ws); |
117 | | |
118 | | Montgomery_Int& mul_by_4(secure_vector<word>& ws); |
119 | | |
120 | | Montgomery_Int& mul_by_8(secure_vector<word>& ws); |
121 | | |
122 | 0 | void const_time_poison() const { m_v.const_time_poison(); } |
123 | | |
124 | 853 | void const_time_unpoison() const { return m_v.const_time_unpoison(); } |
125 | | |
126 | | private: |
127 | | std::shared_ptr<const Montgomery_Params> m_params; |
128 | | BigInt m_v; |
129 | | }; |
130 | | |
131 | | /** |
132 | | * Parameters for Montgomery Reduction |
133 | | */ |
134 | | class BOTAN_TEST_API Montgomery_Params final { |
135 | | public: |
136 | | /** |
137 | | * Initialize a set of Montgomery reduction parameters. These values |
138 | | * can be shared by all values in a specific Montgomery domain. |
139 | | */ |
140 | | Montgomery_Params(const BigInt& p, const Modular_Reducer& mod_p); |
141 | | |
142 | | /** |
143 | | * Initialize a set of Montgomery reduction parameters. These values |
144 | | * can be shared by all values in a specific Montgomery domain. |
145 | | */ |
146 | | Montgomery_Params(const BigInt& p); |
147 | | |
148 | 1.70k | const BigInt& p() const { return m_p; } |
149 | | |
150 | 853 | const BigInt& R1() const { return m_r1; } |
151 | | |
152 | 853 | const BigInt& R2() const { return m_r2; } |
153 | | |
154 | 0 | const BigInt& R3() const { return m_r3; } |
155 | | |
156 | 0 | word p_dash() const { return m_p_dash; } |
157 | | |
158 | 13.6k | size_t p_words() const { return m_p_words; } |
159 | | |
160 | | BigInt redc(const BigInt& x, secure_vector<word>& ws) const; |
161 | | |
162 | | BigInt mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const; |
163 | | |
164 | | BigInt mul(const BigInt& x, const secure_vector<word>& y, secure_vector<word>& ws) const; |
165 | | |
166 | | void mul_by(BigInt& x, const secure_vector<word>& y, secure_vector<word>& ws) const; |
167 | | |
168 | | void mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const; |
169 | | |
170 | | BigInt sqr(const BigInt& x, secure_vector<word>& ws) const; |
171 | | |
172 | | void square_this(BigInt& x, secure_vector<word>& ws) const; |
173 | | |
174 | | BigInt inv_mod_p(const BigInt& x) const; |
175 | | |
176 | | private: |
177 | | BigInt m_p; |
178 | | BigInt m_r1; |
179 | | BigInt m_r2; |
180 | | BigInt m_r3; |
181 | | word m_p_dash; |
182 | | size_t m_p_words; |
183 | | }; |
184 | | |
185 | | } // namespace Botan |
186 | | |
187 | | #endif |