bignum.c 67 KB

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