-- |
-- Module      : Crypto.PubKey.Rabin.Basic
-- License     : BSD-style
-- Maintainer  : Carlos Rodriguez-Vega <crodveg@yahoo.es>
-- Stability   : experimental
-- Portability : unknown
--
-- Rabin cryptosystem for public-key cryptography and digital signature.
--
{-# LANGUAGE DeriveDataTypeable #-}
module Crypto.PubKey.Rabin.Basic
    ( PublicKey(..)
    , PrivateKey(..)
    , Signature(..)
    , generate
    , encrypt
    , encryptWithSeed
    , decrypt
    , sign
    , signWith
    , verify
    ) where

import           Data.ByteString (ByteString)
import qualified Data.ByteString as B
import           Data.Data
import           Data.Either (rights)

import           Crypto.Hash
import           Crypto.Number.Basic (gcde, numBytes)
import           Crypto.Number.ModArithmetic (expSafe, jacobi)
import           Crypto.Number.Serialize (i2osp, i2ospOf_, os2ip)
import           Crypto.PubKey.Rabin.OAEP 
import           Crypto.PubKey.Rabin.Types
import           Crypto.Random (MonadRandom, getRandomBytes)

-- | Represent a Rabin public key.
data PublicKey = PublicKey
    { PublicKey -> Int
public_size :: Int      -- ^ size of key in bytes
    , PublicKey -> Integer
public_n    :: Integer  -- ^ public p*q
    } deriving (Int -> PublicKey -> ShowS
[PublicKey] -> ShowS
PublicKey -> String
(Int -> PublicKey -> ShowS)
-> (PublicKey -> String)
-> ([PublicKey] -> ShowS)
-> Show PublicKey
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> PublicKey -> ShowS
showsPrec :: Int -> PublicKey -> ShowS
$cshow :: PublicKey -> String
show :: PublicKey -> String
$cshowList :: [PublicKey] -> ShowS
showList :: [PublicKey] -> ShowS
Show, ReadPrec [PublicKey]
ReadPrec PublicKey
Int -> ReadS PublicKey
ReadS [PublicKey]
(Int -> ReadS PublicKey)
-> ReadS [PublicKey]
-> ReadPrec PublicKey
-> ReadPrec [PublicKey]
-> Read PublicKey
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS PublicKey
readsPrec :: Int -> ReadS PublicKey
$creadList :: ReadS [PublicKey]
readList :: ReadS [PublicKey]
$creadPrec :: ReadPrec PublicKey
readPrec :: ReadPrec PublicKey
$creadListPrec :: ReadPrec [PublicKey]
readListPrec :: ReadPrec [PublicKey]
Read, PublicKey -> PublicKey -> Bool
(PublicKey -> PublicKey -> Bool)
-> (PublicKey -> PublicKey -> Bool) -> Eq PublicKey
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: PublicKey -> PublicKey -> Bool
== :: PublicKey -> PublicKey -> Bool
$c/= :: PublicKey -> PublicKey -> Bool
/= :: PublicKey -> PublicKey -> Bool
Eq, Typeable PublicKey
Typeable PublicKey =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> PublicKey -> c PublicKey)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c PublicKey)
-> (PublicKey -> Constr)
-> (PublicKey -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c PublicKey))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PublicKey))
-> ((forall b. Data b => b -> b) -> PublicKey -> PublicKey)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> PublicKey -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> PublicKey -> r)
-> (forall u. (forall d. Data d => d -> u) -> PublicKey -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> PublicKey -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> PublicKey -> m PublicKey)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> PublicKey -> m PublicKey)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> PublicKey -> m PublicKey)
-> Data PublicKey
PublicKey -> Constr
PublicKey -> DataType
(forall b. Data b => b -> b) -> PublicKey -> PublicKey
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> PublicKey -> u
forall u. (forall d. Data d => d -> u) -> PublicKey -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PublicKey -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PublicKey -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PublicKey
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PublicKey -> c PublicKey
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PublicKey)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PublicKey)
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PublicKey -> c PublicKey
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PublicKey -> c PublicKey
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PublicKey
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PublicKey
$ctoConstr :: PublicKey -> Constr
toConstr :: PublicKey -> Constr
$cdataTypeOf :: PublicKey -> DataType
dataTypeOf :: PublicKey -> DataType
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PublicKey)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PublicKey)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PublicKey)
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PublicKey)
$cgmapT :: (forall b. Data b => b -> b) -> PublicKey -> PublicKey
gmapT :: (forall b. Data b => b -> b) -> PublicKey -> PublicKey
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PublicKey -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PublicKey -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PublicKey -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PublicKey -> r
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> PublicKey -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> PublicKey -> [u]
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PublicKey -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PublicKey -> u
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PublicKey -> m PublicKey
Data)

-- | Represent a Rabin private key.
data PrivateKey = PrivateKey
    { PrivateKey -> PublicKey
private_pub :: PublicKey
    , PrivateKey -> Integer
private_p   :: Integer   -- ^ p prime number
    , PrivateKey -> Integer
private_q   :: Integer   -- ^ q prime number
    , PrivateKey -> Integer
private_a   :: Integer
    , PrivateKey -> Integer
private_b   :: Integer
    } deriving (Int -> PrivateKey -> ShowS
[PrivateKey] -> ShowS
PrivateKey -> String
(Int -> PrivateKey -> ShowS)
-> (PrivateKey -> String)
-> ([PrivateKey] -> ShowS)
-> Show PrivateKey
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> PrivateKey -> ShowS
showsPrec :: Int -> PrivateKey -> ShowS
$cshow :: PrivateKey -> String
show :: PrivateKey -> String
$cshowList :: [PrivateKey] -> ShowS
showList :: [PrivateKey] -> ShowS
Show, ReadPrec [PrivateKey]
ReadPrec PrivateKey
Int -> ReadS PrivateKey
ReadS [PrivateKey]
(Int -> ReadS PrivateKey)
-> ReadS [PrivateKey]
-> ReadPrec PrivateKey
-> ReadPrec [PrivateKey]
-> Read PrivateKey
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS PrivateKey
readsPrec :: Int -> ReadS PrivateKey
$creadList :: ReadS [PrivateKey]
readList :: ReadS [PrivateKey]
$creadPrec :: ReadPrec PrivateKey
readPrec :: ReadPrec PrivateKey
$creadListPrec :: ReadPrec [PrivateKey]
readListPrec :: ReadPrec [PrivateKey]
Read, PrivateKey -> PrivateKey -> Bool
(PrivateKey -> PrivateKey -> Bool)
-> (PrivateKey -> PrivateKey -> Bool) -> Eq PrivateKey
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: PrivateKey -> PrivateKey -> Bool
== :: PrivateKey -> PrivateKey -> Bool
$c/= :: PrivateKey -> PrivateKey -> Bool
/= :: PrivateKey -> PrivateKey -> Bool
Eq, Typeable PrivateKey
Typeable PrivateKey =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> PrivateKey -> c PrivateKey)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c PrivateKey)
-> (PrivateKey -> Constr)
-> (PrivateKey -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c PrivateKey))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c PrivateKey))
-> ((forall b. Data b => b -> b) -> PrivateKey -> PrivateKey)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> PrivateKey -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> PrivateKey -> r)
-> (forall u. (forall d. Data d => d -> u) -> PrivateKey -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> PrivateKey -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey)
-> Data PrivateKey
PrivateKey -> Constr
PrivateKey -> DataType
(forall b. Data b => b -> b) -> PrivateKey -> PrivateKey
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> PrivateKey -> u
forall u. (forall d. Data d => d -> u) -> PrivateKey -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PrivateKey -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PrivateKey -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PrivateKey
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrivateKey -> c PrivateKey
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PrivateKey)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PrivateKey)
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrivateKey -> c PrivateKey
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrivateKey -> c PrivateKey
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PrivateKey
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PrivateKey
$ctoConstr :: PrivateKey -> Constr
toConstr :: PrivateKey -> Constr
$cdataTypeOf :: PrivateKey -> DataType
dataTypeOf :: PrivateKey -> DataType
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PrivateKey)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PrivateKey)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PrivateKey)
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c PrivateKey)
$cgmapT :: (forall b. Data b => b -> b) -> PrivateKey -> PrivateKey
gmapT :: (forall b. Data b => b -> b) -> PrivateKey -> PrivateKey
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PrivateKey -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PrivateKey -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PrivateKey -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PrivateKey -> r
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> PrivateKey -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> PrivateKey -> [u]
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PrivateKey -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PrivateKey -> u
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrivateKey -> m PrivateKey
Data)

-- | Rabin Signature.
data Signature = Signature (Integer, Integer) deriving (Int -> Signature -> ShowS
[Signature] -> ShowS
Signature -> String
(Int -> Signature -> ShowS)
-> (Signature -> String)
-> ([Signature] -> ShowS)
-> Show Signature
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Signature -> ShowS
showsPrec :: Int -> Signature -> ShowS
$cshow :: Signature -> String
show :: Signature -> String
$cshowList :: [Signature] -> ShowS
showList :: [Signature] -> ShowS
Show, ReadPrec [Signature]
ReadPrec Signature
Int -> ReadS Signature
ReadS [Signature]
(Int -> ReadS Signature)
-> ReadS [Signature]
-> ReadPrec Signature
-> ReadPrec [Signature]
-> Read Signature
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS Signature
readsPrec :: Int -> ReadS Signature
$creadList :: ReadS [Signature]
readList :: ReadS [Signature]
$creadPrec :: ReadPrec Signature
readPrec :: ReadPrec Signature
$creadListPrec :: ReadPrec [Signature]
readListPrec :: ReadPrec [Signature]
Read, Signature -> Signature -> Bool
(Signature -> Signature -> Bool)
-> (Signature -> Signature -> Bool) -> Eq Signature
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Signature -> Signature -> Bool
== :: Signature -> Signature -> Bool
$c/= :: Signature -> Signature -> Bool
/= :: Signature -> Signature -> Bool
Eq, Typeable Signature
Typeable Signature =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> Signature -> c Signature)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c Signature)
-> (Signature -> Constr)
-> (Signature -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c Signature))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Signature))
-> ((forall b. Data b => b -> b) -> Signature -> Signature)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Signature -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Signature -> r)
-> (forall u. (forall d. Data d => d -> u) -> Signature -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> Signature -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Signature -> m Signature)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Signature -> m Signature)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Signature -> m Signature)
-> Data Signature
Signature -> Constr
Signature -> DataType
(forall b. Data b => b -> b) -> Signature -> Signature
forall a.
Typeable a =>
(forall (c :: * -> *).
 (forall d b. Data d => c (d -> b) -> d -> c b)
 -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Signature -> u
forall u. (forall d. Data d => d -> u) -> Signature -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Signature -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Signature -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Signature
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Signature -> c Signature
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Signature)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Signature)
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Signature -> c Signature
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Signature -> c Signature
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Signature
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Signature
$ctoConstr :: Signature -> Constr
toConstr :: Signature -> Constr
$cdataTypeOf :: Signature -> DataType
dataTypeOf :: Signature -> DataType
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Signature)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c Signature)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Signature)
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Signature)
$cgmapT :: (forall b. Data b => b -> b) -> Signature -> Signature
gmapT :: (forall b. Data b => b -> b) -> Signature -> Signature
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Signature -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Signature -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Signature -> r
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Signature -> r
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> Signature -> [u]
gmapQ :: forall u. (forall d. Data d => d -> u) -> Signature -> [u]
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Signature -> u
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Signature -> u
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Signature -> m Signature
Data)

-- | Generate a pair of (private, public) key of size in bytes.
-- Primes p and q are both congruent 3 mod 4.
--
-- See algorithm 8.11 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
generate :: MonadRandom m
         => Int
         -> m (PublicKey, PrivateKey)
generate :: forall (m :: * -> *).
MonadRandom m =>
Int -> m (PublicKey, PrivateKey)
generate Int
size = do
    (Integer
p, Integer
q) <- Int -> PrimeCondition -> PrimeCondition -> m (Integer, Integer)
forall (m :: * -> *).
MonadRandom m =>
Int -> PrimeCondition -> PrimeCondition -> m (Integer, Integer)
generatePrimes Int
size (\Integer
p -> Integer
p Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> PrimeCondition
forall a. Eq a => a -> a -> Bool
== Integer
3) (\Integer
q -> Integer
q Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> PrimeCondition
forall a. Eq a => a -> a -> Bool
== Integer
3)
    (PublicKey, PrivateKey) -> m (PublicKey, PrivateKey)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((PublicKey, PrivateKey) -> m (PublicKey, PrivateKey))
-> (PublicKey, PrivateKey) -> m (PublicKey, PrivateKey)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> (PublicKey, PrivateKey)
generateKeys Integer
p Integer
q
  where 
    generateKeys :: Integer -> Integer -> (PublicKey, PrivateKey)
generateKeys Integer
p Integer
q =
        let n :: Integer
n = Integer
pInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q
            (Integer
a, Integer
b, Integer
_) = Integer -> Integer -> (Integer, Integer, Integer)
gcde Integer
p Integer
q 
            publicKey :: PublicKey
publicKey = PublicKey { public_size :: Int
public_size = Int
size
                                    , public_n :: Integer
public_n    = Integer
n }
            privateKey :: PrivateKey
privateKey = PrivateKey { private_pub :: PublicKey
private_pub = PublicKey
publicKey
                                    , private_p :: Integer
private_p   = Integer
p
                                    , private_q :: Integer
private_q   = Integer
q
                                    , private_a :: Integer
private_a   = Integer
a
                                    , private_b :: Integer
private_b   = Integer
b }
            in (PublicKey
publicKey, PrivateKey
privateKey)

-- | Encrypt plaintext using public key an a predefined OAEP seed.
--
-- See algorithm 8.11 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
encryptWithSeed :: HashAlgorithm hash
                => ByteString                               -- ^ Seed
                -> OAEPParams hash ByteString ByteString    -- ^ OAEP padding
                -> PublicKey                                -- ^ public key
                -> ByteString                               -- ^ plaintext
                -> Either Error ByteString
encryptWithSeed :: forall hash.
HashAlgorithm hash =>
ByteString
-> OAEPParams hash ByteString ByteString
-> PublicKey
-> ByteString
-> Either Error ByteString
encryptWithSeed ByteString
seed OAEPParams hash ByteString ByteString
oaep PublicKey
pk ByteString
m =
    let n :: Integer
n  = PublicKey -> Integer
public_n PublicKey
pk
        k :: Int
k  = Integer -> Int
numBytes Integer
n
     in do
        ByteString
m' <- ByteString
-> OAEPParams hash ByteString ByteString
-> Int
-> ByteString
-> Either Error ByteString
forall hash.
HashAlgorithm hash =>
ByteString
-> OAEPParams hash ByteString ByteString
-> Int
-> ByteString
-> Either Error ByteString
pad ByteString
seed OAEPParams hash ByteString ByteString
oaep Int
k ByteString
m
        let m'' :: Integer
m'' = ByteString -> Integer
forall ba. ByteArrayAccess ba => ba -> Integer
os2ip ByteString
m'
        ByteString -> Either Error ByteString
forall a. a -> Either Error a
forall (m :: * -> *) a. Monad m => a -> m a
return (ByteString -> Either Error ByteString)
-> ByteString -> Either Error ByteString
forall a b. (a -> b) -> a -> b
$ Integer -> ByteString
forall ba. ByteArray ba => Integer -> ba
i2osp (Integer -> ByteString) -> Integer -> ByteString
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Integer -> Integer
expSafe Integer
m'' Integer
2 Integer
n

-- | Encrypt plaintext using public key.
encrypt :: (HashAlgorithm hash, MonadRandom m)
        => OAEPParams hash ByteString ByteString    -- ^ OAEP padding parameters
        -> PublicKey                                -- ^ public key
        -> ByteString                               -- ^ plaintext 
        -> m (Either Error ByteString)
encrypt :: forall hash (m :: * -> *).
(HashAlgorithm hash, MonadRandom m) =>
OAEPParams hash ByteString ByteString
-> PublicKey -> ByteString -> m (Either Error ByteString)
encrypt OAEPParams hash ByteString ByteString
oaep PublicKey
pk ByteString
m = do
    ByteString
seed <- Int -> m ByteString
forall byteArray. ByteArray byteArray => Int -> m byteArray
forall (m :: * -> *) byteArray.
(MonadRandom m, ByteArray byteArray) =>
Int -> m byteArray
getRandomBytes Int
hashLen
    Either Error ByteString -> m (Either Error ByteString)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Either Error ByteString -> m (Either Error ByteString))
-> Either Error ByteString -> m (Either Error ByteString)
forall a b. (a -> b) -> a -> b
$ ByteString
-> OAEPParams hash ByteString ByteString
-> PublicKey
-> ByteString
-> Either Error ByteString
forall hash.
HashAlgorithm hash =>
ByteString
-> OAEPParams hash ByteString ByteString
-> PublicKey
-> ByteString
-> Either Error ByteString
encryptWithSeed ByteString
seed OAEPParams hash ByteString ByteString
oaep PublicKey
pk ByteString
m
  where
    hashLen :: Int
hashLen = hash -> Int
forall a. HashAlgorithm a => a -> Int
hashDigestSize (OAEPParams hash ByteString ByteString -> hash
forall hash seed output. OAEPParams hash seed output -> hash
oaepHash OAEPParams hash ByteString ByteString
oaep) 

-- | Decrypt ciphertext using private key.
--
-- See algorithm 8.12 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
decrypt :: HashAlgorithm hash
        => OAEPParams hash ByteString ByteString    -- ^ OAEP padding parameters
        -> PrivateKey                               -- ^ private key
        -> ByteString                               -- ^ ciphertext
        -> Maybe ByteString
decrypt :: forall hash.
HashAlgorithm hash =>
OAEPParams hash ByteString ByteString
-> PrivateKey -> ByteString -> Maybe ByteString
decrypt OAEPParams hash ByteString ByteString
oaep PrivateKey
pk ByteString
c =
    let p :: Integer
p  = PrivateKey -> Integer
private_p PrivateKey
pk 
        q :: Integer
q  = PrivateKey -> Integer
private_q PrivateKey
pk     
        a :: Integer
a  = PrivateKey -> Integer
private_a PrivateKey
pk 
        b :: Integer
b  = PrivateKey -> Integer
private_b PrivateKey
pk
        n :: Integer
n  = PublicKey -> Integer
public_n (PublicKey -> Integer) -> PublicKey -> Integer
forall a b. (a -> b) -> a -> b
$ PrivateKey -> PublicKey
private_pub PrivateKey
pk
        k :: Int
k  = Integer -> Int
numBytes Integer
n
        c' :: Integer
c' = ByteString -> Integer
forall ba. ByteArrayAccess ba => ba -> Integer
os2ip ByteString
c
        solutions :: [ByteString]
solutions = [Either Error ByteString] -> [ByteString]
forall a b. [Either a b] -> [b]
rights ([Either Error ByteString] -> [ByteString])
-> [Either Error ByteString] -> [ByteString]
forall a b. (a -> b) -> a -> b
$ (Either Error ByteString, Either Error ByteString,
 Either Error ByteString, Either Error ByteString)
-> [Either Error ByteString]
forall {a}. (a, a, a, a) -> [a]
toList ((Either Error ByteString, Either Error ByteString,
  Either Error ByteString, Either Error ByteString)
 -> [Either Error ByteString])
-> (Either Error ByteString, Either Error ByteString,
    Either Error ByteString, Either Error ByteString)
-> [Either Error ByteString]
forall a b. (a -> b) -> a -> b
$ (Integer -> Either Error ByteString)
-> (Integer, Integer, Integer, Integer)
-> (Either Error ByteString, Either Error ByteString,
    Either Error ByteString, Either Error ByteString)
forall {t} {d}. (t -> d) -> (t, t, t, t) -> (d, d, d, d)
mapTuple (OAEPParams hash ByteString ByteString
-> Int -> ByteString -> Either Error ByteString
forall hash.
HashAlgorithm hash =>
OAEPParams hash ByteString ByteString
-> Int -> ByteString -> Either Error ByteString
unpad OAEPParams hash ByteString ByteString
oaep Int
k (ByteString -> Either Error ByteString)
-> (Integer -> ByteString) -> Integer -> Either Error ByteString
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Integer -> ByteString
forall ba. ByteArray ba => Int -> Integer -> ba
i2ospOf_ Int
k) ((Integer, Integer, Integer, Integer)
 -> (Either Error ByteString, Either Error ByteString,
     Either Error ByteString, Either Error ByteString))
-> (Integer, Integer, Integer, Integer)
-> (Either Error ByteString, Either Error ByteString,
    Either Error ByteString, Either Error ByteString)
forall a b. (a -> b) -> a -> b
$ Integer
-> Integer
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer, Integer)
sqroot' Integer
c' Integer
p Integer
q Integer
a Integer
b Integer
n
     in if [ByteString] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [ByteString]
solutions Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
1 then Maybe ByteString
forall a. Maybe a
Nothing
        else ByteString -> Maybe ByteString
forall a. a -> Maybe a
Just (ByteString -> Maybe ByteString) -> ByteString -> Maybe ByteString
forall a b. (a -> b) -> a -> b
$ [ByteString] -> ByteString
forall a. HasCallStack => [a] -> a
head [ByteString]
solutions
      where toList :: (a, a, a, a) -> [a]
toList (a
w, a
x, a
y, a
z) = a
wa -> [a] -> [a]
forall a. a -> [a] -> [a]
:a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:a
za -> [a] -> [a]
forall a. a -> [a] -> [a]
:[]
            mapTuple :: (t -> d) -> (t, t, t, t) -> (d, d, d, d)
mapTuple t -> d
f (t
w, t
x, t
y, t
z) = (t -> d
f t
w, t -> d
f t
x, t -> d
f t
y, t -> d
f t
z)

-- | Sign message using padding, hash algorithm and private key.
--
-- See <https://en.wikipedia.org/wiki/Rabin_signature_algorithm>.
signWith :: HashAlgorithm hash
         => ByteString    -- ^ padding
         -> PrivateKey    -- ^ private key
         -> hash          -- ^ hash function
         -> ByteString    -- ^ message to sign
         -> Either Error Signature
signWith :: forall hash.
HashAlgorithm hash =>
ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Signature
signWith ByteString
padding PrivateKey
pk hash
hashAlg ByteString
m = do
    Integer
h <- ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Integer
forall hash.
HashAlgorithm hash =>
ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Integer
calculateHash ByteString
padding PrivateKey
pk hash
hashAlg ByteString
m
    Signature
signature <- Integer -> Either Error Signature
calculateSignature Integer
h
    Signature -> Either Error Signature
forall a. a -> Either Error a
forall (m :: * -> *) a. Monad m => a -> m a
return Signature
signature
  where
    calculateSignature :: Integer -> Either Error Signature
calculateSignature Integer
h =
        let p :: Integer
p = PrivateKey -> Integer
private_p PrivateKey
pk
            q :: Integer
q = PrivateKey -> Integer
private_q PrivateKey
pk     
            a :: Integer
a = PrivateKey -> Integer
private_a PrivateKey
pk 
            b :: Integer
b = PrivateKey -> Integer
private_b PrivateKey
pk
            n :: Integer
n = PublicKey -> Integer
public_n (PublicKey -> Integer) -> PublicKey -> Integer
forall a b. (a -> b) -> a -> b
$ PrivateKey -> PublicKey
private_pub PrivateKey
pk
         in if Integer
h Integer -> PrimeCondition
forall a. Ord a => a -> a -> Bool
>= Integer
n then Error -> Either Error Signature
forall a b. a -> Either a b
Left Error
MessageTooLong
            else let (Integer
r, Integer
_, Integer
_, Integer
_) = Integer
-> Integer
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer, Integer)
sqroot' Integer
h Integer
p Integer
q Integer
a Integer
b Integer
n
                  in Signature -> Either Error Signature
forall a b. b -> Either a b
Right (Signature -> Either Error Signature)
-> Signature -> Either Error Signature
forall a b. (a -> b) -> a -> b
$ (Integer, Integer) -> Signature
Signature (ByteString -> Integer
forall ba. ByteArrayAccess ba => ba -> Integer
os2ip ByteString
padding, Integer
r)

-- | Sign message using hash algorithm and private key.
--
-- See <https://en.wikipedia.org/wiki/Rabin_signature_algorithm>.
sign :: (MonadRandom m, HashAlgorithm hash)
     => PrivateKey    -- ^ private key
     -> hash          -- ^ hash function
     -> ByteString    -- ^ message to sign
     -> m (Either Error Signature)
sign :: forall (m :: * -> *) hash.
(MonadRandom m, HashAlgorithm hash) =>
PrivateKey -> hash -> ByteString -> m (Either Error Signature)
sign PrivateKey
pk hash
hashAlg ByteString
m = do
    ByteString
padding <- m ByteString
findPadding
    Either Error Signature -> m (Either Error Signature)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Either Error Signature -> m (Either Error Signature))
-> Either Error Signature -> m (Either Error Signature)
forall a b. (a -> b) -> a -> b
$ ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Signature
forall hash.
HashAlgorithm hash =>
ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Signature
signWith ByteString
padding PrivateKey
pk hash
hashAlg ByteString
m
  where 
    findPadding :: m ByteString
findPadding = do
        ByteString
padding <- Int -> m ByteString
forall byteArray. ByteArray byteArray => Int -> m byteArray
forall (m :: * -> *) byteArray.
(MonadRandom m, ByteArray byteArray) =>
Int -> m byteArray
getRandomBytes Int
8
        case ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Integer
forall hash.
HashAlgorithm hash =>
ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Integer
calculateHash ByteString
padding PrivateKey
pk hash
hashAlg ByteString
m of
            Right Integer
_ -> ByteString -> m ByteString
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ByteString
padding
            Either Error Integer
_       -> m ByteString
findPadding

-- | Calculate hash of message and padding.
-- If the padding is valid, then the result of the hash operation is returned, otherwise an error.
calculateHash :: HashAlgorithm hash
              => ByteString    -- ^ padding
              -> PrivateKey    -- ^ private key
              -> hash          -- ^ hash function
              -> ByteString    -- ^ message to sign
              -> Either Error Integer
calculateHash :: forall hash.
HashAlgorithm hash =>
ByteString
-> PrivateKey -> hash -> ByteString -> Either Error Integer
calculateHash ByteString
padding PrivateKey
pk hash
hashAlg ByteString
m = 
    let p :: Integer
p = PrivateKey -> Integer
private_p PrivateKey
pk
        q :: Integer
q = PrivateKey -> Integer
private_q PrivateKey
pk
        h :: Integer
h = Digest hash -> Integer
forall ba. ByteArrayAccess ba => ba -> Integer
os2ip (Digest hash -> Integer) -> Digest hash -> Integer
forall a b. (a -> b) -> a -> b
$ hash -> ByteString -> Digest hash
forall ba alg.
(ByteArrayAccess ba, HashAlgorithm alg) =>
alg -> ba -> Digest alg
hashWith hash
hashAlg (ByteString -> Digest hash) -> ByteString -> Digest hash
forall a b. (a -> b) -> a -> b
$ ByteString -> ByteString -> ByteString
B.append ByteString
padding ByteString
m
     in case (Integer -> Integer -> Maybe Integer
jacobi (Integer
h Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p) Integer
p, Integer -> Integer -> Maybe Integer
jacobi (Integer
h Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q) Integer
q) of
            (Just Integer
1, Just Integer
1) -> Integer -> Either Error Integer
forall a b. b -> Either a b
Right Integer
h
            (Maybe Integer, Maybe Integer)
_                -> Error -> Either Error Integer
forall a b. a -> Either a b
Left Error
InvalidParameters

-- | Verify signature using hash algorithm and public key.
--
-- See <https://en.wikipedia.org/wiki/Rabin_signature_algorithm>.
verify :: HashAlgorithm hash
       => PublicKey     -- ^ private key
       -> hash          -- ^ hash function
       -> ByteString    -- ^ message
       -> Signature     -- ^ signature
       -> Bool
verify :: forall hash.
HashAlgorithm hash =>
PublicKey -> hash -> ByteString -> Signature -> Bool
verify PublicKey
pk hash
hashAlg ByteString
m (Signature (Integer
padding, Integer
s)) =
    let n :: Integer
n  = PublicKey -> Integer
public_n PublicKey
pk
        p :: ByteString
p  = Integer -> ByteString
forall ba. ByteArray ba => Integer -> ba
i2osp Integer
padding
        h :: Integer
h  = Digest hash -> Integer
forall ba. ByteArrayAccess ba => ba -> Integer
os2ip (Digest hash -> Integer) -> Digest hash -> Integer
forall a b. (a -> b) -> a -> b
$ hash -> ByteString -> Digest hash
forall ba alg.
(ByteArrayAccess ba, HashAlgorithm alg) =>
alg -> ba -> Digest alg
hashWith hash
hashAlg (ByteString -> Digest hash) -> ByteString -> Digest hash
forall a b. (a -> b) -> a -> b
$ ByteString -> ByteString -> ByteString
B.append ByteString
p ByteString
m 
        h' :: Integer
h' = Integer -> Integer -> Integer -> Integer
expSafe Integer
s Integer
2 Integer
n
     in Integer
h' Integer -> PrimeCondition
forall a. Eq a => a -> a -> Bool
== Integer
h

-- | Square roots modulo prime p where p is congruent 3 mod 4
-- Value a must be a quadratic residue modulo p (i.e. jacobi symbol (a/n) = 1).
--
-- See algorithm 3.36 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
sqroot :: Integer
       -> Integer   -- ^ prime p
       -> (Integer, Integer)
sqroot :: Integer -> Integer -> (Integer, Integer)
sqroot Integer
a Integer
p =
    let r :: Integer
r = Integer -> Integer -> Integer -> Integer
expSafe Integer
a ((Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
4) Integer
p
     in (Integer
r, -Integer
r)

-- | Square roots modulo n given its prime factors p and q (both congruent 3 mod 4)
-- Value a must be a quadratic residue of both modulo p and modulo q (i.e. jacobi symbols (a/p) = (a/q) = 1).
-- 
-- See algorithm 3.44 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
sqroot' :: Integer 
        -> Integer  -- ^ prime p
        -> Integer  -- ^ prime q
        -> Integer  -- ^ c such that c*p + d*q = 1
        -> Integer  -- ^ d such that c*p + d*q = 1
        -> Integer  -- ^ n = p*q
        -> (Integer, Integer, Integer, Integer)
sqroot' :: Integer
-> Integer
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer, Integer)
sqroot' Integer
a Integer
p Integer
q Integer
c Integer
d Integer
n =
    let (Integer
r, Integer
_) = Integer -> Integer -> (Integer, Integer)
sqroot Integer
a Integer
p
        (Integer
s, Integer
_) = Integer -> Integer -> (Integer, Integer)
sqroot Integer
a Integer
q
        x :: Integer
x      = (Integer
rInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
dInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
sInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
cInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
p) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n
        y :: Integer
y      = (Integer
rInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
dInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
sInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
cInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
p) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n
     in (Integer
x, (-Integer
x) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n, Integer
y, (-Integer
y) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n)