projects / reactos.git / blob
? search:


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