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