API tools faq
paste
dipto181

bignum.c

dipto181
Sep 18th, 2020
107
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 46.63 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * Multi-precision integer library
  3. *
  4. * Copyright (C) 2006-2010, Brainspark B.V.
  5. *
  6. * This file is part of PolarSSL (http://www.polarssl.org)
  7. * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
  8. *
  9. * All rights reserved.
  10. *
  11. * This program is free software; you can redistribute it and/or modify
  12. * it under the terms of the GNU General Public License as published by
  13. * the Free Software Foundation; either version 2 of the License, or
  14. * (at your option) any later version.
  15. *
  16. * This program is distributed in the hope that it will be useful,
  17. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  19. * GNU General Public License for more details.
  20. *
  21. * You should have received a copy of the GNU General Public License along
  22. * with this program; if not, write to the Free Software Foundation, Inc.,
  23. * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  24. */
  25. /*
  26. * This MPI implementation is based on:
  27. *
  28. * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
  29. * http://www.stillhq.com/extracted/gnupg-api/mpi/
  30. * http://math.libtomcrypt.com/files/tommath.pdf
  31. */
  32.  
  33. #include "config.h"
  34.  
  35. #if defined(POLARSSL_BIGNUM_C)
  36.  
  37. #include "bignum.h"
  38. #include "bn_mul.h"
  39. #include "memory.h"
  40.  
  41. //#include <stdlib.h>
  42. #include <linux/string.h>
  43.  
  44. #define ciL (sizeof(t_uint)) /* chars in limb */
  45. #define biL (ciL << 3) /* bits in limb */
  46. #define biH (ciL << 2) /* half limb size */
  47.  
  48. /*
  49. * Convert between bits/chars and number of limbs
  50. */
  51. #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
  52. #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
  53.  
  54. /*
  55. * Initialize one MPI
  56. */
  57. void mpi_init( mpi *X )
  58. {
  59. if( X == NULL )
  60. return;
  61.  
  62. X->s = 1;
  63. X->n = 0;
  64. X->p = NULL;
  65. }
  66.  
  67. /*
  68. * Unallocate one MPI
  69. */
  70. void mpi_free( mpi *X )
  71. {
  72. if( X == NULL )
  73. return;
  74.  
  75. if( X->p != NULL )
  76. {
  77. //memset( X->p, 0, X->n * ciL );
  78. //free( X->p );
  79. memset1( X->p, 0, X->n * ciL );
  80. polarssl_free( X->p );
  81. }
  82.  
  83. X->s = 1;
  84. X->n = 0;
  85. X->p = NULL;
  86. }
  87.  
  88. /*
  89. * Enlarge to the specified number of limbs
  90. */
  91.  
  92. /*
  93. int mpi_grow( mpi *X, size_t nblimbs )
  94. {
  95. t_uint *p;
  96.  
  97. if( nblimbs > POLARSSL_MPI_MAX_LIMBS )
  98. return( POLARSSL_ERR_MPI_MALLOC_FAILED );
  99.  
  100. if( X->n < nblimbs )
  101. {
  102. if( ( p = (t_uint *) malloc( nblimbs * ciL ) ) == NULL )
  103. return( POLARSSL_ERR_MPI_MALLOC_FAILED );
  104.  
  105. memset( p, 0, nblimbs * ciL );
  106.  
  107. if( X->p != NULL )
  108. {
  109. memcpy( p, X->p, X->n * ciL );
  110. memset( X->p, 0, X->n * ciL );
  111. free( X->p );
  112. }
  113.  
  114. X->n = nblimbs;
  115. X->p = p;
  116. }
  117.  
  118. return( 0 );
  119. }
  120. */
  121. int mpi_grow( mpi *X, size_t nblimbs )
  122. {
  123. t_uint *p;
  124.  
  125. if( nblimbs > POLARSSL_MPI_MAX_LIMBS )
  126. return( POLARSSL_ERR_MPI_MALLOC_FAILED );
  127.  
  128. if( X->n < nblimbs )
  129. {
  130. if( ( p = (t_uint *) polarssl_malloc( nblimbs * ciL ) ) == NULL )
  131. return( POLARSSL_ERR_MPI_MALLOC_FAILED );
  132.  
  133. memset1( p, 0, nblimbs * ciL );
  134.  
  135. if( X->p != NULL )
  136. {
  137. memcpy1( p, X->p, X->n * ciL );
  138. memset1( X->p, 0, X->n * ciL );
  139. polarssl_free( X->p );
  140. }
  141.  
  142. X->n = nblimbs;
  143. X->p = p;
  144. }
  145.  
  146. return( 0 );
  147. }
  148.  
  149.  
  150.  
  151. /*
  152. * Copy the contents of Y into X
  153. */
  154. int mpi_copy( mpi *X, const mpi *Y )
  155. {
  156. int ret;
  157. size_t i;
  158.  
  159. if( X == Y )
  160. return( 0 );
  161.  
  162. for( i = Y->n - 1; i > 0; i-- )
  163. if( Y->p[i] != 0 )
  164. break;
  165. i++;
  166.  
  167. X->s = Y->s;
  168.  
  169. MPI_CHK( mpi_grow( X, i ) );
  170.  
  171. memset( X->p, 0, X->n * ciL );
  172. memcpy( X->p, Y->p, i * ciL );
  173.  
  174. cleanup:
  175.  
  176. return( ret );
  177. }
  178.  
  179. /*
  180. * Swap the contents of X and Y
  181. */
  182. void mpi_swap( mpi *X, mpi *Y )
  183. {
  184. mpi T;
  185.  
  186. memcpy( &T, X, sizeof( mpi ) );
  187. memcpy( X, Y, sizeof( mpi ) );
  188. memcpy( Y, &T, sizeof( mpi ) );
  189. }
  190.  
  191. /*
  192. * Set value from integer
  193. */
  194. int mpi_lset( mpi *X, t_sint z )
  195. {
  196. int ret;
  197.  
  198. MPI_CHK( mpi_grow( X, 1 ) );
  199. memset( X->p, 0, X->n * ciL );
  200.  
  201. X->p[0] = ( z < 0 ) ? -z : z;
  202. X->s = ( z < 0 ) ? -1 : 1;
  203.  
  204. cleanup:
  205.  
  206. return( ret );
  207. }
  208.  
  209. /*
  210. * Get a specific bit
  211. */
  212. int mpi_get_bit( const mpi *X, size_t pos )
  213. {
  214. if( X->n * biL <= pos )
  215. return( 0 );
  216.  
  217. return ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01;
  218. }
  219.  
  220. /*
  221. * Set a bit to a specific value of 0 or 1
  222. */
  223. int mpi_set_bit( mpi *X, size_t pos, unsigned char val )
  224. {
  225. int ret = 0;
  226. size_t off = pos / biL;
  227. size_t idx = pos % biL;
  228.  
  229. if( val != 0 && val != 1 )
  230. return POLARSSL_ERR_MPI_BAD_INPUT_DATA;
  231.  
  232. if( X->n * biL <= pos )
  233. {
  234. if( val == 0 )
  235. return ( 0 );
  236.  
  237. MPI_CHK( mpi_grow( X, off + 1 ) );
  238. }
  239.  
  240. X->p[off] = ( X->p[off] & ~( 0x01 << idx ) ) | ( val << idx );
  241.  
  242. cleanup:
  243.  
  244. return( ret );
  245. }
  246.  
  247. /*
  248. * Return the number of least significant bits
  249. */
  250. size_t mpi_lsb( const mpi *X )
  251. {
  252. size_t i, j, count = 0;
  253.  
  254. for( i = 0; i < X->n; i++ )
  255. for( j = 0; j < biL; j++, count++ )
  256. if( ( ( X->p[i] >> j ) & 1 ) != 0 )
  257. return( count );
  258.  
  259. return( 0 );
  260. }
  261.  
  262. /*
  263. * Return the number of most significant bits
  264. */
  265. size_t mpi_msb( const mpi *X )
  266. {
  267. size_t i, j;
  268.  
  269. for( i = X->n - 1; i > 0; i-- )
  270. if( X->p[i] != 0 )
  271. break;
  272.  
  273. for( j = biL; j > 0; j-- )
  274. if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
  275. break;
  276.  
  277. return( ( i * biL ) + j );
  278. }
  279.  
  280. /*
  281. * Return the total size in bytes
  282. */
  283. size_t mpi_size( const mpi *X )
  284. {
  285. return( ( mpi_msb( X ) + 7 ) >> 3 );
  286. }
  287.  
  288. /*
  289. * Convert an ASCII character to digit value
  290. */
  291. static int mpi_get_digit( t_uint *d, int radix, char c )
  292. {
  293. *d = 255;
  294.  
  295. if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
  296. if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
  297. if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
  298.  
  299. if( *d >= (t_uint) radix )
  300. return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
  301.  
  302. return( 0 );
  303. }
  304.  
  305. /*
  306. * Import from an ASCII string
  307. */
  308. int mpi_read_string( mpi *X, int radix, const char *s )
  309. {
  310. int ret;
  311. size_t i, j, slen, n;
  312. t_uint d;
  313. mpi T;
  314.  
  315. if( radix < 2 || radix > 16 )
  316. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  317.  
  318. mpi_init( &T );
  319.  
  320. slen = strlen( s );
  321.  
  322. if( radix == 16 )
  323. {
  324. n = BITS_TO_LIMBS( slen << 2 );
  325.  
  326. MPI_CHK( mpi_grow( X, n ) );
  327. MPI_CHK( mpi_lset( X, 0 ) );
  328.  
  329. for( i = slen, j = 0; i > 0; i--, j++ )
  330. {
  331. if( i == 1 && s[i - 1] == '-' )
  332. {
  333. X->s = -1;
  334. break;
  335. }
  336.  
  337. MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
  338. X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
  339. }
  340. }
  341. else
  342. {
  343. MPI_CHK( mpi_lset( X, 0 ) );
  344.  
  345. for( i = 0; i < slen; i++ )
  346. {
  347. if( i == 0 && s[i] == '-' )
  348. {
  349. X->s = -1;
  350. continue;
  351. }
  352.  
  353. MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
  354. MPI_CHK( mpi_mul_int( &T, X, radix ) );
  355.  
  356. if( X->s == 1 )
  357. {
  358. MPI_CHK( mpi_add_int( X, &T, d ) );
  359. }
  360. else
  361. {
  362. MPI_CHK( mpi_sub_int( X, &T, d ) );
  363. }
  364. }
  365. }
  366.  
  367. cleanup:
  368.  
  369. mpi_free( &T );
  370.  
  371. return( ret );
  372. }
  373.  
  374. /*
  375. * Helper to write the digits high-order first
  376. */
  377. static int mpi_write_hlp( mpi *X, int radix, char **p )
  378. {
  379. int ret;
  380. t_uint r;
  381.  
  382. if( radix < 2 || radix > 16 )
  383. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  384.  
  385. MPI_CHK( mpi_mod_int( &r, X, radix ) );
  386. MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
  387.  
  388. if( mpi_cmp_int( X, 0 ) != 0 )
  389. MPI_CHK( mpi_write_hlp( X, radix, p ) );
  390.  
  391. if( r < 10 )
  392. *(*p)++ = (char)( r + 0x30 );
  393. else
  394. *(*p)++ = (char)( r + 0x37 );
  395.  
  396. cleanup:
  397.  
  398. return( ret );
  399. }
  400.  
  401. /*
  402. * Export into an ASCII string
  403. */
  404. int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen )
  405. {
  406. int ret = 0;
  407. size_t n;
  408. char *p;
  409. mpi T;
  410.  
  411. if( radix < 2 || radix > 16 )
  412. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  413.  
  414. n = mpi_msb( X );
  415. if( radix >= 4 ) n >>= 1;
  416. if( radix >= 16 ) n >>= 1;
  417. n += 3;
  418.  
  419. if( *slen < n )
  420. {
  421. *slen = n;
  422. return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
  423. }
  424.  
  425. p = s;
  426. mpi_init( &T );
  427.  
  428. if( X->s == -1 )
  429. *p++ = '-';
  430.  
  431. if( radix == 16 )
  432. {
  433. int c;
  434. size_t i, j, k;
  435.  
  436. for( i = X->n, k = 0; i > 0; i-- )
  437. {
  438. for( j = ciL; j > 0; j-- )
  439. {
  440. c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
  441.  
  442. if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
  443. continue;
  444.  
  445. *(p++) = "0123456789ABCDEF" [c / 16];
  446. *(p++) = "0123456789ABCDEF" [c % 16];
  447. k = 1;
  448. }
  449. }
  450. }
  451. else
  452. {
  453. MPI_CHK( mpi_copy( &T, X ) );
  454.  
  455. if( T.s == -1 )
  456. T.s = 1;
  457.  
  458. MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
  459. }
  460.  
  461. *p++ = '\0';
  462. *slen = p - s;
  463.  
  464. cleanup:
  465.  
  466. mpi_free( &T );
  467.  
  468. return( ret );
  469. }
  470.  
  471. #if defined(POLARSSL_FS_IO)
  472. /*
  473. * Read X from an opened file
  474. */
  475. int mpi_read_file( mpi *X, int radix, FILE *fin )
  476. {
  477. t_uint d;
  478. size_t slen;
  479. char *p;
  480. /*
  481. * Buffer should have space for (short) label and decimal formatted MPI,
  482. * newline characters and '\0'
  483. */
  484. char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
  485.  
  486. memset( s, 0, sizeof( s ) );
  487. if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
  488. return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
  489.  
  490. slen = strlen( s );
  491. if( slen == sizeof( s ) - 2 )
  492. return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
  493.  
  494. if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
  495. if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
  496.  
  497. p = s + slen;
  498. while( --p >= s )
  499. if( mpi_get_digit( &d, radix, *p ) != 0 )
  500. break;
  501.  
  502. return( mpi_read_string( X, radix, p + 1 ) );
  503. }
  504.  
  505. /*
  506. * Write X into an opened file (or stdout if fout == NULL)
  507. */
  508. int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout )
  509. {
  510. int ret;
  511. size_t n, slen, plen;
  512. /*
  513. * Buffer should have space for (short) label and decimal formatted MPI,
  514. * newline characters and '\0'
  515. */
  516. char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
  517.  
  518. n = sizeof( s );
  519. memset( s, 0, n );
  520. n -= 2;
  521.  
  522. MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &n ) );
  523.  
  524. if( p == NULL ) p = "";
  525.  
  526. plen = strlen( p );
  527. slen = strlen( s );
  528. s[slen++] = '\r';
  529. s[slen++] = '\n';
  530.  
  531. if( fout != NULL )
  532. {
  533. if( fwrite( p, 1, plen, fout ) != plen ||
  534. fwrite( s, 1, slen, fout ) != slen )
  535. return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
  536. }
  537. else
  538. printf( "%s%s", p, s );
  539.  
  540. cleanup:
  541.  
  542. return( ret );
  543. }
  544. #endif /* POLARSSL_FS_IO */
  545.  
  546. /*
  547. * Import X from unsigned binary data, big endian
  548. */
  549. int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen )
  550. {
  551. int ret;
  552. size_t i, j, n;
  553.  
  554. for( n = 0; n < buflen; n++ )
  555. if( buf[n] != 0 )
  556. break;
  557.  
  558. MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
  559. MPI_CHK( mpi_lset( X, 0 ) );
  560.  
  561. for( i = buflen, j = 0; i > n; i--, j++ )
  562. X->p[j / ciL] |= ((t_uint) buf[i - 1]) << ((j % ciL) << 3);
  563.  
  564. cleanup:
  565.  
  566. return( ret );
  567. }
  568.  
  569. /*
  570. * Export X into unsigned binary data, big endian
  571. */
  572. int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen )
  573. {
  574. size_t i, j, n;
  575.  
  576. n = mpi_size( X );
  577.  
  578. if( buflen < n )
  579. return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
  580.  
  581. memset( buf, 0, buflen );
  582.  
  583. for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
  584. buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
  585.  
  586. return( 0 );
  587. }
  588.  
  589. /*
  590. * Left-shift: X <<= count
  591. */
  592. int mpi_shift_l( mpi *X, size_t count )
  593. {
  594. int ret;
  595. size_t i, v0, t1;
  596. t_uint r0 = 0, r1;
  597.  
  598. v0 = count / (biL );
  599. t1 = count & (biL - 1);
  600.  
  601. i = mpi_msb( X ) + count;
  602.  
  603. if( X->n * biL < i )
  604. MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
  605.  
  606. ret = 0;
  607.  
  608. /*
  609. * shift by count / limb_size
  610. */
  611. if( v0 > 0 )
  612. {
  613. for( i = X->n; i > v0; i-- )
  614. X->p[i - 1] = X->p[i - v0 - 1];
  615.  
  616. for( ; i > 0; i-- )
  617. X->p[i - 1] = 0;
  618. }
  619.  
  620. /*
  621. * shift by count % limb_size
  622. */
  623. if( t1 > 0 )
  624. {
  625. for( i = v0; i < X->n; i++ )
  626. {
  627. r1 = X->p[i] >> (biL - t1);
  628. X->p[i] <<= t1;
  629. X->p[i] |= r0;
  630. r0 = r1;
  631. }
  632. }
  633.  
  634. cleanup:
  635.  
  636. return( ret );
  637. }
  638.  
  639. /*
  640. * Right-shift: X >>= count
  641. */
  642. int mpi_shift_r( mpi *X, size_t count )
  643. {
  644. size_t i, v0, v1;
  645. t_uint r0 = 0, r1;
  646.  
  647. v0 = count / biL;
  648. v1 = count & (biL - 1);
  649.  
  650. if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
  651. return mpi_lset( X, 0 );
  652.  
  653. /*
  654. * shift by count / limb_size
  655. */
  656. if( v0 > 0 )
  657. {
  658. for( i = 0; i < X->n - v0; i++ )
  659. X->p[i] = X->p[i + v0];
  660.  
  661. for( ; i < X->n; i++ )
  662. X->p[i] = 0;
  663. }
  664.  
  665. /*
  666. * shift by count % limb_size
  667. */
  668. if( v1 > 0 )
  669. {
  670. for( i = X->n; i > 0; i-- )
  671. {
  672. r1 = X->p[i - 1] << (biL - v1);
  673. X->p[i - 1] >>= v1;
  674. X->p[i - 1] |= r0;
  675. r0 = r1;
  676. }
  677. }
  678.  
  679. return( 0 );
  680. }
  681.  
  682. /*
  683. * Compare unsigned values
  684. */
  685. int mpi_cmp_abs( const mpi *X, const mpi *Y )
  686. {
  687. size_t i, j;
  688.  
  689. for( i = X->n; i > 0; i-- )
  690. if( X->p[i - 1] != 0 )
  691. break;
  692.  
  693. for( j = Y->n; j > 0; j-- )
  694. if( Y->p[j - 1] != 0 )
  695. break;
  696.  
  697. if( i == 0 && j == 0 )
  698. return( 0 );
  699.  
  700. if( i > j ) return( 1 );
  701. if( j > i ) return( -1 );
  702.  
  703. for( ; i > 0; i-- )
  704. {
  705. if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
  706. if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
  707. }
  708.  
  709. return( 0 );
  710. }
  711.  
  712. /*
  713. * Compare signed values
  714. */
  715. int mpi_cmp_mpi( const mpi *X, const mpi *Y )
  716. {
  717. size_t i, j;
  718.  
  719. for( i = X->n; i > 0; i-- )
  720. if( X->p[i - 1] != 0 )
  721. break;
  722.  
  723. for( j = Y->n; j > 0; j-- )
  724. if( Y->p[j - 1] != 0 )
  725. break;
  726.  
  727. if( i == 0 && j == 0 )
  728. return( 0 );
  729.  
  730. if( i > j ) return( X->s );
  731. if( j > i ) return( -Y->s );
  732.  
  733. if( X->s > 0 && Y->s < 0 ) return( 1 );
  734. if( Y->s > 0 && X->s < 0 ) return( -1 );
  735.  
  736. for( ; i > 0; i-- )
  737. {
  738. if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
  739. if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
  740. }
  741.  
  742. return( 0 );
  743. }
  744.  
  745. /*
  746. * Compare signed values
  747. */
  748. int mpi_cmp_int( const mpi *X, t_sint z )
  749. {
  750. mpi Y;
  751. t_uint p[1];
  752.  
  753. *p = ( z < 0 ) ? -z : z;
  754. Y.s = ( z < 0 ) ? -1 : 1;
  755. Y.n = 1;
  756. Y.p = p;
  757.  
  758. return( mpi_cmp_mpi( X, &Y ) );
  759. }
  760.  
  761. /*
  762. * Unsigned addition: X = |A| + |B| (HAC 14.7)
  763. */
  764. int mpi_add_abs( mpi *X, const mpi *A, const mpi *B )
  765. {
  766. int ret;
  767. size_t i, j;
  768. t_uint *o, *p, c;
  769.  
  770. if( X == B )
  771. {
  772. const mpi *T = A; A = X; B = T;
  773. }
  774.  
  775. if( X != A )
  776. MPI_CHK( mpi_copy( X, A ) );
  777.  
  778. /*
  779. * X should always be positive as a result of unsigned additions.
  780. */
  781. X->s = 1;
  782.  
  783. for( j = B->n; j > 0; j-- )
  784. if( B->p[j - 1] != 0 )
  785. break;
  786.  
  787. MPI_CHK( mpi_grow( X, j ) );
  788.  
  789. o = B->p; p = X->p; c = 0;
  790.  
  791. for( i = 0; i < j; i++, o++, p++ )
  792. {
  793. *p += c; c = ( *p < c );
  794. *p += *o; c += ( *p < *o );
  795. }
  796.  
  797. while( c != 0 )
  798. {
  799. if( i >= X->n )
  800. {
  801. MPI_CHK( mpi_grow( X, i + 1 ) );
  802. p = X->p + i;
  803. }
  804.  
  805. *p += c; c = ( *p < c ); i++; p++;
  806. }
  807.  
  808. cleanup:
  809.  
  810. return( ret );
  811. }
  812.  
  813. /*
  814. * Helper for mpi substraction
  815. */
  816. static void mpi_sub_hlp( size_t n, t_uint *s, t_uint *d )
  817. {
  818. size_t i;
  819. t_uint c, z;
  820.  
  821. for( i = c = 0; i < n; i++, s++, d++ )
  822. {
  823. z = ( *d < c ); *d -= c;
  824. c = ( *d < *s ) + z; *d -= *s;
  825. }
  826.  
  827. while( c != 0 )
  828. {
  829. z = ( *d < c ); *d -= c;
  830. c = z; i++; d++;
  831. }
  832. }
  833.  
  834. /*
  835. * Unsigned substraction: X = |A| - |B| (HAC 14.9)
  836. */
  837. int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B )
  838. {
  839. mpi TB;
  840. int ret;
  841. size_t n;
  842.  
  843. if( mpi_cmp_abs( A, B ) < 0 )
  844. return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
  845.  
  846. mpi_init( &TB );
  847.  
  848. if( X == B )
  849. {
  850. MPI_CHK( mpi_copy( &TB, B ) );
  851. B = &TB;
  852. }
  853.  
  854. if( X != A )
  855. MPI_CHK( mpi_copy( X, A ) );
  856.  
  857. /*
  858. * X should always be positive as a result of unsigned substractions.
  859. */
  860. X->s = 1;
  861.  
  862. ret = 0;
  863.  
  864. for( n = B->n; n > 0; n-- )
  865. if( B->p[n - 1] != 0 )
  866. break;
  867.  
  868. mpi_sub_hlp( n, B->p, X->p );
  869.  
  870. cleanup:
  871.  
  872. mpi_free( &TB );
  873.  
  874. return( ret );
  875. }
  876.  
  877. /*
  878. * Signed addition: X = A + B
  879. */
  880. int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B )
  881. {
  882. int ret, s = A->s;
  883.  
  884. if( A->s * B->s < 0 )
  885. {
  886. if( mpi_cmp_abs( A, B ) >= 0 )
  887. {
  888. MPI_CHK( mpi_sub_abs( X, A, B ) );
  889. X->s = s;
  890. }
  891. else
  892. {
  893. MPI_CHK( mpi_sub_abs( X, B, A ) );
  894. X->s = -s;
  895. }
  896. }
  897. else
  898. {
  899. MPI_CHK( mpi_add_abs( X, A, B ) );
  900. X->s = s;
  901. }
  902.  
  903. cleanup:
  904.  
  905. return( ret );
  906. }
  907.  
  908. /*
  909. * Signed substraction: X = A - B
  910. */
  911. int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B )
  912. {
  913. int ret, s = A->s;
  914.  
  915. if( A->s * B->s > 0 )
  916. {
  917. if( mpi_cmp_abs( A, B ) >= 0 )
  918. {
  919. MPI_CHK( mpi_sub_abs( X, A, B ) );
  920. X->s = s;
  921. }
  922. else
  923. {
  924. MPI_CHK( mpi_sub_abs( X, B, A ) );
  925. X->s = -s;
  926. }
  927. }
  928. else
  929. {
  930. MPI_CHK( mpi_add_abs( X, A, B ) );
  931. X->s = s;
  932. }
  933.  
  934. cleanup:
  935.  
  936. return( ret );
  937. }
  938.  
  939. /*
  940. * Signed addition: X = A + b
  941. */
  942. int mpi_add_int( mpi *X, const mpi *A, t_sint b )
  943. {
  944. mpi _B;
  945. t_uint p[1];
  946.  
  947. p[0] = ( b < 0 ) ? -b : b;
  948. _B.s = ( b < 0 ) ? -1 : 1;
  949. _B.n = 1;
  950. _B.p = p;
  951.  
  952. return( mpi_add_mpi( X, A, &_B ) );
  953. }
  954.  
  955. /*
  956. * Signed substraction: X = A - b
  957. */
  958. int mpi_sub_int( mpi *X, const mpi *A, t_sint b )
  959. {
  960. mpi _B;
  961. t_uint p[1];
  962.  
  963. p[0] = ( b < 0 ) ? -b : b;
  964. _B.s = ( b < 0 ) ? -1 : 1;
  965. _B.n = 1;
  966. _B.p = p;
  967.  
  968. return( mpi_sub_mpi( X, A, &_B ) );
  969. }
  970.  
  971. /*
  972. * Helper for mpi multiplication
  973. */
  974. static
  975. #if defined(__APPLE__) && defined(__arm__)
  976. /*
  977. * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
  978. * appears to need this to prevent bad ARM code generation at -O3.
  979. */
  980. __attribute__ ((noinline))
  981. #endif
  982. void mpi_mul_hlp( size_t i, t_uint *s, t_uint *d, t_uint b )
  983. {
  984. t_uint c = 0, t = 0;
  985.  
  986. #if defined(MULADDC_HUIT)
  987. for( ; i >= 8; i -= 8 )
  988. {
  989. MULADDC_INIT
  990. MULADDC_HUIT
  991. MULADDC_STOP
  992. }
  993.  
  994. for( ; i > 0; i-- )
  995. {
  996. MULADDC_INIT
  997. MULADDC_CORE
  998. MULADDC_STOP
  999. }
  1000. #else
  1001. for( ; i >= 16; i -= 16 )
  1002. {
  1003. MULADDC_INIT
  1004. MULADDC_CORE MULADDC_CORE
  1005. MULADDC_CORE MULADDC_CORE
  1006. MULADDC_CORE MULADDC_CORE
  1007. MULADDC_CORE MULADDC_CORE
  1008.  
  1009. MULADDC_CORE MULADDC_CORE
  1010. MULADDC_CORE MULADDC_CORE
  1011. MULADDC_CORE MULADDC_CORE
  1012. MULADDC_CORE MULADDC_CORE
  1013. MULADDC_STOP
  1014. }
  1015.  
  1016. for( ; i >= 8; i -= 8 )
  1017. {
  1018. MULADDC_INIT
  1019. MULADDC_CORE MULADDC_CORE
  1020. MULADDC_CORE MULADDC_CORE
  1021.  
  1022. MULADDC_CORE MULADDC_CORE
  1023. MULADDC_CORE MULADDC_CORE
  1024. MULADDC_STOP
  1025. }
  1026.  
  1027. for( ; i > 0; i-- )
  1028. {
  1029. MULADDC_INIT
  1030. MULADDC_CORE
  1031. MULADDC_STOP
  1032. }
  1033. #endif
  1034.  
  1035. t++;
  1036.  
  1037. do {
  1038. *d += c; c = ( *d < c ); d++;
  1039. }
  1040. while( c != 0 );
  1041. }
  1042.  
  1043. /*
  1044. * Baseline multiplication: X = A * B (HAC 14.12)
  1045. */
  1046. int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B )
  1047. {
  1048. int ret;
  1049. size_t i, j;
  1050. mpi TA, TB;
  1051.  
  1052. mpi_init( &TA ); mpi_init( &TB );
  1053.  
  1054. if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
  1055. if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
  1056.  
  1057. for( i = A->n; i > 0; i-- )
  1058. if( A->p[i - 1] != 0 )
  1059. break;
  1060.  
  1061. for( j = B->n; j > 0; j-- )
  1062. if( B->p[j - 1] != 0 )
  1063. break;
  1064.  
  1065. MPI_CHK( mpi_grow( X, i + j ) );
  1066. MPI_CHK( mpi_lset( X, 0 ) );
  1067.  
  1068. for( i++; j > 0; j-- )
  1069. mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
  1070.  
  1071. X->s = A->s * B->s;
  1072.  
  1073. cleanup:
  1074.  
  1075. mpi_free( &TB ); mpi_free( &TA );
  1076.  
  1077. return( ret );
  1078. }
  1079.  
  1080. /*
  1081. * Baseline multiplication: X = A * b
  1082. */
  1083. int mpi_mul_int( mpi *X, const mpi *A, t_sint b )
  1084. {
  1085. mpi _B;
  1086. t_uint p[1];
  1087.  
  1088. _B.s = 1;
  1089. _B.n = 1;
  1090. _B.p = p;
  1091. p[0] = b;
  1092.  
  1093. return( mpi_mul_mpi( X, A, &_B ) );
  1094. }
  1095.  
  1096. /*
  1097. * Division by mpi: A = Q * B + R (HAC 14.20)
  1098. */
  1099. int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B )
  1100. {
  1101. int ret;
  1102. size_t i, n, t, k;
  1103. mpi X, Y, Z, T1, T2;
  1104.  
  1105. if( mpi_cmp_int( B, 0 ) == 0 )
  1106. return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
  1107.  
  1108. mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
  1109. mpi_init( &T1 ); mpi_init( &T2 );
  1110.  
  1111. if( mpi_cmp_abs( A, B ) < 0 )
  1112. {
  1113. if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
  1114. if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
  1115. return( 0 );
  1116. }
  1117.  
  1118. MPI_CHK( mpi_copy( &X, A ) );
  1119. MPI_CHK( mpi_copy( &Y, B ) );
  1120. X.s = Y.s = 1;
  1121.  
  1122. MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
  1123. MPI_CHK( mpi_lset( &Z, 0 ) );
  1124. MPI_CHK( mpi_grow( &T1, 2 ) );
  1125. MPI_CHK( mpi_grow( &T2, 3 ) );
  1126.  
  1127. k = mpi_msb( &Y ) % biL;
  1128. if( k < biL - 1 )
  1129. {
  1130. k = biL - 1 - k;
  1131. MPI_CHK( mpi_shift_l( &X, k ) );
  1132. MPI_CHK( mpi_shift_l( &Y, k ) );
  1133. }
  1134. else k = 0;
  1135.  
  1136. n = X.n - 1;
  1137. t = Y.n - 1;
  1138. MPI_CHK( mpi_shift_l( &Y, biL * (n - t) ) );
  1139.  
  1140. while( mpi_cmp_mpi( &X, &Y ) >= 0 )
  1141. {
  1142. Z.p[n - t]++;
  1143. mpi_sub_mpi( &X, &X, &Y );
  1144. }
  1145. mpi_shift_r( &Y, biL * (n - t) );
  1146.  
  1147. for( i = n; i > t ; i-- )
  1148. {
  1149. if( X.p[i] >= Y.p[t] )
  1150. Z.p[i - t - 1] = ~0;
  1151. else
  1152. {
  1153. #if defined(POLARSSL_HAVE_UDBL)
  1154. t_udbl r;
  1155.  
  1156. r = (t_udbl) X.p[i] << biL;
  1157. r |= (t_udbl) X.p[i - 1];
  1158. r /= Y.p[t];
  1159. if( r > ((t_udbl) 1 << biL) - 1)
  1160. r = ((t_udbl) 1 << biL) - 1;
  1161.  
  1162. Z.p[i - t - 1] = (t_uint) r;
  1163. #else
  1164. /*
  1165. * __udiv_qrnnd_c, from gmp/longlong.h
  1166. */
  1167. t_uint q0, q1, r0, r1;
  1168. t_uint d0, d1, d, m;
  1169.  
  1170. d = Y.p[t];
  1171. d0 = ( d << biH ) >> biH;
  1172. d1 = ( d >> biH );
  1173.  
  1174. q1 = X.p[i] / d1;
  1175. r1 = X.p[i] - d1 * q1;
  1176. r1 <<= biH;
  1177. r1 |= ( X.p[i - 1] >> biH );
  1178.  
  1179. m = q1 * d0;
  1180. if( r1 < m )
  1181. {
  1182. q1--, r1 += d;
  1183. while( r1 >= d && r1 < m )
  1184. q1--, r1 += d;
  1185. }
  1186. r1 -= m;
  1187.  
  1188. q0 = r1 / d1;
  1189. r0 = r1 - d1 * q0;
  1190. r0 <<= biH;
  1191. r0 |= ( X.p[i - 1] << biH ) >> biH;
  1192.  
  1193. m = q0 * d0;
  1194. if( r0 < m )
  1195. {
  1196. q0--, r0 += d;
  1197. while( r0 >= d && r0 < m )
  1198. q0--, r0 += d;
  1199. }
  1200. r0 -= m;
  1201.  
  1202. Z.p[i - t - 1] = ( q1 << biH ) | q0;
  1203. #endif
  1204. }
  1205.  
  1206. Z.p[i - t - 1]++;
  1207. do
  1208. {
  1209. Z.p[i - t - 1]--;
  1210.  
  1211. MPI_CHK( mpi_lset( &T1, 0 ) );
  1212. T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
  1213. T1.p[1] = Y.p[t];
  1214. MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
  1215.  
  1216. MPI_CHK( mpi_lset( &T2, 0 ) );
  1217. T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
  1218. T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
  1219. T2.p[2] = X.p[i];
  1220. }
  1221. while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
  1222.  
  1223. MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
  1224. MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
  1225. MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
  1226.  
  1227. if( mpi_cmp_int( &X, 0 ) < 0 )
  1228. {
  1229. MPI_CHK( mpi_copy( &T1, &Y ) );
  1230. MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
  1231. MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
  1232. Z.p[i - t - 1]--;
  1233. }
  1234. }
  1235.  
  1236. if( Q != NULL )
  1237. {
  1238. mpi_copy( Q, &Z );
  1239. Q->s = A->s * B->s;
  1240. }
  1241.  
  1242. if( R != NULL )
  1243. {
  1244. mpi_shift_r( &X, k );
  1245. X.s = A->s;
  1246. mpi_copy( R, &X );
  1247.  
  1248. if( mpi_cmp_int( R, 0 ) == 0 )
  1249. R->s = 1;
  1250. }
  1251.  
  1252. cleanup:
  1253.  
  1254. mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
  1255. mpi_free( &T1 ); mpi_free( &T2 );
  1256.  
  1257. return( ret );
  1258. }
  1259.  
  1260. /*
  1261. * Division by int: A = Q * b + R
  1262. */
  1263. int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b )
  1264. {
  1265. mpi _B;
  1266. t_uint p[1];
  1267.  
  1268. p[0] = ( b < 0 ) ? -b : b;
  1269. _B.s = ( b < 0 ) ? -1 : 1;
  1270. _B.n = 1;
  1271. _B.p = p;
  1272.  
  1273. return( mpi_div_mpi( Q, R, A, &_B ) );
  1274. }
  1275.  
  1276. /*
  1277. * Modulo: R = A mod B
  1278. */
  1279. int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B )
  1280. {
  1281. int ret;
  1282.  
  1283. if( mpi_cmp_int( B, 0 ) < 0 )
  1284. return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
  1285.  
  1286. MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
  1287.  
  1288. while( mpi_cmp_int( R, 0 ) < 0 )
  1289. MPI_CHK( mpi_add_mpi( R, R, B ) );
  1290.  
  1291. while( mpi_cmp_mpi( R, B ) >= 0 )
  1292. MPI_CHK( mpi_sub_mpi( R, R, B ) );
  1293.  
  1294. cleanup:
  1295.  
  1296. return( ret );
  1297. }
  1298.  
  1299. /*
  1300. * Modulo: r = A mod b
  1301. */
  1302. int mpi_mod_int( t_uint *r, const mpi *A, t_sint b )
  1303. {
  1304. size_t i;
  1305. t_uint x, y, z;
  1306.  
  1307. if( b == 0 )
  1308. return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
  1309.  
  1310. if( b < 0 )
  1311. return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
  1312.  
  1313. /*
  1314. * handle trivial cases
  1315. */
  1316. if( b == 1 )
  1317. {
  1318. *r = 0;
  1319. return( 0 );
  1320. }
  1321.  
  1322. if( b == 2 )
  1323. {
  1324. *r = A->p[0] & 1;
  1325. return( 0 );
  1326. }
  1327.  
  1328. /*
  1329. * general case
  1330. */
  1331. for( i = A->n, y = 0; i > 0; i-- )
  1332. {
  1333. x = A->p[i - 1];
  1334. y = ( y << biH ) | ( x >> biH );
  1335. z = y / b;
  1336. y -= z * b;
  1337.  
  1338. x <<= biH;
  1339. y = ( y << biH ) | ( x >> biH );
  1340. z = y / b;
  1341. y -= z * b;
  1342. }
  1343.  
  1344. /*
  1345. * If A is negative, then the current y represents a negative value.
  1346. * Flipping it to the positive side.
  1347. */
  1348. if( A->s < 0 && y != 0 )
  1349. y = b - y;
  1350.  
  1351. *r = y;
  1352.  
  1353. return( 0 );
  1354. }
  1355.  
  1356. /*
  1357. * Fast Montgomery initialization (thanks to Tom St Denis)
  1358. */
  1359. static void mpi_montg_init( t_uint *mm, const mpi *N )
  1360. {
  1361. t_uint x, m0 = N->p[0];
  1362.  
  1363. x = m0;
  1364. x += ( ( m0 + 2 ) & 4 ) << 1;
  1365. x *= ( 2 - ( m0 * x ) );
  1366.  
  1367. if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
  1368. if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
  1369. if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
  1370.  
  1371. *mm = ~x + 1;
  1372. }
  1373.  
  1374. /*
  1375. * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
  1376. */
  1377. static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_uint mm, const mpi *T )
  1378. {
  1379. size_t i, n, m;
  1380. t_uint u0, u1, *d;
  1381.  
  1382. memset( T->p, 0, T->n * ciL );
  1383.  
  1384. d = T->p;
  1385. n = N->n;
  1386. m = ( B->n < n ) ? B->n : n;
  1387.  
  1388. for( i = 0; i < n; i++ )
  1389. {
  1390. /*
  1391. * T = (T + u0*B + u1*N) / 2^biL
  1392. */
  1393. u0 = A->p[i];
  1394. u1 = ( d[0] + u0 * B->p[0] ) * mm;
  1395.  
  1396. mpi_mul_hlp( m, B->p, d, u0 );
  1397. mpi_mul_hlp( n, N->p, d, u1 );
  1398.  
  1399. *d++ = u0; d[n + 1] = 0;
  1400. }
  1401.  
  1402. memcpy( A->p, d, (n + 1) * ciL );
  1403.  
  1404. if( mpi_cmp_abs( A, N ) >= 0 )
  1405. mpi_sub_hlp( n, N->p, A->p );
  1406. else
  1407. /* prevent timing attacks */
  1408. mpi_sub_hlp( n, A->p, T->p );
  1409. }
  1410.  
  1411. /*
  1412. * Montgomery reduction: A = A * R^-1 mod N
  1413. */
  1414. static void mpi_montred( mpi *A, const mpi *N, t_uint mm, const mpi *T )
  1415. {
  1416. t_uint z = 1;
  1417. mpi U;
  1418.  
  1419. U.n = U.s = (int) z;
  1420. U.p = &z;
  1421.  
  1422. mpi_montmul( A, &U, N, mm, T );
  1423. }
  1424.  
  1425. /*
  1426. * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
  1427. */
  1428. int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR )
  1429. {
  1430. int ret;
  1431. size_t wbits, wsize, one = 1;
  1432. size_t i, j, nblimbs;
  1433. size_t bufsize, nbits;
  1434. t_uint ei, mm, state;
  1435. mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos;
  1436. int neg;
  1437.  
  1438. if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
  1439. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  1440.  
  1441. if( mpi_cmp_int( E, 0 ) < 0 )
  1442. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  1443.  
  1444. /*
  1445. * Init temps and window size
  1446. */
  1447. mpi_montg_init( &mm, N );
  1448. mpi_init( &RR ); mpi_init( &T );
  1449. memset( W, 0, sizeof( W ) );
  1450.  
  1451. i = mpi_msb( E );
  1452.  
  1453. wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
  1454. ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
  1455.  
  1456. if( wsize > POLARSSL_MPI_WINDOW_SIZE )
  1457. wsize = POLARSSL_MPI_WINDOW_SIZE;
  1458.  
  1459. j = N->n + 1;
  1460. MPI_CHK( mpi_grow( X, j ) );
  1461. MPI_CHK( mpi_grow( &W[1], j ) );
  1462. MPI_CHK( mpi_grow( &T, j * 2 ) );
  1463.  
  1464. /*
  1465. * Compensate for negative A (and correct at the end)
  1466. */
  1467. neg = ( A->s == -1 );
  1468.  
  1469. mpi_init( &Apos );
  1470. if( neg )
  1471. {
  1472. MPI_CHK( mpi_copy( &Apos, A ) );
  1473. Apos.s = 1;
  1474. A = &Apos;
  1475. }
  1476.  
  1477. /*
  1478. * If 1st call, pre-compute R^2 mod N
  1479. */
  1480. if( _RR == NULL || _RR->p == NULL )
  1481. {
  1482. MPI_CHK( mpi_lset( &RR, 1 ) );
  1483. MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
  1484. MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
  1485.  
  1486. if( _RR != NULL )
  1487. memcpy( _RR, &RR, sizeof( mpi ) );
  1488. }
  1489. else
  1490. memcpy( &RR, _RR, sizeof( mpi ) );
  1491.  
  1492. /*
  1493. * W[1] = A * R^2 * R^-1 mod N = A * R mod N
  1494. */
  1495. if( mpi_cmp_mpi( A, N ) >= 0 )
  1496. mpi_mod_mpi( &W[1], A, N );
  1497. else mpi_copy( &W[1], A );
  1498.  
  1499. mpi_montmul( &W[1], &RR, N, mm, &T );
  1500.  
  1501. /*
  1502. * X = R^2 * R^-1 mod N = R mod N
  1503. */
  1504. MPI_CHK( mpi_copy( X, &RR ) );
  1505. mpi_montred( X, N, mm, &T );
  1506.  
  1507. if( wsize > 1 )
  1508. {
  1509. /*
  1510. * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
  1511. */
  1512. j = one << (wsize - 1);
  1513.  
  1514. MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
  1515. MPI_CHK( mpi_copy( &W[j], &W[1] ) );
  1516.  
  1517. for( i = 0; i < wsize - 1; i++ )
  1518. mpi_montmul( &W[j], &W[j], N, mm, &T );
  1519.  
  1520. /*
  1521. * W[i] = W[i - 1] * W[1]
  1522. */
  1523. for( i = j + 1; i < (one << wsize); i++ )
  1524. {
  1525. MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
  1526. MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
  1527.  
  1528. mpi_montmul( &W[i], &W[1], N, mm, &T );
  1529. }
  1530. }
  1531.  
  1532. nblimbs = E->n;
  1533. bufsize = 0;
  1534. nbits = 0;
  1535. wbits = 0;
  1536. state = 0;
  1537.  
  1538. while( 1 )
  1539. {
  1540. if( bufsize == 0 )
  1541. {
  1542. if( nblimbs-- == 0 )
  1543. break;
  1544.  
  1545. bufsize = sizeof( t_uint ) << 3;
  1546. }
  1547.  
  1548. bufsize--;
  1549.  
  1550. ei = (E->p[nblimbs] >> bufsize) & 1;
  1551.  
  1552. /*
  1553. * skip leading 0s
  1554. */
  1555. if( ei == 0 && state == 0 )
  1556. continue;
  1557.  
  1558. if( ei == 0 && state == 1 )
  1559. {
  1560. /*
  1561. * out of window, square X
  1562. */
  1563. mpi_montmul( X, X, N, mm, &T );
  1564. continue;
  1565. }
  1566.  
  1567. /*
  1568. * add ei to current window
  1569. */
  1570. state = 2;
  1571.  
  1572. nbits++;
  1573. wbits |= (ei << (wsize - nbits));
  1574.  
  1575. if( nbits == wsize )
  1576. {
  1577. /*
  1578. * X = X^wsize R^-1 mod N
  1579. */
  1580. for( i = 0; i < wsize; i++ )
  1581. mpi_montmul( X, X, N, mm, &T );
  1582.  
  1583. /*
  1584. * X = X * W[wbits] R^-1 mod N
  1585. */
  1586. mpi_montmul( X, &W[wbits], N, mm, &T );
  1587.  
  1588. state--;
  1589. nbits = 0;
  1590. wbits = 0;
  1591. }
  1592. }
  1593.  
  1594. /*
  1595. * process the remaining bits
  1596. */
  1597. for( i = 0; i < nbits; i++ )
  1598. {
  1599. mpi_montmul( X, X, N, mm, &T );
  1600.  
  1601. wbits <<= 1;
  1602.  
  1603. if( (wbits & (one << wsize)) != 0 )
  1604. mpi_montmul( X, &W[1], N, mm, &T );
  1605. }
  1606.  
  1607. /*
  1608. * X = A^E * R * R^-1 mod N = A^E mod N
  1609. */
  1610. mpi_montred( X, N, mm, &T );
  1611.  
  1612. if( neg )
  1613. {
  1614. X->s = -1;
  1615. mpi_add_mpi( X, N, X );
  1616. }
  1617.  
  1618. cleanup:
  1619.  
  1620. for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
  1621. mpi_free( &W[i] );
  1622.  
  1623. mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos );
  1624.  
  1625. if( _RR == NULL )
  1626. mpi_free( &RR );
  1627.  
  1628. return( ret );
  1629. }
  1630.  
  1631. /*
  1632. * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
  1633. */
  1634. int mpi_gcd( mpi *G, const mpi *A, const mpi *B )
  1635. {
  1636. int ret;
  1637. size_t lz, lzt;
  1638. mpi TG, TA, TB;
  1639.  
  1640. mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB );
  1641.  
  1642. MPI_CHK( mpi_copy( &TA, A ) );
  1643. MPI_CHK( mpi_copy( &TB, B ) );
  1644.  
  1645. lz = mpi_lsb( &TA );
  1646. lzt = mpi_lsb( &TB );
  1647.  
  1648. if ( lzt < lz )
  1649. lz = lzt;
  1650.  
  1651. MPI_CHK( mpi_shift_r( &TA, lz ) );
  1652. MPI_CHK( mpi_shift_r( &TB, lz ) );
  1653.  
  1654. TA.s = TB.s = 1;
  1655.  
  1656. while( mpi_cmp_int( &TA, 0 ) != 0 )
  1657. {
  1658. MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
  1659. MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
  1660.  
  1661. if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
  1662. {
  1663. MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
  1664. MPI_CHK( mpi_shift_r( &TA, 1 ) );
  1665. }
  1666. else
  1667. {
  1668. MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
  1669. MPI_CHK( mpi_shift_r( &TB, 1 ) );
  1670. }
  1671. }
  1672.  
  1673. MPI_CHK( mpi_shift_l( &TB, lz ) );
  1674. MPI_CHK( mpi_copy( G, &TB ) );
  1675.  
  1676. cleanup:
  1677.  
  1678. mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB );
  1679.  
  1680. return( ret );
  1681. }
  1682.  
  1683. int mpi_fill_random( mpi *X, size_t size,
  1684. int (*f_rng)(void *, unsigned char *, size_t),
  1685. void *p_rng )
  1686. {
  1687. int ret;
  1688.  
  1689. MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( size ) ) );
  1690. MPI_CHK( mpi_lset( X, 0 ) );
  1691.  
  1692. MPI_CHK( f_rng( p_rng, (unsigned char *) X->p, size ) );
  1693.  
  1694. cleanup:
  1695. return( ret );
  1696. }
  1697.  
  1698. /*
  1699. * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
  1700. */
  1701. int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
  1702. {
  1703. int ret;
  1704. mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
  1705.  
  1706. if( mpi_cmp_int( N, 0 ) <= 0 )
  1707. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  1708.  
  1709. mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 );
  1710. mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV );
  1711. mpi_init( &V1 ); mpi_init( &V2 );
  1712.  
  1713. MPI_CHK( mpi_gcd( &G, A, N ) );
  1714.  
  1715. if( mpi_cmp_int( &G, 1 ) != 0 )
  1716. {
  1717. ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
  1718. goto cleanup;
  1719. }
  1720.  
  1721. MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
  1722. MPI_CHK( mpi_copy( &TU, &TA ) );
  1723. MPI_CHK( mpi_copy( &TB, N ) );
  1724. MPI_CHK( mpi_copy( &TV, N ) );
  1725.  
  1726. MPI_CHK( mpi_lset( &U1, 1 ) );
  1727. MPI_CHK( mpi_lset( &U2, 0 ) );
  1728. MPI_CHK( mpi_lset( &V1, 0 ) );
  1729. MPI_CHK( mpi_lset( &V2, 1 ) );
  1730.  
  1731. do
  1732. {
  1733. while( ( TU.p[0] & 1 ) == 0 )
  1734. {
  1735. MPI_CHK( mpi_shift_r( &TU, 1 ) );
  1736.  
  1737. if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
  1738. {
  1739. MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
  1740. MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
  1741. }
  1742.  
  1743. MPI_CHK( mpi_shift_r( &U1, 1 ) );
  1744. MPI_CHK( mpi_shift_r( &U2, 1 ) );
  1745. }
  1746.  
  1747. while( ( TV.p[0] & 1 ) == 0 )
  1748. {
  1749. MPI_CHK( mpi_shift_r( &TV, 1 ) );
  1750.  
  1751. if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
  1752. {
  1753. MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
  1754. MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
  1755. }
  1756.  
  1757. MPI_CHK( mpi_shift_r( &V1, 1 ) );
  1758. MPI_CHK( mpi_shift_r( &V2, 1 ) );
  1759. }
  1760.  
  1761. if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
  1762. {
  1763. MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
  1764. MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
  1765. MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
  1766. }
  1767. else
  1768. {
  1769. MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
  1770. MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
  1771. MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
  1772. }
  1773. }
  1774. while( mpi_cmp_int( &TU, 0 ) != 0 );
  1775.  
  1776. while( mpi_cmp_int( &V1, 0 ) < 0 )
  1777. MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
  1778.  
  1779. while( mpi_cmp_mpi( &V1, N ) >= 0 )
  1780. MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
  1781.  
  1782. MPI_CHK( mpi_copy( X, &V1 ) );
  1783.  
  1784. cleanup:
  1785.  
  1786. mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 );
  1787. mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV );
  1788. mpi_free( &V1 ); mpi_free( &V2 );
  1789.  
  1790. return( ret );
  1791. }
  1792.  
  1793. #if defined(POLARSSL_GENPRIME)
  1794.  
  1795. static const int small_prime[] =
  1796. {
  1797. 3, 5, 7, 11, 13, 17, 19, 23,
  1798. 29, 31, 37, 41, 43, 47, 53, 59,
  1799. 61, 67, 71, 73, 79, 83, 89, 97,
  1800. 101, 103, 107, 109, 113, 127, 131, 137,
  1801. 139, 149, 151, 157, 163, 167, 173, 179,
  1802. 181, 191, 193, 197, 199, 211, 223, 227,
  1803. 229, 233, 239, 241, 251, 257, 263, 269,
  1804. 271, 277, 281, 283, 293, 307, 311, 313,
  1805. 317, 331, 337, 347, 349, 353, 359, 367,
  1806. 373, 379, 383, 389, 397, 401, 409, 419,
  1807. 421, 431, 433, 439, 443, 449, 457, 461,
  1808. 463, 467, 479, 487, 491, 499, 503, 509,
  1809. 521, 523, 541, 547, 557, 563, 569, 571,
  1810. 577, 587, 593, 599, 601, 607, 613, 617,
  1811. 619, 631, 641, 643, 647, 653, 659, 661,
  1812. 673, 677, 683, 691, 701, 709, 719, 727,
  1813. 733, 739, 743, 751, 757, 761, 769, 773,
  1814. 787, 797, 809, 811, 821, 823, 827, 829,
  1815. 839, 853, 857, 859, 863, 877, 881, 883,
  1816. 887, 907, 911, 919, 929, 937, 941, 947,
  1817. 953, 967, 971, 977, 983, 991, 997, -103
  1818. };
  1819.  
  1820. /*
  1821. * Miller-Rabin primality test (HAC 4.24)
  1822. */
  1823. int mpi_is_prime( mpi *X,
  1824. int (*f_rng)(void *, unsigned char *, size_t),
  1825. void *p_rng )
  1826. {
  1827. int ret, xs;
  1828. size_t i, j, n, s;
  1829. mpi W, R, T, A, RR;
  1830.  
  1831. if( mpi_cmp_int( X, 0 ) == 0 ||
  1832. mpi_cmp_int( X, 1 ) == 0 )
  1833. return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
  1834.  
  1835. if( mpi_cmp_int( X, 2 ) == 0 )
  1836. return( 0 );
  1837.  
  1838. mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
  1839. mpi_init( &RR );
  1840.  
  1841. xs = X->s; X->s = 1;
  1842.  
  1843. /*
  1844. * test trivial factors first
  1845. */
  1846. if( ( X->p[0] & 1 ) == 0 )
  1847. return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
  1848.  
  1849. for( i = 0; small_prime[i] > 0; i++ )
  1850. {
  1851. t_uint r;
  1852.  
  1853. if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
  1854. return( 0 );
  1855.  
  1856. MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
  1857.  
  1858. if( r == 0 )
  1859. return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
  1860. }
  1861.  
  1862. /*
  1863. * W = |X| - 1
  1864. * R = W >> lsb( W )
  1865. */
  1866. MPI_CHK( mpi_sub_int( &W, X, 1 ) );
  1867. s = mpi_lsb( &W );
  1868. MPI_CHK( mpi_copy( &R, &W ) );
  1869. MPI_CHK( mpi_shift_r( &R, s ) );
  1870.  
  1871. i = mpi_msb( X );
  1872. /*
  1873. * HAC, table 4.4
  1874. */
  1875. n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
  1876. ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
  1877. ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
  1878.  
  1879. for( i = 0; i < n; i++ )
  1880. {
  1881. /*
  1882. * pick a random A, 1 < A < |X| - 1
  1883. */
  1884. MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
  1885.  
  1886. if( mpi_cmp_mpi( &A, &W ) >= 0 )
  1887. {
  1888. j = mpi_msb( &A ) - mpi_msb( &W );
  1889. MPI_CHK( mpi_shift_r( &A, j + 1 ) );
  1890. }
  1891. A.p[0] |= 3;
  1892.  
  1893. /*
  1894. * A = A^R mod |X|
  1895. */
  1896. MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
  1897.  
  1898. if( mpi_cmp_mpi( &A, &W ) == 0 ||
  1899. mpi_cmp_int( &A, 1 ) == 0 )
  1900. continue;
  1901.  
  1902. j = 1;
  1903. while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
  1904. {
  1905. /*
  1906. * A = A * A mod |X|
  1907. */
  1908. MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
  1909. MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
  1910.  
  1911. if( mpi_cmp_int( &A, 1 ) == 0 )
  1912. break;
  1913.  
  1914. j++;
  1915. }
  1916.  
  1917. /*
  1918. * not prime if A != |X| - 1 or A == 1
  1919. */
  1920. if( mpi_cmp_mpi( &A, &W ) != 0 ||
  1921. mpi_cmp_int( &A, 1 ) == 0 )
  1922. {
  1923. ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
  1924. break;
  1925. }
  1926. }
  1927.  
  1928. cleanup:
  1929.  
  1930. X->s = xs;
  1931.  
  1932. mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
  1933. mpi_free( &RR );
  1934.  
  1935. return( ret );
  1936. }
  1937.  
  1938. /*
  1939. * Prime number generation
  1940. */
  1941. int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
  1942. int (*f_rng)(void *, unsigned char *, size_t),
  1943. void *p_rng )
  1944. {
  1945. int ret;
  1946. size_t k, n;
  1947. mpi Y;
  1948.  
  1949. if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
  1950. return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
  1951.  
  1952. mpi_init( &Y );
  1953.  
  1954. n = BITS_TO_LIMBS( nbits );
  1955.  
  1956. MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
  1957.  
  1958. k = mpi_msb( X );
  1959. if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
  1960. if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
  1961.  
  1962. X->p[0] |= 3;
  1963.  
  1964. if( dh_flag == 0 )
  1965. {
  1966. while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
  1967. {
  1968. if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
  1969. goto cleanup;
  1970.  
  1971. MPI_CHK( mpi_add_int( X, X, 2 ) );
  1972. }
  1973. }
  1974. else
  1975. {
  1976. MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
  1977. MPI_CHK( mpi_shift_r( &Y, 1 ) );
  1978.  
  1979. while( 1 )
  1980. {
  1981. if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
  1982. {
  1983. if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
  1984. break;
  1985.  
  1986. if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
  1987. goto cleanup;
  1988. }
  1989.  
  1990. if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
  1991. goto cleanup;
  1992.  
  1993. MPI_CHK( mpi_add_int( &Y, X, 1 ) );
  1994. MPI_CHK( mpi_add_int( X, X, 2 ) );
  1995. MPI_CHK( mpi_shift_r( &Y, 1 ) );
  1996. }
  1997. }
  1998.  
  1999. cleanup:
  2000.  
  2001. mpi_free( &Y );
  2002.  
  2003. return( ret );
  2004. }
  2005.  
  2006. #endif
  2007.  
  2008. #if defined(POLARSSL_SELF_TEST)
  2009.  
  2010. #define GCD_PAIR_COUNT 3
  2011.  
  2012. static const int gcd_pairs[GCD_PAIR_COUNT][3] =
  2013. {
  2014. { 693, 609, 21 },
  2015. { 1764, 868, 28 },
  2016. { 768454923, 542167814, 1 }
  2017. };
  2018.  
  2019. /*
  2020. * Checkup routine
  2021. */
  2022. int mpi_self_test( int verbose )
  2023. {
  2024. int ret, i;
  2025. mpi A, E, N, X, Y, U, V;
  2026.  
  2027. mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X );
  2028. mpi_init( &Y ); mpi_init( &U ); mpi_init( &V );
  2029.  
  2030. MPI_CHK( mpi_read_string( &A, 16,
  2031. "EFE021C2645FD1DC586E69184AF4A31E" \
  2032. "D5F53E93B5F123FA41680867BA110131" \
  2033. "944FE7952E2517337780CB0DB80E61AA" \
  2034. "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
  2035.  
  2036. MPI_CHK( mpi_read_string( &E, 16,
  2037. "B2E7EFD37075B9F03FF989C7C5051C20" \
  2038. "34D2A323810251127E7BF8625A4F49A5" \
  2039. "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
  2040. "5B5C25763222FEFCCFC38B832366C29E" ) );
  2041.  
  2042. MPI_CHK( mpi_read_string( &N, 16,
  2043. "0066A198186C18C10B2F5ED9B522752A" \
  2044. "9830B69916E535C8F047518A889A43A5" \
  2045. "94B6BED27A168D31D4A52F88925AA8F5" ) );
  2046.  
  2047. MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
  2048.  
  2049. MPI_CHK( mpi_read_string( &U, 16,
  2050. "602AB7ECA597A3D6B56FF9829A5E8B85" \
  2051. "9E857EA95A03512E2BAE7391688D264A" \
  2052. "A5663B0341DB9CCFD2C4C5F421FEC814" \
  2053. "8001B72E848A38CAE1C65F78E56ABDEF" \
  2054. "E12D3C039B8A02D6BE593F0BBBDA56F1" \
  2055. "ECF677152EF804370C1A305CAF3B5BF1" \
  2056. "30879B56C61DE584A0F53A2447A51E" ) );
  2057.  
  2058. if( verbose != 0 )
  2059. printf( " MPI test #1 (mul_mpi): " );
  2060.  
  2061. if( mpi_cmp_mpi( &X, &U ) != 0 )
  2062. {
  2063. if( verbose != 0 )
  2064. printf( "failed\n" );
  2065.  
  2066. return( 1 );
  2067. }
  2068.  
  2069. if( verbose != 0 )
  2070. printf( "passed\n" );
  2071.  
  2072. MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
  2073.  
  2074. MPI_CHK( mpi_read_string( &U, 16,
  2075. "256567336059E52CAE22925474705F39A94" ) );
  2076.  
  2077. MPI_CHK( mpi_read_string( &V, 16,
  2078. "6613F26162223DF488E9CD48CC132C7A" \
  2079. "0AC93C701B001B092E4E5B9F73BCD27B" \
  2080. "9EE50D0657C77F374E903CDFA4C642" ) );
  2081.  
  2082. if( verbose != 0 )
  2083. printf( " MPI test #2 (div_mpi): " );
  2084.  
  2085. if( mpi_cmp_mpi( &X, &U ) != 0 ||
  2086. mpi_cmp_mpi( &Y, &V ) != 0 )
  2087. {
  2088. if( verbose != 0 )
  2089. printf( "failed\n" );
  2090.  
  2091. return( 1 );
  2092. }
  2093.  
  2094. if( verbose != 0 )
  2095. printf( "passed\n" );
  2096.  
  2097. MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
  2098.  
  2099. MPI_CHK( mpi_read_string( &U, 16,
  2100. "36E139AEA55215609D2816998ED020BB" \
  2101. "BD96C37890F65171D948E9BC7CBAA4D9" \
  2102. "325D24D6A3C12710F10A09FA08AB87" ) );
  2103.  
  2104. if( verbose != 0 )
  2105. printf( " MPI test #3 (exp_mod): " );
  2106.  
  2107. if( mpi_cmp_mpi( &X, &U ) != 0 )
  2108. {
  2109. if( verbose != 0 )
  2110. printf( "failed\n" );
  2111.  
  2112. return( 1 );
  2113. }
  2114.  
  2115. if( verbose != 0 )
  2116. printf( "passed\n" );
  2117.  
  2118. #if defined(POLARSSL_GENPRIME)
  2119. MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
  2120.  
  2121. MPI_CHK( mpi_read_string( &U, 16,
  2122. "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
  2123. "C3DBA76456363A10869622EAC2DD84EC" \
  2124. "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
  2125.  
  2126. if( verbose != 0 )
  2127. printf( " MPI test #4 (inv_mod): " );
  2128.  
  2129. if( mpi_cmp_mpi( &X, &U ) != 0 )
  2130. {
  2131. if( verbose != 0 )
  2132. printf( "failed\n" );
  2133.  
  2134. return( 1 );
  2135. }
  2136.  
  2137. if( verbose != 0 )
  2138. printf( "passed\n" );
  2139. #endif
  2140.  
  2141. if( verbose != 0 )
  2142. printf( " MPI test #5 (simple gcd): " );
  2143.  
  2144. for ( i = 0; i < GCD_PAIR_COUNT; i++)
  2145. {
  2146. MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
  2147. MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
  2148.  
  2149. MPI_CHK( mpi_gcd( &A, &X, &Y ) );
  2150.  
  2151. if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
  2152. {
  2153. if( verbose != 0 )
  2154. printf( "failed at %d\n", i );
  2155.  
  2156. return( 1 );
  2157. }
  2158. }
  2159.  
  2160. if( verbose != 0 )
  2161. printf( "passed\n" );
  2162.  
  2163. cleanup:
  2164.  
  2165. if( ret != 0 && verbose != 0 )
  2166. printf( "Unexpected error, return code = %08X\n", ret );
  2167.  
  2168. mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X );
  2169. mpi_free( &Y ); mpi_free( &U ); mpi_free( &V );
  2170.  
  2171. if( verbose != 0 )
  2172. printf( "\n" );
  2173.  
  2174. return( ret );
  2175. }
  2176.  
  2177. #endif
  2178.  
  2179. #endif
  2180.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!