    -- | Elliptic Curve Arithmetic.
    --
    -- /WARNING:/ These functions are vulnerable to timing attacks.
    module Crypto.PubKey.ECC.Prim
        ( scalarGenerate
        , pointAdd
        , pointNegate
        , pointDouble
        , pointBaseMul
        , pointMul
        , pointAddTwoMuls
        , isPointAtInfinity
        , isPointValid
        ) where

    import Data.Maybe
    import Crypto.Number.ModArithmetic
    import Crypto.Number.F2m
    import Crypto.Number.Generate (generateBetween)
    import Crypto.PubKey.ECC.Types
    import Crypto.Random

    -- | Generate a valid scalar for a specific Curve
    scalarGenerate :: MonadRandom randomly => Curve -> randomly PrivateNumber
    scalarGenerate :: forall (randomly :: * -> *).
    MonadRandom randomly =>
    Curve -> randomly Integer
    scalarGenerate Curve
    curve = Integer -> Integer -> randomly Integer
    forall (m :: * -> *).
    MonadRandom m =>
    Integer -> Integer -> m Integer
    generateBetween Integer
    1 (Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    1)
      where
            n :: Integer
    n = CurveCommon -> Integer
    ecc_n (CurveCommon -> Integer) -> CurveCommon -> Integer
    forall a b. (a -> b) -> a -> b
    $ Curve -> CurveCommon
    common_curve Curve
    curve

    --TODO: Extract helper function for `fromMaybe PointO...`

    -- | Elliptic Curve point negation:
    -- @pointNegate c p@ returns point @q@ such that @pointAdd c p q == PointO@.
    pointNegate :: Curve -> Point -> Point
    pointNegate :: Curve -> Point -> Point
    pointNegate Curve
    _            Point
    PointO     = Point
    PointO
    pointNegate (CurveFP CurvePrime
    c) (Point Integer
    x Integer
    y) = Integer -> Integer -> Point
    Point Integer
    x (CurvePrime -> Integer
    ecc_p CurvePrime
    c Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    y)
    pointNegate CurveF2m{}  (Point Integer
    x Integer
    y) = Integer -> Integer -> Point
    Point Integer
    x (Integer
    x Integer -> Integer -> Integer
    `addF2m` Integer
    y)

    -- | Elliptic Curve point addition.
    --
    -- /WARNING:/ Vulnerable to timing attacks.
    pointAdd :: Curve -> Point -> Point -> Point
    pointAdd :: Curve -> Point -> Point -> Point
    pointAdd Curve
    _ Point
    PointO Point
    PointO = Point
    PointO
    pointAdd Curve
    _ Point
    PointO Point
    q = Point
    q
    pointAdd Curve
    _ Point
    p Point
    PointO = Point
    p
    pointAdd Curve
    c Point
    p Point
    q
      | Point
    p Point -> Point -> Bool
    forall a. Eq a => a -> a -> Bool
    == Point
    q = Curve -> Point -> Point
    pointDouble Curve
    c Point
    p
      | Point
    p Point -> Point -> Bool
    forall a. Eq a => a -> a -> Bool
    == Curve -> Point -> Point
    pointNegate Curve
    c Point
    q = Point
    PointO
    pointAdd (CurveFP (CurvePrime Integer
    pr CurveCommon
    _)) (Point Integer
    xp Integer
    yp) (Point Integer
    xq Integer
    yq)
        = Point -> Maybe Point -> Point
    forall a. a -> Maybe a -> a
    fromMaybe Point
    PointO (Maybe Point -> Point) -> Maybe Point -> Point
    forall a b. (a -> b) -> a -> b
    $ do
            s <- Integer -> Integer -> Integer -> Maybe Integer
    divmod (Integer
    yp Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    yq) (Integer
    xp Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    xq) Integer
    pr
            let xr = (Integer
    s Integer -> Int -> Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^ (Int
    2::Int) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    xp Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    xq) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    pr
                yr = (Integer
    s Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * (Integer
    xp Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    xr) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    yp) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    pr
            return $ Point xr yr
    pointAdd (CurveF2m (CurveBinary Integer
    fx CurveCommon
    cc)) (Point Integer
    xp Integer
    yp) (Point Integer
    xq Integer
    yq)
        = Point -> Maybe Point -> Point
    forall a. a -> Maybe a -> a
    fromMaybe Point
    PointO (Maybe Point -> Point) -> Maybe Point -> Point
    forall a b. (a -> b) -> a -> b
    $ do
            s <- Integer -> Integer -> Integer -> Maybe Integer
    divF2m Integer
    fx (Integer
    yp Integer -> Integer -> Integer
    `addF2m` Integer
    yq) (Integer
    xp Integer -> Integer -> Integer
    `addF2m` Integer
    xq)
            let xr = Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    s Integer
    s Integer -> Integer -> Integer
    `addF2m` Integer
    s Integer -> Integer -> Integer
    `addF2m` Integer
    xp Integer -> Integer -> Integer
    `addF2m` Integer
    xq Integer -> Integer -> Integer
    `addF2m` Integer
    a
                yr = Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    s (Integer
    xp Integer -> Integer -> Integer
    `addF2m` Integer
    xr) Integer -> Integer -> Integer
    `addF2m` Integer
    xr Integer -> Integer -> Integer
    `addF2m` Integer
    yp
            return $ Point xr yr
      where a :: Integer
    a = CurveCommon -> Integer
    ecc_a CurveCommon
    cc

    -- | Elliptic Curve point doubling.
    --
    -- /WARNING:/ Vulnerable to timing attacks.
    --
    -- This perform the following calculation:
    -- > lambda = (3 * xp ^ 2 + a) / 2 yp
    -- > xr = lambda ^ 2 - 2 xp
    -- > yr = lambda (xp - xr) - yp
    --
    -- With binary curve:
    -- > xp == 0   => P = O
    -- > otherwise =>
    -- >    s = xp + (yp / xp)
    -- >    xr = s ^ 2 + s + a
    -- >    yr = xp ^ 2 + (s+1) * xr
    --
    pointDouble :: Curve -> Point -> Point
    pointDouble :: Curve -> Point -> Point
    pointDouble Curve
    _ Point
    PointO = Point
    PointO
    pointDouble (CurveFP (CurvePrime Integer
    pr CurveCommon
    cc)) (Point Integer
    xp Integer
    yp) = Point -> Maybe Point -> Point
    forall a. a -> Maybe a -> a
    fromMaybe Point
    PointO (Maybe Point -> Point) -> Maybe Point -> Point
    forall a b. (a -> b) -> a -> b
    $ do
        lambda <- Integer -> Integer -> Integer -> Maybe Integer
    divmod (Integer
    3 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    xp Integer -> Int -> Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^ (Int
    2::Int) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    a) (Integer
    2 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    yp) Integer
    pr
        let xr = (Integer
    lambda Integer -> Int -> Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^ (Int
    2::Int) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    2 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    xp) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    pr
            yr = (Integer
    lambda Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * (Integer
    xp Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    xr) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    yp) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    pr
        return $ Point xr yr
      where a :: Integer
    a = CurveCommon -> Integer
    ecc_a CurveCommon
    cc
    pointDouble (CurveF2m (CurveBinary Integer
    fx CurveCommon
    cc)) (Point Integer
    xp Integer
    yp)
        | Integer
    xp Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0   = Point
    PointO
        | Bool
    otherwise = Point -> Maybe Point -> Point
    forall a. a -> Maybe a -> a
    fromMaybe Point
    PointO (Maybe Point -> Point) -> Maybe Point -> Point
    forall a b. (a -> b) -> a -> b
    $ do
            s <- Integer -> Maybe Integer
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Integer -> Maybe Integer)
    -> (Integer -> Integer) -> Integer -> Maybe Integer
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Integer -> Integer -> Integer
    addF2m Integer
    xp (Integer -> Maybe Integer) -> Maybe Integer -> Maybe Integer
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Integer -> Integer -> Integer -> Maybe Integer
    divF2m Integer
    fx Integer
    yp Integer
    xp
            let xr = Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    s Integer
    s Integer -> Integer -> Integer
    `addF2m` Integer
    s Integer -> Integer -> Integer
    `addF2m` Integer
    a
                yr = Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    xp Integer
    xp Integer -> Integer -> Integer
    `addF2m` Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    xr (Integer
    s Integer -> Integer -> Integer
    `addF2m` Integer
    1)
            return $ Point xr yr
      where a :: Integer
    a = CurveCommon -> Integer
    ecc_a CurveCommon
    cc

    -- | Elliptic curve point multiplication using the base
    --
    -- /WARNING:/ Vulnerable to timing attacks.
    pointBaseMul :: Curve -> Integer -> Point
    pointBaseMul :: Curve -> Integer -> Point
    pointBaseMul Curve
    c Integer
    n = Curve -> Integer -> Point -> Point
    pointMul Curve
    c Integer
    n (CurveCommon -> Point
    ecc_g (CurveCommon -> Point) -> CurveCommon -> Point
    forall a b. (a -> b) -> a -> b
    $ Curve -> CurveCommon
    common_curve Curve
    c)

    -- | Elliptic curve point multiplication (double and add algorithm).
    --
    -- /WARNING:/ Vulnerable to timing attacks.
    pointMul :: Curve -> Integer -> Point -> Point
    pointMul :: Curve -> Integer -> Point -> Point
    pointMul Curve
    _ Integer
    _ Point
    PointO = Point
    PointO
    pointMul Curve
    c Integer
    n Point
    p
        | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <  Integer
    0 = Curve -> Integer -> Point -> Point
    pointMul Curve
    c (-Integer
    n) (Curve -> Point -> Point
    pointNegate Curve
    c Point
    p)
        | Integer
    n Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0 = Point
    PointO
        | Integer
    n Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    1 = Point
    p
        | Integer -> Bool
    forall a. Integral a => a -> Bool
    odd Integer
    n = Curve -> Point -> Point -> Point
    pointAdd Curve
    c Point
    p (Curve -> Integer -> Point -> Point
    pointMul Curve
    c (Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    1) Point
    p)
        | Bool
    otherwise = Curve -> Integer -> Point -> Point
    pointMul Curve
    c (Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2) (Curve -> Point -> Point
    pointDouble Curve
    c Point
    p)

    -- | Elliptic curve double-scalar multiplication (uses Shamir's trick).
    --
    -- > pointAddTwoMuls c n1 p1 n2 p2 == pointAdd c (pointMul c n1 p1)
    -- >                                             (pointMul c n2 p2)
    --
    -- /WARNING:/ Vulnerable to timing attacks.
    pointAddTwoMuls :: Curve -> Integer -> Point -> Integer -> Point -> Point
    pointAddTwoMuls :: Curve -> Integer -> Point -> Integer -> Point -> Point
    pointAddTwoMuls Curve
    _ Integer
    _  Point
    PointO Integer
    _  Point
    PointO = Point
    PointO
    pointAddTwoMuls Curve
    c Integer
    _  Point
    PointO Integer
    n2 Point
    p2     = Curve -> Integer -> Point -> Point
    pointMul Curve
    c Integer
    n2 Point
    p2
    pointAddTwoMuls Curve
    c Integer
    n1 Point
    p1     Integer
    _  Point
    PointO = Curve -> Integer -> Point -> Point
    pointMul Curve
    c Integer
    n1 Point
    p1
    pointAddTwoMuls Curve
    c Integer
    n1 Point
    p1     Integer
    n2 Point
    p2
        | Integer
    n1 Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0    = Curve -> Integer -> Point -> Integer -> Point -> Point
    pointAddTwoMuls Curve
    c (-Integer
    n1) (Curve -> Point -> Point
    pointNegate Curve
    c Point
    p1) Integer
    n2 Point
    p2
        | Integer
    n2 Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0    = Curve -> Integer -> Point -> Integer -> Point -> Point
    pointAddTwoMuls Curve
    c Integer
    n1 Point
    p1 (-Integer
    n2) (Curve -> Point -> Point
    pointNegate Curve
    c Point
    p2)
        | Bool
    otherwise = (Integer, Integer) -> Point
    forall {a} {a}. (Integral a, Integral a) => (a, a) -> Point
    go (Integer
    n1, Integer
    n2)

      where
        p0 :: Point
    p0 = Curve -> Point -> Point -> Point
    pointAdd Curve
    c Point
    p1 Point
    p2

        go :: (a, a) -> Point
    go (a
    0,  a
    0 ) = Point
    PointO
        go (a
    k1, a
    k2) =
            let q :: Point
    q = Curve -> Point -> Point
    pointDouble Curve
    c (Point -> Point) -> Point -> Point
    forall a b. (a -> b) -> a -> b
    $ (a, a) -> Point
    go (a
    k1 a -> a -> a
    forall a. Integral a => a -> a -> a
    `div` a
    2, a
    k2 a -> a -> a
    forall a. Integral a => a -> a -> a
    `div` a
    2)
            in case (a -> Bool
    forall a. Integral a => a -> Bool
    odd a
    k1, a -> Bool
    forall a. Integral a => a -> Bool
    odd a
    k2) of
                (Bool
    True  , Bool
    True  ) -> Curve -> Point -> Point -> Point
    pointAdd Curve
    c Point
    p0 Point
    q
                (Bool
    True  , Bool
    False ) -> Curve -> Point -> Point -> Point
    pointAdd Curve
    c Point
    p1 Point
    q
                (Bool
    False , Bool
    True  ) -> Curve -> Point -> Point -> Point
    pointAdd Curve
    c Point
    p2 Point
    q
                (Bool
    False , Bool
    False ) -> Point
    q

    -- | Check if a point is the point at infinity.
    isPointAtInfinity :: Point -> Bool
    isPointAtInfinity :: Point -> Bool
    isPointAtInfinity Point
    PointO = Bool
    True
    isPointAtInfinity Point
    _      = Bool
    False

    -- | check if a point is on specific curve
    --
    -- This perform three checks:
    --
    -- * x is not out of range
    -- * y is not out of range
    -- * the equation @y^2 = x^3 + a*x + b (mod p)@ holds
    isPointValid :: Curve -> Point -> Bool
    isPointValid :: Curve -> Point -> Bool
    isPointValid Curve
    _                           Point
    PointO      = Bool
    True
    isPointValid (CurveFP (CurvePrime Integer
    p CurveCommon
    cc)) (Point Integer
    x Integer
    y) =
        Integer -> Bool
    isValid Integer
    x Bool -> Bool -> Bool
    && Integer -> Bool
    isValid Integer
    y Bool -> Bool -> Bool
    && (Integer
    y Integer -> Int -> Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^ (Int
    2 :: Int)) Integer -> Integer -> Bool
    `eqModP` (Integer
    x Integer -> Int -> Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^ (Int
    3 :: Int) Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    a Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    x Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    b)
      where a :: Integer
    a  = CurveCommon -> Integer
    ecc_a CurveCommon
    cc
            b :: Integer
    b  = CurveCommon -> Integer
    ecc_b CurveCommon
    cc
            eqModP :: Integer -> Integer -> Bool
    eqModP Integer
    z1 Integer
    z2 = (Integer
    z1 Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    p) Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == (Integer
    z2 Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    p)
            isValid :: Integer -> Bool
    isValid Integer
    e = Integer
    e Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Integer
    0 Bool -> Bool -> Bool
    && Integer
    e Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    p
    isPointValid (CurveF2m (CurveBinary Integer
    fx CurveCommon
    cc)) (Point Integer
    x Integer
    y) =
        [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and [ Integer -> Bool
    isValid Integer
    x
            , Integer -> Bool
    isValid Integer
    y
            , ((((Integer
    x Integer -> Integer -> Integer
    `add` Integer
    a) Integer -> Integer -> Integer
    `mul` Integer
    x Integer -> Integer -> Integer
    `add` Integer
    y) Integer -> Integer -> Integer
    `mul` Integer
    x) Integer -> Integer -> Integer
    `add` Integer
    b Integer -> Integer -> Integer
    `add` (Integer -> Integer -> Integer
    squareF2m Integer
    fx Integer
    y)) Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0
            ]
      where a :: Integer
    a  = CurveCommon -> Integer
    ecc_a CurveCommon
    cc
            b :: Integer
    b  = CurveCommon -> Integer
    ecc_b CurveCommon
    cc
            add :: Integer -> Integer -> Integer
    add = Integer -> Integer -> Integer
    addF2m
            mul :: Integer -> Integer -> Integer
    mul = Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx
            isValid :: Integer -> Bool
    isValid Integer
    e = Integer -> Integer -> Integer
    modF2m Integer
    fx Integer
    e Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    e

    -- | div and mod
    divmod :: Integer -> Integer -> Integer -> Maybe Integer
    divmod :: Integer -> Integer -> Integer -> Maybe Integer
    divmod Integer
    y Integer
    x Integer
    m = do
        i <- Integer -> Integer -> Maybe Integer
    inverse (Integer
    x Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    m) Integer
    m
        return $ y * i `mod` m