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