ecdsa_ossl.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464
  1. /*
  2. * Copyright 2002-2021 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. * ECDSA low level APIs are deprecated for public use, but still ok for
  11. * internal use.
  12. */
  13. #include "internal/deprecated.h"
  14. #include <string.h>
  15. #include <openssl/err.h>
  16. #include <openssl/obj_mac.h>
  17. #include <openssl/rand.h>
  18. #include "crypto/bn.h"
  19. #include "ec_local.h"
  20. int ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
  21. BIGNUM **rp)
  22. {
  23. if (eckey->group->meth->ecdsa_sign_setup == NULL) {
  24. ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA);
  25. return 0;
  26. }
  27. return eckey->group->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp);
  28. }
  29. ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len,
  30. const BIGNUM *in_kinv, const BIGNUM *in_r,
  31. EC_KEY *eckey)
  32. {
  33. if (eckey->group->meth->ecdsa_sign_sig == NULL) {
  34. ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA);
  35. return NULL;
  36. }
  37. return eckey->group->meth->ecdsa_sign_sig(dgst, dgst_len,
  38. in_kinv, in_r, eckey);
  39. }
  40. int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len,
  41. const ECDSA_SIG *sig, EC_KEY *eckey)
  42. {
  43. if (eckey->group->meth->ecdsa_verify_sig == NULL) {
  44. ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA);
  45. return 0;
  46. }
  47. return eckey->group->meth->ecdsa_verify_sig(dgst, dgst_len, sig, eckey);
  48. }
  49. int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen,
  50. unsigned char *sig, unsigned int *siglen,
  51. const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey)
  52. {
  53. ECDSA_SIG *s;
  54. s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey);
  55. if (s == NULL) {
  56. *siglen = 0;
  57. return 0;
  58. }
  59. *siglen = i2d_ECDSA_SIG(s, &sig);
  60. ECDSA_SIG_free(s);
  61. return 1;
  62. }
  63. static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
  64. BIGNUM **kinvp, BIGNUM **rp,
  65. const unsigned char *dgst, int dlen)
  66. {
  67. BN_CTX *ctx = NULL;
  68. BIGNUM *k = NULL, *r = NULL, *X = NULL;
  69. const BIGNUM *order;
  70. EC_POINT *tmp_point = NULL;
  71. const EC_GROUP *group;
  72. int ret = 0;
  73. int order_bits;
  74. const BIGNUM *priv_key;
  75. if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
  76. ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER);
  77. return 0;
  78. }
  79. if ((priv_key = EC_KEY_get0_private_key(eckey)) == NULL) {
  80. ERR_raise(ERR_LIB_EC, EC_R_MISSING_PRIVATE_KEY);
  81. return 0;
  82. }
  83. if (!EC_KEY_can_sign(eckey)) {
  84. ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
  85. return 0;
  86. }
  87. if ((ctx = ctx_in) == NULL) {
  88. if ((ctx = BN_CTX_new_ex(eckey->libctx)) == NULL) {
  89. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  90. return 0;
  91. }
  92. }
  93. k = BN_secure_new(); /* this value is later returned in *kinvp */
  94. r = BN_new(); /* this value is later returned in *rp */
  95. X = BN_new();
  96. if (k == NULL || r == NULL || X == NULL) {
  97. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  98. goto err;
  99. }
  100. if ((tmp_point = EC_POINT_new(group)) == NULL) {
  101. ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
  102. goto err;
  103. }
  104. order = EC_GROUP_get0_order(group);
  105. /* Preallocate space */
  106. order_bits = BN_num_bits(order);
  107. if (!BN_set_bit(k, order_bits)
  108. || !BN_set_bit(r, order_bits)
  109. || !BN_set_bit(X, order_bits))
  110. goto err;
  111. do {
  112. /* get random k */
  113. do {
  114. if (dgst != NULL) {
  115. if (!BN_generate_dsa_nonce(k, order, priv_key,
  116. dgst, dlen, ctx)) {
  117. ERR_raise(ERR_LIB_EC, EC_R_RANDOM_NUMBER_GENERATION_FAILED);
  118. goto err;
  119. }
  120. } else {
  121. if (!BN_priv_rand_range_ex(k, order, 0, ctx)) {
  122. ERR_raise(ERR_LIB_EC, EC_R_RANDOM_NUMBER_GENERATION_FAILED);
  123. goto err;
  124. }
  125. }
  126. } while (BN_is_zero(k));
  127. /* compute r the x-coordinate of generator * k */
  128. if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
  129. ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
  130. goto err;
  131. }
  132. if (!EC_POINT_get_affine_coordinates(group, tmp_point, X, NULL, ctx)) {
  133. ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
  134. goto err;
  135. }
  136. if (!BN_nnmod(r, X, order, ctx)) {
  137. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  138. goto err;
  139. }
  140. } while (BN_is_zero(r));
  141. /* compute the inverse of k */
  142. if (!ossl_ec_group_do_inverse_ord(group, k, k, ctx)) {
  143. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  144. goto err;
  145. }
  146. /* clear old values if necessary */
  147. BN_clear_free(*rp);
  148. BN_clear_free(*kinvp);
  149. /* save the pre-computed values */
  150. *rp = r;
  151. *kinvp = k;
  152. ret = 1;
  153. err:
  154. if (!ret) {
  155. BN_clear_free(k);
  156. BN_clear_free(r);
  157. }
  158. if (ctx != ctx_in)
  159. BN_CTX_free(ctx);
  160. EC_POINT_free(tmp_point);
  161. BN_clear_free(X);
  162. return ret;
  163. }
  164. int ossl_ecdsa_simple_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
  165. BIGNUM **rp)
  166. {
  167. return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0);
  168. }
  169. ECDSA_SIG *ossl_ecdsa_simple_sign_sig(const unsigned char *dgst, int dgst_len,
  170. const BIGNUM *in_kinv, const BIGNUM *in_r,
  171. EC_KEY *eckey)
  172. {
  173. int ok = 0, i;
  174. BIGNUM *kinv = NULL, *s, *m = NULL;
  175. const BIGNUM *order, *ckinv;
  176. BN_CTX *ctx = NULL;
  177. const EC_GROUP *group;
  178. ECDSA_SIG *ret;
  179. const BIGNUM *priv_key;
  180. group = EC_KEY_get0_group(eckey);
  181. priv_key = EC_KEY_get0_private_key(eckey);
  182. if (group == NULL) {
  183. ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER);
  184. return NULL;
  185. }
  186. if (priv_key == NULL) {
  187. ERR_raise(ERR_LIB_EC, EC_R_MISSING_PRIVATE_KEY);
  188. return NULL;
  189. }
  190. if (!EC_KEY_can_sign(eckey)) {
  191. ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
  192. return NULL;
  193. }
  194. ret = ECDSA_SIG_new();
  195. if (ret == NULL) {
  196. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  197. return NULL;
  198. }
  199. ret->r = BN_new();
  200. ret->s = BN_new();
  201. if (ret->r == NULL || ret->s == NULL) {
  202. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  203. goto err;
  204. }
  205. s = ret->s;
  206. if ((ctx = BN_CTX_new_ex(eckey->libctx)) == NULL
  207. || (m = BN_new()) == NULL) {
  208. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  209. goto err;
  210. }
  211. order = EC_GROUP_get0_order(group);
  212. i = BN_num_bits(order);
  213. /*
  214. * Need to truncate digest if it is too long: first truncate whole bytes.
  215. */
  216. if (8 * dgst_len > i)
  217. dgst_len = (i + 7) / 8;
  218. if (!BN_bin2bn(dgst, dgst_len, m)) {
  219. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  220. goto err;
  221. }
  222. /* If still too long, truncate remaining bits with a shift */
  223. if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
  224. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  225. goto err;
  226. }
  227. do {
  228. if (in_kinv == NULL || in_r == NULL) {
  229. if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) {
  230. ERR_raise(ERR_LIB_EC, ERR_R_ECDSA_LIB);
  231. goto err;
  232. }
  233. ckinv = kinv;
  234. } else {
  235. ckinv = in_kinv;
  236. if (BN_copy(ret->r, in_r) == NULL) {
  237. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  238. goto err;
  239. }
  240. }
  241. /*
  242. * With only one multiplicant being in Montgomery domain
  243. * multiplication yields real result without post-conversion.
  244. * Also note that all operations but last are performed with
  245. * zero-padded vectors. Last operation, BN_mod_mul_montgomery
  246. * below, returns user-visible value with removed zero padding.
  247. */
  248. if (!bn_to_mont_fixed_top(s, ret->r, group->mont_data, ctx)
  249. || !bn_mul_mont_fixed_top(s, s, priv_key, group->mont_data, ctx)) {
  250. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  251. goto err;
  252. }
  253. if (!bn_mod_add_fixed_top(s, s, m, order)) {
  254. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  255. goto err;
  256. }
  257. /*
  258. * |s| can still be larger than modulus, because |m| can be. In
  259. * such case we count on Montgomery reduction to tie it up.
  260. */
  261. if (!bn_to_mont_fixed_top(s, s, group->mont_data, ctx)
  262. || !BN_mod_mul_montgomery(s, s, ckinv, group->mont_data, ctx)) {
  263. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  264. goto err;
  265. }
  266. if (BN_is_zero(s)) {
  267. /*
  268. * if kinv and r have been supplied by the caller, don't
  269. * generate new kinv and r values
  270. */
  271. if (in_kinv != NULL && in_r != NULL) {
  272. ERR_raise(ERR_LIB_EC, EC_R_NEED_NEW_SETUP_VALUES);
  273. goto err;
  274. }
  275. } else {
  276. /* s != 0 => we have a valid signature */
  277. break;
  278. }
  279. } while (1);
  280. ok = 1;
  281. err:
  282. if (!ok) {
  283. ECDSA_SIG_free(ret);
  284. ret = NULL;
  285. }
  286. BN_CTX_free(ctx);
  287. BN_clear_free(m);
  288. BN_clear_free(kinv);
  289. return ret;
  290. }
  291. /*-
  292. * returns
  293. * 1: correct signature
  294. * 0: incorrect signature
  295. * -1: error
  296. */
  297. int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len,
  298. const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)
  299. {
  300. ECDSA_SIG *s;
  301. const unsigned char *p = sigbuf;
  302. unsigned char *der = NULL;
  303. int derlen = -1;
  304. int ret = -1;
  305. s = ECDSA_SIG_new();
  306. if (s == NULL)
  307. return ret;
  308. if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL)
  309. goto err;
  310. /* Ensure signature uses DER and doesn't have trailing garbage */
  311. derlen = i2d_ECDSA_SIG(s, &der);
  312. if (derlen != sig_len || memcmp(sigbuf, der, derlen) != 0)
  313. goto err;
  314. ret = ECDSA_do_verify(dgst, dgst_len, s, eckey);
  315. err:
  316. OPENSSL_free(der);
  317. ECDSA_SIG_free(s);
  318. return ret;
  319. }
  320. int ossl_ecdsa_simple_verify_sig(const unsigned char *dgst, int dgst_len,
  321. const ECDSA_SIG *sig, EC_KEY *eckey)
  322. {
  323. int ret = -1, i;
  324. BN_CTX *ctx;
  325. const BIGNUM *order;
  326. BIGNUM *u1, *u2, *m, *X;
  327. EC_POINT *point = NULL;
  328. const EC_GROUP *group;
  329. const EC_POINT *pub_key;
  330. /* check input values */
  331. if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
  332. (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) {
  333. ERR_raise(ERR_LIB_EC, EC_R_MISSING_PARAMETERS);
  334. return -1;
  335. }
  336. if (!EC_KEY_can_sign(eckey)) {
  337. ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
  338. return -1;
  339. }
  340. ctx = BN_CTX_new_ex(eckey->libctx);
  341. if (ctx == NULL) {
  342. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  343. return -1;
  344. }
  345. BN_CTX_start(ctx);
  346. u1 = BN_CTX_get(ctx);
  347. u2 = BN_CTX_get(ctx);
  348. m = BN_CTX_get(ctx);
  349. X = BN_CTX_get(ctx);
  350. if (X == NULL) {
  351. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  352. goto err;
  353. }
  354. order = EC_GROUP_get0_order(group);
  355. if (order == NULL) {
  356. ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
  357. goto err;
  358. }
  359. if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
  360. BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) ||
  361. BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) {
  362. ERR_raise(ERR_LIB_EC, EC_R_BAD_SIGNATURE);
  363. ret = 0; /* signature is invalid */
  364. goto err;
  365. }
  366. /* calculate tmp1 = inv(S) mod order */
  367. if (!ossl_ec_group_do_inverse_ord(group, u2, sig->s, ctx)) {
  368. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  369. goto err;
  370. }
  371. /* digest -> m */
  372. i = BN_num_bits(order);
  373. /*
  374. * Need to truncate digest if it is too long: first truncate whole bytes.
  375. */
  376. if (8 * dgst_len > i)
  377. dgst_len = (i + 7) / 8;
  378. if (!BN_bin2bn(dgst, dgst_len, m)) {
  379. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  380. goto err;
  381. }
  382. /* If still too long truncate remaining bits with a shift */
  383. if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
  384. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  385. goto err;
  386. }
  387. /* u1 = m * tmp mod order */
  388. if (!BN_mod_mul(u1, m, u2, order, ctx)) {
  389. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  390. goto err;
  391. }
  392. /* u2 = r * w mod q */
  393. if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) {
  394. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  395. goto err;
  396. }
  397. if ((point = EC_POINT_new(group)) == NULL) {
  398. ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE);
  399. goto err;
  400. }
  401. if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) {
  402. ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
  403. goto err;
  404. }
  405. if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, ctx)) {
  406. ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
  407. goto err;
  408. }
  409. if (!BN_nnmod(u1, X, order, ctx)) {
  410. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  411. goto err;
  412. }
  413. /* if the signature is correct u1 is equal to sig->r */
  414. ret = (BN_ucmp(u1, sig->r) == 0);
  415. err:
  416. BN_CTX_end(ctx);
  417. BN_CTX_free(ctx);
  418. EC_POINT_free(point);
  419. return ret;
  420. }