{-# LANGUAGE BangPatterns #-}

-- |
-- Module      : Crypto.Number.ModArithmetic
-- License     : BSD-style
-- Maintainer  : Vincent Hanquez <vincent@snarc.org>
-- Stability   : experimental
-- Portability : Good
--
-- Modular arithmetic on 'Integer'.
--
-- == What an 'Integer' shows
--
-- An 'Integer' is as long as its value needs, and every operation on one
-- costs what that length says.  A secret that happens to be short is
-- multiplied, reduced and compared in fewer words than a full-length one, and
-- the difference is there to be measured.  'expSafe' and 'inverseSafe' keep
-- the /value/ of an exponent or of a number being inverted out of the work
-- they do, and that is as far as an 'Integer' can be taken: hiding the length
-- as well means a fixed-width representation, which is what the curve modules
-- and 'expSafe' itself use underneath.
module Crypto.Number.ModArithmetic (
    -- * Exceptions
    CoprimesAssertionError (..),
    ModulusAssertionError (..),

    -- * Exponentiation
    expSafe,
    expFast,

    -- * Inverse computing
    inverse,
    inverseSafe,
    inverseCoprimes,
    inverseFermat,

    -- * Squares
    jacobi,
    squareRoot,
) where

import qualified Control.Exception as E
import Crypto.Internal.Compat (unsafeDoIO)
import Crypto.Number.Basic
import Crypto.Number.Compat
import Crypto.Number.ModArithmetic.Pub (expPub)
import qualified Crypto.Number.Serialize.Internal as Internal
import Data.Memory.PtrMethods (memSet)
import Data.Word (Word32, Word8)
import Foreign.C.Types (CInt (..))
import Foreign.Marshal.Alloc (allocaBytes)
import Foreign.Ptr (Ptr, plusPtr)

-- | Raised when two numbers are supposed to be coprimes but are not.
data CoprimesAssertionError = CoprimesAssertionError
    deriving (Int -> CoprimesAssertionError -> ShowS
[CoprimesAssertionError] -> ShowS
CoprimesAssertionError -> String
(Int -> CoprimesAssertionError -> ShowS)
-> (CoprimesAssertionError -> String)
-> ([CoprimesAssertionError] -> ShowS)
-> Show CoprimesAssertionError
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> CoprimesAssertionError -> ShowS
showsPrec :: Int -> CoprimesAssertionError -> ShowS
$cshow :: CoprimesAssertionError -> String
show :: CoprimesAssertionError -> String
$cshowList :: [CoprimesAssertionError] -> ShowS
showList :: [CoprimesAssertionError] -> ShowS
Show)

instance E.Exception CoprimesAssertionError

-- | Compute the modular exponentiation of base^exponent using
-- algorithms design to avoid side channels and timing measurement
--
-- Modulo need to be odd otherwise the normal fast modular exponentiation
-- is used.
--
-- With an odd modulo the work is done in C, four bits of exponent at a time:
-- four squarings and one multiplication by a small power of the base, taken
-- from a table of sixteen which is read by touching every entry and keeping
-- one of them with a mask.  So each group of four bits costs the same five
-- multiplications and the same sixteen reads whatever those bits are, and
-- nothing branches on the exponent or indexes memory with it.
--
-- What the exponent still shows is its length: it is rounded up to a whole
-- 64-bit word and every bit of that is walked over, so its value is hidden
-- but its size is not.  The @mpz_powm_sec@ of GMP, which GHC stopped
-- offering in integer-gmp 1.1 and which this replaces, hides exactly as much.
--
-- The base is taken to be public -- in this library it is a ciphertext, a
-- public value from a peer, or a generator -- and is reduced modulo the
-- modulus in the ordinary way first.
--
-- Hiding the exponent has a price: against the windowed exponentiation of
-- GMP, which is what this function used to end up calling, a 2048-bit
-- modulus costs somewhat over twice as much.
expSafe
    :: Integer
    -- ^ base
    -> Integer
    -- ^ exponent
    -> Integer
    -- ^ modulo
    -> Integer
    -- ^ result
expSafe :: Integer -> Integer -> Integer -> Integer
expSafe Integer
b Integer
e Integer
m
    | Integer -> Bool
forall a. Integral a => a -> Bool
odd Integer
m Bool -> Bool -> Bool
&& Integer
m Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
1 Bool -> Bool -> Bool
&& Integer
e Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
0 =
        Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModSecInteger Integer
b Integer
e Integer
m GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Integer -> Integer -> Integer -> Integer
expSec (Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m) Integer
e Integer
m
    -- a modulus of one, and a negative exponent asking for an inverse, are
    -- left to the path they have always taken
    | Bool
otherwise =
        Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModInteger Integer
b Integer
e Integer
m
            GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m

-- | The windowed exponentiation itself, in C.  The base has to be reduced
-- already, the exponent to be zero or more, and the modulus odd and above
-- one.
expSec :: Integer -> Integer -> Integer -> Integer
expSec :: Integer -> Integer -> Integer -> Integer
expSec Integer
b Integer
e Integer
m = IO Integer -> Integer
forall a. IO a -> a
unsafeDoIO (IO Integer -> Integer) -> IO Integer -> Integer
forall a b. (a -> b) -> a -> b
$
    Int -> (Ptr Word8 -> IO Integer) -> IO Integer
forall a b. Int -> (Ptr a -> IO b) -> IO b
allocaBytes ([Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int]
widths) ((Ptr Word8 -> IO Integer) -> IO Integer)
-> (Ptr Word8 -> IO Integer) -> IO Integer
forall a b. (a -> b) -> a -> b
$ \Ptr Word8
start -> case (Ptr Word8 -> Int -> Ptr Word8)
-> Ptr Word8 -> [Int] -> [Ptr Word8]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl Ptr Word8 -> Int -> Ptr Word8
forall a b. Ptr a -> Int -> Ptr b
plusPtr Ptr Word8
start [Int]
widths of
        (Ptr Word8
out : Ptr Word8
base : Ptr Word8
expo : Ptr Word8
modu : [Ptr Word8]
_) -> do
            Int
_ <- Integer -> Ptr Word8 -> Int -> IO Int
Internal.i2ospOf Integer
b Ptr Word8
base Int
mLen
            Int
_ <- Integer -> Ptr Word8 -> Int -> IO Int
Internal.i2ospOf Integer
e Ptr Word8
expo Int
eLen
            Int
_ <- Integer -> Ptr Word8 -> Int -> IO Int
Internal.i2ospOf Integer
m Ptr Word8
modu Int
mLen
            CInt
r <-
                Ptr Word8
-> Ptr Word8
-> Word32
-> Ptr Word8
-> Word32
-> Ptr Word8
-> Word32
-> IO CInt
c_powm_sec
                    Ptr Word8
out
                    Ptr Word8
base
                    (Int -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
mLen)
                    Ptr Word8
expo
                    (Int -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
eLen)
                    Ptr Word8
modu
                    (Int -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
mLen)
            -- the exponent is the caller's secret, and this is the last place it
            -- is written out in the clear
            Ptr Word8 -> Word8 -> Int -> IO ()
memSet Ptr Word8
expo Word8
0 Int
eLen
            if CInt
r CInt -> CInt -> Bool
forall a. Eq a => a -> a -> Bool
== CInt
0
                then do
                    !Integer
v <- Ptr Word8 -> Int -> IO Integer
Internal.os2ip Ptr Word8
out Int
mLen
                    Integer -> IO Integer
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return Integer
v
                else
                    Integer -> IO Integer
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return
                        ( Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModInteger Integer
b Integer
e Integer
m
                            GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m
                        )
        [Ptr Word8]
_ -> Integer -> IO Integer
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return Integer
0 -- there are four, but say so anyway
  where
    !mLen :: Int
mLen = Integer -> Int
numBytes Integer
m
    -- the answer, the base, the exponent and the modulus.  The room to take
    -- and where each one starts both come from here, so they cannot drift
    -- apart.
    widths :: [Int]
widths = [Int
mLen, Int
mLen, Int
eLen, Int
mLen]
    -- whole words of exponent, so that the count of them says as little as
    -- what GMP's own secure exponentiation lets slip
    !eLen :: Int
eLen = Int
8 Int -> Int -> Int
forall a. Num a => a -> a -> a
* ((Integer -> Int
numBytes Integer
e Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
7) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
8)


foreign import ccall safe "crypton_powm_sec"
    c_powm_sec
        :: Ptr Word8
        -> Ptr Word8
        -> Word32
        -> Ptr Word8
        -> Word32
        -> Ptr Word8
        -> Word32
        -> IO CInt

-- | Compute the modular exponentiation of base^exponent using
-- the fastest algorithm without any consideration for
-- hiding parameters.
--
-- Use this function when all the parameters are public,
-- otherwise 'expSafe' should be preferred.
--
-- A short exponent on an odd modulus -- RSA verification, where the exponent
-- is 65537 and comes out of the public key -- is walked a bit at a time in
-- C, squaring at each step and multiplying where a bit is set, which reads
-- the exponent and branches on it and is why this is not 'expSafe'.  That
-- path is taken only where it is the faster of the two, which the C decides;
-- everywhere else, and for every longer exponent, this is GMP's windowed
-- exponentiation as it has always been.
expFast
    :: Integer
    -- ^ base
    -> Integer
    -- ^ exponent
    -> Integer
    -- ^ modulo
    -> Integer
    -- ^ result
expFast :: Integer -> Integer -> Integer -> Integer
expFast Integer
b Integer
e Integer
m
    | Integer -> Bool
forall a. Integral a => a -> Bool
odd Integer
m Bool -> Bool -> Bool
&& Integer
m Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
1 Bool -> Bool -> Bool
&& Integer
e Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 = case Integer -> Integer -> Integer -> Maybe Integer
expPub (Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m) Integer
e Integer
m of
        Just Integer
r -> Integer
r
        Maybe Integer
Nothing -> Integer
slow
    | Bool
otherwise = Integer
slow
  where
    slow :: Integer
slow = Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModInteger Integer
b Integer
e Integer
m GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m

-- | @exponentiation@ computes modular exponentiation as /b^e mod m/
-- using repetitive squaring.
--
-- The corner cases are held to what GMP answers, since that is what this
-- computes on every build that has it: a modulus of one is zero whatever
-- else is asked, and a negative exponent is a request for the inverse of
-- the base raised to its magnitude, which is zero when no inverse exists.
-- Read literally, the recursion below walked a negative exponent from -1 to
-- -2 and back for as long as the stack held.
exponentiation :: Integer -> Integer -> Integer -> Integer
exponentiation :: Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m
    | Integer
m Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
0
    | Integer
e Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 =
        Integer -> (Integer -> Integer) -> Maybe Integer -> Integer
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Integer
0 (\Integer
bInv -> Integer -> Integer -> Integer -> Integer
exponentiation Integer
bInv (Integer -> Integer
forall a. Num a => a -> a
negate Integer
e) Integer
m) (Integer -> Integer -> Maybe Integer
inverse (Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m) Integer
m)
    | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
1
    | Integer
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Integer
1
    | Integer
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
    | Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
e =
        let p :: Integer
p = Integer -> Integer -> Integer -> Integer
exponentiation Integer
b (Integer
e Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
2) Integer
m Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
         in (Integer
p Integer -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ (Integer
2 :: Integer)) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
    | Bool
otherwise = (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer -> Integer -> Integer
exponentiation Integer
b (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) Integer
m) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m

-- | @inverse@ computes the modular inverse as in /g^(-1) mod m/.
inverse :: Integer -> Integer -> Maybe Integer
inverse :: Integer -> Integer -> Maybe Integer
inverse Integer
g Integer
m = Integer -> Integer -> GmpSupported (Maybe Integer)
gmpInverse Integer
g Integer
m GmpSupported (Maybe Integer) -> Maybe Integer -> Maybe Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Maybe Integer
v
  where
    v :: Maybe Integer
v
        | Integer
d Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
1 = Maybe Integer
forall a. Maybe a
Nothing
        | Bool
otherwise = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m)
    (Integer
x, Integer
_, Integer
d) = Integer -> Integer -> (Integer, Integer, Integer)
gcde Integer
g Integer
m

-- | Compute the modular inverse of two coprime numbers.
-- This is equivalent to inverse except that the result
-- is known to exists.
--
-- If the numbers are not defined as coprime, this function
-- will raise a t'CoprimesAssertionError'.
inverseCoprimes :: Integer -> Integer -> Integer
inverseCoprimes :: Integer -> Integer -> Integer
inverseCoprimes Integer
g Integer
m =
    case Integer -> Integer -> Maybe Integer
inverse Integer
g Integer
m of
        Maybe Integer
Nothing -> CoprimesAssertionError -> Integer
forall a e. Exception e => e -> a
E.throw CoprimesAssertionError
CoprimesAssertionError
        Just Integer
i -> Integer
i

-- | Computes the Jacobi symbol (a/n).
-- 0 ≤ a < n; n ≥ 3 and odd.
--
-- The Legendre and Jacobi symbols are indistinguishable exactly when the
-- lower argument is an odd prime, in which case they have the same value.
--
-- See algorithm 2.149 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
jacobi :: Integer -> Integer -> Maybe Integer
jacobi :: Integer -> Integer -> Maybe Integer
jacobi Integer
a Integer
n
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
3 Bool -> Bool -> Bool
|| Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
n = Maybe Integer
forall a. Maybe a
Nothing
    | Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
|| Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
a
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
a = Integer -> Integer -> Maybe Integer
jacobi (Integer
a Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n) Integer
n
    | Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 =
        let b :: Integer
b = if Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then Integer
1 else -Integer
1
         in (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
b) (Integer -> Integer -> Maybe Integer
jacobi (-Integer
a) Integer
n)
    | Bool
otherwise =
        let (Int
e, Integer
a1) = Integer -> (Int, Integer)
asPowerOf2AndOdd Integer
a
            nMod8 :: Integer
nMod8 = Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
8
            nMod4 :: Integer
nMod4 = Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4
            a1Mod4 :: Integer
a1Mod4 = Integer
a1 Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4
            s' :: Integer
s' = if Int -> Bool
forall a. Integral a => a -> Bool
even Int
e Bool -> Bool -> Bool
|| Integer
nMod8 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 Bool -> Bool -> Bool
|| Integer
nMod8 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
7 then Integer
1 else -Integer
1
            s :: Integer
s = if Integer
nMod4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
3 Bool -> Bool -> Bool
&& Integer
a1Mod4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
3 then -Integer
s' else Integer
s'
            n1 :: Integer
n1 = Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
a1
         in if Integer
a1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1
                then Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
s
                else (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
s) (Integer -> Integer -> Maybe Integer
jacobi Integer
n1 Integer
a1)

-- | Modular inverse using Fermat's little theorem.  This works only when
-- the modulus is prime but avoids side channels like in 'expSafe'.
inverseFermat :: Integer -> Integer -> Integer
inverseFermat :: Integer -> Integer -> Integer
inverseFermat Integer
g Integer
p = Integer -> Integer -> Integer -> Integer
expSafe Integer
g (Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
2) Integer
p

-- | @inverseSafe@ computes the modular inverse without letting the number
-- being inverted steer how long the work takes, which is what 'inverse' does:
-- the extended Euclidean algorithm takes a number of steps that follows the
-- bits it is given, and a nonce inverted that way has been taken apart before
-- by watching the steps go by.
--
-- The answer comes from a fixed number of division steps where the assembly
-- for them is built, and from 'inverseFermat' where it is not.  Either way it
-- is checked here by multiplying out: neither one says when the number has no
-- inverse -- the first returns something that is not one and the second
-- returns something that is not one either -- so the check is what makes this
-- agree with 'inverse' on every input, and 'inverse' is asked when it fails.
-- That fallback is reached only by parameters that are already broken.
--
-- The division steps cost about a twentieth of the exponentiation: on an
-- Apple M4, inverting modulo the P-256 group order is 0.80 microseconds
-- against 6.02, and modulo the P-521 one 2.05 against 63.2.
inverseSafe :: Integer -> Integer -> Maybe Integer
inverseSafe :: Integer -> Integer -> Maybe Integer
inverseSafe Integer
g Integer
m
    | Integer
m Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
1 Bool -> Bool -> Bool
&& (Integer
g Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
r) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
r
    | Bool
otherwise = Integer -> Integer -> Maybe Integer
inverse Integer
g Integer
m
  where
    r :: Integer
r = case Integer -> Integer -> Maybe Integer
inverseSec Integer
g Integer
m of
        Just Integer
v -> Integer
v
        Maybe Integer
Nothing -> Integer -> Integer -> Integer
inverseFermat Integer
g Integer
m

-- | The inverse in a fixed number of division steps, from the vendored
-- assembly.  'Nothing' when that is not built, when the modulus is even --
-- where the routine answers without saying it cannot -- or when the numbers
-- are larger than it keeps room for.  The answer is not checked here; the
-- caller does that.
inverseSec :: Integer -> Integer -> Maybe Integer
inverseSec :: Integer -> Integer -> Maybe Integer
inverseSec Integer
g Integer
m
    | Integer
m Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
1 Bool -> Bool -> Bool
|| Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
m Bool -> Bool -> Bool
|| Integer
g Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = Maybe Integer
forall a. Maybe a
Nothing
    | Bool
otherwise = IO (Maybe Integer) -> Maybe Integer
forall a. IO a -> a
unsafeDoIO (IO (Maybe Integer) -> Maybe Integer)
-> IO (Maybe Integer) -> Maybe Integer
forall a b. (a -> b) -> a -> b
$
        Int -> (Ptr Word8 -> IO (Maybe Integer)) -> IO (Maybe Integer)
forall a b. Int -> (Ptr a -> IO b) -> IO b
allocaBytes (Int
3 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
mLen) ((Ptr Word8 -> IO (Maybe Integer)) -> IO (Maybe Integer))
-> (Ptr Word8 -> IO (Maybe Integer)) -> IO (Maybe Integer)
forall a b. (a -> b) -> a -> b
$ \Ptr Word8
out -> do
            let gp :: Ptr b
gp = Ptr Word8
out Ptr Word8 -> Int -> Ptr b
forall a b. Ptr a -> Int -> Ptr b
`plusPtr` Int
mLen
                mp :: Ptr b
mp = Ptr Any
forall {b}. Ptr b
gp Ptr Any -> Int -> Ptr b
forall a b. Ptr a -> Int -> Ptr b
`plusPtr` Int
mLen
            Int
_ <- Integer -> Ptr Word8 -> Int -> IO Int
Internal.i2ospOf (Integer
g Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m) Ptr Word8
forall {b}. Ptr b
gp Int
mLen
            Int
_ <- Integer -> Ptr Word8 -> Int -> IO Int
Internal.i2ospOf Integer
m Ptr Word8
forall {b}. Ptr b
mp Int
mLen
            CInt
r <- Ptr Word8 -> Ptr Word8 -> Ptr Word8 -> Word32 -> IO CInt
c_modinv_sec Ptr Word8
out Ptr Word8
forall {b}. Ptr b
gp Ptr Word8
forall {b}. Ptr b
mp (Int -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
mLen)
            if CInt
r CInt -> CInt -> Bool
forall a. Eq a => a -> a -> Bool
== CInt
0
                then do
                    !Integer
v <- Ptr Word8 -> Int -> IO Integer
Internal.os2ip Ptr Word8
out Int
mLen
                    Maybe Integer -> IO (Maybe Integer)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
v)
                else Maybe Integer -> IO (Maybe Integer)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe Integer
forall a. Maybe a
Nothing
  where
    !mLen :: Int
mLen = Integer -> Int
numBytes Integer
m

foreign import ccall unsafe "crypton_modinv_sec"
    c_modinv_sec
        :: Ptr Word8
        -> Ptr Word8
        -> Ptr Word8
        -> Word32
        -> IO CInt

-- | Raised when the assumption about the modulus is invalid.
data ModulusAssertionError = ModulusAssertionError
    deriving (Int -> ModulusAssertionError -> ShowS
[ModulusAssertionError] -> ShowS
ModulusAssertionError -> String
(Int -> ModulusAssertionError -> ShowS)
-> (ModulusAssertionError -> String)
-> ([ModulusAssertionError] -> ShowS)
-> Show ModulusAssertionError
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> ModulusAssertionError -> ShowS
showsPrec :: Int -> ModulusAssertionError -> ShowS
$cshow :: ModulusAssertionError -> String
show :: ModulusAssertionError -> String
$cshowList :: [ModulusAssertionError] -> ShowS
showList :: [ModulusAssertionError] -> ShowS
Show)

instance E.Exception ModulusAssertionError

-- | Modular square root of @g@ modulo a prime @p@.
--
-- If the modulus is found not to be prime, the function will raise a
-- t'ModulusAssertionError'.
--
-- This implementation is variable time and should be used with public
-- parameters only.
squareRoot :: Integer -> Integer -> Maybe Integer
squareRoot :: Integer -> Integer -> Maybe Integer
squareRoot Integer
p
    | Integer
p Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
2 = ModulusAssertionError -> Integer -> Maybe Integer
forall a e. Exception e => e -> a
E.throw ModulusAssertionError
ModulusAssertionError
    | Bool
otherwise =
        case Integer
p Integer -> Integer -> (Integer, Integer)
forall a. Integral a => a -> a -> (a, a)
`divMod` Integer
8 of
            (Integer
v, Integer
3) -> Integer -> Integer -> Maybe Integer
method1 (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
v Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1)
            (Integer
v, Integer
7) -> Integer -> Integer -> Maybe Integer
method1 (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
v Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
2)
            (Integer
u, Integer
5) -> Integer -> Integer -> Maybe Integer
method2 Integer
u
            (Integer
_, Integer
1) -> Integer -> Integer -> Maybe Integer
tonelliShanks Integer
p
            (Integer
0, Integer
2) -> \Integer
a -> Integer -> Maybe Integer
forall a. a -> Maybe a
Just (if Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
a then Integer
0 else Integer
1)
            (Integer, Integer)
_ -> ModulusAssertionError -> Integer -> Maybe Integer
forall a e. Exception e => e -> a
E.throw ModulusAssertionError
ModulusAssertionError
  where
    Integer
x eqMod :: Integer -> Integer -> Bool
`eqMod` Integer
y = (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
y) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0

    validate :: Integer -> Integer -> Maybe Integer
validate Integer
g Integer
y
        | (Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y) Integer -> Integer -> Bool
`eqMod` Integer
g = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
y
        | Bool
otherwise = Maybe Integer
forall a. Maybe a
Nothing

    -- p == 4u + 3 and u' == u + 1
    method1 :: Integer -> Integer -> Maybe Integer
method1 Integer
u' Integer
g =
        let y :: Integer
y = Integer -> Integer -> Integer -> Integer
expFast Integer
g Integer
u' Integer
p
         in Integer -> Integer -> Maybe Integer
validate Integer
g Integer
y

    -- p == 8u + 5
    method2 :: Integer -> Integer -> Maybe Integer
method2 Integer
u Integer
g =
        let gamma :: Integer
gamma = Integer -> Integer -> Integer -> Integer
expFast (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
g) Integer
u Integer
p
            g_gamma :: Integer
g_gamma = Integer
g Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
gamma
            i :: Integer
i = (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
g_gamma Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
gamma) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p
            y :: Integer
y = (Integer
g_gamma Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
i Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p
         in Integer -> Integer -> Maybe Integer
validate Integer
g Integer
y

tonelliShanks :: Integer -> Integer -> Maybe Integer
tonelliShanks :: Integer -> Integer -> Maybe Integer
tonelliShanks Integer
p Integer
a
    | Integer
aa Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
0
    | Bool
otherwise =
        case Integer -> Integer -> Integer -> Integer
expFast Integer
aa Integer
p2 Integer
p of
            Integer
b
                | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
p1 -> Maybe Integer
forall a. Maybe a
Nothing
                | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 ->
                    Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer -> Maybe Integer) -> Integer -> Maybe Integer
forall a b. (a -> b) -> a -> b
$
                        Integer -> Integer -> Integer -> Int -> Integer
forall {t}.
(Eq t, Num t) =>
Integer -> Integer -> Integer -> t -> Integer
go
                            (Integer -> Integer -> Integer -> Integer
expFast Integer
aa ((Integer
s Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
2) Integer
p)
                            (Integer -> Integer -> Integer -> Integer
expFast Integer
aa Integer
s Integer
p)
                            (Integer -> Integer -> Integer -> Integer
expFast Integer
n Integer
s Integer
p)
                            Int
e
                | Bool
otherwise -> ModulusAssertionError -> Maybe Integer
forall a e. Exception e => e -> a
E.throw ModulusAssertionError
ModulusAssertionError
  where
    aa :: Integer
aa = Integer
a Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p
    p1 :: Integer
p1 = Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1
    p2 :: Integer
p2 = Integer
p1 Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
2
    n :: Integer
n = Integer -> Integer
findN Integer
2

    Integer
x mul :: Integer -> Integer -> Integer
`mul` Integer
y = (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p

    pow2m :: t -> Integer -> Integer
pow2m t
0 Integer
x = Integer
x
    pow2m t
i Integer
x = t -> Integer -> Integer
pow2m (t
i t -> t -> t
forall a. Num a => a -> a -> a
- t
1) (Integer
x Integer -> Integer -> Integer
`mul` Integer
x)

    (Int
e, Integer
s) = Integer -> (Int, Integer)
asPowerOf2AndOdd Integer
p1

    -- find a quadratic non-residue
    findN :: Integer -> Integer
findN Integer
i
        | Integer -> Integer -> Integer -> Integer
expFast Integer
i Integer
p2 Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
p1 = Integer
i
        | Bool
otherwise = Integer -> Integer
findN (Integer
i Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1)

    -- find m such that b^(2^m) == 1 (mod p)
    findM :: Integer -> t -> t
findM Integer
b t
i
        | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = t
i
        | Bool
otherwise = Integer -> t -> t
findM (Integer
b Integer -> Integer -> Integer
`mul` Integer
b) (t
i t -> t -> t
forall a. Num a => a -> a -> a
+ t
1)

    go :: Integer -> Integer -> Integer -> t -> Integer
go !Integer
x Integer
b Integer
g !t
r
        | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
x
        | Bool
otherwise =
            let r' :: t
r' = Integer -> t -> t
forall {t}. Num t => Integer -> t -> t
findM Integer
b t
0
                z :: Integer
z = t -> Integer -> Integer
forall {t}. (Eq t, Num t) => t -> Integer -> Integer
pow2m (t
r t -> t -> t
forall a. Num a => a -> a -> a
- t
r' t -> t -> t
forall a. Num a => a -> a -> a
- t
1) Integer
g
                x' :: Integer
x' = Integer
x Integer -> Integer -> Integer
`mul` Integer
z
                b' :: Integer
b' = Integer
b Integer -> Integer -> Integer
`mul` Integer
g'
                g' :: Integer
g' = Integer
z Integer -> Integer -> Integer
`mul` Integer
z
             in Integer -> Integer -> Integer -> t -> Integer
go Integer
x' Integer
b' Integer
g' t
r'