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(const 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));
  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(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  */
 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  */
 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  */
 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  */
 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  */
 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 */