-- |
-- 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