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
1358 carry = mpi_sub_hlp( n, X->p, B->p );
1359 if( carry != 0 )
1360 {
1361 /* Propagate the carry to the first nonzero limb of X. */
1362 for( ; n < X->n && X->p[n] == 0; n++ )
1363 --X->p[n];
1364 /* If we ran out of space for the carry, it means that the result
1365 * is negative. */
1366 if( n == X->n )
1367 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1368 --X->p[n];
1369 }
1370
1371 cleanup:
1372
1373 mbedtls_mpi_free( &TB );
1374
1375 return( ret );
1376 }
1377
1378 /*
1379 * Signed addition: X = A + B
1380 */
mbedtls_mpi_add_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1381 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1382 {
1383 int ret, s;
1384 MPI_VALIDATE_RET( X != NULL );
1385 MPI_VALIDATE_RET( A != NULL );
1386 MPI_VALIDATE_RET( B != NULL );
1387
1388 s = A->s;
1389 if( A->s * B->s < 0 )
1390 {
1391 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1392 {
1393 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1394 X->s = s;
1395 }
1396 else
1397 {
1398 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1399 X->s = -s;
1400 }
1401 }
1402 else
1403 {
1404 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1405 X->s = s;
1406 }
1407
1408 cleanup:
1409
1410 return( ret );
1411 }
1412
1413 /*
1414 * Signed subtraction: X = A - B
1415 */
mbedtls_mpi_sub_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1416 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1417 {
1418 int ret, s;
1419 MPI_VALIDATE_RET( X != NULL );
1420 MPI_VALIDATE_RET( A != NULL );
1421 MPI_VALIDATE_RET( B != NULL );
1422
1423 s = A->s;
1424 if( A->s * B->s > 0 )
1425 {
1426 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1427 {
1428 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1429 X->s = s;
1430 }
1431 else
1432 {
1433 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1434 X->s = -s;
1435 }
1436 }
1437 else
1438 {
1439 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1440 X->s = s;
1441 }
1442
1443 cleanup:
1444
1445 return( ret );
1446 }
1447
1448 /*
1449 * Signed addition: X = A + b
1450 */
mbedtls_mpi_add_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_sint b)1451 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1452 {
1453 mbedtls_mpi _B;
1454 mbedtls_mpi_uint p[1];
1455 MPI_VALIDATE_RET( X != NULL );
1456 MPI_VALIDATE_RET( A != NULL );
1457
1458 p[0] = ( b < 0 ) ? -b : b;
1459 _B.s = ( b < 0 ) ? -1 : 1;
1460 _B.n = 1;
1461 _B.p = p;
1462
1463 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
1464 }
1465
1466 /*
1467 * Signed subtraction: X = A - b
1468 */
mbedtls_mpi_sub_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_sint b)1469 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1470 {
1471 mbedtls_mpi _B;
1472 mbedtls_mpi_uint p[1];
1473 MPI_VALIDATE_RET( X != NULL );
1474 MPI_VALIDATE_RET( A != NULL );
1475
1476 p[0] = ( b < 0 ) ? -b : b;
1477 _B.s = ( b < 0 ) ? -1 : 1;
1478 _B.n = 1;
1479 _B.p = p;
1480
1481 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
1482 }
1483
1484 /*
1485 * Helper for mbedtls_mpi multiplication
1486 */
1487 static
1488 #if defined(__APPLE__) && defined(__arm__)
1489 /*
1490 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1491 * appears to need this to prevent bad ARM code generation at -O3.
1492 */
1493 __attribute__ ((noinline))
1494 #endif
mpi_mul_hlp(size_t i,mbedtls_mpi_uint * s,mbedtls_mpi_uint * d,mbedtls_mpi_uint b)1495 void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
1496 {
1497 mbedtls_mpi_uint c = 0, t = 0;
1498
1499 #if defined(MULADDC_HUIT)
1500 for( ; i >= 8; i -= 8 )
1501 {
1502 MULADDC_INIT
1503 MULADDC_HUIT
1504 MULADDC_STOP
1505 }
1506
1507 for( ; i > 0; i-- )
1508 {
1509 MULADDC_INIT
1510 MULADDC_CORE
1511 MULADDC_STOP
1512 }
1513 #else /* MULADDC_HUIT */
1514 for( ; i >= 16; i -= 16 )
1515 {
1516 MULADDC_INIT
1517 MULADDC_CORE MULADDC_CORE
1518 MULADDC_CORE MULADDC_CORE
1519 MULADDC_CORE MULADDC_CORE
1520 MULADDC_CORE MULADDC_CORE
1521
1522 MULADDC_CORE MULADDC_CORE
1523 MULADDC_CORE MULADDC_CORE
1524 MULADDC_CORE MULADDC_CORE
1525 MULADDC_CORE MULADDC_CORE
1526 MULADDC_STOP
1527 }
1528
1529 for( ; i >= 8; i -= 8 )
1530 {
1531 MULADDC_INIT
1532 MULADDC_CORE MULADDC_CORE
1533 MULADDC_CORE MULADDC_CORE
1534
1535 MULADDC_CORE MULADDC_CORE
1536 MULADDC_CORE MULADDC_CORE
1537 MULADDC_STOP
1538 }
1539
1540 for( ; i > 0; i-- )
1541 {
1542 MULADDC_INIT
1543 MULADDC_CORE
1544 MULADDC_STOP
1545 }
1546 #endif /* MULADDC_HUIT */
1547
1548 t++;
1549
1550 do {
1551 *d += c; c = ( *d < c ); d++;
1552 }
1553 while( c != 0 );
1554 }
1555
1556 /*
1557 * Baseline multiplication: X = A * B (HAC 14.12)
1558 */
mbedtls_mpi_mul_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1559 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1560 {
1561 int ret;
1562 size_t i, j;
1563 mbedtls_mpi TA, TB;
1564 MPI_VALIDATE_RET( X != NULL );
1565 MPI_VALIDATE_RET( A != NULL );
1566 MPI_VALIDATE_RET( B != NULL );
1567
1568 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
1569
1570 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1571 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1572
1573 for( i = A->n; i > 0; i-- )
1574 if( A->p[i - 1] != 0 )
1575 break;
1576
1577 for( j = B->n; j > 0; j-- )
1578 if( B->p[j - 1] != 0 )
1579 break;
1580
1581 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1582 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1583
1584 for( ; j > 0; j-- )
1585 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
1586
1587 X->s = A->s * B->s;
1588
1589 cleanup:
1590
1591 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
1592
1593 return( ret );
1594 }
1595
1596 /*
1597 * Baseline multiplication: X = A * b
1598 */
mbedtls_mpi_mul_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_uint b)1599 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1600 {
1601 mbedtls_mpi _B;
1602 mbedtls_mpi_uint p[1];
1603 MPI_VALIDATE_RET( X != NULL );
1604 MPI_VALIDATE_RET( A != NULL );
1605
1606 _B.s = 1;
1607 _B.n = 1;
1608 _B.p = p;
1609 p[0] = b;
1610
1611 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
1612 }
1613
1614 /*
1615 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1616 * mbedtls_mpi_uint divisor, d
1617 */
mbedtls_int_div_int(mbedtls_mpi_uint u1,mbedtls_mpi_uint u0,mbedtls_mpi_uint d,mbedtls_mpi_uint * r)1618 static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1619 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
1620 {
1621 #if defined(MBEDTLS_HAVE_UDBL)
1622 mbedtls_t_udbl dividend, quotient;
1623 #else
1624 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1625 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
1626 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1627 mbedtls_mpi_uint u0_msw, u0_lsw;
1628 size_t s;
1629 #endif
1630
1631 /*
1632 * Check for overflow
1633 */
1634 if( 0 == d || u1 >= d )
1635 {
1636 if (r != NULL) *r = ~0;
1637
1638 return ( ~0 );
1639 }
1640
1641 #if defined(MBEDTLS_HAVE_UDBL)
1642 dividend = (mbedtls_t_udbl) u1 << biL;
1643 dividend |= (mbedtls_t_udbl) u0;
1644 quotient = dividend / d;
1645 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1646 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1647
1648 if( r != NULL )
1649 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
1650
1651 return (mbedtls_mpi_uint) quotient;
1652 #else
1653
1654 /*
1655 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1656 * Vol. 2 - Seminumerical Algorithms, Knuth
1657 */
1658
1659 /*
1660 * Normalize the divisor, d, and dividend, u0, u1
1661 */
1662 s = mbedtls_clz( d );
1663 d = d << s;
1664
1665 u1 = u1 << s;
1666 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
1667 u0 = u0 << s;
1668
1669 d1 = d >> biH;
1670 d0 = d & uint_halfword_mask;
1671
1672 u0_msw = u0 >> biH;
1673 u0_lsw = u0 & uint_halfword_mask;
1674
1675 /*
1676 * Find the first quotient and remainder
1677 */
1678 q1 = u1 / d1;
1679 r0 = u1 - d1 * q1;
1680
1681 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1682 {
1683 q1 -= 1;
1684 r0 += d1;
1685
1686 if ( r0 >= radix ) break;
1687 }
1688
1689 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
1690 q0 = rAX / d1;
1691 r0 = rAX - q0 * d1;
1692
1693 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1694 {
1695 q0 -= 1;
1696 r0 += d1;
1697
1698 if ( r0 >= radix ) break;
1699 }
1700
1701 if (r != NULL)
1702 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
1703
1704 quotient = q1 * radix + q0;
1705
1706 return quotient;
1707 #endif
1708 }
1709
1710 /*
1711 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1712 */
mbedtls_mpi_div_mpi(mbedtls_mpi * Q,mbedtls_mpi * R,const mbedtls_mpi * A,const mbedtls_mpi * B)1713 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1714 const mbedtls_mpi *B )
1715 {
1716 int ret;
1717 size_t i, n, t, k;
1718 mbedtls_mpi X, Y, Z, T1, T2;
1719 MPI_VALIDATE_RET( A != NULL );
1720 MPI_VALIDATE_RET( B != NULL );
1721
1722 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1723 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1724
1725 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1726 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
1727
1728 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1729 {
1730 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1731 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1732 return( 0 );
1733 }
1734
1735 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1736 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1737 X.s = Y.s = 1;
1738
1739 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1740 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1741 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1742 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
1743
1744 k = mbedtls_mpi_bitlen( &Y ) % biL;
1745 if( k < biL - 1 )
1746 {
1747 k = biL - 1 - k;
1748 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1749 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1750 }
1751 else k = 0;
1752
1753 n = X.n - 1;
1754 t = Y.n - 1;
1755 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1756
1757 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
1758 {
1759 Z.p[n - t]++;
1760 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
1761 }
1762 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
1763
1764 for( i = n; i > t ; i-- )
1765 {
1766 if( X.p[i] >= Y.p[t] )
1767 Z.p[i - t - 1] = ~0;
1768 else
1769 {
1770 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1771 Y.p[t], NULL);
1772 }
1773
1774 Z.p[i - t - 1]++;
1775 do
1776 {
1777 Z.p[i - t - 1]--;
1778
1779 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
1780 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
1781 T1.p[1] = Y.p[t];
1782 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1783
1784 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
1785 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1786 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1787 T2.p[2] = X.p[i];
1788 }
1789 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
1790
1791 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1792 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1793 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
1794
1795 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
1796 {
1797 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1798 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1799 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
1800 Z.p[i - t - 1]--;
1801 }
1802 }
1803
1804 if( Q != NULL )
1805 {
1806 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
1807 Q->s = A->s * B->s;
1808 }
1809
1810 if( R != NULL )
1811 {
1812 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
1813 X.s = A->s;
1814 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
1815
1816 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
1817 R->s = 1;
1818 }
1819
1820 cleanup:
1821
1822 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1823 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
1824
1825 return( ret );
1826 }
1827
1828 /*
1829 * Division by int: A = Q * b + R
1830 */
mbedtls_mpi_div_int(mbedtls_mpi * Q,mbedtls_mpi * R,const mbedtls_mpi * A,mbedtls_mpi_sint b)1831 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1832 const mbedtls_mpi *A,
1833 mbedtls_mpi_sint b )
1834 {
1835 mbedtls_mpi _B;
1836 mbedtls_mpi_uint p[1];
1837 MPI_VALIDATE_RET( A != NULL );
1838
1839 p[0] = ( b < 0 ) ? -b : b;
1840 _B.s = ( b < 0 ) ? -1 : 1;
1841 _B.n = 1;
1842 _B.p = p;
1843
1844 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
1845 }
1846
1847 /*
1848 * Modulo: R = A mod B
1849 */
mbedtls_mpi_mod_mpi(mbedtls_mpi * R,const mbedtls_mpi * A,const mbedtls_mpi * B)1850 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1851 {
1852 int ret;
1853 MPI_VALIDATE_RET( R != NULL );
1854 MPI_VALIDATE_RET( A != NULL );
1855 MPI_VALIDATE_RET( B != NULL );
1856
1857 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1858 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1859
1860 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
1861
1862 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1863 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
1864
1865 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1866 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
1867
1868 cleanup:
1869
1870 return( ret );
1871 }
1872
1873 /*
1874 * Modulo: r = A mod b
1875 */
mbedtls_mpi_mod_int(mbedtls_mpi_uint * r,const mbedtls_mpi * A,mbedtls_mpi_sint b)1876 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1877 {
1878 size_t i;
1879 mbedtls_mpi_uint x, y, z;
1880 MPI_VALIDATE_RET( r != NULL );
1881 MPI_VALIDATE_RET( A != NULL );
1882
1883 if( b == 0 )
1884 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1885
1886 if( b < 0 )
1887 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1888
1889 /*
1890 * handle trivial cases
1891 */
1892 if( b == 1 )
1893 {
1894 *r = 0;
1895 return( 0 );
1896 }
1897
1898 if( b == 2 )
1899 {
1900 *r = A->p[0] & 1;
1901 return( 0 );
1902 }
1903
1904 /*
1905 * general case
1906 */
1907 for( i = A->n, y = 0; i > 0; i-- )
1908 {
1909 x = A->p[i - 1];
1910 y = ( y << biH ) | ( x >> biH );
1911 z = y / b;
1912 y -= z * b;
1913
1914 x <<= biH;
1915 y = ( y << biH ) | ( x >> biH );
1916 z = y / b;
1917 y -= z * b;
1918 }
1919
1920 /*
1921 * If A is negative, then the current y represents a negative value.
1922 * Flipping it to the positive side.
1923 */
1924 if( A->s < 0 && y != 0 )
1925 y = b - y;
1926
1927 *r = y;
1928
1929 return( 0 );
1930 }
1931
1932 /*
1933 * Fast Montgomery initialization (thanks to Tom St Denis)
1934 */
mpi_montg_init(mbedtls_mpi_uint * mm,const mbedtls_mpi * N)1935 static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
1936 {
1937 mbedtls_mpi_uint x, m0 = N->p[0];
1938 unsigned int i;
1939
1940 x = m0;
1941 x += ( ( m0 + 2 ) & 4 ) << 1;
1942
1943 for( i = biL; i >= 8; i /= 2 )
1944 x *= ( 2 - ( m0 * x ) );
1945
1946 *mm = ~x + 1;
1947 }
1948
1949 /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1950 *
1951 * \param[in,out] A One of the numbers to multiply.
1952 * It must have at least as many limbs as N
1953 * (A->n >= N->n), and any limbs beyond n are ignored.
1954 * On successful completion, A contains the result of
1955 * the multiplication A * B * R^-1 mod N where
1956 * R = (2^ciL)^n.
1957 * \param[in] B One of the numbers to multiply.
1958 * It must be nonzero and must not have more limbs than N
1959 * (B->n <= N->n).
1960 * \param[in] N The modulo. N must be odd.
1961 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1962 * This is -N^-1 mod 2^ciL.
1963 * \param[in,out] T A bignum for temporary storage.
1964 * It must be at least twice the limb size of N plus 2
1965 * (T->n >= 2 * (N->n + 1)).
1966 * Its initial content is unused and
1967 * its final content is indeterminate.
1968 * Note that unlike the usual convention in the library
1969 * for `const mbedtls_mpi*`, the content of T can change.
1970 */
mpi_montmul(mbedtls_mpi * A,const mbedtls_mpi * B,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)1971 static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1972 const mbedtls_mpi *T )
1973 {
1974 size_t i, n, m;
1975 mbedtls_mpi_uint u0, u1, *d;
1976
1977 memset( T->p, 0, T->n * ciL );
1978
1979 d = T->p;
1980 n = N->n;
1981 m = ( B->n < n ) ? B->n : n;
1982
1983 for( i = 0; i < n; i++ )
1984 {
1985 /*
1986 * T = (T + u0*B + u1*N) / 2^biL
1987 */
1988 u0 = A->p[i];
1989 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1990
1991 mpi_mul_hlp( m, B->p, d, u0 );
1992 mpi_mul_hlp( n, N->p, d, u1 );
1993
1994 *d++ = u0; d[n + 1] = 0;
1995 }
1996
1997 /* At this point, d is either the desired result or the desired result
1998 * plus N. We now potentially subtract N, avoiding leaking whether the
1999 * subtraction is performed through side channels. */
2000
2001 /* Copy the n least significant limbs of d to A, so that
2002 * A = d if d < N (recall that N has n limbs). */
2003 memcpy( A->p, d, n * ciL );
2004 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
2005 * do the calculation without using conditional tests. */
2006 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
2007 d[n] += 1;
2008 d[n] -= mpi_sub_hlp( n, d, N->p );
2009 /* If d0 < N then d < (2^biL)^n
2010 * so d[n] == 0 and we want to keep A as it is.
2011 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
2012 * so d[n] == 1 and we want to set A to the result of the subtraction
2013 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
2014 * This exactly corresponds to a conditional assignment. */
2015 mpi_safe_cond_assign( n, A->p, d, (unsigned char) d[n] );
2016 }
2017
2018 /*
2019 * Montgomery reduction: A = A * R^-1 mod N
2020 *
2021 * See mpi_montmul() regarding constraints and guarantees on the parameters.
2022 */
mpi_montred(mbedtls_mpi * A,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)2023 static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
2024 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
2025 {
2026 mbedtls_mpi_uint z = 1;
2027 mbedtls_mpi U;
2028
2029 U.n = U.s = (int) z;
2030 U.p = &z;
2031
2032 mpi_montmul( A, &U, N, mm, T );
2033 }
2034
2035 /*
2036 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
2037 */
mbedtls_mpi_exp_mod(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * E,const mbedtls_mpi * N,mbedtls_mpi * _RR)2038 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
2039 const mbedtls_mpi *E, const mbedtls_mpi *N,
2040 mbedtls_mpi *_RR )
2041 {
2042 int ret;
2043 size_t wbits, wsize, one = 1;
2044 size_t i, j, nblimbs;
2045 size_t bufsize, nbits;
2046 mbedtls_mpi_uint ei, mm, state;
2047 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
2048 int neg;
2049
2050 MPI_VALIDATE_RET( X != NULL );
2051 MPI_VALIDATE_RET( A != NULL );
2052 MPI_VALIDATE_RET( E != NULL );
2053 MPI_VALIDATE_RET( N != NULL );
2054
2055 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
2056 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2057
2058 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
2059 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2060
2061 /*
2062 * Init temps and window size
2063 */
2064 mpi_montg_init( &mm, N );
2065 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
2066 mbedtls_mpi_init( &Apos );
2067 memset( W, 0, sizeof( W ) );
2068
2069 i = mbedtls_mpi_bitlen( E );
2070
2071 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2072 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2073
2074 #if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
2075 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2076 wsize = MBEDTLS_MPI_WINDOW_SIZE;
2077 #endif
2078
2079 j = N->n + 1;
2080 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2081 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2082 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
2083
2084 /*
2085 * Compensate for negative A (and correct at the end)
2086 */
2087 neg = ( A->s == -1 );
2088 if( neg )
2089 {
2090 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
2091 Apos.s = 1;
2092 A = &Apos;
2093 }
2094
2095 /*
2096 * If 1st call, pre-compute R^2 mod N
2097 */
2098 if( _RR == NULL || _RR->p == NULL )
2099 {
2100 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2101 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2102 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
2103
2104 if( _RR != NULL )
2105 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
2106 }
2107 else
2108 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
2109
2110 /*
2111 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2112 */
2113 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
2114 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
2115 else
2116 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
2117
2118 mpi_montmul( &W[1], &RR, N, mm, &T );
2119
2120 /*
2121 * X = R^2 * R^-1 mod N = R mod N
2122 */
2123 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
2124 mpi_montred( X, N, mm, &T );
2125
2126 if( wsize > 1 )
2127 {
2128 /*
2129 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2130 */
2131 j = one << ( wsize - 1 );
2132
2133 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2134 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
2135
2136 for( i = 0; i < wsize - 1; i++ )
2137 mpi_montmul( &W[j], &W[j], N, mm, &T );
2138
2139 /*
2140 * W[i] = W[i - 1] * W[1]
2141 */
2142 for( i = j + 1; i < ( one << wsize ); i++ )
2143 {
2144 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2145 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
2146
2147 mpi_montmul( &W[i], &W[1], N, mm, &T );
2148 }
2149 }
2150
2151 nblimbs = E->n;
2152 bufsize = 0;
2153 nbits = 0;
2154 wbits = 0;
2155 state = 0;
2156
2157 while( 1 )
2158 {
2159 if( bufsize == 0 )
2160 {
2161 if( nblimbs == 0 )
2162 break;
2163
2164 nblimbs--;
2165
2166 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
2167 }
2168
2169 bufsize--;
2170
2171 ei = (E->p[nblimbs] >> bufsize) & 1;
2172
2173 /*
2174 * skip leading 0s
2175 */
2176 if( ei == 0 && state == 0 )
2177 continue;
2178
2179 if( ei == 0 && state == 1 )
2180 {
2181 /*
2182 * out of window, square X
2183 */
2184 mpi_montmul( X, X, N, mm, &T );
2185 continue;
2186 }
2187
2188 /*
2189 * add ei to current window
2190 */
2191 state = 2;
2192
2193 nbits++;
2194 wbits |= ( ei << ( wsize - nbits ) );
2195
2196 if( nbits == wsize )
2197 {
2198 /*
2199 * X = X^wsize R^-1 mod N
2200 */
2201 for( i = 0; i < wsize; i++ )
2202 mpi_montmul( X, X, N, mm, &T );
2203
2204 /*
2205 * X = X * W[wbits] R^-1 mod N
2206 */
2207 mpi_montmul( X, &W[wbits], N, mm, &T );
2208
2209 state--;
2210 nbits = 0;
2211 wbits = 0;
2212 }
2213 }
2214
2215 /*
2216 * process the remaining bits
2217 */
2218 for( i = 0; i < nbits; i++ )
2219 {
2220 mpi_montmul( X, X, N, mm, &T );
2221
2222 wbits <<= 1;
2223
2224 if( ( wbits & ( one << wsize ) ) != 0 )
2225 mpi_montmul( X, &W[1], N, mm, &T );
2226 }
2227
2228 /*
2229 * X = A^E * R * R^-1 mod N = A^E mod N
2230 */
2231 mpi_montred( X, N, mm, &T );
2232
2233 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
2234 {
2235 X->s = -1;
2236 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
2237 }
2238
2239 cleanup:
2240
2241 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
2242 mbedtls_mpi_free( &W[i] );
2243
2244 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
2245
2246 if( _RR == NULL || _RR->p == NULL )
2247 mbedtls_mpi_free( &RR );
2248
2249 return( ret );
2250 }
2251
2252 /*
2253 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2254 */
mbedtls_mpi_gcd(mbedtls_mpi * G,const mbedtls_mpi * A,const mbedtls_mpi * B)2255 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
2256 {
2257 int ret;
2258 size_t lz, lzt;
2259 mbedtls_mpi TG, TA, TB;
2260
2261 MPI_VALIDATE_RET( G != NULL );
2262 MPI_VALIDATE_RET( A != NULL );
2263 MPI_VALIDATE_RET( B != NULL );
2264
2265 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
2266
2267 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2268 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
2269
2270 lz = mbedtls_mpi_lsb( &TA );
2271 lzt = mbedtls_mpi_lsb( &TB );
2272
2273 if( lzt < lz )
2274 lz = lzt;
2275
2276 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2277 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
2278
2279 TA.s = TB.s = 1;
2280
2281 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
2282 {
2283 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2284 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
2285
2286 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
2287 {
2288 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2289 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
2290 }
2291 else
2292 {
2293 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2294 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
2295 }
2296 }
2297
2298 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2299 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
2300
2301 cleanup:
2302
2303 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
2304
2305 return( ret );
2306 }
2307
2308 /*
2309 * Fill X with size bytes of random.
2310 *
2311 * Use a temporary bytes representation to make sure the result is the same
2312 * regardless of the platform endianness (useful when f_rng is actually
2313 * deterministic, eg for tests).
2314 */
mbedtls_mpi_fill_random(mbedtls_mpi * X,size_t size,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2315 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
2316 int (*f_rng)(void *, unsigned char *, size_t),
2317 void *p_rng )
2318 {
2319 int ret;
2320 size_t const limbs = CHARS_TO_LIMBS( size );
2321 size_t const overhead = ( limbs * ciL ) - size;
2322 unsigned char *Xp;
2323
2324 MPI_VALIDATE_RET( X != NULL );
2325 MPI_VALIDATE_RET( f_rng != NULL );
2326
2327 /* Ensure that target MPI has exactly the necessary number of limbs */
2328 if( X->n != limbs )
2329 {
2330 mbedtls_mpi_free( X );
2331 mbedtls_mpi_init( X );
2332 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
2333 }
2334 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
2335
2336 Xp = (unsigned char*) X->p;
2337 f_rng( p_rng, Xp + overhead, size );
2338
2339 mpi_bigendian_to_host( X->p, limbs );
2340
2341 cleanup:
2342 return( ret );
2343 }
2344
2345 /*
2346 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2347 */
mbedtls_mpi_inv_mod(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * N)2348 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
2349 {
2350 int ret;
2351 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
2352 MPI_VALIDATE_RET( X != NULL );
2353 MPI_VALIDATE_RET( A != NULL );
2354 MPI_VALIDATE_RET( N != NULL );
2355
2356 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
2357 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2358
2359 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2360 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2361 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
2362
2363 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
2364
2365 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
2366 {
2367 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2368 goto cleanup;
2369 }
2370
2371 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2372 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2373 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2374 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
2375
2376 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2377 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2378 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2379 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
2380
2381 do
2382 {
2383 while( ( TU.p[0] & 1 ) == 0 )
2384 {
2385 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
2386
2387 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2388 {
2389 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2390 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
2391 }
2392
2393 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2394 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
2395 }
2396
2397 while( ( TV.p[0] & 1 ) == 0 )
2398 {
2399 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
2400
2401 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2402 {
2403 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2404 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
2405 }
2406
2407 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2408 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
2409 }
2410
2411 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
2412 {
2413 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2414 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2415 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
2416 }
2417 else
2418 {
2419 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2420 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2421 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
2422 }
2423 }
2424 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
2425
2426 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2427 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
2428
2429 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2430 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
2431
2432 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
2433
2434 cleanup:
2435
2436 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2437 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2438 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
2439
2440 return( ret );
2441 }
2442
2443 #if defined(MBEDTLS_GENPRIME)
2444
2445 static const int small_prime[] =
2446 {
2447 3, 5, 7, 11, 13, 17, 19, 23,
2448 29, 31, 37, 41, 43, 47, 53, 59,
2449 61, 67, 71, 73, 79, 83, 89, 97,
2450 101, 103, 107, 109, 113, 127, 131, 137,
2451 139, 149, 151, 157, 163, 167, 173, 179,
2452 181, 191, 193, 197, 199, 211, 223, 227,
2453 229, 233, 239, 241, 251, 257, 263, 269,
2454 271, 277, 281, 283, 293, 307, 311, 313,
2455 317, 331, 337, 347, 349, 353, 359, 367,
2456 373, 379, 383, 389, 397, 401, 409, 419,
2457 421, 431, 433, 439, 443, 449, 457, 461,
2458 463, 467, 479, 487, 491, 499, 503, 509,
2459 521, 523, 541, 547, 557, 563, 569, 571,
2460 577, 587, 593, 599, 601, 607, 613, 617,
2461 619, 631, 641, 643, 647, 653, 659, 661,
2462 673, 677, 683, 691, 701, 709, 719, 727,
2463 733, 739, 743, 751, 757, 761, 769, 773,
2464 787, 797, 809, 811, 821, 823, 827, 829,
2465 839, 853, 857, 859, 863, 877, 881, 883,
2466 887, 907, 911, 919, 929, 937, 941, 947,
2467 953, 967, 971, 977, 983, 991, 997, -103
2468 };
2469
2470 /*
2471 * Small divisors test (X must be positive)
2472 *
2473 * Return values:
2474 * 0: no small factor (possible prime, more tests needed)
2475 * 1: certain prime
2476 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2477 * other negative: error
2478 */
mpi_check_small_factors(const mbedtls_mpi * X)2479 static int mpi_check_small_factors( const mbedtls_mpi *X )
2480 {
2481 int ret = 0;
2482 size_t i;
2483 mbedtls_mpi_uint r;
2484
2485 if( ( X->p[0] & 1 ) == 0 )
2486 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2487
2488 for( i = 0; small_prime[i] > 0; i++ )
2489 {
2490 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
2491 return( 1 );
2492
2493 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
2494
2495 if( r == 0 )
2496 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2497 }
2498
2499 cleanup:
2500 return( ret );
2501 }
2502
2503 /*
2504 * Miller-Rabin pseudo-primality test (HAC 4.24)
2505 */
mpi_miller_rabin(const mbedtls_mpi * X,size_t rounds,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2506 static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
2507 int (*f_rng)(void *, unsigned char *, size_t),
2508 void *p_rng )
2509 {
2510 int ret, count;
2511 size_t i, j, k, s;
2512 mbedtls_mpi W, R, T, A, RR;
2513
2514 MPI_VALIDATE_RET( X != NULL );
2515 MPI_VALIDATE_RET( f_rng != NULL );
2516
2517 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2518 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2519 mbedtls_mpi_init( &RR );
2520
2521 /*
2522 * W = |X| - 1
2523 * R = W >> lsb( W )
2524 */
2525 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2526 s = mbedtls_mpi_lsb( &W );
2527 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2528 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
2529
2530 for( i = 0; i < rounds; i++ )
2531 {
2532 /*
2533 * pick a random A, 1 < A < |X| - 1
2534 */
2535 count = 0;
2536 do {
2537 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2538
2539 j = mbedtls_mpi_bitlen( &A );
2540 k = mbedtls_mpi_bitlen( &W );
2541 if (j > k) {
2542 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
2543 }
2544
2545 if (count++ > 30) {
2546 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2547 goto cleanup;
2548 }
2549
2550 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2551 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
2552
2553 /*
2554 * A = A^R mod |X|
2555 */
2556 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
2557
2558 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2559 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2560 continue;
2561
2562 j = 1;
2563 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
2564 {
2565 /*
2566 * A = A * A mod |X|
2567 */
2568 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2569 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
2570
2571 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2572 break;
2573
2574 j++;
2575 }
2576
2577 /*
2578 * not prime if A != |X| - 1 or A == 1
2579 */
2580 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2581 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2582 {
2583 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2584 break;
2585 }
2586 }
2587
2588 cleanup:
2589 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2590 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2591 mbedtls_mpi_free( &RR );
2592
2593 return( ret );
2594 }
2595
2596 /*
2597 * Pseudo-primality test: small factors, then Miller-Rabin
2598 */
mbedtls_mpi_is_prime_ext(const mbedtls_mpi * X,int rounds,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2599 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2600 int (*f_rng)(void *, unsigned char *, size_t),
2601 void *p_rng )
2602 {
2603 int ret;
2604 mbedtls_mpi XX;
2605 MPI_VALIDATE_RET( X != NULL );
2606 MPI_VALIDATE_RET( f_rng != NULL );
2607
2608 XX.s = 1;
2609 XX.n = X->n;
2610 XX.p = X->p;
2611
2612 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2613 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2614 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2615
2616 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
2617 return( 0 );
2618
2619 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2620 {
2621 if( ret == 1 )
2622 return( 0 );
2623
2624 return( ret );
2625 }
2626
2627 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
2628 }
2629
2630 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
2631 /*
2632 * Pseudo-primality test, error probability 2^-80
2633 */
mbedtls_mpi_is_prime(const mbedtls_mpi * X,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2634 int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2635 int (*f_rng)(void *, unsigned char *, size_t),
2636 void *p_rng )
2637 {
2638 MPI_VALIDATE_RET( X != NULL );
2639 MPI_VALIDATE_RET( f_rng != NULL );
2640
2641 /*
2642 * In the past our key generation aimed for an error rate of at most
2643 * 2^-80. Since this function is deprecated, aim for the same certainty
2644 * here as well.
2645 */
2646 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
2647 }
2648 #endif
2649
2650 /*
2651 * Prime number generation
2652 *
2653 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2654 * be either 1024 bits or 1536 bits long, and flags must contain
2655 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2656 */
mbedtls_mpi_gen_prime(mbedtls_mpi * X,size_t nbits,int flags,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2657 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
2658 int (*f_rng)(void *, unsigned char *, size_t),
2659 void *p_rng )
2660 {
2661 #ifdef MBEDTLS_HAVE_INT64
2662 // ceil(2^63.5)
2663 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2664 #else
2665 // ceil(2^31.5)
2666 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2667 #endif
2668 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2669 size_t k, n;
2670 int rounds;
2671 mbedtls_mpi_uint r;
2672 mbedtls_mpi Y;
2673
2674 MPI_VALIDATE_RET( X != NULL );
2675 MPI_VALIDATE_RET( f_rng != NULL );
2676
2677 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2678 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2679
2680 mbedtls_mpi_init( &Y );
2681
2682 n = BITS_TO_LIMBS( nbits );
2683
2684 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2685 {
2686 /*
2687 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2688 */
2689 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2690 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2691 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2692 }
2693 else
2694 {
2695 /*
2696 * 2^-100 error probability, number of rounds computed based on HAC,
2697 * fact 4.48
2698 */
2699 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2700 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2701 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2702 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2703 }
2704
2705 while( 1 )
2706 {
2707 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2708 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2709 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2710
2711 k = n * biL;
2712 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2713 X->p[0] |= 1;
2714
2715 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
2716 {
2717 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
2718
2719 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2720 goto cleanup;
2721 }
2722 else
2723 {
2724 /*
2725 * An necessary condition for Y and X = 2Y + 1 to be prime
2726 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2727 * Make sure it is satisfied, while keeping X = 3 mod 4
2728 */
2729
2730 X->p[0] |= 2;
2731
2732 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2733 if( r == 0 )
2734 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2735 else if( r == 1 )
2736 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2737
2738 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2739 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2740 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2741
2742 while( 1 )
2743 {
2744 /*
2745 * First, check small factors for X and Y
2746 * before doing Miller-Rabin on any of them
2747 */
2748 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2749 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2750 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
2751 == 0 &&
2752 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
2753 == 0 )
2754 goto cleanup;
2755
2756 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2757 goto cleanup;
2758
2759 /*
2760 * Next candidates. We want to preserve Y = (X-1) / 2 and
2761 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2762 * so up Y by 6 and X by 12.
2763 */
2764 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2765 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
2766 }
2767 }
2768 }
2769
2770 cleanup:
2771
2772 mbedtls_mpi_free( &Y );
2773
2774 return( ret );
2775 }
2776
2777 #endif /* MBEDTLS_GENPRIME */
2778
2779 #if defined(MBEDTLS_SELF_TEST)
2780
2781 #define GCD_PAIR_COUNT 3
2782
2783 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2784 {
2785 { 693, 609, 21 },
2786 { 1764, 868, 28 },
2787 { 768454923, 542167814, 1 }
2788 };
2789
2790 /*
2791 * Checkup routine
2792 */
mbedtls_mpi_self_test(int verbose)2793 int mbedtls_mpi_self_test( int verbose )
2794 {
2795 int ret, i;
2796 mbedtls_mpi A, E, N, X, Y, U, V;
2797
2798 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2799 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
2800
2801 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
2802 "EFE021C2645FD1DC586E69184AF4A31E" \
2803 "D5F53E93B5F123FA41680867BA110131" \
2804 "944FE7952E2517337780CB0DB80E61AA" \
2805 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2806
2807 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
2808 "B2E7EFD37075B9F03FF989C7C5051C20" \
2809 "34D2A323810251127E7BF8625A4F49A5" \
2810 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2811 "5B5C25763222FEFCCFC38B832366C29E" ) );
2812
2813 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
2814 "0066A198186C18C10B2F5ED9B522752A" \
2815 "9830B69916E535C8F047518A889A43A5" \
2816 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2817
2818 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
2819
2820 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2821 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2822 "9E857EA95A03512E2BAE7391688D264A" \
2823 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2824 "8001B72E848A38CAE1C65F78E56ABDEF" \
2825 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2826 "ECF677152EF804370C1A305CAF3B5BF1" \
2827 "30879B56C61DE584A0F53A2447A51E" ) );
2828
2829 if( verbose != 0 )
2830 mbedtls_printf( " MPI test #1 (mul_mpi): " );
2831
2832 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2833 {
2834 if( verbose != 0 )
2835 mbedtls_printf( "failed\n" );
2836
2837 ret = 1;
2838 goto cleanup;
2839 }
2840
2841 if( verbose != 0 )
2842 mbedtls_printf( "passed\n" );
2843
2844 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
2845
2846 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2847 "256567336059E52CAE22925474705F39A94" ) );
2848
2849 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
2850 "6613F26162223DF488E9CD48CC132C7A" \
2851 "0AC93C701B001B092E4E5B9F73BCD27B" \
2852 "9EE50D0657C77F374E903CDFA4C642" ) );
2853
2854 if( verbose != 0 )
2855 mbedtls_printf( " MPI test #2 (div_mpi): " );
2856
2857 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2858 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
2859 {
2860 if( verbose != 0 )
2861 mbedtls_printf( "failed\n" );
2862
2863 ret = 1;
2864 goto cleanup;
2865 }
2866
2867 if( verbose != 0 )
2868 mbedtls_printf( "passed\n" );
2869
2870 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
2871
2872 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2873 "36E139AEA55215609D2816998ED020BB" \
2874 "BD96C37890F65171D948E9BC7CBAA4D9" \
2875 "325D24D6A3C12710F10A09FA08AB87" ) );
2876
2877 if( verbose != 0 )
2878 mbedtls_printf( " MPI test #3 (exp_mod): " );
2879
2880 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2881 {
2882 if( verbose != 0 )
2883 mbedtls_printf( "failed\n" );
2884
2885 ret = 1;
2886 goto cleanup;
2887 }
2888
2889 if( verbose != 0 )
2890 mbedtls_printf( "passed\n" );
2891
2892 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
2893
2894 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2895 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2896 "C3DBA76456363A10869622EAC2DD84EC" \
2897 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2898
2899 if( verbose != 0 )
2900 mbedtls_printf( " MPI test #4 (inv_mod): " );
2901
2902 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2903 {
2904 if( verbose != 0 )
2905 mbedtls_printf( "failed\n" );
2906
2907 ret = 1;
2908 goto cleanup;
2909 }
2910
2911 if( verbose != 0 )
2912 mbedtls_printf( "passed\n" );
2913
2914 if( verbose != 0 )
2915 mbedtls_printf( " MPI test #5 (simple gcd): " );
2916
2917 for( i = 0; i < GCD_PAIR_COUNT; i++ )
2918 {
2919 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2920 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
2921
2922 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
2923
2924 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
2925 {
2926 if( verbose != 0 )
2927 mbedtls_printf( "failed at %d\n", i );
2928
2929 ret = 1;
2930 goto cleanup;
2931 }
2932 }
2933
2934 if( verbose != 0 )
2935 mbedtls_printf( "passed\n" );
2936
2937 cleanup:
2938
2939 if( ret != 0 && verbose != 0 )
2940 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
2941
2942 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2943 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
2944
2945 if( verbose != 0 )
2946 mbedtls_printf( "\n" );
2947
2948 return( ret );
2949 }
2950
2951 #endif /* MBEDTLS_SELF_TEST */
2952
2953 #endif /* MBEDTLS_BIGNUM_C */
2954