_ Git - BoarSSL/blob - Crypto/RSA.cs

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 using System;
  26
  27 namespace Crypto {
  28
  29 /*
  30  * This class implements the RSA encryption and signature algorithms.
  31  * The static methods provide access to the algorithm primitives. For
  32  * signatures, the hash of the signed data must be provided externally.
  33  */
  34
  35 public static class RSA {
  36
  37         /*
  38          * Get the maximum length (in bytes) of an RSA-encrypted value
  39          * with the specified public key.
  40          */
  41         public static int GetMaxEncryptedLength(RSAPublicKey pk)
  42         {
  43                 return pk.Modulus.Length;
  44         }
  45
  46         /*
  47          * Encrypt a message with a public key. This applied PKCS#1 v1.5
  48          * "type 2" padding. If the message length exceeds the maximum
  49          * that can be processed with that public key, an exception is
  50          * thrown.
  51          *
  52          * There are four methods, depending on the kind of source
  53          * operand, and how the destination is to be obtained.
  54          */
  55
  56         public static byte[] Encrypt(RSAPublicKey pk, byte[] buf)
  57         {
  58                 return Encrypt(pk, buf, 0, buf.Length);
  59         }
  60
  61         public static byte[] Encrypt(RSAPublicKey pk,
  62                 byte[] buf, int off, int len)
  63         {
  64                 byte[] n = pk.Modulus;
  65                 int modLen = n.Length;
  66                 byte[] x = DoPKCS1Padding(modLen, true, null, buf, off, len);
  67                 return BigInt.ModPow(x, pk.Exponent, n);
  68         }
  69
  70         public static int Encrypt(RSAPublicKey pk,
  71                 byte[] buf, byte[] outBuf, int outOff)
  72         {
  73                 return Encrypt(pk, buf, 0, buf.Length, outBuf, outOff);
  74         }
  75
  76         public static int Encrypt(RSAPublicKey pk,
  77                 byte[] buf, int off, int len, byte[] outBuf, int outOff)
  78         {
  79                 byte[] r = Encrypt(pk, buf, off, len);
  80                 Array.Copy(r, 0, outBuf, outOff, r.Length);
  81                 return r.Length;
  82         }
  83
  84         /*
  85          * Perform a RSA decryption. A PKCS#1 v1.5 "type 2" padding is
  86          * expected, and removed. An exception is thrown on any error.
  87          *
  88          * WARNING: potentially vulnerable to Bleichenbacher's attack.
  89          * Use with care.
  90          *
  91          * There are four methods, depending on input and output
  92          * operands.
  93          */
  94         public static byte[] Decrypt(RSAPrivateKey sk, byte[] buf)
  95         {
  96                 return Decrypt(sk, buf, 0, buf.Length);
  97         }
  98
  99         public static byte[] Decrypt(RSAPrivateKey sk,
 100                 byte[] buf, int off, int len)
 101         {
 102                 byte[] tmp = new byte[sk.N.Length];
 103                 int outLen = Decrypt(sk, buf, off, len, tmp, 0);
 104                 byte[] outBuf = new byte[outLen];
 105                 Array.Copy(tmp, 0, outBuf, 0, outLen);
 106                 return outBuf;
 107         }
 108
 109         public static int Decrypt(RSAPrivateKey sk,
 110                 byte[] buf, byte[] outBuf, int outOff)
 111         {
 112                 return Decrypt(sk, buf, 0, buf.Length, outBuf, outOff);
 113         }
 114
 115         public static int Decrypt(RSAPrivateKey sk,
 116                 byte[] buf, int off, int len, byte[] outBuf, int outOff)
 117         {
 118                 if (len != sk.N.Length) {
 119                         throw new CryptoException(
 120                                 "Invalid RSA-encrypted message length");
 121                 }
 122
 123                 /*
 124                  * Note: since RSAPrivateKey refuses a modulus of less
 125                  * than 64 bytes, we know that len >= 64 here.
 126                  */
 127                 byte[] x = new byte[len];
 128                 Array.Copy(buf, off, x, 0, len);
 129                 DoPrivate(sk, x);
 130                 if (x[0] != 0x00 || x[1] != 0x02) {
 131                         throw new CryptoException(
 132                                 "Invalid PKCS#1 v1.5 encryption padding");
 133                 }
 134                 int i;
 135                 for (i = 2; i < len && x[i] != 0x00; i ++);
 136                 if (i < 10 || i >= len) {
 137                         throw new CryptoException(
 138                                 "Invalid PKCS#1 v1.5 encryption padding");
 139                 }
 140                 i ++;
 141                 int olen = len - i;
 142                 Array.Copy(x, i, outBuf, outOff, olen);
 143                 return olen;
 144         }
 145
 146         /*
 147          * Perform a RSA private key operation (modular exponentiation
 148          * with the private exponent). The source array MUST have the
 149          * same length as the modulus, and it is modified "in place".
 150          *
 151          * This function is constant-time, except if the source x[] does
 152          * not have the proper length (it should be identical to the
 153          * modulus length). If the source array has the proper length
 154          * but the numerical value is not in the proper range, then it
 155          * is first reduced modulo N.
 156          */
 157         public static void DoPrivate(RSAPrivateKey sk, byte[] x)
 158         {
 159                 DoPrivate(sk, x, 0, x.Length);
 160         }
 161
 162         public static void DoPrivate(RSAPrivateKey sk,
 163                 byte[] x, int off, int len)
 164         {
 165                 /*
 166                  * Check that the source array has the proper length
 167                  * (identical to the length of the modulus).
 168                  */
 169                 if (len != sk.N.Length) {
 170                         throw new CryptoException(
 171                                 "Invalid source length for RSA private");
 172                 }
 173
 174                 /*
 175                  * Reduce the source value to the proper range.
 176                  */
 177                 ModInt mx = new ModInt(sk.N);
 178                 mx.DecodeReduce(x, off, len);
 179
 180                 /*
 181                  * Compute m1 = x^dp mod p.
 182                  */
 183                 ModInt m1 = new ModInt(sk.P);
 184                 m1.Set(mx);
 185                 m1.Pow(sk.DP);
 186
 187                 /*
 188                  * Compute m2 = x^dq mod q.
 189                  */
 190                 ModInt m2 = new ModInt(sk.Q);
 191                 m2.Set(mx);
 192                 m2.Pow(sk.DQ);
 193
 194                 /*
 195                  * Compute h = (m1 - m2) / q mod p.
 196                  * (Result goes in m1.)
 197                  */
 198                 ModInt m3 = m1.Dup();
 199                 m3.Set(m2);
 200                 m1.Sub(m3);
 201                 m3.Decode(sk.IQ);
 202                 m1.ToMonty();
 203                 m1.MontyMul(m3);
 204
 205                 /*
 206                  * Compute m_2 + q*h. This works on plain integers, but
 207                  * we have efficient and constant-time code for modular
 208                  * integers, so we will do it modulo n.
 209                  */
 210                 m3 = mx;
 211                 m3.Set(m1);
 212                 m1 = m3.Dup();
 213                 m1.Decode(sk.Q);
 214                 m1.ToMonty();
 215                 m3.MontyMul(m1);
 216                 m1.Set(m2);
 217                 m3.Add(m1);
 218
 219                 /*
 220                  * Write result back in x[].
 221                  */
 222                 m3.Encode(x, off, len);
 223         }
 224
 225         /*
 226          * Constant headers for PKCS#1 v1.5 "type 1" padding. There are
 227          * two versions for each header, because of the PKCS#1 ambiguity
 228          * with regards to hash function parameters (ASN.1 NULL value,
 229          * or omitted).
 230          */
 231
 232         // PKCS#1 with no explicit digest function (special for SSL/TLS)
 233         public static byte[] PKCS1_ND = new byte[] { };
 234
 235         // PKCS#1 with MD5
 236         public static byte[] PKCS1_MD5 = new byte[] {
 237                 0x30, 0x20, 0x30, 0x0C, 0x06, 0x08, 0x2A, 0x86,
 238                 0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, 0x05, 0x00,
 239                 0x04, 0x10
 240         };
 241
 242         // PKCS#1 with MD5 (alt)
 243         public static byte[] PKCS1_MD5_ALT = new byte[] {
 244                 0x30, 0x1E, 0x30, 0x0A, 0x06, 0x08, 0x2A, 0x86,
 245                 0x48, 0x86, 0xF7, 0x0D, 0x02, 0x05, 0x04, 0x10
 246         };
 247
 248         // PKCS#1 with SHA-1
 249         public static byte[] PKCS1_SHA1 = new byte[] {
 250                 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B, 0x0E,
 251                 0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14
 252         };
 253
 254         // PKCS#1 with SHA-1 (alt)
 255         public static byte[] PKCS1_SHA1_ALT = new byte[] {
 256                 0x30, 0x1F, 0x30, 0x07, 0x06, 0x05, 0x2B, 0x0E,
 257                 0x03, 0x02, 0x1A, 0x04, 0x14
 258         };
 259
 260         // PKCS#1 with SHA-224
 261         public static byte[] PKCS1_SHA224 = new byte[] {
 262                 0x30, 0x2D, 0x30, 0x0D, 0x06, 0x09, 0x60, 0x86,
 263                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x05,
 264                 0x00, 0x04, 0x1C
 265         };
 266
 267         // PKCS#1 with SHA-224 (alt)
 268         public static byte[] PKCS1_SHA224_ALT = new byte[] {
 269                 0x30, 0x2B, 0x30, 0x0B, 0x06, 0x09, 0x60, 0x86,
 270                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x04,
 271                 0x1C
 272         };
 273
 274         // PKCS#1 with SHA-256
 275         public static byte[] PKCS1_SHA256 = new byte[] {
 276                 0x30, 0x31, 0x30, 0x0D, 0x06, 0x09, 0x60, 0x86,
 277                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05,
 278                 0x00, 0x04, 0x20
 279         };
 280
 281         // PKCS#1 with SHA-256 (alt)
 282         public static byte[] PKCS1_SHA256_ALT = new byte[] {
 283                 0x30, 0x2F, 0x30, 0x0B, 0x06, 0x09, 0x60, 0x86,
 284                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x04,
 285                 0x20
 286         };
 287
 288         // PKCS#1 with SHA-384
 289         public static byte[] PKCS1_SHA384 = new byte[] {
 290                 0x30, 0x41, 0x30, 0x0D, 0x06, 0x09, 0x60, 0x86,
 291                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05,
 292                 0x00, 0x04, 0x30
 293         };
 294
 295         // PKCS#1 with SHA-384 (alt)
 296         public static byte[] PKCS1_SHA384_ALT = new byte[] {
 297                 0x30, 0x3F, 0x30, 0x0B, 0x06, 0x09, 0x60, 0x86,
 298                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x04,
 299                 0x30
 300         };
 301
 302         // PKCS#1 with SHA-512
 303         public static byte[] PKCS1_SHA512 = new byte[] {
 304                 0x30, 0x51, 0x30, 0x0D, 0x06, 0x09, 0x60, 0x86,
 305                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05,
 306                 0x00, 0x04, 0x40
 307         };
 308
 309         // PKCS#1 with SHA-512 (alt)
 310         public static byte[] PKCS1_SHA512_ALT = new byte[] {
 311                 0x30, 0x4F, 0x30, 0x0B, 0x06, 0x09, 0x60, 0x86,
 312                 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x04,
 313                 0x40
 314         };
 315
 316         /*
 317          * Verify an "ND" signature (no digest header: this is for
 318          * signatures in SSL/TLS up to TLS-1.1). The hash value
 319          * (normally the 36-byte concatenation of MD5 and SHA-1 in
 320          * the case of SSL/TLS) and the signature are provided.
 321          * Returned value is true on success, false otherwise. No
 322          * exception is thrown even if the public key is invalid.
 323          */
 324
 325         public static bool VerifyND(RSAPublicKey pk,
 326                 byte[] hash, byte[] sig)
 327         {
 328                 return Verify(pk, PKCS1_ND, null,
 329                         hash, 0, hash.Length,
 330                         sig, 0, sig.Length);
 331         }
 332
 333         public static bool VerifyND(RSAPublicKey pk,
 334                 byte[] hash, int hashOff, int hashLen, byte[] sig)
 335         {
 336                 return Verify(pk, PKCS1_ND, null,
 337                         hash, hashOff, hashLen,
 338                         sig, 0, sig.Length);
 339         }
 340
 341         public static bool VerifyND(RSAPublicKey pk,
 342                 byte[] hash, byte[] sig, int sigOff, int sigLen)
 343         {
 344                 return Verify(pk, PKCS1_ND, null,
 345                         hash, 0, hash.Length,
 346                         sig, sigOff, sigLen);
 347         }
 348
 349         public static bool VerifyND(RSAPublicKey pk,
 350                 byte[] hash, int hashOff, int hashLen,
 351                 byte[] sig, int sigOff, int sigLen)
 352         {
 353                 return Verify(pk, PKCS1_ND, null,
 354                         hash, hashOff, hashLen,
 355                         sig, sigOff, sigLen);
 356         }
 357
 358         /*
 359          * Verify a RSA signature, with PKCS#1 v1.5 "type 1" padding.
 360          * The digest header, digest alternative header, hashed data,
 361          * and signature value are provided. On any error (including
 362          * an invalid RSA public key), false is returned.
 363          *
 364          * If 'headerAlt' is null, then the signature MUST use the
 365          * header value provided in 'header'. Otherwise, the signature
 366          * MUST use either 'header' or 'headerAlt'.
 367          */
 368
 369         public static bool Verify(RSAPublicKey pk,
 370                 byte[] header, byte[] headerAlt,
 371                 byte[] hash, byte[] sig)
 372         {
 373                 return Verify(pk, header, headerAlt,
 374                         hash, 0, hash.Length,
 375                         sig, 0, sig.Length);
 376         }
 377
 378         public static bool Verify(RSAPublicKey pk,
 379                 byte[] header, byte[] headerAlt,
 380                 byte[] hash, int hashOff, int hashLen, byte[] sig)
 381         {
 382                 return Verify(pk, header, headerAlt,
 383                         hash, hashOff, hashLen,
 384                         sig, 0, sig.Length);
 385         }
 386
 387         public static bool Verify(RSAPublicKey pk,
 388                 byte[] header, byte[] headerAlt,
 389                 byte[] hash, byte[] sig, int sigOff, int sigLen)
 390         {
 391                 return Verify(pk, header, headerAlt,
 392                         hash, 0, hash.Length,
 393                         sig, sigOff, sigLen);
 394         }
 395
 396         public static bool Verify(RSAPublicKey pk,
 397                 byte[] header, byte[] headerAlt,
 398                 byte[] hash, int hashOff, int hashLen,
 399                 byte[] sig, int sigOff, int sigLen)
 400         {
 401                 /*
 402                  * Signature must be an integer less than the modulus,
 403                  * but encoded over exactly the same size as the modulus.
 404                  */
 405                 byte[] n = pk.Modulus;
 406                 int modLen = n.Length;
 407                 if (sigLen != modLen) {
 408                         return false;
 409                 }
 410                 byte[] x = new byte[modLen];
 411                 Array.Copy(sig, sigOff, x, 0, modLen);
 412                 if (BigInt.Compare(x, n) >= 0) {
 413                         return false;
 414                 }
 415
 416                 /*
 417                  * Do the RSA exponentation, then verify and remove the
 418                  * "Type 1" padding (00 01 FF...FF 00 with at least
 419                  * eight bytes of value FF).
 420                  */
 421                 x = BigInt.ModPow(x, pk.Exponent, n);
 422                 if (x.Length < 11 || x[0] != 0x00 || x[1] != 0x01) {
 423                         return false;
 424                 }
 425                 int k = 2;
 426                 while (k < x.Length && x[k] == 0xFF) {
 427                         k ++;
 428                 }
 429                 if (k < 10 || k == x.Length || x[k] != 0x00) {
 430                         return false;
 431                 }
 432                 k ++;
 433
 434                 /*
 435                  * Check that the remaining byte end with the provided
 436                  * hash value.
 437                  */
 438                 int len = modLen - k;
 439                 if (len < hashLen) {
 440                         return false;
 441                 }
 442                 for (int i = 0; i < hashLen; i ++) {
 443                         if (x[modLen - hashLen + i] != hash[hashOff + i]) {
 444                                 return false;
 445                         }
 446                 }
 447                 len -= hashLen;
 448
 449                 /*
 450                  * Header is at offset 'k', and length 'len'. Compare
 451                  * with the provided header(s).
 452                  */
 453                 if (Eq(header, 0, header.Length, x, k, len)) {
 454                         return true;
 455                 }
 456                 if (headerAlt != null) {
 457                         if (Eq(headerAlt, 0, headerAlt.Length, x, k, len)) {
 458                                 return true;
 459                         }
 460                 }
 461                 return false;
 462         }
 463
 464         /*
 465          * Compute a RSA signature (PKCS#1 v1.5 "type 1" padding).
 466          * The digest header and the hashed data are provided. The
 467          * header should be one of the standard PKCS#1 header; it
 468          * may also be an empty array or null for a "ND" signature
 469          * (this is normally used only in SSL/TLS up to TLS-1.1).
 470          */
 471
 472         public static byte[] Sign(RSAPrivateKey sk, byte[] header,
 473                 byte[] hash)
 474         {
 475                 return Sign(sk, header, hash, 0, hash.Length);
 476         }
 477
 478         public static byte[] Sign(RSAPrivateKey sk, byte[] header,
 479                 byte[] hash, int hashOff, int hashLen)
 480         {
 481                 byte[] sig = new byte[sk.N.Length];
 482                 Sign(sk, header, hash, hashOff, hashLen, sig, 0);
 483                 return sig;
 484         }
 485
 486         public static int Sign(RSAPrivateKey sk, byte[] header,
 487                 byte[] hash, byte[] outBuf, int outOff)
 488         {
 489                 return Sign(sk, header, hash, 0, hash.Length, outBuf, outOff);
 490         }
 491
 492         public static int Sign(RSAPrivateKey sk, byte[] header,
 493                 byte[] hash, int hashOff, int hashLen,
 494                 byte[] outBuf, int outOff)
 495         {
 496                 int modLen = sk.N.Length;
 497                 byte[] x = DoPKCS1Padding(modLen, false,
 498                         header, hash, hashOff, hashLen);
 499                 DoPrivate(sk, x);
 500                 Array.Copy(x, 0, outBuf, outOff, x.Length);
 501                 return x.Length;
 502         }
 503
 504         /*
 505          * Apply PKCS#1 v1.5 padding. The data to pad is the concatenation
 506          * of head[] and the chunk of val[] beginning at valOff and of
 507          * length valLen. If 'head' is null, then an empty array is used.
 508          *
 509          * The returned array has length modLen (the modulus size, in bytes).
 510          * Padding type 2 (random bytes, for encryption) is used if type2
 511          * is true; otherwise, padding type 1 is applied (bytes 0xFF, for
 512          * signatures).
 513          */
 514         public static byte[] DoPKCS1Padding(int modLen, bool type2,
 515                 byte[] head, byte[] val, int valOff, int valLen)
 516         {
 517                 if (head == null) {
 518                         head = PKCS1_ND;
 519                 }
 520                 int len = head.Length + valLen;
 521                 int padLen = modLen - len - 3;
 522                 if (padLen < 8) {
 523                         throw new Exception(
 524                                 "modulus too short for PKCS#1 padding");
 525                 }
 526                 byte[] x = new byte[modLen];
 527                 x[0] = 0x00;
 528                 x[1] = (byte)(type2 ? 0x02 : 0x01);
 529                 if (type2) {
 530                         RNG.GetBytesNonZero(x, 2, padLen);
 531                 } else {
 532                         for (int i = 0; i < padLen; i ++) {
 533                                 x[i + 2] = 0xFF;
 534                         }
 535                 }
 536                 x[padLen + 2] = 0x00;
 537                 Array.Copy(head, 0, x, padLen + 3, head.Length);
 538                 Array.Copy(val, valOff, x, modLen - valLen, valLen);
 539                 return x;
 540         }
 541
 542         /*
 543          * Compare two byte chunks for equality.
 544          */
 545         static bool Eq(byte[] a, int aoff, int alen,
 546                 byte[] b, int boff, int blen)
 547         {
 548                 if (alen != blen) {
 549                         return false;
 550                 }
 551                 for (int i = 0; i < alen; i ++) {
 552                         if (a[aoff + i] != b[boff + i]) {
 553                                 return false;
 554                         }
 555                 }
 556                 return true;
 557         }
 558 }
 559
 560 }