Botan  2.19.1
Crypto and TLS for C++11
monty.h
Go to the documentation of this file.
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>
12 
13 namespace Botan {
14 
15 class Modular_Reducer;
16 
17 class Montgomery_Params;
18 
19 /**
20 * The Montgomery representation of an integer
21 */
23  {
24  public:
25  /**
26  * Create a zero-initialized Montgomery_Int
27  */
28  Montgomery_Int(std::shared_ptr<const Montgomery_Params> params) : m_params(params) {}
29 
30  /**
31  * Create a Montgomery_Int
32  */
33  Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
34  const BigInt& v,
35  bool redc_needed = true);
36 
37  /**
38  * Create a Montgomery_Int
39  */
40  Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
41  const uint8_t bits[], size_t len,
42  bool redc_needed = true);
43 
44  /**
45  * Create a Montgomery_Int
46  */
47  Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
48  const word words[], size_t len,
49  bool redc_needed = true);
50 
51  bool operator==(const Montgomery_Int& other) const;
52  bool operator!=(const Montgomery_Int& other) const { return (m_v != other.m_v); }
53 
54  std::vector<uint8_t> serialize() const;
55 
56  size_t size() const;
57  bool is_one() const;
58  bool is_zero() const;
59 
60  void fix_size();
61 
62  /**
63  * Return the value to normal mod-p space
64  */
65  BigInt value() const;
66 
67  /**
68  * Return the Montgomery representation
69  */
70  const BigInt& repr() const { return m_v; }
71 
72  Montgomery_Int operator+(const Montgomery_Int& other) const;
73 
74  Montgomery_Int operator-(const Montgomery_Int& other) const;
75 
77 
78  Montgomery_Int& operator-=(const Montgomery_Int& other);
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 secure_vector<word>& other);
85 
86  Montgomery_Int& add(const Montgomery_Int& other,
88 
89  Montgomery_Int& sub(const Montgomery_Int& other,
91 
92  Montgomery_Int mul(const Montgomery_Int& other,
93  secure_vector<word>& ws) const;
94 
95  Montgomery_Int& mul_by(const Montgomery_Int& other,
97 
98  Montgomery_Int& mul_by(const secure_vector<word>& other,
100 
102 
103  Montgomery_Int& square_this(secure_vector<word>& ws);
104 
105  Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
106 
107  Montgomery_Int multiplicative_inverse() const;
108 
109  Montgomery_Int additive_inverse() const;
110 
111  Montgomery_Int& mul_by_2(secure_vector<word>& ws);
112 
113  Montgomery_Int& mul_by_3(secure_vector<word>& ws);
114 
115  Montgomery_Int& mul_by_4(secure_vector<word>& ws);
116 
117  Montgomery_Int& mul_by_8(secure_vector<word>& ws);
118 
119  void const_time_poison() const { m_v.const_time_poison(); }
120  void const_time_unpoison() const { return m_v.const_time_unpoison(); }
121 
122  private:
123  std::shared_ptr<const Montgomery_Params> m_params;
124  BigInt m_v;
125  };
126 
127 /**
128 * Parameters for Montgomery Reduction
129 */
131  {
132  public:
133  /**
134  * Initialize a set of Montgomery reduction parameters. These values
135  * can be shared by all values in a specific Montgomery domain.
136  */
137  Montgomery_Params(const BigInt& p, const Modular_Reducer& mod_p);
138 
139  /**
140  * Initialize a set of Montgomery reduction parameters. These values
141  * can be shared by all values in a specific Montgomery domain.
142  */
143  Montgomery_Params(const BigInt& p);
144 
145  const BigInt& p() const { return m_p; }
146  const BigInt& R1() const { return m_r1; }
147  const BigInt& R2() const { return m_r2; }
148  const BigInt& R3() const { return m_r3; }
149 
150  word p_dash() const { return m_p_dash; }
151 
152  size_t p_words() const { return m_p_words; }
153 
154  BigInt redc(const BigInt& x,
155  secure_vector<word>& ws) const;
156 
157  BigInt mul(const BigInt& x,
158  const BigInt& y,
159  secure_vector<word>& ws) const;
160 
161  BigInt mul(const BigInt& x,
162  const secure_vector<word>& y,
163  secure_vector<word>& ws) const;
164 
165  void mul_by(BigInt& x,
166  const secure_vector<word>& y,
167  secure_vector<word>& ws) const;
168 
169  void mul_by(BigInt& x, const BigInt& y,
170  secure_vector<word>& ws) const;
171 
172  BigInt sqr(const BigInt& x,
173  secure_vector<word>& ws) const;
174 
175  void square_this(BigInt& x,
176  secure_vector<word>& ws) const;
177 
178  BigInt inv_mod_p(const BigInt& x) const;
179 
180  private:
181  BigInt m_p;
182  BigInt m_r1;
183  BigInt m_r2;
184  BigInt m_r3;
185  word m_p_dash;
186  size_t m_p_words;
187  };
188 
189 }
190 
191 #endif
#define BOTAN_UNSTABLE_API
Definition: compiler.h:44
const BigInt & R2() const
Definition: monty.h:147
const BigInt & p() const
Definition: monty.h:145
size_t p_words() const
Definition: monty.h:152
void const_time_unpoison() const
Definition: monty.h:120
word p_dash() const
Definition: monty.h:150
Montgomery_Int(std::shared_ptr< const Montgomery_Params > params)
Definition: monty.h:28
int(* final)(unsigned char *, CTX *)
OID operator+(const OID &oid, uint32_t new_comp)
Definition: asn1_oid.cpp:122
const BigInt & repr() const
Definition: monty.h:70
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: bigint.h:1085
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
const BigInt & R1() const
Definition: monty.h:146
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
Definition: secmem.h:79
BigInt m_r3
Definition: curve_gfp.cpp:87
Definition: alg_id.cpp:13
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
const BigInt & R3() const
Definition: monty.h:148
BigInt m_r2
Definition: curve_gfp.cpp:87
BigInt m_p
Definition: pow_mod.cpp:108
bool operator==(const AlgorithmIdentifier &a1, const AlgorithmIdentifier &a2)
Definition: alg_id.cpp:65
bool operator!=(const Montgomery_Int &other) const
Definition: monty.h:52
void const_time_poison() const
Definition: monty.h:119
size_t m_p_words
Definition: curve_gfp.cpp:84
#define BOTAN_FUTURE_INTERNAL_HEADER(hdr)
Definition: compiler.h:136
word m_p_dash
Definition: curve_gfp.cpp:88