mcs/class/corlib/Mono.Security.Cryptography/DSAManaged.cs

   1 //
   2 // DSAManaged.cs - Implements the DSA algorithm.
   3 //
   4 // Authors:
   5 //      Dan Lewis (dihlewis@yahoo.co.uk)
   6 //      Sebastien Pouliot (spouliot@motus.com)
   7 //      Ben Maurer (bmaurer@users.sf.net)
   8 //
   9 // (C) 2002, 2003 Motus Technologies Inc. (http://www.motus.com)
  10 // Portions (C) 2003 Ben Maurer
  11 //
  12 // Key generation translated from Bouncy Castle JCE (http://www.bouncycastle.org/)
  13 // See bouncycastle.txt for license.
  14 //
  15
  16 //
  17 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  18 //
  19 // Permission is hereby granted, free of charge, to any person obtaining
  20 // a copy of this software and associated documentation files (the
  21 // "Software"), to deal in the Software without restriction, including
  22 // without limitation the rights to use, copy, modify, merge, publish,
  23 // distribute, sublicense, and/or sell copies of the Software, and to
  24 // permit persons to whom the Software is furnished to do so, subject to
  25 // the following conditions:
  26 //
  27 // The above copyright notice and this permission notice shall be
  28 // included in all copies or substantial portions of the Software.
  29 //
  30 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  31 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  32 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  33 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  34 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  35 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  36 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  37 //
  38
  39 using System;
  40 using System.Security.Cryptography;
  41
  42 using Mono.Math;
  43
  44 namespace Mono.Security.Cryptography {
  45
  46 #if INSIDE_CORLIB
  47         internal
  48 #else
  49         public
  50 #endif
  51         class DSAManaged : DSA {
  52
  53                 private const int defaultKeySize = 1024;
  54
  55                 private bool keypairGenerated = false;
  56                 private bool m_disposed = false;
  57
  58                 private BigInteger p;
  59                 private BigInteger q;
  60                 private BigInteger g;
  61                 private BigInteger x;   // private key
  62                 private BigInteger y;
  63                 private BigInteger j;
  64                 private BigInteger seed;
  65                 private int counter;
  66                 private bool j_missing;
  67
  68                 private RandomNumberGenerator rng;
  69
  70                 public DSAManaged () : this (defaultKeySize) {}
  71
  72                 public DSAManaged (int dwKeySize)
  73                 {
  74                         KeySizeValue = dwKeySize;
  75                         LegalKeySizesValue = new KeySizes [1];
  76                         LegalKeySizesValue [0] = new KeySizes (512, 1024, 64);
  77                 }
  78
  79                 ~DSAManaged ()
  80                 {
  81                         // Zeroize private key
  82                         Dispose (false);
  83                 }
  84
  85                 // generate both the group and the keypair
  86                 private void Generate ()
  87                 {
  88                         GenerateParams (base.KeySize);
  89                         GenerateKeyPair ();
  90                         keypairGenerated = true;
  91                         if (KeyGenerated != null)
  92                                 KeyGenerated (this, null);
  93                 }
  94
  95                 // this part is quite fast
  96                 private void GenerateKeyPair ()
  97                 {
  98                         x = BigInteger.GenerateRandom (160);
  99                         while ((x == 0) || (x >= q)) {
 100                                 // size of x (private key) isn't affected by the keysize (512-1024)
 101                                 x.Randomize ();
 102                         }
 103
 104                         // calculate the public key y = g^x % p
 105                         y = g.ModPow (x, p);
 106                 }
 107
 108                 private void add (byte[] a, byte[] b, int value)
 109                 {
 110                         uint x = (uint) ((b [b.Length - 1] & 0xff) + value);
 111
 112                         a [b.Length - 1] = (byte)x;
 113                         x >>= 8;
 114
 115                         for (int i = b.Length - 2; i >= 0; i--) {
 116                                 x += (uint) (b [i] & 0xff);
 117                                 a [i] = (byte)x;
 118                                 x >>= 8;
 119                         }
 120                 }
 121
 122                 private void GenerateParams (int keyLength)
 123                 {
 124                         byte[] seed = new byte[20];
 125                         byte[] part1 = new byte[20];
 126                         byte[] part2 = new byte[20];
 127                         byte[] u = new byte[20];
 128
 129                         // TODO: a prime generator should be made for this
 130
 131                         SHA1 sha = SHA1.Create ();
 132
 133                         int n = (keyLength - 1) / 160;
 134                         byte[] w = new byte [keyLength / 8];
 135                         bool primesFound = false;
 136
 137                         while (!primesFound) {
 138                                 do {
 139                                         Random.GetBytes (seed);
 140                                         part1 = sha.ComputeHash (seed);
 141                                         Array.Copy(seed, 0, part2, 0, seed.Length);
 142
 143                                         add (part2, seed, 1);
 144
 145                                         part2 = sha.ComputeHash (part2);
 146
 147                                         for (int i = 0; i != u.Length; i++)
 148                                                 u [i] = (byte)(part1 [i] ^ part2 [i]);
 149
 150                                         // first bit must be set (to respect key length)
 151                                         u[0] |= (byte)0x80;
 152                                         // last bit must be set (prime are all odds - except 2)
 153                                         u[19] |= (byte)0x01;
 154
 155                                         q = new BigInteger (u);
 156                                 }
 157                                 while (!q.IsProbablePrime ());
 158
 159                                 counter = 0;
 160                                 int offset = 2;
 161                                 while (counter < 4096) {
 162                                         for (int k = 0; k < n; k++) {
 163                                                 add(part1, seed, offset + k);
 164                                                 part1 = sha.ComputeHash (part1);
 165                                                 Array.Copy (part1, 0, w, w.Length - (k + 1) * part1.Length, part1.Length);
 166                                         }
 167
 168                                         add(part1, seed, offset + n);
 169                                         part1 = sha.ComputeHash (part1);
 170                                         Array.Copy (part1, part1.Length - ((w.Length - (n) * part1.Length)), w, 0, w.Length - n * part1.Length);
 171
 172                                         w[0] |= (byte)0x80;
 173                                         BigInteger x = new BigInteger (w);
 174
 175                                         BigInteger c = x % (q * 2);
 176
 177                                         p = x - (c - 1);
 178
 179                                         if (p.TestBit ((uint)(keyLength - 1))) {
 180                                                 if (p.IsProbablePrime ()) {
 181                                                         primesFound = true;
 182                                                         break;
 183                                                 }
 184                                         }
 185
 186                                         counter += 1;
 187                                         offset += n + 1;
 188                                 }
 189                         }
 190
 191                         // calculate the generator g
 192                         BigInteger pMinusOneOverQ = (p - 1) / q;
 193                         for (;;) {
 194                                 BigInteger h = BigInteger.GenerateRandom (keyLength);
 195                                 if ((h <= 1) || (h >= (p - 1)))
 196                                         continue;
 197
 198                                 g = h.ModPow (pMinusOneOverQ, p);
 199                                 if (g <= 1)
 200                                         continue;
 201                                 break;
 202                         }
 203
 204                         this.seed = new BigInteger (seed);
 205                         j = (p - 1) / q;
 206                 }
 207
 208                 private RandomNumberGenerator Random {
 209                         get {
 210                                 if (rng == null)
 211                                         rng = RandomNumberGenerator.Create ();
 212                                 return rng;
 213                         }
 214                 }
 215
 216                 // overrides from DSA class
 217
 218                 public override int KeySize {
 219                         get {
 220                                 // in case keypair hasn't been (yet) generated
 221                                 if (keypairGenerated)
 222                                         return p.BitCount ();
 223                                 else
 224                                         return base.KeySize;
 225                         }
 226                 }
 227
 228                 public override string KeyExchangeAlgorithm {
 229                         get { return null; }
 230                 }
 231
 232                 // note: when (if) we generate a keypair then it will have both
 233                 // the public and private keys
 234                 public bool PublicOnly {
 235                         get { return ((keypairGenerated) && (x == null)); }
 236                 }
 237
 238                 public override string SignatureAlgorithm {
 239                         get { return "http://www.w3.org/2000/09/xmldsig#dsa-sha1"; }
 240                 }
 241
 242                 private byte[] NormalizeArray (byte[] array)
 243                 {
 244                         int n = (array.Length % 4);
 245                         if (n > 0) {
 246                                 byte[] temp = new byte [array.Length + 4 - n];
 247                                 Array.Copy (array, 0, temp, (4 - n), array.Length);
 248                                 return temp;
 249                         }
 250                         else
 251                                 return array;
 252                 }
 253
 254                 public override DSAParameters ExportParameters (bool includePrivateParameters)
 255                 {
 256                         if (m_disposed)
 257                                 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed"));
 258
 259                         if (!keypairGenerated)
 260                                 Generate ();
 261
 262                         if ((includePrivateParameters) && (x == null))
 263                                 throw new CryptographicException ("no private key to export");
 264
 265                         DSAParameters param = new DSAParameters ();
 266                         // all parameters must be in multiple of 4 bytes arrays
 267                         // this isn't (generally) a problem for most of the parameters
 268                         // except for J (but we won't take a chance)
 269                         param.P = NormalizeArray (p.GetBytes ());
 270                         param.Q = NormalizeArray (q.GetBytes ());
 271                         param.G = NormalizeArray (g.GetBytes ());
 272                         param.Y = NormalizeArray (y.GetBytes ());
 273                         if (!j_missing) {
 274                                 param.J = NormalizeArray (j.GetBytes ());
 275                         }
 276                         if (seed != 0) {
 277                                 param.Seed = NormalizeArray (seed.GetBytes ());
 278                                 param.Counter = counter;
 279                         }
 280                         if (includePrivateParameters) {
 281                                 byte[] privateKey = x.GetBytes ();
 282                                 if (privateKey.Length == 20) {
 283                                         param.X = NormalizeArray (privateKey);
 284                                 }
 285                         }
 286                         return param;
 287                 }
 288
 289                 public override void ImportParameters (DSAParameters parameters)
 290                 {
 291                         if (m_disposed)
 292                                 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed"));
 293
 294                         // if missing "mandatory" parameters
 295                         if ((parameters.P == null) || (parameters.Q == null) || (parameters.G == null))
 296                                 throw new CryptographicException (Locale.GetText ("Missing mandatory DSA parameters (P, Q or G)."));
 297                         // We can calculate Y from X, but both can't be missing
 298                         if ((parameters.X == null) && (parameters.Y == null))
 299                                 throw new CryptographicException (Locale.GetText ("Missing both public (Y) and private (X) keys."));
 300
 301                         p = new BigInteger (parameters.P);
 302                         q = new BigInteger (parameters.Q);
 303                         g = new BigInteger (parameters.G);
 304                         // optional parameter - private key
 305                         if (parameters.X != null)
 306                                 x = new BigInteger (parameters.X);
 307                         else
 308                                 x = null;
 309                         // we can calculate Y from X if required
 310                         if (parameters.Y != null)
 311                                 y = new BigInteger (parameters.Y);
 312                         else
 313                                 y = g.ModPow (x, p);
 314                         // optional parameter - pre-computation
 315                         if (parameters.J != null) {
 316                                 j = new BigInteger (parameters.J);
 317                         } else {
 318                                 j = (p - 1) / q;
 319                                 j_missing = true;
 320                         }
 321                         // optional - seed and counter must both be present (or absent)
 322                         if (parameters.Seed != null) {
 323                                 seed = new BigInteger (parameters.Seed);
 324                                 counter = parameters.Counter;
 325                         }
 326                         else
 327                                 seed = 0;
 328
 329                         // we now have a keypair
 330                         keypairGenerated = true;
 331                 }
 332
 333                 public override byte[] CreateSignature (byte[] rgbHash)
 334                 {
 335                         if (m_disposed)
 336                                 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed"));
 337
 338                         if (rgbHash == null)
 339                                 throw new ArgumentNullException ("rgbHash");
 340                         if (rgbHash.Length != 20)
 341                                 throw new CryptographicException ("invalid hash length");
 342
 343                         if (!keypairGenerated)
 344                                 Generate ();
 345
 346                         // if required key must be generated before checking for X
 347                         if (x == null)
 348                                 throw new CryptographicException ("no private key available for signature");
 349
 350                         BigInteger m = new BigInteger (rgbHash);
 351                         // (a) Select a random secret integer k; 0 < k < q.
 352                         BigInteger k = BigInteger.GenerateRandom (160);
 353                         while (k >= q)
 354                                 k.Randomize ();
 355                         // (b) Compute r = (g^k mod p) mod q
 356                         BigInteger r = (g.ModPow (k, p)) % q;
 357                         // (c) Compute k -1 mod q (e.g., using Algorithm 2.142).
 358                         // (d) Compute s = k -1 fh(m) +arg mod q.
 359                         BigInteger s = (k.ModInverse (q) * (m + x * r)) % q;
 360                         // (e) A's signature for m is the pair (r; s).
 361                         byte[] signature = new byte [40];
 362                         byte[] part1 = r.GetBytes ();
 363                         byte[] part2 = s.GetBytes ();
 364                         // note: sometime (1/256) we may get less than 20 bytes (if first is 00)
 365                         int start = 20 - part1.Length;
 366                         Array.Copy (part1, 0, signature, start, part1.Length);
 367                         start = 40 - part2.Length;
 368                         Array.Copy (part2, 0, signature, start, part2.Length);
 369                         return signature;
 370                 }
 371
 372                 public override bool VerifySignature (byte[] rgbHash, byte[] rgbSignature)
 373                 {
 374                         if (m_disposed)
 375                                 throw new ObjectDisposedException (Locale.GetText ("Keypair was disposed"));
 376
 377                         if (rgbHash == null)
 378                                 throw new ArgumentNullException ("rgbHash");
 379                         if (rgbSignature == null)
 380                                 throw new ArgumentNullException ("rgbSignature");
 381
 382                         if (rgbHash.Length != 20)
 383                                 throw new CryptographicException ("invalid hash length");
 384                         // signature is always 40 bytes (no matter the size of the
 385                         // public key). In fact it is 2 times the size of the private
 386                         // key (which is 20 bytes for 512 to 1024 bits DSA keypairs)
 387                         if (rgbSignature.Length != 40)
 388                                 throw new CryptographicException ("invalid signature length");
 389
 390                         // it would be stupid to verify a signature with a newly
 391                         // generated keypair - so we return false
 392                         if (!keypairGenerated)
 393                                 return false;
 394
 395                         try {
 396                                 BigInteger m = new BigInteger (rgbHash);
 397                                 byte[] half = new byte [20];
 398                                 Array.Copy (rgbSignature, 0, half, 0, 20);
 399                                 BigInteger r = new BigInteger (half);
 400                                 Array.Copy (rgbSignature, 20, half, 0, 20);
 401                                 BigInteger s = new BigInteger (half);
 402
 403                                 if ((r < 0) || (q <= r))
 404                                         return false;
 405
 406                                 if ((s < 0) || (q <= s))
 407                                         return false;
 408
 409                                 BigInteger w = s.ModInverse(q);
 410                                 BigInteger u1 = m * w % q;
 411                                 BigInteger u2 = r * w % q;
 412
 413                                 u1 = g.ModPow(u1, p);
 414                                 u2 = y.ModPow(u2, p);
 415
 416                                 BigInteger v = ((u1 * u2 % p) % q);
 417                                 return (v == r);
 418                         }
 419                         catch {
 420                                 throw new CryptographicException ("couldn't compute signature verification");
 421                         }
 422                 }
 423
 424                 protected override void Dispose (bool disposing)
 425                 {
 426                         if (!m_disposed) {
 427                                 // Always zeroize private key
 428                                 if (x != null) {
 429                                         x.Clear ();
 430                                         x = null;
 431                                 }
 432
 433                                 if (disposing) {
 434                                         // clear group
 435                                         if (p != null) {
 436                                                 p.Clear ();
 437                                                 p = null;
 438                                         }
 439                                         if (q != null) {
 440                                                 q.Clear ();
 441                                                 q = null;
 442                                         }
 443                                         if (g != null) {
 444                                                 g.Clear ();
 445                                                 g = null;
 446                                         }
 447                                         if (j != null) {
 448                                                 j.Clear ();
 449                                                 j = null;
 450                                         }
 451                                         if (seed != null) {
 452                                                 seed.Clear ();
 453                                                 seed = null;
 454                                         }
 455                                         // clear public key
 456                                         if (y != null) {
 457                                                 y.Clear ();
 458                                                 y = null;
 459                                         }
 460                                 }
 461                         }
 462                         // call base class
 463                         // no need as they all are abstract before us
 464                         m_disposed = true;
 465                 }
 466
 467                 public delegate void KeyGeneratedEventHandler (object sender, EventArgs e);
 468
 469                 public event KeyGeneratedEventHandler KeyGenerated;
 470         }
 471 }