ecp_smpl.c 40 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716
  1. /* crypto/ec/ecp_smpl.c */
  2. /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
  3. * for the OpenSSL project.
  4. * Includes code written by Bodo Moeller for the OpenSSL project.
  5. */
  6. /* ====================================================================
  7. * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
  8. *
  9. * Redistribution and use in source and binary forms, with or without
  10. * modification, are permitted provided that the following conditions
  11. * are met:
  12. *
  13. * 1. Redistributions of source code must retain the above copyright
  14. * notice, this list of conditions and the following disclaimer.
  15. *
  16. * 2. Redistributions in binary form must reproduce the above copyright
  17. * notice, this list of conditions and the following disclaimer in
  18. * the documentation and/or other materials provided with the
  19. * distribution.
  20. *
  21. * 3. All advertising materials mentioning features or use of this
  22. * software must display the following acknowledgment:
  23. * "This product includes software developed by the OpenSSL Project
  24. * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  25. *
  26. * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  27. * endorse or promote products derived from this software without
  28. * prior written permission. For written permission, please contact
  29. * openssl-core@openssl.org.
  30. *
  31. * 5. Products derived from this software may not be called "OpenSSL"
  32. * nor may "OpenSSL" appear in their names without prior written
  33. * permission of the OpenSSL Project.
  34. *
  35. * 6. Redistributions of any form whatsoever must retain the following
  36. * acknowledgment:
  37. * "This product includes software developed by the OpenSSL Project
  38. * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  39. *
  40. * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  41. * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  43. * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
  44. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  45. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  46. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  47. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  49. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  50. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  51. * OF THE POSSIBILITY OF SUCH DAMAGE.
  52. * ====================================================================
  53. *
  54. * This product includes cryptographic software written by Eric Young
  55. * (eay@cryptsoft.com). This product includes software written by Tim
  56. * Hudson (tjh@cryptsoft.com).
  57. *
  58. */
  59. /* ====================================================================
  60. * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  61. * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  62. * and contributed to the OpenSSL project.
  63. */
  64. #include <openssl/err.h>
  65. #include <openssl/symhacks.h>
  66. #include "ec_lcl.h"
  67. const EC_METHOD *EC_GFp_simple_method(void)
  68. {
  69. static const EC_METHOD ret = {
  70. NID_X9_62_prime_field,
  71. ec_GFp_simple_group_init,
  72. ec_GFp_simple_group_finish,
  73. ec_GFp_simple_group_clear_finish,
  74. ec_GFp_simple_group_copy,
  75. ec_GFp_simple_group_set_curve,
  76. ec_GFp_simple_group_get_curve,
  77. ec_GFp_simple_group_get_degree,
  78. ec_GFp_simple_group_check_discriminant,
  79. ec_GFp_simple_point_init,
  80. ec_GFp_simple_point_finish,
  81. ec_GFp_simple_point_clear_finish,
  82. ec_GFp_simple_point_copy,
  83. ec_GFp_simple_point_set_to_infinity,
  84. ec_GFp_simple_set_Jprojective_coordinates_GFp,
  85. ec_GFp_simple_get_Jprojective_coordinates_GFp,
  86. ec_GFp_simple_point_set_affine_coordinates,
  87. ec_GFp_simple_point_get_affine_coordinates,
  88. ec_GFp_simple_set_compressed_coordinates,
  89. ec_GFp_simple_point2oct,
  90. ec_GFp_simple_oct2point,
  91. ec_GFp_simple_add,
  92. ec_GFp_simple_dbl,
  93. ec_GFp_simple_invert,
  94. ec_GFp_simple_is_at_infinity,
  95. ec_GFp_simple_is_on_curve,
  96. ec_GFp_simple_cmp,
  97. ec_GFp_simple_make_affine,
  98. ec_GFp_simple_points_make_affine,
  99. 0 /* mul */,
  100. 0 /* precompute_mult */,
  101. 0 /* have_precompute_mult */,
  102. ec_GFp_simple_field_mul,
  103. ec_GFp_simple_field_sqr,
  104. 0 /* field_div */,
  105. 0 /* field_encode */,
  106. 0 /* field_decode */,
  107. 0 /* field_set_to_one */ };
  108. return &ret;
  109. }
  110. /* Most method functions in this file are designed to work with
  111. * non-trivial representations of field elements if necessary
  112. * (see ecp_mont.c): while standard modular addition and subtraction
  113. * are used, the field_mul and field_sqr methods will be used for
  114. * multiplication, and field_encode and field_decode (if defined)
  115. * will be used for converting between representations.
  116. * Functions ec_GFp_simple_points_make_affine() and
  117. * ec_GFp_simple_point_get_affine_coordinates() specifically assume
  118. * that if a non-trivial representation is used, it is a Montgomery
  119. * representation (i.e. 'encoding' means multiplying by some factor R).
  120. */
  121. int ec_GFp_simple_group_init(EC_GROUP *group)
  122. {
  123. BN_init(&group->field);
  124. BN_init(&group->a);
  125. BN_init(&group->b);
  126. group->a_is_minus3 = 0;
  127. return 1;
  128. }
  129. void ec_GFp_simple_group_finish(EC_GROUP *group)
  130. {
  131. BN_free(&group->field);
  132. BN_free(&group->a);
  133. BN_free(&group->b);
  134. }
  135. void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
  136. {
  137. BN_clear_free(&group->field);
  138. BN_clear_free(&group->a);
  139. BN_clear_free(&group->b);
  140. }
  141. int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
  142. {
  143. if (!BN_copy(&dest->field, &src->field)) return 0;
  144. if (!BN_copy(&dest->a, &src->a)) return 0;
  145. if (!BN_copy(&dest->b, &src->b)) return 0;
  146. dest->a_is_minus3 = src->a_is_minus3;
  147. return 1;
  148. }
  149. int ec_GFp_simple_group_set_curve(EC_GROUP *group,
  150. const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  151. {
  152. int ret = 0;
  153. BN_CTX *new_ctx = NULL;
  154. BIGNUM *tmp_a;
  155. /* p must be a prime > 3 */
  156. if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
  157. {
  158. ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
  159. return 0;
  160. }
  161. if (ctx == NULL)
  162. {
  163. ctx = new_ctx = BN_CTX_new();
  164. if (ctx == NULL)
  165. return 0;
  166. }
  167. BN_CTX_start(ctx);
  168. tmp_a = BN_CTX_get(ctx);
  169. if (tmp_a == NULL) goto err;
  170. /* group->field */
  171. if (!BN_copy(&group->field, p)) goto err;
  172. BN_set_negative(&group->field, 0);
  173. /* group->a */
  174. if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
  175. if (group->meth->field_encode)
  176. { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
  177. else
  178. if (!BN_copy(&group->a, tmp_a)) goto err;
  179. /* group->b */
  180. if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
  181. if (group->meth->field_encode)
  182. if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
  183. /* group->a_is_minus3 */
  184. if (!BN_add_word(tmp_a, 3)) goto err;
  185. group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
  186. ret = 1;
  187. err:
  188. BN_CTX_end(ctx);
  189. if (new_ctx != NULL)
  190. BN_CTX_free(new_ctx);
  191. return ret;
  192. }
  193. int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
  194. {
  195. int ret = 0;
  196. BN_CTX *new_ctx = NULL;
  197. if (p != NULL)
  198. {
  199. if (!BN_copy(p, &group->field)) return 0;
  200. }
  201. if (a != NULL || b != NULL)
  202. {
  203. if (group->meth->field_decode)
  204. {
  205. if (ctx == NULL)
  206. {
  207. ctx = new_ctx = BN_CTX_new();
  208. if (ctx == NULL)
  209. return 0;
  210. }
  211. if (a != NULL)
  212. {
  213. if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
  214. }
  215. if (b != NULL)
  216. {
  217. if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
  218. }
  219. }
  220. else
  221. {
  222. if (a != NULL)
  223. {
  224. if (!BN_copy(a, &group->a)) goto err;
  225. }
  226. if (b != NULL)
  227. {
  228. if (!BN_copy(b, &group->b)) goto err;
  229. }
  230. }
  231. }
  232. ret = 1;
  233. err:
  234. if (new_ctx)
  235. BN_CTX_free(new_ctx);
  236. return ret;
  237. }
  238. int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
  239. {
  240. return BN_num_bits(&group->field);
  241. }
  242. int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
  243. {
  244. int ret = 0;
  245. BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
  246. const BIGNUM *p = &group->field;
  247. BN_CTX *new_ctx = NULL;
  248. if (ctx == NULL)
  249. {
  250. ctx = new_ctx = BN_CTX_new();
  251. if (ctx == NULL)
  252. {
  253. ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
  254. goto err;
  255. }
  256. }
  257. BN_CTX_start(ctx);
  258. a = BN_CTX_get(ctx);
  259. b = BN_CTX_get(ctx);
  260. tmp_1 = BN_CTX_get(ctx);
  261. tmp_2 = BN_CTX_get(ctx);
  262. order = BN_CTX_get(ctx);
  263. if (order == NULL) goto err;
  264. if (group->meth->field_decode)
  265. {
  266. if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
  267. if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
  268. }
  269. else
  270. {
  271. if (!BN_copy(a, &group->a)) goto err;
  272. if (!BN_copy(b, &group->b)) goto err;
  273. }
  274. /* check the discriminant:
  275. * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
  276. * 0 =< a, b < p */
  277. if (BN_is_zero(a))
  278. {
  279. if (BN_is_zero(b)) goto err;
  280. }
  281. else if (!BN_is_zero(b))
  282. {
  283. if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
  284. if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
  285. if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
  286. /* tmp_1 = 4*a^3 */
  287. if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
  288. if (!BN_mul_word(tmp_2, 27)) goto err;
  289. /* tmp_2 = 27*b^2 */
  290. if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
  291. if (BN_is_zero(a)) goto err;
  292. }
  293. ret = 1;
  294. err:
  295. if (ctx != NULL)
  296. BN_CTX_end(ctx);
  297. if (new_ctx != NULL)
  298. BN_CTX_free(new_ctx);
  299. return ret;
  300. }
  301. int ec_GFp_simple_point_init(EC_POINT *point)
  302. {
  303. BN_init(&point->X);
  304. BN_init(&point->Y);
  305. BN_init(&point->Z);
  306. point->Z_is_one = 0;
  307. return 1;
  308. }
  309. void ec_GFp_simple_point_finish(EC_POINT *point)
  310. {
  311. BN_free(&point->X);
  312. BN_free(&point->Y);
  313. BN_free(&point->Z);
  314. }
  315. void ec_GFp_simple_point_clear_finish(EC_POINT *point)
  316. {
  317. BN_clear_free(&point->X);
  318. BN_clear_free(&point->Y);
  319. BN_clear_free(&point->Z);
  320. point->Z_is_one = 0;
  321. }
  322. int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
  323. {
  324. if (!BN_copy(&dest->X, &src->X)) return 0;
  325. if (!BN_copy(&dest->Y, &src->Y)) return 0;
  326. if (!BN_copy(&dest->Z, &src->Z)) return 0;
  327. dest->Z_is_one = src->Z_is_one;
  328. return 1;
  329. }
  330. int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
  331. {
  332. point->Z_is_one = 0;
  333. BN_zero(&point->Z);
  334. return 1;
  335. }
  336. int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
  337. const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
  338. {
  339. BN_CTX *new_ctx = NULL;
  340. int ret = 0;
  341. if (ctx == NULL)
  342. {
  343. ctx = new_ctx = BN_CTX_new();
  344. if (ctx == NULL)
  345. return 0;
  346. }
  347. if (x != NULL)
  348. {
  349. if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
  350. if (group->meth->field_encode)
  351. {
  352. if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
  353. }
  354. }
  355. if (y != NULL)
  356. {
  357. if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
  358. if (group->meth->field_encode)
  359. {
  360. if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
  361. }
  362. }
  363. if (z != NULL)
  364. {
  365. int Z_is_one;
  366. if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
  367. Z_is_one = BN_is_one(&point->Z);
  368. if (group->meth->field_encode)
  369. {
  370. if (Z_is_one && (group->meth->field_set_to_one != 0))
  371. {
  372. if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
  373. }
  374. else
  375. {
  376. if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
  377. }
  378. }
  379. point->Z_is_one = Z_is_one;
  380. }
  381. ret = 1;
  382. err:
  383. if (new_ctx != NULL)
  384. BN_CTX_free(new_ctx);
  385. return ret;
  386. }
  387. int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
  388. BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
  389. {
  390. BN_CTX *new_ctx = NULL;
  391. int ret = 0;
  392. if (group->meth->field_decode != 0)
  393. {
  394. if (ctx == NULL)
  395. {
  396. ctx = new_ctx = BN_CTX_new();
  397. if (ctx == NULL)
  398. return 0;
  399. }
  400. if (x != NULL)
  401. {
  402. if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
  403. }
  404. if (y != NULL)
  405. {
  406. if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
  407. }
  408. if (z != NULL)
  409. {
  410. if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
  411. }
  412. }
  413. else
  414. {
  415. if (x != NULL)
  416. {
  417. if (!BN_copy(x, &point->X)) goto err;
  418. }
  419. if (y != NULL)
  420. {
  421. if (!BN_copy(y, &point->Y)) goto err;
  422. }
  423. if (z != NULL)
  424. {
  425. if (!BN_copy(z, &point->Z)) goto err;
  426. }
  427. }
  428. ret = 1;
  429. err:
  430. if (new_ctx != NULL)
  431. BN_CTX_free(new_ctx);
  432. return ret;
  433. }
  434. int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
  435. const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
  436. {
  437. if (x == NULL || y == NULL)
  438. {
  439. /* unlike for projective coordinates, we do not tolerate this */
  440. ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
  441. return 0;
  442. }
  443. return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
  444. }
  445. int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
  446. BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
  447. {
  448. BN_CTX *new_ctx = NULL;
  449. BIGNUM *Z, *Z_1, *Z_2, *Z_3;
  450. const BIGNUM *Z_;
  451. int ret = 0;
  452. if (EC_POINT_is_at_infinity(group, point))
  453. {
  454. ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
  455. return 0;
  456. }
  457. if (ctx == NULL)
  458. {
  459. ctx = new_ctx = BN_CTX_new();
  460. if (ctx == NULL)
  461. return 0;
  462. }
  463. BN_CTX_start(ctx);
  464. Z = BN_CTX_get(ctx);
  465. Z_1 = BN_CTX_get(ctx);
  466. Z_2 = BN_CTX_get(ctx);
  467. Z_3 = BN_CTX_get(ctx);
  468. if (Z_3 == NULL) goto err;
  469. /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */
  470. if (group->meth->field_decode)
  471. {
  472. if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
  473. Z_ = Z;
  474. }
  475. else
  476. {
  477. Z_ = &point->Z;
  478. }
  479. if (BN_is_one(Z_))
  480. {
  481. if (group->meth->field_decode)
  482. {
  483. if (x != NULL)
  484. {
  485. if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
  486. }
  487. if (y != NULL)
  488. {
  489. if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
  490. }
  491. }
  492. else
  493. {
  494. if (x != NULL)
  495. {
  496. if (!BN_copy(x, &point->X)) goto err;
  497. }
  498. if (y != NULL)
  499. {
  500. if (!BN_copy(y, &point->Y)) goto err;
  501. }
  502. }
  503. }
  504. else
  505. {
  506. if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
  507. {
  508. ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
  509. goto err;
  510. }
  511. if (group->meth->field_encode == 0)
  512. {
  513. /* field_sqr works on standard representation */
  514. if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
  515. }
  516. else
  517. {
  518. if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
  519. }
  520. if (x != NULL)
  521. {
  522. /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
  523. if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
  524. }
  525. if (y != NULL)
  526. {
  527. if (group->meth->field_encode == 0)
  528. {
  529. /* field_mul works on standard representation */
  530. if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
  531. }
  532. else
  533. {
  534. if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
  535. }
  536. /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
  537. if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
  538. }
  539. }
  540. ret = 1;
  541. err:
  542. BN_CTX_end(ctx);
  543. if (new_ctx != NULL)
  544. BN_CTX_free(new_ctx);
  545. return ret;
  546. }
  547. int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
  548. const BIGNUM *x_, int y_bit, BN_CTX *ctx)
  549. {
  550. BN_CTX *new_ctx = NULL;
  551. BIGNUM *tmp1, *tmp2, *x, *y;
  552. int ret = 0;
  553. /* clear error queue*/
  554. ERR_clear_error();
  555. if (ctx == NULL)
  556. {
  557. ctx = new_ctx = BN_CTX_new();
  558. if (ctx == NULL)
  559. return 0;
  560. }
  561. y_bit = (y_bit != 0);
  562. BN_CTX_start(ctx);
  563. tmp1 = BN_CTX_get(ctx);
  564. tmp2 = BN_CTX_get(ctx);
  565. x = BN_CTX_get(ctx);
  566. y = BN_CTX_get(ctx);
  567. if (y == NULL) goto err;
  568. /* Recover y. We have a Weierstrass equation
  569. * y^2 = x^3 + a*x + b,
  570. * so y is one of the square roots of x^3 + a*x + b.
  571. */
  572. /* tmp1 := x^3 */
  573. if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
  574. if (group->meth->field_decode == 0)
  575. {
  576. /* field_{sqr,mul} work on standard representation */
  577. if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
  578. if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
  579. }
  580. else
  581. {
  582. if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
  583. if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
  584. }
  585. /* tmp1 := tmp1 + a*x */
  586. if (group->a_is_minus3)
  587. {
  588. if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
  589. if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
  590. if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
  591. }
  592. else
  593. {
  594. if (group->meth->field_decode)
  595. {
  596. if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
  597. if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
  598. }
  599. else
  600. {
  601. /* field_mul works on standard representation */
  602. if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
  603. }
  604. if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
  605. }
  606. /* tmp1 := tmp1 + b */
  607. if (group->meth->field_decode)
  608. {
  609. if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
  610. if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
  611. }
  612. else
  613. {
  614. if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
  615. }
  616. if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
  617. {
  618. unsigned long err = ERR_peek_last_error();
  619. if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
  620. {
  621. ERR_clear_error();
  622. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
  623. }
  624. else
  625. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
  626. goto err;
  627. }
  628. if (y_bit != BN_is_odd(y))
  629. {
  630. if (BN_is_zero(y))
  631. {
  632. int kron;
  633. kron = BN_kronecker(x, &group->field, ctx);
  634. if (kron == -2) goto err;
  635. if (kron == 1)
  636. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
  637. else
  638. /* BN_mod_sqrt() should have cought this error (not a square) */
  639. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
  640. goto err;
  641. }
  642. if (!BN_usub(y, &group->field, y)) goto err;
  643. }
  644. if (y_bit != BN_is_odd(y))
  645. {
  646. ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
  647. goto err;
  648. }
  649. if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  650. ret = 1;
  651. err:
  652. BN_CTX_end(ctx);
  653. if (new_ctx != NULL)
  654. BN_CTX_free(new_ctx);
  655. return ret;
  656. }
  657. size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
  658. unsigned char *buf, size_t len, BN_CTX *ctx)
  659. {
  660. size_t ret;
  661. BN_CTX *new_ctx = NULL;
  662. int used_ctx = 0;
  663. BIGNUM *x, *y;
  664. size_t field_len, i, skip;
  665. if ((form != POINT_CONVERSION_COMPRESSED)
  666. && (form != POINT_CONVERSION_UNCOMPRESSED)
  667. && (form != POINT_CONVERSION_HYBRID))
  668. {
  669. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
  670. goto err;
  671. }
  672. if (EC_POINT_is_at_infinity(group, point))
  673. {
  674. /* encodes to a single 0 octet */
  675. if (buf != NULL)
  676. {
  677. if (len < 1)
  678. {
  679. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
  680. return 0;
  681. }
  682. buf[0] = 0;
  683. }
  684. return 1;
  685. }
  686. /* ret := required output buffer length */
  687. field_len = BN_num_bytes(&group->field);
  688. ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
  689. /* if 'buf' is NULL, just return required length */
  690. if (buf != NULL)
  691. {
  692. if (len < ret)
  693. {
  694. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
  695. goto err;
  696. }
  697. if (ctx == NULL)
  698. {
  699. ctx = new_ctx = BN_CTX_new();
  700. if (ctx == NULL)
  701. return 0;
  702. }
  703. BN_CTX_start(ctx);
  704. used_ctx = 1;
  705. x = BN_CTX_get(ctx);
  706. y = BN_CTX_get(ctx);
  707. if (y == NULL) goto err;
  708. if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  709. if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
  710. buf[0] = form + 1;
  711. else
  712. buf[0] = form;
  713. i = 1;
  714. skip = field_len - BN_num_bytes(x);
  715. if (skip > field_len)
  716. {
  717. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  718. goto err;
  719. }
  720. while (skip > 0)
  721. {
  722. buf[i++] = 0;
  723. skip--;
  724. }
  725. skip = BN_bn2bin(x, buf + i);
  726. i += skip;
  727. if (i != 1 + field_len)
  728. {
  729. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  730. goto err;
  731. }
  732. if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
  733. {
  734. skip = field_len - BN_num_bytes(y);
  735. if (skip > field_len)
  736. {
  737. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  738. goto err;
  739. }
  740. while (skip > 0)
  741. {
  742. buf[i++] = 0;
  743. skip--;
  744. }
  745. skip = BN_bn2bin(y, buf + i);
  746. i += skip;
  747. }
  748. if (i != ret)
  749. {
  750. ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
  751. goto err;
  752. }
  753. }
  754. if (used_ctx)
  755. BN_CTX_end(ctx);
  756. if (new_ctx != NULL)
  757. BN_CTX_free(new_ctx);
  758. return ret;
  759. err:
  760. if (used_ctx)
  761. BN_CTX_end(ctx);
  762. if (new_ctx != NULL)
  763. BN_CTX_free(new_ctx);
  764. return 0;
  765. }
  766. int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
  767. const unsigned char *buf, size_t len, BN_CTX *ctx)
  768. {
  769. point_conversion_form_t form;
  770. int y_bit;
  771. BN_CTX *new_ctx = NULL;
  772. BIGNUM *x, *y;
  773. size_t field_len, enc_len;
  774. int ret = 0;
  775. if (len == 0)
  776. {
  777. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
  778. return 0;
  779. }
  780. form = buf[0];
  781. y_bit = form & 1;
  782. form = form & ~1U;
  783. if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
  784. && (form != POINT_CONVERSION_UNCOMPRESSED)
  785. && (form != POINT_CONVERSION_HYBRID))
  786. {
  787. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  788. return 0;
  789. }
  790. if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
  791. {
  792. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  793. return 0;
  794. }
  795. if (form == 0)
  796. {
  797. if (len != 1)
  798. {
  799. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  800. return 0;
  801. }
  802. return EC_POINT_set_to_infinity(group, point);
  803. }
  804. field_len = BN_num_bytes(&group->field);
  805. enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
  806. if (len != enc_len)
  807. {
  808. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  809. return 0;
  810. }
  811. if (ctx == NULL)
  812. {
  813. ctx = new_ctx = BN_CTX_new();
  814. if (ctx == NULL)
  815. return 0;
  816. }
  817. BN_CTX_start(ctx);
  818. x = BN_CTX_get(ctx);
  819. y = BN_CTX_get(ctx);
  820. if (y == NULL) goto err;
  821. if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
  822. if (BN_ucmp(x, &group->field) >= 0)
  823. {
  824. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  825. goto err;
  826. }
  827. if (form == POINT_CONVERSION_COMPRESSED)
  828. {
  829. if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
  830. }
  831. else
  832. {
  833. if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
  834. if (BN_ucmp(y, &group->field) >= 0)
  835. {
  836. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  837. goto err;
  838. }
  839. if (form == POINT_CONVERSION_HYBRID)
  840. {
  841. if (y_bit != BN_is_odd(y))
  842. {
  843. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
  844. goto err;
  845. }
  846. }
  847. if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  848. }
  849. if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
  850. {
  851. ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
  852. goto err;
  853. }
  854. ret = 1;
  855. err:
  856. BN_CTX_end(ctx);
  857. if (new_ctx != NULL)
  858. BN_CTX_free(new_ctx);
  859. return ret;
  860. }
  861. int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
  862. {
  863. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  864. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  865. const BIGNUM *p;
  866. BN_CTX *new_ctx = NULL;
  867. BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
  868. int ret = 0;
  869. if (a == b)
  870. return EC_POINT_dbl(group, r, a, ctx);
  871. if (EC_POINT_is_at_infinity(group, a))
  872. return EC_POINT_copy(r, b);
  873. if (EC_POINT_is_at_infinity(group, b))
  874. return EC_POINT_copy(r, a);
  875. field_mul = group->meth->field_mul;
  876. field_sqr = group->meth->field_sqr;
  877. p = &group->field;
  878. if (ctx == NULL)
  879. {
  880. ctx = new_ctx = BN_CTX_new();
  881. if (ctx == NULL)
  882. return 0;
  883. }
  884. BN_CTX_start(ctx);
  885. n0 = BN_CTX_get(ctx);
  886. n1 = BN_CTX_get(ctx);
  887. n2 = BN_CTX_get(ctx);
  888. n3 = BN_CTX_get(ctx);
  889. n4 = BN_CTX_get(ctx);
  890. n5 = BN_CTX_get(ctx);
  891. n6 = BN_CTX_get(ctx);
  892. if (n6 == NULL) goto end;
  893. /* Note that in this function we must not read components of 'a' or 'b'
  894. * once we have written the corresponding components of 'r'.
  895. * ('r' might be one of 'a' or 'b'.)
  896. */
  897. /* n1, n2 */
  898. if (b->Z_is_one)
  899. {
  900. if (!BN_copy(n1, &a->X)) goto end;
  901. if (!BN_copy(n2, &a->Y)) goto end;
  902. /* n1 = X_a */
  903. /* n2 = Y_a */
  904. }
  905. else
  906. {
  907. if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
  908. if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
  909. /* n1 = X_a * Z_b^2 */
  910. if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
  911. if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
  912. /* n2 = Y_a * Z_b^3 */
  913. }
  914. /* n3, n4 */
  915. if (a->Z_is_one)
  916. {
  917. if (!BN_copy(n3, &b->X)) goto end;
  918. if (!BN_copy(n4, &b->Y)) goto end;
  919. /* n3 = X_b */
  920. /* n4 = Y_b */
  921. }
  922. else
  923. {
  924. if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
  925. if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
  926. /* n3 = X_b * Z_a^2 */
  927. if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
  928. if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
  929. /* n4 = Y_b * Z_a^3 */
  930. }
  931. /* n5, n6 */
  932. if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
  933. if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
  934. /* n5 = n1 - n3 */
  935. /* n6 = n2 - n4 */
  936. if (BN_is_zero(n5))
  937. {
  938. if (BN_is_zero(n6))
  939. {
  940. /* a is the same point as b */
  941. BN_CTX_end(ctx);
  942. ret = EC_POINT_dbl(group, r, a, ctx);
  943. ctx = NULL;
  944. goto end;
  945. }
  946. else
  947. {
  948. /* a is the inverse of b */
  949. BN_zero(&r->Z);
  950. r->Z_is_one = 0;
  951. ret = 1;
  952. goto end;
  953. }
  954. }
  955. /* 'n7', 'n8' */
  956. if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
  957. if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
  958. /* 'n7' = n1 + n3 */
  959. /* 'n8' = n2 + n4 */
  960. /* Z_r */
  961. if (a->Z_is_one && b->Z_is_one)
  962. {
  963. if (!BN_copy(&r->Z, n5)) goto end;
  964. }
  965. else
  966. {
  967. if (a->Z_is_one)
  968. { if (!BN_copy(n0, &b->Z)) goto end; }
  969. else if (b->Z_is_one)
  970. { if (!BN_copy(n0, &a->Z)) goto end; }
  971. else
  972. { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
  973. if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
  974. }
  975. r->Z_is_one = 0;
  976. /* Z_r = Z_a * Z_b * n5 */
  977. /* X_r */
  978. if (!field_sqr(group, n0, n6, ctx)) goto end;
  979. if (!field_sqr(group, n4, n5, ctx)) goto end;
  980. if (!field_mul(group, n3, n1, n4, ctx)) goto end;
  981. if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
  982. /* X_r = n6^2 - n5^2 * 'n7' */
  983. /* 'n9' */
  984. if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
  985. if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
  986. /* n9 = n5^2 * 'n7' - 2 * X_r */
  987. /* Y_r */
  988. if (!field_mul(group, n0, n0, n6, ctx)) goto end;
  989. if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
  990. if (!field_mul(group, n1, n2, n5, ctx)) goto end;
  991. if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
  992. if (BN_is_odd(n0))
  993. if (!BN_add(n0, n0, p)) goto end;
  994. /* now 0 <= n0 < 2*p, and n0 is even */
  995. if (!BN_rshift1(&r->Y, n0)) goto end;
  996. /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
  997. ret = 1;
  998. end:
  999. if (ctx) /* otherwise we already called BN_CTX_end */
  1000. BN_CTX_end(ctx);
  1001. if (new_ctx != NULL)
  1002. BN_CTX_free(new_ctx);
  1003. return ret;
  1004. }
  1005. int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
  1006. {
  1007. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1008. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1009. const BIGNUM *p;
  1010. BN_CTX *new_ctx = NULL;
  1011. BIGNUM *n0, *n1, *n2, *n3;
  1012. int ret = 0;
  1013. if (EC_POINT_is_at_infinity(group, a))
  1014. {
  1015. BN_zero(&r->Z);
  1016. r->Z_is_one = 0;
  1017. return 1;
  1018. }
  1019. field_mul = group->meth->field_mul;
  1020. field_sqr = group->meth->field_sqr;
  1021. p = &group->field;
  1022. if (ctx == NULL)
  1023. {
  1024. ctx = new_ctx = BN_CTX_new();
  1025. if (ctx == NULL)
  1026. return 0;
  1027. }
  1028. BN_CTX_start(ctx);
  1029. n0 = BN_CTX_get(ctx);
  1030. n1 = BN_CTX_get(ctx);
  1031. n2 = BN_CTX_get(ctx);
  1032. n3 = BN_CTX_get(ctx);
  1033. if (n3 == NULL) goto err;
  1034. /* Note that in this function we must not read components of 'a'
  1035. * once we have written the corresponding components of 'r'.
  1036. * ('r' might the same as 'a'.)
  1037. */
  1038. /* n1 */
  1039. if (a->Z_is_one)
  1040. {
  1041. if (!field_sqr(group, n0, &a->X, ctx)) goto err;
  1042. if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
  1043. if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
  1044. if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
  1045. /* n1 = 3 * X_a^2 + a_curve */
  1046. }
  1047. else if (group->a_is_minus3)
  1048. {
  1049. if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
  1050. if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
  1051. if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
  1052. if (!field_mul(group, n1, n0, n2, ctx)) goto err;
  1053. if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
  1054. if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
  1055. /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
  1056. * = 3 * X_a^2 - 3 * Z_a^4 */
  1057. }
  1058. else
  1059. {
  1060. if (!field_sqr(group, n0, &a->X, ctx)) goto err;
  1061. if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
  1062. if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
  1063. if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
  1064. if (!field_sqr(group, n1, n1, ctx)) goto err;
  1065. if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
  1066. if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
  1067. /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
  1068. }
  1069. /* Z_r */
  1070. if (a->Z_is_one)
  1071. {
  1072. if (!BN_copy(n0, &a->Y)) goto err;
  1073. }
  1074. else
  1075. {
  1076. if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
  1077. }
  1078. if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
  1079. r->Z_is_one = 0;
  1080. /* Z_r = 2 * Y_a * Z_a */
  1081. /* n2 */
  1082. if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
  1083. if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
  1084. if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
  1085. /* n2 = 4 * X_a * Y_a^2 */
  1086. /* X_r */
  1087. if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
  1088. if (!field_sqr(group, &r->X, n1, ctx)) goto err;
  1089. if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
  1090. /* X_r = n1^2 - 2 * n2 */
  1091. /* n3 */
  1092. if (!field_sqr(group, n0, n3, ctx)) goto err;
  1093. if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
  1094. /* n3 = 8 * Y_a^4 */
  1095. /* Y_r */
  1096. if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
  1097. if (!field_mul(group, n0, n1, n0, ctx)) goto err;
  1098. if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
  1099. /* Y_r = n1 * (n2 - X_r) - n3 */
  1100. ret = 1;
  1101. err:
  1102. BN_CTX_end(ctx);
  1103. if (new_ctx != NULL)
  1104. BN_CTX_free(new_ctx);
  1105. return ret;
  1106. }
  1107. int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
  1108. {
  1109. if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
  1110. /* point is its own inverse */
  1111. return 1;
  1112. return BN_usub(&point->Y, &group->field, &point->Y);
  1113. }
  1114. int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
  1115. {
  1116. return BN_is_zero(&point->Z);
  1117. }
  1118. int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
  1119. {
  1120. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1121. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1122. const BIGNUM *p;
  1123. BN_CTX *new_ctx = NULL;
  1124. BIGNUM *rh, *tmp, *Z4, *Z6;
  1125. int ret = -1;
  1126. if (EC_POINT_is_at_infinity(group, point))
  1127. return 1;
  1128. field_mul = group->meth->field_mul;
  1129. field_sqr = group->meth->field_sqr;
  1130. p = &group->field;
  1131. if (ctx == NULL)
  1132. {
  1133. ctx = new_ctx = BN_CTX_new();
  1134. if (ctx == NULL)
  1135. return -1;
  1136. }
  1137. BN_CTX_start(ctx);
  1138. rh = BN_CTX_get(ctx);
  1139. tmp = BN_CTX_get(ctx);
  1140. Z4 = BN_CTX_get(ctx);
  1141. Z6 = BN_CTX_get(ctx);
  1142. if (Z6 == NULL) goto err;
  1143. /* We have a curve defined by a Weierstrass equation
  1144. * y^2 = x^3 + a*x + b.
  1145. * The point to consider is given in Jacobian projective coordinates
  1146. * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
  1147. * Substituting this and multiplying by Z^6 transforms the above equation into
  1148. * Y^2 = X^3 + a*X*Z^4 + b*Z^6.
  1149. * To test this, we add up the right-hand side in 'rh'.
  1150. */
  1151. /* rh := X^2 */
  1152. if (!field_sqr(group, rh, &point->X, ctx)) goto err;
  1153. if (!point->Z_is_one)
  1154. {
  1155. if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
  1156. if (!field_sqr(group, Z4, tmp, ctx)) goto err;
  1157. if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
  1158. /* rh := (rh + a*Z^4)*X */
  1159. if (group->a_is_minus3)
  1160. {
  1161. if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
  1162. if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
  1163. if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
  1164. if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
  1165. }
  1166. else
  1167. {
  1168. if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
  1169. if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
  1170. if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
  1171. }
  1172. /* rh := rh + b*Z^6 */
  1173. if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
  1174. if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
  1175. }
  1176. else
  1177. {
  1178. /* point->Z_is_one */
  1179. /* rh := (rh + a)*X */
  1180. if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
  1181. if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
  1182. /* rh := rh + b */
  1183. if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
  1184. }
  1185. /* 'lh' := Y^2 */
  1186. if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
  1187. ret = (0 == BN_ucmp(tmp, rh));
  1188. err:
  1189. BN_CTX_end(ctx);
  1190. if (new_ctx != NULL)
  1191. BN_CTX_free(new_ctx);
  1192. return ret;
  1193. }
  1194. int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
  1195. {
  1196. /* return values:
  1197. * -1 error
  1198. * 0 equal (in affine coordinates)
  1199. * 1 not equal
  1200. */
  1201. int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  1202. int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
  1203. BN_CTX *new_ctx = NULL;
  1204. BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
  1205. const BIGNUM *tmp1_, *tmp2_;
  1206. int ret = -1;
  1207. if (EC_POINT_is_at_infinity(group, a))
  1208. {
  1209. return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
  1210. }
  1211. if (a->Z_is_one && b->Z_is_one)
  1212. {
  1213. return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
  1214. }
  1215. field_mul = group->meth->field_mul;
  1216. field_sqr = group->meth->field_sqr;
  1217. if (ctx == NULL)
  1218. {
  1219. ctx = new_ctx = BN_CTX_new();
  1220. if (ctx == NULL)
  1221. return -1;
  1222. }
  1223. BN_CTX_start(ctx);
  1224. tmp1 = BN_CTX_get(ctx);
  1225. tmp2 = BN_CTX_get(ctx);
  1226. Za23 = BN_CTX_get(ctx);
  1227. Zb23 = BN_CTX_get(ctx);
  1228. if (Zb23 == NULL) goto end;
  1229. /* We have to decide whether
  1230. * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
  1231. * or equivalently, whether
  1232. * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
  1233. */
  1234. if (!b->Z_is_one)
  1235. {
  1236. if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
  1237. if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
  1238. tmp1_ = tmp1;
  1239. }
  1240. else
  1241. tmp1_ = &a->X;
  1242. if (!a->Z_is_one)
  1243. {
  1244. if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
  1245. if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
  1246. tmp2_ = tmp2;
  1247. }
  1248. else
  1249. tmp2_ = &b->X;
  1250. /* compare X_a*Z_b^2 with X_b*Z_a^2 */
  1251. if (BN_cmp(tmp1_, tmp2_) != 0)
  1252. {
  1253. ret = 1; /* points differ */
  1254. goto end;
  1255. }
  1256. if (!b->Z_is_one)
  1257. {
  1258. if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
  1259. if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
  1260. /* tmp1_ = tmp1 */
  1261. }
  1262. else
  1263. tmp1_ = &a->Y;
  1264. if (!a->Z_is_one)
  1265. {
  1266. if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
  1267. if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
  1268. /* tmp2_ = tmp2 */
  1269. }
  1270. else
  1271. tmp2_ = &b->Y;
  1272. /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
  1273. if (BN_cmp(tmp1_, tmp2_) != 0)
  1274. {
  1275. ret = 1; /* points differ */
  1276. goto end;
  1277. }
  1278. /* points are equal */
  1279. ret = 0;
  1280. end:
  1281. BN_CTX_end(ctx);
  1282. if (new_ctx != NULL)
  1283. BN_CTX_free(new_ctx);
  1284. return ret;
  1285. }
  1286. int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
  1287. {
  1288. BN_CTX *new_ctx = NULL;
  1289. BIGNUM *x, *y;
  1290. int ret = 0;
  1291. if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
  1292. return 1;
  1293. if (ctx == NULL)
  1294. {
  1295. ctx = new_ctx = BN_CTX_new();
  1296. if (ctx == NULL)
  1297. return 0;
  1298. }
  1299. BN_CTX_start(ctx);
  1300. x = BN_CTX_get(ctx);
  1301. y = BN_CTX_get(ctx);
  1302. if (y == NULL) goto err;
  1303. if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  1304. if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
  1305. if (!point->Z_is_one)
  1306. {
  1307. ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
  1308. goto err;
  1309. }
  1310. ret = 1;
  1311. err:
  1312. BN_CTX_end(ctx);
  1313. if (new_ctx != NULL)
  1314. BN_CTX_free(new_ctx);
  1315. return ret;
  1316. }
  1317. int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
  1318. {
  1319. BN_CTX *new_ctx = NULL;
  1320. BIGNUM *tmp0, *tmp1;
  1321. size_t pow2 = 0;
  1322. BIGNUM **heap = NULL;
  1323. size_t i;
  1324. int ret = 0;
  1325. if (num == 0)
  1326. return 1;
  1327. if (ctx == NULL)
  1328. {
  1329. ctx = new_ctx = BN_CTX_new();
  1330. if (ctx == NULL)
  1331. return 0;
  1332. }
  1333. BN_CTX_start(ctx);
  1334. tmp0 = BN_CTX_get(ctx);
  1335. tmp1 = BN_CTX_get(ctx);
  1336. if (tmp0 == NULL || tmp1 == NULL) goto err;
  1337. /* Before converting the individual points, compute inverses of all Z values.
  1338. * Modular inversion is rather slow, but luckily we can do with a single
  1339. * explicit inversion, plus about 3 multiplications per input value.
  1340. */
  1341. pow2 = 1;
  1342. while (num > pow2)
  1343. pow2 <<= 1;
  1344. /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
  1345. * We need twice that. */
  1346. pow2 <<= 1;
  1347. heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
  1348. if (heap == NULL) goto err;
  1349. /* The array is used as a binary tree, exactly as in heapsort:
  1350. *
  1351. * heap[1]
  1352. * heap[2] heap[3]
  1353. * heap[4] heap[5] heap[6] heap[7]
  1354. * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
  1355. *
  1356. * We put the Z's in the last line;
  1357. * then we set each other node to the product of its two child-nodes (where
  1358. * empty or 0 entries are treated as ones);
  1359. * then we invert heap[1];
  1360. * then we invert each other node by replacing it by the product of its
  1361. * parent (after inversion) and its sibling (before inversion).
  1362. */
  1363. heap[0] = NULL;
  1364. for (i = pow2/2 - 1; i > 0; i--)
  1365. heap[i] = NULL;
  1366. for (i = 0; i < num; i++)
  1367. heap[pow2/2 + i] = &points[i]->Z;
  1368. for (i = pow2/2 + num; i < pow2; i++)
  1369. heap[i] = NULL;
  1370. /* set each node to the product of its children */
  1371. for (i = pow2/2 - 1; i > 0; i--)
  1372. {
  1373. heap[i] = BN_new();
  1374. if (heap[i] == NULL) goto err;
  1375. if (heap[2*i] != NULL)
  1376. {
  1377. if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
  1378. {
  1379. if (!BN_copy(heap[i], heap[2*i])) goto err;
  1380. }
  1381. else
  1382. {
  1383. if (BN_is_zero(heap[2*i]))
  1384. {
  1385. if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
  1386. }
  1387. else
  1388. {
  1389. if (!group->meth->field_mul(group, heap[i],
  1390. heap[2*i], heap[2*i + 1], ctx)) goto err;
  1391. }
  1392. }
  1393. }
  1394. }
  1395. /* invert heap[1] */
  1396. if (!BN_is_zero(heap[1]))
  1397. {
  1398. if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
  1399. {
  1400. ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
  1401. goto err;
  1402. }
  1403. }
  1404. if (group->meth->field_encode != 0)
  1405. {
  1406. /* in the Montgomery case, we just turned R*H (representing H)
  1407. * into 1/(R*H), but we need R*(1/H) (representing 1/H);
  1408. * i.e. we have need to multiply by the Montgomery factor twice */
  1409. if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
  1410. if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
  1411. }
  1412. /* set other heap[i]'s to their inverses */
  1413. for (i = 2; i < pow2/2 + num; i += 2)
  1414. {
  1415. /* i is even */
  1416. if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
  1417. {
  1418. if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
  1419. if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
  1420. if (!BN_copy(heap[i], tmp0)) goto err;
  1421. if (!BN_copy(heap[i + 1], tmp1)) goto err;
  1422. }
  1423. else
  1424. {
  1425. if (!BN_copy(heap[i], heap[i/2])) goto err;
  1426. }
  1427. }
  1428. /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
  1429. for (i = 0; i < num; i++)
  1430. {
  1431. EC_POINT *p = points[i];
  1432. if (!BN_is_zero(&p->Z))
  1433. {
  1434. /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
  1435. if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
  1436. if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
  1437. if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
  1438. if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
  1439. if (group->meth->field_set_to_one != 0)
  1440. {
  1441. if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
  1442. }
  1443. else
  1444. {
  1445. if (!BN_one(&p->Z)) goto err;
  1446. }
  1447. p->Z_is_one = 1;
  1448. }
  1449. }
  1450. ret = 1;
  1451. err:
  1452. BN_CTX_end(ctx);
  1453. if (new_ctx != NULL)
  1454. BN_CTX_free(new_ctx);
  1455. if (heap != NULL)
  1456. {
  1457. /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
  1458. for (i = pow2/2 - 1; i > 0; i--)
  1459. {
  1460. if (heap[i] != NULL)
  1461. BN_clear_free(heap[i]);
  1462. }
  1463. OPENSSL_free(heap);
  1464. }
  1465. return ret;
  1466. }
  1467. int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  1468. {
  1469. return BN_mod_mul(r, a, b, &group->field, ctx);
  1470. }
  1471. int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
  1472. {
  1473. return BN_mod_sqr(r, a, &group->field, ctx);
  1474. }