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