bignum.c 59 KB

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