2 // DSAManaged.cs - Implements the DSA algorithm.
5 // Dan Lewis (dihlewis@yahoo.co.uk)
6 // Sebastien Pouliot (spouliot@motus.com)
7 // Ben Maurer (bmaurer@users.sf.net)
9 // (C) 2002, 2003 Motus Technologies Inc. (http://www.motus.com)
10 // Portions (C) 2003 Ben Maurer
12 // Key generation translated from Bouncy Castle JCE (http://www.bouncycastle.org/)
13 // See bouncycastle.txt for license.
17 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
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:
27 // The above copyright notice and this permission notice shall be
28 // included in all copies or substantial portions of the Software.
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.
40 using System
.Security
.Cryptography
;
44 namespace Mono
.Security
.Cryptography
{
51 class DSAManaged
: DSA
{
53 private const int defaultKeySize
= 1024;
55 private bool keypairGenerated
= false;
56 private bool m_disposed
= false;
61 private BigInteger x
; // private key
64 private BigInteger seed
;
66 private bool j_missing
;
68 private RandomNumberGenerator rng
;
70 public DSAManaged () : this (defaultKeySize
) {}
72 public DSAManaged (int dwKeySize
)
74 KeySizeValue
= dwKeySize
;
75 LegalKeySizesValue
= new KeySizes
[1];
76 LegalKeySizesValue
[0] = new KeySizes (512, 1024, 64);
81 // Zeroize private key
85 // generate both the group and the keypair
86 private void Generate ()
88 GenerateParams (base.KeySize
);
90 keypairGenerated
= true;
91 if (KeyGenerated
!= null)
92 KeyGenerated (this, null);
95 // this part is quite fast
96 private void GenerateKeyPair ()
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)
104 // calculate the public key y = g^x % p
108 private void add (byte[] a
, byte[] b
, int value)
110 uint x
= (uint) ((b
[b
.Length
- 1] & 0xff) + value);
112 a
[b
.Length
- 1] = (byte)x
;
115 for (int i
= b
.Length
- 2; i
>= 0; i
--) {
116 x
+= (uint) (b
[i
] & 0xff);
122 private void GenerateParams (int keyLength
)
124 byte[] seed
= new byte[20];
125 byte[] part1
= new byte[20];
126 byte[] part2
= new byte[20];
127 byte[] u
= new byte[20];
129 // TODO: a prime generator should be made for this
131 SHA1 sha
= SHA1
.Create ();
133 int n
= (keyLength
- 1) / 160;
134 byte[] w
= new byte [keyLength
/ 8];
135 bool primesFound
= false;
137 while (!primesFound
) {
139 Random
.GetBytes (seed
);
140 part1
= sha
.ComputeHash (seed
);
141 Array
.Copy(seed
, 0, part2
, 0, seed
.Length
);
143 add (part2
, seed
, 1);
145 part2
= sha
.ComputeHash (part2
);
147 for (int i
= 0; i
!= u
.Length
; i
++)
148 u
[i
] = (byte)(part1
[i
] ^ part2
[i
]);
150 // first bit must be set (to respect key length)
152 // last bit must be set (prime are all odds - except 2)
155 q
= new BigInteger (u
);
157 while (!q
.IsProbablePrime ());
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
);
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
);
173 BigInteger x
= new BigInteger (w
);
175 BigInteger c
= x
% (q
* 2);
179 if (p
.TestBit ((uint)(keyLength
- 1))) {
180 if (p
.IsProbablePrime ()) {
191 // calculate the generator g
192 BigInteger pMinusOneOverQ
= (p
- 1) / q
;
194 BigInteger h
= BigInteger
.GenerateRandom (keyLength
);
195 if ((h
<= 1) || (h
>= (p
- 1)))
198 g
= h
.ModPow (pMinusOneOverQ
, p
);
204 this.seed
= new BigInteger (seed
);
208 private RandomNumberGenerator Random
{
211 rng
= RandomNumberGenerator
.Create ();
216 // overrides from DSA class
218 public override int KeySize
{
220 // in case keypair hasn't been (yet) generated
221 if (keypairGenerated
)
222 return p
.BitCount ();
228 public override string KeyExchangeAlgorithm
{
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)); }
238 public override string SignatureAlgorithm
{
239 get { return "http://www.w3.org/2000/09/xmldsig#dsa-sha1"; }
242 private byte[] NormalizeArray (byte[] array
)
244 int n
= (array
.Length
% 4);
246 byte[] temp
= new byte [array
.Length
+ 4 - n
];
247 Array
.Copy (array
, 0, temp
, (4 - n
), array
.Length
);
254 public override DSAParameters
ExportParameters (bool includePrivateParameters
)
257 throw new ObjectDisposedException (Locale
.GetText ("Keypair was disposed"));
259 if (!keypairGenerated
)
262 if ((includePrivateParameters
) && (x
== null))
263 throw new CryptographicException ("no private key to export");
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 ());
274 param
.J
= NormalizeArray (j
.GetBytes ());
277 param
.Seed
= NormalizeArray (seed
.GetBytes ());
278 param
.Counter
= counter
;
280 if (includePrivateParameters
) {
281 byte[] privateKey
= x
.GetBytes ();
282 if (privateKey
.Length
== 20) {
283 param
.X
= NormalizeArray (privateKey
);
289 public override void ImportParameters (DSAParameters parameters
)
292 throw new ObjectDisposedException (Locale
.GetText ("Keypair was disposed"));
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."));
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
);
309 // we can calculate Y from X if required
310 if (parameters
.Y
!= null)
311 y
= new BigInteger (parameters
.Y
);
314 // optional parameter - pre-computation
315 if (parameters
.J
!= null) {
316 j
= new BigInteger (parameters
.J
);
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
;
329 // we now have a keypair
330 keypairGenerated
= true;
333 public override byte[] CreateSignature (byte[] rgbHash
)
336 throw new ObjectDisposedException (Locale
.GetText ("Keypair was disposed"));
339 throw new ArgumentNullException ("rgbHash");
340 if (rgbHash
.Length
!= 20)
341 throw new CryptographicException ("invalid hash length");
343 if (!keypairGenerated
)
346 // if required key must be generated before checking for X
348 throw new CryptographicException ("no private key available for signature");
350 BigInteger m
= new BigInteger (rgbHash
);
351 // (a) Select a random secret integer k; 0 < k < q.
352 BigInteger k
= BigInteger
.GenerateRandom (160);
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
);
372 public override bool VerifySignature (byte[] rgbHash
, byte[] rgbSignature
)
375 throw new ObjectDisposedException (Locale
.GetText ("Keypair was disposed"));
378 throw new ArgumentNullException ("rgbHash");
379 if (rgbSignature
== null)
380 throw new ArgumentNullException ("rgbSignature");
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");
390 // it would be stupid to verify a signature with a newly
391 // generated keypair - so we return false
392 if (!keypairGenerated
)
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
);
403 if ((r
< 0) || (q
<= r
))
406 if ((s
< 0) || (q
<= s
))
409 BigInteger w
= s
.ModInverse(q
);
410 BigInteger u1
= m
* w
% q
;
411 BigInteger u2
= r
* w
% q
;
413 u1
= g
.ModPow(u1
, p
);
414 u2
= y
.ModPow(u2
, p
);
416 BigInteger v
= ((u1
* u2
% p
) % q
);
420 throw new CryptographicException ("couldn't compute signature verification");
424 protected override void Dispose (bool disposing
)
427 // Always zeroize private key
463 // no need as they all are abstract before us
467 public delegate void KeyGeneratedEventHandler (object sender
, EventArgs e
);
469 public event KeyGeneratedEventHandler KeyGenerated
;