1-- |
2-- Module      : Crypto.PubKey.ElGamal
3-- License     : BSD-style
4-- Maintainer  : Vincent Hanquez <vincent@snarc.org>
5-- Stability   : experimental
6-- Portability : Good
7--
8-- This module is a work in progress. do not use:
9-- it might eat your dog, your data or even both.
10--
11-- TODO: provide a mapping between integer and ciphertext
12--       generate numbers correctly
13--
14{-# LANGUAGE GeneralizedNewtypeDeriving #-}
15module Crypto.PubKey.ElGamal
16    ( Params
17    , PublicNumber
18    , PrivateNumber
19    , EphemeralKey(..)
20    , SharedKey
21    , Signature
22    -- * Generation
23    , generatePrivate
24    , generatePublic
25    -- * Encryption and decryption with no scheme
26    , encryptWith
27    , encrypt
28    , decrypt
29    -- * Signature primitives
30    , signWith
31    , sign
32    -- * Verification primitives
33    , verify
34    ) where
35
36import Data.Maybe (fromJust)
37import Crypto.Internal.Imports
38import Crypto.Internal.ByteArray (ByteArrayAccess)
39import Crypto.Number.ModArithmetic (expSafe, expFast, inverse)
40import Crypto.Number.Generate (generateMax)
41import Crypto.Number.Serialize (os2ip)
42import Crypto.Number.Basic (gcde)
43import Crypto.Random.Types
44import Crypto.PubKey.DH (PrivateNumber(..), PublicNumber(..), Params(..), SharedKey(..))
45import Crypto.Hash
46
47-- | ElGamal Signature
48data Signature = Signature (Integer, Integer)
49
50-- | ElGamal Ephemeral key. also called Temporary key.
51newtype EphemeralKey = EphemeralKey Integer
52    deriving (NFData)
53
54-- | generate a private number with no specific property
55-- this number is usually called a and need to be between
56-- 0 and q (order of the group G).
57--
58generatePrivate :: MonadRandom m => Integer -> m PrivateNumber
59generatePrivate q = PrivateNumber <$> generateMax q
60
61-- | generate an ephemeral key which is a number with no specific property,
62-- and need to be between 0 and q (order of the group G).
63--
64generateEphemeral :: MonadRandom m => Integer -> m EphemeralKey
65generateEphemeral q = toEphemeral <$> generatePrivate q
66    where toEphemeral (PrivateNumber n) = EphemeralKey n
67
68-- | generate a public number that is for the other party benefits.
69-- this number is usually called h=g^a
70generatePublic :: Params -> PrivateNumber -> PublicNumber
71generatePublic (Params p g _) (PrivateNumber a) = PublicNumber $ expSafe g a p
72
73-- | encrypt with a specified ephemeral key
74-- do not reuse ephemeral key.
75encryptWith :: EphemeralKey -> Params -> PublicNumber -> Integer -> (Integer,Integer)
76encryptWith (EphemeralKey b) (Params p g _) (PublicNumber h) m = (c1,c2)
77    where s  = expSafe h b p
78          c1 = expSafe g b p
79          c2 = (s * m) `mod` p
80
81-- | encrypt a message using params and public keys
82-- will generate b (called the ephemeral key)
83encrypt :: MonadRandom m => Params -> PublicNumber -> Integer -> m (Integer,Integer)
84encrypt params@(Params p _ _) public m = (\b -> encryptWith b params public m) <$> generateEphemeral q
85    where q = p-1 -- p is prime, hence order of the group is p-1
86
87-- | decrypt message
88decrypt :: Params -> PrivateNumber -> (Integer, Integer) -> Integer
89decrypt (Params p _ _) (PrivateNumber a) (c1,c2) = (c2 * sm1) `mod` p
90    where s   = expSafe c1 a p
91          sm1 = fromJust $ inverse s p -- always inversible in Zp
92
93-- | sign a message with an explicit k number
94--
95-- if k is not appropriate, then no signature is returned.
96--
97-- with some appropriate value of k, the signature generation can fail,
98-- and no signature is returned. User of this function need to retry
99-- with a different k value.
100signWith :: (ByteArrayAccess msg, HashAlgorithm hash)
101         => Integer         -- ^ random number k, between 0 and p-1 and gcd(k,p-1)=1
102         -> Params          -- ^ DH params (p,g)
103         -> PrivateNumber   -- ^ DH private key
104         -> hash            -- ^ collision resistant hash algorithm
105         -> msg             -- ^ message to sign
106         -> Maybe Signature
107signWith k (Params p g _) (PrivateNumber x) hashAlg msg
108    | k >= p-1 || d > 1 = Nothing -- gcd(k,p-1) is not 1
109    | s == 0            = Nothing
110    | otherwise         = Just $ Signature (r,s)
111    where r          = expSafe g k p
112          h          = os2ip $ hashWith hashAlg msg
113          s          = ((h - x*r) * kInv) `mod` (p-1)
114          (kInv,_,d) = gcde k (p-1)
115
116-- | sign message
117--
118-- This function will generate a random number, however
119-- as the signature might fail, the function will automatically retry
120-- until a proper signature has been created.
121--
122sign :: (ByteArrayAccess msg, HashAlgorithm hash, MonadRandom m)
123     => Params         -- ^ DH params (p,g)
124     -> PrivateNumber  -- ^ DH private key
125     -> hash           -- ^ collision resistant hash algorithm
126     -> msg            -- ^ message to sign
127     -> m Signature
128sign params@(Params p _ _) priv hashAlg msg = do
129    k <- generateMax (p-1)
130    case signWith k params priv hashAlg msg of
131        Nothing  -> sign params priv hashAlg msg
132        Just sig -> return sig
133
134-- | verify a signature
135verify :: (ByteArrayAccess msg, HashAlgorithm hash)
136       => Params
137       -> PublicNumber
138       -> hash
139       -> msg
140       -> Signature
141       -> Bool
142verify (Params p g _) (PublicNumber y) hashAlg msg (Signature (r,s))
143    | or [r <= 0,r >= p,s <= 0,s >= (p-1)] = False
144    | otherwise                            = lhs == rhs
145    where h   = os2ip $ hashWith hashAlg msg
146          lhs = expFast g h p
147          rhs = (expFast y r p * expFast r s p) `mod` p
148