rsa-mod-exp.c 8.9 KB

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