-- |
-- Module : Crypto.PubKey.DSA
-- License : BSD-style
-- Maintainer : Vincent Hanquez <vincent@snarc.org>
-- Stability : experimental
-- Portability : Good
--
-- An implementation of the Digital Signature Algorithm (DSA)
{-# LANGUAGE DeriveDataTypeable #-}
module Crypto.PubKey.DSA
( Params(..)
, Signature(..)
, PublicKey(..)
, PrivateKey(..)
, PublicNumber
, PrivateNumber
-- * generation
, generatePrivate
, calculatePublic
-- * signature primitive
, sign
, signWith
-- * verification primitive
, verify
-- * Key pair
, KeyPair(..)
, toPublicKey
, toPrivateKey
) where
import Crypto.Random.Types
import Data.Bits (testBit)
import Data.Data
import Data.Maybe
import Crypto.Number.Basic (numBits)
import Crypto.Number.ModArithmetic (expFast, expSafe, inverse)
import Crypto.Number.Serialize
import Crypto.Number.Generate
import Crypto.Internal.ByteArray (ByteArrayAccess(length), convert, index, dropView, takeView)
import Crypto.Internal.Imports
import Crypto.Hash
import Prelude hiding (length)
-- | DSA Public Number, usually embedded in DSA Public Key
type PublicNumber = Integer
-- | DSA Private Number, usually embedded in DSA Private Key
type PrivateNumber = Integer
-- | Represent DSA parameters namely P, G, and Q.
data Params = Params
{ params_p :: Integer -- ^ DSA p
, params_g :: Integer -- ^ DSA g
, params_q :: Integer -- ^ DSA q
} deriving (Show,Read,Eq,Data,Typeable)
instance NFData Params where
rnf (Params p g q) = p `seq` g `seq` q `seq` ()
-- | Represent a DSA signature namely R and S.
data Signature = Signature
{ sign_r :: Integer -- ^ DSA r
, sign_s :: Integer -- ^ DSA s
} deriving (Show,Read,Eq,Data,Typeable)
instance NFData Signature where
rnf (Signature r s) = r `seq` s `seq` ()
-- | Represent a DSA public key.
data PublicKey = PublicKey
{ public_params :: Params -- ^ DSA parameters
, public_y :: PublicNumber -- ^ DSA public Y
} deriving (Show,Read,Eq,Data,Typeable)
instance NFData PublicKey where
rnf (PublicKey params y) = y `seq` params `seq` ()
-- | Represent a DSA private key.
--
-- Only x need to be secret.
-- the DSA parameters are publicly shared with the other side.
data PrivateKey = PrivateKey
{ private_params :: Params -- ^ DSA parameters
, private_x :: PrivateNumber -- ^ DSA private X
} deriving (Show,Read,Eq,Data,Typeable)
instance NFData PrivateKey where
rnf (PrivateKey params x) = x `seq` params `seq` ()
-- | Represent a DSA key pair
data KeyPair = KeyPair Params PublicNumber PrivateNumber
deriving (Show,Read,Eq,Data,Typeable)
instance NFData KeyPair where
rnf (KeyPair params y x) = x `seq` y `seq` params `seq` ()
-- | Public key of a DSA Key pair
toPublicKey :: KeyPair -> PublicKey
toPublicKey (KeyPair params pub _) = PublicKey params pub
-- | Private key of a DSA Key pair
toPrivateKey :: KeyPair -> PrivateKey
toPrivateKey (KeyPair params _ priv) = PrivateKey params priv
-- | generate a private number with no specific property
-- this number is usually called X in DSA text.
generatePrivate :: MonadRandom m => Params -> m PrivateNumber
generatePrivate (Params _ _ q) = generateMax q
-- | Calculate the public number from the parameters and the private key
calculatePublic :: Params -> PrivateNumber -> PublicNumber
calculatePublic (Params p g _) x = expSafe g x p
-- | sign message using the private key and an explicit k number.
signWith :: (ByteArrayAccess msg, HashAlgorithm hash)
=> Integer -- ^ k random number
-> PrivateKey -- ^ private key
-> hash -- ^ hash function
-> msg -- ^ message to sign
-> Maybe Signature
signWith k pk hashAlg msg
| r == 0 || s == 0 = Nothing
| otherwise = Just $ Signature r s
where -- parameters
(Params p g q) = private_params pk
x = private_x pk
-- compute r,s
kInv = fromJust $ inverse k q
hm = os2ip $ hashWith hashAlg msg
r = expSafe g k p `mod` q
s = (kInv * (hm + x * r)) `mod` q
-- | sign message using the private key.
sign :: (ByteArrayAccess msg, HashAlgorithm hash, MonadRandom m) => PrivateKey -> hash -> msg -> m Signature
sign pk hashAlg msg = do
k <- generateMax q
case signWith k pk hashAlg msg of
Nothing -> sign pk hashAlg msg
Just sig -> return sig
where
(Params _ _ q) = private_params pk
-- | verify a bytestring using the public key.
verify :: (ByteArrayAccess msg, HashAlgorithm hash) => hash -> PublicKey -> Signature -> msg -> Bool
verify hashAlg pk (Signature r s) m
-- Reject the signature if either 0 < r < q or 0 < s < q is not satisfied.
| r <= 0 || r >= q || s <= 0 || s >= q = False
| otherwise = v == r
where (Params p g q) = public_params pk
y = public_y pk
hm = os2ip . truncateHash $ hashWith hashAlg m
w = fromJust $ inverse s q
u1 = (hm*w) `mod` q
u2 = (r*w) `mod` q
v = ((expFast g u1 p) * (expFast y u2 p)) `mod` p `mod` q
-- if the hash is larger than the size of q, truncate it; FIXME: deal with the case of a q not evenly divisible by 8
truncateHash h = if numBits (os2ip h) > numBits q then takeView h (numBits q `div` 8) else dropView h 0