Botan 3.9.0
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#include <memory>
14#include <span>
15
16namespace Botan {
17
19
20/**
21* Parameters for Montgomery Reduction
22*/
24 public:
25 /**
26 * Initialize a set of Montgomery reduction parameters. These values
27 * can be shared by all values in a specific Montgomery domain.
28 */
29 Montgomery_Params(const BigInt& p, const Barrett_Reduction& mod_p);
30
31 /**
32 * Initialize a set of Montgomery reduction parameters. These values
33 * can be shared by all values in a specific Montgomery domain.
34 */
35 explicit Montgomery_Params(const BigInt& p);
36
37 bool operator==(const Montgomery_Params& other) const;
38
39 bool operator!=(const Montgomery_Params& other) const { return !((*this) == other); }
40
41 const BigInt& p() const { return m_data->p(); }
42
43 const BigInt& R1() const { return m_data->r1(); }
44
45 const BigInt& R2() const { return m_data->r2(); }
46
47 const BigInt& R3() const { return m_data->r3(); }
48
49 word p_dash() const { return m_data->p_dash(); }
50
51 size_t p_words() const { return m_data->p_size(); }
52
53 BigInt redc(const BigInt& x, secure_vector<word>& ws) const;
54
55 void mul(BigInt& z, const BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
56
57 void mul(BigInt& z, const BigInt& x, std::span<const word> y, secure_vector<word>& ws) const;
58
59 BigInt mul(const BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
60
61 void mul_by(BigInt& x, const BigInt& y, secure_vector<word>& ws) const;
62
63 BigInt sqr(const BigInt& x, secure_vector<word>& ws) const;
64
65 void sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const;
66
67 void sqr(BigInt& z, std::span<const word> x, secure_vector<word>& ws) const;
68
69 private:
70 BigInt sqr(std::span<const word> x, secure_vector<word>& ws) const;
71
72 class Data final {
73 public:
74 Data(const BigInt& p, const Barrett_Reduction& mod_p);
75
76 const BigInt& p() const { return m_p; }
77
78 const BigInt& r1() const { return m_r1; }
79
80 const BigInt& r2() const { return m_r2; }
81
82 const BigInt& r3() const { return m_r3; }
83
84 word p_dash() const { return m_p_dash; }
85
86 size_t p_size() const { return m_p_words; }
87
88 private:
89 BigInt m_p;
90 BigInt m_r1;
91 BigInt m_r2;
92 BigInt m_r3;
93 word m_p_dash;
94 size_t m_p_words;
95 };
96
97 std::shared_ptr<const Data> m_data;
98};
99
100/**
101* The Montgomery representation of an integer
102*/
104 public:
105 /**
106 * Create a zero-initialized Montgomery_Int
107 */
108 explicit Montgomery_Int(const Montgomery_Params& params) : m_params(params) {}
109
110 /**
111 * Create a Montgomery_Int from a BigInt
112 */
113 Montgomery_Int(const Montgomery_Params& params, const BigInt& v, bool redc_needed = true);
114
115 /**
116 * Create a Montgomery_Int
117 *
118 * The span must be exactly p_words long and encoding a value less than p already
119 * in Montgomery form
120 */
121 Montgomery_Int(const Montgomery_Params& params, std::span<const word> words);
122
123 /**
124 * Return the value 1 in Montgomery form
125 */
126 static Montgomery_Int one(const Montgomery_Params& params);
127
128 /**
129 * Wide reduction - input can be at most 2*bytes long
130 */
131 static Montgomery_Int from_wide_int(const Montgomery_Params& params, const BigInt& x);
132
133 std::vector<uint8_t> serialize() const;
134
135 /**
136 * Return the value to normal mod-p space
137 */
138 BigInt value() const;
139
140 /**
141 * Return the Montgomery representation
142 */
143 const secure_vector<word>& repr() const { return m_v; }
144
145 Montgomery_Int operator+(const Montgomery_Int& other) const;
146
147 Montgomery_Int operator-(const Montgomery_Int& other) const;
148
149 Montgomery_Int mul(const Montgomery_Int& other, secure_vector<word>& ws) const;
150
151 Montgomery_Int& mul_by(const Montgomery_Int& other, secure_vector<word>& ws);
152
153 Montgomery_Int& mul_by(std::span<const word> other, secure_vector<word>& ws);
154
156
157 Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
158
159 void _const_time_poison() const { CT::poison(m_v); }
160
161 void _const_time_unpoison() const { CT::unpoison(m_v); }
162
163 const Montgomery_Params& _params() const { return m_params; }
164
165 private:
167
168 Montgomery_Params m_params;
170};
171
172} // namespace Botan
173
174#endif
#define BOTAN_TEST_API
Definition api.h:41
void _const_time_unpoison() const
Definition monty.h:161
const secure_vector< word > & repr() const
Definition monty.h:143
Montgomery_Int(const Montgomery_Params &params)
Definition monty.h:108
void _const_time_poison() const
Definition monty.h:159
const Montgomery_Params & _params() const
Definition monty.h:163
bool operator!=(const Montgomery_Params &other) const
Definition monty.h:39
size_t p_words() const
Definition monty.h:51
bool operator==(const Montgomery_Params &other) const
Definition monty.cpp:51
Montgomery_Params(const BigInt &p, const Barrett_Reduction &mod_p)
Definition monty.cpp:45
const BigInt & R3() const
Definition monty.h:47
const BigInt & R2() const
Definition monty.h:45
const BigInt & R1() const
Definition monty.h:43
word p_dash() const
Definition monty.h:49
const BigInt & p() const
Definition monty.h:41
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:65
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:54
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:1095
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119