git.sur5r.net Git - freertos/blob - FreeRTOS-Plus/CyaSSL/ctaocrypt/src/rsa.c

   1 /* rsa.c
   2  *
   3  * Copyright (C) 2006-2012 Sawtooth Consulting Ltd.
   4  *
   5  * This file is part of CyaSSL.
   6  *
   7  * CyaSSL is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * CyaSSL is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  20  */
  21
  22
  23 #ifdef HAVE_CONFIG_H
  24     #include <config.h>
  25 #endif
  26
  27 #include <cyassl/ctaocrypt/rsa.h>
  28 #include <cyassl/ctaocrypt/random.h>
  29 #include <cyassl/ctaocrypt/error.h>
  30 #include <cyassl/ctaocrypt/logging.h>
  31
  32 #ifdef SHOW_GEN
  33     #include <stdio.h>
  34 #endif
  35
  36
  37 enum {
  38     RSA_PUBLIC_ENCRYPT  = 0,
  39     RSA_PUBLIC_DECRYPT  = 1,
  40     RSA_PRIVATE_ENCRYPT = 2,
  41     RSA_PRIVATE_DECRYPT = 3,
  42
  43     RSA_BLOCK_TYPE_1 = 1,
  44     RSA_BLOCK_TYPE_2 = 2,
  45
  46     RSA_MIN_SIZE = 512,
  47     RSA_MAX_SIZE = 4096,
  48
  49     RSA_MIN_PAD_SZ   = 11      /* seperator + 0 + pad value + 8 pads */
  50 };
  51
  52
  53 void InitRsaKey(RsaKey* key, void* heap)
  54 {
  55     key->type = -1;  /* haven't decided yet */
  56     key->heap = heap;
  57
  58 /* TomsFastMath doesn't use memory allocation */
  59 #ifndef USE_FAST_MATH
  60     key->n.dp = key->e.dp = 0;  /* public  alloc parts */
  61
  62     key->d.dp = key->p.dp  = 0;  /* private alloc parts */
  63     key->q.dp = key->dP.dp = 0;
  64     key->u.dp = key->dQ.dp = 0;
  65 #endif
  66 }
  67
  68
  69 void FreeRsaKey(RsaKey* key)
  70 {
  71     (void)key;
  72 /* TomsFastMath doesn't use memory allocation */
  73 #ifndef USE_FAST_MATH
  74     if (key->type == RSA_PRIVATE) {
  75         mp_clear(&key->u);
  76         mp_clear(&key->dQ);
  77         mp_clear(&key->dP);
  78         mp_clear(&key->q);
  79         mp_clear(&key->p);
  80         mp_clear(&key->d);
  81     }
  82     mp_clear(&key->e);
  83     mp_clear(&key->n);
  84 #endif
  85 }
  86
  87 static void RsaPad(const byte* input, word32 inputLen, byte* pkcsBlock,
  88                    word32 pkcsBlockLen, byte padValue, RNG* rng)
  89 {
  90     if (inputLen == 0) return;
  91
  92     pkcsBlock[0] = 0x0;       /* set first byte to zero and advance */
  93     pkcsBlock++; pkcsBlockLen--;
  94     pkcsBlock[0] = padValue;  /* insert padValue */
  95
  96     if (padValue == RSA_BLOCK_TYPE_1)
  97         /* pad with 0xff bytes */
  98         XMEMSET(&pkcsBlock[1], 0xFF, pkcsBlockLen - inputLen - 2);
  99     else {
 100         /* pad with non-zero random bytes */
 101         word32 padLen = pkcsBlockLen - inputLen - 1, i;
 102         RNG_GenerateBlock(rng, &pkcsBlock[1], padLen);
 103
 104         /* remove zeros */
 105         for (i = 1; i < padLen; i++)
 106             if (pkcsBlock[i] == 0) pkcsBlock[i] = 0x01;
 107     }
 108
 109     pkcsBlock[pkcsBlockLen-inputLen-1] = 0;     /* separator */
 110     XMEMCPY(pkcsBlock+pkcsBlockLen-inputLen, input, inputLen);
 111 }
 112
 113
 114 static word32 RsaUnPad(const byte *pkcsBlock, unsigned int pkcsBlockLen,
 115                        byte **output, byte padValue)
 116 {
 117     word32 maxOutputLen = (pkcsBlockLen > 10) ? (pkcsBlockLen - 10) : 0,
 118            invalid = 0,
 119            i = 1,
 120            outputLen;
 121
 122     if (pkcsBlock[0] != 0x0) /* skip past zero */
 123         invalid = 1;
 124     pkcsBlock++; pkcsBlockLen--;
 125
 126     /* Require block type padValue */
 127     invalid = (pkcsBlock[0] != padValue) || invalid;
 128
 129     /* skip past the padding until we find the separator */
 130     while (i<pkcsBlockLen && pkcsBlock[i++]) { /* null body */
 131         }
 132     if(!(i==pkcsBlockLen || pkcsBlock[i-1]==0)) {
 133         CYASSL_MSG("RsaUnPad error, bad formatting");
 134         return 0;
 135     }
 136
 137     outputLen = pkcsBlockLen - i;
 138     invalid = (outputLen > maxOutputLen) || invalid;
 139
 140     if (invalid) {
 141         CYASSL_MSG("RsaUnPad error, bad formatting");
 142         return 0;
 143     }
 144
 145     *output = (byte *)(pkcsBlock + i);
 146     return outputLen;
 147 }
 148
 149
 150 static int RsaFunction(const byte* in, word32 inLen, byte* out, word32* outLen,
 151                        int type, RsaKey* key)
 152 {
 153     #define ERROR_OUT(x) { ret = x; goto done;}
 154
 155     mp_int tmp;
 156     int    ret = 0;
 157     word32 keyLen, len;
 158
 159     if (mp_init(&tmp) != MP_OKAY)
 160         return MP_INIT_E;
 161
 162     if (mp_read_unsigned_bin(&tmp, (byte*)in, inLen) != MP_OKAY)
 163         ERROR_OUT(MP_READ_E);
 164
 165     if (type == RSA_PRIVATE_DECRYPT || type == RSA_PRIVATE_ENCRYPT) {
 166         #ifdef RSA_LOW_MEM      /* half as much memory but twice as slow */
 167             if (mp_exptmod(&tmp, &key->d, &key->n, &tmp) != MP_OKAY)
 168                 ERROR_OUT(MP_EXPTMOD_E);
 169         #else
 170             #define INNER_ERROR_OUT(x) { ret = x; goto inner_done; }
 171
 172             mp_int tmpa, tmpb;
 173
 174             if (mp_init(&tmpa) != MP_OKAY)
 175                 ERROR_OUT(MP_INIT_E);
 176
 177             if (mp_init(&tmpb) != MP_OKAY) {
 178                 mp_clear(&tmpa);
 179                 ERROR_OUT(MP_INIT_E);
 180             }
 181
 182             /* tmpa = tmp^dP mod p */
 183             if (mp_exptmod(&tmp, &key->dP, &key->p, &tmpa) != MP_OKAY)
 184                 INNER_ERROR_OUT(MP_EXPTMOD_E);
 185
 186             /* tmpb = tmp^dQ mod q */
 187             if (mp_exptmod(&tmp, &key->dQ, &key->q, &tmpb) != MP_OKAY)
 188                 INNER_ERROR_OUT(MP_EXPTMOD_E);
 189
 190             /* tmp = (tmpa - tmpb) * qInv (mod p) */
 191             if (mp_sub(&tmpa, &tmpb, &tmp) != MP_OKAY)
 192                 INNER_ERROR_OUT(MP_SUB_E);
 193
 194             if (mp_mulmod(&tmp, &key->u, &key->p, &tmp) != MP_OKAY)
 195                 INNER_ERROR_OUT(MP_MULMOD_E);
 196
 197             /* tmp = tmpb + q * tmp */
 198             if (mp_mul(&tmp, &key->q, &tmp) != MP_OKAY)
 199                 INNER_ERROR_OUT(MP_MUL_E);
 200
 201             if (mp_add(&tmp, &tmpb, &tmp) != MP_OKAY)
 202                 INNER_ERROR_OUT(MP_ADD_E);
 203
 204         inner_done:
 205             mp_clear(&tmpa);
 206             mp_clear(&tmpb);
 207
 208             if (ret != 0) return ret;
 209
 210         #endif   /* RSA_LOW_MEM */
 211     }
 212     else if (type == RSA_PUBLIC_ENCRYPT || type == RSA_PUBLIC_DECRYPT) {
 213         if (mp_exptmod(&tmp, &key->e, &key->n, &tmp) != MP_OKAY)
 214             ERROR_OUT(MP_EXPTMOD_E);
 215     }
 216     else
 217         ERROR_OUT(RSA_WRONG_TYPE_E);
 218
 219     keyLen = mp_unsigned_bin_size(&key->n);
 220     if (keyLen > *outLen)
 221         ERROR_OUT(RSA_BUFFER_E);
 222
 223     len = mp_unsigned_bin_size(&tmp);
 224
 225     /* pad front w/ zeros to match key length */
 226     while (len < keyLen) {
 227         *out++ = 0x00;
 228         len++;
 229     }
 230
 231     *outLen = keyLen;
 232
 233     /* convert */
 234     if (mp_to_unsigned_bin(&tmp, out) != MP_OKAY)
 235         ERROR_OUT(MP_TO_E);
 236
 237 done:
 238     mp_clear(&tmp);
 239     return ret;
 240 }
 241
 242
 243 int RsaPublicEncrypt(const byte* in, word32 inLen, byte* out, word32 outLen,
 244                      RsaKey* key, RNG* rng)
 245 {
 246     int sz = mp_unsigned_bin_size(&key->n), ret;
 247
 248     if (sz > (int)outLen)
 249         return RSA_BUFFER_E;
 250
 251     if (inLen > (word32)(sz - RSA_MIN_PAD_SZ))
 252         return RSA_BUFFER_E;
 253
 254     RsaPad(in, inLen, out, sz, RSA_BLOCK_TYPE_2, rng);
 255
 256     if ((ret = RsaFunction(out, sz, out, &outLen, RSA_PUBLIC_ENCRYPT, key)) < 0)
 257         sz = ret;
 258
 259     return sz;
 260 }
 261
 262
 263 int RsaPrivateDecryptInline(byte* in, word32 inLen, byte** out, RsaKey* key)
 264 {
 265     int plainLen, ret;
 266
 267     if ((ret = RsaFunction(in, inLen, in, &inLen, RSA_PRIVATE_DECRYPT, key))
 268             < 0) {
 269         return ret;
 270     }
 271
 272     plainLen = RsaUnPad(in, inLen, out, RSA_BLOCK_TYPE_2);
 273
 274     return plainLen;
 275 }
 276
 277
 278 int RsaPrivateDecrypt(const byte* in, word32 inLen, byte* out, word32 outLen,
 279                      RsaKey* key)
 280 {
 281     int plainLen, ret;
 282     byte*  tmp;
 283     byte*  pad = 0;
 284
 285     tmp = (byte*)XMALLOC(inLen, key->heap, DYNAMIC_TYPE_RSA);
 286     if (tmp == NULL) {
 287         return MEMORY_E;
 288     }
 289
 290     XMEMCPY(tmp, in, inLen);
 291
 292     if ((ret = plainLen = RsaPrivateDecryptInline(tmp, inLen, &pad, key))
 293             < 0) {
 294         XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA);
 295         return ret;
 296     }
 297     if (plainLen > (int)outLen)
 298         plainLen = BAD_FUNC_ARG;
 299     else
 300         XMEMCPY(out, pad, plainLen);
 301     XMEMSET(tmp, 0x00, inLen);
 302
 303     XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA);
 304     return plainLen;
 305 }
 306
 307
 308 /* for Rsa Verify */
 309 int RsaSSL_VerifyInline(byte* in, word32 inLen, byte** out, RsaKey* key)
 310 {
 311     int plainLen, ret;
 312
 313     if ((ret = RsaFunction(in, inLen, in, &inLen, RSA_PUBLIC_DECRYPT, key))
 314             < 0) {
 315         return ret;
 316     }
 317
 318     plainLen = RsaUnPad(in, inLen, out, RSA_BLOCK_TYPE_1);
 319
 320     return plainLen;
 321 }
 322
 323
 324 int RsaSSL_Verify(const byte* in, word32 inLen, byte* out, word32 outLen,
 325                      RsaKey* key)
 326 {
 327     int plainLen, ret;
 328     byte*  tmp;
 329     byte*  pad = 0;
 330
 331     tmp = (byte*)XMALLOC(inLen, key->heap, DYNAMIC_TYPE_RSA);
 332     if (tmp == NULL) {
 333         return MEMORY_E;
 334     }
 335
 336     XMEMCPY(tmp, in, inLen);
 337
 338     if ((ret = plainLen = RsaSSL_VerifyInline(tmp, inLen, &pad, key))
 339             < 0) {
 340         XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA);
 341         return ret;
 342     }
 343
 344     if (plainLen > (int)outLen)
 345         plainLen = BAD_FUNC_ARG;
 346     else
 347         XMEMCPY(out, pad, plainLen);
 348     XMEMSET(tmp, 0x00, inLen);
 349
 350     XFREE(tmp, key->heap, DYNAMIC_TYPE_RSA);
 351     return plainLen;
 352 }
 353
 354
 355 /* for Rsa Sign */
 356 int RsaSSL_Sign(const byte* in, word32 inLen, byte* out, word32 outLen,
 357                       RsaKey* key, RNG* rng)
 358 {
 359     int sz = mp_unsigned_bin_size(&key->n), ret;
 360
 361     if (sz > (int)outLen)
 362         return RSA_BUFFER_E;
 363
 364     if (inLen > (word32)(sz - RSA_MIN_PAD_SZ))
 365         return RSA_BUFFER_E;
 366
 367     RsaPad(in, inLen, out, sz, RSA_BLOCK_TYPE_1, rng);
 368
 369     if ((ret = RsaFunction(out, sz, out, &outLen, RSA_PRIVATE_ENCRYPT,key)) < 0)
 370         sz = ret;
 371
 372     return sz;
 373 }
 374
 375
 376 int RsaEncryptSize(RsaKey* key)
 377 {
 378     return mp_unsigned_bin_size(&key->n);
 379 }
 380
 381
 382 #ifdef CYASSL_KEY_GEN
 383
 384 static const int USE_BBS = 1;
 385
 386 static int rand_prime(mp_int* N, int len, RNG* rng, void* heap)
 387 {
 388     int   err, res, type;
 389     byte* buf;
 390
 391     (void)heap;
 392     if (N == NULL || rng == NULL)
 393        return BAD_FUNC_ARG;
 394
 395     /* get type */
 396     if (len < 0) {
 397         type = USE_BBS;
 398         len = -len;
 399     } else {
 400         type = 0;
 401     }
 402
 403     /* allow sizes between 2 and 512 bytes for a prime size */
 404     if (len < 2 || len > 512) {
 405         return BAD_FUNC_ARG;
 406     }
 407
 408     /* allocate buffer to work with */
 409     buf = (byte*)XMALLOC(len, heap, DYNAMIC_TYPE_RSA);
 410     if (buf == NULL) {
 411         return MEMORY_E;
 412     }
 413     XMEMSET(buf, 0, len);
 414
 415     do {
 416 #ifdef SHOW_GEN
 417         printf(".");
 418         fflush(stdout);
 419 #endif
 420         /* generate value */
 421         RNG_GenerateBlock(rng, buf, len);
 422
 423         /* munge bits */
 424         buf[0]     |= 0x80 | 0x40;
 425         buf[len-1] |= 0x01 | ((type & USE_BBS) ? 0x02 : 0x00);
 426
 427         /* load value */
 428         if ((err = mp_read_unsigned_bin(N, buf, len)) != MP_OKAY) {
 429             XFREE(buf, heap, DYNAMIC_TYPE_RSA);
 430             return err;
 431         }
 432
 433         /* test */
 434         if ((err = mp_prime_is_prime(N, 8, &res)) != MP_OKAY) {
 435             XFREE(buf, heap, DYNAMIC_TYPE_RSA);
 436             return err;
 437         }
 438     } while (res == MP_NO);
 439
 440 #ifdef LTC_CLEAN_STACK
 441     XMEMSET(buf, 0, len);
 442 #endif
 443
 444     XFREE(buf, heap, DYNAMIC_TYPE_RSA);
 445     return 0;
 446 }
 447
 448
 449 /* Make an RSA key for size bits, with e specified, 65537 is a good e */
 450 int MakeRsaKey(RsaKey* key, int size, long e, RNG* rng)
 451 {
 452     mp_int p, q, tmp1, tmp2, tmp3;
 453     int    err;
 454
 455     if (key == NULL || rng == NULL)
 456         return BAD_FUNC_ARG;
 457
 458     if (size < RSA_MIN_SIZE || size > RSA_MAX_SIZE)
 459         return BAD_FUNC_ARG;
 460
 461     if (e < 3 || (e & 1) == 0)
 462         return BAD_FUNC_ARG;
 463
 464     if ((err = mp_init_multi(&p, &q, &tmp1, &tmp2, &tmp3, NULL)) != MP_OKAY)
 465         return err;
 466
 467     err = mp_set_int(&tmp3, e);
 468
 469     /* make p */
 470     if (err == MP_OKAY) {
 471         do {
 472             err = rand_prime(&p, size/16, rng, key->heap); /* size in bytes/2 */
 473
 474             if (err == MP_OKAY)
 475                 err = mp_sub_d(&p, 1, &tmp1);  /* tmp1 = p-1 */
 476
 477             if (err == MP_OKAY)
 478                 err = mp_gcd(&tmp1, &tmp3, &tmp2);  /* tmp2 = gcd(p-1, e) */
 479         } while (err == MP_OKAY && mp_cmp_d(&tmp2, 1) != 0);  /* e divdes p-1 */
 480     }
 481
 482     /* make q */
 483     if (err == MP_OKAY) {
 484         do {
 485             err = rand_prime(&q, size/16, rng, key->heap); /* size in bytes/2 */
 486
 487             if (err == MP_OKAY)
 488                 err = mp_sub_d(&q, 1, &tmp1);  /* tmp1 = q-1 */
 489
 490             if (err == MP_OKAY)
 491                 err = mp_gcd(&tmp1, &tmp3, &tmp2);  /* tmp2 = gcd(q-1, e) */
 492         } while (err == MP_OKAY && mp_cmp_d(&tmp2, 1) != 0);  /* e divdes q-1 */
 493     }
 494
 495     if (err == MP_OKAY)
 496         err = mp_init_multi(&key->n, &key->e, &key->d, &key->p, &key->q, NULL);
 497
 498     if (err == MP_OKAY)
 499         err = mp_init_multi(&key->dP, &key->dP, &key->u, NULL, NULL, NULL);
 500
 501     if (err == MP_OKAY)
 502         err = mp_sub_d(&p, 1, &tmp2);  /* tmp2 = p-1 */
 503
 504     if (err == MP_OKAY)
 505         err = mp_lcm(&tmp1, &tmp2, &tmp1);  /* tmp1 = lcm(p-1, q-1),last loop */
 506
 507     /* make key */
 508     if (err == MP_OKAY)
 509         err = mp_set_int(&key->e, e);  /* key->e = e */
 510
 511     if (err == MP_OKAY)                /* key->d = 1/e mod lcm(p-1, q-1) */
 512         err = mp_invmod(&key->e, &tmp1, &key->d);
 513
 514     if (err == MP_OKAY)
 515         err = mp_mul(&p, &q, &key->n);  /* key->n = pq */
 516
 517     if (err == MP_OKAY)
 518         err = mp_sub_d(&p, 1, &tmp1);
 519
 520     if (err == MP_OKAY)
 521         err = mp_sub_d(&q, 1, &tmp2);
 522
 523     if (err == MP_OKAY)
 524         err = mp_mod(&key->d, &tmp1, &key->dP);
 525
 526     if (err == MP_OKAY)
 527         err = mp_mod(&key->d, &tmp2, &key->dQ);
 528
 529     if (err == MP_OKAY)
 530         err = mp_invmod(&q, &p, &key->u);
 531
 532     if (err == MP_OKAY)
 533         err = mp_copy(&p, &key->p);
 534
 535     if (err == MP_OKAY)
 536         err = mp_copy(&q, &key->q);
 537
 538     if (err == MP_OKAY)
 539         key->type = RSA_PRIVATE;
 540
 541     mp_clear(&tmp3);
 542     mp_clear(&tmp2);
 543     mp_clear(&tmp1);
 544     mp_clear(&q);
 545     mp_clear(&p);
 546
 547     if (err != MP_OKAY) {
 548         FreeRsaKey(key);
 549         return err;
 550     }
 551
 552     return 0;
 553 }
 554
 555
 556 #endif /* CYASLS_KEY_GEN */
 557