    -- |
    -- Module      : Crypto.PubKey.ElGamal
    -- License     : BSD-style
    -- Maintainer  : Vincent Hanquez <vincent@snarc.org>
    -- Stability   : experimental
    -- Portability : Good
    --
    -- This module is a work in progress. do not use:
    -- it might eat your dog, your data or even both.
    --
    -- TODO: provide a mapping between integer and ciphertext
    --       generate numbers correctly
    --
    module Crypto.PubKey.ElGamal
        ( Params
        , PublicNumber
        , PrivateNumber
        , EphemeralKey(..)
        , SharedKey
        , Signature
        -- * generation
        , generatePrivate
        , generatePublic
        -- * encryption and decryption with no scheme
        , encryptWith
        , encrypt
        , decrypt
        -- * signature primitives
        , signWith
        , sign
        -- * verification primitives
        , verify
        ) where

    import Data.ByteString (ByteString)
    import Crypto.Number.ModArithmetic (expSafe, expFast, inverse)
    import Crypto.Number.Generate (generateMax)
    import Crypto.Number.Serialize (os2ip)
    import Crypto.Number.Basic (gcde_binary)
    import Crypto.Types.PubKey.DH
    import Crypto.Random.API
    import Control.Arrow (first)
    import Data.Maybe (fromJust)
    import Crypto.PubKey.HashDescr (HashFunction)

    -- | ElGamal Signature
    data Signature = Signature (Integer, Integer)

    -- | ElGamal Ephemeral key. also called Temporary key.
    newtype EphemeralKey = EphemeralKey Integer

    -- | generate a private number with no specific property
    -- this number is usually called a and need to be between
    -- 0 and q (order of the group G).
    --
    generatePrivate :: CPRG g => g -> Integer -> (PrivateNumber, g)
    generatePrivate :: g -> Integer -> (PrivateNumber, g)
    generatePrivate rng :: g
    rng q :: Integer
    q = (Integer -> PrivateNumber) -> (Integer, g) -> (PrivateNumber, g)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first Integer -> PrivateNumber
    PrivateNumber ((Integer, g) -> (PrivateNumber, g))
    -> (Integer, g) -> (PrivateNumber, g)
    forall a b. (a -> b) -> a -> b
    $ g -> Integer -> (Integer, g)
    forall g. CPRG g => g -> Integer -> (Integer, g)
    generateMax g
    rng Integer
    q

    -- | generate an ephemeral key which is a number with no specific property,
    -- and need to be between 0 and q (order of the group G).
    --
    generateEphemeral :: CPRG g => g -> Integer -> (EphemeralKey, g)
    generateEphemeral :: g -> Integer -> (EphemeralKey, g)
    generateEphemeral rng :: g
    rng q :: Integer
    q = (PrivateNumber -> EphemeralKey)
    -> (PrivateNumber, g) -> (EphemeralKey, g)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first PrivateNumber -> EphemeralKey
    toEphemeral ((PrivateNumber, g) -> (EphemeralKey, g))
    -> (PrivateNumber, g) -> (EphemeralKey, g)
    forall a b. (a -> b) -> a -> b
    $ g -> Integer -> (PrivateNumber, g)
    forall g. CPRG g => g -> Integer -> (PrivateNumber, g)
    generatePrivate g
    rng Integer
    q
        where toEphemeral :: PrivateNumber -> EphemeralKey
    toEphemeral (PrivateNumber n :: Integer
    n) = Integer -> EphemeralKey
    EphemeralKey Integer
    n

    -- | generate a public number that is for the other party benefits.
    -- this number is usually called h=g^a
    generatePublic :: Params -> PrivateNumber -> PublicNumber
    generatePublic :: Params -> PrivateNumber -> PublicNumber
    generatePublic (Params p :: Integer
    p g :: Integer
    g) (PrivateNumber a :: Integer
    a) = Integer -> PublicNumber
    PublicNumber (Integer -> PublicNumber) -> Integer -> PublicNumber
    forall a b. (a -> b) -> a -> b
    $ Integer -> Integer -> Integer -> Integer
    expSafe Integer
    g Integer
    a Integer
    p

    -- | encrypt with a specified ephemeral key
    -- do not reuse ephemeral key.
    encryptWith :: EphemeralKey -> Params -> PublicNumber -> Integer -> (Integer,Integer)
    encryptWith :: EphemeralKey
    -> Params -> PublicNumber -> Integer -> (Integer, Integer)
    encryptWith (EphemeralKey b :: Integer
    b) (Params p :: Integer
    p g :: Integer
    g) (PublicNumber h :: Integer
    h) m :: Integer
    m = (Integer
    c1,Integer
    c2)
        where s :: Integer
    s  = Integer -> Integer -> Integer -> Integer
    expSafe Integer
    h Integer
    b Integer
    p
              c1 :: Integer
    c1 = Integer -> Integer -> Integer -> Integer
    expSafe Integer
    g Integer
    b Integer
    p
              c2 :: Integer
    c2 = (Integer
    s Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    m) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    p

    -- | encrypt a message using params and public keys
    -- will generate b (called the ephemeral key)
    encrypt :: CPRG g => g -> Params -> PublicNumber -> Integer -> ((Integer,Integer), g)
    encrypt :: g -> Params -> PublicNumber -> Integer -> ((Integer, Integer), g)
    encrypt rng :: g
    rng params :: Params
    params@(Params p :: Integer
    p _) public :: PublicNumber
    public m :: Integer
    m = (EphemeralKey -> (Integer, Integer))
    -> (EphemeralKey, g) -> ((Integer, Integer), g)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first (\b :: EphemeralKey
    b -> EphemeralKey
    -> Params -> PublicNumber -> Integer -> (Integer, Integer)
    encryptWith EphemeralKey
    b Params
    params PublicNumber
    public Integer
    m) ((EphemeralKey, g) -> ((Integer, Integer), g))
    -> (EphemeralKey, g) -> ((Integer, Integer), g)
    forall a b. (a -> b) -> a -> b
    $ g -> Integer -> (EphemeralKey, g)
    forall g. CPRG g => g -> Integer -> (EphemeralKey, g)
    generateEphemeral g
    rng Integer
    q
        where q :: Integer
    q = Integer
    pInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1 -- p is prime, hence order of the group is p-1

    -- | decrypt message
    decrypt :: Params -> PrivateNumber -> (Integer, Integer) -> Integer
    decrypt :: Params -> PrivateNumber -> (Integer, Integer) -> Integer
    decrypt (Params p :: Integer
    p _) (PrivateNumber a :: Integer
    a) (c1 :: Integer
    c1,c2 :: Integer
    c2) = (Integer
    c2 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    sm1) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    p
        where s :: Integer
    s   = Integer -> Integer -> Integer -> Integer
    expSafe Integer
    c1 Integer
    a Integer
    p
              sm1 :: Integer
    sm1 = Maybe Integer -> Integer
    forall a. HasCallStack => Maybe a -> a
    fromJust (Maybe Integer -> Integer) -> Maybe Integer -> Integer
    forall a b. (a -> b) -> a -> b
    $ Integer -> Integer -> Maybe Integer
    inverse Integer
    s Integer
    p -- always inversible in Zp

    -- | sign a message with an explicit k number
    --
    -- if k is not appropriate, then no signature is returned.
    --
    -- with some appropriate value of k, the signature generation can fail,
    -- and no signature is returned. User of this function need to retry
    -- with a different k value.
    signWith :: Integer         -- ^ random number k, between 0 and p-1 and gcd(k,p-1)=1
             -> Params          -- ^ DH params (p,g)
             -> PrivateNumber   -- ^ DH private key
             -> HashFunction    -- ^ collision resistant hash function
             -> ByteString      -- ^ message to sign
             -> Maybe Signature
    signWith :: Integer
    -> Params
    -> PrivateNumber
    -> HashFunction
    -> ByteString
    -> Maybe Signature
    signWith k :: Integer
    k (Params p :: Integer
    p g :: Integer
    g) (PrivateNumber x :: Integer
    x) hashF :: HashFunction
    hashF msg :: ByteString
    msg
        | Integer
    k Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Integer
    pInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1 Bool -> Bool -> Bool
    || Integer
    d Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > 1 = Maybe Signature
    forall a. Maybe a
    Nothing -- gcd(k,p-1) is not 1
        | Integer
    s Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0            = Maybe Signature
    forall a. Maybe a
    Nothing
        | Bool
    otherwise         = Signature -> Maybe Signature
    forall a. a -> Maybe a
    Just (Signature -> Maybe Signature) -> Signature -> Maybe Signature
    forall a b. (a -> b) -> a -> b
    $ (Integer, Integer) -> Signature
    Signature (Integer
    r,Integer
    s)
        where r :: Integer
    r          = Integer -> Integer -> Integer -> Integer
    expSafe Integer
    g Integer
    k Integer
    p
              h :: Integer
    h          = ByteString -> Integer
    os2ip (ByteString -> Integer) -> ByteString -> Integer
    forall a b. (a -> b) -> a -> b
    $ HashFunction
    hashF ByteString
    msg
              s :: Integer
    s          = ((Integer
    h Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    xInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    *Integer
    r) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    kInv) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` (Integer
    pInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1)
              (kInv :: Integer
    kInv,_,d :: Integer
    d) = Integer -> Integer -> (Integer, Integer, Integer)
    gcde_binary Integer
    k (Integer
    pInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1)

    -- | sign message
    --
    -- This function will generate a random number, however
    -- as the signature might fail, the function will automatically retry
    -- until a proper signature has been created.
    --
    sign :: CPRG g
         => g              -- ^ random number generator
         -> Params         -- ^ DH params (p,g)
         -> PrivateNumber  -- ^ DH private key
         -> HashFunction   -- ^ collision resistant hash function
         -> ByteString     -- ^ message to sign
         -> (Signature, g)
    sign :: g
    -> Params
    -> PrivateNumber
    -> HashFunction
    -> ByteString
    -> (Signature, g)
    sign rng :: g
    rng params :: Params
    params@(Params p :: Integer
    p _) priv :: PrivateNumber
    priv hashF :: HashFunction
    hashF msg :: ByteString
    msg =
        let (k :: Integer
    k, rng' :: g
    rng') = g -> Integer -> (Integer, g)
    forall g. CPRG g => g -> Integer -> (Integer, g)
    generateMax g
    rng (Integer
    pInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1)
         in case Integer
    -> Params
    -> PrivateNumber
    -> HashFunction
    -> ByteString
    -> Maybe Signature
    signWith Integer
    k Params
    params PrivateNumber
    priv HashFunction
    hashF ByteString
    msg of
                 Nothing  -> g
    -> Params
    -> PrivateNumber
    -> HashFunction
    -> ByteString
    -> (Signature, g)
    forall g.
    CPRG g =>
    g
    -> Params
    -> PrivateNumber
    -> HashFunction
    -> ByteString
    -> (Signature, g)
    sign g
    rng' Params
    params PrivateNumber
    priv HashFunction
    hashF ByteString
    msg
                 Just sig :: Signature
    sig -> (Signature
    sig, g
    rng')

    -- | verify a signature
    verify :: Params
           -> PublicNumber
           -> HashFunction
           -> ByteString
           -> Signature
           -> Bool
    verify :: Params
    -> PublicNumber -> HashFunction -> ByteString -> Signature -> Bool
    verify (Params p :: Integer
    p g :: Integer
    g) (PublicNumber y :: Integer
    y) hashF :: HashFunction
    hashF msg :: ByteString
    msg (Signature (r :: Integer
    r,s :: Integer
    s))
        | [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    or [Integer
    r Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= 0,Integer
    r Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Integer
    p,Integer
    s Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= 0,Integer
    s Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    >= (Integer
    pInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1)] = Bool
    False
        | Bool
    otherwise                            = Integer
    lhs Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    rhs
        where h :: Integer
    h   = ByteString -> Integer
    os2ip (ByteString -> Integer) -> ByteString -> Integer
    forall a b. (a -> b) -> a -> b
    $ HashFunction
    hashF ByteString
    msg
              lhs :: Integer
    lhs = Integer -> Integer -> Integer -> Integer
    expFast Integer
    g Integer
    h Integer
    p
              rhs :: Integer
    rhs = (Integer -> Integer -> Integer -> Integer
    expFast Integer
    y Integer
    r Integer
    p Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer -> Integer -> Integer -> Integer
    expFast Integer
    r Integer
    s Integer
    p) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    p