ecp_sm2p256.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790
  1. /*
  2. * Copyright 2023 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. *
  9. */
  10. /*
  11. * SM2 low level APIs are deprecated for public use, but still ok for
  12. * internal use.
  13. */
  14. #include "internal/deprecated.h"
  15. #include <string.h>
  16. #include <openssl/err.h>
  17. #include "crypto/bn.h"
  18. #include "ec_local.h"
  19. #include "internal/common.h"
  20. #include "internal/constant_time.h"
  21. #define P256_LIMBS (256 / BN_BITS2)
  22. #if !defined(OPENSSL_NO_SM2_PRECOMP)
  23. extern const BN_ULONG ecp_sm2p256_precomputed[8 * 32 * 256];
  24. #endif
  25. typedef struct {
  26. BN_ULONG X[P256_LIMBS];
  27. BN_ULONG Y[P256_LIMBS];
  28. BN_ULONG Z[P256_LIMBS];
  29. } P256_POINT;
  30. typedef struct {
  31. BN_ULONG X[P256_LIMBS];
  32. BN_ULONG Y[P256_LIMBS];
  33. } P256_POINT_AFFINE;
  34. #if !defined(OPENSSL_NO_SM2_PRECOMP)
  35. /* Coordinates of G, for which we have precomputed tables */
  36. static const BN_ULONG def_xG[P256_LIMBS] ALIGN32 = {
  37. 0x715a4589334c74c7, 0x8fe30bbff2660be1,
  38. 0x5f9904466a39c994, 0x32c4ae2c1f198119
  39. };
  40. static const BN_ULONG def_yG[P256_LIMBS] ALIGN32 = {
  41. 0x02df32e52139f0a0, 0xd0a9877cc62a4740,
  42. 0x59bdcee36b692153, 0xbc3736a2f4f6779c,
  43. };
  44. #endif
  45. /* p and order for SM2 according to GB/T 32918.5-2017 */
  46. static const BN_ULONG def_p[P256_LIMBS] ALIGN32 = {
  47. 0xffffffffffffffff, 0xffffffff00000000,
  48. 0xffffffffffffffff, 0xfffffffeffffffff
  49. };
  50. static const BN_ULONG def_ord[P256_LIMBS] ALIGN32 = {
  51. 0x53bbf40939d54123, 0x7203df6b21c6052b,
  52. 0xffffffffffffffff, 0xfffffffeffffffff
  53. };
  54. static const BN_ULONG ONE[P256_LIMBS] ALIGN32 = {1, 0, 0, 0};
  55. /* Functions implemented in assembly */
  56. /*
  57. * Most of below mentioned functions *preserve* the property of inputs
  58. * being fully reduced, i.e. being in [0, modulus) range. Simply put if
  59. * inputs are fully reduced, then output is too.
  60. */
  61. /* Right shift: a >> 1 */
  62. void bn_rshift1(BN_ULONG *a);
  63. /* Sub: r = a - b */
  64. void bn_sub(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b);
  65. /* Modular div by 2: r = a / 2 mod p */
  66. void ecp_sm2p256_div_by_2(BN_ULONG *r, const BN_ULONG *a);
  67. /* Modular div by 2: r = a / 2 mod n, where n = ord(p) */
  68. void ecp_sm2p256_div_by_2_mod_ord(BN_ULONG *r, const BN_ULONG *a);
  69. /* Modular add: r = a + b mod p */
  70. void ecp_sm2p256_add(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b);
  71. /* Modular sub: r = a - b mod p */
  72. void ecp_sm2p256_sub(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b);
  73. /* Modular sub: r = a - b mod n, where n = ord(p) */
  74. void ecp_sm2p256_sub_mod_ord(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b);
  75. /* Modular mul by 3: out = 3 * a mod p */
  76. void ecp_sm2p256_mul_by_3(BN_ULONG *r, const BN_ULONG *a);
  77. /* Modular mul: r = a * b mod p */
  78. void ecp_sm2p256_mul(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b);
  79. /* Modular sqr: r = a ^ 2 mod p */
  80. void ecp_sm2p256_sqr(BN_ULONG *r, const BN_ULONG *a);
  81. static ossl_inline BN_ULONG is_zeros(const BN_ULONG *a)
  82. {
  83. BN_ULONG res;
  84. res = a[0] | a[1] | a[2] | a[3];
  85. return constant_time_is_zero_64(res);
  86. }
  87. static ossl_inline int is_equal(const BN_ULONG *a, const BN_ULONG *b)
  88. {
  89. BN_ULONG res;
  90. res = a[0] ^ b[0];
  91. res |= a[1] ^ b[1];
  92. res |= a[2] ^ b[2];
  93. res |= a[3] ^ b[3];
  94. return constant_time_is_zero_64(res);
  95. }
  96. static ossl_inline int is_greater(const BN_ULONG *a, const BN_ULONG *b)
  97. {
  98. int i;
  99. for (i = P256_LIMBS - 1; i >= 0; --i) {
  100. if (a[i] > b[i])
  101. return 1;
  102. if (a[i] < b[i])
  103. return -1;
  104. }
  105. return 0;
  106. }
  107. #define is_one(a) is_equal(a, ONE)
  108. #define is_even(a) !(a[0] & 1)
  109. #define is_point_equal(a, b) \
  110. is_equal(a->X, b->X) && \
  111. is_equal(a->Y, b->Y) && \
  112. is_equal(a->Z, b->Z)
  113. /* Bignum and field elements conversion */
  114. #define ecp_sm2p256_bignum_field_elem(out, in) \
  115. bn_copy_words(out, in, P256_LIMBS)
  116. /* Binary algorithm for inversion in Fp */
  117. #define BN_MOD_INV(out, in, mod_div, mod_sub, mod) \
  118. do { \
  119. BN_ULONG u[4] ALIGN32; \
  120. BN_ULONG v[4] ALIGN32; \
  121. BN_ULONG x1[4] ALIGN32 = {1, 0, 0, 0}; \
  122. BN_ULONG x2[4] ALIGN32 = {0}; \
  123. \
  124. if (is_zeros(in)) \
  125. return; \
  126. memcpy(u, in, 32); \
  127. memcpy(v, mod, 32); \
  128. while (!is_one(u) && !is_one(v)) { \
  129. while (is_even(u)) { \
  130. bn_rshift1(u); \
  131. mod_div(x1, x1); \
  132. } \
  133. while (is_even(v)) { \
  134. bn_rshift1(v); \
  135. mod_div(x2, x2); \
  136. } \
  137. if (is_greater(u, v) == 1) { \
  138. bn_sub(u, u, v); \
  139. mod_sub(x1, x1, x2); \
  140. } else { \
  141. bn_sub(v, v, u); \
  142. mod_sub(x2, x2, x1); \
  143. } \
  144. } \
  145. if (is_one(u)) \
  146. memcpy(out, x1, 32); \
  147. else \
  148. memcpy(out, x2, 32); \
  149. } while (0)
  150. /* Modular inverse |out| = |in|^(-1) mod |p|. */
  151. static ossl_inline void ecp_sm2p256_mod_inverse(BN_ULONG* out,
  152. const BN_ULONG* in) {
  153. BN_MOD_INV(out, in, ecp_sm2p256_div_by_2, ecp_sm2p256_sub, def_p);
  154. }
  155. /* Modular inverse mod order |out| = |in|^(-1) % |ord|. */
  156. static ossl_inline void ecp_sm2p256_mod_ord_inverse(BN_ULONG* out,
  157. const BN_ULONG* in) {
  158. BN_MOD_INV(out, in, ecp_sm2p256_div_by_2_mod_ord, ecp_sm2p256_sub_mod_ord,
  159. def_ord);
  160. }
  161. /* Point double: R <- P + P */
  162. static void ecp_sm2p256_point_double(P256_POINT *R, const P256_POINT *P)
  163. {
  164. unsigned int i;
  165. BN_ULONG tmp0[P256_LIMBS] ALIGN32;
  166. BN_ULONG tmp1[P256_LIMBS] ALIGN32;
  167. BN_ULONG tmp2[P256_LIMBS] ALIGN32;
  168. /* zero-check P->Z */
  169. if (is_zeros(P->Z)) {
  170. for (i = 0; i < P256_LIMBS; ++i)
  171. R->Z[i] = 0;
  172. return;
  173. }
  174. ecp_sm2p256_sqr(tmp0, P->Z);
  175. ecp_sm2p256_sub(tmp1, P->X, tmp0);
  176. ecp_sm2p256_add(tmp0, P->X, tmp0);
  177. ecp_sm2p256_mul(tmp1, tmp1, tmp0);
  178. ecp_sm2p256_mul_by_3(tmp1, tmp1);
  179. ecp_sm2p256_add(R->Y, P->Y, P->Y);
  180. ecp_sm2p256_mul(R->Z, R->Y, P->Z);
  181. ecp_sm2p256_sqr(R->Y, R->Y);
  182. ecp_sm2p256_mul(tmp2, R->Y, P->X);
  183. ecp_sm2p256_sqr(R->Y, R->Y);
  184. ecp_sm2p256_div_by_2(R->Y, R->Y);
  185. ecp_sm2p256_sqr(R->X, tmp1);
  186. ecp_sm2p256_add(tmp0, tmp2, tmp2);
  187. ecp_sm2p256_sub(R->X, R->X, tmp0);
  188. ecp_sm2p256_sub(tmp0, tmp2, R->X);
  189. ecp_sm2p256_mul(tmp0, tmp0, tmp1);
  190. ecp_sm2p256_sub(tmp1, tmp0, R->Y);
  191. memcpy(R->Y, tmp1, 32);
  192. }
  193. /* Point add affine: R <- P + Q */
  194. static void ecp_sm2p256_point_add_affine(P256_POINT *R, const P256_POINT *P,
  195. const P256_POINT_AFFINE *Q)
  196. {
  197. unsigned int i;
  198. BN_ULONG tmp0[P256_LIMBS] ALIGN32 = {0};
  199. BN_ULONG tmp1[P256_LIMBS] ALIGN32 = {0};
  200. BN_ULONG tmp2[P256_LIMBS] ALIGN32 = {0};
  201. BN_ULONG tmp3[P256_LIMBS] ALIGN32 = {0};
  202. /* zero-check P->Z */
  203. if (is_zeros(P->Z)) {
  204. for (i = 0; i < P256_LIMBS; ++i) {
  205. R->X[i] = Q->X[i];
  206. R->Y[i] = Q->Y[i];
  207. R->Z[i] = 0;
  208. }
  209. R->Z[0] = 1;
  210. return;
  211. }
  212. ecp_sm2p256_sqr(tmp0, P->Z);
  213. ecp_sm2p256_mul(tmp1, tmp0, P->Z);
  214. ecp_sm2p256_mul(tmp0, tmp0, Q->X);
  215. ecp_sm2p256_mul(tmp1, tmp1, Q->Y);
  216. ecp_sm2p256_sub(tmp0, tmp0, P->X);
  217. ecp_sm2p256_sub(tmp1, tmp1, P->Y);
  218. /* zero-check tmp0, tmp1 */
  219. if (is_zeros(tmp0)) {
  220. if (is_zeros(tmp1)) {
  221. P256_POINT K;
  222. for (i = 0; i < P256_LIMBS; ++i) {
  223. K.X[i] = Q->X[i];
  224. K.Y[i] = Q->Y[i];
  225. K.Z[i] = 0;
  226. }
  227. K.Z[0] = 1;
  228. ecp_sm2p256_point_double(R, &K);
  229. } else {
  230. for (i = 0; i < P256_LIMBS; ++i)
  231. R->Z[i] = 0;
  232. }
  233. return;
  234. }
  235. ecp_sm2p256_mul(R->Z, P->Z, tmp0);
  236. ecp_sm2p256_sqr(tmp2, tmp0);
  237. ecp_sm2p256_mul(tmp3, tmp2, tmp0);
  238. ecp_sm2p256_mul(tmp2, tmp2, P->X);
  239. ecp_sm2p256_add(tmp0, tmp2, tmp2);
  240. ecp_sm2p256_sqr(R->X, tmp1);
  241. ecp_sm2p256_sub(R->X, R->X, tmp0);
  242. ecp_sm2p256_sub(R->X, R->X, tmp3);
  243. ecp_sm2p256_sub(tmp2, tmp2, R->X);
  244. ecp_sm2p256_mul(tmp2, tmp2, tmp1);
  245. ecp_sm2p256_mul(tmp3, tmp3, P->Y);
  246. ecp_sm2p256_sub(R->Y, tmp2, tmp3);
  247. }
  248. /* Point add: R <- P + Q */
  249. static void ecp_sm2p256_point_add(P256_POINT *R, const P256_POINT *P,
  250. const P256_POINT *Q)
  251. {
  252. unsigned int i;
  253. BN_ULONG tmp0[P256_LIMBS] ALIGN32 = {0};
  254. BN_ULONG tmp1[P256_LIMBS] ALIGN32 = {0};
  255. BN_ULONG tmp2[P256_LIMBS] ALIGN32 = {0};
  256. /* zero-check P | Q ->Z */
  257. if (is_zeros(P->Z)) {
  258. for (i = 0; i < P256_LIMBS; ++i) {
  259. R->X[i] = Q->X[i];
  260. R->Y[i] = Q->Y[i];
  261. R->Z[i] = Q->Z[i];
  262. }
  263. return;
  264. } else if (is_zeros(Q->Z)) {
  265. for (i = 0; i < P256_LIMBS; ++i) {
  266. R->X[i] = P->X[i];
  267. R->Y[i] = P->Y[i];
  268. R->Z[i] = P->Z[i];
  269. }
  270. return;
  271. } else if (is_point_equal(P, Q)) {
  272. ecp_sm2p256_point_double(R, Q);
  273. return;
  274. }
  275. ecp_sm2p256_sqr(tmp0, P->Z);
  276. ecp_sm2p256_mul(tmp1, tmp0, P->Z);
  277. ecp_sm2p256_mul(tmp0, tmp0, Q->X);
  278. ecp_sm2p256_mul(tmp1, tmp1, Q->Y);
  279. ecp_sm2p256_mul(R->Y, P->Y, Q->Z);
  280. ecp_sm2p256_mul(R->Z, Q->Z, P->Z);
  281. ecp_sm2p256_sqr(tmp2, Q->Z);
  282. ecp_sm2p256_mul(R->Y, tmp2, R->Y);
  283. ecp_sm2p256_mul(R->X, tmp2, P->X);
  284. ecp_sm2p256_sub(tmp0, tmp0, R->X);
  285. ecp_sm2p256_mul(R->Z, tmp0, R->Z);
  286. ecp_sm2p256_sub(tmp1, tmp1, R->Y);
  287. ecp_sm2p256_sqr(tmp2, tmp0);
  288. ecp_sm2p256_mul(tmp0, tmp0, tmp2);
  289. ecp_sm2p256_mul(tmp2, tmp2, R->X);
  290. ecp_sm2p256_sqr(R->X, tmp1);
  291. ecp_sm2p256_sub(R->X, R->X, tmp2);
  292. ecp_sm2p256_sub(R->X, R->X, tmp2);
  293. ecp_sm2p256_sub(R->X, R->X, tmp0);
  294. ecp_sm2p256_sub(tmp2, tmp2, R->X);
  295. ecp_sm2p256_mul(tmp2, tmp1, tmp2);
  296. ecp_sm2p256_mul(tmp0, tmp0, R->Y);
  297. ecp_sm2p256_sub(R->Y, tmp2, tmp0);
  298. }
  299. #if !defined(OPENSSL_NO_SM2_PRECOMP)
  300. /* Base point mul by scalar: k - scalar, G - base point */
  301. static void ecp_sm2p256_point_G_mul_by_scalar(P256_POINT *R, const BN_ULONG *k)
  302. {
  303. unsigned int i, index, mask = 0xff;
  304. P256_POINT_AFFINE Q;
  305. memset(R, 0, sizeof(P256_POINT));
  306. if (is_zeros(k))
  307. return;
  308. index = k[0] & mask;
  309. if (index) {
  310. index = index * 8;
  311. memcpy(R->X, ecp_sm2p256_precomputed + index, 32);
  312. memcpy(R->Y, ecp_sm2p256_precomputed + index + P256_LIMBS, 32);
  313. R->Z[0] = 1;
  314. }
  315. for (i = 1; i < 32; ++i) {
  316. index = (k[i / 8] >> (8 * (i % 8))) & mask;
  317. if (index) {
  318. index = index + i * 256;
  319. index = index * 8;
  320. memcpy(Q.X, ecp_sm2p256_precomputed + index, 32);
  321. memcpy(Q.Y, ecp_sm2p256_precomputed + index + P256_LIMBS, 32);
  322. ecp_sm2p256_point_add_affine(R, R, &Q);
  323. }
  324. }
  325. }
  326. #endif
  327. /*
  328. * Affine point mul by scalar: k - scalar, P - affine point
  329. */
  330. static void ecp_sm2p256_point_P_mul_by_scalar(P256_POINT *R, const BN_ULONG *k,
  331. P256_POINT_AFFINE P)
  332. {
  333. int i, init = 0;
  334. unsigned int index, mask = 0x0f;
  335. P256_POINT precomputed[16] ALIGN64;
  336. memset(R, 0, sizeof(P256_POINT));
  337. if (is_zeros(k))
  338. return;
  339. /* The first value of the precomputed table is P. */
  340. memcpy(precomputed[1].X, P.X, 32);
  341. memcpy(precomputed[1].Y, P.Y, 32);
  342. precomputed[1].Z[0] = 1;
  343. precomputed[1].Z[1] = 0;
  344. precomputed[1].Z[2] = 0;
  345. precomputed[1].Z[3] = 0;
  346. /* The second value of the precomputed table is 2P. */
  347. ecp_sm2p256_point_double(&precomputed[2], &precomputed[1]);
  348. /* The subsequent elements are 3P, 4P, and so on. */
  349. for (i = 3; i < 16; ++i)
  350. ecp_sm2p256_point_add_affine(&precomputed[i], &precomputed[i - 1], &P);
  351. for (i = 64 - 1; i >= 0; --i) {
  352. index = (k[i / 16] >> (4 * (i % 16))) & mask;
  353. if (init == 0) {
  354. if (index) {
  355. memcpy(R, &precomputed[index], sizeof(P256_POINT));
  356. init = 1;
  357. }
  358. } else {
  359. ecp_sm2p256_point_double(R, R);
  360. ecp_sm2p256_point_double(R, R);
  361. ecp_sm2p256_point_double(R, R);
  362. ecp_sm2p256_point_double(R, R);
  363. if (index)
  364. ecp_sm2p256_point_add(R, R, &precomputed[index]);
  365. }
  366. }
  367. }
  368. /* Get affine point */
  369. static void ecp_sm2p256_point_get_affine(P256_POINT_AFFINE *R,
  370. const P256_POINT *P)
  371. {
  372. BN_ULONG z_inv3[P256_LIMBS] ALIGN32 = {0};
  373. BN_ULONG z_inv2[P256_LIMBS] ALIGN32 = {0};
  374. if (is_one(P->Z)) {
  375. memcpy(R->X, P->X, 32);
  376. memcpy(R->Y, P->Y, 32);
  377. return;
  378. }
  379. ecp_sm2p256_mod_inverse(z_inv3, P->Z);
  380. ecp_sm2p256_sqr(z_inv2, z_inv3);
  381. ecp_sm2p256_mul(R->X, P->X, z_inv2);
  382. ecp_sm2p256_mul(z_inv3, z_inv3, z_inv2);
  383. ecp_sm2p256_mul(R->Y, P->Y, z_inv3);
  384. }
  385. #if !defined(OPENSSL_NO_SM2_PRECOMP)
  386. static int ecp_sm2p256_is_affine_G(const EC_POINT *generator)
  387. {
  388. return (bn_get_top(generator->X) == P256_LIMBS)
  389. && (bn_get_top(generator->Y) == P256_LIMBS)
  390. && is_equal(bn_get_words(generator->X), def_xG)
  391. && is_equal(bn_get_words(generator->Y), def_yG)
  392. && (generator->Z_is_one == 1);
  393. }
  394. #endif
  395. /*
  396. * Convert Jacobian coordinate point into affine coordinate (x,y)
  397. */
  398. static int ecp_sm2p256_get_affine(const EC_GROUP *group,
  399. const EC_POINT *point,
  400. BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
  401. {
  402. BN_ULONG z_inv2[P256_LIMBS] ALIGN32 = {0};
  403. BN_ULONG z_inv3[P256_LIMBS] ALIGN32 = {0};
  404. BN_ULONG x_aff[P256_LIMBS] ALIGN32 = {0};
  405. BN_ULONG y_aff[P256_LIMBS] ALIGN32 = {0};
  406. BN_ULONG point_x[P256_LIMBS] ALIGN32 = {0};
  407. BN_ULONG point_y[P256_LIMBS] ALIGN32 = {0};
  408. BN_ULONG point_z[P256_LIMBS] ALIGN32 = {0};
  409. if (EC_POINT_is_at_infinity(group, point)) {
  410. ECerr(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
  411. return 0;
  412. }
  413. if (ecp_sm2p256_bignum_field_elem(point_x, point->X) <= 0
  414. || ecp_sm2p256_bignum_field_elem(point_y, point->Y) <= 0
  415. || ecp_sm2p256_bignum_field_elem(point_z, point->Z) <= 0) {
  416. ECerr(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  417. return 0;
  418. }
  419. ecp_sm2p256_mod_inverse(z_inv3, point_z);
  420. ecp_sm2p256_sqr(z_inv2, z_inv3);
  421. if (x != NULL) {
  422. ecp_sm2p256_mul(x_aff, point_x, z_inv2);
  423. if (!bn_set_words(x, x_aff, P256_LIMBS))
  424. return 0;
  425. }
  426. if (y != NULL) {
  427. ecp_sm2p256_mul(z_inv3, z_inv3, z_inv2);
  428. ecp_sm2p256_mul(y_aff, point_y, z_inv3);
  429. if (!bn_set_words(y, y_aff, P256_LIMBS))
  430. return 0;
  431. }
  432. return 1;
  433. }
  434. /* r = sum(scalar[i]*point[i]) */
  435. static int ecp_sm2p256_windowed_mul(const EC_GROUP *group,
  436. P256_POINT *r,
  437. const BIGNUM **scalar,
  438. const EC_POINT **point,
  439. size_t num, BN_CTX *ctx)
  440. {
  441. unsigned int i;
  442. int ret = 0;
  443. const BIGNUM **scalars = NULL;
  444. BN_ULONG k[P256_LIMBS] ALIGN32 = {0};
  445. P256_POINT kP;
  446. ALIGN32 union {
  447. P256_POINT p;
  448. P256_POINT_AFFINE a;
  449. } t, p;
  450. if (num > OPENSSL_MALLOC_MAX_NELEMS(P256_POINT)
  451. || (scalars = OPENSSL_malloc(num * sizeof(BIGNUM *))) == NULL) {
  452. ECerr(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  453. goto err;
  454. }
  455. memset(r, 0, sizeof(P256_POINT));
  456. for (i = 0; i < num; i++) {
  457. if (EC_POINT_is_at_infinity(group, point[i]))
  458. continue;
  459. if ((BN_num_bits(scalar[i]) > 256) || BN_is_negative(scalar[i])) {
  460. BIGNUM *tmp;
  461. if ((tmp = BN_CTX_get(ctx)) == NULL)
  462. goto err;
  463. if (!BN_nnmod(tmp, scalar[i], group->order, ctx)) {
  464. ECerr(ERR_LIB_EC, ERR_R_BN_LIB);
  465. goto err;
  466. }
  467. scalars[i] = tmp;
  468. } else {
  469. scalars[i] = scalar[i];
  470. }
  471. if (ecp_sm2p256_bignum_field_elem(k, scalars[i]) <= 0
  472. || ecp_sm2p256_bignum_field_elem(p.p.X, point[i]->X) <= 0
  473. || ecp_sm2p256_bignum_field_elem(p.p.Y, point[i]->Y) <= 0
  474. || ecp_sm2p256_bignum_field_elem(p.p.Z, point[i]->Z) <= 0) {
  475. ECerr(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  476. goto err;
  477. }
  478. ecp_sm2p256_point_get_affine(&t.a, &p.p);
  479. ecp_sm2p256_point_P_mul_by_scalar(&kP, k, t.a);
  480. ecp_sm2p256_point_add(r, r, &kP);
  481. }
  482. ret = 1;
  483. err:
  484. OPENSSL_free(scalars);
  485. return ret;
  486. }
  487. /* r = scalar*G + sum(scalars[i]*points[i]) */
  488. static int ecp_sm2p256_points_mul(const EC_GROUP *group,
  489. EC_POINT *r,
  490. const BIGNUM *scalar,
  491. size_t num,
  492. const EC_POINT *points[],
  493. const BIGNUM *scalars[], BN_CTX *ctx)
  494. {
  495. int ret = 0, p_is_infinity = 0;
  496. const EC_POINT *generator = NULL;
  497. BN_ULONG k[P256_LIMBS] ALIGN32 = {0};
  498. ALIGN32 union {
  499. P256_POINT p;
  500. P256_POINT_AFFINE a;
  501. } t, p;
  502. if ((num + 1) == 0 || (num + 1) > OPENSSL_MALLOC_MAX_NELEMS(void *)) {
  503. ECerr(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  504. goto err;
  505. }
  506. BN_CTX_start(ctx);
  507. if (scalar) {
  508. generator = EC_GROUP_get0_generator(group);
  509. if (generator == NULL) {
  510. ECerr(ERR_LIB_EC, EC_R_UNDEFINED_GENERATOR);
  511. goto err;
  512. }
  513. if (!ecp_sm2p256_bignum_field_elem(k, scalar)) {
  514. ECerr(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  515. goto err;
  516. }
  517. #if !defined(OPENSSL_NO_SM2_PRECOMP)
  518. if (ecp_sm2p256_is_affine_G(generator)) {
  519. ecp_sm2p256_point_G_mul_by_scalar(&p.p, k);
  520. } else
  521. #endif
  522. {
  523. /* if no precomputed table */
  524. const EC_POINT *new_generator[1];
  525. const BIGNUM *g_scalars[1];
  526. new_generator[0] = generator;
  527. g_scalars[0] = scalar;
  528. if (!ecp_sm2p256_windowed_mul(group, &p.p, g_scalars, new_generator,
  529. (new_generator[0] != NULL
  530. && g_scalars[0] != NULL), ctx))
  531. goto err;
  532. }
  533. } else {
  534. p_is_infinity = 1;
  535. }
  536. if (num) {
  537. P256_POINT *out = &t.p;
  538. if (p_is_infinity)
  539. out = &p.p;
  540. if (!ecp_sm2p256_windowed_mul(group, out, scalars, points, num, ctx))
  541. goto err;
  542. if (!p_is_infinity)
  543. ecp_sm2p256_point_add(&p.p, &p.p, out);
  544. }
  545. /* Not constant-time, but we're only operating on the public output. */
  546. if (!bn_set_words(r->X, p.p.X, P256_LIMBS)
  547. || !bn_set_words(r->Y, p.p.Y, P256_LIMBS)
  548. || !bn_set_words(r->Z, p.p.Z, P256_LIMBS))
  549. goto err;
  550. r->Z_is_one = is_equal(bn_get_words(r->Z), ONE) & 1;
  551. ret = 1;
  552. err:
  553. BN_CTX_end(ctx);
  554. return ret;
  555. }
  556. static int ecp_sm2p256_field_mul(const EC_GROUP *group, BIGNUM *r,
  557. const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  558. {
  559. BN_ULONG a_fe[P256_LIMBS] ALIGN32 = {0};
  560. BN_ULONG b_fe[P256_LIMBS] ALIGN32 = {0};
  561. BN_ULONG r_fe[P256_LIMBS] ALIGN32 = {0};
  562. if (a == NULL || b == NULL || r == NULL)
  563. return 0;
  564. if (!ecp_sm2p256_bignum_field_elem(a_fe, a)
  565. || !ecp_sm2p256_bignum_field_elem(b_fe, b)) {
  566. ECerr(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  567. return 0;
  568. }
  569. ecp_sm2p256_mul(r_fe, a_fe, b_fe);
  570. if (!bn_set_words(r, r_fe, P256_LIMBS))
  571. return 0;
  572. return 1;
  573. }
  574. static int ecp_sm2p256_field_sqr(const EC_GROUP *group, BIGNUM *r,
  575. const BIGNUM *a, BN_CTX *ctx)
  576. {
  577. BN_ULONG a_fe[P256_LIMBS] ALIGN32 = {0};
  578. BN_ULONG r_fe[P256_LIMBS] ALIGN32 = {0};
  579. if (a == NULL || r == NULL)
  580. return 0;
  581. if (!ecp_sm2p256_bignum_field_elem(a_fe, a)) {
  582. ECerr(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  583. return 0;
  584. }
  585. ecp_sm2p256_sqr(r_fe, a_fe);
  586. if (!bn_set_words(r, r_fe, P256_LIMBS))
  587. return 0;
  588. return 1;
  589. }
  590. static int ecp_sm2p256_inv_mod_ord(const EC_GROUP *group, BIGNUM *r,
  591. const BIGNUM *x, BN_CTX *ctx)
  592. {
  593. int ret = 0;
  594. BN_ULONG t[P256_LIMBS] ALIGN32 = {0};
  595. BN_ULONG out[P256_LIMBS] ALIGN32 = {0};
  596. if (bn_wexpand(r, P256_LIMBS) == NULL) {
  597. ECerr(ERR_LIB_EC, ERR_R_BN_LIB);
  598. goto err;
  599. }
  600. if ((BN_num_bits(x) > 256) || BN_is_negative(x)) {
  601. BIGNUM *tmp;
  602. if ((tmp = BN_CTX_get(ctx)) == NULL
  603. || !BN_nnmod(tmp, x, group->order, ctx)) {
  604. ECerr(ERR_LIB_EC, ERR_R_BN_LIB);
  605. goto err;
  606. }
  607. x = tmp;
  608. }
  609. if (!ecp_sm2p256_bignum_field_elem(t, x)) {
  610. ECerr(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  611. goto err;
  612. }
  613. ecp_sm2p256_mod_ord_inverse(out, t);
  614. if (!bn_set_words(r, out, P256_LIMBS))
  615. goto err;
  616. ret = 1;
  617. err:
  618. return ret;
  619. }
  620. const EC_METHOD *EC_GFp_sm2p256_method(void)
  621. {
  622. static const EC_METHOD ret = {
  623. EC_FLAGS_DEFAULT_OCT,
  624. NID_X9_62_prime_field,
  625. ossl_ec_GFp_simple_group_init,
  626. ossl_ec_GFp_simple_group_finish,
  627. ossl_ec_GFp_simple_group_clear_finish,
  628. ossl_ec_GFp_simple_group_copy,
  629. ossl_ec_GFp_simple_group_set_curve,
  630. ossl_ec_GFp_simple_group_get_curve,
  631. ossl_ec_GFp_simple_group_get_degree,
  632. ossl_ec_group_simple_order_bits,
  633. ossl_ec_GFp_simple_group_check_discriminant,
  634. ossl_ec_GFp_simple_point_init,
  635. ossl_ec_GFp_simple_point_finish,
  636. ossl_ec_GFp_simple_point_clear_finish,
  637. ossl_ec_GFp_simple_point_copy,
  638. ossl_ec_GFp_simple_point_set_to_infinity,
  639. ossl_ec_GFp_simple_point_set_affine_coordinates,
  640. ecp_sm2p256_get_affine,
  641. 0, 0, 0,
  642. ossl_ec_GFp_simple_add,
  643. ossl_ec_GFp_simple_dbl,
  644. ossl_ec_GFp_simple_invert,
  645. ossl_ec_GFp_simple_is_at_infinity,
  646. ossl_ec_GFp_simple_is_on_curve,
  647. ossl_ec_GFp_simple_cmp,
  648. ossl_ec_GFp_simple_make_affine,
  649. ossl_ec_GFp_simple_points_make_affine,
  650. ecp_sm2p256_points_mul, /* mul */
  651. 0 /* precompute_mult */,
  652. 0 /* have_precompute_mult */,
  653. ecp_sm2p256_field_mul,
  654. ecp_sm2p256_field_sqr,
  655. 0 /* field_div */,
  656. 0 /* field_inv */,
  657. 0 /* field_encode */,
  658. 0 /* field_decode */,
  659. 0 /* field_set_to_one */,
  660. ossl_ec_key_simple_priv2oct,
  661. ossl_ec_key_simple_oct2priv,
  662. 0, /* set private */
  663. ossl_ec_key_simple_generate_key,
  664. ossl_ec_key_simple_check_key,
  665. ossl_ec_key_simple_generate_public_key,
  666. 0, /* keycopy */
  667. 0, /* keyfinish */
  668. ossl_ecdh_simple_compute_key,
  669. ossl_ecdsa_simple_sign_setup,
  670. ossl_ecdsa_simple_sign_sig,
  671. ossl_ecdsa_simple_verify_sig,
  672. ecp_sm2p256_inv_mod_ord,
  673. 0, /* blind_coordinates */
  674. 0, /* ladder_pre */
  675. 0, /* ladder_step */
  676. 0 /* ladder_post */
  677. };
  678. return &ret;
  679. }