6070332b94397688307660033f85f8d76aad8e26
[gnuk/gnuk.git] / polarssl / include / polarssl / bignum.h
1 /**
2  * \file bignum.h
3  *
4  *  Copyright (C) 2006-2010, Brainspark B.V.
5  *
6  *  This file is part of PolarSSL (http://www.polarssl.org)
7  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  *  All rights reserved.
10  *
11  *  This program is free software; you can redistribute it and/or modify
12  *  it under the terms of the GNU General Public License as published by
13  *  the Free Software Foundation; either version 2 of the License, or
14  *  (at your option) any later version.
15  *
16  *  This program is distributed in the hope that it will be useful,
17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  *  GNU General Public License for more details.
20  *
21  *  You should have received a copy of the GNU General Public License along
22  *  with this program; if not, write to the Free Software Foundation, Inc.,
23  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
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       #if defined(POLARSSL_HAVE_LONGLONG)
61       typedef unsigned long long t_dbl;
62       #endif
63     #endif
64   #endif
65 #endif
66 #endif
67
68 /**
69  * \brief          MPI structure
70  */
71 typedef struct
72 {
73     int s;              /*!<  integer sign      */
74     int n;              /*!<  total # of limbs  */
75     t_int *p;           /*!<  pointer to limbs  */
76 }
77 mpi;
78
79 #ifdef __cplusplus
80 extern "C" {
81 #endif
82
83 /**
84  * \brief          Initialize one or more mpi
85  */
86 void mpi_init( mpi *X, ... );
87
88 /**
89  * \brief          Unallocate one or more mpi
90  */
91 void mpi_free( mpi *X, ... );
92
93 /**
94  * \brief          Enlarge to the specified number of limbs
95  *
96  * \param X        MPI to grow
97  * \param nblimbs  The target number of limbs
98  *
99  * \return         0 if successful,
100  *                 1 if memory allocation failed
101  */
102 int mpi_grow( mpi *X, int nblimbs );
103
104 /**
105  * \brief          Copy the contents of Y into X
106  *
107  * \param X        Destination MPI
108  * \param Y        Source MPI
109  *
110  * \return         0 if successful,
111  *                 1 if memory allocation failed
112  */
113 int mpi_copy( mpi *X, const mpi *Y );
114
115 /**
116  * \brief          Swap the contents of X and Y
117  *
118  * \param X        First MPI value
119  * \param Y        Second MPI value
120  */
121 void mpi_swap( mpi *X, mpi *Y );
122
123 /**
124  * \brief          Set value from integer
125  *
126  * \param X        MPI to set
127  * \param z        Value to use
128  *
129  * \return         0 if successful,
130  *                 1 if memory allocation failed
131  */
132 int mpi_lset( mpi *X, int z );
133
134 /**
135  * \brief          Return the number of least significant bits
136  *
137  * \param X        MPI to use
138  */
139 int mpi_lsb( const mpi *X );
140
141 /**
142  * \brief          Return the number of most significant bits
143  *
144  * \param X        MPI to use
145  */
146 int mpi_msb( const mpi *X );
147
148 /**
149  * \brief          Return the total size in bytes
150  *
151  * \param X        MPI to use
152  */
153 int mpi_size( const mpi *X );
154
155 /**
156  * \brief          Import from an ASCII string
157  *
158  * \param X        Destination MPI
159  * \param radix    Input numeric base
160  * \param s        Null-terminated string buffer
161  *
162  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
163  */
164 int mpi_read_string( mpi *X, int radix, const char *s );
165
166 /**
167  * \brief          Export into an ASCII string
168  *
169  * \param X        Source MPI
170  * \param radix    Output numeric base
171  * \param s        String buffer
172  * \param slen     String buffer size
173  *
174  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code.
175  *                 *slen is always updated to reflect the amount
176  *                 of data that has (or would have) been written.
177  *
178  * \note           Call this function with *slen = 0 to obtain the
179  *                 minimum required buffer size in *slen.
180  */
181 int mpi_write_string( const mpi *X, int radix, char *s, int *slen );
182
183 /**
184  * \brief          Read X from an opened file
185  *
186  * \param X        Destination MPI
187  * \param radix    Input numeric base
188  * \param fin      Input file handle
189  *
190  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
191  */
192 int mpi_read_file( mpi *X, int radix, FILE *fin );
193
194 /**
195  * \brief          Write X into an opened file, or stdout if fout is NULL
196  *
197  * \param p        Prefix, can be NULL
198  * \param X        Source MPI
199  * \param radix    Output numeric base
200  * \param fout     Output file handle (can be NULL)
201  *
202  * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
203  *
204  * \note           Set fout == NULL to print X on the console.
205  */
206 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
207
208 /**
209  * \brief          Import X from unsigned binary data, big endian
210  *
211  * \param X        Destination MPI
212  * \param buf      Input buffer
213  * \param buflen   Input buffer size
214  *
215  * \return         0 if successful,
216  *                 1 if memory allocation failed
217  */
218 int mpi_read_binary( mpi *X, const unsigned char *buf, int buflen );
219
220 /**
221  * \brief          Export X into unsigned binary data, big endian
222  *
223  * \param X        Source MPI
224  * \param buf      Output buffer
225  * \param buflen   Output buffer size
226  *
227  * \return         0 if successful,
228  *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
229  */
230 int mpi_write_binary( const mpi *X, unsigned char *buf, int buflen );
231
232 /**
233  * \brief          Left-shift: X <<= count
234  *
235  * \param X        MPI to shift
236  * \param count    Amount to shift
237  *
238  * \return         0 if successful,
239  *                 1 if memory allocation failed
240  */
241 int mpi_shift_l( mpi *X, int count );
242
243 /**
244  * \brief          Right-shift: X >>= count
245  *
246  * \param X        MPI to shift
247  * \param count    Amount to shift
248  *
249  * \return         0 if successful,
250  *                 1 if memory allocation failed
251  */
252 int mpi_shift_r( mpi *X, int count );
253
254 /**
255  * \brief          Compare unsigned values
256  *
257  * \param X        Left-hand MPI
258  * \param Y        Right-hand MPI
259  *
260  * \return         1 if |X| is greater than |Y|,
261  *                -1 if |X| is lesser  than |Y| or
262  *                 0 if |X| is equal to |Y|
263  */
264 int mpi_cmp_abs( const mpi *X, const mpi *Y );
265
266 /**
267  * \brief          Compare signed values
268  *
269  * \param X        Left-hand MPI
270  * \param Y        Right-hand MPI
271  *
272  * \return         1 if X is greater than Y,
273  *                -1 if X is lesser  than Y or
274  *                 0 if X is equal to Y
275  */
276 int mpi_cmp_mpi( const mpi *X, const mpi *Y );
277
278 /**
279  * \brief          Compare signed values
280  *
281  * \param X        Left-hand MPI
282  * \param z        The integer value to compare to
283  *
284  * \return         1 if X is greater than z,
285  *                -1 if X is lesser  than z or
286  *                 0 if X is equal to z
287  */
288 int mpi_cmp_int( const mpi *X, int z );
289
290 /**
291  * \brief          Unsigned addition: X = |A| + |B|
292  *
293  * \param X        Destination MPI
294  * \param A        Left-hand MPI
295  * \param B        Right-hand MPI
296  *
297  * \return         0 if successful,
298  *                 1 if memory allocation failed
299  */
300 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
301
302 /**
303  * \brief          Unsigned substraction: X = |A| - |B|
304  *
305  * \param X        Destination MPI
306  * \param A        Left-hand MPI
307  * \param B        Right-hand MPI
308  *
309  * \return         0 if successful,
310  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
311  */
312 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
313
314 /**
315  * \brief          Signed addition: X = A + B
316  *
317  * \param X        Destination MPI
318  * \param A        Left-hand MPI
319  * \param B        Right-hand MPI
320  *
321  * \return         0 if successful,
322  *                 1 if memory allocation failed
323  */
324 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
325
326 /**
327  * \brief          Signed substraction: X = A - B
328  *
329  * \param X        Destination MPI
330  * \param A        Left-hand MPI
331  * \param B        Right-hand MPI
332  *
333  * \return         0 if successful,
334  *                 1 if memory allocation failed
335  */
336 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
337
338 /**
339  * \brief          Signed addition: X = A + b
340  *
341  * \param X        Destination MPI
342  * \param A        Left-hand MPI
343  * \param b        The integer value to add
344  *
345  * \return         0 if successful,
346  *                 1 if memory allocation failed
347  */
348 int mpi_add_int( mpi *X, const mpi *A, int b );
349
350 /**
351  * \brief          Signed substraction: X = A - b
352  *
353  * \param X        Destination MPI
354  * \param A        Left-hand MPI
355  * \param b        The integer value to subtract
356  *
357  * \return         0 if successful,
358  *                 1 if memory allocation failed
359  */
360 int mpi_sub_int( mpi *X, const mpi *A, int b );
361
362 /**
363  * \brief          Baseline multiplication: X = A * B
364  *
365  * \param X        Destination MPI
366  * \param A        Left-hand MPI
367  * \param B        Right-hand MPI
368  *
369  * \return         0 if successful,
370  *                 1 if memory allocation failed
371  */
372 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
373
374 /**
375  * \brief          Baseline multiplication: X = A * b
376  *                 Note: b is an unsigned integer type, thus
377  *                 Negative values of b are ignored.
378  *
379  * \param X        Destination MPI
380  * \param A        Left-hand MPI
381  * \param b        The integer value to multiply with
382  *
383  * \return         0 if successful,
384  *                 1 if memory allocation failed
385  */
386 int mpi_mul_int( mpi *X, const mpi *A, t_int b );
387
388 /**
389  * \brief          Division by mpi: A = Q * B + R
390  *
391  * \param Q        Destination MPI for the quotient
392  * \param R        Destination MPI for the rest value
393  * \param A        Left-hand MPI
394  * \param B        Right-hand MPI
395  *
396  * \return         0 if successful,
397  *                 1 if memory allocation failed,
398  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
399  *
400  * \note           Either Q or R can be NULL.
401  */
402 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
403
404 /**
405  * \brief          Division by int: A = Q * b + R
406  *
407  * \param Q        Destination MPI for the quotient
408  * \param R        Destination MPI for the rest value
409  * \param A        Left-hand MPI
410  * \param b        Integer to divide by
411  *
412  * \return         0 if successful,
413  *                 1 if memory allocation failed,
414  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
415  *
416  * \note           Either Q or R can be NULL.
417  */
418 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, int b );
419
420 /**
421  * \brief          Modulo: R = A mod B
422  *
423  * \param R        Destination MPI for the rest value
424  * \param A        Left-hand MPI
425  * \param B        Right-hand MPI
426  *
427  * \return         0 if successful,
428  *                 1 if memory allocation failed,
429  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0,
430  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B < 0
431  */
432 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
433
434 /**
435  * \brief          Modulo: r = A mod b
436  *
437  * \param r        Destination t_int
438  * \param A        Left-hand MPI
439  * \param b        Integer to divide by
440  *
441  * \return         0 if successful,
442  *                 1 if memory allocation failed,
443  *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0,
444  *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if b < 0
445  */
446 int mpi_mod_int( t_int *r, const mpi *A, int b );
447
448 /**
449  * \brief          Sliding-window exponentiation: X = A^E mod N
450  *
451  * \param X        Destination MPI 
452  * \param A        Left-hand MPI
453  * \param E        Exponent MPI
454  * \param N        Modular MPI
455  * \param _RR      Speed-up MPI used for recalculations
456  *
457  * \return         0 if successful,
458  *                 1 if memory allocation failed,
459  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
460  *
461  * \note           _RR is used to avoid re-computing R*R mod N across
462  *                 multiple calls, which speeds up things a bit. It can
463  *                 be set to NULL if the extra performance is unneeded.
464  */
465 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
466
467 /**
468  * \brief          Greatest common divisor: G = gcd(A, B)
469  *
470  * \param G        Destination MPI
471  * \param A        Left-hand MPI
472  * \param B        Right-hand MPI
473  *
474  * \return         0 if successful,
475  *                 1 if memory allocation failed
476  */
477 int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
478
479 /**
480  * \brief          Modular inverse: X = A^-1 mod N
481  *
482  * \param X        Destination MPI
483  * \param A        Left-hand MPI
484  * \param N        Right-hand MPI
485  *
486  * \return         0 if successful,
487  *                 1 if memory allocation failed,
488  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
489                    POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
490  */
491 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
492
493 /**
494  * \brief          Miller-Rabin primality test
495  *
496  * \param X        MPI to check
497  * \param f_rng    RNG function
498  * \param p_rng    RNG parameter
499  *
500  * \return         0 if successful (probably prime),
501  *                 1 if memory allocation failed,
502  *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
503  */
504 int mpi_is_prime( mpi *X, unsigned char (*f_rng)(void *), void *p_rng );
505
506 /**
507  * \brief          Prime number generation
508  *
509  * \param X        Destination MPI
510  * \param nbits    Required size of X in bits
511  * \param dh_flag  If 1, then (X-1)/2 will be prime too
512  * \param f_rng    RNG function
513  * \param p_rng    RNG parameter
514  *
515  * \return         0 if successful (probably prime),
516  *                 1 if memory allocation failed,
517  *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
518  */
519 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
520                    unsigned char (*f_rng)(void *), void *p_rng );
521
522 /**
523  * \brief          Checkup routine
524  *
525  * \return         0 if successful, or 1 if the test failed
526  */
527 int mpi_self_test( int verbose );
528
529 #ifdef __cplusplus
530 }
531 #endif
532
533 #endif /* bignum.h */