bignum.h 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766
  1. /**
  2. * \file bignum.h
  3. *
  4. * \brief Multi-precision integer library
  5. */
  6. /*
  7. * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
  8. * SPDX-License-Identifier: Apache-2.0
  9. *
  10. * Licensed under the Apache License, Version 2.0 (the "License"); you may
  11. * not use this file except in compliance with the License.
  12. * You may obtain a copy of the License at
  13. *
  14. * http://www.apache.org/licenses/LICENSE-2.0
  15. *
  16. * Unless required by applicable law or agreed to in writing, software
  17. * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  18. * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  19. * See the License for the specific language governing permissions and
  20. * limitations under the License.
  21. *
  22. * This file is part of mbed TLS (https://tls.mbed.org)
  23. */
  24. #ifndef MBEDTLS_BIGNUM_H
  25. #define MBEDTLS_BIGNUM_H
  26. #if !defined(MBEDTLS_CONFIG_FILE)
  27. #include "config.h"
  28. #else
  29. #include MBEDTLS_CONFIG_FILE
  30. #endif
  31. #include <stddef.h>
  32. #include <stdint.h>
  33. #if defined(MBEDTLS_FS_IO)
  34. #include <stdio.h>
  35. #endif
  36. #define MBEDTLS_ERR_MPI_FILE_IO_ERROR -0x0002 /**< An error occurred while reading from or writing to a file. */
  37. #define MBEDTLS_ERR_MPI_BAD_INPUT_DATA -0x0004 /**< Bad input parameters to function. */
  38. #define MBEDTLS_ERR_MPI_INVALID_CHARACTER -0x0006 /**< There is an invalid character in the digit string. */
  39. #define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL -0x0008 /**< The buffer is too small to write to. */
  40. #define MBEDTLS_ERR_MPI_NEGATIVE_VALUE -0x000A /**< The input arguments are negative or result in illegal output. */
  41. #define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO -0x000C /**< The input argument for division is zero, which is not allowed. */
  42. #define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE -0x000E /**< The input arguments are not acceptable. */
  43. #define MBEDTLS_ERR_MPI_ALLOC_FAILED -0x0010 /**< Memory allocation failed. */
  44. #define MBEDTLS_MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
  45. /*
  46. * Maximum size MPIs are allowed to grow to in number of limbs.
  47. */
  48. #define MBEDTLS_MPI_MAX_LIMBS 10000
  49. #if !defined(MBEDTLS_MPI_WINDOW_SIZE)
  50. /*
  51. * Maximum window size used for modular exponentiation. Default: 6
  52. * Minimum value: 1. Maximum value: 6.
  53. *
  54. * Result is an array of ( 2 << MBEDTLS_MPI_WINDOW_SIZE ) MPIs used
  55. * for the sliding window calculation. (So 64 by default)
  56. *
  57. * Reduction in size, reduces speed.
  58. */
  59. #define MBEDTLS_MPI_WINDOW_SIZE 6 /**< Maximum windows size used. */
  60. #endif /* !MBEDTLS_MPI_WINDOW_SIZE */
  61. #if !defined(MBEDTLS_MPI_MAX_SIZE)
  62. /*
  63. * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
  64. * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
  65. *
  66. * Note: Calculations can temporarily result in larger MPIs. So the number
  67. * of limbs required (MBEDTLS_MPI_MAX_LIMBS) is higher.
  68. */
  69. #define MBEDTLS_MPI_MAX_SIZE 1024 /**< Maximum number of bytes for usable MPIs. */
  70. #endif /* !MBEDTLS_MPI_MAX_SIZE */
  71. #define MBEDTLS_MPI_MAX_BITS ( 8 * MBEDTLS_MPI_MAX_SIZE ) /**< Maximum number of bits for usable MPIs. */
  72. /*
  73. * When reading from files with mbedtls_mpi_read_file() and writing to files with
  74. * mbedtls_mpi_write_file() the buffer should have space
  75. * for a (short) label, the MPI (in the provided radix), the newline
  76. * characters and the '\0'.
  77. *
  78. * By default we assume at least a 10 char label, a minimum radix of 10
  79. * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
  80. * Autosized at compile time for at least a 10 char label, a minimum radix
  81. * of 10 (decimal) for a number of MBEDTLS_MPI_MAX_BITS size.
  82. *
  83. * This used to be statically sized to 1250 for a maximum of 4096 bit
  84. * numbers (1234 decimal chars).
  85. *
  86. * Calculate using the formula:
  87. * MBEDTLS_MPI_RW_BUFFER_SIZE = ceil(MBEDTLS_MPI_MAX_BITS / ln(10) * ln(2)) +
  88. * LabelSize + 6
  89. */
  90. #define MBEDTLS_MPI_MAX_BITS_SCALE100 ( 100 * MBEDTLS_MPI_MAX_BITS )
  91. #define MBEDTLS_LN_2_DIV_LN_10_SCALE100 332
  92. #define MBEDTLS_MPI_RW_BUFFER_SIZE ( ((MBEDTLS_MPI_MAX_BITS_SCALE100 + MBEDTLS_LN_2_DIV_LN_10_SCALE100 - 1) / MBEDTLS_LN_2_DIV_LN_10_SCALE100) + 10 + 6 )
  93. /*
  94. * Define the base integer type, architecture-wise.
  95. *
  96. * 32 or 64-bit integer types can be forced regardless of the underlying
  97. * architecture by defining MBEDTLS_HAVE_INT32 or MBEDTLS_HAVE_INT64
  98. * respectively and undefining MBEDTLS_HAVE_ASM.
  99. *
  100. * Double-width integers (e.g. 128-bit in 64-bit architectures) can be
  101. * disabled by defining MBEDTLS_NO_UDBL_DIVISION.
  102. */
  103. #if !defined(MBEDTLS_HAVE_INT32)
  104. #if defined(_MSC_VER) && defined(_M_AMD64)
  105. /* Always choose 64-bit when using MSC */
  106. #if !defined(MBEDTLS_HAVE_INT64)
  107. #define MBEDTLS_HAVE_INT64
  108. #endif /* !MBEDTLS_HAVE_INT64 */
  109. typedef int64_t mbedtls_mpi_sint;
  110. typedef uint64_t mbedtls_mpi_uint;
  111. #elif defined(__GNUC__) && ( \
  112. defined(__amd64__) || defined(__x86_64__) || \
  113. defined(__ppc64__) || defined(__powerpc64__) || \
  114. defined(__ia64__) || defined(__alpha__) || \
  115. ( defined(__sparc__) && defined(__arch64__) ) || \
  116. defined(__s390x__) || defined(__mips64) )
  117. #if !defined(MBEDTLS_HAVE_INT64)
  118. #define MBEDTLS_HAVE_INT64
  119. #endif /* MBEDTLS_HAVE_INT64 */
  120. typedef int64_t mbedtls_mpi_sint;
  121. typedef uint64_t mbedtls_mpi_uint;
  122. #if !defined(MBEDTLS_NO_UDBL_DIVISION)
  123. /* mbedtls_t_udbl defined as 128-bit unsigned int */
  124. typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI)));
  125. #define MBEDTLS_HAVE_UDBL
  126. #endif /* !MBEDTLS_NO_UDBL_DIVISION */
  127. #elif defined(__ARMCC_VERSION) && defined(__aarch64__)
  128. /*
  129. * __ARMCC_VERSION is defined for both armcc and armclang and
  130. * __aarch64__ is only defined by armclang when compiling 64-bit code
  131. */
  132. #if !defined(MBEDTLS_HAVE_INT64)
  133. #define MBEDTLS_HAVE_INT64
  134. #endif /* !MBEDTLS_HAVE_INT64 */
  135. typedef int64_t mbedtls_mpi_sint;
  136. typedef uint64_t mbedtls_mpi_uint;
  137. #if !defined(MBEDTLS_NO_UDBL_DIVISION)
  138. /* mbedtls_t_udbl defined as 128-bit unsigned int */
  139. typedef __uint128_t mbedtls_t_udbl;
  140. #define MBEDTLS_HAVE_UDBL
  141. #endif /* !MBEDTLS_NO_UDBL_DIVISION */
  142. #elif defined(MBEDTLS_HAVE_INT64)
  143. /* Force 64-bit integers with unknown compiler */
  144. typedef int64_t mbedtls_mpi_sint;
  145. typedef uint64_t mbedtls_mpi_uint;
  146. #endif
  147. #endif /* !MBEDTLS_HAVE_INT32 */
  148. #if !defined(MBEDTLS_HAVE_INT64)
  149. /* Default to 32-bit compilation */
  150. #if !defined(MBEDTLS_HAVE_INT32)
  151. #define MBEDTLS_HAVE_INT32
  152. #endif /* !MBEDTLS_HAVE_INT32 */
  153. typedef int32_t mbedtls_mpi_sint;
  154. typedef uint32_t mbedtls_mpi_uint;
  155. #if !defined(MBEDTLS_NO_UDBL_DIVISION)
  156. typedef uint64_t mbedtls_t_udbl;
  157. #define MBEDTLS_HAVE_UDBL
  158. #endif /* !MBEDTLS_NO_UDBL_DIVISION */
  159. #endif /* !MBEDTLS_HAVE_INT64 */
  160. #ifdef __cplusplus
  161. extern "C" {
  162. #endif
  163. /**
  164. * \brief MPI structure
  165. */
  166. typedef struct
  167. {
  168. int s; /*!< integer sign */
  169. size_t n; /*!< total # of limbs */
  170. mbedtls_mpi_uint *p; /*!< pointer to limbs */
  171. }
  172. mbedtls_mpi;
  173. /**
  174. * \brief Initialize one MPI (make internal references valid)
  175. * This just makes it ready to be set or freed,
  176. * but does not define a value for the MPI.
  177. *
  178. * \param X One MPI to initialize.
  179. */
  180. void mbedtls_mpi_init( mbedtls_mpi *X );
  181. /**
  182. * \brief Unallocate one MPI
  183. *
  184. * \param X One MPI to unallocate.
  185. */
  186. void mbedtls_mpi_free( mbedtls_mpi *X );
  187. /**
  188. * \brief Enlarge to the specified number of limbs
  189. *
  190. * \param X MPI to grow
  191. * \param nblimbs The target number of limbs
  192. *
  193. * \return 0 if successful,
  194. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  195. */
  196. int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs );
  197. /**
  198. * \brief Resize down, keeping at least the specified number of limbs
  199. *
  200. * \param X MPI to shrink
  201. * \param nblimbs The minimum number of limbs to keep
  202. *
  203. * \return 0 if successful,
  204. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  205. */
  206. int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs );
  207. /**
  208. * \brief Copy the contents of Y into X
  209. *
  210. * \param X Destination MPI
  211. * \param Y Source MPI
  212. *
  213. * \return 0 if successful,
  214. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  215. */
  216. int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y );
  217. /**
  218. * \brief Swap the contents of X and Y
  219. *
  220. * \param X First MPI value
  221. * \param Y Second MPI value
  222. */
  223. void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y );
  224. /**
  225. * \brief Safe conditional assignement X = Y if assign is 1
  226. *
  227. * \param X MPI to conditionally assign to
  228. * \param Y Value to be assigned
  229. * \param assign 1: perform the assignment, 0: keep X's original value
  230. *
  231. * \return 0 if successful,
  232. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  233. *
  234. * \note This function is equivalent to
  235. * if( assign ) mbedtls_mpi_copy( X, Y );
  236. * except that it avoids leaking any information about whether
  237. * the assignment was done or not (the above code may leak
  238. * information through branch prediction and/or memory access
  239. * patterns analysis).
  240. */
  241. int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign );
  242. /**
  243. * \brief Safe conditional swap X <-> Y if swap is 1
  244. *
  245. * \param X First mbedtls_mpi value
  246. * \param Y Second mbedtls_mpi value
  247. * \param assign 1: perform the swap, 0: keep X and Y's original values
  248. *
  249. * \return 0 if successful,
  250. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  251. *
  252. * \note This function is equivalent to
  253. * if( assign ) mbedtls_mpi_swap( X, Y );
  254. * except that it avoids leaking any information about whether
  255. * the assignment was done or not (the above code may leak
  256. * information through branch prediction and/or memory access
  257. * patterns analysis).
  258. */
  259. int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign );
  260. /**
  261. * \brief Set value from integer
  262. *
  263. * \param X MPI to set
  264. * \param z Value to use
  265. *
  266. * \return 0 if successful,
  267. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  268. */
  269. int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z );
  270. /**
  271. * \brief Get a specific bit from X
  272. *
  273. * \param X MPI to use
  274. * \param pos Zero-based index of the bit in X
  275. *
  276. * \return Either a 0 or a 1
  277. */
  278. int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos );
  279. /**
  280. * \brief Set a bit of X to a specific value of 0 or 1
  281. *
  282. * \note Will grow X if necessary to set a bit to 1 in a not yet
  283. * existing limb. Will not grow if bit should be set to 0
  284. *
  285. * \param X MPI to use
  286. * \param pos Zero-based index of the bit in X
  287. * \param val The value to set the bit to (0 or 1)
  288. *
  289. * \return 0 if successful,
  290. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  291. * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1
  292. */
  293. int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val );
  294. /**
  295. * \brief Return the number of zero-bits before the least significant
  296. * '1' bit
  297. *
  298. * Note: Thus also the zero-based index of the least significant '1' bit
  299. *
  300. * \param X MPI to use
  301. */
  302. size_t mbedtls_mpi_lsb( const mbedtls_mpi *X );
  303. /**
  304. * \brief Return the number of bits up to and including the most
  305. * significant '1' bit'
  306. *
  307. * Note: Thus also the one-based index of the most significant '1' bit
  308. *
  309. * \param X MPI to use
  310. */
  311. size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X );
  312. /**
  313. * \brief Return the total size in bytes
  314. *
  315. * \param X MPI to use
  316. */
  317. size_t mbedtls_mpi_size( const mbedtls_mpi *X );
  318. /**
  319. * \brief Import from an ASCII string
  320. *
  321. * \param X Destination MPI
  322. * \param radix Input numeric base
  323. * \param s Null-terminated string buffer
  324. *
  325. * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code
  326. */
  327. int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s );
  328. /**
  329. * \brief Export into an ASCII string
  330. *
  331. * \param X Source MPI
  332. * \param radix Output numeric base
  333. * \param buf Buffer to write the string to
  334. * \param buflen Length of buf
  335. * \param olen Length of the string written, including final NUL byte
  336. *
  337. * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code.
  338. * *olen is always updated to reflect the amount
  339. * of data that has (or would have) been written.
  340. *
  341. * \note Call this function with buflen = 0 to obtain the
  342. * minimum required buffer size in *olen.
  343. */
  344. int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
  345. char *buf, size_t buflen, size_t *olen );
  346. #if defined(MBEDTLS_FS_IO)
  347. /**
  348. * \brief Read MPI from a line in an opened file
  349. *
  350. * \param X Destination MPI
  351. * \param radix Input numeric base
  352. * \param fin Input file handle
  353. *
  354. * \return 0 if successful, MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if
  355. * the file read buffer is too small or a
  356. * MBEDTLS_ERR_MPI_XXX error code
  357. *
  358. * \note On success, this function advances the file stream
  359. * to the end of the current line or to EOF.
  360. *
  361. * The function returns 0 on an empty line.
  362. *
  363. * Leading whitespaces are ignored, as is a
  364. * '0x' prefix for radix 16.
  365. *
  366. */
  367. int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin );
  368. /**
  369. * \brief Write X into an opened file, or stdout if fout is NULL
  370. *
  371. * \param p Prefix, can be NULL
  372. * \param X Source MPI
  373. * \param radix Output numeric base
  374. * \param fout Output file handle (can be NULL)
  375. *
  376. * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code
  377. *
  378. * \note Set fout == NULL to print X on the console.
  379. */
  380. int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout );
  381. #endif /* MBEDTLS_FS_IO */
  382. /**
  383. * \brief Import X from unsigned binary data, big endian
  384. *
  385. * \param X Destination MPI
  386. * \param buf Input buffer
  387. * \param buflen Input buffer size
  388. *
  389. * \return 0 if successful,
  390. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  391. */
  392. int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen );
  393. /**
  394. * \brief Export X into unsigned binary data, big endian.
  395. * Always fills the whole buffer, which will start with zeros
  396. * if the number is smaller.
  397. *
  398. * \param X Source MPI
  399. * \param buf Output buffer
  400. * \param buflen Output buffer size
  401. *
  402. * \return 0 if successful,
  403. * MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough
  404. */
  405. int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen );
  406. /**
  407. * \brief Left-shift: X <<= count
  408. *
  409. * \param X MPI to shift
  410. * \param count Amount to shift
  411. *
  412. * \return 0 if successful,
  413. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  414. */
  415. int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count );
  416. /**
  417. * \brief Right-shift: X >>= count
  418. *
  419. * \param X MPI to shift
  420. * \param count Amount to shift
  421. *
  422. * \return 0 if successful,
  423. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  424. */
  425. int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count );
  426. /**
  427. * \brief Compare unsigned values
  428. *
  429. * \param X Left-hand MPI
  430. * \param Y Right-hand MPI
  431. *
  432. * \return 1 if |X| is greater than |Y|,
  433. * -1 if |X| is lesser than |Y| or
  434. * 0 if |X| is equal to |Y|
  435. */
  436. int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y );
  437. /**
  438. * \brief Compare signed values
  439. *
  440. * \param X Left-hand MPI
  441. * \param Y Right-hand MPI
  442. *
  443. * \return 1 if X is greater than Y,
  444. * -1 if X is lesser than Y or
  445. * 0 if X is equal to Y
  446. */
  447. int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y );
  448. /**
  449. * \brief Compare signed values
  450. *
  451. * \param X Left-hand MPI
  452. * \param z The integer value to compare to
  453. *
  454. * \return 1 if X is greater than z,
  455. * -1 if X is lesser than z or
  456. * 0 if X is equal to z
  457. */
  458. int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z );
  459. /**
  460. * \brief Unsigned addition: X = |A| + |B|
  461. *
  462. * \param X Destination MPI
  463. * \param A Left-hand MPI
  464. * \param B Right-hand MPI
  465. *
  466. * \return 0 if successful,
  467. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  468. */
  469. int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
  470. /**
  471. * \brief Unsigned subtraction: X = |A| - |B|
  472. *
  473. * \param X Destination MPI
  474. * \param A Left-hand MPI
  475. * \param B Right-hand MPI
  476. *
  477. * \return 0 if successful,
  478. * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B is greater than A
  479. */
  480. int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
  481. /**
  482. * \brief Signed addition: X = A + B
  483. *
  484. * \param X Destination MPI
  485. * \param A Left-hand MPI
  486. * \param B Right-hand MPI
  487. *
  488. * \return 0 if successful,
  489. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  490. */
  491. int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
  492. /**
  493. * \brief Signed subtraction: X = A - B
  494. *
  495. * \param X Destination MPI
  496. * \param A Left-hand MPI
  497. * \param B Right-hand MPI
  498. *
  499. * \return 0 if successful,
  500. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  501. */
  502. int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
  503. /**
  504. * \brief Signed addition: X = A + b
  505. *
  506. * \param X Destination MPI
  507. * \param A Left-hand MPI
  508. * \param b The integer value to add
  509. *
  510. * \return 0 if successful,
  511. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  512. */
  513. int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b );
  514. /**
  515. * \brief Signed subtraction: X = A - b
  516. *
  517. * \param X Destination MPI
  518. * \param A Left-hand MPI
  519. * \param b The integer value to subtract
  520. *
  521. * \return 0 if successful,
  522. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  523. */
  524. int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b );
  525. /**
  526. * \brief Baseline multiplication: X = A * B
  527. *
  528. * \param X Destination MPI
  529. * \param A Left-hand MPI
  530. * \param B Right-hand MPI
  531. *
  532. * \return 0 if successful,
  533. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  534. */
  535. int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
  536. /**
  537. * \brief Baseline multiplication: X = A * b
  538. *
  539. * \param X Destination MPI
  540. * \param A Left-hand MPI
  541. * \param b The unsigned integer value to multiply with
  542. *
  543. * \note b is unsigned
  544. *
  545. * \return 0 if successful,
  546. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  547. */
  548. int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b );
  549. /**
  550. * \brief Division by mbedtls_mpi: A = Q * B + R
  551. *
  552. * \param Q Destination MPI for the quotient
  553. * \param R Destination MPI for the rest value
  554. * \param A Left-hand MPI
  555. * \param B Right-hand MPI
  556. *
  557. * \return 0 if successful,
  558. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  559. * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0
  560. *
  561. * \note Either Q or R can be NULL.
  562. */
  563. int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B );
  564. /**
  565. * \brief Division by int: A = Q * b + R
  566. *
  567. * \param Q Destination MPI for the quotient
  568. * \param R Destination MPI for the rest value
  569. * \param A Left-hand MPI
  570. * \param b Integer to divide by
  571. *
  572. * \return 0 if successful,
  573. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  574. * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0
  575. *
  576. * \note Either Q or R can be NULL.
  577. */
  578. int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b );
  579. /**
  580. * \brief Modulo: R = A mod B
  581. *
  582. * \param R Destination MPI for the rest value
  583. * \param A Left-hand MPI
  584. * \param B Right-hand MPI
  585. *
  586. * \return 0 if successful,
  587. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  588. * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0,
  589. * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B < 0
  590. */
  591. int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B );
  592. /**
  593. * \brief Modulo: r = A mod b
  594. *
  595. * \param r Destination mbedtls_mpi_uint
  596. * \param A Left-hand MPI
  597. * \param b Integer to divide by
  598. *
  599. * \return 0 if successful,
  600. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  601. * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0,
  602. * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if b < 0
  603. */
  604. int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b );
  605. /**
  606. * \brief Sliding-window exponentiation: X = A^E mod N
  607. *
  608. * \param X Destination MPI
  609. * \param A Left-hand MPI
  610. * \param E Exponent MPI
  611. * \param N Modular MPI
  612. * \param _RR Speed-up MPI used for recalculations
  613. *
  614. * \return 0 if successful,
  615. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  616. * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is negative or even or
  617. * if E is negative
  618. *
  619. * \note _RR is used to avoid re-computing R*R mod N across
  620. * multiple calls, which speeds up things a bit. It can
  621. * be set to NULL if the extra performance is unneeded.
  622. */
  623. int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR );
  624. /**
  625. * \brief Fill an MPI X with size bytes of random
  626. *
  627. * \param X Destination MPI
  628. * \param size Size in bytes
  629. * \param f_rng RNG function
  630. * \param p_rng RNG parameter
  631. *
  632. * \return 0 if successful,
  633. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  634. *
  635. * \note The bytes obtained from the PRNG are interpreted
  636. * as a big-endian representation of an MPI; this can
  637. * be relevant in applications like deterministic ECDSA.
  638. */
  639. int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
  640. int (*f_rng)(void *, unsigned char *, size_t),
  641. void *p_rng );
  642. /**
  643. * \brief Greatest common divisor: G = gcd(A, B)
  644. *
  645. * \param G Destination MPI
  646. * \param A Left-hand MPI
  647. * \param B Right-hand MPI
  648. *
  649. * \return 0 if successful,
  650. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed
  651. */
  652. int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B );
  653. /**
  654. * \brief Modular inverse: X = A^-1 mod N
  655. *
  656. * \param X Destination MPI
  657. * \param A Left-hand MPI
  658. * \param N Right-hand MPI
  659. *
  660. * \return 0 if successful,
  661. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  662. * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is <= 1,
  663. MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N.
  664. */
  665. int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N );
  666. /**
  667. * \brief Miller-Rabin primality test
  668. *
  669. * \param X MPI to check
  670. * \param f_rng RNG function
  671. * \param p_rng RNG parameter
  672. *
  673. * \return 0 if successful (probably prime),
  674. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  675. * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime
  676. */
  677. int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
  678. int (*f_rng)(void *, unsigned char *, size_t),
  679. void *p_rng );
  680. /**
  681. * \brief Prime number generation
  682. *
  683. * \param X Destination MPI
  684. * \param nbits Required size of X in bits
  685. * ( 3 <= nbits <= MBEDTLS_MPI_MAX_BITS )
  686. * \param dh_flag If 1, then (X-1)/2 will be prime too
  687. * \param f_rng RNG function
  688. * \param p_rng RNG parameter
  689. *
  690. * \return 0 if successful (probably prime),
  691. * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed,
  692. * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if nbits is < 3
  693. */
  694. int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
  695. int (*f_rng)(void *, unsigned char *, size_t),
  696. void *p_rng );
  697. /**
  698. * \brief Checkup routine
  699. *
  700. * \return 0 if successful, or 1 if the test failed
  701. */
  702. int mbedtls_mpi_self_test( int verbose );
  703. #ifdef __cplusplus
  704. }
  705. #endif
  706. #endif /* bignum.h */