Botan  2.7.0
Crypto and TLS for C++11
mp_core.h
Go to the documentation of this file.
1 /*
2 * MPI Algorithms
3 * (C) 1999-2010 Jack Lloyd
4 * 2006 Luca Piccarreta
5 * 2016 Matthias Gierlings
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9 
10 #ifndef BOTAN_MP_CORE_OPS_H_
11 #define BOTAN_MP_CORE_OPS_H_
12 
13 #include <botan/types.h>
14 
15 namespace Botan {
16 
17 const word MP_WORD_MASK = ~static_cast<word>(0);
18 const word MP_WORD_TOP_BIT = static_cast<word>(1) << (8*sizeof(word) - 1);
20 
21 /*
22 * If cond == 0, does nothing.
23 * If cond > 0, swaps x[0:size] with y[0:size]
24 * Runs in constant time
25 */
27 void bigint_cnd_swap(word cnd, word x[], word y[], size_t size);
28 
29 /*
30 * If cond > 0 adds x[0:size] and y[0:size] and returns carry
31 * Runs in constant time
32 */
34 word bigint_cnd_add(word cnd, word x[], const word y[], size_t size);
35 
36 /*
37 * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
38 * Runs in constant time
39 */
41 word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
42 
43 /*
44 * Equivalent to
45 * bigint_cnd_add( mask, x, y, size);
46 * bigint_cnd_sub(~mask, x, y, size);
47 *
48 * Mask must be either 0 or all 1 bits
49 */
50 void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size);
51 
52 /*
53 * 2s complement absolute value
54 * If cond > 0 sets x to ~x + 1
55 * Runs in constant time
56 */
58 void bigint_cnd_abs(word cnd, word x[], size_t size);
59 
60 /**
61 * Two operand addition
62 * @param x the first operand (and output)
63 * @param x_size size of x
64 * @param y the second operand
65 * @param y_size size of y (must be >= x_size)
66 */
67 void bigint_add2(word x[], size_t x_size,
68  const word y[], size_t y_size);
69 
70 /**
71 * Three operand addition
72 */
73 void bigint_add3(word z[],
74  const word x[], size_t x_size,
75  const word y[], size_t y_size);
76 
77 /**
78 * Two operand addition with carry out
79 */
80 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size);
81 
82 /**
83 * Three operand addition with carry out
84 */
85 word bigint_add3_nc(word z[],
86  const word x[], size_t x_size,
87  const word y[], size_t y_size);
88 
89 /**
90 * Two operand subtraction
91 */
92 word bigint_sub2(word x[], size_t x_size,
93  const word y[], size_t y_size);
94 
95 /**
96 * Two operand subtraction, x = y - x; assumes y >= x
97 */
98 void bigint_sub2_rev(word x[], const word y[], size_t y_size);
99 
100 /**
101 * Three operand subtraction
102 */
103 word bigint_sub3(word z[],
104  const word x[], size_t x_size,
105  const word y[], size_t y_size);
106 
107 /**
108 * Return abs(x-y), ie if x >= y, then compute z = x - y
109 * Otherwise compute z = y - x
110 * No borrow is possible since the result is always >= 0
111 *
112 * Returns 1 if x >= y or 0 if x < y
113 * @param z output array of at least N words
114 * @param x input array of N words
115 * @param y input array of N words
116 * @param N length of x and y
117 * @param ws array of at least 2*N words
118 */
119 word bigint_sub_abs(word z[],
120  const word x[], const word y[], size_t N,
121  word ws[]);
122 
123 /*
124 * Shift Operations
125 */
126 void bigint_shl1(word x[], size_t x_size,
127  size_t word_shift, size_t bit_shift);
128 
129 void bigint_shr1(word x[], size_t x_size,
130  size_t word_shift, size_t bit_shift);
131 
132 void bigint_shl2(word y[], const word x[], size_t x_size,
133  size_t word_shift, size_t bit_shift);
134 
135 void bigint_shr2(word y[], const word x[], size_t x_size,
136  size_t word_shift, size_t bit_shift);
137 
138 /*
139 * Linear Multiply
140 */
141 void bigint_linmul2(word x[], size_t x_size, word y);
142 void bigint_linmul3(word z[], const word x[], size_t x_size, word y);
143 
144 /**
145 * Montgomery Reduction
146 * @param z integer to reduce, of size exactly 2*(p_size+1).
147  Output is in the first p_size+1 words, higher
148  words are set to zero.
149 * @param p modulus
150 * @param p_size size of p
151 * @param p_dash Montgomery value
152 * @param workspace array of at least 2*(p_size+1) words
153 * @param ws_size size of workspace in words
154 */
155 void bigint_monty_redc(word z[],
156  const word p[], size_t p_size,
157  word p_dash,
158  word workspace[],
159  size_t ws_size);
160 
161 /**
162 * Compare x and y returning early
163 */
164 int32_t bigint_cmp(const word x[], size_t x_size,
165  const word y[], size_t y_size);
166 
167 /**
168 * Compute ((n1<<bits) + n0) / d
169 */
170 word bigint_divop(word n1, word n0, word d);
171 
172 /**
173 * Compute ((n1<<bits) + n0) % d
174 */
175 word bigint_modop(word n1, word n0, word d);
176 
177 /*
178 * Comba Multiplication / Squaring
179 */
180 void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
181 void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
182 void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
183 void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
184 void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
185 void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
186 
187 void bigint_comba_sqr4(word out[8], const word in[4]);
188 void bigint_comba_sqr6(word out[12], const word in[6]);
189 void bigint_comba_sqr8(word out[16], const word in[8]);
190 void bigint_comba_sqr9(word out[18], const word in[9]);
191 void bigint_comba_sqr16(word out[32], const word in[16]);
192 void bigint_comba_sqr24(word out[48], const word in[24]);
193 
194 /*
195 * High Level Multiplication/Squaring Interfaces
196 */
197 
198 void bigint_mul(word z[], size_t z_size,
199  const word x[], size_t x_size, size_t x_sw,
200  const word y[], size_t y_size, size_t y_sw,
201  word workspace[], size_t ws_size);
202 
203 void bigint_sqr(word z[], size_t z_size,
204  const word x[], size_t x_size, size_t x_sw,
205  word workspace[], size_t ws_size);
206 
207 }
208 
209 #endif
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:359
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.cpp:227
void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
Definition: mp_core.cpp:95
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:434
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:456
void bigint_cnd_abs(word cnd, word x[], size_t size)
Definition: mp_core.cpp:123
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:204
void bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.cpp:300
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:161
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
Definition: mp_core.cpp:22
word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
Definition: mp_core.cpp:39
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition: mp_comba.cpp:50
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:276
word bigint_divop(word n1, word n0, word d)
Definition: mp_core.cpp:482
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
Definition: mp_comba.cpp:474
#define BOTAN_TEST_API
Definition: compiler.h:41
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:352
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
Definition: mp_comba.cpp:1535
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.cpp:318
void bigint_comba_sqr16(word z[32], const word x[16])
Definition: mp_comba.cpp:598
void bigint_comba_sqr24(word z[48], const word x[24])
Definition: mp_comba.cpp:1132
word bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.cpp:242
word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
Definition: mp_core.cpp:69
word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:138
Definition: alg_id.cpp:13
void bigint_comba_sqr9(word z[18], const word x[9])
Definition: mp_comba.cpp:386
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:293
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:111
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:414
const word MP_WORD_MASK
Definition: mp_core.h:17
void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.cpp:336
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
Definition: mp_comba.cpp:283
const word MP_WORD_MAX
Definition: mp_core.h:19
void bigint_comba_sqr8(word z[16], const word x[8])
Definition: mp_comba.cpp:208
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:186
void bigint_comba_mul16(word z[32], const word x[16], const word y[16])
Definition: mp_comba.cpp:805
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
Definition: mp_comba.cpp:141
void bigint_comba_sqr4(word z[8], const word x[4])
Definition: mp_comba.cpp:17
void bigint_comba_sqr6(word z[12], const word x[6])
Definition: mp_comba.cpp:89
const word MP_WORD_TOP_BIT
Definition: mp_core.h:18
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.cpp:194
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.cpp:515