projects / openwrt.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
brcm47xx: update bcma and ssb to master-2011-07-21
[openwrt.git] / package / px5g / src / library / bignum.c
1 /*
2 * Multi-precision integer library
3 *
4 * Based on XySSL: Copyright (C) 2006-2008 Christophe Devine
5 *
6 * Copyright (C) 2009 Paul Bakker <polarssl_maintainer at polarssl dot org>
7 *
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * * Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * * Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * * Neither the names of PolarSSL or XySSL nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35 /*
36 * This MPI implementation is based on:
37 *
38 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
39 * http://www.stillhq.com/extracted/gnupg-api/mpi/
40 * http://math.libtomcrypt.com/files/tommath.pdf
41 */
42
43 #include "polarssl/config.h"
44
45 #if defined(POLARSSL_BIGNUM_C)
46
47 #include "polarssl/bignum.h"
48 #include "polarssl/bn_mul.h"
49
50 #include <string.h>
51 #include <stdlib.h>
52 #include <stdarg.h>
53
54 #define ciL ((int) sizeof(t_int)) /* chars in limb */
55 #define biL (ciL << 3) /* bits in limb */
56 #define biH (ciL << 2) /* half limb size */
57
58 /*
59 * Convert between bits/chars and number of limbs
60 */
61 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
62 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
63
64 /*
65 * Initialize one or more mpi
66 */
67 void mpi_init( mpi *X, ... )
68 {
69 va_list args;
70
71 va_start( args, X );
72
73 while( X != NULL )
74 {
75 X->s = 1;
76 X->n = 0;
77 X->p = NULL;
78
79 X = va_arg( args, mpi* );
80 }
81
82 va_end( args );
83 }
84
85 /*
86 * Unallocate one or more mpi
87 */
88 void mpi_free( mpi *X, ... )
89 {
90 va_list args;
91
92 va_start( args, X );
93
94 while( X != NULL )
95 {
96 if( X->p != NULL )
97 {
98 memset( X->p, 0, X->n * ciL );
99 free( X->p );
100 }
101
102 X->s = 1;
103 X->n = 0;
104 X->p = NULL;
105
106 X = va_arg( args, mpi* );
107 }
108
109 va_end( args );
110 }
111
112 /*
113 * Enlarge to the specified number of limbs
114 */
115 int mpi_grow( mpi *X, int nblimbs )
116 {
117 t_int *p;
118
119 if( X->n < nblimbs )
120 {
121 if( ( p = (t_int *) malloc( nblimbs * ciL ) ) == NULL )
122 return( 1 );
123
124 memset( p, 0, nblimbs * ciL );
125
126 if( X->p != NULL )
127 {
128 memcpy( p, X->p, X->n * ciL );
129 memset( X->p, 0, X->n * ciL );
130 free( X->p );
131 }
132
133 X->n = nblimbs;
134 X->p = p;
135 }
136
137 return( 0 );
138 }
139
140 /*
141 * Copy the contents of Y into X
142 */
143 int mpi_copy( mpi *X, mpi *Y )
144 {
145 int ret, i;
146
147 if( X == Y )
148 return( 0 );
149
150 for( i = Y->n - 1; i > 0; i-- )
151 if( Y->p[i] != 0 )
152 break;
153 i++;
154
155 X->s = Y->s;
156
157 MPI_CHK( mpi_grow( X, i ) );
158
159 memset( X->p, 0, X->n * ciL );
160 memcpy( X->p, Y->p, i * ciL );
161
162 cleanup:
163
164 return( ret );
165 }
166
167 /*
168 * Swap the contents of X and Y
169 */
170 void mpi_swap( mpi *X, mpi *Y )
171 {
172 mpi T;
173
174 memcpy( &T, X, sizeof( mpi ) );
175 memcpy( X, Y, sizeof( mpi ) );
176 memcpy( Y, &T, sizeof( mpi ) );
177 }
178
179 /*
180 * Set value from integer
181 */
182 int mpi_lset( mpi *X, int z )
183 {
184 int ret;
185
186 MPI_CHK( mpi_grow( X, 1 ) );
187 memset( X->p, 0, X->n * ciL );
188
189 X->p[0] = ( z < 0 ) ? -z : z;
190 X->s = ( z < 0 ) ? -1 : 1;
191
192 cleanup:
193
194 return( ret );
195 }
196
197 /*
198 * Return the number of least significant bits
199 */
200 int mpi_lsb( mpi *X )
201 {
202 int i, j, count = 0;
203
204 for( i = 0; i < X->n; i++ )
205 for( j = 0; j < (int) biL; j++, count++ )
206 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
207 return( count );
208
209 return( 0 );
210 }
211
212 /*
213 * Return the number of most significant bits
214 */
215 int mpi_msb( mpi *X )
216 {
217 int i, j;
218
219 for( i = X->n - 1; i > 0; i-- )
220 if( X->p[i] != 0 )
221 break;
222
223 for( j = biL - 1; j >= 0; j-- )
224 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
225 break;
226
227 return( ( i * biL ) + j + 1 );
228 }
229
230 /*
231 * Return the total size in bytes
232 */
233 int mpi_size( mpi *X )
234 {
235 return( ( mpi_msb( X ) + 7 ) >> 3 );
236 }
237
238 /*
239 * Convert an ASCII character to digit value
240 */
241 static int mpi_get_digit( t_int *d, int radix, char c )
242 {
243 *d = 255;
244
245 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
246 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
247 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
248
249 if( *d >= (t_int) radix )
250 return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
251
252 return( 0 );
253 }
254
255 /*
256 * Import from an ASCII string
257 */
258 int mpi_read_string( mpi *X, int radix, char *s )
259 {
260 int ret, i, j, n;
261 t_int d;
262 mpi T;
263
264 if( radix < 2 || radix > 16 )
265 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
266
267 mpi_init( &T, NULL );
268
269 if( radix == 16 )
270 {
271 n = BITS_TO_LIMBS( strlen( s ) << 2 );
272
273 MPI_CHK( mpi_grow( X, n ) );
274 MPI_CHK( mpi_lset( X, 0 ) );
275
276 for( i = strlen( s ) - 1, j = 0; i >= 0; i--, j++ )
277 {
278 if( i == 0 && s[i] == '-' )
279 {
280 X->s = -1;
281 break;
282 }
283
284 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
285 X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
286 }
287 }
288 else
289 {
290 MPI_CHK( mpi_lset( X, 0 ) );
291
292 for( i = 0; i < (int) strlen( s ); i++ )
293 {
294 if( i == 0 && s[i] == '-' )
295 {
296 X->s = -1;
297 continue;
298 }
299
300 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
301 MPI_CHK( mpi_mul_int( &T, X, radix ) );
302 MPI_CHK( mpi_add_int( X, &T, d ) );
303 }
304 }
305
306 cleanup:
307
308 mpi_free( &T, NULL );
309
310 return( ret );
311 }
312
313 /*
314 * Helper to write the digits high-order first
315 */
316 static int mpi_write_hlp( mpi *X, int radix, char **p )
317 {
318 int ret;
319 t_int r;
320
321 if( radix < 2 || radix > 16 )
322 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
323
324 MPI_CHK( mpi_mod_int( &r, X, radix ) );
325 MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
326
327 if( mpi_cmp_int( X, 0 ) != 0 )
328 MPI_CHK( mpi_write_hlp( X, radix, p ) );
329
330 if( r < 10 )
331 *(*p)++ = (char)( r + 0x30 );
332 else
333 *(*p)++ = (char)( r + 0x37 );
334
335 cleanup:
336
337 return( ret );
338 }
339
340 /*
341 * Export into an ASCII string
342 */
343 int mpi_write_string( mpi *X, int radix, char *s, int *slen )
344 {
345 int ret = 0, n;
346 char *p;
347 mpi T;
348
349 if( radix < 2 || radix > 16 )
350 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
351
352 n = mpi_msb( X );
353 if( radix >= 4 ) n >>= 1;
354 if( radix >= 16 ) n >>= 1;
355 n += 3;
356
357 if( *slen < n )
358 {
359 *slen = n;
360 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
361 }
362
363 p = s;
364 mpi_init( &T, NULL );
365
366 if( X->s == -1 )
367 *p++ = '-';
368
369 if( radix == 16 )
370 {
371 int c, i, j, k;
372
373 for( i = X->n - 1, k = 0; i >= 0; i-- )
374 {
375 for( j = ciL - 1; j >= 0; j-- )
376 {
377 c = ( X->p[i] >> (j << 3) ) & 0xFF;
378
379 if( c == 0 && k == 0 && (i + j) != 0 )
380 continue;
381
382 p += sprintf( p, "%02X", c );
383 k = 1;
384 }
385 }
386 }
387 else
388 {
389 MPI_CHK( mpi_copy( &T, X ) );
390 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
391 }
392
393 *p++ = '\0';
394 *slen = p - s;
395
396 cleanup:
397
398 mpi_free( &T, NULL );
399
400 return( ret );
401 }
402
403 /*
404 * Read X from an opened file
405 */
406 int mpi_read_file( mpi *X, int radix, FILE *fin )
407 {
408 t_int d;
409 int slen;
410 char *p;
411 char s[1024];
412
413 memset( s, 0, sizeof( s ) );
414 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
415 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
416
417 slen = strlen( s );
418 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
419 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
420
421 p = s + slen;
422 while( --p >= s )
423 if( mpi_get_digit( &d, radix, *p ) != 0 )
424 break;
425
426 return( mpi_read_string( X, radix, p + 1 ) );
427 }
428
429 /*
430 * Write X into an opened file (or stdout if fout == NULL)
431 */
432 int mpi_write_file( char *p, mpi *X, int radix, FILE *fout )
433 {
434 int n, ret;
435 size_t slen;
436 size_t plen;
437 char s[1024];
438
439 n = sizeof( s );
440 memset( s, 0, n );
441 n -= 2;
442
443 MPI_CHK( mpi_write_string( X, radix, s, (int *) &n ) );
444
445 if( p == NULL ) p = "";
446
447 plen = strlen( p );
448 slen = strlen( s );
449 s[slen++] = '\r';
450 s[slen++] = '\n';
451
452 if( fout != NULL )
453 {
454 if( fwrite( p, 1, plen, fout ) != plen ||
455 fwrite( s, 1, slen, fout ) != slen )
456 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
457 }
458 else
459 printf( "%s%s", p, s );
460
461 cleanup:
462
463 return( ret );
464 }
465
466 /*
467 * Import X from unsigned binary data, big endian
468 */
469 int mpi_read_binary( mpi *X, unsigned char *buf, int buflen )
470 {
471 int ret, i, j, n;
472
473 for( n = 0; n < buflen; n++ )
474 if( buf[n] != 0 )
475 break;
476
477 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
478 MPI_CHK( mpi_lset( X, 0 ) );
479
480 for( i = buflen - 1, j = 0; i >= n; i--, j++ )
481 X->p[j / ciL] |= ((t_int) buf[i]) << ((j % ciL) << 3);
482
483 cleanup:
484
485 return( ret );
486 }
487
488 /*
489 * Export X into unsigned binary data, big endian
490 */
491 int mpi_write_binary( mpi *X, unsigned char *buf, int buflen )
492 {
493 int i, j, n;
494
495 n = mpi_size( X );
496
497 if( buflen < n )
498 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
499
500 memset( buf, 0, buflen );
501
502 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
503 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
504
505 return( 0 );
506 }
507
508 /*
509 * Left-shift: X <<= count
510 */
511 int mpi_shift_l( mpi *X, int count )
512 {
513 int ret, i, v0, t1;
514 t_int r0 = 0, r1;
515
516 v0 = count / (biL );
517 t1 = count & (biL - 1);
518
519 i = mpi_msb( X ) + count;
520
521 if( X->n * (int) biL < i )
522 MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
523
524 ret = 0;
525
526 /*
527 * shift by count / limb_size
528 */
529 if( v0 > 0 )
530 {
531 for( i = X->n - 1; i >= v0; i-- )
532 X->p[i] = X->p[i - v0];
533
534 for( ; i >= 0; i-- )
535 X->p[i] = 0;
536 }
537
538 /*
539 * shift by count % limb_size
540 */
541 if( t1 > 0 )
542 {
543 for( i = v0; i < X->n; i++ )
544 {
545 r1 = X->p[i] >> (biL - t1);
546 X->p[i] <<= t1;
547 X->p[i] |= r0;
548 r0 = r1;
549 }
550 }
551
552 cleanup:
553
554 return( ret );
555 }
556
557 /*
558 * Right-shift: X >>= count
559 */
560 int mpi_shift_r( mpi *X, int count )
561 {
562 int i, v0, v1;
563 t_int r0 = 0, r1;
564
565 v0 = count / biL;
566 v1 = count & (biL - 1);
567
568 /*
569 * shift by count / limb_size
570 */
571 if( v0 > 0 )
572 {
573 for( i = 0; i < X->n - v0; i++ )
574 X->p[i] = X->p[i + v0];
575
576 for( ; i < X->n; i++ )
577 X->p[i] = 0;
578 }
579
580 /*
581 * shift by count % limb_size
582 */
583 if( v1 > 0 )
584 {
585 for( i = X->n - 1; i >= 0; i-- )
586 {
587 r1 = X->p[i] << (biL - v1);
588 X->p[i] >>= v1;
589 X->p[i] |= r0;
590 r0 = r1;
591 }
592 }
593
594 return( 0 );
595 }
596
597 /*
598 * Compare unsigned values
599 */
600 int mpi_cmp_abs( mpi *X, mpi *Y )
601 {
602 int i, j;
603
604 for( i = X->n - 1; i >= 0; i-- )
605 if( X->p[i] != 0 )
606 break;
607
608 for( j = Y->n - 1; j >= 0; j-- )
609 if( Y->p[j] != 0 )
610 break;
611
612 if( i < 0 && j < 0 )
613 return( 0 );
614
615 if( i > j ) return( 1 );
616 if( j > i ) return( -1 );
617
618 for( ; i >= 0; i-- )
619 {
620 if( X->p[i] > Y->p[i] ) return( 1 );
621 if( X->p[i] < Y->p[i] ) return( -1 );
622 }
623
624 return( 0 );
625 }
626
627 /*
628 * Compare signed values
629 */
630 int mpi_cmp_mpi( mpi *X, mpi *Y )
631 {
632 int i, j;
633
634 for( i = X->n - 1; i >= 0; i-- )
635 if( X->p[i] != 0 )
636 break;
637
638 for( j = Y->n - 1; j >= 0; j-- )
639 if( Y->p[j] != 0 )
640 break;
641
642 if( i < 0 && j < 0 )
643 return( 0 );
644
645 if( i > j ) return( X->s );
646 if( j > i ) return( -X->s );
647
648 if( X->s > 0 && Y->s < 0 ) return( 1 );
649 if( Y->s > 0 && X->s < 0 ) return( -1 );
650
651 for( ; i >= 0; i-- )
652 {
653 if( X->p[i] > Y->p[i] ) return( X->s );
654 if( X->p[i] < Y->p[i] ) return( -X->s );
655 }
656
657 return( 0 );
658 }
659
660 /*
661 * Compare signed values
662 */
663 int mpi_cmp_int( mpi *X, int z )
664 {
665 mpi Y;
666 t_int p[1];
667
668 *p = ( z < 0 ) ? -z : z;
669 Y.s = ( z < 0 ) ? -1 : 1;
670 Y.n = 1;
671 Y.p = p;
672
673 return( mpi_cmp_mpi( X, &Y ) );
674 }
675
676 /*
677 * Unsigned addition: X = |A| + |B| (HAC 14.7)
678 */
679 int mpi_add_abs( mpi *X, mpi *A, mpi *B )
680 {
681 int ret, i, j;
682 t_int *o, *p, c;
683
684 if( X == B )
685 {
686 mpi *T = A; A = X; B = T;
687 }
688
689 if( X != A )
690 MPI_CHK( mpi_copy( X, A ) );
691
692 for( j = B->n - 1; j >= 0; j-- )
693 if( B->p[j] != 0 )
694 break;
695
696 MPI_CHK( mpi_grow( X, j + 1 ) );
697
698 o = B->p; p = X->p; c = 0;
699
700 for( i = 0; i <= j; i++, o++, p++ )
701 {
702 *p += c; c = ( *p < c );
703 *p += *o; c += ( *p < *o );
704 }
705
706 while( c != 0 )
707 {
708 if( i >= X->n )
709 {
710 MPI_CHK( mpi_grow( X, i + 1 ) );
711 p = X->p + i;
712 }
713
714 *p += c; c = ( *p < c ); i++;
715 }
716
717 cleanup:
718
719 return( ret );
720 }
721
722 /*
723 * Helper for mpi substraction
724 */
725 static void mpi_sub_hlp( int n, t_int *s, t_int *d )
726 {
727 int i;
728 t_int c, z;
729
730 for( i = c = 0; i < n; i++, s++, d++ )
731 {
732 z = ( *d < c ); *d -= c;
733 c = ( *d < *s ) + z; *d -= *s;
734 }
735
736 while( c != 0 )
737 {
738 z = ( *d < c ); *d -= c;
739 c = z; i++; d++;
740 }
741 }
742
743 /*
744 * Unsigned substraction: X = |A| - |B| (HAC 14.9)
745 */
746 int mpi_sub_abs( mpi *X, mpi *A, mpi *B )
747 {
748 mpi TB;
749 int ret, n;
750
751 if( mpi_cmp_abs( A, B ) < 0 )
752 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
753
754 mpi_init( &TB, NULL );
755
756 if( X == B )
757 {
758 MPI_CHK( mpi_copy( &TB, B ) );
759 B = &TB;
760 }
761
762 if( X != A )
763 MPI_CHK( mpi_copy( X, A ) );
764
765 ret = 0;
766
767 for( n = B->n - 1; n >= 0; n-- )
768 if( B->p[n] != 0 )
769 break;
770
771 mpi_sub_hlp( n + 1, B->p, X->p );
772
773 cleanup:
774
775 mpi_free( &TB, NULL );
776
777 return( ret );
778 }
779
780 /*
781 * Signed addition: X = A + B
782 */
783 int mpi_add_mpi( mpi *X, mpi *A, mpi *B )
784 {
785 int ret, s = A->s;
786
787 if( A->s * B->s < 0 )
788 {
789 if( mpi_cmp_abs( A, B ) >= 0 )
790 {
791 MPI_CHK( mpi_sub_abs( X, A, B ) );
792 X->s = s;
793 }
794 else
795 {
796 MPI_CHK( mpi_sub_abs( X, B, A ) );
797 X->s = -s;
798 }
799 }
800 else
801 {
802 MPI_CHK( mpi_add_abs( X, A, B ) );
803 X->s = s;
804 }
805
806 cleanup:
807
808 return( ret );
809 }
810
811 /*
812 * Signed substraction: X = A - B
813 */
814 int mpi_sub_mpi( mpi *X, mpi *A, mpi *B )
815 {
816 int ret, s = A->s;
817
818 if( A->s * B->s > 0 )
819 {
820 if( mpi_cmp_abs( A, B ) >= 0 )
821 {
822 MPI_CHK( mpi_sub_abs( X, A, B ) );
823 X->s = s;
824 }
825 else
826 {
827 MPI_CHK( mpi_sub_abs( X, B, A ) );
828 X->s = -s;
829 }
830 }
831 else
832 {
833 MPI_CHK( mpi_add_abs( X, A, B ) );
834 X->s = s;
835 }
836
837 cleanup:
838
839 return( ret );
840 }
841
842 /*
843 * Signed addition: X = A + b
844 */
845 int mpi_add_int( mpi *X, mpi *A, int b )
846 {
847 mpi _B;
848 t_int p[1];
849
850 p[0] = ( b < 0 ) ? -b : b;
851 _B.s = ( b < 0 ) ? -1 : 1;
852 _B.n = 1;
853 _B.p = p;
854
855 return( mpi_add_mpi( X, A, &_B ) );
856 }
857
858 /*
859 * Signed substraction: X = A - b
860 */
861 int mpi_sub_int( mpi *X, mpi *A, int b )
862 {
863 mpi _B;
864 t_int p[1];
865
866 p[0] = ( b < 0 ) ? -b : b;
867 _B.s = ( b < 0 ) ? -1 : 1;
868 _B.n = 1;
869 _B.p = p;
870
871 return( mpi_sub_mpi( X, A, &_B ) );
872 }
873
874 /*
875 * Helper for mpi multiplication
876 */
877 static void mpi_mul_hlp( int i, t_int *s, t_int *d, t_int b )
878 {
879 t_int c = 0, t = 0;
880
881 #if defined(MULADDC_HUIT)
882 for( ; i >= 8; i -= 8 )
883 {
884 MULADDC_INIT
885 MULADDC_HUIT
886 MULADDC_STOP
887 }
888
889 for( ; i > 0; i-- )
890 {
891 MULADDC_INIT
892 MULADDC_CORE
893 MULADDC_STOP
894 }
895 #else
896 for( ; i >= 16; i -= 16 )
897 {
898 MULADDC_INIT
899 MULADDC_CORE MULADDC_CORE
900 MULADDC_CORE MULADDC_CORE
901 MULADDC_CORE MULADDC_CORE
902 MULADDC_CORE MULADDC_CORE
903
904 MULADDC_CORE MULADDC_CORE
905 MULADDC_CORE MULADDC_CORE
906 MULADDC_CORE MULADDC_CORE
907 MULADDC_CORE MULADDC_CORE
908 MULADDC_STOP
909 }
910
911 for( ; i >= 8; i -= 8 )
912 {
913 MULADDC_INIT
914 MULADDC_CORE MULADDC_CORE
915 MULADDC_CORE MULADDC_CORE
916
917 MULADDC_CORE MULADDC_CORE
918 MULADDC_CORE MULADDC_CORE
919 MULADDC_STOP
920 }
921
922 for( ; i > 0; i-- )
923 {
924 MULADDC_INIT
925 MULADDC_CORE
926 MULADDC_STOP
927 }
928 #endif
929
930 t++;
931
932 do {
933 *d += c; c = ( *d < c ); d++;
934 }
935 while( c != 0 );
936 }
937
938 /*
939 * Baseline multiplication: X = A * B (HAC 14.12)
940 */
941 int mpi_mul_mpi( mpi *X, mpi *A, mpi *B )
942 {
943 int ret, i, j;
944 mpi TA, TB;
945
946 mpi_init( &TA, &TB, NULL );
947
948 if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
949 if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
950
951 for( i = A->n - 1; i >= 0; i-- )
952 if( A->p[i] != 0 )
953 break;
954
955 for( j = B->n - 1; j >= 0; j-- )
956 if( B->p[j] != 0 )
957 break;
958
959 MPI_CHK( mpi_grow( X, i + j + 2 ) );
960 MPI_CHK( mpi_lset( X, 0 ) );
961
962 for( i++; j >= 0; j-- )
963 mpi_mul_hlp( i, A->p, X->p + j, B->p[j] );
964
965 X->s = A->s * B->s;
966
967 cleanup:
968
969 mpi_free( &TB, &TA, NULL );
970
971 return( ret );
972 }
973
974 /*
975 * Baseline multiplication: X = A * b
976 */
977 int mpi_mul_int( mpi *X, mpi *A, t_int b )
978 {
979 mpi _B;
980 t_int p[1];
981
982 _B.s = 1;
983 _B.n = 1;
984 _B.p = p;
985 p[0] = b;
986
987 return( mpi_mul_mpi( X, A, &_B ) );
988 }
989
990 /*
991 * Division by mpi: A = Q * B + R (HAC 14.20)
992 */
993 int mpi_div_mpi( mpi *Q, mpi *R, mpi *A, mpi *B )
994 {
995 int ret, i, n, t, k;
996 mpi X, Y, Z, T1, T2;
997
998 if( mpi_cmp_int( B, 0 ) == 0 )
999 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1000
1001 mpi_init( &X, &Y, &Z, &T1, &T2, NULL );
1002
1003 if( mpi_cmp_abs( A, B ) < 0 )
1004 {
1005 if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
1006 if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
1007 return( 0 );
1008 }
1009
1010 MPI_CHK( mpi_copy( &X, A ) );
1011 MPI_CHK( mpi_copy( &Y, B ) );
1012 X.s = Y.s = 1;
1013
1014 MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
1015 MPI_CHK( mpi_lset( &Z, 0 ) );
1016 MPI_CHK( mpi_grow( &T1, 2 ) );
1017 MPI_CHK( mpi_grow( &T2, 3 ) );
1018
1019 k = mpi_msb( &Y ) % biL;
1020 if( k < (int) biL - 1 )
1021 {
1022 k = biL - 1 - k;
1023 MPI_CHK( mpi_shift_l( &X, k ) );
1024 MPI_CHK( mpi_shift_l( &Y, k ) );
1025 }
1026 else k = 0;
1027
1028 n = X.n - 1;
1029 t = Y.n - 1;
1030 mpi_shift_l( &Y, biL * (n - t) );
1031
1032 while( mpi_cmp_mpi( &X, &Y ) >= 0 )
1033 {
1034 Z.p[n - t]++;
1035 mpi_sub_mpi( &X, &X, &Y );
1036 }
1037 mpi_shift_r( &Y, biL * (n - t) );
1038
1039 for( i = n; i > t ; i-- )
1040 {
1041 if( X.p[i] >= Y.p[t] )
1042 Z.p[i - t - 1] = ~0;
1043 else
1044 {
1045 #if defined(POLARSSL_HAVE_LONGLONG)
1046 t_dbl r;
1047
1048 r = (t_dbl) X.p[i] << biL;
1049 r |= (t_dbl) X.p[i - 1];
1050 r /= Y.p[t];
1051 if( r > ((t_dbl) 1 << biL) - 1)
1052 r = ((t_dbl) 1 << biL) - 1;
1053
1054 Z.p[i - t - 1] = (t_int) r;
1055 #else
1056 /*
1057 * __udiv_qrnnd_c, from gmp/longlong.h
1058 */
1059 t_int q0, q1, r0, r1;
1060 t_int d0, d1, d, m;
1061
1062 d = Y.p[t];
1063 d0 = ( d << biH ) >> biH;
1064 d1 = ( d >> biH );
1065
1066 q1 = X.p[i] / d1;
1067 r1 = X.p[i] - d1 * q1;
1068 r1 <<= biH;
1069 r1 |= ( X.p[i - 1] >> biH );
1070
1071 m = q1 * d0;
1072 if( r1 < m )
1073 {
1074 q1--, r1 += d;
1075 while( r1 >= d && r1 < m )
1076 q1--, r1 += d;
1077 }
1078 r1 -= m;
1079
1080 q0 = r1 / d1;
1081 r0 = r1 - d1 * q0;
1082 r0 <<= biH;
1083 r0 |= ( X.p[i - 1] << biH ) >> biH;
1084
1085 m = q0 * d0;
1086 if( r0 < m )
1087 {
1088 q0--, r0 += d;
1089 while( r0 >= d && r0 < m )
1090 q0--, r0 += d;
1091 }
1092 r0 -= m;
1093
1094 Z.p[i - t - 1] = ( q1 << biH ) | q0;
1095 #endif
1096 }
1097
1098 Z.p[i - t - 1]++;
1099 do
1100 {
1101 Z.p[i - t - 1]--;
1102
1103 MPI_CHK( mpi_lset( &T1, 0 ) );
1104 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1105 T1.p[1] = Y.p[t];
1106 MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1107
1108 MPI_CHK( mpi_lset( &T2, 0 ) );
1109 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1110 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1111 T2.p[2] = X.p[i];
1112 }
1113 while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
1114
1115 MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1116 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1117 MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
1118
1119 if( mpi_cmp_int( &X, 0 ) < 0 )
1120 {
1121 MPI_CHK( mpi_copy( &T1, &Y ) );
1122 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1123 MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
1124 Z.p[i - t - 1]--;
1125 }
1126 }
1127
1128 if( Q != NULL )
1129 {
1130 mpi_copy( Q, &Z );
1131 Q->s = A->s * B->s;
1132 }
1133
1134 if( R != NULL )
1135 {
1136 mpi_shift_r( &X, k );
1137 mpi_copy( R, &X );
1138
1139 R->s = A->s;
1140 if( mpi_cmp_int( R, 0 ) == 0 )
1141 R->s = 1;
1142 }
1143
1144 cleanup:
1145
1146 mpi_free( &X, &Y, &Z, &T1, &T2, NULL );
1147
1148 return( ret );
1149 }
1150
1151 /*
1152 * Division by int: A = Q * b + R
1153 *
1154 * Returns 0 if successful
1155 * 1 if memory allocation failed
1156 * POLARSSL_ERR_MPI_DIVISION_BY_ZERO if b == 0
1157 */
1158 int mpi_div_int( mpi *Q, mpi *R, mpi *A, int b )
1159 {
1160 mpi _B;
1161 t_int p[1];
1162
1163 p[0] = ( b < 0 ) ? -b : b;
1164 _B.s = ( b < 0 ) ? -1 : 1;
1165 _B.n = 1;
1166 _B.p = p;
1167
1168 return( mpi_div_mpi( Q, R, A, &_B ) );
1169 }
1170
1171 /*
1172 * Modulo: R = A mod B
1173 */
1174 int mpi_mod_mpi( mpi *R, mpi *A, mpi *B )
1175 {
1176 int ret;
1177
1178 MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
1179
1180 while( mpi_cmp_int( R, 0 ) < 0 )
1181 MPI_CHK( mpi_add_mpi( R, R, B ) );
1182
1183 while( mpi_cmp_mpi( R, B ) >= 0 )
1184 MPI_CHK( mpi_sub_mpi( R, R, B ) );
1185
1186 cleanup:
1187
1188 return( ret );
1189 }
1190
1191 /*
1192 * Modulo: r = A mod b
1193 */
1194 int mpi_mod_int( t_int *r, mpi *A, int b )
1195 {
1196 int i;
1197 t_int x, y, z;
1198
1199 if( b == 0 )
1200 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1201
1202 if( b < 0 )
1203 b = -b;
1204
1205 /*
1206 * handle trivial cases
1207 */
1208 if( b == 1 )
1209 {
1210 *r = 0;
1211 return( 0 );
1212 }
1213
1214 if( b == 2 )
1215 {
1216 *r = A->p[0] & 1;
1217 return( 0 );
1218 }
1219
1220 /*
1221 * general case
1222 */
1223 for( i = A->n - 1, y = 0; i >= 0; i-- )
1224 {
1225 x = A->p[i];
1226 y = ( y << biH ) | ( x >> biH );
1227 z = y / b;
1228 y -= z * b;
1229
1230 x <<= biH;
1231 y = ( y << biH ) | ( x >> biH );
1232 z = y / b;
1233 y -= z * b;
1234 }
1235
1236 *r = y;
1237
1238 return( 0 );
1239 }
1240
1241 /*
1242 * Fast Montgomery initialization (thanks to Tom St Denis)
1243 */
1244 static void mpi_montg_init( t_int *mm, mpi *N )
1245 {
1246 t_int x, m0 = N->p[0];
1247
1248 x = m0;
1249 x += ( ( m0 + 2 ) & 4 ) << 1;
1250 x *= ( 2 - ( m0 * x ) );
1251
1252 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1253 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1254 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1255
1256 *mm = ~x + 1;
1257 }
1258
1259 /*
1260 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1261 */
1262 static void mpi_montmul( mpi *A, mpi *B, mpi *N, t_int mm, mpi *T )
1263 {
1264 int i, n, m;
1265 t_int u0, u1, *d;
1266
1267 memset( T->p, 0, T->n * ciL );
1268
1269 d = T->p;
1270 n = N->n;
1271 m = ( B->n < n ) ? B->n : n;
1272
1273 for( i = 0; i < n; i++ )
1274 {
1275 /*
1276 * T = (T + u0*B + u1*N) / 2^biL
1277 */
1278 u0 = A->p[i];
1279 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1280
1281 mpi_mul_hlp( m, B->p, d, u0 );
1282 mpi_mul_hlp( n, N->p, d, u1 );
1283
1284 *d++ = u0; d[n + 1] = 0;
1285 }
1286
1287 memcpy( A->p, d, (n + 1) * ciL );
1288
1289 if( mpi_cmp_abs( A, N ) >= 0 )
1290 mpi_sub_hlp( n, N->p, A->p );
1291 else
1292 /* prevent timing attacks */
1293 mpi_sub_hlp( n, A->p, T->p );
1294 }
1295
1296 /*
1297 * Montgomery reduction: A = A * R^-1 mod N
1298 */
1299 static void mpi_montred( mpi *A, mpi *N, t_int mm, mpi *T )
1300 {
1301 t_int z = 1;
1302 mpi U;
1303
1304 U.n = U.s = z;
1305 U.p = &z;
1306
1307 mpi_montmul( A, &U, N, mm, T );
1308 }
1309
1310 /*
1311 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1312 */
1313 int mpi_exp_mod( mpi *X, mpi *A, mpi *E, mpi *N, mpi *_RR )
1314 {
1315 int ret, i, j, wsize, wbits;
1316 int bufsize, nblimbs, nbits;
1317 t_int ei, mm, state;
1318 mpi RR, T, W[64];
1319
1320 if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
1321 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1322
1323 /*
1324 * Init temps and window size
1325 */
1326 mpi_montg_init( &mm, N );
1327 mpi_init( &RR, &T, NULL );
1328 memset( W, 0, sizeof( W ) );
1329
1330 i = mpi_msb( E );
1331
1332 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1333 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1334
1335 j = N->n + 1;
1336 MPI_CHK( mpi_grow( X, j ) );
1337 MPI_CHK( mpi_grow( &W[1], j ) );
1338 MPI_CHK( mpi_grow( &T, j * 2 ) );
1339
1340 /*
1341 * If 1st call, pre-compute R^2 mod N
1342 */
1343 if( _RR == NULL || _RR->p == NULL )
1344 {
1345 MPI_CHK( mpi_lset( &RR, 1 ) );
1346 MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
1347 MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
1348
1349 if( _RR != NULL )
1350 memcpy( _RR, &RR, sizeof( mpi ) );
1351 }
1352 else
1353 memcpy( &RR, _RR, sizeof( mpi ) );
1354
1355 /*
1356 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1357 */
1358 if( mpi_cmp_mpi( A, N ) >= 0 )
1359 mpi_mod_mpi( &W[1], A, N );
1360 else mpi_copy( &W[1], A );
1361
1362 mpi_montmul( &W[1], &RR, N, mm, &T );
1363
1364 /*
1365 * X = R^2 * R^-1 mod N = R mod N
1366 */
1367 MPI_CHK( mpi_copy( X, &RR ) );
1368 mpi_montred( X, N, mm, &T );
1369
1370 if( wsize > 1 )
1371 {
1372 /*
1373 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1374 */
1375 j = 1 << (wsize - 1);
1376
1377 MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
1378 MPI_CHK( mpi_copy( &W[j], &W[1] ) );
1379
1380 for( i = 0; i < wsize - 1; i++ )
1381 mpi_montmul( &W[j], &W[j], N, mm, &T );
1382
1383 /*
1384 * W[i] = W[i - 1] * W[1]
1385 */
1386 for( i = j + 1; i < (1 << wsize); i++ )
1387 {
1388 MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
1389 MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
1390
1391 mpi_montmul( &W[i], &W[1], N, mm, &T );
1392 }
1393 }
1394
1395 nblimbs = E->n;
1396 bufsize = 0;
1397 nbits = 0;
1398 wbits = 0;
1399 state = 0;
1400
1401 while( 1 )
1402 {
1403 if( bufsize == 0 )
1404 {
1405 if( nblimbs-- == 0 )
1406 break;
1407
1408 bufsize = sizeof( t_int ) << 3;
1409 }
1410
1411 bufsize--;
1412
1413 ei = (E->p[nblimbs] >> bufsize) & 1;
1414
1415 /*
1416 * skip leading 0s
1417 */
1418 if( ei == 0 && state == 0 )
1419 continue;
1420
1421 if( ei == 0 && state == 1 )
1422 {
1423 /*
1424 * out of window, square X
1425 */
1426 mpi_montmul( X, X, N, mm, &T );
1427 continue;
1428 }
1429
1430 /*
1431 * add ei to current window
1432 */
1433 state = 2;
1434
1435 nbits++;
1436 wbits |= (ei << (wsize - nbits));
1437
1438 if( nbits == wsize )
1439 {
1440 /*
1441 * X = X^wsize R^-1 mod N
1442 */
1443 for( i = 0; i < wsize; i++ )
1444 mpi_montmul( X, X, N, mm, &T );
1445
1446 /*
1447 * X = X * W[wbits] R^-1 mod N
1448 */
1449 mpi_montmul( X, &W[wbits], N, mm, &T );
1450
1451 state--;
1452 nbits = 0;
1453 wbits = 0;
1454 }
1455 }
1456
1457 /*
1458 * process the remaining bits
1459 */
1460 for( i = 0; i < nbits; i++ )
1461 {
1462 mpi_montmul( X, X, N, mm, &T );
1463
1464 wbits <<= 1;
1465
1466 if( (wbits & (1 << wsize)) != 0 )
1467 mpi_montmul( X, &W[1], N, mm, &T );
1468 }
1469
1470 /*
1471 * X = A^E * R * R^-1 mod N = A^E mod N
1472 */
1473 mpi_montred( X, N, mm, &T );
1474
1475 cleanup:
1476
1477 for( i = (1 << (wsize - 1)); i < (1 << wsize); i++ )
1478 mpi_free( &W[i], NULL );
1479
1480 if( _RR != NULL )
1481 mpi_free( &W[1], &T, NULL );
1482 else mpi_free( &W[1], &T, &RR, NULL );
1483
1484 return( ret );
1485 }
1486
1487 /*
1488 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1489 */
1490 int mpi_gcd( mpi *G, mpi *A, mpi *B )
1491 {
1492 int ret, lz, lzt;
1493 mpi TG, TA, TB;
1494
1495 mpi_init( &TG, &TA, &TB, NULL );
1496
1497 MPI_CHK( mpi_copy( &TA, A ) );
1498 MPI_CHK( mpi_copy( &TB, B ) );
1499
1500 lz = mpi_lsb( &TA );
1501 lzt = mpi_lsb( &TB );
1502
1503 if ( lzt < lz )
1504 lz = lzt;
1505
1506 MPI_CHK( mpi_shift_r( &TA, lz ) );
1507 MPI_CHK( mpi_shift_r( &TB, lz ) );
1508
1509 TA.s = TB.s = 1;
1510
1511 while( mpi_cmp_int( &TA, 0 ) != 0 )
1512 {
1513 MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
1514 MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
1515
1516 if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
1517 {
1518 MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
1519 MPI_CHK( mpi_shift_r( &TA, 1 ) );
1520 }
1521 else
1522 {
1523 MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
1524 MPI_CHK( mpi_shift_r( &TB, 1 ) );
1525 }
1526 }
1527
1528 MPI_CHK( mpi_shift_l( &TB, lz ) );
1529 MPI_CHK( mpi_copy( G, &TB ) );
1530
1531 cleanup:
1532
1533 mpi_free( &TB, &TA, &TG, NULL );
1534
1535 return( ret );
1536 }
1537
1538 #if defined(POLARSSL_GENPRIME)
1539
1540 /*
1541 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1542 */
1543 int mpi_inv_mod( mpi *X, mpi *A, mpi *N )
1544 {
1545 int ret;
1546 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1547
1548 if( mpi_cmp_int( N, 0 ) <= 0 )
1549 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1550
1551 mpi_init( &TA, &TU, &U1, &U2, &G,
1552 &TB, &TV, &V1, &V2, NULL );
1553
1554 MPI_CHK( mpi_gcd( &G, A, N ) );
1555
1556 if( mpi_cmp_int( &G, 1 ) != 0 )
1557 {
1558 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1559 goto cleanup;
1560 }
1561
1562 MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
1563 MPI_CHK( mpi_copy( &TU, &TA ) );
1564 MPI_CHK( mpi_copy( &TB, N ) );
1565 MPI_CHK( mpi_copy( &TV, N ) );
1566
1567 MPI_CHK( mpi_lset( &U1, 1 ) );
1568 MPI_CHK( mpi_lset( &U2, 0 ) );
1569 MPI_CHK( mpi_lset( &V1, 0 ) );
1570 MPI_CHK( mpi_lset( &V2, 1 ) );
1571
1572 do
1573 {
1574 while( ( TU.p[0] & 1 ) == 0 )
1575 {
1576 MPI_CHK( mpi_shift_r( &TU, 1 ) );
1577
1578 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1579 {
1580 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
1581 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
1582 }
1583
1584 MPI_CHK( mpi_shift_r( &U1, 1 ) );
1585 MPI_CHK( mpi_shift_r( &U2, 1 ) );
1586 }
1587
1588 while( ( TV.p[0] & 1 ) == 0 )
1589 {
1590 MPI_CHK( mpi_shift_r( &TV, 1 ) );
1591
1592 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1593 {
1594 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
1595 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
1596 }
1597
1598 MPI_CHK( mpi_shift_r( &V1, 1 ) );
1599 MPI_CHK( mpi_shift_r( &V2, 1 ) );
1600 }
1601
1602 if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
1603 {
1604 MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
1605 MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
1606 MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
1607 }
1608 else
1609 {
1610 MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
1611 MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
1612 MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
1613 }
1614 }
1615 while( mpi_cmp_int( &TU, 0 ) != 0 );
1616
1617 while( mpi_cmp_int( &V1, 0 ) < 0 )
1618 MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
1619
1620 while( mpi_cmp_mpi( &V1, N ) >= 0 )
1621 MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
1622
1623 MPI_CHK( mpi_copy( X, &V1 ) );
1624
1625 cleanup:
1626
1627 mpi_free( &V2, &V1, &TV, &TB, &G,
1628 &U2, &U1, &TU, &TA, NULL );
1629
1630 return( ret );
1631 }
1632
1633 static const int small_prime[] =
1634 {
1635 3, 5, 7, 11, 13, 17, 19, 23,
1636 29, 31, 37, 41, 43, 47, 53, 59,
1637 61, 67, 71, 73, 79, 83, 89, 97,
1638 101, 103, 107, 109, 113, 127, 131, 137,
1639 139, 149, 151, 157, 163, 167, 173, 179,
1640 181, 191, 193, 197, 199, 211, 223, 227,
1641 229, 233, 239, 241, 251, 257, 263, 269,
1642 271, 277, 281, 283, 293, 307, 311, 313,
1643 317, 331, 337, 347, 349, 353, 359, 367,
1644 373, 379, 383, 389, 397, 401, 409, 419,
1645 421, 431, 433, 439, 443, 449, 457, 461,
1646 463, 467, 479, 487, 491, 499, 503, 509,
1647 521, 523, 541, 547, 557, 563, 569, 571,
1648 577, 587, 593, 599, 601, 607, 613, 617,
1649 619, 631, 641, 643, 647, 653, 659, 661,
1650 673, 677, 683, 691, 701, 709, 719, 727,
1651 733, 739, 743, 751, 757, 761, 769, 773,
1652 787, 797, 809, 811, 821, 823, 827, 829,
1653 839, 853, 857, 859, 863, 877, 881, 883,
1654 887, 907, 911, 919, 929, 937, 941, 947,
1655 953, 967, 971, 977, 983, 991, 997, -103
1656 };
1657
1658 /*
1659 * Miller-Rabin primality test (HAC 4.24)
1660 */
1661 int mpi_is_prime( mpi *X, int (*f_rng)(void *), void *p_rng )
1662 {
1663 int ret, i, j, n, s, xs;
1664 mpi W, R, T, A, RR;
1665 unsigned char *p;
1666
1667 if( mpi_cmp_int( X, 0 ) == 0 )
1668 return( 0 );
1669
1670 mpi_init( &W, &R, &T, &A, &RR, NULL );
1671
1672 xs = X->s; X->s = 1;
1673
1674 /*
1675 * test trivial factors first
1676 */
1677 if( ( X->p[0] & 1 ) == 0 )
1678 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1679
1680 for( i = 0; small_prime[i] > 0; i++ )
1681 {
1682 t_int r;
1683
1684 if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
1685 return( 0 );
1686
1687 MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
1688
1689 if( r == 0 )
1690 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1691 }
1692
1693 /*
1694 * W = |X| - 1
1695 * R = W >> lsb( W )
1696 */
1697 s = mpi_lsb( &W );
1698 MPI_CHK( mpi_sub_int( &W, X, 1 ) );
1699 MPI_CHK( mpi_copy( &R, &W ) );
1700 MPI_CHK( mpi_shift_r( &R, s ) );
1701
1702 i = mpi_msb( X );
1703 /*
1704 * HAC, table 4.4
1705 */
1706 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1707 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1708 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1709
1710 for( i = 0; i < n; i++ )
1711 {
1712 /*
1713 * pick a random A, 1 < A < |X| - 1
1714 */
1715 MPI_CHK( mpi_grow( &A, X->n ) );
1716
1717 p = (unsigned char *) A.p;
1718 for( j = 0; j < A.n * ciL; j++ )
1719 *p++ = (unsigned char) f_rng( p_rng );
1720
1721 j = mpi_msb( &A ) - mpi_msb( &W );
1722 MPI_CHK( mpi_shift_r( &A, j + 1 ) );
1723 A.p[0] |= 3;
1724
1725 /*
1726 * A = A^R mod |X|
1727 */
1728 MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
1729
1730 if( mpi_cmp_mpi( &A, &W ) == 0 ||
1731 mpi_cmp_int( &A, 1 ) == 0 )
1732 continue;
1733
1734 j = 1;
1735 while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
1736 {
1737 /*
1738 * A = A * A mod |X|
1739 */
1740 MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
1741 MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
1742
1743 if( mpi_cmp_int( &A, 1 ) == 0 )
1744 break;
1745
1746 j++;
1747 }
1748
1749 /*
1750 * not prime if A != |X| - 1 or A == 1
1751 */
1752 if( mpi_cmp_mpi( &A, &W ) != 0 ||
1753 mpi_cmp_int( &A, 1 ) == 0 )
1754 {
1755 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1756 break;
1757 }
1758 }
1759
1760 cleanup:
1761
1762 X->s = xs;
1763
1764 mpi_free( &RR, &A, &T, &R, &W, NULL );
1765
1766 return( ret );
1767 }
1768
1769 /*
1770 * Prime number generation
1771 */
1772 int mpi_gen_prime( mpi *X, int nbits, int dh_flag,
1773 int (*f_rng)(void *), void *p_rng )
1774 {
1775 int ret, k, n;
1776 unsigned char *p;
1777 mpi Y;
1778
1779 if( nbits < 3 )
1780 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1781
1782 mpi_init( &Y, NULL );
1783
1784 n = BITS_TO_LIMBS( nbits );
1785
1786 MPI_CHK( mpi_grow( X, n ) );
1787 MPI_CHK( mpi_lset( X, 0 ) );
1788
1789 p = (unsigned char *) X->p;
1790 for( k = 0; k < X->n * ciL; k++ )
1791 *p++ = (unsigned char) f_rng( p_rng );
1792
1793 k = mpi_msb( X );
1794 if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
1795 if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
1796
1797 X->p[0] |= 3;
1798
1799 if( dh_flag == 0 )
1800 {
1801 while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1802 {
1803 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1804 goto cleanup;
1805
1806 MPI_CHK( mpi_add_int( X, X, 2 ) );
1807 }
1808 }
1809 else
1810 {
1811 MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
1812 MPI_CHK( mpi_shift_r( &Y, 1 ) );
1813
1814 while( 1 )
1815 {
1816 if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
1817 {
1818 if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
1819 break;
1820
1821 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1822 goto cleanup;
1823 }
1824
1825 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
1826 goto cleanup;
1827
1828 MPI_CHK( mpi_add_int( &Y, X, 1 ) );
1829 MPI_CHK( mpi_add_int( X, X, 2 ) );
1830 MPI_CHK( mpi_shift_r( &Y, 1 ) );
1831 }
1832 }
1833
1834 cleanup:
1835
1836 mpi_free( &Y, NULL );
1837
1838 return( ret );
1839 }
1840
1841 #endif
1842
1843 #if defined(POLARSSL_SELF_TEST)
1844
1845 #define GCD_PAIR_COUNT 3
1846
1847 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1848 {
1849 { 693, 609, 21 },
1850 { 1764, 868, 28 },
1851 { 768454923, 542167814, 1 }
1852 };
1853
1854 /*
1855 * Checkup routine
1856 */
1857 int mpi_self_test( int verbose )
1858 {
1859 int ret, i;
1860 mpi A, E, N, X, Y, U, V;
1861
1862 mpi_init( &A, &E, &N, &X, &Y, &U, &V, NULL );
1863
1864 MPI_CHK( mpi_read_string( &A, 16,
1865 "EFE021C2645FD1DC586E69184AF4A31E" \
1866 "D5F53E93B5F123FA41680867BA110131" \
1867 "944FE7952E2517337780CB0DB80E61AA" \
1868 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
1869
1870 MPI_CHK( mpi_read_string( &E, 16,
1871 "B2E7EFD37075B9F03FF989C7C5051C20" \
1872 "34D2A323810251127E7BF8625A4F49A5" \
1873 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
1874 "5B5C25763222FEFCCFC38B832366C29E" ) );
1875
1876 MPI_CHK( mpi_read_string( &N, 16,
1877 "0066A198186C18C10B2F5ED9B522752A" \
1878 "9830B69916E535C8F047518A889A43A5" \
1879 "94B6BED27A168D31D4A52F88925AA8F5" ) );
1880
1881 MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
1882
1883 MPI_CHK( mpi_read_string( &U, 16,
1884 "602AB7ECA597A3D6B56FF9829A5E8B85" \
1885 "9E857EA95A03512E2BAE7391688D264A" \
1886 "A5663B0341DB9CCFD2C4C5F421FEC814" \
1887 "8001B72E848A38CAE1C65F78E56ABDEF" \
1888 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
1889 "ECF677152EF804370C1A305CAF3B5BF1" \
1890 "30879B56C61DE584A0F53A2447A51E" ) );
1891
1892 if( verbose != 0 )
1893 printf( " MPI test #1 (mul_mpi): " );
1894
1895 if( mpi_cmp_mpi( &X, &U ) != 0 )
1896 {
1897 if( verbose != 0 )
1898 printf( "failed\n" );
1899
1900 return( 1 );
1901 }
1902
1903 if( verbose != 0 )
1904 printf( "passed\n" );
1905
1906 MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
1907
1908 MPI_CHK( mpi_read_string( &U, 16,
1909 "256567336059E52CAE22925474705F39A94" ) );
1910
1911 MPI_CHK( mpi_read_string( &V, 16,
1912 "6613F26162223DF488E9CD48CC132C7A" \
1913 "0AC93C701B001B092E4E5B9F73BCD27B" \
1914 "9EE50D0657C77F374E903CDFA4C642" ) );
1915
1916 if( verbose != 0 )
1917 printf( " MPI test #2 (div_mpi): " );
1918
1919 if( mpi_cmp_mpi( &X, &U ) != 0 ||
1920 mpi_cmp_mpi( &Y, &V ) != 0 )
1921 {
1922 if( verbose != 0 )
1923 printf( "failed\n" );
1924
1925 return( 1 );
1926 }
1927
1928 if( verbose != 0 )
1929 printf( "passed\n" );
1930
1931 MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
1932
1933 MPI_CHK( mpi_read_string( &U, 16,
1934 "36E139AEA55215609D2816998ED020BB" \
1935 "BD96C37890F65171D948E9BC7CBAA4D9" \
1936 "325D24D6A3C12710F10A09FA08AB87" ) );
1937
1938 if( verbose != 0 )
1939 printf( " MPI test #3 (exp_mod): " );
1940
1941 if( mpi_cmp_mpi( &X, &U ) != 0 )
1942 {
1943 if( verbose != 0 )
1944 printf( "failed\n" );
1945
1946 return( 1 );
1947 }
1948
1949 if( verbose != 0 )
1950 printf( "passed\n" );
1951
1952 MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
1953
1954 MPI_CHK( mpi_read_string( &U, 16,
1955 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
1956 "C3DBA76456363A10869622EAC2DD84EC" \
1957 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
1958
1959 if( verbose != 0 )
1960 printf( " MPI test #4 (inv_mod): " );
1961
1962 if( mpi_cmp_mpi( &X, &U ) != 0 )
1963 {
1964 if( verbose != 0 )
1965 printf( "failed\n" );
1966
1967 return( 1 );
1968 }
1969
1970 if( verbose != 0 )
1971 printf( "passed\n" );
1972
1973 if( verbose != 0 )
1974 printf( " MPI test #5 (simple gcd): " );
1975
1976 for ( i = 0; i < GCD_PAIR_COUNT; i++)
1977 {
1978 MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
1979 MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
1980
1981 MPI_CHK( mpi_gcd( &A, &X, &Y ) );
1982
1983 if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
1984 {
1985 if( verbose != 0 )
1986 printf( "failed at %d\n", i );
1987
1988 return( 1 );
1989 }
1990 }
1991
1992 if( verbose != 0 )
1993 printf( "passed\n" );
1994
1995 cleanup:
1996
1997 if( ret != 0 && verbose != 0 )
1998 printf( "Unexpected error, return code = %08X\n", ret );
1999
2000 mpi_free( &V, &U, &Y, &X, &N, &E, &A, NULL );
2001
2002 if( verbose != 0 )
2003 printf( "\n" );
2004
2005 return( ret );
2006 }
2007
2008 #endif
2009
2010 #endif
Personal OpenWRT clone
This page took 0.136876 seconds and 5 git commands to generate.