| 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 |