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 *  All rights reserved.
9 *
10 *  Redistribution and use in source and binary forms, with or without
11 *  modification, are permitted provided that the following conditions
12 *  are met:
13 *
14 *    * Redistributions of source code must retain the above copyright
15 *      notice, this list of conditions and the following disclaimer.
16 *    * Redistributions in binary form must reproduce the above copyright
17 *      notice, this list of conditions and the following disclaimer in the
18 *      documentation and/or other materials provided with the distribution.
19 *    * Neither the names of PolarSSL or XySSL nor the names of its contributors
20 *      may be used to endorse or promote products derived from this software
21 *      without specific prior written permission.
22 *
23 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 *  TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 *  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 *  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 *  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 *  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35#ifndef POLARSSL_BIGNUM_H
36#define POLARSSL_BIGNUM_H
37
38#include <stdio.h>
39
40#define POLARSSL_ERR_MPI_FILE_IO_ERROR                     -0x0002
41#define POLARSSL_ERR_MPI_BAD_INPUT_DATA                    -0x0004
42#define POLARSSL_ERR_MPI_INVALID_CHARACTER                 -0x0006
43#define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL                  -0x0008
44#define POLARSSL_ERR_MPI_NEGATIVE_VALUE                    -0x000A
45#define POLARSSL_ERR_MPI_DIVISION_BY_ZERO                  -0x000C
46#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE                    -0x000E
47
48#define MPI_CHK(f) if( ( ret = f ) != 0 ) goto cleanup
49
50/*
51 * Define the base integer type, architecture-wise
52 */
53#if defined(POLARSSL_HAVE_INT8)
54typedef unsigned char  t_int;
55typedef unsigned short t_dbl;
56#else
57#if defined(POLARSSL_HAVE_INT16)
58typedef unsigned short t_int;
59typedef unsigned long  t_dbl;
60#else
61  typedef unsigned long t_int;
62  #if defined(_MSC_VER) && defined(_M_IX86)
63  typedef unsigned __int64 t_dbl;
64  #else
65    #if defined(__amd64__) || defined(__x86_64__)    || \
66        defined(__ppc64__) || defined(__powerpc64__) || \
67        defined(__ia64__)  || defined(__alpha__)
68    typedef unsigned int t_dbl __attribute__((mode(TI)));
69    #else
70    typedef unsigned long long t_dbl;
71    #endif
72  #endif
73#endif
74#endif
75
76/**
77 * \brief          MPI structure
78 */
79typedef struct
80{
81    int s;              /*!<  integer sign      */
82    int n;              /*!<  total # of limbs  */
83    t_int *p;           /*!<  pointer to limbs  */
84}
85mpi;
86
87#ifdef __cplusplus
88extern "C" {
89#endif
90
91/**
92 * \brief          Initialize one or more mpi
93 */
94void mpi_init( mpi *X, ... );
95
96/**
97 * \brief          Unallocate one or more mpi
98 */
99void mpi_free( mpi *X, ... );
100
101/**
102 * \brief          Enlarge to the specified number of limbs
103 *
104 * \return         0 if successful,
105 *                 1 if memory allocation failed
106 */
107int mpi_grow( mpi *X, int nblimbs );
108
109/**
110 * \brief          Copy the contents of Y into X
111 *
112 * \return         0 if successful,
113 *                 1 if memory allocation failed
114 */
115int mpi_copy( mpi *X, mpi *Y );
116
117/**
118 * \brief          Swap the contents of X and Y
119 */
120void mpi_swap( mpi *X, mpi *Y );
121
122/**
123 * \brief          Set value from integer
124 *
125 * \return         0 if successful,
126 *                 1 if memory allocation failed
127 */
128int mpi_lset( mpi *X, int z );
129
130/**
131 * \brief          Return the number of least significant bits
132 */
133int mpi_lsb( mpi *X );
134
135/**
136 * \brief          Return the number of most significant bits
137 */
138int mpi_msb( mpi *X );
139
140/**
141 * \brief          Return the total size in bytes
142 */
143int mpi_size( mpi *X );
144
145/**
146 * \brief          Import from an ASCII string
147 *
148 * \param X        destination mpi
149 * \param radix    input numeric base
150 * \param s        null-terminated string buffer
151 *
152 * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
153 */
154int mpi_read_string( mpi *X, int radix, char *s );
155
156/**
157 * \brief          Export into an ASCII string
158 *
159 * \param X        source mpi
160 * \param radix    output numeric base
161 * \param s        string buffer
162 * \param slen     string buffer size
163 *
164 * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
165 *
166 * \note           Call this function with *slen = 0 to obtain the
167 *                 minimum required buffer size in *slen.
168 */
169int mpi_write_string( mpi *X, int radix, char *s, int *slen );
170
171/**
172 * \brief          Read X from an opened file
173 *
174 * \param X        destination mpi
175 * \param radix    input numeric base
176 * \param fin      input file handle
177 *
178 * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
179 */
180int mpi_read_file( mpi *X, int radix, FILE *fin );
181
182/**
183 * \brief          Write X into an opened file, or stdout
184 *
185 * \param p        prefix, can be NULL
186 * \param X        source mpi
187 * \param radix    output numeric base
188 * \param fout     output file handle
189 *
190 * \return         0 if successful, or an POLARSSL_ERR_MPI_XXX error code
191 *
192 * \note           Set fout == NULL to print X on the console.
193 */
194int mpi_write_file( char *p, mpi *X, int radix, FILE *fout );
195
196/**
197 * \brief          Import X from unsigned binary data, big endian
198 *
199 * \param X        destination mpi
200 * \param buf      input buffer
201 * \param buflen   input buffer size
202 *
203 * \return         0 if successful,
204 *                 1 if memory allocation failed
205 */
206int mpi_read_binary( mpi *X, unsigned char *buf, int buflen );
207
208/**
209 * \brief          Export X into unsigned binary data, big endian
210 *
211 * \param X        source mpi
212 * \param buf      output buffer
213 * \param buflen   output buffer size
214 *
215 * \return         0 if successful,
216 *                 POLARSSL_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
217 *
218 * \note           Call this function with *buflen = 0 to obtain the
219 *                 minimum required buffer size in *buflen.
220 */
221int mpi_write_binary( mpi *X, unsigned char *buf, int buflen );
222
223/**
224 * \brief          Left-shift: X <<= count
225 *
226 * \return         0 if successful,
227 *                 1 if memory allocation failed
228 */
229int mpi_shift_l( mpi *X, int count );
230
231/**
232 * \brief          Right-shift: X >>= count
233 *
234 * \return         0 if successful,
235 *                 1 if memory allocation failed
236 */
237int mpi_shift_r( mpi *X, int count );
238
239/**
240 * \brief          Compare unsigned values
241 *
242 * \return         1 if |X| is greater than |Y|,
243 *                -1 if |X| is lesser  than |Y| or
244 *                 0 if |X| is equal to |Y|
245 */
246int mpi_cmp_abs( mpi *X, mpi *Y );
247
248/**
249 * \brief          Compare signed values
250 *
251 * \return         1 if X is greater than Y,
252 *                -1 if X is lesser  than Y or
253 *                 0 if X is equal to Y
254 */
255int mpi_cmp_mpi( mpi *X, mpi *Y );
256
257/**
258 * \brief          Compare signed values
259 *
260 * \return         1 if X is greater than z,
261 *                -1 if X is lesser  than z or
262 *                 0 if X is equal to z
263 */
264int mpi_cmp_int( mpi *X, int z );
265
266/**
267 * \brief          Unsigned addition: X = |A| + |B|
268 *
269 * \return         0 if successful,
270 *                 1 if memory allocation failed
271 */
272int mpi_add_abs( mpi *X, mpi *A, mpi *B );
273
274/**
275 * \brief          Unsigned substraction: X = |A| - |B|
276 *
277 * \return         0 if successful,
278 *                 POLARSSL_ERR_MPI_NEGATIVE_VALUE if B is greater than A
279 */
280int mpi_sub_abs( mpi *X, mpi *A, mpi *B );
281
282/**
283 * \brief          Signed addition: X = A + B
284 *
285 * \return         0 if successful,
286 *                 1 if memory allocation failed
287 */
288int mpi_add_mpi( mpi *X, mpi *A, mpi *B );
289
290/**
291 * \brief          Signed substraction: X = A - B
292 *
293 * \return         0 if successful,
294 *                 1 if memory allocation failed
295 */
296int mpi_sub_mpi( mpi *X, mpi *A, mpi *B );
297
298/**
299 * \brief          Signed addition: X = A + b
300 *
301 * \return         0 if successful,
302 *                 1 if memory allocation failed
303 */
304int mpi_add_int( mpi *X, mpi *A, int b );
305
306/**
307 * \brief          Signed substraction: X = A - b
308 *
309 * \return         0 if successful,
310 *                 1 if memory allocation failed
311 */
312int mpi_sub_int( mpi *X, mpi *A, int b );
313
314/**
315 * \brief          Baseline multiplication: X = A * B
316 *
317 * \return         0 if successful,
318 *                 1 if memory allocation failed
319 */
320int mpi_mul_mpi( mpi *X, mpi *A, mpi *B );
321
322/**
323 * \brief          Baseline multiplication: X = A * b
324 *
325 * \return         0 if successful,
326 *                 1 if memory allocation failed
327 */
328int mpi_mul_int( mpi *X, mpi *A, t_int b );
329
330/**
331 * \brief          Division by mpi: A = Q * B + R
332 *
333 * \return         0 if successful,
334 *                 1 if memory allocation failed,
335 *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
336 *
337 * \note           Either Q or R can be NULL.
338 */
339int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B );
340
341/**
342 * \brief          Division by int: A = Q * b + R
343 *
344 * \return         0 if successful,
345 *                 1 if memory allocation failed,
346 *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
347 *
348 * \note           Either Q or R can be NULL.
349 */
350int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b );
351
352/**
353 * \brief          Modulo: R = A mod B
354 *
355 * \return         0 if successful,
356 *                 1 if memory allocation failed,
357 *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if B == 0
358 */
359int mpi_mod_mpi( mpi *R, mpi *A, mpi *B );
360
361/**
362 * \brief          Modulo: r = A mod b
363 *
364 * \return         0 if successful,
365 *                 1 if memory allocation failed,
366 *                 POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
367 */
368int mpi_mod_int( t_int *r, mpi *A, int b );
369
370/**
371 * \brief          Sliding-window exponentiation: X = A^E mod N
372 *
373 * \return         0 if successful,
374 *                 1 if memory allocation failed,
375 *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or even
376 *
377 * \note           _RR is used to avoid re-computing R*R mod N across
378 *                 multiple calls, which speeds up things a bit. It can
379 *                 be set to NULL if the extra performance is unneeded.
380 */
381int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR );
382
383/**
384 * \brief          Greatest common divisor: G = gcd(A, B)
385 *
386 * \return         0 if successful,
387 *                 1 if memory allocation failed
388 */
389int mpi_gcd( mpi *G, mpi *A, mpi *B );
390
391/**
392 * \brief          Modular inverse: X = A^-1 mod N
393 *
394 * \return         0 if successful,
395 *                 1 if memory allocation failed,
396 *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if N is negative or nil
397 *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N
398 */
399int mpi_inv_mod( mpi *X, mpi *A, mpi *N );
400
401/**
402 * \brief          Miller-Rabin primality test
403 *
404 * \return         0 if successful (probably prime),
405 *                 1 if memory allocation failed,
406 *                 POLARSSL_ERR_MPI_NOT_ACCEPTABLE if X is not prime
407 */
408int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng );
409
410/**
411 * \brief          Prime number generation
412 *
413 * \param X        destination mpi
414 * \param nbits    required size of X in bits
415 * \param dh_flag  if 1, then (X-1)/2 will be prime too
416 * \param f_rng    RNG function
417 * \param p_rng    RNG parameter
418 *
419 * \return         0 if successful (probably prime),
420 *                 1 if memory allocation failed,
421 *                 POLARSSL_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
422 */
423int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
424                   int (*f_rng)(void *), void *p_rng );
425
426/**
427 * \brief          Checkup routine
428 *
429 * \return         0 if successful, or 1 if the test failed
430 */
431int mpi_self_test( int verbose );
432
433#ifdef __cplusplus
434}
435#endif
436
437#endif /* bignum.h */
438