Debian Codegraph @

Crypto/ECC/Simple/Prim.hs

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