?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2010-06-21 Marek Habersack <mhabersack@novell.com>
[mcs.git] / class / corlib / Mono.Security.Cryptography / DSAManaged.cs
blob752f660fdefb3f3caaf20c0ae075f776b426feaa
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 }
git-svn mirror of mcs