rsa.c 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268
  1. /*
  2. * Copyright (c) 2007, Cameron Rich
  3. *
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions are met:
  8. *
  9. * * Redistributions of source code must retain the above copyright notice,
  10. * this list of conditions and the following disclaimer.
  11. * * Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. * * Neither the name of the axTLS project nor the names of its contributors
  15. * may be used to endorse or promote products derived from this software
  16. * without specific prior written permission.
  17. *
  18. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  22. * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  23. * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  24. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  25. * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  26. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  27. * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  28. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29. */
  30. /**
  31. * Implements the RSA public encryption algorithm. Uses the bigint library to
  32. * perform its calculations.
  33. */
  34. #include <stdio.h>
  35. #include <string.h>
  36. #include <time.h>
  37. #include <stdlib.h>
  38. #include "crypto.h"
  39. void RSA_priv_key_new(RSA_CTX **ctx,
  40. const uint8_t *modulus, int mod_len,
  41. const uint8_t *pub_exp, int pub_len,
  42. const uint8_t *priv_exp, int priv_len
  43. #if CONFIG_BIGINT_CRT
  44. , const uint8_t *p, int p_len,
  45. const uint8_t *q, int q_len,
  46. const uint8_t *dP, int dP_len,
  47. const uint8_t *dQ, int dQ_len,
  48. const uint8_t *qInv, int qInv_len
  49. #endif
  50. )
  51. {
  52. RSA_CTX *rsa_ctx;
  53. BI_CTX *bi_ctx;
  54. RSA_pub_key_new(ctx, modulus, mod_len, pub_exp, pub_len);
  55. rsa_ctx = *ctx;
  56. bi_ctx = rsa_ctx->bi_ctx;
  57. rsa_ctx->d = bi_import(bi_ctx, priv_exp, priv_len);
  58. bi_permanent(rsa_ctx->d);
  59. #ifdef CONFIG_BIGINT_CRT
  60. rsa_ctx->p = bi_import(bi_ctx, p, p_len);
  61. rsa_ctx->q = bi_import(bi_ctx, q, q_len);
  62. rsa_ctx->dP = bi_import(bi_ctx, dP, dP_len);
  63. rsa_ctx->dQ = bi_import(bi_ctx, dQ, dQ_len);
  64. rsa_ctx->qInv = bi_import(bi_ctx, qInv, qInv_len);
  65. bi_permanent(rsa_ctx->dP);
  66. bi_permanent(rsa_ctx->dQ);
  67. bi_permanent(rsa_ctx->qInv);
  68. bi_set_mod(bi_ctx, rsa_ctx->p, BIGINT_P_OFFSET);
  69. bi_set_mod(bi_ctx, rsa_ctx->q, BIGINT_Q_OFFSET);
  70. #endif
  71. }
  72. void RSA_pub_key_new(RSA_CTX **ctx,
  73. const uint8_t *modulus, int mod_len,
  74. const uint8_t *pub_exp, int pub_len)
  75. {
  76. RSA_CTX *rsa_ctx;
  77. BI_CTX *bi_ctx;
  78. if (*ctx) /* if we load multiple certs, dump the old one */
  79. RSA_free(*ctx);
  80. bi_ctx = bi_initialize();
  81. *ctx = (RSA_CTX *)calloc(1, sizeof(RSA_CTX));
  82. rsa_ctx = *ctx;
  83. rsa_ctx->bi_ctx = bi_ctx;
  84. rsa_ctx->num_octets = (mod_len & 0xFFF0);
  85. rsa_ctx->m = bi_import(bi_ctx, modulus, mod_len);
  86. bi_set_mod(bi_ctx, rsa_ctx->m, BIGINT_M_OFFSET);
  87. rsa_ctx->e = bi_import(bi_ctx, pub_exp, pub_len);
  88. bi_permanent(rsa_ctx->e);
  89. }
  90. /**
  91. * Free up any RSA context resources.
  92. */
  93. void RSA_free(RSA_CTX *rsa_ctx)
  94. {
  95. BI_CTX *bi_ctx;
  96. if (rsa_ctx == NULL) /* deal with ptrs that are null */
  97. return;
  98. bi_ctx = rsa_ctx->bi_ctx;
  99. bi_depermanent(rsa_ctx->e);
  100. bi_free(bi_ctx, rsa_ctx->e);
  101. bi_free_mod(rsa_ctx->bi_ctx, BIGINT_M_OFFSET);
  102. if (rsa_ctx->d)
  103. {
  104. bi_depermanent(rsa_ctx->d);
  105. bi_free(bi_ctx, rsa_ctx->d);
  106. #ifdef CONFIG_BIGINT_CRT
  107. bi_depermanent(rsa_ctx->dP);
  108. bi_depermanent(rsa_ctx->dQ);
  109. bi_depermanent(rsa_ctx->qInv);
  110. bi_free(bi_ctx, rsa_ctx->dP);
  111. bi_free(bi_ctx, rsa_ctx->dQ);
  112. bi_free(bi_ctx, rsa_ctx->qInv);
  113. bi_free_mod(rsa_ctx->bi_ctx, BIGINT_P_OFFSET);
  114. bi_free_mod(rsa_ctx->bi_ctx, BIGINT_Q_OFFSET);
  115. #endif
  116. }
  117. bi_terminate(bi_ctx);
  118. free(rsa_ctx);
  119. }
  120. /**
  121. * @brief Use PKCS1.5 for decryption/verification.
  122. * @param ctx [in] The context
  123. * @param in_data [in] The data to encrypt (must be < modulus size-11)
  124. * @param out_data [out] The encrypted data.
  125. * @param is_decryption [in] Decryption or verify operation.
  126. * @return The number of bytes that were originally encrypted. -1 on error.
  127. * @see http://www.rsasecurity.com/rsalabs/node.asp?id=2125
  128. */
  129. int RSA_decrypt(const RSA_CTX *ctx, const uint8_t *in_data,
  130. uint8_t *out_data, int is_decryption)
  131. {
  132. const int byte_size = ctx->num_octets;
  133. int i, size;
  134. bigint *decrypted_bi, *dat_bi;
  135. uint8_t *block = (uint8_t *)alloca(byte_size);
  136. memset(out_data, 0, byte_size); /* initialise */
  137. /* decrypt */
  138. dat_bi = bi_import(ctx->bi_ctx, in_data, byte_size);
  139. #ifdef CONFIG_SSL_CERT_VERIFICATION
  140. decrypted_bi = is_decryption ? /* decrypt or verify? */
  141. RSA_private(ctx, dat_bi) : RSA_public(ctx, dat_bi);
  142. #else /* always a decryption */
  143. decrypted_bi = RSA_private(ctx, dat_bi);
  144. #endif
  145. /* convert to a normal block */
  146. bi_export(ctx->bi_ctx, decrypted_bi, block, byte_size);
  147. i = 10; /* start at the first possible non-padded byte */
  148. #ifdef CONFIG_SSL_CERT_VERIFICATION
  149. if (is_decryption == 0) /* PKCS1.5 signing pads with "0xff"s */
  150. {
  151. while (block[i++] == 0xff && i < byte_size);
  152. if (block[i-2] != 0xff)
  153. i = byte_size; /*ensure size is 0 */
  154. }
  155. else /* PKCS1.5 encryption padding is random */
  156. #endif
  157. {
  158. while (block[i++] && i < byte_size);
  159. }
  160. size = byte_size - i;
  161. /* get only the bit we want */
  162. if (size > 0)
  163. memcpy(out_data, &block[i], size);
  164. return size ? size : -1;
  165. }
  166. /**
  167. * Performs m = c^d mod n
  168. */
  169. bigint *RSA_private(const RSA_CTX *c, bigint *bi_msg)
  170. {
  171. #ifdef CONFIG_BIGINT_CRT
  172. return bi_crt(c->bi_ctx, bi_msg, c->dP, c->dQ, c->p, c->q, c->qInv);
  173. #else
  174. BI_CTX *ctx = c->bi_ctx;
  175. ctx->mod_offset = BIGINT_M_OFFSET;
  176. return bi_mod_power(ctx, bi_msg, c->d);
  177. #endif
  178. }
  179. #ifdef CONFIG_SSL_FULL_MODE
  180. /**
  181. * Used for diagnostics.
  182. */
  183. void RSA_print(const RSA_CTX *rsa_ctx)
  184. {
  185. if (rsa_ctx == NULL)
  186. return;
  187. printf("----------------- RSA DEBUG ----------------\n");
  188. printf("Size:\t%d\n", rsa_ctx->num_octets);
  189. bi_print("Modulus", rsa_ctx->m);
  190. bi_print("Public Key", rsa_ctx->e);
  191. bi_print("Private Key", rsa_ctx->d);
  192. }
  193. #endif
  194. #if defined(CONFIG_SSL_CERT_VERIFICATION) || defined(CONFIG_SSL_GENERATE_X509_CERT)
  195. /**
  196. * Performs c = m^e mod n
  197. */
  198. bigint *RSA_public(const RSA_CTX * c, bigint *bi_msg)
  199. {
  200. c->bi_ctx->mod_offset = BIGINT_M_OFFSET;
  201. return bi_mod_power(c->bi_ctx, bi_msg, c->e);
  202. }
  203. /**
  204. * Use PKCS1.5 for encryption/signing.
  205. * see http://www.rsasecurity.com/rsalabs/node.asp?id=2125
  206. */
  207. int RSA_encrypt(const RSA_CTX *ctx, const uint8_t *in_data, uint16_t in_len,
  208. uint8_t *out_data, int is_signing)
  209. {
  210. int byte_size = ctx->num_octets;
  211. int num_pads_needed = byte_size-in_len-3;
  212. bigint *dat_bi, *encrypt_bi;
  213. /* note: in_len+11 must be > byte_size */
  214. out_data[0] = 0; /* ensure encryption block is < modulus */
  215. if (is_signing)
  216. {
  217. out_data[1] = 1; /* PKCS1.5 signing pads with "0xff"'s */
  218. memset(&out_data[2], 0xff, num_pads_needed);
  219. }
  220. else /* randomize the encryption padding with non-zero bytes */
  221. {
  222. out_data[1] = 2;
  223. get_random_NZ(num_pads_needed, &out_data[2]);
  224. }
  225. out_data[2+num_pads_needed] = 0;
  226. memcpy(&out_data[3+num_pads_needed], in_data, in_len);
  227. /* now encrypt it */
  228. dat_bi = bi_import(ctx->bi_ctx, out_data, byte_size);
  229. encrypt_bi = is_signing ? RSA_private(ctx, dat_bi) :
  230. RSA_public(ctx, dat_bi);
  231. bi_export(ctx->bi_ctx, encrypt_bi, out_data, byte_size);
  232. /* save a few bytes of memory */
  233. bi_clear_cache(ctx->bi_ctx);
  234. return byte_size;
  235. }
  236. #endif /* CONFIG_SSL_CERT_VERIFICATION */