Commit | Line | Data |
---|---|---|
80a47a2c TK |
1 | /** |
2 | * \file bignum.h | |
3 | * | |
4 | * Based on XySSL: Copyright (C) 2006-2008 Christophe Devine | |
5 | * | |
6 | * Copyright (C) 2009 Paul Bakker <polarssl_maintainer at polarssl dot org> | |
7 | * | |
8 | * This program is free software; you can redistribute it and/or modify | |
9 | * it under the terms of the GNU General Public License as published by | |
10 | * the Free Software Foundation; either version 2 of the License, or | |
11 | * (at your option) any later version. | |
12 | * | |
13 | * This program is distributed in the hope that it will be useful, | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | * GNU General Public License for more details. | |
17 | * | |
18 | * You should have received a copy of the GNU General Public License along | |
19 | * with this program; if not, write to the Free Software Foundation, Inc., | |
20 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | |
21 | */ | |
22 | ||
23 | /* $Cambridge: exim/src/src/pdkim/bignum.h,v 1.2 2009/06/10 07:34:05 tom Exp $ */ | |
24 | ||
25 | #ifndef POLARSSL_BIGNUM_H | |
26 | #define POLARSSL_BIGNUM_H | |
27 | ||
28 | #include <stdio.h> | |
29 | ||
30 | #define POLARSSL_ERR_MPI_FILE_IO_ERROR -0x0002 | |
31 | #define POLARSSL_ERR_MPI_BAD_INPUT_DATA -0x0004 | |
32 | #define POLARSSL_ERR_MPI_INVALID_CHARACTER -0x0006 | |
33 | #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL -0x0008 | |
34 | #define POLARSSL_ERR_MPI_NEGATIVE_VALUE -0x000A | |
35 | #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO -0x000C | |
36 | #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE -0x000E | |
37 | ||
38 | #define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup | |
39 | ||
40 | /* | |
41 | * Define the base integer type, architecture-wise | |
42 | */ | |
43 | #if defined(POLARSSL_HAVE_INT8) | |
44 | typedef unsigned char t_int; | |
45 | typedef unsigned short t_dbl; | |
46 | #else | |
47 | #if defined(POLARSSL_HAVE_INT16) | |
48 | typedef unsigned short t_int; | |
49 | typedef unsigned long t_dbl; | |
50 | #else | |
51 | typedef unsigned long t_int; | |
52 | #if defined(_MSC_VER) && defined(_M_IX86) | |
53 | typedef unsigned __int64 t_dbl; | |
54 | #else | |
55 | #if defined(__amd64__) || defined(__x86_64__) || \ | |
56 | defined(__ppc64__) || defined(__powerpc64__) || \ | |
57 | defined(__ia64__) || defined(__alpha__) | |
58 | typedef unsigned int t_dbl __attribute__((mode(TI))); | |
59 | #else | |
60 | typedef unsigned long long t_dbl; | |
61 | #endif | |
62 | #endif | |
63 | #endif | |
64 | #endif | |
65 | ||
66 | /** | |
67 | * \brief MPI structure | |
68 | */ | |
69 | typedef struct | |
70 | { | |
71 | int s; /*!< integer sign */ | |
72 | int n; /*!< total # of limbs */ | |
73 | t_int *p; /*!< pointer to limbs */ | |
74 | } | |
75 | mpi; | |
76 | ||
77 | #ifdef __cplusplus | |
78 | extern "C" { | |
79 | #endif | |
80 | ||
81 | /** | |
82 | * \brief Initialize one or more mpi | |
83 | */ | |
84 | void mpi_init( mpi *X, ... ); | |
85 | ||
86 | /** | |
87 | * \brief Unallocate one or more mpi | |
88 | */ | |
89 | void mpi_free( mpi *X, ... ); | |
90 | ||
91 | /** | |
92 | * \brief Enlarge to the specified number of limbs | |
93 | * | |
94 | * \return 0 if successful, | |
95 | * 1 if memory allocation failed | |
96 | */ | |
97 | int mpi_grow( mpi *X, int nblimbs ); | |
98 | ||
99 | /** | |
100 | * \brief Copy the contents of Y into X | |
101 | * | |
102 | * \return 0 if successful, | |
103 | * 1 if memory allocation failed | |
104 | */ | |
105 | int mpi_copy( mpi *X, mpi *Y ); | |
106 | ||
107 | /** | |
108 | * \brief Swap the contents of X and Y | |
109 | */ | |
110 | void mpi_swap( mpi *X, mpi *Y ); | |
111 | ||
112 | /** | |
113 | * \brief Set value from integer | |
114 | * | |
115 | * \return 0 if successful, | |
116 | * 1 if memory allocation failed | |
117 | */ | |
118 | int mpi_lset( mpi *X, int z ); | |
119 | ||
120 | /** | |
121 | * \brief Return the number of least significant bits | |
122 | */ | |
123 | int mpi_lsb( mpi *X ); | |
124 | ||
125 | /** | |
126 | * \brief Return the number of most significant bits | |
127 | */ | |
128 | int mpi_msb( mpi *X ); | |
129 | ||
130 | /** | |
131 | * \brief Return the total size in bytes | |
132 | */ | |
133 | int mpi_size( mpi *X ); | |
134 | ||
135 | /** | |
136 | * \brief Import from an ASCII string | |
137 | * | |
138 | * \param X destination mpi | |
139 | * \param radix input numeric base | |
140 | * \param s null-terminated string buffer | |
141 | * | |
142 | * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code | |
143 | */ | |
144 | int mpi_read_string( mpi *X, int radix, char *s ); | |
145 | ||
146 | /** | |
147 | * \brief Export into an ASCII string | |
148 | * | |
149 | * \param X source mpi | |
150 | * \param radix output numeric base | |
151 | * \param s string buffer | |
152 | * \param slen string buffer size | |
153 | * | |
154 | * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code | |
155 | * | |
156 | * \note Call this function with *slen = 0 to obtain the | |
157 | * minimum required buffer size in *slen. | |
158 | */ | |
159 | int mpi_write_string( mpi *X, int radix, char *s, int *slen ); | |
160 | ||
161 | /** | |
162 | * \brief Read X from an opened file | |
163 | * | |
164 | * \param X destination mpi | |
165 | * \param radix input numeric base | |
166 | * \param fin input file handle | |
167 | * | |
168 | * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code | |
169 | */ | |
170 | int mpi_read_file( mpi *X, int radix, FILE *fin ); | |
171 | ||
172 | /** | |
173 | * \brief Write X into an opened file, or stdout | |
174 | * | |
175 | * \param p prefix, can be NULL | |
176 | * \param X source mpi | |
177 | * \param radix output numeric base | |
178 | * \param fout output file handle | |
179 | * | |
180 | * \return 0 if successful, or an POLARSSL_ERR_MPI_XXX error code | |
181 | * | |
182 | * \note Set fout == NULL to print X on the console. | |
183 | */ | |
184 | int mpi_write_file( char *p, mpi *X, int radix, FILE *fout ); | |
185 | ||
186 | /** | |
187 | * \brief Import X from unsigned binary data, big endian | |
188 | * | |
189 | * \param X destination mpi | |
190 | * \param buf input buffer | |
191 | * \param buflen input buffer size | |
192 | * | |
193 | * \return 0 if successful, | |
194 | * 1 if memory allocation failed | |
195 | */ | |
196 | int mpi_read_binary( mpi *X, unsigned char *buf, int buflen ); | |
197 | ||
198 | /** | |
199 | * \brief Export X into unsigned binary data, big endian | |
200 | * | |
201 | * \param X source mpi | |
202 | * \param buf output buffer | |
203 | * \param buflen output buffer size | |
204 | * | |
205 | * \return 0 if successful, | |
206 | * POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough | |
207 | * | |
208 | * \note Call this function with *buflen = 0 to obtain the | |
209 | * minimum required buffer size in *buflen. | |
210 | */ | |
211 | int mpi_write_binary( mpi *X, unsigned char *buf, int buflen ); | |
212 | ||
213 | /** | |
214 | * \brief Left-shift: X <<= count | |
215 | * | |
216 | * \return 0 if successful, | |
217 | * 1 if memory allocation failed | |
218 | */ | |
219 | int mpi_shift_l( mpi *X, int count ); | |
220 | ||
221 | /** | |
222 | * \brief Right-shift: X >>= count | |
223 | * | |
224 | * \return 0 if successful, | |
225 | * 1 if memory allocation failed | |
226 | */ | |
227 | int mpi_shift_r( mpi *X, int count ); | |
228 | ||
229 | /** | |
230 | * \brief Compare unsigned values | |
231 | * | |
232 | * \return 1 if |X| is greater than |Y|, | |
233 | * -1 if |X| is lesser than |Y| or | |
234 | * 0 if |X| is equal to |Y| | |
235 | */ | |
236 | int mpi_cmp_abs( mpi *X, mpi *Y ); | |
237 | ||
238 | /** | |
239 | * \brief Compare signed values | |
240 | * | |
241 | * \return 1 if X is greater than Y, | |
242 | * -1 if X is lesser than Y or | |
243 | * 0 if X is equal to Y | |
244 | */ | |
245 | int mpi_cmp_mpi( mpi *X, mpi *Y ); | |
246 | ||
247 | /** | |
248 | * \brief Compare signed values | |
249 | * | |
250 | * \return 1 if X is greater than z, | |
251 | * -1 if X is lesser than z or | |
252 | * 0 if X is equal to z | |
253 | */ | |
254 | int mpi_cmp_int( mpi *X, int z ); | |
255 | ||
256 | /** | |
257 | * \brief Unsigned addition: X = |A| + |B| | |
258 | * | |
259 | * \return 0 if successful, | |
260 | * 1 if memory allocation failed | |
261 | */ | |
262 | int mpi_add_abs( mpi *X, mpi *A, mpi *B ); | |
263 | ||
264 | /** | |
265 | * \brief Unsigned substraction: X = |A| - |B| | |
266 | * | |
267 | * \return 0 if successful, | |
268 | * POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A | |
269 | */ | |
270 | int mpi_sub_abs( mpi *X, mpi *A, mpi *B ); | |
271 | ||
272 | /** | |
273 | * \brief Signed addition: X = A + B | |
274 | * | |
275 | * \return 0 if successful, | |
276 | * 1 if memory allocation failed | |
277 | */ | |
278 | int mpi_add_mpi( mpi *X, mpi *A, mpi *B ); | |
279 | ||
280 | /** | |
281 | * \brief Signed substraction: X = A - B | |
282 | * | |
283 | * \return 0 if successful, | |
284 | * 1 if memory allocation failed | |
285 | */ | |
286 | int mpi_sub_mpi( mpi *X, mpi *A, mpi *B ); | |
287 | ||
288 | /** | |
289 | * \brief Signed addition: X = A + b | |
290 | * | |
291 | * \return 0 if successful, | |
292 | * 1 if memory allocation failed | |
293 | */ | |
294 | int mpi_add_int( mpi *X, mpi *A, int b ); | |
295 | ||
296 | /** | |
297 | * \brief Signed substraction: X = A - b | |
298 | * | |
299 | * \return 0 if successful, | |
300 | * 1 if memory allocation failed | |
301 | */ | |
302 | int mpi_sub_int( mpi *X, mpi *A, int b ); | |
303 | ||
304 | /** | |
305 | * \brief Baseline multiplication: X = A * B | |
306 | * | |
307 | * \return 0 if successful, | |
308 | * 1 if memory allocation failed | |
309 | */ | |
310 | int mpi_mul_mpi( mpi *X, mpi *A, mpi *B ); | |
311 | ||
312 | /** | |
313 | * \brief Baseline multiplication: X = A * b | |
314 | * | |
315 | * \return 0 if successful, | |
316 | * 1 if memory allocation failed | |
317 | */ | |
318 | int mpi_mul_int( mpi *X, mpi *A, t_int b ); | |
319 | ||
320 | /** | |
321 | * \brief Division by mpi: A = Q * B + R | |
322 | * | |
323 | * \return 0 if successful, | |
324 | * 1 if memory allocation failed, | |
325 | * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0 | |
326 | * | |
327 | * \note Either Q or R can be NULL. | |
328 | */ | |
329 | int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B ); | |
330 | ||
331 | /** | |
332 | * \brief Division by int: A = Q * b + R | |
333 | * | |
334 | * \return 0 if successful, | |
335 | * 1 if memory allocation failed, | |
336 | * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0 | |
337 | * | |
338 | * \note Either Q or R can be NULL. | |
339 | */ | |
340 | int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b ); | |
341 | ||
342 | /** | |
343 | * \brief Modulo: R = A mod B | |
344 | * | |
345 | * \return 0 if successful, | |
346 | * 1 if memory allocation failed, | |
347 | * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0 | |
348 | */ | |
349 | int mpi_mod_mpi( mpi *R, mpi *A, mpi *B ); | |
350 | ||
351 | /** | |
352 | * \brief Modulo: r = A mod b | |
353 | * | |
354 | * \return 0 if successful, | |
355 | * 1 if memory allocation failed, | |
356 | * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0 | |
357 | */ | |
358 | int mpi_mod_int( t_int *r, mpi *A, int b ); | |
359 | ||
360 | /** | |
361 | * \brief Sliding-window exponentiation: X = A^E mod N | |
362 | * | |
363 | * \return 0 if successful, | |
364 | * 1 if memory allocation failed, | |
365 | * POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even | |
366 | * | |
367 | * \note _RR is used to avoid re-computing R*R mod N across | |
368 | * multiple calls, which speeds up things a bit. It can | |
369 | * be set to NULL if the extra performance is unneeded. | |
370 | */ | |
371 | int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR ); | |
372 | ||
373 | /** | |
374 | * \brief Greatest common divisor: G = gcd(A, B) | |
375 | * | |
376 | * \return 0 if successful, | |
377 | * 1 if memory allocation failed | |
378 | */ | |
379 | int mpi_gcd( mpi *G, mpi *A, mpi *B ); | |
380 | ||
381 | /** | |
382 | * \brief Modular inverse: X = A^-1 mod N | |
383 | * | |
384 | * \return 0 if successful, | |
385 | * 1 if memory allocation failed, | |
386 | * POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil | |
387 | * POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N | |
388 | */ | |
389 | int mpi_inv_mod( mpi *X, mpi *A, mpi *N ); | |
390 | ||
391 | #ifdef __cplusplus | |
392 | } | |
393 | #endif | |
394 | ||
395 | #endif /* bignum.h */ |