2 * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
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:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
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
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.
35 public static class RSA {
38 * Get the maximum length (in bytes) of an RSA-encrypted value
39 * with the specified public key.
41 public static int GetMaxEncryptedLength(RSAPublicKey pk)
43 return pk.Modulus.Length;
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
52 * There are four methods, depending on the kind of source
53 * operand, and how the destination is to be obtained.
56 public static byte[] Encrypt(RSAPublicKey pk, byte[] buf)
58 return Encrypt(pk, buf, 0, buf.Length);
61 public static byte[] Encrypt(RSAPublicKey pk,
62 byte[] buf, int off, int len)
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);
70 public static int Encrypt(RSAPublicKey pk,
71 byte[] buf, byte[] outBuf, int outOff)
73 return Encrypt(pk, buf, 0, buf.Length, outBuf, outOff);
76 public static int Encrypt(RSAPublicKey pk,
77 byte[] buf, int off, int len, byte[] outBuf, int outOff)
79 byte[] r = Encrypt(pk, buf, off, len);
80 Array.Copy(r, 0, outBuf, outOff, r.Length);
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.
88 * WARNING: potentially vulnerable to Bleichenbacher's attack.
91 * There are four methods, depending on input and output
94 public static byte[] Decrypt(RSAPrivateKey sk, byte[] buf)
96 return Decrypt(sk, buf, 0, buf.Length);
99 public static byte[] Decrypt(RSAPrivateKey sk,
100 byte[] buf, int off, int len)
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);
109 public static int Decrypt(RSAPrivateKey sk,
110 byte[] buf, byte[] outBuf, int outOff)
112 return Decrypt(sk, buf, 0, buf.Length, outBuf, outOff);
115 public static int Decrypt(RSAPrivateKey sk,
116 byte[] buf, int off, int len, byte[] outBuf, int outOff)
118 if (len != sk.N.Length) {
119 throw new CryptoException(
120 "Invalid RSA-encrypted message length");
124 * Note: since RSAPrivateKey refuses a modulus of less
125 * than 64 bytes, we know that len >= 64 here.
127 byte[] x = new byte[len];
128 Array.Copy(buf, off, x, 0, len);
130 if (x[0] != 0x00 || x[1] != 0x02) {
131 throw new CryptoException(
132 "Invalid PKCS#1 v1.5 encryption padding");
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");
142 Array.Copy(x, i, outBuf, outOff, olen);
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".
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.
157 public static void DoPrivate(RSAPrivateKey sk, byte[] x)
159 DoPrivate(sk, x, 0, x.Length);
162 public static void DoPrivate(RSAPrivateKey sk,
163 byte[] x, int off, int len)
166 * Check that the source array has the proper length
167 * (identical to the length of the modulus).
169 if (len != sk.N.Length) {
170 throw new CryptoException(
171 "Invalid source length for RSA private");
175 * Reduce the source value to the proper range.
177 ModInt mx = new ModInt(sk.N);
178 mx.DecodeReduce(x, off, len);
181 * Compute m1 = x^dp mod p.
183 ModInt m1 = new ModInt(sk.P);
188 * Compute m2 = x^dq mod q.
190 ModInt m2 = new ModInt(sk.Q);
195 * Compute h = (m1 - m2) / q mod p.
196 * (Result goes in m1.)
198 ModInt m3 = m1.Dup();
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.
220 * Write result back in x[].
222 m3.Encode(x, off, len);
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,
232 // PKCS#1 with no explicit digest function (special for SSL/TLS)
233 public static byte[] PKCS1_ND = new byte[] { };
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,
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
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
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
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,
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,
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,
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,
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,
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,
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,
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,
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.
325 public static bool VerifyND(RSAPublicKey pk,
326 byte[] hash, byte[] sig)
328 return Verify(pk, PKCS1_ND, null,
329 hash, 0, hash.Length,
333 public static bool VerifyND(RSAPublicKey pk,
334 byte[] hash, int hashOff, int hashLen, byte[] sig)
336 return Verify(pk, PKCS1_ND, null,
337 hash, hashOff, hashLen,
341 public static bool VerifyND(RSAPublicKey pk,
342 byte[] hash, byte[] sig, int sigOff, int sigLen)
344 return Verify(pk, PKCS1_ND, null,
345 hash, 0, hash.Length,
346 sig, sigOff, sigLen);
349 public static bool VerifyND(RSAPublicKey pk,
350 byte[] hash, int hashOff, int hashLen,
351 byte[] sig, int sigOff, int sigLen)
353 return Verify(pk, PKCS1_ND, null,
354 hash, hashOff, hashLen,
355 sig, sigOff, sigLen);
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.
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'.
369 public static bool Verify(RSAPublicKey pk,
370 byte[] header, byte[] headerAlt,
371 byte[] hash, byte[] sig)
373 return Verify(pk, header, headerAlt,
374 hash, 0, hash.Length,
378 public static bool Verify(RSAPublicKey pk,
379 byte[] header, byte[] headerAlt,
380 byte[] hash, int hashOff, int hashLen, byte[] sig)
382 return Verify(pk, header, headerAlt,
383 hash, hashOff, hashLen,
387 public static bool Verify(RSAPublicKey pk,
388 byte[] header, byte[] headerAlt,
389 byte[] hash, byte[] sig, int sigOff, int sigLen)
391 return Verify(pk, header, headerAlt,
392 hash, 0, hash.Length,
393 sig, sigOff, sigLen);
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)
402 * Signature must be an integer less than the modulus,
403 * but encoded over exactly the same size as the modulus.
405 byte[] n = pk.Modulus;
406 int modLen = n.Length;
407 if (sigLen != modLen) {
410 byte[] x = new byte[modLen];
411 Array.Copy(sig, sigOff, x, 0, modLen);
412 if (BigInt.Compare(x, n) >= 0) {
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).
421 x = BigInt.ModPow(x, pk.Exponent, n);
422 if (x.Length < 11 || x[0] != 0x00 || x[1] != 0x01) {
426 while (k < x.Length && x[k] == 0xFF) {
429 if (k < 10 || k == x.Length || x[k] != 0x00) {
435 * Check that the remaining byte end with the provided
438 int len = modLen - k;
442 for (int i = 0; i < hashLen; i ++) {
443 if (x[modLen - hashLen + i] != hash[hashOff + i]) {
450 * Header is at offset 'k', and length 'len'. Compare
451 * with the provided header(s).
453 if (Eq(header, 0, header.Length, x, k, len)) {
456 if (headerAlt != null) {
457 if (Eq(headerAlt, 0, headerAlt.Length, x, k, len)) {
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).
472 public static byte[] Sign(RSAPrivateKey sk, byte[] header,
475 return Sign(sk, header, hash, 0, hash.Length);
478 public static byte[] Sign(RSAPrivateKey sk, byte[] header,
479 byte[] hash, int hashOff, int hashLen)
481 byte[] sig = new byte[sk.N.Length];
482 Sign(sk, header, hash, hashOff, hashLen, sig, 0);
486 public static int Sign(RSAPrivateKey sk, byte[] header,
487 byte[] hash, byte[] outBuf, int outOff)
489 return Sign(sk, header, hash, 0, hash.Length, outBuf, outOff);
492 public static int Sign(RSAPrivateKey sk, byte[] header,
493 byte[] hash, int hashOff, int hashLen,
494 byte[] outBuf, int outOff)
496 int modLen = sk.N.Length;
497 byte[] x = DoPKCS1Padding(modLen, false,
498 header, hash, hashOff, hashLen);
500 Array.Copy(x, 0, outBuf, outOff, x.Length);
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.
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
514 public static byte[] DoPKCS1Padding(int modLen, bool type2,
515 byte[] head, byte[] val, int valOff, int valLen)
520 int len = head.Length + valLen;
521 int padLen = modLen - len - 3;
524 "modulus too short for PKCS#1 padding");
526 byte[] x = new byte[modLen];
528 x[1] = (byte)(type2 ? 0x02 : 0x01);
530 RNG.GetBytesNonZero(x, 2, padLen);
532 for (int i = 0; i < padLen; i ++) {
536 x[padLen + 2] = 0x00;
537 Array.Copy(head, 0, x, padLen + 3, head.Length);
538 Array.Copy(val, valOff, x, modLen - valLen, valLen);
543 * Compare two byte chunks for equality.
545 static bool Eq(byte[] a, int aoff, int alen,
546 byte[] b, int boff, int blen)
551 for (int i = 0; i < alen; i ++) {
552 if (a[aoff + i] != b[boff + i]) {