1 // 2 // RSAManaged.cs - Implements the RSA algorithm. 3 // 4 // Authors: 5 // Sebastien Pouliot (sebastien@ximian.com) 6 // Ben Maurer (bmaurer@users.sf.net) 7 // 8 // (C) 2002, 2003 Motus Technologies Inc. (http://www.motus.com) 9 // Portions (C) 2003 Ben Maurer 10 // Copyright (C) 2004,2006 Novell, Inc (http://www.novell.com) 11 // 12 // Key generation translated from Bouncy Castle JCE (http://www.bouncycastle.org/) 13 // See bouncycastle.txt for license. 14 // 15 // Permission is hereby granted, free of charge, to any person obtaining 16 // a copy of this software and associated documentation files (the 17 // "Software"), to deal in the Software without restriction, including 18 // without limitation the rights to use, copy, modify, merge, publish, 19 // distribute, sublicense, and/or sell copies of the Software, and to 20 // permit persons to whom the Software is furnished to do so, subject to 21 // the following conditions: 22 // 23 // The above copyright notice and this permission notice shall be 24 // included in all copies or substantial portions of the Software. 25 // 26 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 27 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 28 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 29 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 30 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 31 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 32 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 33 // 34 35 using System; 36 using System.Security.Cryptography; 37 using System.Text; 38 39 using Mono.Math; 40 41 // Big chunks of code are coming from the original RSACryptoServiceProvider class. 42 // The class was refactored to : 43 // a. ease integration of new hash algorithm (like MD2, RIPEMD160, ...); 44 // b. provide better support for the coming SSL implementation (requires 45 // EncryptValue/DecryptValue) with, or without, Mono runtime/corlib; 46 // c. provide an alternative RSA implementation for all Windows (like using 47 // OAEP without Windows XP). 48 49 namespace Mono.Security.Cryptography { 50 51 #if INSIDE_CORLIB 52 internal 53 #else 54 public 55 #endif 56 class RSAManaged : RSA { 57 58 private const int defaultKeySize = 1024; 59 60 private bool isCRTpossible = false; 61 private bool keyBlinding = true; 62 private bool keypairGenerated = false; 63 private bool m_disposed = false; 64 65 private BigInteger d; 66 private BigInteger p; 67 private BigInteger q; 68 private BigInteger dp; 69 private BigInteger dq; 70 private BigInteger qInv; 71 private BigInteger n; // modulus 72 private BigInteger e; 73 RSAManaged()74 public RSAManaged () : this (defaultKeySize) 75 { 76 } 77 RSAManaged(int keySize)78 public RSAManaged (int keySize) 79 { 80 LegalKeySizesValue = new KeySizes [1]; 81 LegalKeySizesValue [0] = new KeySizes (384, 16384, 8); 82 base.KeySize = keySize; 83 } 84 ~RSAManaged()85 ~RSAManaged () 86 { 87 // Zeroize private key 88 Dispose (false); 89 } 90 GenerateKeyPair()91 private void GenerateKeyPair () 92 { 93 // p and q values should have a length of half the strength in bits 94 int pbitlength = ((KeySize + 1) >> 1); 95 int qbitlength = (KeySize - pbitlength); 96 const uint uint_e = 65537; 97 e = uint_e; // fixed 98 99 // generate p, prime and (p-1) relatively prime to e 100 for (;;) { 101 p = BigInteger.GeneratePseudoPrime (pbitlength); 102 if (p % uint_e != 1) 103 break; 104 } 105 // generate a modulus of the required length 106 for (;;) { 107 // generate q, prime and (q-1) relatively prime to e, 108 // and not equal to p 109 for (;;) { 110 q = BigInteger.GeneratePseudoPrime (qbitlength); 111 if ((q % uint_e != 1) && (p != q)) 112 break; 113 } 114 115 // calculate the modulus 116 n = p * q; 117 if (n.BitCount () == KeySize) 118 break; 119 120 // if we get here our primes aren't big enough, make the largest 121 // of the two p and try again 122 if (p < q) 123 p = q; 124 } 125 126 BigInteger pSub1 = (p - 1); 127 BigInteger qSub1 = (q - 1); 128 BigInteger phi = pSub1 * qSub1; 129 130 // calculate the private exponent 131 d = e.ModInverse (phi); 132 133 // calculate the CRT factors 134 dp = d % pSub1; 135 dq = d % qSub1; 136 qInv = q.ModInverse (p); 137 138 keypairGenerated = true; 139 isCRTpossible = true; 140 141 if (KeyGenerated != null) 142 KeyGenerated (this, null); 143 } 144 145 // overrides from RSA class 146 147 public override int KeySize { 148 get { 149 if (m_disposed) 150 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed")); 151 152 // in case keypair hasn't been (yet) generated 153 if (keypairGenerated) { 154 int ks = n.BitCount (); 155 if ((ks & 7) != 0) 156 ks = ks + (8 - (ks & 7)); 157 return ks; 158 } 159 else 160 return base.KeySize; 161 } 162 } 163 public override string KeyExchangeAlgorithm { 164 get { return "RSA-PKCS1-KeyEx"; } 165 } 166 167 // note: when (if) we generate a keypair then it will have both 168 // the public and private keys 169 public bool PublicOnly { 170 get { return (keypairGenerated && ((d == null) || (n == null))); } 171 } 172 173 public override string SignatureAlgorithm { 174 get { return "http://www.w3.org/2000/09/xmldsig#rsa-sha1"; } 175 } 176 DecryptValue(byte[] rgb)177 public override byte[] DecryptValue (byte[] rgb) 178 { 179 if (m_disposed) 180 throw new ObjectDisposedException ("private key"); 181 182 // decrypt operation is used for signature 183 if (!keypairGenerated) 184 GenerateKeyPair (); 185 186 BigInteger input = new BigInteger (rgb); 187 BigInteger r = null; 188 189 // we use key blinding (by default) against timing attacks 190 if (keyBlinding) { 191 // x = (r^e * g) mod n 192 // *new* random number (so it's timing is also random) 193 r = BigInteger.GenerateRandom (n.BitCount ()); 194 input = r.ModPow (e, n) * input % n; 195 } 196 197 BigInteger output; 198 // decrypt (which uses the private key) can be 199 // optimized by using CRT (Chinese Remainder Theorem) 200 if (isCRTpossible) { 201 // m1 = c^dp mod p 202 BigInteger m1 = input.ModPow (dp, p); 203 // m2 = c^dq mod q 204 BigInteger m2 = input.ModPow (dq, q); 205 BigInteger h; 206 if (m2 > m1) { 207 // thanks to benm! 208 h = p - ((m2 - m1) * qInv % p); 209 output = m2 + q * h; 210 } else { 211 // h = (m1 - m2) * qInv mod p 212 h = (m1 - m2) * qInv % p; 213 // m = m2 + q * h; 214 output = m2 + q * h; 215 } 216 } else if (!PublicOnly) { 217 // m = c^d mod n 218 output = input.ModPow (d, n); 219 } else { 220 throw new CryptographicException (Locale.GetText ("Missing private key to decrypt value.")); 221 } 222 223 if (keyBlinding) { 224 // Complete blinding 225 // x^e / r mod n 226 output = output * r.ModInverse (n) % n; 227 r.Clear (); 228 } 229 230 // it's sometimes possible for the results to be a byte short 231 // and this can break some software (see #79502) so we 0x00 pad the result 232 byte[] result = GetPaddedValue (output, (KeySize >> 3)); 233 // zeroize values 234 input.Clear (); 235 output.Clear (); 236 return result; 237 } 238 EncryptValue(byte[] rgb)239 public override byte[] EncryptValue (byte[] rgb) 240 { 241 if (m_disposed) 242 throw new ObjectDisposedException ("public key"); 243 244 if (!keypairGenerated) 245 GenerateKeyPair (); 246 247 BigInteger input = new BigInteger (rgb); 248 BigInteger output = input.ModPow (e, n); 249 // it's sometimes possible for the results to be a byte short 250 // and this can break some software (see #79502) so we 0x00 pad the result 251 byte[] result = GetPaddedValue (output, (KeySize >> 3)); 252 // zeroize value 253 input.Clear (); 254 output.Clear (); 255 return result; 256 } 257 258 259 ExportParameters(bool includePrivateParameters)260 public override RSAParameters ExportParameters (bool includePrivateParameters) 261 { 262 if (m_disposed) 263 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed")); 264 265 if (!keypairGenerated) 266 GenerateKeyPair (); 267 268 RSAParameters param = new RSAParameters (); 269 param.Exponent = e.GetBytes (); 270 param.Modulus = n.GetBytes (); 271 if (includePrivateParameters) { 272 // some parameters are required for exporting the private key 273 if (d == null) 274 throw new CryptographicException ("Missing private key"); 275 param.D = d.GetBytes (); 276 // hack for bugzilla #57941 where D wasn't provided 277 if (param.D.Length != param.Modulus.Length) { 278 byte[] normalizedD = new byte [param.Modulus.Length]; 279 Buffer.BlockCopy (param.D, 0, normalizedD, (normalizedD.Length - param.D.Length), param.D.Length); 280 param.D = normalizedD; 281 } 282 // but CRT parameters are optionals 283 if ((p != null) && (q != null) && (dp != null) && (dq != null) && (qInv != null)) { 284 // and we include them only if we have them all 285 int length = (KeySize >> 4); 286 param.P = GetPaddedValue (p, length); 287 param.Q = GetPaddedValue (q, length); 288 param.DP = GetPaddedValue (dp, length); 289 param.DQ = GetPaddedValue (dq, length); 290 param.InverseQ = GetPaddedValue (qInv, length); 291 } 292 } 293 return param; 294 } 295 ImportParameters(RSAParameters parameters)296 public override void ImportParameters (RSAParameters parameters) 297 { 298 if (m_disposed) 299 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed")); 300 301 // if missing "mandatory" parameters 302 if (parameters.Exponent == null) 303 throw new CryptographicException (Locale.GetText ("Missing Exponent")); 304 if (parameters.Modulus == null) 305 throw new CryptographicException (Locale.GetText ("Missing Modulus")); 306 307 e = new BigInteger (parameters.Exponent); 308 n = new BigInteger (parameters.Modulus); 309 310 //reset all private key values to null 311 d = dp = dq = qInv = p = q = null; 312 313 // only if the private key is present 314 if (parameters.D != null) 315 d = new BigInteger (parameters.D); 316 if (parameters.DP != null) 317 dp = new BigInteger (parameters.DP); 318 if (parameters.DQ != null) 319 dq = new BigInteger (parameters.DQ); 320 if (parameters.InverseQ != null) 321 qInv = new BigInteger (parameters.InverseQ); 322 if (parameters.P != null) 323 p = new BigInteger (parameters.P); 324 if (parameters.Q != null) 325 q = new BigInteger (parameters.Q); 326 327 // we now have a keypair 328 keypairGenerated = true; 329 bool privateKey = ((p != null) && (q != null) && (dp != null)); 330 isCRTpossible = (privateKey && (dq != null) && (qInv != null)); 331 332 // check if the public/private keys match 333 // the way the check is made allows a bad D to work if CRT is available (like MS does, see unit tests) 334 if (!privateKey) 335 return; 336 337 // always check n == p * q 338 bool ok = (n == (p * q)); 339 if (ok) { 340 // we now know that p and q are correct, so (p - 1), (q - 1) and phi will be ok too 341 BigInteger pSub1 = (p - 1); 342 BigInteger qSub1 = (q - 1); 343 BigInteger phi = pSub1 * qSub1; 344 // e is fairly static but anyway we can ensure it makes sense by recomputing d 345 BigInteger dcheck = e.ModInverse (phi); 346 347 // now if our new d(check) is different than the d we're provided then we cannot 348 // be sure if 'd' or 'e' is invalid... (note that, from experience, 'd' is more 349 // likely to be invalid since it's twice as large as DP (or DQ) and sits at the 350 // end of the structure (e.g. truncation). 351 ok = (d == dcheck); 352 353 // ... unless we have the pre-computed CRT parameters 354 if (!ok && isCRTpossible) { 355 // we can override the previous decision since Mono always prefer, for 356 // performance reasons, using the CRT algorithm 357 ok = (dp == (dcheck % pSub1)) && (dq == (dcheck % qSub1)) && 358 (qInv == q.ModInverse (p)); 359 } 360 } 361 362 if (!ok) 363 throw new CryptographicException (Locale.GetText ("Private/public key mismatch")); 364 } 365 Dispose(bool disposing)366 protected override void Dispose (bool disposing) 367 { 368 if (!m_disposed) { 369 // Always zeroize private key 370 if (d != null) { 371 d.Clear (); 372 d = null; 373 } 374 if (p != null) { 375 p.Clear (); 376 p = null; 377 } 378 if (q != null) { 379 q.Clear (); 380 q = null; 381 } 382 if (dp != null) { 383 dp.Clear (); 384 dp = null; 385 } 386 if (dq != null) { 387 dq.Clear (); 388 dq = null; 389 } 390 if (qInv != null) { 391 qInv.Clear (); 392 qInv = null; 393 } 394 395 if (disposing) { 396 // clear public key 397 if (e != null) { 398 e.Clear (); 399 e = null; 400 } 401 if (n != null) { 402 n.Clear (); 403 n = null; 404 } 405 } 406 } 407 // call base class 408 // no need as they all are abstract before us 409 m_disposed = true; 410 } 411 KeyGeneratedEventHandler(object sender, EventArgs e)412 public delegate void KeyGeneratedEventHandler (object sender, EventArgs e); 413 414 public event KeyGeneratedEventHandler KeyGenerated; 415 ToXmlString(bool includePrivateParameters)416 public override string ToXmlString (bool includePrivateParameters) 417 { 418 StringBuilder sb = new StringBuilder (); 419 RSAParameters rsaParams = ExportParameters (includePrivateParameters); 420 try { 421 sb.Append ("<RSAKeyValue>"); 422 423 sb.Append ("<Modulus>"); 424 sb.Append (Convert.ToBase64String (rsaParams.Modulus)); 425 sb.Append ("</Modulus>"); 426 427 sb.Append ("<Exponent>"); 428 sb.Append (Convert.ToBase64String (rsaParams.Exponent)); 429 sb.Append ("</Exponent>"); 430 431 if (includePrivateParameters) { 432 if (rsaParams.P != null) { 433 sb.Append ("<P>"); 434 sb.Append (Convert.ToBase64String (rsaParams.P)); 435 sb.Append ("</P>"); 436 } 437 if (rsaParams.Q != null) { 438 sb.Append ("<Q>"); 439 sb.Append (Convert.ToBase64String (rsaParams.Q)); 440 sb.Append ("</Q>"); 441 } 442 if (rsaParams.DP != null) { 443 sb.Append ("<DP>"); 444 sb.Append (Convert.ToBase64String (rsaParams.DP)); 445 sb.Append ("</DP>"); 446 } 447 if (rsaParams.DQ != null) { 448 sb.Append ("<DQ>"); 449 sb.Append (Convert.ToBase64String (rsaParams.DQ)); 450 sb.Append ("</DQ>"); 451 } 452 if (rsaParams.InverseQ != null) { 453 sb.Append ("<InverseQ>"); 454 sb.Append (Convert.ToBase64String (rsaParams.InverseQ)); 455 sb.Append ("</InverseQ>"); 456 } 457 sb.Append ("<D>"); 458 sb.Append (Convert.ToBase64String (rsaParams.D)); 459 sb.Append ("</D>"); 460 } 461 462 sb.Append ("</RSAKeyValue>"); 463 } 464 catch { 465 if (rsaParams.P != null) 466 Array.Clear (rsaParams.P, 0, rsaParams.P.Length); 467 if (rsaParams.Q != null) 468 Array.Clear (rsaParams.Q, 0, rsaParams.Q.Length); 469 if (rsaParams.DP != null) 470 Array.Clear (rsaParams.DP, 0, rsaParams.DP.Length); 471 if (rsaParams.DQ != null) 472 Array.Clear (rsaParams.DQ, 0, rsaParams.DQ.Length); 473 if (rsaParams.InverseQ != null) 474 Array.Clear (rsaParams.InverseQ, 0, rsaParams.InverseQ.Length); 475 if (rsaParams.D != null) 476 Array.Clear (rsaParams.D, 0, rsaParams.D.Length); 477 throw; 478 } 479 480 return sb.ToString (); 481 } 482 483 // internal for Mono 1.0.x in order to preserve public contract 484 // they are public for Mono 1.1.x (for 1.2) as the API isn't froze ATM 485 486 public bool UseKeyBlinding { 487 get { return keyBlinding; } 488 // you REALLY shoudn't touch this (true is fine ;-) 489 set { keyBlinding = value; } 490 } 491 492 public bool IsCrtPossible { 493 // either the key pair isn't generated (and will be 494 // generated with CRT parameters) or CRT is (or isn't) 495 // possible (in case the key was imported) 496 get { return (!keypairGenerated || isCRTpossible); } 497 } 498 GetPaddedValue(BigInteger value, int length)499 private byte[] GetPaddedValue (BigInteger value, int length) 500 { 501 byte[] result = value.GetBytes (); 502 if (result.Length >= length) 503 return result; 504 505 // left-pad 0x00 value on the result (same integer, correct length) 506 byte[] padded = new byte[length]; 507 Buffer.BlockCopy (result, 0, padded, (length - result.Length), result.Length); 508 // temporary result may contain decrypted (plaintext) data, clear it 509 Array.Clear (result, 0, result.Length); 510 return padded; 511 } 512 } 513 } 514