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