source: azure_iot_hub_mbedtls/trunk/mbedtls-2.16.1/library/bignum.c@ 398

Last change on this file since 398 was 398, checked in by coas-nagasima, 5 years ago

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