ecp.c 66 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197
  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. unsigned char rnd[MBEDTLS_ECP_MAX_BYTES];
  1649. /*
  1650. * Match the procedure given in RFC 6979 (deterministic ECDSA):
  1651. * - use the same byte ordering;
  1652. * - keep the leftmost nbits bits of the generated octet string;
  1653. * - try until result is in the desired range.
  1654. * This also avoids any biais, which is especially important for ECDSA.
  1655. */
  1656. do
  1657. {
  1658. MBEDTLS_MPI_CHK( f_rng( p_rng, rnd, n_size ) );
  1659. MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( d, rnd, n_size ) );
  1660. MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
  1661. /*
  1662. * Each try has at worst a probability 1/2 of failing (the msb has
  1663. * a probability 1/2 of being 0, and then the result will be < N),
  1664. * so after 30 tries failure probability is a most 2**(-30).
  1665. *
  1666. * For most curves, 1 try is enough with overwhelming probability,
  1667. * since N starts with a lot of 1s in binary, but some curves
  1668. * such as secp224k1 are actually very close to the worst case.
  1669. */
  1670. if( ++count > 30 )
  1671. return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
  1672. }
  1673. while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
  1674. mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );
  1675. }
  1676. else
  1677. #endif /* ECP_SHORTWEIERSTRASS */
  1678. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1679. cleanup:
  1680. if( ret != 0 )
  1681. return( ret );
  1682. return( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
  1683. }
  1684. /*
  1685. * Generate key pair, wrapper for conventional base point
  1686. */
  1687. int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
  1688. mbedtls_mpi *d, mbedtls_ecp_point *Q,
  1689. int (*f_rng)(void *, unsigned char *, size_t),
  1690. void *p_rng )
  1691. {
  1692. return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
  1693. }
  1694. /*
  1695. * Generate a keypair, prettier wrapper
  1696. */
  1697. int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
  1698. int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
  1699. {
  1700. int ret;
  1701. if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
  1702. return( ret );
  1703. return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
  1704. }
  1705. /*
  1706. * Check a public-private key pair
  1707. */
  1708. int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )
  1709. {
  1710. int ret;
  1711. mbedtls_ecp_point Q;
  1712. mbedtls_ecp_group grp;
  1713. if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||
  1714. pub->grp.id != prv->grp.id ||
  1715. mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||
  1716. mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||
  1717. mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
  1718. {
  1719. return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  1720. }
  1721. mbedtls_ecp_point_init( &Q );
  1722. mbedtls_ecp_group_init( &grp );
  1723. /* mbedtls_ecp_mul() needs a non-const group... */
  1724. mbedtls_ecp_group_copy( &grp, &prv->grp );
  1725. /* Also checks d is valid */
  1726. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
  1727. if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||
  1728. mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||
  1729. mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
  1730. {
  1731. ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
  1732. goto cleanup;
  1733. }
  1734. cleanup:
  1735. mbedtls_ecp_point_free( &Q );
  1736. mbedtls_ecp_group_free( &grp );
  1737. return( ret );
  1738. }
  1739. #if defined(MBEDTLS_SELF_TEST)
  1740. /*
  1741. * Checkup routine
  1742. */
  1743. int mbedtls_ecp_self_test( int verbose )
  1744. {
  1745. int ret;
  1746. size_t i;
  1747. mbedtls_ecp_group grp;
  1748. mbedtls_ecp_point R, P;
  1749. mbedtls_mpi m;
  1750. unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
  1751. /* exponents especially adapted for secp192r1 */
  1752. const char *exponents[] =
  1753. {
  1754. "000000000000000000000000000000000000000000000001", /* one */
  1755. "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
  1756. "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
  1757. "400000000000000000000000000000000000000000000000", /* one and zeros */
  1758. "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
  1759. "555555555555555555555555555555555555555555555555", /* 101010... */
  1760. };
  1761. mbedtls_ecp_group_init( &grp );
  1762. mbedtls_ecp_point_init( &R );
  1763. mbedtls_ecp_point_init( &P );
  1764. mbedtls_mpi_init( &m );
  1765. /* Use secp192r1 if available, or any available curve */
  1766. #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
  1767. MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
  1768. #else
  1769. MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
  1770. #endif
  1771. if( verbose != 0 )
  1772. mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
  1773. /* Do a dummy multiplication first to trigger precomputation */
  1774. MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
  1775. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
  1776. add_count = 0;
  1777. dbl_count = 0;
  1778. mul_count = 0;
  1779. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
  1780. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
  1781. for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
  1782. {
  1783. add_c_prev = add_count;
  1784. dbl_c_prev = dbl_count;
  1785. mul_c_prev = mul_count;
  1786. add_count = 0;
  1787. dbl_count = 0;
  1788. mul_count = 0;
  1789. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
  1790. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
  1791. if( add_count != add_c_prev ||
  1792. dbl_count != dbl_c_prev ||
  1793. mul_count != mul_c_prev )
  1794. {
  1795. if( verbose != 0 )
  1796. mbedtls_printf( "failed (%u)\n", (unsigned int) i );
  1797. ret = 1;
  1798. goto cleanup;
  1799. }
  1800. }
  1801. if( verbose != 0 )
  1802. mbedtls_printf( "passed\n" );
  1803. if( verbose != 0 )
  1804. mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
  1805. /* We computed P = 2G last time, use it */
  1806. add_count = 0;
  1807. dbl_count = 0;
  1808. mul_count = 0;
  1809. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
  1810. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
  1811. for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
  1812. {
  1813. add_c_prev = add_count;
  1814. dbl_c_prev = dbl_count;
  1815. mul_c_prev = mul_count;
  1816. add_count = 0;
  1817. dbl_count = 0;
  1818. mul_count = 0;
  1819. MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
  1820. MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
  1821. if( add_count != add_c_prev ||
  1822. dbl_count != dbl_c_prev ||
  1823. mul_count != mul_c_prev )
  1824. {
  1825. if( verbose != 0 )
  1826. mbedtls_printf( "failed (%u)\n", (unsigned int) i );
  1827. ret = 1;
  1828. goto cleanup;
  1829. }
  1830. }
  1831. if( verbose != 0 )
  1832. mbedtls_printf( "passed\n" );
  1833. cleanup:
  1834. if( ret < 0 && verbose != 0 )
  1835. mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
  1836. mbedtls_ecp_group_free( &grp );
  1837. mbedtls_ecp_point_free( &R );
  1838. mbedtls_ecp_point_free( &P );
  1839. mbedtls_mpi_free( &m );
  1840. if( verbose != 0 )
  1841. mbedtls_printf( "\n" );
  1842. return( ret );
  1843. }
  1844. #endif /* MBEDTLS_SELF_TEST */
  1845. #endif /* !MBEDTLS_ECP_ALT */
  1846. #endif /* MBEDTLS_ECP_C */