{-# OPTIONS_HADDOCK hide #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DuplicateRecordFields #-}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE TypeFamilies #-}
{-|
Module: Crypto.Spake2.Groups.Ed25519
Description: Ed25519 group for SPAKE2

Derived from @ed25519_basic.py@ in [python-spake2](https://github.com/warner/python-spake2),
in turn derived from the slow, reference, Python implementation at
<http://ed25519.cr.yp.to/python/ed25519.py>
-}
module Crypto.Spake2.Groups.Ed25519
  ( Ed25519(..)
  -- * Exported for testing
  , l
  , generator
  ) where

import Protolude hiding (group)

import Crypto.Error (CryptoFailable(..), CryptoError(..))
import Crypto.Number.Generate (generateMax)
import Crypto.Number.ModArithmetic (expSafe, inverseCoprimes)
import Crypto.Number.Serialize (i2osp, os2ip)
import Data.ByteArray (ByteArray, ByteArrayAccess)
import qualified Data.ByteArray as ByteArray
import qualified Data.List as List

import Crypto.Spake2.Group (AbelianGroup(..), Group(..), KeyPair(..), scalarSizeBytes)
import Crypto.Spake2.Util (bytesToNumber, expandArbitraryElementSeed)

{-
Note [Ed25519 vs curve25519]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

As best as jml can tell,

* X25519 is Elliptic Curve Diffie-Hellman (ECDH) over Curve25519
* Ed25519 is Edwards-curve Digital Signature Algorithm (EdDSA) over Curve25519

(quoted from a [StackOverflow answer](https://crypto.stackexchange.com/questions/27866/why-curve25519-for-encryption-but-ed25519-for-signatures))

This means the underlying curve is the same,
and Ed25519 is the use of that curve in signing,
and X25519 is the curve used in key exchange.

Complicated by the fact that Curve25519 /used/ to be the name of ECDH over Curve25519.

Since our primary goal is Python interoperability,
we are going to implement an analogue of the Python code here,
and call it Ed25519.

Once that is done, we can explore using Cryptonite's Curve25519 logic,
ideally demonstrating its equivalence with some automated tests.

<https://security.stackexchange.com/questions/50878/ecdsa-vs-ecdh-vs-ed25519-vs-curve25519>
<https://crypto.stackexchange.com/questions/27866/why-curve25519-for-encryption-but-ed25519-for-signatures>
-}

data Ed25519 = Ed25519 deriving (Ed25519 -> Ed25519 -> Bool
(Ed25519 -> Ed25519 -> Bool)
-> (Ed25519 -> Ed25519 -> Bool) -> Eq Ed25519
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Ed25519 -> Ed25519 -> Bool
$c/= :: Ed25519 -> Ed25519 -> Bool
== :: Ed25519 -> Ed25519 -> Bool
$c== :: Ed25519 -> Ed25519 -> Bool
Eq, Int -> Ed25519 -> ShowS
[Ed25519] -> ShowS
Ed25519 -> String
(Int -> Ed25519 -> ShowS)
-> (Ed25519 -> String) -> ([Ed25519] -> ShowS) -> Show Ed25519
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Ed25519] -> ShowS
$cshowList :: [Ed25519] -> ShowS
show :: Ed25519 -> String
$cshow :: Ed25519 -> String
showsPrec :: Int -> Ed25519 -> ShowS
$cshowsPrec :: Int -> Ed25519 -> ShowS
Show)

instance Group Ed25519 where
  type Element Ed25519 = ExtendedPoint 'Member

  elementAdd :: Ed25519 -> Element Ed25519 -> Element Ed25519 -> Element Ed25519
elementAdd _ x :: Element Ed25519
x y :: Element Ed25519
y = ExtendedPoint 'Member
-> ExtendedPoint 'Member -> ExtendedPoint 'Member
forall (a :: GroupMembership).
ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
addExtendedPoints Element Ed25519
ExtendedPoint 'Member
x Element Ed25519
ExtendedPoint 'Member
y
  elementNegate :: Ed25519 -> Element Ed25519 -> Element Ed25519
elementNegate _ x :: Element Ed25519
x = ExtendedPoint 'Member -> ExtendedPoint 'Member
forall (preserving :: GroupMembership).
ExtendedPoint preserving -> ExtendedPoint preserving
negateExtendedPoint Element Ed25519
ExtendedPoint 'Member
x
  groupIdentity :: Ed25519 -> Element Ed25519
groupIdentity _ = HasCallStack => ExtendedPoint 'Unknown -> ExtendedPoint 'Member
ExtendedPoint 'Unknown -> ExtendedPoint 'Member
assertInGroup ExtendedPoint 'Unknown
forall (a :: GroupMembership). ExtendedPoint a
extendedZero

  encodeElement :: Ed25519 -> Element Ed25519 -> bytes
encodeElement _ x :: Element Ed25519
x = AffinePoint -> bytes
forall bytes.
(ByteArray bytes, ByteArrayAccess bytes) =>
AffinePoint -> bytes
encodeAffinePoint (ExtendedPoint 'Member -> AffinePoint
forall (a :: GroupMembership). ExtendedPoint a -> AffinePoint
extendedToAffine' Element Ed25519
ExtendedPoint 'Member
x)
  decodeElement :: Ed25519 -> bytes -> CryptoFailable (Element Ed25519)
decodeElement _ bytes :: bytes
bytes = Either Error (ExtendedPoint 'Member)
-> CryptoFailable (Element Ed25519)
forall a. Either Error a -> CryptoFailable a
toCryptoFailable (Either Error (ExtendedPoint 'Member)
 -> CryptoFailable (Element Ed25519))
-> Either Error (ExtendedPoint 'Member)
-> CryptoFailable (Element Ed25519)
forall a b. (a -> b) -> a -> b
$ do
    ExtendedPoint 'Unknown
extended <- AffinePoint -> ExtendedPoint 'Unknown
affineToExtended (AffinePoint -> ExtendedPoint 'Unknown)
-> Either Error AffinePoint
-> Either Error (ExtendedPoint 'Unknown)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> bytes -> Either Error AffinePoint
forall bytes.
(ByteArray bytes, ByteArrayAccess bytes) =>
bytes -> Either Error AffinePoint
decodeAffinePoint bytes
bytes
    ExtendedPoint 'Unknown -> Either Error (ExtendedPoint 'Member)
ensureInGroup ExtendedPoint 'Unknown
extended

  elementSizeBits :: Ed25519 -> Int
elementSizeBits _ = 255

  arbitraryElement :: Ed25519 -> bytes -> Element Ed25519
arbitraryElement group :: Ed25519
group bytes :: bytes
bytes =
    let seed :: ByteString
seed = bytes -> Int -> ByteString
forall ikm out.
(ByteArrayAccess ikm, ByteArray out) =>
ikm -> Int -> out
expandArbitraryElementSeed bytes
bytes (Ed25519 -> Int
forall group. AbelianGroup group => group -> Int
scalarSizeBytes Ed25519
group Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 16) :: ByteString
        y :: Integer
y = ByteString -> Integer
forall bytes. ByteArrayAccess bytes => bytes -> Integer
bytesToNumber ByteString
seed Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    in
    [ExtendedPoint 'Member] -> ExtendedPoint 'Member
forall a. [a] -> a
List.head [ ExtendedPoint 'Member
element | Right element :: ExtendedPoint 'Member
element <- (Integer -> Either Error (ExtendedPoint 'Member))
-> [Integer] -> [Either Error (ExtendedPoint 'Member)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map Integer -> Either Error (Element Ed25519)
Integer -> Either Error (ExtendedPoint 'Member)
makeGroupMember [Integer
y..] ]

instance AbelianGroup Ed25519 where
  type Scalar Ed25519 = Integer

  scalarMultiply :: Ed25519 -> Scalar Ed25519 -> Element Ed25519 -> Element Ed25519
scalarMultiply _ n :: Scalar Ed25519
n x :: Element Ed25519
x = Integer -> ExtendedPoint 'Member -> ExtendedPoint 'Member
forall (a :: GroupMembership).
Integer -> ExtendedPoint a -> ExtendedPoint a
safeScalarMultiply Integer
Scalar Ed25519
n Element Ed25519
ExtendedPoint 'Member
x

  integerToScalar :: Ed25519 -> Integer -> Scalar Ed25519
integerToScalar _ x :: Integer
x = Integer
Scalar Ed25519
x
  scalarToInteger :: Ed25519 -> Scalar Ed25519 -> Integer
scalarToInteger _ x :: Scalar Ed25519
x = Integer
Scalar Ed25519
x

  scalarSizeBits :: Ed25519 -> Int
scalarSizeBits _ = 255

  generateElement :: Ed25519 -> randomly (KeyPair Ed25519)
generateElement group :: Ed25519
group = do
    Integer
scalar <- Integer -> randomly Integer
forall (m :: * -> *). MonadRandom m => Integer -> m Integer
generateMax Integer
l
    let element :: Element Ed25519
element = Ed25519 -> Scalar Ed25519 -> Element Ed25519 -> Element Ed25519
forall group.
AbelianGroup group =>
group -> Scalar group -> Element group -> Element group
scalarMultiply Ed25519
group Integer
Scalar Ed25519
scalar Element Ed25519
generator
    KeyPair Ed25519 -> randomly (KeyPair Ed25519)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Element Ed25519 -> Scalar Ed25519 -> KeyPair Ed25519
forall group. Element group -> Scalar group -> KeyPair group
KeyPair Element Ed25519
element Integer
Scalar Ed25519
scalar)


-- | Errors that can occur within the group.
data Error
  = NotOnCurve Integer Integer
  | NotInGroup (ExtendedPoint 'Unknown)
  | LowOrderPoint (ExtendedPoint 'Unknown)
  deriving (Error -> Error -> Bool
(Error -> Error -> Bool) -> (Error -> Error -> Bool) -> Eq Error
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Error -> Error -> Bool
$c/= :: Error -> Error -> Bool
== :: Error -> Error -> Bool
$c== :: Error -> Error -> Bool
Eq, Int -> Error -> ShowS
[Error] -> ShowS
Error -> String
(Int -> Error -> ShowS)
-> (Error -> String) -> ([Error] -> ShowS) -> Show Error
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Error] -> ShowS
$cshowList :: [Error] -> ShowS
show :: Error -> String
$cshow :: Error -> String
showsPrec :: Int -> Error -> ShowS
$cshowsPrec :: Int -> Error -> ShowS
Show)

-- | Translate internal errors into CryptoFailable.
toCryptoFailable :: Either Error a -> CryptoFailable a
toCryptoFailable :: Either Error a -> CryptoFailable a
toCryptoFailable (Right r :: a
r) = a -> CryptoFailable a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
r
toCryptoFailable (Left _) = CryptoError -> CryptoFailable a
forall a. CryptoError -> CryptoFailable a
CryptoFailed CryptoError
CryptoError_PointCoordinatesInvalid

-- | Guarantee an element is in the Ed25519 subgroup.
ensureInGroup :: ExtendedPoint 'Unknown -> Either Error (ExtendedPoint 'Member)
ensureInGroup :: ExtendedPoint 'Unknown -> Either Error (ExtendedPoint 'Member)
ensureInGroup element :: ExtendedPoint 'Unknown
element@ExtendedPoint{Integer
$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x :: Integer
x, Integer
$sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y :: Integer
y, Integer
$sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z :: Integer
z, Integer
$sel:t:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
t :: Integer
t} =
  if ExtendedPoint 'Unknown -> Bool
forall (irrelevant :: GroupMembership).
ExtendedPoint irrelevant -> Bool
isExtendedZero (Integer -> ExtendedPoint 'Unknown -> ExtendedPoint 'Unknown
forall (a :: GroupMembership).
Integer -> ExtendedPoint a -> ExtendedPoint a
safeScalarMultiply Integer
l ExtendedPoint 'Unknown
element)
  then ExtendedPoint 'Member -> Either Error (ExtendedPoint 'Member)
forall (f :: * -> *) a. Applicative f => a -> f a
pure $WExtendedPoint :: forall (groupMembership :: GroupMembership).
Integer
-> Integer -> Integer -> Integer -> ExtendedPoint groupMembership
ExtendedPoint { $sel:x:ExtendedPoint :: Integer
x = Integer
x, $sel:y:ExtendedPoint :: Integer
y = Integer
y, $sel:z:ExtendedPoint :: Integer
z = Integer
z, $sel:t:ExtendedPoint :: Integer
t = Integer
t}
  else  Error -> Either Error (ExtendedPoint 'Member)
forall e (m :: * -> *) a. MonadError e m => e -> m a
throwError (Error -> Either Error (ExtendedPoint 'Member))
-> Error -> Either Error (ExtendedPoint 'Member)
forall a b. (a -> b) -> a -> b
$ ExtendedPoint 'Unknown -> Error
NotInGroup ExtendedPoint 'Unknown
element

-- | Assert that an element is the Ed25519 subgroup.
--
-- Panics if it is not.
assertInGroup :: HasCallStack => ExtendedPoint 'Unknown -> ExtendedPoint 'Member
assertInGroup :: ExtendedPoint 'Unknown -> ExtendedPoint 'Member
assertInGroup element :: ExtendedPoint 'Unknown
element =
  -- XXX: Should we force evaluation of this? We mostly use it only for
  -- constants.
  case ExtendedPoint 'Unknown -> Either Error (ExtendedPoint 'Member)
ensureInGroup ExtendedPoint 'Unknown
element of
    Left err :: Error
err -> Text -> ExtendedPoint 'Member
forall a. HasCallStack => Text -> a
panic (Text -> ExtendedPoint 'Member) -> Text -> ExtendedPoint 'Member
forall a b. (a -> b) -> a -> b
$ "Element not in group (" Text -> Text -> Text
forall a. Semigroup a => a -> a -> a
<> Error -> Text
forall a b. (Show a, ConvertText String b) => a -> b
show Error
err Text -> Text -> Text
forall a. Semigroup a => a -> a -> a
<> "): " Text -> Text -> Text
forall a. Semigroup a => a -> a -> a
<> ExtendedPoint 'Unknown -> Text
forall a b. (Show a, ConvertText String b) => a -> b
show ExtendedPoint 'Unknown
element
    Right x :: ExtendedPoint 'Member
x -> ExtendedPoint 'Member
x

-- TODO: Document this.
-- Guess: the size of the subgroup? the group?
q :: Integer
q :: Integer
q = 2 Integer -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ 255 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- 19  -- XXX: force eval?

-- | The order of the group represented by 'Ed25519'.
--
-- Note that this is a subgroup of the underlying elliptic curve.
l :: Integer
l :: Integer
l = 2 Integer -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ 252 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ 27742317777372353535851937790883648493

-- TODO document this
dConst :: Integer
dConst :: Integer
dConst = (-121665 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer
inv 121666) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q  -- XXX: force eval?

-- TODO document this
i :: Integer
i :: Integer
i = Integer -> Integer -> Integer -> Integer
expSafe 2 ((Integer
qInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-1) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` 4) Integer
q  -- XXX: force eval

-- | The generator for the (sub)group represented by 'Ed25519'.
generator :: Element Ed25519
generator :: Element Ed25519
generator = HasCallStack => ExtendedPoint 'Unknown -> ExtendedPoint 'Member
ExtendedPoint 'Unknown -> Element Ed25519
assertInGroup (ExtendedPoint 'Unknown -> Element Ed25519)
-> ExtendedPoint 'Unknown -> Element Ed25519
forall a b. (a -> b) -> a -> b
$ AffinePoint -> ExtendedPoint 'Unknown
affineToExtended AffinePoint
b
  where
    b :: AffinePoint
b = case Integer -> Integer -> Either Error AffinePoint
makeAffinePoint (Integer
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q) (Integer
y Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q) of
          Left err :: Error
err -> Text -> AffinePoint
forall a. HasCallStack => Text -> a
panic (Text -> AffinePoint) -> Text -> AffinePoint
forall a b. (a -> b) -> a -> b
$ "Generator is not affine point: " Text -> Text -> Text
forall a. Semigroup a => a -> a -> a
<> Error -> Text
forall a b. (Show a, ConvertText String b) => a -> b
show Error
err
          Right r :: AffinePoint
r -> AffinePoint
r
    x :: Integer
x = Integer -> Integer
xRecover Integer
y
    y :: Integer
y = 4 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer
inv 5

-- | Calculate the inverse of @x@ modulo 'q'.
--
-- Assumes that @x@ is coprime with 'q' and non-zero.
-- Will raise an exception if either of these assumptions is false.
--
-- prop> \x -> (x * inv x) `mod` q == 1
inv :: Integer -> Integer
inv :: Integer -> Integer
inv x :: Integer
x = Integer -> Integer -> Integer
inverseCoprimes Integer
x Integer
q

xRecover :: Integer -> Integer
xRecover :: Integer -> Integer
xRecover y :: Integer
y =
  let x'' :: Integer
x'' = (Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- 1) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer
inv(Integer
dConst Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ 1)
      x' :: Integer
x' = Integer -> Integer -> Integer -> Integer
expSafe Integer
x'' ((Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ 3) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` 8) Integer
q
      x :: Integer
x = if (Integer
x' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x'') Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= 0
          then (Integer
x' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
i) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
          else Integer
x'
  in
    if Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
x then Integer
x else Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x


-- | Whether or not an extended point is a member of Ed25519.
data GroupMembership = Unknown | Member

-- | A point that might be a member of Ed25519.
-- Note: [Extended coordinates]
data ExtendedPoint (groupMembership :: GroupMembership)
  = ExtendedPoint
  { ExtendedPoint groupMembership -> Integer
x :: !Integer
  , ExtendedPoint groupMembership -> Integer
y :: !Integer
  , ExtendedPoint groupMembership -> Integer
z :: !Integer
  , ExtendedPoint groupMembership -> Integer
t :: !Integer
  } deriving (Int -> ExtendedPoint groupMembership -> ShowS
[ExtendedPoint groupMembership] -> ShowS
ExtendedPoint groupMembership -> String
(Int -> ExtendedPoint groupMembership -> ShowS)
-> (ExtendedPoint groupMembership -> String)
-> ([ExtendedPoint groupMembership] -> ShowS)
-> Show (ExtendedPoint groupMembership)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall (groupMembership :: GroupMembership).
Int -> ExtendedPoint groupMembership -> ShowS
forall (groupMembership :: GroupMembership).
[ExtendedPoint groupMembership] -> ShowS
forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> String
showList :: [ExtendedPoint groupMembership] -> ShowS
$cshowList :: forall (groupMembership :: GroupMembership).
[ExtendedPoint groupMembership] -> ShowS
show :: ExtendedPoint groupMembership -> String
$cshow :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> String
showsPrec :: Int -> ExtendedPoint groupMembership -> ShowS
$cshowsPrec :: forall (groupMembership :: GroupMembership).
Int -> ExtendedPoint groupMembership -> ShowS
Show)

-- XXX: jml unsure about overriding equality like this.
-- Note: [Extended coordinates]
instance Eq (ExtendedPoint a) where
  point1 :: ExtendedPoint a
point1 == :: ExtendedPoint a -> ExtendedPoint a -> Bool
== point2 :: ExtendedPoint a
point2 = ExtendedPoint a -> AffinePoint
forall (a :: GroupMembership). ExtendedPoint a -> AffinePoint
extendedToAffine' ExtendedPoint a
point1 AffinePoint -> AffinePoint -> Bool
forall a. Eq a => a -> a -> Bool
== ExtendedPoint a -> AffinePoint
forall (a :: GroupMembership). ExtendedPoint a -> AffinePoint
extendedToAffine' ExtendedPoint a
point2

-- | Zero in the extended coordinate space.
--
-- > affineZero = AffinePoint{x = 0, y = 1}
-- > extendedZero == affineToExtended affineZero
--
-- Note: [Extended coordinates]
extendedZero :: ExtendedPoint a
extendedZero :: ExtendedPoint a
extendedZero = $WExtendedPoint :: forall (groupMembership :: GroupMembership).
Integer
-> Integer -> Integer -> Integer -> ExtendedPoint groupMembership
ExtendedPoint {$sel:x:ExtendedPoint :: Integer
x = 0, $sel:y:ExtendedPoint :: Integer
y = 1, $sel:z:ExtendedPoint :: Integer
z = 1, $sel:t:ExtendedPoint :: Integer
t = 0}

-- | Check if a point is equivalent to zero.
--
-- jml is unsure, but this probably exists because it might be faster than
-- mapping to affine space and checking for equality.
--
-- Note: [Extended coordinates]
isExtendedZero :: ExtendedPoint irrelevant -> Bool
isExtendedZero :: ExtendedPoint irrelevant -> Bool
isExtendedZero ExtendedPoint{Integer
x :: Integer
$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x, Integer
y :: Integer
$sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y, Integer
z :: Integer
$sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z} = Integer
x Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0 Bool -> Bool -> Bool
&& Integer
y' Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
z' Bool -> Bool -> Bool
&& Integer
y' Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= 0
  where
    y' :: Integer
y' = Integer
y Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    z' :: Integer
z' = Integer
z Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

-- | Add two extended points.
--
-- The points don't have to be in the Ed25519 subgroup, and we can't say
-- anything about whether the result will be.
--
-- add-2008-hwcd-3
addExtendedPoints :: ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
addExtendedPoints :: ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
addExtendedPoints ExtendedPoint{$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x = Integer
x1, $sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y = Integer
y1, $sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z = Integer
z1, $sel:t:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
t = Integer
t1} ExtendedPoint{$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x = Integer
x2, $sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y = Integer
y2, $sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z = Integer
z2, $sel:t:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
t = Integer
t2} =
  $WExtendedPoint :: forall (groupMembership :: GroupMembership).
Integer
-> Integer -> Integer -> Integer -> ExtendedPoint groupMembership
ExtendedPoint{$sel:x:ExtendedPoint :: Integer
x = Integer
x3, $sel:y:ExtendedPoint :: Integer
y = Integer
y3, $sel:z:ExtendedPoint :: Integer
z = Integer
z3, $sel:t:ExtendedPoint :: Integer
t = Integer
t3}
  where
    -- X3 = (E*F) % Q
    x3 :: Integer
x3 = (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
f) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- Y3 = (G*H) % Q
    y3 :: Integer
y3 = (Integer
g Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- Z3 = (F*G) % Q
    z3 :: Integer
z3 = (Integer
f Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
g) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- T3 = (E*H) % Q
    t3 :: Integer
t3 = (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

    -- E = (B-A) % Q
    e :: Integer
e = (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- F = (D-C) % Q
    f :: Integer
f = (Integer
d' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
c) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- G = (D+C) % Q
    g :: Integer
g = (Integer
d' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
c) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- H = (B+A) % Q
    h :: Integer
h = (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
a) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

    -- A = ((Y1-X1)*(Y2-X2)) % Q
    a :: Integer
a = ((Integer
y1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x1) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
y2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x2)) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- B = ((Y1+X1)*(Y2+X2)) % Q
    b :: Integer
b = ((Integer
y1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
x1) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
y2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
x2)) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- C = T1*(2*d)*T2 % Q
    c :: Integer
c = (Integer
t1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
dConst) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
t2) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- D = Z1*2*Z2 % Q
    d' :: Integer
d' = (Integer
z1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* 2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z2) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

-- | Double an extended point.
--
-- dbl-2008-hwcd
doubleExtendedPoint :: ExtendedPoint preserving -> ExtendedPoint preserving
doubleExtendedPoint :: ExtendedPoint preserving -> ExtendedPoint preserving
doubleExtendedPoint ExtendedPoint{$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x = Integer
x1, $sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y = Integer
y1, $sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z = Integer
z1} =
  $WExtendedPoint :: forall (groupMembership :: GroupMembership).
Integer
-> Integer -> Integer -> Integer -> ExtendedPoint groupMembership
ExtendedPoint{$sel:x:ExtendedPoint :: Integer
x= Integer
x3, $sel:y:ExtendedPoint :: Integer
y = Integer
y3, $sel:z:ExtendedPoint :: Integer
z = Integer
z3, $sel:t:ExtendedPoint :: Integer
t = Integer
t3}
  where
    -- X3 = (E*F) % Q
    x3 :: Integer
x3 = (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
f) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- Y3 = (G*H) % Q
    y3 :: Integer
y3 = (Integer
g Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- Z3 = (F*G) % Q
    z3 :: Integer
z3 = (Integer
f Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
g) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- T3 = (E*H) % Q
    t3 :: Integer
t3 = (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
h) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

    -- E = (J*J-A-B) % Q
    e :: Integer
e = (Integer
j Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
j Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
b) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- F = (G-C) % Q
    f :: Integer
f = (Integer
g Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
c) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- G = (D+B) % Q
    g :: Integer
g = (Integer
d' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
b) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- H = (D-B) % Q
    h :: Integer
h = (Integer
d' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
b) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

    -- A = (X1*X1)
    a :: Integer
a = Integer
x1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x1
    -- B = (Y1*Y1)
    b :: Integer
b = Integer
y1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y1
    -- C = (2*Z1*Z1)
    c :: Integer
c = 2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z1
    -- D = (-A) % Q
    d' :: Integer
d' = (-Integer
a) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    -- J = (X1+Y1) % Q
    j :: Integer
j = (Integer
x1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
y1) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q

-- | Negate an extended point.
negateExtendedPoint :: ExtendedPoint preserving -> ExtendedPoint preserving
negateExtendedPoint :: ExtendedPoint preserving -> ExtendedPoint preserving
negateExtendedPoint ExtendedPoint{$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x = Integer
x1, $sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y = Integer
y1, $sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z = Integer
z1, $sel:t:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
t = Integer
t1} =
  $WExtendedPoint :: forall (groupMembership :: GroupMembership).
Integer
-> Integer -> Integer -> Integer -> ExtendedPoint groupMembership
ExtendedPoint{$sel:x:ExtendedPoint :: Integer
x= Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x1, $sel:y:ExtendedPoint :: Integer
y = Integer
y1, $sel:z:ExtendedPoint :: Integer
z = Integer
z1, $sel:t:ExtendedPoint :: Integer
t = Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
t1}

-- | Multiply a point (might be in the group, might not) by a scalar.
safeScalarMultiply :: Integer -> ExtendedPoint a -> ExtendedPoint a
safeScalarMultiply :: Integer -> ExtendedPoint a -> ExtendedPoint a
safeScalarMultiply n :: Integer
n = (ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
forall (a :: GroupMembership).
(ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
scalarMultiplyExtendedPoint ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
forall (a :: GroupMembership).
ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
addExtendedPoints Integer
n

-- | Scalar multiplication parametrised by addition.
scalarMultiplyExtendedPoint :: (ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a) -> Integer -> ExtendedPoint a -> ExtendedPoint a
scalarMultiplyExtendedPoint :: (ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
scalarMultiplyExtendedPoint _ 0 _    = ExtendedPoint a
forall (a :: GroupMembership). ExtendedPoint a
extendedZero
scalarMultiplyExtendedPoint add :: ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
add n :: Integer
n x :: ExtendedPoint a
x
  | Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
n    = ExtendedPoint a -> ExtendedPoint a
forall (preserving :: GroupMembership).
ExtendedPoint preserving -> ExtendedPoint preserving
doubleExtendedPoint ((ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
forall (a :: GroupMembership).
(ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
scalarMultiplyExtendedPoint ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
add (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` 2) ExtendedPoint a
x)
  | Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1    = ExtendedPoint a
x
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= 0    = Text -> ExtendedPoint a
forall a. HasCallStack => Text -> a
panic (Text -> ExtendedPoint a) -> Text -> ExtendedPoint a
forall a b. (a -> b) -> a -> b
$ "Unexpected negative multiplier: " Text -> Text -> Text
forall a. Semigroup a => a -> a -> a
<> Integer -> Text
forall a b. (Show a, ConvertText String b) => a -> b
show Integer
n
  | Bool
otherwise = ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
add ExtendedPoint a
x ((ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
forall (a :: GroupMembership).
(ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a)
-> Integer -> ExtendedPoint a -> ExtendedPoint a
scalarMultiplyExtendedPoint ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a
add (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- 1) ExtendedPoint a
x)


-- | Attempt to create a member of Ed25519 from an affine @y@ coordinate.
makeGroupMember :: Integer -> Either Error (Element Ed25519)
makeGroupMember :: Integer -> Either Error (Element Ed25519)
makeGroupMember y :: Integer
y = do
  ExtendedPoint 'Unknown
point <- AffinePoint -> ExtendedPoint 'Unknown
affineToExtended (AffinePoint -> ExtendedPoint 'Unknown)
-> Either Error AffinePoint
-> Either Error (ExtendedPoint 'Unknown)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Integer -> Integer -> Either Error AffinePoint
makeAffinePoint (Integer -> Integer
xRecover Integer
y) Integer
y
  let point8 :: ExtendedPoint 'Unknown
point8 = Integer -> ExtendedPoint 'Unknown -> ExtendedPoint 'Unknown
forall (a :: GroupMembership).
Integer -> ExtendedPoint a -> ExtendedPoint a
safeScalarMultiply 8 ExtendedPoint 'Unknown
point
  if ExtendedPoint 'Unknown -> Bool
forall (irrelevant :: GroupMembership).
ExtendedPoint irrelevant -> Bool
isExtendedZero ExtendedPoint 'Unknown
point8
    then Error -> Either Error (ExtendedPoint 'Member)
forall e (m :: * -> *) a. MonadError e m => e -> m a
throwError (Error -> Either Error (ExtendedPoint 'Member))
-> Error -> Either Error (ExtendedPoint 'Member)
forall a b. (a -> b) -> a -> b
$ ExtendedPoint 'Unknown -> Error
LowOrderPoint ExtendedPoint 'Unknown
point
    else ExtendedPoint 'Unknown -> Either Error (ExtendedPoint 'Member)
ensureInGroup ExtendedPoint 'Unknown
point8

{-
Note: [Arbitrary point generation]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This is cribbed from warner's notes in python-spake2:
<https://github.com/warner/python-spake2/blob/05b9f968d37dc5419f0e6e20c9b65737de21a7e9/src/spake2/ed25519_basic.py#L291>

* only about 50% of Y coordinates map to valid curve points
* even if the point is on our curve, it may not be in our particular (order=l) subgroup
  The curve has order 8*L, so an arbitrary point could have order 1,2,4,8,1*L,2*L,4*L,8*L
  (everything which divides the group order)
* 50% of random points will have order 8*L,
  25% will have order 4*L,
  13% order 2*L,
  13% will have our desired order 1*L
  (and a vanishingly small fraction will have 1/2/4/8).
* If we multiply any of the 8*L points by 2, we're sure to get an 4*L point
  (and multiplying a 4*L point by 2 gives us a 2*L point, and so on).
* Multiplying a 1*L point by 2 gives us a different 1*L point.
  So multiplying by 8 gets us from almost any point into a uniform point on the correct 1*L subgroup.
* We might still get really unlucky and pick one of the 8 low-order points.
  Multiplying by 8 will get us to the identity (Zero), which we check for explicitly.
* Double check that *this* point (8 * P) is in the right subgroup.

That final check is a Python assertion,
which would crash the program if incorrect.
For programming convenience, I just skip these values.

The 'order' of a point \(x\) is the number \(n\) such that:
'scalarMultiply group (integerToScalar group n) x == groupIdentity group'

Note this is different from the order of a /group/,
which for finite groups is the number of elements in the group.

-}

-- TODO: Document this
data AffinePoint
  = AffinePoint
  { AffinePoint -> Integer
x :: !Integer
  , AffinePoint -> Integer
y :: !Integer
  } deriving (AffinePoint -> AffinePoint -> Bool
(AffinePoint -> AffinePoint -> Bool)
-> (AffinePoint -> AffinePoint -> Bool) -> Eq AffinePoint
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: AffinePoint -> AffinePoint -> Bool
$c/= :: AffinePoint -> AffinePoint -> Bool
== :: AffinePoint -> AffinePoint -> Bool
$c== :: AffinePoint -> AffinePoint -> Bool
Eq, Int -> AffinePoint -> ShowS
[AffinePoint] -> ShowS
AffinePoint -> String
(Int -> AffinePoint -> ShowS)
-> (AffinePoint -> String)
-> ([AffinePoint] -> ShowS)
-> Show AffinePoint
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [AffinePoint] -> ShowS
$cshowList :: [AffinePoint] -> ShowS
show :: AffinePoint -> String
$cshow :: AffinePoint -> String
showsPrec :: Int -> AffinePoint -> ShowS
$cshowsPrec :: Int -> AffinePoint -> ShowS
Show)

-- | Construct an affine point that is on Curve25519.
makeAffinePoint :: Integer -> Integer -> Either Error AffinePoint
makeAffinePoint :: Integer -> Integer -> Either Error AffinePoint
makeAffinePoint x :: Integer
x y :: Integer
y
  | Integer -> Integer -> Bool
isOnCurve Integer
x Integer
y = AffinePoint -> Either Error AffinePoint
forall (f :: * -> *) a. Applicative f => a -> f a
pure $WAffinePoint :: Integer -> Integer -> AffinePoint
AffinePoint { $sel:x:AffinePoint :: Integer
x = Integer
x, $sel:y:AffinePoint :: Integer
y = Integer
y }
  | Bool
otherwise = Error -> Either Error AffinePoint
forall e (m :: * -> *) a. MonadError e m => e -> m a
throwError (Error -> Either Error AffinePoint)
-> Error -> Either Error AffinePoint
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Error
NotOnCurve Integer
x Integer
y
  where
    isOnCurve :: Integer -> Integer -> Bool
isOnCurve x' :: Integer
x' y' :: Integer
y' = ((-Integer
x') Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
y' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- 1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
dConst Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
x' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y' Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y') Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0

-- | Encode an 'AffinePoint' into bytes.
--
-- MSB of the output is whether or not @x@ is even (i.e. @x .&. 1@),
-- teh rest of the output is little-endian @y@.
encodeAffinePoint :: (ByteArray bytes, ByteArrayAccess bytes) => AffinePoint -> bytes
encodeAffinePoint :: AffinePoint -> bytes
encodeAffinePoint AffinePoint{Integer
x :: Integer
$sel:x:AffinePoint :: AffinePoint -> Integer
x, Integer
y :: Integer
$sel:y:AffinePoint :: AffinePoint -> Integer
y}
  | Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
x = Integer -> bytes
forall bytes. ByteArray bytes => Integer -> bytes
numberToLitteEndianBytes Integer
y
  | Bool
otherwise = Integer -> bytes
forall bytes. ByteArray bytes => Integer -> bytes
numberToLitteEndianBytes (Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift 1 255)

decodeAffinePoint :: (ByteArray bytes, ByteArrayAccess bytes) => bytes -> Either Error AffinePoint
decodeAffinePoint :: bytes -> Either Error AffinePoint
decodeAffinePoint bytes :: bytes
bytes =
  let unclamped :: Integer
unclamped = bytes -> Integer
forall bytes.
(ByteArray bytes, ByteArrayAccess bytes) =>
bytes -> Integer
littleEndianBytesToNumber bytes
bytes
      clamp :: Integer
clamp = Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift 1 255 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- 1
      y :: Integer
y = Integer
unclamped Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer
clamp
      x :: Integer
x = Integer -> Integer
xRecover Integer
y
      x' :: Integer
x' = if Integer
x Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. 1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
unclamped Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
.&. Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift 1 255 then Integer
x else Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x
  in Integer -> Integer -> Either Error AffinePoint
makeAffinePoint Integer
x' Integer
y


numberToLitteEndianBytes :: ByteArray bytes => Integer -> bytes
numberToLitteEndianBytes :: Integer -> bytes
numberToLitteEndianBytes n :: Integer
n = [Word8] -> bytes
forall a. ByteArray a => [Word8] -> a
ByteArray.pack ([Word8] -> [Word8]
forall a. [a] -> [a]
reverse (ByteString -> [Word8]
forall a. ByteArrayAccess a => a -> [Word8]
ByteArray.unpack (Integer -> ByteString
forall bytes. ByteArray bytes => Integer -> bytes
i2osp Integer
n :: ByteString)))

littleEndianBytesToNumber :: (ByteArray bytes, ByteArrayAccess bytes) => bytes -> Integer
littleEndianBytesToNumber :: bytes -> Integer
littleEndianBytesToNumber bytes :: bytes
bytes = ByteString -> Integer
forall bytes. ByteArrayAccess bytes => bytes -> Integer
os2ip ([Word8] -> ByteString
forall a. ByteArray a => [Word8] -> a
ByteArray.pack ([Word8] -> [Word8]
forall a. [a] -> [a]
reverse (bytes -> [Word8]
forall a. ByteArrayAccess a => a -> [Word8]
ByteArray.unpack bytes
bytes)) :: ByteString)

{-
Note: [Extended coordinates]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

jml only partly understands these. Here's that understanding.

The underlying elliptic curve is two-dimensional.
These are the AffinePoints.
We project that curve into a 4-dimensional space,
i.e. to the ExtendedPoints.

Doing so makes some of the arithmetic faster.
But ultimately, the values we are interested in are the affine points.

Thus, even if two ExtendedPoints have differing values internally,
they might be equivalent with respect to the Ed25519 group.

That is,
the affine points form a group
the extended points form a group
you can get a subgroup of the extended points group isomorphic to the affine points group
by using "maps to the same affine point" as an equivalence relation.

The Python version goes to some lengths to avoid doing calculations with zero.
In an earlier revision, I preserved that behaviour,
however, I have since removed it,
as we have no performance data,
and it adds extra complexity.

This URL might help:
http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
-}

affineToExtended :: AffinePoint -> ExtendedPoint 'Unknown
affineToExtended :: AffinePoint -> ExtendedPoint 'Unknown
affineToExtended AffinePoint{Integer
x :: Integer
$sel:x:AffinePoint :: AffinePoint -> Integer
x, Integer
y :: Integer
$sel:y:AffinePoint :: AffinePoint -> Integer
y} =
  $WExtendedPoint :: forall (groupMembership :: GroupMembership).
Integer
-> Integer -> Integer -> Integer -> ExtendedPoint groupMembership
ExtendedPoint
  { $sel:x:ExtendedPoint :: Integer
x = Integer
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
  , $sel:y:ExtendedPoint :: Integer
y = Integer
y Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
  , $sel:z:ExtendedPoint :: Integer
z = 1
  , $sel:t:ExtendedPoint :: Integer
t = (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
y) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
  }

extendedToAffine' :: ExtendedPoint a -> AffinePoint
extendedToAffine' :: ExtendedPoint a -> AffinePoint
extendedToAffine' ExtendedPoint{Integer
x :: Integer
$sel:x:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
x, Integer
y :: Integer
$sel:y:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
y, Integer
z :: Integer
$sel:z:ExtendedPoint :: forall (groupMembership :: GroupMembership).
ExtendedPoint groupMembership -> Integer
z} =
  case Integer -> Integer -> Either Error AffinePoint
makeAffinePoint Integer
x' Integer
y' of
    Left err :: Error
err -> Text -> AffinePoint
forall a. HasCallStack => Text -> a
panic (Text -> AffinePoint) -> Text -> AffinePoint
forall a b. (a -> b) -> a -> b
$ "Could not make affine point: " Text -> Text -> Text
forall a. Semigroup a => a -> a -> a
<> Error -> Text
forall a b. (Show a, ConvertText String b) => a -> b
show Error
err
    Right r :: AffinePoint
r -> AffinePoint
r
  where
    x' :: Integer
x' = (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer
inv Integer
z) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q
    y' :: Integer
y' = (Integer
y Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer
inv Integer
z) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
q