projects / reactos.git / blob
? search:


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