]> git.zerfleddert.de Git - proxmark3-svn/blame - common/mbedtls/bignum.c
projects / proxmark3-svn / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Update cmdlft55xx.c
[proxmark3-svn] / common / mbedtls / bignum.c
CommitLineData
700d8687
OM		 1/*
2 * Multi-precision integer library
3 *
4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
5 * SPDX-License-Identifier: GPL-2.0
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * This file is part of mbed TLS (https://tls.mbed.org)
22 */
23
24/*
25 * The following sources were referenced in the design of this Multi-precision
26 * Integer library:
27 *
28 * [1] Handbook of Applied Cryptography - 1997
29 * Menezes, van Oorschot and Vanstone
30 *
31 * [2] Multi-Precision Math
32 * Tom St Denis
33 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
34 *
35 * [3] GNU Multi-Precision Arithmetic Library
36 * https://gmplib.org/manual/index.html
37 *
38 */
39
40#if !defined(MBEDTLS_CONFIG_FILE)
41#include "mbedtls/config.h"
42#else
43#include MBEDTLS_CONFIG_FILE
44#endif
45
46#if defined(MBEDTLS_BIGNUM_C)
47
48#include "mbedtls/bignum.h"
49#include "mbedtls/bn_mul.h"
50#include "mbedtls/platform_util.h"
51
52#include <string.h>
53
54#if defined(MBEDTLS_PLATFORM_C)
55#include "mbedtls/platform.h"
56#else
57#include <stdio.h>
58#include <stdlib.h>
59#define mbedtls_printf printf
60#define mbedtls_calloc calloc
61#define mbedtls_free free
62#endif
63
64#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
65#define biL (ciL << 3) /* bits in limb */
66#define biH (ciL << 2) /* half limb size */
67
68#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
69
70/*
71 * Convert between bits/chars and number of limbs
72 * Divide first in order to avoid potential overflows
73 */
74#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
75#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
76
77/* Implementation that should never be optimized out by the compiler */
78static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
79{
80 mbedtls_platform_zeroize( v, ciL * n );
81}
82
83/*
84 * Initialize one MPI
85 */
86void mbedtls_mpi_init( mbedtls_mpi *X )
87{
88 if( X == NULL )
89 return;
90
91 X->s = 1;
92 X->n = 0;
93 X->p = NULL;
94}
95
96/*
97 * Unallocate one MPI
98 */
99void mbedtls_mpi_free( mbedtls_mpi *X )
100{
101 if( X == NULL )
102 return;
103
104 if( X->p != NULL )
105 {
106 mbedtls_mpi_zeroize( X->p, X->n );
107 mbedtls_free( X->p );
108 }
109
110 X->s = 1;
111 X->n = 0;
112 X->p = NULL;
113}
114
115/*
116 * Enlarge to the specified number of limbs
117 */
118int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
119{
120 mbedtls_mpi_uint *p;
121
122 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
123 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
124
125 if( X->n < nblimbs )
126 {
127 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
128 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
129
130 if( X->p != NULL )
131 {
132 memcpy( p, X->p, X->n * ciL );
133 mbedtls_mpi_zeroize( X->p, X->n );
134 mbedtls_free( X->p );
135 }
136
137 X->n = nblimbs;
138 X->p = p;
139 }
140
141 return( 0 );
142}
143
144/*
145 * Resize down as much as possible,
146 * while keeping at least the specified number of limbs
147 */
148int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
149{
150 mbedtls_mpi_uint *p;
151 size_t i;
152
153 /* Actually resize up in this case */
154 if( X->n <= nblimbs )
155 return( mbedtls_mpi_grow( X, nblimbs ) );
156
157 for( i = X->n - 1; i > 0; i-- )
158 if( X->p[i] != 0 )
159 break;
160 i++;
161
162 if( i < nblimbs )
163 i = nblimbs;
164
165 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
166 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
167
168 if( X->p != NULL )
169 {
170 memcpy( p, X->p, i * ciL );
171 mbedtls_mpi_zeroize( X->p, X->n );
172 mbedtls_free( X->p );
173 }
174
175 X->n = i;
176 X->p = p;
177
178 return( 0 );
179}
180
181/*
182 * Copy the contents of Y into X
183 */
184int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
185{
186 int ret = 0;
187 size_t i;
188
189 if( X == Y )
190 return( 0 );
191
192 if( Y->p == NULL )
193 {
194 mbedtls_mpi_free( X );
195 return( 0 );
196 }
197
198 for( i = Y->n - 1; i > 0; i-- )
199 if( Y->p[i] != 0 )
200 break;
201 i++;
202
203 X->s = Y->s;
204
205 if( X->n < i )
206 {
207 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
208 }
209 else
210 {
211 memset( X->p + i, 0, ( X->n - i ) * ciL );
212 }
213
214 memcpy( X->p, Y->p, i * ciL );
215
216cleanup:
217
218 return( ret );
219}
220
221/*
222 * Swap the contents of X and Y
223 */
224void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
225{
226 mbedtls_mpi T;
227
228 memcpy( &T, X, sizeof( mbedtls_mpi ) );
229 memcpy( X, Y, sizeof( mbedtls_mpi ) );
230 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
231}
232
233/*
234 * Conditionally assign X = Y, without leaking information
235 * about whether the assignment was made or not.
236 * (Leaking information about the respective sizes of X and Y is ok however.)
237 */
238int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
239{
240 int ret = 0;
241 size_t i;
242
243 /* make sure assign is 0 or 1 in a time-constant manner */
244 assign = (assign | (unsigned char)-assign) >> 7;
245
246 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
247
248 X->s = X->s * ( 1 - assign ) + Y->s * assign;
249
250 for( i = 0; i < Y->n; i++ )
251 X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
252
253 for( ; i < X->n; i++ )
254 X->p[i] *= ( 1 - assign );
255
256cleanup:
257 return( ret );
258}
259
260/*
261 * Conditionally swap X and Y, without leaking information
262 * about whether the swap was made or not.
263 * Here it is not ok to simply swap the pointers, which whould lead to
264 * different memory access patterns when X and Y are used afterwards.
265 */
266int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
267{
268 int ret, s;
269 size_t i;
270 mbedtls_mpi_uint tmp;
271
272 if( X == Y )
273 return( 0 );
274
275 /* make sure swap is 0 or 1 in a time-constant manner */
276 swap = (swap | (unsigned char)-swap) >> 7;
277
278 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
279 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
280
281 s = X->s;
282 X->s = X->s * ( 1 - swap ) + Y->s * swap;
283 Y->s = Y->s * ( 1 - swap ) + s * swap;
284
285
286 for( i = 0; i < X->n; i++ )
287 {
288 tmp = X->p[i];
289 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
290 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
291 }
292
293cleanup:
294 return( ret );
295}
296
297/*
298 * Set value from integer
299 */
300int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
301{
302 int ret;
303
304 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
305 memset( X->p, 0, X->n * ciL );
306
307 X->p[0] = ( z < 0 ) ? -z : z;
308 X->s = ( z < 0 ) ? -1 : 1;
309
310cleanup:
311
312 return( ret );
313}
314
315/*
316 * Get a specific bit
317 */
318int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
319{
320 if( X->n * biL <= pos )
321 return( 0 );
322
323 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
324}
325
326/*
327 * Set a bit to a specific value of 0 or 1
328 */
329int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
330{
331 int ret = 0;
332 size_t off = pos / biL;
333 size_t idx = pos % biL;
334
335 if( val != 0 && val != 1 )
336 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
337
338 if( X->n * biL <= pos )
339 {
340 if( val == 0 )
341 return( 0 );
342
343 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
344 }
345
346 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
347 X->p[off] |= (mbedtls_mpi_uint) val << idx;
348
349cleanup:
350
351 return( ret );
352}
353
354/*
355 * Return the number of less significant zero-bits
356 */
357size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
358{
359 size_t i, j, count = 0;
360
361 for( i = 0; i < X->n; i++ )
362 for( j = 0; j < biL; j++, count++ )
363 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
364 return( count );
365
366 return( 0 );
367}
368
369/*
370 * Count leading zero bits in a given integer
371 */
372static size_t mbedtls_clz( const mbedtls_mpi_uint x )
373{
374 size_t j;
375 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
376
377 for( j = 0; j < biL; j++ )
378 {
379 if( x & mask ) break;
380
381 mask >>= 1;
382 }
383
384 return j;
385}
386
387/*
388 * Return the number of bits
389 */
390size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
391{
392 size_t i, j;
393
394 if( X->n == 0 )
395 return( 0 );
396
397 for( i = X->n - 1; i > 0; i-- )
398 if( X->p[i] != 0 )
399 break;
400
401 j = biL - mbedtls_clz( X->p[i] );
402
403 return( ( i * biL ) + j );
404}
405
406/*
407 * Return the total size in bytes
408 */
409size_t mbedtls_mpi_size( const mbedtls_mpi *X )
410{
411 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
412}
413
414/*
415 * Convert an ASCII character to digit value
416 */
417static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
418{
419 *d = 255;
420
421 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
422 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
423 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
424
425 if( *d >= (mbedtls_mpi_uint) radix )
426 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
427
428 return( 0 );
429}
430
431/*
432 * Import from an ASCII string
433 */
434int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
435{
436 int ret;
437 size_t i, j, slen, n;
438 mbedtls_mpi_uint d;
439 mbedtls_mpi T;
440
441 if( radix < 2 || radix > 16 )
442 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
443
444 mbedtls_mpi_init( &T );
445
446 slen = strlen( s );
447
448 if( radix == 16 )
449 {
450 if( slen > MPI_SIZE_T_MAX >> 2 )
451 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
452
453 n = BITS_TO_LIMBS( slen << 2 );
454
455 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
456 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
457
458 for( i = slen, j = 0; i > 0; i--, j++ )
459 {
460 if( i == 1 && s[i - 1] == '-' )
461 {
462 X->s = -1;
463 break;
464 }
465
466 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
467 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
468 }
469 }
470 else
471 {
472 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
473
474 for( i = 0; i < slen; i++ )
475 {
476 if( i == 0 && s[i] == '-' )
477 {
478 X->s = -1;
479 continue;
480 }
481
482 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
483 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
484
485 if( X->s == 1 )
486 {
487 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
488 }
489 else
490 {
491 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
492 }
493 }
494 }
495
496cleanup:
497
498 mbedtls_mpi_free( &T );
499
500 return( ret );
501}
502
503/*
504 * Helper to write the digits high-order first
505 */
506static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
507{
508 int ret;
509 mbedtls_mpi_uint r;
510
511 if( radix < 2 || radix > 16 )
512 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
513
514 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
515 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
516
517 if( mbedtls_mpi_cmp_int( X, 0 ) != 0 )
518 MBEDTLS_MPI_CHK( mpi_write_hlp( X, radix, p ) );
519
520 if( r < 10 )
521 *(*p)++ = (char)( r + 0x30 );
522 else
523 *(*p)++ = (char)( r + 0x37 );
524
525cleanup:
526
527 return( ret );
528}
529
530/*
531 * Export into an ASCII string
532 */
533int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
534 char *buf, size_t buflen, size_t *olen )
535{
536 int ret = 0;
537 size_t n;
538 char *p;
539 mbedtls_mpi T;
540
541 if( radix < 2 || radix > 16 )
542 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
543
544 n = mbedtls_mpi_bitlen( X );
545 if( radix >= 4 ) n >>= 1;
546 if( radix >= 16 ) n >>= 1;
547 /*
548 * Round up the buffer length to an even value to ensure that there is
549 * enough room for hexadecimal values that can be represented in an odd
550 * number of digits.
551 */
552 n += 3 + ( ( n + 1 ) & 1 );
553
554 if( buflen < n )
555 {
556 *olen = n;
557 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
558 }
559
560 p = buf;
561 mbedtls_mpi_init( &T );
562
563 if( X->s == -1 )
564 *p++ = '-';
565
566 if( radix == 16 )
567 {
568 int c;
569 size_t i, j, k;
570
571 for( i = X->n, k = 0; i > 0; i-- )
572 {
573 for( j = ciL; j > 0; j-- )
574 {
575 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
576
577 if( c == 0 && k == 0 && ( i + j ) != 2 )
578 continue;
579
580 *(p++) = "0123456789ABCDEF" [c / 16];
581 *(p++) = "0123456789ABCDEF" [c % 16];
582 k = 1;
583 }
584 }
585 }
586 else
587 {
588 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
589
590 if( T.s == -1 )
591 T.s = 1;
592
593 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
594 }
595
596 *p++ = '\0';
597 *olen = p - buf;
598
599cleanup:
600
601 mbedtls_mpi_free( &T );
602
603 return( ret );
604}
605
606#if defined(MBEDTLS_FS_IO)
607/*
608 * Read X from an opened file
609 */
610int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
611{
612 mbedtls_mpi_uint d;
613 size_t slen;
614 char *p;
615 /*
616 * Buffer should have space for (short) label and decimal formatted MPI,
617 * newline characters and '\0'
618 */
619 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
620
621 memset( s, 0, sizeof( s ) );
622 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
623 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
624
625 slen = strlen( s );
626 if( slen == sizeof( s ) - 2 )
627 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
628
629 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
630 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
631
632 p = s + slen;
633 while( p-- > s )
634 if( mpi_get_digit( &d, radix, *p ) != 0 )
635 break;
636
637 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
638}
639
640/*
641 * Write X into an opened file (or stdout if fout == NULL)
642 */
643int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
644{
645 int ret;
646 size_t n, slen, plen;
647 /*
648 * Buffer should have space for (short) label and decimal formatted MPI,
649 * newline characters and '\0'
650 */
651 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
652
653 memset( s, 0, sizeof( s ) );
654
655 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
656
657 if( p == NULL ) p = "";
658
659 plen = strlen( p );
660 slen = strlen( s );
661 s[slen++] = '\r';
662 s[slen++] = '\n';
663
664 if( fout != NULL )
665 {
666 if( fwrite( p, 1, plen, fout ) != plen ||
667 fwrite( s, 1, slen, fout ) != slen )
668 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
669 }
670 else
671 mbedtls_printf( "%s%s", p, s );
672
673cleanup:
674
675 return( ret );
676}
677#endif /* MBEDTLS_FS_IO */
678
679/*
680 * Import X from unsigned binary data, big endian
681 */
682int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
683{
684 int ret;
685 size_t i, j;
686 size_t const limbs = CHARS_TO_LIMBS( buflen );
687
688 /* Ensure that target MPI has exactly the necessary number of limbs */
689 if( X->n != limbs )
690 {
691 mbedtls_mpi_free( X );
692 mbedtls_mpi_init( X );
693 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
694 }
695
696 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
697
698 for( i = buflen, j = 0; i > 0; i--, j++ )
699 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
700
701cleanup:
702
703 return( ret );
704}
705
706/*
707 * Export X into unsigned binary data, big endian
708 */
709int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
710{
711 size_t i, j, n;
712
713 n = mbedtls_mpi_size( X );
714
715 if( buflen < n )
716 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
717
718 memset( buf, 0, buflen );
719
720 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
721 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
722
723 return( 0 );
724}
725
726/*
727 * Left-shift: X <<= count
728 */
729int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
730{
731 int ret;
732 size_t i, v0, t1;
733 mbedtls_mpi_uint r0 = 0, r1;
734
735 v0 = count / (biL );
736 t1 = count & (biL - 1);
737
738 i = mbedtls_mpi_bitlen( X ) + count;
739
740 if( X->n * biL < i )
741 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
742
743 ret = 0;
744
745 /*
746 * shift by count / limb_size
747 */
748 if( v0 > 0 )
749 {
750 for( i = X->n; i > v0; i-- )
751 X->p[i - 1] = X->p[i - v0 - 1];
752
753 for( ; i > 0; i-- )
754 X->p[i - 1] = 0;
755 }
756
757 /*
758 * shift by count % limb_size
759 */
760 if( t1 > 0 )
761 {
762 for( i = v0; i < X->n; i++ )
763 {
764 r1 = X->p[i] >> (biL - t1);
765 X->p[i] <<= t1;
766 X->p[i] |= r0;
767 r0 = r1;
768 }
769 }
770
771cleanup:
772
773 return( ret );
774}
775
776/*
777 * Right-shift: X >>= count
778 */
779int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
780{
781 size_t i, v0, v1;
782 mbedtls_mpi_uint r0 = 0, r1;
783
784 v0 = count / biL;
785 v1 = count & (biL - 1);
786
787 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
788 return mbedtls_mpi_lset( X, 0 );
789
790 /*
791 * shift by count / limb_size
792 */
793 if( v0 > 0 )
794 {
795 for( i = 0; i < X->n - v0; i++ )
796 X->p[i] = X->p[i + v0];
797
798 for( ; i < X->n; i++ )
799 X->p[i] = 0;
800 }
801
802 /*
803 * shift by count % limb_size
804 */
805 if( v1 > 0 )
806 {
807 for( i = X->n; i > 0; i-- )
808 {
809 r1 = X->p[i - 1] << (biL - v1);
810 X->p[i - 1] >>= v1;
811 X->p[i - 1] |= r0;
812 r0 = r1;
813 }
814 }
815
816 return( 0 );
817}
818
819/*
820 * Compare unsigned values
821 */
822int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
823{
824 size_t i, j;
825
826 for( i = X->n; i > 0; i-- )
827 if( X->p[i - 1] != 0 )
828 break;
829
830 for( j = Y->n; j > 0; j-- )
831 if( Y->p[j - 1] != 0 )
832 break;
833
834 if( i == 0 && j == 0 )
835 return( 0 );
836
837 if( i > j ) return( 1 );
838 if( j > i ) return( -1 );
839
840 for( ; i > 0; i-- )
841 {
842 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
843 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
844 }
845
846 return( 0 );
847}
848
849/*
850 * Compare signed values
851 */
852int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
853{
854 size_t i, j;
855
856 for( i = X->n; i > 0; i-- )
857 if( X->p[i - 1] != 0 )
858 break;
859
860 for( j = Y->n; j > 0; j-- )
861 if( Y->p[j - 1] != 0 )
862 break;
863
864 if( i == 0 && j == 0 )
865 return( 0 );
866
867 if( i > j ) return( X->s );
868 if( j > i ) return( -Y->s );
869
870 if( X->s > 0 && Y->s < 0 ) return( 1 );
871 if( Y->s > 0 && X->s < 0 ) return( -1 );
872
873 for( ; i > 0; i-- )
874 {
875 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
876 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
877 }
878
879 return( 0 );
880}
881
882/*
883 * Compare signed values
884 */
885int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
886{
887 mbedtls_mpi Y;
888 mbedtls_mpi_uint p[1];
889
890 *p = ( z < 0 ) ? -z : z;
891 Y.s = ( z < 0 ) ? -1 : 1;
892 Y.n = 1;
893 Y.p = p;
894
895 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
896}
897
898/*
899 * Unsigned addition: X = |A| + |B| (HAC 14.7)
900 */
901int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
902{
903 int ret;
904 size_t i, j;
905 mbedtls_mpi_uint *o, *p, c, tmp;
906
907 if( X == B )
908 {
909 const mbedtls_mpi *T = A; A = X; B = T;
910 }
911
912 if( X != A )
913 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
914
915 /*
916 * X should always be positive as a result of unsigned additions.
917 */
918 X->s = 1;
919
920 for( j = B->n; j > 0; j-- )
921 if( B->p[j - 1] != 0 )
922 break;
923
924 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
925
926 o = B->p; p = X->p; c = 0;
927
928 /*
929 * tmp is used because it might happen that p == o
930 */
931 for( i = 0; i < j; i++, o++, p++ )
932 {
933 tmp= *o;
934 *p += c; c = ( *p < c );
935 *p += tmp; c += ( *p < tmp );
936 }
937
938 while( c != 0 )
939 {
940 if( i >= X->n )
941 {
942 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
943 p = X->p + i;
944 }
945
946 *p += c; c = ( *p < c ); i++; p++;
947 }
948
949cleanup:
950
951 return( ret );
952}
953
954/*
955 * Helper for mbedtls_mpi subtraction
956 */
957static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
958{
959 size_t i;
960 mbedtls_mpi_uint c, z;
961
962 for( i = c = 0; i < n; i++, s++, d++ )
963 {
964 z = ( *d < c ); *d -= c;
965 c = ( *d < *s ) + z; *d -= *s;
966 }
967
968 while( c != 0 )
969 {
970 z = ( *d < c ); *d -= c;
971 c = z; d++;
972 }
973}
974
975/*
976 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
977 */
978int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
979{
980 mbedtls_mpi TB;
981 int ret;
982 size_t n;
983
984 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
985 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
986
987 mbedtls_mpi_init( &TB );
988
989 if( X == B )
990 {
991 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
992 B = &TB;
993 }
994
995 if( X != A )
996 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
997
998 /*
999 * X should always be positive as a result of unsigned subtractions.
1000 */
1001 X->s = 1;
1002
1003 ret = 0;
1004
1005 for( n = B->n; n > 0; n-- )
1006 if( B->p[n - 1] != 0 )
1007 break;
1008
1009 mpi_sub_hlp( n, B->p, X->p );
1010
1011cleanup:
1012
1013 mbedtls_mpi_free( &TB );
1014
1015 return( ret );
1016}
1017
1018/*
1019 * Signed addition: X = A + B
1020 */
1021int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1022{
1023 int ret, s = A->s;
1024
1025 if( A->s * B->s < 0 )
1026 {
1027 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1028 {
1029 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1030 X->s = s;
1031 }
1032 else
1033 {
1034 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1035 X->s = -s;
1036 }
1037 }
1038 else
1039 {
1040 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1041 X->s = s;
1042 }
1043
1044cleanup:
1045
1046 return( ret );
1047}
1048
1049/*
1050 * Signed subtraction: X = A - B
1051 */
1052int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1053{
1054 int ret, s = A->s;
1055
1056 if( A->s * B->s > 0 )
1057 {
1058 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1059 {
1060 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1061 X->s = s;
1062 }
1063 else
1064 {
1065 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1066 X->s = -s;
1067 }
1068 }
1069 else
1070 {
1071 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1072 X->s = s;
1073 }
1074
1075cleanup:
1076
1077 return( ret );
1078}
1079
1080/*
1081 * Signed addition: X = A + b
1082 */
1083int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1084{
1085 mbedtls_mpi _B;
1086 mbedtls_mpi_uint p[1];
1087
1088 p[0] = ( b < 0 ) ? -b : b;
1089 _B.s = ( b < 0 ) ? -1 : 1;
1090 _B.n = 1;
1091 _B.p = p;
1092
1093 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
1094}
1095
1096/*
1097 * Signed subtraction: X = A - b
1098 */
1099int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1100{
1101 mbedtls_mpi _B;
1102 mbedtls_mpi_uint p[1];
1103
1104 p[0] = ( b < 0 ) ? -b : b;
1105 _B.s = ( b < 0 ) ? -1 : 1;
1106 _B.n = 1;
1107 _B.p = p;
1108
1109 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
1110}
1111
1112/*
1113 * Helper for mbedtls_mpi multiplication
1114 */
1115static
1116#if defined(__APPLE__) && defined(__arm__)
1117/*
1118 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1119 * appears to need this to prevent bad ARM code generation at -O3.
1120 */
1121__attribute__ ((noinline))
1122#endif
1123void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
1124{
1125 mbedtls_mpi_uint c = 0, t = 0;
1126
1127#if defined(MULADDC_HUIT)
1128 for( ; i >= 8; i -= 8 )
1129 {
1130 MULADDC_INIT
1131 MULADDC_HUIT
1132 MULADDC_STOP
1133 }
1134
1135 for( ; i > 0; i-- )
1136 {
1137 MULADDC_INIT
1138 MULADDC_CORE
1139 MULADDC_STOP
1140 }
1141#else /* MULADDC_HUIT */
1142 for( ; i >= 16; i -= 16 )
1143 {
1144 MULADDC_INIT
1145 MULADDC_CORE MULADDC_CORE
1146 MULADDC_CORE MULADDC_CORE
1147 MULADDC_CORE MULADDC_CORE
1148 MULADDC_CORE MULADDC_CORE
1149
1150 MULADDC_CORE MULADDC_CORE
1151 MULADDC_CORE MULADDC_CORE
1152 MULADDC_CORE MULADDC_CORE
1153 MULADDC_CORE MULADDC_CORE
1154 MULADDC_STOP
1155 }
1156
1157 for( ; i >= 8; i -= 8 )
1158 {
1159 MULADDC_INIT
1160 MULADDC_CORE MULADDC_CORE
1161 MULADDC_CORE MULADDC_CORE
1162
1163 MULADDC_CORE MULADDC_CORE
1164 MULADDC_CORE MULADDC_CORE
1165 MULADDC_STOP
1166 }
1167
1168 for( ; i > 0; i-- )
1169 {
1170 MULADDC_INIT
1171 MULADDC_CORE
1172 MULADDC_STOP
1173 }
1174#endif /* MULADDC_HUIT */
1175
1176 t++;
1177
1178 do {
1179 *d += c; c = ( *d < c ); d++;
1180 }
1181 while( c != 0 );
1182}
1183
1184/*
1185 * Baseline multiplication: X = A * B (HAC 14.12)
1186 */
1187int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1188{
1189 int ret;
1190 size_t i, j;
1191 mbedtls_mpi TA, TB;
1192
1193 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
1194
1195 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1196 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1197
1198 for( i = A->n; i > 0; i-- )
1199 if( A->p[i - 1] != 0 )
1200 break;
1201
1202 for( j = B->n; j > 0; j-- )
1203 if( B->p[j - 1] != 0 )
1204 break;
1205
1206 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1207 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1208
1209 for( ; j > 0; j-- )
1210 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
1211
1212 X->s = A->s * B->s;
1213
1214cleanup:
1215
1216 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
1217
1218 return( ret );
1219}
1220
1221/*
1222 * Baseline multiplication: X = A * b
1223 */
1224int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1225{
1226 mbedtls_mpi _B;
1227 mbedtls_mpi_uint p[1];
1228
1229 _B.s = 1;
1230 _B.n = 1;
1231 _B.p = p;
1232 p[0] = b;
1233
1234 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
1235}
1236
1237/*
1238 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1239 * mbedtls_mpi_uint divisor, d
1240 */
1241static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1242 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
1243{
1244#if defined(MBEDTLS_HAVE_UDBL)
1245 mbedtls_t_udbl dividend, quotient;
1246#else
1247 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1248 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
1249 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1250 mbedtls_mpi_uint u0_msw, u0_lsw;
1251 size_t s;
1252#endif
1253
1254 /*
1255 * Check for overflow
1256 */
1257 if( 0 == d || u1 >= d )
1258 {
1259 if (r != NULL) *r = ~0;
1260
1261 return ( ~0 );
1262 }
1263
1264#if defined(MBEDTLS_HAVE_UDBL)
1265 dividend = (mbedtls_t_udbl) u1 << biL;
1266 dividend |= (mbedtls_t_udbl) u0;
1267 quotient = dividend / d;
1268 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1269 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1270
1271 if( r != NULL )
1272 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
1273
1274 return (mbedtls_mpi_uint) quotient;
1275#else
1276
1277 /*
1278 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1279 * Vol. 2 - Seminumerical Algorithms, Knuth
1280 */
1281
1282 /*
1283 * Normalize the divisor, d, and dividend, u0, u1
1284 */
1285 s = mbedtls_clz( d );
1286 d = d << s;
1287
1288 u1 = u1 << s;
1289 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
1290 u0 = u0 << s;
1291
1292 d1 = d >> biH;
1293 d0 = d & uint_halfword_mask;
1294
1295 u0_msw = u0 >> biH;
1296 u0_lsw = u0 & uint_halfword_mask;
1297
1298 /*
1299 * Find the first quotient and remainder
1300 */
1301 q1 = u1 / d1;
1302 r0 = u1 - d1 * q1;
1303
1304 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1305 {
1306 q1 -= 1;
1307 r0 += d1;
1308
1309 if ( r0 >= radix ) break;
1310 }
1311
1312 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
1313 q0 = rAX / d1;
1314 r0 = rAX - q0 * d1;
1315
1316 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1317 {
1318 q0 -= 1;
1319 r0 += d1;
1320
1321 if ( r0 >= radix ) break;
1322 }
1323
1324 if (r != NULL)
1325 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
1326
1327 quotient = q1 * radix + q0;
1328
1329 return quotient;
1330#endif
1331}
1332
1333/*
1334 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1335 */
1336int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1337{
1338 int ret;
1339 size_t i, n, t, k;
1340 mbedtls_mpi X, Y, Z, T1, T2;
1341
1342 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1343 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1344
1345 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1346 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
1347
1348 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1349 {
1350 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1351 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1352 return( 0 );
1353 }
1354
1355 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1356 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1357 X.s = Y.s = 1;
1358
1359 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1360 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1361 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1362 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
1363
1364 k = mbedtls_mpi_bitlen( &Y ) % biL;
1365 if( k < biL - 1 )
1366 {
1367 k = biL - 1 - k;
1368 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1369 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1370 }
1371 else k = 0;
1372
1373 n = X.n - 1;
1374 t = Y.n - 1;
1375 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1376
1377 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
1378 {
1379 Z.p[n - t]++;
1380 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
1381 }
1382 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
1383
1384 for( i = n; i > t ; i-- )
1385 {
1386 if( X.p[i] >= Y.p[t] )
1387 Z.p[i - t - 1] = ~0;
1388 else
1389 {
1390 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1391 Y.p[t], NULL);
1392 }
1393
1394 Z.p[i - t - 1]++;
1395 do
1396 {
1397 Z.p[i - t - 1]--;
1398
1399 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
1400 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
1401 T1.p[1] = Y.p[t];
1402 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1403
1404 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
1405 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1406 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1407 T2.p[2] = X.p[i];
1408 }
1409 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
1410
1411 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1412 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1413 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
1414
1415 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
1416 {
1417 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1418 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1419 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
1420 Z.p[i - t - 1]--;
1421 }
1422 }
1423
1424 if( Q != NULL )
1425 {
1426 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
1427 Q->s = A->s * B->s;
1428 }
1429
1430 if( R != NULL )
1431 {
1432 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
1433 X.s = A->s;
1434 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
1435
1436 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
1437 R->s = 1;
1438 }
1439
1440cleanup:
1441
1442 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1443 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
1444
1445 return( ret );
1446}
1447
1448/*
1449 * Division by int: A = Q * b + R
1450 */
1451int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1452{
1453 mbedtls_mpi _B;
1454 mbedtls_mpi_uint p[1];
1455
1456 p[0] = ( b < 0 ) ? -b : b;
1457 _B.s = ( b < 0 ) ? -1 : 1;
1458 _B.n = 1;
1459 _B.p = p;
1460
1461 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
1462}
1463
1464/*
1465 * Modulo: R = A mod B
1466 */
1467int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1468{
1469 int ret;
1470
1471 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1472 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1473
1474 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
1475
1476 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1477 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
1478
1479 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1480 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
1481
1482cleanup:
1483
1484 return( ret );
1485}
1486
1487/*
1488 * Modulo: r = A mod b
1489 */
1490int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1491{
1492 size_t i;
1493 mbedtls_mpi_uint x, y, z;
1494
1495 if( b == 0 )
1496 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1497
1498 if( b < 0 )
1499 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1500
1501 /*
1502 * handle trivial cases
1503 */
1504 if( b == 1 )
1505 {
1506 *r = 0;
1507 return( 0 );
1508 }
1509
1510 if( b == 2 )
1511 {
1512 *r = A->p[0] & 1;
1513 return( 0 );
1514 }
1515
1516 /*
1517 * general case
1518 */
1519 for( i = A->n, y = 0; i > 0; i-- )
1520 {
1521 x = A->p[i - 1];
1522 y = ( y << biH ) | ( x >> biH );
1523 z = y / b;
1524 y -= z * b;
1525
1526 x <<= biH;
1527 y = ( y << biH ) | ( x >> biH );
1528 z = y / b;
1529 y -= z * b;
1530 }
1531
1532 /*
1533 * If A is negative, then the current y represents a negative value.
1534 * Flipping it to the positive side.
1535 */
1536 if( A->s < 0 && y != 0 )
1537 y = b - y;
1538
1539 *r = y;
1540
1541 return( 0 );
1542}
1543
1544/*
1545 * Fast Montgomery initialization (thanks to Tom St Denis)
1546 */
1547static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
1548{
1549 mbedtls_mpi_uint x, m0 = N->p[0];
1550 unsigned int i;
1551
1552 x = m0;
1553 x += ( ( m0 + 2 ) & 4 ) << 1;
1554
1555 for( i = biL; i >= 8; i /= 2 )
1556 x *= ( 2 - ( m0 * x ) );
1557
1558 *mm = ~x + 1;
1559}
1560
1561/*
1562 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1563 */
1564static int mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1565 const mbedtls_mpi *T )
1566{
1567 size_t i, n, m;
1568 mbedtls_mpi_uint u0, u1, *d;
1569
1570 if( T->n < N->n + 1 || T->p == NULL )
1571 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1572
1573 memset( T->p, 0, T->n * ciL );
1574
1575 d = T->p;
1576 n = N->n;
1577 m = ( B->n < n ) ? B->n : n;
1578
1579 for( i = 0; i < n; i++ )
1580 {
1581 /*
1582 * T = (T + u0*B + u1*N) / 2^biL
1583 */
1584 u0 = A->p[i];
1585 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1586
1587 mpi_mul_hlp( m, B->p, d, u0 );
1588 mpi_mul_hlp( n, N->p, d, u1 );
1589
1590 *d++ = u0; d[n + 1] = 0;
1591 }
1592
1593 memcpy( A->p, d, ( n + 1 ) * ciL );
1594
1595 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
1596 mpi_sub_hlp( n, N->p, A->p );
1597 else
1598 /* prevent timing attacks */
1599 mpi_sub_hlp( n, A->p, T->p );
1600
1601 return( 0 );
1602}
1603
1604/*
1605 * Montgomery reduction: A = A * R^-1 mod N
1606 */
1607static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T )
1608{
1609 mbedtls_mpi_uint z = 1;
1610 mbedtls_mpi U;
1611
1612 U.n = U.s = (int) z;
1613 U.p = &z;
1614
1615 return( mpi_montmul( A, &U, N, mm, T ) );
1616}
1617
1618/*
1619 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1620 */
1621int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR )
1622{
1623 int ret;
1624 size_t wbits, wsize, one = 1;
1625 size_t i, j, nblimbs;
1626 size_t bufsize, nbits;
1627 mbedtls_mpi_uint ei, mm, state;
1628 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
1629 int neg;
1630
1631 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
1632 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1633
1634 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1635 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1636
1637 /*
1638 * Init temps and window size
1639 */
1640 mpi_montg_init( &mm, N );
1641 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1642 mbedtls_mpi_init( &Apos );
1643 memset( W, 0, sizeof( W ) );
1644
1645 i = mbedtls_mpi_bitlen( E );
1646
1647 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1648 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1649
1650 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1651 wsize = MBEDTLS_MPI_WINDOW_SIZE;
1652
1653 j = N->n + 1;
1654 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1655 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1656 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
1657
1658 /*
1659 * Compensate for negative A (and correct at the end)
1660 */
1661 neg = ( A->s == -1 );
1662 if( neg )
1663 {
1664 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
1665 Apos.s = 1;
1666 A = &Apos;
1667 }
1668
1669 /*
1670 * If 1st call, pre-compute R^2 mod N
1671 */
1672 if( _RR == NULL || _RR->p == NULL )
1673 {
1674 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1675 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1676 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
1677
1678 if( _RR != NULL )
1679 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
1680 }
1681 else
1682 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
1683
1684 /*
1685 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1686 */
1687 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
1688 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
1689 else
1690 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
1691
1692 MBEDTLS_MPI_CHK( mpi_montmul( &W[1], &RR, N, mm, &T ) );
1693
1694 /*
1695 * X = R^2 * R^-1 mod N = R mod N
1696 */
1697 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
1698 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) );
1699
1700 if( wsize > 1 )
1701 {
1702 /*
1703 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1704 */
1705 j = one << ( wsize - 1 );
1706
1707 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1708 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
1709
1710 for( i = 0; i < wsize - 1; i++ )
1711 MBEDTLS_MPI_CHK( mpi_montmul( &W[j], &W[j], N, mm, &T ) );
1712
1713 /*
1714 * W[i] = W[i - 1] * W[1]
1715 */
1716 for( i = j + 1; i < ( one << wsize ); i++ )
1717 {
1718 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1719 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
1720
1721 MBEDTLS_MPI_CHK( mpi_montmul( &W[i], &W[1], N, mm, &T ) );
1722 }
1723 }
1724
1725 nblimbs = E->n;
1726 bufsize = 0;
1727 nbits = 0;
1728 wbits = 0;
1729 state = 0;
1730
1731 while( 1 )
1732 {
1733 if( bufsize == 0 )
1734 {
1735 if( nblimbs == 0 )
1736 break;
1737
1738 nblimbs--;
1739
1740 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
1741 }
1742
1743 bufsize--;
1744
1745 ei = (E->p[nblimbs] >> bufsize) & 1;
1746
1747 /*
1748 * skip leading 0s
1749 */
1750 if( ei == 0 && state == 0 )
1751 continue;
1752
1753 if( ei == 0 && state == 1 )
1754 {
1755 /*
1756 * out of window, square X
1757 */
1758 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
1759 continue;
1760 }
1761
1762 /*
1763 * add ei to current window
1764 */
1765 state = 2;
1766
1767 nbits++;
1768 wbits |= ( ei << ( wsize - nbits ) );
1769
1770 if( nbits == wsize )
1771 {
1772 /*
1773 * X = X^wsize R^-1 mod N
1774 */
1775 for( i = 0; i < wsize; i++ )
1776 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
1777
1778 /*
1779 * X = X * W[wbits] R^-1 mod N
1780 */
1781 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[wbits], N, mm, &T ) );
1782
1783 state--;
1784 nbits = 0;
1785 wbits = 0;
1786 }
1787 }
1788
1789 /*
1790 * process the remaining bits
1791 */
1792 for( i = 0; i < nbits; i++ )
1793 {
1794 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
1795
1796 wbits <<= 1;
1797
1798 if( ( wbits & ( one << wsize ) ) != 0 )
1799 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[1], N, mm, &T ) );
1800 }
1801
1802 /*
1803 * X = A^E * R * R^-1 mod N = A^E mod N
1804 */
1805 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) );
1806
1807 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
1808 {
1809 X->s = -1;
1810 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
1811 }
1812
1813cleanup:
1814
1815 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
1816 mbedtls_mpi_free( &W[i] );
1817
1818 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
1819
1820 if( _RR == NULL || _RR->p == NULL )
1821 mbedtls_mpi_free( &RR );
1822
1823 return( ret );
1824}
1825
1826/*
1827 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1828 */
1829int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
1830{
1831 int ret;
1832 size_t lz, lzt;
1833 mbedtls_mpi TG, TA, TB;
1834
1835 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
1836
1837 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
1838 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
1839
1840 lz = mbedtls_mpi_lsb( &TA );
1841 lzt = mbedtls_mpi_lsb( &TB );
1842
1843 if( lzt < lz )
1844 lz = lzt;
1845
1846 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
1847 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
1848
1849 TA.s = TB.s = 1;
1850
1851 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
1852 {
1853 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
1854 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
1855
1856 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
1857 {
1858 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
1859 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
1860 }
1861 else
1862 {
1863 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
1864 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
1865 }
1866 }
1867
1868 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
1869 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
1870
1871cleanup:
1872
1873 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
1874
1875 return( ret );
1876}
1877
1878/*
1879 * Fill X with size bytes of random.
1880 *
1881 * Use a temporary bytes representation to make sure the result is the same
1882 * regardless of the platform endianness (useful when f_rng is actually
1883 * deterministic, eg for tests).
1884 */
1885int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
1886 int (*f_rng)(void *, unsigned char *, size_t),
1887 void *p_rng )
1888{
1889 int ret;
1890 unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
1891
1892 if( size > MBEDTLS_MPI_MAX_SIZE )
1893 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1894
1895 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
1896 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
1897
1898cleanup:
1899 mbedtls_platform_zeroize( buf, sizeof( buf ) );
1900 return( ret );
1901}
1902
1903/*
1904 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1905 */
1906int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
1907{
1908 int ret;
1909 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1910
1911 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
1912 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1913
1914 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
1915 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
1916 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
1917
1918 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
1919
1920 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
1921 {
1922 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
1923 goto cleanup;
1924 }
1925
1926 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
1927 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
1928 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
1929 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
1930
1931 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
1932 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
1933 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
1934 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
1935
1936 do
1937 {
1938 while( ( TU.p[0] & 1 ) == 0 )
1939 {
1940 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
1941
1942 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1943 {
1944 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
1945 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
1946 }
1947
1948 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
1949 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
1950 }
1951
1952 while( ( TV.p[0] & 1 ) == 0 )
1953 {
1954 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
1955
1956 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1957 {
1958 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
1959 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
1960 }
1961
1962 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
1963 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
1964 }
1965
1966 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
1967 {
1968 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
1969 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
1970 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
1971 }
1972 else
1973 {
1974 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
1975 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
1976 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
1977 }
1978 }
1979 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
1980
1981 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
1982 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
1983
1984 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
1985 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
1986
1987 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
1988
1989cleanup:
1990
1991 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
1992 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
1993 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
1994
1995 return( ret );
1996}
1997
1998#if defined(MBEDTLS_GENPRIME)
1999
2000static const int small_prime[] =
2001{
2002 3, 5, 7, 11, 13, 17, 19, 23,
2003 29, 31, 37, 41, 43, 47, 53, 59,
2004 61, 67, 71, 73, 79, 83, 89, 97,
2005 101, 103, 107, 109, 113, 127, 131, 137,
2006 139, 149, 151, 157, 163, 167, 173, 179,
2007 181, 191, 193, 197, 199, 211, 223, 227,
2008 229, 233, 239, 241, 251, 257, 263, 269,
2009 271, 277, 281, 283, 293, 307, 311, 313,
2010 317, 331, 337, 347, 349, 353, 359, 367,
2011 373, 379, 383, 389, 397, 401, 409, 419,
2012 421, 431, 433, 439, 443, 449, 457, 461,
2013 463, 467, 479, 487, 491, 499, 503, 509,
2014 521, 523, 541, 547, 557, 563, 569, 571,
2015 577, 587, 593, 599, 601, 607, 613, 617,
2016 619, 631, 641, 643, 647, 653, 659, 661,
2017 673, 677, 683, 691, 701, 709, 719, 727,
2018 733, 739, 743, 751, 757, 761, 769, 773,
2019 787, 797, 809, 811, 821, 823, 827, 829,
2020 839, 853, 857, 859, 863, 877, 881, 883,
2021 887, 907, 911, 919, 929, 937, 941, 947,
2022 953, 967, 971, 977, 983, 991, 997, -103
2023};
2024
2025/*
2026 * Small divisors test (X must be positive)
2027 *
2028 * Return values:
2029 * 0: no small factor (possible prime, more tests needed)
2030 * 1: certain prime
2031 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2032 * other negative: error
2033 */
2034static int mpi_check_small_factors( const mbedtls_mpi *X )
2035{
2036 int ret = 0;
2037 size_t i;
2038 mbedtls_mpi_uint r;
2039
2040 if( ( X->p[0] & 1 ) == 0 )
2041 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2042
2043 for( i = 0; small_prime[i] > 0; i++ )
2044 {
2045 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
2046 return( 1 );
2047
2048 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
2049
2050 if( r == 0 )
2051 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2052 }
2053
2054cleanup:
2055 return( ret );
2056}
2057
2058/*
2059 * Miller-Rabin pseudo-primality test (HAC 4.24)
2060 */
2061static int mpi_miller_rabin( const mbedtls_mpi *X,
2062 int (*f_rng)(void *, unsigned char *, size_t),
2063 void *p_rng )
2064{
2065 int ret, count;
2066 size_t i, j, k, n, s;
2067 mbedtls_mpi W, R, T, A, RR;
2068
2069 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2070 mbedtls_mpi_init( &RR );
2071
2072 /*
2073 * W = |X| - 1
2074 * R = W >> lsb( W )
2075 */
2076 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2077 s = mbedtls_mpi_lsb( &W );
2078 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2079 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
2080
2081 i = mbedtls_mpi_bitlen( X );
2082 /*
2083 * HAC, table 4.4
2084 */
2085 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
2086 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
2087 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
2088
2089 for( i = 0; i < n; i++ )
2090 {
2091 /*
2092 * pick a random A, 1 < A < |X| - 1
2093 */
2094 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2095
2096 if( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 )
2097 {
2098 j = mbedtls_mpi_bitlen( &A ) - mbedtls_mpi_bitlen( &W );
2099 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j + 1 ) );
2100 }
2101 A.p[0] |= 3;
2102
2103 count = 0;
2104 do {
2105 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2106
2107 j = mbedtls_mpi_bitlen( &A );
2108 k = mbedtls_mpi_bitlen( &W );
2109 if (j > k) {
2110 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j - k ) );
2111 }
2112
2113 if (count++ > 30) {
2114 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2115 }
2116
2117 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2118 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
2119
2120 /*
2121 * A = A^R mod |X|
2122 */
2123 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
2124
2125 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2126 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2127 continue;
2128
2129 j = 1;
2130 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
2131 {
2132 /*
2133 * A = A * A mod |X|
2134 */
2135 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2136 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
2137
2138 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2139 break;
2140
2141 j++;
2142 }
2143
2144 /*
2145 * not prime if A != |X| - 1 or A == 1
2146 */
2147 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2148 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2149 {
2150 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2151 break;
2152 }
2153 }
2154
2155cleanup:
2156 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2157 mbedtls_mpi_free( &RR );
2158
2159 return( ret );
2160}
2161
2162/*
2163 * Pseudo-primality test: small factors, then Miller-Rabin
2164 */
2165int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2166 int (*f_rng)(void *, unsigned char *, size_t),
2167 void *p_rng )
2168{
2169 int ret;
2170 mbedtls_mpi XX;
2171
2172 XX.s = 1;
2173 XX.n = X->n;
2174 XX.p = X->p;
2175
2176 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2177 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2178 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2179
2180 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
2181 return( 0 );
2182
2183 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2184 {
2185 if( ret == 1 )
2186 return( 0 );
2187
2188 return( ret );
2189 }
2190
2191 return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
2192}
2193
2194/*
2195 * Prime number generation
2196 *
2197 * If dh_flag is 0 and nbits is at least 1024, then the procedure
2198 * follows the RSA probably-prime generation method of FIPS 186-4.
2199 * NB. FIPS 186-4 only allows the specific bit lengths of 1024 and 1536.
2200 */
2201int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
2202 int (*f_rng)(void *, unsigned char *, size_t),
2203 void *p_rng )
2204{
2205#ifdef MBEDTLS_HAVE_INT64
2206// ceil(2^63.5)
2207#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2208#else
2209// ceil(2^31.5)
2210#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2211#endif
2212 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2213 size_t k, n;
2214 mbedtls_mpi_uint r;
2215 mbedtls_mpi Y;
2216
2217 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2218 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2219
2220 mbedtls_mpi_init( &Y );
2221
2222 n = BITS_TO_LIMBS( nbits );
2223
2224 while( 1 )
2225 {
2226 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2227 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2228 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2229
2230 k = n * biL;
2231 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2232 X->p[0] |= 1;
2233
2234 if( dh_flag == 0 )
2235 {
2236 ret = mbedtls_mpi_is_prime( X, f_rng, p_rng );
2237
2238 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2239 goto cleanup;
2240 }
2241 else
2242 {
2243 /*
2244 * An necessary condition for Y and X = 2Y + 1 to be prime
2245 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2246 * Make sure it is satisfied, while keeping X = 3 mod 4
2247 */
2248
2249 X->p[0] |= 2;
2250
2251 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2252 if( r == 0 )
2253 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2254 else if( r == 1 )
2255 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2256
2257 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2258 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2259 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2260
2261 while( 1 )
2262 {
2263 /*
2264 * First, check small factors for X and Y
2265 * before doing Miller-Rabin on any of them
2266 */
2267 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2268 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2269 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
2270 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
2271 goto cleanup;
2272
2273 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2274 goto cleanup;
2275
2276 /*
2277 * Next candidates. We want to preserve Y = (X-1) / 2 and
2278 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2279 * so up Y by 6 and X by 12.
2280 */
2281 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2282 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
2283 }
2284 }
2285 }
2286
2287cleanup:
2288
2289 mbedtls_mpi_free( &Y );
2290
2291 return( ret );
2292}
2293
2294#endif /* MBEDTLS_GENPRIME */
2295
2296#if defined(MBEDTLS_SELF_TEST)
2297
2298#define GCD_PAIR_COUNT 3
2299
2300static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2301{
2302 { 693, 609, 21 },
2303 { 1764, 868, 28 },
2304 { 768454923, 542167814, 1 }
2305};
2306
2307/*
2308 * Checkup routine
2309 */
2310int mbedtls_mpi_self_test( int verbose )
2311{
2312 int ret, i;
2313 mbedtls_mpi A, E, N, X, Y, U, V;
2314
2315 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2316 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
2317
2318 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
2319 "EFE021C2645FD1DC586E69184AF4A31E" \
2320 "D5F53E93B5F123FA41680867BA110131" \
2321 "944FE7952E2517337780CB0DB80E61AA" \
2322 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2323
2324 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
2325 "B2E7EFD37075B9F03FF989C7C5051C20" \
2326 "34D2A323810251127E7BF8625A4F49A5" \
2327 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2328 "5B5C25763222FEFCCFC38B832366C29E" ) );
2329
2330 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
2331 "0066A198186C18C10B2F5ED9B522752A" \
2332 "9830B69916E535C8F047518A889A43A5" \
2333 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2334
2335 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
2336
2337 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2338 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2339 "9E857EA95A03512E2BAE7391688D264A" \
2340 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2341 "8001B72E848A38CAE1C65F78E56ABDEF" \
2342 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2343 "ECF677152EF804370C1A305CAF3B5BF1" \
2344 "30879B56C61DE584A0F53A2447A51E" ) );
2345
2346 if( verbose != 0 )
2347 mbedtls_printf( " MPI test #1 (mul_mpi): " );
2348
2349 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2350 {
2351 if( verbose != 0 )
2352 mbedtls_printf( "failed\n" );
2353
2354 ret = 1;
2355 goto cleanup;
2356 }
2357
2358 if( verbose != 0 )
2359 mbedtls_printf( "passed\n" );
2360
2361 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
2362
2363 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2364 "256567336059E52CAE22925474705F39A94" ) );
2365
2366 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
2367 "6613F26162223DF488E9CD48CC132C7A" \
2368 "0AC93C701B001B092E4E5B9F73BCD27B" \
2369 "9EE50D0657C77F374E903CDFA4C642" ) );
2370
2371 if( verbose != 0 )
2372 mbedtls_printf( " MPI test #2 (div_mpi): " );
2373
2374 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2375 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
2376 {
2377 if( verbose != 0 )
2378 mbedtls_printf( "failed\n" );
2379
2380 ret = 1;
2381 goto cleanup;
2382 }
2383
2384 if( verbose != 0 )
2385 mbedtls_printf( "passed\n" );
2386
2387 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
2388
2389 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2390 "36E139AEA55215609D2816998ED020BB" \
2391 "BD96C37890F65171D948E9BC7CBAA4D9" \
2392 "325D24D6A3C12710F10A09FA08AB87" ) );
2393
2394 if( verbose != 0 )
2395 mbedtls_printf( " MPI test #3 (exp_mod): " );
2396
2397 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2398 {
2399 if( verbose != 0 )
2400 mbedtls_printf( "failed\n" );
2401
2402 ret = 1;
2403 goto cleanup;
2404 }
2405
2406 if( verbose != 0 )
2407 mbedtls_printf( "passed\n" );
2408
2409 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
2410
2411 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2412 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2413 "C3DBA76456363A10869622EAC2DD84EC" \
2414 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2415
2416 if( verbose != 0 )
2417 mbedtls_printf( " MPI test #4 (inv_mod): " );
2418
2419 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2420 {
2421 if( verbose != 0 )
2422 mbedtls_printf( "failed\n" );
2423
2424 ret = 1;
2425 goto cleanup;
2426 }
2427
2428 if( verbose != 0 )
2429 mbedtls_printf( "passed\n" );
2430
2431 if( verbose != 0 )
2432 mbedtls_printf( " MPI test #5 (simple gcd): " );
2433
2434 for( i = 0; i < GCD_PAIR_COUNT; i++ )
2435 {
2436 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2437 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
2438
2439 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
2440
2441 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
2442 {
2443 if( verbose != 0 )
2444 mbedtls_printf( "failed at %d\n", i );
2445
2446 ret = 1;
2447 goto cleanup;
2448 }
2449 }
2450
2451 if( verbose != 0 )
2452 mbedtls_printf( "passed\n" );
2453
2454cleanup:
2455
2456 if( ret != 0 && verbose != 0 )
2457 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
2458
2459 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2460 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
2461
2462 if( verbose != 0 )
2463 mbedtls_printf( "\n" );
2464
2465 return( ret );
2466}
2467
2468#endif /* MBEDTLS_SELF_TEST */
2469
2470#endif /* MBEDTLS_BIGNUM_C */
Proxmark3 GIT tracking
Impressum, Datenschutz