ecp.c 66 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195
  1. /*
  2. * Elliptic curves over GF(p): generic functions
  3. *
  4. * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
  5. * SPDX-License-Identifier: Apache-2.0
  6. *
  7. * Licensed under the Apache License, Version 2.0 (the "License"); you may
  8. * not use this file except in compliance with the License.
  9. * You may obtain a copy of the License at
  10. *
  11. * http://www.apache.org/licenses/LICENSE-2.0
  12. *
  13. * Unless required by applicable law or agreed to in writing, software
  14. * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  15. * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16. * See the License for the specific language governing permissions and
  17. * limitations under the License.
  18. *
  19. * This file is part of mbed TLS (https://tls.mbed.org)
  20. */
  21. /*
  22. * References:
  23. *
  24. * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
  25. * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
  26. * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
  27. * RFC 4492 for the related TLS structures and constants
  28. *
  29. * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
  30. *
  31. * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
  32. * for elliptic curve cryptosystems. In : Cryptographic Hardware and
  33. * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
  34. * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
  35. *
  36. * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
  37. * render ECC resistant against Side Channel Attacks. IACR Cryptology
  38. * ePrint Archive, 2004, vol. 2004, p. 342.
  39. * <http://eprint.iacr.org/2004/342.pdf>
  40. */
  41. #if !defined(MBEDTLS_CONFIG_FILE)
  42. #include "mbedtls/config.h"
  43. #else
  44. #include MBEDTLS_CONFIG_FILE
  45. #endif
  46. #if defined(MBEDTLS_ECP_C)
  47. #include "mbedtls/ecp.h"
  48. #include "mbedtls/threading.h"
  49. #include <string.h>
  50. #if !defined(MBEDTLS_ECP_ALT)
  51. #if defined(MBEDTLS_PLATFORM_C)
  52. #include "mbedtls/platform.h"
  53. #else
  54. #include <stdlib.h>
  55. #include <stdio.h>
  56. #define mbedtls_printf printf
  57. #define mbedtls_calloc calloc
  58. #define mbedtls_free free
  59. #endif
  60. #include "mbedtls/ecp_internal.h"
  61. #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
  62. !defined(inline) && !defined(__cplusplus)
  63. #define inline __inline
  64. #endif
  65. /* Implementation that should never be optimized out by the compiler */
  66. static void mbedtls_zeroize( void *v, size_t n ) {
  67. volatile unsigned char *p = v; while( n-- ) *p++ = 0;
  68. }
  69. #if defined(MBEDTLS_SELF_TEST)
  70. /*
  71. * Counts of point addition and doubling, and field multiplications.
  72. * Used to test resistance of point multiplication to simple timing attacks.
  73. */
  74. static unsigned long add_count, dbl_count, mul_count;
  75. #endif
  76. #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \
  77. defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \
  78. defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \
  79. defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \
  80. defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \
  81. defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \
  82. defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \
  83. defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \
  84. defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \
  85. defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \
  86. defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
  87. #define ECP_SHORTWEIERSTRASS
  88. #endif
  89. #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
  90. #define ECP_MONTGOMERY
  91. #endif
  92. /*
  93. * Curve types: internal for now, might be exposed later
  94. */
  95. typedef enum
  96. {
  97. ECP_TYPE_NONE = 0,
  98. ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
  99. ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
  100. } ecp_curve_type;
  101. /*
  102. * List of supported curves:
  103. * - internal ID
  104. * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
  105. * - size in bits
  106. * - readable name
  107. *
  108. * Curves are listed in order: largest curves first, and for a given size,
  109. * fastest curves first. This provides the default order for the SSL module.
  110. *
  111. * Reminder: update profiles in x509_crt.c when adding a new curves!
  112. */
  113. static const mbedtls_ecp_curve_info ecp_supported_curves[] =
  114. {
  115. #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
  116. { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
  117. #endif
  118. #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
  119. { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
  120. #endif
  121. #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
  122. { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
  123. #endif
  124. #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
  125. { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
  126. #endif
  127. #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
  128. { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
  129. #endif
  130. #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
  131. { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
  132. #endif
  133. #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
  134. { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
  135. #endif
  136. #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
  137. { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
  138. #endif
  139. #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
  140. { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
  141. #endif
  142. #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
  143. { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
  144. #endif
  145. #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
  146. { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
  147. #endif
  148. { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
  149. };
  150. #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
  151. sizeof( ecp_supported_curves[0] )
  152. static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
  153. /*
  154. * List of supported curves and associated info
  155. */
  156. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
  157. {
  158. return( ecp_supported_curves );
  159. }
  160. /*
  161. * List of supported curves, group ID only
  162. */
  163. const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
  164. {
  165. static int init_done = 0;
  166. if( ! init_done )
  167. {
  168. size_t i = 0;
  169. const mbedtls_ecp_curve_info *curve_info;
  170. for( curve_info = mbedtls_ecp_curve_list();
  171. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  172. curve_info++ )
  173. {
  174. ecp_supported_grp_id[i++] = curve_info->grp_id;
  175. }
  176. ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
  177. init_done = 1;
  178. }
  179. return( ecp_supported_grp_id );
  180. }
  181. /*
  182. * Get the curve info for the internal identifier
  183. */
  184. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
  185. {
  186. const mbedtls_ecp_curve_info *curve_info;
  187. for( curve_info = mbedtls_ecp_curve_list();
  188. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  189. curve_info++ )
  190. {
  191. if( curve_info->grp_id == grp_id )
  192. return( curve_info );
  193. }
  194. return( NULL );
  195. }
  196. /*
  197. * Get the curve info from the TLS identifier
  198. */
  199. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
  200. {
  201. const mbedtls_ecp_curve_info *curve_info;
  202. for( curve_info = mbedtls_ecp_curve_list();
  203. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  204. curve_info++ )
  205. {
  206. if( curve_info->tls_id == tls_id )
  207. return( curve_info );
  208. }
  209. return( NULL );
  210. }
  211. /*
  212. * Get the curve info from the name
  213. */
  214. const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
  215. {
  216. const mbedtls_ecp_curve_info *curve_info;
  217. for( curve_info = mbedtls_ecp_curve_list();
  218. curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
  219. curve_info++ )
  220. {
  221. if( strcmp( curve_info->name, name ) == 0 )
  222. return( curve_info );
  223. }
  224. return( NULL );
  225. }
  226. /*
  227. * Get the type of a curve
  228. */
  229. static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
  230. {
  231. if( grp->G.X.p == NULL )
  232. return( ECP_TYPE_NONE );
  233. if( grp->G.Y.p == NULL )
  234. return( ECP_TYPE_MONTGOMERY );
  235. else
  236. return( ECP_TYPE_SHORT_WEIERSTRASS );
  237. }
  238. /*
  239. * Initialize (the components of) a point
  240. */
  241. void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
  242. {
  243. if( pt == NULL )
  244. return;
  245. mbedtls_mpi_init( &pt->X );
  246. mbedtls_mpi_init( &pt->Y );
  247. mbedtls_mpi_init( &pt->Z );
  248. }
  249. /*
  250. * Initialize (the components of) a group
  251. */
  252. void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
  253. {
  254. if( grp == NULL )
  255. return;
  256. memset( grp, 0, sizeof( mbedtls_ecp_group ) );
  257. }
  258. /*
  259. * Initialize (the components of) a key pair
  260. */
  261. void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
  262. {
  263. if( key == NULL )
  264. return;
  265. mbedtls_ecp_group_init( &key->grp );
  266. mbedtls_mpi_init( &key->d );
  267. mbedtls_ecp_point_init( &key->Q );
  268. }
  269. /*
  270. * Unallocate (the components of) a point
  271. */
  272. void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
  273. {
  274. if( pt == NULL )
  275. return;
  276. mbedtls_mpi_free( &( pt->X ) );
  277. mbedtls_mpi_free( &( pt->Y ) );
  278. mbedtls_mpi_free( &( pt->Z ) );
  279. }
  280. /*
  281. * Unallocate (the components of) a group
  282. */
  283. void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
  284. {
  285. size_t i;
  286. if( grp == NULL )
  287. return;
  288. if( grp->h != 1 )
  289. {
  290. mbedtls_mpi_free( &grp->P );
  291. mbedtls_mpi_free( &grp->A );
  292. mbedtls_mpi_free( &grp->B );
  293. mbedtls_ecp_point_free( &grp->G );
  294. mbedtls_mpi_free( &grp->N );
  295. }
  296. if( grp->T != NULL )
  297. {
  298. for( i = 0; i < grp->T_size; i++ )
  299. mbedtls_ecp_point_free( &grp->T[i] );
  300. mbedtls_free( grp->T );
  301. }
  302. mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
  303. }
  304. /*
  305. * Unallocate (the components of) a key pair
  306. */
  307. void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
  308. {
  309. if( key == NULL )
  310. return;
  311. mbedtls_ecp_group_free( &key->grp );
  312. mbedtls_mpi_free( &key->d );
  313. mbedtls_ecp_point_free( &key->Q );
  314. }
  315. /*
  316. * Copy the contents of a point
  317. */
  318. int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
  319. {
  320. int ret;
  321. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
  322. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
  323. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
  324. cleanup:
  325. return( ret );
  326. }
  327. /*
  328. * Copy the contents of a group object
  329. */
  330. int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
  331. {
  332. return mbedtls_ecp_group_load( dst, src->id );
  333. }
  334. /*
  335. * Set point to zero
  336. */
  337. int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
  338. {
  339. int ret;
  340. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
  341. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
  342. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
  343. cleanup:
  344. return( ret );
  345. }
  346. /*
  347. * Tell if a point is zero
  348. */
  349. int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
  350. {
  351. return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
  352. }
  353. /*
  354. * Compare two points lazyly
  355. */
  356. int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
  357. const mbedtls_ecp_point *Q )
  358. {
  359. if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
  360. mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&
  361. mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )
  362. {
  363. return( 0 );
  364. }
  365. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  366. }
  367. /*
  368. * Import a non-zero point from ASCII strings
  369. */
  370. int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
  371. const char *x, const char *y )
  372. {
  373. int ret;
  374. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
  375. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
  376. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
  377. cleanup:
  378. return( ret );
  379. }
  380. /*
  381. * Export a point into unsigned binary data (SEC1 2.3.3)
  382. */
  383. int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P,
  384. int format, size_t *olen,
  385. unsigned char *buf, size_t buflen )
  386. {
  387. int ret = 0;
  388. size_t plen;
  389. if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
  390. format != MBEDTLS_ECP_PF_COMPRESSED )
  391. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  392. /*
  393. * Common case: P == 0
  394. */
  395. if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
  396. {
  397. if( buflen < 1 )
  398. return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
  399. buf[0] = 0x00;
  400. *olen = 1;
  401. return( 0 );
  402. }
  403. plen = mbedtls_mpi_size( &grp->P );
  404. if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
  405. {
  406. *olen = 2 * plen + 1;
  407. if( buflen < *olen )
  408. return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
  409. buf[0] = 0x04;
  410. MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
  411. MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
  412. }
  413. else if( format == MBEDTLS_ECP_PF_COMPRESSED )
  414. {
  415. *olen = plen + 1;
  416. if( buflen < *olen )
  417. return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
  418. buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
  419. MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
  420. }
  421. cleanup:
  422. return( ret );
  423. }
  424. /*
  425. * Import a point from unsigned binary data (SEC1 2.3.4)
  426. */
  427. int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
  428. const unsigned char *buf, size_t ilen )
  429. {
  430. int ret;
  431. size_t plen;
  432. if( ilen < 1 )
  433. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  434. if( buf[0] == 0x00 )
  435. {
  436. if( ilen == 1 )
  437. return( mbedtls_ecp_set_zero( pt ) );
  438. else
  439. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  440. }
  441. plen = mbedtls_mpi_size( &grp->P );
  442. if( buf[0] != 0x04 )
  443. return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
  444. if( ilen != 2 * plen + 1 )
  445. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  446. MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
  447. MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
  448. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
  449. cleanup:
  450. return( ret );
  451. }
  452. /*
  453. * Import a point from a TLS ECPoint record (RFC 4492)
  454. * struct {
  455. * opaque point <1..2^8-1>;
  456. * } ECPoint;
  457. */
  458. int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
  459. const unsigned char **buf, size_t buf_len )
  460. {
  461. unsigned char data_len;
  462. const unsigned char *buf_start;
  463. /*
  464. * We must have at least two bytes (1 for length, at least one for data)
  465. */
  466. if( buf_len < 2 )
  467. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  468. data_len = *(*buf)++;
  469. if( data_len < 1 || data_len > buf_len - 1 )
  470. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  471. /*
  472. * Save buffer start for read_binary and update buf
  473. */
  474. buf_start = *buf;
  475. *buf += data_len;
  476. return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
  477. }
  478. /*
  479. * Export a point as a TLS ECPoint record (RFC 4492)
  480. * struct {
  481. * opaque point <1..2^8-1>;
  482. * } ECPoint;
  483. */
  484. int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
  485. int format, size_t *olen,
  486. unsigned char *buf, size_t blen )
  487. {
  488. int ret;
  489. /*
  490. * buffer length must be at least one, for our length byte
  491. */
  492. if( blen < 1 )
  493. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  494. if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
  495. olen, buf + 1, blen - 1) ) != 0 )
  496. return( ret );
  497. /*
  498. * write length to the first byte and update total length
  499. */
  500. buf[0] = (unsigned char) *olen;
  501. ++*olen;
  502. return( 0 );
  503. }
  504. /*
  505. * Set a group from an ECParameters record (RFC 4492)
  506. */
  507. int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len )
  508. {
  509. uint16_t tls_id;
  510. const mbedtls_ecp_curve_info *curve_info;
  511. /*
  512. * We expect at least three bytes (see below)
  513. */
  514. if( len < 3 )
  515. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  516. /*
  517. * First byte is curve_type; only named_curve is handled
  518. */
  519. if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
  520. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  521. /*
  522. * Next two bytes are the namedcurve value
  523. */
  524. tls_id = *(*buf)++;
  525. tls_id <<= 8;
  526. tls_id |= *(*buf)++;
  527. if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
  528. return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
  529. return mbedtls_ecp_group_load( grp, curve_info->grp_id );
  530. }
  531. /*
  532. * Write the ECParameters record corresponding to a group (RFC 4492)
  533. */
  534. int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
  535. unsigned char *buf, size_t blen )
  536. {
  537. const mbedtls_ecp_curve_info *curve_info;
  538. if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
  539. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  540. /*
  541. * We are going to write 3 bytes (see below)
  542. */
  543. *olen = 3;
  544. if( blen < *olen )
  545. return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
  546. /*
  547. * First byte is curve_type, always named_curve
  548. */
  549. *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
  550. /*
  551. * Next two bytes are the namedcurve value
  552. */
  553. buf[0] = curve_info->tls_id >> 8;
  554. buf[1] = curve_info->tls_id & 0xFF;
  555. return( 0 );
  556. }
  557. /*
  558. * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
  559. * See the documentation of struct mbedtls_ecp_group.
  560. *
  561. * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
  562. */
  563. static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
  564. {
  565. int ret;
  566. if( grp->modp == NULL )
  567. return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
  568. /* N->s < 0 is a much faster test, which fails only if N is 0 */
  569. if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
  570. mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
  571. {
  572. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  573. }
  574. MBEDTLS_MPI_CHK( grp->modp( N ) );
  575. /* N->s < 0 is a much faster test, which fails only if N is 0 */
  576. while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
  577. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
  578. while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
  579. /* we known P, N and the result are positive */
  580. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
  581. cleanup:
  582. return( ret );
  583. }
  584. /*
  585. * Fast mod-p functions expect their argument to be in the 0..p^2 range.
  586. *
  587. * In order to guarantee that, we need to ensure that operands of
  588. * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
  589. * bring the result back to this range.
  590. *
  591. * The following macros are shortcuts for doing that.
  592. */
  593. /*
  594. * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
  595. */
  596. #if defined(MBEDTLS_SELF_TEST)
  597. #define INC_MUL_COUNT mul_count++;
  598. #else
  599. #define INC_MUL_COUNT
  600. #endif
  601. #define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
  602. while( 0 )
  603. /*
  604. * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
  605. * N->s < 0 is a very fast test, which fails only if N is 0
  606. */
  607. #define MOD_SUB( N ) \
  608. while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \
  609. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
  610. /*
  611. * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
  612. * We known P, N and the result are positive, so sub_abs is correct, and
  613. * a bit faster.
  614. */
  615. #define MOD_ADD( N ) \
  616. while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
  617. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
  618. #if defined(ECP_SHORTWEIERSTRASS)
  619. /*
  620. * For curves in short Weierstrass form, we do all the internal operations in
  621. * Jacobian coordinates.
  622. *
  623. * For multiplication, we'll use a comb method with coutermeasueres against
  624. * SPA, hence timing attacks.
  625. */
  626. /*
  627. * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
  628. * Cost: 1N := 1I + 3M + 1S
  629. */
  630. static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
  631. {
  632. int ret;
  633. mbedtls_mpi Zi, ZZi;
  634. if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
  635. return( 0 );
  636. #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
  637. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  638. {
  639. return mbedtls_internal_ecp_normalize_jac( grp, pt );
  640. }
  641. #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
  642. mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
  643. /*
  644. * X = X / Z^2 mod p
  645. */
  646. MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
  647. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
  648. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
  649. /*
  650. * Y = Y / Z^3 mod p
  651. */
  652. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
  653. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
  654. /*
  655. * Z = 1
  656. */
  657. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
  658. cleanup:
  659. mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
  660. return( ret );
  661. }
  662. /*
  663. * Normalize jacobian coordinates of an array of (pointers to) points,
  664. * using Montgomery's trick to perform only one inversion mod P.
  665. * (See for example Cohen's "A Course in Computational Algebraic Number
  666. * Theory", Algorithm 10.3.4.)
  667. *
  668. * Warning: fails (returning an error) if one of the points is zero!
  669. * This should never happen, see choice of w in ecp_mul_comb().
  670. *
  671. * Cost: 1N(t) := 1I + (6t - 3)M + 1S
  672. */
  673. static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
  674. mbedtls_ecp_point *T[], size_t t_len )
  675. {
  676. int ret;
  677. size_t i;
  678. mbedtls_mpi *c, u, Zi, ZZi;
  679. if( t_len < 2 )
  680. return( ecp_normalize_jac( grp, *T ) );
  681. #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
  682. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  683. {
  684. return mbedtls_internal_ecp_normalize_jac_many(grp, T, t_len);
  685. }
  686. #endif
  687. if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL )
  688. return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
  689. mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
  690. /*
  691. * c[i] = Z_0 * ... * Z_i
  692. */
  693. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
  694. for( i = 1; i < t_len; i++ )
  695. {
  696. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
  697. MOD_MUL( c[i] );
  698. }
  699. /*
  700. * u = 1 / (Z_0 * ... * Z_n) mod P
  701. */
  702. MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
  703. for( i = t_len - 1; ; i-- )
  704. {
  705. /*
  706. * Zi = 1 / Z_i mod p
  707. * u = 1 / (Z_0 * ... * Z_i) mod P
  708. */
  709. if( i == 0 ) {
  710. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
  711. }
  712. else
  713. {
  714. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
  715. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u );
  716. }
  717. /*
  718. * proceed as in normalize()
  719. */
  720. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
  721. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
  722. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
  723. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y );
  724. /*
  725. * Post-precessing: reclaim some memory by shrinking coordinates
  726. * - not storing Z (always 1)
  727. * - shrinking other coordinates, but still keeping the same number of
  728. * limbs as P, as otherwise it will too likely be regrown too fast.
  729. */
  730. MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
  731. MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
  732. mbedtls_mpi_free( &T[i]->Z );
  733. if( i == 0 )
  734. break;
  735. }
  736. cleanup:
  737. mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
  738. for( i = 0; i < t_len; i++ )
  739. mbedtls_mpi_free( &c[i] );
  740. mbedtls_free( c );
  741. return( ret );
  742. }
  743. /*
  744. * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
  745. * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
  746. */
  747. static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
  748. mbedtls_ecp_point *Q,
  749. unsigned char inv )
  750. {
  751. int ret;
  752. unsigned char nonzero;
  753. mbedtls_mpi mQY;
  754. mbedtls_mpi_init( &mQY );
  755. /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
  756. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
  757. nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
  758. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
  759. cleanup:
  760. mbedtls_mpi_free( &mQY );
  761. return( ret );
  762. }
  763. /*
  764. * Point doubling R = 2 P, Jacobian coordinates
  765. *
  766. * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
  767. *
  768. * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
  769. * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
  770. *
  771. * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
  772. *
  773. * Cost: 1D := 3M + 4S (A == 0)
  774. * 4M + 4S (A == -3)
  775. * 3M + 6S + 1a otherwise
  776. */
  777. static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  778. const mbedtls_ecp_point *P )
  779. {
  780. int ret;
  781. mbedtls_mpi M, S, T, U;
  782. #if defined(MBEDTLS_SELF_TEST)
  783. dbl_count++;
  784. #endif
  785. #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
  786. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  787. {
  788. return mbedtls_internal_ecp_double_jac( grp, R, P );
  789. }
  790. #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
  791. mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
  792. /* Special case for A = -3 */
  793. if( grp->A.p == NULL )
  794. {
  795. /* M = 3(X + Z^2)(X - Z^2) */
  796. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
  797. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T );
  798. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U );
  799. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S );
  800. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
  801. }
  802. else
  803. {
  804. /* M = 3.X^2 */
  805. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S );
  806. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
  807. /* Optimize away for "koblitz" curves with A = 0 */
  808. if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
  809. {
  810. /* M += A.Z^4 */
  811. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
  812. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T );
  813. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S );
  814. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M );
  815. }
  816. }
  817. /* S = 4.X.Y^2 */
  818. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T );
  819. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T );
  820. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S );
  821. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S );
  822. /* U = 8.Y^4 */
  823. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U );
  824. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
  825. /* T = M^2 - 2.S */
  826. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T );
  827. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
  828. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
  829. /* S = M(S - T) - U */
  830. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S );
  831. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S );
  832. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S );
  833. /* U = 2.Y.Z */
  834. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U );
  835. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
  836. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
  837. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
  838. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
  839. cleanup:
  840. mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
  841. return( ret );
  842. }
  843. /*
  844. * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
  845. *
  846. * The coordinates of Q must be normalized (= affine),
  847. * but those of P don't need to. R is not normalized.
  848. *
  849. * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
  850. * None of these cases can happen as intermediate step in ecp_mul_comb():
  851. * - at each step, P, Q and R are multiples of the base point, the factor
  852. * being less than its order, so none of them is zero;
  853. * - Q is an odd multiple of the base point, P an even multiple,
  854. * due to the choice of precomputed points in the modified comb method.
  855. * So branches for these cases do not leak secret information.
  856. *
  857. * We accept Q->Z being unset (saving memory in tables) as meaning 1.
  858. *
  859. * Cost: 1A := 8M + 3S
  860. */
  861. static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  862. const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
  863. {
  864. int ret;
  865. mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
  866. #if defined(MBEDTLS_SELF_TEST)
  867. add_count++;
  868. #endif
  869. #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
  870. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  871. {
  872. return mbedtls_internal_ecp_add_mixed( grp, R, P, Q );
  873. }
  874. #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
  875. /*
  876. * Trivial cases: P == 0 or Q == 0 (case 1)
  877. */
  878. if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
  879. return( mbedtls_ecp_copy( R, Q ) );
  880. if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
  881. return( mbedtls_ecp_copy( R, P ) );
  882. /*
  883. * Make sure Q coordinates are normalized
  884. */
  885. if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
  886. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  887. mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
  888. mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
  889. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
  890. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
  891. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
  892. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
  893. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
  894. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
  895. /* Special cases (2) and (3) */
  896. if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
  897. {
  898. if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
  899. {
  900. ret = ecp_double_jac( grp, R, P );
  901. goto cleanup;
  902. }
  903. else
  904. {
  905. ret = mbedtls_ecp_set_zero( R );
  906. goto cleanup;
  907. }
  908. }
  909. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
  910. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
  911. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
  912. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
  913. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
  914. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
  915. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
  916. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
  917. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
  918. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
  919. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
  920. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
  921. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
  922. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
  923. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
  924. cleanup:
  925. mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
  926. mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
  927. return( ret );
  928. }
  929. /*
  930. * Randomize jacobian coordinates:
  931. * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
  932. * This is sort of the reverse operation of ecp_normalize_jac().
  933. *
  934. * This countermeasure was first suggested in [2].
  935. */
  936. static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
  937. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
  938. {
  939. int ret;
  940. mbedtls_mpi l, ll;
  941. size_t p_size;
  942. int count = 0;
  943. #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
  944. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  945. {
  946. return mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng );
  947. }
  948. #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
  949. p_size = ( grp->pbits + 7 ) / 8;
  950. mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
  951. /* Generate l such that 1 < l < p */
  952. do
  953. {
  954. MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
  955. while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
  956. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
  957. if( count++ > 10 )
  958. return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
  959. }
  960. while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
  961. /* Z = l * Z */
  962. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
  963. /* X = l^2 * X */
  964. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
  965. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
  966. /* Y = l^3 * Y */
  967. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
  968. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
  969. cleanup:
  970. mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
  971. return( ret );
  972. }
  973. /*
  974. * Check and define parameters used by the comb method (see below for details)
  975. */
  976. #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
  977. #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
  978. #endif
  979. /* d = ceil( n / w ) */
  980. #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
  981. /* number of precomputed points */
  982. #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
  983. /*
  984. * Compute the representation of m that will be used with our comb method.
  985. *
  986. * The basic comb method is described in GECC 3.44 for example. We use a
  987. * modified version that provides resistance to SPA by avoiding zero
  988. * digits in the representation as in [3]. We modify the method further by
  989. * requiring that all K_i be odd, which has the small cost that our
  990. * representation uses one more K_i, due to carries.
  991. *
  992. * Also, for the sake of compactness, only the seven low-order bits of x[i]
  993. * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in
  994. * the paper): it is set if and only if if s_i == -1;
  995. *
  996. * Calling conventions:
  997. * - x is an array of size d + 1
  998. * - w is the size, ie number of teeth, of the comb, and must be between
  999. * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
  1000. * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
  1001. * (the result will be incorrect if these assumptions are not satisfied)
  1002. */
  1003. static void ecp_comb_fixed( unsigned char x[], size_t d,
  1004. unsigned char w, const mbedtls_mpi *m )
  1005. {
  1006. size_t i, j;
  1007. unsigned char c, cc, adjust;
  1008. memset( x, 0, d+1 );
  1009. /* First get the classical comb values (except for x_d = 0) */
  1010. for( i = 0; i < d; i++ )
  1011. for( j = 0; j < w; j++ )
  1012. x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j;
  1013. /* Now make sure x_1 .. x_d are odd */
  1014. c = 0;
  1015. for( i = 1; i <= d; i++ )
  1016. {
  1017. /* Add carry and update it */
  1018. cc = x[i] & c;
  1019. x[i] = x[i] ^ c;
  1020. c = cc;
  1021. /* Adjust if needed, avoiding branches */
  1022. adjust = 1 - ( x[i] & 0x01 );
  1023. c |= x[i] & ( x[i-1] * adjust );
  1024. x[i] = x[i] ^ ( x[i-1] * adjust );
  1025. x[i-1] |= adjust << 7;
  1026. }
  1027. }
  1028. /*
  1029. * Precompute points for the comb method
  1030. *
  1031. * If i = i_{w-1} ... i_1 is the binary representation of i, then
  1032. * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P
  1033. *
  1034. * T must be able to hold 2^{w - 1} elements
  1035. *
  1036. * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
  1037. */
  1038. static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
  1039. mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
  1040. unsigned char w, size_t d )
  1041. {
  1042. int ret;
  1043. unsigned char i, k;
  1044. size_t j;
  1045. mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
  1046. /*
  1047. * Set T[0] = P and
  1048. * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
  1049. */
  1050. MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );
  1051. k = 0;
  1052. for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
  1053. {
  1054. cur = T + i;
  1055. MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
  1056. for( j = 0; j < d; j++ )
  1057. MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
  1058. TT[k++] = cur;
  1059. }
  1060. MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
  1061. /*
  1062. * Compute the remaining ones using the minimal number of additions
  1063. * Be careful to update T[2^l] only after using it!
  1064. */
  1065. k = 0;
  1066. for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
  1067. {
  1068. j = i;
  1069. while( j-- )
  1070. {
  1071. MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
  1072. TT[k++] = &T[i + j];
  1073. }
  1074. }
  1075. MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
  1076. cleanup:
  1077. return( ret );
  1078. }
  1079. /*
  1080. * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
  1081. */
  1082. static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1083. const mbedtls_ecp_point T[], unsigned char t_len,
  1084. unsigned char i )
  1085. {
  1086. int ret;
  1087. unsigned char ii, j;
  1088. /* Ignore the "sign" bit and scale down */
  1089. ii = ( i & 0x7Fu ) >> 1;
  1090. /* Read the whole table to thwart cache-based timing attacks */
  1091. for( j = 0; j < t_len; j++ )
  1092. {
  1093. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
  1094. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );
  1095. }
  1096. /* Safely invert result if i is "negative" */
  1097. MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
  1098. cleanup:
  1099. return( ret );
  1100. }
  1101. /*
  1102. * Core multiplication algorithm for the (modified) comb method.
  1103. * This part is actually common with the basic comb method (GECC 3.44)
  1104. *
  1105. * Cost: d A + d D + 1 R
  1106. */
  1107. static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1108. const mbedtls_ecp_point T[], unsigned char t_len,
  1109. const unsigned char x[], size_t d,
  1110. int (*f_rng)(void *, unsigned char *, size_t),
  1111. void *p_rng )
  1112. {
  1113. int ret;
  1114. mbedtls_ecp_point Txi;
  1115. size_t i;
  1116. mbedtls_ecp_point_init( &Txi );
  1117. /* Start with a non-zero point and randomize its coordinates */
  1118. i = d;
  1119. MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
  1120. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );
  1121. if( f_rng != 0 )
  1122. MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
  1123. while( i-- != 0 )
  1124. {
  1125. MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
  1126. MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
  1127. MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
  1128. }
  1129. cleanup:
  1130. mbedtls_ecp_point_free( &Txi );
  1131. return( ret );
  1132. }
  1133. /*
  1134. * Multiplication using the comb method,
  1135. * for curves in short Weierstrass form
  1136. */
  1137. static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1138. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  1139. int (*f_rng)(void *, unsigned char *, size_t),
  1140. void *p_rng )
  1141. {
  1142. int ret;
  1143. unsigned char w, m_is_odd, p_eq_g, pre_len, i;
  1144. size_t d;
  1145. unsigned char k[COMB_MAX_D + 1];
  1146. mbedtls_ecp_point *T;
  1147. mbedtls_mpi M, mm;
  1148. mbedtls_mpi_init( &M );
  1149. mbedtls_mpi_init( &mm );
  1150. /* we need N to be odd to trnaform m in an odd number, check now */
  1151. if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )
  1152. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1153. /*
  1154. * Minimize the number of multiplications, that is minimize
  1155. * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
  1156. * (see costs of the various parts, with 1S = 1M)
  1157. */
  1158. w = grp->nbits >= 384 ? 5 : 4;
  1159. /*
  1160. * If P == G, pre-compute a bit more, since this may be re-used later.
  1161. * Just adding one avoids upping the cost of the first mul too much,
  1162. * and the memory cost too.
  1163. */
  1164. #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
  1165. p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
  1166. mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
  1167. if( p_eq_g )
  1168. w++;
  1169. #else
  1170. p_eq_g = 0;
  1171. #endif
  1172. /*
  1173. * Make sure w is within bounds.
  1174. * (The last test is useful only for very small curves in the test suite.)
  1175. */
  1176. if( w > MBEDTLS_ECP_WINDOW_SIZE )
  1177. w = MBEDTLS_ECP_WINDOW_SIZE;
  1178. if( w >= grp->nbits )
  1179. w = 2;
  1180. /* Other sizes that depend on w */
  1181. pre_len = 1U << ( w - 1 );
  1182. d = ( grp->nbits + w - 1 ) / w;
  1183. /*
  1184. * Prepare precomputed points: if P == G we want to
  1185. * use grp->T if already initialized, or initialize it.
  1186. */
  1187. T = p_eq_g ? grp->T : NULL;
  1188. if( T == NULL )
  1189. {
  1190. T = mbedtls_calloc( pre_len, sizeof( mbedtls_ecp_point ) );
  1191. if( T == NULL )
  1192. {
  1193. ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
  1194. goto cleanup;
  1195. }
  1196. MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
  1197. if( p_eq_g )
  1198. {
  1199. grp->T = T;
  1200. grp->T_size = pre_len;
  1201. }
  1202. }
  1203. /*
  1204. * Make sure M is odd (M = m or M = N - m, since N is odd)
  1205. * using the fact that m * P = - (N - m) * P
  1206. */
  1207. m_is_odd = ( mbedtls_mpi_get_bit( m, 0 ) == 1 );
  1208. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
  1209. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );
  1210. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) );
  1211. /*
  1212. * Go for comb multiplication, R = M * P
  1213. */
  1214. ecp_comb_fixed( k, d, w, &M );
  1215. MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
  1216. /*
  1217. * Now get m * P from M * P and normalize it
  1218. */
  1219. MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
  1220. MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
  1221. cleanup:
  1222. if( T != NULL && ! p_eq_g )
  1223. {
  1224. for( i = 0; i < pre_len; i++ )
  1225. mbedtls_ecp_point_free( &T[i] );
  1226. mbedtls_free( T );
  1227. }
  1228. mbedtls_mpi_free( &M );
  1229. mbedtls_mpi_free( &mm );
  1230. if( ret != 0 )
  1231. mbedtls_ecp_point_free( R );
  1232. return( ret );
  1233. }
  1234. #endif /* ECP_SHORTWEIERSTRASS */
  1235. #if defined(ECP_MONTGOMERY)
  1236. /*
  1237. * For Montgomery curves, we do all the internal arithmetic in projective
  1238. * coordinates. Import/export of points uses only the x coordinates, which is
  1239. * internaly represented as X / Z.
  1240. *
  1241. * For scalar multiplication, we'll use a Montgomery ladder.
  1242. */
  1243. /*
  1244. * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
  1245. * Cost: 1M + 1I
  1246. */
  1247. static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )
  1248. {
  1249. int ret;
  1250. #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
  1251. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  1252. {
  1253. return mbedtls_internal_ecp_normalize_mxz( grp, P );
  1254. }
  1255. #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
  1256. MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
  1257. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
  1258. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
  1259. cleanup:
  1260. return( ret );
  1261. }
  1262. /*
  1263. * Randomize projective x/z coordinates:
  1264. * (X, Z) -> (l X, l Z) for random l
  1265. * This is sort of the reverse operation of ecp_normalize_mxz().
  1266. *
  1267. * This countermeasure was first suggested in [2].
  1268. * Cost: 2M
  1269. */
  1270. static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
  1271. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
  1272. {
  1273. int ret;
  1274. mbedtls_mpi l;
  1275. size_t p_size;
  1276. int count = 0;
  1277. #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
  1278. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  1279. {
  1280. return mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );
  1281. }
  1282. #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
  1283. p_size = ( grp->pbits + 7 ) / 8;
  1284. mbedtls_mpi_init( &l );
  1285. /* Generate l such that 1 < l < p */
  1286. do
  1287. {
  1288. MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
  1289. while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
  1290. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
  1291. if( count++ > 10 )
  1292. return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
  1293. }
  1294. while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
  1295. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
  1296. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
  1297. cleanup:
  1298. mbedtls_mpi_free( &l );
  1299. return( ret );
  1300. }
  1301. /*
  1302. * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
  1303. * for Montgomery curves in x/z coordinates.
  1304. *
  1305. * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
  1306. * with
  1307. * d = X1
  1308. * P = (X2, Z2)
  1309. * Q = (X3, Z3)
  1310. * R = (X4, Z4)
  1311. * S = (X5, Z5)
  1312. * and eliminating temporary variables tO, ..., t4.
  1313. *
  1314. * Cost: 5M + 4S
  1315. */
  1316. static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
  1317. mbedtls_ecp_point *R, mbedtls_ecp_point *S,
  1318. const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
  1319. const mbedtls_mpi *d )
  1320. {
  1321. int ret;
  1322. mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
  1323. #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
  1324. if ( mbedtls_internal_ecp_grp_capable( grp ) )
  1325. {
  1326. return mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d );
  1327. }
  1328. #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
  1329. mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );
  1330. mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );
  1331. mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );
  1332. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
  1333. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
  1334. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
  1335. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
  1336. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
  1337. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
  1338. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
  1339. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
  1340. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
  1341. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
  1342. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
  1343. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
  1344. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
  1345. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
  1346. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
  1347. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
  1348. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
  1349. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
  1350. cleanup:
  1351. mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );
  1352. mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );
  1353. mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );
  1354. return( ret );
  1355. }
  1356. /*
  1357. * Multiplication with Montgomery ladder in x/z coordinates,
  1358. * for curves in Montgomery form
  1359. */
  1360. static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1361. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  1362. int (*f_rng)(void *, unsigned char *, size_t),
  1363. void *p_rng )
  1364. {
  1365. int ret;
  1366. size_t i;
  1367. unsigned char b;
  1368. mbedtls_ecp_point RP;
  1369. mbedtls_mpi PX;
  1370. mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );
  1371. /* Save PX and read from P before writing to R, in case P == R */
  1372. MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) );
  1373. MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );
  1374. /* Set R to zero in modified x/z coordinates */
  1375. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) );
  1376. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) );
  1377. mbedtls_mpi_free( &R->Y );
  1378. /* RP.X might be sligtly larger than P, so reduce it */
  1379. MOD_ADD( RP.X );
  1380. /* Randomize coordinates of the starting point */
  1381. if( f_rng != NULL )
  1382. MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
  1383. /* Loop invariant: R = result so far, RP = R + P */
  1384. i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
  1385. while( i-- > 0 )
  1386. {
  1387. b = mbedtls_mpi_get_bit( m, i );
  1388. /*
  1389. * if (b) R = 2R + P else R = 2R,
  1390. * which is:
  1391. * if (b) double_add( RP, R, RP, R )
  1392. * else double_add( R, RP, R, RP )
  1393. * but using safe conditional swaps to avoid leaks
  1394. */
  1395. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
  1396. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
  1397. MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
  1398. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
  1399. MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
  1400. }
  1401. MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
  1402. cleanup:
  1403. mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );
  1404. return( ret );
  1405. }
  1406. #endif /* ECP_MONTGOMERY */
  1407. /*
  1408. * Multiplication R = m * P
  1409. */
  1410. int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1411. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  1412. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
  1413. {
  1414. int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  1415. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  1416. char is_grp_capable = 0;
  1417. #endif
  1418. /* Common sanity checks */
  1419. if( mbedtls_mpi_cmp_int( &P->Z, 1 ) != 0 )
  1420. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1421. if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 ||
  1422. ( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 )
  1423. return( ret );
  1424. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  1425. if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) )
  1426. {
  1427. MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
  1428. }
  1429. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  1430. #if defined(ECP_MONTGOMERY)
  1431. if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
  1432. ret = ecp_mul_mxz( grp, R, m, P, f_rng, p_rng );
  1433. #endif
  1434. #if defined(ECP_SHORTWEIERSTRASS)
  1435. if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
  1436. ret = ecp_mul_comb( grp, R, m, P, f_rng, p_rng );
  1437. #endif
  1438. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  1439. cleanup:
  1440. if ( is_grp_capable )
  1441. {
  1442. mbedtls_internal_ecp_free( grp );
  1443. }
  1444. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  1445. return( ret );
  1446. }
  1447. #if defined(ECP_SHORTWEIERSTRASS)
  1448. /*
  1449. * Check that an affine point is valid as a public key,
  1450. * short weierstrass curves (SEC1 3.2.3.1)
  1451. */
  1452. static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
  1453. {
  1454. int ret;
  1455. mbedtls_mpi YY, RHS;
  1456. /* pt coordinates must be normalized for our checks */
  1457. if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ||
  1458. mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 ||
  1459. mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
  1460. mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
  1461. return( MBEDTLS_ERR_ECP_INVALID_KEY );
  1462. mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );
  1463. /*
  1464. * YY = Y^2
  1465. * RHS = X (X^2 + A) + B = X^3 + A X + B
  1466. */
  1467. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
  1468. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
  1469. /* Special case for A = -3 */
  1470. if( grp->A.p == NULL )
  1471. {
  1472. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
  1473. }
  1474. else
  1475. {
  1476. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
  1477. }
  1478. MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
  1479. MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
  1480. if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
  1481. ret = MBEDTLS_ERR_ECP_INVALID_KEY;
  1482. cleanup:
  1483. mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
  1484. return( ret );
  1485. }
  1486. #endif /* ECP_SHORTWEIERSTRASS */
  1487. /*
  1488. * R = m * P with shortcuts for m == 1 and m == -1
  1489. * NOT constant-time - ONLY for short Weierstrass!
  1490. */
  1491. static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
  1492. mbedtls_ecp_point *R,
  1493. const mbedtls_mpi *m,
  1494. const mbedtls_ecp_point *P )
  1495. {
  1496. int ret;
  1497. if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
  1498. {
  1499. MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
  1500. }
  1501. else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
  1502. {
  1503. MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
  1504. if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
  1505. MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
  1506. }
  1507. else
  1508. {
  1509. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) );
  1510. }
  1511. cleanup:
  1512. return( ret );
  1513. }
  1514. /*
  1515. * Linear combination
  1516. * NOT constant-time
  1517. */
  1518. int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
  1519. const mbedtls_mpi *m, const mbedtls_ecp_point *P,
  1520. const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
  1521. {
  1522. int ret;
  1523. mbedtls_ecp_point mP;
  1524. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  1525. char is_grp_capable = 0;
  1526. #endif
  1527. if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
  1528. return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
  1529. mbedtls_ecp_point_init( &mP );
  1530. MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) );
  1531. MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) );
  1532. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  1533. if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) )
  1534. {
  1535. MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
  1536. }
  1537. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  1538. MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) );
  1539. MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
  1540. cleanup:
  1541. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  1542. if ( is_grp_capable )
  1543. {
  1544. mbedtls_internal_ecp_free( grp );
  1545. }
  1546. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  1547. mbedtls_ecp_point_free( &mP );
  1548. return( ret );
  1549. }
  1550. #if defined(ECP_MONTGOMERY)
  1551. /*
  1552. * Check validity of a public key for Montgomery curves with x-only schemes
  1553. */
  1554. static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
  1555. {
  1556. /* [Curve25519 p. 5] Just check X is the correct number of bytes */
  1557. if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
  1558. return( MBEDTLS_ERR_ECP_INVALID_KEY );
  1559. return( 0 );
  1560. }
  1561. #endif /* ECP_MONTGOMERY */
  1562. /*
  1563. * Check that a point is valid as a public key
  1564. */
  1565. int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
  1566. {
  1567. /* Must use affine coordinates */
  1568. if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )
  1569. return( MBEDTLS_ERR_ECP_INVALID_KEY );
  1570. #if defined(ECP_MONTGOMERY)
  1571. if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
  1572. return( ecp_check_pubkey_mx( grp, pt ) );
  1573. #endif
  1574. #if defined(ECP_SHORTWEIERSTRASS)
  1575. if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
  1576. return( ecp_check_pubkey_sw( grp, pt ) );
  1577. #endif
  1578. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1579. }
  1580. /*
  1581. * Check that an mbedtls_mpi is valid as a private key
  1582. */
  1583. int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d )
  1584. {
  1585. #if defined(ECP_MONTGOMERY)
  1586. if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
  1587. {
  1588. /* see [Curve25519] page 5 */
  1589. if( mbedtls_mpi_get_bit( d, 0 ) != 0 ||
  1590. mbedtls_mpi_get_bit( d, 1 ) != 0 ||
  1591. mbedtls_mpi_get_bit( d, 2 ) != 0 ||
  1592. mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */
  1593. return( MBEDTLS_ERR_ECP_INVALID_KEY );
  1594. else
  1595. return( 0 );
  1596. }
  1597. #endif /* ECP_MONTGOMERY */
  1598. #if defined(ECP_SHORTWEIERSTRASS)
  1599. if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
  1600. {
  1601. /* see SEC1 3.2 */
  1602. if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
  1603. mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
  1604. return( MBEDTLS_ERR_ECP_INVALID_KEY );
  1605. else
  1606. return( 0 );
  1607. }
  1608. #endif /* ECP_SHORTWEIERSTRASS */
  1609. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1610. }
  1611. /*
  1612. * Generate a keypair with configurable base point
  1613. */
  1614. int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,
  1615. const mbedtls_ecp_point *G,
  1616. mbedtls_mpi *d, mbedtls_ecp_point *Q,
  1617. int (*f_rng)(void *, unsigned char *, size_t),
  1618. void *p_rng )
  1619. {
  1620. int ret;
  1621. size_t n_size = ( grp->nbits + 7 ) / 8;
  1622. #if defined(ECP_MONTGOMERY)
  1623. if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
  1624. {
  1625. /* [M225] page 5 */
  1626. size_t b;
  1627. do {
  1628. MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
  1629. } while( mbedtls_mpi_bitlen( d ) == 0);
  1630. /* Make sure the most significant bit is nbits */
  1631. b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
  1632. if( b > grp->nbits )
  1633. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );
  1634. else
  1635. MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );
  1636. /* Make sure the last three bits are unset */
  1637. MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
  1638. MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
  1639. MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
  1640. }
  1641. else
  1642. #endif /* ECP_MONTGOMERY */
  1643. #if defined(ECP_SHORTWEIERSTRASS)
  1644. if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
  1645. {
  1646. /* SEC1 3.2.1: Generate d such that 1 <= n < N */
  1647. int count = 0;
  1648. /*
  1649. * Match the procedure given in RFC 6979 (deterministic ECDSA):
  1650. * - use the same byte ordering;
  1651. * - keep the leftmost nbits bits of the generated octet string;
  1652. * - try until result is in the desired range.
  1653. * This also avoids any biais, which is especially important for ECDSA.
  1654. */
  1655. do
  1656. {
  1657. MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
  1658. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
  1659. /*
  1660. * Each try has at worst a probability 1/2 of failing (the msb has
  1661. * a probability 1/2 of being 0, and then the result will be < N),
  1662. * so after 30 tries failure probability is a most 2**(-30).
  1663. *
  1664. * For most curves, 1 try is enough with overwhelming probability,
  1665. * since N starts with a lot of 1s in binary, but some curves
  1666. * such as secp224k1 are actually very close to the worst case.
  1667. */
  1668. if( ++count > 30 )
  1669. return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
  1670. }
  1671. while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
  1672. mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );
  1673. }
  1674. else
  1675. #endif /* ECP_SHORTWEIERSTRASS */
  1676. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1677. cleanup:
  1678. if( ret != 0 )
  1679. return( ret );
  1680. return( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
  1681. }
  1682. /*
  1683. * Generate key pair, wrapper for conventional base point
  1684. */
  1685. int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
  1686. mbedtls_mpi *d, mbedtls_ecp_point *Q,
  1687. int (*f_rng)(void *, unsigned char *, size_t),
  1688. void *p_rng )
  1689. {
  1690. return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
  1691. }
  1692. /*
  1693. * Generate a keypair, prettier wrapper
  1694. */
  1695. int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
  1696. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
  1697. {
  1698. int ret;
  1699. if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
  1700. return( ret );
  1701. return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
  1702. }
  1703. /*
  1704. * Check a public-private key pair
  1705. */
  1706. int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )
  1707. {
  1708. int ret;
  1709. mbedtls_ecp_point Q;
  1710. mbedtls_ecp_group grp;
  1711. if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||
  1712. pub->grp.id != prv->grp.id ||
  1713. mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||
  1714. mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||
  1715. mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
  1716. {
  1717. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1718. }
  1719. mbedtls_ecp_point_init( &Q );
  1720. mbedtls_ecp_group_init( &grp );
  1721. /* mbedtls_ecp_mul() needs a non-const group... */
  1722. mbedtls_ecp_group_copy( &grp, &prv->grp );
  1723. /* Also checks d is valid */
  1724. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
  1725. if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||
  1726. mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||
  1727. mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
  1728. {
  1729. ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  1730. goto cleanup;
  1731. }
  1732. cleanup:
  1733. mbedtls_ecp_point_free( &Q );
  1734. mbedtls_ecp_group_free( &grp );
  1735. return( ret );
  1736. }
  1737. #if defined(MBEDTLS_SELF_TEST)
  1738. /*
  1739. * Checkup routine
  1740. */
  1741. int mbedtls_ecp_self_test( int verbose )
  1742. {
  1743. int ret;
  1744. size_t i;
  1745. mbedtls_ecp_group grp;
  1746. mbedtls_ecp_point R, P;
  1747. mbedtls_mpi m;
  1748. unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
  1749. /* exponents especially adapted for secp192r1 */
  1750. const char *exponents[] =
  1751. {
  1752. "000000000000000000000000000000000000000000000001", /* one */
  1753. "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
  1754. "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
  1755. "400000000000000000000000000000000000000000000000", /* one and zeros */
  1756. "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
  1757. "555555555555555555555555555555555555555555555555", /* 101010... */
  1758. };
  1759. mbedtls_ecp_group_init( &grp );
  1760. mbedtls_ecp_point_init( &R );
  1761. mbedtls_ecp_point_init( &P );
  1762. mbedtls_mpi_init( &m );
  1763. /* Use secp192r1 if available, or any available curve */
  1764. #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
  1765. MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
  1766. #else
  1767. MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
  1768. #endif
  1769. if( verbose != 0 )
  1770. mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
  1771. /* Do a dummy multiplication first to trigger precomputation */
  1772. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
  1773. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
  1774. add_count = 0;
  1775. dbl_count = 0;
  1776. mul_count = 0;
  1777. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
  1778. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
  1779. for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
  1780. {
  1781. add_c_prev = add_count;
  1782. dbl_c_prev = dbl_count;
  1783. mul_c_prev = mul_count;
  1784. add_count = 0;
  1785. dbl_count = 0;
  1786. mul_count = 0;
  1787. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
  1788. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
  1789. if( add_count != add_c_prev ||
  1790. dbl_count != dbl_c_prev ||
  1791. mul_count != mul_c_prev )
  1792. {
  1793. if( verbose != 0 )
  1794. mbedtls_printf( "failed (%u)\n", (unsigned int) i );
  1795. ret = 1;
  1796. goto cleanup;
  1797. }
  1798. }
  1799. if( verbose != 0 )
  1800. mbedtls_printf( "passed\n" );
  1801. if( verbose != 0 )
  1802. mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
  1803. /* We computed P = 2G last time, use it */
  1804. add_count = 0;
  1805. dbl_count = 0;
  1806. mul_count = 0;
  1807. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
  1808. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
  1809. for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
  1810. {
  1811. add_c_prev = add_count;
  1812. dbl_c_prev = dbl_count;
  1813. mul_c_prev = mul_count;
  1814. add_count = 0;
  1815. dbl_count = 0;
  1816. mul_count = 0;
  1817. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
  1818. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
  1819. if( add_count != add_c_prev ||
  1820. dbl_count != dbl_c_prev ||
  1821. mul_count != mul_c_prev )
  1822. {
  1823. if( verbose != 0 )
  1824. mbedtls_printf( "failed (%u)\n", (unsigned int) i );
  1825. ret = 1;
  1826. goto cleanup;
  1827. }
  1828. }
  1829. if( verbose != 0 )
  1830. mbedtls_printf( "passed\n" );
  1831. cleanup:
  1832. if( ret < 0 && verbose != 0 )
  1833. mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
  1834. mbedtls_ecp_group_free( &grp );
  1835. mbedtls_ecp_point_free( &R );
  1836. mbedtls_ecp_point_free( &P );
  1837. mbedtls_mpi_free( &m );
  1838. if( verbose != 0 )
  1839. mbedtls_printf( "\n" );
  1840. return( ret );
  1841. }
  1842. #endif /* MBEDTLS_SELF_TEST */
  1843. #endif /* !MBEDTLS_ECP_ALT */
  1844. #endif /* MBEDTLS_ECP_C */