{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}

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

import Crypto.ECC.Simple.Types
import Crypto.Error
import Crypto.Internal.ECC (CurveField (..), MulResult (..), curveMul)
import Crypto.Number.Basic (numBits)
import Crypto.Number.F2m
import Crypto.Number.Generate (generateBetween)
import Crypto.Number.ModArithmetic
import Crypto.Random
import Data.Bits (shiftL, shiftR, testBit, (.&.))

import Data.Maybe
import Data.Proxy

-- | Generate a valid scalar for a specific Curve
scalarGenerate
    :: forall randomly curve
     . (MonadRandom randomly, Curve curve) => randomly (Scalar curve)
scalarGenerate :: forall (randomly :: * -> *) curve.
(MonadRandom randomly, Curve curve) =>
randomly (Scalar curve)
scalarGenerate =
    Integer -> Scalar curve
forall curve. Integer -> Scalar curve
Scalar (Integer -> Scalar curve)
-> randomly Integer -> randomly (Scalar curve)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> 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 = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccN (CurveParameters curve -> Integer)
-> CurveParameters curve -> Integer
forall a b. (a -> b) -> a -> b
$ Proxy curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve)

scalarFromInteger
    :: forall curve. Curve curve => Integer -> CryptoFailable (Scalar curve)
scalarFromInteger :: forall curve.
Curve curve =>
Integer -> CryptoFailable (Scalar curve)
scalarFromInteger Integer
n
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 Bool -> Bool -> Bool
|| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
mx = CryptoError -> CryptoFailable (Scalar curve)
forall a. CryptoError -> CryptoFailable a
CryptoFailed (CryptoError -> CryptoFailable (Scalar curve))
-> CryptoError -> CryptoFailable (Scalar curve)
forall a b. (a -> b) -> a -> b
$ CryptoError
CryptoError_EcScalarOutOfBounds
    | Bool
otherwise = Scalar curve -> CryptoFailable (Scalar curve)
forall a. a -> CryptoFailable a
CryptoPassed (Scalar curve -> CryptoFailable (Scalar curve))
-> Scalar curve -> CryptoFailable (Scalar curve)
forall a b. (a -> b) -> a -> b
$ Integer -> Scalar curve
forall curve. Integer -> Scalar curve
Scalar Integer
n
  where
    mx :: Integer
mx = case Proxy curve -> CurveType
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveType
forall (proxy :: * -> *). proxy curve -> CurveType
curveType (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve) of
        CurveBinary (CurveBinaryParam Integer
b) -> Integer
b
        CurvePrime (CurvePrimeParam Integer
p) -> Integer
p

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

-- | Elliptic Curve point negation:
-- @pointNegate p@ returns point @q@ such that @pointAdd p q == PointO@.
pointNegate :: Curve curve => Point curve -> Point curve
pointNegate :: forall curve. Curve curve => Point curve -> Point curve
pointNegate Point curve
PointO = Point curve
forall curve. Point curve
PointO
pointNegate point :: Point curve
point@(Point Integer
x Integer
y) =
    case Point curve -> CurveType
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveType
forall (proxy :: * -> *). proxy curve -> CurveType
curveType Point curve
point of
        CurvePrime (CurvePrimeParam Integer
p) -> Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
x (Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
y)
        CurveBinary{} -> Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
x (Integer
x Integer -> Integer -> Integer
`addF2m` Integer
y)

-- | Elliptic Curve point addition.
--
-- /WARNING:/ Vulnerable to timing attacks.
pointAdd :: Curve curve => Point curve -> Point curve -> Point curve
pointAdd :: forall curve.
Curve curve =>
Point curve -> Point curve -> Point curve
pointAdd Point curve
PointO Point curve
PointO = Point curve
forall curve. Point curve
PointO
pointAdd Point curve
PointO Point curve
q = Point curve
q
pointAdd Point curve
p Point curve
PointO = Point curve
p
pointAdd Point curve
p Point curve
q
    | Point curve
p Point curve -> Point curve -> Bool
forall a. Eq a => a -> a -> Bool
== Point curve
q = Point curve -> Point curve
forall curve. Curve curve => Point curve -> Point curve
pointDouble Point curve
p
    | Point curve
p Point curve -> Point curve -> Bool
forall a. Eq a => a -> a -> Bool
== Point curve -> Point curve
forall curve. Curve curve => Point curve -> Point curve
pointNegate Point curve
q = Point curve
forall curve. Point curve
PointO
pointAdd point :: Point curve
point@(Point Integer
xp Integer
yp) (Point Integer
xq Integer
yq) =
    case CurveType
ty of
        CurvePrime (CurvePrimeParam Integer
pr) -> Point curve -> Maybe (Point curve) -> Point curve
forall a. a -> Maybe a -> a
fromMaybe Point curve
forall curve. Point curve
PointO (Maybe (Point curve) -> Point curve)
-> Maybe (Point curve) -> Point curve
forall a b. (a -> b) -> a -> b
$ do
            Integer
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
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
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
            Point curve -> Maybe (Point curve)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Point curve -> Maybe (Point curve))
-> Point curve -> Maybe (Point curve)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
xr Integer
yr
        CurveBinary (CurveBinaryParam Integer
fx) -> Point curve -> Maybe (Point curve) -> Point curve
forall a. a -> Maybe a -> a
fromMaybe Point curve
forall curve. Point curve
PointO (Maybe (Point curve) -> Point curve)
-> Maybe (Point curve) -> Point curve
forall a b. (a -> b) -> a -> b
$ do
            Integer
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
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
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
            Point curve -> Maybe (Point curve)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Point curve -> Maybe (Point curve))
-> Point curve -> Maybe (Point curve)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
xr Integer
yr
  where
    ty :: CurveType
ty = Point curve -> CurveType
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveType
forall (proxy :: * -> *). proxy curve -> CurveType
curveType Point curve
point
    cc :: CurveParameters curve
cc = Point curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters Point curve
point
    a :: Integer
a = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccA CurveParameters curve
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 curve => Point curve -> Point curve
pointDouble :: forall curve. Curve curve => Point curve -> Point curve
pointDouble Point curve
PointO = Point curve
forall curve. Point curve
PointO
pointDouble point :: Point curve
point@(Point Integer
xp Integer
yp) =
    case CurveType
ty of
        CurvePrime (CurvePrimeParam Integer
pr) -> Point curve -> Maybe (Point curve) -> Point curve
forall a. a -> Maybe a -> a
fromMaybe Point curve
forall curve. Point curve
PointO (Maybe (Point curve) -> Point curve)
-> Maybe (Point curve) -> Point curve
forall a b. (a -> b) -> a -> b
$ do
            Integer
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
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
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
            Point curve -> Maybe (Point curve)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Point curve -> Maybe (Point curve))
-> Point curve -> Maybe (Point curve)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
xr Integer
yr
        CurveBinary (CurveBinaryParam Integer
fx)
            | Integer
xp Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 -> Point curve
forall curve. Point curve
PointO
            | Bool
otherwise -> Point curve -> Maybe (Point curve) -> Point curve
forall a. a -> Maybe a -> a
fromMaybe Point curve
forall curve. Point curve
PointO (Maybe (Point curve) -> Point curve)
-> Maybe (Point curve) -> Point curve
forall a b. (a -> b) -> a -> b
$ do
                Integer
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
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
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)
                Point curve -> Maybe (Point curve)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Point curve -> Maybe (Point curve))
-> Point curve -> Maybe (Point curve)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
xr Integer
yr
  where
    ty :: CurveType
ty = Point curve -> CurveType
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveType
forall (proxy :: * -> *). proxy curve -> CurveType
curveType Point curve
point
    cc :: CurveParameters curve
cc = Point curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters Point curve
point
    a :: Integer
a = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccA CurveParameters curve
cc

-- | Elliptic curve point multiplication using the base
--
-- /WARNING:/ Vulnerable to timing attacks.
pointBaseMul :: Curve curve => Scalar curve -> Point curve
pointBaseMul :: forall curve. Curve curve => Scalar curve -> Point curve
pointBaseMul Scalar curve
n = Scalar curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Scalar curve -> Point curve -> Point curve
pointMul Scalar curve
n (CurveParameters curve -> Point curve
forall curve. CurveParameters curve -> Point curve
curveEccG (CurveParameters curve -> Point curve)
-> CurveParameters curve -> Point curve
forall a b. (a -> b) -> a -> b
$ Proxy curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters (Proxy curve
forall {curve}. Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve))

-- | Elliptic curve point multiplication.
--
-- Over a prime field this goes to C, four bits of scalar at a time, with the
-- multiple to add taken from a table read by touching every entry of it.
-- Over a binary field it also goes to C, as Montgomery's ladder: it carries
-- the x coordinates of two consecutive multiples -- their difference being
-- the point is what lets it carry no more than that -- and spends one
-- addition and one doubling on every bit whichever way the bit goes, with the
-- two exchanged by a mask rather than chosen by a branch.  Either way the work
-- follows the width of the curve's order and not the scalar.
--
-- What falls back on the 'Integer' arithmetic below is a point that is not on
-- the curve, the one point of a binary curve that has no x, and a prime the C
-- will not take.
--
-- Multiplying the base point of a curve over a prime field -- which is what
-- signing and making a key do, and nothing else does -- goes through a table
-- of its multiples, built when that curve is first asked for one and kept
-- afterwards.  The build is a few milliseconds and the table a few hundred
-- kilobytes, and a multiplication that uses it takes about a third of what
-- one without it takes.
--
-- /WARNING:/ What is left of the 'Integer' arithmetic below -- a point off
-- the curve, the one point of a binary curve with no x, a prime or a
-- polynomial the C will not take -- has uniform operation counts at best, and
-- uniform operation counts are not constant time: those operations cost what
-- the values they are given cost.  See the note in
-- "Crypto.ECC".
pointMul
    :: forall curve. Curve curve => Scalar curve -> Point curve -> Point curve
pointMul :: forall curve.
Curve curve =>
Scalar curve -> Point curve -> Point curve
pointMul Scalar curve
_ Point curve
PointO = Point curve
forall curve. Point curve
PointO
pointMul (Scalar Integer
n) Point curve
p
    | Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Point curve
forall curve. Point curve
PointO
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = Point curve -> Point curve
forall curve. Curve curve => Point curve -> Point curve
pointNegate (Scalar curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Scalar curve -> Point curve -> Point curve
pointMul (Integer -> Scalar curve
forall curve. Integer -> Scalar curve
Scalar (Integer -> Integer
forall a. Num a => a -> a
negate Integer
n) :: Scalar curve) Point curve
p)
    | Bool
otherwise =
        case Proxy curve -> CurveType
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveType
forall (proxy :: * -> *). proxy curve -> CurveType
curveType (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve) of
            CurvePrime (CurvePrimeParam Integer
pr) -> Integer -> Point curve
primeMul Integer
pr
            CurveBinary (CurveBinaryParam Integer
fx) -> Integer -> Point curve
binaryMul Integer
fx
  where
    cc :: CurveParameters curve
cc = Proxy curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve)
    a :: Integer
a = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccA CurveParameters curve
cc
    -- Count to the width of the order, which is public, so a scalar in range
    -- -- which is every secret one -- takes the same number of steps whatever
    -- it is.  A scalar may still be given out of range, and then the count has
    -- to follow it or the high bits would be dropped.
    bits :: Int
bits = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (Integer -> Int
integerBits Integer
n) (Integer -> Int
integerBits (CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccN CurveParameters curve
cc))

    -- The C answers for a point on the curve; anything else keeps the
    -- answers it has always had from the code below.
    primeMul :: Integer -> Point curve
primeMul Integer
pr = case Point curve
p of
        Point Integer
px Integer
py
            | Proxy curve -> Integer -> Integer -> Bool
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> Integer -> Integer -> Bool
isPointValid (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve) Integer
px Integer
py ->
                Point curve -> MulResult -> Point curve
forall {curve}. Point curve -> MulResult -> Point curve
answer Point curve
slow (MulResult -> Point curve) -> MulResult -> Point curve
forall a b. (a -> b) -> a -> b
$
                    CurveField
-> Integer -> Integer -> Integer -> Integer -> Bool -> MulResult
curveMul
                        (Integer -> Integer -> Integer -> CurveField
Prime Integer
pr Integer
a (CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccB CurveParameters curve
cc))
                        (CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccN CurveParameters curve
cc)
                        Integer
n
                        Integer
px
                        Integer
py
                        (Point curve
p Point curve -> Point curve -> Bool
forall a. Eq a => a -> a -> Bool
== CurveParameters curve -> Point curve
forall curve. CurveParameters curve -> Point curve
curveEccG CurveParameters curve
cc)
        Point curve
_ -> Point curve
slow
      where
        slow :: Point curve
slow = Integer -> Integer -> Int -> Integer -> Point curve -> Point curve
forall curve.
Integer -> Integer -> Int -> Integer -> Point curve -> Point curve
jacobianMul Integer
pr Integer
a Int
bits Integer
n Point curve
p

    -- The ladder answers for a point on the curve that has an x; the one
    -- point with no x, and anything off the curve, keep what they had.
    binaryMul :: Integer -> Point curve
binaryMul Integer
fx = case Point curve
p of
        Point Integer
px Integer
py
            | Proxy curve -> Integer -> Integer -> Bool
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> Integer -> Integer -> Bool
isPointValid (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve) Integer
px Integer
py ->
                Point curve -> MulResult -> Point curve
forall {curve}. Point curve -> MulResult -> Point curve
answer (Integer -> Point curve -> Point curve
forall {t} {curve}.
(Integral t, Curve curve) =>
t -> Point curve -> Point curve
affineMul Integer
n Point curve
p) (MulResult -> Point curve) -> MulResult -> Point curve
forall a b. (a -> b) -> a -> b
$
                    CurveField
-> Integer -> Integer -> Integer -> Integer -> Bool -> MulResult
curveMul (Integer -> Integer -> CurveField
Binary Integer
fx (CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccB CurveParameters curve
cc)) (CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccN CurveParameters curve
cc) Integer
n Integer
px Integer
py Bool
False
        Point curve
_ -> Integer -> Point curve -> Point curve
forall {t} {curve}.
(Integral t, Curve curve) =>
t -> Point curve -> Point curve
affineMul Integer
n Point curve
p

    -- what the C could not take goes back to the code that was here before
    answer :: Point curve -> MulResult -> Point curve
answer Point curve
fallback MulResult
r = case MulResult
r of
        MulPoint Integer
x Integer
y -> Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
x Integer
y
        MulResult
MulInfinity -> Point curve
forall curve. Point curve
PointO
        MulResult
MulUnsupported -> Point curve
fallback

    affineMul :: t -> Point curve -> Point curve
affineMul t
k Point curve
q
        | t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 = Point curve
forall curve. Point curve
PointO
        | t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
1 = Point curve
q
        | t -> Bool
forall a. Integral a => a -> Bool
odd t
k = Point curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Point curve -> Point curve -> Point curve
pointAdd Point curve
q (t -> Point curve -> Point curve
affineMul (t
k t -> t -> t
forall a. Num a => a -> a -> a
- t
1) Point curve
q)
        | Bool
otherwise = t -> Point curve -> Point curve
affineMul (t
k t -> t -> t
forall a. Integral a => a -> a -> a
`div` t
2) (Point curve -> Point curve
forall curve. Curve curve => Point curve -> Point curve
pointDouble Point curve
q)

-- | Number of bits needed to write n, for n > 0.
integerBits :: Integer -> Int
integerBits :: Integer -> Int
integerBits = Int -> Integer -> Int
forall {t} {t}. (Num t, Integral t) => t -> t -> t
go Int
0
  where
    go :: t -> t -> t
go t
acc t
0 = t
acc
    go t
acc t
k = t -> t -> t
go (t
acc t -> t -> t
forall a. Num a => a -> a -> a
+ t
1) (t
k t -> t -> t
forall a. Integral a => a -> a -> a
`div` t
2)

-- | A point in Jacobian coordinates: @(X, Y, Z)@ stands for the affine
-- @(X\/Z^2, Y\/Z^3)@, and @JPointO@ for the point at infinity.  Only ever
-- used inside this module, since t'Point' is what the curve exposes.
data JPoint = JPointO | JPoint !Integer !Integer !Integer

-- | The prime, the width to fold at, and what to fold back in.  A @c@ of zero
-- says to divide instead, either because the prime has no such shape or
-- because it is too small for folding to pay: @c@ has to be under half the
-- width, or folding would not shrink the number, and below 256 bits the
-- handful of 'Integer' operations folding takes costs more than the division
-- it saves -- measured on P-192, where folding is 14% slower.
--
-- Most curve primes are @2^k - c@ with @c@ far smaller than the prime, and
-- then reducing is a shift, a multiplication by @c@ and an addition, where
-- dividing a number twice the width costs about four times as much.
data Field = Field !Integer !Int !Integer

mkField :: Integer -> Field
mkField :: Integer -> Field
mkField Integer
p
    | Integer
p Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 Bool -> Bool -> Bool
&& Integer
c Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 Bool -> Bool -> Bool
&& Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Integer -> Int
numBits Integer
c Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
k Bool -> Bool -> Bool
&& Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
256 = Integer -> Int -> Integer -> Field
Field Integer
p Int
k Integer
c
    | Bool
otherwise = Integer -> Int -> Integer -> Field
Field Integer
p Int
0 Integer
0
  where
    k :: Int
k = Integer -> Int
numBits Integer
p
    c :: Integer
c = (Integer
1 Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
`shiftL` Int
k) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
p

fieldPrime :: Field -> Integer
fieldPrime :: Field -> Integer
fieldPrime (Field Integer
p Int
_ Integer
_) = Integer
p

fieldReduce :: Field -> Integer -> Integer
fieldReduce :: Field -> Integer -> Integer
fieldReduce (Field Integer
p Int
k Integer
c) Integer
x
    | Integer
c Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
|| Integer
x Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = Integer
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p
    | Bool
otherwise = Integer -> Integer
trim (Integer -> Integer
fold Integer
x)
  where
    mask :: Integer
mask = (Integer
1 Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
`shiftL` Int
k) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1
    fold :: Integer -> Integer
fold Integer
v
        | Integer
v Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
mask = Integer -> Integer
fold ((Integer
v Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
`shiftR` Int
k) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
c Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ (Integer
v Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer
mask))
        | Bool
otherwise = Integer
v
    trim :: Integer -> Integer
trim Integer
v
        | Integer
v Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
p = Integer -> Integer
trim (Integer
v Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
p)
        | Bool
otherwise = Integer
v
{-# INLINE fieldReduce #-}

jacobianMul
    :: Integer -> Integer -> Int -> Integer -> Point curve -> Point curve
jacobianMul :: forall curve.
Integer -> Integer -> Int -> Integer -> Point curve -> Point curve
jacobianMul Integer
_ Integer
_ Int
_ Integer
_ Point curve
PointO = Point curve
forall curve. Point curve
PointO
jacobianMul Integer
pr Integer
a Int
bits Integer
n (Point Integer
px Integer
py) = Field -> JPoint -> Point curve
forall curve. Field -> JPoint -> Point curve
fromJacobian Field
f (Int -> JPoint -> JPoint
go (Int
bits Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) JPoint
JPointO)
  where
    f :: Field
f = Integer -> Field
mkField Integer
pr

    -- The bangs are what make the addition happen at every bit.  Without
    -- them the one that is not taken stays a thunk and is never worked out,
    -- so the multiplication costs a step for every bit that is set rather
    -- than for every bit there is, and a single measurement tells an attacker
    -- how many bits of the scalar are set.
    go :: Int -> JPoint -> JPoint
go Int
i JPoint
acc
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = JPoint
acc
        | Bool
otherwise =
            let !d :: JPoint
d = Field -> Integer -> JPoint -> JPoint
jDouble Field
f Integer
a JPoint
acc
                !s :: JPoint
s = Field -> Integer -> JPoint -> Integer -> Integer -> JPoint
jAddAffine Field
f Integer
a JPoint
d Integer
px Integer
py
             in Int -> JPoint -> JPoint
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (if Integer -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Integer
n Int
i then JPoint
s else JPoint
d)

jDouble :: Field -> Integer -> JPoint -> JPoint
jDouble :: Field -> Integer -> JPoint -> JPoint
jDouble Field
_ Integer
_ JPoint
JPointO = JPoint
JPointO
jDouble Field
f Integer
a (JPoint Integer
x Integer
y Integer
z)
    | Integer
y Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = JPoint
JPointO
    | Bool
otherwise = Integer -> Integer -> Integer -> JPoint
JPoint Integer
x3 Integer
y3 Integer
z3
  where
    red :: Integer -> Integer
red = Field -> Integer -> Integer
fieldReduce Field
f
    yy :: Integer
yy = Integer -> Integer
red (Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y)
    delta :: Integer
delta = Integer -> Integer
red (Integer
4 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
yy)
    zz :: Integer
zz = Integer -> Integer
red (Integer
z Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z)
    m :: Integer
m = Integer -> Integer
red (Integer
3 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
zz Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
zz)
    x3 :: Integer
x3 = Integer -> Integer
red (Integer
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
delta)
    y3 :: Integer
y3 = Integer -> Integer
red (Integer
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
delta Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x3) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
8 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
yy Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
yy)
    z3 :: Integer
z3 = Integer -> Integer
red (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z)

-- | Add a point whose z is one, which is what a scalar multiplication always
-- adds: u1 is x1, s1 is y1, and z3 is one multiplication rather than two.
jAddAffine :: Field -> Integer -> JPoint -> Integer -> Integer -> JPoint
jAddAffine :: Field -> Integer -> JPoint -> Integer -> Integer -> JPoint
jAddAffine Field
_ Integer
_ JPoint
JPointO Integer
x2 Integer
y2 = Integer -> Integer -> Integer -> JPoint
JPoint Integer
x2 Integer
y2 Integer
1
jAddAffine Field
f Integer
a p :: JPoint
p@(JPoint Integer
x1 Integer
y1 Integer
z1) Integer
x2 Integer
y2
    | Integer
h Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
0 = Integer -> Integer -> Integer -> JPoint
JPoint Integer
x3 Integer
y3 Integer
z3
    | Integer
r Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
0 = JPoint
JPointO
    | Bool
otherwise = Field -> Integer -> JPoint -> JPoint
jDouble Field
f Integer
a JPoint
p
  where
    red :: Integer -> Integer
red = Field -> Integer -> Integer
fieldReduce Field
f
    z1s :: Integer
z1s = Integer -> Integer
red (Integer
z1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1)
    u2 :: Integer
u2 = Integer -> Integer
red (Integer
x2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1s)
    s2 :: Integer
s2 = Integer -> Integer
red (Integer
y2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1s Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1)
    h :: Integer
h = Integer -> Integer
red (Integer
u2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x1)
    r :: Integer
r = Integer -> Integer
red (Integer
s2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
y1)
    h2 :: Integer
h2 = Integer -> Integer
red (Integer
h Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h)
    h3 :: Integer
h3 = Integer -> Integer
red (Integer
h2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h)
    x3 :: Integer
x3 = Integer -> Integer
red (Integer
r Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
r Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
h3 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h2)
    y3 :: Integer
y3 = Integer -> Integer
red (Integer
r Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
x1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x3) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
y1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h3)
    z3 :: Integer
z3 = Integer -> Integer
red (Integer
h Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1)

fromJacobian :: Field -> JPoint -> Point curve
fromJacobian :: forall curve. Field -> JPoint -> Point curve
fromJacobian Field
_ JPoint
JPointO = Point curve
forall curve. Point curve
PointO
fromJacobian Field
f (JPoint Integer
x Integer
y Integer
z) =
    case Integer -> Integer -> Maybe Integer
inverse Integer
z (Field -> Integer
fieldPrime Field
f) of
        Maybe Integer
Nothing -> Point curve
forall curve. Point curve
PointO
        Just Integer
zi ->
            let red :: Integer -> Integer
red = Field -> Integer -> Integer
fieldReduce Field
f
                zi2 :: Integer
zi2 = Integer -> Integer
red (Integer
zi Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
zi)
             in Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point (Integer -> Integer
red (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
zi2)) (Integer -> Integer
red (Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
zi2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
zi))

-- | Elliptic curve double-scalar multiplication.
--
-- > pointAddTwoMuls n1 p1 n2 p2 == pointAdd (pointMul n1 p1)
-- >                                         (pointMul n2 p2)
--
-- which is how it is done: the two multiplications separately, and then one
-- addition.
--
-- This used to be Shamir's trick, one pass over the bits of both scalars at
-- once, which shares the doublings between them and is the right thing to do
-- when the two multiplications would cost the same.  They no longer do.
-- 'pointMul' goes to C, and over a prime field it multiplies the base point
-- through a table of its multiples, which is a third of the price of an
-- ordinary multiplication -- and the base point is one of the two here,
-- since ECDSA verification is what asks for this.  Sharing the doublings
-- with a pass in "Integer" arithmetic gives that up and more: on P-384 it
-- costs twice what two multiplications in C cost, and on the curves over a
-- binary field, whose addition needs an inversion where C has a ladder that
-- needs none, it costs two hundred times as much.
--
-- /WARNING:/ Vulnerable to timing attacks.
pointAddTwoMuls
    :: forall curve
     . Curve curve
    => Scalar curve -> Point curve -> Scalar curve -> Point curve -> Point curve
pointAddTwoMuls :: forall curve.
Curve curve =>
Scalar curve
-> Point curve -> Scalar curve -> Point curve -> Point curve
pointAddTwoMuls Scalar curve
n1 Point curve
p1 Scalar curve
n2 Point curve
p2 = Point curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Point curve -> Point curve -> Point curve
pointAdd (Scalar curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Scalar curve -> Point curve -> Point curve
pointMul Scalar curve
n1 Point curve
p1) (Scalar curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Scalar curve -> Point curve -> Point curve
pointMul Scalar curve
n2 Point curve
p2)

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

-- | Make a point on a curve from integer (x,y) coordinate
--
-- if the point is not valid related to the curve then an error is
-- returned instead of a point
pointFromIntegers
    :: forall curve. Curve curve => (Integer, Integer) -> CryptoFailable (Point curve)
pointFromIntegers :: forall curve.
Curve curve =>
(Integer, Integer) -> CryptoFailable (Point curve)
pointFromIntegers (Integer
x, Integer
y)
    | Bool -> Bool
not (Proxy curve -> Integer -> Integer -> Bool
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> Integer -> Integer -> Bool
isPointValid (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve) Integer
x Integer
y) =
        CryptoError -> CryptoFailable (Point curve)
forall a. CryptoError -> CryptoFailable a
CryptoFailed CryptoError
CryptoError_PointCoordinatesInvalid
    | Bool -> Bool
not (Proxy curve -> Point curve -> Bool
forall (proxy :: * -> *) curve.
Curve curve =>
proxy curve -> Point curve -> Bool
isPointInSubgroup (Proxy curve
forall {k} (t :: k). Proxy t
Proxy :: Proxy curve) Point curve
forall curve. Point curve
p) =
        CryptoError -> CryptoFailable (Point curve)
forall a. CryptoError -> CryptoFailable a
CryptoFailed CryptoError
CryptoError_PointSubgroupInvalid
    | Bool
otherwise = Point curve -> CryptoFailable (Point curve)
forall a. a -> CryptoFailable a
CryptoPassed Point curve
forall curve. Point curve
p
  where
    p :: Point curve
p = Integer -> Integer -> Point curve
forall curve. Integer -> Integer -> Point curve
Point Integer
x Integer
y

-- | 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 curve => proxy curve -> Integer -> Integer -> Bool
isPointValid :: forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> Integer -> Integer -> Bool
isPointValid proxy curve
proxy Integer
x Integer
y =
    case CurveType
ty of
        CurvePrime (CurvePrimeParam Integer
p) ->
            let a :: Integer
a = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccA CurveParameters curve
cc
                b :: Integer
b = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccB CurveParameters curve
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
             in 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)
        CurveBinary (CurveBinaryParam Integer
fx) ->
            let a :: Integer
a = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccA CurveParameters curve
cc
                b :: Integer
b = CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccB CurveParameters curve
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
             in [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
    ty :: CurveType
ty = proxy curve -> CurveType
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveType
forall (proxy :: * -> *). proxy curve -> CurveType
curveType proxy curve
proxy
    cc :: CurveParameters curve
cc = proxy curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters proxy curve
proxy

-- | Check that a point is in the subgroup the base point generates, which is
-- the further check 'isPointValid' does not make.  A point that is on the
-- curve but outside that subgroup answers a multiplication modulo an order
-- smaller than the group's, so the multiplier -- a private number, where the
-- point came from a peer -- is revealed modulo that small order.
--
-- Where the cofactor is 1 the subgroup is the whole curve group and the
-- answer is 'True' for any point on the curve, at no cost.  Otherwise the
-- point is multiplied by the group order and the answer is whether that
-- reaches the point at infinity, which costs one scalar multiplication.
isPointInSubgroup
    :: forall proxy curve. Curve curve => proxy curve -> Point curve -> Bool
isPointInSubgroup :: forall (proxy :: * -> *) curve.
Curve curve =>
proxy curve -> Point curve -> Bool
isPointInSubgroup proxy curve
proxy Point curve
p
    | CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccH CurveParameters curve
cc Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Bool
True
    | Bool
otherwise = Scalar curve -> Point curve -> Point curve
forall curve.
Curve curve =>
Scalar curve -> Point curve -> Point curve
pointMul (Integer -> Scalar curve
forall curve. Integer -> Scalar curve
Scalar (CurveParameters curve -> Integer
forall curve. CurveParameters curve -> Integer
curveEccN CurveParameters curve
cc) :: Scalar curve) Point curve
p Point curve -> Point curve -> Bool
forall a. Eq a => a -> a -> Bool
== Point curve
forall curve. Point curve
PointO
  where
    cc :: CurveParameters curve
cc = proxy curve -> CurveParameters curve
forall curve (proxy :: * -> *).
Curve curve =>
proxy curve -> CurveParameters curve
forall (proxy :: * -> *). proxy curve -> CurveParameters curve
curveParameters proxy curve
proxy

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