Botan 3.7.1
Crypto and TLS for C&
monty.h
Go to the documentation of this file.
1/*
2* (C) 2018,2024 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#include <botan/internal/ct_utils.h>
13
14namespace Botan {
15
16class Modular_Reducer;
17
18class Montgomery_Params;
19
20/**
21* The Montgomery representation of an integer
22*/
24 public:
25 /**
26 * Create a zero-initialized Montgomery_Int
27 */
28 Montgomery_Int(std::shared_ptr<const Montgomery_Params> params) : m_params(std::move(params)) {}
29
30 /**
31 * Create a Montgomery_Int
32 */
33 Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params, const BigInt& v, bool redc_needed = true);
34
35 /**
36 * Create a Montgomery_Int
37 */
38 Montgomery_Int(const std::shared_ptr<const Montgomery_Params>& params,
39 const uint8_t bits[],
40 size_t len,
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 word words[],
48 size_t len,
49 bool redc_needed = true);
50
51 static Montgomery_Int one(const std::shared_ptr<const Montgomery_Params>& params);
52
53 /**
54 * Wide reduction - input can be at most 2*bytes long
55 */
56 static Montgomery_Int from_wide_int(const std::shared_ptr<const Montgomery_Params>& params, const BigInt& x);
57
58 bool operator==(const Montgomery_Int& other) const;
59
60 bool operator!=(const Montgomery_Int& other) const { return (m_v != other.m_v); }
61
62 std::vector<uint8_t> serialize() const;
63
64 size_t size() const;
65 bool is_one() const;
66 bool is_zero() const;
67
68 void fix_size();
69
70 /**
71 * Return the value to normal mod-p space
72 */
73 BigInt value() const;
74
75 /**
76 * Return the Montgomery representation
77 */
78 const BigInt& repr() const { return m_v; }
79
80 Montgomery_Int operator+(const Montgomery_Int& other) const;
81
82 Montgomery_Int operator-(const Montgomery_Int& other) const;
83
85
87
88 Montgomery_Int operator*(const Montgomery_Int& other) const;
89
91
93
95
97
98 Montgomery_Int mul(const Montgomery_Int& other, secure_vector<word>& ws) const;
99
100 Montgomery_Int& mul_by(const Montgomery_Int& other, secure_vector<word>& ws);
101
102 Montgomery_Int& mul_by(const secure_vector<word>& other, secure_vector<word>& ws);
103
105
106 Montgomery_Int cube(secure_vector<word>& ws) const;
107
108 Montgomery_Int& square_this(secure_vector<word>& ws);
109
110 Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
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 void _const_time_poison() const { CT::poison(m_v); }
123
124 void _const_time_unpoison() const { CT::unpoison(m_v); }
125
126 const std::shared_ptr<const Montgomery_Params>& _params() const { return m_params; }
127
128 private:
129 std::shared_ptr<const Montgomery_Params> m_params;
130 BigInt m_v;
131};
132
133/**
134* Parameters for Montgomery Reduction
135*/
137 public:
138 /**
139 * Initialize a set of Montgomery reduction parameters. These values
140 * can be shared by all values in a specific Montgomery domain.
141 */
142 Montgomery_Params(const BigInt& p, const Modular_Reducer& mod_p);
143
144 /**
145 * Initialize a set of Montgomery reduction parameters. These values
146 * can be shared by all values in a specific Montgomery domain.
147 */
148 Montgomery_Params(const BigInt& p);
149
150 const BigInt& p() const { return m_p; }
151
152 const BigInt& R1() const { return m_r1; }
153
154 const BigInt& R2() const { return m_r2; }
155
156 const BigInt& R3() const { return m_r3; }
157
158 word p_dash() const { return m_p_dash; }
159
160 size_t p_words() const { return m_p_words; }
161
162 BigInt redc(const BigInt& x, secure_vector<word>& ws) const;
163
164 void redc_in_place(BigInt& x, secure_vector<word>& ws) const;
165
166 void mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
167
168 void mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const;
169
170 BigInt mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
171
172 BigInt mul(const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const;
173
174 void mul_by(BigInt& x, std::span<const word> y, secure_vector<word>& ws) const;
175
176 void mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
177
178 BigInt sqr(const BigInt& x, secure_vector<word>& ws) const;
179
180 BigInt sqr(std::span<const word> x, secure_vector<word>& ws) const;
181
182 void sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const;
183
184 void sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const;
185
186 void square_this(BigInt& x, secure_vector<word>& ws) 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} // namespace Botan
198
199#endif
#define BOTAN_TEST_API
Definition api.h:39
void _const_time_unpoison() const
Definition monty.h:124
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition monty.h:28
const BigInt & repr() const
Definition monty.h:78
const std::shared_ptr< const Montgomery_Params > & _params() const
Definition monty.h:126
bool operator!=(const Montgomery_Int &other) const
Definition monty.h:60
void _const_time_poison() const
Definition monty.h:122
size_t p_words() const
Definition monty.h:160
const BigInt & R3() const
Definition monty.h:156
const BigInt & R2() const
Definition monty.h:154
const BigInt & R1() const
Definition monty.h:152
word p_dash() const
Definition monty.h:158
const BigInt & p() const
Definition monty.h:150
int(* final)(unsigned char *, CTX *)
BigInt operator*(const BigInt &x, const BigInt &y)
Definition big_ops3.cpp:46
BigInt square(const BigInt &x)
Definition numthry.cpp:157
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:1094
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition alg_id.cpp:54
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition secmem.h:80
constexpr auto operator-=(Strong< T1, Tags... > &a, T2 b)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
constexpr auto operator*=(Strong< T1, Tags... > &a, T2 b)