rsa-mod-exp.c 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Copyright (c) 2013, Google Inc.
  4. */
  5. #ifndef USE_HOSTCC
  6. #include <common.h>
  7. #include <fdtdec.h>
  8. #include <log.h>
  9. #include <asm/types.h>
  10. #include <asm/byteorder.h>
  11. #include <linux/errno.h>
  12. #include <asm/types.h>
  13. #include <asm/unaligned.h>
  14. #else
  15. #include "fdt_host.h"
  16. #include "mkimage.h"
  17. #include <fdt_support.h>
  18. #endif
  19. #include <u-boot/rsa.h>
  20. #include <u-boot/rsa-mod-exp.h>
  21. #define UINT64_MULT32(v, multby) (((uint64_t)(v)) * ((uint32_t)(multby)))
  22. #define get_unaligned_be32(a) fdt32_to_cpu(*(uint32_t *)a)
  23. #define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_fdt32(a))
  24. /* Default public exponent for backward compatibility */
  25. #define RSA_DEFAULT_PUBEXP 65537
  26. /**
  27. * subtract_modulus() - subtract modulus from the given value
  28. *
  29. * @key: Key containing modulus to subtract
  30. * @num: Number to subtract modulus from, as little endian word array
  31. */
  32. static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[])
  33. {
  34. int64_t acc = 0;
  35. uint i;
  36. for (i = 0; i < key->len; i++) {
  37. acc += (uint64_t)num[i] - key->modulus[i];
  38. num[i] = (uint32_t)acc;
  39. acc >>= 32;
  40. }
  41. }
  42. /**
  43. * greater_equal_modulus() - check if a value is >= modulus
  44. *
  45. * @key: Key containing modulus to check
  46. * @num: Number to check against modulus, as little endian word array
  47. * @return 0 if num < modulus, 1 if num >= modulus
  48. */
  49. static int greater_equal_modulus(const struct rsa_public_key *key,
  50. uint32_t num[])
  51. {
  52. int i;
  53. for (i = (int)key->len - 1; i >= 0; i--) {
  54. if (num[i] < key->modulus[i])
  55. return 0;
  56. if (num[i] > key->modulus[i])
  57. return 1;
  58. }
  59. return 1; /* equal */
  60. }
  61. /**
  62. * montgomery_mul_add_step() - Perform montgomery multiply-add step
  63. *
  64. * Operation: montgomery result[] += a * b[] / n0inv % modulus
  65. *
  66. * @key: RSA key
  67. * @result: Place to put result, as little endian word array
  68. * @a: Multiplier
  69. * @b: Multiplicand, as little endian word array
  70. */
  71. static void montgomery_mul_add_step(const struct rsa_public_key *key,
  72. uint32_t result[], const uint32_t a, const uint32_t b[])
  73. {
  74. uint64_t acc_a, acc_b;
  75. uint32_t d0;
  76. uint i;
  77. acc_a = (uint64_t)a * b[0] + result[0];
  78. d0 = (uint32_t)acc_a * key->n0inv;
  79. acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a;
  80. for (i = 1; i < key->len; i++) {
  81. acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i];
  82. acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] +
  83. (uint32_t)acc_a;
  84. result[i - 1] = (uint32_t)acc_b;
  85. }
  86. acc_a = (acc_a >> 32) + (acc_b >> 32);
  87. result[i - 1] = (uint32_t)acc_a;
  88. if (acc_a >> 32)
  89. subtract_modulus(key, result);
  90. }
  91. /**
  92. * montgomery_mul() - Perform montgomery mutitply
  93. *
  94. * Operation: montgomery result[] = a[] * b[] / n0inv % modulus
  95. *
  96. * @key: RSA key
  97. * @result: Place to put result, as little endian word array
  98. * @a: Multiplier, as little endian word array
  99. * @b: Multiplicand, as little endian word array
  100. */
  101. static void montgomery_mul(const struct rsa_public_key *key,
  102. uint32_t result[], uint32_t a[], const uint32_t b[])
  103. {
  104. uint i;
  105. for (i = 0; i < key->len; ++i)
  106. result[i] = 0;
  107. for (i = 0; i < key->len; ++i)
  108. montgomery_mul_add_step(key, result, a[i], b);
  109. }
  110. /**
  111. * num_pub_exponent_bits() - Number of bits in the public exponent
  112. *
  113. * @key: RSA key
  114. * @num_bits: Storage for the number of public exponent bits
  115. */
  116. static int num_public_exponent_bits(const struct rsa_public_key *key,
  117. int *num_bits)
  118. {
  119. uint64_t exponent;
  120. int exponent_bits;
  121. const uint max_bits = (sizeof(exponent) * 8);
  122. exponent = key->exponent;
  123. exponent_bits = 0;
  124. if (!exponent) {
  125. *num_bits = exponent_bits;
  126. return 0;
  127. }
  128. for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits)
  129. if (!(exponent >>= 1)) {
  130. *num_bits = exponent_bits;
  131. return 0;
  132. }
  133. return -EINVAL;
  134. }
  135. /**
  136. * is_public_exponent_bit_set() - Check if a bit in the public exponent is set
  137. *
  138. * @key: RSA key
  139. * @pos: The bit position to check
  140. */
  141. static int is_public_exponent_bit_set(const struct rsa_public_key *key,
  142. int pos)
  143. {
  144. return key->exponent & (1ULL << pos);
  145. }
  146. /**
  147. * pow_mod() - in-place public exponentiation
  148. *
  149. * @key: RSA key
  150. * @inout: Big-endian word array containing value and result
  151. */
  152. static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
  153. {
  154. uint32_t *result, *ptr;
  155. uint i;
  156. int j, k;
  157. /* Sanity check for stack size - key->len is in 32-bit words */
  158. if (key->len > RSA_MAX_KEY_BITS / 32) {
  159. debug("RSA key words %u exceeds maximum %d\n", key->len,
  160. RSA_MAX_KEY_BITS / 32);
  161. return -EINVAL;
  162. }
  163. uint32_t val[key->len], acc[key->len], tmp[key->len];
  164. uint32_t a_scaled[key->len];
  165. result = tmp; /* Re-use location. */
  166. /* Convert from big endian byte array to little endian word array. */
  167. for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--)
  168. val[i] = get_unaligned_be32(ptr);
  169. if (0 != num_public_exponent_bits(key, &k))
  170. return -EINVAL;
  171. if (k < 2) {
  172. debug("Public exponent is too short (%d bits, minimum 2)\n",
  173. k);
  174. return -EINVAL;
  175. }
  176. if (!is_public_exponent_bit_set(key, 0)) {
  177. debug("LSB of RSA public exponent must be set.\n");
  178. return -EINVAL;
  179. }
  180. /* the bit at e[k-1] is 1 by definition, so start with: C := M */
  181. montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */
  182. /* retain scaled version for intermediate use */
  183. memcpy(a_scaled, acc, key->len * sizeof(a_scaled[0]));
  184. for (j = k - 2; j > 0; --j) {
  185. montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
  186. if (is_public_exponent_bit_set(key, j)) {
  187. /* acc = tmp * val / R mod n */
  188. montgomery_mul(key, acc, tmp, a_scaled);
  189. } else {
  190. /* e[j] == 0, copy tmp back to acc for next operation */
  191. memcpy(acc, tmp, key->len * sizeof(acc[0]));
  192. }
  193. }
  194. /* the bit at e[0] is always 1 */
  195. montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
  196. montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */
  197. memcpy(result, acc, key->len * sizeof(result[0]));
  198. /* Make sure result < mod; result is at most 1x mod too large. */
  199. if (greater_equal_modulus(key, result))
  200. subtract_modulus(key, result);
  201. /* Convert to bigendian byte array */
  202. for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++)
  203. put_unaligned_be32(result[i], ptr);
  204. return 0;
  205. }
  206. static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len)
  207. {
  208. int i;
  209. for (i = 0; i < len; i++)
  210. dst[i] = fdt32_to_cpu(src[len - 1 - i]);
  211. }
  212. int rsa_mod_exp_sw(const uint8_t *sig, uint32_t sig_len,
  213. struct key_prop *prop, uint8_t *out)
  214. {
  215. struct rsa_public_key key;
  216. int ret;
  217. if (!prop) {
  218. debug("%s: Skipping invalid prop", __func__);
  219. return -EBADF;
  220. }
  221. key.n0inv = prop->n0inv;
  222. key.len = prop->num_bits;
  223. if (!prop->public_exponent)
  224. key.exponent = RSA_DEFAULT_PUBEXP;
  225. else
  226. rsa_convert_big_endian((uint32_t *)&key.exponent,
  227. prop->public_exponent, 2);
  228. if (!key.len || !prop->modulus || !prop->rr) {
  229. debug("%s: Missing RSA key info", __func__);
  230. return -EFAULT;
  231. }
  232. /* Sanity check for stack size */
  233. if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) {
  234. debug("RSA key bits %u outside allowed range %d..%d\n",
  235. key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS);
  236. return -EFAULT;
  237. }
  238. key.len /= sizeof(uint32_t) * 8;
  239. uint32_t key1[key.len], key2[key.len];
  240. key.modulus = key1;
  241. key.rr = key2;
  242. rsa_convert_big_endian(key.modulus, (uint32_t *)prop->modulus, key.len);
  243. rsa_convert_big_endian(key.rr, (uint32_t *)prop->rr, key.len);
  244. if (!key.modulus || !key.rr) {
  245. debug("%s: Out of memory", __func__);
  246. return -ENOMEM;
  247. }
  248. uint32_t buf[sig_len / sizeof(uint32_t)];
  249. memcpy(buf, sig, sig_len);
  250. ret = pow_mod(&key, buf);
  251. if (ret)
  252. return ret;
  253. memcpy(out, buf, sig_len);
  254. return 0;
  255. }
  256. #if defined(CONFIG_CMD_ZYNQ_RSA)
  257. /**
  258. * zynq_pow_mod - in-place public exponentiation
  259. *
  260. * @keyptr: RSA key
  261. * @inout: Big-endian word array containing value and result
  262. * @return 0 on successful calculation, otherwise failure error code
  263. *
  264. * FIXME: Use pow_mod() instead of zynq_pow_mod()
  265. * pow_mod calculation required for zynq is bit different from
  266. * pw_mod above here, hence defined zynq specific routine.
  267. */
  268. int zynq_pow_mod(u32 *keyptr, u32 *inout)
  269. {
  270. u32 *result, *ptr;
  271. uint i;
  272. struct rsa_public_key *key;
  273. u32 val[RSA2048_BYTES], acc[RSA2048_BYTES], tmp[RSA2048_BYTES];
  274. key = (struct rsa_public_key *)keyptr;
  275. /* Sanity check for stack size - key->len is in 32-bit words */
  276. if (key->len > RSA_MAX_KEY_BITS / 32) {
  277. debug("RSA key words %u exceeds maximum %d\n", key->len,
  278. RSA_MAX_KEY_BITS / 32);
  279. return -EINVAL;
  280. }
  281. result = tmp; /* Re-use location. */
  282. for (i = 0, ptr = inout; i < key->len; i++, ptr++)
  283. val[i] = *(ptr);
  284. montgomery_mul(key, acc, val, key->rr); /* axx = a * RR / R mod M */
  285. for (i = 0; i < 16; i += 2) {
  286. montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod M */
  287. montgomery_mul(key, acc, tmp, tmp); /* acc = tmp^2 / R mod M */
  288. }
  289. montgomery_mul(key, result, acc, val); /* result = XX * a / R mod M */
  290. /* Make sure result < mod; result is at most 1x mod too large. */
  291. if (greater_equal_modulus(key, result))
  292. subtract_modulus(key, result);
  293. for (i = 0, ptr = inout; i < key->len; i++, ptr++)
  294. *ptr = result[i];
  295. return 0;
  296. }
  297. #endif