1 /*
2 * Copyright(C) 2006 Cameron Rich
3 *
4 * This library is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation; either version 2.1 of the License, or
7 * (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18
19 /**
20 * Implements the RSA public encryption algorithm. Uses the bigint library to
21 * perform its calculations.
22 */
23
24 #include <stdio.h>
25 #include <string.h>
26 #include <time.h>
27 #include <stdlib.h>
28 #include "crypto.h"
29
30 #ifdef CONFIG_BIGINT_CRT
31 static bigint *bi_crt(const RSA_CTX *rsa, bigint *bi);
32 #endif
33
RSA_priv_key_new(RSA_CTX ** ctx,const uint8_t * modulus,int mod_len,const uint8_t * pub_exp,int pub_len,const uint8_t * priv_exp,int priv_len,const uint8_t * p,int p_len,const uint8_t * q,int q_len,const uint8_t * dP,int dP_len,const uint8_t * dQ,int dQ_len,const uint8_t * qInv,int qInv_len)34 void RSA_priv_key_new(RSA_CTX **ctx,
35 const uint8_t *modulus, int mod_len,
36 const uint8_t *pub_exp, int pub_len,
37 const uint8_t *priv_exp, int priv_len
38 #if CONFIG_BIGINT_CRT
39 , const uint8_t *p, int p_len,
40 const uint8_t *q, int q_len,
41 const uint8_t *dP, int dP_len,
42 const uint8_t *dQ, int dQ_len,
43 const uint8_t *qInv, int qInv_len
44 #endif
45 )
46 {
47 RSA_CTX *rsa_ctx;
48 BI_CTX *bi_ctx;
49 RSA_pub_key_new(ctx, modulus, mod_len, pub_exp, pub_len);
50 rsa_ctx = *ctx;
51 bi_ctx = rsa_ctx->bi_ctx;
52 rsa_ctx->d = bi_import(bi_ctx, priv_exp, priv_len);
53 bi_permanent(rsa_ctx->d);
54
55 #ifdef CONFIG_BIGINT_CRT
56 rsa_ctx->p = bi_import(bi_ctx, p, p_len);
57 rsa_ctx->q = bi_import(bi_ctx, q, q_len);
58 rsa_ctx->dP = bi_import(bi_ctx, dP, dP_len);
59 rsa_ctx->dQ = bi_import(bi_ctx, dQ, dQ_len);
60 rsa_ctx->qInv = bi_import(bi_ctx, qInv, qInv_len);
61 bi_permanent(rsa_ctx->dP);
62 bi_permanent(rsa_ctx->dQ);
63 bi_permanent(rsa_ctx->qInv);
64 bi_set_mod(bi_ctx, rsa_ctx->p, BIGINT_P_OFFSET);
65 bi_set_mod(bi_ctx, rsa_ctx->q, BIGINT_Q_OFFSET);
66 #endif
67 }
68
RSA_pub_key_new(RSA_CTX ** ctx,const uint8_t * modulus,int mod_len,const uint8_t * pub_exp,int pub_len)69 void RSA_pub_key_new(RSA_CTX **ctx,
70 const uint8_t *modulus, int mod_len,
71 const uint8_t *pub_exp, int pub_len)
72 {
73 RSA_CTX *rsa_ctx;
74 BI_CTX *bi_ctx = bi_initialize();
75 *ctx = (RSA_CTX *)calloc(1, sizeof(RSA_CTX));
76 rsa_ctx = *ctx;
77 rsa_ctx->bi_ctx = bi_ctx;
78 rsa_ctx->num_octets = (mod_len & 0xFFF0);
79 rsa_ctx->m = bi_import(bi_ctx, modulus, mod_len);
80 bi_set_mod(bi_ctx, rsa_ctx->m, BIGINT_M_OFFSET);
81 rsa_ctx->e = bi_import(bi_ctx, pub_exp, pub_len);
82 bi_permanent(rsa_ctx->e);
83 }
84
85 /**
86 * Free up any RSA context resources.
87 */
RSA_free(RSA_CTX * rsa_ctx)88 void RSA_free(RSA_CTX *rsa_ctx)
89 {
90 BI_CTX *bi_ctx;
91 if (rsa_ctx == NULL) /* deal with ptrs that are null */
92 return;
93
94 bi_ctx = rsa_ctx->bi_ctx;
95
96 bi_depermanent(rsa_ctx->e);
97 bi_free(bi_ctx, rsa_ctx->e);
98 bi_free_mod(rsa_ctx->bi_ctx, BIGINT_M_OFFSET);
99
100 if (rsa_ctx->d)
101 {
102 bi_depermanent(rsa_ctx->d);
103 bi_free(bi_ctx, rsa_ctx->d);
104 #ifdef CONFIG_BIGINT_CRT
105 bi_depermanent(rsa_ctx->dP);
106 bi_depermanent(rsa_ctx->dQ);
107 bi_depermanent(rsa_ctx->qInv);
108 bi_free(bi_ctx, rsa_ctx->dP);
109 bi_free(bi_ctx, rsa_ctx->dQ);
110 bi_free(bi_ctx, rsa_ctx->qInv);
111 bi_free_mod(rsa_ctx->bi_ctx, BIGINT_P_OFFSET);
112 bi_free_mod(rsa_ctx->bi_ctx, BIGINT_Q_OFFSET);
113 #endif
114 }
115
116 bi_terminate(bi_ctx);
117 free(rsa_ctx);
118 }
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 */
RSA_decrypt(const RSA_CTX * ctx,const uint8_t * in_data,uint8_t * out_data,int is_decryption)129 int RSA_decrypt(const RSA_CTX *ctx, const uint8_t *in_data,
130 uint8_t *out_data, int is_decryption)
131 {
132 int byte_size = ctx->num_octets;
133 uint8_t *block;
134 int i, size;
135 bigint *decrypted_bi, *dat_bi;
136
137 memset(out_data, 0, byte_size); /* initialise */
138
139 /* decrypt */
140 dat_bi = bi_import(ctx->bi_ctx, in_data, byte_size);
141 #ifdef CONFIG_SSL_CERT_VERIFICATION
142 decrypted_bi = is_decryption ? /* decrypt or verify? */
143 RSA_private(ctx, dat_bi) : RSA_public(ctx, dat_bi);
144 #else /* always a decryption */
145 decrypted_bi = RSA_private(ctx, dat_bi);
146 #endif
147
148 /* convert to a normal block */
149 block = (uint8_t *)malloc(byte_size);
150 bi_export(ctx->bi_ctx, decrypted_bi, block, byte_size);
151
152 i = 10; /* start at the first possible non-padded byte */
153
154 #ifdef CONFIG_SSL_CERT_VERIFICATION
155 if (is_decryption == 0) /* PKCS1.5 signing pads with "0xff"s */
156 {
157 while (block[i++] == 0xff && i < byte_size);
158
159 if (block[i-2] != 0xff)
160 i = byte_size; /*ensure size is 0 */
161 }
162 else /* PKCS1.5 encryption padding is random */
163 #endif
164 {
165 while (block[i++] && i < byte_size);
166 }
167 size = byte_size - i;
168
169 /* get only the bit we want */
170 if (size > 0)
171 memcpy(out_data, &block[i], size);
172
173 free(block);
174 return size ? size : -1;
175 }
176
177 /**
178 * Performs m = c^d mod n
179 */
RSA_private(const RSA_CTX * c,bigint * bi_msg)180 bigint *RSA_private(const RSA_CTX *c, bigint *bi_msg)
181 {
182 #ifdef CONFIG_BIGINT_CRT
183 return bi_crt(c, bi_msg);
184 #else
185 BI_CTX *ctx = c->bi_ctx;
186 ctx->mod_offset = BIGINT_M_OFFSET;
187 return bi_mod_power(ctx, bi_msg, c->d);
188 #endif
189 }
190
191 #ifdef CONFIG_BIGINT_CRT
192 /**
193 * Use the Chinese Remainder Theorem to quickly perform RSA decrypts.
194 * This should really be in bigint.c (and was at one stage), but needs
195 * access to the RSA_CTX context...
196 */
bi_crt(const RSA_CTX * rsa,bigint * bi)197 static bigint *bi_crt(const RSA_CTX *rsa, bigint *bi)
198 {
199 BI_CTX *ctx = rsa->bi_ctx;
200 bigint *m1, *m2, *h;
201
202 /* Montgomery has a condition the 0 < x, y < m and these products violate
203 * that condition. So disable Montgomery when using CRT */
204 #if defined(CONFIG_BIGINT_MONTGOMERY)
205 ctx->use_classical = 1;
206 #endif
207 ctx->mod_offset = BIGINT_P_OFFSET;
208 m1 = bi_mod_power(ctx, bi_copy(bi), rsa->dP);
209
210 ctx->mod_offset = BIGINT_Q_OFFSET;
211 m2 = bi_mod_power(ctx, bi, rsa->dQ);
212
213 h = bi_subtract(ctx, bi_add(ctx, m1, rsa->p), bi_copy(m2), NULL);
214 h = bi_multiply(ctx, h, rsa->qInv);
215 ctx->mod_offset = BIGINT_P_OFFSET;
216 h = bi_residue(ctx, h);
217 #if defined(CONFIG_BIGINT_MONTGOMERY)
218 ctx->use_classical = 0; /* reset for any further operation */
219 #endif
220 return bi_add(ctx, m2, bi_multiply(ctx, rsa->q, h));
221 }
222 #endif
223
224 #ifdef CONFIG_SSL_FULL_MODE
225 /**
226 * Used for diagnostics.
227 */
RSA_print(const RSA_CTX * rsa_ctx)228 void RSA_print(const RSA_CTX *rsa_ctx)
229 {
230 if (rsa_ctx == NULL)
231 return;
232
233 printf("----------------- RSA DEBUG ----------------\n");
234 printf("Size:\t%d\n", rsa_ctx->num_octets);
235 bi_print("Modulus", rsa_ctx->m);
236 bi_print("Public Key", rsa_ctx->e);
237 bi_print("Private Key", rsa_ctx->d);
238 }
239 #endif
240
241 #ifdef CONFIG_SSL_CERT_VERIFICATION
242 /**
243 * Performs c = m^e mod n
244 */
RSA_public(const RSA_CTX * c,bigint * bi_msg)245 bigint *RSA_public(const RSA_CTX * c, bigint *bi_msg)
246 {
247 c->bi_ctx->mod_offset = BIGINT_M_OFFSET;
248 return bi_mod_power(c->bi_ctx, bi_msg, c->e);
249 }
250
251 /**
252 * Use PKCS1.5 for encryption/signing.
253 * see http://www.rsasecurity.com/rsalabs/node.asp?id=2125
254 */
RSA_encrypt(const RSA_CTX * ctx,const uint8_t * in_data,uint16_t in_len,uint8_t * out_data,int is_signing)255 int RSA_encrypt(const RSA_CTX *ctx, const uint8_t *in_data, uint16_t in_len,
256 uint8_t *out_data, int is_signing)
257 {
258 int byte_size = ctx->num_octets;
259 int num_pads_needed = byte_size-in_len-3;
260 bigint *dat_bi, *encrypt_bi;
261
262 /* note: in_len+11 must be > byte_size */
263 out_data[0] = 0; /* ensure encryption block is < modulus */
264
265 if (is_signing)
266 {
267 out_data[1] = 1; /* PKCS1.5 signing pads with "0xff"'s */
268 memset(&out_data[2], 0xff, num_pads_needed);
269 }
270 else /* randomize the encryption padding with non-zero bytes */
271 {
272 out_data[1] = 2;
273 get_random_NZ(num_pads_needed, &out_data[2]);
274 }
275
276 out_data[2+num_pads_needed] = 0;
277 memcpy(&out_data[3+num_pads_needed], in_data, in_len);
278
279 /* now encrypt it */
280 dat_bi = bi_import(ctx->bi_ctx, out_data, byte_size);
281 encrypt_bi = is_signing ? RSA_private(ctx, dat_bi) :
282 RSA_public(ctx, dat_bi);
283 bi_export(ctx->bi_ctx, encrypt_bi, out_data, byte_size);
284 return byte_size;
285 }
286
287 #if 0
288 /**
289 * Take a signature and decrypt it.
290 */
291 bigint *RSA_sign_verify(BI_CTX *ctx, const uint8_t *sig, int sig_len,
292 bigint *modulus, bigint *pub_exp)
293 {
294 uint8_t *block;
295 int i, size;
296 bigint *decrypted_bi, *dat_bi;
297 bigint *bir = NULL;
298
299 block = (uint8_t *)malloc(sig_len);
300
301 /* decrypt */
302 dat_bi = bi_import(ctx, sig, sig_len);
303 ctx->mod_offset = BIGINT_M_OFFSET;
304
305 /* convert to a normal block */
306 decrypted_bi = bi_mod_power2(ctx, dat_bi, modulus, pub_exp);
307
308 bi_export(ctx, decrypted_bi, block, sig_len);
309 ctx->mod_offset = BIGINT_M_OFFSET;
310
311 i = 10; /* start at the first possible non-padded byte */
312 while (block[i++] && i < sig_len);
313 size = sig_len - i;
314
315 /* get only the bit we want */
316 if (size > 0)
317 {
318 int len;
319 const uint8_t *sig_ptr = x509_get_signature(&block[i], &len);
320
321 if (sig_ptr)
322 {
323 bir = bi_import(ctx, sig_ptr, len);
324 }
325 }
326
327 free(block);
328 return bir;
329 }
330 #endif
331
332 #endif /* CONFIG_SSL_CERT_VERIFICATION */
333