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