1 /*
2 * Multi-precision integer library
3 *
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 *
7 * This file is provided under the Apache License 2.0, or the
8 * GNU General Public License v2.0 or later.
9 *
10 * **********
11 * Apache License 2.0:
12 *
13 * Licensed under the Apache License, Version 2.0 (the "License"); you may
14 * not use this file except in compliance with the License.
15 * You may obtain a copy of the License at
16 *
17 * http://www.apache.org/licenses/LICENSE-2.0
18 *
19 * Unless required by applicable law or agreed to in writing, software
20 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
21 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
22 * See the License for the specific language governing permissions and
23 * limitations under the License.
24 *
25 * **********
26 *
27 * **********
28 * GNU General Public License v2.0 or later:
29 *
30 * This program is free software; you can redistribute it and/or modify
31 * it under the terms of the GNU General Public License as published by
32 * the Free Software Foundation; either version 2 of the License, or
33 * (at your option) any later version.
34 *
35 * This program is distributed in the hope that it will be useful,
36 * but WITHOUT ANY WARRANTY; without even the implied warranty of
37 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
38 * GNU General Public License for more details.
39 *
40 * You should have received a copy of the GNU General Public License along
41 * with this program; if not, write to the Free Software Foundation, Inc.,
42 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
43 *
44 * **********
45 */
46
47 /*
48 * The following sources were referenced in the design of this Multi-precision
49 * Integer library:
50 *
51 * [1] Handbook of Applied Cryptography - 1997
52 * Menezes, van Oorschot and Vanstone
53 *
54 * [2] Multi-Precision Math
55 * Tom St Denis
56 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
57 *
58 * [3] GNU Multi-Precision Arithmetic Library
59 * https://gmplib.org/manual/index.html
60 *
61 */
62
63 #if !defined(MBEDTLS_CONFIG_FILE)
64 #include "mbedtls/config.h"
65 #else
66 #include MBEDTLS_CONFIG_FILE
67 #endif
68
69 #if defined(MBEDTLS_BIGNUM_C)
70
71 #include "mbedtls/bignum.h"
72 #include "mbedtls/bn_mul.h"
73 #include "mbedtls/platform_util.h"
74
75 #include <string.h>
76
77 #if defined(MBEDTLS_PLATFORM_C)
78 #include "mbedtls/platform.h"
79 #else
80 #include <stdio.h>
81 #include <stdlib.h>
82 #define mbedtls_printf printf
83 #define mbedtls_calloc calloc
84 #define mbedtls_free free
85 #endif
86
87 #define MPI_VALIDATE_RET( cond ) \
88 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
89 #define MPI_VALIDATE( cond ) \
90 MBEDTLS_INTERNAL_VALIDATE( cond )
91
92 #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
93 #define biL (ciL << 3) /* bits in limb */
94 #define biH (ciL << 2) /* half limb size */
95
96 #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
97
98 /*
99 * Convert between bits/chars and number of limbs
100 * Divide first in order to avoid potential overflows
101 */
102 #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
103 #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
104
105 /* Implementation that should never be optimized out by the compiler */
mbedtls_mpi_zeroize(mbedtls_mpi_uint * v,size_t n)106 static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
107 {
108 mbedtls_platform_zeroize( v, ciL * n );
109 }
110
111 /*
112 * Initialize one MPI
113 */
mbedtls_mpi_init(mbedtls_mpi * X)114 void mbedtls_mpi_init( mbedtls_mpi *X )
115 {
116 MPI_VALIDATE( X != NULL );
117
118 X->s = 1;
119 X->n = 0;
120 X->p = NULL;
121 }
122
123 /*
124 * Unallocate one MPI
125 */
mbedtls_mpi_free(mbedtls_mpi * X)126 void mbedtls_mpi_free( mbedtls_mpi *X )
127 {
128 if( X == NULL )
129 return;
130
131 if( X->p != NULL )
132 {
133 mbedtls_mpi_zeroize( X->p, X->n );
134 mbedtls_free( X->p );
135 }
136
137 X->s = 1;
138 X->n = 0;
139 X->p = NULL;
140 }
141
142 /*
143 * Enlarge to the specified number of limbs
144 */
mbedtls_mpi_grow(mbedtls_mpi * X,size_t nblimbs)145 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
146 {
147 mbedtls_mpi_uint *p;
148 MPI_VALIDATE_RET( X != NULL );
149
150 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
151 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
152
153 if( X->n < nblimbs )
154 {
155 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
156 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
157
158 if( X->p != NULL )
159 {
160 memcpy( p, X->p, X->n * ciL );
161 mbedtls_mpi_zeroize( X->p, X->n );
162 mbedtls_free( X->p );
163 }
164
165 X->n = nblimbs;
166 X->p = p;
167 }
168
169 return( 0 );
170 }
171
172 /*
173 * Resize down as much as possible,
174 * while keeping at least the specified number of limbs
175 */
mbedtls_mpi_shrink(mbedtls_mpi * X,size_t nblimbs)176 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
177 {
178 mbedtls_mpi_uint *p;
179 size_t i;
180 MPI_VALIDATE_RET( X != NULL );
181
182 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
183 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
184
185 /* Actually resize up if there are currently fewer than nblimbs limbs. */
186 if( X->n <= nblimbs )
187 return( mbedtls_mpi_grow( X, nblimbs ) );
188 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
189
190 for( i = X->n - 1; i > 0; i-- )
191 if( X->p[i] != 0 )
192 break;
193 i++;
194
195 if( i < nblimbs )
196 i = nblimbs;
197
198 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
199 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
200
201 if( X->p != NULL )
202 {
203 memcpy( p, X->p, i * ciL );
204 mbedtls_mpi_zeroize( X->p, X->n );
205 mbedtls_free( X->p );
206 }
207
208 X->n = i;
209 X->p = p;
210
211 return( 0 );
212 }
213
214 /*
215 * Copy the contents of Y into X
216 */
mbedtls_mpi_copy(mbedtls_mpi * X,const mbedtls_mpi * Y)217 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
218 {
219 int ret = 0;
220 size_t i;
221 MPI_VALIDATE_RET( X != NULL );
222 MPI_VALIDATE_RET( Y != NULL );
223
224 if( X == Y )
225 return( 0 );
226
227 if( Y->n == 0 )
228 {
229 mbedtls_mpi_free( X );
230 return( 0 );
231 }
232
233 for( i = Y->n - 1; i > 0; i-- )
234 if( Y->p[i] != 0 )
235 break;
236 i++;
237
238 X->s = Y->s;
239
240 if( X->n < i )
241 {
242 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
243 }
244 else
245 {
246 memset( X->p + i, 0, ( X->n - i ) * ciL );
247 }
248
249 memcpy( X->p, Y->p, i * ciL );
250
251 cleanup:
252
253 return( ret );
254 }
255
256 /*
257 * Swap the contents of X and Y
258 */
mbedtls_mpi_swap(mbedtls_mpi * X,mbedtls_mpi * Y)259 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
260 {
261 mbedtls_mpi T;
262 MPI_VALIDATE( X != NULL );
263 MPI_VALIDATE( Y != NULL );
264
265 memcpy( &T, X, sizeof( mbedtls_mpi ) );
266 memcpy( X, Y, sizeof( mbedtls_mpi ) );
267 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
268 }
269
270 /**
271 * Select between two sign values in constant-time.
272 *
273 * This is functionally equivalent to second ? a : b but uses only bit
274 * operations in order to avoid branches.
275 *
276 * \param[in] a The first sign; must be either +1 or -1.
277 * \param[in] b The second sign; must be either +1 or -1.
278 * \param[in] second Must be either 1 (return b) or 0 (return a).
279 *
280 * \return The selected sign value.
281 */
mpi_safe_cond_select_sign(int a,int b,unsigned char second)282 static int mpi_safe_cond_select_sign( int a, int b, unsigned char second )
283 {
284 /* In order to avoid questions about what we can reasonnably assume about
285 * the representations of signed integers, move everything to unsigned
286 * by taking advantage of the fact that a and b are either +1 or -1. */
287 unsigned ua = a + 1;
288 unsigned ub = b + 1;
289
290 /* second was 0 or 1, mask is 0 or 2 as are ua and ub */
291 const unsigned mask = second << 1;
292
293 /* select ua or ub */
294 unsigned ur = ( ua & ~mask ) | ( ub & mask );
295
296 /* ur is now 0 or 2, convert back to -1 or +1 */
297 return( (int) ur - 1 );
298 }
299
300 /*
301 * Conditionally assign dest = src, without leaking information
302 * about whether the assignment was made or not.
303 * dest and src must be arrays of limbs of size n.
304 * assign must be 0 or 1.
305 */
mpi_safe_cond_assign(size_t n,mbedtls_mpi_uint * dest,const mbedtls_mpi_uint * src,unsigned char assign)306 static void mpi_safe_cond_assign( size_t n,
307 mbedtls_mpi_uint *dest,
308 const mbedtls_mpi_uint *src,
309 unsigned char assign )
310 {
311 size_t i;
312
313 /* MSVC has a warning about unary minus on unsigned integer types,
314 * but this is well-defined and precisely what we want to do here. */
315 #if defined(_MSC_VER)
316 #pragma warning( push )
317 #pragma warning( disable : 4146 )
318 #endif
319
320 /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */
321 const mbedtls_mpi_uint mask = -assign;
322
323 #if defined(_MSC_VER)
324 #pragma warning( pop )
325 #endif
326
327 for( i = 0; i < n; i++ )
328 dest[i] = ( src[i] & mask ) | ( dest[i] & ~mask );
329 }
330
331 /*
332 * Conditionally assign X = Y, without leaking information
333 * about whether the assignment was made or not.
334 * (Leaking information about the respective sizes of X and Y is ok however.)
335 */
mbedtls_mpi_safe_cond_assign(mbedtls_mpi * X,const mbedtls_mpi * Y,unsigned char assign)336 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
337 {
338 int ret = 0;
339 size_t i;
340 mbedtls_mpi_uint limb_mask;
341 MPI_VALIDATE_RET( X != NULL );
342 MPI_VALIDATE_RET( Y != NULL );
343
344 /* MSVC has a warning about unary minus on unsigned integer types,
345 * but this is well-defined and precisely what we want to do here. */
346 #if defined(_MSC_VER)
347 #pragma warning( push )
348 #pragma warning( disable : 4146 )
349 #endif
350
351 /* make sure assign is 0 or 1 in a time-constant manner */
352 assign = (assign | (unsigned char)-assign) >> (sizeof( assign ) * 8 - 1);
353 /* all-bits 1 if assign is 1, all-bits 0 if assign is 0 */
354 limb_mask = -assign;
355
356 #if defined(_MSC_VER)
357 #pragma warning( pop )
358 #endif
359
360 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
361
362 X->s = mpi_safe_cond_select_sign( X->s, Y->s, assign );
363
364 mpi_safe_cond_assign( Y->n, X->p, Y->p, assign );
365
366 for( i = Y->n; i < X->n; i++ )
367 X->p[i] &= ~limb_mask;
368
369 cleanup:
370 return( ret );
371 }
372
373 /*
374 * Conditionally swap X and Y, without leaking information
375 * about whether the swap was made or not.
376 * Here it is not ok to simply swap the pointers, which whould lead to
377 * different memory access patterns when X and Y are used afterwards.
378 */
mbedtls_mpi_safe_cond_swap(mbedtls_mpi * X,mbedtls_mpi * Y,unsigned char swap)379 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
380 {
381 int ret, s;
382 size_t i;
383 mbedtls_mpi_uint limb_mask;
384 mbedtls_mpi_uint tmp;
385 MPI_VALIDATE_RET( X != NULL );
386 MPI_VALIDATE_RET( Y != NULL );
387
388 if( X == Y )
389 return( 0 );
390
391 /* MSVC has a warning about unary minus on unsigned integer types,
392 * but this is well-defined and precisely what we want to do here. */
393 #if defined(_MSC_VER)
394 #pragma warning( push )
395 #pragma warning( disable : 4146 )
396 #endif
397
398 /* make sure swap is 0 or 1 in a time-constant manner */
399 swap = (swap | (unsigned char)-swap) >> (sizeof( swap ) * 8 - 1);
400 /* all-bits 1 if swap is 1, all-bits 0 if swap is 0 */
401 limb_mask = -swap;
402
403 #if defined(_MSC_VER)
404 #pragma warning( pop )
405 #endif
406
407 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
408 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
409
410 s = X->s;
411 X->s = mpi_safe_cond_select_sign( X->s, Y->s, swap );
412 Y->s = mpi_safe_cond_select_sign( Y->s, s, swap );
413
414
415 for( i = 0; i < X->n; i++ )
416 {
417 tmp = X->p[i];
418 X->p[i] = ( X->p[i] & ~limb_mask ) | ( Y->p[i] & limb_mask );
419 Y->p[i] = ( Y->p[i] & ~limb_mask ) | ( tmp & limb_mask );
420 }
421
422 cleanup:
423 return( ret );
424 }
425
426 /*
427 * Set value from integer
428 */
mbedtls_mpi_lset(mbedtls_mpi * X,mbedtls_mpi_sint z)429 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
430 {
431 int ret;
432 MPI_VALIDATE_RET( X != NULL );
433
434 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
435 memset( X->p, 0, X->n * ciL );
436
437 X->p[0] = ( z < 0 ) ? -z : z;
438 X->s = ( z < 0 ) ? -1 : 1;
439
440 cleanup:
441
442 return( ret );
443 }
444
445 /*
446 * Get a specific bit
447 */
mbedtls_mpi_get_bit(const mbedtls_mpi * X,size_t pos)448 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
449 {
450 MPI_VALIDATE_RET( X != NULL );
451
452 if( X->n * biL <= pos )
453 return( 0 );
454
455 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
456 }
457
458 /* Get a specific byte, without range checks. */
459 #define GET_BYTE( X, i ) \
460 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
461
462 /*
463 * Set a bit to a specific value of 0 or 1
464 */
mbedtls_mpi_set_bit(mbedtls_mpi * X,size_t pos,unsigned char val)465 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
466 {
467 int ret = 0;
468 size_t off = pos / biL;
469 size_t idx = pos % biL;
470 MPI_VALIDATE_RET( X != NULL );
471
472 if( val != 0 && val != 1 )
473 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
474
475 if( X->n * biL <= pos )
476 {
477 if( val == 0 )
478 return( 0 );
479
480 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
481 }
482
483 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
484 X->p[off] |= (mbedtls_mpi_uint) val << idx;
485
486 cleanup:
487
488 return( ret );
489 }
490
491 /*
492 * Return the number of less significant zero-bits
493 */
mbedtls_mpi_lsb(const mbedtls_mpi * X)494 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
495 {
496 size_t i, j, count = 0;
497 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
498
499 for( i = 0; i < X->n; i++ )
500 for( j = 0; j < biL; j++, count++ )
501 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
502 return( count );
503
504 return( 0 );
505 }
506
507 /*
508 * Count leading zero bits in a given integer
509 */
mbedtls_clz(const mbedtls_mpi_uint x)510 static size_t mbedtls_clz( const mbedtls_mpi_uint x )
511 {
512 size_t j;
513 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
514
515 for( j = 0; j < biL; j++ )
516 {
517 if( x & mask ) break;
518
519 mask >>= 1;
520 }
521
522 return j;
523 }
524
525 /*
526 * Return the number of bits
527 */
mbedtls_mpi_bitlen(const mbedtls_mpi * X)528 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
529 {
530 size_t i, j;
531
532 if( X->n == 0 )
533 return( 0 );
534
535 for( i = X->n - 1; i > 0; i-- )
536 if( X->p[i] != 0 )
537 break;
538
539 j = biL - mbedtls_clz( X->p[i] );
540
541 return( ( i * biL ) + j );
542 }
543
544 /*
545 * Return the total size in bytes
546 */
mbedtls_mpi_size(const mbedtls_mpi * X)547 size_t mbedtls_mpi_size( const mbedtls_mpi *X )
548 {
549 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
550 }
551
552 /*
553 * Convert an ASCII character to digit value
554 */
mpi_get_digit(mbedtls_mpi_uint * d,int radix,char c)555 static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
556 {
557 *d = 255;
558
559 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
560 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
561 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
562
563 if( *d >= (mbedtls_mpi_uint) radix )
564 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
565
566 return( 0 );
567 }
568
569 /*
570 * Import from an ASCII string
571 */
mbedtls_mpi_read_string(mbedtls_mpi * X,int radix,const char * s)572 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
573 {
574 int ret;
575 size_t i, j, slen, n;
576 int sign = 1;
577 mbedtls_mpi_uint d;
578 mbedtls_mpi T;
579 MPI_VALIDATE_RET( X != NULL );
580 MPI_VALIDATE_RET( s != NULL );
581
582 if( radix < 2 || radix > 16 )
583 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
584
585 mbedtls_mpi_init( &T );
586
587 if( s[0] == '-' )
588 {
589 ++s;
590 sign = -1;
591 }
592
593 slen = strlen( s );
594
595 if( radix == 16 )
596 {
597 if( slen > MPI_SIZE_T_MAX >> 2 )
598 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
599
600 n = BITS_TO_LIMBS( slen << 2 );
601
602 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
603 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
604
605 for( i = slen, j = 0; i > 0; i--, j++ )
606 {
607 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
608 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
609 }
610 }
611 else
612 {
613 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
614
615 for( i = 0; i < slen; i++ )
616 {
617 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
618 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
619 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
620 }
621 }
622
623 if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 )
624 X->s = -1;
625
626 cleanup:
627
628 mbedtls_mpi_free( &T );
629
630 return( ret );
631 }
632
633 /*
634 * Helper to write the digits high-order first.
635 */
mpi_write_hlp(mbedtls_mpi * X,int radix,char ** p,const size_t buflen)636 static int mpi_write_hlp( mbedtls_mpi *X, int radix,
637 char **p, const size_t buflen )
638 {
639 int ret;
640 mbedtls_mpi_uint r;
641 size_t length = 0;
642 char *p_end = *p + buflen;
643
644 do
645 {
646 if( length >= buflen )
647 {
648 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
649 }
650
651 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
652 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
653 /*
654 * Write the residue in the current position, as an ASCII character.
655 */
656 if( r < 0xA )
657 *(--p_end) = (char)( '0' + r );
658 else
659 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
660
661 length++;
662 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
663
664 memmove( *p, p_end, length );
665 *p += length;
666
667 cleanup:
668
669 return( ret );
670 }
671
672 /*
673 * Export into an ASCII string
674 */
mbedtls_mpi_write_string(const mbedtls_mpi * X,int radix,char * buf,size_t buflen,size_t * olen)675 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
676 char *buf, size_t buflen, size_t *olen )
677 {
678 int ret = 0;
679 size_t n;
680 char *p;
681 mbedtls_mpi T;
682 MPI_VALIDATE_RET( X != NULL );
683 MPI_VALIDATE_RET( olen != NULL );
684 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
685
686 if( radix < 2 || radix > 16 )
687 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
688
689 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
690 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
691 * `n`. If radix > 4, this might be a strict
692 * overapproximation of the number of
693 * radix-adic digits needed to present `n`. */
694 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
695 * present `n`. */
696
697 n += 1; /* Terminating null byte */
698 n += 1; /* Compensate for the divisions above, which round down `n`
699 * in case it's not even. */
700 n += 1; /* Potential '-'-sign. */
701 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
702 * which always uses an even number of hex-digits. */
703
704 if( buflen < n )
705 {
706 *olen = n;
707 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
708 }
709
710 p = buf;
711 mbedtls_mpi_init( &T );
712
713 if( X->s == -1 )
714 {
715 *p++ = '-';
716 buflen--;
717 }
718
719 if( radix == 16 )
720 {
721 int c;
722 size_t i, j, k;
723
724 for( i = X->n, k = 0; i > 0; i-- )
725 {
726 for( j = ciL; j > 0; j-- )
727 {
728 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
729
730 if( c == 0 && k == 0 && ( i + j ) != 2 )
731 continue;
732
733 *(p++) = "0123456789ABCDEF" [c / 16];
734 *(p++) = "0123456789ABCDEF" [c % 16];
735 k = 1;
736 }
737 }
738 }
739 else
740 {
741 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
742
743 if( T.s == -1 )
744 T.s = 1;
745
746 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
747 }
748
749 *p++ = '\0';
750 *olen = p - buf;
751
752 cleanup:
753
754 mbedtls_mpi_free( &T );
755
756 return( ret );
757 }
758
759 #if defined(MBEDTLS_FS_IO)
760 /*
761 * Read X from an opened file
762 */
mbedtls_mpi_read_file(mbedtls_mpi * X,int radix,FILE * fin)763 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
764 {
765 mbedtls_mpi_uint d;
766 size_t slen;
767 char *p;
768 /*
769 * Buffer should have space for (short) label and decimal formatted MPI,
770 * newline characters and '\0'
771 */
772 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
773
774 MPI_VALIDATE_RET( X != NULL );
775 MPI_VALIDATE_RET( fin != NULL );
776
777 if( radix < 2 || radix > 16 )
778 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
779
780 memset( s, 0, sizeof( s ) );
781 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
782 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
783
784 slen = strlen( s );
785 if( slen == sizeof( s ) - 2 )
786 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
787
788 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
789 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
790
791 p = s + slen;
792 while( p-- > s )
793 if( mpi_get_digit( &d, radix, *p ) != 0 )
794 break;
795
796 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
797 }
798
799 /*
800 * Write X into an opened file (or stdout if fout == NULL)
801 */
mbedtls_mpi_write_file(const char * p,const mbedtls_mpi * X,int radix,FILE * fout)802 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
803 {
804 int ret;
805 size_t n, slen, plen;
806 /*
807 * Buffer should have space for (short) label and decimal formatted MPI,
808 * newline characters and '\0'
809 */
810 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
811 MPI_VALIDATE_RET( X != NULL );
812
813 if( radix < 2 || radix > 16 )
814 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
815
816 memset( s, 0, sizeof( s ) );
817
818 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
819
820 if( p == NULL ) p = "";
821
822 plen = strlen( p );
823 slen = strlen( s );
824 s[slen++] = '\r';
825 s[slen++] = '\n';
826
827 if( fout != NULL )
828 {
829 if( fwrite( p, 1, plen, fout ) != plen ||
830 fwrite( s, 1, slen, fout ) != slen )
831 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
832 }
833 else
834 mbedtls_printf( "%s%s", p, s );
835
836 cleanup:
837
838 return( ret );
839 }
840 #endif /* MBEDTLS_FS_IO */
841
842
843 /* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
844 * into the storage form used by mbedtls_mpi. */
845
mpi_uint_bigendian_to_host_c(mbedtls_mpi_uint x)846 static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x )
847 {
848 uint8_t i;
849 unsigned char *x_ptr;
850 mbedtls_mpi_uint tmp = 0;
851
852 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ )
853 {
854 tmp <<= CHAR_BIT;
855 tmp |= (mbedtls_mpi_uint) *x_ptr;
856 }
857
858 return( tmp );
859 }
860
mpi_uint_bigendian_to_host(mbedtls_mpi_uint x)861 static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x )
862 {
863 #if defined(__BYTE_ORDER__)
864
865 /* Nothing to do on bigendian systems. */
866 #if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ )
867 return( x );
868 #endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
869
870 #if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ )
871
872 /* For GCC and Clang, have builtins for byte swapping. */
873 #if defined(__GNUC__) && defined(__GNUC_PREREQ)
874 #if __GNUC_PREREQ(4,3)
875 #define have_bswap
876 #endif
877 #endif
878
879 #if defined(__clang__) && defined(__has_builtin)
880 #if __has_builtin(__builtin_bswap32) && \
881 __has_builtin(__builtin_bswap64)
882 #define have_bswap
883 #endif
884 #endif
885
886 #if defined(have_bswap)
887 /* The compiler is hopefully able to statically evaluate this! */
888 switch( sizeof(mbedtls_mpi_uint) )
889 {
890 case 4:
891 return( __builtin_bswap32(x) );
892 case 8:
893 return( __builtin_bswap64(x) );
894 }
895 #endif
896 #endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
897 #endif /* __BYTE_ORDER__ */
898
899 /* Fall back to C-based reordering if we don't know the byte order
900 * or we couldn't use a compiler-specific builtin. */
901 return( mpi_uint_bigendian_to_host_c( x ) );
902 }
903
mpi_bigendian_to_host(mbedtls_mpi_uint * const p,size_t limbs)904 static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs )
905 {
906 mbedtls_mpi_uint *cur_limb_left;
907 mbedtls_mpi_uint *cur_limb_right;
908 if( limbs == 0 )
909 return;
910
911 /*
912 * Traverse limbs and
913 * - adapt byte-order in each limb
914 * - swap the limbs themselves.
915 * For that, simultaneously traverse the limbs from left to right
916 * and from right to left, as long as the left index is not bigger
917 * than the right index (it's not a problem if limbs is odd and the
918 * indices coincide in the last iteration).
919 */
920 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
921 cur_limb_left <= cur_limb_right;
922 cur_limb_left++, cur_limb_right-- )
923 {
924 mbedtls_mpi_uint tmp;
925 /* Note that if cur_limb_left == cur_limb_right,
926 * this code effectively swaps the bytes only once. */
927 tmp = mpi_uint_bigendian_to_host( *cur_limb_left );
928 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right );
929 *cur_limb_right = tmp;
930 }
931 }
932
933 /*
934 * Import X from unsigned binary data, big endian
935 */
mbedtls_mpi_read_binary(mbedtls_mpi * X,const unsigned char * buf,size_t buflen)936 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
937 {
938 int ret;
939 size_t const limbs = CHARS_TO_LIMBS( buflen );
940 size_t const overhead = ( limbs * ciL ) - buflen;
941 unsigned char *Xp;
942
943 MPI_VALIDATE_RET( X != NULL );
944 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
945
946 /* Ensure that target MPI has exactly the necessary number of limbs */
947 if( X->n != limbs )
948 {
949 mbedtls_mpi_free( X );
950 mbedtls_mpi_init( X );
951 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
952 }
953 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
954
955 /* Avoid calling `memcpy` with NULL source argument,
956 * even if buflen is 0. */
957 if( buf != NULL )
958 {
959 Xp = (unsigned char*) X->p;
960 memcpy( Xp + overhead, buf, buflen );
961
962 mpi_bigendian_to_host( X->p, limbs );
963 }
964
965 cleanup:
966
967 return( ret );
968 }
969
970 /*
971 * Export X into unsigned binary data, big endian
972 */
mbedtls_mpi_write_binary(const mbedtls_mpi * X,unsigned char * buf,size_t buflen)973 int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
974 unsigned char *buf, size_t buflen )
975 {
976 size_t stored_bytes;
977 size_t bytes_to_copy;
978 unsigned char *p;
979 size_t i;
980
981 MPI_VALIDATE_RET( X != NULL );
982 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
983
984 stored_bytes = X->n * ciL;
985
986 if( stored_bytes < buflen )
987 {
988 /* There is enough space in the output buffer. Write initial
989 * null bytes and record the position at which to start
990 * writing the significant bytes. In this case, the execution
991 * trace of this function does not depend on the value of the
992 * number. */
993 bytes_to_copy = stored_bytes;
994 p = buf + buflen - stored_bytes;
995 memset( buf, 0, buflen - stored_bytes );
996 }
997 else
998 {
999 /* The output buffer is smaller than the allocated size of X.
1000 * However X may fit if its leading bytes are zero. */
1001 bytes_to_copy = buflen;
1002 p = buf;
1003 for( i = bytes_to_copy; i < stored_bytes; i++ )
1004 {
1005 if( GET_BYTE( X, i ) != 0 )
1006 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
1007 }
1008 }
1009
1010 for( i = 0; i < bytes_to_copy; i++ )
1011 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
1012
1013 return( 0 );
1014 }
1015
1016 /*
1017 * Left-shift: X <<= count
1018 */
mbedtls_mpi_shift_l(mbedtls_mpi * X,size_t count)1019 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
1020 {
1021 int ret;
1022 size_t i, v0, t1;
1023 mbedtls_mpi_uint r0 = 0, r1;
1024 MPI_VALIDATE_RET( X != NULL );
1025
1026 v0 = count / (biL );
1027 t1 = count & (biL - 1);
1028
1029 i = mbedtls_mpi_bitlen( X ) + count;
1030
1031 if( X->n * biL < i )
1032 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
1033
1034 ret = 0;
1035
1036 /*
1037 * shift by count / limb_size
1038 */
1039 if( v0 > 0 )
1040 {
1041 for( i = X->n; i > v0; i-- )
1042 X->p[i - 1] = X->p[i - v0 - 1];
1043
1044 for( ; i > 0; i-- )
1045 X->p[i - 1] = 0;
1046 }
1047
1048 /*
1049 * shift by count % limb_size
1050 */
1051 if( t1 > 0 )
1052 {
1053 for( i = v0; i < X->n; i++ )
1054 {
1055 r1 = X->p[i] >> (biL - t1);
1056 X->p[i] <<= t1;
1057 X->p[i] |= r0;
1058 r0 = r1;
1059 }
1060 }
1061
1062 cleanup:
1063
1064 return( ret );
1065 }
1066
1067 /*
1068 * Right-shift: X >>= count
1069 */
mbedtls_mpi_shift_r(mbedtls_mpi * X,size_t count)1070 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
1071 {
1072 size_t i, v0, v1;
1073 mbedtls_mpi_uint r0 = 0, r1;
1074 MPI_VALIDATE_RET( X != NULL );
1075
1076 v0 = count / biL;
1077 v1 = count & (biL - 1);
1078
1079 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
1080 return mbedtls_mpi_lset( X, 0 );
1081
1082 /*
1083 * shift by count / limb_size
1084 */
1085 if( v0 > 0 )
1086 {
1087 for( i = 0; i < X->n - v0; i++ )
1088 X->p[i] = X->p[i + v0];
1089
1090 for( ; i < X->n; i++ )
1091 X->p[i] = 0;
1092 }
1093
1094 /*
1095 * shift by count % limb_size
1096 */
1097 if( v1 > 0 )
1098 {
1099 for( i = X->n; i > 0; i-- )
1100 {
1101 r1 = X->p[i - 1] << (biL - v1);
1102 X->p[i - 1] >>= v1;
1103 X->p[i - 1] |= r0;
1104 r0 = r1;
1105 }
1106 }
1107
1108 return( 0 );
1109 }
1110
1111 /*
1112 * Compare unsigned values
1113 */
mbedtls_mpi_cmp_abs(const mbedtls_mpi * X,const mbedtls_mpi * Y)1114 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
1115 {
1116 size_t i, j;
1117 MPI_VALIDATE_RET( X != NULL );
1118 MPI_VALIDATE_RET( Y != NULL );
1119
1120 for( i = X->n; i > 0; i-- )
1121 if( X->p[i - 1] != 0 )
1122 break;
1123
1124 for( j = Y->n; j > 0; j-- )
1125 if( Y->p[j - 1] != 0 )
1126 break;
1127
1128 if( i == 0 && j == 0 )
1129 return( 0 );
1130
1131 if( i > j ) return( 1 );
1132 if( j > i ) return( -1 );
1133
1134 for( ; i > 0; i-- )
1135 {
1136 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
1137 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
1138 }
1139
1140 return( 0 );
1141 }
1142
1143 /*
1144 * Compare signed values
1145 */
mbedtls_mpi_cmp_mpi(const mbedtls_mpi * X,const mbedtls_mpi * Y)1146 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
1147 {
1148 size_t i, j;
1149 MPI_VALIDATE_RET( X != NULL );
1150 MPI_VALIDATE_RET( Y != NULL );
1151
1152 for( i = X->n; i > 0; i-- )
1153 if( X->p[i - 1] != 0 )
1154 break;
1155
1156 for( j = Y->n; j > 0; j-- )
1157 if( Y->p[j - 1] != 0 )
1158 break;
1159
1160 if( i == 0 && j == 0 )
1161 return( 0 );
1162
1163 if( i > j ) return( X->s );
1164 if( j > i ) return( -Y->s );
1165
1166 if( X->s > 0 && Y->s < 0 ) return( 1 );
1167 if( Y->s > 0 && X->s < 0 ) return( -1 );
1168
1169 for( ; i > 0; i-- )
1170 {
1171 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
1172 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
1173 }
1174
1175 return( 0 );
1176 }
1177
1178 /** Decide if an integer is less than the other, without branches.
1179 *
1180 * \param x First integer.
1181 * \param y Second integer.
1182 *
1183 * \return 1 if \p x is less than \p y, 0 otherwise
1184 */
ct_lt_mpi_uint(const mbedtls_mpi_uint x,const mbedtls_mpi_uint y)1185 static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x,
1186 const mbedtls_mpi_uint y )
1187 {
1188 mbedtls_mpi_uint ret;
1189 mbedtls_mpi_uint cond;
1190
1191 /*
1192 * Check if the most significant bits (MSB) of the operands are different.
1193 */
1194 cond = ( x ^ y );
1195 /*
1196 * If the MSB are the same then the difference x-y will be negative (and
1197 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
1198 */
1199 ret = ( x - y ) & ~cond;
1200 /*
1201 * If the MSB are different, then the operand with the MSB of 1 is the
1202 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
1203 * the MSB of y is 0.)
1204 */
1205 ret |= y & cond;
1206
1207
1208 ret = ret >> ( biL - 1 );
1209
1210 return (unsigned) ret;
1211 }
1212
1213 /*
1214 * Compare signed values in constant time
1215 */
mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi * X,const mbedtls_mpi * Y,unsigned * ret)1216 int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
1217 unsigned *ret )
1218 {
1219 size_t i;
1220 /* The value of any of these variables is either 0 or 1 at all times. */
1221 unsigned cond, done, X_is_negative, Y_is_negative;
1222
1223 MPI_VALIDATE_RET( X != NULL );
1224 MPI_VALIDATE_RET( Y != NULL );
1225 MPI_VALIDATE_RET( ret != NULL );
1226
1227 if( X->n != Y->n )
1228 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1229
1230 /*
1231 * Set sign_N to 1 if N >= 0, 0 if N < 0.
1232 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
1233 */
1234 X_is_negative = ( X->s & 2 ) >> 1;
1235 Y_is_negative = ( Y->s & 2 ) >> 1;
1236
1237 /*
1238 * If the signs are different, then the positive operand is the bigger.
1239 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
1240 * is false if X is positive (X_is_negative == 0).
1241 */
1242 cond = ( X_is_negative ^ Y_is_negative );
1243 *ret = cond & X_is_negative;
1244
1245 /*
1246 * This is a constant-time function. We might have the result, but we still
1247 * need to go through the loop. Record if we have the result already.
1248 */
1249 done = cond;
1250
1251 for( i = X->n; i > 0; i-- )
1252 {
1253 /*
1254 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
1255 * X and Y are negative.
1256 *
1257 * Again even if we can make a decision, we just mark the result and
1258 * the fact that we are done and continue looping.
1259 */
1260 cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
1261 *ret |= cond & ( 1 - done ) & X_is_negative;
1262 done |= cond;
1263
1264 /*
1265 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
1266 * X and Y are positive.
1267 *
1268 * Again even if we can make a decision, we just mark the result and
1269 * the fact that we are done and continue looping.
1270 */
1271 cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
1272 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
1273 done |= cond;
1274 }
1275
1276 return( 0 );
1277 }
1278
1279 /*
1280 * Compare signed values
1281 */
mbedtls_mpi_cmp_int(const mbedtls_mpi * X,mbedtls_mpi_sint z)1282 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
1283 {
1284 mbedtls_mpi Y;
1285 mbedtls_mpi_uint p[1];
1286 MPI_VALIDATE_RET( X != NULL );
1287
1288 *p = ( z < 0 ) ? -z : z;
1289 Y.s = ( z < 0 ) ? -1 : 1;
1290 Y.n = 1;
1291 Y.p = p;
1292
1293 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
1294 }
1295
1296 /*
1297 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1298 */
mbedtls_mpi_add_abs(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1299 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1300 {
1301 int ret;
1302 size_t i, j;
1303 mbedtls_mpi_uint *o, *p, c, tmp;
1304 MPI_VALIDATE_RET( X != NULL );
1305 MPI_VALIDATE_RET( A != NULL );
1306 MPI_VALIDATE_RET( B != NULL );
1307
1308 if( X == B )
1309 {
1310 const mbedtls_mpi *T = A; A = X; B = T;
1311 }
1312
1313 if( X != A )
1314 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1315
1316 /*
1317 * X should always be positive as a result of unsigned additions.
1318 */
1319 X->s = 1;
1320
1321 for( j = B->n; j > 0; j-- )
1322 if( B->p[j - 1] != 0 )
1323 break;
1324
1325 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1326
1327 o = B->p; p = X->p; c = 0;
1328
1329 /*
1330 * tmp is used because it might happen that p == o
1331 */
1332 for( i = 0; i < j; i++, o++, p++ )
1333 {
1334 tmp= *o;
1335 *p += c; c = ( *p < c );
1336 *p += tmp; c += ( *p < tmp );
1337 }
1338
1339 while( c != 0 )
1340 {
1341 if( i >= X->n )
1342 {
1343 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
1344 p = X->p + i;
1345 }
1346
1347 *p += c; c = ( *p < c ); i++; p++;
1348 }
1349
1350 cleanup:
1351
1352 return( ret );
1353 }
1354
1355 /**
1356 * Helper for mbedtls_mpi subtraction.
1357 *
1358 * Calculate d - s where d and s have the same size.
1359 * This function operates modulo (2^ciL)^n and returns the carry
1360 * (1 if there was a wraparound, i.e. if `d < s`, and 0 otherwise).
1361 *
1362 * \param n Number of limbs of \p d and \p s.
1363 * \param[in,out] d On input, the left operand.
1364 * On output, the result of the subtraction:
1365 * \param[in] s The right operand.
1366 *
1367 * \return 1 if `d < s`.
1368 * 0 if `d >= s`.
1369 */
mpi_sub_hlp(size_t n,mbedtls_mpi_uint * d,const mbedtls_mpi_uint * s)1370 static mbedtls_mpi_uint mpi_sub_hlp( size_t n,
1371 mbedtls_mpi_uint *d,
1372 const mbedtls_mpi_uint *s )
1373 {
1374 size_t i;
1375 mbedtls_mpi_uint c, z;
1376
1377 for( i = c = 0; i < n; i++, s++, d++ )
1378 {
1379 z = ( *d < c ); *d -= c;
1380 c = ( *d < *s ) + z; *d -= *s;
1381 }
1382
1383 return( c );
1384 }
1385
1386 /*
1387 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1388 */
mbedtls_mpi_sub_abs(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1389 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1390 {
1391 mbedtls_mpi TB;
1392 int ret;
1393 size_t n;
1394 mbedtls_mpi_uint carry;
1395 MPI_VALIDATE_RET( X != NULL );
1396 MPI_VALIDATE_RET( A != NULL );
1397 MPI_VALIDATE_RET( B != NULL );
1398
1399 mbedtls_mpi_init( &TB );
1400
1401 if( X == B )
1402 {
1403 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
1404 B = &TB;
1405 }
1406
1407 if( X != A )
1408 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1409
1410 /*
1411 * X should always be positive as a result of unsigned subtractions.
1412 */
1413 X->s = 1;
1414
1415 ret = 0;
1416
1417 for( n = B->n; n > 0; n-- )
1418 if( B->p[n - 1] != 0 )
1419 break;
1420 if( n > A->n )
1421 {
1422 /* B >= (2^ciL)^n > A */
1423 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1424 goto cleanup;
1425 }
1426
1427 carry = mpi_sub_hlp( n, X->p, B->p );
1428 if( carry != 0 )
1429 {
1430 /* Propagate the carry to the first nonzero limb of X. */
1431 for( ; n < X->n && X->p[n] == 0; n++ )
1432 --X->p[n];
1433 /* If we ran out of space for the carry, it means that the result
1434 * is negative. */
1435 if( n == X->n )
1436 {
1437 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1438 goto cleanup;
1439 }
1440 --X->p[n];
1441 }
1442
1443 cleanup:
1444
1445 mbedtls_mpi_free( &TB );
1446
1447 return( ret );
1448 }
1449
1450 /*
1451 * Signed addition: X = A + B
1452 */
mbedtls_mpi_add_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1453 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1454 {
1455 int ret, s;
1456 MPI_VALIDATE_RET( X != NULL );
1457 MPI_VALIDATE_RET( A != NULL );
1458 MPI_VALIDATE_RET( B != NULL );
1459
1460 s = A->s;
1461 if( A->s * B->s < 0 )
1462 {
1463 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1464 {
1465 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1466 X->s = s;
1467 }
1468 else
1469 {
1470 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1471 X->s = -s;
1472 }
1473 }
1474 else
1475 {
1476 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1477 X->s = s;
1478 }
1479
1480 cleanup:
1481
1482 return( ret );
1483 }
1484
1485 /*
1486 * Signed subtraction: X = A - B
1487 */
mbedtls_mpi_sub_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1488 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1489 {
1490 int ret, s;
1491 MPI_VALIDATE_RET( X != NULL );
1492 MPI_VALIDATE_RET( A != NULL );
1493 MPI_VALIDATE_RET( B != NULL );
1494
1495 s = A->s;
1496 if( A->s * B->s > 0 )
1497 {
1498 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1499 {
1500 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1501 X->s = s;
1502 }
1503 else
1504 {
1505 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1506 X->s = -s;
1507 }
1508 }
1509 else
1510 {
1511 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1512 X->s = s;
1513 }
1514
1515 cleanup:
1516
1517 return( ret );
1518 }
1519
1520 /*
1521 * Signed addition: X = A + b
1522 */
mbedtls_mpi_add_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_sint b)1523 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1524 {
1525 mbedtls_mpi _B;
1526 mbedtls_mpi_uint p[1];
1527 MPI_VALIDATE_RET( X != NULL );
1528 MPI_VALIDATE_RET( A != NULL );
1529
1530 p[0] = ( b < 0 ) ? -b : b;
1531 _B.s = ( b < 0 ) ? -1 : 1;
1532 _B.n = 1;
1533 _B.p = p;
1534
1535 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
1536 }
1537
1538 /*
1539 * Signed subtraction: X = A - b
1540 */
mbedtls_mpi_sub_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_sint b)1541 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1542 {
1543 mbedtls_mpi _B;
1544 mbedtls_mpi_uint p[1];
1545 MPI_VALIDATE_RET( X != NULL );
1546 MPI_VALIDATE_RET( A != NULL );
1547
1548 p[0] = ( b < 0 ) ? -b : b;
1549 _B.s = ( b < 0 ) ? -1 : 1;
1550 _B.n = 1;
1551 _B.p = p;
1552
1553 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
1554 }
1555
1556 /*
1557 * Helper for mbedtls_mpi multiplication
1558 */
1559 static
1560 #if defined(__APPLE__) && defined(__arm__)
1561 /*
1562 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1563 * appears to need this to prevent bad ARM code generation at -O3.
1564 */
1565 __attribute__ ((noinline))
1566 #endif
mpi_mul_hlp(size_t i,mbedtls_mpi_uint * s,mbedtls_mpi_uint * d,mbedtls_mpi_uint b)1567 void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
1568 {
1569 mbedtls_mpi_uint c = 0, t = 0;
1570
1571 #if defined(MULADDC_HUIT)
1572 for( ; i >= 8; i -= 8 )
1573 {
1574 MULADDC_INIT
1575 MULADDC_HUIT
1576 MULADDC_STOP
1577 }
1578
1579 for( ; i > 0; i-- )
1580 {
1581 MULADDC_INIT
1582 MULADDC_CORE
1583 MULADDC_STOP
1584 }
1585 #else /* MULADDC_HUIT */
1586 for( ; i >= 16; i -= 16 )
1587 {
1588 MULADDC_INIT
1589 MULADDC_CORE MULADDC_CORE
1590 MULADDC_CORE MULADDC_CORE
1591 MULADDC_CORE MULADDC_CORE
1592 MULADDC_CORE MULADDC_CORE
1593
1594 MULADDC_CORE MULADDC_CORE
1595 MULADDC_CORE MULADDC_CORE
1596 MULADDC_CORE MULADDC_CORE
1597 MULADDC_CORE MULADDC_CORE
1598 MULADDC_STOP
1599 }
1600
1601 for( ; i >= 8; i -= 8 )
1602 {
1603 MULADDC_INIT
1604 MULADDC_CORE MULADDC_CORE
1605 MULADDC_CORE MULADDC_CORE
1606
1607 MULADDC_CORE MULADDC_CORE
1608 MULADDC_CORE MULADDC_CORE
1609 MULADDC_STOP
1610 }
1611
1612 for( ; i > 0; i-- )
1613 {
1614 MULADDC_INIT
1615 MULADDC_CORE
1616 MULADDC_STOP
1617 }
1618 #endif /* MULADDC_HUIT */
1619
1620 t++;
1621
1622 do {
1623 *d += c; c = ( *d < c ); d++;
1624 }
1625 while( c != 0 );
1626 }
1627
1628 /*
1629 * Baseline multiplication: X = A * B (HAC 14.12)
1630 */
mbedtls_mpi_mul_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1631 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1632 {
1633 int ret;
1634 size_t i, j;
1635 mbedtls_mpi TA, TB;
1636 int result_is_zero = 0;
1637 MPI_VALIDATE_RET( X != NULL );
1638 MPI_VALIDATE_RET( A != NULL );
1639 MPI_VALIDATE_RET( B != NULL );
1640
1641 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
1642
1643 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1644 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1645
1646 for( i = A->n; i > 0; i-- )
1647 if( A->p[i - 1] != 0 )
1648 break;
1649 if( i == 0 )
1650 result_is_zero = 1;
1651
1652 for( j = B->n; j > 0; j-- )
1653 if( B->p[j - 1] != 0 )
1654 break;
1655 if( j == 0 )
1656 result_is_zero = 1;
1657
1658 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1659 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1660
1661 for( ; j > 0; j-- )
1662 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
1663
1664 /* If the result is 0, we don't shortcut the operation, which reduces
1665 * but does not eliminate side channels leaking the zero-ness. We do
1666 * need to take care to set the sign bit properly since the library does
1667 * not fully support an MPI object with a value of 0 and s == -1. */
1668 if( result_is_zero )
1669 X->s = 1;
1670 else
1671 X->s = A->s * B->s;
1672
1673 cleanup:
1674
1675 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
1676
1677 return( ret );
1678 }
1679
1680 /*
1681 * Baseline multiplication: X = A * b
1682 */
mbedtls_mpi_mul_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_uint b)1683 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1684 {
1685 mbedtls_mpi _B;
1686 mbedtls_mpi_uint p[1];
1687 MPI_VALIDATE_RET( X != NULL );
1688 MPI_VALIDATE_RET( A != NULL );
1689
1690 _B.s = 1;
1691 _B.n = 1;
1692 _B.p = p;
1693 p[0] = b;
1694
1695 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
1696 }
1697
1698 /*
1699 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1700 * mbedtls_mpi_uint divisor, d
1701 */
mbedtls_int_div_int(mbedtls_mpi_uint u1,mbedtls_mpi_uint u0,mbedtls_mpi_uint d,mbedtls_mpi_uint * r)1702 static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1703 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
1704 {
1705 #if defined(MBEDTLS_HAVE_UDBL)
1706 mbedtls_t_udbl dividend, quotient;
1707 #else
1708 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1709 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
1710 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1711 mbedtls_mpi_uint u0_msw, u0_lsw;
1712 size_t s;
1713 #endif
1714
1715 /*
1716 * Check for overflow
1717 */
1718 if( 0 == d || u1 >= d )
1719 {
1720 if (r != NULL) *r = ~0;
1721
1722 return ( ~0 );
1723 }
1724
1725 #if defined(MBEDTLS_HAVE_UDBL)
1726 dividend = (mbedtls_t_udbl) u1 << biL;
1727 dividend |= (mbedtls_t_udbl) u0;
1728 quotient = dividend / d;
1729 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1730 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1731
1732 if( r != NULL )
1733 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
1734
1735 return (mbedtls_mpi_uint) quotient;
1736 #else
1737
1738 /*
1739 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1740 * Vol. 2 - Seminumerical Algorithms, Knuth
1741 */
1742
1743 /*
1744 * Normalize the divisor, d, and dividend, u0, u1
1745 */
1746 s = mbedtls_clz( d );
1747 d = d << s;
1748
1749 u1 = u1 << s;
1750 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
1751 u0 = u0 << s;
1752
1753 d1 = d >> biH;
1754 d0 = d & uint_halfword_mask;
1755
1756 u0_msw = u0 >> biH;
1757 u0_lsw = u0 & uint_halfword_mask;
1758
1759 /*
1760 * Find the first quotient and remainder
1761 */
1762 q1 = u1 / d1;
1763 r0 = u1 - d1 * q1;
1764
1765 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1766 {
1767 q1 -= 1;
1768 r0 += d1;
1769
1770 if ( r0 >= radix ) break;
1771 }
1772
1773 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
1774 q0 = rAX / d1;
1775 r0 = rAX - q0 * d1;
1776
1777 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1778 {
1779 q0 -= 1;
1780 r0 += d1;
1781
1782 if ( r0 >= radix ) break;
1783 }
1784
1785 if (r != NULL)
1786 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
1787
1788 quotient = q1 * radix + q0;
1789
1790 return quotient;
1791 #endif
1792 }
1793
1794 /*
1795 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1796 */
mbedtls_mpi_div_mpi(mbedtls_mpi * Q,mbedtls_mpi * R,const mbedtls_mpi * A,const mbedtls_mpi * B)1797 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1798 const mbedtls_mpi *B )
1799 {
1800 int ret;
1801 size_t i, n, t, k;
1802 mbedtls_mpi X, Y, Z, T1, T2;
1803 MPI_VALIDATE_RET( A != NULL );
1804 MPI_VALIDATE_RET( B != NULL );
1805
1806 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1807 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1808
1809 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1810 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
1811
1812 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1813 {
1814 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1815 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1816 return( 0 );
1817 }
1818
1819 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1820 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1821 X.s = Y.s = 1;
1822
1823 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1824 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1825 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1826 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
1827
1828 k = mbedtls_mpi_bitlen( &Y ) % biL;
1829 if( k < biL - 1 )
1830 {
1831 k = biL - 1 - k;
1832 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1833 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1834 }
1835 else k = 0;
1836
1837 n = X.n - 1;
1838 t = Y.n - 1;
1839 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1840
1841 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
1842 {
1843 Z.p[n - t]++;
1844 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
1845 }
1846 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
1847
1848 for( i = n; i > t ; i-- )
1849 {
1850 if( X.p[i] >= Y.p[t] )
1851 Z.p[i - t - 1] = ~0;
1852 else
1853 {
1854 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1855 Y.p[t], NULL);
1856 }
1857
1858 Z.p[i - t - 1]++;
1859 do
1860 {
1861 Z.p[i - t - 1]--;
1862
1863 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
1864 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
1865 T1.p[1] = Y.p[t];
1866 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1867
1868 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
1869 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1870 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1871 T2.p[2] = X.p[i];
1872 }
1873 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
1874
1875 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1876 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1877 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
1878
1879 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
1880 {
1881 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1882 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1883 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
1884 Z.p[i - t - 1]--;
1885 }
1886 }
1887
1888 if( Q != NULL )
1889 {
1890 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
1891 Q->s = A->s * B->s;
1892 }
1893
1894 if( R != NULL )
1895 {
1896 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
1897 X.s = A->s;
1898 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
1899
1900 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
1901 R->s = 1;
1902 }
1903
1904 cleanup:
1905
1906 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1907 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
1908
1909 return( ret );
1910 }
1911
1912 /*
1913 * Division by int: A = Q * b + R
1914 */
mbedtls_mpi_div_int(mbedtls_mpi * Q,mbedtls_mpi * R,const mbedtls_mpi * A,mbedtls_mpi_sint b)1915 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1916 const mbedtls_mpi *A,
1917 mbedtls_mpi_sint b )
1918 {
1919 mbedtls_mpi _B;
1920 mbedtls_mpi_uint p[1];
1921 MPI_VALIDATE_RET( A != NULL );
1922
1923 p[0] = ( b < 0 ) ? -b : b;
1924 _B.s = ( b < 0 ) ? -1 : 1;
1925 _B.n = 1;
1926 _B.p = p;
1927
1928 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
1929 }
1930
1931 /*
1932 * Modulo: R = A mod B
1933 */
mbedtls_mpi_mod_mpi(mbedtls_mpi * R,const mbedtls_mpi * A,const mbedtls_mpi * B)1934 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1935 {
1936 int ret;
1937 MPI_VALIDATE_RET( R != NULL );
1938 MPI_VALIDATE_RET( A != NULL );
1939 MPI_VALIDATE_RET( B != NULL );
1940
1941 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1942 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1943
1944 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
1945
1946 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1947 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
1948
1949 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1950 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
1951
1952 cleanup:
1953
1954 return( ret );
1955 }
1956
1957 /*
1958 * Modulo: r = A mod b
1959 */
mbedtls_mpi_mod_int(mbedtls_mpi_uint * r,const mbedtls_mpi * A,mbedtls_mpi_sint b)1960 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1961 {
1962 size_t i;
1963 mbedtls_mpi_uint x, y, z;
1964 MPI_VALIDATE_RET( r != NULL );
1965 MPI_VALIDATE_RET( A != NULL );
1966
1967 if( b == 0 )
1968 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1969
1970 if( b < 0 )
1971 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1972
1973 /*
1974 * handle trivial cases
1975 */
1976 if( b == 1 )
1977 {
1978 *r = 0;
1979 return( 0 );
1980 }
1981
1982 if( b == 2 )
1983 {
1984 *r = A->p[0] & 1;
1985 return( 0 );
1986 }
1987
1988 /*
1989 * general case
1990 */
1991 for( i = A->n, y = 0; i > 0; i-- )
1992 {
1993 x = A->p[i - 1];
1994 y = ( y << biH ) | ( x >> biH );
1995 z = y / b;
1996 y -= z * b;
1997
1998 x <<= biH;
1999 y = ( y << biH ) | ( x >> biH );
2000 z = y / b;
2001 y -= z * b;
2002 }
2003
2004 /*
2005 * If A is negative, then the current y represents a negative value.
2006 * Flipping it to the positive side.
2007 */
2008 if( A->s < 0 && y != 0 )
2009 y = b - y;
2010
2011 *r = y;
2012
2013 return( 0 );
2014 }
2015
2016 /*
2017 * Fast Montgomery initialization (thanks to Tom St Denis)
2018 */
mpi_montg_init(mbedtls_mpi_uint * mm,const mbedtls_mpi * N)2019 static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
2020 {
2021 mbedtls_mpi_uint x, m0 = N->p[0];
2022 unsigned int i;
2023
2024 x = m0;
2025 x += ( ( m0 + 2 ) & 4 ) << 1;
2026
2027 for( i = biL; i >= 8; i /= 2 )
2028 x *= ( 2 - ( m0 * x ) );
2029
2030 *mm = ~x + 1;
2031 }
2032
2033 /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
2034 *
2035 * \param[in,out] A One of the numbers to multiply.
2036 * It must have at least as many limbs as N
2037 * (A->n >= N->n), and any limbs beyond n are ignored.
2038 * On successful completion, A contains the result of
2039 * the multiplication A * B * R^-1 mod N where
2040 * R = (2^ciL)^n.
2041 * \param[in] B One of the numbers to multiply.
2042 * It must be nonzero and must not have more limbs than N
2043 * (B->n <= N->n).
2044 * \param[in] N The modulo. N must be odd.
2045 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
2046 * This is -N^-1 mod 2^ciL.
2047 * \param[in,out] T A bignum for temporary storage.
2048 * It must be at least twice the limb size of N plus 2
2049 * (T->n >= 2 * (N->n + 1)).
2050 * Its initial content is unused and
2051 * its final content is indeterminate.
2052 * Note that unlike the usual convention in the library
2053 * for `const mbedtls_mpi*`, the content of T can change.
2054 */
mpi_montmul(mbedtls_mpi * A,const mbedtls_mpi * B,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)2055 static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
2056 const mbedtls_mpi *T )
2057 {
2058 size_t i, n, m;
2059 mbedtls_mpi_uint u0, u1, *d;
2060
2061 memset( T->p, 0, T->n * ciL );
2062
2063 d = T->p;
2064 n = N->n;
2065 m = ( B->n < n ) ? B->n : n;
2066
2067 for( i = 0; i < n; i++ )
2068 {
2069 /*
2070 * T = (T + u0*B + u1*N) / 2^biL
2071 */
2072 u0 = A->p[i];
2073 u1 = ( d[0] + u0 * B->p[0] ) * mm;
2074
2075 mpi_mul_hlp( m, B->p, d, u0 );
2076 mpi_mul_hlp( n, N->p, d, u1 );
2077
2078 *d++ = u0; d[n + 1] = 0;
2079 }
2080
2081 /* At this point, d is either the desired result or the desired result
2082 * plus N. We now potentially subtract N, avoiding leaking whether the
2083 * subtraction is performed through side channels. */
2084
2085 /* Copy the n least significant limbs of d to A, so that
2086 * A = d if d < N (recall that N has n limbs). */
2087 memcpy( A->p, d, n * ciL );
2088 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
2089 * do the calculation without using conditional tests. */
2090 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
2091 d[n] += 1;
2092 d[n] -= mpi_sub_hlp( n, d, N->p );
2093 /* If d0 < N then d < (2^biL)^n
2094 * so d[n] == 0 and we want to keep A as it is.
2095 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
2096 * so d[n] == 1 and we want to set A to the result of the subtraction
2097 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
2098 * This exactly corresponds to a conditional assignment. */
2099 mpi_safe_cond_assign( n, A->p, d, (unsigned char) d[n] );
2100 }
2101
2102 /*
2103 * Montgomery reduction: A = A * R^-1 mod N
2104 *
2105 * See mpi_montmul() regarding constraints and guarantees on the parameters.
2106 */
mpi_montred(mbedtls_mpi * A,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)2107 static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
2108 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
2109 {
2110 mbedtls_mpi_uint z = 1;
2111 mbedtls_mpi U;
2112
2113 U.n = U.s = (int) z;
2114 U.p = &z;
2115
2116 mpi_montmul( A, &U, N, mm, T );
2117 }
2118
2119 /*
2120 * Constant-flow boolean "equal" comparison:
2121 * return x == y
2122 *
2123 * This function can be used to write constant-time code by replacing branches
2124 * with bit operations - it can be used in conjunction with
2125 * mbedtls_ssl_cf_mask_from_bit().
2126 *
2127 * This function is implemented without using comparison operators, as those
2128 * might be translated to branches by some compilers on some platforms.
2129 */
mbedtls_mpi_cf_bool_eq(size_t x,size_t y)2130 static size_t mbedtls_mpi_cf_bool_eq( size_t x, size_t y )
2131 {
2132 /* diff = 0 if x == y, non-zero otherwise */
2133 const size_t diff = x ^ y;
2134
2135 /* MSVC has a warning about unary minus on unsigned integer types,
2136 * but this is well-defined and precisely what we want to do here. */
2137 #if defined(_MSC_VER)
2138 #pragma warning( push )
2139 #pragma warning( disable : 4146 )
2140 #endif
2141
2142 /* diff_msb's most significant bit is equal to x != y */
2143 const size_t diff_msb = ( diff | (size_t) -diff );
2144
2145 #if defined(_MSC_VER)
2146 #pragma warning( pop )
2147 #endif
2148
2149 /* diff1 = (x != y) ? 1 : 0 */
2150 const size_t diff1 = diff_msb >> ( sizeof( diff_msb ) * 8 - 1 );
2151
2152 return( 1 ^ diff1 );
2153 }
2154
2155 /**
2156 * Select an MPI from a table without leaking the index.
2157 *
2158 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
2159 * reads the entire table in order to avoid leaking the value of idx to an
2160 * attacker able to observe memory access patterns.
2161 *
2162 * \param[out] R Where to write the selected MPI.
2163 * \param[in] T The table to read from.
2164 * \param[in] T_size The number of elements in the table.
2165 * \param[in] idx The index of the element to select;
2166 * this must satisfy 0 <= idx < T_size.
2167 *
2168 * \return \c 0 on success, or a negative error code.
2169 */
mpi_select(mbedtls_mpi * R,const mbedtls_mpi * T,size_t T_size,size_t idx)2170 static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
2171 {
2172 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2173 size_t i;
2174
2175 for( i = 0; i < T_size; i++ )
2176 {
2177 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i],
2178 (unsigned char) mbedtls_mpi_cf_bool_eq( i, idx ) ) );
2179 }
2180
2181 cleanup:
2182 return( ret );
2183 }
2184
2185 /*
2186 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
2187 */
mbedtls_mpi_exp_mod(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * E,const mbedtls_mpi * N,mbedtls_mpi * _RR)2188 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
2189 const mbedtls_mpi *E, const mbedtls_mpi *N,
2190 mbedtls_mpi *_RR )
2191 {
2192 int ret;
2193 size_t wbits, wsize, one = 1;
2194 size_t i, j, nblimbs;
2195 size_t bufsize, nbits;
2196 mbedtls_mpi_uint ei, mm, state;
2197 mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
2198 int neg;
2199
2200 MPI_VALIDATE_RET( X != NULL );
2201 MPI_VALIDATE_RET( A != NULL );
2202 MPI_VALIDATE_RET( E != NULL );
2203 MPI_VALIDATE_RET( N != NULL );
2204
2205 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
2206 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2207
2208 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
2209 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2210
2211 if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS ||
2212 mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS )
2213 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2214
2215 /*
2216 * Init temps and window size
2217 */
2218 mpi_montg_init( &mm, N );
2219 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
2220 mbedtls_mpi_init( &Apos );
2221 mbedtls_mpi_init( &WW );
2222 memset( W, 0, sizeof( W ) );
2223
2224 i = mbedtls_mpi_bitlen( E );
2225
2226 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2227 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2228
2229 #if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
2230 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2231 wsize = MBEDTLS_MPI_WINDOW_SIZE;
2232 #endif
2233
2234 j = N->n + 1;
2235 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
2236 * and mpi_montred() calls later. Here we ensure that W[1] and X are
2237 * large enough, and later we'll grow other W[i] to the same length.
2238 * They must not be shrunk midway through this function!
2239 */
2240 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2241 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2242 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
2243
2244 /*
2245 * Compensate for negative A (and correct at the end)
2246 */
2247 neg = ( A->s == -1 );
2248 if( neg )
2249 {
2250 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
2251 Apos.s = 1;
2252 A = &Apos;
2253 }
2254
2255 /*
2256 * If 1st call, pre-compute R^2 mod N
2257 */
2258 if( _RR == NULL || _RR->p == NULL )
2259 {
2260 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2261 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2262 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
2263
2264 if( _RR != NULL )
2265 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
2266 }
2267 else
2268 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
2269
2270 /*
2271 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2272 */
2273 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
2274 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
2275 else
2276 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
2277 /* Re-grow W[1] if necessary. This should be only necessary in one corner
2278 * case: when A == 0 represented with A.n == 0, mbedtls_mpi_copy shrinks
2279 * W[1] to 0 limbs. */
2280 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n +1 ) );
2281
2282 mpi_montmul( &W[1], &RR, N, mm, &T );
2283
2284 /*
2285 * X = R^2 * R^-1 mod N = R mod N
2286 */
2287 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
2288 mpi_montred( X, N, mm, &T );
2289
2290 if( wsize > 1 )
2291 {
2292 /*
2293 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2294 */
2295 j = one << ( wsize - 1 );
2296
2297 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2298 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
2299
2300 for( i = 0; i < wsize - 1; i++ )
2301 mpi_montmul( &W[j], &W[j], N, mm, &T );
2302
2303 /*
2304 * W[i] = W[i - 1] * W[1]
2305 */
2306 for( i = j + 1; i < ( one << wsize ); i++ )
2307 {
2308 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2309 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
2310
2311 mpi_montmul( &W[i], &W[1], N, mm, &T );
2312 }
2313 }
2314
2315 nblimbs = E->n;
2316 bufsize = 0;
2317 nbits = 0;
2318 wbits = 0;
2319 state = 0;
2320
2321 while( 1 )
2322 {
2323 if( bufsize == 0 )
2324 {
2325 if( nblimbs == 0 )
2326 break;
2327
2328 nblimbs--;
2329
2330 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
2331 }
2332
2333 bufsize--;
2334
2335 ei = (E->p[nblimbs] >> bufsize) & 1;
2336
2337 /*
2338 * skip leading 0s
2339 */
2340 if( ei == 0 && state == 0 )
2341 continue;
2342
2343 if( ei == 0 && state == 1 )
2344 {
2345 /*
2346 * out of window, square X
2347 */
2348 mpi_montmul( X, X, N, mm, &T );
2349 continue;
2350 }
2351
2352 /*
2353 * add ei to current window
2354 */
2355 state = 2;
2356
2357 nbits++;
2358 wbits |= ( ei << ( wsize - nbits ) );
2359
2360 if( nbits == wsize )
2361 {
2362 /*
2363 * X = X^wsize R^-1 mod N
2364 */
2365 for( i = 0; i < wsize; i++ )
2366 mpi_montmul( X, X, N, mm, &T );
2367
2368 /*
2369 * X = X * W[wbits] R^-1 mod N
2370 */
2371 MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
2372 mpi_montmul( X, &WW, N, mm, &T );
2373
2374 state--;
2375 nbits = 0;
2376 wbits = 0;
2377 }
2378 }
2379
2380 /*
2381 * process the remaining bits
2382 */
2383 for( i = 0; i < nbits; i++ )
2384 {
2385 mpi_montmul( X, X, N, mm, &T );
2386
2387 wbits <<= 1;
2388
2389 if( ( wbits & ( one << wsize ) ) != 0 )
2390 mpi_montmul( X, &W[1], N, mm, &T );
2391 }
2392
2393 /*
2394 * X = A^E * R * R^-1 mod N = A^E mod N
2395 */
2396 mpi_montred( X, N, mm, &T );
2397
2398 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
2399 {
2400 X->s = -1;
2401 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
2402 }
2403
2404 cleanup:
2405
2406 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
2407 mbedtls_mpi_free( &W[i] );
2408
2409 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
2410 mbedtls_mpi_free( &WW );
2411
2412 if( _RR == NULL || _RR->p == NULL )
2413 mbedtls_mpi_free( &RR );
2414
2415 return( ret );
2416 }
2417
2418 /*
2419 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2420 */
mbedtls_mpi_gcd(mbedtls_mpi * G,const mbedtls_mpi * A,const mbedtls_mpi * B)2421 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
2422 {
2423 int ret;
2424 size_t lz, lzt;
2425 mbedtls_mpi TG, TA, TB;
2426
2427 MPI_VALIDATE_RET( G != NULL );
2428 MPI_VALIDATE_RET( A != NULL );
2429 MPI_VALIDATE_RET( B != NULL );
2430
2431 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
2432
2433 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2434 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
2435
2436 lz = mbedtls_mpi_lsb( &TA );
2437 lzt = mbedtls_mpi_lsb( &TB );
2438
2439 /* The loop below gives the correct result when A==0 but not when B==0.
2440 * So have a special case for B==0. Leverage the fact that we just
2441 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
2442 * slightly more efficient than cmp_int(). */
2443 if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 )
2444 {
2445 ret = mbedtls_mpi_copy( G, A );
2446 goto cleanup;
2447 }
2448
2449 if( lzt < lz )
2450 lz = lzt;
2451
2452 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2453 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
2454
2455 TA.s = TB.s = 1;
2456
2457 /* We mostly follow the procedure described in HAC 14.54, but with some
2458 * minor differences:
2459 * - Sequences of multiplications or divisions by 2 are grouped into a
2460 * single shift operation.
2461 * - The procedure in HAC assumes that 0 < TB <= TA.
2462 * - The condition TB <= TA is not actually necessary for correctness.
2463 * TA and TB have symmetric roles except for the loop termination
2464 * condition, and the shifts at the beginning of the loop body
2465 * remove any significance from the ordering of TA vs TB before
2466 * the shifts.
2467 * - If TA = 0, the loop goes through 0 iterations and the result is
2468 * correctly TB.
2469 * - The case TB = 0 was short-circuited above.
2470 *
2471 * For the correctness proof below, decompose the original values of
2472 * A and B as
2473 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
2474 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
2475 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
2476 * and gcd(A',B') is odd or 0.
2477 *
2478 * At the beginning, we have TA = |A|/2^a and TB = |B|/2^b.
2479 * The code maintains the following invariant:
2480 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
2481 */
2482
2483 /* Proof that the loop terminates:
2484 * At each iteration, either the right-shift by 1 is made on a nonzero
2485 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
2486 * by at least 1, or the right-shift by 1 is made on zero and then
2487 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
2488 * since in that case TB is calculated from TB-TA with the condition TB>TA).
2489 */
2490 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
2491 {
2492 /* Divisions by 2 preserve the invariant (I). */
2493 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2494 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
2495
2496 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
2497 * TA-TB is even so the division by 2 has an integer result.
2498 * Invariant (I) is preserved since any odd divisor of both TA and TB
2499 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
2500 * also divides TB, and any odd divisior of both TB and |TA-TB|/2 also
2501 * divides TA.
2502 */
2503 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
2504 {
2505 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2506 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
2507 }
2508 else
2509 {
2510 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2511 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
2512 }
2513 /* Note that one of TA or TB is still odd. */
2514 }
2515
2516 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
2517 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
2518 * - If there was at least one loop iteration, then one of TA or TB is odd,
2519 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
2520 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
2521 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
2522 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
2523 */
2524
2525 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2526 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
2527
2528 cleanup:
2529
2530 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
2531
2532 return( ret );
2533 }
2534
2535 /*
2536 * Fill X with size bytes of random.
2537 *
2538 * Use a temporary bytes representation to make sure the result is the same
2539 * regardless of the platform endianness (useful when f_rng is actually
2540 * deterministic, eg for tests).
2541 */
mbedtls_mpi_fill_random(mbedtls_mpi * X,size_t size,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2542 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
2543 int (*f_rng)(void *, unsigned char *, size_t),
2544 void *p_rng )
2545 {
2546 int ret;
2547 size_t const limbs = CHARS_TO_LIMBS( size );
2548 size_t const overhead = ( limbs * ciL ) - size;
2549 unsigned char *Xp;
2550
2551 MPI_VALIDATE_RET( X != NULL );
2552 MPI_VALIDATE_RET( f_rng != NULL );
2553
2554 /* Ensure that target MPI has exactly the necessary number of limbs */
2555 if( X->n != limbs )
2556 {
2557 mbedtls_mpi_free( X );
2558 mbedtls_mpi_init( X );
2559 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
2560 }
2561 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
2562
2563 Xp = (unsigned char*) X->p;
2564 MBEDTLS_MPI_CHK( f_rng( p_rng, Xp + overhead, size ) );
2565
2566 mpi_bigendian_to_host( X->p, limbs );
2567
2568 cleanup:
2569 return( ret );
2570 }
2571
2572 /*
2573 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2574 */
mbedtls_mpi_inv_mod(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * N)2575 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
2576 {
2577 int ret;
2578 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
2579 MPI_VALIDATE_RET( X != NULL );
2580 MPI_VALIDATE_RET( A != NULL );
2581 MPI_VALIDATE_RET( N != NULL );
2582
2583 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
2584 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2585
2586 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2587 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2588 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
2589
2590 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
2591
2592 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
2593 {
2594 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2595 goto cleanup;
2596 }
2597
2598 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2599 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2600 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2601 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
2602
2603 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2604 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2605 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2606 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
2607
2608 do
2609 {
2610 while( ( TU.p[0] & 1 ) == 0 )
2611 {
2612 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
2613
2614 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2615 {
2616 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2617 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
2618 }
2619
2620 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2621 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
2622 }
2623
2624 while( ( TV.p[0] & 1 ) == 0 )
2625 {
2626 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
2627
2628 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2629 {
2630 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2631 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
2632 }
2633
2634 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2635 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
2636 }
2637
2638 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
2639 {
2640 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2641 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2642 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
2643 }
2644 else
2645 {
2646 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2647 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2648 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
2649 }
2650 }
2651 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
2652
2653 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2654 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
2655
2656 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2657 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
2658
2659 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
2660
2661 cleanup:
2662
2663 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2664 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2665 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
2666
2667 return( ret );
2668 }
2669
2670 #if defined(MBEDTLS_GENPRIME)
2671
2672 static const int small_prime[] =
2673 {
2674 3, 5, 7, 11, 13, 17, 19, 23,
2675 29, 31, 37, 41, 43, 47, 53, 59,
2676 61, 67, 71, 73, 79, 83, 89, 97,
2677 101, 103, 107, 109, 113, 127, 131, 137,
2678 139, 149, 151, 157, 163, 167, 173, 179,
2679 181, 191, 193, 197, 199, 211, 223, 227,
2680 229, 233, 239, 241, 251, 257, 263, 269,
2681 271, 277, 281, 283, 293, 307, 311, 313,
2682 317, 331, 337, 347, 349, 353, 359, 367,
2683 373, 379, 383, 389, 397, 401, 409, 419,
2684 421, 431, 433, 439, 443, 449, 457, 461,
2685 463, 467, 479, 487, 491, 499, 503, 509,
2686 521, 523, 541, 547, 557, 563, 569, 571,
2687 577, 587, 593, 599, 601, 607, 613, 617,
2688 619, 631, 641, 643, 647, 653, 659, 661,
2689 673, 677, 683, 691, 701, 709, 719, 727,
2690 733, 739, 743, 751, 757, 761, 769, 773,
2691 787, 797, 809, 811, 821, 823, 827, 829,
2692 839, 853, 857, 859, 863, 877, 881, 883,
2693 887, 907, 911, 919, 929, 937, 941, 947,
2694 953, 967, 971, 977, 983, 991, 997, -103
2695 };
2696
2697 /*
2698 * Small divisors test (X must be positive)
2699 *
2700 * Return values:
2701 * 0: no small factor (possible prime, more tests needed)
2702 * 1: certain prime
2703 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2704 * other negative: error
2705 */
mpi_check_small_factors(const mbedtls_mpi * X)2706 static int mpi_check_small_factors( const mbedtls_mpi *X )
2707 {
2708 int ret = 0;
2709 size_t i;
2710 mbedtls_mpi_uint r;
2711
2712 if( ( X->p[0] & 1 ) == 0 )
2713 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2714
2715 for( i = 0; small_prime[i] > 0; i++ )
2716 {
2717 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
2718 return( 1 );
2719
2720 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
2721
2722 if( r == 0 )
2723 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2724 }
2725
2726 cleanup:
2727 return( ret );
2728 }
2729
2730 /*
2731 * Miller-Rabin pseudo-primality test (HAC 4.24)
2732 */
mpi_miller_rabin(const mbedtls_mpi * X,size_t rounds,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2733 static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
2734 int (*f_rng)(void *, unsigned char *, size_t),
2735 void *p_rng )
2736 {
2737 int ret, count;
2738 size_t i, j, k, s;
2739 mbedtls_mpi W, R, T, A, RR;
2740
2741 MPI_VALIDATE_RET( X != NULL );
2742 MPI_VALIDATE_RET( f_rng != NULL );
2743
2744 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2745 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2746 mbedtls_mpi_init( &RR );
2747
2748 /*
2749 * W = |X| - 1
2750 * R = W >> lsb( W )
2751 */
2752 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2753 s = mbedtls_mpi_lsb( &W );
2754 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2755 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
2756
2757 for( i = 0; i < rounds; i++ )
2758 {
2759 /*
2760 * pick a random A, 1 < A < |X| - 1
2761 */
2762 count = 0;
2763 do {
2764 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2765
2766 j = mbedtls_mpi_bitlen( &A );
2767 k = mbedtls_mpi_bitlen( &W );
2768 if (j > k) {
2769 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
2770 }
2771
2772 if (count++ > 30) {
2773 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2774 goto cleanup;
2775 }
2776
2777 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2778 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
2779
2780 /*
2781 * A = A^R mod |X|
2782 */
2783 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
2784
2785 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2786 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2787 continue;
2788
2789 j = 1;
2790 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
2791 {
2792 /*
2793 * A = A * A mod |X|
2794 */
2795 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2796 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
2797
2798 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2799 break;
2800
2801 j++;
2802 }
2803
2804 /*
2805 * not prime if A != |X| - 1 or A == 1
2806 */
2807 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2808 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2809 {
2810 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2811 break;
2812 }
2813 }
2814
2815 cleanup:
2816 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2817 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2818 mbedtls_mpi_free( &RR );
2819
2820 return( ret );
2821 }
2822
2823 /*
2824 * Pseudo-primality test: small factors, then Miller-Rabin
2825 */
mbedtls_mpi_is_prime_ext(const mbedtls_mpi * X,int rounds,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2826 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2827 int (*f_rng)(void *, unsigned char *, size_t),
2828 void *p_rng )
2829 {
2830 int ret;
2831 mbedtls_mpi XX;
2832 MPI_VALIDATE_RET( X != NULL );
2833 MPI_VALIDATE_RET( f_rng != NULL );
2834
2835 XX.s = 1;
2836 XX.n = X->n;
2837 XX.p = X->p;
2838
2839 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2840 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2841 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2842
2843 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
2844 return( 0 );
2845
2846 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2847 {
2848 if( ret == 1 )
2849 return( 0 );
2850
2851 return( ret );
2852 }
2853
2854 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
2855 }
2856
2857 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
2858 /*
2859 * Pseudo-primality test, error probability 2^-80
2860 */
mbedtls_mpi_is_prime(const mbedtls_mpi * X,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2861 int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2862 int (*f_rng)(void *, unsigned char *, size_t),
2863 void *p_rng )
2864 {
2865 MPI_VALIDATE_RET( X != NULL );
2866 MPI_VALIDATE_RET( f_rng != NULL );
2867
2868 /*
2869 * In the past our key generation aimed for an error rate of at most
2870 * 2^-80. Since this function is deprecated, aim for the same certainty
2871 * here as well.
2872 */
2873 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
2874 }
2875 #endif
2876
2877 /*
2878 * Prime number generation
2879 *
2880 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2881 * be either 1024 bits or 1536 bits long, and flags must contain
2882 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2883 */
mbedtls_mpi_gen_prime(mbedtls_mpi * X,size_t nbits,int flags,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2884 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
2885 int (*f_rng)(void *, unsigned char *, size_t),
2886 void *p_rng )
2887 {
2888 #ifdef MBEDTLS_HAVE_INT64
2889 // ceil(2^63.5)
2890 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2891 #else
2892 // ceil(2^31.5)
2893 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2894 #endif
2895 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2896 size_t k, n;
2897 int rounds;
2898 mbedtls_mpi_uint r;
2899 mbedtls_mpi Y;
2900
2901 MPI_VALIDATE_RET( X != NULL );
2902 MPI_VALIDATE_RET( f_rng != NULL );
2903
2904 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2905 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2906
2907 mbedtls_mpi_init( &Y );
2908
2909 n = BITS_TO_LIMBS( nbits );
2910
2911 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2912 {
2913 /*
2914 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2915 */
2916 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2917 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2918 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2919 }
2920 else
2921 {
2922 /*
2923 * 2^-100 error probability, number of rounds computed based on HAC,
2924 * fact 4.48
2925 */
2926 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2927 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2928 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2929 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2930 }
2931
2932 while( 1 )
2933 {
2934 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2935 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2936 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2937
2938 k = n * biL;
2939 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2940 X->p[0] |= 1;
2941
2942 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
2943 {
2944 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
2945
2946 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2947 goto cleanup;
2948 }
2949 else
2950 {
2951 /*
2952 * An necessary condition for Y and X = 2Y + 1 to be prime
2953 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2954 * Make sure it is satisfied, while keeping X = 3 mod 4
2955 */
2956
2957 X->p[0] |= 2;
2958
2959 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2960 if( r == 0 )
2961 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2962 else if( r == 1 )
2963 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2964
2965 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2966 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2967 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2968
2969 while( 1 )
2970 {
2971 /*
2972 * First, check small factors for X and Y
2973 * before doing Miller-Rabin on any of them
2974 */
2975 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2976 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2977 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
2978 == 0 &&
2979 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
2980 == 0 )
2981 goto cleanup;
2982
2983 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2984 goto cleanup;
2985
2986 /*
2987 * Next candidates. We want to preserve Y = (X-1) / 2 and
2988 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2989 * so up Y by 6 and X by 12.
2990 */
2991 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2992 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
2993 }
2994 }
2995 }
2996
2997 cleanup:
2998
2999 mbedtls_mpi_free( &Y );
3000
3001 return( ret );
3002 }
3003
3004 #endif /* MBEDTLS_GENPRIME */
3005
3006 #if defined(MBEDTLS_SELF_TEST)
3007
3008 #define GCD_PAIR_COUNT 3
3009
3010 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
3011 {
3012 { 693, 609, 21 },
3013 { 1764, 868, 28 },
3014 { 768454923, 542167814, 1 }
3015 };
3016
3017 /*
3018 * Checkup routine
3019 */
mbedtls_mpi_self_test(int verbose)3020 int mbedtls_mpi_self_test( int verbose )
3021 {
3022 int ret, i;
3023 mbedtls_mpi A, E, N, X, Y, U, V;
3024
3025 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
3026 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
3027
3028 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
3029 "EFE021C2645FD1DC586E69184AF4A31E" \
3030 "D5F53E93B5F123FA41680867BA110131" \
3031 "944FE7952E2517337780CB0DB80E61AA" \
3032 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
3033
3034 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
3035 "B2E7EFD37075B9F03FF989C7C5051C20" \
3036 "34D2A323810251127E7BF8625A4F49A5" \
3037 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
3038 "5B5C25763222FEFCCFC38B832366C29E" ) );
3039
3040 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
3041 "0066A198186C18C10B2F5ED9B522752A" \
3042 "9830B69916E535C8F047518A889A43A5" \
3043 "94B6BED27A168D31D4A52F88925AA8F5" ) );
3044
3045 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
3046
3047 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3048 "602AB7ECA597A3D6B56FF9829A5E8B85" \
3049 "9E857EA95A03512E2BAE7391688D264A" \
3050 "A5663B0341DB9CCFD2C4C5F421FEC814" \
3051 "8001B72E848A38CAE1C65F78E56ABDEF" \
3052 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
3053 "ECF677152EF804370C1A305CAF3B5BF1" \
3054 "30879B56C61DE584A0F53A2447A51E" ) );
3055
3056 if( verbose != 0 )
3057 mbedtls_printf( " MPI test #1 (mul_mpi): " );
3058
3059 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
3060 {
3061 if( verbose != 0 )
3062 mbedtls_printf( "failed\n" );
3063
3064 ret = 1;
3065 goto cleanup;
3066 }
3067
3068 if( verbose != 0 )
3069 mbedtls_printf( "passed\n" );
3070
3071 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
3072
3073 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3074 "256567336059E52CAE22925474705F39A94" ) );
3075
3076 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
3077 "6613F26162223DF488E9CD48CC132C7A" \
3078 "0AC93C701B001B092E4E5B9F73BCD27B" \
3079 "9EE50D0657C77F374E903CDFA4C642" ) );
3080
3081 if( verbose != 0 )
3082 mbedtls_printf( " MPI test #2 (div_mpi): " );
3083
3084 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
3085 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
3086 {
3087 if( verbose != 0 )
3088 mbedtls_printf( "failed\n" );
3089
3090 ret = 1;
3091 goto cleanup;
3092 }
3093
3094 if( verbose != 0 )
3095 mbedtls_printf( "passed\n" );
3096
3097 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
3098
3099 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3100 "36E139AEA55215609D2816998ED020BB" \
3101 "BD96C37890F65171D948E9BC7CBAA4D9" \
3102 "325D24D6A3C12710F10A09FA08AB87" ) );
3103
3104 if( verbose != 0 )
3105 mbedtls_printf( " MPI test #3 (exp_mod): " );
3106
3107 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
3108 {
3109 if( verbose != 0 )
3110 mbedtls_printf( "failed\n" );
3111
3112 ret = 1;
3113 goto cleanup;
3114 }
3115
3116 if( verbose != 0 )
3117 mbedtls_printf( "passed\n" );
3118
3119 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
3120
3121 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3122 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
3123 "C3DBA76456363A10869622EAC2DD84EC" \
3124 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
3125
3126 if( verbose != 0 )
3127 mbedtls_printf( " MPI test #4 (inv_mod): " );
3128
3129 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
3130 {
3131 if( verbose != 0 )
3132 mbedtls_printf( "failed\n" );
3133
3134 ret = 1;
3135 goto cleanup;
3136 }
3137
3138 if( verbose != 0 )
3139 mbedtls_printf( "passed\n" );
3140
3141 if( verbose != 0 )
3142 mbedtls_printf( " MPI test #5 (simple gcd): " );
3143
3144 for( i = 0; i < GCD_PAIR_COUNT; i++ )
3145 {
3146 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
3147 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
3148
3149 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
3150
3151 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
3152 {
3153 if( verbose != 0 )
3154 mbedtls_printf( "failed at %d\n", i );
3155
3156 ret = 1;
3157 goto cleanup;
3158 }
3159 }
3160
3161 if( verbose != 0 )
3162 mbedtls_printf( "passed\n" );
3163
3164 cleanup:
3165
3166 if( ret != 0 && verbose != 0 )
3167 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
3168
3169 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
3170 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
3171
3172 if( verbose != 0 )
3173 mbedtls_printf( "\n" );
3174
3175 return( ret );
3176 }
3177
3178 #endif /* MBEDTLS_SELF_TEST */
3179
3180 #endif /* MBEDTLS_BIGNUM_C */
3181