{-# OPTIONS_GHC -O2 -feager-blackholing #-}
{-# LANGUAGE Safe, GADTs, DeriveDataTypeable, NoImplicitPrelude, StrictData #-}
module Crypto.ECC.Weierstrass.Internal.Curvemath where
import safe Prelude (Eq,Show,(==),(&&),Integer,Int,show,Bool,(++),(-),otherwise,(<),mod,(^),(+))
import safe qualified Data.Bits as B ((.&.))
import safe Data.Typeable(Typeable)
import safe qualified Crypto.Fi as FP
data EC a where
ECi :: Int
-> FP.FPrime
-> FP.FPrime
-> FP.FPrime
-> EC FP.FPrime
deriving(Typeable)
instance Eq (EC a) where
(ECi Int
l FPrime
b FPrime
p FPrime
r) == :: EC a -> EC a -> Bool
== (ECi Int
l' FPrime
b' FPrime
p' FPrime
r') = Int
lInt -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==Int
l' Bool -> Bool -> Bool
&& FPrime -> FPrime -> Bool
FP.eq FPrime
b FPrime
b' Bool -> Bool -> Bool
&& FPrime -> FPrime -> Bool
FP.eq FPrime
p FPrime
p' Bool -> Bool -> Bool
&& FPrime -> FPrime -> Bool
FP.eq FPrime
r FPrime
r'
instance Show (EC a) where
show :: EC a -> String
show (ECi Int
l FPrime
b FPrime
p FPrime
r) = String
"Curve with length" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
l String -> ShowS
forall a. [a] -> [a] -> [a]
++String
", y^2=x^3-3*x+" String -> ShowS
forall a. [a] -> [a] -> [a]
++ FPrime -> String
forall a. Show a => a -> String
show FPrime
b String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" mod " String -> ShowS
forall a. [a] -> [a] -> [a]
++ FPrime -> String
forall a. Show a => a -> String
show FPrime
p String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" and group order " String -> ShowS
forall a. [a] -> [a] -> [a]
++ FPrime -> String
forall a. Show a => a -> String
show FPrime
r String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"."
data ECPF a where
ECPp :: FP.FPrime
-> FP.FPrime
-> FP.FPrime
-> ECPF FP.FPrime
deriving(Typeable)
instance Eq (ECPF a) where
(ECPp FPrime
x FPrime
y FPrime
z) == :: ECPF a -> ECPF a -> Bool
== (ECPp FPrime
x' FPrime
y' FPrime
z') = FPrime -> FPrime -> Bool
FP.eq FPrime
x FPrime
x' Bool -> Bool -> Bool
&& FPrime -> FPrime -> Bool
FP.eq FPrime
y FPrime
y' Bool -> Bool -> Bool
&& FPrime -> FPrime -> Bool
FP.eq FPrime
z FPrime
z'
instance Show (ECPF a) where
show :: ECPF a -> String
show (ECPp FPrime
x FPrime
y FPrime
z) = String
"x: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ FPrime -> String
forall a. Show a => a -> String
show FPrime
x String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" y: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ FPrime -> String
forall a. Show a => a -> String
show FPrime
y String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" z: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ FPrime -> String
forall a. Show a => a -> String
show FPrime
z
isinf :: EC a -> ECPF a -> Bool
isinf :: EC a -> ECPF a -> Bool
isinf (ECi Int
l FPrime
_ FPrime
_ FPrime
_) (ECPp FPrime
x FPrime
_ FPrime
z) = FPrime -> FPrime -> Bool
FP.eq FPrime
x (Int -> FPrime -> FPrime
FP.fromInteger Int
l FPrime
0) Bool -> Bool -> Bool
&& FPrime -> FPrime -> Bool
FP.eq FPrime
z (Int -> FPrime -> FPrime
FP.fromInteger Int
l FPrime
0)
export :: EC a -> ECPF a -> (Integer,Integer)
export :: EC a -> ECPF a -> (FPrime, FPrime)
export c :: EC a
c@ECi{} pt :: ECPF a
pt@ECPp{} = let (FPrime
x,FPrime
y) = EC a -> ECPF a -> (FPrime, FPrime)
forall a. EC a -> ECPF a -> (FPrime, FPrime)
affine EC a
c ECPF a
pt
in (FPrime -> FPrime
FP.toInteger FPrime
x, FPrime -> FPrime
FP.toInteger FPrime
y)
affine :: EC a -> ECPF a -> (Integer,Integer)
affine :: EC a -> ECPF a -> (FPrime, FPrime)
affine (ECi Int
_ FPrime
_ FPrime
p FPrime
_) (ECPp FPrime
x FPrime
y FPrime
z) = let z' :: FPrime
z' = FPrime -> FPrime -> FPrime
FP.inv FPrime
p FPrime
z
in (FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x FPrime
z', FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
y FPrime
z')
{-# INLINABLE affine #-}
pdouble :: EC a -> ECPF a -> ECPF a
pdouble :: EC a -> ECPF a -> ECPF a
pdouble (ECi Int
_ FPrime
b FPrime
p FPrime
_) (ECPp FPrime
x FPrime
y FPrime
z) =
let t0_0 :: FPrime
t0_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x FPrime
x
t1_0 :: FPrime
t1_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
y FPrime
y
t2_0 :: FPrime
t2_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
z FPrime
z
t3_0 :: FPrime
t3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x FPrime
y
t3_1 :: FPrime
t3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t3_0 FPrime
t3_0
z3_0 :: FPrime
z3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x FPrime
z
z3_1 :: FPrime
z3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
z3_0 FPrime
z3_0
y3_0 :: FPrime
y3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
b FPrime
t2_0
y3_1 :: FPrime
y3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
y3_0 FPrime
z3_1
x3_0 :: FPrime
x3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
y3_1 FPrime
y3_1
y3_2 :: FPrime
y3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x3_0 FPrime
y3_1
x3_1 :: FPrime
x3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
t1_0 FPrime
y3_2
y3_3 :: FPrime
y3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t1_0 FPrime
y3_2
y3_4 :: FPrime
y3_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x3_1 FPrime
y3_3
x3_2 :: FPrime
x3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x3_1 FPrime
t3_1
t3_2 :: FPrime
t3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t2_0 FPrime
t2_0
t2_1 :: FPrime
t2_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t2_0 FPrime
t3_2
z3_2 :: FPrime
z3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
b FPrime
z3_1
z3_3 :: FPrime
z3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
z3_2 FPrime
t2_1
z3_4 :: FPrime
z3_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
z3_3 FPrime
t0_0
t3_3 :: FPrime
t3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
z3_4 FPrime
z3_4
z3_5 :: FPrime
z3_5 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
z3_4 FPrime
t3_3
t3_4 :: FPrime
t3_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t0_0 FPrime
t0_0
t0_1 :: FPrime
t0_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t3_4 FPrime
t0_0
t0_2 :: FPrime
t0_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
t0_1 FPrime
t2_1
t0_3 :: FPrime
t0_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t0_2 FPrime
z3_5
y3_5 :: FPrime
y3_5 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
y3_4 FPrime
t0_3
t0_4 :: FPrime
t0_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
y FPrime
z
t0_5 :: FPrime
t0_5 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t0_4 FPrime
t0_4
z3_6 :: FPrime
z3_6 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t0_5 FPrime
z3_5
x3_3 :: FPrime
x3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
x3_2 FPrime
z3_6
z3_7 :: FPrime
z3_7 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t0_5 FPrime
t1_0
z3_8 :: FPrime
z3_8 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
z3_7 FPrime
z3_7
z3_9 :: FPrime
z3_9 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
z3_8 FPrime
z3_8
in FPrime -> FPrime -> FPrime -> ECPF FPrime
ECPp FPrime
x3_3 FPrime
y3_5 FPrime
z3_9
{-# INLINABLE pdouble #-}
padd :: EC a -> ECPF a -> ECPF a -> ECPF a
padd :: EC a -> ECPF a -> ECPF a -> ECPF a
padd (ECi Int
_ FPrime
b FPrime
p FPrime
_) (ECPp FPrime
x1 FPrime
y1 FPrime
z1) (ECPp FPrime
x2 FPrime
y2 FPrime
z2)
= let t0_0 :: FPrime
t0_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x1 FPrime
x2
t1_0 :: FPrime
t1_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
y1 FPrime
y2
t2_0 :: FPrime
t2_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
z1 FPrime
z2
t3_0 :: FPrime
t3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x1 FPrime
y1
t4_0 :: FPrime
t4_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x2 FPrime
y2
t3_1 :: FPrime
t3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t3_0 FPrime
t4_0
t4_1 :: FPrime
t4_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t0_0 FPrime
t1_0
t3_2 :: FPrime
t3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
t3_1 FPrime
t4_1
t4_2 :: FPrime
t4_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
y1 FPrime
z1
x3_0 :: FPrime
x3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
y2 FPrime
z2
t4_3 :: FPrime
t4_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t4_2 FPrime
x3_0
x3_1 :: FPrime
x3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t1_0 FPrime
t2_0
t4_4 :: FPrime
t4_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
t4_3 FPrime
x3_1
x3_2 :: FPrime
x3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x1 FPrime
z1
y3_0 :: FPrime
y3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x2 FPrime
z2
x3_3 :: FPrime
x3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x3_2 FPrime
y3_0
y3_1 :: FPrime
y3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t0_0 FPrime
t2_0
y3_2 :: FPrime
y3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
x3_3 FPrime
y3_1
z3_0 :: FPrime
z3_0 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
b FPrime
t2_0
x3_4 :: FPrime
x3_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
y3_2 FPrime
z3_0
z3_1 :: FPrime
z3_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x3_4 FPrime
x3_4
x3_5 :: FPrime
x3_5 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
x3_4 FPrime
z3_1
z3_2 :: FPrime
z3_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
t1_0 FPrime
x3_5
x3_6 :: FPrime
x3_6 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t1_0 FPrime
x3_5
y3_3 :: FPrime
y3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
b FPrime
y3_2
t1_1 :: FPrime
t1_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t2_0 FPrime
t2_0
t2_1 :: FPrime
t2_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t1_1 FPrime
t2_0
y3_4 :: FPrime
y3_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
y3_3 FPrime
t2_1
y3_5 :: FPrime
y3_5 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
y3_4 FPrime
t0_0
t1_2 :: FPrime
t1_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
y3_5 FPrime
y3_5
y3_6 :: FPrime
y3_6 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t1_2 FPrime
y3_5
t1_3 :: FPrime
t1_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t0_0 FPrime
t0_0
t0_1 :: FPrime
t0_1 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
t1_3 FPrime
t0_0
t0_2 :: FPrime
t0_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
t0_1 FPrime
t2_1
t1_4 :: FPrime
t1_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t4_4 FPrime
y3_6
t2_2 :: FPrime
t2_2 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t0_2 FPrime
y3_6
y3_7 :: FPrime
y3_7 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
x3_6 FPrime
z3_2
y3_8 :: FPrime
y3_8 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
y3_7 FPrime
t2_2
x3_7 :: FPrime
x3_7 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t3_2 FPrime
x3_6
x3_8 :: FPrime
x3_8 = FPrime -> FPrime -> FPrime -> FPrime
FP.subr FPrime
p FPrime
x3_7 FPrime
t1_4
z3_3 :: FPrime
z3_3 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t4_4 FPrime
z3_2
t1_5 :: FPrime
t1_5 = FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
t3_2 FPrime
t0_2
z3_4 :: FPrime
z3_4 = FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p FPrime
z3_3 FPrime
t1_5
in FPrime -> FPrime -> FPrime -> ECPF FPrime
ECPp FPrime
x3_8 FPrime
y3_8 FPrime
z3_4
{-# INLINABLE padd #-}
ison :: EC a -> ECPF a -> Bool
ison :: EC a -> ECPF a -> Bool
ison (ECi Int
l FPrime
beta FPrime
p FPrime
_) (ECPp FPrime
x FPrime
y FPrime
z) = FPrime -> FPrime -> Bool
FP.eq
(FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p (FPrime -> FPrime -> FPrime -> FPrime
FP.pow FPrime
p FPrime
y (FPrime
2::Integer)) FPrime
z)
(FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p (FPrime -> FPrime -> FPrime -> FPrime
FP.pow FPrime
p FPrime
x (FPrime
3::Integer)) (FPrime -> FPrime -> FPrime -> FPrime
FP.addr FPrime
p (FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p (FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p (FPrime -> FPrime -> FPrime
FP.neg FPrime
p (Int -> FPrime -> FPrime
FP.fromInteger Int
l FPrime
3)) FPrime
x) (FPrime -> FPrime -> FPrime -> FPrime
FP.pow FPrime
p FPrime
z (FPrime
2::Integer))) (FPrime -> FPrime -> FPrime -> FPrime
FP.mulr FPrime
p FPrime
beta (FPrime -> FPrime -> FPrime -> FPrime
FP.pow FPrime
p FPrime
z (FPrime
3::Integer)))))
{-# INLINABLE ison #-}
pmul :: EC a -> ECPF a -> FP.FPrime -> ECPF a
pmul :: EC a -> ECPF a -> FPrime -> ECPF a
pmul curve :: EC a
curve@(ECi Int
l FPrime
_ FPrime
p FPrime
_) (ECPp FPrime
x FPrime
y FPrime
z) FPrime
k =
let alleeins :: FPrime
alleeins = Int -> FPrime -> FPrime
FP.fromInteger Int
l (FPrime
2FPrime -> Int -> FPrime
forall a b. (Num a, Integral b) => a -> b -> a
^Int
lFPrime -> FPrime -> FPrime
forall a. Num a => a -> a -> a
-FPrime
1)
eins :: FPrime
eins = Int -> FPrime -> FPrime
FP.fromInteger Int
l FPrime
1
k' :: FPrime
k' = FPrime
k FPrime -> FPrime -> FPrime
forall a. Integral a => a -> a -> a
`mod` (FPrime
pFPrime -> FPrime -> FPrime
forall a. Num a => a -> a -> a
+FPrime
1)
ex :: ECPF a -> Int -> ECPF a
ex ECPF a
erg Int
j
| Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = ECPF a
erg
| Bool
otherwise = let s :: FPrime
s = FPrime -> Int -> FPrime
FP.condBit FPrime
k' Int
j
realpattern :: FPrime
realpattern = FPrime -> FPrime -> FPrime
FP.mul FPrime
alleeins FPrime
s
invpattern :: FPrime
invpattern = FPrime -> FPrime -> FPrime
FP.mul FPrime
alleeins (FPrime -> FPrime -> FPrime
FP.sub FPrime
eins FPrime
s)
x' :: FPrime
x' = FPrime
x FPrime -> FPrime -> FPrime
forall a. Bits a => a -> a -> a
B..&. FPrime
realpattern
y' :: FPrime
y' = FPrime -> FPrime -> FPrime
FP.add (FPrime
y FPrime -> FPrime -> FPrime
forall a. Bits a => a -> a -> a
B..&. FPrime
realpattern) (FPrime
eins FPrime -> FPrime -> FPrime
forall a. Bits a => a -> a -> a
B..&. FPrime
invpattern)
z' :: FPrime
z' = (FPrime
z FPrime -> FPrime -> FPrime
forall a. Bits a => a -> a -> a
B..&. FPrime
realpattern)
in ECPF a -> Int -> ECPF a
ex (EC a -> ECPF a -> ECPF a -> ECPF a
forall a. EC a -> ECPF a -> ECPF a -> ECPF a
padd EC a
curve (EC a -> ECPF a -> ECPF a
forall a. EC a -> ECPF a -> ECPF a
pdouble EC a
curve ECPF a
erg) (FPrime -> FPrime -> FPrime -> ECPF FPrime
ECPp FPrime
x' FPrime
y' FPrime
z')) (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
in ECPF a -> Int -> ECPF a
ex (FPrime -> FPrime -> FPrime -> ECPF FPrime
ECPp FPrime
0 FPrime
1 FPrime
0) (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
{-# INLINABLE pmul #-}