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