ec2_oct.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390
  1. /*
  2. * Copyright 2011-2021 The OpenSSL Project Authors. All Rights Reserved.
  3. * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  4. *
  5. * Licensed under the Apache License 2.0 (the "License"). You may not use
  6. * this file except in compliance with the License. You can obtain a copy
  7. * in the file LICENSE in the source distribution or at
  8. * https://www.openssl.org/source/license.html
  9. */
  10. /*
  11. * ECDSA low level APIs are deprecated for public use, but still ok for
  12. * internal use.
  13. */
  14. #include "internal/deprecated.h"
  15. #include <openssl/err.h>
  16. #include "ec_local.h"
  17. #ifndef OPENSSL_NO_EC2M
  18. /*-
  19. * Calculates and sets the affine coordinates of an EC_POINT from the given
  20. * compressed coordinates. Uses algorithm 2.3.4 of SEC 1.
  21. * Note that the simple implementation only uses affine coordinates.
  22. *
  23. * The method is from the following publication:
  24. *
  25. * Harper, Menezes, Vanstone:
  26. * "Public-Key Cryptosystems with Very Small Key Lengths",
  27. * EUROCRYPT '92, Springer-Verlag LNCS 658,
  28. * published February 1993
  29. *
  30. * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe
  31. * the same method, but claim no priority date earlier than July 29, 1994
  32. * (and additionally fail to cite the EUROCRYPT '92 publication as prior art).
  33. */
  34. int ossl_ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group,
  35. EC_POINT *point,
  36. const BIGNUM *x_, int y_bit,
  37. BN_CTX *ctx)
  38. {
  39. BIGNUM *tmp, *x, *y, *z;
  40. int ret = 0, z0;
  41. #ifndef FIPS_MODULE
  42. BN_CTX *new_ctx = NULL;
  43. if (ctx == NULL) {
  44. ctx = new_ctx = BN_CTX_new();
  45. if (ctx == NULL)
  46. return 0;
  47. }
  48. #endif
  49. y_bit = (y_bit != 0) ? 1 : 0;
  50. BN_CTX_start(ctx);
  51. tmp = BN_CTX_get(ctx);
  52. x = BN_CTX_get(ctx);
  53. y = BN_CTX_get(ctx);
  54. z = BN_CTX_get(ctx);
  55. if (z == NULL)
  56. goto err;
  57. if (!BN_GF2m_mod_arr(x, x_, group->poly))
  58. goto err;
  59. if (BN_is_zero(x)) {
  60. if (!BN_GF2m_mod_sqrt_arr(y, group->b, group->poly, ctx))
  61. goto err;
  62. } else {
  63. if (!group->meth->field_sqr(group, tmp, x, ctx))
  64. goto err;
  65. if (!group->meth->field_div(group, tmp, group->b, tmp, ctx))
  66. goto err;
  67. if (!BN_GF2m_add(tmp, group->a, tmp))
  68. goto err;
  69. if (!BN_GF2m_add(tmp, x, tmp))
  70. goto err;
  71. ERR_set_mark();
  72. if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) {
  73. #ifndef FIPS_MODULE
  74. unsigned long err = ERR_peek_last_error();
  75. if (ERR_GET_LIB(err) == ERR_LIB_BN
  76. && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) {
  77. ERR_pop_to_mark();
  78. ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSED_POINT);
  79. } else
  80. #endif
  81. {
  82. ERR_clear_last_mark();
  83. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  84. }
  85. goto err;
  86. }
  87. ERR_clear_last_mark();
  88. z0 = (BN_is_odd(z)) ? 1 : 0;
  89. if (!group->meth->field_mul(group, y, x, z, ctx))
  90. goto err;
  91. if (z0 != y_bit) {
  92. if (!BN_GF2m_add(y, y, x))
  93. goto err;
  94. }
  95. }
  96. if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
  97. goto err;
  98. ret = 1;
  99. err:
  100. BN_CTX_end(ctx);
  101. #ifndef FIPS_MODULE
  102. BN_CTX_free(new_ctx);
  103. #endif
  104. return ret;
  105. }
  106. /*
  107. * Converts an EC_POINT to an octet string. If buf is NULL, the encoded
  108. * length will be returned. If the length len of buf is smaller than required
  109. * an error will be returned.
  110. */
  111. size_t ossl_ec_GF2m_simple_point2oct(const EC_GROUP *group,
  112. const EC_POINT *point,
  113. point_conversion_form_t form,
  114. unsigned char *buf, size_t len, BN_CTX *ctx)
  115. {
  116. size_t ret;
  117. int used_ctx = 0;
  118. BIGNUM *x, *y, *yxi;
  119. size_t field_len, i, skip;
  120. #ifndef FIPS_MODULE
  121. BN_CTX *new_ctx = NULL;
  122. #endif
  123. if ((form != POINT_CONVERSION_COMPRESSED)
  124. && (form != POINT_CONVERSION_UNCOMPRESSED)
  125. && (form != POINT_CONVERSION_HYBRID)) {
  126. ERR_raise(ERR_LIB_EC, EC_R_INVALID_FORM);
  127. goto err;
  128. }
  129. if (EC_POINT_is_at_infinity(group, point)) {
  130. /* encodes to a single 0 octet */
  131. if (buf != NULL) {
  132. if (len < 1) {
  133. ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL);
  134. return 0;
  135. }
  136. buf[0] = 0;
  137. }
  138. return 1;
  139. }
  140. /* ret := required output buffer length */
  141. field_len = (EC_GROUP_get_degree(group) + 7) / 8;
  142. ret =
  143. (form ==
  144. POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
  145. /* if 'buf' is NULL, just return required length */
  146. if (buf != NULL) {
  147. if (len < ret) {
  148. ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL);
  149. goto err;
  150. }
  151. #ifndef FIPS_MODULE
  152. if (ctx == NULL) {
  153. ctx = new_ctx = BN_CTX_new();
  154. if (ctx == NULL)
  155. return 0;
  156. }
  157. #endif
  158. BN_CTX_start(ctx);
  159. used_ctx = 1;
  160. x = BN_CTX_get(ctx);
  161. y = BN_CTX_get(ctx);
  162. yxi = BN_CTX_get(ctx);
  163. if (yxi == NULL)
  164. goto err;
  165. if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
  166. goto err;
  167. buf[0] = form;
  168. if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) {
  169. if (!group->meth->field_div(group, yxi, y, x, ctx))
  170. goto err;
  171. if (BN_is_odd(yxi))
  172. buf[0]++;
  173. }
  174. i = 1;
  175. skip = field_len - BN_num_bytes(x);
  176. if (skip > field_len) {
  177. ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
  178. goto err;
  179. }
  180. while (skip > 0) {
  181. buf[i++] = 0;
  182. skip--;
  183. }
  184. skip = BN_bn2bin(x, buf + i);
  185. i += skip;
  186. if (i != 1 + field_len) {
  187. ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
  188. goto err;
  189. }
  190. if (form == POINT_CONVERSION_UNCOMPRESSED
  191. || form == POINT_CONVERSION_HYBRID) {
  192. skip = field_len - BN_num_bytes(y);
  193. if (skip > field_len) {
  194. ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
  195. goto err;
  196. }
  197. while (skip > 0) {
  198. buf[i++] = 0;
  199. skip--;
  200. }
  201. skip = BN_bn2bin(y, buf + i);
  202. i += skip;
  203. }
  204. if (i != ret) {
  205. ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR);
  206. goto err;
  207. }
  208. }
  209. if (used_ctx)
  210. BN_CTX_end(ctx);
  211. #ifndef FIPS_MODULE
  212. BN_CTX_free(new_ctx);
  213. #endif
  214. return ret;
  215. err:
  216. if (used_ctx)
  217. BN_CTX_end(ctx);
  218. #ifndef FIPS_MODULE
  219. BN_CTX_free(new_ctx);
  220. #endif
  221. return 0;
  222. }
  223. /*
  224. * Converts an octet string representation to an EC_POINT. Note that the
  225. * simple implementation only uses affine coordinates.
  226. */
  227. int ossl_ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
  228. const unsigned char *buf, size_t len,
  229. BN_CTX *ctx)
  230. {
  231. point_conversion_form_t form;
  232. int y_bit, m;
  233. BIGNUM *x, *y, *yxi;
  234. size_t field_len, enc_len;
  235. int ret = 0;
  236. #ifndef FIPS_MODULE
  237. BN_CTX *new_ctx = NULL;
  238. #endif
  239. if (len == 0) {
  240. ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL);
  241. return 0;
  242. }
  243. /*
  244. * The first octet is the point converison octet PC, see X9.62, page 4
  245. * and section 4.4.2. It must be:
  246. * 0x00 for the point at infinity
  247. * 0x02 or 0x03 for compressed form
  248. * 0x04 for uncompressed form
  249. * 0x06 or 0x07 for hybrid form.
  250. * For compressed or hybrid forms, we store the last bit of buf[0] as
  251. * y_bit and clear it from buf[0] so as to obtain a POINT_CONVERSION_*.
  252. * We error if buf[0] contains any but the above values.
  253. */
  254. y_bit = buf[0] & 1;
  255. form = buf[0] & ~1U;
  256. if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
  257. && (form != POINT_CONVERSION_UNCOMPRESSED)
  258. && (form != POINT_CONVERSION_HYBRID)) {
  259. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  260. return 0;
  261. }
  262. if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
  263. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  264. return 0;
  265. }
  266. /* The point at infinity is represented by a single zero octet. */
  267. if (form == 0) {
  268. if (len != 1) {
  269. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  270. return 0;
  271. }
  272. return EC_POINT_set_to_infinity(group, point);
  273. }
  274. m = EC_GROUP_get_degree(group);
  275. field_len = (m + 7) / 8;
  276. enc_len =
  277. (form ==
  278. POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
  279. if (len != enc_len) {
  280. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  281. return 0;
  282. }
  283. #ifndef FIPS_MODULE
  284. if (ctx == NULL) {
  285. ctx = new_ctx = BN_CTX_new();
  286. if (ctx == NULL)
  287. return 0;
  288. }
  289. #endif
  290. BN_CTX_start(ctx);
  291. x = BN_CTX_get(ctx);
  292. y = BN_CTX_get(ctx);
  293. yxi = BN_CTX_get(ctx);
  294. if (yxi == NULL)
  295. goto err;
  296. if (!BN_bin2bn(buf + 1, field_len, x))
  297. goto err;
  298. if (BN_num_bits(x) > m) {
  299. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  300. goto err;
  301. }
  302. if (form == POINT_CONVERSION_COMPRESSED) {
  303. if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx))
  304. goto err;
  305. } else {
  306. if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
  307. goto err;
  308. if (BN_num_bits(y) > m) {
  309. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  310. goto err;
  311. }
  312. if (form == POINT_CONVERSION_HYBRID) {
  313. /*
  314. * Check that the form in the encoding was set correctly
  315. * according to X9.62 4.4.2.a, 4(c), see also first paragraph
  316. * of X9.62, 4.4.1.b.
  317. */
  318. if (BN_is_zero(x)) {
  319. if (y_bit != 0) {
  320. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  321. goto err;
  322. }
  323. } else {
  324. if (!group->meth->field_div(group, yxi, y, x, ctx))
  325. goto err;
  326. if (y_bit != BN_is_odd(yxi)) {
  327. ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING);
  328. goto err;
  329. }
  330. }
  331. }
  332. /*
  333. * EC_POINT_set_affine_coordinates is responsible for checking that
  334. * the point is on the curve.
  335. */
  336. if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
  337. goto err;
  338. }
  339. ret = 1;
  340. err:
  341. BN_CTX_end(ctx);
  342. #ifndef FIPS_MODULE
  343. BN_CTX_free(new_ctx);
  344. #endif
  345. return ret;
  346. }
  347. #endif