CyaSSL is an SSL library for devices like mbed.
Dependents: cyassl-client Sync
rsa.c
00001 /* rsa.c 00002 * 00003 * Copyright (C) 2006-2009 Sawtooth Consulting Ltd. 00004 * 00005 * This file is part of CyaSSL. 00006 * 00007 * CyaSSL is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU General Public License as published by 00009 * the Free Software Foundation; either version 2 of the License, or 00010 * (at your option) any later version. 00011 * 00012 * CyaSSL is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 00020 */ 00021 00022 00023 00024 #include "ctc_rsa.h" 00025 #include "random.h" 00026 #include "error.h" 00027 00028 #ifdef SHOW_GEN 00029 #include <stdio.h> 00030 #endif 00031 00032 00033 enum { 00034 RSA_PUBLIC_ENCRYPT = 0, 00035 RSA_PUBLIC_DECRYPT = 1, 00036 RSA_PRIVATE_ENCRYPT = 2, 00037 RSA_PRIVATE_DECRYPT = 3, 00038 00039 RSA_BLOCK_TYPE_1 = 1, 00040 RSA_BLOCK_TYPE_2 = 2, 00041 00042 RSA_MIN_SIZE = 512, 00043 RSA_MAX_SIZE = 4096, 00044 00045 RSA_MIN_PAD_SZ = 11 /* seperator + 0 + pad value + 8 pads */ 00046 }; 00047 00048 00049 void InitRsaKey(RsaKey* key, void* heap) 00050 { 00051 key->type = -1; /* haven't decdied yet */ 00052 key->heap = heap; 00053 00054 /* TomsFastMath doesn't use memory allocation */ 00055 #ifndef USE_FAST_MATH 00056 key->n.dp = key->e.dp = 0; /* public alloc parts */ 00057 00058 key->d.dp = key->p.dp = 0; /* private alloc parts */ 00059 key->q.dp = key->dP.dp = 0; 00060 key->u.dp = key->dQ.dp = 0; 00061 #endif 00062 } 00063 00064 00065 void FreeRsaKey(RsaKey* key) 00066 { 00067 /* TomsFastMath doesn't use memory allocation */ 00068 #ifndef USE_FAST_MATH 00069 if (key->type == RSA_PRIVATE) { 00070 mp_clear(&key->u); 00071 mp_clear(&key->dQ); 00072 mp_clear(&key->dP); 00073 mp_clear(&key->q); 00074 mp_clear(&key->p); 00075 mp_clear(&key->d); 00076 } 00077 mp_clear(&key->e); 00078 mp_clear(&key->n); 00079 #endif 00080 } 00081 00082 static void RsaPad(const byte* input, word32 inputLen, byte* pkcsBlock, 00083 word32 pkcsBlockLen, byte padValue, RNG* rng) 00084 { 00085 if (inputLen == 0) return; 00086 00087 pkcsBlock[0] = 0x0; /* set first byte to zero and advance */ 00088 pkcsBlock++; pkcsBlockLen--; 00089 pkcsBlock[0] = padValue; /* insert padValue */ 00090 00091 if (padValue == RSA_BLOCK_TYPE_1) 00092 /* pad with 0xff bytes */ 00093 XMEMSET(&pkcsBlock[1], 0xFF, pkcsBlockLen - inputLen - 2); 00094 else { 00095 /* pad with non-zero random bytes */ 00096 word32 padLen = pkcsBlockLen - inputLen - 1, i; 00097 RNG_GenerateBlock(rng, &pkcsBlock[1], padLen); 00098 00099 /* remove zeros */ 00100 for (i = 1; i < padLen; i++) 00101 if (pkcsBlock[i] == 0) pkcsBlock[i] = 0x01; 00102 } 00103 00104 pkcsBlock[pkcsBlockLen-inputLen-1] = 0; /* separator */ 00105 XMEMCPY(pkcsBlock+pkcsBlockLen-inputLen, input, inputLen); 00106 } 00107 00108 00109 static word32 RsaUnPad(const byte *pkcsBlock, unsigned int pkcsBlockLen, 00110 byte **output, byte padValue) 00111 { 00112 word32 maxOutputLen = (pkcsBlockLen > 10) ? (pkcsBlockLen - 10) : 0, 00113 invalid = 0, 00114 i = 1, 00115 outputLen; 00116 00117 if (pkcsBlock[0] != 0x0) /* skip past zero */ 00118 invalid = 1; 00119 pkcsBlock++; pkcsBlockLen--; 00120 00121 /* Require block type padValue */ 00122 invalid = (pkcsBlock[0] != padValue) || invalid; 00123 00124 /* skip past the padding until we find the separator */ 00125 while (i<pkcsBlockLen && pkcsBlock[i++]) { /* null body */ 00126 } 00127 if(!(i==pkcsBlockLen || pkcsBlock[i-1]==0)) 00128 return 0; 00129 00130 outputLen = pkcsBlockLen - i; 00131 invalid = (outputLen > maxOutputLen) || invalid; 00132 00133 if (invalid) 00134 return 0; 00135 00136 *output = (byte *)(pkcsBlock + i); 00137 return outputLen; 00138 } 00139 00140 00141 static int RsaFunction(const byte* in, word32 inLen, byte* out, word32* outLen, 00142 int type, RsaKey* key) 00143 { 00144 #define ERROR_OUT(x) { ret = x; goto done;} 00145 00146 mp_int tmp; 00147 int ret = 0; 00148 word32 keyLen, len; 00149 00150 if (mp_init(&tmp) != MP_OKAY) 00151 return MP_INIT_E; 00152 00153 if (mp_read_unsigned_bin(&tmp, (byte*)in, inLen) != MP_OKAY) 00154 ERROR_OUT(MP_READ_E); 00155 00156 if (type == RSA_PRIVATE_DECRYPT || type == RSA_PRIVATE_ENCRYPT) { 00157 #ifdef RSA_LOW_MEM /* half as much memory but twice as slow */ 00158 if (mp_exptmod(&tmp, &key->d, &key->n, &tmp) != MP_OKAY) 00159 ERROR_OUT(MP_EXPTMOD_E); 00160 #else 00161 #define INNER_ERROR_OUT(x) { ret = x; goto inner_done; } 00162 00163 mp_int tmpa, tmpb; 00164 00165 if (mp_init(&tmpa) != MP_OKAY) 00166 ERROR_OUT(MP_INIT_E); 00167 00168 if (mp_init(&tmpb) != MP_OKAY) { 00169 mp_clear(&tmpa); 00170 ERROR_OUT(MP_INIT_E); 00171 } 00172 00173 /* tmpa = tmp^dP mod p */ 00174 if (mp_exptmod(&tmp, &key->dP, &key->p, &tmpa) != MP_OKAY) 00175 INNER_ERROR_OUT(MP_EXPTMOD_E); 00176 00177 /* tmpb = tmp^dQ mod q */ 00178 if (mp_exptmod(&tmp, &key->dQ, &key->q, &tmpb) != MP_OKAY) 00179 INNER_ERROR_OUT(MP_EXPTMOD_E); 00180 00181 /* tmp = (tmpa - tmpb) * qInv (mod p) */ 00182 if (mp_sub(&tmpa, &tmpb, &tmp) != MP_OKAY) 00183 INNER_ERROR_OUT(MP_SUB_E); 00184 00185 if (mp_mulmod(&tmp, &key->u, &key->p, &tmp) != MP_OKAY) 00186 INNER_ERROR_OUT(MP_MULMOD_E); 00187 00188 /* tmp = tmpb + q * tmp */ 00189 if (mp_mul(&tmp, &key->q, &tmp) != MP_OKAY) 00190 INNER_ERROR_OUT(MP_MUL_E); 00191 00192 if (mp_add(&tmp, &tmpb, &tmp) != MP_OKAY) 00193 INNER_ERROR_OUT(MP_ADD_E); 00194 00195 inner_done: 00196 mp_clear(&tmpa); 00197 mp_clear(&tmpb); 00198 00199 if (ret != 0) return ret; 00200 00201 #endif /* RSA_LOW_MEM */ 00202 } 00203 else if (type == RSA_PUBLIC_ENCRYPT || type == RSA_PUBLIC_DECRYPT) { 00204 if (mp_exptmod(&tmp, &key->e, &key->n, &tmp) != MP_OKAY) 00205 ERROR_OUT(MP_EXPTMOD_E); 00206 } 00207 else 00208 ERROR_OUT(RSA_WRONG_TYPE_E); 00209 00210 keyLen = mp_unsigned_bin_size(&key->n); 00211 if (keyLen > *outLen) 00212 ERROR_OUT(RSA_BUFFER_E); 00213 00214 len = mp_unsigned_bin_size(&tmp); 00215 00216 /* pad front w/ zeros to match key length */ 00217 while (len < keyLen) { 00218 *out++ = 0x00; 00219 len++; 00220 } 00221 00222 *outLen = keyLen; 00223 00224 /* convert */ 00225 if (mp_to_unsigned_bin(&tmp, out) != MP_OKAY) 00226 ERROR_OUT(MP_TO_E); 00227 00228 done: 00229 mp_clear(&tmp); 00230 return ret; 00231 } 00232 00233 00234 00235 int RsaPublicEncrypt(const byte* in, word32 inLen, byte* out, word32 outLen, 00236 RsaKey* key, RNG* rng) 00237 { 00238 int sz = mp_unsigned_bin_size(&key->n), ret; 00239 00240 if (sz > (int)outLen) 00241 return RSA_BUFFER_E; 00242 00243 if (inLen > (word32)(sz - RSA_MIN_PAD_SZ)) 00244 return RSA_BUFFER_E; 00245 00246 RsaPad(in, inLen, out, sz, RSA_BLOCK_TYPE_2, rng); 00247 00248 if ((ret = RsaFunction(out, sz, out, &outLen, RSA_PUBLIC_ENCRYPT, key)) < 0) 00249 sz = ret; 00250 00251 return sz; 00252 } 00253 00254 00255 int RsaPrivateDecryptInline(byte* in, word32 inLen, byte** out, RsaKey* key) 00256 { 00257 int plainLen, ret; 00258 00259 if ((ret = RsaFunction(in, inLen, in, &inLen, RSA_PRIVATE_DECRYPT, key)) 00260 < 0) { 00261 return ret; 00262 } 00263 00264 plainLen = RsaUnPad(in, inLen, out, RSA_BLOCK_TYPE_2); 00265 00266 return plainLen; 00267 } 00268 00269 int RsaPrivateDecrypt(const byte* in, word32 inLen, byte* out, word32 outLen, 00270 RsaKey* key) 00271 { 00272 int plainLen, ret; 00273 byte* tmp; 00274 byte* pad = 0; 00275 00276 if ( !(tmp = (byte*)XMALLOC(inLen, key->heap, DYNAMIC_TYPE_RSA)) ) 00277 return MEMORY_E; 00278 00279 XMEMCPY(tmp, in, inLen); 00280 00281 if ((ret = plainLen = RsaPrivateDecryptInline(tmp, inLen, &pad, key)) 00282 < 0) { 00283 XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA); 00284 return ret; 00285 } 00286 XMEMCPY(out, pad, plainLen); 00287 XMEMSET(tmp, 0x00, inLen); 00288 00289 XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA); 00290 return plainLen; 00291 } 00292 00293 00294 /* for Rsa Verify */ 00295 int RsaSSL_VerifyInline(byte* in, word32 inLen, byte** out, RsaKey* key) 00296 { 00297 int plainLen, ret; 00298 00299 if ((ret = RsaFunction(in, inLen, in, &inLen, RSA_PUBLIC_DECRYPT, key)) 00300 < 0) { 00301 return ret; 00302 } 00303 00304 plainLen = RsaUnPad(in, inLen, out, RSA_BLOCK_TYPE_1); 00305 00306 return plainLen; 00307 } 00308 00309 int RsaSSL_Verify(const byte* in, word32 inLen, byte* out, word32 outLen, 00310 RsaKey* key) 00311 { 00312 int plainLen, ret; 00313 byte* tmp; 00314 byte* pad = 0; 00315 00316 if ( !(tmp = (byte*)XMALLOC(inLen, key->heap, DYNAMIC_TYPE_RSA)) ) 00317 return MEMORY_E; 00318 00319 XMEMCPY(tmp, in, inLen); 00320 00321 if ((ret = plainLen = RsaSSL_VerifyInline(tmp, inLen, &pad, key)) 00322 < 0) { 00323 XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA); 00324 return ret; 00325 } 00326 00327 XMEMCPY(out, pad, plainLen); 00328 XMEMSET(tmp, 0x00, inLen); 00329 00330 XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA); 00331 return plainLen; 00332 } 00333 00334 00335 /* for Rsa Sign */ 00336 int RsaSSL_Sign(const byte* in, word32 inLen, byte* out, word32 outLen, 00337 RsaKey* key, RNG* rng) 00338 { 00339 int sz = mp_unsigned_bin_size(&key->n), ret; 00340 00341 if (sz > (int)outLen) 00342 return RSA_BUFFER_E; 00343 00344 if (inLen > (word32)(sz - RSA_MIN_PAD_SZ)) 00345 return RSA_BUFFER_E; 00346 00347 RsaPad(in, inLen, out, sz, RSA_BLOCK_TYPE_1, rng); 00348 00349 if ((ret = RsaFunction(out, sz, out, &outLen, RSA_PRIVATE_ENCRYPT,key)) < 0) 00350 sz = ret; 00351 00352 return sz; 00353 } 00354 00355 00356 int RsaEncryptSize(RsaKey* key) 00357 { 00358 return mp_unsigned_bin_size(&key->n); 00359 } 00360 00361 00362 #ifdef CYASSL_KEY_GEN 00363 00364 static const int USE_BBS = 1; 00365 00366 static int rand_prime(mp_int* N, int len, RNG* rng, void* heap) 00367 { 00368 int err, res, type; 00369 byte* buf; 00370 00371 if (N == NULL || rng == NULL) 00372 return -1; 00373 00374 /* get type */ 00375 if (len < 0) { 00376 type = USE_BBS; 00377 len = -len; 00378 } else { 00379 type = 0; 00380 } 00381 00382 /* allow sizes between 2 and 512 bytes for a prime size */ 00383 if (len < 2 || len > 512) { 00384 return -1; 00385 } 00386 00387 /* allocate buffer to work with */ 00388 buf = XCALLOC(1, len, heap); 00389 if (buf == NULL) { 00390 return -1; 00391 } 00392 00393 do { 00394 #ifdef SHOW_GEN 00395 printf("."); 00396 fflush(stdout); 00397 #endif 00398 /* generate value */ 00399 RNG_GenerateBlock(rng, buf, len); 00400 00401 /* munge bits */ 00402 buf[0] |= 0x80 | 0x40; 00403 buf[len-1] |= 0x01 | ((type & USE_BBS) ? 0x02 : 0x00); 00404 00405 /* load value */ 00406 if ((err = mp_read_unsigned_bin(N, buf, len)) != MP_OKAY) { 00407 XFREE(buf, heap, DYNAMIC_TYPE_RSA); 00408 return err; 00409 } 00410 00411 /* test */ 00412 if ((err = mp_prime_is_prime(N, 8, &res)) != MP_OKAY) { 00413 XFREE(buf, heap, DYNAMIC_TYPE_RSA); 00414 return err; 00415 } 00416 } while (res == MP_NO); 00417 00418 #ifdef LTC_CLEAN_STACK 00419 XMEMSET(buf, 0, len); 00420 #endif 00421 00422 XFREE(buf, heap, DYNAMIC_TYPE_RSA); 00423 return 0; 00424 } 00425 00426 00427 /* Make an RSA key for size bits, with e specified, 65537 is a good e */ 00428 int MakeRsaKey(RsaKey* key, int size, long e, RNG* rng) 00429 { 00430 mp_int p, q, tmp1, tmp2, tmp3; 00431 int err; 00432 00433 if (key == NULL || rng == NULL) 00434 return -1; 00435 00436 if (size < RSA_MIN_SIZE || size > RSA_MAX_SIZE) 00437 return -1; 00438 00439 if (e < 3 || (e & 1) == 0) 00440 return -1; 00441 00442 if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != MP_OKAY) 00443 return err; 00444 00445 err = mp_set_int(&tmp3, e); 00446 00447 /* make p */ 00448 if (err == MP_OKAY) { 00449 do { 00450 err = rand_prime(&p, size/16, rng, key->heap); /* size in bytes/2 */ 00451 00452 if (err == MP_OKAY) 00453 err = mp_sub_d(&p, 1, &tmp1); /* tmp1 = p-1 */ 00454 00455 if (err == MP_OKAY) 00456 err = mp_gcd(&tmp1, &tmp3, &tmp2); /* tmp2 = gcd(p-1, e) */ 00457 } while (err == MP_OKAY && mp_cmp_d(&tmp2, 1) != 0); /* e divdes p-1 */ 00458 } 00459 00460 /* make q */ 00461 if (err == MP_OKAY) { 00462 do { 00463 err = rand_prime(&q, size/16, rng, key->heap); /* size in bytes/2 */ 00464 00465 if (err == MP_OKAY) 00466 err = mp_sub_d(&q, 1, &tmp1); /* tmp1 = q-1 */ 00467 00468 if (err == MP_OKAY) 00469 err = mp_gcd(&tmp1, &tmp3, &tmp2); /* tmp2 = gcd(q-1, e) */ 00470 } while (err == MP_OKAY && mp_cmp_d(&tmp2, 1) != 0); /* e divdes q-1 */ 00471 } 00472 00473 if (err == MP_OKAY) 00474 err = mp_init_multi(&key->n, &key->e, &key->d, &key->p, &key->q, NULL); 00475 00476 if (err == MP_OKAY) 00477 err = mp_init_multi(&key->dP, &key->dP, &key->u, NULL, NULL, NULL); 00478 00479 if (err == MP_OKAY) 00480 err = mp_sub_d(&p, 1, &tmp2); /* tmp2 = p-1 */ 00481 00482 if (err == MP_OKAY) 00483 err = mp_lcm(&tmp1, &tmp2, &tmp1); /* tmp1 = lcm(p-1, q-1),last loop */ 00484 00485 /* make key */ 00486 if (err == MP_OKAY) 00487 err = mp_set_int(&key->e, e); /* key->e = e */ 00488 00489 if (err == MP_OKAY) /* key->d = 1/e mod lcm(p-1, q-1) */ 00490 err = mp_invmod(&key->e, &tmp1, &key->d); 00491 00492 if (err == MP_OKAY) 00493 err = mp_mul(&p, &q, &key->n); /* key->n = pq */ 00494 00495 if (err == MP_OKAY) 00496 err = mp_sub_d(&p, 1, &tmp1); 00497 00498 if (err == MP_OKAY) 00499 err = mp_sub_d(&q, 1, &tmp2); 00500 00501 if (err == MP_OKAY) 00502 err = mp_mod(&key->d, &tmp1, &key->dP); 00503 00504 if (err == MP_OKAY) 00505 err = mp_mod(&key->d, &tmp2, &key->dQ); 00506 00507 if (err == MP_OKAY) 00508 err = mp_invmod(&q, &p, &key->u); 00509 00510 if (err == MP_OKAY) 00511 err = mp_copy(&p, &key->p); 00512 00513 if (err == MP_OKAY) 00514 err = mp_copy(&q, &key->q); 00515 00516 if (err == MP_OKAY) 00517 key->type = RSA_PRIVATE; 00518 00519 mp_clear(&tmp3); 00520 mp_clear(&tmp2); 00521 mp_clear(&tmp1); 00522 mp_clear(&q); 00523 mp_clear(&p); 00524 00525 if (err != MP_OKAY) { 00526 FreeRsaKey(key); 00527 return err; 00528 } 00529 00530 return 0; 00531 } 00532 00533 00534 #endif /* CYASLS_KEY_GEN */ 00535
Generated on Tue Jul 12 2022 18:43:19 by 1.7.2