rsa.c

00001 /*
00002  * Copyright (c) 2007, Cameron Rich
00003  * 
00004  * All rights reserved.
00005  * 
00006  * Redistribution and use in source and binary forms, with or without 
00007  * modification, are permitted provided that the following conditions are met:
00008  *
00009  * * Redistributions of source code must retain the above copyright notice, 
00010  *   this list of conditions and the following disclaimer.
00011  * * Redistributions in binary form must reproduce the above copyright notice, 
00012  *   this list of conditions and the following disclaimer in the documentation 
00013  *   and/or other materials provided with the distribution.
00014  * * Neither the name of the axTLS project nor the names of its contributors 
00015  *   may be used to endorse or promote products derived from this software 
00016  *   without specific prior written permission.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
00022  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00023  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00024  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00025  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00026  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00027  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  */
00030 
00031 /**
00032  * Implements the RSA public encryption algorithm. Uses the bigint library to
00033  * perform its calculations.
00034  */
00035 
00036 #include <stdio.h>
00037 #include <string.h>
00038 #include <time.h>
00039 #include <stdlib.h>
00040 #include "os_port.h"
00041 #include "crypto.h "
00042 
00043 void RSA_priv_key_new(RSA_CTX **ctx, 
00044         const uint8_t *modulus, int mod_len,
00045         const uint8_t *pub_exp, int pub_len,
00046         const uint8_t *priv_exp, int priv_len
00047 #if CONFIG_BIGINT_CRT
00048       , const uint8_t *p, int p_len,
00049         const uint8_t *q, int q_len,
00050         const uint8_t *dP, int dP_len,
00051         const uint8_t *dQ, int dQ_len,
00052         const uint8_t *qInv, int qInv_len
00053 #endif
00054     )
00055 {
00056     RSA_CTX *rsa_ctx;
00057     BI_CTX *bi_ctx;
00058     RSA_pub_key_new(ctx, modulus, mod_len, pub_exp, pub_len);
00059     rsa_ctx = *ctx;
00060     bi_ctx = rsa_ctx->bi_ctx;
00061     rsa_ctx->d = bi_import(bi_ctx, priv_exp, priv_len);
00062     bi_permanent(rsa_ctx->d);
00063 
00064 #ifdef CONFIG_BIGINT_CRT
00065     rsa_ctx->p = bi_import(bi_ctx, p, p_len);
00066     rsa_ctx->q = bi_import(bi_ctx, q, q_len);
00067     rsa_ctx->dP = bi_import(bi_ctx, dP, dP_len);
00068     rsa_ctx->dQ = bi_import(bi_ctx, dQ, dQ_len);
00069     rsa_ctx->qInv = bi_import(bi_ctx, qInv, qInv_len);
00070     bi_permanent(rsa_ctx->dP);
00071     bi_permanent(rsa_ctx->dQ);
00072     bi_permanent(rsa_ctx->qInv);
00073     bi_set_mod(bi_ctx, rsa_ctx->p, BIGINT_P_OFFSET);
00074     bi_set_mod(bi_ctx, rsa_ctx->q, BIGINT_Q_OFFSET);
00075 #endif
00076 }
00077 
00078 void RSA_pub_key_new(RSA_CTX **ctx, 
00079         const uint8_t *modulus, int mod_len,
00080         const uint8_t *pub_exp, int pub_len)
00081 {
00082     RSA_CTX *rsa_ctx;
00083     BI_CTX *bi_ctx;
00084 
00085     if (*ctx)   /* if we load multiple certs, dump the old one */
00086         RSA_free(*ctx);
00087 
00088     bi_ctx = bi_initialize();
00089     *ctx = (RSA_CTX *)calloc(1, sizeof(RSA_CTX));
00090     rsa_ctx = *ctx;
00091     rsa_ctx->bi_ctx = bi_ctx;
00092     rsa_ctx->num_octets = mod_len;
00093     rsa_ctx->m = bi_import(bi_ctx, modulus, mod_len);
00094     bi_set_mod(bi_ctx, rsa_ctx->m, BIGINT_M_OFFSET);
00095     rsa_ctx->e = bi_import(bi_ctx, pub_exp, pub_len);
00096     bi_permanent(rsa_ctx->e);
00097 }
00098 
00099 /**
00100  * Free up any RSA context resources.
00101  */
00102 void RSA_free(RSA_CTX *rsa_ctx)
00103 {
00104     BI_CTX *bi_ctx;
00105     if (rsa_ctx == NULL)                /* deal with ptrs that are null */
00106         return;
00107 
00108     bi_ctx = rsa_ctx->bi_ctx;
00109 
00110     bi_depermanent(rsa_ctx->e);
00111     bi_free(bi_ctx, rsa_ctx->e);
00112     bi_free_mod(rsa_ctx->bi_ctx, BIGINT_M_OFFSET);
00113 
00114     if (rsa_ctx->d)
00115     {
00116         bi_depermanent(rsa_ctx->d);
00117         bi_free(bi_ctx, rsa_ctx->d);
00118 #ifdef CONFIG_BIGINT_CRT
00119         bi_depermanent(rsa_ctx->dP);
00120         bi_depermanent(rsa_ctx->dQ);
00121         bi_depermanent(rsa_ctx->qInv);
00122         bi_free(bi_ctx, rsa_ctx->dP);
00123         bi_free(bi_ctx, rsa_ctx->dQ);
00124         bi_free(bi_ctx, rsa_ctx->qInv);
00125         bi_free_mod(rsa_ctx->bi_ctx, BIGINT_P_OFFSET);
00126         bi_free_mod(rsa_ctx->bi_ctx, BIGINT_Q_OFFSET);
00127 #endif
00128     }
00129 
00130     bi_terminate(bi_ctx);
00131     free(rsa_ctx);
00132 }
00133 
00134 /**
00135  * @brief Use PKCS1.5 for decryption/verification.
00136  * @param ctx [in] The context
00137  * @param in_data [in] The data to encrypt (must be < modulus size-11)
00138  * @param out_data [out] The encrypted data.
00139  * @param is_decryption [in] Decryption or verify operation.
00140  * @return  The number of bytes that were originally encrypted. -1 on error.
00141  * @see http://www.rsasecurity.com/rsalabs/node.asp?id=2125
00142  */
00143 int RSA_decrypt(const RSA_CTX *ctx, const uint8_t *in_data, 
00144                             uint8_t *out_data, int is_decryption)
00145 {
00146     const int byte_size = ctx->num_octets;
00147     int i, size;
00148     bigint *decrypted_bi, *dat_bi;
00149     uint8_t *block = (uint8_t *)alloca(byte_size);
00150 
00151     memset(out_data, 0, byte_size); /* initialise */
00152 
00153     /* decrypt */
00154     dat_bi = bi_import(ctx->bi_ctx, in_data, byte_size);
00155 #ifdef CONFIG_SSL_CERT_VERIFICATION
00156     decrypted_bi = is_decryption ?  /* decrypt or verify? */
00157             RSA_private(ctx, dat_bi) : RSA_public(ctx, dat_bi);
00158 #else   /* always a decryption */
00159     decrypted_bi = RSA_private(ctx, dat_bi);
00160 #endif
00161 
00162     /* convert to a normal block */
00163     bi_export(ctx->bi_ctx, decrypted_bi, block, byte_size);
00164 
00165     i = 10; /* start at the first possible non-padded byte */
00166 
00167 #ifdef CONFIG_SSL_CERT_VERIFICATION
00168     if (is_decryption == 0) /* PKCS1.5 signing pads with "0xff"s */
00169     {
00170         while (block[i++] == 0xff && i < byte_size);
00171 
00172         if (block[i-2] != 0xff)
00173             i = byte_size;     /*ensure size is 0 */   
00174     }
00175     else                    /* PKCS1.5 encryption padding is random */
00176 #endif
00177     {
00178         while (block[i++] && i < byte_size);
00179     }
00180     size = byte_size - i;
00181 
00182     /* get only the bit we want */
00183     if (size > 0)
00184         memcpy(out_data, &block[i], size);
00185     
00186     return size ? size : -1;
00187 }
00188 
00189 /**
00190  * Performs m = c^d mod n
00191  */
00192 bigint *RSA_private(const RSA_CTX *c, bigint *bi_msg)
00193 {
00194 #ifdef CONFIG_BIGINT_CRT
00195     return bi_crt(c->bi_ctx, bi_msg, c->dP, c->dQ, c->p, c->q, c->qInv);
00196 #else
00197     BI_CTX *ctx = c->bi_ctx;
00198     ctx->mod_offset = BIGINT_M_OFFSET;
00199     return bi_mod_power(ctx, bi_msg, c->d);
00200 #endif
00201 }
00202 
00203 #ifdef CONFIG_SSL_FULL_MODE
00204 /**
00205  * Used for diagnostics.
00206  */
00207 void RSA_print(const RSA_CTX *rsa_ctx) 
00208 {
00209     if (rsa_ctx == NULL)
00210         return;
00211 
00212     printf("-----------------   RSA DEBUG   ----------------\n");
00213     printf("Size:\t%d\n", rsa_ctx->num_octets);
00214     bi_print("Modulus", rsa_ctx->m);
00215     bi_print("Public Key", rsa_ctx->e);
00216     bi_print("Private Key", rsa_ctx->d);
00217 }
00218 #endif
00219 
00220 #if defined(CONFIG_SSL_CERT_VERIFICATION) || defined(CONFIG_SSL_GENERATE_X509_CERT)
00221 /**
00222  * Performs c = m^e mod n
00223  */
00224 bigint *RSA_public(const RSA_CTX * c, bigint *bi_msg)
00225 {
00226     c->bi_ctx->mod_offset = BIGINT_M_OFFSET;
00227     return bi_mod_power(c->bi_ctx, bi_msg, c->e);
00228 }
00229 
00230 /**
00231  * Use PKCS1.5 for encryption/signing.
00232  * see http://www.rsasecurity.com/rsalabs/node.asp?id=2125
00233  */
00234 int RSA_encrypt(const RSA_CTX *ctx, const uint8_t *in_data, uint16_t in_len, 
00235         uint8_t *out_data, int is_signing)
00236 {
00237     int byte_size = ctx->num_octets;
00238     int num_pads_needed = byte_size-in_len-3;
00239     bigint *dat_bi, *encrypt_bi;
00240 
00241     /* note: in_len+11 must be > byte_size */
00242     out_data[0] = 0;     /* ensure encryption block is < modulus */
00243 
00244     if (is_signing)
00245     {
00246         out_data[1] = 1;        /* PKCS1.5 signing pads with "0xff"'s */
00247         memset(&out_data[2], 0xff, num_pads_needed);
00248     }
00249     else /* randomize the encryption padding with non-zero bytes */   
00250     {
00251         out_data[1] = 2;
00252         get_random_NZ(num_pads_needed, &out_data[2]);
00253     }
00254 
00255     out_data[2+num_pads_needed] = 0;
00256     memcpy(&out_data[3+num_pads_needed], in_data, in_len);
00257 
00258     /* now encrypt it */
00259     dat_bi = bi_import(ctx->bi_ctx, out_data, byte_size);
00260     encrypt_bi = is_signing ? RSA_private(ctx, dat_bi) : 
00261                               RSA_public(ctx, dat_bi);
00262     bi_export(ctx->bi_ctx, encrypt_bi, out_data, byte_size);
00263 
00264     /* save a few bytes of memory */
00265     bi_clear_cache(ctx->bi_ctx);
00266     return byte_size;
00267 }
00268 
00269 #endif  /* CONFIG_SSL_CERT_VERIFICATION */