1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
-- |
-- 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 Crypto.Hash
import Crypto.Internal.ByteArray (ByteArrayAccess)
import Crypto.Internal.Imports
import Crypto.Number.Basic (gcde)
import Crypto.Number.Generate (generateMax)
import Crypto.Number.ModArithmetic (expFast, expSafe, inverse)
import Crypto.Number.Serialize (os2ip)
import Crypto.PubKey.DH (
Params (..),
PrivateNumber (..),
PublicNumber (..),
SharedKey (..),
)
import Crypto.Random.Types
import Data.Maybe (fromJust)
-- | ElGamal Signature
data Signature = Signature (Integer, Integer)
-- | ElGamal Ephemeral key. also called Temporary key.
newtype EphemeralKey = EphemeralKey Integer
deriving (NFData)
-- | 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 :: MonadRandom m => Integer -> m PrivateNumber
generatePrivate q = PrivateNumber <$> generateMax 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 :: MonadRandom m => Integer -> m EphemeralKey
generateEphemeral q = toEphemeral <$> generatePrivate q
where
toEphemeral (PrivateNumber n) = EphemeralKey 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 p g _) (PrivateNumber a) = PublicNumber $ expSafe g a p
-- | encrypt with a specified ephemeral key
-- do not reuse ephemeral key.
encryptWith
:: EphemeralKey -> Params -> PublicNumber -> Integer -> (Integer, Integer)
encryptWith (EphemeralKey b) (Params p g _) (PublicNumber h) m = (c1, c2)
where
s = expSafe h b p
c1 = expSafe g b p
c2 = (s * m) `mod` p
-- | encrypt a message using params and public keys
-- will generate b (called the ephemeral key)
encrypt
:: MonadRandom m => Params -> PublicNumber -> Integer -> m (Integer, Integer)
encrypt params@(Params p _ _) public m = (\b -> encryptWith b params public m) <$> generateEphemeral q
where
q = p - 1 -- p is prime, hence order of the group is p-1
-- | decrypt message
decrypt :: Params -> PrivateNumber -> (Integer, Integer) -> Integer
decrypt (Params p _ _) (PrivateNumber a) (c1, c2) = (c2 * sm1) `mod` p
where
s = expSafe c1 a p
sm1 = fromJust $ inverse s 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
:: (ByteArrayAccess msg, HashAlgorithm hash)
=> Integer
-- ^ random number k, between 0 and p-1 and gcd(k,p-1)=1
-> Params
-- ^ DH params (p,g)
-> PrivateNumber
-- ^ DH private key
-> hash
-- ^ collision resistant hash algorithm
-> msg
-- ^ message to sign
-> Maybe Signature
signWith k (Params p g _) (PrivateNumber x) hashAlg msg
| k >= p - 1 || d > 1 = Nothing -- gcd(k,p-1) is not 1
| s == 0 = Nothing
| otherwise = Just $ Signature (r, s)
where
r = expSafe g k p
h = os2ip $ hashWith hashAlg msg
s = ((h - x * r) * kInv) `mod` (p - 1)
(kInv, _, d) = gcde k (p - 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
:: (ByteArrayAccess msg, HashAlgorithm hash, MonadRandom m)
=> Params
-- ^ DH params (p,g)
-> PrivateNumber
-- ^ DH private key
-> hash
-- ^ collision resistant hash algorithm
-> msg
-- ^ message to sign
-> m Signature
sign params@(Params p _ _) priv hashAlg msg = do
k <- generateMax (p - 1)
case signWith k params priv hashAlg msg of
Nothing -> sign params priv hashAlg msg
Just sig -> return sig
-- | verify a signature
verify
:: (ByteArrayAccess msg, HashAlgorithm hash)
=> Params
-> PublicNumber
-> hash
-> msg
-> Signature
-> Bool
verify (Params p g _) (PublicNumber y) hashAlg msg (Signature (r, s))
| or [r <= 0, r >= p, s <= 0, s >= (p - 1)] = False
| otherwise = lhs == rhs
where
h = os2ip $ hashWith hashAlg msg
lhs = expFast g h p
rhs = (expFast y r p * expFast r s p) `mod` p
|
