69db9ae783ff9c2a748dc7b5132e1ca74452c850
[people/adir/gpxe.git] / src / crypto / axtls / rsa.c
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(RSA_CTX *rsa, bigint *bi);
32 #endif
33
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
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));   /* reset to all 0 */
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  */
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  */
129 int RSA_decrypt(RSA_CTX *ctx, const uint8_t *in_data, uint8_t *out_data,
130         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         if (block[i-2] != 0xff)
159         {
160             i = byte_size;     /*ensure size is 0 */   
161         }
162     }
163     else                    /* PKCS1.5 encryption padding is random */
164 #endif
165     {
166         while (block[i++] && i < byte_size);
167     }
168     size = byte_size - i;
169
170     /* get only the bit we want */
171     if (size > 0)
172     {
173         memcpy(out_data, &block[i], size);
174     }
175     
176     free(block);
177     return size ? size : -1;
178 }
179
180 /**
181  * Performs m = c^d mod n
182  */
183 bigint *RSA_private(RSA_CTX *c, bigint *bi_msg)
184 {
185 #ifdef CONFIG_BIGINT_CRT
186     return bi_crt(c, bi_msg);
187 #else
188     BI_CTX *ctx = c->bi_ctx;
189     ctx->mod_offset = BIGINT_M_OFFSET;
190     return bi_mod_power(ctx, bi_msg, c->d);
191 #endif
192 }
193
194 #ifdef CONFIG_BIGINT_CRT
195 /**
196  * Use the Chinese Remainder Theorem to quickly perform RSA decrypts.
197  * This should really be in bigint.c (and was at one stage), but needs 
198  * access to the RSA_CTX context...
199  */
200 static bigint *bi_crt(RSA_CTX *rsa, bigint *bi)
201 {
202     BI_CTX *ctx = rsa->bi_ctx;
203     bigint *m1, *m2, *h;
204
205     /* Montgomery has a condition the 0 < x, y < m and these products violate
206      * that condition. So disable Montgomery when using CRT */
207 #if defined(CONFIG_BIGINT_MONTGOMERY)
208     ctx->use_classical = 1;
209 #endif
210     ctx->mod_offset = BIGINT_P_OFFSET;
211     m1 = bi_mod_power(ctx, bi_copy(bi), rsa->dP);
212
213     ctx->mod_offset = BIGINT_Q_OFFSET;
214     m2 = bi_mod_power(ctx, bi, rsa->dQ);
215
216     h = bi_subtract(ctx, bi_add(ctx, m1, rsa->p), bi_copy(m2), NULL);
217     h = bi_multiply(ctx, h, rsa->qInv);
218     ctx->mod_offset = BIGINT_P_OFFSET;
219     h = bi_residue(ctx, h);
220 #if defined(CONFIG_BIGINT_MONTGOMERY)
221     ctx->use_classical = 0;         /* reset for any further operation */
222 #endif
223     return bi_add(ctx, m2, bi_multiply(ctx, rsa->q, h));
224 }
225 #endif
226
227 #ifdef CONFIG_SSL_FULL_MODE
228 /**
229  * Used for diagnostics.
230  */
231 void RSA_print(const RSA_CTX *rsa_ctx) 
232 {
233     if (rsa_ctx == NULL)
234         return;
235
236     printf("-----------------   RSA DEBUG   ----------------\n");
237     printf("Size:\t%d\n", rsa_ctx->num_octets);
238     bi_print("Modulus", rsa_ctx->m);
239     bi_print("Public Key", rsa_ctx->e);
240     bi_print("Private Key", rsa_ctx->d);
241 }
242 #endif
243
244 #ifdef CONFIG_SSL_CERT_VERIFICATION
245 /**
246  * Performs c = m^e mod n
247  */
248 bigint *RSA_public(RSA_CTX *c, bigint *bi_msg)
249 {
250     c->bi_ctx->mod_offset = BIGINT_M_OFFSET;
251     return bi_mod_power(c->bi_ctx, bi_msg, c->e);
252 }
253
254 /**
255  * Use PKCS1.5 for encryption/signing.
256  * see http://www.rsasecurity.com/rsalabs/node.asp?id=2125
257  */
258 int RSA_encrypt(RSA_CTX *ctx, const uint8_t *in_data, uint16_t in_len, 
259         uint8_t *out_data, int is_signing)
260 {
261     int byte_size = ctx->num_octets;
262     int num_pads_needed = byte_size-in_len-3;
263     bigint *dat_bi, *encrypt_bi;
264
265     /* note: in_len+11 must be > byte_size */
266     out_data[0] = 0;     /* ensure encryption block is < modulus */
267
268     if (is_signing)
269     {
270         out_data[1] = 1;        /* PKCS1.5 signing pads with "0xff"'s */
271         memset(&out_data[2], 0xff, num_pads_needed);
272     }
273     else /* randomize the encryption padding with non-zero bytes */   
274     {
275         out_data[1] = 2;
276         memset(&out_data[2], 0x01, num_pads_needed);
277 #if 0
278         get_random_NZ(num_pads_needed, &out_data[2]);
279 #endif
280     }
281
282     out_data[2+num_pads_needed] = 0;
283     memcpy(&out_data[3+num_pads_needed], in_data, in_len);
284
285     /* now encrypt it */
286     dat_bi = bi_import(ctx->bi_ctx, out_data, byte_size);
287     encrypt_bi = is_signing ? RSA_private(ctx, dat_bi) : 
288         RSA_public(ctx, dat_bi);
289     bi_export(ctx->bi_ctx, encrypt_bi, out_data, byte_size);
290     return byte_size;
291 }
292
293 #if 0
294
295 /**
296  * Take a signature and decrypt it.
297  */
298 bigint *RSA_sign_verify(BI_CTX *ctx, const uint8_t *sig, int sig_len,
299         bigint *modulus, bigint *pub_exp)
300 {
301     uint8_t *block = (uint8_t *)malloc(sig_len);
302     int i, size;
303     bigint *decrypted_bi, *dat_bi;
304     bigint *bir = NULL;
305
306     /* decrypt */
307     dat_bi = bi_import(ctx, sig, sig_len);
308     ctx->mod_offset = BIGINT_M_OFFSET;
309
310     /* convert to a normal block */
311     decrypted_bi = bi_mod_power2(ctx, dat_bi, modulus, pub_exp);
312
313     bi_export(ctx, decrypted_bi, block, sig_len);
314     ctx->mod_offset = BIGINT_M_OFFSET;
315
316     i = 10; /* start at the first possible non-padded byte */
317     while (block[i++] && i < sig_len);
318     size = sig_len - i;
319
320     /* get only the bit we want */
321     if (size > 0)
322     {
323         int len;
324         const uint8_t *sig_ptr = x509_get_signature(&block[i], &len);
325
326         if (sig_ptr)
327         {
328             bir = bi_import(ctx, sig_ptr, len);
329         }
330     }
331
332     free(block);
333     return bir;
334 }
335
336 #endif
337
338 #endif  /* CONFIG_SSL_CERT_VERIFICATION */