ecp.c 114 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647
  1. /*
  2. * Elliptic curves over GF(p): generic functions
  3. *
  4. * Copyright The Mbed TLS Contributors
  5. * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
  6. */
  7. /*
  8. * References:
  9. *
  10. * SEC1 https://www.secg.org/sec1-v2.pdf
  11. * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
  12. * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
  13. * RFC 4492 for the related TLS structures and constants
  14. * - https://www.rfc-editor.org/rfc/rfc4492
  15. * RFC 7748 for the Curve448 and Curve25519 curve definitions
  16. * - https://www.rfc-editor.org/rfc/rfc7748
  17. *
  18. * [Curve25519] https://cr.yp.to/ecdh/curve25519-20060209.pdf
  19. *
  20. * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
  21. * for elliptic curve cryptosystems. In : Cryptographic Hardware and
  22. * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
  23. * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
  24. *
  25. * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
  26. * render ECC resistant against Side Channel Attacks. IACR Cryptology
  27. * ePrint Archive, 2004, vol. 2004, p. 342.
  28. * <http://eprint.iacr.org/2004/342.pdf>
  29. */
  30. #include "common.h"
  31. /**
  32. * \brief Function level alternative implementation.
  33. *
  34. * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to
  35. * replace certain functions in this module. The alternative implementations are
  36. * typically hardware accelerators and need to activate the hardware before the
  37. * computation starts and deactivate it after it finishes. The
  38. * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve
  39. * this purpose.
  40. *
  41. * To preserve the correct functionality the following conditions must hold:
  42. *
  43. * - The alternative implementation must be activated by
  44. * mbedtls_internal_ecp_init() before any of the replaceable functions is
  45. * called.
  46. * - mbedtls_internal_ecp_free() must \b only be called when the alternative
  47. * implementation is activated.
  48. * - mbedtls_internal_ecp_init() must \b not be called when the alternative
  49. * implementation is activated.
  50. * - Public functions must not return while the alternative implementation is
  51. * activated.
  52. * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and
  53. * before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) )
  54. * \endcode ensures that the alternative implementation supports the current
  55. * group.
  56. */
  57. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  58. #endif
  59. #if defined(MBEDTLS_ECP_C)
  60. #include "mbedtls/ecp.h"
  61. #include "mbedtls/threading.h"
  62. #include "mbedtls/platform_util.h"
  63. #include "mbedtls/error.h"
  64. #include "mbedtls/bn_mul.h"
  65. #include "ecp_invasive.h"
  66. #include <string.h>
  67. #if !defined(MBEDTLS_ECP_ALT)
  68. /* Parameter validation macros based on platform_util.h */
  69. #define ECP_VALIDATE_RET(cond) \
  70. MBEDTLS_INTERNAL_VALIDATE_RET(cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA)
  71. #define ECP_VALIDATE(cond) \
  72. MBEDTLS_INTERNAL_VALIDATE(cond)
  73. #include "mbedtls/platform.h"
  74. #include "mbedtls/ecp_internal.h"
  75. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  76. #if defined(MBEDTLS_HMAC_DRBG_C)
  77. #include "mbedtls/hmac_drbg.h"
  78. #elif defined(MBEDTLS_CTR_DRBG_C)
  79. #include "mbedtls/ctr_drbg.h"
  80. #else
  81. #error \
  82. "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
  83. #endif
  84. #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
  85. #if defined(MBEDTLS_SELF_TEST)
  86. /*
  87. * Counts of point addition and doubling, and field multiplications.
  88. * Used to test resistance of point multiplication to simple timing attacks.
  89. */
  90. static unsigned long add_count, dbl_count, mul_count;
  91. #endif
  92. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  93. /*
  94. * Currently ecp_mul() takes a RNG function as an argument, used for
  95. * side-channel protection, but it can be NULL. The initial reasoning was
  96. * that people will pass non-NULL RNG when they care about side-channels, but
  97. * unfortunately we have some APIs that call ecp_mul() with a NULL RNG, with
  98. * no opportunity for the user to do anything about it.
  99. *
  100. * The obvious strategies for addressing that include:
  101. * - change those APIs so that they take RNG arguments;
  102. * - require a global RNG to be available to all crypto modules.
  103. *
  104. * Unfortunately those would break compatibility. So what we do instead is
  105. * have our own internal DRBG instance, seeded from the secret scalar.
  106. *
  107. * The following is a light-weight abstraction layer for doing that with
  108. * HMAC_DRBG (first choice) or CTR_DRBG.
  109. */
  110. #if defined(MBEDTLS_HMAC_DRBG_C)
  111. /* DRBG context type */
  112. typedef mbedtls_hmac_drbg_context ecp_drbg_context;
  113. /* DRBG context init */
  114. static inline void ecp_drbg_init(ecp_drbg_context *ctx)
  115. {
  116. mbedtls_hmac_drbg_init(ctx);
  117. }
  118. /* DRBG context free */
  119. static inline void ecp_drbg_free(ecp_drbg_context *ctx)
  120. {
  121. mbedtls_hmac_drbg_free(ctx);
  122. }
  123. /* DRBG function */
  124. static inline int ecp_drbg_random(void *p_rng,
  125. unsigned char *output, size_t output_len)
  126. {
  127. return mbedtls_hmac_drbg_random(p_rng, output, output_len);
  128. }
  129. /* DRBG context seeding */
  130. static int ecp_drbg_seed(ecp_drbg_context *ctx,
  131. const mbedtls_mpi *secret, size_t secret_len)
  132. {
  133. int ret;
  134. unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
  135. /* The list starts with strong hashes */
  136. const mbedtls_md_type_t md_type =
  137. (mbedtls_md_type_t) (mbedtls_md_list()[0]);
  138. const mbedtls_md_info_t *md_info = mbedtls_md_info_from_type(md_type);
  139. if (secret_len > MBEDTLS_ECP_MAX_BYTES) {
  140. ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
  141. goto cleanup;
  142. }
  143. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(secret,
  144. secret_bytes, secret_len));
  145. ret = mbedtls_hmac_drbg_seed_buf(ctx, md_info, secret_bytes, secret_len);
  146. cleanup:
  147. mbedtls_platform_zeroize(secret_bytes, secret_len);
  148. return ret;
  149. }
  150. #elif defined(MBEDTLS_CTR_DRBG_C)
  151. /* DRBG context type */
  152. typedef mbedtls_ctr_drbg_context ecp_drbg_context;
  153. /* DRBG context init */
  154. static inline void ecp_drbg_init(ecp_drbg_context *ctx)
  155. {
  156. mbedtls_ctr_drbg_init(ctx);
  157. }
  158. /* DRBG context free */
  159. static inline void ecp_drbg_free(ecp_drbg_context *ctx)
  160. {
  161. mbedtls_ctr_drbg_free(ctx);
  162. }
  163. /* DRBG function */
  164. static inline int ecp_drbg_random(void *p_rng,
  165. unsigned char *output, size_t output_len)
  166. {
  167. return mbedtls_ctr_drbg_random(p_rng, output, output_len);
  168. }
  169. /*
  170. * Since CTR_DRBG doesn't have a seed_buf() function the way HMAC_DRBG does,
  171. * we need to pass an entropy function when seeding. So we use a dummy
  172. * function for that, and pass the actual entropy as customisation string.
  173. * (During seeding of CTR_DRBG the entropy input and customisation string are
  174. * concatenated before being used to update the secret state.)
  175. */
  176. static int ecp_ctr_drbg_null_entropy(void *ctx, unsigned char *out, size_t len)
  177. {
  178. (void) ctx;
  179. memset(out, 0, len);
  180. return 0;
  181. }
  182. /* DRBG context seeding */
  183. static int ecp_drbg_seed(ecp_drbg_context *ctx,
  184. const mbedtls_mpi *secret, size_t secret_len)
  185. {
  186. int ret;
  187. unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
  188. if (secret_len > MBEDTLS_ECP_MAX_BYTES) {
  189. ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
  190. goto cleanup;
  191. }
  192. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(secret,
  193. secret_bytes, secret_len));
  194. ret = mbedtls_ctr_drbg_seed(ctx, ecp_ctr_drbg_null_entropy, NULL,
  195. secret_bytes, secret_len);
  196. cleanup:
  197. mbedtls_platform_zeroize(secret_bytes, secret_len);
  198. return ret;
  199. }
  200. #else
  201. #error \
  202. "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
  203. #endif /* DRBG modules */
  204. #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
  205. #if defined(MBEDTLS_ECP_RESTARTABLE)
  206. /*
  207. * Maximum number of "basic operations" to be done in a row.
  208. *
  209. * Default value 0 means that ECC operations will not yield.
  210. * Note that regardless of the value of ecp_max_ops, always at
  211. * least one step is performed before yielding.
  212. *
  213. * Setting ecp_max_ops=1 can be suitable for testing purposes
  214. * as it will interrupt computation at all possible points.
  215. */
  216. static unsigned ecp_max_ops = 0;
  217. /*
  218. * Set ecp_max_ops
  219. */
  220. void mbedtls_ecp_set_max_ops(unsigned max_ops)
  221. {
  222. ecp_max_ops = max_ops;
  223. }
  224. /*
  225. * Check if restart is enabled
  226. */
  227. int mbedtls_ecp_restart_is_enabled(void)
  228. {
  229. return ecp_max_ops != 0;
  230. }
  231. /*
  232. * Restart sub-context for ecp_mul_comb()
  233. */
  234. struct mbedtls_ecp_restart_mul {
  235. mbedtls_ecp_point R; /* current intermediate result */
  236. size_t i; /* current index in various loops, 0 outside */
  237. mbedtls_ecp_point *T; /* table for precomputed points */
  238. unsigned char T_size; /* number of points in table T */
  239. enum { /* what were we doing last time we returned? */
  240. ecp_rsm_init = 0, /* nothing so far, dummy initial state */
  241. ecp_rsm_pre_dbl, /* precompute 2^n multiples */
  242. ecp_rsm_pre_norm_dbl, /* normalize precomputed 2^n multiples */
  243. ecp_rsm_pre_add, /* precompute remaining points by adding */
  244. ecp_rsm_pre_norm_add, /* normalize all precomputed points */
  245. ecp_rsm_comb_core, /* ecp_mul_comb_core() */
  246. ecp_rsm_final_norm, /* do the final normalization */
  247. } state;
  248. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  249. ecp_drbg_context drbg_ctx;
  250. unsigned char drbg_seeded;
  251. #endif
  252. };
  253. /*
  254. * Init restart_mul sub-context
  255. */
  256. static void ecp_restart_rsm_init(mbedtls_ecp_restart_mul_ctx *ctx)
  257. {
  258. mbedtls_ecp_point_init(&ctx->R);
  259. ctx->i = 0;
  260. ctx->T = NULL;
  261. ctx->T_size = 0;
  262. ctx->state = ecp_rsm_init;
  263. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  264. ecp_drbg_init(&ctx->drbg_ctx);
  265. ctx->drbg_seeded = 0;
  266. #endif
  267. }
  268. /*
  269. * Free the components of a restart_mul sub-context
  270. */
  271. static void ecp_restart_rsm_free(mbedtls_ecp_restart_mul_ctx *ctx)
  272. {
  273. unsigned char i;
  274. if (ctx == NULL) {
  275. return;
  276. }
  277. mbedtls_ecp_point_free(&ctx->R);
  278. if (ctx->T != NULL) {
  279. for (i = 0; i < ctx->T_size; i++) {
  280. mbedtls_ecp_point_free(ctx->T + i);
  281. }
  282. mbedtls_free(ctx->T);
  283. }
  284. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  285. ecp_drbg_free(&ctx->drbg_ctx);
  286. #endif
  287. ecp_restart_rsm_init(ctx);
  288. }
  289. /*
  290. * Restart context for ecp_muladd()
  291. */
  292. struct mbedtls_ecp_restart_muladd {
  293. mbedtls_ecp_point mP; /* mP value */
  294. mbedtls_ecp_point R; /* R intermediate result */
  295. enum { /* what should we do next? */
  296. ecp_rsma_mul1 = 0, /* first multiplication */
  297. ecp_rsma_mul2, /* second multiplication */
  298. ecp_rsma_add, /* addition */
  299. ecp_rsma_norm, /* normalization */
  300. } state;
  301. };
  302. /*
  303. * Init restart_muladd sub-context
  304. */
  305. static void ecp_restart_ma_init(mbedtls_ecp_restart_muladd_ctx *ctx)
  306. {
  307. mbedtls_ecp_point_init(&ctx->mP);
  308. mbedtls_ecp_point_init(&ctx->R);
  309. ctx->state = ecp_rsma_mul1;
  310. }
  311. /*
  312. * Free the components of a restart_muladd sub-context
  313. */
  314. static void ecp_restart_ma_free(mbedtls_ecp_restart_muladd_ctx *ctx)
  315. {
  316. if (ctx == NULL) {
  317. return;
  318. }
  319. mbedtls_ecp_point_free(&ctx->mP);
  320. mbedtls_ecp_point_free(&ctx->R);
  321. ecp_restart_ma_init(ctx);
  322. }
  323. /*
  324. * Initialize a restart context
  325. */
  326. void mbedtls_ecp_restart_init(mbedtls_ecp_restart_ctx *ctx)
  327. {
  328. ECP_VALIDATE(ctx != NULL);
  329. ctx->ops_done = 0;
  330. ctx->depth = 0;
  331. ctx->rsm = NULL;
  332. ctx->ma = NULL;
  333. }
  334. /*
  335. * Free the components of a restart context
  336. */
  337. void mbedtls_ecp_restart_free(mbedtls_ecp_restart_ctx *ctx)
  338. {
  339. if (ctx == NULL) {
  340. return;
  341. }
  342. ecp_restart_rsm_free(ctx->rsm);
  343. mbedtls_free(ctx->rsm);
  344. ecp_restart_ma_free(ctx->ma);
  345. mbedtls_free(ctx->ma);
  346. mbedtls_ecp_restart_init(ctx);
  347. }
  348. /*
  349. * Check if we can do the next step
  350. */
  351. int mbedtls_ecp_check_budget(const mbedtls_ecp_group *grp,
  352. mbedtls_ecp_restart_ctx *rs_ctx,
  353. unsigned ops)
  354. {
  355. ECP_VALIDATE_RET(grp != NULL);
  356. if (rs_ctx != NULL && ecp_max_ops != 0) {
  357. /* scale depending on curve size: the chosen reference is 256-bit,
  358. * and multiplication is quadratic. Round to the closest integer. */
  359. if (grp->pbits >= 512) {
  360. ops *= 4;
  361. } else if (grp->pbits >= 384) {
  362. ops *= 2;
  363. }
  364. /* Avoid infinite loops: always allow first step.
  365. * Because of that, however, it's not generally true
  366. * that ops_done <= ecp_max_ops, so the check
  367. * ops_done > ecp_max_ops below is mandatory. */
  368. if ((rs_ctx->ops_done != 0) &&
  369. (rs_ctx->ops_done > ecp_max_ops ||
  370. ops > ecp_max_ops - rs_ctx->ops_done)) {
  371. return MBEDTLS_ERR_ECP_IN_PROGRESS;
  372. }
  373. /* update running count */
  374. rs_ctx->ops_done += ops;
  375. }
  376. return 0;
  377. }
  378. /* Call this when entering a function that needs its own sub-context */
  379. #define ECP_RS_ENTER(SUB) do { \
  380. /* reset ops count for this call if top-level */ \
  381. if (rs_ctx != NULL && rs_ctx->depth++ == 0) \
  382. rs_ctx->ops_done = 0; \
  383. \
  384. /* set up our own sub-context if needed */ \
  385. if (mbedtls_ecp_restart_is_enabled() && \
  386. rs_ctx != NULL && rs_ctx->SUB == NULL) \
  387. { \
  388. rs_ctx->SUB = mbedtls_calloc(1, sizeof(*rs_ctx->SUB)); \
  389. if (rs_ctx->SUB == NULL) \
  390. return MBEDTLS_ERR_ECP_ALLOC_FAILED; \
  391. \
  392. ecp_restart_## SUB ##_init(rs_ctx->SUB); \
  393. } \
  394. } while (0)
  395. /* Call this when leaving a function that needs its own sub-context */
  396. #define ECP_RS_LEAVE(SUB) do { \
  397. /* clear our sub-context when not in progress (done or error) */ \
  398. if (rs_ctx != NULL && rs_ctx->SUB != NULL && \
  399. ret != MBEDTLS_ERR_ECP_IN_PROGRESS) \
  400. { \
  401. ecp_restart_## SUB ##_free(rs_ctx->SUB); \
  402. mbedtls_free(rs_ctx->SUB); \
  403. rs_ctx->SUB = NULL; \
  404. } \
  405. \
  406. if (rs_ctx != NULL) \
  407. rs_ctx->depth--; \
  408. } while (0)
  409. #else /* MBEDTLS_ECP_RESTARTABLE */
  410. #define ECP_RS_ENTER(sub) (void) rs_ctx;
  411. #define ECP_RS_LEAVE(sub) (void) rs_ctx;
  412. #endif /* MBEDTLS_ECP_RESTARTABLE */
  413. /*
  414. * List of supported curves:
  415. * - internal ID
  416. * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2, RFC 8446 sec. 4.2.7)
  417. * - size in bits
  418. * - readable name
  419. *
  420. * Curves are listed in order: largest curves first, and for a given size,
  421. * fastest curves first. This provides the default order for the SSL module.
  422. *
  423. * Reminder: update profiles in x509_crt.c when adding a new curves!
  424. */
  425. static const mbedtls_ecp_curve_info ecp_supported_curves[] =
  426. {
  427. #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
  428. { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
  429. #endif
  430. #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
  431. { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
  432. #endif
  433. #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
  434. { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
  435. #endif
  436. #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
  437. { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
  438. #endif
  439. #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
  440. { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
  441. #endif
  442. #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
  443. { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
  444. #endif
  445. #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
  446. { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
  447. #endif
  448. #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
  449. { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
  450. #endif
  451. #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
  452. { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
  453. #endif
  454. #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
  455. { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
  456. #endif
  457. #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
  458. { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
  459. #endif
  460. #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
  461. { MBEDTLS_ECP_DP_CURVE25519, 29, 256, "x25519" },
  462. #endif
  463. #if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
  464. { MBEDTLS_ECP_DP_CURVE448, 30, 448, "x448" },
  465. #endif
  466. { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
  467. };
  468. #define ECP_NB_CURVES sizeof(ecp_supported_curves) / \
  469. sizeof(ecp_supported_curves[0])
  470. static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
  471. /*
  472. * List of supported curves and associated info
  473. */
  474. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list(void)
  475. {
  476. return ecp_supported_curves;
  477. }
  478. /*
  479. * List of supported curves, group ID only
  480. */
  481. const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list(void)
  482. {
  483. static int init_done = 0;
  484. if (!init_done) {
  485. size_t i = 0;
  486. const mbedtls_ecp_curve_info *curve_info;
  487. for (curve_info = mbedtls_ecp_curve_list();
  488. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  489. curve_info++) {
  490. ecp_supported_grp_id[i++] = curve_info->grp_id;
  491. }
  492. ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
  493. init_done = 1;
  494. }
  495. return ecp_supported_grp_id;
  496. }
  497. /*
  498. * Get the curve info for the internal identifier
  499. */
  500. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id(mbedtls_ecp_group_id grp_id)
  501. {
  502. const mbedtls_ecp_curve_info *curve_info;
  503. for (curve_info = mbedtls_ecp_curve_list();
  504. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  505. curve_info++) {
  506. if (curve_info->grp_id == grp_id) {
  507. return curve_info;
  508. }
  509. }
  510. return NULL;
  511. }
  512. /*
  513. * Get the curve info from the TLS identifier
  514. */
  515. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id(uint16_t tls_id)
  516. {
  517. const mbedtls_ecp_curve_info *curve_info;
  518. for (curve_info = mbedtls_ecp_curve_list();
  519. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  520. curve_info++) {
  521. if (curve_info->tls_id == tls_id) {
  522. return curve_info;
  523. }
  524. }
  525. return NULL;
  526. }
  527. /*
  528. * Get the curve info from the name
  529. */
  530. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name(const char *name)
  531. {
  532. const mbedtls_ecp_curve_info *curve_info;
  533. if (name == NULL) {
  534. return NULL;
  535. }
  536. for (curve_info = mbedtls_ecp_curve_list();
  537. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  538. curve_info++) {
  539. if (strcmp(curve_info->name, name) == 0) {
  540. return curve_info;
  541. }
  542. }
  543. return NULL;
  544. }
  545. /*
  546. * Get the type of a curve
  547. */
  548. mbedtls_ecp_curve_type mbedtls_ecp_get_type(const mbedtls_ecp_group *grp)
  549. {
  550. if (grp->G.X.p == NULL) {
  551. return MBEDTLS_ECP_TYPE_NONE;
  552. }
  553. if (grp->G.Y.p == NULL) {
  554. return MBEDTLS_ECP_TYPE_MONTGOMERY;
  555. } else {
  556. return MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS;
  557. }
  558. }
  559. /*
  560. * Initialize (the components of) a point
  561. */
  562. void mbedtls_ecp_point_init(mbedtls_ecp_point *pt)
  563. {
  564. ECP_VALIDATE(pt != NULL);
  565. mbedtls_mpi_init(&pt->X);
  566. mbedtls_mpi_init(&pt->Y);
  567. mbedtls_mpi_init(&pt->Z);
  568. }
  569. /*
  570. * Initialize (the components of) a group
  571. */
  572. void mbedtls_ecp_group_init(mbedtls_ecp_group *grp)
  573. {
  574. ECP_VALIDATE(grp != NULL);
  575. grp->id = MBEDTLS_ECP_DP_NONE;
  576. mbedtls_mpi_init(&grp->P);
  577. mbedtls_mpi_init(&grp->A);
  578. mbedtls_mpi_init(&grp->B);
  579. mbedtls_ecp_point_init(&grp->G);
  580. mbedtls_mpi_init(&grp->N);
  581. grp->pbits = 0;
  582. grp->nbits = 0;
  583. grp->h = 0;
  584. grp->modp = NULL;
  585. grp->t_pre = NULL;
  586. grp->t_post = NULL;
  587. grp->t_data = NULL;
  588. grp->T = NULL;
  589. grp->T_size = 0;
  590. }
  591. /*
  592. * Initialize (the components of) a key pair
  593. */
  594. void mbedtls_ecp_keypair_init(mbedtls_ecp_keypair *key)
  595. {
  596. ECP_VALIDATE(key != NULL);
  597. mbedtls_ecp_group_init(&key->grp);
  598. mbedtls_mpi_init(&key->d);
  599. mbedtls_ecp_point_init(&key->Q);
  600. }
  601. /*
  602. * Unallocate (the components of) a point
  603. */
  604. void mbedtls_ecp_point_free(mbedtls_ecp_point *pt)
  605. {
  606. if (pt == NULL) {
  607. return;
  608. }
  609. mbedtls_mpi_free(&(pt->X));
  610. mbedtls_mpi_free(&(pt->Y));
  611. mbedtls_mpi_free(&(pt->Z));
  612. }
  613. /*
  614. * Unallocate (the components of) a group
  615. */
  616. void mbedtls_ecp_group_free(mbedtls_ecp_group *grp)
  617. {
  618. size_t i;
  619. if (grp == NULL) {
  620. return;
  621. }
  622. if (grp->h != 1) {
  623. mbedtls_mpi_free(&grp->P);
  624. mbedtls_mpi_free(&grp->A);
  625. mbedtls_mpi_free(&grp->B);
  626. mbedtls_ecp_point_free(&grp->G);
  627. mbedtls_mpi_free(&grp->N);
  628. }
  629. if (grp->T != NULL) {
  630. for (i = 0; i < grp->T_size; i++) {
  631. mbedtls_ecp_point_free(&grp->T[i]);
  632. }
  633. mbedtls_free(grp->T);
  634. }
  635. mbedtls_platform_zeroize(grp, sizeof(mbedtls_ecp_group));
  636. }
  637. /*
  638. * Unallocate (the components of) a key pair
  639. */
  640. void mbedtls_ecp_keypair_free(mbedtls_ecp_keypair *key)
  641. {
  642. if (key == NULL) {
  643. return;
  644. }
  645. mbedtls_ecp_group_free(&key->grp);
  646. mbedtls_mpi_free(&key->d);
  647. mbedtls_ecp_point_free(&key->Q);
  648. }
  649. /*
  650. * Copy the contents of a point
  651. */
  652. int mbedtls_ecp_copy(mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
  653. {
  654. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  655. ECP_VALIDATE_RET(P != NULL);
  656. ECP_VALIDATE_RET(Q != NULL);
  657. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->X, &Q->X));
  658. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Y, &Q->Y));
  659. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Z, &Q->Z));
  660. cleanup:
  661. return ret;
  662. }
  663. /*
  664. * Copy the contents of a group object
  665. */
  666. int mbedtls_ecp_group_copy(mbedtls_ecp_group *dst, const mbedtls_ecp_group *src)
  667. {
  668. ECP_VALIDATE_RET(dst != NULL);
  669. ECP_VALIDATE_RET(src != NULL);
  670. return mbedtls_ecp_group_load(dst, src->id);
  671. }
  672. /*
  673. * Set point to zero
  674. */
  675. int mbedtls_ecp_set_zero(mbedtls_ecp_point *pt)
  676. {
  677. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  678. ECP_VALIDATE_RET(pt != NULL);
  679. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->X, 1));
  680. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Y, 1));
  681. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 0));
  682. cleanup:
  683. return ret;
  684. }
  685. /*
  686. * Tell if a point is zero
  687. */
  688. int mbedtls_ecp_is_zero(mbedtls_ecp_point *pt)
  689. {
  690. ECP_VALIDATE_RET(pt != NULL);
  691. return mbedtls_mpi_cmp_int(&pt->Z, 0) == 0;
  692. }
  693. /*
  694. * Compare two points lazily
  695. */
  696. int mbedtls_ecp_point_cmp(const mbedtls_ecp_point *P,
  697. const mbedtls_ecp_point *Q)
  698. {
  699. ECP_VALIDATE_RET(P != NULL);
  700. ECP_VALIDATE_RET(Q != NULL);
  701. if (mbedtls_mpi_cmp_mpi(&P->X, &Q->X) == 0 &&
  702. mbedtls_mpi_cmp_mpi(&P->Y, &Q->Y) == 0 &&
  703. mbedtls_mpi_cmp_mpi(&P->Z, &Q->Z) == 0) {
  704. return 0;
  705. }
  706. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  707. }
  708. /*
  709. * Import a non-zero point from ASCII strings
  710. */
  711. int mbedtls_ecp_point_read_string(mbedtls_ecp_point *P, int radix,
  712. const char *x, const char *y)
  713. {
  714. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  715. ECP_VALIDATE_RET(P != NULL);
  716. ECP_VALIDATE_RET(x != NULL);
  717. ECP_VALIDATE_RET(y != NULL);
  718. MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->X, radix, x));
  719. MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->Y, radix, y));
  720. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&P->Z, 1));
  721. cleanup:
  722. return ret;
  723. }
  724. /*
  725. * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748)
  726. */
  727. int mbedtls_ecp_point_write_binary(const mbedtls_ecp_group *grp,
  728. const mbedtls_ecp_point *P,
  729. int format, size_t *olen,
  730. unsigned char *buf, size_t buflen)
  731. {
  732. int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  733. size_t plen;
  734. ECP_VALIDATE_RET(grp != NULL);
  735. ECP_VALIDATE_RET(P != NULL);
  736. ECP_VALIDATE_RET(olen != NULL);
  737. ECP_VALIDATE_RET(buf != NULL);
  738. ECP_VALIDATE_RET(format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
  739. format == MBEDTLS_ECP_PF_COMPRESSED);
  740. plen = mbedtls_mpi_size(&grp->P);
  741. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  742. (void) format; /* Montgomery curves always use the same point format */
  743. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  744. *olen = plen;
  745. if (buflen < *olen) {
  746. return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
  747. }
  748. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&P->X, buf, plen));
  749. }
  750. #endif
  751. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  752. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  753. /*
  754. * Common case: P == 0
  755. */
  756. if (mbedtls_mpi_cmp_int(&P->Z, 0) == 0) {
  757. if (buflen < 1) {
  758. return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
  759. }
  760. buf[0] = 0x00;
  761. *olen = 1;
  762. return 0;
  763. }
  764. if (format == MBEDTLS_ECP_PF_UNCOMPRESSED) {
  765. *olen = 2 * plen + 1;
  766. if (buflen < *olen) {
  767. return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
  768. }
  769. buf[0] = 0x04;
  770. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen));
  771. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->Y, buf + 1 + plen, plen));
  772. } else if (format == MBEDTLS_ECP_PF_COMPRESSED) {
  773. *olen = plen + 1;
  774. if (buflen < *olen) {
  775. return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
  776. }
  777. buf[0] = 0x02 + mbedtls_mpi_get_bit(&P->Y, 0);
  778. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen));
  779. }
  780. }
  781. #endif
  782. cleanup:
  783. return ret;
  784. }
  785. /*
  786. * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748)
  787. */
  788. int mbedtls_ecp_point_read_binary(const mbedtls_ecp_group *grp,
  789. mbedtls_ecp_point *pt,
  790. const unsigned char *buf, size_t ilen)
  791. {
  792. int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  793. size_t plen;
  794. ECP_VALIDATE_RET(grp != NULL);
  795. ECP_VALIDATE_RET(pt != NULL);
  796. ECP_VALIDATE_RET(ilen == 0 || buf != NULL);
  797. if (ilen < 1) {
  798. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  799. }
  800. plen = mbedtls_mpi_size(&grp->P);
  801. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  802. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  803. if (plen != ilen) {
  804. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  805. }
  806. MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&pt->X, buf, plen));
  807. mbedtls_mpi_free(&pt->Y);
  808. if (grp->id == MBEDTLS_ECP_DP_CURVE25519) {
  809. /* Set most significant bit to 0 as prescribed in RFC7748 §5 */
  810. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&pt->X, plen * 8 - 1, 0));
  811. }
  812. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
  813. }
  814. #endif
  815. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  816. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  817. if (buf[0] == 0x00) {
  818. if (ilen == 1) {
  819. return mbedtls_ecp_set_zero(pt);
  820. } else {
  821. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  822. }
  823. }
  824. if (buf[0] != 0x04) {
  825. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  826. }
  827. if (ilen != 2 * plen + 1) {
  828. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  829. }
  830. MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&pt->X, buf + 1, plen));
  831. MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&pt->Y,
  832. buf + 1 + plen, plen));
  833. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
  834. }
  835. #endif
  836. cleanup:
  837. return ret;
  838. }
  839. /*
  840. * Import a point from a TLS ECPoint record (RFC 4492)
  841. * struct {
  842. * opaque point <1..2^8-1>;
  843. * } ECPoint;
  844. */
  845. int mbedtls_ecp_tls_read_point(const mbedtls_ecp_group *grp,
  846. mbedtls_ecp_point *pt,
  847. const unsigned char **buf, size_t buf_len)
  848. {
  849. unsigned char data_len;
  850. const unsigned char *buf_start;
  851. ECP_VALIDATE_RET(grp != NULL);
  852. ECP_VALIDATE_RET(pt != NULL);
  853. ECP_VALIDATE_RET(buf != NULL);
  854. ECP_VALIDATE_RET(buf_len == 0 || *buf != NULL);
  855. /*
  856. * We must have at least two bytes (1 for length, at least one for data)
  857. */
  858. if (buf_len < 2) {
  859. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  860. }
  861. data_len = *(*buf)++;
  862. if (data_len < 1 || data_len > buf_len - 1) {
  863. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  864. }
  865. /*
  866. * Save buffer start for read_binary and update buf
  867. */
  868. buf_start = *buf;
  869. *buf += data_len;
  870. return mbedtls_ecp_point_read_binary(grp, pt, buf_start, data_len);
  871. }
  872. /*
  873. * Export a point as a TLS ECPoint record (RFC 4492)
  874. * struct {
  875. * opaque point <1..2^8-1>;
  876. * } ECPoint;
  877. */
  878. int mbedtls_ecp_tls_write_point(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
  879. int format, size_t *olen,
  880. unsigned char *buf, size_t blen)
  881. {
  882. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  883. ECP_VALIDATE_RET(grp != NULL);
  884. ECP_VALIDATE_RET(pt != NULL);
  885. ECP_VALIDATE_RET(olen != NULL);
  886. ECP_VALIDATE_RET(buf != NULL);
  887. ECP_VALIDATE_RET(format == MBEDTLS_ECP_PF_UNCOMPRESSED ||
  888. format == MBEDTLS_ECP_PF_COMPRESSED);
  889. /*
  890. * buffer length must be at least one, for our length byte
  891. */
  892. if (blen < 1) {
  893. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  894. }
  895. if ((ret = mbedtls_ecp_point_write_binary(grp, pt, format,
  896. olen, buf + 1, blen - 1)) != 0) {
  897. return ret;
  898. }
  899. /*
  900. * write length to the first byte and update total length
  901. */
  902. buf[0] = (unsigned char) *olen;
  903. ++*olen;
  904. return 0;
  905. }
  906. /*
  907. * Set a group from an ECParameters record (RFC 4492)
  908. */
  909. int mbedtls_ecp_tls_read_group(mbedtls_ecp_group *grp,
  910. const unsigned char **buf, size_t len)
  911. {
  912. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  913. mbedtls_ecp_group_id grp_id;
  914. ECP_VALIDATE_RET(grp != NULL);
  915. ECP_VALIDATE_RET(buf != NULL);
  916. ECP_VALIDATE_RET(len == 0 || *buf != NULL);
  917. if ((ret = mbedtls_ecp_tls_read_group_id(&grp_id, buf, len)) != 0) {
  918. return ret;
  919. }
  920. return mbedtls_ecp_group_load(grp, grp_id);
  921. }
  922. /*
  923. * Read a group id from an ECParameters record (RFC 4492) and convert it to
  924. * mbedtls_ecp_group_id.
  925. */
  926. int mbedtls_ecp_tls_read_group_id(mbedtls_ecp_group_id *grp,
  927. const unsigned char **buf, size_t len)
  928. {
  929. uint16_t tls_id;
  930. const mbedtls_ecp_curve_info *curve_info;
  931. ECP_VALIDATE_RET(grp != NULL);
  932. ECP_VALIDATE_RET(buf != NULL);
  933. ECP_VALIDATE_RET(len == 0 || *buf != NULL);
  934. /*
  935. * We expect at least three bytes (see below)
  936. */
  937. if (len < 3) {
  938. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  939. }
  940. /*
  941. * First byte is curve_type; only named_curve is handled
  942. */
  943. if (*(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE) {
  944. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  945. }
  946. /*
  947. * Next two bytes are the namedcurve value
  948. */
  949. tls_id = *(*buf)++;
  950. tls_id <<= 8;
  951. tls_id |= *(*buf)++;
  952. if ((curve_info = mbedtls_ecp_curve_info_from_tls_id(tls_id)) == NULL) {
  953. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  954. }
  955. *grp = curve_info->grp_id;
  956. return 0;
  957. }
  958. /*
  959. * Write the ECParameters record corresponding to a group (RFC 4492)
  960. */
  961. int mbedtls_ecp_tls_write_group(const mbedtls_ecp_group *grp, size_t *olen,
  962. unsigned char *buf, size_t blen)
  963. {
  964. const mbedtls_ecp_curve_info *curve_info;
  965. ECP_VALIDATE_RET(grp != NULL);
  966. ECP_VALIDATE_RET(buf != NULL);
  967. ECP_VALIDATE_RET(olen != NULL);
  968. if ((curve_info = mbedtls_ecp_curve_info_from_grp_id(grp->id)) == NULL) {
  969. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  970. }
  971. /*
  972. * We are going to write 3 bytes (see below)
  973. */
  974. *olen = 3;
  975. if (blen < *olen) {
  976. return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
  977. }
  978. /*
  979. * First byte is curve_type, always named_curve
  980. */
  981. *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
  982. /*
  983. * Next two bytes are the namedcurve value
  984. */
  985. MBEDTLS_PUT_UINT16_BE(curve_info->tls_id, buf, 0);
  986. return 0;
  987. }
  988. /*
  989. * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
  990. * See the documentation of struct mbedtls_ecp_group.
  991. *
  992. * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
  993. */
  994. static int ecp_modp(mbedtls_mpi *N, const mbedtls_ecp_group *grp)
  995. {
  996. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  997. if (grp->modp == NULL) {
  998. return mbedtls_mpi_mod_mpi(N, N, &grp->P);
  999. }
  1000. /* N->s < 0 is a much faster test, which fails only if N is 0 */
  1001. if ((N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) ||
  1002. mbedtls_mpi_bitlen(N) > 2 * grp->pbits) {
  1003. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  1004. }
  1005. MBEDTLS_MPI_CHK(grp->modp(N));
  1006. /* N->s < 0 is a much faster test, which fails only if N is 0 */
  1007. while (N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) {
  1008. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(N, N, &grp->P));
  1009. }
  1010. while (mbedtls_mpi_cmp_mpi(N, &grp->P) >= 0) {
  1011. /* we known P, N and the result are positive */
  1012. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(N, N, &grp->P));
  1013. }
  1014. cleanup:
  1015. return ret;
  1016. }
  1017. /*
  1018. * Fast mod-p functions expect their argument to be in the 0..p^2 range.
  1019. *
  1020. * In order to guarantee that, we need to ensure that operands of
  1021. * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
  1022. * bring the result back to this range.
  1023. *
  1024. * The following macros are shortcuts for doing that.
  1025. */
  1026. /*
  1027. * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
  1028. */
  1029. #if defined(MBEDTLS_SELF_TEST)
  1030. #define INC_MUL_COUNT mul_count++;
  1031. #else
  1032. #define INC_MUL_COUNT
  1033. #endif
  1034. #define MOD_MUL(N) \
  1035. do \
  1036. { \
  1037. MBEDTLS_MPI_CHK(ecp_modp(&(N), grp)); \
  1038. INC_MUL_COUNT \
  1039. } while (0)
  1040. static inline int mbedtls_mpi_mul_mod(const mbedtls_ecp_group *grp,
  1041. mbedtls_mpi *X,
  1042. const mbedtls_mpi *A,
  1043. const mbedtls_mpi *B)
  1044. {
  1045. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1046. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(X, A, B));
  1047. MOD_MUL(*X);
  1048. cleanup:
  1049. return ret;
  1050. }
  1051. /*
  1052. * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
  1053. * N->s < 0 is a very fast test, which fails only if N is 0
  1054. */
  1055. #define MOD_SUB(N) \
  1056. while ((N).s < 0 && mbedtls_mpi_cmp_int(&(N), 0) != 0) \
  1057. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&(N), &(N), &grp->P))
  1058. #if (defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \
  1059. !(defined(MBEDTLS_ECP_NO_FALLBACK) && \
  1060. defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \
  1061. defined(MBEDTLS_ECP_ADD_MIXED_ALT))) || \
  1062. (defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) && \
  1063. !(defined(MBEDTLS_ECP_NO_FALLBACK) && \
  1064. defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)))
  1065. static inline int mbedtls_mpi_sub_mod(const mbedtls_ecp_group *grp,
  1066. mbedtls_mpi *X,
  1067. const mbedtls_mpi *A,
  1068. const mbedtls_mpi *B)
  1069. {
  1070. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1071. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(X, A, B));
  1072. MOD_SUB(*X);
  1073. cleanup:
  1074. return ret;
  1075. }
  1076. #endif /* All functions referencing mbedtls_mpi_sub_mod() are alt-implemented without fallback */
  1077. /*
  1078. * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
  1079. * We known P, N and the result are positive, so sub_abs is correct, and
  1080. * a bit faster.
  1081. */
  1082. #define MOD_ADD(N) \
  1083. while (mbedtls_mpi_cmp_mpi(&(N), &grp->P) >= 0) \
  1084. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&(N), &(N), &grp->P))
  1085. static inline int mbedtls_mpi_add_mod(const mbedtls_ecp_group *grp,
  1086. mbedtls_mpi *X,
  1087. const mbedtls_mpi *A,
  1088. const mbedtls_mpi *B)
  1089. {
  1090. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1091. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, A, B));
  1092. MOD_ADD(*X);
  1093. cleanup:
  1094. return ret;
  1095. }
  1096. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \
  1097. !(defined(MBEDTLS_ECP_NO_FALLBACK) && \
  1098. defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \
  1099. defined(MBEDTLS_ECP_ADD_MIXED_ALT))
  1100. static inline int mbedtls_mpi_shift_l_mod(const mbedtls_ecp_group *grp,
  1101. mbedtls_mpi *X,
  1102. size_t count)
  1103. {
  1104. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1105. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, count));
  1106. MOD_ADD(*X);
  1107. cleanup:
  1108. return ret;
  1109. }
  1110. #endif \
  1111. /* All functions referencing mbedtls_mpi_shift_l_mod() are alt-implemented without fallback */
  1112. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  1113. /*
  1114. * For curves in short Weierstrass form, we do all the internal operations in
  1115. * Jacobian coordinates.
  1116. *
  1117. * For multiplication, we'll use a comb method with countermeasures against
  1118. * SPA, hence timing attacks.
  1119. */
  1120. /*
  1121. * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
  1122. * Cost: 1N := 1I + 3M + 1S
  1123. */
  1124. static int ecp_normalize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt)
  1125. {
  1126. if (mbedtls_mpi_cmp_int(&pt->Z, 0) == 0) {
  1127. return 0;
  1128. }
  1129. #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
  1130. if (mbedtls_internal_ecp_grp_capable(grp)) {
  1131. return mbedtls_internal_ecp_normalize_jac(grp, pt);
  1132. }
  1133. #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
  1134. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
  1135. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  1136. #else
  1137. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1138. mbedtls_mpi Zi, ZZi;
  1139. mbedtls_mpi_init(&Zi); mbedtls_mpi_init(&ZZi);
  1140. /*
  1141. * X = X / Z^2 mod p
  1142. */
  1143. MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&Zi, &pt->Z, &grp->P));
  1144. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ZZi, &Zi, &Zi));
  1145. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->X, &pt->X, &ZZi));
  1146. /*
  1147. * Y = Y / Z^3 mod p
  1148. */
  1149. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Y, &pt->Y, &ZZi));
  1150. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Y, &pt->Y, &Zi));
  1151. /*
  1152. * Z = 1
  1153. */
  1154. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
  1155. cleanup:
  1156. mbedtls_mpi_free(&Zi); mbedtls_mpi_free(&ZZi);
  1157. return ret;
  1158. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) */
  1159. }
  1160. /*
  1161. * Normalize jacobian coordinates of an array of (pointers to) points,
  1162. * using Montgomery's trick to perform only one inversion mod P.
  1163. * (See for example Cohen's "A Course in Computational Algebraic Number
  1164. * Theory", Algorithm 10.3.4.)
  1165. *
  1166. * Warning: fails (returning an error) if one of the points is zero!
  1167. * This should never happen, see choice of w in ecp_mul_comb().
  1168. *
  1169. * Cost: 1N(t) := 1I + (6t - 3)M + 1S
  1170. */
  1171. static int ecp_normalize_jac_many(const mbedtls_ecp_group *grp,
  1172. mbedtls_ecp_point *T[], size_t T_size)
  1173. {
  1174. if (T_size < 2) {
  1175. return ecp_normalize_jac(grp, *T);
  1176. }
  1177. #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
  1178. if (mbedtls_internal_ecp_grp_capable(grp)) {
  1179. return mbedtls_internal_ecp_normalize_jac_many(grp, T, T_size);
  1180. }
  1181. #endif
  1182. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
  1183. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  1184. #else
  1185. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1186. size_t i;
  1187. mbedtls_mpi *c, u, Zi, ZZi;
  1188. if ((c = mbedtls_calloc(T_size, sizeof(mbedtls_mpi))) == NULL) {
  1189. return MBEDTLS_ERR_ECP_ALLOC_FAILED;
  1190. }
  1191. for (i = 0; i < T_size; i++) {
  1192. mbedtls_mpi_init(&c[i]);
  1193. }
  1194. mbedtls_mpi_init(&u); mbedtls_mpi_init(&Zi); mbedtls_mpi_init(&ZZi);
  1195. /*
  1196. * c[i] = Z_0 * ... * Z_i
  1197. */
  1198. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&c[0], &T[0]->Z));
  1199. for (i = 1; i < T_size; i++) {
  1200. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &c[i], &c[i-1], &T[i]->Z));
  1201. }
  1202. /*
  1203. * u = 1 / (Z_0 * ... * Z_n) mod P
  1204. */
  1205. MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&u, &c[T_size-1], &grp->P));
  1206. for (i = T_size - 1;; i--) {
  1207. /*
  1208. * Zi = 1 / Z_i mod p
  1209. * u = 1 / (Z_0 * ... * Z_i) mod P
  1210. */
  1211. if (i == 0) {
  1212. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Zi, &u));
  1213. } else {
  1214. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &Zi, &u, &c[i-1]));
  1215. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &u, &u, &T[i]->Z));
  1216. }
  1217. /*
  1218. * proceed as in normalize()
  1219. */
  1220. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ZZi, &Zi, &Zi));
  1221. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T[i]->X, &T[i]->X, &ZZi));
  1222. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T[i]->Y, &T[i]->Y, &ZZi));
  1223. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T[i]->Y, &T[i]->Y, &Zi));
  1224. /*
  1225. * Post-precessing: reclaim some memory by shrinking coordinates
  1226. * - not storing Z (always 1)
  1227. * - shrinking other coordinates, but still keeping the same number of
  1228. * limbs as P, as otherwise it will too likely be regrown too fast.
  1229. */
  1230. MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->X, grp->P.n));
  1231. MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->Y, grp->P.n));
  1232. mbedtls_mpi_free(&T[i]->Z);
  1233. if (i == 0) {
  1234. break;
  1235. }
  1236. }
  1237. cleanup:
  1238. mbedtls_mpi_free(&u); mbedtls_mpi_free(&Zi); mbedtls_mpi_free(&ZZi);
  1239. for (i = 0; i < T_size; i++) {
  1240. mbedtls_mpi_free(&c[i]);
  1241. }
  1242. mbedtls_free(c);
  1243. return ret;
  1244. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) */
  1245. }
  1246. /*
  1247. * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
  1248. * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
  1249. */
  1250. static int ecp_safe_invert_jac(const mbedtls_ecp_group *grp,
  1251. mbedtls_ecp_point *Q,
  1252. unsigned char inv)
  1253. {
  1254. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1255. unsigned char nonzero;
  1256. mbedtls_mpi mQY;
  1257. mbedtls_mpi_init(&mQY);
  1258. /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
  1259. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&mQY, &grp->P, &Q->Y));
  1260. nonzero = mbedtls_mpi_cmp_int(&Q->Y, 0) != 0;
  1261. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&Q->Y, &mQY, inv & nonzero));
  1262. cleanup:
  1263. mbedtls_mpi_free(&mQY);
  1264. return ret;
  1265. }
  1266. /*
  1267. * Point doubling R = 2 P, Jacobian coordinates
  1268. *
  1269. * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
  1270. *
  1271. * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
  1272. * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
  1273. *
  1274. * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
  1275. *
  1276. * Cost: 1D := 3M + 4S (A == 0)
  1277. * 4M + 4S (A == -3)
  1278. * 3M + 6S + 1a otherwise
  1279. */
  1280. static int ecp_double_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1281. const mbedtls_ecp_point *P)
  1282. {
  1283. #if defined(MBEDTLS_SELF_TEST)
  1284. dbl_count++;
  1285. #endif
  1286. #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
  1287. if (mbedtls_internal_ecp_grp_capable(grp)) {
  1288. return mbedtls_internal_ecp_double_jac(grp, R, P);
  1289. }
  1290. #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
  1291. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
  1292. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  1293. #else
  1294. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1295. mbedtls_mpi M, S, T, U;
  1296. mbedtls_mpi_init(&M); mbedtls_mpi_init(&S); mbedtls_mpi_init(&T); mbedtls_mpi_init(&U);
  1297. /* Special case for A = -3 */
  1298. if (grp->A.p == NULL) {
  1299. /* M = 3(X + Z^2)(X - Z^2) */
  1300. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->Z, &P->Z));
  1301. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &T, &P->X, &S));
  1302. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &U, &P->X, &S));
  1303. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &T, &U));
  1304. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&M, &S, 3)); MOD_ADD(M);
  1305. } else {
  1306. /* M = 3.X^2 */
  1307. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->X, &P->X));
  1308. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&M, &S, 3)); MOD_ADD(M);
  1309. /* Optimize away for "koblitz" curves with A = 0 */
  1310. if (mbedtls_mpi_cmp_int(&grp->A, 0) != 0) {
  1311. /* M += A.Z^4 */
  1312. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->Z, &P->Z));
  1313. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T, &S, &S));
  1314. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &T, &grp->A));
  1315. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &M, &M, &S));
  1316. }
  1317. }
  1318. /* S = 4.X.Y^2 */
  1319. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T, &P->Y, &P->Y));
  1320. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &T, 1));
  1321. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &P->X, &T));
  1322. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &S, 1));
  1323. /* U = 8.Y^4 */
  1324. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &U, &T, &T));
  1325. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &U, 1));
  1326. /* T = M^2 - 2.S */
  1327. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T, &M, &M));
  1328. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T, &T, &S));
  1329. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T, &T, &S));
  1330. /* S = M(S - T) - U */
  1331. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &S, &S, &T));
  1332. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S, &S, &M));
  1333. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &S, &S, &U));
  1334. /* U = 2.Y.Z */
  1335. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &U, &P->Y, &P->Z));
  1336. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &U, 1));
  1337. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->X, &T));
  1338. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Y, &S));
  1339. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Z, &U));
  1340. cleanup:
  1341. mbedtls_mpi_free(&M); mbedtls_mpi_free(&S); mbedtls_mpi_free(&T); mbedtls_mpi_free(&U);
  1342. return ret;
  1343. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) */
  1344. }
  1345. /*
  1346. * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
  1347. *
  1348. * The coordinates of Q must be normalized (= affine),
  1349. * but those of P don't need to. R is not normalized.
  1350. *
  1351. * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
  1352. * None of these cases can happen as intermediate step in ecp_mul_comb():
  1353. * - at each step, P, Q and R are multiples of the base point, the factor
  1354. * being less than its order, so none of them is zero;
  1355. * - Q is an odd multiple of the base point, P an even multiple,
  1356. * due to the choice of precomputed points in the modified comb method.
  1357. * So branches for these cases do not leak secret information.
  1358. *
  1359. * We accept Q->Z being unset (saving memory in tables) as meaning 1.
  1360. *
  1361. * Cost: 1A := 8M + 3S
  1362. */
  1363. static int ecp_add_mixed(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1364. const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
  1365. {
  1366. #if defined(MBEDTLS_SELF_TEST)
  1367. add_count++;
  1368. #endif
  1369. #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
  1370. if (mbedtls_internal_ecp_grp_capable(grp)) {
  1371. return mbedtls_internal_ecp_add_mixed(grp, R, P, Q);
  1372. }
  1373. #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
  1374. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_ADD_MIXED_ALT)
  1375. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  1376. #else
  1377. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1378. mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
  1379. /*
  1380. * Trivial cases: P == 0 or Q == 0 (case 1)
  1381. */
  1382. if (mbedtls_mpi_cmp_int(&P->Z, 0) == 0) {
  1383. return mbedtls_ecp_copy(R, Q);
  1384. }
  1385. if (Q->Z.p != NULL && mbedtls_mpi_cmp_int(&Q->Z, 0) == 0) {
  1386. return mbedtls_ecp_copy(R, P);
  1387. }
  1388. /*
  1389. * Make sure Q coordinates are normalized
  1390. */
  1391. if (Q->Z.p != NULL && mbedtls_mpi_cmp_int(&Q->Z, 1) != 0) {
  1392. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  1393. }
  1394. mbedtls_mpi_init(&T1); mbedtls_mpi_init(&T2); mbedtls_mpi_init(&T3); mbedtls_mpi_init(&T4);
  1395. mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
  1396. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T1, &P->Z, &P->Z));
  1397. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T2, &T1, &P->Z));
  1398. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T1, &T1, &Q->X));
  1399. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T2, &T2, &Q->Y));
  1400. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T1, &T1, &P->X));
  1401. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T2, &T2, &P->Y));
  1402. /* Special cases (2) and (3) */
  1403. if (mbedtls_mpi_cmp_int(&T1, 0) == 0) {
  1404. if (mbedtls_mpi_cmp_int(&T2, 0) == 0) {
  1405. ret = ecp_double_jac(grp, R, P);
  1406. goto cleanup;
  1407. } else {
  1408. ret = mbedtls_ecp_set_zero(R);
  1409. goto cleanup;
  1410. }
  1411. }
  1412. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &Z, &P->Z, &T1));
  1413. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T3, &T1, &T1));
  1414. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T4, &T3, &T1));
  1415. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T3, &T3, &P->X));
  1416. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &T3));
  1417. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, &T1, 1));
  1418. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &X, &T2, &T2));
  1419. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &X, &X, &T1));
  1420. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &X, &X, &T4));
  1421. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &T3, &T3, &X));
  1422. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T3, &T3, &T2));
  1423. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &T4, &T4, &P->Y));
  1424. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &Y, &T3, &T4));
  1425. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->X, &X));
  1426. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Y, &Y));
  1427. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R->Z, &Z));
  1428. cleanup:
  1429. mbedtls_mpi_free(&T1); mbedtls_mpi_free(&T2); mbedtls_mpi_free(&T3); mbedtls_mpi_free(&T4);
  1430. mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
  1431. return ret;
  1432. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_ADD_MIXED_ALT) */
  1433. }
  1434. /*
  1435. * Randomize jacobian coordinates:
  1436. * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
  1437. * This is sort of the reverse operation of ecp_normalize_jac().
  1438. *
  1439. * This countermeasure was first suggested in [2].
  1440. */
  1441. static int ecp_randomize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
  1442. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
  1443. {
  1444. #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
  1445. if (mbedtls_internal_ecp_grp_capable(grp)) {
  1446. return mbedtls_internal_ecp_randomize_jac(grp, pt, f_rng, p_rng);
  1447. }
  1448. #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
  1449. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
  1450. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  1451. #else
  1452. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1453. mbedtls_mpi l, ll;
  1454. mbedtls_mpi_init(&l); mbedtls_mpi_init(&ll);
  1455. /* Generate l such that 1 < l < p */
  1456. MBEDTLS_MPI_CHK(mbedtls_mpi_random(&l, 2, &grp->P, f_rng, p_rng));
  1457. /* Z = l * Z */
  1458. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Z, &pt->Z, &l));
  1459. /* X = l^2 * X */
  1460. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ll, &l, &l));
  1461. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->X, &pt->X, &ll));
  1462. /* Y = l^3 * Y */
  1463. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &ll, &ll, &l));
  1464. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &pt->Y, &pt->Y, &ll));
  1465. cleanup:
  1466. mbedtls_mpi_free(&l); mbedtls_mpi_free(&ll);
  1467. if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
  1468. ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
  1469. }
  1470. return ret;
  1471. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) */
  1472. }
  1473. /*
  1474. * Check and define parameters used by the comb method (see below for details)
  1475. */
  1476. #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
  1477. #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
  1478. #endif
  1479. /* d = ceil( n / w ) */
  1480. #define COMB_MAX_D (MBEDTLS_ECP_MAX_BITS + 1) / 2
  1481. /* number of precomputed points */
  1482. #define COMB_MAX_PRE (1 << (MBEDTLS_ECP_WINDOW_SIZE - 1))
  1483. /*
  1484. * Compute the representation of m that will be used with our comb method.
  1485. *
  1486. * The basic comb method is described in GECC 3.44 for example. We use a
  1487. * modified version that provides resistance to SPA by avoiding zero
  1488. * digits in the representation as in [3]. We modify the method further by
  1489. * requiring that all K_i be odd, which has the small cost that our
  1490. * representation uses one more K_i, due to carries, but saves on the size of
  1491. * the precomputed table.
  1492. *
  1493. * Summary of the comb method and its modifications:
  1494. *
  1495. * - The goal is to compute m*P for some w*d-bit integer m.
  1496. *
  1497. * - The basic comb method splits m into the w-bit integers
  1498. * x[0] .. x[d-1] where x[i] consists of the bits in m whose
  1499. * index has residue i modulo d, and computes m * P as
  1500. * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where
  1501. * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.
  1502. *
  1503. * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by
  1504. * .. + 2^{i-1} S[x[i-1]] - 2^i S[x[i]] + 2^{i+1} S[x[i]] + 2^{i+2} S[x[i+2]] ..,
  1505. * thereby successively converting it into a form where all summands
  1506. * are nonzero, at the cost of negative summands. This is the basic idea of [3].
  1507. *
  1508. * - More generally, even if x[i+1] != 0, we can first transform the sum as
  1509. * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,
  1510. * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].
  1511. * Performing and iterating this procedure for those x[i] that are even
  1512. * (keeping track of carry), we can transform the original sum into one of the form
  1513. * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]
  1514. * with all x'[i] odd. It is therefore only necessary to know S at odd indices,
  1515. * which is why we are only computing half of it in the first place in
  1516. * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.
  1517. *
  1518. * - For the sake of compactness, only the seven low-order bits of x[i]
  1519. * are used to represent its absolute value (K_i in the paper), and the msb
  1520. * of x[i] encodes the sign (s_i in the paper): it is set if and only if
  1521. * if s_i == -1;
  1522. *
  1523. * Calling conventions:
  1524. * - x is an array of size d + 1
  1525. * - w is the size, ie number of teeth, of the comb, and must be between
  1526. * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
  1527. * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
  1528. * (the result will be incorrect if these assumptions are not satisfied)
  1529. */
  1530. static void ecp_comb_recode_core(unsigned char x[], size_t d,
  1531. unsigned char w, const mbedtls_mpi *m)
  1532. {
  1533. size_t i, j;
  1534. unsigned char c, cc, adjust;
  1535. memset(x, 0, d+1);
  1536. /* First get the classical comb values (except for x_d = 0) */
  1537. for (i = 0; i < d; i++) {
  1538. for (j = 0; j < w; j++) {
  1539. x[i] |= mbedtls_mpi_get_bit(m, i + d * j) << j;
  1540. }
  1541. }
  1542. /* Now make sure x_1 .. x_d are odd */
  1543. c = 0;
  1544. for (i = 1; i <= d; i++) {
  1545. /* Add carry and update it */
  1546. cc = x[i] & c;
  1547. x[i] = x[i] ^ c;
  1548. c = cc;
  1549. /* Adjust if needed, avoiding branches */
  1550. adjust = 1 - (x[i] & 0x01);
  1551. c |= x[i] & (x[i-1] * adjust);
  1552. x[i] = x[i] ^ (x[i-1] * adjust);
  1553. x[i-1] |= adjust << 7;
  1554. }
  1555. }
  1556. /*
  1557. * Precompute points for the adapted comb method
  1558. *
  1559. * Assumption: T must be able to hold 2^{w - 1} elements.
  1560. *
  1561. * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,
  1562. * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.
  1563. *
  1564. * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
  1565. *
  1566. * Note: Even comb values (those where P would be omitted from the
  1567. * sum defining T[i] above) are not needed in our adaption
  1568. * the comb method. See ecp_comb_recode_core().
  1569. *
  1570. * This function currently works in four steps:
  1571. * (1) [dbl] Computation of intermediate T[i] for 2-power values of i
  1572. * (2) [norm_dbl] Normalization of coordinates of these T[i]
  1573. * (3) [add] Computation of all T[i]
  1574. * (4) [norm_add] Normalization of all T[i]
  1575. *
  1576. * Step 1 can be interrupted but not the others; together with the final
  1577. * coordinate normalization they are the largest steps done at once, depending
  1578. * on the window size. Here are operation counts for P-256:
  1579. *
  1580. * step (2) (3) (4)
  1581. * w = 5 142 165 208
  1582. * w = 4 136 77 160
  1583. * w = 3 130 33 136
  1584. * w = 2 124 11 124
  1585. *
  1586. * So if ECC operations are blocking for too long even with a low max_ops
  1587. * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order
  1588. * to minimize maximum blocking time.
  1589. */
  1590. static int ecp_precompute_comb(const mbedtls_ecp_group *grp,
  1591. mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
  1592. unsigned char w, size_t d,
  1593. mbedtls_ecp_restart_ctx *rs_ctx)
  1594. {
  1595. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1596. unsigned char i;
  1597. size_t j = 0;
  1598. const unsigned char T_size = 1U << (w - 1);
  1599. mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
  1600. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1601. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1602. if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) {
  1603. goto dbl;
  1604. }
  1605. if (rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl) {
  1606. goto norm_dbl;
  1607. }
  1608. if (rs_ctx->rsm->state == ecp_rsm_pre_add) {
  1609. goto add;
  1610. }
  1611. if (rs_ctx->rsm->state == ecp_rsm_pre_norm_add) {
  1612. goto norm_add;
  1613. }
  1614. }
  1615. #else
  1616. (void) rs_ctx;
  1617. #endif
  1618. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1619. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1620. rs_ctx->rsm->state = ecp_rsm_pre_dbl;
  1621. /* initial state for the loop */
  1622. rs_ctx->rsm->i = 0;
  1623. }
  1624. dbl:
  1625. #endif
  1626. /*
  1627. * Set T[0] = P and
  1628. * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
  1629. */
  1630. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&T[0], P));
  1631. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1632. if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) {
  1633. j = rs_ctx->rsm->i;
  1634. } else
  1635. #endif
  1636. j = 0;
  1637. for (; j < d * (w - 1); j++) {
  1638. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL);
  1639. i = 1U << (j / d);
  1640. cur = T + i;
  1641. if (j % d == 0) {
  1642. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(cur, T + (i >> 1)));
  1643. }
  1644. MBEDTLS_MPI_CHK(ecp_double_jac(grp, cur, cur));
  1645. }
  1646. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1647. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1648. rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl;
  1649. }
  1650. norm_dbl:
  1651. #endif
  1652. /*
  1653. * Normalize current elements in T. As T has holes,
  1654. * use an auxiliary array of pointers to elements in T.
  1655. */
  1656. j = 0;
  1657. for (i = 1; i < T_size; i <<= 1) {
  1658. TT[j++] = T + i;
  1659. }
  1660. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2);
  1661. MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j));
  1662. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1663. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1664. rs_ctx->rsm->state = ecp_rsm_pre_add;
  1665. }
  1666. add:
  1667. #endif
  1668. /*
  1669. * Compute the remaining ones using the minimal number of additions
  1670. * Be careful to update T[2^l] only after using it!
  1671. */
  1672. MBEDTLS_ECP_BUDGET((T_size - 1) * MBEDTLS_ECP_OPS_ADD);
  1673. for (i = 1; i < T_size; i <<= 1) {
  1674. j = i;
  1675. while (j--) {
  1676. MBEDTLS_MPI_CHK(ecp_add_mixed(grp, &T[i + j], &T[j], &T[i]));
  1677. }
  1678. }
  1679. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1680. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1681. rs_ctx->rsm->state = ecp_rsm_pre_norm_add;
  1682. }
  1683. norm_add:
  1684. #endif
  1685. /*
  1686. * Normalize final elements in T. Even though there are no holes now, we
  1687. * still need the auxiliary array for homogeneity with the previous
  1688. * call. Also, skip T[0] which is already normalised, being a copy of P.
  1689. */
  1690. for (j = 0; j + 1 < T_size; j++) {
  1691. TT[j] = T + j + 1;
  1692. }
  1693. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2);
  1694. MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j));
  1695. cleanup:
  1696. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1697. if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
  1698. ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
  1699. if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) {
  1700. rs_ctx->rsm->i = j;
  1701. }
  1702. }
  1703. #endif
  1704. return ret;
  1705. }
  1706. /*
  1707. * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
  1708. *
  1709. * See ecp_comb_recode_core() for background
  1710. */
  1711. static int ecp_select_comb(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1712. const mbedtls_ecp_point T[], unsigned char T_size,
  1713. unsigned char i)
  1714. {
  1715. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1716. unsigned char ii, j;
  1717. /* Ignore the "sign" bit and scale down */
  1718. ii = (i & 0x7Fu) >> 1;
  1719. /* Read the whole table to thwart cache-based timing attacks */
  1720. for (j = 0; j < T_size; j++) {
  1721. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&R->X, &T[j].X, j == ii));
  1722. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&R->Y, &T[j].Y, j == ii));
  1723. }
  1724. /* Safely invert result if i is "negative" */
  1725. MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, R, i >> 7));
  1726. cleanup:
  1727. return ret;
  1728. }
  1729. /*
  1730. * Core multiplication algorithm for the (modified) comb method.
  1731. * This part is actually common with the basic comb method (GECC 3.44)
  1732. *
  1733. * Cost: d A + d D + 1 R
  1734. */
  1735. static int ecp_mul_comb_core(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1736. const mbedtls_ecp_point T[], unsigned char T_size,
  1737. const unsigned char x[], size_t d,
  1738. int (*f_rng)(void *, unsigned char *, size_t),
  1739. void *p_rng,
  1740. mbedtls_ecp_restart_ctx *rs_ctx)
  1741. {
  1742. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1743. mbedtls_ecp_point Txi;
  1744. size_t i;
  1745. mbedtls_ecp_point_init(&Txi);
  1746. #if !defined(MBEDTLS_ECP_RESTARTABLE)
  1747. (void) rs_ctx;
  1748. #endif
  1749. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1750. if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
  1751. rs_ctx->rsm->state != ecp_rsm_comb_core) {
  1752. rs_ctx->rsm->i = 0;
  1753. rs_ctx->rsm->state = ecp_rsm_comb_core;
  1754. }
  1755. /* new 'if' instead of nested for the sake of the 'else' branch */
  1756. if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) {
  1757. /* restore current index (R already pointing to rs_ctx->rsm->R) */
  1758. i = rs_ctx->rsm->i;
  1759. } else
  1760. #endif
  1761. {
  1762. int have_rng = 1;
  1763. /* Start with a non-zero point and randomize its coordinates */
  1764. i = d;
  1765. MBEDTLS_MPI_CHK(ecp_select_comb(grp, R, T, T_size, x[i]));
  1766. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&R->Z, 1));
  1767. #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  1768. if (f_rng == NULL) {
  1769. have_rng = 0;
  1770. }
  1771. #endif
  1772. if (have_rng) {
  1773. MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, R, f_rng, p_rng));
  1774. }
  1775. }
  1776. while (i != 0) {
  1777. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD);
  1778. --i;
  1779. MBEDTLS_MPI_CHK(ecp_double_jac(grp, R, R));
  1780. MBEDTLS_MPI_CHK(ecp_select_comb(grp, &Txi, T, T_size, x[i]));
  1781. MBEDTLS_MPI_CHK(ecp_add_mixed(grp, R, R, &Txi));
  1782. }
  1783. cleanup:
  1784. mbedtls_ecp_point_free(&Txi);
  1785. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1786. if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
  1787. ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
  1788. rs_ctx->rsm->i = i;
  1789. /* no need to save R, already pointing to rs_ctx->rsm->R */
  1790. }
  1791. #endif
  1792. return ret;
  1793. }
  1794. /*
  1795. * Recode the scalar to get constant-time comb multiplication
  1796. *
  1797. * As the actual scalar recoding needs an odd scalar as a starting point,
  1798. * this wrapper ensures that by replacing m by N - m if necessary, and
  1799. * informs the caller that the result of multiplication will be negated.
  1800. *
  1801. * This works because we only support large prime order for Short Weierstrass
  1802. * curves, so N is always odd hence either m or N - m is.
  1803. *
  1804. * See ecp_comb_recode_core() for background.
  1805. */
  1806. static int ecp_comb_recode_scalar(const mbedtls_ecp_group *grp,
  1807. const mbedtls_mpi *m,
  1808. unsigned char k[COMB_MAX_D + 1],
  1809. size_t d,
  1810. unsigned char w,
  1811. unsigned char *parity_trick)
  1812. {
  1813. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1814. mbedtls_mpi M, mm;
  1815. mbedtls_mpi_init(&M);
  1816. mbedtls_mpi_init(&mm);
  1817. /* N is always odd (see above), just make extra sure */
  1818. if (mbedtls_mpi_get_bit(&grp->N, 0) != 1) {
  1819. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  1820. }
  1821. /* do we need the parity trick? */
  1822. *parity_trick = (mbedtls_mpi_get_bit(m, 0) == 0);
  1823. /* execute parity fix in constant time */
  1824. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&M, m));
  1825. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&mm, &grp->N, m));
  1826. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&M, &mm, *parity_trick));
  1827. /* actual scalar recoding */
  1828. ecp_comb_recode_core(k, d, w, &M);
  1829. cleanup:
  1830. mbedtls_mpi_free(&mm);
  1831. mbedtls_mpi_free(&M);
  1832. return ret;
  1833. }
  1834. /*
  1835. * Perform comb multiplication (for short Weierstrass curves)
  1836. * once the auxiliary table has been pre-computed.
  1837. *
  1838. * Scalar recoding may use a parity trick that makes us compute -m * P,
  1839. * if that is the case we'll need to recover m * P at the end.
  1840. */
  1841. static int ecp_mul_comb_after_precomp(const mbedtls_ecp_group *grp,
  1842. mbedtls_ecp_point *R,
  1843. const mbedtls_mpi *m,
  1844. const mbedtls_ecp_point *T,
  1845. unsigned char T_size,
  1846. unsigned char w,
  1847. size_t d,
  1848. int (*f_rng)(void *, unsigned char *, size_t),
  1849. void *p_rng,
  1850. mbedtls_ecp_restart_ctx *rs_ctx)
  1851. {
  1852. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1853. unsigned char parity_trick;
  1854. unsigned char k[COMB_MAX_D + 1];
  1855. mbedtls_ecp_point *RR = R;
  1856. int have_rng = 1;
  1857. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1858. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1859. RR = &rs_ctx->rsm->R;
  1860. if (rs_ctx->rsm->state == ecp_rsm_final_norm) {
  1861. goto final_norm;
  1862. }
  1863. }
  1864. #endif
  1865. MBEDTLS_MPI_CHK(ecp_comb_recode_scalar(grp, m, k, d, w,
  1866. &parity_trick));
  1867. MBEDTLS_MPI_CHK(ecp_mul_comb_core(grp, RR, T, T_size, k, d,
  1868. f_rng, p_rng, rs_ctx));
  1869. MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, RR, parity_trick));
  1870. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1871. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1872. rs_ctx->rsm->state = ecp_rsm_final_norm;
  1873. }
  1874. final_norm:
  1875. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV);
  1876. #endif
  1877. /*
  1878. * Knowledge of the jacobian coordinates may leak the last few bits of the
  1879. * scalar [1], and since our MPI implementation isn't constant-flow,
  1880. * inversion (used for coordinate normalization) may leak the full value
  1881. * of its input via side-channels [2].
  1882. *
  1883. * [1] https://eprint.iacr.org/2003/191
  1884. * [2] https://eprint.iacr.org/2020/055
  1885. *
  1886. * Avoid the leak by randomizing coordinates before we normalize them.
  1887. */
  1888. #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  1889. if (f_rng == NULL) {
  1890. have_rng = 0;
  1891. }
  1892. #endif
  1893. if (have_rng) {
  1894. MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, RR, f_rng, p_rng));
  1895. }
  1896. MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, RR));
  1897. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1898. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1899. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, RR));
  1900. }
  1901. #endif
  1902. cleanup:
  1903. return ret;
  1904. }
  1905. /*
  1906. * Pick window size based on curve size and whether we optimize for base point
  1907. */
  1908. static unsigned char ecp_pick_window_size(const mbedtls_ecp_group *grp,
  1909. unsigned char p_eq_g)
  1910. {
  1911. unsigned char w;
  1912. /*
  1913. * Minimize the number of multiplications, that is minimize
  1914. * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
  1915. * (see costs of the various parts, with 1S = 1M)
  1916. */
  1917. w = grp->nbits >= 384 ? 5 : 4;
  1918. /*
  1919. * If P == G, pre-compute a bit more, since this may be re-used later.
  1920. * Just adding one avoids upping the cost of the first mul too much,
  1921. * and the memory cost too.
  1922. */
  1923. if (p_eq_g) {
  1924. w++;
  1925. }
  1926. /*
  1927. * Make sure w is within bounds.
  1928. * (The last test is useful only for very small curves in the test suite.)
  1929. */
  1930. #if (MBEDTLS_ECP_WINDOW_SIZE < 6)
  1931. if (w > MBEDTLS_ECP_WINDOW_SIZE) {
  1932. w = MBEDTLS_ECP_WINDOW_SIZE;
  1933. }
  1934. #endif
  1935. if (w >= grp->nbits) {
  1936. w = 2;
  1937. }
  1938. return w;
  1939. }
  1940. /*
  1941. * Multiplication using the comb method - for curves in short Weierstrass form
  1942. *
  1943. * This function is mainly responsible for administrative work:
  1944. * - managing the restart context if enabled
  1945. * - managing the table of precomputed points (passed between the below two
  1946. * functions): allocation, computation, ownership transfer, freeing.
  1947. *
  1948. * It delegates the actual arithmetic work to:
  1949. * ecp_precompute_comb() and ecp_mul_comb_with_precomp()
  1950. *
  1951. * See comments on ecp_comb_recode_core() regarding the computation strategy.
  1952. */
  1953. static int ecp_mul_comb(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1954. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  1955. int (*f_rng)(void *, unsigned char *, size_t),
  1956. void *p_rng,
  1957. mbedtls_ecp_restart_ctx *rs_ctx)
  1958. {
  1959. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  1960. unsigned char w, p_eq_g, i;
  1961. size_t d;
  1962. unsigned char T_size = 0, T_ok = 0;
  1963. mbedtls_ecp_point *T = NULL;
  1964. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  1965. ecp_drbg_context drbg_ctx;
  1966. ecp_drbg_init(&drbg_ctx);
  1967. #endif
  1968. ECP_RS_ENTER(rsm);
  1969. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  1970. if (f_rng == NULL) {
  1971. /* Adjust pointers */
  1972. f_rng = &ecp_drbg_random;
  1973. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1974. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1975. p_rng = &rs_ctx->rsm->drbg_ctx;
  1976. } else
  1977. #endif
  1978. p_rng = &drbg_ctx;
  1979. /* Initialize internal DRBG if necessary */
  1980. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1981. if (rs_ctx == NULL || rs_ctx->rsm == NULL ||
  1982. rs_ctx->rsm->drbg_seeded == 0)
  1983. #endif
  1984. {
  1985. const size_t m_len = (grp->nbits + 7) / 8;
  1986. MBEDTLS_MPI_CHK(ecp_drbg_seed(p_rng, m, m_len));
  1987. }
  1988. #if defined(MBEDTLS_ECP_RESTARTABLE)
  1989. if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
  1990. rs_ctx->rsm->drbg_seeded = 1;
  1991. }
  1992. #endif
  1993. }
  1994. #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
  1995. /* Is P the base point ? */
  1996. #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
  1997. p_eq_g = (mbedtls_mpi_cmp_mpi(&P->Y, &grp->G.Y) == 0 &&
  1998. mbedtls_mpi_cmp_mpi(&P->X, &grp->G.X) == 0);
  1999. #else
  2000. p_eq_g = 0;
  2001. #endif
  2002. /* Pick window size and deduce related sizes */
  2003. w = ecp_pick_window_size(grp, p_eq_g);
  2004. T_size = 1U << (w - 1);
  2005. d = (grp->nbits + w - 1) / w;
  2006. /* Pre-computed table: do we have it already for the base point? */
  2007. if (p_eq_g && grp->T != NULL) {
  2008. /* second pointer to the same table, will be deleted on exit */
  2009. T = grp->T;
  2010. T_ok = 1;
  2011. } else
  2012. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2013. /* Pre-computed table: do we have one in progress? complete? */
  2014. if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL) {
  2015. /* transfer ownership of T from rsm to local function */
  2016. T = rs_ctx->rsm->T;
  2017. rs_ctx->rsm->T = NULL;
  2018. rs_ctx->rsm->T_size = 0;
  2019. /* This effectively jumps to the call to mul_comb_after_precomp() */
  2020. T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core;
  2021. } else
  2022. #endif
  2023. /* Allocate table if we didn't have any */
  2024. {
  2025. T = mbedtls_calloc(T_size, sizeof(mbedtls_ecp_point));
  2026. if (T == NULL) {
  2027. ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
  2028. goto cleanup;
  2029. }
  2030. for (i = 0; i < T_size; i++) {
  2031. mbedtls_ecp_point_init(&T[i]);
  2032. }
  2033. T_ok = 0;
  2034. }
  2035. /* Compute table (or finish computing it) if not done already */
  2036. if (!T_ok) {
  2037. MBEDTLS_MPI_CHK(ecp_precompute_comb(grp, T, P, w, d, rs_ctx));
  2038. if (p_eq_g) {
  2039. /* almost transfer ownership of T to the group, but keep a copy of
  2040. * the pointer to use for calling the next function more easily */
  2041. grp->T = T;
  2042. grp->T_size = T_size;
  2043. }
  2044. }
  2045. /* Actual comb multiplication using precomputed points */
  2046. MBEDTLS_MPI_CHK(ecp_mul_comb_after_precomp(grp, R, m,
  2047. T, T_size, w, d,
  2048. f_rng, p_rng, rs_ctx));
  2049. cleanup:
  2050. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  2051. ecp_drbg_free(&drbg_ctx);
  2052. #endif
  2053. /* does T belong to the group? */
  2054. if (T == grp->T) {
  2055. T = NULL;
  2056. }
  2057. /* does T belong to the restart context? */
  2058. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2059. if (rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL) {
  2060. /* transfer ownership of T from local function to rsm */
  2061. rs_ctx->rsm->T_size = T_size;
  2062. rs_ctx->rsm->T = T;
  2063. T = NULL;
  2064. }
  2065. #endif
  2066. /* did T belong to us? then let's destroy it! */
  2067. if (T != NULL) {
  2068. for (i = 0; i < T_size; i++) {
  2069. mbedtls_ecp_point_free(&T[i]);
  2070. }
  2071. mbedtls_free(T);
  2072. }
  2073. /* prevent caller from using invalid value */
  2074. int should_free_R = (ret != 0);
  2075. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2076. /* don't free R while in progress in case R == P */
  2077. if (ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
  2078. should_free_R = 0;
  2079. }
  2080. #endif
  2081. if (should_free_R) {
  2082. mbedtls_ecp_point_free(R);
  2083. }
  2084. ECP_RS_LEAVE(rsm);
  2085. return ret;
  2086. }
  2087. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  2088. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2089. /*
  2090. * For Montgomery curves, we do all the internal arithmetic in projective
  2091. * coordinates. Import/export of points uses only the x coordinates, which is
  2092. * internally represented as X / Z.
  2093. *
  2094. * For scalar multiplication, we'll use a Montgomery ladder.
  2095. */
  2096. /*
  2097. * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
  2098. * Cost: 1M + 1I
  2099. */
  2100. static int ecp_normalize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P)
  2101. {
  2102. #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
  2103. if (mbedtls_internal_ecp_grp_capable(grp)) {
  2104. return mbedtls_internal_ecp_normalize_mxz(grp, P);
  2105. }
  2106. #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
  2107. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
  2108. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2109. #else
  2110. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2111. MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&P->Z, &P->Z, &grp->P));
  2112. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &P->X, &P->X, &P->Z));
  2113. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&P->Z, 1));
  2114. cleanup:
  2115. return ret;
  2116. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) */
  2117. }
  2118. /*
  2119. * Randomize projective x/z coordinates:
  2120. * (X, Z) -> (l X, l Z) for random l
  2121. * This is sort of the reverse operation of ecp_normalize_mxz().
  2122. *
  2123. * This countermeasure was first suggested in [2].
  2124. * Cost: 2M
  2125. */
  2126. static int ecp_randomize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
  2127. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
  2128. {
  2129. #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
  2130. if (mbedtls_internal_ecp_grp_capable(grp)) {
  2131. return mbedtls_internal_ecp_randomize_mxz(grp, P, f_rng, p_rng);
  2132. }
  2133. #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
  2134. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
  2135. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2136. #else
  2137. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2138. mbedtls_mpi l;
  2139. mbedtls_mpi_init(&l);
  2140. /* Generate l such that 1 < l < p */
  2141. MBEDTLS_MPI_CHK(mbedtls_mpi_random(&l, 2, &grp->P, f_rng, p_rng));
  2142. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &P->X, &P->X, &l));
  2143. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &P->Z, &P->Z, &l));
  2144. cleanup:
  2145. mbedtls_mpi_free(&l);
  2146. if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
  2147. ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
  2148. }
  2149. return ret;
  2150. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) */
  2151. }
  2152. /*
  2153. * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
  2154. * for Montgomery curves in x/z coordinates.
  2155. *
  2156. * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
  2157. * with
  2158. * d = X1
  2159. * P = (X2, Z2)
  2160. * Q = (X3, Z3)
  2161. * R = (X4, Z4)
  2162. * S = (X5, Z5)
  2163. * and eliminating temporary variables tO, ..., t4.
  2164. *
  2165. * Cost: 5M + 4S
  2166. */
  2167. static int ecp_double_add_mxz(const mbedtls_ecp_group *grp,
  2168. mbedtls_ecp_point *R, mbedtls_ecp_point *S,
  2169. const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
  2170. const mbedtls_mpi *d)
  2171. {
  2172. #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
  2173. if (mbedtls_internal_ecp_grp_capable(grp)) {
  2174. return mbedtls_internal_ecp_double_add_mxz(grp, R, S, P, Q, d);
  2175. }
  2176. #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
  2177. #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
  2178. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2179. #else
  2180. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2181. mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
  2182. mbedtls_mpi_init(&A); mbedtls_mpi_init(&AA); mbedtls_mpi_init(&B);
  2183. mbedtls_mpi_init(&BB); mbedtls_mpi_init(&E); mbedtls_mpi_init(&C);
  2184. mbedtls_mpi_init(&D); mbedtls_mpi_init(&DA); mbedtls_mpi_init(&CB);
  2185. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &A, &P->X, &P->Z));
  2186. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &AA, &A, &A));
  2187. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &B, &P->X, &P->Z));
  2188. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &BB, &B, &B));
  2189. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &E, &AA, &BB));
  2190. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &C, &Q->X, &Q->Z));
  2191. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &D, &Q->X, &Q->Z));
  2192. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &DA, &D, &A));
  2193. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &CB, &C, &B));
  2194. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &S->X, &DA, &CB));
  2195. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S->X, &S->X, &S->X));
  2196. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, &S->Z, &DA, &CB));
  2197. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S->Z, &S->Z, &S->Z));
  2198. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &S->Z, d, &S->Z));
  2199. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &R->X, &AA, &BB));
  2200. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &R->Z, &grp->A, &E));
  2201. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &R->Z, &BB, &R->Z));
  2202. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &R->Z, &E, &R->Z));
  2203. cleanup:
  2204. mbedtls_mpi_free(&A); mbedtls_mpi_free(&AA); mbedtls_mpi_free(&B);
  2205. mbedtls_mpi_free(&BB); mbedtls_mpi_free(&E); mbedtls_mpi_free(&C);
  2206. mbedtls_mpi_free(&D); mbedtls_mpi_free(&DA); mbedtls_mpi_free(&CB);
  2207. return ret;
  2208. #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) */
  2209. }
  2210. /*
  2211. * Multiplication with Montgomery ladder in x/z coordinates,
  2212. * for curves in Montgomery form
  2213. */
  2214. static int ecp_mul_mxz(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  2215. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  2216. int (*f_rng)(void *, unsigned char *, size_t),
  2217. void *p_rng)
  2218. {
  2219. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2220. int have_rng = 1;
  2221. size_t i;
  2222. unsigned char b;
  2223. mbedtls_ecp_point RP;
  2224. mbedtls_mpi PX;
  2225. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  2226. ecp_drbg_context drbg_ctx;
  2227. ecp_drbg_init(&drbg_ctx);
  2228. #endif
  2229. mbedtls_ecp_point_init(&RP); mbedtls_mpi_init(&PX);
  2230. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  2231. if (f_rng == NULL) {
  2232. const size_t m_len = (grp->nbits + 7) / 8;
  2233. MBEDTLS_MPI_CHK(ecp_drbg_seed(&drbg_ctx, m, m_len));
  2234. f_rng = &ecp_drbg_random;
  2235. p_rng = &drbg_ctx;
  2236. }
  2237. #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
  2238. /* Save PX and read from P before writing to R, in case P == R */
  2239. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&PX, &P->X));
  2240. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&RP, P));
  2241. /* Set R to zero in modified x/z coordinates */
  2242. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&R->X, 1));
  2243. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&R->Z, 0));
  2244. mbedtls_mpi_free(&R->Y);
  2245. /* RP.X might be slightly larger than P, so reduce it */
  2246. MOD_ADD(RP.X);
  2247. /* Randomize coordinates of the starting point */
  2248. #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  2249. if (f_rng == NULL) {
  2250. have_rng = 0;
  2251. }
  2252. #endif
  2253. if (have_rng) {
  2254. MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, &RP, f_rng, p_rng));
  2255. }
  2256. /* Loop invariant: R = result so far, RP = R + P */
  2257. i = grp->nbits + 1; /* one past the (zero-based) required msb for private keys */
  2258. while (i-- > 0) {
  2259. b = mbedtls_mpi_get_bit(m, i);
  2260. /*
  2261. * if (b) R = 2R + P else R = 2R,
  2262. * which is:
  2263. * if (b) double_add( RP, R, RP, R )
  2264. * else double_add( R, RP, R, RP )
  2265. * but using safe conditional swaps to avoid leaks
  2266. */
  2267. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->X, &RP.X, b));
  2268. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->Z, &RP.Z, b));
  2269. MBEDTLS_MPI_CHK(ecp_double_add_mxz(grp, R, &RP, R, &RP, &PX));
  2270. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->X, &RP.X, b));
  2271. MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap(&R->Z, &RP.Z, b));
  2272. }
  2273. /*
  2274. * Knowledge of the projective coordinates may leak the last few bits of the
  2275. * scalar [1], and since our MPI implementation isn't constant-flow,
  2276. * inversion (used for coordinate normalization) may leak the full value
  2277. * of its input via side-channels [2].
  2278. *
  2279. * [1] https://eprint.iacr.org/2003/191
  2280. * [2] https://eprint.iacr.org/2020/055
  2281. *
  2282. * Avoid the leak by randomizing coordinates before we normalize them.
  2283. */
  2284. have_rng = 1;
  2285. #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  2286. if (f_rng == NULL) {
  2287. have_rng = 0;
  2288. }
  2289. #endif
  2290. if (have_rng) {
  2291. MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, R, f_rng, p_rng));
  2292. }
  2293. MBEDTLS_MPI_CHK(ecp_normalize_mxz(grp, R));
  2294. cleanup:
  2295. #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
  2296. ecp_drbg_free(&drbg_ctx);
  2297. #endif
  2298. mbedtls_ecp_point_free(&RP); mbedtls_mpi_free(&PX);
  2299. return ret;
  2300. }
  2301. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  2302. /*
  2303. * Restartable multiplication R = m * P
  2304. */
  2305. int mbedtls_ecp_mul_restartable(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  2306. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  2307. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
  2308. mbedtls_ecp_restart_ctx *rs_ctx)
  2309. {
  2310. int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2311. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  2312. char is_grp_capable = 0;
  2313. #endif
  2314. ECP_VALIDATE_RET(grp != NULL);
  2315. ECP_VALIDATE_RET(R != NULL);
  2316. ECP_VALIDATE_RET(m != NULL);
  2317. ECP_VALIDATE_RET(P != NULL);
  2318. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2319. /* reset ops count for this call if top-level */
  2320. if (rs_ctx != NULL && rs_ctx->depth++ == 0) {
  2321. rs_ctx->ops_done = 0;
  2322. }
  2323. #else
  2324. (void) rs_ctx;
  2325. #endif
  2326. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  2327. if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) {
  2328. MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp));
  2329. }
  2330. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  2331. int restarting = 0;
  2332. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2333. restarting = (rs_ctx != NULL && rs_ctx->rsm != NULL);
  2334. #endif
  2335. /* skip argument check when restarting */
  2336. if (!restarting) {
  2337. /* check_privkey is free */
  2338. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_CHK);
  2339. /* Common sanity checks */
  2340. MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(grp, m));
  2341. MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
  2342. }
  2343. ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2344. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2345. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  2346. MBEDTLS_MPI_CHK(ecp_mul_mxz(grp, R, m, P, f_rng, p_rng));
  2347. }
  2348. #endif
  2349. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2350. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2351. MBEDTLS_MPI_CHK(ecp_mul_comb(grp, R, m, P, f_rng, p_rng, rs_ctx));
  2352. }
  2353. #endif
  2354. cleanup:
  2355. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  2356. if (is_grp_capable) {
  2357. mbedtls_internal_ecp_free(grp);
  2358. }
  2359. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  2360. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2361. if (rs_ctx != NULL) {
  2362. rs_ctx->depth--;
  2363. }
  2364. #endif
  2365. return ret;
  2366. }
  2367. /*
  2368. * Multiplication R = m * P
  2369. */
  2370. int mbedtls_ecp_mul(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  2371. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  2372. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
  2373. {
  2374. ECP_VALIDATE_RET(grp != NULL);
  2375. ECP_VALIDATE_RET(R != NULL);
  2376. ECP_VALIDATE_RET(m != NULL);
  2377. ECP_VALIDATE_RET(P != NULL);
  2378. return mbedtls_ecp_mul_restartable(grp, R, m, P, f_rng, p_rng, NULL);
  2379. }
  2380. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2381. /*
  2382. * Check that an affine point is valid as a public key,
  2383. * short weierstrass curves (SEC1 3.2.3.1)
  2384. */
  2385. static int ecp_check_pubkey_sw(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
  2386. {
  2387. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2388. mbedtls_mpi YY, RHS;
  2389. /* pt coordinates must be normalized for our checks */
  2390. if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0 ||
  2391. mbedtls_mpi_cmp_int(&pt->Y, 0) < 0 ||
  2392. mbedtls_mpi_cmp_mpi(&pt->X, &grp->P) >= 0 ||
  2393. mbedtls_mpi_cmp_mpi(&pt->Y, &grp->P) >= 0) {
  2394. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2395. }
  2396. mbedtls_mpi_init(&YY); mbedtls_mpi_init(&RHS);
  2397. /*
  2398. * YY = Y^2
  2399. * RHS = X (X^2 + A) + B = X^3 + A X + B
  2400. */
  2401. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &YY, &pt->Y, &pt->Y));
  2402. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &RHS, &pt->X, &pt->X));
  2403. /* Special case for A = -3 */
  2404. if (grp->A.p == NULL) {
  2405. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&RHS, &RHS, 3)); MOD_SUB(RHS);
  2406. } else {
  2407. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &RHS, &RHS, &grp->A));
  2408. }
  2409. MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, &RHS, &RHS, &pt->X));
  2410. MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, &RHS, &RHS, &grp->B));
  2411. if (mbedtls_mpi_cmp_mpi(&YY, &RHS) != 0) {
  2412. ret = MBEDTLS_ERR_ECP_INVALID_KEY;
  2413. }
  2414. cleanup:
  2415. mbedtls_mpi_free(&YY); mbedtls_mpi_free(&RHS);
  2416. return ret;
  2417. }
  2418. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  2419. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2420. /*
  2421. * R = m * P with shortcuts for m == 0, m == 1 and m == -1
  2422. * NOT constant-time - ONLY for short Weierstrass!
  2423. */
  2424. static int mbedtls_ecp_mul_shortcuts(mbedtls_ecp_group *grp,
  2425. mbedtls_ecp_point *R,
  2426. const mbedtls_mpi *m,
  2427. const mbedtls_ecp_point *P,
  2428. mbedtls_ecp_restart_ctx *rs_ctx)
  2429. {
  2430. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2431. if (mbedtls_mpi_cmp_int(m, 0) == 0) {
  2432. MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
  2433. MBEDTLS_MPI_CHK(mbedtls_ecp_set_zero(R));
  2434. } else if (mbedtls_mpi_cmp_int(m, 1) == 0) {
  2435. MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
  2436. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P));
  2437. } else if (mbedtls_mpi_cmp_int(m, -1) == 0) {
  2438. MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
  2439. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P));
  2440. if (mbedtls_mpi_cmp_int(&R->Y, 0) != 0) {
  2441. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&R->Y, &grp->P, &R->Y));
  2442. }
  2443. } else {
  2444. MBEDTLS_MPI_CHK(mbedtls_ecp_mul_restartable(grp, R, m, P,
  2445. NULL, NULL, rs_ctx));
  2446. }
  2447. cleanup:
  2448. return ret;
  2449. }
  2450. /*
  2451. * Restartable linear combination
  2452. * NOT constant-time
  2453. */
  2454. int mbedtls_ecp_muladd_restartable(
  2455. mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  2456. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  2457. const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
  2458. mbedtls_ecp_restart_ctx *rs_ctx)
  2459. {
  2460. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2461. mbedtls_ecp_point mP;
  2462. mbedtls_ecp_point *pmP = &mP;
  2463. mbedtls_ecp_point *pR = R;
  2464. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  2465. char is_grp_capable = 0;
  2466. #endif
  2467. ECP_VALIDATE_RET(grp != NULL);
  2468. ECP_VALIDATE_RET(R != NULL);
  2469. ECP_VALIDATE_RET(m != NULL);
  2470. ECP_VALIDATE_RET(P != NULL);
  2471. ECP_VALIDATE_RET(n != NULL);
  2472. ECP_VALIDATE_RET(Q != NULL);
  2473. if (mbedtls_ecp_get_type(grp) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2474. return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2475. }
  2476. mbedtls_ecp_point_init(&mP);
  2477. ECP_RS_ENTER(ma);
  2478. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2479. if (rs_ctx != NULL && rs_ctx->ma != NULL) {
  2480. /* redirect intermediate results to restart context */
  2481. pmP = &rs_ctx->ma->mP;
  2482. pR = &rs_ctx->ma->R;
  2483. /* jump to next operation */
  2484. if (rs_ctx->ma->state == ecp_rsma_mul2) {
  2485. goto mul2;
  2486. }
  2487. if (rs_ctx->ma->state == ecp_rsma_add) {
  2488. goto add;
  2489. }
  2490. if (rs_ctx->ma->state == ecp_rsma_norm) {
  2491. goto norm;
  2492. }
  2493. }
  2494. #endif /* MBEDTLS_ECP_RESTARTABLE */
  2495. MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pmP, m, P, rs_ctx));
  2496. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2497. if (rs_ctx != NULL && rs_ctx->ma != NULL) {
  2498. rs_ctx->ma->state = ecp_rsma_mul2;
  2499. }
  2500. mul2:
  2501. #endif
  2502. MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pR, n, Q, rs_ctx));
  2503. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  2504. if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) {
  2505. MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp));
  2506. }
  2507. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  2508. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2509. if (rs_ctx != NULL && rs_ctx->ma != NULL) {
  2510. rs_ctx->ma->state = ecp_rsma_add;
  2511. }
  2512. add:
  2513. #endif
  2514. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_ADD);
  2515. MBEDTLS_MPI_CHK(ecp_add_mixed(grp, pR, pmP, pR));
  2516. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2517. if (rs_ctx != NULL && rs_ctx->ma != NULL) {
  2518. rs_ctx->ma->state = ecp_rsma_norm;
  2519. }
  2520. norm:
  2521. #endif
  2522. MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV);
  2523. MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, pR));
  2524. #if defined(MBEDTLS_ECP_RESTARTABLE)
  2525. if (rs_ctx != NULL && rs_ctx->ma != NULL) {
  2526. MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, pR));
  2527. }
  2528. #endif
  2529. cleanup:
  2530. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  2531. if (is_grp_capable) {
  2532. mbedtls_internal_ecp_free(grp);
  2533. }
  2534. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  2535. mbedtls_ecp_point_free(&mP);
  2536. ECP_RS_LEAVE(ma);
  2537. return ret;
  2538. }
  2539. /*
  2540. * Linear combination
  2541. * NOT constant-time
  2542. */
  2543. int mbedtls_ecp_muladd(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  2544. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  2545. const mbedtls_mpi *n, const mbedtls_ecp_point *Q)
  2546. {
  2547. ECP_VALIDATE_RET(grp != NULL);
  2548. ECP_VALIDATE_RET(R != NULL);
  2549. ECP_VALIDATE_RET(m != NULL);
  2550. ECP_VALIDATE_RET(P != NULL);
  2551. ECP_VALIDATE_RET(n != NULL);
  2552. ECP_VALIDATE_RET(Q != NULL);
  2553. return mbedtls_ecp_muladd_restartable(grp, R, m, P, n, Q, NULL);
  2554. }
  2555. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  2556. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2557. #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
  2558. #define ECP_MPI_INIT(s, n, p) { s, (n), (mbedtls_mpi_uint *) (p) }
  2559. #define ECP_MPI_INIT_ARRAY(x) \
  2560. ECP_MPI_INIT(1, sizeof(x) / sizeof(mbedtls_mpi_uint), x)
  2561. /*
  2562. * Constants for the two points other than 0, 1, -1 (mod p) in
  2563. * https://cr.yp.to/ecdh.html#validate
  2564. * See ecp_check_pubkey_x25519().
  2565. */
  2566. static const mbedtls_mpi_uint x25519_bad_point_1[] = {
  2567. MBEDTLS_BYTES_TO_T_UINT_8(0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae),
  2568. MBEDTLS_BYTES_TO_T_UINT_8(0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a),
  2569. MBEDTLS_BYTES_TO_T_UINT_8(0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd),
  2570. MBEDTLS_BYTES_TO_T_UINT_8(0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00),
  2571. };
  2572. static const mbedtls_mpi_uint x25519_bad_point_2[] = {
  2573. MBEDTLS_BYTES_TO_T_UINT_8(0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24),
  2574. MBEDTLS_BYTES_TO_T_UINT_8(0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b),
  2575. MBEDTLS_BYTES_TO_T_UINT_8(0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86),
  2576. MBEDTLS_BYTES_TO_T_UINT_8(0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57),
  2577. };
  2578. static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY(
  2579. x25519_bad_point_1);
  2580. static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY(
  2581. x25519_bad_point_2);
  2582. #endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
  2583. /*
  2584. * Check that the input point is not one of the low-order points.
  2585. * This is recommended by the "May the Fourth" paper:
  2586. * https://eprint.iacr.org/2017/806.pdf
  2587. * Those points are never sent by an honest peer.
  2588. */
  2589. static int ecp_check_bad_points_mx(const mbedtls_mpi *X, const mbedtls_mpi *P,
  2590. const mbedtls_ecp_group_id grp_id)
  2591. {
  2592. int ret;
  2593. mbedtls_mpi XmP;
  2594. mbedtls_mpi_init(&XmP);
  2595. /* Reduce X mod P so that we only need to check values less than P.
  2596. * We know X < 2^256 so we can proceed by subtraction. */
  2597. MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&XmP, X));
  2598. while (mbedtls_mpi_cmp_mpi(&XmP, P) >= 0) {
  2599. MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&XmP, &XmP, P));
  2600. }
  2601. /* Check against the known bad values that are less than P. For Curve448
  2602. * these are 0, 1 and -1. For Curve25519 we check the values less than P
  2603. * from the following list: https://cr.yp.to/ecdh.html#validate */
  2604. if (mbedtls_mpi_cmp_int(&XmP, 1) <= 0) { /* takes care of 0 and 1 */
  2605. ret = MBEDTLS_ERR_ECP_INVALID_KEY;
  2606. goto cleanup;
  2607. }
  2608. #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
  2609. if (grp_id == MBEDTLS_ECP_DP_CURVE25519) {
  2610. if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_1) == 0) {
  2611. ret = MBEDTLS_ERR_ECP_INVALID_KEY;
  2612. goto cleanup;
  2613. }
  2614. if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_2) == 0) {
  2615. ret = MBEDTLS_ERR_ECP_INVALID_KEY;
  2616. goto cleanup;
  2617. }
  2618. }
  2619. #else
  2620. (void) grp_id;
  2621. #endif
  2622. /* Final check: check if XmP + 1 is P (final because it changes XmP!) */
  2623. MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&XmP, &XmP, 1));
  2624. if (mbedtls_mpi_cmp_mpi(&XmP, P) == 0) {
  2625. ret = MBEDTLS_ERR_ECP_INVALID_KEY;
  2626. goto cleanup;
  2627. }
  2628. ret = 0;
  2629. cleanup:
  2630. mbedtls_mpi_free(&XmP);
  2631. return ret;
  2632. }
  2633. /*
  2634. * Check validity of a public key for Montgomery curves with x-only schemes
  2635. */
  2636. static int ecp_check_pubkey_mx(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
  2637. {
  2638. /* [Curve25519 p. 5] Just check X is the correct number of bytes */
  2639. /* Allow any public value, if it's too big then we'll just reduce it mod p
  2640. * (RFC 7748 sec. 5 para. 3). */
  2641. if (mbedtls_mpi_size(&pt->X) > (grp->nbits + 7) / 8) {
  2642. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2643. }
  2644. /* Implicit in all standards (as they don't consider negative numbers):
  2645. * X must be non-negative. This is normally ensured by the way it's
  2646. * encoded for transmission, but let's be extra sure. */
  2647. if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0) {
  2648. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2649. }
  2650. return ecp_check_bad_points_mx(&pt->X, &grp->P, grp->id);
  2651. }
  2652. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  2653. /*
  2654. * Check that a point is valid as a public key
  2655. */
  2656. int mbedtls_ecp_check_pubkey(const mbedtls_ecp_group *grp,
  2657. const mbedtls_ecp_point *pt)
  2658. {
  2659. ECP_VALIDATE_RET(grp != NULL);
  2660. ECP_VALIDATE_RET(pt != NULL);
  2661. /* Must use affine coordinates */
  2662. if (mbedtls_mpi_cmp_int(&pt->Z, 1) != 0) {
  2663. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2664. }
  2665. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2666. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  2667. return ecp_check_pubkey_mx(grp, pt);
  2668. }
  2669. #endif
  2670. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2671. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2672. return ecp_check_pubkey_sw(grp, pt);
  2673. }
  2674. #endif
  2675. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2676. }
  2677. /*
  2678. * Check that an mbedtls_mpi is valid as a private key
  2679. */
  2680. int mbedtls_ecp_check_privkey(const mbedtls_ecp_group *grp,
  2681. const mbedtls_mpi *d)
  2682. {
  2683. ECP_VALIDATE_RET(grp != NULL);
  2684. ECP_VALIDATE_RET(d != NULL);
  2685. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2686. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  2687. /* see RFC 7748 sec. 5 para. 5 */
  2688. if (mbedtls_mpi_get_bit(d, 0) != 0 ||
  2689. mbedtls_mpi_get_bit(d, 1) != 0 ||
  2690. mbedtls_mpi_bitlen(d) - 1 != grp->nbits) { /* mbedtls_mpi_bitlen is one-based! */
  2691. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2692. }
  2693. /* see [Curve25519] page 5 */
  2694. if (grp->nbits == 254 && mbedtls_mpi_get_bit(d, 2) != 0) {
  2695. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2696. }
  2697. return 0;
  2698. }
  2699. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  2700. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2701. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2702. /* see SEC1 3.2 */
  2703. if (mbedtls_mpi_cmp_int(d, 1) < 0 ||
  2704. mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0) {
  2705. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2706. } else {
  2707. return 0;
  2708. }
  2709. }
  2710. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  2711. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2712. }
  2713. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2714. MBEDTLS_STATIC_TESTABLE
  2715. int mbedtls_ecp_gen_privkey_mx(size_t high_bit,
  2716. mbedtls_mpi *d,
  2717. int (*f_rng)(void *, unsigned char *, size_t),
  2718. void *p_rng)
  2719. {
  2720. int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2721. size_t n_random_bytes = high_bit / 8 + 1;
  2722. /* [Curve25519] page 5 */
  2723. /* Generate a (high_bit+1)-bit random number by generating just enough
  2724. * random bytes, then shifting out extra bits from the top (necessary
  2725. * when (high_bit+1) is not a multiple of 8). */
  2726. MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(d, n_random_bytes,
  2727. f_rng, p_rng));
  2728. MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(d, 8 * n_random_bytes - high_bit - 1));
  2729. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, high_bit, 1));
  2730. /* Make sure the last two bits are unset for Curve448, three bits for
  2731. Curve25519 */
  2732. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 0, 0));
  2733. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 1, 0));
  2734. if (high_bit == 254) {
  2735. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 2, 0));
  2736. }
  2737. cleanup:
  2738. return ret;
  2739. }
  2740. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  2741. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2742. static int mbedtls_ecp_gen_privkey_sw(
  2743. const mbedtls_mpi *N, mbedtls_mpi *d,
  2744. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
  2745. {
  2746. int ret = mbedtls_mpi_random(d, 1, N, f_rng, p_rng);
  2747. switch (ret) {
  2748. case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE:
  2749. return MBEDTLS_ERR_ECP_RANDOM_FAILED;
  2750. default:
  2751. return ret;
  2752. }
  2753. }
  2754. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  2755. /*
  2756. * Generate a private key
  2757. */
  2758. int mbedtls_ecp_gen_privkey(const mbedtls_ecp_group *grp,
  2759. mbedtls_mpi *d,
  2760. int (*f_rng)(void *, unsigned char *, size_t),
  2761. void *p_rng)
  2762. {
  2763. ECP_VALIDATE_RET(grp != NULL);
  2764. ECP_VALIDATE_RET(d != NULL);
  2765. ECP_VALIDATE_RET(f_rng != NULL);
  2766. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2767. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  2768. return mbedtls_ecp_gen_privkey_mx(grp->nbits, d, f_rng, p_rng);
  2769. }
  2770. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  2771. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2772. if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2773. return mbedtls_ecp_gen_privkey_sw(&grp->N, d, f_rng, p_rng);
  2774. }
  2775. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  2776. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2777. }
  2778. /*
  2779. * Generate a keypair with configurable base point
  2780. */
  2781. int mbedtls_ecp_gen_keypair_base(mbedtls_ecp_group *grp,
  2782. const mbedtls_ecp_point *G,
  2783. mbedtls_mpi *d, mbedtls_ecp_point *Q,
  2784. int (*f_rng)(void *, unsigned char *, size_t),
  2785. void *p_rng)
  2786. {
  2787. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2788. ECP_VALIDATE_RET(grp != NULL);
  2789. ECP_VALIDATE_RET(d != NULL);
  2790. ECP_VALIDATE_RET(G != NULL);
  2791. ECP_VALIDATE_RET(Q != NULL);
  2792. ECP_VALIDATE_RET(f_rng != NULL);
  2793. MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, d, f_rng, p_rng));
  2794. MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, Q, d, G, f_rng, p_rng));
  2795. cleanup:
  2796. return ret;
  2797. }
  2798. /*
  2799. * Generate key pair, wrapper for conventional base point
  2800. */
  2801. int mbedtls_ecp_gen_keypair(mbedtls_ecp_group *grp,
  2802. mbedtls_mpi *d, mbedtls_ecp_point *Q,
  2803. int (*f_rng)(void *, unsigned char *, size_t),
  2804. void *p_rng)
  2805. {
  2806. ECP_VALIDATE_RET(grp != NULL);
  2807. ECP_VALIDATE_RET(d != NULL);
  2808. ECP_VALIDATE_RET(Q != NULL);
  2809. ECP_VALIDATE_RET(f_rng != NULL);
  2810. return mbedtls_ecp_gen_keypair_base(grp, &grp->G, d, Q, f_rng, p_rng);
  2811. }
  2812. /*
  2813. * Generate a keypair, prettier wrapper
  2814. */
  2815. int mbedtls_ecp_gen_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
  2816. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
  2817. {
  2818. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2819. ECP_VALIDATE_RET(key != NULL);
  2820. ECP_VALIDATE_RET(f_rng != NULL);
  2821. if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
  2822. return ret;
  2823. }
  2824. return mbedtls_ecp_gen_keypair(&key->grp, &key->d, &key->Q, f_rng, p_rng);
  2825. }
  2826. #define ECP_CURVE25519_KEY_SIZE 32
  2827. /*
  2828. * Read a private key.
  2829. */
  2830. int mbedtls_ecp_read_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
  2831. const unsigned char *buf, size_t buflen)
  2832. {
  2833. int ret = 0;
  2834. ECP_VALIDATE_RET(key != NULL);
  2835. ECP_VALIDATE_RET(buf != NULL);
  2836. if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
  2837. return ret;
  2838. }
  2839. ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2840. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2841. if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  2842. /*
  2843. * If it is Curve25519 curve then mask the key as mandated by RFC7748
  2844. */
  2845. if (grp_id == MBEDTLS_ECP_DP_CURVE25519) {
  2846. if (buflen != ECP_CURVE25519_KEY_SIZE) {
  2847. return MBEDTLS_ERR_ECP_INVALID_KEY;
  2848. }
  2849. MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&key->d, buf, buflen));
  2850. /* Set the three least significant bits to 0 */
  2851. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 0, 0));
  2852. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 1, 0));
  2853. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 2, 0));
  2854. /* Set the most significant bit to 0 */
  2855. MBEDTLS_MPI_CHK(
  2856. mbedtls_mpi_set_bit(&key->d,
  2857. ECP_CURVE25519_KEY_SIZE * 8 - 1, 0)
  2858. );
  2859. /* Set the second most significant bit to 1 */
  2860. MBEDTLS_MPI_CHK(
  2861. mbedtls_mpi_set_bit(&key->d,
  2862. ECP_CURVE25519_KEY_SIZE * 8 - 2, 1)
  2863. );
  2864. } else {
  2865. ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2866. }
  2867. }
  2868. #endif
  2869. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2870. if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2871. MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&key->d, buf, buflen));
  2872. MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(&key->grp, &key->d));
  2873. }
  2874. #endif
  2875. cleanup:
  2876. if (ret != 0) {
  2877. mbedtls_mpi_free(&key->d);
  2878. }
  2879. return ret;
  2880. }
  2881. /*
  2882. * Write a private key.
  2883. */
  2884. int mbedtls_ecp_write_key(mbedtls_ecp_keypair *key,
  2885. unsigned char *buf, size_t buflen)
  2886. {
  2887. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2888. ECP_VALIDATE_RET(key != NULL);
  2889. ECP_VALIDATE_RET(buflen == 0 || buf != NULL);
  2890. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  2891. if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
  2892. if (key->grp.id == MBEDTLS_ECP_DP_CURVE25519) {
  2893. if (buflen < ECP_CURVE25519_KEY_SIZE) {
  2894. return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
  2895. }
  2896. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&key->d, buf, buflen));
  2897. } else {
  2898. ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
  2899. }
  2900. }
  2901. #endif
  2902. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  2903. if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
  2904. MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&key->d, buf, buflen));
  2905. }
  2906. #endif
  2907. cleanup:
  2908. return ret;
  2909. }
  2910. /*
  2911. * Check a public-private key pair
  2912. */
  2913. int mbedtls_ecp_check_pub_priv(const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv)
  2914. {
  2915. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  2916. mbedtls_ecp_point Q;
  2917. mbedtls_ecp_group grp;
  2918. ECP_VALIDATE_RET(pub != NULL);
  2919. ECP_VALIDATE_RET(prv != NULL);
  2920. if (pub->grp.id == MBEDTLS_ECP_DP_NONE ||
  2921. pub->grp.id != prv->grp.id ||
  2922. mbedtls_mpi_cmp_mpi(&pub->Q.X, &prv->Q.X) ||
  2923. mbedtls_mpi_cmp_mpi(&pub->Q.Y, &prv->Q.Y) ||
  2924. mbedtls_mpi_cmp_mpi(&pub->Q.Z, &prv->Q.Z)) {
  2925. return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2926. }
  2927. mbedtls_ecp_point_init(&Q);
  2928. mbedtls_ecp_group_init(&grp);
  2929. /* mbedtls_ecp_mul() needs a non-const group... */
  2930. mbedtls_ecp_group_copy(&grp, &prv->grp);
  2931. /* Also checks d is valid */
  2932. MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &Q, &prv->d, &prv->grp.G, NULL, NULL));
  2933. if (mbedtls_mpi_cmp_mpi(&Q.X, &prv->Q.X) ||
  2934. mbedtls_mpi_cmp_mpi(&Q.Y, &prv->Q.Y) ||
  2935. mbedtls_mpi_cmp_mpi(&Q.Z, &prv->Q.Z)) {
  2936. ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  2937. goto cleanup;
  2938. }
  2939. cleanup:
  2940. mbedtls_ecp_point_free(&Q);
  2941. mbedtls_ecp_group_free(&grp);
  2942. return ret;
  2943. }
  2944. #if defined(MBEDTLS_SELF_TEST)
  2945. /* Adjust the exponent to be a valid private point for the specified curve.
  2946. * This is sometimes necessary because we use a single set of exponents
  2947. * for all curves but the validity of values depends on the curve. */
  2948. static int self_test_adjust_exponent(const mbedtls_ecp_group *grp,
  2949. mbedtls_mpi *m)
  2950. {
  2951. int ret = 0;
  2952. switch (grp->id) {
  2953. /* If Curve25519 is available, then that's what we use for the
  2954. * Montgomery test, so we don't need the adjustment code. */
  2955. #if !defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
  2956. #if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
  2957. case MBEDTLS_ECP_DP_CURVE448:
  2958. /* Move highest bit from 254 to N-1. Setting bit N-1 is
  2959. * necessary to enforce the highest-bit-set constraint. */
  2960. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, 254, 0));
  2961. MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, grp->nbits, 1));
  2962. /* Copy second-highest bit from 253 to N-2. This is not
  2963. * necessary but improves the test variety a bit. */
  2964. MBEDTLS_MPI_CHK(
  2965. mbedtls_mpi_set_bit(m, grp->nbits - 1,
  2966. mbedtls_mpi_get_bit(m, 253)));
  2967. break;
  2968. #endif
  2969. #endif /* ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) */
  2970. default:
  2971. /* Non-Montgomery curves and Curve25519 need no adjustment. */
  2972. (void) grp;
  2973. (void) m;
  2974. goto cleanup;
  2975. }
  2976. cleanup:
  2977. return ret;
  2978. }
  2979. /* Calculate R = m.P for each m in exponents. Check that the number of
  2980. * basic operations doesn't depend on the value of m. */
  2981. static int self_test_point(int verbose,
  2982. mbedtls_ecp_group *grp,
  2983. mbedtls_ecp_point *R,
  2984. mbedtls_mpi *m,
  2985. const mbedtls_ecp_point *P,
  2986. const char *const *exponents,
  2987. size_t n_exponents)
  2988. {
  2989. int ret = 0;
  2990. size_t i = 0;
  2991. unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
  2992. add_count = 0;
  2993. dbl_count = 0;
  2994. mul_count = 0;
  2995. MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[0]));
  2996. MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m));
  2997. MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, NULL, NULL));
  2998. for (i = 1; i < n_exponents; i++) {
  2999. add_c_prev = add_count;
  3000. dbl_c_prev = dbl_count;
  3001. mul_c_prev = mul_count;
  3002. add_count = 0;
  3003. dbl_count = 0;
  3004. mul_count = 0;
  3005. MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[i]));
  3006. MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m));
  3007. MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, NULL, NULL));
  3008. if (add_count != add_c_prev ||
  3009. dbl_count != dbl_c_prev ||
  3010. mul_count != mul_c_prev) {
  3011. ret = 1;
  3012. break;
  3013. }
  3014. }
  3015. cleanup:
  3016. if (verbose != 0) {
  3017. if (ret != 0) {
  3018. mbedtls_printf("failed (%u)\n", (unsigned int) i);
  3019. } else {
  3020. mbedtls_printf("passed\n");
  3021. }
  3022. }
  3023. return ret;
  3024. }
  3025. /*
  3026. * Checkup routine
  3027. */
  3028. int mbedtls_ecp_self_test(int verbose)
  3029. {
  3030. int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
  3031. mbedtls_ecp_group grp;
  3032. mbedtls_ecp_point R, P;
  3033. mbedtls_mpi m;
  3034. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  3035. /* Exponents especially adapted for secp192k1, which has the lowest
  3036. * order n of all supported curves (secp192r1 is in a slightly larger
  3037. * field but the order of its base point is slightly smaller). */
  3038. const char *sw_exponents[] =
  3039. {
  3040. "000000000000000000000000000000000000000000000001", /* one */
  3041. "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8C", /* n - 1 */
  3042. "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
  3043. "400000000000000000000000000000000000000000000000", /* one and zeros */
  3044. "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
  3045. "555555555555555555555555555555555555555555555555", /* 101010... */
  3046. };
  3047. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  3048. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  3049. const char *m_exponents[] =
  3050. {
  3051. /* Valid private values for Curve25519. In a build with Curve448
  3052. * but not Curve25519, they will be adjusted in
  3053. * self_test_adjust_exponent(). */
  3054. "4000000000000000000000000000000000000000000000000000000000000000",
  3055. "5C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C30",
  3056. "5715ECCE24583F7A7023C24164390586842E816D7280A49EF6DF4EAE6B280BF8",
  3057. "41A2B017516F6D254E1F002BCCBADD54BE30F8CEC737A0E912B4963B6BA74460",
  3058. "5555555555555555555555555555555555555555555555555555555555555550",
  3059. "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8",
  3060. };
  3061. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  3062. mbedtls_ecp_group_init(&grp);
  3063. mbedtls_ecp_point_init(&R);
  3064. mbedtls_ecp_point_init(&P);
  3065. mbedtls_mpi_init(&m);
  3066. #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
  3067. /* Use secp192r1 if available, or any available curve */
  3068. #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
  3069. MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_SECP192R1));
  3070. #else
  3071. MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, mbedtls_ecp_curve_list()->grp_id));
  3072. #endif
  3073. if (verbose != 0) {
  3074. mbedtls_printf(" ECP SW test #1 (constant op_count, base point G): ");
  3075. }
  3076. /* Do a dummy multiplication first to trigger precomputation */
  3077. MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&m, 2));
  3078. MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &P, &m, &grp.G, NULL, NULL));
  3079. ret = self_test_point(verbose,
  3080. &grp, &R, &m, &grp.G,
  3081. sw_exponents,
  3082. sizeof(sw_exponents) / sizeof(sw_exponents[0]));
  3083. if (ret != 0) {
  3084. goto cleanup;
  3085. }
  3086. if (verbose != 0) {
  3087. mbedtls_printf(" ECP SW test #2 (constant op_count, other point): ");
  3088. }
  3089. /* We computed P = 2G last time, use it */
  3090. ret = self_test_point(verbose,
  3091. &grp, &R, &m, &P,
  3092. sw_exponents,
  3093. sizeof(sw_exponents) / sizeof(sw_exponents[0]));
  3094. if (ret != 0) {
  3095. goto cleanup;
  3096. }
  3097. mbedtls_ecp_group_free(&grp);
  3098. mbedtls_ecp_point_free(&R);
  3099. #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
  3100. #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
  3101. if (verbose != 0) {
  3102. mbedtls_printf(" ECP Montgomery test (constant op_count): ");
  3103. }
  3104. #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
  3105. MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE25519));
  3106. #elif defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
  3107. MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE448));
  3108. #else
  3109. #error "MBEDTLS_ECP_MONTGOMERY_ENABLED is defined, but no curve is supported for self-test"
  3110. #endif
  3111. ret = self_test_point(verbose,
  3112. &grp, &R, &m, &grp.G,
  3113. m_exponents,
  3114. sizeof(m_exponents) / sizeof(m_exponents[0]));
  3115. if (ret != 0) {
  3116. goto cleanup;
  3117. }
  3118. #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
  3119. cleanup:
  3120. if (ret < 0 && verbose != 0) {
  3121. mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
  3122. }
  3123. mbedtls_ecp_group_free(&grp);
  3124. mbedtls_ecp_point_free(&R);
  3125. mbedtls_ecp_point_free(&P);
  3126. mbedtls_mpi_free(&m);
  3127. if (verbose != 0) {
  3128. mbedtls_printf("\n");
  3129. }
  3130. return ret;
  3131. }
  3132. #endif /* MBEDTLS_SELF_TEST */
  3133. #endif /* !MBEDTLS_ECP_ALT */
  3134. #endif /* MBEDTLS_ECP_C */