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 31static bigint *bi_crt(const RSA_CTX *rsa, bigint *bi); 32#endif 33 34void 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 69void 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 */ 88void 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 */ 129int 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 */ 180bigint *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 */ 197static 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 */ 228void 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 */ 245bigint *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 */ 255int 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 */ 291bigint *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