packages feed

crypton-2.3.0: Crypto/PubKey/ECC/ECDSA.hs

{-# LANGUAGE DeriveDataTypeable #-}

-- | /WARNING:/ Signature operations may leak the private key.  The nonce is
-- inverted without a side channel on every curve, and on P-256 the scalar
-- multiplication is the constant-time C implementation, but what surrounds
-- them is 'Integer' arithmetic, whose cost follows the values it is given, and
-- on every other curve the multiplication follows the nonce as well.
-- Signature verification takes only public values and should be safe.
module Crypto.PubKey.ECC.ECDSA (
    Signature (..),
    ExtendedSignature (..),
    PublicPoint,
    PublicKey (..),
    PrivateNumber,
    PrivateKey (..),
    KeyPair (..),
    toPublicKey,
    toPrivateKey,
    signWith,
    signDigestWith,
    signExtendedDigestWith,
    sign,
    signDigest,
    signExtendedDigest,
    verify,
    verifyDigest,
    recover,
    recoverDigest,
    deterministicNonce,
) where

import Crypto.Debug (DebugShow (..))
import Control.Monad
import Data.Bits
import Data.ByteArray (ByteArrayAccess)
import qualified Data.ByteArray as B
import Data.Data

import Crypto.Hash
import Crypto.Number.ModArithmetic (inverse)
import Crypto.PubKey.ECC.Prim
import Crypto.PubKey.ECC.Types
import Crypto.PubKey.Internal (dsaTruncHashDigest, getHashAlg, rfc6979Nonce)
import Crypto.Random.Types

-- | Represent a ECDSA signature namely R and S.
data Signature = Signature
    { sign_r :: Integer
    -- ^ ECDSA r
    , sign_s :: Integer
    -- ^ ECDSA s
    }
    deriving (Show, Read, Eq, Data)

-- | ECDSA signature with public key recovery information.
data ExtendedSignature = ExtendedSignature
    { index :: Integer
    -- ^ Index of the X coordinate
    , parity :: Bool
    -- ^ Parity of the Y coordinate
    , signature :: Signature
    -- ^ Inner signature
    }
    deriving (Show, Read, Eq, Data)

-- | ECDSA Private Key.
data PrivateKey = PrivateKey
    { private_curve :: Curve
    , private_d :: PrivateNumber
    }
    deriving (Read, Eq, Data)

-- | The curve is shown; @private_d@ is not.  Use
-- 'Crypto.Debug.debugShow' to see it.
instance Show PrivateKey where
    showsPrec d k =
        showParen (d > 10) $
            showString "PrivateKey {private_curve = "
                . shows (private_curve k)
                . showString ", private_d = <secret>}"

instance DebugShow PrivateKey where
    debugShow k =
        showString "PrivateKey {private_curve = "
            . shows (private_curve k)
            . showString ", private_d = "
            . shows (private_d k)
            . showChar '}'
            $ ""

-- | ECDSA Public Key.
data PublicKey = PublicKey
    { public_curve :: Curve
    , public_q :: PublicPoint
    }
    deriving (Show, Read, Eq, Data)

-- | ECDSA Key Pair.
data KeyPair = KeyPair Curve PublicPoint PrivateNumber
    deriving (Read, Eq, Data)

instance Show KeyPair where
    showsPrec d (KeyPair c q _) =
        showParen (d > 10) $
            showString "KeyPair "
                . showsPrec 11 c
                . showChar ' '
                . showsPrec 11 q
                . showString " <secret>"

instance DebugShow KeyPair where
    debugShow (KeyPair c q x) =
        showString "KeyPair "
            . showsPrec 11 c
            . showChar ' '
            . showsPrec 11 q
            . showChar ' '
            . showsPrec 11 x
            $ ""

-- | Public key of a ECDSA Key pair.
toPublicKey :: KeyPair -> PublicKey
toPublicKey (KeyPair curve pub _) = PublicKey curve pub

-- | Private key of a ECDSA Key pair.
toPrivateKey :: KeyPair -> PrivateKey
toPrivateKey (KeyPair curve _ priv) = PrivateKey curve priv

-- | Sign digest using the private key and an explicit k number.
--
-- /WARNING:/ Vulnerable to timing attacks.
signExtendedDigestWith
    :: HashAlgorithm hash
    => Integer
    -- ^ k random number
    -> PrivateKey
    -- ^ private key
    -> Digest hash
    -- ^ digest to sign
    -> Maybe ExtendedSignature
signExtendedDigestWith k (PrivateKey curve d) digest = do
    let z = dsaTruncHashDigest digest n
        CurveCommon _ _ g n _ = common_curve curve
    (i, r, p) <- pointDecompose curve $ pointMul curve k g
    kInv <- scalarInverse curve k
    -- kInv and d are secret, so the arithmetic that mixes them goes through
    -- the curve's own, which on P-256 is the C implementation's
    let s = scalarMul curve kInv (scalarAdd curve z (scalarMul curve r d))
    when (r == 0 || s == 0) Nothing
    return $
        if s <= n `unsafeShiftR` 1
            then ExtendedSignature i p $ Signature r s
            else ExtendedSignature i (not p) $ Signature r (n - s)

-- | Sign digest using the private key and an explicit k number.
--
-- /WARNING:/ Vulnerable to timing attacks.
signDigestWith
    :: HashAlgorithm hash
    => Integer
    -- ^ k random number
    -> PrivateKey
    -- ^ private key
    -> Digest hash
    -- ^ digest to sign
    -> Maybe Signature
signDigestWith k pk digest = signature <$> signExtendedDigestWith k pk digest

-- | Sign message using the private key and an explicit k number.
--
-- /WARNING:/ Vulnerable to timing attacks.
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 = signDigestWith k pk (hashWith hashAlg msg)

-- | Sign digest using the private key.
--
-- The nonce is hedged: RFC 6979's, from the private key and the digest,
-- with 32 random bytes added as in its section 3.6.  Repeated randomness
-- then repeats a nonce only for the same digest, which gives away nothing.
--
-- /WARNING:/ Vulnerable to timing attacks.
signExtendedDigest
    :: (HashAlgorithm hash, MonadRandom m)
    => PrivateKey -> Digest hash -> m ExtendedSignature
signExtendedDigest pk@(PrivateKey curve key) digest = do
    extra <- getRandomBytes 32
    return $
        rfc6979Nonce (getHashAlg digest) n key digest extra $ \k ->
            signExtendedDigestWith k pk digest
  where
    n = ecc_n $ common_curve curve

-- | Sign digest using the private key.
--
-- /WARNING:/ Vulnerable to timing attacks.
signDigest
    :: (HashAlgorithm hash, MonadRandom m)
    => PrivateKey -> Digest hash -> m Signature
signDigest pk digest = signature <$> signExtendedDigest pk digest

-- | Sign message using the private key.
--
-- /WARNING:/ Vulnerable to timing attacks.
sign
    :: (ByteArrayAccess msg, HashAlgorithm hash, MonadRandom m)
    => PrivateKey -> hash -> msg -> m Signature
sign pk hashAlg msg = signDigest pk (hashWith hashAlg msg)

-- | Verify a digest using the public key.
verifyDigest
    :: HashAlgorithm hash => PublicKey -> Signature -> Digest hash -> Bool
verifyDigest (PublicKey _ PointO) _ _ = False
verifyDigest pk@(PublicKey curve q) (Signature r s) digest
    | r < 1 || r >= n || s < 1 || s >= n = False
    | otherwise = maybe False (r ==) $ do
        w <- inverse s n
        let z = dsaTruncHashDigest digest n
            u1 = z * w `mod` n
            u2 = r * w `mod` n
            x = pointAddTwoMuls curve u1 g u2 q
        case x of
            PointO -> Nothing
            Point x1 _ -> return $ x1 `mod` n
  where
    n = ecc_n cc
    g = ecc_g cc
    cc = common_curve $ public_curve pk

-- | Verify a bytestring using the public key.
verify
    :: (ByteArrayAccess msg, HashAlgorithm hash)
    => hash -> PublicKey -> Signature -> msg -> Bool
verify hashAlg pk sig msg = verifyDigest pk sig (hashWith hashAlg msg)

-- | Recover the public key from an extended signature and a digest.
recoverDigest
    :: HashAlgorithm hash
    => Curve -> ExtendedSignature -> Digest hash -> Maybe PublicKey
recoverDigest curve (ExtendedSignature i p (Signature r s)) digest = do
    let CurveCommon _ _ g n _ = common_curve curve
    -- SEC 1 4.1.6 takes r and s in [1, n-1], as verify does
    guard (r > 0 && r < n && s > 0 && s < n && i >= 0)
    let z = dsaTruncHashDigest digest n
    w <- inverse r n
    c <- pointCompose curve i r p
    let q = pointAddTwoMuls curve (s * w) c (negate $ z * w) g
    guard (not (isPointAtInfinity q))
    pure $ PublicKey curve q

-- | Recover the public key from an extended signature and a message.
recover
    :: (ByteArrayAccess msg, HashAlgorithm hash)
    => hash -> Curve -> ExtendedSignature -> msg -> Maybe PublicKey
recover hashAlg curve sig msg = recoverDigest curve sig $ hashWith hashAlg msg

-- | Deterministic nonce generation according to RFC 6979.
-- Allows using different hash algorithms for the HMAC-based DRG and the message digest.
deterministicNonce
    :: (HashAlgorithm hashDRG, HashAlgorithm hashDigest)
    => hashDRG -> PrivateKey -> Digest hashDigest -> (Integer -> Maybe a) -> a
deterministicNonce alg (PrivateKey curve key) digest =
    rfc6979Nonce alg n key digest B.empty
  where
    n = ecc_n $ common_curve curve