summaryrefslogtreecommitdiff
path: root/src/Crypto/ECC/Simple/Prim.hs
diff options
context:
space:
mode:
Diffstat (limited to 'src/Crypto/ECC/Simple/Prim.hs')
-rw-r--r--src/Crypto/ECC/Simple/Prim.hs208
1 files changed, 0 insertions, 208 deletions
diff --git a/src/Crypto/ECC/Simple/Prim.hs b/src/Crypto/ECC/Simple/Prim.hs
deleted file mode 100644
index 117988f2..00000000
--- a/src/Crypto/ECC/Simple/Prim.hs
+++ /dev/null
@@ -1,208 +0,0 @@
1-- | Elliptic Curve Arithmetic.
2--
3-- /WARNING:/ These functions are vulnerable to timing attacks.
4{-# LANGUAGE ScopedTypeVariables #-}
5module Crypto.ECC.Simple.Prim
6 ( scalarGenerate
7 , scalarFromInteger
8 , pointAdd
9 , pointDouble
10 , pointBaseMul
11 , pointMul
12 , pointAddTwoMuls
13 , pointFromIntegers
14 , isPointAtInfinity
15 , isPointValid
16 ) where
17
18import Data.Maybe
19import Data.Typeable
20import Crypto.Internal.Imports
21import Crypto.Number.ModArithmetic
22import Crypto.Number.F2m
23import Crypto.Number.Generate (generateBetween)
24import Crypto.ECC.Simple.Types
25-- import Crypto.Error
26import Crypto.Error.Types
27import Crypto.Random
28
29-- | Generate a valid scalar for a specific Curve
30scalarGenerate :: forall randomly curve . (MonadRandom randomly, Curve curve) => randomly (Scalar curve)
31scalarGenerate =
32 Scalar <$> generateBetween 1 (n - 1)
33 where
34 n = curveEccN $ curveParameters (Proxy :: Proxy curve)
35
36scalarFromInteger :: forall curve . Curve curve => Integer -> CryptoFailable (Scalar curve)
37scalarFromInteger n
38 | n < 0 || n >= mx = CryptoFailed $ CryptoError_EcScalarOutOfBounds
39 | otherwise = CryptoPassed $ Scalar n
40 where
41 mx = case curveType (Proxy :: Proxy curve) of
42 CurveBinary (CurveBinaryParam b) -> b
43 CurvePrime (CurvePrimeParam p) -> p
44
45--TODO: Extract helper function for `fromMaybe PointO...`
46
47-- | Elliptic Curve point negation:
48-- @pointNegate p@ returns point @q@ such that @pointAdd p q == PointO@.
49pointNegate :: Curve curve => Point curve -> Point curve
50pointNegate PointO = PointO
51pointNegate point@(Point x y) =
52 case curveType point of
53 CurvePrime {} -> Point x (-y)
54 CurveBinary {} -> Point x (x `addF2m` y)
55
56-- | Elliptic Curve point addition.
57--
58-- /WARNING:/ Vulnerable to timing attacks.
59pointAdd :: Curve curve => Point curve -> Point curve -> Point curve
60pointAdd PointO PointO = PointO
61pointAdd PointO q = q
62pointAdd p PointO = p
63pointAdd p q
64 | p == q = pointDouble p
65 | p == pointNegate q = PointO
66pointAdd point@(Point xp yp) (Point xq yq) =
67 case ty of
68 CurvePrime (CurvePrimeParam pr) -> fromMaybe PointO $ do
69 s <- divmod (yp - yq) (xp - xq) pr
70 let xr = (s ^ (2::Int) - xp - xq) `mod` pr
71 yr = (s * (xp - xr) - yp) `mod` pr
72 return $ Point xr yr
73 CurveBinary (CurveBinaryParam fx) -> fromMaybe PointO $ do
74 s <- divF2m fx (yp `addF2m` yq) (xp `addF2m` xq)
75 let xr = mulF2m fx s s `addF2m` s `addF2m` xp `addF2m` xq `addF2m` a
76 yr = mulF2m fx s (xp `addF2m` xr) `addF2m` xr `addF2m` yp
77 return $ Point xr yr
78 where
79 ty = curveType point
80 cc = curveParameters point
81 a = curveEccA cc
82
83-- | Elliptic Curve point doubling.
84--
85-- /WARNING:/ Vulnerable to timing attacks.
86--
87-- This perform the following calculation:
88-- > lambda = (3 * xp ^ 2 + a) / 2 yp
89-- > xr = lambda ^ 2 - 2 xp
90-- > yr = lambda (xp - xr) - yp
91--
92-- With binary curve:
93-- > xp == 0 => P = O
94-- > otherwise =>
95-- > s = xp + (yp / xp)
96-- > xr = s ^ 2 + s + a
97-- > yr = xp ^ 2 + (s+1) * xr
98--
99pointDouble :: Curve curve => Point curve -> Point curve
100pointDouble PointO = PointO
101pointDouble point@(Point xp yp) =
102 case ty of
103 CurvePrime (CurvePrimeParam pr) -> fromMaybe PointO $ do
104 lambda <- divmod (3 * xp ^ (2::Int) + a) (2 * yp) pr
105 let xr = (lambda ^ (2::Int) - 2 * xp) `mod` pr
106 yr = (lambda * (xp - xr) - yp) `mod` pr
107 return $ Point xr yr
108 CurveBinary (CurveBinaryParam fx)
109 | xp == 0 -> PointO
110 | otherwise -> fromMaybe PointO $ do
111 s <- return . addF2m xp =<< divF2m fx yp xp
112 let xr = mulF2m fx s s `addF2m` s `addF2m` a
113 yr = mulF2m fx xp xp `addF2m` mulF2m fx xr (s `addF2m` 1)
114 return $ Point xr yr
115 where
116 ty = curveType point
117 cc = curveParameters point
118 a = curveEccA cc
119
120-- | Elliptic curve point multiplication using the base
121--
122-- /WARNING:/ Vulnerable to timing attacks.
123pointBaseMul :: Curve curve => Scalar curve -> Point curve
124pointBaseMul n = pointMul n (curveEccG $ curveParameters (Proxy :: Proxy curve))
125
126-- | Elliptic curve point multiplication (double and add algorithm).
127--
128-- /WARNING:/ Vulnerable to timing attacks.
129pointMul :: Curve curve => Scalar curve -> Point curve -> Point curve
130pointMul _ PointO = PointO
131pointMul (Scalar n) p
132 | n == 0 = PointO
133 | n == 1 = p
134 | odd n = pointAdd p (pointMul (Scalar (n - 1)) p)
135 | otherwise = pointMul (Scalar (n `div` 2)) (pointDouble p)
136
137-- | Elliptic curve double-scalar multiplication (uses Shamir's trick).
138--
139-- > pointAddTwoMuls n1 p1 n2 p2 == pointAdd (pointMul n1 p1)
140-- > (pointMul n2 p2)
141--
142-- /WARNING:/ Vulnerable to timing attacks.
143pointAddTwoMuls :: Curve curve => Scalar curve -> Point curve -> Scalar curve -> Point curve -> Point curve
144pointAddTwoMuls _ PointO _ PointO = PointO
145pointAddTwoMuls _ PointO n2 p2 = pointMul n2 p2
146pointAddTwoMuls n1 p1 _ PointO = pointMul n1 p1
147pointAddTwoMuls (Scalar n1) p1 (Scalar n2) p2 = go (n1, n2)
148 where
149 p0 = pointAdd p1 p2
150
151 go (0, 0 ) = PointO
152 go (k1, k2) =
153 let q = pointDouble $ go (k1 `div` 2, k2 `div` 2)
154 in case (odd k1, odd k2) of
155 (True , True ) -> pointAdd p0 q
156 (True , False ) -> pointAdd p1 q
157 (False , True ) -> pointAdd p2 q
158 (False , False ) -> q
159
160-- | Check if a point is the point at infinity.
161isPointAtInfinity :: Point curve -> Bool
162isPointAtInfinity PointO = True
163isPointAtInfinity _ = False
164
165-- | Make a point on a curve from integer (x,y) coordinate
166--
167-- if the point is not valid related to the curve then an error is
168-- returned instead of a point
169pointFromIntegers :: forall curve . Curve curve => (Integer, Integer) -> CryptoFailable (Point curve)
170pointFromIntegers (x,y)
171 | isPointValid (Proxy :: Proxy curve) x y = CryptoPassed $ Point x y
172 | otherwise = CryptoFailed $ CryptoError_PointCoordinatesInvalid
173
174-- | check if a point is on specific curve
175--
176-- This perform three checks:
177--
178-- * x is not out of range
179-- * y is not out of range
180-- * the equation @y^2 = x^3 + a*x + b (mod p)@ holds
181isPointValid :: Curve curve => proxy curve -> Integer -> Integer -> Bool
182isPointValid proxy x y =
183 case ty of
184 CurvePrime (CurvePrimeParam p) ->
185 let a = curveEccA cc
186 b = curveEccB cc
187 eqModP z1 z2 = (z1 `mod` p) == (z2 `mod` p)
188 isValid e = e >= 0 && e < p
189 in isValid x && isValid y && (y ^ (2 :: Int)) `eqModP` (x ^ (3 :: Int) + a * x + b)
190 CurveBinary (CurveBinaryParam fx) ->
191 let a = curveEccA cc
192 b = curveEccB cc
193 add = addF2m
194 mul = mulF2m fx
195 isValid e = modF2m fx e == e
196 in and [ isValid x
197 , isValid y
198 , ((((x `add` a) `mul` x `add` y) `mul` x) `add` b `add` (squareF2m fx y)) == 0
199 ]
200 where
201 ty = curveType proxy
202 cc = curveParameters proxy
203
204-- | div and mod
205divmod :: Integer -> Integer -> Integer -> Maybe Integer
206divmod y x m = do
207 i <- inverse (x `mod` m) m
208 return $ y * i `mod` m
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 18:55:24 +0000