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
scalarGenerate :: MonadRandom randomly => Curve -> randomly PrivateNumber
scalarGenerate :: Curve -> randomly PrivateNumber
scalarGenerate curve :: Curve
curve = PrivateNumber -> PrivateNumber -> randomly PrivateNumber
forall (m :: * -> *).
MonadRandom m =>
PrivateNumber -> PrivateNumber -> m PrivateNumber
generateBetween 1 (PrivateNumber
n PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- 1)
where
n :: PrivateNumber
n = CurveCommon -> PrivateNumber
ecc_n (CurveCommon -> PrivateNumber) -> CurveCommon -> PrivateNumber
forall a b. (a -> b) -> a -> b
$ Curve -> CurveCommon
common_curve Curve
curve
pointNegate :: Curve -> Point -> Point
pointNegate :: Curve -> Point -> Point
pointNegate _ PointO = Point
PointO
pointNegate (CurveFP c :: CurvePrime
c) (Point x :: PrivateNumber
x y :: PrivateNumber
y) = PrivateNumber -> PrivateNumber -> Point
Point PrivateNumber
x (CurvePrime -> PrivateNumber
ecc_p CurvePrime
c PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
y)
pointNegate CurveF2m{} (Point x :: PrivateNumber
x y :: PrivateNumber
y) = PrivateNumber -> PrivateNumber -> Point
Point PrivateNumber
x (PrivateNumber
x PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
y)
pointAdd :: Curve -> Point -> Point -> Point
pointAdd :: Curve -> Point -> Point -> Point
pointAdd _ PointO PointO = Point
PointO
pointAdd _ PointO q :: Point
q = Point
q
pointAdd _ p :: Point
p PointO = Point
p
pointAdd c :: Curve
c p :: Point
p q :: 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 pr :: PrivateNumber
pr _)) (Point xp :: PrivateNumber
xp yp :: PrivateNumber
yp) (Point xq :: PrivateNumber
xq yq :: PrivateNumber
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
PrivateNumber
s <- PrivateNumber
-> PrivateNumber -> PrivateNumber -> Maybe PrivateNumber
divmod (PrivateNumber
yp PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
yq) (PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
xq) PrivateNumber
pr
let xr :: PrivateNumber
xr = (PrivateNumber
s PrivateNumber -> Int -> PrivateNumber
forall a b. (Num a, Integral b) => a -> b -> a
^ (2::Int) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
xq) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
pr
yr :: PrivateNumber
yr = (PrivateNumber
s PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* (PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
xr) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
yp) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
pr
Point -> Maybe Point
forall (m :: * -> *) a. Monad m => a -> m a
return (Point -> Maybe Point) -> Point -> Maybe Point
forall a b. (a -> b) -> a -> b
$ PrivateNumber -> PrivateNumber -> Point
Point PrivateNumber
xr PrivateNumber
yr
pointAdd (CurveF2m (CurveBinary fx :: PrivateNumber
fx cc :: CurveCommon
cc)) (Point xp :: PrivateNumber
xp yp :: PrivateNumber
yp) (Point xq :: PrivateNumber
xq yq :: PrivateNumber
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
PrivateNumber
s <- PrivateNumber
-> PrivateNumber -> PrivateNumber -> Maybe PrivateNumber
divF2m PrivateNumber
fx (PrivateNumber
yp PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
yq) (PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
xq)
let xr :: PrivateNumber
xr = PrivateNumber -> PrivateNumber -> PrivateNumber -> PrivateNumber
mulF2m PrivateNumber
fx PrivateNumber
s PrivateNumber
s PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
s PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
xq PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
a
yr :: PrivateNumber
yr = PrivateNumber -> PrivateNumber -> PrivateNumber -> PrivateNumber
mulF2m PrivateNumber
fx PrivateNumber
s (PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
xr) PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
xr PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
yp
Point -> Maybe Point
forall (m :: * -> *) a. Monad m => a -> m a
return (Point -> Maybe Point) -> Point -> Maybe Point
forall a b. (a -> b) -> a -> b
$ PrivateNumber -> PrivateNumber -> Point
Point PrivateNumber
xr PrivateNumber
yr
where a :: PrivateNumber
a = CurveCommon -> PrivateNumber
ecc_a CurveCommon
cc
pointDouble :: Curve -> Point -> Point
pointDouble :: Curve -> Point -> Point
pointDouble _ PointO = Point
PointO
pointDouble (CurveFP (CurvePrime pr :: PrivateNumber
pr cc :: CurveCommon
cc)) (Point xp :: PrivateNumber
xp yp :: PrivateNumber
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
PrivateNumber
lambda <- PrivateNumber
-> PrivateNumber -> PrivateNumber -> Maybe PrivateNumber
divmod (3 PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* PrivateNumber
xp PrivateNumber -> Int -> PrivateNumber
forall a b. (Num a, Integral b) => a -> b -> a
^ (2::Int) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
+ PrivateNumber
a) (2 PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* PrivateNumber
yp) PrivateNumber
pr
let xr :: PrivateNumber
xr = (PrivateNumber
lambda PrivateNumber -> Int -> PrivateNumber
forall a b. (Num a, Integral b) => a -> b -> a
^ (2::Int) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- 2 PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* PrivateNumber
xp) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
pr
yr :: PrivateNumber
yr = (PrivateNumber
lambda PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* (PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
xr) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- PrivateNumber
yp) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
pr
Point -> Maybe Point
forall (m :: * -> *) a. Monad m => a -> m a
return (Point -> Maybe Point) -> Point -> Maybe Point
forall a b. (a -> b) -> a -> b
$ PrivateNumber -> PrivateNumber -> Point
Point PrivateNumber
xr PrivateNumber
yr
where a :: PrivateNumber
a = CurveCommon -> PrivateNumber
ecc_a CurveCommon
cc
pointDouble (CurveF2m (CurveBinary fx :: PrivateNumber
fx cc :: CurveCommon
cc)) (Point xp :: PrivateNumber
xp yp :: PrivateNumber
yp)
| PrivateNumber
xp PrivateNumber -> PrivateNumber -> Bool
forall a. Eq a => a -> a -> Bool
== 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
PrivateNumber
s <- PrivateNumber -> Maybe PrivateNumber
forall (m :: * -> *) a. Monad m => a -> m a
return (PrivateNumber -> Maybe PrivateNumber)
-> (PrivateNumber -> PrivateNumber)
-> PrivateNumber
-> Maybe PrivateNumber
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PrivateNumber -> PrivateNumber -> PrivateNumber
addF2m PrivateNumber
xp (PrivateNumber -> Maybe PrivateNumber)
-> Maybe PrivateNumber -> Maybe PrivateNumber
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< PrivateNumber
-> PrivateNumber -> PrivateNumber -> Maybe PrivateNumber
divF2m PrivateNumber
fx PrivateNumber
yp PrivateNumber
xp
let xr :: PrivateNumber
xr = PrivateNumber -> PrivateNumber -> PrivateNumber -> PrivateNumber
mulF2m PrivateNumber
fx PrivateNumber
s PrivateNumber
s PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
s PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber
a
yr :: PrivateNumber
yr = PrivateNumber -> PrivateNumber -> PrivateNumber -> PrivateNumber
mulF2m PrivateNumber
fx PrivateNumber
xp PrivateNumber
xp PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` PrivateNumber -> PrivateNumber -> PrivateNumber -> PrivateNumber
mulF2m PrivateNumber
fx PrivateNumber
xr (PrivateNumber
s PrivateNumber -> PrivateNumber -> PrivateNumber
`addF2m` 1)
Point -> Maybe Point
forall (m :: * -> *) a. Monad m => a -> m a
return (Point -> Maybe Point) -> Point -> Maybe Point
forall a b. (a -> b) -> a -> b
$ PrivateNumber -> PrivateNumber -> Point
Point PrivateNumber
xr PrivateNumber
yr
where a :: PrivateNumber
a = CurveCommon -> PrivateNumber
ecc_a CurveCommon
cc
pointBaseMul :: Curve -> Integer -> Point
pointBaseMul :: Curve -> PrivateNumber -> Point
pointBaseMul c :: Curve
c n :: PrivateNumber
n = Curve -> PrivateNumber -> Point -> Point
pointMul Curve
c PrivateNumber
n (CurveCommon -> Point
ecc_g (CurveCommon -> Point) -> CurveCommon -> Point
forall a b. (a -> b) -> a -> b
$ Curve -> CurveCommon
common_curve Curve
c)
pointMul :: Curve -> Integer -> Point -> Point
pointMul :: Curve -> PrivateNumber -> Point -> Point
pointMul _ _ PointO = Point
PointO
pointMul c :: Curve
c n :: PrivateNumber
n p :: Point
p
| PrivateNumber
n PrivateNumber -> PrivateNumber -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = Curve -> PrivateNumber -> Point -> Point
pointMul Curve
c (-PrivateNumber
n) (Curve -> Point -> Point
pointNegate Curve
c Point
p)
| PrivateNumber
n PrivateNumber -> PrivateNumber -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Point
PointO
| PrivateNumber
n PrivateNumber -> PrivateNumber -> Bool
forall a. Eq a => a -> a -> Bool
== 1 = Point
p
| PrivateNumber -> Bool
forall a. Integral a => a -> Bool
odd PrivateNumber
n = Curve -> Point -> Point -> Point
pointAdd Curve
c Point
p (Curve -> PrivateNumber -> Point -> Point
pointMul Curve
c (PrivateNumber
n PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
- 1) Point
p)
| Bool
otherwise = Curve -> PrivateNumber -> Point -> Point
pointMul Curve
c (PrivateNumber
n PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`div` 2) (Curve -> Point -> Point
pointDouble Curve
c Point
p)
pointAddTwoMuls :: Curve -> Integer -> Point -> Integer -> Point -> Point
pointAddTwoMuls :: Curve -> PrivateNumber -> Point -> PrivateNumber -> Point -> Point
pointAddTwoMuls _ _ PointO _ PointO = Point
PointO
pointAddTwoMuls c :: Curve
c _ PointO n2 :: PrivateNumber
n2 p2 :: Point
p2 = Curve -> PrivateNumber -> Point -> Point
pointMul Curve
c PrivateNumber
n2 Point
p2
pointAddTwoMuls c :: Curve
c n1 :: PrivateNumber
n1 p1 :: Point
p1 _ PointO = Curve -> PrivateNumber -> Point -> Point
pointMul Curve
c PrivateNumber
n1 Point
p1
pointAddTwoMuls c :: Curve
c n1 :: PrivateNumber
n1 p1 :: Point
p1 n2 :: PrivateNumber
n2 p2 :: Point
p2
| PrivateNumber
n1 PrivateNumber -> PrivateNumber -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = Curve -> PrivateNumber -> Point -> PrivateNumber -> Point -> Point
pointAddTwoMuls Curve
c (-PrivateNumber
n1) (Curve -> Point -> Point
pointNegate Curve
c Point
p1) PrivateNumber
n2 Point
p2
| PrivateNumber
n2 PrivateNumber -> PrivateNumber -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = Curve -> PrivateNumber -> Point -> PrivateNumber -> Point -> Point
pointAddTwoMuls Curve
c PrivateNumber
n1 Point
p1 (-PrivateNumber
n2) (Curve -> Point -> Point
pointNegate Curve
c Point
p2)
| Bool
otherwise = (PrivateNumber, PrivateNumber) -> Point
forall a a. (Integral a, Integral a) => (a, a) -> Point
go (PrivateNumber
n1, PrivateNumber
n2)
where
p0 :: Point
p0 = Curve -> Point -> Point -> Point
pointAdd Curve
c Point
p1 Point
p2
go :: (a, a) -> Point
go (0, 0 ) = Point
PointO
go (k1 :: a
k1, k2 :: 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` 2, a
k2 a -> a -> a
forall a. Integral a => a -> a -> a
`div` 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
(True , True ) -> Curve -> Point -> Point -> Point
pointAdd Curve
c Point
p0 Point
q
(True , False ) -> Curve -> Point -> Point -> Point
pointAdd Curve
c Point
p1 Point
q
(False , True ) -> Curve -> Point -> Point -> Point
pointAdd Curve
c Point
p2 Point
q
(False , False ) -> Point
q
isPointAtInfinity :: Point -> Bool
isPointAtInfinity :: Point -> Bool
isPointAtInfinity PointO = Bool
True
isPointAtInfinity _ = Bool
False
isPointValid :: Curve -> Point -> Bool
isPointValid :: Curve -> Point -> Bool
isPointValid _ PointO = Bool
True
isPointValid (CurveFP (CurvePrime p :: PrivateNumber
p cc :: CurveCommon
cc)) (Point x :: PrivateNumber
x y :: PrivateNumber
y) =
PrivateNumber -> Bool
isValid PrivateNumber
x Bool -> Bool -> Bool
&& PrivateNumber -> Bool
isValid PrivateNumber
y Bool -> Bool -> Bool
&& (PrivateNumber
y PrivateNumber -> Int -> PrivateNumber
forall a b. (Num a, Integral b) => a -> b -> a
^ (2 :: Int)) PrivateNumber -> PrivateNumber -> Bool
`eqModP` (PrivateNumber
x PrivateNumber -> Int -> PrivateNumber
forall a b. (Num a, Integral b) => a -> b -> a
^ (3 :: Int) PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
+ PrivateNumber
a PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* PrivateNumber
x PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
+ PrivateNumber
b)
where a :: PrivateNumber
a = CurveCommon -> PrivateNumber
ecc_a CurveCommon
cc
b :: PrivateNumber
b = CurveCommon -> PrivateNumber
ecc_b CurveCommon
cc
eqModP :: PrivateNumber -> PrivateNumber -> Bool
eqModP z1 :: PrivateNumber
z1 z2 :: PrivateNumber
z2 = (PrivateNumber
z1 PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
p) PrivateNumber -> PrivateNumber -> Bool
forall a. Eq a => a -> a -> Bool
== (PrivateNumber
z2 PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
p)
isValid :: PrivateNumber -> Bool
isValid e :: PrivateNumber
e = PrivateNumber
e PrivateNumber -> PrivateNumber -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& PrivateNumber
e PrivateNumber -> PrivateNumber -> Bool
forall a. Ord a => a -> a -> Bool
< PrivateNumber
p
isPointValid (CurveF2m (CurveBinary fx :: PrivateNumber
fx cc :: CurveCommon
cc)) (Point x :: PrivateNumber
x y :: PrivateNumber
y) =
[Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ PrivateNumber -> Bool
isValid PrivateNumber
x
, PrivateNumber -> Bool
isValid PrivateNumber
y
, ((((PrivateNumber
x PrivateNumber -> PrivateNumber -> PrivateNumber
`add` PrivateNumber
a) PrivateNumber -> PrivateNumber -> PrivateNumber
`mul` PrivateNumber
x PrivateNumber -> PrivateNumber -> PrivateNumber
`add` PrivateNumber
y) PrivateNumber -> PrivateNumber -> PrivateNumber
`mul` PrivateNumber
x) PrivateNumber -> PrivateNumber -> PrivateNumber
`add` PrivateNumber
b PrivateNumber -> PrivateNumber -> PrivateNumber
`add` (PrivateNumber -> PrivateNumber -> PrivateNumber
squareF2m PrivateNumber
fx PrivateNumber
y)) PrivateNumber -> PrivateNumber -> Bool
forall a. Eq a => a -> a -> Bool
== 0
]
where a :: PrivateNumber
a = CurveCommon -> PrivateNumber
ecc_a CurveCommon
cc
b :: PrivateNumber
b = CurveCommon -> PrivateNumber
ecc_b CurveCommon
cc
add :: PrivateNumber -> PrivateNumber -> PrivateNumber
add = PrivateNumber -> PrivateNumber -> PrivateNumber
addF2m
mul :: PrivateNumber -> PrivateNumber -> PrivateNumber
mul = PrivateNumber -> PrivateNumber -> PrivateNumber -> PrivateNumber
mulF2m PrivateNumber
fx
isValid :: PrivateNumber -> Bool
isValid e :: PrivateNumber
e = PrivateNumber -> PrivateNumber -> PrivateNumber
modF2m PrivateNumber
fx PrivateNumber
e PrivateNumber -> PrivateNumber -> Bool
forall a. Eq a => a -> a -> Bool
== PrivateNumber
e
divmod :: Integer -> Integer -> Integer -> Maybe Integer
divmod :: PrivateNumber
-> PrivateNumber -> PrivateNumber -> Maybe PrivateNumber
divmod y :: PrivateNumber
y x :: PrivateNumber
x m :: PrivateNumber
m = do
PrivateNumber
i <- PrivateNumber -> PrivateNumber -> Maybe PrivateNumber
inverse (PrivateNumber
x PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
m) PrivateNumber
m
PrivateNumber -> Maybe PrivateNumber
forall (m :: * -> *) a. Monad m => a -> m a
return (PrivateNumber -> Maybe PrivateNumber)
-> PrivateNumber -> Maybe PrivateNumber
forall a b. (a -> b) -> a -> b
$ PrivateNumber
y PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Num a => a -> a -> a
* PrivateNumber
i PrivateNumber -> PrivateNumber -> PrivateNumber
forall a. Integral a => a -> a -> a
`mod` PrivateNumber
m