crypto/rsa/rsa_enc.c

   1 /* crypto/rsa/rsa_enc.c */
   2 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn.h"
  62 #include "rsa.h"
  63 #include "rand.h"
  64
  65 #ifndef NOPROTO
  66 static int RSA_eay_public_encrypt(int flen, unsigned char *from,
  67                 unsigned char *to, RSA *rsa,int padding);
  68 static int RSA_eay_private_encrypt(int flen, unsigned char *from,
  69                 unsigned char *to, RSA *rsa,int padding);
  70 static int RSA_eay_public_decrypt(int flen, unsigned char *from,
  71                 unsigned char *to, RSA *rsa,int padding);
  72 static int RSA_eay_private_decrypt(int flen, unsigned char *from,
  73                 unsigned char *to, RSA *rsa,int padding);
  74 static int RSA_eay_mod_exp(BIGNUM *r0, BIGNUM *i, RSA *rsa);
  75 #else
  76 static int RSA_eay_public_encrypt();
  77 static int RSA_eay_private_encrypt();
  78 static int RSA_eay_public_decrypt();
  79 static int RSA_eay_private_decrypt();
  80 static int RSA_eay_mod_exp();
  81 #endif
  82
  83 static RSA_METHOD rsa_pkcs1_eay_meth={
  84         "Eric Young's PKCS#1 RSA",
  85         RSA_eay_public_encrypt,
  86         RSA_eay_public_decrypt,
  87         RSA_eay_private_encrypt,
  88         RSA_eay_private_decrypt,
  89         RSA_eay_mod_exp,
  90         BN_mod_exp,
  91         NULL,
  92         NULL,
  93         };
  94
  95 RSA_METHOD *RSA_PKCS1_SSLeay()
  96         {
  97         return(&rsa_pkcs1_eay_meth);
  98         }
  99
 100 static int RSA_eay_public_encrypt(flen, from, to, rsa, padding)
 101 int flen;
 102 unsigned char *from;
 103 unsigned char *to;
 104 RSA *rsa;
 105 int padding;
 106         {
 107         BIGNUM *f=NULL,*ret=NULL;
 108         int i,j,k,num=0,r= -1;
 109         unsigned char *p;
 110         unsigned char *buf=NULL;
 111         BN_CTX *ctx=NULL;
 112
 113         if (    (padding != RSA_PKCS1_PADDING) &&
 114                 (padding != RSA_SSLV23_PADDING))
 115                 {
 116                 RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
 117                 goto err;
 118                 }
 119
 120         ctx=BN_CTX_new();
 121         if (ctx == NULL) goto err;
 122
 123         num=BN_num_bytes(rsa->n);
 124         if (flen > (num-11))
 125                 {
 126                 RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT,RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 127                 goto err;
 128                 }
 129
 130         buf=(unsigned char *)Malloc(num);
 131         if (buf == NULL)
 132                 {
 133                 RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT,ERR_R_MALLOC_FAILURE);
 134                 goto err;
 135                 }
 136         p=(unsigned char *)buf;
 137
 138         *(p++)=0;
 139         *(p++)=2; /* Public Key BT (Block Type) */
 140
 141         /* pad out with non-zero random data */
 142         j=num-3-flen;
 143
 144         RAND_bytes(p,j);
 145         for (i=0; i<j; i++)
 146                 {
 147                 if (*p == '\0')
 148                         do      {
 149                                 RAND_bytes(p,1);
 150                                 } while (*p == '\0');
 151                 p++;
 152                 }
 153
 154         if (padding == RSA_SSLV23_PADDING)
 155                 memset(&(p[-8]),3,8);
 156
 157         *(p++)='\0';
 158
 159         memcpy(p,from,(unsigned int)flen);
 160
 161         f=BN_new();
 162         ret=BN_new();
 163         if ((f == NULL) || (ret == NULL)) goto err;
 164
 165         if (BN_bin2bn(buf,num,f) == NULL) goto err;
 166         if (!rsa->meth->bn_mod_exp(ret,f,rsa->e,rsa->n,ctx)) goto err;
 167
 168         /* put in leading 0 bytes if the number is less than the
 169          * length of the modulus */
 170         j=BN_num_bytes(ret);
 171         i=BN_bn2bin(ret,&(to[num-j]));
 172         for (k=0; k<(num-i); k++)
 173                 to[k]=0;
 174
 175         r=num;
 176 err:
 177         if (ctx != NULL) BN_CTX_free(ctx);
 178         if (f != NULL) BN_free(f);
 179         if (ret != NULL) BN_free(ret);
 180         if (buf != NULL)
 181                 {
 182                 memset(buf,0,num);
 183                 Free(buf);
 184                 }
 185         return(r);
 186         }
 187
 188 static int RSA_eay_private_encrypt(flen, from, to, rsa, padding)
 189 int flen;
 190 unsigned char *from;
 191 unsigned char *to;
 192 RSA *rsa;
 193 int padding;
 194         {
 195         BIGNUM *f=NULL,*ret=NULL;
 196         int i,j,k,num=0,r= -1;
 197         unsigned char *p;
 198         unsigned char *buf=NULL;
 199         BN_CTX *ctx=NULL;
 200
 201         if (padding != RSA_PKCS1_PADDING)
 202                 {
 203                 RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
 204                 goto err;
 205                 }
 206
 207         ctx=BN_CTX_new();
 208         if (ctx == NULL) goto err;
 209
 210         num=BN_num_bytes(rsa->n);
 211         if (flen > (num-11))
 212                 {
 213                 RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 214                 goto err;
 215                 }
 216         buf=(unsigned char *)Malloc(num);
 217         if (buf == NULL)
 218                 {
 219                 RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,ERR_R_MALLOC_FAILURE);
 220                 goto err;
 221                 }
 222         p=buf;
 223
 224         *(p++)=0;
 225         *(p++)=1; /* Private Key BT (Block Type) */
 226
 227         /* padd out with 0xff data */
 228         j=num-3-flen;
 229         for (i=0; i<j; i++)
 230                 *(p++)=0xff;
 231         *(p++)='\0';
 232         memcpy(p,from,(unsigned int)flen);
 233         ret=BN_new();
 234         f=BN_new();
 235         if ((ret == NULL) || (f == NULL)) goto err;
 236         if (BN_bin2bn(buf,num,f) == NULL) goto err;
 237         if (    (rsa->p != NULL) &&
 238                 (rsa->q != NULL) &&
 239                 (rsa->dmp1 != NULL) &&
 240                 (rsa->dmq1 != NULL) &&
 241                 (rsa->iqmp != NULL))
 242                 { if (!rsa->meth->rsa_mod_exp(ret,f,rsa)) goto err; }
 243         else
 244                 { if (!rsa->meth->bn_mod_exp(ret,f,rsa->d,rsa->n,ctx)) goto err; }
 245
 246         p=buf;
 247         BN_bn2bin(ret,p);
 248
 249         /* put in leading 0 bytes if the number is less than the
 250          * length of the modulus */
 251         j=BN_num_bytes(ret);
 252         i=BN_bn2bin(ret,&(to[num-j]));
 253         for (k=0; k<(num-i); k++)
 254                 to[k]=0;
 255
 256         r=num;
 257 err:
 258         if (ctx != NULL) BN_CTX_free(ctx);
 259         if (ret != NULL) BN_free(ret);
 260         if (f != NULL) BN_free(f);
 261         if (buf != NULL)
 262                 {
 263                 memset(buf,0,num);
 264                 Free(buf);
 265                 }
 266         return(r);
 267         }
 268
 269 static int RSA_eay_private_decrypt(flen, from, to, rsa,padding)
 270 int flen;
 271 unsigned char *from;
 272 unsigned char *to;
 273 RSA *rsa;
 274 int padding;
 275         {
 276         BIGNUM *f=NULL,*ret=NULL;
 277         int i,j,num=0,r= -1;
 278         unsigned char *p;
 279         unsigned char *buf=NULL;
 280         BN_CTX *ctx=NULL;
 281
 282         if ((padding != RSA_PKCS1_PADDING) && (padding != RSA_SSLV23_PADDING))
 283                 {
 284                 RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
 285                 goto err;
 286                 }
 287
 288         ctx=BN_CTX_new();
 289         if (ctx == NULL) goto err;
 290
 291         num=BN_num_bytes(rsa->n);
 292
 293         buf=(unsigned char *)Malloc(num);
 294         if (buf == NULL)
 295                 {
 296                 RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,ERR_R_MALLOC_FAILURE);
 297                 goto err;
 298                 }
 299
 300         /* This check was for equallity but PGP does evil things
 301          * and chops off the top '0' bytes */
 302         if (flen > num)
 303                 {
 304                 RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
 305                 goto err;
 306                 }
 307
 308         /* make data into a big number */
 309         ret=BN_new();
 310         f=BN_new();
 311         if ((ret == NULL) || (f == NULL)) goto err;
 312         if (BN_bin2bn(from,(int)flen,f) == NULL) goto err;
 313         /* do the decrypt */
 314         if (    (rsa->p != NULL) &&
 315                 (rsa->q != NULL) &&
 316                 (rsa->dmp1 != NULL) &&
 317                 (rsa->dmq1 != NULL) &&
 318                 (rsa->iqmp != NULL))
 319                 { if (!rsa->meth->rsa_mod_exp(ret,f,rsa)) goto err; }
 320         else
 321                 { if (!rsa->meth->bn_mod_exp(ret,f,rsa->d,rsa->n,ctx)) goto err; }
 322
 323         p=buf;
 324         BN_bn2bin(ret,p);
 325
 326         /* BT must be 02 */
 327         if (*(p++) != 02)
 328                 {
 329                 RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_BLOCK_TYPE_IS_NOT_02);
 330                 goto err;
 331                 }
 332
 333         /* scan over padding data */
 334         j=num-2; /* one for type and one for the prepended 0. */
 335         for (i=0; i<j; i++)
 336                 if (*(p++) == 0) break;
 337
 338         if (i == j)
 339                 {
 340                 RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_NULL_BEFORE_BLOCK_MISSING);
 341                 goto err;
 342                 }
 343
 344         if (i < 8)
 345                 {
 346                 RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_BAD_PAD_BYTE_COUNT);
 347                 goto err;
 348                 }
 349
 350 #undef RSA_DEBUG
 351 #ifdef RSA_DEBUG
 352         {
 353         int z;
 354         unsigned char *q;
 355         q= &(p[-9]);
 356         fprintf(stderr,"\n");
 357         for (z=0; z<8; z++) fprintf(stderr,"%02X",q[z]);
 358         fprintf(stderr,"\n");
 359         }
 360 #endif
 361
 362         if (padding == RSA_SSLV23_PADDING)
 363                 {
 364                 int z;
 365                 unsigned char *q;
 366
 367                 /* -9 because we have jumped the '\0' */
 368                 q= &(p[-9]);
 369                 for (z=0; z<8; z++)
 370                         {
 371                         if (*(q++) != 0x03)
 372                                 break;
 373                         }
 374                 if (z == 8)
 375                         {
 376                         RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,RSA_R_SSLV3_ROLLBACK_ATTACK);
 377                         goto err;
 378                         }
 379                 }
 380
 381         /* skip over the '\0' */
 382         i++;
 383         j-=i;
 384
 385         /* output data */
 386         memcpy(to,p,(unsigned int)j);
 387         r=j;
 388 err:
 389         if (ctx != NULL) BN_CTX_free(ctx);
 390         if (f != NULL) BN_free(f);
 391         if (ret != NULL) BN_free(ret);
 392         if (buf != NULL)
 393                 {
 394                 memset(buf,0,num);
 395                 Free(buf);
 396                 }
 397         return(r);
 398         }
 399
 400 static int RSA_eay_public_decrypt(flen, from, to, rsa, padding)
 401 int flen;
 402 unsigned char *from;
 403 unsigned char *to;
 404 RSA *rsa;
 405 int padding;
 406         {
 407         BIGNUM *f=NULL,*ret=NULL;
 408         int i,j,num=0,r= -1;
 409         unsigned char *p;
 410         unsigned char *buf=NULL;
 411         BN_CTX *ctx=NULL;
 412
 413         if (padding != RSA_PKCS1_PADDING)
 414                 {
 415                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_UNKNOWN_PADDING_TYPE);
 416                 goto err;
 417                 }
 418
 419         ctx=BN_CTX_new();
 420         if (ctx == NULL) goto err;
 421
 422         num=BN_num_bytes(rsa->n);
 423         buf=(unsigned char *)Malloc(num);
 424         if (buf == NULL)
 425                 {
 426                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,ERR_R_MALLOC_FAILURE);
 427                 goto err;
 428                 }
 429
 430         /* This check was for equallity but PGP does evil things
 431          * and chops off the top '0' bytes */
 432         if (flen > num)
 433                 {
 434                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_DATA_GREATER_THAN_MOD_LEN);
 435                 goto err;
 436                 }
 437
 438         /* make data into a big number */
 439         f=BN_new();
 440         ret=BN_new();
 441         if ((f == NULL) || (ret == NULL)) goto err;
 442
 443         if (BN_bin2bn(from,flen,f) == NULL) goto err;
 444         /* do the decrypt */
 445         if (!rsa->meth->bn_mod_exp(ret,f,rsa->e,rsa->n,ctx)) goto err;
 446
 447         p=buf;
 448         i=BN_bn2bin(ret,p);
 449
 450         /* BT must be 01 */
 451         if (*(p++) != 01)
 452                 {
 453                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_BLOCK_TYPE_IS_NOT_01);
 454                 goto err;
 455                 }
 456
 457         /* scan over padding data */
 458         j=num-2; /* one for type and one for the prepended 0. */
 459         for (i=0; i<j; i++)
 460                 {
 461                 if (*p != 0xff) /* should decrypt to 0xff */
 462                         {
 463                         if (*p == 0)
 464                                 { p++; break; }
 465                         else    {
 466                                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_BAD_FIXED_HEADER_DECRYPT);
 467                                 goto err;
 468                                 }
 469                         }
 470                 p++;
 471                 }
 472         if (i == j)
 473                 {
 474                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_NULL_BEFORE_BLOCK_MISSING);
 475                 goto err;
 476                 }
 477         if (i < 8)
 478                 {
 479                 RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,RSA_R_BAD_PAD_BYTE_COUNT);
 480                 goto err;
 481                 }
 482
 483         /* skip over the '\0' */
 484         i++;
 485         j-=i;
 486
 487         /* output data */
 488         memcpy(to,p,(unsigned int)j);
 489         r=j;
 490 err:
 491         if (ctx != NULL) BN_CTX_free(ctx);
 492         if (f != NULL) BN_free(f);
 493         if (ret != NULL) BN_free(ret);
 494         if (buf != NULL)
 495                 {
 496                 memset(buf,0,num);
 497                 Free(buf);
 498                 }
 499         return(r);
 500         }
 501
 502 static int RSA_eay_mod_exp(r0, I, rsa)
 503 BIGNUM *r0;
 504 BIGNUM *I;
 505 RSA *rsa;
 506         {
 507         BIGNUM *r1=NULL,*m1=NULL;
 508         int ret=0;
 509         BN_CTX *ctx;
 510
 511         if ((ctx=BN_CTX_new()) == NULL) goto err;
 512         m1=BN_new();
 513         r1=BN_new();
 514         if ((m1 == NULL) || (r1 == NULL)) goto err;
 515
 516         if (!BN_mod(r1,I,rsa->q,ctx)) goto err;
 517         if (!rsa->meth->bn_mod_exp(m1,r1,rsa->dmq1,rsa->q,ctx)) goto err;
 518
 519         if (!BN_mod(r1,I,rsa->p,ctx)) goto err;
 520         if (!rsa->meth->bn_mod_exp(r0,r1,rsa->dmp1,rsa->p,ctx)) goto err;
 521
 522         if (!BN_add(r1,r0,rsa->p)) goto err;
 523         if (!BN_sub(r0,r1,m1)) goto err;
 524
 525         if (!BN_mul(r1,r0,rsa->iqmp)) goto err;
 526         if (!BN_mod(r0,r1,rsa->p,ctx)) goto err;
 527         if (!BN_mul(r1,r0,rsa->q)) goto err;
 528         if (!BN_add(r0,r1,m1)) goto err;
 529
 530         ret=1;
 531 err:
 532         if (m1 != NULL) BN_free(m1);
 533         if (r1 != NULL) BN_free(r1);
 534         BN_CTX_free(ctx);
 535         return(ret);
 536         }
 537
 538