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
|
{-# LANGUAGE DeriveDataTypeable #-}
-- |
-- Module : Crypto.PubKey.Rabin.Modified
-- License : BSD-style
-- Maintainer : Carlos Rodriguez-Vega <crodveg@yahoo.es>
-- Stability : experimental
-- Portability : unknown
--
-- Modified-Rabin public-key digital signature algorithm.
-- See algorithm 11.30 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
module Crypto.PubKey.Rabin.Modified (
PublicKey (..),
PrivateKey (..),
generate,
sign,
verify,
) where
import Data.ByteString
import Data.Data
import Crypto.Hash
import Crypto.Number.ModArithmetic (expSafe, jacobi)
import Crypto.Number.Serialize (os2ip)
import Crypto.PubKey.Rabin.Types
import Crypto.Random.Types
-- | Represent a Modified-Rabin public key.
data PublicKey = PublicKey
{ public_size :: Int
-- ^ size of key in bytes
, public_n :: Integer
-- ^ public p*q
}
deriving (Show, Read, Eq, Data)
-- | Represent a Modified-Rabin private key.
data PrivateKey = PrivateKey
{ private_pub :: PublicKey
, private_p :: Integer
-- ^ p prime number
, private_q :: Integer
-- ^ q prime number
, private_d :: Integer
}
deriving (Show, Read, Eq, Data)
-- | Generate a pair of (private, public) key of size in bytes.
-- Prime p is congruent 3 mod 8 and prime q is congruent 7 mod 8.
generate
:: MonadRandom m
=> Int
-> m (PublicKey, PrivateKey)
generate size = do
(p, q) <- generatePrimes size (\p -> p `mod` 8 == 3) (\q -> q `mod` 8 == 7)
return $ generateKeys p q
where
generateKeys p q =
let n = p * q
d = (n - p - q + 5) `div` 8
publicKey =
PublicKey
{ public_size = size
, public_n = n
}
privateKey =
PrivateKey
{ private_pub = publicKey
, private_p = p
, private_q = q
, private_d = d
}
in (publicKey, privateKey)
-- | Sign message using hash algorithm and private key.
sign
:: HashAlgorithm hash
=> PrivateKey
-- ^ private key
-> hash
-- ^ hash function
-> ByteString
-- ^ message to sign
-> Either Error Integer
sign pk hashAlg m =
let d = private_d pk
n = public_n $ private_pub pk
h = os2ip $ hashWith hashAlg m
limit = (n - 6) `div` 16
in if h > limit
then Left MessageTooLong
else
let h' = 16 * h + 6
in case jacobi h' n of
Just 1 -> Right $ expSafe h' d n
Just (-1) -> Right $ expSafe (h' `div` 2) d n
_ -> Left InvalidParameters
-- | Verify signature using hash algorithm and public key.
verify
:: HashAlgorithm hash
=> PublicKey
-- ^ public key
-> hash
-- ^ hash function
-> ByteString
-- ^ message
-> Integer
-- ^ signature
-> Bool
verify pk hashAlg m s =
let n = public_n pk
h = os2ip $ hashWith hashAlg m
s' = expSafe s 2 n
s'' = case s' `mod` 8 of
6 -> s'
3 -> 2 * s'
7 -> n - s'
2 -> 2 * (n - s')
_ -> 0
in case s'' `mod` 16 of
6 ->
let h' = (s'' - 6) `div` 16
in h' == h
_ -> False
|
