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 */ 333
